PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2610.36696v1cs.LGcs.AI

TL;DR

Heterophilous graph GCD must recognize known classes and discover novel ones despite unreliable homophily cues and no novel-class supervision. HeteGCD combines attribute and neighborhood statistics in a dual-prototype framework, achieving the best average All and New ranks across five graphs. The reported evaluation is transductive, with known-class labels used for validation and selection.

  • Problem

    Graph GCD must recognize known classes and discover novel ones, but homophily-based methods can receive misleading neighborhood evidence and heterophilous methods lack novel-class feedback for signal selection.

    Source: §1 · p. 1

  • Method

    HeteGCD combines node attributes and local attribute-difference statistics in a gated encoder, then uses feature prototypes and neighborhood-distribution prototypes for category assignment.

    Source: §1 · p. 2

  • Results

    HeteGCD achieves the best average ranks in All and New accuracy across five heterophilous graphs against 24 baseline combinations; its average All rank is 3.80 versus 7.80 for both runners-up.

    Source: §1 · p. 2, §6.2 · p. 7

  • Takeaways & Limitations

    The authors offer HeteGCD as a pioneering and effective baseline for heterophilous graph GCD and further exploration of open-world settings.

    Source: §7 · p. 8

    The evaluation is transductive with known total category count, and hyperparameter and checkpoint selection use only known-class validation labels.

    Source: §3 · p. 2

Abstract

from arXiv · show

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.

1 Introduction

Heterophilous graph GCD must handle unreliable homophily cues and the absence of novel-class labels. HeteGCD combines attribute and neighborhood statistics for discovery and achieves the best average All and New ranks across five graphs.

1 Introduction

  • Homophily-based graph GCD methods can receive misleading neighborhood evidence, while heterophilous methods lack novel-class feedback to select and combine signals.The resulting question is how to use heterogeneous neighborhood information for discovery without novel-class supervision.Source: §1 · pp. 1–2
  • HeteGCD uses a gated dual-stream encoder for attributes and local attribute differences, then combines feature-prototype similarity with neighborhood-distribution consistency.Neighborhood distributions and their prototypes are estimated from evolving soft assignments over known and novel classes without novel-class labels.Source: §1 · p. 2
  • HeteGCD achieves the best average ranks in All and New accuracy across five heterophilous graphs against 24 baseline combinations.It remains in the top six on every dataset, while each baseline ranks 13th or lower on at least one.Source: §1 · p. 2
  • The study presents the first systematic examination of generalized category discovery on heterophilous graphs, focusing on unreliable homophily priors and unavailable novel-class supervision.Source: §1 · p. 2

2 Related Work

Prior graph GCD methods incorporate topology but often use neighborhood agreement, while heterophilous graph learning offers diverse signals whose selection and fusion remain challenging without novel-class supervision.

2.1 Generalized Category Discovery

  • Visual GCD methods use contrastive representation learning followed by semi-supervised k-means or joint self-distillation and entropy regularization; graph GCD adds topology.SWIRL applies graph contrastive learning, while POWN and TopoNC use prototype learning or neighborhood consensus for pseudo-labeling.Source: §2.1 · p. 2
  • Neighborhood-consensus discovery relies on agreement between connected nodes, which can be unreliable when heterophilous graphs have frequent cross-class edges.Source: §2.1 · p. 2

2.2 Learning on Heterophilous Graphs

  • Heterophilous graph methods exploit attributes, multiple hops, adaptive fusion, filtering, channel mixing, interaction types, geometry, global relations, and adjacency.Source: §2.2 · p. 2
  • Neighborhood class distributions can capture similar neighborhood compositions across same-class nodes, but existing methods mainly use them for propagation or representation learning.HeteGCD instead uses these distributions for category assignment in probability space, without novel-class supervision to guide signal selection and fusion.Source: §2.2 · p. 2

3 Problem Formulation

The paper formulates transductive node-level generalized category discovery on an attributed graph. Training labels cover every known category and no novel categories, while unlabeled nodes may belong to either group.

3 Problem Formulation

  • The graph is undirected and attributed, with node attributes represented by rows of X and a row-normalized adjacency matrix without self-loops.Isolated nodes have zero rows in the adjacency matrix.Source: §3 · p. 2
  • The labeled set contains examples from every known category and none from novel categories; the unlabeled set contains both, and must be assigned to known or novel categories.Source: §3 · p. 2
  • The setting is transductive with known total category count K; all node features and edges are available, but training labels are restricted to the labeled set.Hyperparameter and checkpoint selection use only held-out known-class validation labels.Source: §3 · p. 2

