L2G-Net: Local to Global Spectral Graph Neural Networks via Cauchy Factorizations

Samuel Fernández-Menduiña; Eduardo Pavez; Antonio Ortega

cs.LGFeb 21, 2026

L2G-Net: Local to Global Spectral Graph Neural Networks via Cauchy Factorizations

Authors: Samuel Fernández-Menduiña, Eduardo Pavez, Antonio Ortega

Organizations: University of Southern California.

Abstract

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 $\mathcal{F}(L=3,\{\mathcal{G}_{i}\}_{i=1}^{8},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(n^{2})$	Global	Node
ChebNet	$O(K\|E\|)$	$K$ -hop	Node
GFT	$O(n^{3})$	Global	Graph
L2G-Net	$O(kn^{2})$	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 (

\uparrow

). 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(n^{3})

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 ( $\uparrow$ )	pep.-struct ( $\downarrow$ )
Trans.	Graph ViT	69.42 $\pm$ 0.75	0.2449 $\pm$ 0.0016
Trans.	GRIT	69.88 $\pm$ 0.82	0.2460 $\pm$ 0.0012
Rewir.	DRew-GCN+PE	71.50 $\pm$ 0.44	0.2536 $\pm$ 0.0015
SS	GMN	70.71 $\pm$ 0.83	0.2473 $\pm$ 0.0025
SS	MP-SSM	69.93 $\pm$ 0.52	0.2458 $\pm$ 0.0017
GNN	GCN	68.60 $\pm$ 0.50	0.2460 $\pm$ 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\times 10^{-4}$	1000	0.005
Amazon-ratings	256	4	1	6	0.30	$4\times 10^{-3}$	1500	0.005
Minesweeper	32	14	1	6	0.225	$2\times 10^{-3}$	1000	0.005
Tolokers	64	3	1	4	0.20	$8\times 10^{-4}$	2000	0.01
peptides-func	256	4	1	12	0.35	$1\times 10^{-3}$	500	1
peptides-struct	256	4	1	12	0.3	$1\times 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 ] .

Panel of Figure 7 — 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.

Panel of Figure 17 — Algorithm 3 Cauchy factorization

Figure 8: Example of a barbell-like graph.

Panel of Figure 9 — 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.

Panel of Figure 10 — 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 ] .

MPNNs
Model	Roman-empire	Amazon-ratings	Minesweeper	Tolokers
GAT	80.87 $\pm$ 0.30	49.09 $\pm$ 0.63	92.01 $\pm$ 0.68	83.70 $\pm$ 0.47
GAT (LapPE)	84.80 $\pm$ 0.46	44.90 $\pm$ 0.73	93.50 $\pm$ 0.54	84.99 $\pm$ 0.54
GAT (RWSE)	86.62 $\pm$ 0.53	48.58 $\pm$ 0.41	92.53 $\pm$ 0.65	85.02 $\pm$ 0.67
Gated-GCN	74.46 $\pm$ 0.54	43.00 $\pm$ 0.32	87.54 $\pm$ 1.22	77.31 $\pm$ 1.14
GCN	73.69 $\pm$ 0.74	48.70 $\pm$ 0.63	89.75 $\pm$ 0.52	83.64 $\pm$ 0.67

Appendix

Table 12: Performance comparison on long-range benchmarks. Results are reported as mean

\pm

standard deviation. We report Acc for Roman-empire and Amazon-ratings and AUC for Tolokers and Minesweeper . Higher is better (

\uparrow

). Best method appears in boldface, second best method underlined, third best method in italics.

Type	Model	peptides-func (AP $\uparrow$ )	peptides-struct (MAE $\downarrow$ )
Trans.	SAN+LapPE	63.84 $\pm$ 1.21	0.2683 $\pm$ 0.0043
	TIGT	66.79 $\pm$ 0.74	0.2485 $\pm$ 0.0015
	Specformer	66.86 $\pm$ 0.64	0.2550 $\pm$ 0.0014
	Exphormer	65.27 $\pm$ 0.43	0.2481 $\pm$ 0.0007
	G.MLPMixer	69.21 $\pm$ 0.54	0.2475 $\pm$ 0.0015
	Graph ViT	69.42 $\pm$ 0.75	0.2449 $\pm$ 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

Spectral graph convolution applies learned filters in the graph Laplacian or Fourier domain to model graph structure, signal frequencies, and long-range dependencies.

See all 22 papers

Full-Spectrum Graph Neural Networks: Expressive and Scalable
May 7, 2026Xiaohan Wang, Deyu Bo, Longlong Li +1Graph Neural Networks GNN Expressivity
Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore.
Position: Spectral GNNs Are Neither Spectral Nor Superior for Node Classification
Mar 19, 2026Qin Jiang, Chengjia Wang, Michael Lones +2Spectral Graph Convolution Node Classification
Department of Computer Science, University of Heriot-Watt, Edinburgh, UK
S $^3$ GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learning
May 22, 2026Dai Shi, Luke Thompson, Linhan Luo +4Long-Range Graph Learning Graph Neural Networks
Department of Engineering, University of Cambridge, Cambridge, UK · University of Sydney, Australia

May 7, 2026J/K move · Enter open · S save

Full-Spectrum Graph Neural Networks: Expressive and Scalable

Xiaohan Wang, Deyu Bo, Longlong Li, Kelin Xia

Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore.

Graph Neural Networks GNN Expressivity Spectral Methods Higher-Order GNNs Spectral Graph Convolution

Open paper AskPDF arXiv

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.

Abstract

Spectral Graph Convolution

Explore similar work

Full-Spectrum Graph Neural Networks: Expressive and Scalable

Position: Spectral GNNs Are Neither Spectral Nor Superior for Node Classification

S3^33GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learning

S $^3$ GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learning