GRAIN: Bridging Name and Narrative Shifts in Real-World Graph Reasoning through Invariance-Rewarded Agentic RL

• URL: http://arxiv.org/abs/2608.27142v1
• Date: Thu, 27 Aug 2026 13:53:52 GMT
• Title: GRAIN: Bridging Name and Narrative Shifts in Real-World Graph Reasoning through Invariance-Rewarded Agentic RL
• Abstract summary: We propose GRAIN, a single-agent framework optimized via reinforcement learning.<n>GRAIN models reasoning as a semantic parsing and tool-execution pipeline.<n>It outperforms multi-agent baselines by 16.45% in accuracy with approximately 24% lower latency.
• Score: 34.35715901787783
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite their potential in standardized graph tasks, Large Language Models (LLMs) remain brittle to real-world shifts in node identifiers and task formulation. While deterministic graph tools are invariant to such shifts, extracting topological structures from noisy text is highly fragile for LLMs, which often overfit to surface patterns. Moreover, mitigating these parsing failures via multi-agent systems incurs prohibitive latency. To address this, we propose GRAIN, a single-agent framework optimized via reinforcement learning. GRAIN models reasoning as a semantic parsing and tool-execution pipeline, guided by a Structure Invariance Reward. By validating extracted intermediate graphs against ground-truth topologies, this reward forces the LLM to learn robust text-to-structure mappings rather than memorizing linguistic artifacts. We also introduce GRIT, a benchmark evaluating sensitivity to such linguistic shifts. GRAIN outperforms multi-agent baselines by 16.45\% in accuracy with approximately 24\% lower latency. Furthermore, it demonstrates superior structural generalization, halving the out-of-distribution (OOD) gap of SFT models (from 15.77\% to 7.80\%) and maintaining robustness on large-scale graphs beyond the training distribution.

Related papers

• Rethinking Message Passing as Retrieval for Text-Attributed Graph Learning [63.602658976990874]
  Graph neural networks (GNNs) are typically conceptualized as message-passing neural networks.<n>We present a retrieval-augmented view of GNNs: each layer makes predictions by applying anvariant to a node representation together with a permutation-in summary of retrieved graph context.<n>Motivated by this perspective, we propose RTA, a simple aggregation-based framework that replaces structural message passing with label-aware retrieval and propagation.
  arXiv  Detail & Related papers  (2026-08-27T07:25:44Z)
• Dynamic analysis enhances issue resolution [53.50448142467294]
  DAIRA (Dynamic Analysis-enhanced Issue Resolution Agent) is an automated repair framework that embeds dynamic analysis into the agent's reasoning cycle.<n> Driven by a Test Tracing-Driven methodology, DAIRA utilizes lightweight monitors to extract critical runtime data.<n>When powered by Gemini 3 Flash Preview, DAIRA establishes a new state-of-the-art (SOTA) performance, achieving a 79.4% resolution rate on the SWE-bench Verified dataset.
  arXiv  Detail & Related papers  (2026-03-23T14:48:54Z)
• HELP: HyperNode Expansion and Logical Path-Guided Evidence Localization for Accurate and Efficient GraphRAG [53.30561659838455]
  Large Language Models (LLMs) often struggle with inherent knowledge boundaries and hallucinations.<n>Retrieval-Augmented Generation (RAG) frequently overlooks structural interdependencies essential for multi-hop reasoning.<n>Help achieves competitive performance across multiple simple and multi-hop QA benchmarks and up to a 28.8$times$ speedup over leading Graph-based RAG baselines.
  arXiv  Detail & Related papers  (2026-02-24T14:05:29Z)
• RL-Struct: A Lightweight Reinforcement Learning Framework for Reliable Structured Output in LLMs [0.08594140167290097]
  Large Language Models (LLMs) have demonstrated remarkable capabilities in natural language generation and reasoning.<n>Their integration into automated software ecosystems is often hindered by the "Structure Gap"<n>We propose a lightweight, efficient Reinforcement Learning framework to bridge this gap.
  arXiv  Detail & Related papers  (2025-11-29T04:47:14Z)
• GRAVER: Generative Graph Vocabularies for Robust Graph Foundation Models Fine-tuning [92.19531718298744]
  Graph Foundation Models (GFMs) hold promise for broad applicability across diverse graph tasks and domains.<n>Existing GFMs struggle with unstable few-shot fine-tuning.<n>We propose GRAVER, a novel Generative gRAph VocabulariEs for Robust GFM fine-tuning framework.
  arXiv  Detail & Related papers  (2025-11-05T13:07:26Z)
• GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning [50.40400074353263]
  Graph Neural Networks (GNNs) are powerful tools for precessing relational data but often struggle to generalize to unseen graphs.<n>We introduce textbfGraph textbfIn-context textbfL textbfTransformer (GILT), a framework built on an LLM-free and tuning-free architecture.
  arXiv  Detail & Related papers  (2025-10-06T08:09:15Z)
• GRIL: Knowledge Graph Retrieval-Integrated Learning with Large Language Models [59.72897499248909]
  We propose a novel graph retriever trained end-to-end with Large Language Models (LLMs)<n>Within the extracted subgraph, structural knowledge and semantic features are encoded via soft tokens and the verbalized graph, respectively, which are infused into the LLM together.<n>Our approach consistently achieves state-of-the-art performance, validating the strength of joint graph-LLM optimization for complex reasoning tasks.
  arXiv  Detail & Related papers  (2025-09-20T02:38:00Z)
• Enhancing Spatial Reasoning in Vision-Language Models via Chain-of-Thought Prompting and Reinforcement Learning [0.42855555838080844]
  This study investigates the spatial reasoning capabilities of vision-language models (VLMs) through Chain-of-Thought prompting and reinforcement learning.<n>We find that simple CoT formats, where the model generates a reasoning step before the answer, can harm the model's original performance.<n>In contrast, structured multi-stage prompting based on scene graphs (SceneGraph CoT) significantly improves spatial reasoning accuracy.
  arXiv  Detail & Related papers  (2025-07-06T10:51:12Z)
• TrustGLM: Evaluating the Robustness of GraphLLMs Against Prompt, Text, and Structure Attacks [3.3238054848751535]
  We introduce TrustGLM, a comprehensive study evaluating the vulnerability of GraphLLMs to adversarial attacks across three dimensions: text, graph structure, and prompt manipulations.<n>Our findings reveal that GraphLLMs are highly susceptible to text attacks that merely replace a few semantically similar words in a node's textual attribute.<n>We also find that standard graph structure attack methods can significantly degrade model performance, while random shuffling of the candidate label set in prompt templates leads to substantial performance drops.
  arXiv  Detail & Related papers  (2025-06-13T14:48:01Z)
• LOBSTUR: A Local Bootstrap Framework for Tuning Unsupervised Representations in Graph Neural Networks [0.9208007322096533]
  Graph Neural Networks (GNNs) are increasingly used in conjunction with unsupervised learning techniques to learn powerful node representations.<n>We propose a novel framework designed to adapt bootstrapping techniques for unsupervised graph representation learning.
  arXiv  Detail & Related papers  (2025-05-20T19:59:35Z)
• Structural Alignment Improves Graph Test-Time Adaptation [17.564393890432193]
  We introduce Test-Time Structural Alignment (TSA), a novel algorithm for Graph Test-Time Adaptation (GTTA)<n>TSA aligns graph structures during inference without accessing the source data.<n>Experiments on synthetic and real-world datasets demonstrate TSA's consistent outperformance of both non-graph TTA methods and state-of-the-art GTTA baselines.
  arXiv  Detail & Related papers  (2025-02-25T16:26:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.