Generalization of Graph Neural Networks: Over Geometric Graphs Sampled from Manifolds

In this work, we study the generalization capabilities of graph neural networks (GNNs) over geometric graphs sampled from manifolds. Specifically, we focus on graphs constructed from randomly sampled points over an embedded manifold with underlying geometric information captured. The graph is relatively sparse under a practical model assumption. We derive a generalization gap between the empirical and statistical risks of this GNN. We observe that the gap increases with the dimension of the underlying manifold and decreases with the number of sampled points from the manifold. This result demonstrates that a GNN trained on a graph constructed from a finite set of sampled points can effectively process unseen graphs generated from the same underlying manifold. Our theoretical analysis is grounded in the non-asymptotic convergence of a GNN on the sampled geometric graph to the underlying manifold neural network (MNN). We verify this theoretical result with experiments on a citation network.