Uncovering Systematic Blind Spots in Graph Database Testing through Integration and Process-Level Analysis

arXiv:2611.07754v1 [cs.SE] 5 Nov 2026

Uncovering Systematic Blind Spots in Graph Database Testing through Integration and Process-Level Analysis TINGHAN LI, The Chinese University of Hong Kong, Shenzhen, China AOYANG FANG, The Chinese University of Hong Kong, Shenzhen, China LONGBIN LAI, Alibaba Group, China ZIFAN XIE, Chongqing University, China HONGBO ZHAO, Beijing University of Posts and Telecommunications, China YU SHAO, Alibaba Group, China YING ZHANG, Zhejiang Gongshang University, China PINJIA HE, The Chinese University of Hong Kong, Shenzhen, China Graph databases are becoming foundational infrastructure for connected data, and a growing body of automated testing techniques has uncovered many bugs across mature graph database systems. Each technique checks a different aspect of correctness and exposes a different class of defect. Combining them is the natural next step, but each technique is judged by the real bugs it finds, not by useless reports or tests that can never fail, and that is what decides whether a developer can afford to fix the problems. To identify the remaining gaps, we integrated test capabilities from 8 testing methods and conducted an empirical study of their behavior, during which we found two blind spots. First, 12 hours of testing produce thousands of bug reports, far more than the number of genuine defects a mature database is likely to contain. Most reports are false positives caused by dialect or pattern-matching differences, and many of the remaining reports are duplicates. Second, analysis of process-level data reveals that many equivalence-based metamorphic test cases lose their ability to detect defects because of the optimization mechanism. Based on these findings, we summarize and realize these guidelines in GraphWeave, an integrated testing platform for graph databases. This includes a multi-agent system that analyzes the flood of bug reports to produce gating rules for issue filtering and adapter rules for dialect adaptation, and a plan-aware triage routes metamorphic pairs by plan, skipping those that share a plan on the same graph state and therefore cannot detect defects. We apply GraphWeave to NeuG, a recently open-sourced industrial graph database that has not been covered by prior graph database testing work. With modest manual effort, GraphWeave uncovers 19 previously unknown bugs, all of which have since been confirmed. CCS Concepts: • Software and its engineering → Software testing and debugging; • Information systems → Database management system engines. Additional Key Words and Phrases: graph databases, database testing

Author preprint. Submitted to ACM Transactions on Software Engineering and Methodology; not yet peer reviewed or accepted. 1

Introduction

Graph databases are widely used for managing highly connected data, including social networks, recommendation systems, fraud detection, and knowledge graphs [2, 14, 32]. Reflecting this demand, new systems continue to appear: as of this writing, the CMU Database of Databases [27] lists 26 Authors’ Contact Information: Tinghan Li, 225045006@link.cuhk.edu.cn, School of Data Science, The Chinese University of Hong Kong, Shenzhen, Shenzhen, China; Aoyang Fang, aoyangfang@link.cuhk.edu.cn, The Chinese University of Hong Kong, Shenzhen, Shenzhen, China; Longbin Lai, longbin.lai@gmail.com, Alibaba Group, Hangzhou, China; Zifan Xie, xzff@cqu.edu.cn, Chongqing University, Chongqing, China; Hongbo Zhao, hongbozhao72@gmail.com, Beijing University of Posts and Telecommunications, Beijing, China; Yu Shao, yu.shao@alibaba-inc.com, Alibaba Group, Hangzhou, China; Ying Zhang, yingz.au@gmail.com, Computer Science and Engineering, Zhejiang Gongshang University, Hangzhou, China; Pinjia He, hepinjia@cuhk.edu.cn, School of Data Science, The Chinese University of Hong Kong, Shenzhen, Shenzhen, China.

2

Tinghan Li et al.

graph database systems first released since 2021. Each of these new systems must be tested for correctness before it can be relied upon. Driven by this demand, researchers have developed a range of automated testing techniques for graph databases. These techniques rely on different test oracles, which are mechanisms for determining whether a test has passed or failed. The kinds of correctness they check can differ substantially: some compare the results that independent systems return for the same query [15], while others check, within a single system, whether write operations leave the graph in the expected state [19]. Different methods therefore expose different classes of defects [19, 21]. Combining them is the natural next step, yet no prior work has run these methods together, and their combined behavior remains unknown. Each technique is judged by the real bugs it finds, not by useless reports or tests that can never fail, and that is what decides whether a developer can afford to fix the problems. To identify the remaining gaps, we integrate eight methods [15, 17–19, 21, 22, 40, 45] behind a shared interface, record process-level data for each test, and study what these methods report and why. The study reveals two blind spots of existing testing methods; Figure 1 previews the three mechanisms behind them. Blind spot 1: Most raw reports are false positives or duplicates. A twelve-hour run of the integrated methods on Neo4j, Memgraph [23], and FalkorDB, three mature graph databases, produced more than four thousand raw reports, a volume far exceeding the number of genuine defects these mature systems are likely to contain. After inspecting these reports with experts, we found that most reports are false positives. Although false positives have several sources, two classes are especially important for integrated testing. The first is dialect incompatibility, which arises when graph database systems use different syntax to express the same query semantic. As Figure 1(a) shows, test cases originally designed for one system are therefore rejected by another and recorded as raw reports. Prior methods adapt to a target system’s dialect through substantial manual effort. The second arises from differences in the semantic constraints of pattern matching [1], the core operation of graph queries. Systems may make different but permissible choices for unspecified semantics, such as whether an edge may be bound by multiple variables within one match. An oracle built around one choice then produces false positives on a system that makes another. Figure 1(b) shows one such case. On a graph with one node and one self-loop, the same pattern returns one row on FalkorDB [8] but zero on Neo4j [24], because FalkorDB permits this reuse of an edge while Neo4j does not. Such a false positive can be hard to distinguish from a genuine defect without graph-database domain knowledge. After false positives are filtered, the remaining reports still number in the hundreds. Many are redundant because multiple test cases trigger the same underlying bug. In one campaign, 278 reports remained after 249 false positives were removed, but all 278 pointed to the same bug. Separating the few real defects from this noise still demands substantial manual effort. Blind spot 2: Many metamorphic tests cannot detect defects. Methods based on equivalence metamorphic relations generate a semantics-preserving variant of each query and check whether both return the same result. Query optimization mechanism, however, is designed to erase exactly such surface differences and often compiles both queries to the same plan, as shown in Figure 1(c). When both queries are executed against the same graph state and compile to the same plan, their results are identical by construction, so such a test cannot reveal a defect and only consumes testing resources. Worse, if that shared plan contains a bug, both queries return the same incorrect result, and the oracle remains silent. The problems these blind spots cause recur across testing methods and point to concrete guidelines for integrated testing. We realize these guidelines through the following designs.

Uncovering Systematic Blind Spots in Graph Database Testing through Integration and Process-Level Analysis

(a) Dialect differences

(b) Semantic differences

3

(c) Plan collapse

Fig. 1. Three fundamental challenges for graph database testing with existing methods: (a) dialect differences, (b) semantic differences, and (c) plan collapse.

Postprocessing pipeline for noise reduction. The study shows that in semantic regions where systems may validly differ, cross-system disagreement alone is weak bug evidence, while intrasystem contradiction across equivalent forms provides stronger evidence of a real defect. This finding guides us to preserve and analyze process-level data, so that self-contradiction can be detected and false positives attributed to their underlying semantic assumptions. We realize this with a postprocessing pipeline. In this pipeline, reports are clustered by root cause, and representative cases are analyzed by a multi-agent LLM system with skills that encode findings from the study. Each confirmed disposition triggers a corresponding feedback action. The pipeline updates the target adapter for dialect false positives and registers gate rules for confirmed bugs and duplicates to suppress repeated analysis. Plan-aware triage for skipping powerless pairs. The study shows that 5% to 34% of comparable equivalence-based metamorphic pairs compile to the same execution plan on the same graph state, at which point their results are identical by construction and the oracle has no power. This finding guides us to identify same-plan pairs before result execution. We realize this with a triage scheme that collects and compares plan hashes. Same-plan pairs are skipped before result execution. Pairs with different plans but identical results may indicate missed optimization opportunities or performance issues. Pairs with different plans and different results provide potential evidence of a logic bug and are passed to the postprocessing pipeline. GraphWeave combines the initial integration framework with these two designs. The resulting end-to-end platform supports test construction, dialect adaptation, report postprocessing, and process-level analysis. Together, these components make testing new graph databases practical with modest computational and human resources. We apply GraphWeave to NeuG [12], a recently open-sourced industrial graph database not covered by prior graph database testing work, and uncover 19 previously unknown bugs, all since confirmed. We make the following contributions. • An empirical study of integrated graph database testing. We integrate eight methods behind one interface and conduct an empirical study of their behavior, uncovering two blind spots of existing testing methods. • Guidelines for integrated graph database testing. We summarize these findings as guidelines for separating false positives from real bugs and triaging powerless metamorphic pairs.

