A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs
This addresses performance gaps in graph-based learning for sparse graphs, but is incremental as it builds on known spectral methods.
The paper tackles how graph sparsity affects GNN performance in node classification, showing that GNNs outperform spectral methods on sparse graphs, with numerical examples on synthetic and real graphs.
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.