Timezone: »
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 cGNNs, 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 WeisfeilerLehman isomorphism test, cGNNs will be severely limited on simple random graph models. For instance, they will fail to distinguish the communities of a wellseparated 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 (cSGNNs) in the large random graph limit, under new conditions on the node identifiers. We then show that cSGNNs are strictly more powerful than cGNNs 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 permutationinvariant and permutationequivariant architectures.
Author Information
Nicolas Keriven (Ecole Normale SupĂ©rieure)
Alberto Bietti (Inria)
Samuel Vaiter (CNRS)
More from the Same Authors

2021 Poster: On the Sample Complexity of Learning under Geometric Stability »
Alberto Bietti · Luca Venturi · Joan Bruna 
2020 Poster: Convergence and Stability of Graph Convolutional Networks on Large Random Graphs »
Nicolas Keriven · Alberto Bietti · Samuel Vaiter 
2020 Spotlight: Convergence and Stability of Graph Convolutional Networks on Large Random Graphs »
Nicolas Keriven · Alberto Bietti · Samuel Vaiter 
2019 Poster: Universal Invariant and Equivariant Graph Neural Networks »
Nicolas Keriven · Gabriel PeyrĂ© 
2017 Poster: Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite Sum Structure »
Alberto Bietti · Julien Mairal 
2017 Spotlight: Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite Sum Structure »
Alberto Bietti · Julien Mairal 
2017 Poster: Invariance and Stability of Deep Convolutional Representations »
Alberto Bietti · Julien Mairal