{"id":"98e61524-12e0-49de-b311-81b36f8d6e33","arxiv_id":"2507.20441","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"TIMEST estimates temporal motif counts in large timestamped graphs by sampling spanning trees of the motif and rescaling validated extensions.","lead":"A new sampling algorithm counts repeated temporal patterns, called motifs, in timestamped networks with up to six nodes, where exact methods time out. It is often faster and more accurate than prior approximate methods, and the authors provide code and theoretical bounds.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The low-error claim rests on an unproven spanning-tree heuristic; Fig. 6 shows tree choice can swing error from <1% to >350%, and Table 3 already reports >20% error for M6-4/M6-5 in several datasets.","rationale":"The reader's weakest assumption is the same one I would stress-test. The estimator itself appears unbiased if Lemma 4.11 holds; the missing proof is a separate concern, but the demonstrated 350% error spread and the >20% errors on M6-4/M6-5 in Table 3 make tree selection the most load-bearing practical point. The theoretical bound in Theorem 4.14 cannot rescue the headline accuracy claim because it only controls error for a prescribed k depending on W/C; it says nothing about the heuristic's choice. The concrete test above would settle whether the heuristic picks near-minimum-W trees on a real hard motif. I agree with the reader's conditional verdict; the concern does not move it.","tokens_in":27592,"tokens_out":18407,"duration_ms":211740,"concrete_test":"Use the released reproduce.py on SO with M6-4: enumerate all spanning trees, run TIMEST with k=1e8 for each, and compute (a) the W of the tree selected by Algorithm 7 versus the minimum W over all trees, and (b) the empirical error of the selected tree. If the selected tree's W is not within a small factor of the minimum, or its error stays above 20% when k is increased to 1e9 while the minimum-W tree control drops below 5%, the unguaranteed heuristic is the cause of the headline accuracy failure.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.5 (Algorithms 7-8) selects the spanning tree via a constraint-looseness proxy plus top-k W evaluation, with no approximation guarantee. Theorem 4.14 makes the required sample count proportional to W/C, and W is tree-dependent; a bad tree can make the fixed-budget estimate arbitrarily inaccurate. The paper's own Fig. 6 demonstrates this: for M6-4, 54 spanning trees give errors from <1% to >350%. This is not merely hypothetical: Table 3 reports 33.1% error for M6-4 on SO and 72.3%/100% for M6-5, and the text's claim that only M5-4 and M5-5 exceed 20% error is contradicted by that table. Until the heuristic is shown to select near-minimum-W trees, or errors are recomputed with a guaranteed tree selection, the abstract's 'accurate ... less than 5% error in most cases' is not supported as a general claim for arbitrary motifs and graphs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"TIMEST is a randomized estimation algorithm for counting occurrences of a user-specified temporal motif in a temporal multigraph. The algorithm first selects a spanning tree of the motif (Section 4.5), relaxes three groups of temporal constraints (adjacent-edge ordering and δ-window, distinct adjacent endpoints, and a 2δ sliding-window partition), and preprocesses the graph to compute per-edge sampling weights by a bottom-up dynamic program (Claims 4.8–4.10). In the sampling phase it draws partial matches to the spanning tree with probabilities proportional to these weights (Section 4.2), validates them against the full motif definition, counts extending motif instances with a ListCount routine (Section 4.3), and rescales the average by the total sampling weight W. Lemma 4.12 proves unbiasedness; Theorem 4.14 gives a Chernoff-style relative-error bound with sample count k = (3B/ε²)(W/C) ln(2/γ). The paper claims TIMEST is general for arbitrary motif sizes, always faster than prior exact and approximate algorithms (28× average speedup over the Everest GPU exact code, 6× over PRESTO), and accurate with 'less than 5% error in most cases,' illustrated by a money-laundering motif counted in four minutes with 0.6% error where the exact method needed two days. Experiments cover 4-, 5-, and 6-vertex motifs on four datasets.","tokens_in":27769,"tokens_out":33392,"duration_ms":308243,"significance":"If the results hold, TIMEST is a meaningful advance for temporal motif counting: it is the first general-purpose estimator I am aware of that is demonstrated on 5- and 6-vertex temporal motifs, it delivers consistent order-of-magnitude speedups over both exact GPU enumeration and the strongest prior approximate method, and the estimator is derived from first principles. Strengths I want to credit explicitly: the unbiasedness proof (Lemma 4.12) is a genuine from-first-principles argument with no fitted parameters and no circularity; the concentration analysis (Theorem 4.14) is standard and, modulo notation, correct; the 2δ-window correction is sound for true motif matches (any match with span ≤ δ lies in at least one sliding window); and the artifact with source code and reproduction scripts is linked. The accuracy claim, however, is not uniform: several motif/dataset pairs have large errors (M6-4 on SO at 33.1%; M6-5 on WT/SO at 72.3%/100%), and the end-to-end accuracy depends on a spanning-tree selection heuristic without guarantees. These issues qualify the significance but do not erase the algorithmic contribution.","major_comments":[{"comment":"The accuracy claims in the abstract and in Section 1.3 are contradicted by the paper's own Table 3. Section 1.3 states that 'the only hard motifs for TIMEST are M5−4 and M5−5, which have more than 20% error,' but Table 3 reports M6-4 on SO at 33.1% error and M6-5 at 72.3% (WT) and 100% (SO), and the abstract's 'consistently showcasing less than 5% error in most cases' therefore does not hold for a whole class of 6-vertex motifs — precisely the motifs emphasized as money-laundering patterns in the introduction. Moreover, for BI and RE the M6-4/M6-5 error entries are labeled 'No Exact' because Everest timed out, so no accuracy can be claimed for those cells at all. Because accuracy is a headline contribution, the authors need to (i) restate the error regimes per motif class honestly in the abstract and conclusion, (ii) reconcile Section 1.3's 'only hard motifs' sentence with Table 3, and (iii) either show that additional samples or a different spanning tree bring the M6-4/M6-5 errors below 5% on WT/SO, or explicitly exclude such motifs from the accuracy claim.","section":"§1.3, Table 3, Abstract"},{"comment":"The end-to-end approximation guarantee is not supported: Theorem 4.14 bounds the relative error for a fixed spanning tree with k = (3B/ε²)(W/C) ln(2/γ), where W and B are properties of the chosen tree, but the tree selection in Section 4.5 (Algorithms 7–8) is a heuristic — a constraint-looseness proxy computed from the motif alone, followed by exact W computation for only the top n_c candidates — with no proven relation between the selected tree's W (or B·W) and the optimum. Figure 6 demonstrates that the choice is load-bearing: for M6-4, errors across 54 valid spanning trees range from below 1% to above 350%. Note also that the theorem's sample complexity depends on the product B·W/C, whereas the heuristic minimizes W alone and ignores B, so the informal statement in Section 1.3 that 'the temporal spanning tree with the fewest matches is the best choice' does not follow from Theorem 4.14. I recommend that the authors (i) provide an empirical robustness study comparing the heuristic-selected tree with the best and worst spanning trees (exhaustive enumeration is feasible for the 4- and 5-vertex motifs) across all datasets, reporting how close the selected tree comes to the best; (ii) adopt an adaptive sample budget that estimates W and C from pilot samples and sets k according to Theorem 4.14; or (iii) explicitly reword 'approximation guarantee' so that it refers to the estimation step conditional on a given tree.","section":"§4.5 and Theorem 4.14"},{"comment":"The running-time guarantee in Claim 4.15 is not justified as stated. The DP sums in Claim 4.9 run over the sets L_{e,s,s′}, which are δ-window temporal in/out-lists and hence are bounded by the maximum temporal degree in a δ-window (including parallel-edge multiplicity σ_δ), not by d_max as defined in Claim 4.15 ('the maximum number of simple edges incident on any vertex'). If these sums are computed by iterating over the lists, the preprocessing cost should grow with σ_δ; if instead they are evaluated with prefix sums over time-sorted adjacency lists, the proof's assertion of 'O(1) time to fetch those weights' needs to be spelled out and the d_max term should be replaced by an O(log m) binary-search factor. As written, neither the statement nor the proof of Claim 4.15 supports the claimed O(|E(S)|² m d_max) bound.","section":"Claim 4.15"}],"minor_comments":[{"comment":"In the displayed formula for w_{s,e}, the second product factor should be (Σ_{e∈L_{e,s,s2}} w_{s2,e}), with the summation set matching the edge subscript; as printed the factor uses L_{e,s,s1} with w_{s2,e}. The proof states the correct form, so this is a typo, but the displayed identity is wrong as written.","section":"Claim 4.9"},{"comment":"The letter M is used for the true motif count that Lemma 4.12 calls C (e.g., 'E[Y_i]/B = Mk/WB' and 'the event |WY/k − C| ≥ εC' within the same paragraph). Unify the notation.","section":"Theorem 4.14 proof"},{"comment":"The claim 'N_φ ≤ 2 for every partial match φ to S' is not strictly true at sliding-window boundaries: a partial match all of whose edges carry the same timestamp exactly iδ is contained in three windows [(i−2)δ, iδ], [(i−1)δ, (i+1)δ], and [iδ, (i+2)δ]. Unbiasedness survives because ValidateAndDeriveCnt divides by the actual N_φ, but the bound should be corrected to N_φ ≤ 3 (or restricted to non-degenerate matches), and Algorithm 4 should state how N_φ is computed at runtime.","section":"Lemma 4.11 and Algorithm 4"},{"comment":"Line 5 iterates 'for s ∈ O[H]' while the surrounding loop variable is h; this should be O[h]. The loop header 'for h ∈ [H, 0]' is also non-standard notation.","section":"Algorithm 3"},{"comment":"There are several typographical issues: 'we alsoTIMEST and Everest (GPU) on the bipartite money laundering pattern' is missing a verb; Table 4's header contains 'erative error' instead of 'relative error'; and the title and abstract contain artifacts ('Using S ampling Trees', 'Temporal motifs have used to analyze').","section":"§5.2, Table 4, title, abstract"},{"comment":"The RE rows list motifs labeled M4-5 and M4-7, which do not correspond to any motif in Figure 3 (which defines only M4-1 through M4-4); either the labels or the figure need updating.","section":"Table 5"},{"comment":"The reported Everest runtime for SO, M6-5 is 1.5E5 s (≈41.7 hours), which exceeds the stated 1-day timeout limit; the table note says timed-out cases are marked 'No Exact,' so this entry needs reconciliation.","section":"Table 3"},{"comment":"The sentence 'We do not give results for the motifs M6−4 and M6−5 since previous methods timeout even after running for a day' is contradicted by Tables 3 and 4, which report M6-4 and M6-5 results for Everest and PRESTO on WT and SO; please clarify which comparison the sentence refers to.","section":"§1.3"}],"recommendation":"major_revision","confidential_remarks":"The main risk in this paper is the gap between the advertised 'approximation guarantees' and the heuristic-dependent practice; I would like the editor to ensure the revision includes either an empirical robustness study (heuristic-selected tree versus exhaustive best/worst trees for the smaller motifs) or an adaptive sample-budget procedure, plus a corrected accuracy narrative in the abstract and Section 1.3. The lineage from the authors' prior path-sampling work [40,41] is acknowledged appropriately, and the released artifact is a concrete strength; the internal contradictions between Section 1.3 and Table 3 would be a liability in a flagship venue. If the authors deliver those items, I see a clear path to acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read TIMEST. The core idea is a genuine generalization of path sampling: pick a spanning tree of the motif, relax temporal constraints just enough to run a DP-based weighted sampler, sample trees, validate, and rescale. The unbiasedness argument is correct as far as I can tell, and the Chernoff bound is standard but properly adapted. On the practical side the numbers are impressive: 5- and 6-vertex motifs on 100M-edge graphs, a 28x geomean speedup over a GPU exact method, and several motifs where TIMEST gets under 1% error while exact methods time out. The money-laundering example is a good concrete demo. This is a real contribution to temporal graph mining, not a repackaging.\\n\\nThe paper is also honest about some limits: Section 4.5 openly says the spanning-tree choice matters, Figure 6 shows a >350% worst case versus <1% best case, and the M6-5 discussion admits the 6-clique is hard. That is creditworthy. But the abstract's \"less than 5% error in most cases\" is not supported as stated. Table 3 shows M6-4 at 33.1% error on stackoverflow and M6-5 at 72.3% (WT) and 100% (SO), and the text in Section 1.3 says only M5-4 and M5-5 exceed 20%. That internal inconsistency needs fixing; either change the summary or explain why those cases are excluded from \"most.\"\\n\\nThe tree-selection heuristic is the load-bearing soft spot. Theorem 4.14 makes sample complexity proportional to W/C, and W depends on the chosen tree. There is no bound on how close the heuristic's selected tree is to the minimum-W tree, so the fixed-budget guarantee only applies conditional on the chosen tree. The paper's own Figure 6 shows the failure mode is real. This does not sink the paper: unbiasedness does not depend on the heuristic. It does mean the strong accuracy claims are empirical, not theoretical.\\n\\nMinor issues: Lemma 4.11 is stated without proof; it is probably true by telescoping, but it deserves a few lines. Claim 4.9 has a typo in the summation indices, and the M/C notation flips between the lemma and theorem. The code is available but not pinned; for a systems-adjacent paper, pin the commit.\\n\\nBottom line: this is a solid, useful paper that deserves a serious referee. I would accept it for peer review with the expectation of a major revision: prove or properly state Lemma 4.11, fix the error-summary contradiction, and soften the abstract to match the data.","headline":"Real generalization of path sampling with a sound core estimator; accuracy claims need to be reined in.","tokens_in":776,"tokens_out":764,"would_cite":true,"duration_ms":44355,"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":"TIMEST estimates temporal motif counts of arbitrary size by sampling spanning trees, and can count in minutes what exact methods take days to count.","keywords":["temporal motifs","motif counting","sampling","spanning trees","temporal networks","approximation algorithms","graph mining","randomized estimation"],"falsifier":"Take a large temporal graph, pick a 6-vertex motif such as M6-4, and run TIMEST with both the heuristic-chosen spanning tree and the tree S2 shown in Figure 6, using the same sample budget; the paper's Figure 6 predicts a difference between under 1% and over 350% error. If the heuristic-chosen tree's error exceeds the claimed approximation bound while another tree stays under it, the central accuracy claim fails for that input.","tokens_in":27335,"feed_emoji":"⏱️","tokens_out":6059,"duration_ms":54383,"temperature":0.7,"pith_summary":"The paper claims that temporal motif counting, long limited to motifs with at most four vertices, can be done for arbitrary motif sizes by sampling spanning trees of the motif from the input graph. This would matter because financial fraud detection and other applications rely on 5- and 6-vertex temporal patterns that exact enumeration cannot handle on large graphs. TIMEST relaxes some temporal constraints to make sampling efficient, then rescales the observed extension counts to get an unbiased estimate. The authors report under 5% error in most tested cases, with a 4-minute count of a money-laundering motif for which an exact GPU method takes over two days.","feed_headline":"Four-minute motif count replaces two-day exact search","feed_subtitle":"General-purpose sampler counts 5- and 6-vertex motifs on billion-edge graphs that exact methods cannot finish.","key_machinery":"The central object is the temporal spanning tree S of the motif M: a spanning tree of the motif's edges with an ordering and dependency list. TIMEST forms a partial match to S by enforcing only three relaxed constraints — temporal order and delta-window on adjacent edges, distinct endpoints on adjacent edges, and a global 2-delta sliding-window partition — then computes edge sampling weights bottom-up with dynamic programming, samples a partial match from the graph proportionally to these weights, validates it against the full motif constraints, and counts how many full motif matches extend from the sampled tree using binary-search-based list counting. The total sampling weight W, which counts all partial matches to S, is what the sample complexity and runtime estimate depend on, so the heuristic choice of which spanning tree to use is the practical linchpin.","core_discovery":"TIMEST is a general-purpose randomized algorithm that estimates the number of instances of any temporal motif in a temporal multigraph. The central claim is that by selecting a spanning tree of the motif, relaxing some of the motif's temporal constraints so that the tree can be sampled efficiently via weighted dynamic-programming preprocessing, and then validating and extending each sampled tree to full motif matches, one obtains an unbiased, concentrated estimate whose sample complexity depends on the ratio of the total sampling weight to the true count. The paper proves unbiasedness and a Chernoff-based sample bound, gives preprocessing and sampling complexity, and empirically shows an average 28x speedup over the GPU exact solver and 6x speedup over the approximate baseline, with consistently lower error; for the hardest 6-vertex motifs that exact methods cannot finish in a day, TIMEST returns estimates in minutes.","pith_inferences":["If the spanning-tree heuristic were replaced by a principled oracle or an adaptive tree-selection mechanism, the same framework might achieve the theoretical error bound uniformly, avoiding the observed errors above 20% on dense clique motifs.","The 2-delta sliding-window boundary correction suggests a general technique for handling over-counting in any sliding-window temporal sampling scheme, which could transfer to other temporal pattern counting problems.","The same sampling-tree machinery could be extended to partial-order temporal constraints, which the paper lists as future work; motifs whose constraints factor through a tree might be countable without the full validation step.","For very dense motifs such as cliques, the number of valid samples that contribute to the final count is tiny, so accuracy on such motifs would likely improve only if the sampler can exploit motif-specific structure beyond a single spanning tree."],"forward_implications":["Temporal motif counting can be extended beyond 4-vertex motifs: TIMEST handles 5- and 6-vertex motifs on graphs with hundreds of millions of edges, where exact methods time out or run out of memory.","The unbiased estimator plus sample-complexity bound means users can trade accuracy against runtime by setting the number of samples k, with the theory saying error scales roughly as the square root of the sampling weight over the true count divided by k.","Because the estimate is unbiased and the weight preprocessing dominates memory, peak memory use does not grow with motif complexity or sample count.","Counting a given money-laundering cycle motif on the Wiki-talk graph takes about four minutes at 0.6% error, versus two days for the fastest exact GPU system, so previously impractical fraud-pattern counts become routine."],"supporting_citations":[{"why":"Defines temporal motifs and matches, and gives the first general counting algorithm that TIMEST generalizes and that motivates the problem.","marker":"[42]"},{"why":"Provides the chronological backtracking algorithm underlying exact baselines and the evidence that exact methods cannot scale beyond four vertices.","marker":"[31]"},{"why":"The GPU-accelerated exact system that TIMEST compares against in runtime experiments.","marker":"[66]"},{"why":"The approximate sampling baseline PRESTO, whose runtime and error TIMEST compares against.","marker":"[48]"},{"why":"Prior temporal path-sampling estimator for 4-node motifs that TIMEST generalizes from paths to arbitrary spanning trees.","marker":"[41]"},{"why":"Static-graph path-sampling method that supplies the substructure-sampling-and-extension paradigm TIMEST builds on.","marker":"[22]"},{"why":"Provides the Chernoff bound used in the proof of the sample-complexity guarantee.","marker":"[13]"},{"why":"Supplies the ListCount algorithm used in DeriveCnt to count motif extensions without enumeration.","marker":"[40]"}],"fun_headline_variants":["28x faster temporal motif counting with under 5% error","From days to minutes: TIMEST estimates large temporal motifs","Sampling trees speed up motif counting by 28x","General motif estimator tackles 6-vertex nets in minutes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The low-error guarantee rests on a heuristic that chooses which spanning-tree structure of the motif to sample from, and there is no proof that this choice will be a good one on a new graph or motif; a poor choice can inflate the error from under 1% to over 350%.","fun_headline_variants_meta":{"raw":{"variants":["28x faster temporal motif counting with under 5% error","From days to minutes: TIMEST estimates large temporal motifs","Sampling trees speed up motif counting by 28x","General motif estimator tackles 6-vertex nets in minutes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000211,"raw_usage":{"total_tokens":1453,"prompt_tokens":1026,"completion_tokens":427,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":642,"completion_tokens_details":{"reasoning_tokens":359}},"tokens_in":642,"tokens_out":427,"duration_ms":4418,"temperature":1.0,"reasoning_tokens":359,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:44:21.326746+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a large temporal graph, pick a 6-vertex motif such as M6-4, and run TIMEST with both the heuristic-chosen spanning tree and the tree S2 shown in Figure 6, using the same sample budget; the paper's Figure 6 predicts a difference between under 1% and over 350% error. If the heuristic-chosen tree's error exceeds the claimed approximation bound while another tree stays under it, the central accuracy claim fails for that input.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The GPU-accelerated exact system that TIMEST compares against in runtime experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The approximate sampling baseline PRESTO, whose runtime and error TIMEST compares against."},{"cited_title":"Seshadhri, and Nishil Talati","cited_arxiv_id":null,"evidence_quote":"Prior temporal path-sampling estimator for 4-node motifs that TIMEST generalizes from paths to arbitrary spanning trees."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Static-graph path-sampling method that supplies the substructure-sampling-and-extension paradigm TIMEST builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Chernoff bound used in the proof of the sample-complexity guarantee."}],"review_version":2}