Pith. sign in

REVIEW 2 major objections 4 minor 28 references

Dynamic Structural Clustering Unleashed: Flexible Similarities, Versatile Updates and for All Parameters

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read One algorithm, VD-STAR, maintains approximate structural clustering under arbitrary edge updates in O(log n) amortized expected time per update while supporting Jaccard, Cosine, and Dice similarities.

desk verdict A real improvement over BOTBIN — O(log n) amortized per-update for Jaccard/Cosine/Dice under arbitrary updates — with one proof gap in Claim 1 that a referee should push on. read the letter →

arxiv 2411.13817 v1 pith:JTIJLTTJ submitted 2024-11-21 cs.DS

Zhuowei Zhao , Junhao Gan , Boyu Ruan , Zhifeng Bao , Jianzhong Qi , Sibo Wang This is my paper · ORCID
classification cs.DS MSC 68W2068W2568R10
keywords dynamicstructuralclusteringupdateaffordabilityJaccardsimilarityCosineDicerho-absoluteapproximationgraphamortizedanalysis
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that a single algorithm, VD-STAR, can maintain approximate structural clustering of a graph under arbitrary edge insertions and deletions, and can answer queries on the fly for any clustering parameters $\varepsilon$ and $\mu$. The headline gain is update time: $O(\log n)$ amortized in expectation per update, with no assumption that updates are uniformly random, improving on the previous approximate method's $O(\log^2 n)$ expected bound that held only for random updates. The algorithm works for all three standard similarity measures, Jaccard, Cosine, and Dice, whereas the previous approximate method supported only Jaccard. A reader should care because dynamic graphs in social networks, web data, and biological networks need their clusterings refreshed continuously, and the paper supplies both a formal quality guarantee and experiments showing high accuracy on large real graphs.

What carries the argument

The load-bearing mechanism is update affordability: after an edge's similarity is estimated, the number of affecting updates that can occur before the estimate might leave the $\rho$-absolute-approximation window is bounded below by $\tau(u,v) \ge \frac{1}{4}\rho^2 n_v$. Rather than tracking each edge's remaining budget individually, VD-STAR assigns each edge a power-of-two quota $q(u,v) = \frac{1}{4}\lfloor \tau(u,v) \rfloor_2$ and stores the edge in a bucket of that size in a sorted linked bucket list attached to each endpoint. Each vertex keeps a counter of affecting updates; when the counter crosses a bucket's power-of-two threshold twice, the bucket is scanned and edges whose entries are visited a second time are reported invalid and their similarities are recomputed from samples. The sampling estimator draws from the union of the two inclusive neighborhoods and converts the sample into a Jaccard, Cosine, or Dice value, with sample size set by a standard concentration inequality.

What would settle it

Build a graph in which one edge $(u,v)$ has small $n_v$ and repeatedly insert edges that add common neighbors to both $u$ and $v$; measure the exact Jaccard similarity after $\frac{1}{4}\rho^2 n_v$ such affecting updates. If it has risen by more than $\rho$, Claim 1 is false and the $\rho$-absolute-approximation guarantee of VD-STAR fails in that scenario. A complementary test is to run adversarial toggle sequences on high-degree vertices and check whether the fraction of mislabeled edges exceeds the $\rho$ bound before any recomputation is triggered.

Watch

Extended reading notes

Core claim

The central claim is that a $\rho$-absolute-approximate clustering result can be maintained for any $\varepsilon$ and $\mu$ given on the fly, with probability at least $1 - 1/n$, under arbitrary edge updates, for Jaccard, Cosine, and Dice similarities. The per-update cost is $O(\log n)$ amortized in expectation and the space is $O(n + m)$. The algorithm keeps a $\Delta$-Table for core finding, as BOTBIN does, and replaces the similarity-maintenance layer with a bucket scheme that identifies stale edges by update-affordability quotas instead of recomputing all affected edges. The authors prove that every edge can tolerate at least $\frac{1}{4}\rho^2 n_v$ affecting updates before its $\frac{1}{2}\rho$-approximate similarity can drift out of the $\rho$ window, for all three similarities, and that the bucket scheme reports each edge before its quota is consumed.

Load-bearing premise

The load-bearing premise is that for every edge the true similarity drifts slowly enough that it cannot move by more than the allowed error window before the bucket monitoring it fires; if an adversarial run of updates makes the similarity move faster than this bound, stale estimates could slip outside the guarantee and the whole approximation argument collapses.

Editorial extensions

