acceptodds
Under review as a conference paper at ICLR 2027

RISE: Enhancing Knowledge Graph Completion with Large Language Models via Rollback-Guided Influential Subgraphs

Abstract

Knowledge graph completion (KGC) with large language models (LLMs) can benefit from query-specific structural context, yet two challenges remain: identifying structures that are truly relevant to a particular prediction and integrating them into LLMs without verbose graph descriptions. To address these challenges, we propose RISE, a Rollback-guided Influential Subgraph-Enhanced framework for KGC with LLMs. RISE traces triple-level knowledge graph embedding (KGE) optimization updates and uses rollback-induced prediction changes to prioritize query-candidate paths, which are aggregated into compact influential subgraphs. These subgraphs are then encoded and fused with candidate representations to form latent structural prefixes for LLM-based reranking, complementing global KGE representations and textual semantics with query-specific local structure. Experiments on four datasets show that RISE achieves the best performance on most evaluation metrics among the compared methods, while further analyses demonstrate the benefits of prediction-relevant subgraph selection and compact latent conditioning.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Knowledge Graph Completion, Large Language Models, Influential Subgraphs

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_4qmCOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Existing Knowledge Graph Completion (KGC) methods rely on embedding similarity or graph connectivity, making it difficult to identify subgraphs truly influential for query-specific predictions. Furthermore, converting graphs into text for LLM input introduces substantial computational overhead. To address these limitations, RISE records triple-level embedding updates during KGE training and measures changes in prediction probabilities through rollback. It then identifies influential paths and constructs candidate-specific influential subgraphs. The selected subgraphs are encoded using a RelGNN and fused with KGE embeddings to form a Latent Structural Soft Prefix, which guides LLM-based candidate reranking. RISE outperforms existing methods on most evaluation metrics across four KGC benchmarks.

Critical strengths
  • Well-Motivated Prediction-Aware Subgraph Selection

The paper identifies a limitation of conventional KGC subgraph selection methods: structural connectivity and heuristics may not adequately capture information useful for prediction. To address this, it proposes selecting query-specific influential subgraphs by tracking KGE optimization trajectories and measuring prediction probability changes under rollback. This prediction-sensitive approach is reasonable, as useful reasoning paths vary across queries and are difficult to define in advance. It enables the selection of predictive structural information without explicit path-level supervision.

  • Comprehensive Experimental Evaluation

The paper evaluates its method on four datasets (Kinship-MH, UMLS, FB15K-237, and CoDEx-L), outperforming various KGC baselines on most metrics. Using the same Qwen3-8B backbone for applicable LLM-based baselines also improves comparison fairness. Figure 3 shows that rollback-guided selection outperforms structural plausibility and trajectory-magnitude-based selection, supporting the effectiveness of the proposed mechanism. Table 2 and additional analyses across KGE and LLM backbones further validate the main components. Overall, the experimental evaluation is comprehensive.

  • Efficient Integration of Structural Information Through Latent Conditioning

Instead of converting selected subgraphs into natural language, the method encodes them into compact latent structural prefixes using a RelGNN and an adapter. Maintaining a fixed K+2K+2 prefix tokens regardless of subgraph size reduces the overhead of lengthy text-based graph serialization while preserving structural information. The ablation results further support the effectiveness of this design.

Critical weaknesses
  • Limited Methodological Novelty

A major concern is the substantial overlap between RISE and prior work. Gradient Rollback (Lawrence et al., 2021) already introduced rollback-based influence estimation, while GradPath (Di Mauro et al., 2024) and KGExplainer (Ma et al., 2025) explored prediction-aware path and subgraph selection. Similarly, incorporating KGE embeddings or query-specific subgraphs into LLMs through soft prefixes and graph encoders has been studied in KoPA (Zhang et al., 2024) and DrKGC (Xiao et al., 2025). Thus, RISE's primary contribution appears to be the integration of existing rollback-based influence estimation and subgraph encoding techniques into an LLM-based KGC framework, rather than a fundamentally new methodology.

  • Downstream-Specific Optimization and Limited Generalizability

RISE selects influential subgraphs based on KGE prediction sensitivity for specific query–candidate pairs, followed by query-conditioned RelGNN encoding and LLM reranking. Consequently, the entire pipeline is closely tied to the downstream tail prediction objective. While task-specific optimization is reasonable, high prediction sensitivity does not necessarily imply general structural utility. Subgraph usefulness may depend on other criteria, such as structural sufficiency, path simplicity, or interpretability. The paper should clarify the scope and generalizability of its definition of influential subgraphs.

  • Insufficient Justification of Selected Path Quality

The case study in Table 3 does not convincingly demonstrate that RISE selects better subgraphs than existing methods. For the query (Marco, husband of, ?), both DrKGC and RISE correctly predict Lucia, despite selecting 2-hop and 3-hop paths, respectively. It remains unclear what additional predictive value RISE's longer path provides. Although longer paths are not necessarily inferior, path quality should be evaluated based on their contribution to prediction rather than structural complexity alone. Similarly, the improvements observed with longer maximum exploration lengths in Figure 10 may result from increased candidate-path diversity rather than the inherent usefulness of longer paths.

  • Methodological Complexity and Computational Overhead

RISE involves multiple components, including optimization trajectory tracing, path enumeration, dual-criterion preselection, rollback scoring, relational graph encoding, gated fusion, contrastive learning, and LLM reranking. Although ablation studies partially validate these components, the overall framework remains complex. In particular, trajectory map storage reaches 7.90 GB on FB15K-237 and 15.80 GB on CoDEx-L, while rollback-guided subgraph construction introduces additional offline computation. These computational and storage requirements raise concerns about the scalability and practical efficiency of the proposed approach.

