Abstract
Graph convolutional networks (GCNs) are a widely used method for graphrepresentation learning. We investigate the power of GCNs, as a function oftheir number of layers, to distinguish between different random graph models onthe basis of the embeddings of their sample graphs. In particular, the graphmodels that we consider arise from graphons, which are the most generalpossible parameterizations of infinite exchangeable graph models and which arethe central objects of study in the theory of dense graph limits. We exhibit aninfinite class of graphons that are well-separated in terms of cut distance andare indistinguishable by a GCN with nonlinear activation functions coming froma certain broad class if its depth is at least logarithmic in the size of thesample graph. These results theoretically match empirical observations ofseveral prior works. Finally, we show a converse result that for pairs ofgraphons satisfying a degree profile separation property, a very simple GCNarchitecture suffices for distinguishability. To prove our results, we exploita connection to random walks on graphs.