A Formal Diagnostic Framework for Graph Repair Systems

Tung-Wei Lin; Gabe Fierro; Han Li; Tianzhen Hong; Pierluigi Nuzzo; Alberto Sangiovanni-Vinentelli

cs.DBJul 30, 2025

A Formal Diagnostic Framework for Graph Repair Systems

Authors: Tung-Wei Lin, Gabe Fierro, Han Li, Tianzhen Hong, Pierluigi Nuzzo, Alberto Sangiovanni-Vinentelli

Organizations: UC Berkeley, USA · Lawrence Berkeley National Laboratory, USA · National Renewable Energy Laboratory, USA · Colorado School of Mines, USA

Abstract

Graph-based data representations excel at capturing relations among entities, e.g., for semantic web, artificial intelligence, or database applications, and their utility depends critically on their quality, usually enforced via graph schemas. These schemas are often violated, e.g., during data ingestion, calling for repair actions to achieve compliance. This paper presents a formal diagnostic framework for graph repair methods. Current methods often lack rigor and generality, since they rely on ad hoc test datasets. Our method starts, instead, from a compliant graph and uses an abstract rewriting system to systematically introduce schema violations while ensuring provable coverage of the constraints in the schema. We apply the framework to several repair methods, including those based on large language models, and assess their performance across multiple metrics. Results show that our framework effectively differentiates the performance of different methods across various constraints, highlighting the importance of fine-grained, systematic tools for graph repair.

Figures & tables

Panel of Figure 1 — Figure 1. Example of a schema violation. The schema requires that a paper submission phase end before reviewing phase start. submission phase2 violates this constraint. The schema syntax is explained in Sec. 4 .

Panel of Figure 2 — Figure 2. The proposed framework. The shaded blocks are our main contributions; tags specify the section where they are introduced.

$\pi$	$\llbracket\pi\rrbracket^{\mathcal{G}}\subseteq(\mathcal{N}\cup\mathcal{V})\times(\mathcal{N}\cup\mathcal{V})$
$p$	$\{(u,v)\mid(u,p,v)\in\mathcal{G}\}$
$\pi^{-}$	$\{(u,v)\mid(v,u)\in\llbracket\pi\rrbracket^{\mathcal{G}}\}$
$\pi\cdot\pi^{\prime}$	$\{(u,v)\mid\exists w:(u,w)\in\llbracket\pi\rrbracket^{\mathcal{G}}\wedge(w,v)\in\llbracket\pi^{\prime}\rrbracket^{\mathcal{G}}\}$
$\pi\cup\pi^{\prime}$	$\llbracket\pi\rrbracket^{\mathcal{G}}\cup\llbracket\pi^{\prime}\rrbracket^{\mathcal{G}}$
$\pi^{*}$	$\{(u,u)\mid u\in\mathcal{N}\}\cup\llbracket\pi\rrbracket^{\mathcal{G}}\cup\llbracket\pi\cdot\pi\rrbracket^{\mathcal{G}}\cup\ldots$
$\pi?$	$\{(u,u)\mid u\in\mathcal{N}\}\cup\llbracket\pi\rrbracket^{\mathcal{G}}$

Table 1. Evaluation of path expressions.

$\varphi$	$\mathcal{S,G},u\models\varphi$ if:
$\top$	trivially satisfied
$s$	$\mathcal{S,G},u\models def(s,\mathcal{S})$
$\mathrm{test}(\omega_{t,y})$	$u\models\omega_{t,y}$
$\mathrm{closed}(Q)$	$\forall p\in(\mathcal{P}\cup\mathcal{K})\setminus Q:\text{ not }\mathcal{S,G},u\models\geq_{1}p.\top$
$\mathrm{eq}(\pi,q)$	$\{v\mid(u,v)\in\llbracket\pi\rrbracket^{\mathcal{G}}\}=\{v\mid(u,v)\in\llbracket q\rrbracket^{\mathcal{G}}\}$
$\mathrm{disj}(\pi,q)$	$\{v\mid(u,v)\in\llbracket\pi\rrbracket^{\mathcal{G}}\}\cap\{v\mid(u,v)\in\llbracket q\rrbracket^{\mathcal{G}}\}=\emptyset$

