CogniGraph: Governed Graph-of-Agents Reasoning over Knowledge Graph Topologies with Semantic SHACL Validation and Constrained F1 Evaluation

Abstract

Abstract. Multi-agent large language model (LLM) systems are increasingly deployed for regulatoryand high-stakes reasoning, yet none of the prevailing flat-topology frameworks—AutoGen, CrewAI,LangGraph—enforce semantic governance over what each agent may say, in whose name, and withinwhich scope. The result is what we term ungoverned creativity at scale: plausible-sounding answers thatmix regulatorovisions, misattribute framework requirements, or drift beyond an agent’s intendedboundary. We ask: can a knowledge graph itself act as the coordination substrate of a multi-agentreasoning system, and can semantic validation gates supply the governance guarantees that the EU AIAct mandates?We present CogniGraph, a Graph-of-Agents framework in which each activated node of a domainknowledge graph hosts an autonomous LLM agent, communication follows the graph’s typed edgetopology via convergent message passing, and a SemanticSHACLGate enforces three-layer semanticvalidation—framework fidelity, scope boundary, and cross-reference integrity—on every agent output.A Prize-Collecting Steiner Tree (PCST) sub-graph activation step bounds per-query reasoning cost atO(|V∗|·R) independently of |V |; a zero-inference-cost MasterObserver provides complete provenancetraces; and the system is evaluated using a new joint quality–governance metric, Constrained F1.On MultiGov-30, a 30-question multi-regulation EU governance benchmark spanning the AI Act,GDPR, DORA, and NIS2, CogniGraph (Semantic-SHACL) achieves Constrained F1 of 0.756against 0.328 for an ungoverned single-agent Claude Sonnet 4.6 baseline (+130%), with governanceaccuracy of 99.4% (framework fidelity 100%, scope adherence 100%, cross-reference integrity 98.3%).The transition from format-based to semantic SHACL validation independently lifted token F1 by 18%(0.437 → 0.517) by eliminating 49% false-rejection of correct answers. CogniGraph is distributedas the open-source GraQle SDK (pip install graqle, CLI graq); the MultiGov-30 benchmark,the SemanticSHACLGate specification, and the full reference implementation are released underApache 2.0 to enable independent replication.1Version 3.3 (corrected). This version supersedes v3.2 (27 May 2026). A provenance audit traced every number in v3.2 to a dataset file, a run log and a results file. The MultiGov-30 headline comparison, per-tier, cost, latency and gate-layer figures are measured (one run, 11 March 2026) and are now printed exactly as recorded: Constrained F1 0.757 vs 0.328 (+131%), governance accuracy 0.997. The following items in v3.2 had no underlying computation or data and are withdrawn: Cohen's kappa 0.82 and the implied second annotation; all bootstrap confidence intervals, Wilcoxon p-values and Cohen's d; "mean over 3 seeds" and seed 42; per-query token counts; the contraction constant 0.45; the description of ablation rows A3/A6 as re-runs (no ablation has been run); and several smaller details. The Format-SHACL comparison is marked as not reproduced. Availability statements are corrected: the benchmark JSON and reproduction script named in v3.2 do not exist; the question set, knowledge-graph builder and harness are public in the GraQle SDK repository; the gate implementation used in the run is not public, so the governed result cannot currently be replicated by third parties. The paper now states plainly that the baseline's governance accuracy is zero by definition and that governance accuracy is self-scored by the system's own rule-based gate. The unsupported statistics were introduced during AI-assisted drafting and were not caught before posting; the author is responsible. No new results are introduced.