HeteGCD: Statistics-Aware Dual-Prototype Learning for Generalized Category Discovery on Heterophilous Graphs

Xuanzhi Xi; Tongze Zhang; Zhili Qin; Yulin Tao; Hongliang Wang; Zhong Zhang; Qinli Yang; Junming Shao

cs.LGOct 27, 2026

HeteGCD: Statistics-Aware Dual-Prototype Learning for Generalized Category Discovery on Heterophilous Graphs

Authors: Xuanzhi Xi, Tongze Zhang, Zhili Qin, Yulin Tao, Hongliang Wang, Zhong Zhang, Qinli Yang, Junming Shao

Organizations: University of Electronic Science and Technology of China, China

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.

Figures & tables

Panel of Figure 1 — 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.

Panel of Figure 2 — 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.

Panel of Figure 3 — 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.

Panel of Figure 4 — 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-d_{\mathrm{TV}}$ , 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.

Panel of Figure 5 — Figure 5. Fused 1+2-hop distributions retain category information on four of five datasets across the tested noise levels. A fraction $\rho$ 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.

Panel of Figure 6 — 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 $h_{i}$ . Matching $h_{i}$ to trainable feature prototypes $c_{k}$ yields scores $F$ in embedding space. Current soft assignments $q_{i}^{t}$ update memories $\bar{q}_{i}^{t}$ by exponential moving average. Averaging these memories over exact $r$ -hop neighbors estimates neighborhood class distributions $n_{i}^{(r)}$ , $r=1,2$ . In probability space, distribution prototype $\pi_{k}^{(r)}$ is their weighted mean (illustrated for $k=2$ ), with weight $\bar{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 $\mathcal{L}_{\mathrm{cls}}$ , while projected embeddings $z_{i}$ support contrastive loss $\mathcal{L}_{\mathrm{rep}}$ . 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
Variant	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.

Panel of Figure 10 — Figure 10. Sensitivity to the supervised weight $\lambda$ . Lines show mean test accuracy over five settings, and shaded bands indicate $\pm 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.

Panel of Figure 11 — Figure 11. Sensitivity to the MeMax weight $\varepsilon$ . 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.

Panel of Figure 12 — 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.

Panel of Figure 13 — 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	$\mathrm{LogU}[10^{-4},10^{-2}]$
Weight decay	$\{0,10^{-6},10^{-5},3\!\times\!10^{-5},$ $10^{-4},3\!\times\!10^{-4},10^{-3}\}$
Contrastive batch size	$\{1024,2048,4096\}$
Supervised weight $\lambda$	$\mathrm{U}[0.1,0.9]$
MeMax weight $\varepsilon$	$\{0.5,1,2,4\}$
InfoNCE temperature	$\mathrm{LogU}[0.05,1.5]$

Appendix

Table 4. Hyperparameter search space for HeteGCD. U and LogU denote uniform and log-uniform sampling.

Generalized Category Discovery

Generalized category discovery learns known classes from labeled examples while grouping unlabeled data into known and previously unseen categories.

See all 26 papers

Generalized Category Discovery in Federated Graph Learning
May 5, 2026Zhongzheng Yuan, Lianshuai Guo, Xunkai Li +2Federated Graph Learning Federated Learning
Shandong University, School of Airspace Science and Engineering, Weihai 264209, China · Beijing Institute of Technology, School of Computer Science and Technology, Beijing 100081, China
Inductive Subgraphs as Shortcuts: Causal Disentanglement for Heterophilic Graph Learning
Apr 21, 2026Xiangmeng Wang, Qian Li, Haiyang Xia +3Disentangled Representation Learning Graph Neural Networks
Curtin University Perth, Australia · The Education University of Hong Kong New Territories, Hong Kong
Graph Neural Network leveraging Higher-order Class Label Connectivity for Heterophilous Graphs
Jun 5, 2026Takuto Takahashi, Itsuki Nakayama, Takahiro Mitani +3Graph Neural Networks Node Classification
The University of Osaka, 1-5 Yamadaoka, Suita, Osaka, Japan

May 5, 2026J/K move · Enter open · S save

Generalized Category Discovery in Federated Graph Learning

Zhongzheng Yuan, Lianshuai Guo, Xunkai Li, Wenyu Wang+1

Shandong University, School of Airspace Science and Engineering, Weihai 264209, China · Beijing Institute of Technology, School of Computer Science and Technology, Beijing 100081, China

Federated Graph Learning Federated Learning Generalized Category Discovery

Open paper AskPDF arXiv

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.

Abstract

Generalized Category Discovery

Explore similar work

Generalized Category Discovery in Federated Graph Learning

Inductive Subgraphs as Shortcuts: Causal Disentanglement for Heterophilic Graph Learning

Graph Neural Network leveraging Higher-order Class Label Connectivity for Heterophilous Graphs