Table 2. Semantics of a SHACL shape

\varphi

<

and

\leq

are the standard orderings on comparable terms (e.g., numbers, strings, dates) and

v\not\sim w

means

v

and

w

are literals with different language tags.

Panel of Figure 3 — Figure 3. The offending subgraph of the violation in Fig. 1 with the offending focus submission phase2 .

Panel of Figure 4 — Figure 4. Running example. (a) A graph and schema modeling academic publications. (b) The trace sets used in (c). (c) Expansion graph and DFS from $(sel_{1},\varphi_{1})$ . In (c), some intermediate steps such as shape unfolding Reviewer $\to($ $\geq_{1}\pi.\text{len}\geq 3$ ) are omitted.

$\varphi$	Graph Operations
$=y$	$rep(w,p,u,u^{\prime})$ , where $u^{\prime}\neq u$
$\neg=y$	$rep(w,p,u,y)$
$\text{len}\geq y$	$rep(w,p,u,u^{\prime})$ , where $len(u^{\prime})<y$
$\neg\text{len}\geq y$	$rep(w,p,u,u^{\prime})$ , where $len(u^{\prime})\geq y$

Table 3. Graph operations for

\texttt{VIO}^{(T,Q)}(sel,\varphi)

, given a node

u\models sel

and the final hop

(w,p,u)

of a trace.

u^{\prime}

is generated by editing

u

(e.g., adding, removing, transposing characters, or combinations thereof) to violate

\varphi

Panel of Figure 5 — Figure 5. Offending subgraphs of PaperA and PaperABC from applying E1 on the graph of the running example.

Panel of Figure 6 — Figure 6. Focused subgraph context ( $F$ ) of PaperABC violating $(sel_{1},\varphi_{1})$ after E1 is applied in the running example.

Figure 7. Estimated effects of context selection and LLM selection.

Scope	Method	Syn. Val.	Sem. Val.	Iso.	Iso. Hit	Iso. Prec.
Brick	ASP ( Ahmetaj et al., 2022 )	100.0	97.22	32.64	66.67	29.32
	Neural ( Pellissier Tanon and Suchanek, 2021 )	100.0	0	0	–	–
	Subset Avg	99.44	90.49	62.67	–	–
	Llama+ $SF^{+}$	99.31	91.67	68.06	–	–
All	Neural ( Pellissier Tanon and Suchanek, 2021 )	100.0	10.37	8.36	–	–
	Subset Avg	96.96	87.95	52.41	–	–

Table 4. Average scores (

\%

) of the repair systems. “Brick” averages over the Brick dataset; “All” averages over all datasets. Higher scores are better for all metrics: syntactic validity (Syn. Val.), semantic validity (Sem. Val.), isomorphism (Iso.), isomorphic hit (Iso. Hit), and precision (Iso. Prec.).

Figure 8. Per - constraint performance shift from semantic validity to isomorphism, comparing LLM and ASP on the Brick dataset. Point size

\propto

sample count. sh:nodeKind requires a node be of a given node kind, such as a blank node.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

$\varphi$	Graph Operations	Graph Operations
	Given zero-length trace $\langle u\rangle$	Given final hop $(w,p,u)$
$\text{test}(\omega_{\texttt{sh:hasValue},y})$	ineligible	$rep(w,p,u,u^{\prime})$ , where $u^{\prime}\neq u$
$\neg\text{test}(\omega_{\texttt{sh:hasValue},y})$	ineligible	$rep(w,p,u,y)$
$\text{test}(\omega_{\texttt{sh:class},y})$	$-e(u,\texttt{a},c)$ , for each subclass $c$ of $y$
$\neg\text{test}(\omega_{\texttt{sh:class},y})$	$+e(u,\texttt{a},c)$ , for some subclass $c$ of $y$
$\text{test}(\omega_{\texttt{sh:datatype},y})$	ineligible	$rep(w,p,u,z^{\prime})$ , where $z^{\prime}$ is not of datatype $y$

Appendix

Table 5. Graph operations for

\texttt{VIO}^{(T,Q)}(sel,\varphi)

, given a node

u\models sel