4

Tinghan Li et al.

• Realizing the guidelines in GraphWeave. We build GraphWeave to realize these guidelines and apply it to NeuG, uncovering 19 previously unknown bugs, all since confirmed. The distribution of these bugs shows the value of integration, as no single method finds more than half. 2

Background

2.1 Testing Methods for Graph Databases The core difficulty of testing is checking the result for an arbitrary query on an arbitrary database state. Prior work resolves this challenge by proposing test oracles, each of which is a consistency relation the result of the query should satisfy. Existing approaches have proposed oracles to find hundreds of defects in real-world graph databases, and we classify their test capabilities into three categories [15, 17–19, 21, 22, 40, 45]. Differential Testing. Differential testing builds on an assumption: if the same queries are executed against multiple graph database systems on the same database state, the results should be the same [15]. Therefore, the method checks correctness by comparing results across systems without knowing the correct answer. However, differential testing has two limitations. First, false negatives arise when multiple systems share the same defect, since the oracle cannot detect a shared failure. Second, false positives arise even on features that all systems support. The language standard leaves parts of the semantics under-specified, so different systems may resolve them in different yet legitimate ways. The oracle then flags this divergence as a defect although no system is actually wrong. Statement Metamorphic Testing. Motivated by the limitations of differential testing, researchers have designed many metamorphic testing methods. Statement metamorphic testing transforms the query and checks that the result of the transformed query satisfies an expected metamorphic relation with that of the original [6]. A common case is equivalence transformation, which rewrites a query into a semantically equivalent one, such as reordering clauses or introducing redundant conditions, and checks that the two results are identical [22]. Other methods instead adopt transformations that are not equivalence-preserving. For instance, TLP partitioning [30] splits a query into the where true, where false, and where null branches, whose results differ from the original but together reconstruct it through their union. Some statement transformations are graph-native, deriving related queries from structures such as nodes, edges, and paths. Gamera [45] includes such query-derived capabilities through graph-aware metamorphic relations. Graph-Derived Testing. Graph-derived testing constructs oracles by operating on the test graph itself rather than on the query [21, 45]. The underlying observation is that controlled transformations of the graph induce predictable changes in query results; a violation of the predicted relationship signals a defect. GSlicer [21] instantiates this idea for graph databases: it decomposes the test graph into exhaustive, non-overlapping subgraphs and checks that querying each partition and aggregating the results reconstructs the result of querying the full graph. Gamera [45] also includes graph-derived capabilities alongside its query-derived ones. 2.2

Graph Database Semantic Constraints

Graph pattern matching maps a structural template onto a property graph, governed by semantic constraints that decide which mappings are valid and how many result rows each produces. Theory grounds these rules in the choice between isomorphism-based and homomorphism-based semantics [1]; the Cypher specification adopts the no-repeated-edge variant, where edge variables map one-to-one but node variables may repeat [11]. Its formal semantics covers only the core read-only

Uncovering Systematic Blind Spots in Graph Database Testing through Integration and Process-Level Analysis

5

fragment, leaving these rules underspecified [10], and GQL [7, 16] designates path semantics as user-selectable options. We make this design space precise with three constraints on a match within a uniqueness scope 𝑈 . The match exposes a visible relationship sequence 𝜌 = ⟨𝑒 1, . . . , 𝑒𝑘 ⟩ of relationship ids, which may arise from several traversal witnesses 𝜔 with visible projection vis(𝜔), such as the two directions of an undirected edge. Its multiplicity under bag semantics counts these witnesses, 𝑚(𝜌) = { 𝜔 | vis(𝜔) = 𝜌 } . A system’s profile then fixes three choices: legality, whether a sequence with 𝑒𝑖 = 𝑒 𝑗 for some 𝑖 ≠ 𝑗 is admissible within 𝑈 ; multiplicity, the value 𝑚(𝜌); and the reset boundary, the syntactic point at which 𝑈 restarts, which is meaningful only when legality forbids reuse. For oracles that rely on result consistency, a profile mismatched to the target system yields systematic false positives rather than real defects. 2.3

Query Optimization in Graph Databases

The query optimizer is a core component of graph database systems: before execution, it compiles the user-submitted query into a physical execution plan of minimal estimated cost [5, 33]. The literature categorizes graph query optimization into two complementary classes [20]. Rule-based rewriting applies heuristic, semantics-preserving transformations that restructure a query into a more compact equivalent form, such as pushing selections and projections toward the scan, trimming unused fields, fusing adjacent pattern segments, and eliminating redundant or implied pattern constraints [20, 28]. Cost-based optimization then searches the space of physical plans induced by these rewrites and selects the cheapest under statistical cost estimates [5, 33]. For graph pattern matching this search is dominated by join-order selection over the pattern’s relationships [20]. The optimizer estimates intermediate-result cardinalities for subpatterns, increasingly relying on highorder summaries such as short-path and small-pattern statistics [20, 26, 38], and chooses among binary-join and worst-case-optimal-join strategies for expanding the pattern [5, 20, 25, 33, 37]. Although the two classes pursue different objectives, with rule-based rewriting removing structural redundancy and cost-based optimization minimizing estimated cost, both converge structurally distinct queries onto a smaller space of canonical plans. These optimizations carry a critical implication for testing. Metamorphic oracles rely on the structural difference between a reference query and its follow-up to induce distinguishable execution behavior [6, 22]. Yet the optimizer’s objective is precisely to eliminate such differences. When two queries are executed against the same graph state and reduce to the same execution plan, their results agree regardless of whether the system under test contains a defect, and the oracle’s consistency check passes unconditionally [20, 28]. This plan convergence renders affected metamorphic tests incapable of detecting execution-level defects. 3 3.1

Method Integration Framework A Unified Testing Model

Existing graph database testing methods differ substantially in their construction logic: graphderived testing applies controlled transformations to the test graph and checks the predicted relationship between the results; statement metamorphic testing transforms the query and checks a metamorphic relation between the original and transformed results, for example by rewriting a query into a semantically equivalent form; differential testing executes a fixed query across multiple database systems and compares their results. Despite these surface differences, a single round of testing always follows the same structure: prepare one or more database states, execute operations on a target system, collect the results, and

6

Tinghan Li et al.

check a predefined relation over them. We formalize this with four elements. A database state 𝑆 is a snapshot of a graph database: its nodes, edges, labels, and properties. An operation 𝑄 is a Cypher statement. Given a state 𝑆, an operation 𝑄, and a concrete database instance 𝑡 as the execution target, the observation is everything the oracle inspects, such as the returned rows and the execution plan: 𝑂 = execute(𝑆, 𝑄, 𝑡). A correctness relation 𝑅(𝑂 1, . . . , 𝑂𝑛 ) is a predicate over observations; a failing relation constitutes a bug report. Within this model, the three families differ in exactly one way. Each test capability varies a single argument of execute(𝑆, 𝑄, 𝑡) while fixing the other two, as shown in Algorithm 1. Algorithm 1 Unified execution skeleton. Each testing family varies one axis of execute and fixes the other two. Require: seed inputs (𝑆, 𝑄, 𝑡 ); relation 𝑅; a derivation 𝛿 expanding one axis: GraphDerived: 𝛿 = 𝑓 over 𝑆 StatementMetamorphic: 𝛿 = 𝑔 over 𝑄 Differential: 𝛿 = T over 𝑡 Ensure: a bug report iff 𝑅 fails over the collected observations 1: ⟨𝑎 0 , . . . , 𝑎𝑛 ⟩ ← 𝛿 (𝑆, 𝑄, 𝑡 ) 2: for 𝑖 ← 0, 1, . . . , 𝑛 do 3: 𝑥𝑖 ← (𝑆, 𝑄, 𝑡 ), chosen axis set to 𝑎𝑖 4: 𝑂𝑖 ← execute (𝑥𝑖 ) 5: 𝑂𝑖 .result ← normalize (𝑂𝑖 .result ) 6: end for 7: return 𝑅 (𝑂 0 , 𝑂 1 , . . . , 𝑂𝑛 )

⊲ expand the chosen axis

GraphDerived varies the state 𝑆 by deriving a family of states through 𝑓 , StatementMetamorphic varies the operation 𝑄 by deriving variant queries through 𝑔, and Differential varies the target 𝑡 over a set of systems T . Everything else, which covers initialization, execution, and result normalization, is identical across families; only how an input is constructed and which relation 𝑅 is checked differ. The test capabilities we integrate from eight methods [15, 17–19, 21, 22, 40, 45] reduce to these three families under this interface. Table 1(a) lists the integrated methods by family and publication year. 3.2

Integrating Methods Behind the Interface

