New method improves category discovery on graphs with diverse connections
HeteGCD: Statistics-Aware Dual-Prototype Learning for Generalized Category Discovery on Heterophilous Graphs
Machine LearningArtificial Intelligence
Summary
Graphs often connect things that are very different from each other, which makes it hard for computer programs to organize and discover new groups correctly. This paper presents a new approach called HeteGCD that looks at both the differences in connected items' features and how their categories are distributed nearby to learn better. By combining these two views, the method can better understand and identify both known and new categories on these tricky graphs. The authors tested their method on five different graphs and showed it works well compared to many existing methods.
What this means in practice
- •For data scientists: Classify and discover new groups in networks where connected entities are often different, improving analysis of complex graph data.
- •For social network analysts: Better identify emerging communities or user groups on social networks with diverse and dissimilar connections.
Authors
Xuanzhi Xi, Tongze Zhang, Zhili Qin, Yulin Tao, Hongliang Wang, Zhong Zhang, Qinli Yang, Junming Shao
Abstract
Heterophilous graphs are prevalent in real-world applications, where connected nodes often exhibit dissimilar attributes or belong to different classes, posing significant challenges to conventional graph learning methods based on homophily. This limitation becomes particularly pronounced in generalized category discovery (GCD), which requires models to recognize known classes and discover novel ones using labels from known classes only. However, existing graph GCD methods typically rely on aforementioned homophily-based inductive biases, which are ill-suited to heterophilous graphs. Meanwhile, although current heterophilous graph learning methods exploit diverse neighborhood signals, their selection and fusion are often guided by supervision across all classes, including novel classes whose labels are unavailable in GCD. These limitations raise a key question: how can heterogeneous neighborhood information be effectively leveraged for category discovery without any novel-class supervision? To answer this question, in this study we propose HeteGCD, a new statistics-aware dual-prototype learning perspective for generalized category discovery on heterophilous graphs. The key idea is to examine both statistics of local attribute differences and neighborhood class distribution to extract discriminative information in feature and probability spaces simultaneously. Specifically, a gated dual-stream encoder integrates both node attributes and local attribute-difference statistics to learn informative node representations. Afterwards, a dual-prototype classifier combines feature-based similarity with distribution-based consistency to support category discovery. Experiments on five heterophilous graphs show that HeteGCD achieves competitive performance against 24 baseline combinations.