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

arXiv: https://arxiv.org/abs/2211.03231 · HTML: https://mlsanity.com/paper/2211.03231/

## Key facts

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

## Builds on (most cited first, 26 of 26)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Stability Properties of Graph Neural Networks](https://mlsanity.com/paper/1905.04497/) (2019)
- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [Graph Neural Networks: Architectures, Stability and Transferability](https://mlsanity.com/paper/2008.01767/) (2020)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel](https://mlsanity.com/paper/1309.4111/) (2013)
- [Community Detection in Networks with Node Attributes](https://mlsanity.com/paper/1401.7267/) (2014)
- [Transferability Properties of Graph Neural Networks](https://mlsanity.com/paper/2112.04629/) (2021)
- [Inference for multiple heterogeneous networks with a common invariant subspace](https://mlsanity.com/paper/1906.10026/) (2019)
- [Graphon Signal Processing](https://mlsanity.com/paper/2003.05030/) (2020)
- [Covariate-assisted spectral clustering](https://mlsanity.com/paper/1411.2158/) (2014)
- [Effects of Graph Convolutions in Multi-layer Networks](https://mlsanity.com/paper/2204.09297/) (2022)
- [Spectral inference for large Stochastic Blockmodels with nodal covariates](https://mlsanity.com/paper/1908.06438/) (2019)
- [When Does A Spectral Graph Neural Network Fail in Node Classification?](https://mlsanity.com/paper/2202.07902/) (2022)
- [On spectral algorithms for community detection in stochastic blockmodel graphs with vertex covariates](https://mlsanity.com/paper/2007.02156/) (2020)
- [Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information](https://mlsanity.com/paper/1709.03907/) (2017)

## Built on by (most cited first, 5 of 5)

- [A Neural Collapse Perspective on Feature Evolution in Graph Neural Networks](https://mlsanity.com/paper/2307.01951/) (2023)
- [Limits, approximation and size transferability for GNNs on sparse graphs via graphops](https://mlsanity.com/paper/2306.04495/) (2023)
- [Graph neural networks and non-commuting operators](https://mlsanity.com/paper/2411.04265/) (2024)
- [Sampling Transferable Graph Neural Networks with Limited Graph Information](https://mlsanity.com/paper/2410.16593/) (2024)
- [LASE: Learned Adjacency Spectral Embeddings](https://mlsanity.com/paper/2412.17734/) (2024)

## 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.