{"id":"531af866-f4c4-479a-807d-d068e4d827ff","arxiv_id":"2412.10287","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"LARPQ evaluates two-way regular path queries by expressing the simultaneous traversal of graph and query automaton as Boolean linear algebra, with a correctness proof and a mixed but often favorable performance evaluation.","lead":"The paper presents a new breadth-first-search algorithm, called LARPQ, that evaluates single-source regular path queries on labeled graphs using only sparse Boolean matrix operations. It reports large average speedups over several graph databases on real-world knowledge graphs, while also documenting query classes where the approach is slower than competitors.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1 is false as stated: Algorithm 1 never copies the initial M_0 into P, so zero-length accepting paths are omitted; the proof's P_n = ⋃_{1≤m≤n} M_m excludes length-0 paths. A one-line initialization fixes it, but the paper must state and prove the corrected version.","rationale":"The reader's verdict is CONDITIONAL, and I agree with that disposition. My focus differs from the reader's 'weakest_assumption' field: I take the empty-word/initialization gap in Theorem 4.1 and Appendix A as the load-bearing concern because it directly falsifies the stated correctness theorem, whereas the threshold issue affects only the strength of the empirical speedup claims. The paper's own Definitions 2.2 and 2.6 include zero-length paths, so this is an internal inconsistency, not a semantic disagreement. The fix is straightforward, and the hybrid implementation may already avoid the bug, but the pseudocode and proof must be corrected: P must be initialized with M_0, and the proof's P_n should start at 0. The hand-tuned threshold and the unit/timeout inconsistencies in the tables are additional weaknesses that should be addressed in revision, but they are secondary to the correctness gap. Hence I would keep the reader's CONDITIONAL verdict unchanged.","tokens_in":17857,"tokens_out":10985,"duration_ms":650226,"concrete_test":"Instantiate Algorithm 1 exactly as written with G = (V={1}, E=∅) and the 2-NFA for the regular language a* whose single state is both start and final. Since ε is accepted, Definition 2.6 requires vertex 1 to be in the answer; the pseudocode returns F⊗P = 0, demonstrating the theorem fails. Re-run after initializing P to M (or adding M to P before the loop) and verify that the corrected invariant P_n = ⋃_{0≤m≤n} M_m restores the answer.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing defect is in the correctness theorem, not in the benchmark methodology. Algorithm 1 (lines 3–8) initializes P to the zero matrix, initializes M to the singleton start relation, and then repeatedly does P ← P ⊕ M inside the loop. Consequently P accumulates only M_n for n ≥ 1; the Appendix A proof uses exactly this convention, defining P_n = ⋃_{1≤m≤n} M_m. But Definition 2.2 explicitly admits zero-length paths, and Definition 2.6 counts v_s as an answer whenever ε ∈ R. If the 2-NFA has a final start state (e.g., an NFA for a* with Q_S = Q_F = {q0}, no transitions), then for the empty graph the right-hand side of Theorem 4.1 holds for (q0, v_s) while the returned vector F⊗P is empty. The theorem is therefore false as stated, and the proof's invariant cannot establish it because P never contains M_0. The repair is local: initialize P to the same relation as M (or add M to P before the loop) and change the inductive definition to P_n = ⋃_{0≤m≤n} M_m. The paper also should clarify whether single-source reachability is meant to include zero-length paths; if it is not, Definitions 2.2 and 2.6 must be amended. This is a genuine correctness gap in the central claim, but it is fixable, so it warrants a conditional verdict rather than rejection.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes LARPQ, a BFS-style algorithm for single-source 2-RPQs expressed with Boolean sparse matrix operations, and implements it in SuiteSparse:GraphBLAS/LAGraph. The algorithm simultaneously traverses the data graph and a 2-NFA for the regular language, maintaining the relation of reachable (automaton state, graph vertex) pairs and masking out already seen pairs to ensure termination. The authors prove correctness in Appendix A, describe an accumulated-matrix variant, and benchmark against RPQ-matrix, an RPQ-matrix reimplementation on GraphBLAS, MillenniumDB, FalkorDB, and Blazegraph on Wikidata, Yago-2S, and synthetic RPQBench workloads, reporting large average speedups on the Wikidata query set as well as cases where baselines are faster.","tokens_in":18097,"tokens_out":10560,"duration_ms":96436,"significance":"If the correctness gap identified below is repaired, the paper makes a useful contribution. It gives a clean linear-algebra formulation whose invariant proof is mostly elementary, and it ships an open implementation plus benchmark scripts, which is valuable for reproducibility. The comparison is unusually broad: two linear algebra solutions and three graph databases, on real and synthetic data. The main empirical claims are weakened, however, by a hand-tuned switch threshold with no sensitivity analysis and by the absence of a correctness statement for the second algorithm variant that is part of the measured implementation. The algorithmic idea is not conceptually radical, but the careful evaluation makes the paper of interest to the RPQ and graph-querying community.","major_comments":[{"comment":"Theorem 4.1 (and its duplicate, Theorem A.1) is false as stated because Algorithm 1 never puts the initial relation M_0 into P. Line 3 initializes P to the zero matrix, line 4 initializes M to the start relation, and the loop body on lines 7-8 updates M before accumulating P, so after n iterations P contains only M_1,...,M_n. Appendix A uses exactly this convention: it defines P_n = union_{1<=m<=n} M_m and P = union_{m in N} M_m, so the proof establishes a statement that excludes length-0 paths. Since Definitions 2.2 and 2.6 explicitly admit zero-length paths, a query NFA with a final start state (e.g., an NFA for a* with no transitions) yields (q_F, v_s) in the answer set of Definition 2.6 while Algorithm 1 returns F tensor P = 0. The repair is local: initialize P to the same relation as M, or add M to P before the loop, and change the induction to P_n = union_{0<=m<=n} M_m; the termination argument should be adjusted accordingly. The paper must also state whether zero-length paths are intended to be answers and, if not, amend Definitions 2.2 and 2.6.","section":"Section 4 (Algorithm 1); Appendix A"},{"comment":"The reported performance comparison depends on a single hand-tuned switch threshold of 100 nonzero entries. The paper states that 'for the studied datasets the most suitable value is 100', but it gives no sensitivity analysis for this constant and no argument that the value transfers from the Wikidata and Yago-2S workloads to the synthetic RPQBench graph. Because the advertised speedups (6.8x, 11.3x, 18.9x, 16.8x in the abstract, and the per-query times in Tables 1-3) are produced by the switched implementation, the empirical claims are not yet robust. I request a sensitivity study over a range of thresholds on at least the Wikidata and RPQBench workloads, or evidence that the threshold choice is not material.","section":"Section 5.1, Tables 1-3"},{"comment":"Algorithm 2 is used by the implementation after the switch threshold is reached, but no correctness theorem is given for it. The proof in Appendix A covers only Algorithm 1, and the equivalence between the accumulated-matrix and traversal-matrix formulations is asserted informally. Since the reported timings come from an implementation that may execute Algorithm 2 for much of the traversal, the paper should supply a proof or precise invariant for Algorithm 2, or state explicitly that Algorithm 2 is a reformulation whose correctness follows by the same induction with P in place of M.","section":"Section 5.1 (Algorithm 2); Appendix A"}],"minor_comments":[{"comment":"The Yago-2S entry in Section 5.2 gives exactly the same statistics as Wikidata (610 million edges, 91 million vertices, 1400 distinct labels), which is contradicted by the 0.5 GB memory footprint reported for Yago-2S in Table 2 and by the known scale of the dataset. This looks like a copy-paste error and should be corrected.","section":"Section 5.2"},{"comment":"The columns labeled 'Mean speedup' and 'Median speedup' contain values that are the reciprocals of the speedups advertised in the abstract (for example, LARPQ/RPQ-matrix = 0.15 corresponds to the claimed 6.8x speedup of LARPQ over RPQ-matrix). The caption should define the metric explicitly, and the table values should be made consistent with the text.","section":"Tables 1 and 2"},{"comment":"In the proof of the inductive step, the path pi'_N is described as going 'from q_F in Q_F to q''; this should presumably be from a starting state q_s in Q_S, and the text should be corrected for consistency with the invariant.","section":"Appendix A"},{"comment":"The termination argument states that P_{|Q||V|-1} has at least |Q||V| elements after |Q||V|-1 non-empty steps, but each non-empty step adds at least one new element, so the correct conclusion is that the loop may require |Q||V|+1 iterations before M vanishes. Finite termination is unaffected, but the bound should be corrected.","section":"Appendix A"},{"comment":"The sentence introducing Algorithm 2 refers to 'appendix .' without a section number, and a displayed formula fragment precedes the algorithm. This is a formatting/completeness issue that should be cleaned up.","section":"Section 4 (Algorithm 2 introduction)"}],"recommendation":"major_revision","confidential_remarks":"The empirical section is the main selling point, and two features deserve editorial scrutiny: the RPQ-matrix (GrB) baseline was implemented by the same authors, and the switch threshold is hand-tuned for the studied datasets. I do not see evidence of misconduct, but the paper would be substantially strengthened if the provenance of that baseline were disclosed more prominently and if the requested threshold sensitivity analysis were performed. The zero-length correctness gap is real but the proposed fix is local, so the paper is within scope of a major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the core mechanism is sound and the paper is worth engaging, but the central correctness theorem is slightly false as written because Algorithm 1 never puts the initial relation into P. That is a one-line fix, not a deep problem, but it needs to be stated and proven correctly.\n\nWhat is new: a BFS over the product of the graph and a 2-NFA, expressed with Boolean sparse matrices, using a mask to avoid revisits, plus a single-destination variant by reversing the automaton. The BFS-to-linear-algebra translation is clean, and the LAGraph implementation plus benchmark scripts are public. The comparison is genuinely broad: Wikidata (the MillenniumDB challenge queries), Yago-2S, and synthetic RPQBench, with several baselines including the original RPQ-matrix and a GraphBLAS reimplementation. The correctness proof is self-contained and mostly clear.\n\nThe soft spots: first, Theorem 4.1 / A.1 as stated includes only M_m for m >= 1 in P, so the start vertex is never added when the language contains the empty word. Definitions 2.2 and 2.6 explicitly admit zero-length paths, so the theorem is false for e.g. a* on an empty graph. Initialize P with M_0 (or add it before the loop) and the proof goes through with P_n = union_{0 <= m <= n} M_m. Worth checking whether the implementation already does this; the hybrid description in Section 5.1 suggests it might.\n\nSecond, the performance claims are real but have caveats. The switch threshold of 100 nonzeros is hand-tuned with no sensitivity analysis, so the order-of-magnitude speedups on hard queries are not yet shown to be robust. One baseline, RPQ-matrix (GrB), was implemented by the authors; that is a conflict, though they also compare against the original RPQ-matrix and two databases, so it is not fatal. Table units are sloppy (ms vs seconds, totals inconsistent with timeouts), and there are no error bars. None of this sinks the paper, but it should be cleaned up before publication.\n\nVerdict: this deserves a serious referee. The algorithm is a useful addition to the linear-algebra RPQ toolkit, the experiments are substantial, and the correctness gap is both real and easily patched. I would send it to review with a request to fix the epsilon-path handling, report sensitivity on the threshold, and tidy the tables.","headline":"Solid, useful paper on linear-algebra BFS for 2-RPQs, with a fixable correctness gap (empty-word paths) and some benchmark caveats; worth refereeing after those are addressed.","tokens_in":18715,"tokens_out":2519,"would_cite":true,"duration_ms":21748,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that single-source two-way regular path queries can be evaluated by a frontier-based BFS over boolean matrices, proves the algorithm correct, and reports large average speedups over four graph systems on real-world…","keywords":["two-way regular path queries","regular path queries","sparse linear algebra","GraphBLAS","breadth-first search","knowledge graphs","LAGraph","RPQ evaluation"],"falsifier":"Run the identical Wikidata and RPQBench workloads while varying the switch threshold across orders of magnitude (for example 1, 10, 1,000, and 10,000 non-zero entries) and compare the average and median speedups; if the 6.8x–18.9x edge shrinks or reverses at thresholds far from 100, the empirical advantage is an artifact of the tuning constant rather than of the traversal structure itself.","tokens_in":17572,"feed_emoji":"🧮","tokens_out":9568,"duration_ms":81218,"temperature":0.7,"pith_summary":"Two-way regular path queries (2-RPQs) ask for all vertices reachable from a given vertex by a path whose edge-label word belongs to a regular language, and they have become part of the GQL standard yet remain slow on real-world graphs. This paper claims that a BFS-style traversal expressed entirely in boolean sparse matrix operations evaluates single-source 2-RPQs accurately and quickly: at each step a frontier matrix of (automaton state, graph vertex) pairs is advanced by composing the query automaton's transposed Boolean decomposition with the graph's adjacency matrices, and the accumulated matrix masks out already-visited pairs. The authors prove by induction that the final matrix contains exactly the answer set, and they report average speedups of 6.8x over the RPQ-matrix algorithm, 11.3x over MillenniumDB, 18.9x over FalkorDB, and 16.8x over Blazegraph on the Wikidata query set. If true, this gives graph database engines a way to accelerate a standard query class by reusing mature parallel sparse linear algebra kernels rather than specialized indexing.","feed_headline":"Matrix-BFS algorithm beats graph databases on 2-way path queries","feed_subtitle":"Boolean sparse-matrix traversal answers Wikidata path queries faster than four graph systems, often within the one-minute limit.","key_machinery":"The load-bearing object is Algorithm 1's update rule $M \\leftarrow \\bigoplus_{a\\in\\Sigma^{\\leftrightarrow}\\cap L^{\\leftrightarrow}} ((N_a)^T \\otimes M \\otimes G_a)\\langle \\neg P\\rangle$. Here $N_a$ and $G_a$ are the Boolean decompositions of the 2-NFA and the graph adjacency matrices by label, $\\otimes$ is boolean matrix multiplication (relation composition), $\\oplus$ is logical-or (union), and $\\langle \\neg P\\rangle$ masks away pairs already accumulated, so each pair enters the frontier at most once. The frontier matrix $M$ holds the BFS layer of simultaneously reachable automaton states and graph vertices, $P$ accumulates all layers, and the final answer is the vector $F\\otimes P$ for the final states $F$. A companion formulation (Algorithm 2) drops the separate traversal matrix $M$ and updates $P$ directly; the implementation switches between the two when the intermediate matrix reaches roughly 100 non-zero entries, a constant determined empirically for the studied datasets.","core_discovery":"The central result is Theorem 4.1: the algorithm represented in Algorithm 1 computes a matrix $P$ such that $(q,v)\\in P$ if and only if there is a 2-path $\\pi_G$ in $G$ from $v_s$ to $v$ and a path $\\pi_N$ in the 2-NFA $N$ from some start state to $q$ with $\\omega^{\\leftrightarrow}_G(\\pi_G)\\cap \\omega_N(\\pi_N)\\neq \\emptyset$; consequently $P_F=F\\otimes P$ gives exactly the single-source 2-RPQ answer set. The proof is a straightforward induction on path length, with the invariant that after $n$ steps the frontier relation $M_n$ contains exactly those pairs reachable at depth $n$ whose label sets intersect and that have not appeared in earlier depths, and the loop is guaranteed to terminate in at most $|Q|\\cdot|V|$ steps. The same construction solves single-destination queries by reversing the automaton and transposing the Boolean matrices. The authors further claim that this BFS-based formulation is not only correct but also competitive: on Wikidata it achieves the best mean query time for simple queries and remains within the one-minute limit on complex queries where competitors time out.","pith_inferences":["If the threshold constant is truly dataset- and query-dependent, then the practical wins of LARPQ over RPQ-matrix are not solely structural; the same algorithm with a different threshold might lose on graphs with different density or label skew, and a self-tuning threshold would be a direct testable extension.","The paper's own results show RPQ-matrix wins on queries with rare labels and long concatenations, so a hybrid that routes label-rare query fragments to an evaluation-order optimizer and label-dense fragments to the BFS loop is a natural next step.","The masking step $\\langle\\neg P\\rangle$ is where cycle handling lives; replacing it with a counting semiring would yield path counts per vertex, while keeping the same update rule, which is a concrete extension the authors only gesture at in the conclusion.","The threshold switch also indicates that on GPU or distributed targets (where launching many distinct kernels is costly) the accumulated-matrix variant may dominate for a wider range of queries, so porting the two-algorithm pair to such backends would test whether the 100-entry crossover is an artifact of CPU sparse-matrix kernels."],"forward_implications":["Single-source 2-RPQs over graphs with hundreds of millions of edges can be answered in memory within one minute on workloads where three of the four compared graph databases time out.","Because the algorithm is expressed with boolean matrix operations, any fast parallel sparse linear algebra kernel can serve as the execution engine, avoiding per-database query-plan optimization.","The identical traversal solves single-destination 2-RPQs by reversing the 2-NFA and transposing the Boolean decompositions, effectively doubling the query class covered by one implementation.","The frontier-plus-accumulated-matrix structure separates the BFS layer from the visited set, which is exactly the shape needed for semiring-based variants that count paths or compute shortest distances without changing the traversal order.","The two-algorithm switch (frontier-based vs. accumulated-matrix-based) gives implementations a cheap adaptive knob that can be tuned per dataset or per query shape."],"supporting_citations":[{"why":"Defines the RPQ-matrix linear-algebra algorithm that serves as the primary comparison baseline.","marker":"[4]"},{"why":"SuiteSparse:GraphBLAS, the parallel sparse linear algebra library used for the implementation.","marker":"[16]"},{"why":"MillenniumDB path query challenge that supplies the Wikidata snapshot and the 660-query log.","marker":"[19]"},{"why":"LAGraph infrastructure into which the proposed algorithm is integrated.","marker":"[32]"},{"why":"RPQBench synthetic generator providing the controlled query-kind dataset.","marker":"[36]"},{"why":"MillenniumDB, the graph database competitor whose state-of-the-art RPQ performance is beaten in the benchmarks.","marker":"[35]"},{"why":"FalkorDB, the GraphBLAS-based graph database competitor in the evaluation.","marker":"[11]"}],"fun_headline_variants":["Matrix BFS speeds up two-way regular path queries","BFS with matrices beats graph databases on path queries","Linear algebra accelerates single-source regular path queries","Two-way path queries accelerated via sparse matrices","Regular path queries get a matrix boost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reported speedups depend on a single hand-tuned switch threshold of about 100 non-zero entries in the intermediate matrix, chosen for the studied datasets with no sensitivity analysis, so the benchmark results assume this one constant transfers to the workloads tested.","fun_headline_variants_meta":{"raw":{"variants":["Matrix BFS speeds up two-way regular path queries","BFS with matrices beats graph databases on path queries","Linear algebra accelerates single-source regular path queries","Two-way path queries accelerated via sparse matrices","Regular path queries get a matrix boost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000569,"raw_usage":{"total_tokens":2704,"prompt_tokens":964,"completion_tokens":1740,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":1671}},"tokens_in":580,"tokens_out":1740,"duration_ms":13264,"temperature":1.0,"reasoning_tokens":1671,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:01:16.594545+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the identical Wikidata and RPQBench workloads while varying the switch threshold across orders of magnitude (for example 1, 10, 1,000, and 10,000 non-zero entries) and compare the average and median speedups; if the 6.8x–18.9x edge shrinks or reverses at thresholds far from 100, the empirical advantage is an artifact of the tuning constant rather than of the traversal structure itself.","supporting_citations":[{"cited_title":"LAGraph: Linear Algebra, Network Analysis Libraries, and the Study of Graph Algorithms","cited_arxiv_id":"2104.01661","evidence_quote":"LAGraph infrastructure into which the proposed algorithm is integrated."},{"cited_title":"InString Processing and Information Retrieval: 30th International Symposium, SPIRE 2023, Pisa, Italy, September 26–28, 2023, Proceedings(Pisa, Italy)","cited_arxiv_id":null,"evidence_quote":"Defines the RPQ-matrix linear-algebra algorithm that serves as the primary comparison baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"SuiteSparse:GraphBLAS, the parallel sparse linear algebra library used for the implementation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"MillenniumDB path query challenge that supplies the Wikidata snapshot and the 660-query log."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"RPQBench synthetic generator providing the controlled query-kind dataset."},{"cited_title":"MillenniumDB: A Persistent, Open-Source, Graph Database","cited_arxiv_id":"2111.01540","evidence_quote":"MillenniumDB, the graph database competitor whose state-of-the-art RPQ performance is beaten in the benchmarks."}],"review_version":1}