Questions for authors

See Weakness.

7 comments
AuthorsOpenReview ↗

Summary of Paper Revision

Summary of Paper Revision

We have revised the paper to address reviewer 4qmC's concerns and questions as follows:

  1. For W1, we have clarified two contributions: efficient rollback-guided selection, combining structural/trajectory preselection with bounded target-level scoring to avoid GradPath's path-internal influence evaluations; and candidate-specific structural learning, independently selecting and encoding query-conditioned subgraphs to preserve candidate–evidence correspondence through reranking, distinguishing RISE from KoPA's embedding prefixes and DrKGC's shared query graph. We have revised the contributions in Section 1 and the prior-work distinctions in Section 2, and have added the GradPath selector comparison and analysis to Figure 3.

  2. For W2, we have clarified that "influential" denotes model- and prediction-specific sensitivity: rollback-induced reductions in candidate log-probability guide the selection of compact, structurally plausible evidence for reranking. The diagnostics in Table 4 of Section 4.4, with further analysis in Appendix F, have demonstrated additional predictive value when path count, length, and structural/trajectory scores are controlled. We have also expanded Appendix H to examine applicability to noisy, inductive, evolving, and sparser KGs.

  3. For W3, we have clarified the case-study interpretation in Section 4.5, revised the Figure 9 discussion, and added "Path-Length Distributions and Rollback Selection" to Appendix H. We have explained that broader exploration expands the available evidence, while length-normalized rollback sensitivity determines path selection. The new statistics (Tables 19-20) have shown that two-hop paths remain dominant under default retention budgets, supporting selective use of a richer path pool rather than an inherent advantage of longer paths.

  4. For W4, we have updated "Trajectory Storage and Loading Costs" and added "Component-Level Cost Analysis" to Appendix E. Across four datasets, lossless NPZ reduces storage by 87.7–88.0% and provides 8.42–13.43× loading speedups. UMLS profiling shows under 0.20 s/query and 138 MB working set per non-LLM component. We have also updated the performance-latency comparison, showing that RISE achieves the highest MRR (47.8%) with competitive online latency (2.21 s/query) on FB15K-237.

  5. In addition, because we have evaluated broader generalization settings and substantially reduced trajectory-storage costs through lossless NPZ storage, we have updated the limitations in Section 5 "Conclusion" accordingly.

AuthorsOpenReview ↗

Detailed Responses to Reviewer 4qmC (1/3)

Detailed Responses

We thank the reviewer for the constructive feedback. We clarify RISE's methodological contributions and scope, and provide additional evidence on generalization, path quality, and computational efficiency below.

-W1. Clarifying Methodological Contributions

Our contribution lies in constructing rollback-guided influential subgraphs as candidate-specific structural evidence for LLM-based KGC, preserving candidate–evidence correspondence from selection to reranking. This is the motivation behind "Rollback-Guided Influential Subgraphs" in our title: determining which local structures support each candidate prediction and learning how to use those structures to distinguish competing candidates.

1) Efficient construction of influential subgraphs. GradPath evaluates both target-level influence and dependencies among path triples, requiring additional rollback-based probability evaluations. Our RISE controls path quality through structural/trajectory preselection, then evaluates only the target prediction's rollback sensitivity over a bounded path pool. This eliminates path-internal influence evaluations and limits expensive rollback scoring for each candidate, while retaining paths whose recorded updates support that candidate prediction. The resulting subgraphs provide prediction-relevant evidence for reranking at substantially lower construction cost: RISE achieves 5.3×/3.3× faster construction on UMLS/FB15K-237, while matching UMLS MRR and improving FB15K-237 MRR by 1.2 percentage points (Tab.1). Relative to Dual (without rollback), RISE also improves MRR by 4.0 and 3.0 percentage points on UMLS and FB15K-237, respectively, supporting rollback's additional value beyond structural/trajectory preselection.

Tab.1 Path-selector comparison

DatasetMethodMRR (%)↑Subgraph construction time (s/query)↓
UMLSRISE w/ GradPath90.94.42
RISE w/ Dual (S_struct and S_trace only)86.90.75
RISE90.90.84
FB15K-237RISE w/ GradPath46.65.36
RISE w/ Dual (S_struct and S_trace only)44.81.24
RISE47.81.64

2) From global embeddings or shared graphs to candidate-specific evidence. KoPA uses pretrained embedding prefixes, while DrKGC derives candidate embeddings from a shared, rule-guided query graph. RISE independently selects a query-sensitive subgraph for each candidate and fuses its query-conditioned representation with the candidate's global embedding. This helps the reranker distinguish competing candidates using local evidence relevant to the current query. Table 3 in the paper further supports our representation design: removing subgraph representations or query conditioning reduces performance on both datasets, indicating that local structural evidence and query-conditioned encoding both contribute to candidate reranking.

-W2. Clarifying Scope and Generalizability

1) Scope and selection criteria. We clarify that "influential" denotes model- and prediction-specific sensitivity. For a fixed KGE and its recorded updates, RISE preselects query-candidate paths using structural/trajectory scores, then prioritizes them by length-normalized rollback-induced reductions in candidate log-probability. Structural quality and path simplicity are incorporated into selection: S_struct favors plausible facts, while bounded path lengths/counts encourage compact evidence (Figures 9-10 in the paper). The case study (Table 5 in the paper) illustrates relational chains.

2) Downstream predictive value of influential subgraphs. We added Matched Path Replacement, replacing selected paths with alternatives of the same length and similar structural/trajectory scores, while preserving path count. Tab.2 shows that RISE outperforms this control on both datasets, supporting the selected evidence's predictive value beyond these controls.

