Understanding Graph Neural Network Generalization via Message-Passing Structural Complexity

Graph neural networks (GNNs) have become a fundamental paradigm for learning from graph-structured data. Unlike conventional neural networks, their predictions depend not only on learnable parameters but also on the graph structures involved in message passing, making their generalization particularly sensitive to structural variations. However, existing analyses of GNN generalization mainly focus on parameter complexity, while how the complexity of message-passing structures affects generalization remains insufficiently understood. To characterize this effect, we define message-passing structural complexity and derive a structure-aware generalization bound within a transductive Rademacher-complexity framework, theoretically revealing structural complexity as a fundamental factor in GNN generalization. To mitigate the effect of structural complexity on generalization, we develop a graph neural network method with structural entropy regularization, which controls message-passing structural complexity through structural entropy. We theoretically establish an upper-bound relation showing that structural entropy serves as a differentiable surrogate for cross-class information-propagation complexity, thereby enabling principled control of potentially harmful message passing. By incorporating the structural regularization term into several representative GNN architectures, experiments on benchmark datasets show that reducing the structural complexity can consistently improve GNN generalization.