L2G-Net: Local to Global Spectral Graph Neural Networks via Cauchy Factorizations
L2G-Net employs Cauchy decomposition to enable efficient spectral graph transforms, capturing long-range dependencies with quadratic complexity, outperforming traditional full eigendecomposition.
Key Findings
Methodology
This paper introduces L2G-Net, a spectral GNN framework leveraging Cauchy matrix-based factorization of the graph Fourier transform (GFT). By hierarchically partitioning the graph into subgraphs and expressing the GFT as a sequence of localized transformations combined via structured Cauchy matrices, the method avoids costly full eigendecomposition. The algorithm exploits graph topology, using maximum cut optimization to generate partitions that minimize computational cost, resulting in a quadratic complexity of O(n^2). The architecture integrates local spectral filters within subgraphs and a global spectral filter at the top level, enabling efficient long-range dependency modeling while maintaining parameter efficiency.
Key Results
- On large heterophilic graphs, L2G-Net achieves over 10% accuracy improvements compared to polynomial filters and message passing models, with significantly fewer parameters and faster training times.
- Spectral decomposition experiments confirm quadratic scaling with graph size, validating theoretical complexity predictions and demonstrating practical efficiency over traditional eigendecomposition.
- Hierarchical partitioning combined with spectral sparsification reduces cut sizes, maintaining spectral properties and enabling scalable spectral filtering on graphs with millions of nodes.
Significance
This work addresses a fundamental bottleneck in spectral GNNs, enabling their application to large-scale graphs by reducing computational complexity from cubic to quadratic. It effectively combines local and global spectral information, capturing long-range dependencies that are critical in many real-world applications such as social networks, knowledge graphs, and biological systems. The approach opens new avenues for scalable, interpretable, and expressive graph neural models, bridging the gap between theoretical spectral methods and practical large-scale graph processing.
Technical Contribution
The core technical innovation is the derivation of an exact Cauchy matrix-based factorization of the GFT for arbitrary graphs, leveraging hierarchical graph partitioning and spectral sparsification. This yields an O(n^2) complexity algorithm for spectral basis computation, significantly reducing computational costs. The architecture, L2G-Net, integrates local spectral filters with a structured global filter, enabling parameter-efficient long-range dependency modeling. Theoretical analysis proves the expressiveness surpasses purely local or global methods, and the framework generalizes to various graph families, including hierarchical and sparse graphs.
Novelty
This is the first work to utilize Cauchy matrix structures for spectral graph transform factorization, avoiding full eigen-decomposition. The hierarchical approach, combined with spectral sparsification, introduces a scalable divide-and-conquer paradigm for spectral GNNs. Unlike prior methods relying solely on polynomial filters or attention mechanisms, L2G-Net explicitly encodes graph structure into spectral operations, offering a new perspective on spectral filter design with provable efficiency and expressiveness.
Limitations
- The effectiveness depends on the quality of graph partitioning; poor partitions can increase complexity or reduce accuracy.
- In graphs lacking clear hierarchical structure or with large cuts, the computational advantage diminishes.
- Parameter tuning and hyperparameter selection (e.g., number of levels, sparsification epsilon) remain challenging, impacting robustness.
Future Work
Future directions include adaptive partitioning algorithms, dynamic graph extension, and spectral approximation techniques to further reduce complexity. Exploring applications in dynamic, heterogeneous, and multi-relational graphs, as well as integrating with attention mechanisms, could enhance flexibility and performance in diverse real-world scenarios.
AI Executive Summary
Spectral graph neural networks (GNNs) have long promised powerful global representations by leveraging the graph Fourier transform (GFT). However, their practical adoption has been hindered by the high computational cost of eigen-decomposition, scaling cubically with the number of nodes. This bottleneck limits their use in large-scale applications such as social networks, knowledge graphs, and biological systems. To overcome this challenge, the authors propose L2G-Net, a novel spectral GNN architecture that employs a Cauchy matrix-based factorization of the GFT. This approach decomposes the spectral transform into a sequence of localized operations on subgraphs, combined via structured matrices, enabling efficient hierarchical processing. The key innovation is the exploitation of graph topology and maximum cut optimization to generate partitions that minimize the spectral decomposition cost, achieving quadratic complexity in the number of nodes. Extensive experiments on synthetic and real-world large graphs demonstrate that L2G-Net not only scales efficiently but also captures long-range dependencies more effectively than traditional polynomial filters or message passing models. Results show over 10% accuracy improvements on heterophilic graph benchmarks, with parameter counts orders of magnitude smaller than attention-based models. The spectral decomposition experiments confirm the quadratic complexity, validating theoretical predictions. This work significantly advances the applicability of spectral GNNs, providing a scalable, interpretable, and expressive framework for large-scale graph learning. Future research will focus on adaptive partitioning, spectral approximation, and extending to dynamic or heterogeneous graphs, promising broad impact across multiple domains.
Deep Dive
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.