Tab.2 Downstream value of selected paths

VariantUMLS (MRR / H@1)FB15K-237 (MRR / H@1)
RISE w/ Dual (S_struct and S_trace only)86.9 / 84.944.8 / 38.7
RISE w/ Matched Path Replacement89.6 / 87.146.7 / 40.1
Our RISE90.9 / 89.147.8 / 41.5

The remainder of our response to W2, addressing generalization across KG conditions, is provided in the next comment.

AuthorsOpenReview ↗

Detailed Responses to Reviewer 4qmC (2/3)

3) Generalization across KG conditions. We further examine whether our RISE's predictive utility extends to noisy KGs, inductive KGs, evolving KGs and sparser KGs.

Under noisy KGs, we evaluated entity mislinking and relation mislabeling. Tab.3 shows that RISE consistently outperforms Dual, with its MRR advantage generally widening as noise increases. This advantage is consistent with candidate-specific prediction sensitivity: rollback evaluates how path-associated updates affect the candidate prediction, providing relevance information beyond structural plausibility and update magnitude to guide evidence selection under noise.

Tab.3 Robustness to noisy KGs

(a) Entity mislinking

DatasetNoise rateDual (MRR / H@1)RISE (MRR / H@1)RISE−Dual (MRR / H@1)
UMLS0%86.9 / 84.990.9 / 89.1+4.0 / +4.2
5%86.2 / 84.391.0 / 89.1+4.8 / +4.8
10%85.4 / 83.190.1 / 88.2+4.7 / +5.1
20%78.4 / 73.284.0 / 78.2+5.6 / +5.0
FB15K-2370%44.8 / 38.747.8 / 41.5+3.0 / +2.8
5%41.6 / 35.245.1 / 38.2+3.5 / +3.0
10%39.6 / 33.443.2 / 36.4+3.6 / +3.0
20%36.8 / 30.740.4 / 33.5+3.6 / +2.8

(b) Relation mislabeling

DatasetNoise rateDual (MRR / H@1)RISE (MRR / H@1)RISE−Dual (MRR / H@1)
UMLS0%86.9 / 84.990.9 / 89.1+4.0 / +4.2
5%86.6 / 85.390.9 / 90.0+4.3 / +4.7
10%83.9 / 82.390.5 / 88.5+6.6 / +6.2
20%75.5 / 70.882.9 / 78.8+7.4 / +8.0
FB15K-2370%44.8 / 38.747.8 / 41.5+3.0 / +2.8
5%38.2 / 30.141.9 / 32.5+3.7 / +2.4
10%32.0 / 22.336.1 / 24.0+4.1 / +1.7
20%19.0 / 8.223.5 / 9.0+4.5 / +0.8

For inductive KGs, five support facts per unseen entity enable embedding adaptation and provide recorded updates for rollback. Tab.4 shows that RISE achieves the highest MRR across all six settings. Its query-conditioned encoder reuses learned relational patterns to exploit multi-hop evidence connecting unseen entities to existing neighborhoods, complementing limited embedding adaptation.

Tab.4 Performance on inductive KGs (%)

Dataset#Unseen Entities#QueriesDrKGC (MRR / H@1)FtG (MRR / H@1)SRP-KGC (MRR / H@1)Ours (MRR / H@1)
UMLS1015247.3 / 34.930.7 / 24.353.1 / 48.764.3 / 57.9
2022742.1 / 30.428.4 / 21.649.8 / 45.457.4 / 51.1
3027734.1 / 24.222.9 / 16.643.6 / 38.645.8 / 39.0
FB15K-23710045431.3 / 22.528.9 / 21.837.6 / 34.838.3 / 33.9
20079926.1 / 18.124.2 / 15.830.7 / 27.833.6 / 27.0
300166520.4 / 13.922.1 / 14.725.3 / 22.628.4 / 23.8

For evolving KGs, we started with 90% of training facts and added the remainder in two equal batches, keeping validation/test sets fixed and recording new KGE updates for rollback. Tab.5 shows that RISE achieves the highest MRR and H@1 on both datasets in both rounds. Its advantage is consistent with candidate-specific use of updated evidence: recorded updates guide rollback-based path selection, while query-conditioned encoding integrates the selected structures into LLM reranking.

Tab.5 Performance under evolving KGs (%)

DatasetUpdate roundRotatE Recall@30DrKGC (MRR / H@1)FtG (MRR / H@1)SRP-KGC (MRR / H@1)Ours (MRR / H@1)
UMLS1st97.079.8 / 74.458.2 / 49.844.1 / 36.890.5 / 88.5
UMLS2nd97.181.6 / 73.758.0 / 50.545.1 / 37.890.8 / 88.7
FB15K-2371st68.542.8 / 33.741.6 / 33.545.0 / 37.248.1 / 41.3
FB15K-2372nd67.943.3 / 35.041.2 / 33.745.2 / 37.447.5 / 40.9

For sparser KGs, training-fact deletion (Figure 12) examines 0–30% removal on UMLS. RISE tolerates modest removal, consistent with its ability to select useful evidence from the remaining paths. Heavier deletion causes greater degradation, suggesting that fewer alternative connections limit the structural context available for reranking.

Reviewer_GqZHOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents RISE, a reranking‑oriented framework for LLM‑based knowledge graph completion (KGC). Observing that existing subgraph‑augmented LLM‑KGC methods select subgraphs purely based on connectivity or heuristic plausibility (which may include redundant or low‑utility paths), RISE leverages KGE training optimization trajectories and rollback perturbation scoring to identify candidate‑specific influential multi‑hop subgraphs. Instead of verbalizing subgraphs into lengthy text prompts, it encodes subgraphs into compact latent structural soft prefixes and prepends them to LLM inputs, avoiding token‑length explosion.

