Research map / Multi-agent systems and games / Human-AI and goal-conditioned

Walk Wisely on Graph: Knowledge Graph Reasoning with Dual Agents via Efficient Guidance-Exploration

AAAI 2025 · Multi-agent systems and games › Human-AI and goal-conditioned · approach: Language-grounded reinforcement agents · 6 citations (OpenAlex)

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 FULORA, a dual-agent hierarchical RL model for multi-hop KG reasoning where a high-level agent on a clustered KG guides a low-level agent via a constrained guidance-exploration objective and dynamic path feedback.

Problem

Multi-hop KG reasoning agents learn poorly early on due to sparse rewards and struggle on sparse KGs where answers require long reasoning paths.

Approach

Extends the CURL dual-agent framework: GIANT walks a TransE-K-means cluster-level KG and DWARF walks the entity KG, with DWARF's reward constrained by state similarity to GIANT (solved via Lagrange multipliers) and GIANT given a shaped dynamic path feedback reward; DWARF also uses graph attention.

Key results

• On path length 3, FULORA reports MRR 72.5 on NELL-995 and 49.1 on WN18RR, the best multi-hop scores in Table 2, with FB15K-237 MRR 36.4 slightly below HMLS's 37.4.
• Averaged across the three datasets, FULORA improves MRR by 3.5% over CURL (as stated in the text).
• Fact prediction on seven NELL-995 tasks gives an average gain of 9.1% over multi-hop baselines and 16.1% over embedding baselines (as stated).

Measured effects reported in the paper

Limitations

• Gains on FB15K-237 link prediction are not consistent (HMLS is higher on MRR)
• Performance depends on cluster number and the sensitivity hyperparameters delta and alpha
• Relies on a TransE pre-embedding and K-means clustering, with a performance gap to LMKE-based variant

Experimental setup

Datasets: NELL-995 WN18RR FB15K-237

Benchmarks: NELL-995 WN18RR FB15K-237

Metrics: MRR Hits@1 Hits@3 Hits@10 MAP

Baselines: TransE DistMult ComplEx LMKE NBFNet RED-GNN MINERVA AttnPath SQUIRE CURL HMLS

Builds on: CURL MINERVA AttnPath TransE REINFORCE

Closest papers by meaning

• Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs (NeurIPS 2024 · similarity 0.87)
• $\texttt{G1}$: Teaching LLMs to Reason on Graphs with Reinforcement Learning (NeurIPS 2025 · similarity 0.86)
• Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning (ICLR 2024 · similarity 0.86)
• Plan Then Action: High-Level Planning Guidance Reinforcement Learning for LLM Reasoning (ICML 2026 · similarity 0.86)
• Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models (ICML 2025 · similarity 0.86)
• Search-R2: Enhancing Search-Integrated Reasoning via Actor-Refiner Collaboration (ICML 2026 · similarity 0.85)