mlsanityData to 7 Oct 2026

When Does A Spectral Graph Neural Network Fail in Node Classification?

arXiv 2202.07902 ↗First posted 16 Feb 2022cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

Spectral Graph Neural Networks (GNNs) with various graph filters have received extensive affirmation due to their promising performance in graph learning problems. However, it is known that GNNs do not always perform well. Although graph filters provide theoretical foundations for model explanations, it is unclear when a spectral GNN will fail. In this paper, focusing on node classification problems, we conduct a theoretical analysis of spectral GNNs performance by investigating their prediction error. With the aid of graph indicators including homophily degree and response efficiency we proposed, we establish a comprehensive understanding of complex relationships between graph structure, node labels, and graph filters. We indicate that graph filters with low response efficiency on label difference are prone to fail. To enhance GNNs performance, we provide a provably better strategy for filter design from our theoretical analysis - using data-driven filter banks, and propose simple models for empirical validation. Experimental results show consistency with our theoretical results and support our strategy.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 16 of its 26 references that are in the map. First posted on arXiv 16 Feb 2022.

Builds on

16 of 26 references.

References · 16

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2016Categorical Reparameterization with Gumbel-Softmaxcited by 2,708
  5. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  6. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  7. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  8. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  9. 2019Multi-scale Attributed Node Embeddingcited by 543
  10. 2017Graph Signal Processing: Overview, Challenges and Applicationscited by 409
  11. 2021Beyond Low-frequency Information in Graph Convolutional Networkscited by 361
  12. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 260
4 more
  1. 2019Graph Neural Networks with convolutional ARMA filterscited by 185
  2. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  3. 2020Scattering GCN: Overcoming Oversmoothness in Graph Convolutional Networkscited by 57
  4. 2021Message Passing in Graph Convolution Networks via Adaptive Filter Bankscited by 4

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 2; 2024: 1; 2025: 1.

6 papers.

  1. 2024Alleviating Structural Distribution Shift in Graph Anomaly Detectioncited by 31
  2. 2022EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networkscited by 26
  3. 2023Robust Mid-Pass Filtering Graph Convolutional Networkscited by 17
  4. 2022A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphscited by 5
  5. 2023Improving Signed Propagation for Graph Neural Networks in Multi-Class Environmentscited by 2
  6. 2025Aligning the Spectrum: Hybrid Graph Pre-training and Prompt Tuning across Homophily and Heterophilycited by 0