Critical strengths
  1. Use KGE method and LLM for re-rank is not novel. Actually, source from EMNLP 2023, a main stream of works are follow this, and have extend much variants, including training for searching/reteriving, demonstration ranking and LLM re-ranking, rl/sft are also incomed in this procedure. However, the paper correctly points out that “being structurally connected” ≠ “being useful for this specific query‑candidate prediction”. Simply enumerating shortest paths or neighborhoods brings noisy redundant context, which hurts LLM performance. Using rollback on KGE optimization trajectories to score path influence is an interesting conceptual angle for subgraph filtering. This works for me.
  2. Instead of serializing subgraph facts into text (which inflates input length and forces LLM to reason over raw text), the work encodes subgraph information as fixed‑size continuous soft tokens. The LLM input sequence length is decoupled from subgraph complexity, which is a meaningful engineering advantage for inference efficiency.
Critical weaknesses
  1. Strong transductive setting & hard dependency on pre‑trained KGE quality and candidate recall ceiling (major limitation)
  • RISE works in transductive setup: trajectory records and subgraph enumeration are fully built upon training‑set triples. It cannot directly handle inductive KGC where unseen entities/relations appear at test time. The paper only briefly mentions this as future work without any preliminary investigation.
  • The whole pipeline is a reranking paradigm. If the ground‑truth entity is not included inside the top‑K candidates retrieved by RotatE, RISE cannot recover it. The final performance is upper‑bounded by KGE recall@K. While the authors report recall statistics, there is little discussion on how this bottleneck impacts real‑world open‑KG scenarios where recall is often low.
  • Rollback scoring signal is derived from the specific KGE backbone (RotatE / ComplEx). It remains unclear how noisy or unstable the rollback sensitivity score would be when using weaker or different KGE architectures.
  1. Non‑trivial offline computation & storage overhead, insufficient real‑world scalability discussion
  • The method requires storing triple‑level optimization trajectories. On large‑scale datasets like CoDEx‑L the trajectory map reaches 15.8GB. Besides storage, multi‑hop path enumeration plus per‑path rollback‑perturbed KGE scoring introduces heavy offline preprocessing cost.
  • The paper reports offline preprocessing is done one‑time; but for evolving real‑world KGs where training triples are frequently updated, re‑computing trajectory maps and re‑scoring all query‑candidate subgraphs would be prohibitively expensive. There is no analysis or mitigation discussion for incremental / evolving KG scenarios.
  1. Limited understanding of rollback‑score behaviour. Appendix F admits that rollback score SrollS_{roll} naturally gives higher weight to paths touching query head/relation/target candidate, while intermediate‑entity‑heavy multi‑hop paths may be under‑valued. The authors treat this only as a note and use it purely for path ranking. There is no diagnostic ablation: e.g. compare a simplified heuristic variant which discards rollback and only uses Sstruct+StraceS_{struct}+S_{trace}. Although Figure3 shows full pipeline outperforms Dual variant, it is still unclear how much genuine new signal rollback brings beyond the two preselection terms.

  2. Evaluation scope stays within standard static KGC benchmarks only. All experiments are conducted on conventional static link‑prediction benchmarks. There is no extension to more practical downstream tasks such as KGQA, multi‑hop reasoning under noise, or low‑resource KG settings. It is hard to tell whether the gains transfer beyond standard KGC reranking.

Questions for authors

Please see my comments in weakness.

6 comments
AuthorsOpenReview ↗

Summary of Paper Revision

Summary of Paper Revision

We have revised the paper to address reviewer GqZH's concerns and questions as follows:

  1. For W1.(1), we have added "Generalization to Inductive Settings" and Table 24 to Appendix H, covering six unseen-entity settings. We have explained how five support facts per entity enable new-entity embedding adaptation and rollback scoring from recorded adaptation updates, addressing the representation and trajectory challenges for unseen entities. RISE achieves the highest MRR across all six settings, with analysis linking its advantage to reusable, query-relevant relational patterns.

  2. For W1.(2), we have added "Raising the Recall Ceiling with Alternative Candidate Sources" and "Performance under Low Candidate Recall" to Appendix G. We have shown that using KG-FIT or combining RotatE and ComplEx improves candidate recall and final prediction performance at the same K = 30, alleviating the retrieval bottleneck. We have also confirmed RISE's effectiveness under low candidate coverage.

  3. For W1.(3), we have added "Rollback Contributions across KGE Backbones" and "Sensitivity to Rollback Magnitude" to Appendix F, to assess rollback's effectiveness across KGE architectures and the stability of path selection under changes in rollback magnitude.

  4. For W2.(1), we have updated "Trajectory Storage and Loading Costs" and added "Offline Subgraph Construction Cost" to Appendix E. Across all four datasets, lossless NPZ reduces storage by 87.7–88.0% and delivers 8.42–13.43× loading speedups. Compared with Dual, rollback adds 0.09/0.40 s/query while yielding 4.0/3.0 pp MRR gains on UMLS/FB15K-237, quantifying its performance-cost trade-off.

  5. For W2.(2), we have added "Incremental Updates for Evolving KGs" to Appendix H. RISE achieves the highest MRR and H@1 on both datasets in both update rounds. Its advantage is consistent with candidate-specific use of updated graph evidence: recorded KGE updates guide rollback-based path selection, while query-conditioned encoding integrates the selected structures into LLM reranking.

  6. For W3, we have added "Analysis of Rollback Mechanism" to Section 4.4, to examine rollback's predictive value beyond structural/trajectory preselection and the additional contribution of intermediate-entity updates.

  7. For W4, we have added "Model Performance on Noisy KGs" to Appendix H and a new Appendix I "Downstream Multi-hop KGQA" to evaluate robustness to graph corruption and the downstream utility of RISE's predicted facts.

  8. In addition, because we have evaluated broader generalization settings and substantially reduced trajectory-storage costs through lossless NPZ storage, we have updated the limitations in Section 5 "Conclusion" accordingly.