4 Motivation and Observations

The section tests whether raw attributes, local attribute-difference statistics, and neighborhood class distributions retain category information. It uses these observations to motivate combining signals in embedding and probability spaces.

4 Motivation and Observations

  • The analysis evaluates category information using class separation against a shuffled-label baseline and leave-one-out nearest-prototype balanced accuracy.Heatmaps show within- and between-class similarity.Source: §4 · pp. 2–3

4.1 Node Attributes

  • Raw attributes show positive geometry excess, above-chance LOO balanced accuracy, and higher average similarity within than between categories on all five datasets.These observations support retaining raw attributes as a direct source of category information.Source: §4.1 · p. 3, Figure 2 · p. 3

4.2 Local Attribute-Difference Statistics

  • Local attribute differences show positive geometry excess, above-chance LOO balanced accuracy, and higher average within-category similarity on all five datasets.The statistic is R = X − AX.Source: §4.2 · p. 3, Figure 3 · p. 3

4.3 Neighborhood Class Distribution Statistics

  • On four of five datasets, fused 1- and 2-hop distributions outperform either hop in LOO accuracy, while neither hop consistently dominates across datasets.The relative usefulness of 1-hop and 2-hop distributions varies by dataset.Source: Figure 4 · p. 4, §4.3 · p. 4
  • Across tested random-label noise levels, fused distributions retain category separability on four of five datasets.The corruption randomly assigns incorrect labels to a fraction of unlabeled nodes per class.Source: Figure 5 · p. 4, §4.3 · p. 4
  • Four of five datasets retain category separability across evaluated novel-to-known assignment-bias levels.In this setting, corrupted novel-class nodes receive known-class labels.Source: Figure 6 · p. 4, §4.3 · p. 4

4.4 Design Implications

  • The design embeds node attributes and local differences, while matching neighborhood class distributions to distribution prototypes in probability space.The distributions retain category semantics in their coordinates.Source: §4.4 · pp. 4–5

5 Method

HeteGCD combines node attributes and local attribute-difference statistics in a gated encoder, then uses feature prototypes and neighborhood-distribution prototypes for category assignment. Training jointly optimizes representations and assignments using classification and contrastive objectives.

5.1 Gated Dual-Stream Encoder

  • The gated dual-stream encoder combines node attributes and mean signed attribute differences from neighbors, with a node-wise gate controlling their contribution.A separate projector supports contrastive learning, while classification operates directly on the encoder embeddings.Source: §5.1 · p. 5

5.2 Dual-Prototype Classifier

  • The dual-prototype classifier combines feature-based similarity with consistency between neighborhood distributions and category-specific distribution prototypes.Feature prototypes are optimized by gradient descent; distribution prototypes are periodically estimated from soft assignments.Source: §5.2 · p. 5

5.2.1 Feature Prototype Matching.

  • Feature prototypes are initialized by constrained k-means on clean embeddings, keeping labeled nodes in known slots while unlabeled nodes can use all K slots.The prototypes are then optimized jointly with the encoder.Source: §5.2.1 · p. 5

5.2.2 Distribution Prototype Construction and Matching.

  • Neighborhood distributions average stored soft assignments over exact 1- and 2-hop neighbors, and category prototypes average those distributions weighted by center-node soft memberships.These soft-assignment-based prototypes cover known and novel categories without novel-class labels.Source: §5.2.2 · p. 5

5.2.3 Score Fusion.

  • Distribution-based consistency averages total-variation similarities across available hops, then combines the scores with feature scores using a training-adjusted weight before softmax.The distribution scores are shared across views and detached during score fusion.Source: §5.2.2 · p. 5, §5.2.3 · p. 5

5.3 Joint Training and Inference

  • Joint training applies contrastive objectives to projected embeddings and classification objectives to fused scores; inference predicts from the fused scores on the unaugmented graph.Training includes supervised cross-entropy, self-distillation, and mean-entropy maximization; distribution scores are introduced after warm-up and refreshed every five epochs.Source: §5.3 · pp. 5–6

6 Experiments

Experiments on five heterophilous graphs compare HeteGCD with 24 encoder–discovery combinations and examine performance, learned representations, distribution prototypes, component contributions, and loss-weight sensitivity. HeteGCD achieves the best average All and New accuracy ranks across datasets.

6.1 Experimental Setup

  • The evaluation uses five heterophilous graphs, five frozen class partitions and node splits, and 24 combinations of eight encoders with three discovery frameworks.Each setting has ⌊K/2⌋ known classes; hyperparameter and checkpoint selection use known-class validation labels.Source: §6.1 · pp. 6–7