If this is right

  • A practitioner can answer structural-clustering queries for any $\varepsilon$ and $\mu$ on the fly while each edge update costs $O(\log n)$ amortized expected time, independent of maximum degree, using $O(n+m)$ space.
  • Because the bound holds without a random-update assumption, the algorithm stays fast on skewed real-world workloads where most updates touch a few popular vertices.
  • The same index works for Jaccard, Cosine, and Dice similarities, so applications no longer need separate dynamic clustering systems per similarity measure.
  • Every edge is guaranteed to be re-estimated before its similarity can leave the approximation window, which gives a formal quality guarantee, not just a heuristic, for the returned clusters.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: if the drift bound in Claim 1 is tight, the same bucket-quota scheme may generalize to other similarity measures whose change under one affecting update can be bounded by a function of the smaller inclusive degree.
  • Editorial extension: the framework's separation of EdgeSimStr and CoreFindStr suggests that other sampling estimators or other core-finding tables could be swapped in to trade query time against update time.
  • Editorial extension: the power-of-two quota makes edges with very small degrees recompute often; using a finer bucket granularity or a different quota shape might lower update time in practice without changing the asymptotic bound.
  • Editorial extension: the $O(\log n)$ bound relies on hash-table randomness; a deterministic data structure with the same amortized guarantee, if one exists, would make the result fully deterministic except for the sampling randomness.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes VD-STAR, a dynamic structural clustering algorithm that supports Jaccard, Cosine, and Dice similarity measures, answers queries for on-the-fly parameters ε and μ, and processes arbitrary edge insertions/deletions. The algorithm maintains approximate similarities using a sampling estimator and a bucket-based update-affordability mechanism. The main theoretical claim, Theorem 1, states that VD-STAR returns a ρ-absolute-approximate clustering result with probability at least 1 - 1/n per query, handles each update in O(log n) amortized expected time, and uses O(n + m) space, improving on BOTBIN's O(log² n) expected bound under a random-update assumption. The paper also reports experiments on nine real-world graphs, with update-time speedups over prior methods.

Significance. If Theorem 1 is correct, the paper makes a solid theoretical contribution: it removes BOTBIN's random-update assumption, reduces the per-update bound from O(log² n) expected to O(log n) amortized in expectation, and extends support from Jaccard to Cosine and Dice similarities. The sampling estimator in Lemma 1 and the unified algorithm framework are clean and useful. The paper also provides source code and extensive experiments on datasets with up to roughly 1.9 billion edges, which is a practical strength. However, the proof of the key update-affordability claim, Claim 1, has a genuine gap for mixed update sequences, and the amortized charging argument in Section 4.2 is compressed to the point of being incomplete. These issues are fixable, but they are load-bearing for Theorem 1.

major comments (2)
  1. [§4.4, Claim 1] The proof of Claim 1 for Case 2 asserts that affecting updates that increase I(u,v) are the most effective way to increase the exact similarity, and then 'without loss of generality' assumes that n_u and n_v are increased by t-b and b. This omits non-common deletions, which for all three similarity measures also increase the exact similarity: for Cosine and Dice, deleting a non-common neighbor of v decreases n_v while leaving I(u,v) fixed, which increases the similarity by shrinking the denominator. The per-step ordering in Section 4.4 does not by itself imply that a t-step mixed sequence is dominated by t consecutive common insertions, because a non-common deletion can shrink the denominator and amplify the effect of later common insertions. Since Claim 1 is the only place where the update affordability τ is established, and Lemma 2, Theorem 2, and the amortized bound in Section 4.2 all inherit from it, the proof needs a complete analysis of mixed update sequences for Jaccard, Cosine, and Dice, for example via an invariant on the non-common excess n_u + n_v - 2I(u,v). As written, Theorem 1 is not fully supported.
  2. [§4.2, Lemma 5] The proof of the amortized per-update bound states that the bucket-scanning cost of Algorithm 4 is O(K+1), where K is the number of checked buckets. This is not correct as written: when a bucket satisfies the condition on Line 4, Algorithm 4 iterates over every entry in that bucket, so the scanning cost is proportional to the total number of visited entries, not to the number of checked buckets. A bucket can contain many edges, and the proof does not charge the per-entry scanning cost. The argument can likely be repaired by charging O(1) per visited entry to the corresponding edge's maintenance cost ℓ(u,w), but this step is missing and the O(log n) amortized bound is not established by the text as it stands.