AuthorsOpenReview ↗

Detailed Responses to Reviewer GqZH (1/4)

Detailed Responses

We thank the reviewer for the constructive feedback. We address all these concerns below with additional experiments on generalization, rollback diagnostics, and efficiency analyses.

-W1.(1) Exploring Inductive Extensions

To explore an inductive extension of our RISE, we evaluated settings with 10/20/30 held-out UMLS entities and 100/200/300 held-out FB15K-237 entities, following the protocol below. 1) Entity selection. We randomly selected entities, requiring their occurrence in the original test set and at least five training facts connecting each to seen entities. 2) Training. We excluded all training/validation triples involving held-out entities from base training and model selection, and trained the models on the remaining training graph. 3) Adaptation. We used five original-training support triples per held-out entity, excluding unordered entity pairs present in validation/test sets; other removed training facts remained unused. We randomly initialized and optimized only the new-entity embeddings, keeping existing entity and relation embeddings frozen. We accumulated updates per support fact and scored each path by the length-normalized drop in candidate log-probability after rolling back its associated updates. 4) Evaluation. We evaluated all original-test triples involving held-out entities, retrieving candidates from the full entity vocabulary. Inference used only base-training and support triples; test triples were excluded from adaptation.

Tab.1 shows that RISE achieves the highest MRR across all tested inductive settings, with the highest H@1 on UMLS and competitive H@1 on FB15K-237. This advantage is consistent with RISE's reuse of query-relevant relational patterns: its query-conditioned subgraph encoder captures multi-hop evidence connecting unseen entities to existing graph neighborhoods through support facts, complementing limited embedding adaptation with learned structural knowledge. RISE maintains its MRR advantage as more entities are held out, supporting this adaptation strategy.

Tab.1 Performance on inductive settings

Dataset#Unseen Entities#QueriesDrKGC (MRR / H@1)FtG (MRR / H@1)SRP-KGC (MRR / H@1)Ours (MRR / H@1)
UMLS1015247.3 / 34.930.7 / 24.353.1 / 48.764.3 / 57.9
2022742.1 / 30.428.4 / 21.649.8 / 45.457.4 / 51.1
3027734.1 / 24.222.9 / 16.643.6 / 38.645.8 / 39.0
FB15K-23710045431.3 / 22.528.9 / 21.837.6 / 34.838.3 / 33.9
20079926.1 / 18.124.2 / 15.830.7 / 27.833.6 / 27.0
300166520.4 / 13.922.1 / 14.725.3 / 22.628.4 / 23.8

-W1.(2) Exploring Beyond the Recall Ceiling

Stronger or complementary retrieval raises the recall ceiling. Tab.2 shows that using KG-FIT (Jiang et al., NeurIPS 2024) or combining RotatE and ComplEx can improve both candidate recall and final prediction performance at the same K=30, demonstrating a practical way to alleviate the retrieval bottleneck.

Tab.2 Impact of Candidate Sources on FB15K-237

Candidate sourceKRecall@KRISE MRRRISE H@1
RotatE3068.747.841.5
KG-FIT3073.250.344.2
RotatE + ComplEx3071.048.842.1

RISE remains effective under low candidate recall. We select relations with filtered Recall@30 ≤ 50% on the validation set and evaluate all corresponding test queries. Tab.3 shows that RISE outperforms both RotatE and Dual (without rollback), even when test Recall@30 is only around 23%.

Tab.3 Low-recall group analysis

Dataset#Relations#QueriesRecall@30RotatE (MRR / H@1)Dual (MRR / H@1)RISE (MRR / H@1)
FB15K-23766707723.566.48 / 3.3211.32 / 6.5814.47 / 9.91
CoDEx-L9185022.546.46 / 2.867.53 / 4.7011.44 / 7.84

The full-test results also show gains without near-perfect candidate recall. The evaluation in Tables 1 & 16 of the paper includes queries whose answers fall outside the retrieved candidate set. RISE outperforms both RotatE and DrKGC under the same candidate coverage, demonstrating more effective use of the available candidates.

Tab.4 Full-test results (Tables 1 & 16 in the paper)

DatasetRecall@30RotatE MRRDrKGC MRRRISE MRR
FB15K-23768.735.443.347.8
CoDEx-L77.537.539.748.5
AuthorsOpenReview ↗

Detailed Responses to Reviewer GqZH (2/4)

-W1.(3) Rollback Robustness across KGE Backbones

Rollback provides consistent gains across all four tested KGE backbones. Tab.5 shows that enabling rollback improves both MRR and H@1 on both datasets relative to the variant without rollback, supporting the signal's usefulness across different KGE architectures.

Tab.5 Rollback contribution across KGE backbones

