Many graphs that matter in practice come with no useful information about their nodes. Bitcoin wallets, internet routers, and anonymized accounts have only who-connects-to-whom. A graph neural network (GNN), a model that updates each node by averaging messages from its neighbors, must then build node descriptions from structure alone. It typically does this with positional encodings, which are coordinates computed from the graph's eigenvectors. Two problems sit on top of this. First, neighbor averaging assumes homophily, meaning that connected nodes tend to share a label. When the graph is heterophilous, meaning that connected nodes tend to differ, as with fraudsters transacting with victims, averaging blurs exactly the distinctions we need. Second, on a graph that changes over time, the degree of homophily can itself drift or flip abruptly. The Elliptic Bitcoin graph shows such a shock at time step 43, when a darknet market closed and every model collapsed (Anti-Money Laundering in Bitcoin).
We propose a single scalar per time step that lets a topology-only GNN flip its filter into its spectral mirror image when homophily reverses. The flip turns a smoothing filter into a sharpening one. The scalar is set at test time without labels or node features, by checking how predictions from a two-hop-only channel agree across one-hop edges. In two sentences, the idea is this. Split a polynomial graph filter into even-hop and odd-hop parts, and note that negating the odd part gives exactly the same filter reflected across the spectrum. Then estimate, from the shift-robust even-hop channel alone, whether direct edges currently connect like or unlike nodes, and set the sign of the odd part accordingly.
Core Claim
A polynomial filter on a normalized propagation matrix $P_t$ at time $t$ can be written as
$$ h_\theta(P_t; s_t) = \sum_{k} \theta_{2k} P_t^{2k} + s_t \sum_{k} \theta_{2k+1} P_t^{2k+1}, $$
where $\theta$ are learned coefficients and $s_t \in [-1, 1]$ is a per-snapshot gate. With $s_t = 1$ this is the trained filter. With $s_t = -1$ it equals $h_\theta(-P_t; 1)$, the same frequency response mirrored, so a learned low-pass filter becomes high-pass. The filter is applied to structural encodings $Z_t$ rather than to node features.
The claim has three parts. When homophily reverses, the right correction is this reflection and not retraining. In the feature-free regime the reflection can be set label-free, from the even-hop channel. A single learned $\theta$ plus a time-varying $s_t$ should then track a drifting graph better than any fixed filter, including the even-only filter.
Over-smoothing, the collapse of node representations to a common value as averaging is repeated, enters as a constraint and a diagnostic. When the inputs are eigenvector encodings, each eigenvector is simply rescaled by the filter's response at its eigenvalue. Over-smoothing and heterophily failure therefore become the same measurable event: the label-carrying frequencies get attenuated. This makes concrete, in the topology-only setting, the shared-root-cause argument of Two Sides of the Same Coin.
Relation to Prior Work
The proposal reuses its structural inputs from two papers. Understanding and Improving Laplacian Positional Encodings For Temporal GNNs builds encodings from a supra-Laplacian. This is the Laplacian of a graph that stacks snapshots and links each node to its own copy in adjacent snapshots, so that eigenvectors stay consistent over time. The paper computes them cheaply with iterative solvers, reporting up to a 56× speedup. We adopt these encodings as $Z_t$, but that work never considers heterophily or depth. Graph Neural Networks can Recover the Hidden Features Solely from the Graph Structure shows that structure alone can recover latent coordinates, raising feature-stripped Cora from 12.2% to 67.1%. Its random-walk construction is low-pass, however, and its guarantees need dense graphs. Our reflection is designed for the case where that low-pass assumption is wrong.
Two papers motivate the gap. Progressive Graph Structure Adjustment for Homophily Shift Adaptation adapts to homophily shift using agreement between a GNN and an attributes-only multilayer perceptron, a plain network that ignores the graph. Without attributes, that validator has nothing to look at. A Label-Free Heterophily-Guided Approach for Unsupervised Graph Fraud Detection likewise measures heterophily from attribute disparity. Our even-hop channel takes the role of the validator using structure only.
One paper supplies the key mechanism. EvenNet keeps only even powers of $P$, motivated by "the enemy of my enemy is my friend." It stays above 75% on synthetic graphs trained homophilic and tested heterophilic, while learnable full-polynomial filters drop to near random. EvenNet then simply discards the odd hops and pays for it on clean homophilic graphs. We keep the odd hops, use the even channel to decide their sign, and so aim to recover what EvenNet loses.
Three papers constrain the design. AdaSpec proves that without features, a spectral filter can distinguish nodes only as finely as the graph has distinct eigenvalues. This is why we add random-landmark distance encodings to break symmetry. Complete the Missing Half and Geometric Scattering Attention Networks mix low- and high-pass channels, but their high-pass difference signals need informative features. Their mixing weights are also fixed after training rather than reset per snapshot. GReTo uses signed messages for dynamic heterophily, but it targets regression with observed signals and cannot run on unattributed graphs.
Research Program
The model has three parts.
The first part is the inputs. For each snapshot $t$ we compute supra-Laplacian encodings over a sliding window, using the iterative solver from Frasca et al. We concatenate in- and out-degree and shortest-path distances to a small set of random landmark nodes, which break eigenvalue ties.
The second part is a two-channel polynomial filter of low order, with $K \le 4$ hops, followed by a small classifier. The even channel is trained jointly with the full model, and also as a stand-alone predictor $g$.
The third part sets the gate. At each unlabeled snapshot we take nodes where $g$ is confident and estimate edge homophily $\hat h_t$ as the fraction of edges among these nodes whose endpoints share a predicted label. We then set $s_t = 2\hat h_t - 1$. For more than two classes, sign agreement is replaced by a predicted class-compatibility matrix in the spirit of Graph Neural Networks with Heterophily, and the odd channel is re-weighted per class pair.
During training, $s_t$ is set from the true homophily of each labeled snapshot. The filter coefficients $\theta$ therefore learn a response that is correct "up to reflection."
The analysis makes three predictions, each checked directly. First, for two-class stochastic block graphs, a confident even-hop predictor gives a consistent estimate of $h_t$ whenever two-hop neighborhoods are label-aligned. This alignment holds under both strong homophily and strong heterophily by the balance argument, and fails near $h_t = 0.5$. In that regime the odd channel carries little signal anyway, so the estimation error does the least harm there. Second, as $K$ grows, the representations' effective rank and label-frequency energy decay. Third, this decay is slower under the correct $s_t$ than under the wrong one.
Baselines
The naive reference point is a two-layer GCN, a standard graph convolutional network, on the same structural encodings with no adaptation. It shows how much any filter design matters beyond the encodings.
The strongest non-graph competitor is a random forest on per-snapshot structural statistics: degrees, PageRank, clustering, two-hop counts, and the same encodings. A random forest was the best model on Elliptic with features, reaching illicit F1 = 0.788 against EvolveGCN's 0.720 and Skip-GCN's 0.705 (Anti-Money Laundering in Bitcoin). These numbers use the 166 handcrafted features, so we report them as an upper reference and not as a target. There is no reported result found on Lacuna for any model on topology-only Elliptic, so we establish that baseline ourselves.
The strongest graph competitors are EvenNet (the $s_t \equiv 0$ special case), a learnable full polynomial filter trained once ($s_t \equiv 1$), EvolveGCN, and Ordered GNN. All are run on the same encodings. Ordered GNN reports 62.44% on Squirrel and 89.10% on Cora at 64 layers, both with features. It is the strongest depth-robust heterophily model in the file.
We also run PSAHS with encodings in place of attributes. This tests our claim that its validator degrades without attributes.
All methods share the same encodings, the same temporal split, and the same hyperparameter-trial budget with identical seeds. Beating a baseline means a higher mean illicit F1 over test steps, or higher accuracy on the drifting synthetic graphs, across at least five seeds with non-overlapping confidence intervals.
The key ablation compares an oracle gate set from the true $h_t$ with the estimated gate. This isolates the label-free estimator from the reflection itself.
Why not just…?
Why not just use EvenNet everywhere? This is the real threat. EvenNet is already robust to homophily reversal and costs less. Its weakness, documented by its authors, is lost accuracy on clean homophilic graphs. On directed transaction flows it also discards the direct one-hop payment link. Our drifting benchmark includes long homophilic stretches, where the gate should beat EvenNet, and heterophilic stretches, where it should match it. If the gate never measurably beats EvenNet, we will report that keeping odd hops is not worth the added machinery.
Why not just fit a learnable polynomial filter once? EvenNet's synthetic results show such filters collapse to near-random when homophily flips between training and test. This is exactly the failure that a reflection gate fixes without retraining. Comparing $s_t \equiv 1$ with the estimated $s_t$ isolates this.
Why not just use a random forest on structural statistics? On featured Elliptic the forest won, and the same could happen without features. Two things distinguish our model. First, the forest cannot change how it uses neighbors after a structural shock. Second, all models in that paper broke at step 43. We therefore compare performance specifically on steps 43–49. If the forest still wins, the conclusion is that topology-only GNNs add nothing on sparse transaction graphs. This is plausible given that Sato's guarantees need density.
Why not just retrain on each new snapshot? Test-time labels are unavailable in the realistic Elliptic protocol. Retraining with labels serves as an oracle ceiling, not a competitor.
Proposed Experiments
The first setting is a synthetic test. We use a dynamic contextual stochastic block model with features removed, whose homophily drifts smoothly from 0.9 to 0.1 and also jumps abruptly. The decisive check is that the estimated gate's accuracy curve tracks the oracle gate's. It must also beat both the fixed full filter and EvenNet when averaged over the whole trajectory. As a second check, the estimated $\hat h_t$ must correlate with the true $h_t$ except near 0.5.
The second setting is Elliptic with all 166 features stripped. We train on steps 1–34, test on steps 35–49, and report illicit F1 overall and on steps 43–49. Because test labels exist for evaluation, we also report the correlation between $\hat h_t$ and the measured illicit–licit edge homophily. We expect this to be the hardest setting, because the graph is very sparse.
The third setting is a static stress test: Texas, Chameleon, Squirrel, and Cora with features removed. Here we sweep depth $K$ and measure effective rank and label-frequency energy. This tests whether the correct reflection slows the collapse.
As a sanity check, the backbone must reproduce supra-Laplacian encoding behavior on the dynamic graphs CanParl, as733, dblp, and enron10. Frasca et al. report that these encodings were best in 70.8% of their cases.
The proposal is falsified if either of two things happens. One is that the estimated gate fails to approach the oracle gate on synthetic drift. The other is that it yields no gain over EvenNet on any real setting.
References
- Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics
- Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks
- Understanding and Improving Laplacian Positional Encodings for Temporal GNNs
- Graph Neural Networks can Recover the Hidden Features Solely from the Graph Structure
- Progressive Graph Structure Adjustment for Homophily Shift Adaptation
- A Label-free Heterophily-guided Approach for Unsupervised Graph Fraud Detection
- EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks
- AdaSpec: Adaptive Spectrum for Enhanced Node Distinguishability
- Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
- Geometric Scattering Attention Networks
- GReTo: Remedying dynamic graph topology-task discordance via target homophily
- Graph Neural Networks with Heterophily
- Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing