Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum

• URL: http://arxiv.org/abs/2506.05530v1
• Date: Thu, 05 Jun 2025 19:26:29 GMT
• Title: Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum
• Authors: Snir Hordan, Maya Bechler-Speicher, Gur Lifshitz, Nadav Dym,
• Abstract summary: Spectral features are widely incorporated within Graph Neural Networks (GNNs) to improve their expressive power.<n>We propose a method to provably improve SGNNs' expressivity on simple spectrum graphs.
• Score: 2.916558661202724
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Spectral features are widely incorporated within Graph Neural Networks (GNNs) to improve their expressive power, or their ability to distinguish among non-isomorphic graphs. One popular example is the usage of graph Laplacian eigenvectors for positional encoding in MPNNs and Graph Transformers. The expressive power of such Spectrally-enhanced GNNs (SGNNs) is usually evaluated via the k-WL graph isomorphism test hierarchy and homomorphism counting. Yet, these frameworks align poorly with the graph spectra, yielding limited insight into SGNNs' expressive power. We leverage a well-studied paradigm of classifying graphs by their largest eigenvalue multiplicity to introduce an expressivity hierarchy for SGNNs. We then prove that many SGNNs are incomplete even on graphs with distinct eigenvalues. To mitigate this deficiency, we adapt rotation equivariant neural networks to the graph spectra setting to propose a method to provably improve SGNNs' expressivity on simple spectrum graphs. We empirically verify our theoretical claims via an image classification experiment on the MNIST Superpixel dataset and eigenvector canonicalization on graphs from ZINC.

Related papers

• Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization [0.6215404942415159]
  Hierarchical Ego Graph Neural Networks (HEGNNs) are an expressive extension of graph neural networks (GNNs)<n>HEGNNs generalize subgraph-GNNs and form a hierarchy of increasingly expressive models that can distinguish graphs up to isomorphism.<n>Our experimental results confirm the practical feasibility of HEGNNs and show benefits in comparison with traditional GNN architectures.
  arXiv  Detail & Related papers  (2025-06-16T18:39:31Z)
• Higher-Order GNNs Meet Efficiency: Sparse Sobolev Graph Neural Networks [6.080095317098909]
  Graph Neural Networks (GNNs) have shown great promise in modeling relationships between nodes in a graph. Previous studies have primarily attempted to utilize the information from higher-order neighbors in the graph. We make a fundamental observation: the regular and the Hadamard power of the Laplacian matrix behave similarly in the spectrum. We propose a novel graph convolutional operator based on the sparse Sobolev norm of graph signals.
  arXiv  Detail & Related papers  (2024-11-07T09:53:11Z)
• GrassNet: State Space Model Meets Graph Neural Network [57.62885438406724]
  Graph State Space Network (GrassNet) is a novel graph neural network with theoretical support that provides a simple yet effective scheme for designing arbitrary graph spectral filters. To the best of our knowledge, our work is the first to employ SSMs for the design of graph GNN spectral filters. Extensive experiments on nine public benchmarks reveal that GrassNet achieves superior performance in real-world graph modeling tasks.
  arXiv  Detail & Related papers  (2024-08-16T07:33:58Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  We take a manifold perspective to establish the statistical generalization theory of GNNs on graphs sampled from a manifold in the spectral domain. We prove that the generalization bounds of GNNs decrease linearly with the size of the graphs in the logarithmic scale, and increase linearly with the spectral continuity constants of the filter functions.
  arXiv  Detail & Related papers  (2024-06-07T19:25:02Z)
• Permutation-Invariant Graph Partitioning:How Graph Neural Networks Capture Structural Interactions? [2.7398542529968477]
  Graph Neural Networks (GNNs) have paved the way for being a cornerstone in graph-related learning tasks.<n>Yet, the ability of GNNs to capture structural interactions within graphs remains under-explored.<n>We propose Graph Partitioning Neural Networks (GPNNs), a novel architecture that efficiently enhances the expressive power of GNNs in learning structural interactions.
  arXiv  Detail & Related papers  (2023-12-14T06:08:35Z)
• Spectral Heterogeneous Graph Convolutions via Positive Noncommutative Polynomials [34.74726720818622]
  We present Positive Spectral Heterogeneous Graph Convolutional Network (PSHGCN) PSHGCN offers a simple yet effective method for learning valid heterogeneous graph filters. PSHGCN exhibits remarkable scalability, efficiently handling large real-world graphs comprising millions of nodes and edges.
  arXiv  Detail & Related papers  (2023-05-31T14:09:42Z)
• Specformer: Spectral Graph Neural Networks Meet Transformers [51.644312964537356]
  Spectral graph neural networks (GNNs) learn graph representations via spectral-domain graph convolutions. We introduce Specformer, which effectively encodes the set of all eigenvalues and performs self-attention in the spectral domain. By stacking multiple Specformer layers, one can build a powerful spectral GNN.
  arXiv  Detail & Related papers  (2023-03-02T07:36:23Z)
• Stable and Transferable Hyper-Graph Neural Networks [95.07035704188984]
  We introduce an architecture for processing signals supported on hypergraphs via graph neural networks (GNNs) We provide a framework for bounding the stability and transferability error of GNNs across arbitrary graphs via spectral similarity.
  arXiv  Detail & Related papers  (2022-11-11T23:44:20Z)
• A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs [13.954735096637298]
  We analyze how sparsity affects the graph spectra, and thus the performance of graph neural networks (GNNs) in node classification on dense and sparse graphs. We show that GNNs can outperform spectral methods on sparse graphs, and illustrate these results with numerical examples on both synthetic and real graphs.
  arXiv  Detail & Related papers  (2022-11-06T22:38:13Z)
• How Powerful are Spectral Graph Neural Networks [9.594432031144715]
  Spectral Graph Neural Network is a kind of Graph Neural Network based on graph signal filters. We first prove that even spectral GNNs without nonlinearity can produce arbitrary graph signals. We also establish a connection between the expressive power of spectral GNNs and Graph Isomorphism (GI) testing.
  arXiv  Detail & Related papers  (2022-05-23T10:22:12Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  We show that standard Graph Neural Networks (GNNs) produce more discriminative representations than the Weisfeiler-Lehman (WL) algorithm. We also show that simple convolutional architectures with white inputs, produce equivariant features that count the closed paths in the graph.
  arXiv  Detail & Related papers  (2022-05-19T18:40:25Z)
• Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs [6.018995094882323]
  Graph neural networks (GNNs) have been extensively studied for prediction tasks on graphs. Most GNNs assume local homophily, i.e., strong similarities in localneighborhoods. We propose a flexible GNN model, which is capable of handling any graphs without beingrestricted by their underlying homophily.
  arXiv  Detail & Related papers  (2021-03-26T00:35:36Z)
• On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
  Graph-Augmented Multi-Layer Perceptrons (GA-MLPs) first augments node features with certain multi-hop operators on the graph. We prove a separation in expressive power between GA-MLPs and GNNs that grows exponentially in depth.
  arXiv  Detail & Related papers  (2020-10-28T17:59:59Z)
• Graphon Pooling in Graph Neural Networks [169.09536309161314]
  Graph neural networks (GNNs) have been used effectively in different applications involving the processing of signals on irregular structures modeled by graphs. We propose a new strategy for pooling and sampling on GNNs using graphons which preserves the spectral properties of the graph.
  arXiv  Detail & Related papers  (2020-03-03T21:04:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.