How can knowing about some categories help us to dis- cover new ones in unlabeled images? Unsupervised visual category discovery is useful to mine for recurring objects without human supervision, but existing methods assume no prior information and thus tend to perform poorly for cluttered scenes with multiple objects. We propose to lever- age knowledge about previously learned categories to en- able more accurate discovery. We introduce a novel object- graph descriptor to encode the layout of object-level co- occurrence patterns relative to an unfamiliar region, and show that by using it to model the interaction between an image’s known and unknown objects we can better de- tect new visual categories. Rather than mine for all cat- egories from scratch, our method identifies new objects while drawing on useful cues from familiar ones. We eval- uate our approach on benchmark datasets and demonstrate clear improvements in discovery over conventional purely appearance-based baselines.