{"id":"57d8da25-1e06-41eb-ae22-639b17daa8d1","arxiv_id":"2508.15238","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"CoreT answers all temporal k-core queries over a time interval in a single pass by maintaining k-core entry times, with claimed complexity O(Δ·|E|) and up to 10,000x speedups.","lead":"A database paper proposes CoreT, an algorithm that answers temporal k-core queries by recording the earliest time each vertex or edge enters a k-core, claiming linear time in the number of temporal edges times the interval length. If correct, it makes long-range temporal community analysis scalable, with reported speedups of up to four orders of magnitude over the prior OTCD method.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unproved 'each element enters S at most once' invariant in CoreT_Update is load-bearing; if false, the claimed O(Δ|E|) total time collapses.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing point: the unproved order-based invariant in CoreT_Update that each vertex/edge enters S at most once. This invariant is the linchpin of the O(Δ|E|) total complexity, and the paper itself omits its proof. I also agree that Algorithm 2's garbled degree-time update line is a concrete obstruction to verifying the initialization phase, though it is secondary to the S-invariant issue. I considered whether a different concern—such as the TTI uniqueness check or the 'each timestamp has at least one edge' assumption—is more damaging, but those are either addressed by the monotonic enumeration or can be absorbed into the stated bound under a mild assumption. The S-invariant is the true soft spot: if it fails, the worst-case per-iteration work is superlinear and the headline result does not follow. The paper's idea is plausible, the experimental evidence is broad, and the missing proof is explicitly acknowledged, so CONDITIONAL (as the reader already gave) remains the right verdict. My stress-test does not move the verdict; it sharpens the condition: supply a rigorous proof of the descending-order invariant (or a corrected algorithm that provably satisfies it) and fix Algorithm 2's line 11.","tokens_in":22305,"tokens_out":10514,"duration_ms":124144,"concrete_test":"Instrument Algorithm 3 to record, for every vertex and edge, how many times it is inserted into S. Enumerate exhaustively all small temporal graphs (e.g., all subsets of edge-timestamp incidences on ≤6 vertices, ≤4 timestamps, for k=2 and k=3) and run the instrumented CoreT_Update on each. If any vertex or edge is inserted into S more than once on any instance, the 'at most once' invariant is false and the linear per-iteration bound cannot hold as stated; the authors should then either revise the algorithm or the complexity claim. If no duplicates occur throughout the exhaustive enumeration, this strongly suggests the invariant is true but still does not replace the missing formal proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the O(Δ × |E[Ts,Te]|) time bound for CoreT. The per-iteration linearity of CoreT_Update (Algorithm 3) rests entirely on the assertion, in Section III-C ('Update ordering'), that processing updates in descending order of tentative core time ensures 'each vertex or edge enters and leaves the candidate set once.' The paper explicitly says 'To ease the presentation, we omit the formal proof.' This is not a minor gap: the informal argument only shows that after an element with maximum tentative time t* is processed, later updates from elements with smaller times cannot raise it above t*, but it does not rule out an element being inserted, then raised again before it is popped (e.g., a vertex inserted at 50 via one incident edge, then raised to 70 via a different incident edge while still in S). Such re-insertion would invalidate the O(|E|) bound for Lines 7–22 and hence the headline complexity. A separate presentation defect compounds this: Algorithm 2, line 11, is garbled ('dTs(·, G′) ← the k-th smallest one among {Sup(v∗, v,G0) ...}'), so the k-degree update rule in the initialization phase is not actually specified, making it impossible to verify the O(|E0|) initialization claim as written. Both issues are addressable, but until the invariant is proved (or the algorithm is modified to make it true), the strongest stated guarantee is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper revisits the time-range temporal k-core query problem (Problem 1) and proposes CoreT. The algorithm first computes k-core times σ_Ts for vertices and edges (Section III-B), uses Lemma 2 to list all temporal k-cores with start time Ts, then in each of Δ−1 iterations refines the graph and updates σ by Algorithm 3. The central claim is a total running time of O(Δ × |E[Ts,Te]|), a single pass over the query interval, and experiments on nine real graphs report speedups up to four orders of magnitude over OTCD.","tokens_in":22698,"tokens_out":7403,"duration_ms":83066,"significance":"If the complexity analysis were rigorous, CoreT would be a meaningful advance: it replaces OTCD's repeated Decomp calls with a single incremental propagation of entry times, and the experiments suggest large practical gains. The paper's use of k-core times and Lemma 2 is sound, and the empirical comparison is extensive. However, the main theoretical guarantee rests on an unproved and nontrivial invariant in the update phase; this must be supplied before the paper can be assessed as written.","major_comments":[{"comment":"The claimed O(|E[Ts,Te]|) per-iteration bound for CoreT_Update rests entirely on 'each vertex or edge enters and leaves the candidate set once' (Section III-C). The paper explicitly says 'we omit the formal proof.' The informal argument only analyzes elements after they have already been popped; it does not rule out an element being updated upward while it is still in S, nor a popped element being reinserted by a later edge update. For example, if vertex v is in S with tentative time 50 and another incident edge later raises its tentative time to 70, then either the S entry must support priority updates (not specified) or v will be added again. Without a proof that no element is processed more than once (or an alternative amortized accounting), Lines 7–22 cannot be bounded by O(|E|), and the headline O(Δ|E|) complexity does not follow. This is the main revision needed.","section":"Section III-C, Algorithm 3 (Update ordering)"},{"comment":"Algorithm 2, line 11 is garbled: 'dTs(·, G′) ← the k-th smallest one among {Sup(v∗, v,G0) | v ∈ V ′ & (v, v∗) ∈ E0}' has no well-defined left-hand side and uses support times of the removed vertex v*. The intended update rule for the k-degree time of a neighbor v of v* must be stated precisely (presumably the k-th smallest support time among v's incident edges to vertices remaining in V', with +∞ if fewer than k). As written, the reader cannot verify the O(|E0|) initialization time or the correctness proof in Lemma 3.","section":"Section III-B, Algorithm 2, line 11"},{"comment":"The procedure is presented only with an informal rationale; Lemma 4 and 5 give local dependencies but no invariant tying tentative values to σ in Gt. A rigorous proof that Algorithm 3 terminates with σTs+t(·,Gt) is needed, especially because the update ordering may skip recomputations. As it stands, correctness is asserted rather than demonstrated.","section":"Section III-C, correctness of CoreT_Update"}],"minor_comments":[{"comment":"The formula 'O(∆ × |E[Te−Ts])' should be 'O(∆ × |E[Ts,Te]|)'; the same subscript error appears in Section III-C ('O(|E[Te−Ts]|)').","section":"Section III-A, Time complexity analysis"},{"comment":"Line 3 refers to 'Sup(u,v,G1)' but G1 is never defined. Clarify whether this is the graph after removing the current timestamp's edges or another refinement.","section":"Section III-C, Algorithm 3, line 3"},{"comment":"The remark states that the O(|Te−Ts|^2) TTI check is 'strictly smaller than |E[Ts,Te]|' under the assumption that each timestamp has at least one edge. Since |E| ≥ Δ, O(Δ^2) can be equal to O(Δ|E|) when the graph is sparse per timestamp; the statement should be weakened to 'does not asymptotically increase O(Δ|E|)'.","section":"Section III-A, duplicate-removal remark"},{"comment":"In the first part of the proof, 'G′[Ts,t]' refers to a graph that changes during peeling; the argument would be clearer if it fixed the snapshot at the iteration where v′ is removed.","section":"Section III-B, Lemma 3 proof"},{"comment":"Typo: 'phrases' should be 'phases' in Section III-A. Also, 'CoreT_Updte' in Section III-C should be 'CoreT_Update'.","section":"Global"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real algorithmic idea with strong experimental results, but the paper's headline complexity is not actually proven. The single-pass update scheme that advances the start timestamp while maintaining k-core times is new relative to OTCD, and Lemma 2 gives a clean way to enumerate cores once you have core times. The experiments are broad — nine datasets, k and interval sweeps, and orders-of-magnitude speedups look believable, though no code is released.\n\nThe soft spot is exactly where the reader put it. Algorithm 3's claim that processing updates in descending order of tentative core time makes each vertex or edge enter the candidate set once is load-bearing, and the paper explicitly omits the proof. The informal argument only shows that later updates cannot push an element above a value it already reached; it does not rule out an element being raised again while still in the candidate set. If that happens, the per-iteration O(|E|) bound and the total O(Δ|E|) both collapse. This is not a minor cosmetic gap — it is the central complexity claim. Also, Algorithm 2 line 11 is garbled; the intended k-degree update rule has to be guessed, which makes the initialization phase unverifiable as written.\n\nI want to be fair: the overall design is plausible, and I did not find a counterexample to the invariant. Lemma 2 and the CoreT_Init peeling procedure look correct. But 'not obviously wrong' is not 'proved.' The paper would be solid with a formal proof of the invariant (or a modified algorithm that makes it true) and a corrected Algorithm 2.\n\nWho this is for: people working on temporal graph mining and core decomposition. It deserves peer review — the idea is good enough that a referee should spend time on it — but I would not accept it in current form. The authors need to close the proof gap and fix the presentation before the complexity claim is credible.","headline":"CoreT is a promising single-pass algorithm for temporal k-core queries, but the claimed O(Δ|E|) bound rests on an unproved invariant and a garbled line in the initialization algorithm.","tokens_in":23122,"tokens_out":1481,"would_cite":false,"duration_ms":16048,"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":"All distinct temporal k-cores in a query interval can be found in a single pass, with time linear in the interval's length times its edge count — removing the previous quadratic interval enumeration.","keywords":["temporal graphs","temporal k-core query","k-core time","cohesive subgraph mining","core decomposition","time-range query","graph algorithms","single-pass algorithm"],"falsifier":"A concrete check: construct a small temporal graph with interleaved edge expirations, run CoreT_Update by hand or by exhaustive search over all deletion orders, and look for any vertex or edge whose finalized core time must later be raised — i.e., an element that re-enters the candidate set after being processed. Finding one breaks the per-iteration linear bound. Independently, the correct-but-slow reference is brute force: run the peeling decomposition on every sub-interval of a random small graph (all pairs ts ≤ te) and verify CoreT returns exactly the same distinct cores; any mismatch local","tokens_in":22243,"feed_emoji":"🕒","tokens_out":8074,"duration_ms":79925,"temperature":0.7,"pith_summary":"The paper shows that the temporal k-core query — finding every distinct k-core that appears in any sub-interval of a given time range — can be answered in a single pass over time, in O(Δ × |E[Ts,Te]|) total work, where Δ is the query interval's length and |E[Ts,Te]| is the number of temporal edges inside it. The central device is the k-core time: for each vertex and edge, the earliest timestamp at which it enters a k-core. Given these times for a fixed start time, all cores starting at that time are obtained by a monotone threshold sweep, so the quadratic enumeration of overlapping sub-intervals collapses. A peeling initialization computes the core times once, and an incremental update maintains them as the start time advances by one, claiming each element is touched once per timestamp. On large real-world graphs the paper reports speedups of up to four orders of magnitude over the previous state of the art, OTCD, which frequently exceeds a three-hour limit on the same queries.","feed_headline":"One pass finds every temporal k-core in an interval","feed_subtitle":"By logging when each vertex and edge first joins a k-core, the new sweep beats the old method by up to 10,000x.","key_machinery":"The k-core time σ_x(v,G) (Definition 2) — the earliest timestamp t such that v (or edge (u,v)) lies in the k-core of the detemporalized graph over [x,t] — is the paper's central object. Lemma 2 converts core times into an enumeration rule: the temporal k-core T[x,te](G) is exactly the set of vertices and temporal edges whose k-core time is at most te. This identity carries the argument because it turns the problem into computing one vector of entry times per start timestamp rather than decomposing each sub-interval. Two reciprocal update rules (Lemmas 4 and 5) make those vectors maintainable: a vertex's core time equals the k-th smallest core time of its incident edges, and an edge's core ti","core_discovery":"CoreT computes all distinct temporal k-cores of a query interval by maintaining, for every vertex and detemporalized edge, a k-core time σ_x(·,G): the smallest end timestamp t such that the element belongs to the k-core of the detemporalized graph G[x,t]. Lemma 2 turns these times into an enumeration rule: a temporal k-core T[x,te] is exactly the subgraph induced by vertices with σ_x ≤ te and edges with σ_x ≤ te whose timestamp is ≤ te, so for each start time the family of cores is a monotone sweep in te. The initialization computes σ_Ts by repeatedly peeling the vertex with the largest k-degree time and recording the running minimum; the update phase moves the start time forward by deleting","pith_inferences":["The k-core time is a temporal analogue of the static core number; the same 'earliest entry time' bookkeeping can likely be lifted to higher-order structures such as k-trusses, as the paper's conclusion anticipates, or to (k,h)-cores by adapting the support-time and degree-time definitions.","The claimed O(|E[Ts,Te]|) per-timestamp update cost hinges entirely on the unproved invariant that descending-order processing prevents re-insertion. A natural stress test is to search, by exhaustive enumeration over small graphs, for an execution where an element must be revisited; the complexity guarantee stands or falls on that search.","CoreT's output enumeration is monotone per start time, which suggests the method composes with indexing: the per-start-time k-core-time vectors could be precomputed once and reused across many queries on the same graph, turning each query into a threshold sweep (the paper cites follow-up index work for the OTCD model).","For streaming settings, CoreT_Update's incremental revision of entry times as edges expire resembles a sliding-window core-number maintenance scheme; one testable extension is whether the same ordering argument supports arbitrary window slides, not just unit step advances."],"forward_implications":["Temporal k-core queries over long intervals become practical: CoreT finishes in seconds to a few minutes on graphs where OTCD exceeds a three-hour timeout (e.g., the askubuntu, mathoverflow, and wiki-talk datasets).","The single-pass structure eliminates the O(Δ²) round structure of OTCD, so query cost scales linearly in both the interval duration and the number of temporal edges inside it.","Knowledge of k-core times yields all cores for a given start time by a monotone sweep, so output for each start time is produced incrementally, smallest interval first.","Since CoreT is independent of OTCD's Temporal Edge List bookkeeping, it can be implemented on a plain adjacency representation of the detemporalized graph plus per-edge timestamp lists."],"supporting_citations":[{"why":"Defines the temporal k-core model and the time-range k-core query, supplies the baseline algorithm OTCD, and provides the inclusion property (Lemma 1) that CoreT builds on.","marker":"[39]"},{"why":"Introduces the k-core time concept (Definition 2) that the paper adopts as its central bookkeeping device.","marker":"[41]"},{"why":"Defines the classic k-core on static graphs, the structural notion every temporal variant extends.","marker":"[27]"}],"fun_headline_variants":["First-join timestamps shrink temporal k-core search to one pass","CoreT: single-pass temporal k-core query, 10,000x speedup","Log when vertices join cores, then sweep once for all k-cores","Temporal k-cores: one scan, linear complexity, 10k× faster","Earliest entry times enable a single scan for temporal k-cores"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The linear time bound stands on an unproved invariant: processing updates in descending order of tentative k-core time ensures each vertex or edge is finalized once per iteration, and the paper omits the formal proof; if any element must be revisited with a larger tentative time, the claimed O(|E[Ts,Te]|) per-iteration cost — and with it the total O(Δ × |E[Ts,Te]|) bound — fails.","fun_headline_variants_meta":{"raw":{"variants":["First-join timestamps shrink temporal k-core search to one pass","CoreT: single-pass temporal k-core query, 10,000x speedup","Log when vertices join cores, then sweep once for all k-cores","Temporal k-cores: one scan, linear complexity, 10k× faster","Earliest entry times enable a single scan for temporal k-cores"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001209,"raw_usage":{"total_tokens":4841,"prompt_tokens":793,"completion_tokens":4048,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":537,"completion_tokens_details":{"reasoning_tokens":3947}},"tokens_in":537,"tokens_out":4048,"duration_ms":27926,"temperature":1.0,"reasoning_tokens":3947,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T18:01:20.955841+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check: construct a small temporal graph with interleaved edge expirations, run CoreT_Update by hand or by exhaustive search over all deletion orders, and look for any vertex or edge whose finalized core time must later be raised — i.e., an element that re-enters the candidate set after being processed. Finding one breaks the per-iteration linear bound. Independently, the correct-but-slow reference is brute force: run the peeling decomposition on every sub-interval of a random small graph (all pairs ts ≤ te) and verify CoreT returns exactly the same distinct cores; any mismatch local","supporting_citations":[{"cited_title":"Scalable time-range k-core query on temporal graphs,","cited_arxiv_id":null,"evidence_quote":"Defines the temporal k-core model and the time-range k-core query, supplies the baseline algorithm OTCD, and provides the inclusion property (Lemma 1) that CoreT builds on."},{"cited_title":"On querying historical k-cores,","cited_arxiv_id":null,"evidence_quote":"Introduces the k-core time concept (Definition 2) that the paper adopts as its central bookkeeping device."},{"cited_title":"Network structure and minimum degree,","cited_arxiv_id":null,"evidence_quote":"Defines the classic k-core on static graphs, the structural notion every temporal variant extends."}],"review_version":1}