Research map / Graph learning / Graph algorithms and clustering
Complete-Tree Space Favors Data-Efficient Link Prediction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes complete-tree (CT) metric space and a leaf matching network embedding optimized via decentralized greedy navigation, with theory claiming lower sample complexity than Euclidean space for link prediction under scarce observed links.
Problem
Link prediction in data-scarce regimes where most links are unobserved, leading to insufficient sample sizes for learning.
Approach
Uses hierarchical modularity as a structural prior by embedding nodes in a discrete complete-tree metric space whose hierarchical permutation symmetries (quantified via a submetry group) yield a lower sample complexity bound than Euclidean space; optimization is reduced to averaged greedy navigation on generated computation graphs.
Key results
- At link observability 0.02, leaf matching reaches 15.60% Hits@50 on ogbl-collab vs 8.43% for LPFormer without node features and 15.55% for LPFormer with features.
- On ogbl-ppa at 0.02 observability, leaf matching achieves 0.55% Hits@100 vs 0.27% for LPFormer with features.
- Leaf matching's advantage over node2vec grows as link observability decreases from 0.9 to 0.1 across Pubmed, ICEWS18, and ogbl-collab.
- Convergence epochs scale roughly linearly with log(number of nodes) on ER and ogbl-collab networks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use leaf matching in complete-tree space instead of LPformer with node features | Link prediction · ogbl-collab, link observability 0.02 | Hits@50: 15.55 ± 1.63 -> 15.60 ± 0.24 | Helped |
| Use leaf matching in complete-tree space instead of LPformer with node features | Link prediction · ogbl-ppa, link observability 0.02 | Hits@100: 0.27 ± 0.03 -> 0.55 ± 0.04 | Helped |
| Enable node features for LPformer | LPformer · ogbl-collab, link observability 0.02 | Hits@50: 8.43 ± 3.05 -> 15.55 ± 1.63 | Helped |
| Enable node features for LPformer | LPformer · ogbl-ppa, link observability 0.02 | Hits@100: 0.19 ± 0.07 -> 0.27 ± 0.03 | Helped |
| Vary α and γ (ablation) | Leaf matching · Cora, Pubmed, Citeseer, link observability 0.1 | Evaluation metrics | No clear effect |
Surprising findings
- Poincaré hyperbolic embedding performs relatively poorly despite being a tree-like geometry, which the authors attribute to a single central point in its neighborhood structure.
- Leaf matching without node features outperforms LPFormer with node features at very low link observability.
Limitations
- Experiments restricted to link observability settings and six benchmark datasets; the theory relies on the assumption that the link probability is a strictly decreasing function of distance.
- Complete-tree structure is pre-determined (b=2, fixed k) rather than data-driven, so fit to networks lacking hierarchical modularity is unverified.
Experimental setup
Datasets: Cora Pubmed Citeseer ogbl-collab ogbl-ppa ICEWS18
Benchmarks: Cora Pubmed Citeseer ogbl-collab ogbl-ppa ICEWS18
Metrics: ROC-AUC PR-AUC F1 score Hits@50 Hits@100
Baselines: node2vec Poincaré embedding node2ket LPFormer SEAL GAE Adamic Adar Common Neighbors Jaccard Katz Index Resource Allocation Preferential Attachment
Builds on: PAC learning Kleinberg small-world navigation Krioukov hyperbolic link probability model node2vec
Closest papers by meaning
- A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.86)
- Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees (ICML 2025 · similarity 0.86)
- Revisiting Link Prediction: a data perspective (ICLR 2024 · similarity 0.86)
- Bridging Theory and Practice in Link Representation with Graph Neural Networks (NeurIPS 2025 · similarity 0.85)
- GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction (NeurIPS 2026 · similarity 0.85)
- Pure Message Passing Can Estimate Common Neighbor for Link Prediction (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.