  Graph neural networks (GNNs) are the de facto standard deep learning
architectures for machine learning on graphs. This has led to a large body of
work analyzing the capabilities and limitations of these models, particularly
pertaining to their representation and extrapolation capacity. We offer a novel
theoretical perspective on the representation and extrapolation capacity of
GNNs, by answering the question: how do GNNs behave as the number of graph
nodes become very large? Under mild assumptions, we show that when we draw
graphs of increasing size from the Erd\H{o}s-R\'enyi model, the probability
that such graphs are mapped to a particular output by a class of GNN
classifiers tends to either zero or to one. This class includes the popular
graph convolutional network architecture. The result establishes 'zero-one
laws' for these GNNs, and analogously to other convergence laws, entails
theoretical limitations on their capacity. We empirically verify our results,
observing that the theoretical asymptotic limits are evident already on
relatively small graphs.

Machine Learning