{"id":"7d6e9f93-88c4-48ad-b0ca-bc0b922f1a59","arxiv_id":"2508.18151","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A new edge-centric binary forest index answers temporal k-core component queries with far smaller index size and much faster construction than the existing EF-Index.","lead":"This paper proposes a compact index, the ECB-forest, for temporal k-core component queries, which find all people in the same dense connected group as a query vertex inside a given time window. It reports index sizes and build times far below the previous EF-Index while keeping query latency in the tens of microseconds.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 5's edge-core-time formula drops the edge's own timestamp, letting the CT-MSF connect components before the edge exists; this breaks the EC-equivalence at the heart of the index.","rationale":"The reader's weakest_assumption precisely identifies the load-bearing flaw: Section 5's edge-core-time formula omits the edge timestamp, contradicting Definition 4.3. This is not a stylistic or consensus dispute; it is an internal inconsistency that invalidates Lemma 4.7 and the EC-equivalence claim on which the entire ECB-forest construction and query algorithm depend. The paper supplies no proof that max(CT_u, CT_v) equals the earliest end time at which the edge belongs to the k-core, and the counterexample shows it is false. A corrected formula max(CT_u, CT_v, t) could repair the definition, but the manuscript as written does not state or prove it, and the construction algorithms, proofs, and experiments are all built on the incorrect formula. The reader's REJECT verdict is therefore appropriate as written. Other weaknesses, such as the underspecified Lemma 5.1 insertion proof, are secondary; the core-time error alone is sufficient to reject.","tokens_in":27463,"tokens_out":2910,"duration_ms":29913,"concrete_test":"Construct a temporal graph with two disjoint triangles: (a,b,1), (b,c,1), (a,c,1) and (d,e,1), (e,f,1), (d,f,1), plus a bridge (a,d,10), for k=2. Compute vertex core times for start time 1 via the cited algorithm: all six vertices are in a 2-core at end time 1, so each terminal has CT=1. The paper's Section 5 formula then gives the bridge CT=1, so the CT-MSF includes the bridge for window [1,5]. Run Algorithm 1 for query (a, [1,5]) on the PECB-Index and compare with brute-force k-core of G[1,5]: the true answer is {a,b,c}, while the index returns {a,b,c,d,e,f}. To strengthen the test, systematically enumerate small temporal graphs and compare each edge's core time from Definition 4.3 with max(CT_u, CT_v); any mismatch confirms the flaw.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central index's correctness rests on the edge-core-time computation in Section 5. The paper asserts: 'The core time of any edge for the start time t0 is the larger one among the core times of its terminal vertices for t0.' This ignores the edge timestamp t from Definition 4.3. For edge (u,v,t) to belong to the k-core in window [t0, t_e], it must be present, so t_e >= t. If max(CT_u, CT_v) < t, the formula assigns a core time earlier than the edge exists, causing the CT-MSF to connect components before the connecting edge appears. Concretely, take k=2, two triangles at time 1, and a bridge (a,b,10). Vertex core times of a and b are both 1, so the bridge gets CT=1, and the CT-MSF connects the two triangles for all end times >=1; query [1,5] then returns both triangles as one component, whereas the true 2-core component of a in [1,5] is only its triangle. Lemma 4.7 and the ECB-forest equivalence depend on these core times being the true earliest membership times, so this premature merge destroys the EC-equivalence guarantee and invalidates the query claims. The fix max(CT_u, CT_v, t) may restore the approach, but as written the core construction is unsound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the temporal k-core component search (TCCS) problem: given a temporal graph, a query vertex, and a time window, return the connected component of the temporal k-core that contains the query vertex. To support arbitrary windows, the paper introduces the ECB-forest, an edge-centric binary forest derived from a core-time-based minimum spanning forest for each anchored start time, and the PECB-Index, which stores only the differences between forests of adjacent start times. The paper claims a query time of O(r log l), an index size of O(n l) per start-time forest (with l the average number of labels per node), and construction cost bounded by the forest depth per inserted edge. Experiments on 15 real-world temporal graphs report large reductions in index size and construction time relative to the EF-Index while maintaining microsecond-level query latency.","tokens_in":27767,"tokens_out":8359,"duration_ms":89632,"significance":"If the proposed structure is correct, the contribution is significant: it offers a much more compact and faster-to-build index for a practically motivated query primitive, and the experimental study is broad. The paper also provides an artifact URL and avoids fitted parameters, grounding its derivation in the external vertex-core-time algorithm of [33] and the MST threshold property. However, the central correctness argument rests on the Section 5 edge-core-time formula, which is inconsistent with Definition 4.3. Until that formula is repaired and the subsequent proofs and experiments are reworked, the claimed guarantees are unsupported.","major_comments":[{"comment":"The paper states that the core time of an edge (u,v,t) for start time t0 is the larger of the core times of its terminal vertices. Definition 4.3 defines CT_{t0}(e) as the earliest end time te such that e belongs to the k-core of G[t0,te]. Since e has timestamp t, this requires t <= te, so the correct value is max(CT_{t0}(u), CT_{t0}(v), t). The omitted t is load-bearing. For example, take k=2, two disjoint triangles with all edges at time 1, and a bridge edge (a,b,10) between them. The vertex core times of a and b are 1, so the paper's formula assigns the bridge a core time of 1; the CT-MSF then connects the two triangles for every end time te >= 1, and the query [1,5] returns both triangles as one component, whereas the true 2-core component of a in [1,5] is only its triangle. This contradicts Lemma 4.7 and the EC-equivalence property of Definition 4.2, and it invalidates Algorithm 1 and the experimental claims as stated. The formula must be corrected and the construction, proofs, and experiments redone.","section":"Section 5, 'Computing Edge Core Times'; Definition 4.3"},{"comment":"The proof of Lemma 5.1 is not a proof: it asserts that the four insertions and two deletions 'integrate' e and 'preserve reachability' without showing that for every end time te the connected components of the updated ECB-forest coincide with those of the temporal k-core. The argument does not address the edge-timestamp issue from Definition 4.3, and Lemma 5.5 (the WE operator) is stated without proof. Since Lemma 5.1 is the load-bearing invariant for Algorithm 3 and Theorem 5.9, the authors need to provide a rigorous proof, or a counterexample that motivates a different insertion rule.","section":"Section 5, Lemma 5.1"},{"comment":"The query complexity is stated as O(r log l) with r the result size, but Algorithm 1 returns vertices while the BFS visits forest nodes that represent edges. An edge component can contain quadratically more edges than vertices, so the stated bound does not follow from the proof given. The theorem should either define r as the number of visited forest nodes and derive the vertex set from it, or state the complexity as O((|V_comp| + |E_comp|) log l).","section":"Section 4.2, Theorem 4.15"},{"comment":"The experiments measure index size, construction time, and query time, but they never validate that PECB-Index returns the correct k-core component against a brute-force baseline. Because the flaw in Section 5 can produce wrong query results without affecting running time, the current experiments cannot distinguish the proposed index from an incorrect one. A correctness comparison, for example on small graphs with exhaustive enumeration of windows, should be added.","section":"Section 6"}],"minor_comments":[{"comment":"The output comment in Algorithm 1 contains a typo: 'componet' should be 'component'.","section":"Algorithm 1"},{"comment":"The sentence 'we record, so we record' is duplicated and should be reduced to a single occurrence.","section":"Example 4.5"},{"comment":"The claim that core times never decrease as t0 grows is intuitive but unproved; a one-sentence argument would make the monotonicity assumption precise.","section":"Section 4.1"},{"comment":"The y-axis labels in Figures 4-6 do not explicitly state that the reported quantities are in seconds or megabytes; adding clear axis labels would improve readability.","section":"Figures 4-6"}],"recommendation":"major_revision","confidential_remarks":"The reader's report recommends rejection, and the Section 5 edge-core-time bug is indeed load-bearing. However, the error has an evident repair: replace the formula with max(CT_{t0}(u), CT_{t0}(v), t). I therefore regard the central approach as defensible in principle and recommend major revision rather than outright rejection, provided the authors re-derive the construction, supply rigorous proofs for Lemmas 5.1 and 5.5, and rerun the experiments with a correctness check."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the index design is genuinely new and the experiments are serious, but the paper as written has a load-bearing correctness gap in Section 5, exactly where the reader puts it. Definition 4.3 defines an edge's core time for a start time as the earliest end time at which the edge is in the k-core. Since an edge with timestamp t(e) cannot be in any window ending before t(e), that core time is at least t(e). Section 5 instead computes it as the larger of the two terminal vertices' core times. The stress-test example is fair: k=2, two triangles at time 1, bridge (a,b) at time 10. Both a and b have vertex core time 1, so the formula assigns the bridge core time 1, the CT-MSF connects the components for all end times, and a [1,5] query returns both triangles as one component. The one-line fix max(CT_u, CT_v, t(e)) should restore the EC-equivalence, since in an induced k-core an edge is present whenever its endpoints are in the core and its timestamp lies in the window. But as written, the central claim that the ECB-forest is equivalent to the temporal k-core is not supported.\n\nWhat is new and good: the edge-centric binary forest, the versioned label compression across start times, and the incremental construction by edge insertion and wedge elimination. This is a real alternative to the EF-Index's per-window forests, and the complexity story is plausible. The experiments are extensive: 15 real datasets, day-aggregated and raw timestamps, an EF-Index baseline plus a CTMSF baseline. The reported space and construction-time gains are large and likely to survive the corrected core-time formula, since the formula change does not alter the indexing machinery. The citation pattern is fine; the dependency on [33] is a legitimate building block, and the flaw is internal, not a citation issue.\n\nThe other soft spot is Lemma 5.1. Its proof is more assertion than argument; the insertion and deletion operations are stated to preserve components, but the detailed reasoning is thin. A revision needs a real proof there as well as the corrected core-time computation.\n\nWho this is for: anyone working on temporal graph indexes or k-core search. It deserves a serious referee. My editorial recommendation: send to review, and expect a revision that fixes the edge-core-time formula and expands the construction proof. The idea is worth engaging with.","headline":"A genuinely useful index idea undermined by an edge-core-time formula that omits the edge's own timestamp; the fix is a one-line max, but as written the central equivalence claim does not hold.","tokens_in":28248,"tokens_out":4302,"would_cite":false,"duration_ms":44546,"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":"A compact edge-centric binary forest reduces historical k-core component queries to a connected-component search, shrinking index cost by up to three orders of magnitude.","keywords":["temporal graphs","k-core","historical queries","component search","edge core time","binary forest","incremental index construction","temporal k-core"],"falsifier":"Build a small temporal graph where two vertices $u$ and $v$ are already in the $k$-core at time $t_0$ through other edges, and add a single edge $(u,v,t)$ with $t > t_0$. Compute the core time of that edge by the paper's formula $\\max(\\mathrm{CT}(u), \\mathrm{CT}(v))$; if the result is less than $t$, query the window $[t_0, t-1]$. Algorithm 1 will return $u$ and $v$ in one component via that edge, whereas a direct $k$-core computation on $G[t_0, t-1]$ has no such edge and may keep them separated. Any such discrepancy settles the question.","tokens_in":27146,"feed_emoji":"🌲","tokens_out":7195,"duration_ms":74700,"temperature":0.7,"pith_summary":"This paper aims to establish that historical k-core component search (TCCS) in temporal graphs can be answered from a compact 'edge-centric binary forest' instead of from a large set of per-window spanning forests. The claim is that for any fixed start time, a forest whose nodes are edges weighted by their core times preserves exactly the connected components of the temporal k-core for every end time, so a query reduces to a breadth-first search of one connected component. If correct, this replaces the EF-Index's quadratic preprocessing and redundant storage with an $O(n)$-per-start-time index built in near-linear incremental work, while keeping queries in microseconds. That would make temporal core queries practical at fine timestamp granularity for contact tracing, fraud detection, and similar windowed analyses.","feed_headline":"One binary forest answers any historical k-core query","feed_subtitle":"Temporal k-core component search becomes a forest traversal, cutting index construction time by up to 100x.","key_machinery":"The carrying object is the ECB-forest (edge-centric, connectivity-equivalent, binary forest). Given a start time $t_0$, each forest node is an edge of the temporal graph with weight $CT(e)$ (Definition 4.3); the rank of a node is its core time with ties broken by edge ID, and the parent and two children of a node are chosen as the highest-ranked edges below it that connect to each endpoint. This yields a forest with at most two children per node, and Lemma 4.11 states that all nodes in the same temporal core component are connected in the forest. The construction machinery is a set of constant-time rewrite operators, notably the WE (wedge equivalence) operator, that insert a newly appearing edge, break cycles, and identify the expired highest-ranked node as the lowest common ancestor of the two insertion anchors, so each edge insertion costs $O(h)$ for forest depth $h$.","core_discovery":"The central discovery is that the temporal k-core component containing a query vertex in an arbitrary window can be recovered from a spanning forest rather than from the full core. For a fixed start time $t_0$, the paper assigns each edge a core time $CT(e)$ — the earliest end time at which the edge belongs to the k-core — and builds a minimum spanning forest (the CT-MSF) with those core times as weights. It then rewires that forest into an edge-centric binary forest (ECB-forest) in which each node is a graph edge, each node has at most two children, and the parent/child relation is dictated by the global ranking by core time. The paper claims that this forest is EC-equivalent to the temporal k-core: for every end time, the connected components of the forest's edges with core time at most $t_e$ coincide with the components of the temporal k-core, so Algorithm 1's breadth-first traversal returns exactly the query component. Across start times, the PECB-Index stores only the parent/children triples that change, yielding an index whose size and construction time beat the EF-Index by up to three orders of magnitude while retaining microsecond query latency.","pith_inferences":["Editorial inference: the ECB-forest's equivalence argument would survive a corrected edge core time that also accounts for the edge's own timestamp, since the forest machinery only uses the resulting weights; the formula in Section 5, not the structure, is the fragile point.","Editorial inference: any window-monotone cohesive family whose membership per edge can be summarized by an earliest entry time could plausibly be indexed the same way, so span-cores, persistent cores, or burst-detection variants are natural next targets.","Testable extension (editorial): on graphs with many late edges among high-core vertices, running Algorithm 1 against a brute-force k-core computation on random windows should expose any discrepancy, and the errors, if present, would concentrate exactly on the edge-core-time formula."],"forward_implications":["Any start-anchored query can be answered by a breadth-first traversal of an $O(n)$-node binary forest rather than the full temporal core.","Index construction cost is bounded by the forest depth per inserted edge, yielding up to 100x faster builds than the EF-Index baseline on real datasets.","Query time stays $O(r \\log l)$ for result size $r$, keeping latencies in the microsecond range.","The index naturally supports fine-grained original timestamps, where the EF-Index fails to complete on most datasets.","Only changed parent/child triples need storage between consecutive start times, giving the PECB-Index its compact space guarantee."],"supporting_citations":[{"why":"Defines the k-core whose connected components every TCCS query must return.","marker":"[26]"},{"why":"Defines the temporal k-core and supplies the OTCD enumeration that the EF-Index baseline builds on.","marker":"[31]"},{"why":"Formulates the TCCS problem and provides the EF-Index baseline that the paper compares against.","marker":"[32]"},{"why":"Supplies the vertex core-time computation algorithm that the paper extends to edge core times.","marker":"[33]"}],"fun_headline_variants":["ECB-forest slashes k-core index build time by 100x","Temporal k-core search reduced to a forest walk","Compact forest index replaces bulky EF-Index for k-core","100x faster construction for temporal k-core index","One binary forest covers all historical k-core queries"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's index is correct only if an edge's core time for a fixed start time is always the larger of its two endpoints' core times; an edge whose own timestamp is later than both endpoints' core times would be assigned too early an entry time, potentially connecting components before that edge exists.","fun_headline_variants_meta":{"raw":{"variants":["ECB-forest slashes k-core index build time by 100x","Temporal k-core search reduced to a forest walk","Compact forest index replaces bulky EF-Index for k-core","100x faster construction for temporal k-core index","One binary forest covers all historical k-core queries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000257,"raw_usage":{"total_tokens":1572,"prompt_tokens":933,"completion_tokens":639,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":549,"completion_tokens_details":{"reasoning_tokens":559}},"tokens_in":549,"tokens_out":639,"duration_ms":6321,"temperature":1.0,"reasoning_tokens":559,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:59:59.205866+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a small temporal graph where two vertices $u$ and $v$ are already in the $k$-core at time $t_0$ through other edges, and add a single edge $(u,v,t)$ with $t > t_0$. Compute the core time of that edge by the paper's formula $\\max(\\mathrm{CT}(u), \\mathrm{CT}(v))$; if the result is less than $t$, query the window $[t_0, t-1]$. Algorithm 1 will return $u$ and $v$ in one component via that edge, whereas a direct $k$-core computation on $G[t_0, t-1]$ has no such edge and may keep them separated. Any such discrepancy settles the question.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the vertex core-time computation algorithm that the paper extends to edge core times."}],"review_version":2}