and a zero-length trace

\langle u\rangle

or the final hop

(w,p,u)

of a non-zero-length trace in

T

. “Ineligible” indicates that, by the coverage rules in Sec. 5.4.4 , zero-length traces with intrinsic shapes are discarded.

Panel of Figure 9 — Figure 9. Example prompt for qualified satisfaction task.

Figure 10. Average token count and cost for different prompting strategies and LLMs.

Panel of Figure 11 — Figure 11. Prompt template for our LLM-based repair systems

Model	Input Cost	Output Cost
GPT4o	$\$ 2.5$	$\$ 10$
Claude 3.0 Opus	$\$ 15$	$\$ 75$
Gemini 1.5 Pro	$\$ 1.25$	$\$ 5$
Llama 3.1 405B	$\$ 2.4$	$\$ 2.4$

Appendix

Table 6. Pricing Model. Costs are in USD per 1 million tokens.

Figure 12. Performance of each evaluation metric for every combination of LLM, strategy, and dataset.

Method	Syn. Val.	Sem. Val.	Iso.	Iso. Hit	Iso. Prec.
ASP ( Ahmetaj et al., 2022 )	100.0	40.23	13.51	27.59	12.13
Neural ( Pellissier Tanon and Suchanek, 2021 )	100.0	10.37	8.36	-	-
Subset Avg	96.96	87.95	52.41	-	-
Llama $+SF^{+}$	96.84	91.38	58.62	-	-

Appendix

Table 7. Average scores (

\%

) of all repair systems on all datasets.

Selective Retrieval Routing for Multi-Violation Knowledge Graph Repair
Nov 5, 2026Tung-Wei Lin, Gabe Fierro, Han Li +3Knowledge Graphs Retrieval-Augmented Reasoning
UC Berkeley, Berkeley, USA · Colorado School of Mines, Golden, USA · Lawrence Berkeley National Laboratory, Berkeley, USA
PEARL: Auditable Repair for Scientific Reasoning Graph Extraction
Jul 20, 2026Bohan Su, Pengze Li, Yuchen Lu +1LLM Reasoning with Graphs LLM Auditing
School of Computer Science, Wuhan University · Artificial Intelligence Innovation and Incubation, Fudan University · Department of Computer Science, Faculty of Science, University of Bath +1
Externalizing Requirement-to-Repair Artifacts as Observable Traces for LLM-Based Program Repair
Sep 14, 2026Zewen Tao, Shin-nosuke IshikawaAutomated Program Repair Reasoning Trace Analysis
Rikkyo University

Nov 5, 2026J/K move · Enter open · S save

Selective Retrieval Routing for Multi-Violation Knowledge Graph Repair

Tung-Wei Lin, Gabe Fierro, Han Li, Tianzhen Hong+2

UC Berkeley, Berkeley, USA · Colorado School of Mines, Golden, USA · Lawrence Berkeley National Laboratory, Berkeley, USA

Knowledge Graphs Retrieval-Augmented Reasoning LLM Reasoning with Graphs

Open paper AskPDF arXiv

Knowledge graphs often contain missing or inconsistent facts that undermine the applications built on them. Schema validation detects such violations but does not identify which of several valid repairs recovers the intended graph. External corpora can supply the evidence needed to identify the intended repair, but retrieving from them is costly and not always successful. We propose a framework for selective retrieval in iterative graph repair. An LLM repair agent explores and edits the graph, while a router controls its access to a researcher agent that retrieves external evidence. We extend a violation-injection framework to generate cases with multiple compatible violations and known reference repairs. The agent's repair outcomes on these cases provide supervision for training the deployment-specific router. On two building-automation datasets, researcher access improves repairs for some violations and degrades them for others, with effects differing across deployments. The router uses fewer repair-time tokens than always enabling access in all six evaluation suites. It achieves higher repair

F_1

than always disabling access in five of six suites.

Abstract

Explore similar work

Selective Retrieval Routing for Multi-Violation Knowledge Graph Repair

PEARL: Auditable Repair for Scientific Reasoning Graph Extraction

Externalizing Requirement-to-Repair Artifacts as Observable Traces for LLM-Based Program Repair