Full-Spectrum Graph Neural Networks: Expressive and Scalable

Xiaohan Wang, Deyu Bo, Longlong Li, Kelin Xia

Spectral Graph Neural Networks (GNNs) offer a mathematically elegant approach to graph representation learning by applying filters to the eigenvalues of a graph's Laplacian. However, their expressive power has long been constrained by the 1-dimensional Weisfeiler-Lehman (1-WL) test. To address this, researchers have introduced Full-Spectrum Graph Neural Networks (FSpecGNN), a second-order generalization that shatters this barrier. By lifting signals from nodes to node-pairs and employing bivariate spectral filters, FSpecGNN achieves the expressive power of second-order spatial GNNs while maintaining the scalability required for large-scale graphs.

The Limitations of Classical Spectral GNNs

Most spectral GNNs are inherently "diagonal" in the spectral domain. While this diagonal structure is well-suited for homophilic graphs—where connected nodes share similar features or labels—it becomes a significant liability in heterophilic environments, where neighbors often belong to different classes.

Furthermore, the 1-WL ceiling means these models cannot distinguish certain non-isomorphic graphs or capture complex, higher-order structural signals. Existing spatial-based higher-order GNNs attempt to solve this expressivity problem by looking at $k$-tuples of nodes, but they incur massive computational overhead, rendering them impractical for large datasets.

Methodology: Full-Spectrum GNNs

To overcome these limitations, FSpecGNN introduces two core innovations to the spectral filtering paradigm:

  1. Domain Lifting: Instead of filtering signals purely on the node domain ($V$), FSpecGNN lifts signals to the node-pair domain ($V \times V$).
  2. Bivariate Filtering: The standard univariate filter $g(\lambda)$ is replaced with a bivariate filter $g(\lambda_i, \lambda_j)$ that operates on pairs of eigenvalues.

Operating directly on the $V \times V$ domain would typically incur an intractable $O(n^2)$ computational cost. To make FSpecGNN scalable, the authors introduce a clever low-rank approximation. Rather than computing a full bivariate polynomial, the filter is decomposed into a sum of separable univariate filters:

$$H' = \sigma\left(\sum_{r=1}^S h_r(L) \epsilon f_r(L) H W\right)$$

Even with a rank of $S=1$, this formulation captures crucial "off-diagonal" spectral interactions. Because it relies on standard matrix multiplications, its computational complexity remains comparable to classical spectral models like ChebNet or BernNet.

Theoretical Insights

FSpecGNN is grounded in robust theoretical foundations. The authors prove a striking result: the optimal convolution for separating classes in heterophilic graphs must contain off-diagonal components in the spectral basis. Because classical spectral GNNs are strictly diagonal, they are mathematically incapable of reaching this optimal separation. FSpecGNN naturally fills this gap.

Additionally, the paper establishes a geometric connection to product graph theory. It demonstrates that full-spectrum convolution is essentially equivalent to performing standard convolution on a Cartesian product graph ($G \square G$), providing a beautiful bridge between spectral lifting and spatial product graphs.

Empirical Results

The model was rigorously evaluated across expressivity benchmarks and both small and large-scale heterophilic graphs.

  • Expressivity: FSpecGNN successfully matches the distinguishing power of Local 2-GNN. It excels in substructure-counting tasks (such as homomorphism and chordal cycle counting) that typically confound standard 1-WL models.
  • Performance: On heterophilic node classification tasks (e.g., Texas, Wisconsin, Roman Empire, Minesweeper), FSpecGNN variants consistently outperformed their base spectral counterparts.
  • Efficiency: Despite its higher-order capabilities, FSpecGNN achieved roughly 5x lower runtime than spatial second-order baselines like Local 2-GNN. It also maintained the lowest peak GPU memory usage among expressive methods, successfully scaling to large graphs where Local 2-GNN encountered Out-Of-Memory (OOM) errors.

Limitations and Future Directions

While FSpecGNN represents a significant leap forward, the authors identify several avenues for future research:

  • Rank Selection: Most experiments utilized a rank of $S=1$ for the bivariate filter. Exploring higher ranks ($S > 1$) and coordinating multiple filter pairs remains an open challenge.
  • Initial Convolution: The initial node-pair signal $\epsilon$ (set as $I + \alpha GAT$ in the study) is effective but not canonical, suggesting room for more principled initialization strategies.
  • Higher-Order Extensions: The framework theoretically extends to $k$-th order signals on $V^k$. However, the computational trade-offs for $k > 2$ have yet to be explored.

Summary updated

Abstract

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, FSpecGNNs admit 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, FSpecGNNs validate the predicted expressivity on substructure-counting benchmarks and delivers strong performance on heterophilic benchmarks. Our code is available at https://github.com/xwangxshi/FSpecGNN.
BibTeX
@inproceedings{wang2026full,
  author = {Xiaohan Wang and Deyu Bo and Longlong Li and Kelin Xia},
  title = {{Full-Spectrum Graph Neural Networks: Expressive and Scalable}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=jk7P5ppKxD},
}
Figure