Research map / Graph learning / GNN architectures

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

NeurIPS 2026 · Graph learning › GNN architectures · approach: GNN generalization theory

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a finite-sample theoretical guarantee that link-prediction pretraining of graph encoders yields embeddings linearly useful for node classification, analyzed via linear community detection in a stochastic block model.

Problem

Why an edge-level link prediction pretraining objective should yield node embeddings that are linearly useful for downstream node classification, which lacks quantitative theory.

Approach

Studies link prediction pretraining in the finite-sample stochastic block model and shows that the learned encoder-decoder embeddings support linear community detection with finite-sample guarantees.

Closest papers by meaning

• A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.90)
• GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction (NeurIPS 2026 · similarity 0.89)
• Structural Information Enhanced Graph Representation for Link Prediction (AAAI 2024 · similarity 0.89)
• NLGT: Neighborhood-based and Label-enhanced Graph Transformer Framework for Node Classification (AAAI 2025 · similarity 0.88)
• Bridging Theory and Practice in Link Representation with Graph Neural Networks (NeurIPS 2025 · similarity 0.88)
• On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks (NeurIPS 2024 · similarity 0.88)