Expressivity and Simplification of Spectral Graph Neural Networks

This direction is merged into another direction: 1-WL expressivity limit. Its last version stays readable and citable here.

Version 1 of 110 papers19 conceptsfrozen 2026-10-04

For years, Graph Neural Networks (GNNs) have been divided into two camps: "spatial" models that pass messages between neighbors and "spectral" models that operate on the eigenvalues and eigenvectors of the graph Laplacian. While spatial models are often intuitive, spectral GNNs have frequently been treated as complex "black boxes" requiring deep, non-linear architectures to be effective.

Recent research is overturning this view, revealing that spectral GNNs are both simpler and more theoretically constrained than previously thought. By mapping these models to the Weisfeiler-Lehman (WL) hierarchy and demonstrating the power of linear filters, researchers are showing that the "complexity" of spectral GNNs is often an architectural illusion.

The Surprising Power of Linearity

A common assumption in deep learning is that depth and non-linearity are the primary drivers of performance. However, in the context of spectral GNNs, this may not be the case. Xiyuan Wang and Muhan Zhang demonstrated in How Powerful are Spectral Graph Neural Networks that spectral models can achieve universal approximation properties using only a single linear transformation and a learnable polynomial filter.

This suggests that the heavy lifting in graph learning is done by the spectral filter—the mechanism that decides which graph frequencies to amplify or dampen—rather than the non-linear activations. Building on this, Luciano Vinas and Arash A. Amini showed in Simplifying GNN Performance with Low Rank Kernel Models that many state-of-the-art GNNs are over-engineered. They found that a simple linear model with a non-parametric spectral filter could match or exceed the performance of deep, multi-layer stacks, particularly on directed graphs.

Mapping the Theoretical Limits

If spectral GNNs can be simplified into linear filters, what exactly can they "see" in a graph? To answer this, researchers have begun measuring spectral models against the Weisfeiler-Lehman (WL) test, the standard yardstick for graph isomorphism.

In On the Expressive Power of Spectral Invariant Graph Neural Networks, Bohang Zhang, Haggai Maron, and colleagues established a unified framework called EPNN. They proved a definitive upper bound: no matter how sophisticated the spectral features are, these models cannot surpass the expressiveness of the 3-WL test.

Further refining this, Jingchu Gai and Liwei Wang used "homomorphism expressivity" to show that spectral invariant GNNs are equivalent to counting a specific class of tree-like structures known as parallel trees. This places their power strictly between the 1-WL and 2-FWL benchmarks, providing a precise structural explanation for why these models work: they are essentially sophisticated tree-counters.

The Incompleteness of Eigenvalues

Despite their power, spectral GNNs face a fundamental hurdle: the "simple spectrum" problem. Even if a graph has perfectly distinct eigenvalues, standard spectral GNNs might still fail to distinguish it from a non-isomorphic counterpart.

Snir Hordan and Nadav Dym highlighted this in Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum. They argued that traditional spectral frameworks are "incomplete." To fix this, they introduced equiEPNN, which applies rotation-equivariant techniques—often used in 3D point cloud processing—to ensure that the model can handle eigenvector canonicalization properly, thereby reaching a higher level of expressivity.

Two Sides of the Same Coin

The emerging consensus is that the historical divide between spatial and spectral GNNs is largely a matter of perspective. Antonis Vasileiou and Guy Wolf argue in Message-passing and spectral GNNs are two sides of the same coin that both approaches are simply different ways to parameterize permutation-equivariant operators.

By viewing them through a shared lens, the field is moving away from "spectral vs. spatial" debates and toward a unified theory of graph representation. This shift suggests that the future of graph learning lies not in adding more layers, but in more effectively designing the filters that capture the underlying geometry of the data.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_expressivity_and_simplification_of_spect_dc10bf33,
  title = {Expressivity and Simplification of Spectral Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expressivity-and-simplification-of-spectral-graph-neural-networks/rdr_dc10bf33df9f4b2b9b50042afe8bf89a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_expressivity_and_simplification_of_spect_dc10bf33_v1,
  title = {Expressivity and Simplification of Spectral Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expressivity-and-simplification-of-spectral-graph-neural-networks/rdr_dc10bf33df9f4b2b9b50042afe8bf89a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}