From Link Prediction to Linear Community Detection: A Finite-Sample Guarantee for Graph Pretraining

Link prediction is a standard pretraining objective for graph neural networks: hide edges, train an encoder--decoder to predict them, and reuse the node embeddings for downstream node tasks. Despite its empirical success, there is little quantitative theory explaining why an edge-level objective should produce embeddings that are linearly useful for node classification.We study this question in the finite-sample stochastic block model (SBM). For any bounded GNN encoder paired with a symmetric bilinear decoder, we prove a conditional reduction: small population held-out LP excess risk implies small community-classification error for a transductive linear classifier on the learned embeddings.The bound decomposes into an optimization residual, an architectural approximation residual, and explicit statistical terms of order $\widetilde{O}(\sqrt{d/n})$ in bounded dense regimes. We further give a constructive few-label classifier: nearest-centroid classification under the PSD quadratic form $G = W Z^\top Z W$, whose label error is coupled to LP quality.The framework is architecture-agnostic through the approximation residual, and we instantiate this residual as $O(\log n / n)$ for a spectral-positional-encoding GIN with a bilinear decoder. Synthetic SBM experiments validate the theorem chain from LP risk to score error to classification error, and show when the worst-case constants become conservative.