Graph Database Boosts Incident Agent Accuracy by 14%, But the Truth Is More Complicated

When a microservice failure alert fires, you only know something broke—not which service or which change caused it. One developer built an incident diagnosis agent on top of a graph database and hit 95.2% root-cause localization accuracy on a custom dataset, but on a real-world benchmark the graph advantage almost vanished. The lessons here are worth a close look for any team building AI agents.

What a graph database brings to an incident agent

Developer Mohit Sachin Shirke built SynapseGuard for the Graph Hacks competition—a diagnosis agent that starts from an alert and follows the service call chain to find the ignition point. The core idea is to put all the context the agent needs into a graph: the service call graph (real topology from the OpenTelemetry Demo), the host each service runs on, change logs (deployments, config changes, feature flags), people info (team ownership, on-call rotation, change authors), and the agent's own memory of past incidents.

When an incident occurs, the agent uses the graph structure to do five things: prune by reachability (only trace along synchronous CALLS edges to unhealthy services), score candidate services based on evidence (does a candidate's downstream explain the problem, did it degrade first, did a change just land), provide on-call personnel with an evidence chain (e.g., a path like p-alice → ON_CALL → team-checkout → OWNS → payment), compute blast radius and place circuit breakers using the max-flow algorithm, and finally wait for human approval before acting.

The clever part of this design is that every decision traces back to a path in the graph. For an on-call engineer woken at 3 a.m., that's far more useful than an AI saying "trust me."

The max-flow algorithm is a classic in graph theory, used to find the maximum feasible flow from a source to a sink in a capacity-constrained network. In the incident diagnosis scenario, the author uses it for circuit breaker placement: treating the service call graph as a network where edge capacity represents the strength of dependency or traffic-carrying capacity between services, computing max-flow identifies the critical bottleneck paths in the system. Placing circuit breakers at bottlenecks allows the propagation chain to be cut at minimal cost when a failure spreads, while minimizing impact on normal business. The advantage of this algorithm is that it makes decisions based on global graph structure rather than local metrics, embodying the unique value of graph models in systemic risk assessment.

Give the LLM graph tools, not graph access

SynapseGuard exposes capabilities through an MCP server, but it doesn't let the LLM freely write Cypher queries. Instead, there's a hand-written catalog of parameterized tools: blast_radius, who_to_page, path_between, recent_changes, and so on. Before any query executes, service names are resolved in the graph first—if you ask about a nonexistent payments-gateway, the agent runs no query at all, tells you that name isn't in the graph, and asks whether you meant payment.

Free-form Cypher is off by default, and no tool can approve actions. The author tested with an 8B local model running on CPU: it picked the right tool 12 out of 12 times, and the final sentence of output had to match the tool's returned result or it would be rejected. The approach is pragmatic: what LLMs are good at isn't writing queries but understanding intent and interpreting results—put the safety boundary in tool design, not in prompts.

MCP (Model Context Protocol) is an open protocol proposed by Anthropic, aimed at standardizing how LLMs interact with external tools and data sources. It lets developers wrap capabilities like database queries and API calls as tools exposed to the LLM through a unified interface, with the model selecting the appropriate tool based on user intent and passing in parameters. Unlike letting the model generate SQL or Cypher directly, the MCP tool pattern hardcodes query logic into reviewed, parameterized templates, with the model only responsible for intent understanding and parameter filling. This design naturally limits the security risks of excessive model freedom, while reducing the probability of the model generating erroneous or dangerous operations due to unfamiliarity with the query language—a pragmatic practice paradigm in current agent engineering.

Synthetic data looks great, real data slaps back

On 500 held-out synthetic incidents—with distractors, red-herring deployments, and missing telemetry—the graph agent ranked the true root cause first 95.2% of the time. The strongest tabular baseline, with relations stripped out but the same signals and tuning, reached 81.6%, while the author's own first naive version ("pick the deepest failing service") managed only 25%. The signal on synthetic data was clear: graph structure is worth 14 percentage points.

But the author then tested on RCAEval, a public real-world fault-injection benchmark covering Online Boutique, Sock Shop, and Train Ticket—645 cases total. For Train Ticket, he learned the call graph from 574,479 real Jaeger spans. The results were honestly surprising: under default settings the graph structure's ranking tied the strong baseline, trading wins and losses across systems, and lagged by 4 percentage points on held-out Train Ticket.

After tuning with weights learned from other real systems, the graph scorer won on 4 of 6 held-out system suites—but seeing those results, the author didn't change the product defaults. The reason isn't hard to understand: the graph's ranking advantage comes from joining telemetry with changes and host location, and RCAEval doesn't contain that join data—the graph has no structural information to exploit.

In the author's own words: "My synthetic benchmark was flattering me; real data showed me where the graph helps and where it doesn't." That line deserves to be taped to the wall of everyone doing agent evaluation. Real data also caught a bug that synthetic data would never expose: severity scores saturating at 1.0, making services indistinguishable.

RCAEval is a public benchmark for root cause analysis (RCA), specifically designed to evaluate automated fault diagnosis systems in real fault-injection scenarios. It covers three typical microservice demo systems—Online Boutique, Sock Shop, and Train Ticket—and includes a large number of real injected fault cases with corresponding telemetry data (such as Jaeger tracing spans). Unlike synthetic data, RCAEval's failure modes, service topology, and signal noise all come from real runtime environments, but precisely because of that, it doesn't include auxiliary dimensions like change logs or host location that can be joined with the call graph. The author chose this benchmark precisely to test the real boundaries of graph structure when join information is absent—a choice that itself reflects vigilance against "self-built benchmarks are easy to overfit."

Pitfalls encountered with FalkorDB

While pushing FalkorDB 6.0.2 to its limits, the author reproduced two issues: a query shape containing two MATCH … WHERE … IN $list clauses silently returns empty rows unless a WITH is inserted between the two clauses; and a query containing two OPTIONAL MATCHes, an aggregation, and ORDER BY crashes the server.

Two other lessons have universal value. WHERE n.id IN $list can use the index, while UNWIND … MATCH (n {id: x}) cannot—after switching, investigation speed at the scale of 1,000 services improved by about 3.6x. Result sets are capped by default at RESULTSET_SIZE (10,000 rows) with no warning, so any "return everything" query must be explicitly bounded.

FalkorDB is a Redis-based graph database that uses sparse matrices and linear algebra techniques to achieve high-performance graph queries, supporting the Cypher query language and the OpenCypher standard. It's commonly used in knowledge graphs, recommendation systems, and real-time relationship analysis, with advantages in low-latency queries thanks to its memory-first architecture. In the SynapseGuard project, FalkorDB stores multi-dimensional context including the service call graph, change records, and personnel relationships—a typical graph database use case of modeling heterogeneous entities and their relationships as nodes and edges to support multi-hop path queries and reachability analysis. The query optimizer bugs and result-set truncation issues the author found under stress testing also reflect the engineering reality that graph databases still require careful validation under complex query shapes.

An honest summary from a graph database practitioner

The author offers four lessons, each backed by real data rather than vague generalities.

Graph structure is only valuable when the answer depends on joins. When a query needs to combine call relationships with changes, deployment location, and time windows, the absence of relationships causes the same signals to be attributed to the wrong service. Strip out the relations and the same metrics point to a different service. This explains why the graph advantage was obvious on synthetic data but vanished on RCAEval: what the latter lacks is exactly the dimension where graph joins pay off.

Evaluate on someone else's data. Self-built benchmarks easily create illusions; only real data tells you where your advantage ends.

Give the agent graph tools, not graph write access. Read-only access should live at the database and tool-design layer, not be entrusted to prompts.

Make every answer show its path. That turns "trust me" into "check me"—exactly what an on-call engineer at 3 a.m. actually needs.

The code, benchmarks, and raw results are all in the GitHub repository. For teams building AI agents that need structured reasoning, the value of this project isn't the 95.2% number—it's that the author was willing to publish the less flattering results too: 81.6%, a tie, and a 4-point lag.