Research map / Graph learning / Knowledge and temporal graphs
Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
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.
Theoretical analysis of stability and generalization of subgraph reasoning models for inductive KGC, introducing Relational Tree Mover's Distance and a PAC-Bayesian bound linking stability to generalization gap, validated on WN18RR/FB15K-237/NELL-995 splits with 48 GraIL/NBFNet/RED-GNN variants.
Problem
Inductive knowledge graph completion with subgraph reasoning models lacks theoretical understanding of their stability and generalization capability.
Approach
Decomposes subgraph reasoning models into a non-parametric subgraph extractor and an SMPNN, introduces Relational Tree Mover's Distance (RTMD) to measure subgraph differences, defines stability as the inverse Lipschitz constant of the SMPNN w.r.t. RTMD, and derives a PAC-Bayesian generalization bound where the expected risk discrepancy scales with the inverse stability.
Key results
- RTMD-based SVM label classification reaches 0.8205 on WNv3, 0.7739 on FBv1 and 0.8654 on NLv2 (L=3), well above the 0.5 random baseline.
- Across 48 subgraph reasoning models, stability and generalization error are negatively correlated: Pearson -0.5759 (WNv3), -0.5134 (FBv1), -0.4912 (NLv2), all with p<0.01.
- Empirically, max score difference of GraIL grows with RTMD between subgraphs, consistent with the derived Lipschitz bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RTMD to classify triplet labels | SVM on WNv3 · WNv3 | classification accuracy: 0.5 -> 0.8204 | Helped |
| Use RTMD to classify triplet labels | SVM on FBv1 · FBv1 | classification accuracy: 0.5 -> 0.7743 | Helped |
| Use RTMD to classify triplet labels | SVM on NLv2 · NLv2 | classification accuracy: 0.5 -> 0.8652 | Helped |
| Increase RTMD depth from 2 to 3 layers (ablation) | SVM label classification · WNv3 | classification accuracy: 0.8204 -> 0.8205 | No clear effect |
| Increase RTMD depth from 2 to 3 layers (ablation) | SVM label classification · FBv1 | classification accuracy: 0.7743 -> 0.7739 | No clear effect |
| Increase RTMD depth from 2 to 3 layers (ablation) | SVM label classification · NLv2 | classification accuracy: 0.8652 -> 0.8654 | No clear effect |
| Increase model stability | Subgraph reasoning models · WNv3 | generalization error: -0.5759 | Helped |
| Increase model stability | Subgraph reasoning models · FBv1 | generalization error: -0.5134 | Helped |
| Increase model stability | Subgraph reasoning models · NLv2 | generalization error: -0.4912 | Helped |
Limitations
- Generalization bound relies on assumptions (label distribution conditional on subgraph, sufficiency of known triplets) and bounded weight norms.
- RTMD is only a pseudo-metric, and the analysis covers only the inductive setting with unseen entities, not unseen relations.
- Empirical validation is limited to three inductive datasets and correlation rather than a causal test.
Experimental setup
Datasets: WN18RR v3 FB15K-237 v1 NELL-995 v2
Benchmarks: WN18RR v3 FB15K-237 v1 NELL-995 v2
Metrics: label classification accuracy Pearson correlation generalization error empirical Lipschitz constant
Baselines: GraIL NBFNet RED-GNN
Builds on: Tree Mover's Distance GraIL NBFNet RED-GNN ReED
Closest papers by meaning
- Context-aware Inductive Knowledge Graph Completion with Latent Type Constraints and Subgraph Reasoning (AAAI 2025 · similarity 0.89)
- S²DN: Learning to Denoise Unconvincing Knowledge for Inductive Knowledge Graph Completion (AAAI 2025 · similarity 0.89)
- Towards Graph Foundation Models: Training on Knowledge Graphs Enables Transferability to General Graphs (NeurIPS 2025 · similarity 0.89)
- Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning (ICLR 2024 · similarity 0.88)
- Towards Global-Topology Relation Graph for Inductive Knowledge Graph Completion (AAAI 2025 · similarity 0.88)
- Topology of Reasoning: Understanding Large Reasoning Models through Reasoning Graph Properties (NeurIPS 2025 · similarity 0.88)
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.