From Link Prediction to Linear Community Detection: A Finite-Sample Guarantee for Graph Pretraining
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 in bounded dense regimes. We further give a constructive few-label classifier: nearest-centroid classification under the positive semidefinite quadratic form , whose label error is coupled to LP quality. The framework is architecture-agnostic through the approximation residual, and we instantiate this residual as 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
| Symbol | Description |
|---|---|
| Graph and stochastic block model | |
| undirected, unweighted graph; , | |
| , | number of nodes, number of communities |
| symmetric adjacency matrix, | |
| (unobserved) community label of node | |
| , | community proportion, minimum proportion across |
| arch | 200 | 300 | 400 | 500 | 1000 | 1500 | 2000 | |
|---|---|---|---|---|---|---|---|---|
| GIN + random | 10 | 9 | 8 | 9 | 10 | 10 | 10 | 10 |
| GIN + PE | 10 | 10 | 9 | 10 | 10 | 10 | 10 | 10 |
| CP + random | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 |
| GCN + PE | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 |
| GAT + PE | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 |
| arch |
| Sweep | median ratio | IQR | # seeds |
|---|---|---|---|
| -sweep ( ) | |||
| -sweep ( , ) | |||
| cap-ratio sweep (cap-ratio , ) | |||
| sweep ( , ) | |||
| sweep ( , ) | |||
| mean across sweeps | (spread ) | ||
| arch / | 100 | 200 | 300 | 400 | 500 | 1000 | 1500 | 2000 |
|---|---|---|---|---|---|---|---|---|
| GIN+PE | ||||||||
| GCN+PE | ||||||||
| GIN+random | ||||||||
| CP+random | ||||||||
| predicted | ||||||||
| ScoreMSE H | ScoreMSE full | ||
|---|---|---|---|
| arch | oracle | plug-in (Thm. 6 II) | direct (LogReg) | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
| GIN+PE | ||||||||||
| GCN+PE | ||||||||||
| raw PE | Lap PE | spec PE K | ASE K | LP+LogReg | LP+plug-in | ||
|---|---|---|---|---|---|---|---|
| 500 | 1 | ||||||
| 500 | 10 | ||||||
| 1000 | 1 | ||||||
| slope (err vs ) | CV (excess) across | # points | |
|---|---|---|---|
| cap-ratio | ||||||||
|---|---|---|---|---|---|---|---|---|
| floor | ||||||||
| recovered, | – | |||||||
| recovered, |
| oracle err | plug-in err | ||||||
|---|---|---|---|---|---|---|---|
| cell | quantity | main | second |
|---|---|---|---|
| GCN+PE, | plug-in error | ( ) | ( ) |
| GAT+PE, | plug-in error | ( ) | ( ) |
| GIN+random, | plug-in error | ( ) | ( of ) |
| GIN+random, | plug-in error | ( ) | ( of ) |
| cap-ratio | excess (floor ) | ||
| cap-ratio | excess (floor ) |
Graph Representation Learning
Graph representation learning develops methods for encoding nodes, edges, and whole graphs for prediction, comparison, and transfer.
See all 320 papers