{"id":"df3a3b41-af9e-410b-b1aa-56cd8a3ea026","arxiv_id":"2507.14813","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Mayura introduces the MG-Tree, a hierarchical prefix tree over temporal motifs, enabling exact co-mining of multiple motifs with 1.7-2.4x average speedups on GPU/CPU.","lead":"Mayura is a new system that mines several temporal graph motifs at once by sharing the parts of the search that the motif queries have in common. It reports average speedups of 2.4x on CPU and 1.7x on GPU over mining each motif separately, while keeping results exact.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2 computes QN_parent (lines 24-26) but never stores it on the node created at line 35, so any query motif that is a strict prefix of another (e.g., M1 within D1/D2) is disconnected from the MG-Tree; Algorithm 3 then never counts its matches, breaking the claimed exactness.","rationale":"The reader's weakest assumption correctly identifies the MG-Tree partition as load-bearing, and the specific pseudocode defect with QN_parent is the cleanest way to attack that assumption. The paper's abstract and Section 7 explicitly claim exactness, so a construction bug that can drop an entire query motif from the traversal directly undermines the central claim. The concern is internal and concrete: Algorithm 2 computes a value and never uses it, and Algorithm 3's counting is gated on that value being set. The evaluation does not report per-motif counts, only timings and speedups, so a zero count for a prefix motif would not be visible in the presented results. Because the fix appears straightforward (assign QN_parent to the node and attach prefix-motif leaves appropriately) and because the broader co-mining idea and measurements are otherwise plausible, a conditional acceptance rather than rejection is the right posture. I did not find a more load-bearing issue; in particular, the lack of code release and the use of the authors' own Everest baseline are concerns about evidence strength, not about the internal consistency of the core algorithm, whereas the Q_N omission is a direct correctness risk. The secondary root_gid inconsistency reinforces that the pseudocode needs a careful revision pass, but the Q_N issue is the one that changes the match-set claim. If the authors fix the construction, add a short proof of partition completeness, and verify counts against baselines, the exactness claim can be restored; until then, the paper as written should not be accepted as a fully verified exact co-mining system.","tokens_in":26756,"tokens_out":7545,"duration_ms":85793,"concrete_test":"Trace Algorithm 2 on motif group {M1, M4} where M1 is a strict 2-edge prefix of M4, and assert that the tree contains a node on the path root->M4 whose Q_N equals M1. Then run Mayura with enumeration=true on D2/wtt and compare per-motif counts for M1, M4, and M11 against the Mackey/Everest baselines; if M1's count is zero (or any count differs), the exactness claim is falsified. Ideally, also add an assertion in the implementation that every motif in MG is reachable from the root and has exactly one Q_N node.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Mayura's central claim is that MG-Tree-guided co-mining enumerates exactly the same match set as per-motif mining. That claim depends on the partition property stated in Appendix A.1: for every query motif Mi there is exactly one node N with Q_N = Mi, and every such node is reachable from the root. Algorithm 2 does not establish this property. At lines 24-26, when a child_group's prefix length T equals a query motif's edge count, the code computes QN_parent<-M but never assigns it to any node; line 35 unconditionally sets Q_N<-empty for the newly created or reused intermediate node. Since InsertMotif at line 10 creates the query motif M as a separate leaf node that is never attached as a child of that intermediate node, the algorithm can silently omit M from the traversal. This is not a hypothetical corner case: the depth-focused groups D1 and D2 include M1 as a prefix of longer motifs, exactly the situation the 'implicit mining of M1 before M4' description in Section 7 relies on. Algorithm 3 only counts matches when Q_N is non-empty (line 6), so a disconnected leaf contributes zero matches. The paper provides no correctness proof for the partition and no released artifact; the generated-code example in Appendix A.3 only covers the non-prefix group [M3,M4,M5]. There is also a secondary inconsistency: line 5 creates root_gid but line 7 passes a fresh GetNewUniqeGID(), leaving Nroot unused. These are internal inconsistencies in the presented construction, not disagreements with external consensus.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents Mayura, a system for jointly mining multiple temporal motifs by organizing the query motifs into a Motif-Group Tree (MG-Tree). The central claims are that the MG-Tree captures structural and temporal commonalities across motifs, that the co-mining algorithm (Algorithm 3) mines exactly the same match set as independent per-motif mining while doing less work, and that a CPU/GPU runtime with code generation and load-balancing optimizations achieves average speedups of 2.4x on the CPU and 1.7x on the GPU over single-motif baselines. The evaluation covers five real-world temporal graphs and eight multi-motif queries, and the paper includes detailed architectural analysis of instruction counts, warp divergence, occupancy, and memory footprint.","tokens_in":27145,"tokens_out":5530,"duration_ms":64670,"significance":"If the exactness and performance claims hold, Mayura addresses a real gap: exact temporal motif mining has previously been done one motif at a time, while multi-query workloads in fraud detection and network analysis contain overlapping motifs. The MG-Tree abstraction is a plausible and potentially reusable way to share search paths, and the paper's breadth of evaluation (five datasets, eight queries, CPU and GPU backends, sensitivity to δ, and architectural counters) is a strength. The paper also gives concrete optimization ideas, such as predicate-based structural checks and MG-Tree-specific code generation, which would be of value to the community. However, the exactness claim is load-bearing and currently rests on an unproven partition property of Algorithm 2 whose pseudocode appears internally inconsistent; no released artifact or machine-checked correctness argument is provided. Because the claimed speedups are only meaningful if every query motif's matches are actually counted, the correctness gap must be resolved before the results can be accepted.","major_comments":[{"comment":"The construction does not implement the partition property asserted in §A.1. When child_group contains a query motif M with |E(M)| = T together with longer motifs, the variable QN_parent is computed but never assigned to the node created or reused at line 35; line 35 unconditionally sets Q_N ← ∅. Consequently, any counted motif that is a strict prefix of another motif in the same group has its Q_N overwritten or never set, and Algorithm 3 line 6 will never record its matches. This is not an artificial corner case: the depth-focused groups D1 and D2 in Fig. 15 contain M1 as a prefix, and §7 explicitly relies on the \"implicit mining of M1 before M4\" behavior. Since §A.1 asserts that every motif corresponds to exactly one node with Q_N = M_i but no proof is given, the exactness of the co-mining algorithm is not established by the manuscript. Please correct the pseudocode (e.g., set Q_N ← M when |E(M)| = T), and provide a rigorous argument that the traversal in Algorithm 3 visits every node with nonempty Q_N exactly once.","section":"§4.3, Algorithm 2, lines 24-26 and 35"},{"comment":"There is an internal inconsistency at the top of ConstructMGTree. Line 5 obtains root_gid and line 6 initializes Nroot, but line 7 calls CreateTree(1, GetNewUniqeGID(), MG), passing a fresh GID rather than root_gid. The initialized Nroot at gid 0 is therefore never passed to CreateTree and cannot be the root of the returned tree unless additional code not shown attaches it later. Since line 31 reuses p_gid only when the child_group equals motif_group, the effective root of the returned MG-Tree is the node created at gid 1, and a traversal starting from Nroot would see no children. This makes the construction pseudocode impossible to verify as written. Please correct the call to use root_gid, or explicitly describe how the root is finalized.","section":"§4.3, Algorithm 2, lines 5-7"},{"comment":"The heuristic threshold SM = 0.44 for GPU co-mining is selected from the same experiments that are used to report the average GPU speedups. The paper does not describe a holdout validation, a sensitivity analysis around the threshold, or a separate tuning procedure, and the heuristic directly gates whether co-mining is even attempted for low-SM groups such as C1 (SM = 0.36). As a result, the headline 1.7x average GPU speedup conflates the algorithm's intrinsic benefit with the benefit of disabling co-mining on unfavorable inputs. Please report results with and without the heuristic for all queries, or validate the threshold on an independent query/dataset split.","section":"§7, Listing 1 and Fig. 19"},{"comment":"The exactness claim is stated unconditionally in the abstract and conclusion (\"maintaining the exactness required for high-stakes applications\"), but the only supporting statement is the definitional assertion in §A.1 that the MG-Tree contains exactly one node with Q_N = M_i for each motif. No correctness proof for the construction or the co-mining recursion is provided, and no artifact or source code is released to allow independent checking. Given the load-bearing nature of this claim and the discrepancies in the pseudocode, a formal correctness argument (or, failing that, a corrected and executable construction with a randomized differential test against per-motif mining on small graphs) is necessary before the exactness claim can be accepted.","section":"§A.1 and §9"}],"minor_comments":[{"comment":"RollBackEdge(edge_G.u, edge_G.u) should presumably be RollBackEdge(edge_G.u, edge_G.v); the function signature at line 19 takes two endpoint arguments, and the body at line 23 refers to an undefined variable named edge.","section":"§2.2, Algorithm 1, line 18"},{"comment":"The generated-code example checks M3.matches({e1, e2, e3, e4}) in the loop for e3, but e4 is not defined at that point; this appears to be a typo and should be e3 or a comment explaining the intended pseudo-variable.","section":"Appendix A.3, Listing 3"},{"comment":"The sentence beginning \"SThe efficacy of code-generation\" contains a typo and should read \"The efficacy...\".","section":"§7, Figure 20"},{"comment":"The text mentions \"16MB for D2, 20MB for D3,\" but the query set contains D1 and D2, not D3; this should be corrected to a real query name or clarified.","section":"§7, Memory Footprint paragraph"},{"comment":"The abstract reports an average CPU speedup of 2.4x while the conclusion reports 2.5x; please make these consistent.","section":"Abstract vs. Conclusion"}],"recommendation":"major_revision","confidential_remarks":"This is a potentially strong systems paper, but the exactness claim is undermined by the Algorithm 2 issues described in the major comments. The prefix-motif/Q_N omission is the kind of bug that could silently drop an entire motif's matches, so it cannot be treated as a presentation issue. I would like to see a corrected construction, a formal or differentially tested correctness argument, and a de-overfitted treatment of the SM=0.44 heuristic. The fact that Everest is from the same group is not itself a problem, but the paper would benefit from an independent baseline or at least a clear statement of whether the Everest numbers were produced by the authors' own implementation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, the MG-Tree co-mining idea is real: sharing prefix paths across temporal motif queries is a natural and underexploited optimization, and the GPU-specific work (predicated execution, sibling-splitting, multi-offload) is thoughtful. The reported 1.7–2.4x speedups are plausible for this kind of workload. Second, the paper as written does not establish its central exactness claim. Algorithm 2 computes QN_parent at lines 24–26 but never stores it on the node created at line 35; that node's Q_N is unconditionally set to empty. Any query motif that is a strict prefix of another motif in the same non-singleton group never gets attached as a leaf. The D1/D2 groups are exactly that case, and Section 7 says M1 is mined implicitly before M4. As written, M1's matches would never be counted. The appendix's walkthrough only covers the non-prefix group [M3,M4,M5], so it doesn't exercise the bug.\n\nWhat the paper does well: it gives a clear informal argument for why co-mining reduces redundant work, the SM metric is a reasonable way to express motif similarity, and the evaluation covers five real datasets and eight queries with an honest breakdown of speedups. The GPU optimization details are specific and credible.\n\nSoft spots in proportion: the main one is the correctness gap above. It is fixable—store QN_parent on the node, or attach the prefix motif as a child when it terminates—but it is load-bearing because the paper sells exactness as a key advantage over approximation. The SM=0.44 threshold in Listing 1 is fit from the same experiments that report speedups; that is a heuristic, so not fatal, but do not treat it as a predictive result. The GPU baseline is Everest, the authors' own system; that is not a flaw by itself, but a second independent baseline would strengthen the evaluation. No code or artifact is released, which makes the exactness bug harder to dismiss as a typo. There is also a minor typo in RollBackEdge (the argument uses u twice) that should be fixed.\n\nWho this is for: the temporal graph mining and systems community. The paper deserves a serious referee because the idea is meaningful and the evaluation is broad, but a referee should demand a corrected construction and a correctness argument for the partition before accepting. Recommendation: accept for peer review with the expectation of major revision.","headline":"A genuinely useful co-mining idea with a broad evaluation, but the published construction pseudocode has a load-bearing correctness gap that undermines the exactness claim until fixed.","tokens_in":27672,"tokens_out":3262,"would_cite":true,"duration_ms":37111,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Multiple temporal motif queries can be co-mined exactly by sharing common edge prefixes through an MG-Tree, yielding 2.4x average CPU and 1.7x GPU speedups over per-motif mining.","keywords":["temporal motif mining","co-mining","MG-Tree","motif-group tree","exact enumeration","GPU load balancing","multi-query optimization","temporal graphs"],"falsifier":"Take a motif group where one motif is a strict prefix of another, say a two-edge pattern A→B→C and a three-edge pattern A→B→C→D, and mine a tiny graph that certainly contains the two-edge pattern; if the two-edge motif's count is zero while mining it alone finds it, the exactness claim is false, and the construction pseudocode's unassigned parent query reference (lines 24–26 versus line 35) is a plausible source of exactly this failure.","tokens_in":26549,"feed_emoji":"⚡","tokens_out":9106,"duration_ms":107028,"temperature":0.7,"pith_summary":"This paper claims that a batch of temporal-motif queries—small, ordered edge patterns that must occur in sequence within a time window δ—can be mined together exactly instead of one at a time. The key move is to organize the motifs into a Motif-Group Tree (MG-Tree), a tree whose internal nodes are common prefixes of the motifs' chronologically ordered edge sequences, so a single search traverses each shared prefix once and branches where motifs diverge. If correct, this removes redundant re-traversals in workloads such as fraud detection and cybersecurity, where several motif queries run at once and exact enumeration rather than approximation is required. Across five real-world datasets the paper reports average speedups of 2.4x on a 40-core CPU and 1.7x on an NVIDIA A40 GPU over state-of-the-art per-motif baselines, with the same match set and peak gains of 8.8x and 7.6x respectively.","feed_headline":"Mine many temporal motifs at once: 2.4x CPU speedup","feed_subtitle":"Mayura's MG-Tree shares common edge prefixes across queries, keeping matches exact on CPU and GPU.","key_machinery":"The central object is the Motif-Group Tree (MG-Tree), a tree built from the query motifs in which each node stores three things: a common motif С_N (the ordered edge prefix shared by every descendant), a query reference Q_N (the original motif completed at this node, or empty), and child nodes that extend the prefix. This object carries the argument because matching С_N once gives every descendant its partial match, turning several independent searches into one search that branches only where the motifs' edge sequences diverge. Algorithm 2 constructs the tree by grouping motifs according to their edge at each timestamp, reusing a node when the whole group stays together and creating a new internal node only when the group splits; Algorithm 3 then performs the recursive co-mining traversal.","core_discovery":"The central claim is that a group of δ-temporal motifs can be mined exactly in one coordinated search. The MG-Tree organizes the motifs as a hierarchy of common prefixes over chronologically ordered edges; Algorithm 3 traverses each shared prefix once, reusing its matches as partial matches for every descendant motif, and records a match whenever a node's query reference is set. The paper argues this enumerates the same match set as independent per-motif mining while executing less work, and reports average speedups of 2.4x on a 40-core Intel Xeon CPU and 1.7x on an NVIDIA A40 GPU over the individual-mining baselines, with dynamic instruction counts reduced by 1.6–4.5x.","pith_inferences":["The tree construction only shares prefixes under one fixed chronological order of edges; a generalized construction could also share suffixes or reverse-order prefixes and would likely expose co-mining opportunities for motif groups the current similarity metric rates as low-overlap.","The reported GPU cutoff (similarity metric at least 0.44, unless the graph is bipartite) is an empirical threshold; a cost model of prefix-sharing savings versus register pressure and divergence could turn it into a portable decision rule.","For count-only workloads, the MG-Tree provides an implicit family-level pruning: if an internal prefix has zero matches, the entire subtree of motifs is skipped, an effect the paper observes empirically but does not quantify separately as a pruning guarantee."],"forward_implications":["For a motif group with high overlap, co-mining cuts dynamic instructions by 1.6–4.5x, translating directly into wall-clock speedups on both CPU and GPU backends.","Because the match set is identical to independent mining, co-mining can be substituted into exact enumeration workloads without changing downstream results.","The MG-Tree exposes hierarchical parallelism: sibling-splitting and multi-offload let GPU warps explore divergent motifs concurrently, with occupancy loss capped at about 1% and instruction overhead at 6%.","Dataset structure strongly shapes the gains: on bipartite graphs an unmatched intermediate motif prunes all descendants at once, yielding the largest observed speedups (up to 8.8x CPU and 7.6x GPU).","Choosing a smaller time window δ increases the speedup of co-mining over the baseline, because the candidate search space shrinks and load imbalance is less severe."],"supporting_citations":[{"why":"Formalizes δ-temporal motif mining and defines the enumeration and counting problem that Mayura targets for co-mining.","marker":"[34]"},{"why":"Supplies the chronological edge-driven search algorithm captured in Algorithm 1 and directly extended by the co-mining recursion.","marker":"[30]"},{"why":"GPU baseline that provides the warp-level parallel candidate exploration and search-tree splitting which Mayura's GPU runtime adapts.","marker":"[57]"},{"why":"Establishes multi-query optimization for isomorphic subgraph mining, the structural-sharing idea Mayura adapts to temporal constraints.","marker":"[35]"},{"why":"Shows subgraph morphing can produce temporally invalid matches, motivating a tree built directly over temporally ordered edge prefixes.","marker":"[20]"},{"why":"Hierarchical index for visual exploratory subgraph search and the closest structural ancestor of the MG-Tree, distinguished here by offline multi-motif grouping.","marker":"[52]"},{"why":"Builds an on-the-fly hierarchical index for a single evolving query; the contrast clarifies why the MG-Tree is a compile-time tree over distinct motifs.","marker":"[21]"}],"fun_headline_variants":["Shared prefix motif mining: 2.4x CPU, 1.7x GPU speedup","Mayura co-mines temporal motifs with 2.4x CPU speedup","Co-mine temporal motifs: MG-Tree reuses paths, 2.4x faster","Exact multi-motif mining via shared search: 2.4x speedup"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole argument rests on the assumption that the tree-building step attaches every query motif to the tree and marks it on exactly one node, because if a motif is never marked the shared search will silently miss all of that motif's matches.","fun_headline_variants_meta":{"raw":{"variants":["Shared prefix motif mining: 2.4x CPU, 1.7x GPU speedup","Mayura co-mines temporal motifs with 2.4x CPU speedup","Co-mine temporal motifs: MG-Tree reuses paths, 2.4x faster","Exact multi-motif mining via shared search: 2.4x speedup"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000354,"raw_usage":{"total_tokens":1901,"prompt_tokens":896,"completion_tokens":1005,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":512,"completion_tokens_details":{"reasoning_tokens":910}},"tokens_in":512,"tokens_out":1005,"duration_ms":9897,"temperature":1.0,"reasoning_tokens":910,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T15:48:07.900672+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a motif group where one motif is a strict prefix of another, say a two-edge pattern A→B→C and a three-edge pattern A→B→C→D, and mine a tiny graph that certainly contains the two-edge pattern; if the two-edge motif's count is zero while mining it alone finds it, the exactness claim is false, and the construction pseudocode's unassigned parent query reference (lines 24–26 versus line 35) is a plausible source of exactly this failure.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes multi-query optimization for isomorphic subgraph mining, the structural-sharing idea Mayura adapts to temporal constraints."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows subgraph morphing can produce temporally invalid matches, motivating a tree built directly over temporally ordered edge prefixes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Hierarchical index for visual exploratory subgraph search and the closest structural ancestor of the MG-Tree, distinguished here by offline multi-motif grouping."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Builds an on-the-fly hierarchical index for a single evolving query; the contrast clarifies why the MG-Tree is a compile-time tree over distinct motifs."}],"review_version":1}