REVIEW 3 major objections 3 minor 20 references
Streaming and Batch Algorithms for Truss Decomposition
T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The truss decomposition of a graph can be updated exactly after edge insertions by exploring only a small subset of edges.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section IV] 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 V-C] 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 VI] 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.
minor comments (3)
- [Section IV, Theorem 3] 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.
- [Sections V and VI] 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 VIII] 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.
Circularity Check
No circularity found: the algorithm's derivation is self-contained; the unproved theorems are a verification gap, not a circular step.
full rationale
I walked the claimed derivation chain: Theorem 3 bounds the set S of k-truss edges that can change after inserting edge e; Algorithm X(k) explores S and prunes it to S' using Property 1 via the relevant-support-count cascade; the batch algorithm repeats this per k. None of these steps is defined in terms of the output it is supposed to produce. The paper fits no parameters to target data and then calls them predictions; the speedup numbers are measured runtimes against a from-scratch recomputation and against an implementation of Huang et al. The only self-citation is Smith et al. [10], used as the non-incremental baseline; it is a benchmark implementation, not a premise of the correctness argument, so it is not load-bearing. Theorems 1-3 are stated to be 'rigorously proved' but the proofs are omitted, and Property 1 is asserted informally, so the central correctness claim is not independently verifiable from the paper alone; that is an evidence gap, not circularity. No equation or algorithmic output reduces by construction to an input, so the paper receives score 0.
Assumptions & free parameters
assumptions (5)
- domain assumption G is an undirected, unweighted simple graph and truss decomposition is defined by triangle support (Section II).
- ad hoc to paper Theorem 1: inserting an edge increases any edge's truss number by at most 1.
- ad hoc to paper Theorem 2 and 3: any edge promoted from k to k+1 forms a triangle with the inserted edge or with another promoted edge; all promoted edges lie in a path satisfying stated conditions.
- ad hoc to paper Property 1: a candidate set S can be promoted iff it together with a set Q of higher-K edges forms a (k+1)-truss; the cascade pruning by relevant support finds the maximal such S.
- ad hoc to paper The batch algorithm's assignment of initial K=2 to all batch edges and iterative raising without re-inserting individual edges yields the same final decomposition.
Cite this review
Pith. "Pith review of Streaming and Batch Algorithms for Truss Decomposition." pith.science (2026). https://pith.science/paper/JI75O2XG
@misc{pith2026190810550,
author = {Pith},
title = {Pith review of: Streaming and Batch Algorithms for Truss Decomposition},
year = {2026},
howpublished = {\url{https://pith.science/paper/JI75O2XG}},
note = {Machine review of arXiv:1908.10550}
}
read the original abstract
Truss decomposition is a method used to analyze large sparse graphs in order to identify successively better connected subgraphs. Since in many domains the underlying graph changes over time, its associated truss decomposition needs to be updated as well. This work focuses on the problem of incrementally updating an existing truss decomposition and makes the following three significant contributions. First, it presents a theory that identifies how the truss decomposition can change as new edges get added. Second, it develops an efficient incremental algorithm that incorporates various optimizations to update the truss decomposition after every edge addition. These optimizations are designed to reduce the number of edges that are explored by the algorithm. Third, it extends this algorithm to batch updates (i.e., where the truss decomposition needs to be updated after a set of edges are added), which reduces the overall computations that need to be performed. We evaluated the performance of our algorithms on real-world datasets. Our incremental algorithm achieves over 250000x average speedup for inserting an edge in a graph with 10 million edges relative to the non-incremental algorithm. Further, our experiments on batch updates show that our batch algorithm consistently performs better than the incremental algorithm.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Community detection in graphs,
S. Fortunato, “Community detection in graphs,” Physics reports , vol. 486, no. 3-5, pp. 75–174, 2010
2010
-
[2]
A graph-theoretic algorithm for comparative modeling of protein structure,
R. Samudrala and J. Moult, “A graph-theoretic algorithm for comparative modeling of protein structure,” Journal of molecular biology , vol. 279, no. 1, pp. 287–302, 1998
work page 1998
-
[3]
Trusses: Cohesive subgraphs for social network analysis,
J. Cohen, “Trusses: Cohesive subgraphs for social network analysis,” National security agency technical report , vol. 16, pp. 3–1, 2008
work page 2008
-
[4]
Extracting communities from complex networks by the k-dense method,
K. Saito, T. Yamada, and K. Kazama, “Extracting communities from complex networks by the k-dense method,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , vol. 91, no. 11, pp. 3304–3311, 2008
work page 2008
-
[5]
Network clustering via clique relaxations: A community based,
A. Verma and S. Butenko, “Network clustering via clique relaxations: A community based,” Graph Partitioning and Graph Clustering , vol. 588, p. 129, 2013
work page 2013
-
[6]
Approximate closest community search in networks,
X. Huang, L. V . Lakshmanan, J. X. Yu, and H. Cheng, “Approximate closest community search in networks,” Proceedings of the VLDB Endowment, vol. 9, no. 4, pp. 276–287, 2015
work page 2015
-
[7]
Large scale networks fingerprinting and visualization using the k-core decomposition,
J. I. Alvarez-Hamelin, L. Dall’Asta, A. Barrat, and A. Vespignani, “Large scale networks fingerprinting and visualization using the k-core decomposition,” in Advances in neural information processing systems , 2006, pp. 41–50
work page 2006
-
[8]
Truss decomposition in massive networks,
J. Wang and J. Cheng, “Truss decomposition in massive networks,” Proceedings of the VLDB Endowment , vol. 5, no. 9, pp. 812–823, 2012
work page 2012
Show all 20 references
-
[9]
Distributed algorithms for k-truss decomposition,
P.-L. Chen, C.-K. Chou, and M.-S. Chen, “Distributed algorithms for k-truss decomposition,” in 2014 IEEE International Conference on Big Data (Big Data) . IEEE, 2014, pp. 471–480
2014
-
[10]
Truss decomposition on shared-memory parallel systems,
S. Smith, X. Liu, N. K. Ahmed, A. S. Tom, F. Petrini, and G. Karypis, “Truss decomposition on shared-memory parallel systems,” in 2017 IEEE High Performance Extreme Computing Conference (HPEC) . IEEE, 2017, pp. 1–6
2017
-
[11]
Parallel k-truss decomposition on multicore systems,
H. Kabir and K. Madduri, “Parallel k-truss decomposition on multicore systems,” in 2017 IEEE High Performance Extreme Computing Confer- ence (HPEC) . IEEE, 2017, pp. 1–7
2017
-
[12]
Querying k- truss community in large and dynamic graphs,
X. Huang, H. Cheng, L. Qin, W. Tian, and J. X. Yu, “Querying k- truss community in large and dynamic graphs,” in Proceedings of the 2014 ACM SIGMOD international conference on Management of data . ACM, 2014, pp. 1311–1322
2014
-
[13]
Algorithm 457: finding all cliques of an undirected graph,
C. Bron and J. Kerbosch, “Algorithm 457: finding all cliques of an undirected graph,” Communications of the ACM , vol. 16, no. 9, pp. 575–577, 1973
1973
-
[14]
Connectivity and generalized cliques in sociometric group structure,
R. D. Luce, “Connectivity and generalized cliques in sociometric group structure,” Psychometrika, vol. 15, no. 2, pp. 169–190, 1950
1950
-
[15]
Cliques, clubs and clans,
R. J. Mokken, “Cliques, clubs and clans,” Quality & Quantity , vol. 13, no. 2, pp. 161–173, 1979
1979
-
[16]
Extracting analyzing and visualizing triangle k-core motifs within networks,
Y . Zhang and S. Parthasarathy, “Extracting analyzing and visualizing triangle k-core motifs within networks,” in2012 IEEE 28th International Conference on Data Engineering . IEEE, 2012, pp. 1049–1060
2012
-
[17]
An o (m) algorithm for cores decompo- sition of networks,
V . Batagelj and M. Zaversnik, “An o (m) algorithm for cores decompo- sition of networks,” arXiv preprint cs/0310049 , 2003
2003 arXiv
-
[18]
Graph twiddling in a mapreduce world,
J. Cohen, “Graph twiddling in a mapreduce world,” Computing in Science & Engineering , vol. 11, no. 4, p. 29, 2009
2009
-
[19]
Streaming algorithms for k-core decomposition,
A. E. Sar ´ıy¨uce, B. Gedik, G. Jacques-Silva, K.-L. Wu, and ¨U. V . C ¸ ataly¨urek, “Streaming algorithms for k-core decomposition,” Proceed- ings of the VLDB Endowment , vol. 6, no. 6, pp. 433–444, 2013
2013
-
[20]
Snap: A general-purpose network analysis and graph-mining library,
J. Leskovec and R. Sosi ˇc, “Snap: A general-purpose network analysis and graph-mining library,”ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 1, p. 1, 2016
2016
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.