The model above is what makes integration tractable. Because all test capabilities share the same skeleton and differ only in 𝑓 , 𝑔, and 𝑅, GraphWeave can run them in one environment. Each capability is specified by its construction logic and its correctness relation; a shared engine then performs the uniform execute-and-normalize steps, and a per-target adapter isolates all systemspecific logic. Consequently, integrating a new capability reduces to supplying its construction logic and relation, and supporting a new database reduces to adding one adapter, which requires no change to the engine or to any existing capability. Crucially, the same shared execution records process-level data that individual methods discard: how each state and query was derived and which semantic preconditions each relation relies on. This trace is what §5 and §6 build on, because it lets a false positive be attributed to the specific assumption it violates rather than an unexplained mismatch, which is impossible when only the final verdict is kept.

Uncovering Systematic Blind Spots in Graph Database Testing through Integration and Process-Level Analysis

4

7

Studying Testing Methods through Process-Level Analysis

Having integrated eight existing methods behind the shared interface of §3, we now use this platform to study the integrated methods themselves. Because every campaign records processlevel data such as execution plans alongside each verdict, we can look beyond whether an oracle fired and ask why it fired, attributing each outcome to the concrete construction trace and semantic assumption behind it. This section reports what that process-level view reveals about existing testing methods. 4.1

Study Setup

We instantiate our testing framework with the eight methods listed in Table 1(a), and run all of them against three mature, widely deployed graph databases, which in this study are Neo4j, Memgraph [23], and FalkorDB, as shown in Table 1(b). The popularity indicators in Table 1(b) are from June 2026: ranks follow DB-Engines [36], and star counts are from GitHub. All systems run with their default query optimizers enabled and differ in concrete query semantics relevant to oracle validity. Each (method, system) campaign runs in an isolated container against a separate database instance for a fixed 12-hour budget under identical resource and timeout policies, and every run records process-level data such as execution plans and execution times. During integration, we tag each test capability with its originating method, so every report can be attributed to the method that produced it. We distinguish three levels of outcome used throughout the study: a raw report is any oracle-triggered candidate, a false positive is a raw report that does not correspond to a real defect, and a unique bug is a root-cause-level defect obtained after deduplication. Table 1. Testing methods and database systems used in the study. (a) Testing methods. Family

Methods (year)

Graph-derived

Gamera (2023), GSlicer (2025)

Statement metamorphic

GDBMeter (2023), Gamera (2023), GraphGenie (2024), GraspDB (2024), GRev (2024), Dinkel (2026)

Differential

GDsmith (2023) (b) Database systems. System

Version

Rank

Stars

Neo4j Memgraph FalkorDB

2026.03.1 3.9.0 4.16.0

1 13 22

16.8k 4.2k 4.7k

Our study is organized around the following research questions: • RQ1: What does the raw output of the integrated methods look like, and how much of it corresponds to real defects? • RQ2: What root causes underlie the false positives that dominate this raw output? • RQ3: Which query patterns cause metamorphic follow-ups to collapse to the same execution plan, and which resist collapse?

8

4.2

Tinghan Li et al.

RQ1: Raw Reports Produced by the Integrated Methods

Finding 1: reports are dominated by false positives. After the campaigns finish, we observe that thousands of reports are produced, which far exceeds the number of genuine defects a mature database is likely to contain. We then inspect all the reports manually to distinguish false positives from reports of real bugs. Table 2 shows the result of our inspection. Table 2. Report funnel by method and database. Raw denotes reports before triage, FP false positives, and Bugs unique confirmed bugs. GDsmith runs one joint differential campaign across all three systems. (a) Per-database campaigns Neo4j

Memgraph

FalkorDB

Method

Raw

FP

Bugs

Raw

FP

Bugs

Raw

FP

Bugs

Gamera GDBMeter GraphGenie GraspDB GRev GSlicer Dinkel

98 0 54 40 9 128 22

54 0 54 40 9 102 0

1 0 0 0 0 1 3

234 12 133 0 60 362 36

123 0 133 0 13 203 12

1 1 0 0 1 1 3

178 134 527 35 10 412 46

156 134 249 35 2 342 36

2 0 1 0 1 1 1

(b) Joint differential campaign Compared systems

Raw

FP

Bugs

Neo4j + Memgraph + FalkorDB

1,584

1,439

2

For example, GDsmith produces 1,439 false positives out of 1,584 raw reports in its tri-database differential campaign, and GraspDB produces 40 of 40 on Neo4j and 35 of 35 on FalkorDB, making every report a false positive. Overall, 3,136 of the 4,114 raw reports (76.2%) are false positives, so most reports produced by the integrated methods do not correspond to real bugs. Finding 2: Reports of real bugs are dominated by duplicates. Once false positives are set aside, the remaining reports of real bugs still number in the hundreds. Of GraphGenie’s 527 raw reports on FalkorDB, 249 are false positives; the remaining 278 reports all refer to a single unique bug. Similarly, Gamera’s 234 reports on Memgraph include 123 false positives, and the remaining 111 reports all refer to one bug. Most reports of real bugs are therefore duplicates, and false-positive filtering must be followed by deduplication to determine the number of unique bugs. Separating the few real defects from this flood of false positives and duplicates demands substantial manual effort, which is often impractical. 4.3

RQ2: Characterizing False Positives

To explain the false positives observed in RQ1, we inspect their causes and group them into four categories. Impl. denotes implementation-induced false positives, where the reference implementation does not correctly implement the method described in the paper. Graph Sem. denotes false positives related to the semantic constraints of graph pattern matching. Null/Pipe denotes false positives from incorrect assumptions about null values or clause pipelines. Dialect denotes false positives caused by dialect incompatibilities. Table 3 reports the distribution of these false positives across the eight methods. Finding 3: Overlooked graph-semantic constraints cause false positives. In Table 3, Graph Sem. denotes false positives caused by test oracles that overlook the target database’s graph-semantic constraints. As described in Section 2.2, these constraints determine which mappings of a graph

Uncovering Systematic Blind Spots in Graph Database Testing through Integration and Process-Level Analysis

9

Table 3. Distribution of false-positive reports by root-cause category. Method Gamera GDBMeter GraphGenie GraspDB GRev GSlicer Dinkel GDsmith

Impl. (%)

Graph Sem. (%)

Null/Pipe (%)

Dialect (%)

FP Reports

10.8 35.8 59.2 32.0 29.2 11.9 0 4.9

75.6 0 0 18.7 0 43.0 56.2 51.1

0 0 24.5 34.7 0 41.1 0 31.0

13.6 64.2 16.3 14.6 70.8 4.0 43.8 13.0

333 134 436 75 24 647 48 1,439

pattern are valid and how many result rows each mapping produces. We find this cause in five of the eight methods. It accounts for more than half of the false positives from Gamera (75.6%), Dinkel (56.2%), and GDsmith (51.1%). The oracles of these test methods implicitly assume particular semantic constraints when checking the query results of test cases. If these assumptions conflict with the target system’s actual choices, the oracles produce false positives. To understand these false positives, we next examine how graph-semantic constraints differ across database systems. Finding 4: Graph-semantic constraints differ across database systems. We examine how eight graph database systems that support Cypher implement the three constraints defined in Section 2.2. Their choices form five combinations of constraint settings (Table 4). Table 4. Graph-semantic constraints in eight graph database systems. System

Legality

Multiplicity

Reset boundary

Neo4j Memgraph ArcadeDB Apache AGE NebulaGraph FalkorDB NeuG Kuzu

no reuse no reuse no reuse no reuse no reuse edge reuse edge reuse edge reuse

single length-amplified length-amplified single single single per-direction per-direction

MATCH clause MATCH clause MATCH clause comma-pattern comma-pattern n/a n/a n/a

First, legality differs: Neo4j, Memgraph, ArcadeDB [4], Apache AGE [3], and NebulaGraph [39] reject same-edge reuse within the relevant scope, whereas FalkorDB, NeuG, and Kuzu [9] permit it. Second, multiplicity differs even when legality is fixed. On a one-hop undirected self-loop, six systems emit a single witness, but NeuG and Kuzu emit two, one per traversal direction. Under variable-length traversal, Memgraph and ArcadeDB amplify a single legal sequence into multiple witnesses, whereas the other no-reuse systems do not. FalkorDB permits edge reuse yet emits single witnesses, confirming that these two constraints, legality and multiplicity, are separable. Third, the reset boundary differs: Neo4j, Memgraph, and ArcadeDB refresh the uniqueness scope only at MATCH-clause boundaries, while Apache AGE and NebulaGraph refresh it at comma-pattern boundaries; for engines that permit edge reuse the boundary is inapplicable. The same query can therefore yield different row counts because systems differ in which relationship bindings they admit and how often they count each binding. Case 1: relationship binding decides which edges may fill a pattern. A representative example from GDsmith is shown in Figure 2. The witness graph contains one node and one self-loop. GDsmith

10

Tinghan Li et al.

