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

DevFeed: [From Link Prediction to Linear Community Detection: A Finite-Sample Guarantee for Graph Pretraining](<https://devfeed.tech/articles/from-link-prediction-to-linear-community-detection-a-finite-sample-guarantee-for-graph-pretraining-133038.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.15778>)

Author: Ying Chen, Zhangyang Wang, Yixuan He

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>), [Neural Network](<https://devfeed.tech/topics/neural-network.md>)

Tags: [classification](<https://devfeed.tech/tags/classification.md>), [community-detection](<https://devfeed.tech/tags/community-detection.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [embeddings](<https://devfeed.tech/tags/embeddings.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [gnn](<https://devfeed.tech/tags/gnn.md>), [graph](<https://devfeed.tech/tags/graph.md>), [linear](<https://devfeed.tech/tags/linear.md>), [link](<https://devfeed.tech/tags/link.md>), [prediction](<https://devfeed.tech/tags/prediction.md>), [pretraining](<https://devfeed.tech/tags/pretraining.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>)

## AI overview

In the finite-sample stochastic block model, small population held-out link-prediction excess risk implies low community-classification error for a transductive linear classifier on embeddings from a bounded GNN with a symmetric bilinear decoder. The guarantee separates optimization and architectural approximation residuals from statistical terms of order Õ(√(d/n)) in bounded dense regimes. The authors also give a few-label nearest-centroid classifier using the positive semidefinite form G = W ZᵀZW. For a GIN with spectral positional encoding and a bilinear decoder, they bound the approximation residual by O(log n/n). Synthetic experiments support the reduction and indicate that worst-case constants can be conservative.

## Source excerpt

arXiv:2611.15778v1 Announce Type: new 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 $\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 = 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 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.