Research map / Graph learning / Knowledge and temporal graphs
Less is More: One-shot Subgraph Reasoning on Large-scale Knowledge Graphs
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 one-shot-subgraph link prediction on large KGs: a non-parametric PPR sampler extracts one query-dependent subgraph, then a GNN predictor (DRUM/NBFNet/RED-GNN design space) runs on it, with bi-level BO-based configuration search.
Problem
Structural link prediction models on knowledge graphs do not scale because they propagate over the whole KG for each query, which is infeasible on large KGs and not fixed by vanilla sampling.
Approach
Decouple prediction into one-shot extraction of a single query-dependent subgraph using Personalized PageRank from the query entity, then predict on that subgraph with a GNN; jointly search sampler and predictor configurations via Bayesian optimization with a random forest surrogate.
Key results
- Achieves state-of-the-art MRR on WN18RR (0.567), NELL-995 (0.547), and YAGO3-10 (0.606) while using about 10% of entities per query.
- Improves Test MRR on OGBL-WIKIKG2 by 16.6% over prior structural and semantic models (0.6755 vs. best semantic 0.5794).
- Reduces training time on YAGO3-10 by about 94% for NBFNet and RED-GNN when used with subgraph sampling (28.2 min vs. 493.8 min for NBFNet).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use one-shot-subgraph prediction instead of the strongest reported baseline | link prediction · WN18RR | MRR: 0.551 -> 0.567 | Helped |
| use one-shot-subgraph prediction instead of the strongest reported baseline | link prediction · NELL-995 | MRR: 0.543 -> 0.547 | Helped |
| use one-shot-subgraph prediction instead of the strongest reported baseline | link prediction · YAGO3-10 | MRR: 0.559 -> 0.606 | Helped |
| use one-shot-subgraph prediction instead of the strongest reported baseline | link prediction · OGBL-BIOKG test | MRR: 0.8348 -> 0.8430 | Helped |
| use one-shot-subgraph prediction instead of the strongest reported baseline | link prediction · OGBL-WIKIKG2 test | MRR: 0.5794 -> 0.6755 | Helped |
| use 8 layers instead of 6 layers, with 10% of entities (ablation) | one-shot-subgraph · WN18RR | MRR: 0.566 -> 0.567 | Helped |
| use 8 layers instead of 4 layers, with 10% of entities (ablation) | one-shot-subgraph · WN18RR | MRR: 0.523 -> 0.567 | Helped |
| use 10% of entities instead of all entities, with 6 layers (ablation) | one-shot-subgraph · WN18RR | MRR: 0.543 -> 0.566 | Helped |
| use PPR sampling instead of Random Walk sampling (ablation) | one-shot-subgraph · WN18RR | MRR: 0.507 -> 0.567 | Helped |
| use PPR sampling instead of BFS sampling (ablation) | one-shot-subgraph · WN18RR | MRR: 0.543 -> 0.567 | Helped |
| add one-shot-subgraph sampling with 10% entities (ablation) | NBFNet · WN18RR | MRR: 0.551 -> 0.554 | Helped |
| add one-shot-subgraph sampling with 10% entities (ablation) | RED-GNN · YAGO3-10 | MRR: 0.559 -> 0.606 | Helped |
Surprising findings
- Using the whole graph (r_V=1.0) causes out-of-memory for deep models and degrades prediction because irrelevant entities are included.
- Sampling only 10% of entities performs better than full-graph prediction, suggesting less information can improve effectiveness.
Limitations
- Experiments are limited to link prediction on five KG benchmarks; generalization to other tasks is not evaluated.
- Search requires repeated training and Bayesian optimization over a large configuration space, adding cost.
Experimental setup
Datasets: WN18RR NELL-995 YAGO3-10 OGBL-BIOKG OGBL-WIKIKG2
Benchmarks: WN18RR NELL-995 YAGO3-10 OGBL-BIOKG OGBL-WIKIKG2
Metrics: MRR Hits@1 Hits@10 training time GPU memory
Baselines: ConvE QuatE RotatE MINERVA DRUM RNNLogic CompGCN DPMPN NBFNet RED-GNN
Builds on: NBFNet RED-GNN DRUM AdaProp NodePiece
Closest papers by meaning
- Simple is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation (ICLR 2025 · similarity 0.87)
- Context-aware Inductive Knowledge Graph Completion with Latent Type Constraints and Subgraph Reasoning (AAAI 2025 · similarity 0.87)
- Toward a Unified Statistical Theory of Unsupervised Pretraining and Supervised Neural Knowledge Graph Learning (NeurIPS 2026 · similarity 0.86)
- Towards Graph Foundation Models: Training on Knowledge Graphs Enables Transferability to General Graphs (NeurIPS 2025 · similarity 0.86)
- S²DN: Learning to Denoise Unconvincing Knowledge for Inductive Knowledge Graph Completion (AAAI 2025 · similarity 0.86)
- Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion (ICML 2025 · similarity 0.86)
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.