can generate an anonymous two-hop pattern and return only a constant value. On FalkorDB, the single self-loop can be reused for both relationship slots, so the query produces one row. On Neo4j, the same match is rejected because the engine enforces relationship uniqueness within the graph pattern, so the query returns no rows. Both edge-uniqueness semantics are valid, so the row-count mismatch is a false positive of the differential oracle rather than a defect in either system. Witness graph

Query :T4

MATCH (n0:L1)-[:T4]-()-[:T4]-() RETURN 1 AS a7 ORDER BY a7;

n0:L1 Observed rows

0

Neo4j

FalkorDB

1

Fig. 2. A differential false positive caused by relationship-uniqueness semantics.

Case 2: enumeration multiplicity decides how many times a match is reported. A representative false positive from the metamorphic method Dinkel is shown in Figure 3. The witness graph contains one node and two self-loops. Dinkel rewrites a two-hop undirected expansion into two adjacent one-hop expansions and expects the source and follow-up to agree. On Neo4j, both queries return two rows. On Memgraph, the source returns four rows and the split returns eight, so the metamorphic oracle flags a mismatch. Witness graph r1:R

Query forms r2:R

a:N

Source

MATCH p=(a:N)-[*2..2]-(a:N) RETURN relationships(p)

Split

MATCH p=(a:N)-[*1..1]-()-[*1..1]-(a:N) RETURN relationships(p)

Observed rows Source Split

Neo4j

Memgraph

2 2

4 8

Fig. 3. A metamorphic false positive caused by path-enumeration multiplicity.

This mismatch is not simply a relationship-uniqueness violation. An explicit two-hop pattern with named relationships does not admit the binding 𝑟 = 𝑠 on either Neo4j or Memgraph in this graph, so the legal binding set is unchanged. The discrepancy instead comes from bag-semantic path enumeration across a variable-length segment boundary. Neo4j treats an undirected self-loop as a single traversal direction, whereas Memgraph enumerates both directions independently within each one-hop segment, multiplying the final row count. The rewrite therefore preserves which paths are legal but changes how many times each legal path is emitted. Because both engines apply their respective enumeration rules consistently, the report is a false positive of the metamorphic oracle rather than a defect in either system. Finding 5: Inconsistent application of graph-semantic constraints reveals real bugs. When inspecting reports, we also discover real bugs caused by these semantic constraints. Figure 4 shows a real FalkorDB bug we discovered. The witness graph contains two nodes, two reciprocal edges, and one self-loop. From node 1 back to node 1, the exact-length form, the explicit two-hop form, and the

Uncovering Systematic Blind Spots in Graph Database Testing through Integration and Process-Level Analysis

11

split form should describe the same matching space. Neo4j and Memgraph return two rows on all three forms. FalkorDB also returns two rows on the exact-length form, but five on the explicit and split forms. Witness graph

Query forms Exact

MATCH p=(a:N {id:1})-[*2..2]-(b:N {id:1}) RETURN [rel IN relationships(p) | rel.eid] AS eids

Explicit

MATCH (a:N {id:1})-[r]-(m)-[s]-(b:N {id:1}) RETURN r.eid AS reid, s.eid AS seid

Split

MATCH p=(a:N {id:1})-[*1..1]-()-[*1..1]-(b:N {id:1}) RETURN [rel IN relationships(p) | rel.eid] AS eids

r3 r1

1:N

2:N r2

Observed rows Exact Explicit Split

Neo4j

Memgraph

FalkorDB

2 2 2

2 2 2

2 5 5

Fig. 4. A real bug caused by contradictory relationship-uniqueness enforcement.

Unlike Case 2, this discrepancy changes the legal binding set itself rather than only the multiplicity. Repeated-edge bindings such as [r1,r1] and the self-loop self-pair [r3,r3] are excluded by the exact-length form but admitted by the explicit and split forms on FalkorDB. This is a real bug because the system contradicts itself about whether the same edge may occupy two relationship slots in one match. Taken together, RQ2 shows that graph-semantic constraints are a common source of false positives across multiple testing methods. When different systems make different but internally self-consistent choices, the report is a false positive; when one system gives contradictory answers to the same constraint across equivalent forms, the mismatch is a real defect. 4.4

RQ3: Characterizing Plan Collapse

Using the execution plans recorded by GraphWeave, we study how often equivalent query pairs compile to the same plan, why this happens, and which transformations retain different plans. Finding 6: 5–34% of equivalent query pairs lose their ability to detect bugs. Table 5 reports the same-plan ratio for comparable source/follow-up pairs. For each method-database combination we repeat the campaign under three independent seeds, each run stopping once it collects 5,000 comparable pairs whose two queries both execute and expose a plan. Each cell reports the mean fraction sharing a plan hash across the three runs. The three runs agree within 1.3 percentage points. As the table shows, pairs that compile to the same plan appear in every equivalence-based metamorphic method, ranging from roughly 5% to 34% of comparable pairs. Notably, GraspDB’s same-plan ratio rises from 5.5% on Neo4j to 33.2% on FalkorDB, a gradient that reflects dialect fit rather than optimizer strength. FalkorDB and Memgraph accept fewer of its write-bearing variants, so its comparable pairs skew toward collapse-prone forms. The per-method ratios in Table 5 average over transformations that individually behave very differently. Figure 5 resolves the Neo4j campaign into its 54 equivalence-preserving transformations, ranked by collapse rate and encoded by the color and marker shape of their originating method; a collapse-resistant transformation leaves no bar, so a rug beneath the axis marks its method.

12

Tinghan Li et al.

Same-plan collapse rate (%)

Table 5. Same-plan ratios by method and database, averaged over three runs.

Method

Neo4j

Memgraph

FalkorDB

GraphGenie GRev GraspDB Dinkel

11.29% 13.71% 5.50% 27.44%

15.34% 5.79% 26.67% 17.44%

18.94% 19.76% 33.24% 34.21%

100 75 50

33 transformations never collapse (0%)

Method Dinkel GraspDB GraphGenie GRev

25 0

origin

Transformations, ranked by collapse rate

Fig. 5. Same-plan collapse rates of 54 query transformations on Neo4j.

The transformations divide into those that collapse and the 33 of 54 that never do. Which side a transformation falls on follows its shape rather than its source. A single method can include transformations that collapse to the source plan and others that retain distinct plans. §2.3 distinguished the two optimization classes that can erase a follow-up’s distinction: rule-based rewriting, which canonicalizes a query independently of the data, and cost-based optimization, which searches for the cheapest plan under cardinality statistics. We present one collapse driven by each class and a third transformation that neither can collapse, verified on Neo4j with its default planner over a graph with a skewed label distribution where |𝐴|=5, |𝐵|=500, and |𝐶 |=50, with 500 R- and 500 S-edges. Case A: rule-based rewriting collapses syntactic differences regardless of the data. The simplest collapses are structural: the rewrite phase canonicalizes surface variation before any cost is considered. In Figure 6, the follow-up reverses the written traversal direction from (a)-[:R]->(b) to (b)<-[:R]-(a) and appends a tautological WHERE true, both of which are transformations that equivalence-based methods routinely apply. Direction normalization and dead-predicate elimination are semantics-preserving, so Neo4j folds the two queries to an identical operator tree, and both return 500. Driven by rewrite rules rather than statistics, this collapse is data-independent: the queries share a plan on any instance. Case B: cost-based optimization collapses join orders chosen from the data. In Figure 7, a two-hop chain is written as two comma-separated patterns, and the follow-up lists them in the opposite order. Both compile to the same plan, which is anchored by a NodeByLabelScan on A and expands A→B→C, and both return 500. The anchor is set by statistics, not syntax: A is the rarest label, so the planner starts there and drives expansion from the smallest endpoint regardless of how the patterns were written. A control confirms the data dependence: on an isomorphic chain P→Q→Z whose rare label sits at the other end, where |𝑍 |=5, the same reordering instead collapses to a plan anchored at Z. The convergence point moves with the cardinality estimates, which is the signature of cost-based rather than rule-based collapse.

Uncovering Systematic Blind Spots in Graph Database Testing through Integration and Process-Level Analysis

13

Source query MATCH (a:A)-[:R]->(b:B) RETURN count(*) AS cnt Follow-up: direction reversal + dead predicate MATCH (b:B)<-[:R]-(a:A) WHERE true RETURN count(*) AS cnt Shared Neo4j EXPLAIN operator tree ProduceResults | cnt EagerAggregation | count(*) AS cnt Filter | b:B Expand(All) | (a)-[:R]->(b) NodeByLabelScan | a:A

Fig. 6. A rule-based plan-collapse case. Source query MATCH (a:A)-[:R]->(b:B), (b)-[:S]->(c:C) RETURN count(*) AS cnt Follow-up: comma-pattern reordering MATCH (b:B)-[:S]->(c:C), (a:A)-[:R]->(b) RETURN count(*) AS cnt Shared Neo4j EXPLAIN operator tree ProduceResults | cnt EagerAggregation | count(*) AS cnt Filter | c:C Expand(All) | (b)-[:S]->(c) Filter | b:B Expand(All) | (a)-[:R]->(b) NodeByLabelScan | a:A

