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.
Figures & tables
Figure 1. GCD on Heterophilous Graphs. Only a subset of known-class nodes is labeled, while unlabeled nodes include both known and novel classes. Two panels show the same heterophilous graph with four known-class nodes, five novel-class nodes, two same-class edges, and nine cross-class edges. Panel a uses red dashed cross-class edges, gray solid same-class edges, and inequality signs beside the target node's three cross-class edges. Panel b uses gray edges. Two labeled known-class nodes are solid and carry labels A and B. The other known-class nodes have pale fills and question marks; novel-class nodes have white fills, colored outlines, light hatching, and question marks. The shared legend has two independently spaced rows of three items, with equally sized example nodes: known classes, novel classes, cross-class edge, labeled known, unlabeled known, and unlabeled novel. Colors indicate true classes only for illustration.
Figure 2. Raw node attributes X retain category information across all five datasets. (a) Class separation above the shuffled-label baseline. (b) Leave-one-out nearest-prototype balanced accuracy. Triangles mark chance levels. (c–e) Mean cosine similarity between node pairs, grouped by class. Five panels show class geometry, leave-one-out assignment, and three heatmaps ordered Flickr, BlogCatalog, Roman Empire from left to right. Every heatmap has an independent vertical colorbar on the right and excludes node self-pairs.
Figure 3. Local attribute-difference statistics X−AX retain category information across all five datasets. (a) Class separation above the shuffled-label baseline. (b) LOO balanced accuracy. Triangles mark chance levels. (c–e) Mean cosine similarity between local difference vectors, grouped by class. Five panels show class geometry, leave-one-out assignment, and three heatmaps ordered Flickr, BlogCatalog, Roman Empire from left to right. Every heatmap has an independent vertical colorbar on the right and excludes node self-pairs.
Figure 4. Combining 1-hop and 2-hop distributions gives higher LOO accuracy than either hop on four of five datasets. (a,b) Class separation and LOO balanced accuracy. Triangles mark chance levels. (c–e) Mean node-pair similarity 1−dTV , averaged across hops and grouped by class. Five panels show geometry, leave-one-out separability, and class-pair heatmaps for fused one- and two-hop neighborhood class distributions. The heatmaps run Flickr, BlogCatalog, Roman Empire from left to right, with independent vertical colorbars.
Figure 5. Fused 1+2-hop distributions retain category information on four of five datasets across the tested noise levels. A fraction ρ of unlabeled nodes per class receives random incorrect labels. (a) Class separation. (b) LOO balanced-accuracy gain over chance (percentage points). Random wrong-class noise: geometry excess and LOO gain over chance for Flickr, BlogCatalog, Roman Empire, Chameleon, and Actor. Separate plots share dataset colors and markers; all classes are evaluated with fused one- and two-hop neighborhood class distributions.
Figure 6. Four of five datasets retain category information under novel-to-known assignment bias. Corrupted novel-class nodes receive known-class labels. Other settings and measurements follow Figure 5 . Novel-to-known assignment bias: geometry excess and LOO gain over chance for Flickr, BlogCatalog, Roman Empire, Chameleon, and Actor. Separate plots share dataset colors and markers; all classes are evaluated with fused one- and two-hop neighborhood class distributions.
Figure 7. Overview of HeteGCD. A gated dual-stream encoder integrates node attributes X and local attribute-difference statistics X−AX into embeddings hi . Matching hi to trainable feature prototypes ck yields scores F in embedding space. Current soft assignments qit update memories qˉit by exponential moving average. Averaging these memories over exact r -hop neighbors estimates neighborhood class distributions ni(r) , r=1,2 . In probability space, distribution prototype πk(r) is their weighted mean (illustrated for k=2 ), with weight Qˉik denoting node i ’s probability of belonging to class k . Total-variation similarities to these prototypes, averaged across hops, yield consistency scores D . Fused scores S support classification loss Lcls , while projected embeddings zi support contrastive loss Lrep . The upper panel shows two independent MLP streams for node attributes and local attribute-difference statistics, their combined embeddings, a contrastive projector, trainable feature prototypes in embedding space, score fusion, and the loss branches. The lower panel updates the soft-assignment memory, estimates neighborhood class distributions over disjoint exact one- and two-hop neighborhoods, and pools these distributions into category-specific distribution prototypes in probability space. Matching node distributions to these prototypes yields total-variation distances, which are converted to detached distribution-based consistency scores.
Method
Roman Empire
Chameleon
Actor
BlogCatalog
Flickr
Summary
Encoder
Old
New
All
Rk.
Old
New
All
Rk.
Old
New
All
Rk.
Old
New
All
Rk.
Old
New
All
Rk.
Avg. Rank
Overall Rank
GCD
MLP
60.89
30.92
45.58
14
46.14
33.68
38.53
8
35.21
29.01
31.78
2
95.16
48.97
72.03
4
92.37
13.55
48.73
11
7.80
2.5
GCN
34.50
17.98
24.52
23
49.32
30.37
38.50
9
20.44
30.48
27.61
22
73.03
45.07
59.12
11
69.33
34.86
50.29
8
14.60
16
GCNII
71.55
27.01
48.68
6
45.80
26.66
35.91
21
23.43
24.07
25.93
25
97.02
67.66
82.32
2
90.91
28.54
56.36
4
11.60
12
H2GCN
52.87
28.81
40.61
19
46.38
27.28
34.99
25
33.64
23.76
28.43
20
83.32
22.08
52.66
12
88.26
26.08
53.83
6
16.40
18.5
LINKX
58.29
32.90
45.03
15
44.54
33.41
40.06
2
33.84
26.64
29.88
16
97.09
25.45
61.15
9
92.41
27.58
56.51
3
9.00
5
Table 1. Mean test accuracy (%) of 25 methods over five settings. Rk. ranks methods by All accuracy within each dataset. Avg. Rank averages these ranks and determines Overall Rank (lower is better). Light orange, light blue, and light cyan indicate the three best distinct values per column, respectively. HeteGCD achieves the best overall rank.
Figure 8. t-SNE visualization of node embeddings before and after training on BlogCatalog. Cool colors denote known-class nodes, and warm colors denote novel-class nodes. Two t-SNE panels show all 5,196 nodes at epochs 0 and 200. The trained representation exhibits more concentrated category groups and clearer separation.
Figure 9. Neighborhood class distributions for a known and a novel class on BlogCatalog at 1-hop and 2-hop. Orange shows the displayed class’s ground-truth distribution, while blue shows its estimated distribution prototype. Four probability-distribution panels compare ground truth and distribution prototypes for known class 3 and novel class 2. The 1-hop and 2-hop TV distances are 0.113 and 0.157 for the known class, and 0.125 and 0.165 for the novel class.
Variant
Flickr
BlogCatalog
Roman Empire
Old
New
All
Old
New
All
Old
New
All
w/o X
83.50
14.30
45.17
80.87
32.18
56.40
62.57
30.45
48.06
w/o X−AX
95.18
23.91
55.71
97.60
49.40
73.41
56.45
30.07
44.79
w/o distribution
95.00
21.10
54.09
95.56
51.03
73.26
70.82
31.90
52.47
Ours (Full)
95.41
22.89
55.28
97.56
49.13
73.28
63.52
31.14
49.99
Avg. Imp.
+4.19
+3.12
+3.62
+6.22
+4.93
+5.59
+0.24
+0.34
+1.55
Table 2. Component ablation results with mean test accuracy (%) over five settings. Avg. Imp. averages Full-minus-ablation differences (pp). Bold marks column maxima.
Figure 10. Sensitivity to the supervised weight λ . Lines show mean test accuracy over five settings, and shaded bands indicate ±1 standard deviation. Dashed vertical lines mark the selected values. Three separate line plots show Old, New, and All test accuracy against lambda on Flickr, BlogCatalog, and Roman Empire. Old accuracy initially improves. At larger lambda, New accuracy declines on Flickr and BlogCatalog, while it varies less on Roman Empire.
Figure 11. Sensitivity to the MeMax weight ε . The plotting conventions follow Figure 10 . Three separate line plots show Old, New, and All test accuracy against the MeMax weight. Increasing epsilon from zero to two improves mean All accuracy on all three datasets. Further increases have dataset-dependent effects.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
Nodes
Edges
Features
Classes
Old Classes
New Classes
labeled ratio (%)
Edge Homophily
Roman Empire
22,662
32,927
300
18
9
9
10.05–29.51
0.047
Chameleon
890
8,854
2,325
5
2
3
16.40–19.55
0.236
Actor
7,600
26,659
932
5
2
3
14.21–23.76
0.217
BlogCatalog
5,196
171,743
8,189
6
3
3
29.08–30.81
0.401
Flickr
7,575
239,738
12,047
9
4
5
26.27–27.29
0.239
Appendix
Table 3. Dataset statistics. Labeled ratio gives the minimum–maximum percentage of nodes with training labels across five settings. Edge homophily is the fraction of edges connecting nodes of the same class.
Figure 12. Exact 1-hop neighborhood class distributions. Five panels show geometry, leave-one-out separability, and class-pair heatmaps for 1-hop neighborhood class distributions. The heatmaps run Flickr, BlogCatalog, Roman Empire from left to right, with independent vertical colorbars.
Figure 13. Exact 2-hop neighborhood class distributions. Five panels show geometry, leave-one-out separability, and class-pair heatmaps for 2-hop neighborhood class distributions. The heatmaps run Flickr, BlogCatalog, Roman Empire from left to right, with independent vertical colorbars.
Parameter
Search space
Learning rate
LogU[10−4,10−2]
Weight decay
{0,10−6,10−5,3×10−5,10−4,3×10−4,10−3}
Contrastive batch size
{1024,2048,4096}
Supervised weight λ
U[0.1,0.9]
MeMax weight ε
{0.5,1,2,4}
InfoNCE temperature
LogU[0.05,1.5]
Appendix
Table 4. Hyperparameter search space for HeteGCD. U and LogU denote uniform and log-uniform sampling.
Federated Graph Learning (FGL) enables collaborative learning over distributed graph data, yet existing approaches largely rely on a closed-world assumption, limiting their applicability in dynamic environments where novel categories continuously emerge. To bridge this gap, we target the practical scenario of Federated Graph Generalized Category Discovery (FGGCD), aiming to collaboratively discover novel categories across decentralized graph clients while retaining knowledge of known categories. We observe that FGGCD introduces two fundamental challenges: (1) the Neighborhood Absorption Effect, where structural fragmentation leads to biased neighborhood aggregation, causing novel nodes to be misclassified as known categories; and (2) Global Semantic Inconsistency, where the aforementioned local biases propagate to the server and are amplified by heterogeneous subgraph distributions, hindering cross-client knowledge integration. To address these issues, we propose GCD-FGL, an FGL framework for GCD that integrates a client-side Topology-Reliable Semantic Alignment and Discovery process to mitigate the neighborhood absorption effect, and a server-side Hierarchical Prototype Alignment strategy to resolve global semantic inconsistency. Extensive experiments on five real-world graph datasets demonstrate that GCD-FGL consistently outperforms state-of-the-art baselines, achieving an average absolute gain of +4.86 in HRScore.
Zhongzheng Yuan, Lianshuai Guo, Xunkai Li +2
Shandong University, School of Airspace Science and Engineering, Weihai 264209, China · Beijing Institute of Technology, School of Computer Science and Technology, Beijing 100081, China
Heterophily is a prevalent property of real-world graphs and is well known to impair the performance of homophilic Graph Neural Networks (GNNs). Prior work has attempted to adapt GNNs to heterophilic graphs through non-local neighbor extension or architecture refinement. However, the fundamental reasons behind misclassifications remain poorly understood. In this work, we take a novel perspective by examining recurring inductive subgraphs, empirically and theoretically showing that they act as spurious shortcuts that mislead GNNs and reinforce non-causal correlations in heterophilic graphs. To address this, we adopt a causal inference perspective to analyze and correct the biased learning behavior induced by shortcut inductive subgraphs. We propose a debiased causal graph that explicitly blocks confounding and spillover paths responsible for these shortcuts. Guided by this causal graph, we introduce Causal Disentangled GNN (CD-GNN), a principled framework that disentangles spurious inductive subgraphs from true causal subgraphs by explicitly blocking non-causal paths. By focusing on genuine causal signals, CD-GNN substantially improves the robustness and accuracy of node classification in heterophilic graphs. Extensive experiments on real-world datasets not only validate our theoretical findings but also demonstrate that our proposed CD-GNN outperforms state-of-the-art heterophily-aware baselines.
Xiangmeng Wang, Qian Li, Haiyang Xia +3
Curtin University Perth, Australia · The Education University of Hong Kong New Territories, Hong Kong
Node classification in graph neural networks (GNNs) has been widely applied in various fields of graph analysis. GNNs achieve high-accuracy node classification in homophilous graphs, where nodes with the same class label tend to be connected. However, their performance remains limited in heterophilous graphs, where nodes with different class labels are more likely to be connected. In particular, current GNNs derived from graph convolutional networks cannot capture higher-order class label connectivity, which is frequently observed in real-world heterophilous graphs. To address this issue, we propose a novel classifier, Label Context Classifier (LCC), designed to capture higher-order class label connectivity in directed graphs. LCC estimates the class label of a target node by leveraging label context embeddings that are generated through four distinct types of walks. In addition, our approach allows the integration of LCC and any GNN by adaptively learning their importance. Experimental results demonstrate that GNNs integrated with LCC outperform SOTA methods and the label context embeddings improve the node classification performance in heterophilous directed graphs.