minor comments (4)
  1. [Algorithm 5, Line 6] The probability for z=0 is printed as n_x/(n_x+n_y); it should be n_y/(n_x+n_y).
  2. [§4.2, Fact 4] The O(1) expected time for the sorted bucket-list operations is imported from the unpublished preprint [24]. Please include a proof of Fact 4 or cite a peer-reviewed version, since the main per-update bound relies on it.
  3. [Throughout] There are several typos and spacing issues, e.g., 'udpate' in Section 2.1, 'date structures' in Section 4.3, and 'onas-skitter' in Section 6.2.1. A careful proofreading pass is needed.
  4. [§3, initial paragraph] The discussion of M ≤ n0² and rebuilding from scratch assumes that n0 is the vertex count at the current moment, but the abstract mentions vertex updates as well as edge updates. The problem definition in Definition 1 only formalizes edge updates; please clarify the status of vertex insertions and deletions.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorem is derived from explicit similarity formulas, standard concentration bounds, and independent auxiliary data-structure results.

full rationale

The derivation chain is self-contained. Claim 1, the key lower bound on update affordability, is proved directly from the algebraic definitions of Jaccard, Cosine, and Dice similarity together with worst-case update accounting, extending the prior Jaccard-only argument of Ruan et al. rather than assuming the target result. Lemma 1 is a standard Hoeffding bound applied to an explicit estimator whose expectation is identified as 2I(u,v)/(nu+nv); the transformations to Jaccard, Cosine, and Dice are explicit equations, not fitted parameters. Fact 1 is reproduced with a proof in the paper, and Fact 4, though from a co-authored paper, is a separate auxiliary data-structure result about maintaining sorted bucket lists and is used only to bound costEI+costED; it does not encode the clustering approximation claim. The experimental quality numbers are measurements against exact clustering or ground truth, not predictions forced by a fitted input. The main correctness concern raised by the skeptical reading—that the proof of Claim 1 in Section 4.4 asserts without derivation that pure common insertions/deletions are the worst case and does not analyze arbitrary mixed update sequences—is a potential proof gap, not circularity, because it concerns whether the stated bound is proven, not whether the result is derived from its own assumptions. No step in the paper reduces a prediction to a definition, a fit, or a self-citation chain.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central contribution is the bucketing scheme and the affordability lower bound; these are derived in-paper from definitions. The paper relies on two external facts (the sandwich guarantee and the bucket-list data structure) plus the standard Hoeffding bound. No fitted free parameters are introduced; rho, mu, and Delta are user-specified approximation and quality parameters. No new entities are postulated beyond internal data-structure components.

assumptions (4)
  • standard math Fact 1: a rho-absolute-approximation sandwiches the exact clustering result between the exact results for parameters epsilon+rho and epsilon-rho.
    Proven in Section 2.1 from monotonicity of core status; used to justify the quality guarantee of the approximate output.
  • standard math Fact 4: a sorted linked list of buckets supports insertion, deletion, and predecessor queries in O(1) expected time.
    Cited to reference [24], a co-authored paper; the bucket-list operations in Algorithm 4 rely on this result and it is not re-proven here.
  • standard math Hoeffding's inequality is used to set the sample size L in Algorithm 5.
    Classical tail bound; used in the proof of Lemma 1 to guarantee the 1/2 rho approximation error with high probability.
  • domain assumption Vertex updates are reduced to edge insertions and deletions.
    The abstract advertises updates of edges and vertices, but Definition 1 and all algorithms formalize only edge insertions and deletions; no explicit vertex-update procedure is given.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dynamic Structural Clustering Unleashed: Flexible Similarities, Versatile Updates and for All Parameters." pith.science (2026). https://pith.science/paper/JTIJLTTJ

@misc{pith2026241113817,
  author       = {Pith},
  title        = {Pith review of: Dynamic Structural Clustering Unleashed: Flexible Similarities, Versatile Updates and for All Parameters},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JTIJLTTJ}},
  note         = {Machine review of arXiv:2411.13817}
}
abstract

We study structural clustering on graphs in dynamic scenarios, where the graphs can be updated by arbitrary insertions or deletions of edges/vertices. The goal is to efficiently compute structural clustering results for any clustering parameters $\epsilon$ and $\mu$ given on the fly, for arbitrary graph update patterns, and for all typical similarity measurements. Specifically, we adopt the idea of update affordability and propose an a-lot-simpler yet more efficient (both theoretically and practically) algorithm (than state of the art), named VD-STAR to handle graph updates. First, with a theoretical clustering result quality guarantee, VD-STAR can output high-quality clustering results with up to 99.9% accuracy. Second, our VD-STAR is easy to implement as it just needs to maintain certain sorted linked lists and hash tables, and hence, effectively enhances its deployment in practice. Third and most importantly, by careful analysis, VD-STAR improves the per-update time bound of the state-of-the-art from $O(\log^2 n)$ expected with certain update pattern assumption to $O(\log n)$ amortized in expectation without any update pattern assumption. We further design two variants of VD-STAR to enhance its empirical performance. Experimental results show that our algorithms consistently outperform the state-of-the-art competitors by up to 9,315 times in update time across nine real datasets.

