# Spectral Flow Certificates for Depth-Aware Long-Range Propagation in Graph Neural Networks

arXiv: https://arxiv.org/abs/2607.21607 · HTML: https://mlsanity.com/paper/2607.21607/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 28 references that are in the map.
- First posted on arXiv 16 May 2026.

## Builds on (most cited first, 21 of 21)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Graph-Coupled Oscillator Networks](https://mlsanity.com/paper/2202.02296/) (2022)
- [MagNet: A Neural Network for Directed Graphs](https://mlsanity.com/paper/2102.11391/) (2021)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [DiffWire: Inductive Graph Rewiring via the Lov'asz Bound](https://mlsanity.com/paper/2206.07369/) (2022)
- [How does over-squashing affect the power of GNNs?](https://mlsanity.com/paper/2306.03589/) (2023)
- [Spectral Graph Pruning Against Over-Squashing and Over-Smoothing](https://mlsanity.com/paper/2404.04612/) (2024)
- [Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification](https://mlsanity.com/paper/2506.16110/) (2025)
- [Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction](https://mlsanity.com/paper/2401.15603/) (2024)
- [Large-Scale Spectral Graph Neural Networks via Laplacian Sparsification: Technical Report](https://mlsanity.com/paper/2501.04570/) (2025)

## Abstract (arXiv)

Graph Neural Networks propagate information through local message passing, but the graph topologies themselves can silently prevent any amount of training from solving long-range tasks. When we deploy GNNs on new graphs, there is currently no inexpensive way to know, before training begins, whether the graphs' structures will allow information to travel far enough between distant nodes. We address this gap by proposing Spectral Flow Certificates (SFCs), single scalars computed from the graphs' normalised Laplacians in seconds, requiring no model training and no labelled data. An SFC fuses a graph's algebraic connectivity with the chosen message-passing depth into one number that measures how much of the critical spectral bottleneck can be traversed within the available depth budget. Unlike raw spectral gaps, which are static and depth-agnostic, SFCs adapt as the number of layers increases and therefore carry strictly more diagnostic information when depths vary. Compared with classical structural statistics such as average effective resistance and graph diameter, SFCs explain more than twice as much variance in trained GNN long-range accuracy. Across twenty-five synthetic graph families spanning paths, cycles, grids, regular graphs, and random graphs, SFCs predict trained accuracy before any gradients are computed, achieving explanatory power above ninety percent at all tested depths. The same predictive relationships hold on one hundred fifty real molecular graph topologies drawn from three independent benchmark datasets, confirming that the findings are not artefacts of their synthetic construction. Taken together, these results show that a single eigenvalue computation is sufficient to flag topology-limited graphs before committing to expensive training pipelines, providing a principled first filter for GNN deployments.