On the Universality of Graph Neural Networks on Large Random Graphs

Abstract

We study the approximation power of Graph Neural Networks (GNNs) on latent position random graphs. In the large graph limit, GNNs are known to converge to certain "continuous" models known as c-GNNs, which directly enables a study of their approximation power on random graph models. In the absence of input node features however, just as GNNs are limited by the Weisfeiler-Lehman isomorphism test, c-GNNs will be severely limited on simple random graph models. For instance, they will fail to distinguish the communities of a well-separated Stochastic Block Model (SBM) with constant degree function. Thus, we consider recently proposed architectures that augment GNNs with unique node identifiers, referred to as Structural GNNs here (SGNNs). We study the convergence of SGNNs to their continuous counterpart (c-SGNNs) in the large random graph limit, under new conditions on the node identifiers. We then show that c-SGNNs are strictly more powerful than c-GNNs in the continuous limit, and prove their universality on several random graph models of interest, including most SBMs and a large class of random geometric graphs. Our results cover both permutation-invariant and permutation-equivariant architectures.

References in corpus (8)

• Neural Message Passing for Quantum Chemistry
• Geometric deep learning: going beyond Euclidean data
• Consistency of spectral clustering
• Graph Isomorphism in Quasipolynomial Time
• Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology
• From Local Structures to Size Generalization in Graph Neural Networks
• Fundamental Limits of Deep Graph Convolutional Networks
• The expressive power of kth-order invariant graph networks