Semi-Supervised Learning on Graphs using Graph Neural Networks
This provides a theoretical framework for understanding GNN performance in semi-supervised learning, which is incremental as it builds on existing methods but offers new insights into their limitations.
The paper tackles the lack of rigorous theory for graph neural networks (GNNs) in semi-supervised node regression by analyzing an aggregate-and-readout model, proving a sharp non-asymptotic risk bound that separates errors and scales with labeled nodes and graph dependence, with numerical experiments validating the theory.
Graph neural networks (GNNs) work remarkably well in semi-supervised node regression, yet a rigorous theory explaining when and why they succeed remains lacking. To address this gap, we study an aggregate-and-readout model that encompasses several common message passing architectures: node features are first propagated over the graph then mapped to responses via a nonlinear function. For least-squares estimation over GNNs with linear graph convolutions and a deep ReLU readout, we prove a sharp non-asymptotic risk bound that separates approximation, stochastic, and optimization errors. The bound makes explicit how performance scales with the fraction of labeled nodes and graph-induced dependence. Approximation guarantees are further derived for graph-smoothing followed by smooth nonlinear readouts, yielding convergence rates that recover classical nonparametric behavior under full supervision while characterizing performance when labels are scarce. Numerical experiments validate our theory, providing a systematic framework for understanding GNN performance and limitations.