VeriGraph: Towards Verifiable Data-Analytic Agents

• URL: http://arxiv.org/abs/2606.16603v1
• Date: Mon, 15 Jun 2026 11:50:56 GMT
• Title: VeriGraph: Towards Verifiable Data-Analytic Agents
• Abstract summary: LLM-based agents have demonstrated strong capabilities in data-intensive analytical tasks, yet their outputs are rarely verifiable.<n>We propose VeriGraph, a traceable neuro-symbolic reasoning framework that enables agents to construct an explicit heterogeneous evidence directed acyclic graph.<n>Our results suggest that explicit evidence-graph construction is a promising path toward verifiable data-analytic agents.
• Score: 71.17693022916896
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: LLM-based agents have demonstrated strong capabilities in data-intensive analytical tasks, yet their outputs are rarely verifiable: a reliance on linear text trajectories makes their reasoning difficult to audit. In particular, deterministic computations over raw data and semantic deductions over natural-language claims are often entangled in an unstructured stream, leaving numerical conclusions hard to reproduce and qualitative judgments hard to inspect. To address this, we propose VeriGraph, a traceable neuro-symbolic reasoning framework that enables agents to construct an explicit heterogeneous evidence directed acyclic graph (DAG) during execution. VeriGraph introduces three evidence-expansion primitives, namely computational, grounding, and derivational expansion, to connect raw data, interpreter variables, computed results, and natural-language claims in a unified graph. Under this formulation, structural traceability is reduced to graph reachability from raw data sources to terminal claims, while semantic support is measured by claim-level evidence evaluation. To improve graph construction, we further design a graph-based policy optimization strategy with a composite reward that jointly supervises answer correctness, computational integrity, and derivational coherence. Experiments on four benchmarks show that VeriGraph-8B achieves the highest overall score among all baselines. More importantly, VeriGraph produces auditable evidence graphs with substantially stronger claim grounding, achieving a 87.61\% Grounding Rate under our claim-level evidence support evaluation. These results suggest that explicit evidence-graph construction is a promising path toward verifiable data-analytic agents. Our code is available at https://github.com/ignorejjj/VeriGraph.

Related papers

• Statistical Testing on Directed Graphs by Surrogate Data Generation [44.65601297340714]
  We first revisit the notion of stationary graph signals on directed graphs. Specifically, and through the eigendecomposition of the graph shift operator, we define directed graph wide-sense stationary signals.<n>We propose a new framework to generate surrogate graph signals that preserve covariance structure under stationarity assumptions.<n>We provide guiding examples and an application on real data, in which we compare the performance of our framework with existing techniques for undirected graphs or based on naive permutation, demonstrating feasibility and superiority of the proposed approach.
  arXiv  Detail & Related papers  (2026-05-30T14:50:15Z)
• GraphReAct: Reasoning and Acting for Multi-step Graph Inference [49.26607058250454]
  GraphReAct is a graph reasoning-acting framework that enables step-by-step inference over graph-structured data.<n>By interleaving reasoning with both retrieval and refinement actions, our framework enables a progressive transition from context expansion to compression.
  arXiv  Detail & Related papers  (2026-05-08T07:09:42Z)
• Implicit Causal Graph Construction in Text via Chain Discovery [27.889485407012547]
  We study implicit causal graph construction from text by treating each described cause-effect pair as the begin- and endpoint of an underlying latent causal graph.<n>We compare end-to-end graph construction with methods that frame the task as causal chain discovery.<n>We analyze trade-offs among these approaches and evaluate the validity of inferred causal relations using a manually curated database of 1,560 scientifically validated causal pairs.
  arXiv  Detail & Related papers  (2026-04-20T07:29:58Z)
• Enrich-on-Graph: Query-Graph Alignment for Complex Reasoning with LLM Enriching [61.824094419641575]
  Large Language Models (LLMs) struggle with hallucinations and factual errors in knowledge-intensive scenarios like knowledge graph question answering (KGQA)<n>We attribute this to the semantic gap between structured knowledge graphs (KGs) and unstructured queries, caused by inherent differences in their focuses and structures.<n>Existing methods usually employ resource-intensive, non-scalable reasoning on vanilla KGs, but overlook this gap.<n>We propose a flexible framework, Enrich-on-Graph (EoG), which leverages LLMs' prior knowledge to enrich KGs, bridge the semantic gap between graphs and queries.
  arXiv  Detail & Related papers  (2025-09-25T06:48:52Z)
• Beyond Message Passing: Neural Graph Pattern Machine [50.78679002846741]
  We introduce the Neural Graph Pattern Machine (GPM), a novel framework that bypasses message passing by learning directly from graph substructures.<n>GPM efficiently extracts, encodes, and prioritizes task-relevant graph patterns, offering greater expressivity and improved ability to capture long-range dependencies.
  arXiv  Detail & Related papers  (2025-01-30T20:37:47Z)
• Motif-Consistent Counterfactuals with Adversarial Refinement for Graph-Level Anomaly Detection [30.618065157205507]
  We propose a novel approach, Motif-consistent Counterfactuals with Adversarial Refinement (MotifCAR) for graph-level anomaly detection. The model combines the motif of one graph, the core subgraph containing the identification (category) information, and the contextual subgraph of another graph to produce a raw counterfactual graph. MotifCAR can generate high-quality counterfactual graphs.
  arXiv  Detail & Related papers  (2024-07-18T08:04:57Z)
• Graph Agent: Explicit Reasoning Agent for Graphs [3.422149942031643]
  We introduce the Graph Agent (GA), an intelligent agent methodology of leveraging large language models (LLMs), inductive-deductive reasoning modules, and long-term memory for graph reasoning tasks. GA integrates aspects of symbolic reasoning and existing graph embedding methods to provide an innovative approach for complex graph reasoning tasks. Results showed that GA reached state-of-the-art performance, demonstrating accuracy of 90.65%, 95.48%, and 89.32% on Cora, PubMed, and PrimeKG datasets, respectively.
  arXiv  Detail & Related papers  (2023-10-25T07:20:16Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it.
  arXiv  Detail & Related papers  (2023-05-31T11:04:53Z)
• FactGraph: Evaluating Factuality in Summarization with Semantic Graph Representations [114.94628499698096]
  We propose FactGraph, a method that decomposes the document and the summary into structured meaning representations (MRs) MRs describe core semantic concepts and their relations, aggregating the main content in both document and summary in a canonical form, and reducing data sparsity. Experiments on different benchmarks for evaluating factuality show that FactGraph outperforms previous approaches by up to 15%.
  arXiv  Detail & Related papers  (2022-04-13T16:45:33Z)

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.