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.
Figures & tables
Figure 1: (a) A graph in F(L=3,{Gi}i=18,k=3) . Bridge edges are shown in different colors. The GFT basis of the whole graph decomposes as the product of the GFT bases of the base graphs by a sequence of Cauchy factors. (b) We first compute the base GFTs of small subgraphs (right) and apply local spectral filters. We mix the outputs via Cauchy factors corresponding to bridge edges. After all merges, a global spectral filter acts on the full graph representation (left), allowing for global filtering while preserving locality.
Figure 2: Average energy versus hop distance from the source when we input a unit impulse at each node of a graph. ChebNet (3rd-order) has a hard cutoff at 3 hops, while a GFT-based GNN propagates energy globally. L2G-Net’s locality bias adapts to the graph structure, interpolating between these two extremes.
Method
Cost
Locality
CU
MPNNs
O(∣E∣)
Local
Node
GT
O(n2)
Global
Node
ChebNet
O(K∣E∣)
K -hop
Node
GFT
O(n3)
Global
Graph
L2G-Net
O(kn2)
Local to global
Subgraph
Table 1: Comparison of different graph learning methods. CU stands for computational unit and GT for graph transformers.
Method
R. Emp.
Am. Rat.
Mines.
Tolok.
GCN
73.69 (0.7)
48.70 (0.6)
89.75 (0.5)
83.64 (0.7)
CO-GNN
91.57 (0.3)
54.17 (0.4)
97.31 (0.4)
84.45 (1.2)
Polynormer
92.55 (0.3)
54.81 (0.5)
97.46 (0.4)
85.91 (0.7)
MP-SSM
90.91 (0.5)
53.65 (0.7)
95.33 (0.7)
85.26 (0.9)
St-ChebNet
92.03 (0.9)
53.15 (0.2)
95.71 (2.3)
85.55 (3.4)
Ours
92.12 (1.1)
53.39 (0.6)
97.50 (0.3)
85.57 (0.6)
Table 2: Average test accuracy with standard deviation for 10 random train/test partitions on the benchmark in [ 49 ] . We report the best-performing methods per family. We show average Acc for Roman-empire (R. Emp.) and Amazon-ratings (Am. Rat.) and AUC for Tolokers (Tolok.) and Minesweeper (Mines.). Higher is better ( ↑ ). See also Table 12 .
Method
R. Emp.
Am. Rat.
Mines.
Tolok.
ED
731.12
896.56
92.34
117.57
CF (ours)
232.49
281.30
32.21
91.33
Table 3: Runtime (s) for computing the eigenvalue decomposition (ED) and the Cauchy factorization (CF) on heterophilous graphs from [ 49 ] .
Figure 3: Runtime on a random graph for eigendecomposition (ED), Cauchy factorization (CF), and preprocessing (SC+Sparse). The Cauchy factorization scales quadratically with the number of nodes. The preprocessing time is negligible.
Figure 4: Runtime against k on a random graph for Cauchy factorization (CF) and preprocessing (SC+Sparse). The complexity of the Cauchy factorization scales linearly with the cut size. The preprocessing time is small and roughly constant with k .
Figure 5: Performance vs complexity comparison. L2G-Net achieves competitive or superior performance with orders of magnitude fewer learnable parameters than state-of-the-art baselines, and outperforms the Global GFT across all datasets.
Method
Paris
Shanghai
LA
London
ED
OOM
OOM
OOM
OOM
EDP
50412.82
121932.43
131543.54
1632123.32
CF
17.91
45.61
61.53
144.22
Table 4: Time (minutes) to compute the eigendecomposition (ED) versus the CF factorization on City-Networks. ED runs out of memory in all cases; EDP extrapolates the O(n3) trend .
Figure 6: Cumulative node contribution to the prediction on Minesweeper . Average across validation set; shaded areas indicate confidence intervals. L2G-Net localizes predictive power on a smaller fraction of nodes than Global GFT. The node contributions of Polynormer are less localized in the original graph.
Method
Mines.
Tolok.
Am. Rat.
R. Emp.
Paris
Shanghai
LA
London
Full GFT
0.80
1.11
4.80
4.11
103.97
270.61
463.06
2588.22
CF (ours)
0.20
0.28
1.21
1.03
12.21
16.98
14.58
40.96
Table 5: Memory consumption (GB) of full GFT vs. our Cauchy factorization (CF), using 64-bit precision. On [ 49 ] we use L=1 ; on City-Networks [ 44 ] , where full GFT is infeasible at practical hardware limits, we use deeper hierarchies.
Type
Model
pep.-func ( ↑ )
pep.-struct ( ↓ )
Trans.
Graph ViT
69.42 ± 0.75
0.2449 ± 0.0016
GRIT
69.88 ± 0.82
0.2460 ± 0.0012
Rewir.
DRew-GCN+PE
71.50 ± 0.44
0.2536 ± 0.0015
SS
GMN
70.71 ± 0.83
0.2473 ± 0.0025
MP-SSM
69.93 ± 0.52
0.2458 ± 0.0017
GNN
GCN
68.60 ± 0.50
0.2460 ± 0.0007
Table 6: LRGB results [ 21 ] ; top performers per category shown, full results in Appendix I . AP on peptides-func (higher is better), MAE on peptides-struct (lower is better). Trans. = transformer, Rewir. = rewiring, SS = state space.
Model
Paris
Shanghai
LA
London
ChebNet
54.1 (0.2)
66.5 (0.1)
61.4 (0.4)
54.7 (0.2)
GCN
53.2 (0.3)
62.1 (0.2)
58.3 (0.3)
50.1 (0.7)
SAGE
54.6 (0.2)
68.3 (0.5)
61.4 (0.3)
55.4 (0.2)
GraphGPS
52.1 (0.6)
63.0 (0.5)
59.8 (0.5)
OOM
Exphormer
55.1 (0.8)
70.2 (0.4)
63.8 (0.6)
49.5 (0.4)
SGFormer
52.0 (0.8)
64.1 (0.3)
60.1 (0.7)
48.3 (0.3)
Table 7: Average test accuracy with standard deviation for 4 random seeds on City-Networks [ 44 ] . Higher is better. We show selected methods, full results in Appendix I .
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
d
Layers
Levels
K
Dropout
LR
Steps
Sparsif.
Roman-empire
64
5
1
8
0.25
2×10−4
1000
0.005
Amazon-ratings
256
4
1
6
0.30
4×10−3
1500
0.005
Minesweeper
32
14
1
6
0.225
2×10−3
1000
0.005
Tolokers
64
3
1
4
0.20
8×10−4
2000
0.01
peptides-func
256
4
1
12
0.35
1×10−3
500
1
peptides-struct
256
4
1
12
0.3
1×10−3
300
1
Appendix
Table 8: Dataset-specific hyperparameter settings for L2G-Net.
Dataset
Nodes
Edges
Avg. Degree
Features
Classes
k after sparse
Roman-empire
22,662
32,927
2.91
300
18
1
Amazon-ratings
24,492
93,050
7.60
300
5
1
Minesweeper
10,000
39,402
7.88
7
2
1
Tolokers
11,758
519,000
88.28
10
2
25
Appendix
Table 9: Statistics of real-world heterophilous graph datasets from Platonov et al. [ 49 ] .
Figure 7: Sorted eigengaps of the normalized Laplacian on the heterophilous benchmarks of [ 49 ] . Amazon-ratings exhibits a large plateau of numerically zero gaps (approximately 20% of eigenvalues), and Roman-empire shows a smaller cluster of gaps below 10−12 ; Minesweeper and Tolokers are well-separated throughout. Deflation handles near-degenerate eigenvalues in all cases without affecting downstream accuracy.
Algorithm 3 Cauchy factorization
Figure 8: Example of a barbell-like graph.
Figure 9: Learned spectral filters for different graphs in [ 49 ] . In tasks where both low- and high-frequency information are needed (e.g., Tolokers / Amazon-ratings ), local filters emphasize low frequencies, while global filters focus on higher frequencies. When the signal lies in high frequencies ( Minesweeper / Roman-empire ), both local and global filters focus on high-frequency components. This indicates that the hierarchical processing adapts to the task.
Figure 10: Cumulative node contribution to the prediction on Tolokers, Roman Empire , and Amazon Ratings (from left to right). Average across validation set; shaded areas indicate confidence intervals. L2G-Net consistently concentrates predictive importance on a smaller fraction of nodes than both the Global GFT and Polynormer, showing consistent behavior across datasets.
Method
Mines.
Tolok.
Am. Rat.
R. Emp.
GCN
01:23
01:53
02:12
02:02
ChebNet
03:56
06:18
11:22
13:08
Polynormer
15:12
08:32
35:00
28:56
L2G-Net (ours)
08:40
03:04
34:56
50:03
Appendix
Table 10: End-to-end training time (mm:ss) to convergence on heterophilous benchmarks [ 49 ] , under identical hardware.
Method
Mines.
Tolok.
Am. Rat.
R. Emp.
GCN
0.05
0.06
0.07
0.06
ChebNet
0.12
0.21
0.33
0.40
Polynormer
0.29
0.18
0.56
0.48
L2G-Net (ours)
0.35
0.13
1.04
1.54
Appendix
Table 11: Per-epoch wall-clock time (s/epoch) on heterophilous benchmarks [ 49 ] .
Model
Roman-empire
Amazon-ratings
Minesweeper
Tolokers
MPNNs
GAT
80.87 ± 0.30
49.09 ± 0.63
92.01 ± 0.68
83.70 ± 0.47
GAT (LapPE)
84.80 ± 0.46
44.90 ± 0.73
93.50 ± 0.54
84.99 ± 0.54
GAT (RWSE)
86.62 ± 0.53
48.58 ± 0.41
92.53 ± 0.65
85.02 ± 0.67
Gated-GCN
74.46 ± 0.54
43.00 ± 0.32
87.54 ± 1.22
77.31 ± 1.14
GCN
73.69 ± 0.74
48.70 ± 0.63
89.75 ± 0.52
83.64 ± 0.67
Appendix
Table 12: Performance comparison on long-range benchmarks. Results are reported as mean ± standard deviation. We report Acc for Roman-empire and Amazon-ratings and AUC for Tolokers and Minesweeper . Higher is better ( ↑ ). Best method appears in boldface, second best method underlined, third best method in italics.
Type
Model
peptides-func (AP ↑ )
peptides-struct (MAE ↓ )
Trans.
SAN+LapPE
63.84 ± 1.21
0.2683 ± 0.0043
TIGT
66.79 ± 0.74
0.2485 ± 0.0015
Specformer
66.86 ± 0.64
0.2550 ± 0.0014
Exphormer
65.27 ± 0.43
0.2481 ± 0.0007
G.MLPMixer
69.21 ± 0.54
0.2475 ± 0.0015
Graph ViT
69.42 ± 0.75
0.2449 ± 0.0016
Appendix
Table 13: Long-range benchmark results [ 21 ] . AP is reported on peptides-func (higher is better), and MAE on peptides-struct (lower is better). Trans. stands for transformer, Rewir. for rewiring, and SS for state space.
Model
Paris
Shanghai
LA
London
MLP
25.5 (0.4)
48.4 (0.6)
24.1 (0.5)
27.9 (0.1)
ChebNet
54.1 (0.2)
66.5 (0.1)
61.4 (0.4)
54.7 (0.2)
GCN
53.2 (0.3)
62.1 (0.2)
58.3 (0.3)
50.1 (0.7)
SAGE
54.6 (0.2)
68.3 (0.5)
61.4 (0.3)
55.4 (0.2)
GAT
51.1 (0.3)
68.0 (0.5)
59.5 (0.3)
52.0 (0.3)
GCNII
51.3 (0.2)
61.5 (0.4)
56.0 (0.3)
48.2 (0.3)
Appendix
Table 14: Average test accuracy with standard deviation for 4 random seeds on City-Networks [ 44 ] .
Spectral graph convolution applies learned filters in the graph Laplacian or Fourier domain to model graph structure, signal frequencies, and long-range dependencies.
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.
Spectral Graph Neural Networks (Spectral GNNs) for node classification promise frequency-domain filtering on graphs, yet rest on flawed foundations. Recent work shows that graph Laplacian eigenvectors do not in general have the key properties of a true Fourier basis, but leaves the empirical success of Spectral GNNs unexplained. We identify two theoretical glitches: (1) commonly used "graph Fourier bases" are not classical Fourier bases for graph signals; (2) (n-1)-degree polynomials (n = number of nodes) can exactly interpolate any spectral response via a Vandermonde system, so the usual "polynomial approximation" narrative is not theoretically justified. The effectiveness of GCN is commonly attributed to spectral low-pass filtering, yet we prove that low- and high-pass behaviors arise solely from message-passing dynamics rather than Graph Fourier Transform-based spectral formulations. We then analyze two representative directed spectral models, MagNet and HoloNet. Their reported effectiveness is not spectral: it arises from implementation issues that reduce them to powerful MPNNs. When implemented consistently with the claimed spectral algorithms, performance becomes weak. This position paper argues that: for node classification, Spectral GNNs neither meaningfully capture the graph spectrum nor reliably improve performance; competitive results are better explained by their equivalence to MPNNs, sometimes aided by implementations inconsistent with their intended design.
Qin Jiang, Chengjia Wang, Michael Lones +2
Department of Computer Science, University of Heriot-Watt, Edinburgh, UK
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