Fig. 7. A cost-based plan-collapse case.

Both rule-based rewriting and cost-based optimization can therefore eliminate the plan differences introduced by equivalence-preserving transformations. Because equivalence-based metamorphic methods detect bugs via inconsistent results, executing both queries against the same graph state with the same plan makes their results identical by construction. Such pairs consume testing resources without revealing defects; if their shared plan contains a bug, both queries can return the same incorrect result and the oracle remains silent. Finding 7: Some query transformations resist plan collapse. GraspDB builds follow-ups by injecting net-zero write sequences: sequences of write operations that leave the graph state unchanged after completion, such as creating and then deleting a node or assigning a property on a null target. These sequences preserve the intended query results and final graph state while adding write operators to the follow-up plan. In Figure 8, the follow-up extends a write source with a CREATE c0 . . . DELETE c0 no-op. The added sequence creates a temporary node and deletes it before the query completes, without modifying existing graph data; the final graph state is therefore the same as after the source query. Neo4j nevertheless retains the Create and Delete operators and inserts an Eager barrier to enforce read/write ordering, leaving the follow-up plan structurally distinct from the source. Rule-based rewriting cannot drop a write operator, as write semantics forbid treating it as dead code, and cost-based optimization cannot reorder it past the read it conflicts with. This is why write-oriented metamorphic testing resists the plan collapse that read-only equivalence rewrites suffer, and it underlies the method complementarity exploited in the bug-discovery evaluation in §6.4.

14

Tinghan Li et al.

Source query MATCH (a:A) SET a.k = a.k + 1 RETURN count(*) AS cnt Follow-up: injected net-zero write MATCH (a:A) SET a.k = a.k + 1 CREATE (c0 {id:-1}) DELETE c0 RETURN count(*) AS cnt Source plan ProduceResults | cnt EagerAggregation | count(*) AS cnt SetProperty | a.k = a.k + 1 NodeByLabelScan | a:A Follow-up plan: write operators survive ProduceResults | cnt EagerAggregation | count(*) AS cnt Delete | c0 Eager | read/delete conflict Create | (c0 {id:-1}) SetProperty | a.k = a.k + 1 NodeByLabelScan | a:A

Fig. 8. A collapse-resistant case.

4.5

Guidelines from the Study

We distill the study into the following guidelines for both integrated testing and future test-method design. G1: Preserve process-level data for postprocessing. Our analysis depends on information that raw oracle verdicts do not contain, including construction traces, oracle assumptions, execution plans, and observed outputs. An integrated platform should therefore preserve these processlevel artifacts as first-class report fields, so postprocessing can classify false positives, distinguish semantic ambiguity from bugs, and deduplicate reports by root cause. G2: Separate semantic false positives from real bugs. In semantic regions where systems may validly differ, cross-system disagreement alone is weak bug evidence. A stronger signal is intrasystem contradiction: the same system should not disagree across equivalent forms that exercise the same semantic dimension. G3: Treat graph semantics as oracle preconditions. Graph-pattern oracles encode semantic choices, including legality, witness multiplicity, and reset boundaries. A method should declare these assumptions explicitly and check them against the target semantic profile before treating a mismatch as a failure. G4: Triage optimizer-collapsed follow-ups. For equivalence-based metamorphic testing, semantic preservation is not enough: a source/follow-up pair that compiles to the same plan on the same graph state has no oracle power. The execution pipeline should therefore identify same-plan pairs and remove them from bug-oriented inspection. G5: Design transformations that survive optimization. Future metamorphic methods should consider whether their follow-ups remain distinguishable after rule-based and cost-based optimization. Collapse-resistant transformations, such as net-zero writes, provide complementary signal because they preserve semantics while still exercising different execution paths.

Uncovering Systematic Blind Spots in Graph Database Testing through Integration and Process-Level Analysis

5

15

Bug Postprocessing and Process-Level Analysis

The study of §4 provides guidelines for integrated testing. We follow the guidelines to mitigate the two blind spots described above. The design mainly consists of two components: a unified postprocessing workflow and a plan-aware triage. 5.1

Overview

As discussed in §1, running integrated methods for hours can produce thousands of bug reports, including many false positives and duplicate reports. This motivates a postprocessing pipeline that automates these tasks and keeps human effort manageable. The pipeline consists of three stages: noise reduction, report analysis, and feedback mechanisms, as shown in Figure 9. Multi-agent analysis system

Disposition Known issue

Coordinator agent from testing run

Standardized testing artifacts

Rule-based issue gate

Capability clustering + embedding

New bug Cluster splitting

Deep analysis

Rules synthesis False positive

match update spec

to next testing run

Target adapter

Issue library

gate-update spec

Spec applier agent

adapter spec

Fig. 9. GraphWeave’s postprocessing pipeline. Standardized artifacts pass through issue gating, capabilityaware clustering, and multi-agent analysis; confirmed dispositions update the issue library or target adapter.

The pipeline first takes standardized testing artifacts as input, consisting of a raw report with an oracle violation record and relevant process-level data, such as execution plans, collected by the testing framework. Reports then pass through three sequential stages. A rule-based issue gate matches incoming reports against a known-issue library and directly classifies any hits. Remaining reports are grouped by capability labels and then refined using report embeddings. The clustered reports then enter a multi-agent analysis system, in which a coordinator agent dispatches three sub-agents to perform in-depth analysis and produces, for each cluster, a disposition decision: known issue, false positive, or new bug. If the decision is a known issue, a gate-update specification is synthesized and registered back into the issue library. If the decision is a dialect-related false positive, an adapter specification is synthesized and returned to the target adapter of §3, where it is applied automatically in subsequent testing. This section details the multi-agent analysis system and the feedback mechanisms. 5.2

Multi-Agent Analysis System

Relying on an LLM to make disposition decisions during postprocessing raises two challenges. The first is context capacity: raw reports carry sizable construction traces, execution plans, and target outputs. Performing full deep analysis on every report would exhaust the context window. The second is auditability: an LLM may produce plausible disposition judgments, but without explicit evidence requirements it is difficult for analysts to determine whether a judgment is well supported. GraphWeave addresses these two challenges at separate layers of its design. All agents run on Claude Code backed by the claude-sonnet-4-6 snapshot under its default decoding, and the three sub-agents share this backend, differing only in their stage prompt.

16

Tinghan Li et al.

On-demand sub-agents. Mirroring how human analysts work, we design three sub-agents to perform the three sub-tasks of report analysis. The cluster-splitting agent assesses the internal homogeneity of each cluster by comparing two sampled anchors, the medoid with the smallest average cosine distance to the rest and the outlier farthest from that medoid; if the cluster is heterogeneous, the agent splits it into two sub-clusters for further analysis. The deep-analysis agent is responsible for deep analysis and producing verifiable evidence, and it operates through two established debugging techniques. The first is delta debugging [43], which minimizes the witness graph and query while preserving the failure signal, stripping away structures unrelated to the failure; to enable the LLM to perform delta debugging effectively and efficiently, we distill human debugging experience into a skill that specifies the reduction objectives, decision criteria, and iteration strategy. The second is dynamic debugging, where the agent attaches a source-level debugger to a debug build of the system under test to inspect its runtime state. To classify a report as a bug, the agent must provide both dynamic-debugging results and reproducible runtime evidence that links the observed failure to a concrete implementation path for human confirmation. Notably, we distill expert knowledge derived from the study of §4 into the skill that guides this agent to identify whether a report actually represents a semantic-ambiguity false positive. The rules-synthesis agent is activated only after a disposition has been confirmed, and produces a gate rule or a dialect adapter specification. Disposition-specific acceptance criteria. To ensure that the sub-agents adhere to these criteria, a coordinator agent audits the output of each sub-agent and triggers a re-run on demand. Only once the evidence criteria of a disposition are met does the agent system commit to a decision, which falls into one of three categories: known issue, new bug, or false positive. Classifying a report as a known issue or new bug requires the agent to submit two artifacts. The first is evidence, consisting of dynamic-debugging results together with supporting documentation, that establishes the behavior as a genuine defect. The second is a gating rule for the feedback mechanism that prevents such reports from raising a signal in future runs; each rule carries both positive and negative cases, specifying what should and should not be filtered. A false positive is further attributed to one of two causes. A dialect false positive requires a dialect adapter specification together with alignment evidence showing that the adaptation preserves the testing method as faithfully as possible. An oracle false positive, which arises from semantic ambiguity, requires evidence that the observed database behavior is valid, established with the analysis skill described above. 5.3

Feedback Mechanisms

