Rethinking Spectral Graph Neural Networks with Spatially Adaptive Filtering

Jingwei Guo, Kaizhu Huang, Xinping Yi, Zixian Su, Rui ZhangSubmission to ICLR 2024 · Rejected

TL;DR

While spectral Graph Neural Networks (GNNs) are celebrated for their theoretical elegance, their practical implementations rely on truncated polynomials that confine them to local neighborhoods. This paper reveals that graph spectral filtering implicitly constructs an adapted, non-local graph with signed edge weights that discern class consistency. Building on this discovery, the authors propose Spatially Adaptive Filtering (SAF), a framework that explicitly extracts this transformed graph to execute non-local spatial aggregation, substantially boosting GNN performance on heterophilic graphs and long-range dependencies.

What Problem Does This Paper Address?

Graph neural networks generally fall into two camps:

  1. Spatial GNNs, which aggregate node features recursively across immediate neighbors.
  2. Spectral GNNs, which perform convolutions in the Fourier/spectral domain of the graph Laplacian.

To avoid the $O(N^3)$ computational cost of full eigendecomposition, spectral GNNs almost universally approximate filter functions with low-order polynomials (e.g., Chebyshev or Bernstein polynomials). However, this polynomial truncation restricts spectral filtering to local $K$-hop neighborhoods, causing two persistent challenges:

  • Difficulty capturing long-range dependencies.
  • Severe vulnerability to graph heterophily (where connected nodes frequently belong to different classes).

Furthermore, the theoretical relationship between spectral filtering and spatial message passing has remained poorly understood. This paper asks a fundamental question: What information do spectral filters actually encode in the spatial domain?

Methods

The authors bridge spectral filtering and spatial aggregation via a generalized graph optimization framework: $$\arg \min_Z \|X - Z\|_F^2 + c \cdot \text{tr}\left(Z^T \gamma_\theta(\hat{L})Z\right)$$

  • The Closed-Form vs. Iterative Connection: The closed-form minimizer corresponds directly to spectral filtering $Z^* = g_\psi(\hat{L})X$, provided the filter satisfies a non-negative constraint ($0 < g_\psi(\lambda) \le 1$). Conversely, an iterative gradient descent solution mirrors spatial propagation over an adapted new graph: $$\hat{A}^{\text{new}} = I - c^{-1}\left(g_\psi(\hat{L})^{-1} - I\right)$$
  • Non-negative Spectral Filtering: SAF parametrizes $g_\psi(\lambda)$ using Bernstein polynomials (as in BernNet) and rescales them by their maximum coefficient to strictly bound outputs to $[0, 1]$.
  • Non-local Spatial Aggregation: Using precomputed graph eigendecomposition for matrix inversion, SAF explicitly computes $\hat{A}^{\text{new}}$ and runs multi-step spatial propagation over it. A sparsified variant, SAF-$\epsilon$, zeroes out small values in $[-\epsilon, \epsilon]$ to suppress noise.
  • Node-wise Prediction Amalgamation: Rather than statically merging features, SAF uses lightweight attention MLPs to dynamically assign weights $(\kappa_f, \kappa_a)$ balancing spectral predictions ($Y_f$) and spatial predictions ($Y_a$) per node.
Input Graph (X, L) ──┬──> Non-negative Spectral Filtering ──> Zf ──> Yf ──┐
                     │                                                     ├──> Node-wise Blend ──> Y
                     └──> Invert Filter ──> A_new ──> Aggregation ─> Za ─> Ya ─┘

Datasets

The authors evaluated SAF across 13 real-world benchmarks:

  • 3 Homophilic Graphs: Cora, Citeseer, and Pubmed.
  • 5 Traditional Heterophilic Graphs: Chameleon, Squirrel, Texas, Cornell, and Actor.
  • 5 New Heterophilic Benchmarks: Minesweeper (synthetic grid), Tolokers (crowdsourcing workers), Amazon-ratings (co-purchasing), Roman-empire (word dependencies), and Twitch-DE (social network).

