On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry

Abstract

Understanding the interplay between generalization, expressivity, and the geometry of the input space is a central challenge in graph learning. The expressivity of Graph Neural Networks (GNNs) is typically characterized through their correspondence with graph invariants, such as those from the Weisfeiler-Leman (WL) hierarchy. While more expressive GNNs can distinguish a richer set of graphs, they are also associated with weaker generalization guarantees. Previous works have addressed this trade-off using the VC dimension, a purely combinatorial measure, independent of the training data. In this work, we adopt a data-dependent measure of generalization, the empirical Rademacher complexity, and derive tight generalization bounds that jointly consider the expressive power of GNNs and the geometry of the underlying input space. Specifically, any graph invariant that upper-bounds a GNN's expressive power partitions the input space into equivalence classes, and we show that the empirical Rademacher complexity is controlled by the distribution of training samples across these classes. Moving beyond discrete partitions, we incorporate the geometry of the input space and derive covering-number bounds under Lipschitz continuity, showing that the complexity cost can be mitigated when the hypothesis class remains smooth over the data geometry. In addition, we prove that the empirical Rademacher complexity is Lipschitz continuous with respect to the Wasserstein distance between empirical measures supported on different datasets. This yields robustness and generalization guarantees under sampling variability. Importantly, our framework is not restricted to message-passing GNNs or WL, but extends to arbitrary GNN architectures and their associated invariants, providing a step toward a unified theory of GNN generalization.