6.2 Main Results

  • HeteGCD ranks best on average for All (3.80 versus 7.80) and New accuracy (5.40 versus 8.60), remains top-six/top-eight across datasets, and beats MLP+SimGCD in All on all five.The evaluation compares 25 methods over five settings; lower average rank is better.Source: Table 1 · p. 7, §6.2 · p. 7

6.3 Embedding Space Visualization

  • Figure 8 shows tighter within-category groups and clearer separation between known and novel categories after training.The t-SNE visualization distinguishes known-class nodes with cool colors and novel-class nodes with warm colors.Source: Figure 8 · p. 7, §6.3 · p. 7

6.4 Quality of Distribution Prototypes

  • Figure 9’s estimated prototypes follow ground-truth distribution peaks at 1-hop and broader shapes at 2-hop for known and novel categories.This agreement indicates that the prototypes encode category-level neighborhood composition.Source: Figure 9 · p. 8, §6.4 · p. 8

6.5 Component Ablation

  • Preserving X improves mean All accuracy on all three ablation datasets by up to 16.88 points; other component gains vary by dataset and metric.Removing AX raises Roman Empire All by 5.19 points, while distribution prototypes raise Flickr New by 1.79 and BlogCatalog Old by 2.00 points.Source: Table 2 · p. 8, §6.5 · p. 8

6.6 Sensitivity to Loss Weights

  • Moderate increases in λ improve Old and All accuracy, while larger values can reduce New accuracy; increasing ε helps All accuracy, especially novel discovery on Flickr.Further ε increases continue to improve Flickr New and All accuracy, but gains level off or slightly decline on BlogCatalog and Roman Empire; selected values use known-class validation labels and need not maximize New or All accuracy.Source: §6.6 · p. 8, Figure 10 · p. 8, Figure 11 · p. 8

7 Conclusion

The paper extends heterophilous graph learning to generalized category discovery and presents HeteGCD as a baseline for this setting. Experiments on five heterophilous graphs demonstrate its effectiveness.

7 Conclusion

  • HeteGCD combines statistical analysis, a gated dual-stream encoder, and a dual-prototype classifier, and is offered as a baseline for heterophilous graph GCD.The authors hope this work encourages further exploration of heterophilous graph learning in open-world settings.Source: §7 · p. 8

A Training and Inference

Algorithm 1 describes HeteGCD’s training and inference procedure, including neighborhood definitions and the timing of refreshed distribution scores. Refreshed scores take effect in the next epoch.

A Training and Inference

  • Algorithm 1 defines exact r-hop neighborhoods on the original graph and applies refreshed distribution scores in the following epoch.R_i,k indexes available hops for node i and category slot k; V_r contains nodes with nonempty r-hop neighborhoods.Source: A Training and Inference · p. 9

B.1 Datasets and Node Splits

The appendix summarizes the graph datasets and split construction, the HeteGCD training and inference algorithm, and how difficulty-based settings are selected.

B.1 Datasets and Node Splits

  • The algorithm initializes feature prototypes by constrained clustering, trains on two augmented views, refreshes neighborhood-distribution prototypes, and predicts unlabeled nodes by their highest score.The two views use feature masking and edge dropping; refreshed distribution scores are used by the selected network on the clean graph.Source: §B.1 · p. 10
  • The datasets are Roman Empire, filtered Chameleon, Actor, BlogCatalog, and Flickr; the first five splits are used for the first three, while the latter two use five fixed, class-stratified splits.Roman Empire uses the first five official 50/25/25 splits, Actor the first five supplied 48/32/20 splits, and Chameleon its first five official splits. BlogCatalog and Flickr use five fixed, class-stratified 60/20/20 splits per graph.Source: §B.1 · p. 10

B.2 Difficulty-Based Settings

  • Candidate class partitions are ranked by cross-group connectivity and novel-to-known feature-centroid proximity, then selected across easy, intermediate, and hard regimes.The selected partitions are paired with fixed node splits.Source: §B.2 · p. 10

C Observation Methodology

The appendix evaluates category information in node attributes and neighborhood class distributions using class-separation and leave-one-out measures. It also tests corrupted assignments and compares 1-hop with 2-hop neighborhood signals.

C.1.1 Class Separation.

  • Attribute signals are compared with cosine distance using between-class prototype distance B and within-class distance W; the ratio G measures separation, adjusted against shuffled-label references.One hundred class-size-preserving label shuffles provide the reference; positive geometry excess indicates stronger category structure than random grouping.Source: §C.1.1 · p. 10, §C.1 · p. 10

