Early Graph Neural Networks (GNNs) were largely driven by empirical intuition. Message passing was conceptualized as a smart heuristic for aggregating neighborhood features, and when models encountered structural limitations—such as losing distinctiveness at high depths (oversmoothing)—practitioners patched them with architectural fixes like residual connections or dropout.
However, this heuristic approach left a significant gap: without formal mathematical grounding, it was impossible to guarantee how GNNs would generalize to unseen topologies, scale to massive graphs, or behave under distribution shifts. Recent research has focused on closing this theoretical-empirical gap by providing rigorous mathematical foundations for GNN generalization and architecture design.
Quantifying Generalization via Complexity and Kernels
Standard statistical learning theory relies on the assumption that data points are independent and identically distributed (I.I.D.). Because graphs violate this assumption through interconnected nodes, bounding a GNN's generalization gap requires new theoretical tools.
One powerful approach is the Graph Neural Tangent Kernel (GNTK). Introduced by Simon Shaolei Du et al. in Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels, the GNTK models GNNs in the infinite-width limit. This maps a complex, non-convex neural network into a tractable, linear kernel space, allowing researchers to analyze how graph topology directly impacts learning. Leveraging this framework, Mahalakshmi Sabanayagam et al. in Analysis of Convolutions, Non-linearity and Depth in Graph Neural Networks using Neural Tangent Kernel mathematically proved why linear GNNs can match non-linear ones in specific regimes, why row normalization is theoretically superior to symmetric normalization for node classification, and how skip connections preserve expressivity at infinite depth.
Other frameworks use statistical complexity measures to bound the generalization gap. Renjie Liao et al. applied a PAC-Bayesian framework in A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks, demonstrating that a GNN's generalization stability is primarily driven by the graph's maximum node degree and the spectral norm of the model's weights. To explain generalization in transductive settings, Pascal Esser et al. in Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks utilized transductive Rademacher complexity, showing how network architecture and graph structure jointly govern performance on unseen nodes. Early attempts to solve NP-hard graph problems like the Quadratic Assignment Problem (QAP) using GNNs, such as the work by Alex Nowak et al. in Revised Note on Learning Quadratic Assignment with Graph Neural Networks, demonstrated strong empirical performance but highlighted a critical need for these types of formal learnability guarantees.
Furthermore, understanding how models behave under distribution shifts remains critical. Emmanuel Sales et al. in In-distribution and Out-of-distribution Generalization for Graph Neural Networks tightened in-distribution bounds by reducing dependencies on node degrees and provided theoretical guarantees for out-of-distribution size generalization, proving that GNNs can mathematically handle variations in graph size. This theoretical foundation is essential for specialized domains; for instance, Lele Fu et al. in Going Beyond Consistency: Target-oriented Multi-view Graph Neural Network derived generalization bounds for multi-view graph learning by explicitly separating task-relevant features from incidental noise. Similarly, in dynamic settings, Xiao Yang et al. highlighted in A Generalizable Anomaly Detection Method in Dynamic Graphs that while combining structure-aware attention with alternating graph layers yields cross-domain success, establishing a formal mathematical foundation for that generalization remains an open challenge.
Deriving Architectures from Formal Optimization
Instead of treating message passing as an intuitive aggregation heuristic, a parallel line of work derives GNN architectures directly from classical mathematical optimization. This shift ensures that each layer corresponds to a principled step toward minimizing a well-defined energy function.
Liang Yang et al. initiated this perspective in Why Do Attributes Propagate in Graph Convolutional Neural Networks? by reframing Graph Convolutional Networks (GCNs) as numerical optimization algorithms solving a graph representation objective. By viewing propagation layers as gradient descent steps, the authors introduced a conjugate gradient framework that accelerates convergence and prevents oversmoothing. Expanding on this, Yongyi Yang et al. developed the TWIRLS framework in Graph Neural Networks Inspired by Classical Iterative Algorithms. By anchoring GNN layers to proximal gradient descent and Iterative Reweighted Least Squares (IRLS), the authors created a model that naturally handles noisy edges and long-range dependencies without relying on post-hoc architectural patches.
This optimization-driven paradigm also extends to heterogeneous and non-convex settings. Yuling Wang et al. in Ensemble Multi-Relational Graph Neural Networks replaced heuristic multi-relational designs with an architecture derived from a formal optimization objective that balances feature preservation with smoothing across different edge types. To bypass the optimization challenges of deep, non-convex networks entirely, Zhihao Wu et al. introduced the Graph Convolutional Kernel Machine versus Graph Convolutional Networks, marrying graph convolutions with convex kernel methods to provide exact theoretical guarantees and faster, globally optimal training.
Demystifying Structural and Sampling Mechanics
Mathematical grounding also helps demystify why certain empirical phenomena occur in graph learning, transforming empirical observations into provable properties.
Consider the problem of oversmoothing, where deep GNN layers cause node representations to converge and lose distinctiveness. Jiaqi WANG provided a unified theory in A Signed Graph Approach to Understanding and Mitigating Oversmoothing, proving that common empirical fixes like normalization or residual connections implicitly introduce "negative edges" that mathematically repel dissimilar nodes. By formalizing this mechanism, the author designed a propagation scheme that explicitly balances positive and negative interactions, maintaining node distinctiveness across hundreds of layers.
Similarly, Qin Jiang et al. in Demystifying MPNNs: Message Passing as Merely Efficient Matrix Multiplication demystified message-passing neural networks by showing their core operation reduces to iterative matrix multiplication, demonstrating that performance degradation in deep sparse networks is often driven by gradient propagation issues rather than pure oversmoothing.
A similar theoretical gap exists in scaling GNNs to massive graphs, where practitioners routinely train models on small, sampled subgraphs. Yeganeh Alimohammadi et al. provided a rigorous justification for this practice in A Local Graph Limits Perspective on Sampling-Based GNNs. Using the mathematical theory of local graph limits, the authors proved that the parameters learned on a small fraction of a graph formally converge to the optimal parameters of the full graph as its size approaches infinity.
Unifying Spatial, Spectral, and Information-Theoretic Limits
Finally, mathematical grounding serves to unify disparate graph learning paradigms and map their fundamental limits. For years, the field was divided into spatial methods (aggregating local neighborhoods) and spectral methods (operating in the graph Laplacian frequency domain). Zhiqian Chen et al. resolved this fragmentation in Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networks by establishing a unified framework that maps spatial and spectral architectures into a shared mathematical taxonomy, enabling principled model selection.
This theoretical bridge also connects neural methods to classical information theory. Sadamori Kojaku et al. demonstrated in Network community detection via neural embeddings that shallow neural graph embeddings like node2vec are mathematically equivalent to classical spectral methods, proving they can reach information-theoretic limits for community detection even in sparse networks where traditional spectral algorithms fail.
As summarized by Bingzhe Wu et al. in their survey Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection, developing these rigorous frameworks is not merely an academic exercise; it is the foundational requirement for building reliable, provably robust graph learning systems that can be trusted in real-world applications.
Key Foundational Work
Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels (2019) — contributed 1 concept elements to this direction.
Revised Note on Learning Quadratic Assignment with Graph Neural Networks (2018) — contributed 1 concept elements to this direction.