cs.LGNov 11, 2026

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

Authors: Ying Chen, Zhangyang Wang, Yixuan He

Organizations: Arizona State University · University of Texas at Austin

Abstract

Link prediction (LP) is a standard pretraining objective for graph neural networks (GNNs): 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 O~(d/n)\tilde{O}(\sqrt{d/n}) in bounded dense regimes. We further give a constructive few-label classifier: nearest-centroid classification under the positive semidefinite quadratic form G=WZ⊤ZWG = 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)O(\log n / n) for a graph isomorphism network (GIN) with spectral positional encoding and 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.

Figures & tables

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Mini-Batch Class Composition Bias in Link Prediction

    Apr 28, 2026Kieran Maguire, Srinandan DasmahapatraGraph Representation LearningLink Prediction

  2. Same Graph Cross-Task Transfer in GNNs: Protocols and Predictors

    Jul 30, 2026Neelam Akula, Surbhi Kumar, Murat Kantarcioglu +1Graph Neural NetworksLink Prediction