C.1.2 Leave-One-Out Balanced Accuracy.

  • Leave-one-out balanced accuracy excludes each evaluated node from its class prototype and averages correctness within classes, then equally across classes.The plots show percentages, with chance at 1/K.Source: §C.1.2 · p. 10

C.2.1 Class Separation.

  • Neighborhood class distributions encode neighbor-category composition at 1 and 2 hops; class separation replaces attribute vectors and prototypes with these distributions and uses total variation distance.For fused distributions, each comparison averages the 1-hop and 2-hop distances; shuffled-label references are subtracted as for attribute signals.Source: §C.2 · p. 10, §C.2.1 · pp. 10–11

C.2.2 Leave-One-Out Balanced Accuracy.

  • Neighborhood-distribution leave-one-out evaluation excludes each node from its class prototype at each hop and follows the balanced-accuracy procedure.Clean-observation plots show balanced accuracy as a percentage; noise plots show gain over chance in percentage points, where zero is chance-level.Source: §C.2.2 · p. 11

C.2.3 Random Assignment Noise.

  • Random assignment noise corrupts a fraction of unlabeled nodes within each true class with uniformly sampled incorrect categories, then rebuilds distributions and evaluates against true categories.Scores average five settings and 20 repetitions; the class-separation baseline also averages 100 geometry ratios per setting and noise level.Source: §C.2.3 · p. 11

C.2.4 Novel-to-Known Assignment Bias.

  • Novel-to-known assignment bias models novel-class nodes being assigned to known categories while selected known-class nodes receive the same incorrect assignments as under random noise.Distributions, prototypes, and metrics are recomputed as in the random-noise evaluation.Source: §C.2.4 · p. 11, §C.2.3 · p. 11

C.3 Separate 1-Hop and 2-Hop Observations

  • Neither 1-hop nor 2-hop neighborhood distributions consistently dominate across datasets, motivating joint use of both ranges.Figures 12 and 13 show separate hop-range results and class-pair heatmaps, complementing the fusion analysis in Figure 4.Source: §C.3 · p. 11, Figure 12 · p. 11, Figure 13 · p. 11

D Baseline Methods

The baselines combine graph encoders with category-discovery frameworks, alongside graph adaptations and shared selection and tuning procedures. The section describes encoder and framework choices and specifies how models are evaluated and selected.

D Baseline Methods

  • The 24 baselines combine eight encoders with three category-discovery frameworks, which learn from encoder representations and produce category assignments.Encoders extract node representations; frameworks learn from them and assign categories.Source: D Baseline Methods · p. 12

D.1 Graph Encoders

  • The encoder set spans feature-only MLP, conventional neighborhood-aggregating GCN, deep GCNII with initial-feature residuals and identity mappings, heterophily-oriented H2GCN, separately encoded attribute/adjacency LINKX, and multi-scale FSGNN.Source: §D.1 · p. 12
  • The remaining encoders include ACM-GCN's node-wise channel mixing and GAMMA's adaptive multi-hop aggregation with node-specific hop weights.GAMMA uses 0-, 1-, and 2-hop signals with two routing iterations.Source: §D.1 · p. 12

D.2 Category Discovery Frameworks

  • The discovery frameworks include clustering-based GCD, parametric SimGCD, and graph-GCD GGCD, which uses graph-structure regularization and auxiliary semi-supervised clustering.GCD uses contrastive learning and semi-supervised K-means with labeled assignments fixed to known classes; SimGCD uses contrastive learning, supervised classification, cross-view self-distillation, and entropy maximization.Source: §D.2 · p. 12

D.3 Graph Adaptation and Encoder Integration

  • Graph adaptation uses feature masking and undirected edge dropping for two graph views, while each encoder is trained to produce embeddings that replace a pretrained image backbone.Edge dropping is disabled for MLP and fixed-support H2GCN; a projection head maps embeddings to contrastive features, with discovery objectives and predictions remaining framework-specific.Source: §D.3 · p. 12

E.1 Epoch Selection

  • Model selection uses known-class validation accuracy without Hungarian matching, selecting the latest epoch from epoch 20 onward that reaches at least 97% of the candidate maximum.Novel-class validation labels are unavailable for selection or tuning, and every run trains for 200 epochs.Source: §E.1 · p. 12

E.2 Hyperparameter Search

  • Each method–dataset pair receives an independent 100-trial Optuna study, and the best completed configuration is rerun across all five settings for final evaluation.The search objective averages validation scores at selected epochs over the five settings.Source: §E.2 · p. 12, Table 4 · p. 12
Loading 2610.36696v1…