GraphWeave feeds back only confirmed disposition results, and routes them according to the postprocessing guidelines of §4.5. The study distinguishes two feedback paths: dialect false positives require changing how requests are expressed, whereas confirmed bug families and duplicate reports require suppressing repeated analysis of the same root cause. A dialect false positive updates the target adapter, because later executions should express the same testing intent in the target’s dialect or reject an unsupported request shape. A confirmed bug family or duplicate report updates the issue gate, because the input is valid but its signal should no longer trigger deep analysis. These two outcomes define two independent feedback channels: request-level adapter updates and root-cause-level gate updates. Request-level adapter update. We model dialect adaptation as a request-level transformation task. As discussed in §3, a request of a test case can be abstracted into three components: the target database, the graph state to be constructed, and the query sequence. Before a request is sent to the database, the target adapter transforms this combined information into a target-specific request. Given confirmed dialect evidence, the updated adapter may rewrite statements, lower

Uncovering Systematic Blind Spots in Graph Database Testing through Integration and Process-Level Analysis

17

graph construction into a target-specific form, mark expected errors, or reject unsupported request shapes. The key point is that adaptation operates on the full request rather than on an isolated syntax fragment. When a false positive arises from the target dialect, the adapter can adjust the request expression while preserving the testing intent, instead of simply disabling the relevant feature. The multi-agent analysis system synthesizes candidate adaptation rules, which are then applied by the adapter’s deterministic rule pipeline. Any adaptation must preserve the graph state and statement relation; if semantic equivalence cannot be preserved, GraphWeave disables or modifies the request shape rather than silently executing a test with a changed intent. Each update is applied only within the dialect boundary supported by the evidence, and is not generalized to superficially similar query classes. Root-cause-level gate update. Root-cause-level gate feedback serves a different purpose: multiple reports can stem from the same root cause. We realize this with an issue library, where reports that share the same root cause are grouped into one issue family. In the issue gate, each family is associated with multiple rules, so that different manifestations of the same root cause are recognized as one issue and then filtered out. When a report reaches this channel, the multi-agent analysis system first checks whether it maps to an existing issue family; if not, it registers a new family. Because stable and concise root-cause analysis is hard for an agent to produce, we do not aim to use the root cause it submits for direct bug fixing, but only for noise reduction. The rules therefore need only capture the characteristics that group reports into the same issue family. The two channels are not interchangeable, and GraphWeave keeps them distinct: misrouting a confirmed bug family or duplicate report to the adapter can alter a valid input and mask future bugs, while misrouting a dialect false positive to the gate leaves the frontend generating invalid requests. Because both updates enter existing pipelines as rule entries, supporting a new target or issue type requires extending the corresponding rule library, without modifying the generator, adapter, and filter together. This shifts human effort from inspecting individual bugs to auditing rules grouped by family. 5.4

Plan-Aware Triage of Metamorphic Pairs

Section 4.4 showed that equivalence-based metamorphic methods routinely produce source/followup pairs that compile to the same plan on the same graph state, and that such a pair cannot expose a defect: an identical plan makes the two results equal by construction. These pairs waste execution budget on tests with no oracle power. For each equivalence pair, GraphWeave first obtains the execution plans using EXPLAIN and compares them. Only pairs with different plans are executed to compare their query results. This yields three dispositions. A pair with the same plan on the same graph state is redundant by construction and is dropped without executing either query, reclaiming the budget quantified in Section 4.4. A pair with different plans but the same result passes the oracle, yet its divergent plans on identical inputs hint at a missed optimization; GraphWeave records the pair’s execution times so that persistent gaps can be surfaced as performance issues rather than silently discarded. A pair with different plans and different results keeps its full oracle power and is retained for inspection as a candidate logic bug. Only the same-plan class removes work, and it weakens no oracle: a pair whose queries share a plan on the same graph state cannot disagree, so skipping it forfeits no discoverable bug. Because the triage reads only the plan and result already on the shared execution path described in Section 3, every integrated equivalence-based method benefits without method-specific changes.

18

6

Tinghan Li et al.

Evaluation

This section evaluates GraphWeave and guidelines from §4 along two directions: whether the unified postprocessing workflow reduces analytical workload and whether the platform discovers real defects in a previously untested system. 6.1

Experimental Setup

Integrated methods and target systems. We instantiate GraphWeave with the same eight methods listed in Table 1(a) as in the study of §4. Both RQs additionally target NeuG 0.1.1 [12], which had 118 GitHub stars in our June 2026 snapshot and was not previously exercised by any testing method. We likewise run it with its default query optimizer enabled. Execution environment and metrics. All campaigns reuse the unified containerized deployment of §4.1: each (method, system) pair runs in an isolated container against a separate database instance under the same 12-hour budget and timeout policy, with seeds and process-level artifacts recorded for replay. We report outcomes at the same three levels that §4.1 defines: raw report, false positive, and unique bug. Validation protocol. GraphWeave’s post-testing workflow first produces, for each raw report, an initial analysis that includes a false-positive assessment and a candidate root-cause hypothesis, serving only as an aid for human reviewers. Two authors then independently inspect each report and reach a verdict, resolving disagreements through discussion. For reports judged to be real bugs, we check whether the issue has already been reported and submit unreported cases to the developers for confirmation. 6.2

Research Questions

Our evaluation is organized around the following research questions: • RQ4: To what extent does GraphWeave’s unified postprocessing workflow reduce the analytical overhead of raw testing output, and how faithfully do its automated dispositions agree with human judgment? • RQ5: Does the unified platform enable practical bug discovery in a graph database system that has not been systematically exercised by prior work? 6.3

RQ4: Workload Reduction via Unified Postprocessing

As illustrated in §5.1, reports found in GraphWeave are processed by the unified postprocessing workflow. The workflow is organized in batches. Within each batch, raw reports first pass through an initial gating step, are clustered by root cause, examined through representative cases to yield deep-analysis units, and finally aggregated into bug families. We define workload reduction as the relative decrease from the raw report count to the number of items that ultimately require human inspection. A workflow that discards reports blindly would maximize this reduction, so we evaluate it on two axes: how much it compresses the raw output, and how faithfully its automated dispositions agree with the human verdicts of §6.1. Table 6 reports three representative batches on NeuG, to illustrate the per-batch reduction behavior.

Uncovering Systematic Blind Spots in Graph Database Testing through Integration and Process-Level Analysis

19

Table 6. Per-batch workload reduction achieved by GraphWeave’s unified postprocessing workflow on NeuG, shown for three representative batches of the continuous campaign. Input Filter Batch #1 #2 #3

Raw 26 17 12

Analysis

Outputs

Workload

Kept Clusters Units Adapter Gate Bugs 13 13 9

3 3 3

4 3 4

2 1 1

1 2 2

1 0 1

Reduction 84.6% 82.4% 66.7%

The postprocessing workflow reduces analytical workload by 66.7%–84.6% across three batches. Batch #1 gates 26 raw reports down to 13 and clusters them into 3 root-cause clusters, which expand into 4 deep-analysis units mapped to 2 dialect-adapter rules, 1 gate spec, and 1 bug family, an 84.6% reduction; Batch #2 gates 17 raw reports down to 13 and clusters them into 3 clusters that map one-to-one to 3 units, yielding 1 adapter rule and 2 gate specs, an 82.4% reduction; Batch #3 gates 12 raw reports down to 9 and clusters them into 3 clusters that expand into 4 units, yielding 1 adapter rule, 2 gate specs, and 1 bug family, a 66.7% reduction, as shown in Table 6. Each cluster is examined through its centroid and an outlier representative: a homogeneous cluster distills to a single unit, whereas a cluster that mixes two root causes splits into two, so the number of deep-analysis units lies between the cluster count and twice that count, and the adapter, gate, and bug columns sum to the unit count of each batch. In aggregate, the workflow compresses the volume of items requiring human inspection to roughly one sixth to one third of the original raw report count, directly addressing the redundancy noise quantified in the study of §4. The multi-batch design mitigates the coverage cost of representative-based clustering. Because each cluster is inspected only through its centroid and a single outlier representative, a cluster that mixes more than two root causes may leave a bug unexamined in one batch. We do not actively filter such reports out of subsequent batches, and missed bugs continue to surface as testing proceeds. In our campaign, a bug left unexamined in a Batch #1 cluster resurfaced as the outlier of a heterogeneous cluster in Batch #3 and was confirmed there, providing an empirically viable trade-off between per-batch efficiency and overall coverage. Human validation shows that automated triage preserves real bugs. To assess the correctness of the LLM analysis, we sample 100 analyzed reports together with the conclusions produced by the multi-agent system and validate them against human expert judgment. Table 7a summarizes the results. Real-bug recall is 100%, which means that all 29 sampled reports that correspond to real defects are retained after triage. After root-cause deduplication, these 29 bug reports collapse to three unique bugs. False-positive recall is 87.3%, which shows that the LLM conservatively escalates some false-positive reports as potential bugs. Escalating a false positive only adds review effort, whereas dropping a real bug is unrecoverable, so this asymmetry is a deliberate safety bias that lets the same run retain every real bug at 100% recall. The overall agreement rate between human reviewers and the LLM is 91%. Overall, although some wrong verdicts remain, the sampled audit shows that this error profile is acceptable for triage. Issue-gate filtering removes duplicates rather than suppressing new bugs. We also sample 100 reports filtered out by the issue gate and check whether any of them corresponds to a new bug. Table 7b shows that none of these reports corresponds to a new bug; all of them are duplicates of previous issues. Because the filter rules only narrow the scope of the triggering request, the gate reduces duplicate review effort without suppressing new defects.

