A Spectral Analysis of Graph Neural Networks on Dense and Sparse 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.

1. INTRODUCTION

Graph neural networks (GNNs) have achieved impressive results in network data, with successful applications including genomic sequencing [1] and satellite navigation [2]. Their empirical success is supported by a growing body of work on the mathematical properties of these models, such as their universality [3], expressive power [4], [5], stability [6] and transferability [7]. GNNs are built as sequences of layers in which each layer composes a graph convolutional filterbank and a pointwise nonlinearity. A variety of constructions exist in the literature, but most of them are expressible as deep convolutional models; see [8, Sec. I.A].