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
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
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 .
Figure 2. The proposed framework. The shaded blocks are our main contributions; tags specify the section where they are introduced.
π
[[π]]G⊆(N∪V)×(N∪V)
p
{(u,v)∣(u,p,v)∈G}
π−
{(u,v)∣(v,u)∈[[π]]G}
π⋅π′
{(u,v)∣∃w:(u,w)∈[[π]]G∧(w,v)∈[[π′]]G}
π∪π′
[[π]]G∪[[π′]]G
π∗
{(u,u)∣u∈N}∪[[π]]G∪[[π⋅π]]G∪…
π?
{(u,u)∣u∈N}∪[[π]]G
Table 1. Evaluation of path expressions.
φ
S,G,u⊨φ if:
⊤
trivially satisfied
s
S,G,u⊨def(s,S)
test(ωt,y)
u⊨ωt,y
closed(Q)
∀p∈(P∪K)∖Q: not S,G,u⊨≥1p.⊤
eq(π,q)
{v∣(u,v)∈[[π]]G}={v∣(u,v)∈[[q]]G}
disj(π,q)
{v∣(u,v)∈[[π]]G}∩{v∣(u,v)∈[[q]]G}=∅
Table 2. Semantics of a SHACL shape φ . < and ≤ are the standard orderings on comparable terms (e.g., numbers, strings, dates) and v∼w means v and w are literals with different language tags.
Figure 3. The offending subgraph of the violation in Fig. 1 with the offending focus submission phase2 .
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 (sel1,φ1) . In (c), some intermediate steps such as shape unfolding Reviewer →(≥1π.len≥3 ) are omitted.
φ
Graph Operations
=y
rep(w,p,u,u′) , where u′=u
¬=y
rep(w,p,u,y)
len≥y
rep(w,p,u,u′) , where len(u′)<y
¬len≥y
rep(w,p,u,u′) , where len(u′)≥y
Table 3. Graph operations for VIO(T,Q)(sel,φ) , given a node u⊨sel and the final hop (w,p,u) of a trace. u′ is generated by editing u (e.g., adding, removing, transposing characters, or combinations thereof) to violate φ .
Figure 5. Offending subgraphs of PaperA and PaperABC from applying E1 on the graph of the running example.
Figure 6. Focused subgraph context ( F ) of PaperABC violating (sel1,φ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 ∝ 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
φ
Graph Operations
Graph Operations
Given zero-length trace ⟨u⟩
Given final hop (w,p,u)
test(ωsh:hasValue,y)
ineligible
rep(w,p,u,u′) , where u′=u
¬test(ωsh:hasValue,y)
ineligible
rep(w,p,u,y)
test(ωsh:class,y)
−e(u,a,c) , for each subclass c of y
¬test(ωsh:class,y)
+e(u,a,c) , for some subclass c of y
test(ωsh:datatype,y)
ineligible
rep(w,p,u,z′) , where z′ is not of datatype y
Appendix
Table 5. Graph operations for VIO(T,Q)(sel,φ) , given a node u⊨sel and a zero-length trace ⟨u⟩ 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.
Figure 9. Example prompt for qualified satisfaction task.
Figure 10. Average token count and cost for different prompting strategies and LLMs.
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.
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 F1 than always disabling access in five of six suites.
Tung-Wei Lin, Gabe Fierro, Han Li +3
UC Berkeley, Berkeley, USA · Colorado School of Mines, Golden, USA · Lawrence Berkeley National Laboratory, Berkeley, USA
Scientific Reasoning Graph Extraction (SRGE) aims to recover explicit links among observations, evidence, intermediate claims, and paper-level conclusions. LLMs can produce graph-like scientific explanations, but their outputs often mix malformed syntax, drifting edge labels, incorrectly oriented roots, and weak source anchors. We propose PEARL (Peircean Extraction via Abstraction and Repair Layer), a training-free framework that turns noisy LLM graph responses into auditable reasoning graphs and repairs them toward strict semantic validity. PEARL first materializes explicit graph content under a closed Peircean schema, then uses matched evidence-grounded judge feedback to repair rejected edge types, local inference steps, and terminal roots while preserving an audit trail. On five 70-paper model archives from ARCHE, a benchmark for latent reasoning-chain extraction, PEARL raises strict gate passes from 0/350 for the LLM baseline to 300/350, with average REA improving from 0.339 to 0.906. The graphs provide a reliability layer for research-agent and AI scientist workflows that need inspectable reasoning traces rather than unconstrained graph regeneration. Code and audit artifacts are available at https://github.com/BohanSu/auditable-repair-reasoning-graphs/tree/300-350_workshop .
Bohan Su, Pengze Li, Yuchen Lu +1
School of Computer Science, Wuhan University · Artificial Intelligence Innovation and Incubation, Fudan University · Department of Computer Science, Faculty of Science, University of Bath +1
Repository-level repair requires not only correct patches but also inspectable records that explain how issue requirements are translated into code changes and post-edit evidence. We contribute THEMIS, a stage-aware repair workflow that externalizes this requirement-to-repair process through semantic interpretation, a runtime requirement-code graph, graph-derived Developer guidance, retained repair rationale and patches, and post-edit audit records. A retrospective audit of 300 SWE-bench Lite cases demonstrates that these artifacts provide broad support for cross-stage inspection: a complete Developer rationale is available for 288 cases, and 214 cases (71.3%) retain a complete audited field set connecting the selected stages. The retained records further enable systematic measurement of cross-stage correspondence: target symbols recur in 62.6% of Developer rationales and in 62.8% of patches, rising to 75.8% when related symbols are included. In a paired 100-case comparison, the relational workflow resolves 19 cases versus 9 for the direct same-input condition; because the two conditions also differ in Analyzer output, graph-derived distillation, and Judge records, we report this as preliminary, workflow-level evidence rather than a causal effect of the graph component. Together, these results show that THEMIS makes otherwise implicit requirement-to-repair transitions inspectable, enabling systematic examination of how repair decisions persist, align, and evolve across stages.