Semi-Supervised Learning on Graphs using Graph Neural Networks

Juntong Chen; Claire Donnat; Olga Klopp; Johannes Schmidt-Hieber

stat.MLFeb 19, 2026

Semi-Supervised Learning on Graphs using Graph Neural Networks

Authors: Juntong Chen, Claire Donnat, Olga Klopp, Johannes Schmidt-Hieber

Organizations: School of Mathematical Sciences, Xiamen University · Department of Statistics, University of Chicago · ESSEC Business School · Department of Applied Mathematics, University of Twente

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Graph feature propagation followed by a nonlinear readout: a linear message-passing block generates propagated features, which are then mapped to node-level predictions via a ReLU DNN.

Figure 2: MSE (over 20 trials) as a function of training samples $n$ , with the unmasked proportion held constant at $\pi\in\{0.35,0.75,0.85,0.95\}$ . Estimators are distinguished by color: GCN with skip connections, GCN without skip connections, and the MLP baseline.

Figure 3: Left: Fitted slopes of $\log(\mathrm{MSE})$ vs. $\log(n)$ as a function of connection probability $\pi$ . Right : $\log(\operatorname{MSE})$ as a function of the effective sample size $n_{\text{eff}}=n\times\pi$ for the GCN with skip connections, as proposed in Equation ( 7 ).

Figure 4: MSE (over 20 trials) as a function of $\log(1/\pi)$ across different graph sizes. Estimators are distinguished by color: GCN with skip connections, GCN without skip connections, and the MLP baseline.

Figure 5: Performance of the GCN (with skip connection) as a function of the maximum degree of the graph ( $x$ -axis), for different convolution types (columns) and values of $\bar{\delta}$ (colors) on a Barabási–Albert graph.

Figure 6: Performance of the different baselines averaged over 5 experiments as a function of $\pi$ ( $x$ -axis) and the graph type (columns). Here, all GCN versions use $L=2$ layers, and the average degree was fixed to $\bar{\delta}=2$ across topologies.

Figure 7: Performance of the different baselines as a function of the proportion of nodes used for training for the California Housing and Wikipedia datasets. For Wikipedia, displayed MSE values are capped at 3 to keep the scale readable; some MAGNET and MAGNET-critic replicates exceed this value.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Architecture	Covered?	Notes / Why (not)
GCN ( Kipf and Welling, 2017 ) / SGC	✓	Linear propagation with a fixed graph operator (e.g., Laplacian) followed by a learned readout.
Polynomial GNNs	✓	Propagation is a polynomial in a fixed operator; fits $\sum_{\ell}\gamma_{\ell}\mathbf{T}^{\ell}\mathbf{X}\mathbf{W}_{\ell}$ and related forms.
APPNP / Diffusion	✓	Personalized PageRank-style diffusion is linear in features (fixed operator), followed by an MLP readout.
Skip-connected GCN	✓	Directly covered by weighted sums of multiple propagation depths.
GraphSAGE (mean)	partial	Mean aggregation is linear if aggregator weights are fixed; feature-dependent gating falls outside the scope.
GAT (Attention)	✗	Attention makes the propagation operator data-dependent, violating the fixed-operator assumption.

Appendix

Table 1: Coverage of common GNN architectures by our theoretical framework.

Explore similar work

Implicit Regularization of Mini-Batch Training in Graph Neural Networks
May 21, 2026Clement Wang, Antoine Vialle, Robin Vaysse +1Graph Neural Networks Implicit Regularization
Institut Polytechnique de Paris · Mirakl
F\textsuperscript{2}LP-AP: Fast & Flexible Label Propagation with Adaptive Propagation Kernel
Apr 22, 2026Yutong Shen, Ruizhe Xia, Jingyi Liu +1Graph-Based Semi-Supervised Learning Semi-Supervised Learning
Beijing University of Technology
Different Statistical Perspectives for Understanding Generalisation in Graph Neural Networks
May 25, 2026Nil Ayday, Mahalakshmi Sabanayagam, Debarghya GhoshdastidarNeural Network Generalization Graph Neural Networks
Technical University of Munich, School of Computation, Information and Technology, Boltzmannstr. 3, Garching, 85748, Germany. · Australian Institute for Machine Learning, Adelaide University,2026 Adelaide, SA 5000, Australia.

May 21, 2026J/K move · Enter open · S save

Implicit Regularization of Mini-Batch Training in Graph Neural Networks

Clement Wang, Antoine Vialle, Robin Vaysse, Thomas Bonald

Institut Polytechnique de Paris · Mirakl

Graph Neural Networks Implicit Regularization Stochastic Gradient Descent

Open paper AskPDF arXiv

Mini-batch training of Graph Neural Networks (GNNs) is fundamentally different from training on i.i.d. data: sampling a subgraph alters the topology and introduces boundary effects, leading prior work to develop structure-aware samplers that preserve local connectivity and reduce embedding variance. Surprisingly, we demonstrate that the simplest possible scheme, Random Node Sampling (RNS), training on the induced subgraph of uniformly sampled nodes, matches or outperforms full-graph training on 8 of 10 datasets at a fraction of the wall-clock time and memory. To explain this, we apply backward error analysis to graph mini-batch Stochastic Gradient Descent (SGD) and show that it implicitly minimizes the sampled loss plus a regularizer proportional to the mini-batch gradient variance, a quantity directly shaped by the sampler. Although RNS discards local structure, it produces mini-batches whose expected loss is closer to the full-graph loss, and whose per-batch gradients have lower variance, yielding a better implicit objective. Our analysis reframes the choice of graph sampler as a form of implicit regularization, and identifies RNS as a strong, theoretically grounded method for scalable GNN training.

Abstract

Explore similar work

Implicit Regularization of Mini-Batch Training in Graph Neural Networks

F\textsuperscript{2}LP-AP: Fast & Flexible Label Propagation with Adaptive Propagation Kernel

Different Statistical Perspectives for Understanding Generalisation in Graph Neural Networks