Node classification in heterophilic graphs remains an open problem: aggregating over neighbourhoods can damp precisely the part of the signal that carries the labels. The field has answered with ever more expressive propagation operators, leaving the aggregation step that precedes them fixed by degree normalisation. However, degree normalisation acts as a spectral valley in its own right, attenuating a fixed middle band whose position at lambda equal 1 is set by the normalisation rather than by the data, exactly where the eigenvalues of dense graphs accumulate. We therefore begin with the representations rather than the propagation, in two stages: a learnable aggregation followed by an ordinary spectral filter. The first, SpecValley learns the position, sharpness and flank gains of the valley for every graph. We show formally how the aggregation operator and downstream filter interact. We establish that the response 1 minus lambda of degree normalisation vanishes exactly at that accumulation point. A spectral energy budget shows that what aggregation removes from a band, no linear spectral filter can recover. Crowding alone says nothing about the benefit. That is decided by how much label energy the valley removes, which we measure for every graph. SpecValley achieves strong results across heterophilic benchmarks, and a controlled ablation over aggregation operators and downstream filters attributes the gain to aggregation rather than the filter.
Figures & tables
Figure 1: Overview of SpecValley. Top: node features first pass an aggregation stage and then an ordinary spectral filter (ChebNet, Eq. ( 5 )), which predicts the node labels. Bottom: A more detailed visualization of the aggregation stage. On dense graphs the eigenvalues of the normalised Laplacian accumulate at λ=1 (grey histogram) and degree normalisation acts there as the fixed response 1−λ , a valley whose zero is pinned by the normalisation rather than by the data (Proposition 4.1 ). SpecValley replaces it by a response whose centre, sharpness and flank gains are learned per graph (Eq. ( 3 )), so that the attenuated band can be placed away from the modes that carry the label energy.
Model
Cost per forward pass
ChebNet
C0
Psym + ChebNet
C0+O(sd′)
SpecValley
C0+O(n2d′)+O(n3)∗
Table 1: Complexity; C0 covers the input projection and the ChebNet layers. ∗ Once per graph.
Dataset
Nodes
Edges
Features
Classes
Degree
Squirrel-f ∗
2.2K
94K
2.1K
5
42
Chameleon-f ∗
0.9K
14K
2.3K
5
31
Actor ∗
7.6K
30K
932
5
8
Crocodile ∗
11.6K
360K
13.2K
5
62
Tolokers
11.8K
519K
10
2
88
HM-categories
46.6K
21.5M
120
21
923
Table 2: Dataset statistics. ∗ : 48/32/20 train/val/test split; Tolokers: 50/25/25; HM-categories: 10/10/80 (GraphLand RL split). Squirrel-f and Chameleon-f denote the node-deduplicated filtered variants from ( Platonov et al., 2023 ) .
Filt.
Aggr.
Squirrel ∗
Chameleon ∗
Actor
Crocodile
Tolokers ∗∗
HM-cat.
APPNP
none
36.2 ± 1.4
37.6 ± 2.2
36.0 ± 0.6
69.7 ± 0.7
76.9 ± 1.1
37.7 ± 0.7
sym
33.4 ± 1.1
42.5 ± 2.5
24.9 ± 1.0
75.7 ± 0.4
75.4 ± 0.7
53.1 ± 0.4
mean
33.5 ± 0.8
42.4 ± 3.3
25.1 ± 0.7
76.5 ± 0.5
73.4 ± 0.7
51.4 ± 1.4
attn init
33.9 ± 1.7
43.8 ± 2.8
24.9 ± 0.6
76.0 ± 0.6
73.2 ± 0.8
53.5 ± 0.7
attn
34.3 ± 0.8
42.3 ± 2.2
24.9 ± 0.6
75.8 ± 0.6
75.4 ± 0.8
54.4 ± 0.1
valley
39.9 ± 2.0
40.4 ± 3.0
34.8 ± 0.8
74.0 ± 0.8
80.6 ± 0.8
59.3 ± 0.9
Table 3: All combinations of aggregation operator and downstream filter. Accuracy (%), mean ± 95% CI over 10 splits, HM-categories over 3 seeds. ∗ node-deduplicated variant of Platonov et al. (2023) ; ∗∗ ROC-AUC. All runs 150 epochs. Bold marks the best value per dataset, underline the best per filter; colour compares each operator with none under the same filter ( better , worse ).
Rank
Squirrel ∗
Chameleon ∗
Actor
1
SpecValley
45.1
± 2.1
SpecValley
43.8
± 3.1
MUSE
38.6
± 1.3
2
NLSFs
42.7
± 1.7
NLSFs
42.5
± 1.5
GloGNN
37.7
± 1.4
3
FAGCN
41.1
± 2.3
FAGCN
41.9
± 2.7
GGCN
37.5
± 1.6
4
GCN
39.5
± 1.5
ResNet+SGC
41.0
± 4.5
SpecValley
35.7
± 0.9
Rank
Crocodile
Tolokers ∗∗
HM-cat.
1
SpecValley
77.2
± 0.5
Polynorm.-r
85.9
± 0.7
SpecValley
69.7
± 1.2
Table 4: SpecValley vs. the three strongest reported baselines per dataset as published. Accuracy (%), mean ± 95% CI over 10 splits, HM-categories over 3 seeds. ∗∗ ROC-AUC, ∗ node-deduplicated ( Platonov et al., 2023 ) , over 1k epochs. On Crocodile the baselines are self-supervised, so the results are indicative rather than strictly comparable.
Figure 2: Label energy across the Laplacian spectrum (top) and the filter magnitude ∣g(λ)∣ of degree normalisation and of SpecValley (bottom), for two dense graphs. Quantities are defined in the text; the remaining four graphs are in Appendix C.2 .
Figure 3: Robustness and filter order. (a,b) Edges and features removed progressively, SpecValley with ChebNet. (c) Polynomial order K of the ChebNet layer with and without the valley aggregator, all six graphs. (d) The same sweep on Squirrel-f for four aggregation operators. Three splits (one on HM-categories), 150 epochs.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
Split
Repeats
Metric
Selection
Squirrel-f
48/32/20, random
10
Accuracy
validation epoch
Chameleon-f
48/32/20, random
10
Accuracy
validation epoch
Crocodile
48/32/20, random
10
Accuracy
validation epoch
Actor
48/32/20, random
10
Accuracy
validation epoch
Tolokers
50/25/25, official
10
ROC-AUC
validation epoch
HM-categories
10/10/80, official
1 split, 3 seeds
Accuracy
validation epoch
Appendix
Table 5: Evaluation protocol. Splits are stored once and reused across all models and measurements. The epoch is always selected on the validation set.
Squirrel-f
Chameleon-f
Crocodile
Actor
Tolokers
HM-cat.
ChebNet
Selected K
4
2
40
2
8
25
Score
40.37
40.05
75.72
36.86
85.88
65.78
Score at K=5
38.96
35.63
72.56
35.66
85.57
56.90
Δ
+1.41
+4.42
+3.16
+1.20
+0.31
+8.88
SpecValley
Appendix
Table 6: Polynomial order K of the ChebNet layer in the benchmark, for ChebNet alone and for SpecValley, from a 150-epoch sweep. Scores are test accuracy (ROC-AUC on Tolokers) at K selected on the validation score and at K=5 , taken at the epoch with the best validation score and averaged over the sweep splits; Δ is the difference between the two.
Dataset
Nodes
K
Time/epoch (s)
Split @ 150 ep.
Split @ 1000 ep.
Ablation setting: K=5 on every graph
Chameleon-f
890
5
0.073
11.1 s
73.4 s
Squirrel-f
2,223
5
0.084
12.6 s
84.1 s
Actor
7,600
5
0.073
10.9 s
72.7 s
Crocodile
11,631
5
0.216
32.6 s
3.6 min
Tolokers
11,758
5
0.176
26.4 s
2.9 min
Appendix
Table 7: Training time of SpecValley on a single NVIDIA RTX 3060 (12 GB). The ablation trains for 150 epochs with K=5 , the benchmark for 1000 epochs with the per-dataset order of Table 6 ; the eigendecomposition is computed once per graph and excluded.
Figure 4: Label energy across the Laplacian spectrum (top) and magnitude of the fixed and learned aggregation responses (bottom) for all six graphs.
Figure 5: Polynomial order K of the ChebNet layer, with and without the valley aggregator. Test score at the epoch with the best validation score, averaged over three splits (one on HM-categories), 150 epochs per order.
Graphs with heterophily, where adjacent nodes carry different labels, are prevalent in real-world applications, from social networks to molecular interactions. However, existing spectral Graph Neural Network (GNN) approaches tailored for heterophilous graph classification suffer from hub-dominated (node with large degree) aggregation and oversmoothing, as their suboptimal polynomial filters introduce approximation errors and blend distant signals. To address the degree-biased aggregation and suboptimal polynomial filtering, we introduce a Hierarchical Multi-view HAAR (HMH), a novel spectral graph-learning framework that scales in near-linear time . HMH first learns feature- and structure-aware signed affinities via a heterophily-aware encoder, then constructs a soft graph hierarchy guided by these embeddings. At each hierarchical level, HMH constructs a sparse, orthonormal, and locality-aware Haar basis to apply learnable spectral filters in the frequency domain. Finally, skip-connection unpooling layers combine outputs from all hierarchical levels back into the original graph, effectively preventing hub domination and long-range signal bottleneck (over-squashing). Experimentation shows that HMH outperforms state-of-the-art spectral baselines, achieving up to a 3% improvement on node classification and 7% points on graph classification datasets, all while maintaining linear scalability.
Md Sazzad Hossen, Avimanyu Sahoo
University of Alabama in Huntsville, Huntsville, AL, USA.
It is well established that spectral graph neural networks (GNNs) can universally approximate node signals; however, their expressive power remains bounded by the 1-dimensional Weisfeiler-Lehman test, which is mirrored in their lack of universality for higher-order signals. To go beyond this bound, we propose the Full-Spectrum GNNs (FSpecGNNs), a second-order generalization of classical spectral GNNs. FSpecGNN advances spectral filtering from two perspectives: (1) it lifts signals from the node domain to the node-pair domain; and (2) it extends the univariate spectral filter over eigenvalues to a bivariate filter over eigenvalue pairs. We show that classical spectral GNNs arise as a diagonal special case of FSpecGNNs, and prove that FSpecGNNs can be at most as expressive as Local 2-GNN while universally approximating node-pair signals, the latter being particularly beneficial for heterophilic graph learning. Moreover, FSpecGNN admits scalable implementations that avoid explicit node-pair-level computations; combined with a low-rank approximation that reduces full-spectrum convolution to a combination of polynomial spectral filters, it enables learning on large graphs. Empirically, FSpecGNN validates the predicted expressivity and delivers strong performance on heterophilic benchmarks.
Xiaohan Wang, Deyu Bo, Longlong Li +1
Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore.
Graph condensation aims to produce a small surrogate graph that preserves the downstream node-classification performance of a much larger original graph. Existing methods rely on Weisfeiler-Lehman neighbourhood aggregation or gradient-based distribution matching, both of which assume that adjacent nodes share the same label, an assumption that breaks down under heterophily. We propose HERALD (High-fidelity Exemplar Retrieval with Adaptive Landmark Distillation), a gradient-free graph condensation framework that adapts the node scoring and feature selection in the condensation pipeline to the graph's measured heterophily. HERALD selects features via a joint Fisher-discriminability and activation-density criterion that down-weights aggregated representations on heterophilic graphs, and scores nodes by a weighted combination of prototype representativeness, decision-boundary proximity, and Local Intrinsic Dimensionality (LID), where the weights are driven by a smooth sigmoid function of the heterophily ratio. Nodes are then assembled into a condensed subgraph through score-ordered BFS expansion, Personalised PageRank pruning, and class rebalancing, all at an identical storage budget to BONSAI, enabling direct comparison. Experiments on eight benchmark datasets spanning homophilic and heterophilic settings show that HERALD matches or outperforms state-of-the-art condensers on heterophilic graphs and remains competitive on homophilic ones across four GNN architectures.
Sujan Chakraborty, Priyanka Saha, Saptarshi Bej
School of Data Science, Indian Institute of Science Education and Research Thiruvananthapuram, Thiruvananthapuram, 695551, Kerala, India