DatasetKGEw/o rollback (MRR / H@1)w/ rollback (MRR / H@1)ΔMRR / ΔH@1
UMLSTransE81.7 / 79.686.2 / 82.5+4.5 / +2.9
DistMult80.0 / 77.683.8 / 80.5+3.8 / +2.9
ComplEx84.2 / 80.889.3 / 86.2+5.1 / +5.4
RotatE86.9 / 84.990.9 / 89.1+4.0 / +4.2
FB15K-237TransE39.7 / 32.943.9 / 36.3+4.2 / +3.4
DistMult42.7 / 34.246.4 / 38.1+3.7 / +3.9
ComplEx44.1 / 35.747.6 / 39.4+3.5 / +3.7
RotatE44.8 / 38.747.8 / 41.5+3.0 / +2.8

Path selection remains largely consistent under a uniform 10% increase or decrease in rollback magnitude, supporting local stability. Tab.6 further compares independent per-path perturbations and unbounded random scaling, illustrating how perturbation structure and magnitude affect path retention across KGE backbones.

Tab.6 Path retention relative to the original rollback setting

DatasetKGE90% rollback110% rollbackRandom ±10%Unbounded random
UMLSTransE96.90%97.27%69.37%10.96%
DistMult99.19%99.40%58.58%14.26%
ComplEx98.49%98.55%55.43%13.01%
RotatE85.74%95.46%84.79%19.86%
FB15K-237TransE98.30%98.43%85.89%35.42%
DistMult99.46%99.47%85.60%40.30%
ComplEx99.52%99.50%86.14%42.67%
RotatE96.96%97.31%82.56%34.80%

All backbones share 500 test queries per dataset and fixed preselected pools. Paths are reselected after update rescaling. Random per-path multipliers follow Uniform[0.9, 1.1] or Exponential(rate = 1), with results averaged over three repetitions. Query-averaged path retention excludes initially empty selections and assigns zero to newly empty ones.

RISE's end-to-end gains extend across KGE backbones, as shown in Figure 4 and summarized in Tab.7. RISE ranks paths within each query–candidate pair using backbone-specific sensitivity scores.

Tab.7 Existing FB15K-237 results (Figure 4 in the paper)

KGEOriginal KGE MRROurs MRRΔMRR
TransE35.143.9+8.8
DistMult34.946.4+11.5
ComplEx35.847.6+11.8
RotatE35.447.8+12.4

-W2.(1) Offline Computation and Storage Costs

Trajectory storage and loading costs drop substantially with lossless NPZ storage. Tab.8 shows that, on CoDEx-L, storage drops from 15.84 to 1.95 GiB (87.7% reduction), while loading time falls from 300.15 to 22.48 s (13.4× speedup). Conversion from JSON preserves all values, keys, and indices, with exact equality verified across all datasets.

Tab.8 Reduced trajectory storage and loading costs with lossless NPZ

DatasetJSON size / load timeNPZ size / load timeSize reduction factor / Loading speedup
Kinship-MH3.53 MiB / 0.064 s0.43 MiB / 0.0076 s8.21× / 8.42×
UMLS154.28 MiB / 2.67 s18.56 MiB / 0.22 s8.31× / 12.14×
FB15K-2377.90 GiB / 150.38 s0.96 GiB / 11.20 s8.23× / 13.43×
CoDEx-L15.84 GiB / 300.15 s1.95 GiB / 22.48 s8.12× / 13.35×

Offline Construction Cost. Tab.9 shows that our RISE constructs subgraphs faster than GradPath, with only a small overhead over Dual (struct and trace score without rollback). All methods use identical queries (500 per split) and 30 candidates per query, timed independently on one GPU in a single process without cross-query caching.

Tab.9 Average offline subgraph construction time (s/query)

DatasetGradPathDualRISE
UMLS4.420.750.84
FB15K-2375.361.241.64

Rollback cost and gains. Compared with Dual, RISE adds only 0.09 and 0.40 s/query on UMLS and FB15K-237, respectively. Figure 3 in the paper shows corresponding MRR gains of 4.0 and 3.0 pp. These results quantify the performance-cost trade-off.

Reviewer_KUwTOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Existing knowledge graph completion (KGC) with large language models (LLMs) suffers from two major weaknesses. This paper presents RISE, a Rollback guided Influential Subgraph Enhanced framework for LLM based knowledge graph completion. Experiments across four datasets show that the proposed approach obtains state of the art results on most evaluation metrics among all compared baselines.

Critical strengths
  1. The manuscript is well structured and well organized.
  2. Technical implementation details are clearly described.
  3. Empirical results validate the effectiveness of the proposed method.
Critical weaknesses
  1. Statistical significance tests are absent. It cannot be confirmed whether the observed performance gains stem from random experimental fluctuations.
  2. In depth analysis interpreting the underlying causes behind experimental observations is missing; the paper mainly reports experimental numbers without digging into why such results are obtained.
Questions for authors
  1. The paper states that the proposed method focuses on tail entity prediction. Could the authors clarify how tail entities are formally defined in their setting?
  2. How does the proposed framework perform when the input knowledge graph contains initial noisy triples or noisy entities?
  3. What key conditions determine whether this trajectory based rollback mechanism yields good or poor performance?
  4. What are the main technical challenges to extend the proposed RISE to inductive settings with unseen entities at test time?
6 comments
AuthorsOpenReview ↗

Summary of Paper Revision & Detailed Responses to Reviewer KUwT (1/3)

Summary of Paper Revision

