Balancing graph connections and geometric anchors to discover new categories

What is it about?

Many real-world datasets, from citation networks to online communities, are graphs: items are connected as well as described by their own features. In generalized category discovery, an AI system receives labels for only a few nodes from known categories and must both recognize those categories and discover new ones among the remaining nodes. A useful geometric strategy is to give every known or new category a fixed target in the representation space, with these targets arranged as far apart as possible. These maximally separated anchors provide clear and equally spaced destinations for learning. On a graph, however, message passing pulls connected nodes closer together. Too much of this topological smoothing blurs category boundaries, while forcing nodes too strongly toward separate anchors can damage meaningful neighborhood structure. We call this the topology-geometry tension. TopoNC resolves this tension by separating graph-based smoothing from node-specific feature learning and adaptively combining them for each node. It also uses agreement among neighboring nodes to decide which provisional category assignments are reliable enough to guide nodes toward the anchors. Across six benchmark graphs, TopoNC achieved the highest accuracy for both new categories and all categories among the compared methods.

Featured Image

Photo by Alina Grubnyak on Unsplash

Photo by Alina Grubnyak on Unsplash

Why is it important?

Existing category-discovery methods are largely designed for independent samples such as images. Simply transferring their geometric objectives to graphs overlooks the tension between local connectivity and global category separation. TopoNC makes this tension the central design problem. Fixed, maximally separated anchors - technically, Simplex ETF prototypes - define an unambiguous global geometry, while graph topology helps determine which local assignments can be trusted. The dual-stream encoder and node-wise gate prevent either force from dominating, and topology-conditioned provisional labelling extends reliable supervision to unlabelled nodes. This matters because real citation, social, e-commerce, and biological networks continually contain categories not seen during training. On six benchmarks, TopoNC achieved the highest new-category and overall accuracy on every dataset; on Amazon-Photo, new-category accuracy was 19.36 percentage points above the next-best result. More broadly, the work shows that topology can guide, rather than obstruct, neural collapse on graphs.

Perspectives