{"id":"b18bc64b-1ed3-4886-ba6a-01e6137f63ed","arxiv_id":"2411.13817","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A dynamic structural clustering algorithm achieves O(log n) amortized expected update time for Jaccard, Cosine, and Dice similarities under arbitrary edge updates.","lead":"VD-STAR is a new algorithm that keeps structural clustering results up to date on graphs that change over time, supporting Jaccard, Cosine, and Dice similarities and any query thresholds. It tightens the guaranteed per-update cost from a squared-logarithmic bound to a logarithmic bound and reports speedups of up to 9,315 times on real-world networks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Claim 1 (§4.4) asserts without derivation that pure common insertions/deletions are the worst case for all three similarities, then bounds only those pure sequences; arbitrary mixed update sequences—including non-common deletions that shrink the denominator—are not analyzed, so the…","rationale":"After reading the full construction, the unified framework, bucket quotas, and charging argument are coherent conditional on Claim 1. The sampling estimator is unbiased for all three similarities and the Hoeffding/Lemma 1 bounds check out. The mechanical issues the reader noted—unlocatable code, undefined vertex updates, and undefined bucket index when τ < 4—are real but addressable and do not by themselves invalidate the asymptotic theorem. I focus on Claim 1 because the theorem's novelty (arbitrary update patterns at O(log n) amortized expected) collapses if τ can be smaller than the claimed lower bound for a mixed adversarial sequence. My concern is not that I have a counterexample; it is that the proof's central 'largest increment/decrement' assertion is stated without the promised factorization and the subsequent calculation covers only unidirectional pure sequences. Thus the correct verdict remains CONDITIONAL: accept only after the missing argument is supplied or a counterexample is ruled out by the proposed check. This does not move the reader's verdict, so UNCHANGED.","tokens_in":25788,"tokens_out":28349,"duration_ms":273696,"concrete_test":"Implement the exact four transition formulas from §4.4 (common/non-common insertions/deletions at either endpoint) and, for a grid of ρ ∈ {0.1, 0.2, 0.5, 0.8} and starting states with n_u ≤ n_v, n_u ∈ (1/4 ρ² n_v, n_v], I ≤ min(n_u, n_v), solve a short-horizon optimization (or exhaustive search up to t = 1/4 ρ² n_v) maximizing |σ_t − σ_0| for Jaccard, Cosine, and Dice subject to feasibility constraints I_t ≤ min(n_u,t, n_v,t) and update-type counts summing to t. Also run random longer sequences on larger synthetic states. If any feasible sequence exceeds 1/2 ρ, Claim 1 and hence Lemma 2 fail; if none is found, require the authors to supply the missing analytical proof that mixed sequences cannot do worse.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Claim 1 underlies Lemma 2 and the entire bucket/charging argument in §4.2: if τ(u,v) < 1/4 ρ² n_v for some feasible update pattern, approximate similarities can leave the ρ-absolute window before the bucket reports them. The proof of Claim 1 in §4.4 says 'Through factorization, it is not difficult to prove that the first case has the largest increment and the third case has the largest decrement for all three similarity measurements,' but it then analyzes only t consecutive common insertions (increment case) and t consecutive common deletions (decrement case). It never analyzes mixed sequences of the four update types. For Cosine and Dice, deleting a non-common neighbor of v decreases n_v while leaving I(u,v) fixed, which increases σ; interleaving such deletions with common insertions can change I and the denominator simultaneously, and the per-step ordering asserted in §4.4 does not by itself imply that the pure common-insertion sequence maximizes drift over t steps. Because the proof of Claim 1 is the only place that fixes τ, and Theorem 2's correctness and the O(log n) amortized bound inherit from it, this missing mixed-update analysis is the most load-bearing soft spot in Theorem 1.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":25988,"tokens_out":27088,"duration_ms":200276,"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":[{"comment":"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.","section":"§4.4, Claim 1"},{"comment":"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.","section":"§4.2, Lemma 5"}],"minor_comments":[{"comment":"The probability for z=0 is printed as n_x/(n_x+n_y); it should be n_y/(n_x+n_y).","section":"Algorithm 5, Line 6"},{"comment":"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.","section":"§4.2, Fact 4"},{"comment":"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.","section":"Throughout"},{"comment":"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.","section":"§3, initial paragraph"}],"recommendation":"major_revision","confidential_remarks":"The central gap in Claim 1 is real but appears repairable; I do not see grounds for rejection if the authors provide a complete proof for mixed update sequences and tighten the amortized charging argument. The reliance on the unpublished Fact 4 is another point the editor may wish to check. The experimental study is extensive and, conditional on the theory being repaired, the paper would be a strong contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper deserves a serious referee; I'd send it out. The core result is real: VD-STAR removes BOTBIN's two restrictions (Jaccard-only, random-update assumption) and improves the per-update bound from O(log^2 n) expected to O(log n) amortized expected, with query parameters on the fly. That is a genuine step for dynamic SCAN-style clustering, not an incremental tweak. The sampling estimator in Lemma 1 is correct for all three similarities — I checked the bias corrections and the Hoeffding constants — and the bucket-quota tracking idea is genuinely new. The charging argument in Section 4.2 is compressed but holds together at the level I can verify.\n\nThe soft spots, in proportion. First and most important: the proof of Claim 1 in Section 4.4. The per-step assertion that common insertions give the largest increment and common deletions the largest decrement is stated, not derived, and the t-step analysis then bounds only pure sequences. For Cosine and Dice, a non-common deletion shrinks the denominator while leaving I fixed, so mixed sequences are not obviously dominated, and the stress-test is right that the written proof does not close this. My own numerics suggest the claim is true — pure sequences do appear to dominate — and the per-step ordering plus monotonicity makes it plausible, but the derivation should be written out. This is a missing derivation in a load-bearing lemma, which is exactly what a referee should push on.\n\nSecond, the bucket index: Algorithm 2 sets i = log2(q), which is negative when tau < 4 since q can be 1/4 or 1/2, while buckets are indexed 0..ceil(log n). Unaddressed, but it only touches small-degree edges and is likely patchable. Third, the abstract promises vertex insertions/deletions, but the problem statement and the unified framework handle edge updates only; easy wording fix. Fourth, the claimed source code at [27] has no URL and I cannot locate it — a reproducibility ding for a paper with heavy experiments, not a correctness issue. There is also a trivial typo in Algorithm 5's coin-flip probabilities (both written as nx/(nx+ny)), worth cleaning up.\n\nThe math is otherwise honest: no fitted parameters, no circularity, the main external inputs are standard or separately published, and the union bound over invocations is fine. I disagree with any reading that the central argument is fundamentally flawed.\n\nWho this is for: dynamic graph algorithms people, especially the structural-clustering community. I would cite it if I worked in that area, and the bucket scheme alone is worth a reading-group look.\n\nRecommendation: send to review. Referee time is warranted; the report should center on Section 4.4 and ask for a complete derivation of Claim 1.","headline":"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.","tokens_in":26587,"tokens_out":12913,"would_cite":true,"duration_ms":105499,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","68W25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["dynamic structural clustering","update affordability","Jaccard similarity","Cosine similarity","Dice similarity","rho-absolute approximation","graph clustering","amortized analysis"],"falsifier":"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.","tokens_in":25551,"feed_emoji":"⚡","tokens_out":13103,"duration_ms":111175,"temperature":0.7,"pith_summary":"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.","feed_headline":"O(log n) per update: dynamic graph clustering, all similarities","feed_subtitle":"VD-STAR handles arbitrary edge updates for Jaccard, Cosine, and Dice, beating a random-only O(log^2 n) bound.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"BOTBIN is the previous approximate state of the art; supplies the Delta-Table CoreFindStr and the random-update O(log^2 n) bound that VD-STAR improves.","marker":"[4]"},{"why":"Introduces the update-affordability concept and the Jaccard-only drift bound that Claim 1 extends to Cosine and Dice.","marker":"[5]"},{"why":"Defines structural clustering and the three similarity measurements (Jaccard, Cosine, Dice) that the problem targets.","marker":"[3]"},{"why":"GS*-Index is the exact dynamic baseline whose O(d_max^2 log n) per-update cost motivates the approximation approach.","marker":"[6]"},{"why":"Provides the O(1) expected-time sorted linked bucket list that keeps bucket insertion, removal, and successor queries cheap.","marker":"[24]"},{"why":"Supplies the concentration inequality that fixes the number of samples L for the similarity estimator.","marker":"[23]"}],"fun_headline_variants":["VD-STAR: O(log n) updates for dynamic clustering with any similarity","Arbitrary updates, any similarity: O(log n) per update clustering","VD-STAR: 9000x faster updates in dynamic graph clustering","No assumptions, all similarities: O(log n) dynamic clustering","From O(log^2 n) to O(log n): dynamic clustering for all"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["VD-STAR: O(log n) updates for dynamic clustering with any similarity","Arbitrary updates, any similarity: O(log n) per update clustering","VD-STAR: 9000x faster updates in dynamic graph clustering","No assumptions, all similarities: O(log n) dynamic clustering","From O(log^2 n) to O(log n): dynamic clustering for all"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000927,"raw_usage":{"total_tokens":3998,"prompt_tokens":1000,"completion_tokens":2998,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":616,"completion_tokens_details":{"reasoning_tokens":2900}},"tokens_in":616,"tokens_out":2998,"duration_ms":20714,"temperature":1.0,"reasoning_tokens":2900,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:52:18.515909+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Effective indexing for dynamic structural graph clustering","cited_arxiv_id":null,"evidence_quote":"BOTBIN is the previous approximate state of the art; supplies the Delta-Table CoreFindStr and the random-update O(log^2 n) bound that VD-STAR improves."},{"cited_title":"Dynamic structural clustering on graphs","cited_arxiv_id":null,"evidence_quote":"Introduces the update-affordability concept and the Jaccard-only drift bound that Claim 1 extends to Cosine and Dice."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines structural clustering and the three similarity measurements (Jaccard, Cosine, Dice) that the problem targets."},{"cited_title":"Efficient structural graph clustering: An index-based approach","cited_arxiv_id":null,"evidence_quote":"GS*-Index is the exact dynamic baseline whose O(d_max^2 log n) per-update cost motivates the approximation approach."},{"cited_title":"Optimal Dynamic Parameterized Subset Sampling","cited_arxiv_id":"2409.18036","evidence_quote":"Provides the O(1) expected-time sorted linked bucket list that keeps bucket insertion, removal, and successor queries cheap."}],"review_version":1}