We have revised the paper to address reviewer KUwT's concerns and questions as follows:

  1. For W1, we have added "Statistical Reliability" to Section 4.2 "Main Results", including three-run mean±std results in new Table 2. RISE achieves the highest mean MRR and H@1 among the evaluated methods on all four datasets, with small cross-seed variability, supporting the reliability of its performance gains.

  2. For W2, we have improved the analysis in Sections 4.2-4.4 and Appendices F-H to explain how RISE addresses candidate ambiguity that global KGE embeddings and textual associations alone cannot resolve. Overall, rollback-guided subgraphs supply local relational evidence specific to each candidate prediction, while query-conditioned structural encoding enables the LLM to use this evidence to distinguish plausible but incorrect targets, as supported by selector comparisons and ablations.

  3. For Q1, we have clarified at the start of Section 3 that the tail is the object tt in a directed triple (h,r,t)(h,r,t), and tail prediction identifies the missing entity given (h,r,?)(h,r,?).

  4. For Q2, we have added "Model Performance on Noisy KGs" and new Table 23 to Appendix H. RISE consistently outperforms Dual in MRR and H@1 under both entity mislinking and relation mislabeling, although performance generally declines as noise increases. Beyond Dual's structural and trajectory scores, RISE uses rollback-induced changes in each candidate's prediction to prioritize candidate-relevant paths, helping suppress noisy connections that appear plausible but are less useful for reranking.

  5. For Q3, we have refined the discussion in Appendix F to identify rollback-signal informativeness and relevant-path availability as key factors. Rollback adds selection value beyond structural/trajectory scores, while broader preselection followed by compact retention helps exploit available paths, as supported by rollback diagnostics (Tables 4 and 14), path-length statistics (Tables 19-20), noisy KGs (Table 23), and path-budget and training-fact deletion experiments (Figures 8, 10, and 12).

  6. For Q4, we have added "Generalization to Inductive Settings" and Table 24 to Appendix H, covering six unseen-entity settings. We have explained how five support facts per entity enable new-entity embedding adaptation and rollback scoring from recorded adaptation updates, addressing the representation and trajectory challenges for unseen entities. RISE achieves the highest MRR across all six settings, with analysis linking its advantage to reusable, query-relevant relational patterns.

  7. In addition, because we have evaluated broader generalization settings and substantially reduced trajectory-storage costs through lossless NPZ storage, we have updated the limitations in Section 5 "Conclusion" accordingly.


Detailed Responses

We thank the reviewer for the constructive feedback. We address each concern below with additional experiments, analysis, and clarifications.

-W1. Statistical Reliability

For each dataset, we selected key competing methods and evaluated them over three independent runs using different seeds (3407, 42, 123). As shown in Tab.1, our RISE achieves the highest performance across all four datasets while maintaining small cross-seed fluctuations. These results support both the effectiveness and stability of our RISE.

Tab.1 Three-run mean±std (%)

MethodsKinship-MH (MRR / H@1)UMLS (MRR / H@1)FB15K-237 (MRR / H@1)CoDEx-L (MRR / H@1)
SSQR19.32±1.36 / 7.97±1.2676.57±0.39 / 67.62±0.3045.29±0.16 / 38.87±0.1738.41±0.16 / 28.55±0.13
DrKGC80.74±1.23 / 67.39±2.1780.44±0.81 / 73.93±0.6342.88±0.43 / 33.89±0.4340.08±0.33 / 28.79±0.20
ST-KGLP70.73±0.79 / 62.32±1.2688.63±0.57 / 86.74±0.3843.58±0.22 / 35.75±0.2145.41±0.17 / 34.57±0.18
Our RISE87.38±0.97 / 76.81±1.2690.69±0.18 / 88.96±0.1547.66±0.21 / 41.30±0.1748.34±0.12 / 37.31±0.11
AuthorsOpenReview ↗

Detailed Responses to Reviewer KUwT (2/3)

-W2. In-depth Experimental Analysis

We have refined the analysis in Sections 4.2-4.4 and Appendices F-H to explain how candidate-specific relational evidence helps resolve ambiguity left by global KGE embeddings and textual associations. Rollback-guided subgraphs supply local evidence supporting each candidate prediction, while query-conditioned structural encoding enables the LLM to use this evidence to distinguish competing candidates. Selector comparisons show that random paths can hurt reranking, while ablations show that removing subgraph representations or query conditioning reduces performance, supporting the importance of both evidence relevance and structural integration.

We further compared Dual (structure + trace scores, without rollback), Query-Parameter Rollback (query-related parameters only), and Ours (full rollback). Tab. 2 shows that query-parameter rollback captures most of the MRR gains over Dual, highlighting the value of query-specific prediction sensitivity. Full rollback further improves MRR and H@1, supporting the additional value of intermediate-entity updates.

Tab.2 Rollback mechanism analysis (%)

DatasetVariantMRRH@1
UMLSQuery-Parameter Rollback89.887.0
Dual (S_struct and S_trace only)86.984.9
Ours (full rollback)90.989.1
FB15K-237Query-Parameter Rollback47.440.8
Dual (S_struct and S_trace only)44.838.7
Ours (full rollback)47.841.5

-Q1. Definition of Tail Entity Prediction

We have added a clarification at the start of Section 3 (Methodology). In a knowledge graph G=(E,R,T)\mathcal{G}=(\mathcal{E},\mathcal{R},\mathcal{T}), each directed triple (h,r,t)(h,r,t) connects head entity hh to tail entity tt through relation rr. Thus, the tail entity is the object of the relation in that triple. Given a query (h,r,?)(h,r,?), tail entity prediction aims to identify entities t∈Et \in \mathcal{E} for which (h,r,t)(h,r,t) holds.

For the paper's example (Iron Man, created by, ?), Iron Man is the head entity, and Stan Lee is the correct tail entity. Head/tail roles depend on the triple: the same entity can serve as a head in other triples.

-Q2. Model Performance on Noisy KGs

