Long-range graph tasks are challenging for Graph Neural Networks (GNNs): global mechanisms such as attention or rewiring schemes can be computationally expensive, while deep local propagation is prone to vanishing gradients, oversmoothing, and oversquashing. The introduced mu-ChebNet architecture is a simple spectral GNN that learns a node-wise weight function mu before applying ChebNet-style filters. The learned weighting mu induces a modified graph Laplacian which effectively changes the propagation geometry without altering the graph topology. This task-dependent geometry promotes preferred routes for information propagation, thereby helping long-range signals avoid highly contractive bottlenecks, and obviating the need for repeated layer stacking. In practice, we replace the fixed graph Laplacian L by a learned operator L_mu, keeping the proposed mu-ChebNet architecture lightweight while making propagation task-adaptive. Furthermore, we provide a spectral analysis demonstrating how mu modulates propagation dynamics, and empirically observe improved performance on both synthetic long-range reasoning tasks and real-world graph benchmarks. The learned weight function is not only interpretable, but also offers a lightweight alternative to attention and rewiring for adaptive graph propagation.
Figures & tables
Figure 1
Figure 2: Minimal two-community graph.
Table 3
Model
Diameter ↓
SSSP ↓
Eccentricity ↓
GCN
0.7424±0.0466
0.9499±0.0001
0.8468±0.0028
GAT
0.8221±0.0752
0.6951±0.1499
0.7909±0.0222
GraphSAGE
0.8645±0.0401
0.2863±0.1843
0.7863±0.0207
GIN
0.6131±0.0990
−0.5408±0.4193
0.9504±0.0007
GCNII
0.5287±0.0570
−1.1329±0.0135
0.7640±0.0355
DGC
0.6028±0.0050
0.1483±0.0231
0.8261±0.0032
Table 3: Mean test set log10(MSE) and standard deviation averaged over 4 random weight initializations for each configuration on the Graph Property Prediction dataset. The lower the better.
Method
London
Paris
Shanghai
Los Angeles
ChebNet
39.10 ± 1.79
34.34 ± 0.31
40.00 ± 0.39
41.31 ± 0.48
Stable-ChebNet
40.11 ± 0.20
38.11 ± 0.25
41.45 ± 0.27
42.17 ± 0.16
μ -ChebNet (ours)
41.88 ± 0.11
35.14 ± 0.12
41.98 ± 0.96
43.33 ± 0.33
+ Stability
41.44 ± 0.07
37.49 ± 0.26
42.63 ± 0.70
43.10 ± 0.60
Table 4: Accuracy (%) on City-Networks dataset. We use this dataset to fairly compare ChebNet architectures by setting them to the same receptive field K=10 and isolating the effect of the weighted Laplacian Lμ .
Model
ROC-AUC ↑
MLP
72.04±0.48
GCN
72.51±0.35
ChebNet
77.55±0.43
Stable-ChebNet
79.55±0.34
SGC
70.31±0.23
GCN-NSAMPLER
73.51±1.31
Table 5: Results on ogbn-proteins .
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Ring graph configuration. (Left) The query node is in purple and the answer node in yellow. Nodes on the rightward path contain noisy features. (Right) The resulting learned weight function has broken the symmetry of the configuration, routing information on the most informative path.
Figure 4: Spectral analysis on the simple community graph.
Figure 5: 2-community Graph
Figure 6: Singular values of the propagated feature matrix restricted to the target cluster. While standard diffusion rapidly collapses all but one direction, the learned weighted diffusion geometry opens a transient regime in which multiple independent directions survive long enough to traverse the bottleneck.
Hyper-parameter
Values in grid
Diam
SSSP
Ecc
Hidden dimension d
20, 30, 50
50
30
30
Number of layers
1, 2, 3, 5, 10, 20
20
5
5
Polynomial order K
3, 5, 10
4
10
10
Step size ϵ
0.01, 0.10, 0.20, 0.30
0.40
0.30
0.30
Dissipative force γ
0, 0.01, 0.50, 1
0.01
0.00
0.00
Activation function
tanh, relu
relu
relu
relu
Appendix
Table 6: Hyper-parameter grid and best settings for our model on three synthetic graph-property benchmarks.
Hyper-parameter
Sweep
Hidden dim d
256, 512, 1024
Polynomial order K
5, 10, 15
Num of layers
3, 5, 7
MLP layers
1, 2, 3
Step size ϵ
[0.1, 1.0]
Dissipative force γ
0.01, 0.05, 0.1
Appendix
Table 7: Hyper-parameter sweep ranges for our model on ogbn-proteins .
Figure 7: Illustration of a Barbell graph composed of two densely connected node clusters
Despite their theoretical advantages, spectral methods based on the graph Fourier transform (GFT) are seldom used in graph neural networks (GNNs) due to the cost of computing the eigenbasis and the lack of vertex-domain locality in the resulting representations. As a result, most GNNs rely on local approximations such as polynomial Laplacian filters or message passing, which limit their ability to model long-range dependencies. In this paper, we introduce an exact factorization of the GFT into operators acting on subgraphs, which are then combined via a sequence of Cauchy matrices. Building on this factorization, we propose a new class of spectral GNNs, termed L2G-Net (Local to Global Net). Unlike existing spectral methods, which are either fully global (when using the GFT) or local (when using polynomial filters), L2G-Net operates by processing the spectral representations of subgraphs and then combining them via structured matrices. Our algorithm avoids full eigendecompositions, exploiting graph topology to construct the factorization with quadratic complexity in the number of nodes, scaled by the maximum cut size between subgraphs. Experiments stressing long-range dependencies on large graphs show that L2G-Net scales to regimes out of reach for the standard GFT, and is competitive with state-of-the-art methods with orders of magnitude fewer learnable parameters.
Samuel Fernández-Menduiña, Eduardo Pavez, Antonio Ortega
Graph neural networks (GNNs) are often called long-range because their architecture can connect distant nodes, but this does not show whether they use distant information correctly. We introduce a framework that measures how strongly inputs at each graph distance affect predictions and separates limitations due to architecture, finite approximation, training, and numerical execution. Our analysis shows that local message-passing can spread influence slowly, so a finite implementation may rely mainly on nearby inputs even when the ideal computation uses the whole graph. We also explain why mathematically equivalent filters can differ in how easily they are learned and how reliably they run. Across controlled tasks, models with similar architectural reach use distant information very differently, while low average error can hide failures on distant interactions. Together, these results show that long-range capability depends on learning to use information at the distances required by the task and preserving that use during computation.
Filippo Maria Bianchi
UiT The Arctic University of Norway · NORCE Norwegian Research Centre
Message-passing neural networks (MPNNs) often suffer from an information bottleneck when capturing long-range dependencies, leading to the oversquashing (OSQ) phenomenon. Alongside spatial connectivity enrichment (e.g., rewiring), recent studies have shown that spectral filtering can yield strong long-range learning outcomes, as spectral operators enable global information mixing that alleviates OSQ. These approaches achieve this either by stabilizing the Jacobian energies in deep propagation or by guaranteeing OSQ mitigation under strong theoretical assumptions. We revisit these conclusions and show that the associated Jacobian sensitivity lower bound is generally difficult to achieve in practice. We then propose S3GNN, which mitigates OSQ without such restrictive assumptions by lightweightly reintroducing omitted components with substantially lower computational complexity, while standard stability constraints on feature transformations remain effective under our new dynamics. Extensive experiments across diverse domains (e.g., long-range benchmarks, KGQA, and mesh-based fluid dynamics) demonstrate that S3GNN achieves up to an order-of-magnitude error reduction with up to 50% fewer parameters. Our code can be found in https://github.com/EEthanShi/S3-GNN.git.
Dai Shi, Luke Thompson, Linhan Luo +4
Department of Engineering, University of Cambridge, Cambridge, UK · University of Sydney, Australia