20

Tinghan Li et al.

Table 7. Human audits of postprocessing decisions on NeuG: (a) reports analyzed by the multi-agent system and (b) reports filtered by the issue gate. (b) Issue-gate exclusions.

(a) Analyzed reports. Metric

Count

Rate

Outcome

Agreement with human verdict Real-bug recall False-positive recall

91 / 100 29 / 29 62 / 71

91% 100% 87.3%

Duplicate issue New bug

6.4

Count

Rate

100 0

100% 0%

RQ5: Bug Discovery in a Previously Untested System

We apply the eight testing methods integrated in GraphWeave to NeuG [12], a recently opensourced graph database that has not previously been targeted by existing graph database testing methods, to show the benefits of method integration in GraphWeave. The unified platform saturates at 19 unique bugs, and no single method covers all identified bugs. Each method, run in isolation, uncovers between 2 and 9 unique bugs on NeuG, as shown in Figure 10. 2

GDsmith

3

GraphGenie

2

GRev

4

GraspDB

9

Dinkel

2

Gamera GSlicer

3

GDBMeter

3 19

Total 0

5

10

15

20

Number of unique bugs

Fig. 10. Unique bugs uncovered on NeuG by each integrated method and in aggregate under GraphWeave. A single bug may be discovered by multiple methods; per-method counts therefore do not sum to the total.

We run each method until its unique-bug count stops growing, with new reports then filtered by the issue gate as duplicates of known issues. These per-method counts therefore represent each method’s discovery ceiling on this version rather than an artifact of insufficient runtime. Because the per-method bug sets overlap, the aggregate is smaller than the sum of individual counts. Combined under the unified platform, the eight methods collectively uncover 19 unique bugs, beyond which further runs surface only duplicates of known issues. Dinkel is the most productive method, and its 9 bugs include almost every bug found by the other equivalence-based metamorphic methods, yet Dinkel still misses the bugs found by methods such as GSlicer. No single method finds all 19, so the methods are complementary rather than substitutable. The uncovered bugs are confirmed genuine defects. Of the 19 unique bugs, all 19 have been reported upstream, all 19 have been confirmed as genuine defects, and 13 have already been fixed. Together, the two RQs establish the practical value of GraphWeave. Its postprocessing workflow cuts the human-inspection workload to one sixth to one third of the raw reports while preserving every audited real-bug report, yielding 100% real-bug recall; in the audit sample, the 29 retained bug

Uncovering Systematic Blind Spots in Graph Database Testing through Integration and Process-Level Analysis

21

reports collapse to three root-cause-level unique bugs after deduplication, closing the redundancy gap from the study without trading away coverage. Additionally, its unified platform combines eight complementary methods to uncover 19 previously unknown bugs in a previously untested system. A unified framework backed by process-level evidence thus delivers not only methodological value but also tangible returns in real-world bug discovery. 7

Threats to Validity

Internal validity. Every bug count rests on human judgment. We mitigate reviewer bias with the two-author protocol of Section 6.1, and developers confirmed all 19 NeuG defects. The automated triage of Section 5 only aids reviewers and cannot silently drop a defect; Section 6.3 shows 100% real-bug recall at 91% human agreement. For method fidelity, we port each method’s construction logic and oracle unchanged, cross-validate each integration against its reference implementation, and count departures as method-level implementation-induced false positives (Table 3) rather than GraphWeave failures. External validity. We test capabilities from eight methods over four Cypher systems, with NeuG serving as the target outside prior graph database testing work, so results may not transfer to other query languages or architectures. The two phenomena we report should nonetheless generalize. Semantic-constraint false positives follow from standards that leave pattern matching semantics to implementations, and plan collapse follows from the optimization every mature engine performs. The fixed 12-hour budget changes report volumes, not the existence claims behind developerconfirmed bugs. Construct validity. We measure defects at the root-cause level after deduplication rather than by raw report volume, so repeated reports of one root cause do not inflate bug counts. Plan collapse is measured by conservative within-system plan-hash comparison, so we can only undercount collapses. Conclusion validity. Our analysis of false-positive causes in Section 4.3 is qualitative and does not aim to estimate their occurrence rates. A single 12-hour campaign per method and system already yields 4,114 raw reports, far above the plausible number of real defects. We identify these causes by inspecting reports and examining the underlying oracle assumptions and database behavior. This qualitative analysis does not require repeated campaigns to estimate report frequencies. 8

Related Work

Graph and relational database testing. Prior graph database testing contributes complementary oracles, including differential testing [15], statement metamorphic methods [17–19, 22, 40, 45], and graph-derived capabilities [21, 45]. These adapt ideas from relational DBMS testing, including differential testing [35], random generation [34], and the SQLancer oracles [29–31]. Prior work primarily evaluates testing methods by the real bugs they find, with less attention to reports or tests that cannot reveal defects. GraphWeave integrates capabilities from eight methods behind a shared interface and examines both their reports and process-level data to study these problems. Its optimizer-induced plan-collapse finding is a query-engine instance of the oracle-design challenges surveyed in [6]. PATHTest [13], developed concurrently with our work, tests graph databases through transformations between fixed-length and variable-length queries. Like our study, it reports and quantifies false positives across existing methods. It attributes them to semantic differences and implementation errors. Rather than propose another testing method, we examine why existing methods

22

Tinghan Li et al.

produce false positives. We group them into four root-cause categories and focus on graph semantics. We identify three aspects of pattern-matching semantics that affect test oracles. Our criterion treats cross-system disagreement as a false positive when each system is internally consistent, and disagreement across equivalent forms within one system as a real bug. Based on this analysis, we derive guidelines for oracle design and develop an LLM-based workflow for automatic report analysis. Portable testing and LLM-based testing. Recent portable frameworks separate common logic from target handling through hand-maintained drop-ins [40] or runtime feedback that reweights the generation space, as in SQLancer++ [44]. These designs improve portability, but target knowledge still lives in the testing frontend as static rules or validity feedback that trades away parts of the generation space. GraphWeave instead derives target knowledge from post-run evidence and keeps dialect adaptation separate from report denoising, preserving testing intent by attributing each false positive to the assumption it violates under the underspecified GQL semantics [1, 16]. Whereas LLMs have been used to generate tests [41, 42], GraphWeave applies a multi-agent system to triage their output under the evidence-backed acceptance criteria of Section 5.2. 9

Conclusion

In this paper, we present an empirical study of eight existing graph database testing methods through integration and process-level analysis, and distill guidelines for both integrated testing and future test-method design. For integrated testing. False positives from query dialects and semantic constraints, together with duplicate reports, recur across methods, so a unified postprocessing pipeline is needed. Within it, intra-system consistency serves as the principle that separates semantic false positives from true defects. We realize these guidelines in GraphWeave and confirm their actionability on NeuG [12], which also shows the value of integration. For future method design. Semantic assumptions should be treated as explicit preconditions of oracle design. In addition, equivalence-based metamorphic methods can benefit from skipping pairs that share a plan on the same graph state, which cannot expose defects, before execution. References [1] Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan Reutter, and Domagoj Vrgoč. 2017. Foundations of modern query languages for graph databases. ACM Computing Surveys (CSUR) 50, 5 (2017), 1–40. [2] Renzo Angles and Claudio Gutierrez. 2008. Survey of graph database models. ACM computing surveys (CSUR) 40, 1 (2008), 1–39. [3] Apache Software Foundation. 2026. Apache AGE: A Graph Extension for PostgreSQL. https://age.apache.org/. Accessed: 2026-07. [4] ArcadeData Ltd. 2026. ArcadeDB: Multi-Model Database. https://arcadedb.com/. Accessed: 2026-07. [5] Surajit Chaudhuri. 1998. An overview of query optimization in relational systems. In Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. 34–43. [6] Tsong Yueh Chen, Fei-Ching Kuo, Huai Liu, Pak-Lok Poon, Dave Towey, TH Tse, and Zhi Quan Zhou. 2018. Metamorphic testing: A review of challenges and opportunities. ACM Computing Surveys (CSUR) 51, 1 (2018), 1–27. [7] Alin Deutsch, Nadime Francis, Alastair Green, Keith Hare, Bei Li, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Wim Martens, Jan Michels, et al. 2022. Graph pattern matching in GQL and SQL/PGQ. In Proceedings of the 2022 International Conference on Management of Data. 2246–2258. [8] FalkorDB, Inc. 2026. FalkorDB: A Property Graph Database (formerly RedisGraph). https://www.falkordb.com/. Accessed: 2026-07. [9] Xiyang Feng, Guodong Jin, Ziyi Chen, Chang Liu, and Semih Salihoğlu. 2023. Kùzu graph database management system. In The Conference on Innovative Data Systems Research, Vol. 7. 25–35.