We evaluated entity mislinking and relation mislabeling by adding corrupted triples to the training graph while retaining all original triples. The noise rate was the number of added corrupted triples divided by the original training-set size; validation/test sets remained clean and unchanged. As shown in Tab.3, the largest MRR drop occurs between 10% and 20% noise across both datasets and noise types. Although noise hurts performance, our RISE's MRR advantage over the Dual variant (structure + trace scores, without rollback) widens overall as noise increases. These gains suggest that rollback complements structural plausibility and update magnitude by evaluating each path's support for the current candidate prediction, helping limit distraction from plausible but weakly supportive noisy connections.

Tab.3 Robustness to KG Noise (%)

(a) Entity mislinking

DatasetNoise rateDual (MRR / H@1)Ours (MRR / H@1)Ours-Dual (MRR / H@1)
UMLS0%86.9 / 84.990.9 / 89.1+4.0 / +4.2
5%86.2 / 84.391.0 / 89.1+4.8 / +4.8
10%85.4 / 83.190.1 / 88.2+4.7 / +5.1
20%78.4 / 73.284.0 / 78.2+5.6 / +5.0
FB15K-2370%44.8 / 38.747.8 / 41.5+3.0 / +2.8
5%41.6 / 35.245.1 / 38.2+3.5 / +3.0
10%39.6 / 33.443.2 / 36.4+3.6 / +3.0
20%36.8 / 30.740.4 / 33.5+3.6 / +2.8

(b) Relation mislabeling

DatasetNoise rateDual (MRR / H@1)Ours (MRR / H@1)Ours-Dual (MRR / H@1)
UMLS0%86.9 / 84.990.9 / 89.1+4.0 / +4.2
5%86.6 / 85.390.9 / 90.0+4.3 / +4.7
10%83.9 / 82.390.5 / 88.5+6.6 / +6.2
20%75.5 / 70.882.9 / 78.8+7.4 / +8.0
FB15K-2370%44.8 / 38.747.8 / 41.5+3.0 / +2.8
5%38.2 / 30.141.9 / 32.5+3.7 / +2.4
10%32.0 / 22.336.1 / 24.0+4.1 / +1.7
20%19.0 / 8.223.5 / 9.0+4.5 / +0.8
AuthorsOpenReview ↗

Detailed Responses to Reviewer KUwT (3/3)

-Q3. Factors Affecting Rollback Performance

The two factors are the informativeness of the rollback sensitivity signal and the availability of relevant paths.

1) Rollback provides useful selection information beyond the preselection scores. Our RISE outperforms Dual without rollback (Tables 4 & 14 in the paper). Gains over Matched Path Replacement persist when path count, length, and structural/trajectory scores are controlled. Full rollback further outperforms query-parameter rollback (W2-Tab.2), supporting the additional value of intermediate-entity updates. Our noise experiments (Q2-Tab.3) further show that our RISE's MRR advantage over Dual widens overall as noise increases.

2) Relevant-path availability determines the evidence available for selection. The path-length statistics (Tables 19-20 in the paper) show that broader exploration introduces additional path lengths, while two-hop paths remain dominant under the default retention budgets. The training-fact deletion experiment (Figure 12 in the paper) shows greater degradation under heavier removal, consistent with reduced structural evidence. Broader preselection followed by compact retention (Figures 8 & 10 in the paper) helps exploit available paths while limiting redundancy.

-Q4. Inductive Extension

The main challenges in extending our RISE to inductive settings are representing unseen entities for candidate retrieval and constructing rollback signals without prior training trajectories for these entities.

We evaluated inductive settings with 10/20/30 held-out UMLS entities and 100/200/300 held-out FB15K-237 entities. The experimental setup was as follows: 1) Entity selection. We randomly selected entities that appeared in the original test set and had at least five original training facts connecting them to seen entities. 2) Training. We excluded all training and validation triples involving held-out entities from base training and model selection. Each model was trained on the remaining training graph. 3) Adaptation. We used five original training triples per held-out entity as support, excluding entity pairs appearing in either direction in the validation or test sets. All other removed training facts remained unused. We randomly initialized and optimized only the new-entity embeddings, keeping existing entity and relation embeddings frozen. We accumulated updates per support fact and scored each path by the length-normalized decrease in candidate log-probability after reversing its associated updates. 4) Evaluation. We evaluated all original-test triples involving held-out entities, retrieving candidates from the full entity vocabulary. Inference used only base-training and support triples; test triples were excluded from adaptation.

Tab.4 shows that RISE achieves the highest MRR across all tested inductive settings, with the highest H@1 on UMLS and competitive H@1 on FB15K-237. This advantage is consistent with RISE's reuse of query-relevant relational patterns: its query-conditioned subgraph encoder captures multi-hop evidence connecting unseen entities to existing graph neighborhoods through support facts, complementing limited embedding adaptation with learned structural knowledge. RISE maintains its MRR advantage as more entities are held out, supporting this adaptation strategy.

Tab.4 Model performance on inductive settings

Dataset#Unseen Entities#QueriesDrKGC (MRR / H@1)FtG (MRR / H@1)SRP-KGC (MRR / H@1)Ours (MRR / H@1)
UMLS1015247.3 / 34.930.7 / 24.353.1 / 48.764.3 / 57.9
2022742.1 / 30.428.4 / 21.649.8 / 45.457.4 / 51.1
3027734.1 / 24.222.9 / 16.643.6 / 38.645.8 / 39.0
FB15K-23710045431.3 / 22.528.9 / 21.837.6 / 34.838.3 / 33.9
20079926.1 / 18.124.2 / 15.830.7 / 27.833.6 / 27.0
300166520.4 / 13.922.1 / 14.725.3 / 22.628.4 / 23.8

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.