Figures

Figures reproduced from arXiv: 2411.13817 by the authors.

Figure 1
Figure 1. A Structural Clustering Example (ε = 0.5 and µ = 5) [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Index schema examples The Implementation of EdgeSimStr. For each vertex u ∈ V , the EdgeSimStr, maintain du, the degree of u, and I(u, x), the intersection size of N[u] and N[x], for each neighbor x ∈ N(u). And the functions are implemented as follows: • update((u, v), op): maintain the counters du and I(u, x) for each x ∈ N(u) according to the given update. Perform the same maintenance symmetrically for the end-ver… view at source ↗
Figure 3
Figure 3. A Running Example of Our EdgeSimStr 10 [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Update processing performance results • degree-degree (DD): Vertex u is chosen as in DR; vertex v is chosen from the vertices not yet linked to u with dv 2m probability. By default, we set η = 1 10 . For each dataset and a configuration of η and update generation strat…
Figure 8
Figure 8. Figure 8: Query processing performance results Ours Ours-NoT Ours- T GS*-Index Google Topcats Pokec Skitter Talk Orkut LiveJournal Friendster Web 10 1 10 2 10 3 10 4 10 5 Average update time (×10 6 second) (a) Cosine Google Topcats Pokec Skitter Talk Orkut LiveJournal Friendster…
Figure 9
Figure 9. Figure 9: Average update running time on Cosine and Dice [PITH_FULL_IMAGE:figures/full_fig_p022_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 25 canonical work pages

  1. [27]

    Source code and technical report, 2024

    Zhuowei Zhao. Source code and technical report, 2024

    work page 2024

  2. [1]

    Mark E. J. Newman. Finding and evaluating community structure in networks.Physical Review E, 69(26113):1–16, 2004

    work page 2004

  3. [2]

    A spectral clustering approach to finding communities in graphs

    Scott White and Padhraic Smyth. A spectral clustering approach to finding communities in graphs. In SDM, pages 274–285, 2005

    work page 2005

  4. [3]

    Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, and Thomas A. J. Schweiger. Scan: a structural clustering algorithm for networks. In KDD, pages 824–833, 2007

    work page 2007

  5. [4]

    Effective indexing for dynamic structural graph clustering

    Fangyuan Zhang and Sibo Wang. Effective indexing for dynamic structural graph clustering. Proceedings of the VLDB Endowment, 15(11):2908–2920, 2022

    work page 2022

  6. [5]

    Dynamic structural clustering on graphs

    Boyu Ruan, Junhao Gan, Hao Wu, and Anthony Wirth. Dynamic structural clustering on graphs. In SIGMOD, pages 1491–1503, 2021

    work page 2021

  7. [6]

    Efficient structural graph clustering: An index-based approach

    Dong Wen, Lu Qin, Ying Zhang, Lijun Chang, and Xuemin Lin. Efficient structural graph clustering: An index-based approach. Proceedings of the VLDB Endowment, 11(3):243–255, 2017

    work page 2017

  8. [7]

    Harris, Feng Qian, Weigong Ge, Hong Fang, Xiaowei Xu, and Weida Tong

    Yijun Ding, Minjun Chen, Zhichao Liu, Don Ding, Yanbin Ye, Min Zhang, Reagan Kelly, Li Guo, Zhenqiang Su, Stephen C. Harris, Feng Qian, Weigong Ge, Hong Fang, Xiaowei Xu, and Weida Tong. atbionet–an integrated network analysis tool for genomics and biomarker discovery. BMC Genomics, 13:1–12, 2012

    work page 2012

Show all 28 references
  1. [8]

    Translating clinical findings into knowledge in drug safety evaluation-drug induced liver injury prediction system (dilips)

    Zhichao Liu, Qiang Shi, Don Ding, Reagan Kelly, Hong Fang, and Weida Tong. Translating clinical findings into knowledge in drug safety evaluation-drug induced liver injury prediction system (dilips). PLoS Computational Biology, 7(12):e1002310, 2011

    2011

  2. [9]

    Constructing a robust protein-protein interaction network by integrating multiple public databases

    Venkata-Swamy Martha, Zhichao Liu, Li Guo, Zhenqiang Su, Yanbin Ye, Hong Fang, Don Ding, Weida Tong, and Xiaowei Xu. Constructing a robust protein-protein interaction network by integrating multiple public databases. BMC Bioinformatics, 12(Suppl 10):S7, 2011

    2011

  3. [10]

    Linkscan: Overlapping community detection using the link-space transformation

    Sungsu Lim, Seungwoo Ryu, Sejeong Kwon, Kyomin Jung, and Jae-Gil Lee. Linkscan: Overlapping community detection using the link-space transformation. In ICDE, pages 292–303, 2014

    2014

  4. [11]

    Community detection in social media: Performance and application considerations

    Symeon Papadopoulos, Yiannis Kompatsiaris, Athena Vakali, and Ploutarchos Spyridonos. Community detection in social media: Performance and application considerations. Data Mining and Knowledge Discovery, 24:515–554, 2012

    2012

  5. [12]

    Community detection in graphs

    Santo Fortunato. Community detection in graphs. Physics Reports, 486(3-5):75–174, 2010

    2010

  6. [13]

    Leveraging collective intelligence through community detection in tag networks

    Symeon Papadopoulos, Yiannis Kompatsiaris, and Athena Vakali. Leveraging collective intelligence through community detection in tag networks. In Workshop on Collective Knowledge Capturing and Representation, 2009

    2009

  7. [14]

    A graph-based clustering scheme for identifying related tags in folksonomies

    Symeon Papadopoulos, Yiannis Kompatsiaris, and Athena Vakali. A graph-based clustering scheme for identifying related tags in folksonomies. In International Conference on Data Warehousing and Knowledge Discovery, pages 65–76, 2010

    2010

  8. [15]

    Clustering blockchain data

    Sudarshan S Chawathe. Clustering blockchain data. Clustering Methods for Big Data Analytics: Techniques, Toolboxes and Applications, pages 43–72, 2019

    2019

  9. [16]

    Ctb-pki: Clustering and trust enabled blockchain based pki system for efficient communication in p2p network

    Amrutanshu Panigrahi, Ajit Kumar Nayak, Rourab Paul, Bibhuprasad Sahu, and Shashi Kant. Ctb-pki: Clustering and trust enabled blockchain based pki system for efficient communication in p2p network. IEEE Access, 10:124277–124290, 2022

    2022

  10. [17]

    A structural-clustering based active learning for graph neural networks

    Ricky Maulana Fajri, Yulong Pei, Lu Yin, and Mykola Pechenizkiy. A structural-clustering based active learning for graph neural networks. In International Symposium on Intelligent Data Analysis, pages 28–40, 2024

    2024

  11. [18]

    Self-supervised heterogeneous graph pre-training based on structural clustering

    Yaming Yang, Ziyu Guan, Zhe Wang, Wei Zhao, Cai Xu, Weigang Lu, and Jianbin Huang. Self-supervised heterogeneous graph pre-training based on structural clustering. In NeurIPS, pages 16962–16974, 2022

    2022

  12. [19]

    pscan: Fast and exact structural graph clustering

    Lijun Chang, Wei Li, Lu Qin, Wenjie Zhang, and Shiyu Yang. pscan: Fast and exact structural graph clustering. IEEE Transactions on Knowledge and Data Engineering, 29(2):387–401, 2017

    2017

  13. [20]

    Algorithms for distributed functional monitoring

    Graham Cormode, Shanmugavelayutham Muthukrishnan, and Ke Yi. Algorithms for distributed functional monitoring. ACM Transactions on Algorithms, 7(2):1–20, 2011

    2011

  14. [21]

    Randomized algorithms for tracking distributed count, frequencies, and ranks

    Zengfeng Huang, Ke Yi, and Qin Zhang. Randomized algorithms for tracking distributed count, frequencies, and ranks. In PODS, pages 295–306, 2012

    2012

  15. [22]

    Communication-efficient distributed monitoring of thresholded counts

    Ram Keralapura, Graham Cormode, and Jeyashankher Ramamirtham. Communication-efficient distributed monitoring of thresholded counts. In SIGMOD, pages 289–300, 2006. 24

    2006

  16. [23]

    Probability inequalities for sums of bounded random variables

    Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963

    1963

  17. [24]

    Optimal dynamic parame- terized subset sampling

    Junhao Gan, Seeun William Umboh, Hanzhi Wang, Anthony Wirth, and Zhuo Zhang. Optimal dynamic parame- terized subset sampling. arXiv preprint arXiv:2409.18036, 2024

    2024 arXiv

  18. [25]

    SNAP Datasets: Stanford large network dataset collection

    Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.sta nford.edu/data, June 2014

    2014

  19. [26]

    Rossi and Nesreen K

    Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015

    2015

  20. [28]

    Comparing partitions

    Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of Classification, 2:193–218, 1985. 25

    1985

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.