Key Insights and Ideas

  • Spectral Filtering is Inherently Non-Local: By Lemma 1 (Neumann series expansion), when eigenvalues satisfy $|I - g_\psi(\hat{L})| < 1$, the inverted filter $(g_\psi(\hat{L}))^{-1}$ expands into an infinite power series of the adjacency matrix $\sum_{t=0}^\infty \phi_t \hat{A}^t$. Thus, spectral filtering implicitly creates direct edges between nodes separated by many hops in the original graph.
  • Edges Naturally Form Signed Weights: The entries of $\hat{A}^{\text{new}}$ are both positive and negative. Minimizing the optimization trace term requires $\hat{A}^{\text{new}}_{i,j} > 0$ when labels match ($y_i = y_j$) and $\hat{A}^{\text{new}}_{i,j} < 0$ when they disagree ($y_i \neq y_j$). Empirical testing confirms that positive edges reinforce homophily while negative edges bridge cross-class boundaries.
  • Dynamic Spectral-Spatial Trade-offs: Tracking the attention weights $(\kappa_f, \kappa_a)$ over training epochs shows that homophilic graphs (like Cora) favor local spectral filtering ($\kappa_f \to 1$), while heterophilic graphs (like Squirrel) distribute attention equally between spectral and global spatial representations.

Key Results

  • Semi-Supervised Node Classification: SAF and SAF-$\epsilon$ beat BernNet on all 8 tested datasets, achieving accuracy gains up to +15.37% (Texas) and +14.56% (Chameleon), and consistently ranking first or second against 14 baseline models.
  • Full-Supervised Node Classification: SAF sets new state-of-the-art results across most datasets, outperforming cutting-edge spatial models (NodeFormer, GloGNN++) and spectral models (ChebNetII, Specformer). For instance, it achieved 94.75% on Texas and 90.59% on Minesweeper (+12.84% over BernNet).
  • Ablation Studies: Disabling either spectral filtering, spatial aggregation, or the amalgamation gate produced noticeable performance drops across all datasets, confirming the mutual synergy of the hybrid approach.

Limitations and Future Work

  • Filter Expressiveness: Constraining graph filters to $0 < g_\psi(\lambda) \le 1$ excludes certain unrestricted filter families (e.g., standard low-pass/high-pass polynomials with unconstrained negative values).
  • Preprocessing Overhead: SAF relies on exact eigendecomposition ($O(N^3)$ precomputation and $O(N^2)$ space), making full matrix storage expensive for graphs with hundreds of thousands of nodes.
  • Task Scope: The study focuses exclusively on node classification; evaluating whether implicit non-local graph adaptation benefits graph-level or link-level tasks remains an open direction.

Summary updated

Abstract

Whilst spectral Graph Neural Networks (GNNs) are theoretically well-founded in the spectral domain, their practical reliance on polynomial approximation implies a profound linkage to the spatial domain. As previous studies rarely examine spectral GNNs from the spatial perspective, their spatial-domain interpretability remains elusive, e.g., what information is essentially encoded by spectral GNNs in the spatial domain? In this paper, to answer this question, we establish a theoretical connection between spectral filtering and spatial aggregation, unveiling an intrinsic interaction that spectral filtering implicitly leads the original graph to an adapted new graph, explicitly computed for spatial aggregation. Both theoretical and empirical investigations reveal that the adapted new graph not only exhibits non-locality but also accommodates signed edge weights to reflect label consistency between nodes. These findings thus highlight the interpretable role of spectral GNNs in the spatial domain and inspire us to rethink graph spectral filters beyond the fixed-order polynomials, which neglect global information. Built upon the theoretical findings, we revisit the state-of-the-art spectral GNNs and propose a novel Spatially Adaptive Filtering (SAF) framework, which leverages the adapted new graph by spectral filtering for an auxiliary non-local aggregation. Notably, our proposed SAF comprehensively models both node similarity and dissimilarity from a global perspective, therefore alleviating persistent deficiencies of GNNs related to long-range dependencies and graph heterophily. Extensive experiments over 13 node classification benchmarks demonstrate the superiority of our proposed framework to the state-of-the-art models.
BibTeX
@misc{guo2024rethinking,
  author = {Jingwei Guo and Kaizhu Huang and Xinping Yi and Zixian Su and Rui Zhang},
  title = {{Rethinking Spectral Graph Neural Networks with Spatially Adaptive Filtering}},
  year = {2024},
  eprint = {2401.09071},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2401.09071},
}
Figure