mlsanityData to 7 Oct 2026

A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs

arXiv 2211.03231 ↗First posted 6 Nov 2022cs.SI cs.LG eess.SPcited by 5

Not on the map. Why?

Abstract (arXiv)

In this work we propose a random graph model that can produce graphs at different levels of sparsity. 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 compare GNNs with spectral methods known to provide consistent estimators for community detection on dense graphs, a closely related task. We show that GNNs can outperform spectral methods on sparse graphs, and illustrate these results with numerical examples on both synthetic and real graphs.

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

Builds on

26 of 38 references.

References · 26

  1. 2018How Powerful are Graph Neural Networks?cited by 4,355
  2. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  3. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  4. 2019Multi-scale Attributed Node Embeddingcited by 543
  5. 2017Graph Signal Processing: Overview, Challenges and Applicationscited by 409
  6. 2017Community Detection and Stochastic Block Modelscited by 317
  7. 2020Combining Label Propagation and Simple Models Out-performs Graph Neural Networkscited by 199
  8. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  9. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  10. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  11. 2019Stability Properties of Graph Neural Networkscited by 125
  12. 2020Graphon Neural Networks and the Transferability of Graph Neural Networkscited by 117
14 more
  1. 2020Graph Neural Networks: Architectures, Stability and Transferabilitycited by 79
  2. 2017Statistical inference on random dot product graphs: a surveycited by 70
  3. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  4. 2013Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodelcited by 45
  5. 2014Community Detection in Networks with Node Attributescited by 44
  6. 2021Transferability Properties of Graph Neural Networkscited by 42
  7. 2019Inference for multiple heterogeneous networks with a common invariant subspacecited by 39
  8. 2020Graphon Signal Processingcited by 37
  9. 2014Covariate-assisted spectral clusteringcited by 29
  10. 2022Effects of Graph Convolutions in Multi-layer Networkscited by 24
  11. 2019Spectral inference for large Stochastic Blockmodels with nodal covariatescited by 6
  12. 2022When Does A Spectral Graph Neural Network Fail in Node Classification?cited by 6
  13. 2020On spectral algorithms for community detection in stochastic blockmodel graphs with vertex covariatescited by 4
  14. 2017Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Informationcited by 3

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 3.

5 papers.

  1. 2023A Neural Collapse Perspective on Feature Evolution in Graph Neural Networkscited by 19
  2. 2023Limits, approximation and size transferability for GNNs on sparse graphs via graphopscited by 17
  3. 2024Graph neural networks and non-commuting operatorscited by 5
  4. 2024Sampling Transferable Graph Neural Networks with Limited Graph Informationcited by 0
  5. 2024LASE: Learned Adjacency Spectral Embeddingscited by 0