Uncovering Systematic Blind Spots in Graph Database Testing through Integration and Process-Level Analysis

23

[10] Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Martin Schuster, Petra Selmer, et al. 2018. Formal semantics of the language cypher. arXiv preprint arXiv:1802.09984 (2018). [11] Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor. 2018. Cypher: An evolving query language for property graphs. In Proceedings of the 2018 international conference on management of data. 1433–1445. [12] GraphScope Team, Alibaba. 2026. NeuG: A Lightweight, High-Performance Embedded Graph Database. https: //github.com/alibaba/neug. Accessed: 2026-07. [13] Jinxin Gui, Yuanhong Lan, Longlong Lu, Yifei Lu, and Minxue Pan. 2026. Testing Graph Databases via Transformations Between Fixed-Length and Variable-Length Queries. Proceedings of the VLDB Endowment 19, 9 (2026), 2234–2247. doi:10.14778/3819518.3819547 [14] Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d’Amato, Gerard De Melo, Claudio Gutierrez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, et al. 2021. Knowledge graphs. ACM Computing Surveys (Csur) 54, 4 (2021), 1–37. [15] Ziyue Hua, Wei Lin, Luyao Ren, Zongyang Li, Lu Zhang, Wenpin Jiao, and Tao Xie. 2023. GDsmith: Detecting bugs in Cypher graph database engines. In Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis. Association for Computing Machinery, 163–174. doi:10.1145/3597926.3598046 [16] ISO/IEC. 2024. Information technology — Database languages — GQL. International Standard ISO/IEC 39075:2024. First edition, April 2024. [17] Yuancheng Jiang, Jiahao Liu, Jinsheng Ba, Roland HC Yap, Zhenkai Liang, and Manuel Rigger. 2024. Detecting logic bugs in graph database management systems via injective and surjective graph query transformation. In Proceedings of the 46th IEEE/ACM International Conference on Software Engineering. 1–12. [18] Matteo Kamm, Manuel Rigger, Chengyu Zhang, and Zhendong Su. 2023. Testing graph database engines via query partitioning. In Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis. 140–149. [19] Shuang Liu, Junhao Lan, Xiaoning Du, Jiyuan Li, Wei Lu, Jiajun Jiang, and Xiaoyong Du. 2024. Testing graph database systems with graph-state persistence oracle. In Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis. 666–677. [20] Bingqing Lyu, Xiaoli Zhou, Longbin Lai, Yufan Yang, Yunkai Lou, Wenyuan Yu, Ying Zhang, and Jingren Zhou. 2025. A Modular Graph-Native Query Optimization Framework. In Companion of the 2025 International Conference on Management of Data. 566–579. [21] Qiuyang Mang, Jinsheng Ba, Pinjia He, and Manuel Rigger. 2025. Finding Logic Bugs in Graph-processing Systems via Graph-cutting. Proceedings of the ACM on Management of Data 3, 3 (2025), 1–27. [22] Qiuyang Mang, Aoyang Fang, Boxi Yu, Hanfei Chen, and Pinjia He. 2024. Testing graph database systems via equivalent query rewriting. In Proceedings of the IEEE/ACM 46th International Conference on Software Engineering. Association for Computing Machinery, 1–12. doi:10.1145/3597503.3639200 [23] Memgraph Ltd. 2026. Memgraph: In-Memory Graph Database. https://memgraph.com/. Accessed: 2026-07. [24] Neo4j, Inc. 2026. Neo4j Graph Database. https://neo4j.com/. Accessed: 2026-07. [25] Hung Q Ngo, Ely Porat, Christopher Ré, and Atri Rudra. 2018. Worst-case optimal join algorithms. Journal of the ACM (JACM) 65, 3 (2018), 1–40. [26] Yeonsu Park, Seongyun Ko, Sourav S Bhowmick, Kyoungmin Kim, Kijae Hong, and Wook-Shin Han. 2020. G-CARE: A framework for performance benchmarking of cardinality estimation techniques for subgraph matching. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 1099–1114. [27] Andy Pavlo and Carnegie Mellon Database Group. 2026. Database of Databases. https://dbdb.io/. Accessed: 2026-07. [28] Hamid Pirahesh, Joseph M Hellerstein, and Waqar Hasan. 1992. Extensible/rule based query rewrite optimization in Starburst. ACM Sigmod Record 21, 2 (1992), 39–48. [29] Manuel Rigger and Zhendong Su. 2020. Detecting optimization bugs in database engines via non-optimizing reference engine construction. In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 1140–1152. [30] Manuel Rigger and Zhendong Su. 2020. Finding bugs in database systems via query partitioning. Proceedings of the ACM on Programming Languages 4, OOPSLA (2020), 1–30. [31] Manuel Rigger and Zhendong Su. 2020. Testing database engines via pivoted query synthesis. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 667–682. [32] Ian Robinson, Jim Webber, and Emil Eifrem. 2015. Graph databases: new opportunities for connected data. " O’Reilly Media, Inc.". [33] P Griffiths Selinger, Morton M Astrahan, Donald D Chamberlin, Raymond A Lorie, and Thomas G Price. 1979. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD international

24

Tinghan Li et al.

conference on Management of data. 23–34. [34] Andreas Seltenreich. 2015. SQLsmith: A Random SQL Query Generator. https://github.com/anse1/sqlsmith. Accessed: 2026-07. [35] Donald R Slutz. 1998. Massive stochastic testing of SQL. In VLDB, Vol. 98. 618–622. [36] solid IT gmbh. 2026. DB-Engines Ranking of Graph DBMS. https://db-engines.com/en/ranking/graph+dbms. Accessed: 2026-07. [37] Todd L Veldhuizen. 2014. Leapfrog triejoin: A simple, worst-case optimal join algorithm. In Proc. International Conference on Database Theory. [38] Zhengdong Wang, Qiang Yin, and Longbin Lai. 2025. Path-Centric Cardinality Estimation for Subgraph Matching. Proceedings of the VLDB Endowment (PVLDB) 18, 9 (2025), 3063–3076. [39] Min Wu, Xinglu Yi, Hui Yu, Yu Liu, and Yujue Wang. 2022. Nebula Graph: An open source distributed graph database. arXiv preprint arXiv:2206.07278 (2022). [40] Celine Wüst, Zuming Jiang, and Zhendong Su. 2026. Dinkel: State-Aware and Granular Framework for Validating Graph Databases. Proceedings of the VLDB Endowment 19, 6 (2026), 1198–1211. doi:10.14778/3797919.3797928 [41] Chunqiu Steven Xia, Matteo Paltenghi, Jia Le Tian, Michael Pradel, and Lingming Zhang. 2024. Fuzz4all: Universal fuzzing with large language models. In Proceedings of the IEEE/ACM 46th International Conference on Software Engineering. 1–13. [42] Chenyuan Yang, Yinlin Deng, Runyu Lu, Jiayi Yao, Jiawei Liu, Reyhaneh Jabbarvand, and Lingming Zhang. 2024. Whitefox: White-box compiler fuzzing empowered by large language models. Proceedings of the ACM on Programming Languages 8, OOPSLA2 (2024), 709–735. [43] Andreas Zeller and Ralf Hildebrandt. 2002. Simplifying and isolating failure-inducing input. IEEE Transactions on software engineering 28, 2 (2002), 183–200. [44] Suyang Zhong and Manuel Rigger. 2026. Scaling Automated Database System Testing. In Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2. Association for Computing Machinery, 1677–1692. doi:10.1145/3779212.3790215 [45] Zeyang Zhuang, Penghui Li, Pingchuan Ma, Wei Meng, and Shuai Wang. 2023. Testing graph database systems via graph-aware metamorphic relations. Proceedings of the VLDB Endowment 17, 4 (2023), 836–848.

Related documents

• Decoupling Error Attribution in Cloud-Native Graph-RAG: A Data Integrity Diagnostic Framework#1071126
• Evaluating Shrinking (Experience Report)#1199939
• Automation of Database Generation, Statistical Analysis, and Supervised Training of Graph Neural Networks : Application to the Spectroscopy of Large CH Clusters of Astrophysical Interest#364073
• Fast and Theoretically-Efficient Batch-Parallel Link-Cut Trees, Euler Tour Trees, and Treaps#1084670
• How Can We Shrink the Family of Test Databases? Query Containment with Nulls and Comparisons#1110593