Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs
Levi Rauchwerger Stefanie Jegelka Ron Levie
We analyze the universality and generalization of graph neural networks (GNNs) on attributed graphs, i.e., with node attributes. To this end, we propose pseudometrics over the space of all attributed graphs that describe the fine-grained expressivity of GNNs. Namely, GNNs are both Lipschitz continuous with respect to our pseudometrics and can separate attributed graphs that are distant in the metric. Moreover, we prove that the space of all attributed graphs is relatively compact with respect to our metrics. Based on these properties, we prove a universal approximation theorem for GNNs and generalization bounds for GNNs on any data distribution of attributed graphs. The proposed metrics compute the similarity between the structures of attributed  graphs via a hierarchical optimal transport between computation trees. Our work extends and unites previous approaches which either derived theory only for graphs with no attributes, derived compact metrics under which GNNs are continuous but without separation power, or derived metrics under which GNNs are continuous and separate points but the space of graphs is not relatively compact, which prevents universal approximation and generalization analysis.
Graph Neural Networks, Graphon Neural Networks, Machine Learning Theory, 1-WL test for Graphons, Generalization, Expressivity, Universal Approximation, Wasserstein Distance, Optimal Transport, Computation Trees
We analyze the generalization, expressivity, and universality of graph neural networks on attributed graphs via a metric defined through computation trees of attributed graphons, which are based on an extension of the graphon 1-WL test.