{"id":"de66f1c4-e11c-4911-8332-32857fb29594","arxiv_id":"2501.09736","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A bit-matrix indexed, edge-ordered algorithm for exact subgraph matching on labeled multigraphs is described and benchmarked against SuMGra, Neo4J, and Memgraph.","lead":"MultiGraphMatch is a new algorithm for finding all occurrences of a small query graph inside a large graph when both allow multiple labeled edges between the same pair of nodes. The paper reports speedups over several existing graph database tools, which matters for querying biological, social, and financial networks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1/2 never checks that a newly assigned query node's target node is not already in the image of f, so non-injective node mappings (Definition 3.2 violation) can be emitted as valid matches.","rationale":"The reader's weakest_assumption identifies precisely the load-bearing failure: the matching procedure never enforces injectivity of the node mapping f, despite Definition 3.2 requiring it. I have verified this from the pseudocode and by constructing a concrete counterexample in which two query nodes are mapped to the same target node while the edge mapping remains injective, so the edge-injectivity check in Algorithm 1 line 11 cannot prevent the invalid occurrence. This is not a performance or heuristic concern; it breaks the central claim of exact enumeration, because the algorithm can output matches that are not SMM occurrences. The paper provides no formal correctness proof and no machine-checked verification, and the supplementary table even shows SuMGra beating MultiGraphMatch on PANAMA medians, but the decisive issue remains soundness. The bit-matrix and edge-ordering ideas are separable and might be salvageable in a corrected algorithm, but as written the central algorithmic promise is broken. I therefore agree with the reader's REJECT verdict and recommend no change.","tokens_in":34828,"tokens_out":6022,"duration_ms":60019,"concrete_test":"Run the released implementation (github.com/Anto188bas/MultiGraphMatch) on the following instance: target T with nodes t1,t2 and two parallel directed edges of type R from t1 to t2 (or bidirected, depending on input format), all nodes labeled L; query Q with nodes q1,q2,q3, edges (q1,q2) and (q1,q3) both type R, all nodes labeled L. Enumerate the output occurrences and check whether any occurrence maps q2 and q3 to the same target node (i.e., f(q2)=f(q3)). Independently brute-force all injective SMM matches of Q in T per Definition 3.2 and compare the sets; any non-injective occurrence in MultiGraphMatch's output confirms the concern. As an analytical cross-check, trace Algorithm 2 on this instance with ordering [(q1,q2),(q1,q3)] and show that line 13 admits eT=(t1,t2) for the second edge when f(q2)=t2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The SMM definition requires an injective node mapping f (Definition 3.2). For exact enumeration, every returned occurrence must satisfy this. In Algorithm 2, when one endpoint of the current query edge is already mapped (lines 11-16 and 18-22), the unmapped endpoint q' (or q) is assigned the target node t' (or t) from a candidate edge eT=(f(q),t') without checking whether t' is already in image(f). The only identity check in Algorithm 1 is line 11, which checks that the target edge eT has not already been used by the edge mapping g; it says nothing about the target node. Concretely, let Q have nodes q1,q2,q3 and edges (q1,q2),(q1,q3), all with the same label and edge type R, and let T have nodes t1,t2 with two parallel R-edges e_a,e_b between them. Processing (q1,q2) first can set f(q1)=t1, f(q2)=t2, g(e1)=e_a. Then for (q1,q3), Dom(q1,q3) contains (t1,t2) and e_b is a valid candidate; Algorithm 2 line 13 is satisfied and line 11 in Algorithm 1 passes because g(e1)!=e_b. The algorithm then sets f(q3)=t2. The resulting match is accepted although f is not injective and violates Definition 3.2. Thus the claimed 'list of all occurrences' is not guaranteed to contain only SMM occurrences; the central exactness claim fails. Symmetry breaking conditions do not repair this gap, since they only order redundant automorphic matches, not detect colliding images.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes MultiGraphMatch, an in-memory algorithm for exact sub-multigraph matching on labeled, attributed multigraphs. The algorithm introduces a bit-matrix index over target node-pairs, compatibility domains built from bit signatures and type-dependent degree inequalities, a query-edge processing order based on domain cardinalities and local density, and symmetry-breaking conditions adapted from simple-graph matching. The authors report experiments comparing MultiGraphMatch with SuMGra, Neo4J, and Memgraph on synthetic and real networks, plus scalability tests on LDBC graphs, and claim speedups of 2 to 10 times over the compared systems.","tokens_in":35134,"tokens_out":6822,"duration_ms":73255,"significance":"Exact subgraph matching in multigraphs is a legitimate and comparatively under-studied problem, so a correct algorithm with a scalable index and good experimental methodology would be a useful contribution. The paper's strengths are its explicit problem definition, a concrete indexing scheme, an ablation study that isolates the effects of the bit matrix and the ordering heuristic, and benchmarks on several synthetic and real networks with code and datasets made available. However, the central correctness claim is not backed by a proof, and the pseudocode as written admits non-injective node mappings, so the reported experiments currently measure an algorithm that does not solve the SMM problem as defined. The issues appear local and repairable, but the paper cannot be accepted in its present form.","major_comments":[{"comment":"The matching procedure does not enforce injectivity of the node mapping f, although Definition 3.2 requires f to be injective. In Algorithm 1, lines 12-16 assign f(q):=t and f(q'):=t' without checking whether t or t' is already in the image of f; the only global check (line 11) concerns the edge mapping g. In Algorithm 2, when one endpoint is already mapped (lines 11-16 and 18-22), the unmapped endpoint is assigned the target endpoint of a candidate edge e_T=(f(q),t') or e_T=(t,f(q')) without verifying that this target endpoint is not already mapped to a different query node. Concretely, take query nodes q1 (label X), q2 (label A), q3 (label B) with directed R-edges q1->q2 and q1->q3, and target nodes t1 (label X), t2 (labels A,B) with two parallel R-edges t1->t2. Processing q1->q2 first sets f(q1)=t1, f(q2)=t2. For q1->q3, Algorithm 2 line 13 accepts e_T=(t1,t2) because A_Q(q3)={B} is contained in A_T(t2), and no symmetry-breaking condition relates q2 and q3 since they have different labels. The algorithm then sets f(q3)=t2, producing a match with f(q2)=f(q3), which violates Definition 3.2 and is returned as an occurrence at Algorithm 1 line 28. The fix is to maintain the set of used target nodes and reject any candidate whose not-yet-mapped endpoint is already in the image of f; a correctness proof should accompany this fix.","section":"§5.5, Algorithms 1 and 2"},{"comment":"The paper provides no correctness or completeness proof for the matching procedure. The central claim — that the algorithm returns the list of all occurrences satisfying the five conditions of Definition 3.2 — requires a formal argument: an invariant showing that every partial mapping (f,g) built by the search respects Definition 3.2, an induction over the edge ordering O showing that every complete valid match is eventually reached, and a statement that backtracking restores precisely the information needed to continue the enumeration. Without such a theorem, even after the injectivity bug is fixed, the exact-enumeration claim remains unsupported. Adding such a proof is necessary for the algorithmic contribution to be verifiable.","section":"§5.5 and §5.7"},{"comment":"The experimental comparison is affected by the injectivity bug, because MultiGraphMatch can emit non-injective matches that SuMGra, Neo4J, and Memgraph are not asked to produce. The reported running times therefore do not compare the same task, and the speedup claim in Section 7 ('generally faster by a factor ranging from 2 to 10') cannot be taken at face value. The benchmarks should be rerun with the corrected algorithm, and the performance tables and significance statements should be updated accordingly.","section":"§6 and §7"}],"minor_comments":[{"comment":"The text says node and edge properties are not used to build compatibility domains, yet Algorithm 2 checks node and edge properties when constructing candidate lists; please clarify the distinction between domain construction and candidate filtering.","section":"§5.3"},{"comment":"In the case where both endpoints are already mapped (lines 5-10), the candidate set is not explicitly restricted to the compatibility domain Dom; this is harmless because the endpoints are fixed, but the pseudocode and prose could state that Dom is no longer needed in that branch.","section":"§5.5, Algorithm 2"},{"comment":"The caption says 'for each synthetic network' when reporting results on the real networks imdb and panama; it should read 'for each target network.'","section":"Table 3 caption"},{"comment":"The sentence 'the application of the breaking condition q2≺q3 results leads to include solution S1' contains a typo ('results leads'); it should read 'results in including solution S1.'","section":"§5.2"},{"comment":"The abstract's 'factor ranging from 2 to 10' is stronger than the experimental tables suggest, especially for real networks where the margins are smaller and sometimes not significant; please qualify the speedup claim accordingly.","section":"Abstract and §7"}],"recommendation":"major_revision","confidential_remarks":"The reader's stress-test concern is valid and is reproduced by a concrete counterexample in the pseudocode. I recommend major revision rather than rejection because the injectivity problem is local and fixable: adding a used-target-node check plus a correctness proof would address the core issue. The authors should also rerun the experiments after the fix, since the current speed comparison is not measuring the same exact-enumeration task."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this paper brings two things worth keeping—the bit-matrix encoding of endpoint labels plus edge types/directions, and the Sc edge-ordering heuristic—but the matching loop as written does not enforce injectivity of the node mapping, so it can emit invalid matches. The stress-test is right.\n\nDefinition 3.2 requires an injective f. Algorithm 2, lines 11–16, when one endpoint is already mapped, adds eT=(f(q),t') with no check that t' is free. Algorithm 1 only checks edge uniqueness at line 11. Concrete violation: query nodes q1–q3 with edges (q1,q2),(q1,q3) of same type, target nodes t1,t2 with two parallel edges e_a,e_b. Map q1→t1, q2→t2 on e_a, then (q1,q3) can map to e_b, setting f(q3)=t2. That's non-injective, and the algorithm records it as an occurrence. This is exactly the kind of bug that breaks exact enumeration.\n\nWhat is good: the bit-matrix indexing is a neat, compact filter for compatibility domains; the ordering score combining domain size and local density makes sense and the ablation shows it helps; adapting symmetry breaking to multigraphs is a reasonable extension. The experiments are extensive, on synthetic and real graphs, and the code is available. The paper is clearly written.\n\nThe soft spots, in proportion: the injectivity gap is fatal to the stated contribution. Fixing it may be easy—check image(f) or use a boolean array—but until then the output set is not trustworthy. Second, the performance claims overreach. The abstract says 'comparable or better performance in all queries' and the conclusion says 'generally faster by factor 2 to 10', but supplementary Table S1 shows SuMGra significantly faster on PowerLaw(2,10) and PANAMA (median difference negative, p<0.0001). The main text even states MGM is significantly better on PANAMA, which contradicts its own table. That's a reporting issue that needs correction.\n\nWho this is for: researchers working on multigraph querying or subgraph isomorphism who care about the indexing ideas. The current version is not citable as a correct algorithm, but it's a legitimate starting point. I think a serious editor should send it to peer review: the flaw is concrete, fixable, and a good referee could force the authors to add the missing check and a correctness argument. Desk rejection would waste a real idea. My recommendation: accept for review, expect major revision.","headline":"Novel multigraph matching ideas undermined by a missing injectivity check that can emit invalid matches, but the core is salvageable and deserves a serious referee.","tokens_in":35710,"tokens_out":3134,"would_cite":false,"duration_ms":32352,"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":"MultiGraphMatch claims to enumerate every occurrence of a query multigraph in a larger target multigraph, while running 2 to 10 times faster than compared systems on the tested graphs.","keywords":["subgraph matching","multigraph","bit matrix","compatibility domain","symmetry breaking","edge ordering","graph databases"],"falsifier":"Build a target with two parallel edges of the same type from $t_1$ to $t_2$, and a query with two distinct edges $q_1q_2$ and $q_1q_3$ of that type. If MultiGraphMatch returns an occurrence mapping both $q_2$ and $q_3$ to $t_2$ (with $q_1$ mapped to $t_1$), then the node mapping is not injective and the output violates Definition 3.2, so the claimed exact enumeration fails.","tokens_in":34580,"feed_emoji":"🕸️","tokens_out":12692,"duration_ms":125086,"temperature":0.7,"pith_summary":"Sub-multigraph matching is the problem of finding every occurrence of a small labeled, attributed multigraph (the query) inside a larger one (the target), where several edges of different types may connect the same two nodes. Earlier approaches either ignored such parallel edges or had to enumerate node mappings first and post-process them to pair query edges with target edges, a step that can become exponential in the number of target edges. The paper introduces MultiGraphMatch, which carries node and edge mappings together through the search and uses two mechanisms to keep the search small: a bit matrix that encodes, for every connected node pair, the endpoint labels and the presence of each edge type in each direction, and an ordering of query edges that prefers dense regions with few candidate target edges. The paper reports that MultiGraphMatch finds all occurrences satisfying its five matching conditions and is generally 2 to 10 times faster than the compared state-of-the-art systems on synthetic and real networks.","feed_headline":"Multigraph matching runs 2-10x faster with bit-matrix indexing","feed_subtitle":"A new algorithm matches edges during search, avoiding the costly post-processing step required by simple-graph matchers.","key_machinery":"The load-bearing structure is the bit matrix: one row per connected pair of target nodes, whose signature is the concatenation of one-hot bit strings for the first endpoint's labels, the types of incoming edges, the types of outgoing edges, and the second endpoint's labels. A target row can serve a query pair when, after possibly reversing the query pair, the signature containment test $\\operatorname{Sign}(T) \\wedge \\operatorname{Sign}(Q) = \\operatorname{Sign}(T)$ holds, and after comparing type-dependent degrees of the endpoints so that edge multiplicities are respected. The second mechanism is the query-edge ordering score: for each pair of connected query nodes not yet in the ordering, the score is $(\\mathit{CF}, Sc)$, where $\\mathit{CF}$ counts already-ordered endpoints and $Sc$ is proportional to total degree times neighbor Jaccard similarity divided by the compatibility-domain size (or just the inverse domain size when both endpoints are already placed). Lexicographic comparison of these pairs makes the search extend from already-matched dense regions with small candidate sets, which is what cuts the number of backtracks.","core_discovery":"The paper's central claim is that sub-multigraph matching does not need a two-phase node-then-edge approach. MultiGraphMatch first builds compatibility domains: for each directed pair of connected query nodes, the target node pairs whose bit signatures contain the query's bit signature, subject to type-dependent in- and out-degree inequalities that enforce edge multiplicities. It then processes query edges in an order chosen by a score that rises with the number of already-matched endpoints, total degree, and neighborhood Jaccard similarity, and falls with the size of the compatibility domain. The search maintains a partial node mapping and a partial edge mapping simultaneously, adds an occurrence whenever the last query edge in the order is matched, and backtracks otherwise. The paper asserts that this procedure returns exactly the set of occurrences defined by the five conditions of Definition 3.2 (injective node and edge mappings consistent with edge endpoints, node labels, edge types, and property sets), and that experiments show it to be generally 2 to 10 times faster than the compared systems.","pith_inferences":["If the injectivity gap in the pseudocode is repaired, an immediate test is whether the same bit-matrix filtering can be extended to count edge multiplicities directly in the signature, replacing the separate type-dependent degree checks.","The reported speedup over general-purpose graph databases may partly reflect the advantage of a purpose-built in-memory index; porting the same data structures into an incremental database engine would separate algorithmic gains from system overhead.","A natural stress test is to run the algorithm on targets with many parallel edges between high-degree node pairs, since the bit matrix records only presence or absence of edge types and all multiplicity information is delegated to the degree checks."],"forward_implications":["Multigraph queries expressed with logical conditions on labels, types, and properties can be answered without a post-processing phase for edge mappings.","The ordering heuristic should benefit dense query patterns in particular, because it prioritizes edges whose endpoints are already matched and whose candidate sets are small.","On the scalability benchmarks, running time grows as a power law with network scale (exponents roughly 1 to 1.5) while indexing time grows linearly, so the method remains practical as targets grow.","Ablation tests indicate that both the bit matrix and the ordering contribute separately to the speedup; removing either one degrades performance."],"supporting_citations":[{"why":"Defines the query language used to express multigraph queries and logical conditions in MultiGraphMatch.","marker":"[17]"},{"why":"Presents the in-memory multigraph matcher used as the main algorithmic baseline in the performance comparison.","marker":"[24]"},{"why":"Provides the canonical labeling algorithm used to compute query automorphisms and orbits for symmetry-breaking conditions.","marker":"[30]"},{"why":"Establishes that processing order strongly affects subgraph matching runtime, the premise for MultiGraphMatch's edge-ordering score.","marker":"[10]"},{"why":"Supplies the generative model used to produce the synthetic target networks for experiments.","marker":"[6]"},{"why":"Defines the social network benchmark used for scalability tests on larger targets.","marker":"[3]"},{"why":"Supplies the benchmark queries used in the scalability experiments.","marker":"[31]"},{"why":"Supports the choice of the representative graph database system used for comparison.","marker":"[33]"},{"why":"Describes the non-parametric tests used to compute p-values and confidence intervals for running-time differences.","marker":"[25]"}],"fun_headline_variants":["Bit-matrix indexing cuts multigraph matching time by 2-10x","Edge-ordering technique accelerates subgraph matching on multigraphs","MultiGraphMatch: faster subgraph queries with multiple edge types"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes that checking that each target edge is still unused and that candidates come from the compatibility domain is enough to keep the node mapping one-to-one, even though the pseudocode never verifies that a newly mapped target node is not already the image of another query node.","fun_headline_variants_meta":{"raw":{"variants":["Bit-matrix indexing cuts multigraph matching time by 2-10x","Edge-ordering technique accelerates subgraph matching on multigraphs","MultiGraphMatch: faster subgraph queries with multiple edge types"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000881,"raw_usage":{"total_tokens":3806,"prompt_tokens":944,"completion_tokens":2862,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":560,"completion_tokens_details":{"reasoning_tokens":2803}},"tokens_in":560,"tokens_out":2862,"duration_ms":23261,"temperature":1.0,"reasoning_tokens":2803,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T19:43:27.707202+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a target with two parallel edges of the same type from $t_1$ to $t_2$, and a query with two distinct edges $q_1q_2$ and $q_1q_3$ of that type. If MultiGraphMatch returns an occurrence mapping both $q_2$ and $q_3$ to $t_2$ (with $q_1$ mapped to $t_1$), then the node mapping is not injective and the output violates Definition 3.2, so the claimed exact enumeration fails.","supporting_citations":[{"cited_title":"Ingalalli, D","cited_arxiv_id":null,"evidence_quote":"Presents the in-memory multigraph matcher used as the main algorithmic baseline in the performance comparison."},{"cited_title":"Monteiro, F","cited_arxiv_id":null,"evidence_quote":"Supports the choice of the representative graph database system used for comparison."},{"cited_title":"Katari, D","cited_arxiv_id":null,"evidence_quote":"Describes the non-parametric tests used to compute p-values and confidence intervals for running-time differences."}],"review_version":1}