{"id":"ef7ed154-3f09-4ee2-96ea-68f66f0aaae5","arxiv_id":"1908.10550","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New incremental and batch algorithms for updating k-truss decompositions under edge insertions, with large speedups on sparse graphs.","lead":"Researchers present faster ways to update the truss structure of a large graph when new edges are added over time. Their incremental and batch algorithms could make real-time community detection in evolving networks practical.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central correctness claim rests on unproved Theorems 1–3 and informal Property 1; brute-force comparison to static recomputation would settle it.","rationale":"The most load-bearing assumption is unstated rather than stated: the exactness of the pruning rule in Section V-C. The paper explicitly defers the proofs of Theorems 1–3 (Section IV: 'rigorously proved, although we do not present them here') and treats Property 1 as self-evident. These are not minor details: the incremental algorithm's guarantee that edges outside the explored path have unchanged K(.) is the contrapositive of Theorem 3, and the cascade in Section V-C is claimed to find exactly the set S' of edges whose K(.) increases. If Property 1 over-approximates or under-approximates S', the algorithm silently computes wrong truss numbers. The batch algorithm extends the same mechanism to multiple insertions with no additional proof beyond an informal paragraph. No correctness oracle is reported in the experiments: the paper measures speedups but does not state that the updated K(.) values were checked against static recomputation, so the empirical results do not provide evidence of correctness. The concern is concrete: a false Theorem 3 or Property 1 would break both algorithms. The proposed brute-force test is feasible for small n and would either find a counterexample or significantly de-risk the claim. Because the identified gap matches the reader's weakest assumption, I agree with the CONDITIONAL verdict.","tokens_in":13337,"tokens_out":14983,"duration_ms":154496,"concrete_test":"Write an independent implementation of JK-Inc and JK-Batch as specified in Sections V and VI (or obtain the authors' code). Exhaustively enumerate all simple undirected graphs with n≤7 vertices; for every graph and every absent edge, compute the static truss decomposition by Cohen's peeling algorithm, apply the incremental algorithm for that insertion, and compare the resulting K(.) values. Repeat for all batches of up to 3 absent edges using the batch algorithm. Any mismatch constitutes a counterexample to Theorem 3 or Property 1; agreement across all such graphs would substantially mitigate the concern. A randomized version on n≤10 with millions of trials provides additional coverage.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's incremental and batch algorithms update the truss decomposition exactly only if Theorem 3's path characterization and Property 1's pruning rule are correct. The text states (Section IV) that Theorems 1–3 'have been rigorously proved, although we do not present them here due to space limitations,' and Property 1 (Section V-A) is asserted informally. The pruning step in Section V-C assumes that the set S of K(.)=k edges reachable from the inserted edge's triangles, pruned by cascading removal of edges with relevant support count below k-1, exactly equals the set of edges whose K(.) rises to k+1. This equivalence is the entire basis for both the incremental and the batch algorithm; if any of the stated theorems or Property 1 has a hidden counterexample, the algorithms can output incorrect truss numbers while appearing to run. The batch algorithm in Section VI additionally assumes that processing one batch edge at a time and iterating k from 2 upward yields the same result as the single-edge theory applied cumulatively; this is plausible but not proved. Since no proof is supplied and no implementation is released, the correctness claim is currently unverified at its core.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the dynamic truss-decomposition problem under edge insertions. It states three theorems (Theorems 1–3) that bound the set of edges whose truss number can increase after an edge insertion, and it uses them to derive two incremental algorithms (HCQTY, a variant of Huang et al., and JK-Inc, an optimized version) plus a batch algorithm (JK-Batch). The authors evaluate the algorithms on two SNAP temporal graphs, reporting up to 250000× average per-edge speedup over the non-incremental baseline of Smith et al. and up to 17.5× batch speedup over JK-Inc.","tokens_in":13680,"tokens_out":5178,"duration_ms":55941,"significance":"If the correctness claims hold, the paper would make a useful contribution: an exact incremental update method with a small candidate set, a first batch algorithm for truss decomposition, and strong empirical speedups on large sparse graphs. The experimental design (temporal edges, multiple graph sizes, comparison with an implementation of Huang et al.) is appropriate, and the paper is honest about cases in which the incremental approach is slower than recomputation. However, the central theoretical claims are not established in the manuscript: Theorems 1–3 are asserted without proofs, Property 1 is informal, and the batch algorithm's correctness is argued only by analogy. No code or pseudocode is provided, so the experiments are not independently reproducible. The current significance is therefore conditional on the omitted proofs and on a precise algorithmic specification.","major_comments":[{"comment":"Theorems 1–3 are the mathematical foundation of the paper, but the text states only that they \"have been rigorously proved, although we do not present them here due to space limitations.\" The incremental algorithm's exploration rule in Section V uses the contrapositive of Theorem 3 to conclude that no edge outside the constructed path can have its K(.) raised to k+1; without a proof of Theorem 3, and of Theorems 1 and 2 on which it depends, the exactness claim is unsupported. Please provide complete proofs, or a detailed proof appendix, for all three theorems; this is load-bearing material, not auxiliary detail.","section":"Section IV"},{"comment":"Property 1 is stated as an informal \"if and only if\" and is then used to justify the cascade pruning rule. Correctness requires two things: (i) a precise definition of the candidate set S produced by Theorem 3 and of the \"relevant support count,\" and (ii) a proof that the particular order in which edges with relevant support count below k-1 are removed does not affect the final pruned set S', or, if order matters, a specification of the order and a proof that the algorithm's order produces the required maximal set. The current text asserts that the cascade \"continues removing the edges ... till the required property holds\" but never proves that the termination state is exactly the set of edges whose truss numbers should increase. This is load-bearing because any counterexample would make both JK-Inc and JK-Batch output incorrect truss numbers.","section":"Section V-C"},{"comment":"The batch algorithm's correctness is argued by analogy: \"Since both the incremental algorithm as well as the batch algorithm check for edges whose K(.) values increase from k to k+1 for all k, the batch algorithm performs at most as many computations as the incremental algorithm.\" This is not a proof. The algorithm initializes all batch edges to K=2 and iterates k upward, but it must be shown that this schedule yields the same final decomposition as applying the single-edge update after each individual insertion. Please provide a formal correctness proof for JK-Batch and a rigorous comparison of the work done; the latter is also needed to support the \"at most as many computations\" claim.","section":"Section VI"}],"minor_comments":[{"comment":"Condition 4 of Theorem 3 should be rewritten with explicit quantifiers; the phrase \"WLOG assume x = u above\" does not fully specify the role of y, the status of the edge (u,y), and the relation between K((u,y)) and K((v,y)). A precise statement is needed because the proof of the contrapositive used in Section V relies on this condition.","section":"Section IV, Theorem 3"},{"comment":"No pseudocode is given for JK-Inc or JK-Batch, and the data structures for maintaining relevant support counts and truss-degree values are not specified. Adding an algorithm listing would substantially improve reproducibility and would make the distinction between the HCQTY and JK-Inc versions verifiable.","section":"Sections V and VI"},{"comment":"The paper reports average speedups and a few runtime plots, but no error bars, medians, or full distributions. Figure 4b shows only five spikes over 1000 insertions, which suggests a very skewed distribution; a few summary statistics such as median and 90th percentile would better support the headline 250000× average speedup.","section":"Section VIII"}],"recommendation":"major_revision","confidential_remarks":"The omission of proofs for Theorems 1–3 is the central issue; for a journal submission I would require a proof appendix regardless of page limits. I would also ask the authors to release the code or provide a detailed pseudocode listing, since the experimental section otherwise cannot be reproduced. The paper should also be checked against later work on incremental truss decomposition, since the arXiv version is from 2019 and the literature may have moved on."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Chris,\n\nQuick take: this is a real algorithmic idea—batch updating a truss decomposition after multiple edge insertions is genuinely new as far as I know—but the correctness of the whole thing rests on theorems the paper does not prove and a pruning property it only states informally. That gap is fixable, and I think the right move is a serious referee, not a desk rejection.\n\nWhat is actually new: the batch algorithm. The single-edge incremental framework is openly derivative of Huang et al., and the authors say so. The JK-Inc optimization—precomputing “truss-degree” counts to shrink the explored set—is a sensible memoization trick, clearly inspired by Sariyuce et al. on k-core. The batch example in Figure 2 makes the redundant-work argument concrete, and the savings logic is easy to follow. The experiments compare against an implementation of Huang et al., not just static recomputation, and they honestly report that JK-Inc can lose on dense graphs because of the memoization overhead. There are no fitted parameters and no circularity in the evaluation.\n\nThe soft spots are all on the correctness side. Section IV says Theorems 1–3 were “rigorously proved” but not presented “due to space limitations.” For load-bearing claims, that does not work. Property 1 is an iff statement about when the explored set S exactly becomes the set of edges whose truss number rises; Section V-C then turns that into a pruning rule based on relevant support counts. The algorithm is exactly as good as that conversion, and no proof is given for it. The batch algorithm additionally assumes that processing one batch edge at a time and moving up one k level at a time gives the same result as cumulative single-edge updates; plausible, but also unproved. No code or data is released, so there is no way to check the implementation independently.\n\nThe experiments are a bit thin: two datasets, only 100 or 1000 inserted edges, and the headline 250000x is an average over updates that are mostly near-zero cost. Medians or percentiles would be much more informative, along with the code. The authors also openly leave batch-size behavior and the parallel variant for future work; fine, but that limits what the paper claims.\n\nWho it is for: people working on dynamic graph algorithms or k-truss community detection. It is a legitimate problem, and the batch contribution deserves referee time. My recommendation: send it out, conditional on complete proofs—at minimum in an appendix or tech report—and ideally a brute-force check against static recomputation on small graphs. If the theorems hold up, the batch result is publishable. Until then, treat it as a promising extended abstract.","headline":"A genuinely new batch update for truss decomposition, but its correctness is asserted rather than proved—worth a serious referee, conditional on proofs and code.","tokens_in":14068,"tokens_out":4666,"would_cite":false,"duration_ms":47869,"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":"The truss decomposition of a graph can be updated exactly after edge insertions by exploring only a small subset of edges.","keywords":["truss decomposition","k-truss","dynamic graphs","incremental algorithm","batch update","streaming algorithm","cohesive subgraphs","triangle counting"],"falsifier":"Construct any connected graph, insert every possible single edge in turn, and compare the updated truss numbers produced by the incremental algorithm against a full recomputation of the truss decomposition: any graph in which some edge's truss number misses the predicted change, or is changed when it should not be, disproves the central claim. The same test can be run on the batch algorithm by inserting pairs or triples of edges whose candidate regions overlap; Property 1 predicts the two results must coincide.","tokens_in":13136,"feed_emoji":"🔺","tokens_out":5512,"duration_ms":48480,"temperature":0.7,"pith_summary":"This paper claims that when a new edge arrives in a graph, the truss decomposition—the assignment to each edge of the largest $k$ such that it lies in a $k$-truss—can be updated exactly without recomputing anything globally. The authors prove that the only edges whose truss number can rise are those reachable, through a path of same-level edges, from a triangle containing the inserted edge, and that each such edge rises by at most one level. On this basis they build an incremental algorithm that explores only this provably sufficient neighborhood and prunes it to the exact set of affected edges. They also give a batch algorithm that processes many insertions together, avoiding redundant work. On a real sparse graph with 10 million edges the incremental update averaged over 250000x faster than recomputing from scratch.","feed_headline":"Streaming algorithm updates truss decomposition 250000x faster","feed_subtitle":"A path-based theory finds exactly which edges can change when a new edge arrives, and makes batch updates faster too.","key_machinery":"The load-bearing mechanism is Theorem 3's path characterization together with the peel-by-relevant-support-count pruning. The relevant support count of an edge $e'$ within a candidate set $S$ is the number of triangles containing $e'$ whose two other edges both have truss number at least $k$; an edge can only move from $k$ to $k+1$ if this count is at least $k-1$. The algorithm builds the candidate set $S$ by walking paths of same-truss-number edges from each triangle of the inserted edge, then removes low-count edges in a cascade, updating the counts of their neighbors, until every remaining edge satisfies the threshold. This is exactly the operation the paper calls Algorithm X(k), and it is shown to be independent across different values of $k$, which is what lets the batch algorithm promote all affected edges at one level before moving to the next.","core_discovery":"The central claim is that the change set induced by inserting an edge $e=(u,v)$ is tightly contained: no edge's truss number increases by more than 1 (Theorem 1), and any edge whose truss number rises from $k$ to $k+1$ lies on a path of such rising edges that ends in a triangle with $e$ (Theorems 2 and 3). The algorithms therefore need only explore, for each $k$, the connected region of edges with truss number $k$ reachable from the triangles of $e$, and then peel away those whose relevant support count—the number of triangles they form using edges of truss number at least $k$—falls below $k-1$. The paper asserts these structural claims, calls the pruning rule Property 1, and argues it exactly reproduces the set of edges whose truss numbers increase. It reports that the optimized incremental version dominates the prior incremental algorithm on sparse graphs, and that the batch version always matches or beats repeated incremental updates in experiments, with up to 17.5x speedup.","pith_inferences":["Beyond the paper: the path-based containment argument is not specific to truss numbers; the same \"affected region grows along same-label edges\" pattern should transfer to other triangle-count-based indices, such as maintaining triangle counts or k-plexes under insertions.","Beyond the paper: the batch algorithm's per-level promotion suggests a natural GPU-style parallelization in which all candidate sets for a given $k$ are processed in one kernel, a design the authors mention but do not implement.","Beyond the paper: because the speedup collapses on dense graphs, a practical system could measure the size of the explored set $S$ and fall back to static recomputation when $S$ is a large fraction of the graph; the paper mentions this hybrid strategy as future work but offers no decision rule."],"forward_implications":["Dynamic graphs can maintain their truss decomposition continuously, with update cost proportional to the size of the changed region rather than the whole graph.","Batch edge insertions can be processed as one pass per truss level, so edges that jointly form a higher truss are promoted in a single sweep instead of once per inserted edge.","The level-by-level independence of Algorithm X(k) opens a clear path to a parallel implementation, which the paper does not itself provide.","The same theory is stated to extend to edge removals, so streaming deletion of edges could be handled with the same path-based machinery.","On large sparse real-world graphs the update is over 250000 times faster on average than recomputing from scratch per insertion."],"supporting_citations":[{"why":"Supplies the prior incremental truss algorithm that this paper builds on and compares against, providing the baseline candidate-exploration method and the initial HCQTY version.","marker":"[12]"},{"why":"Streaming k-core decomposition work that motivates the truss-degree optimization used in the improved JK-Inc algorithm.","marker":"[19]"},{"why":"The optimized parallel truss decomposition used as the non-incremental baseline for speedup measurements.","marker":"[10]"},{"why":"Provides the SNAP datasets (stackoverflow and email) that supply the temporal edge streams used in evaluation.","marker":"[20]"},{"why":"Gives the original definition of k-truss, which the paper's notion of truss decomposition extends.","marker":"[3]"}],"fun_headline_variants":["Theory pinpoints exact edge changes in truss decomposition","Truss decomposition: exact change set enables 250000x speedup","Streaming truss decomposition: 250000x faster edge updates","Incremental truss decomposition speeds up 250000x","Batch updates beat incremental for truss decomposition"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Correctness rests on the unproved structural claims (Theorems 1-3 and the informal Property 1) that the path exploration plus the relevant-support-count pruning rule exactly identifies—no more and no fewer—the edges whose truss number should increase after an insertion.","fun_headline_variants_meta":{"raw":{"variants":["Theory pinpoints exact edge changes in truss decomposition","Truss decomposition: exact change set enables 250000x speedup","Streaming truss decomposition: 250000x faster edge updates","Incremental truss decomposition speeds up 250000x","Batch updates beat incremental for truss decomposition"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00146,"raw_usage":{"total_tokens":5890,"prompt_tokens":972,"completion_tokens":4918,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":588,"completion_tokens_details":{"reasoning_tokens":4835}},"tokens_in":588,"tokens_out":4918,"duration_ms":31615,"temperature":1.0,"reasoning_tokens":4835,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:39:42.927972+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct any connected graph, insert every possible single edge in turn, and compare the updated truss numbers produced by the incremental algorithm against a full recomputation of the truss decomposition: any graph in which some edge's truss number misses the predicted change, or is changed when it should not be, disproves the central claim. The same test can be run on the batch algorithm by inserting pairs or triples of edges whose candidate regions overlap; Property 1 predicts the two results must coincide.","supporting_citations":[{"cited_title":"Querying k- truss community in large and dynamic graphs,","cited_arxiv_id":null,"evidence_quote":"Supplies the prior incremental truss algorithm that this paper builds on and compares against, providing the baseline candidate-exploration method and the initial HCQTY version."},{"cited_title":"Streaming algorithms for k-core decomposition,","cited_arxiv_id":null,"evidence_quote":"Streaming k-core decomposition work that motivates the truss-degree optimization used in the improved JK-Inc algorithm."},{"cited_title":"Truss decomposition on shared-memory parallel systems,","cited_arxiv_id":null,"evidence_quote":"The optimized parallel truss decomposition used as the non-incremental baseline for speedup measurements."},{"cited_title":"Snap: A general-purpose network analysis and graph-mining library,","cited_arxiv_id":null,"evidence_quote":"Provides the SNAP datasets (stackoverflow and email) that supply the temporal edge streams used in evaluation."},{"cited_title":"Trusses: Cohesive subgraphs for social network analysis,","cited_arxiv_id":null,"evidence_quote":"Gives the original definition of k-truss, which the paper's notion of truss decomposition extends."}],"review_version":1}