SpecValley: Aggregation as Spectral Valley in Dense Heterophilic Graphs
Organizations: Mercedes-Benz AG, Sindelfingen · Department of Computer Science University of Konstanz
Abstract
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
| Model | Cost per forward pass |
|---|---|
| ChebNet | |
| + ChebNet | |
| SpecValley |
| 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 |
| 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 |
| 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 |
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 |
| Squirrel-f | Chameleon-f | Crocodile | Actor | Tolokers | HM-cat. | |
| ChebNet | ||||||
| Selected | 4 | 2 | 40 | 2 | 8 | 25 |
| Score | 40.37 | 40.05 | 75.72 | 36.86 | 85.88 | 65.78 |
| Score at | 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 | ||||||
| Dataset | Nodes | Time/epoch (s) | Split @ 150 ep. | Split @ 1000 ep. | |
|---|---|---|---|---|---|
| Ablation setting: 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 |
Node Classification
Node classification assigns labels to graph entities by combining their features with information from connected nodes and graph structure.
See all 109 papers