{"id":"09b99d73-8b77-4a55-aca2-652eeea65116","arxiv_id":"2501.07745","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"DynHAC is the first fully dynamic algorithm for average-linkage hierarchical clustering that maintains a (1+epsilon)-approximate dendrogram under point insertions and deletions.","lead":"This paper presents DynHAC, an algorithm that maintains an approximate hierarchical clustering tree as points are inserted and deleted, rather than recomputing it from scratch. On three real datasets it reports up to 423x faster updates than full recomputation while keeping clustering quality close to the static baseline.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma C.1's M-stability step is load-bearing and unproven: id reuse can lower M(u) without marking the partition dirty, which would break Theorem C.1.","rationale":"The central claim is Theorem C.1: DynHAC maintains a (1+epsilon)-approximate dendrogram. That theorem rests entirely on Lemma C.1, which asserts that merges in partitions not marked dirty remain (1+epsilon)-good. The reader identified Lemma C.1 as the weak point but attributed it to blue partition representatives being skipped. That specific mechanism is not valid: Algorithm 4 inserts every p' unconditionally, so a blue singleton whose partition id is unchanged still gets re-clustered, and a blue singleton whose id changes has no old merge to preserve. The actual load-bearing hole is case (2) of the proof, where the paper asserts without proof that a vertex's M value cannot change unless the partition is re-run. Since contracted vertex ids can be reused, a vertex may persist with the same id while its merge history changes, lowering M(u) and potentially making an old merge non-good. The dirty-partition logic is based on vertex/edge insertions and deletions, not on silent changes to M of existing vertices, so the proof does not rule this out. This is a genuine correctness risk, not merely a style issue. The proposed test settles it empirically on a small adversarial instance; if the invariant happens to be enforced by the deletion/reinsertion bookkeeping, the test will show u being deleted and reinserted, and the concern is resolved. The complexity bound of Theorem C.2 is also underexplained, but it is secondary to the correctness guarantee and is not the main reason for a conditional verdict.","tokens_in":18583,"tokens_out":28524,"duration_ms":291601,"concrete_test":"Instrument DynHAC to record, after each update, every vertex whose stored M value changes but whose partition is not marked dirty. Construct a two-round instance with id reuse: in the old state let a and b merge to u (id a, M(u)=0.5); after a small update let a and c merge to the same id a, with M(c)=0.1. Check whether u is added to V_{i+1} or to a dirty partition, and whether M(u) is updated via UpdateMinMergeSim. Then recompute the dendrogram from scratch and compare linkage similarities; if any merge in a non-dirty partition is not (1+epsilon)-good while M(u) changed without re-clustering, Theorem C.1 fails.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Lemma C.1 must guarantee that a good merge in a non-dirty partition stays good. Case (2) is dismissed with the sentence 'Only nodes with the same merge sequence can have the same node id. So M(u) cannot change.' This invariant is neither defined nor proved. The paper never specifies how contracted vertices get their ids; Section 2 allows the merged vertex z to take an old id. If an update causes u to keep the same id while its children change, e.g., old u = merge(a,b) and new u = merge(a,c) with M(c) < M(b), then M(u) decreases. Such a change need not put u or any neighbor of u into Delta P, because u's id persists and no new/deleted vertex is adjacent to u in that round. Then the partition containing u is not marked dirty, and a previously good merge involving u can become non-good, invalidating the approximation guarantee. The reader's blue-partition concern does not land: Algorithm 4 inserts p' unconditionally, so a blue singleton whose p'=p is still marked dirty, and a blue partition that changes id is singleton and has no old merges to preserve. The real gap is the unjustified M-stability invariant, which Theorem C.1 depends on directly.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces DynHAC, a fully dynamic algorithm for maintaining an average-linkage hierarchical agglomerative clustering (HAC) dendrogram under point insertions and deletions, with a claimed (1+ε)-approximation guarantee. The algorithm builds on the partition-based framework of TeraHAC: in each round it partitions the current contracted graph, reruns SubgraphHAC from scratch on a set of \"dirty\" partitions, and propagates the resulting newly contracted vertices and edges to the next round. The central theoretical claim (Theorem C.1) is that every merge made by DynHAC is (1+ε)-good, so by Lemma 2.1 the maintained dendrogram is (1+ε)-approximate. The paper also states bounds on the total size of dirty partitions per round (Theorem C.2) and on initialization (Theorem C.3), and reports experiments on MNIST, ALOI, and ILSVRC showing large speedups over static HAC and improved NMI over the dynamic baselines GRINCH and Grove.","tokens_in":18872,"tokens_out":8812,"duration_ms":83939,"significance":"If the correctness proof can be completed, DynHAC would be the first fully dynamic algorithm for average-linkage HAC with a (1+ε) approximation guarantee, a natural and significant contribution given the recent conditional lower bounds for dynamic HAC. The paper is clearly written, builds sensibly on the prior TeraHAC structural results, and includes an experimental study with released code and data, which strengthens the practical relevance. However, the approximation guarantee rests on Lemma C.1, and the current proof of that lemma has a gap in the treatment of the M(v) invariant that is load-bearing for Theorem C.1. The experimental speedups and NMI comparisons are likely unaffected by this gap, but the main theoretical claim is not established as written.","major_comments":[{"comment":"The proof of Lemma C.1 dismisses the case that M(u) decreases with the sentence \"Only nodes with the same merge sequence can have the same node id. So M(u) cannot change.\" This invariant is neither defined nor proved anywhere in the manuscript, and it appears to be false under the algorithm's id-reuse policy. In Section 3 (\"Update vertex mapping\") and Algorithm 5, a vertex in the current round can be mapped to an already-existing vertex in the next round whose merge history is different: for example, an old vertex u = merge(a,b) can be replaced by a new vertex u = merge(a,c) with M(c) < M(b), while keeping the same id. Such a change need not put u, or any neighbor of u, into DeltaP, so the partition containing u is not marked dirty and a previously good merge involving u can become non-good. The same mechanism can change the size S(u) of a contracted vertex, which can increase wmax(x) for a neighbor x without x appearing in DeltaP, undermining case (1) as well. Since Lemma C.1 is the key step in the proof of Theorem C.1, the (1+ε)-approximation guarantee is not established. The authors should either prove the M-stability and wmax-stability invariants under a precise specification of how vertex ids are assigned and reused, or modify the algorithm (e.g., by giving fresh ids to contracted vertices or by marking partitions dirty whenever any incident M or size value changes).","section":"Appendix C, Lemma C.1, case (2)"},{"comment":"The proof of Theorem C.2 is too terse to constitute a valid bound. It asserts that an inserted or deleted node x can make at most its 4-hop neighborhood dirty because partition subgraphs span 2-hop neighborhoods, but it does not account for the fact that re-running SubgraphHAC in one partition changes the contracted vertices and their sizes passed to the next round, which can cascade and mark additional partitions dirty in subsequent rounds. A formal inductive argument over rounds is needed to justify the claimed bound, or the statement should be weakened to an empirical observation.","section":"Appendix C, Theorem C.2"}],"minor_comments":[{"comment":"The word \"appendinx\" should be \"appendix\".","section":"Section 1.1"},{"comment":"The phrase \"consistent with what a full recomputation from scratch would have output\" is stronger than what is proved; Theorem C.1 only establishes that the maintained dendrogram is (1+ε)-approximate, not that it matches the output of a particular recomputation. Please rephrase.","section":"Abstract"},{"comment":"Line 6 checks \"if Vi+1 is empty\" before Vi+1 has been computed (it is initialized only in Line 10). The accompanying text suggests the intended condition is about whether the graph in the next round has any vertex, but the pseudocode should be clarified.","section":"Algorithm 2"},{"comment":"The parameter list of Algorithm 5 includes \"Ddirty\", which is not described in the calling context (Algorithm 2, Line 16). The mismatch should be fixed.","section":"Section 3, Update vertex mapping"},{"comment":"The contraction operation is described as merging x and y into a new vertex z, but the manuscript never states how the id of z is chosen. Since id stability is used in the correctness proof (Lemma C.1), the id assignment rule should be specified precisely.","section":"Section 2, Preliminaries"}],"recommendation":"major_revision","confidential_remarks":"The correctness gap in Lemma C.1 is serious and directly affects the main theoretical claim. The gap appears fixable in principle (e.g., by redefining vertex ids to include generation information), but the fix is not a purely local edit; it requires revisiting the id-reuse policy and the definition of dirty partitions. The experimental section is valuable and likely to stand, but the theoretical guarantee should be repaired before the paper can be accepted. I would also encourage the authors to make the new id-assignment rule explicit in the main text rather than only in the appendix."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me give you the short version before the details: this is a real algorithmic contribution, and it deserves a serious referee, but the central correctness proof has a gap that needs to be closed before the main theorem can be trusted.\n\nThe paper presents DynHAC, the first fully dynamic average-linkage HAC algorithm with a (1+ε)-approximation guarantee. That is genuinely new. The dirty-partition update scheme is a natural extension of TeraHAC, and the experiments are convincing: up to 423x speedup over recomputation, NMI close to static HAC and better than GRINCH/Grove. Code and data are available, and the empirical evaluation is handled carefully with fair baselines.\n\nThe soft spot is in Appendix C. Lemma C.1 claims that a good merge in a non-dirty partition stays good. The proof handles wmax increases and deletions, but case (2) is one sentence: \"Only nodes with the same merge sequence can have the same node id. So M(u) cannot change.\" That invariant is never stated or proved. The paper doesn't specify how contracted vertices get their ids, so a vertex can keep an id while its merge sequence changes; M(u) can then drop without any new or deleted neighbor triggering a dirty flag. The stress-test's example (old u = merge(a,b), new u = merge(a,c) with M(c) < M(b)) is plausible and, on the text as written, not ruled out. The reader's concern about blue partitions does not land — Algorithm 4 does insert p' unconditionally, so that particular scenario is covered — but the M-stability gap is load-bearing: Theorem C.1 depends directly on Lemma C.1. This is fixable, but needs a real argument or a change to the id-assignment scheme.\n\nMinor point: Theorem C.2's 4-hop bound is stated loosely and not proved rigorously, but that is secondary. I don't see circularity or fitted parameters; the ε guarantee is parametric and the TeraHAC dependencies are published.\n\nWho should read this: anyone working on dynamic graph algorithms or scalable HAC. It's a well-executed engineering paper with a solid idea and a proof that currently has one visible hole. I'd send it to a good referee, with the expectation that they push hard on the M-stability question. If the authors can close that gap, this becomes a strong result.","headline":"First dynamic (1+ε)-approximate average-linkage HAC algorithm, but the main correctness theorem rests on an unproved M-stability invariant in Lemma C.1.","tokens_in":19377,"tokens_out":2945,"would_cite":false,"duration_ms":24889,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68W40","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that DynHAC maintains a $(1+\\epsilon)$-approximate average-linkage HAC dendrogram under both insertions and deletions, and that this is the first such guarantee for dynamic HAC.","keywords":["hierarchical agglomerative clustering","average linkage","dynamic graph algorithms","(1+epsilon)-approximation","dendrogram","dirty partitions","normalized mutual information"],"falsifier":"Construct a small graph with a red/blue coloring in which a cluster $c$ formed by earlier merges has no red neighbor (so its partition id is $c$, a blue vertex), then insert a high-weight edge from $c$ to a new vertex. The dirty-partition algorithm marks the new partition but, by its condition that an old partition is only marked if it is not blue, does not mark $c$'s partition; computing the good-merge ratio $\\max(w_{\\max}(u), w_{\\max}(v)) / \\min(M(u), M(v), \\bar{w}(uv))$ for the kept merges that built $c$ after the insertion would settle whether any exceeds $1+\\epsilon$.","tokens_in":18411,"feed_emoji":"🌳","tokens_out":12007,"duration_ms":107993,"temperature":0.7,"pith_summary":"This paper introduces DynHAC, an algorithm that keeps a hierarchical agglomerative clustering (HAC) dendrogram up to date as points are inserted into or deleted from a similarity graph. The claim is that the maintained dendrogram remains a $(1+\\epsilon)$-approximation of what an exact average-linkage HAC would produce, which would let streaming and rapidly changing datasets use HAC without repeatedly recomputing from scratch. DynHAC is presented as the first dynamic average-linkage HAC algorithm with such a guarantee, and the authors report update processing up to 423x faster than static recomputation while keeping cluster quality close to the static baseline and above existing dynamic methods. If the guarantee holds, dynamic HAC stops being a heuristic and becomes a maintainable data structure.","feed_headline":"DynHAC updates hierarchy clusters 423x faster than rebuilding","feed_subtitle":"First dynamic average-linkage HAC keeps a (1+epsilon)-approximate dendrogram with near-static quality.","key_machinery":"The load-bearing object is the $(1+\\epsilon)$-good merge: a merge of edge $uv$ is good when $\\max(w_{\\max}(u), w_{\\max}(v)) / \\min(M(u), M(v), \\bar{w}(uv)) \\le 1+\\epsilon$, where $w_{\\max}$ is the largest normalized weight of an incident edge and $M$ is the smallest linkage similarity used in building the cluster. The SubgraphHAC routine performs only good merges inside a partition subgraph, and the earlier partitioned HAC algorithm proved that any dendrogram built from a sequence of good merges is $(1+\\epsilon)$-approximate. DynHAC's mechanism is to use a red/blue partition-id scheme to identify exactly those partitions whose good merges could have been invalidated by an update, rerun SubgraphHAC only on those dirty partitions, and leave the rest untouched; correctness then reduces to showing a clean partition contains no stale merge.","core_discovery":"On the paper's own terms, the core discovery is that the sensitivity of HAC to updates can be contained: although a single insertion can change an entire dendrogram in the worst case, one can localize the damage by partitioning the graph into small pieces, running a $(1+\\epsilon)$-approximate HAC inside each piece, and re-running only the pieces whose input changed, called dirty partitions. DynHAC maintains the partition at each round, the input graph, the vertex-to-vertex mapping between rounds, and the minimum merge similarity of every cluster; when an update arrives it recomputes dirty partitions from scratch and rewrites only the affected ancestors of the dendrogram. The paper's Theorem C.1 asserts that every merge DynHAC ever makes remains $(1+\\epsilon)$-good, so by the good-merge lemma the maintained dendrogram is a $(1+\\epsilon)$-approximation under both node insertions and deletions.","pith_inferences":["The dirty-partition locality suggests a batch-dynamic variant could process many simultaneous insertions and deletions by taking the union of their dirty partitions; the paper does not explore this, but its definitions invite it.","If a good-merge condition can be defined for other linkage functions, the same round-and-recompute skeleton might extend beyond average linkage; the paper treats only average linkage.","The reported speedups are measured on graphs built from approximate nearest neighbors, so a full streaming deployment would also need to maintain the nearest-neighbor graph dynamically, which the paper leaves to the graph maintenance layer.","The paper cites a worst-case lower bound of $n^{\\Omega(1)}$ per update for dynamic HAC, so no algorithm can be both fast and exact on all instances; DynHAC's practical wager is that real graphs have localized change, and the 4-hop dirty-partition bound is the formal face of that wager."],"forward_implications":["If Theorem C.1 holds, dynamic average-linkage HAC becomes a data-structure problem rather than a periodic batch job: insertions and deletions can be absorbed while preserving a provable approximation bound.","The dirty-partition locality bound means the cost of an update is tied to the 4-hop neighborhood of the changed nodes, so updates that are locally contained stay cheap even in large graphs.","Experiments indicate quality stays close to static HAC — NMI within about 0.0014 to 0.03 on the tested datasets — and up to 0.21 higher than the leading dynamic baselines, so the theoretical guarantee translates into practice.","The approximation parameter trades speed for quality in a controlled way: $\\epsilon=0.1$ is up to about 1.93x faster than exact HAC for insertions and $\\epsilon=1$ up to about 4.22x for deletions, with only small NMI changes."],"supporting_citations":[{"why":"Supplies the SubgraphHAC routine, the definition of good merges, and the lemma that sequences of good merges yield $(1+\\epsilon)$-approximate dendrograms; DynHAC is built on this machinery.","marker":"[1]"},{"why":"Provides the static approximate graph HAC baseline used for speedup and NMI comparisons in the experiments.","marker":"[17]"},{"why":"Establishes the $(1+\\epsilon)$ approximation notion for parallelizing HAC that DynHAC adopts.","marker":"[21]"},{"why":"Gives the worst-case lower bound showing dynamic HAC requires $n^{\\Omega(1)}$ time per update, the hardness result this work's practical approach navigates.","marker":"[22]"},{"why":"Provides the tree-grafting dynamic hierarchical clustering baseline that the experiments compare against.","marker":"[26]"},{"why":"Provides the online level-wise dynamic hierarchical clustering baseline and motivates the tradeoff between quality and approximation.","marker":"[27]"}],"fun_headline_variants":["First dynamic average-linkage HAC with 1+eps guarantee","DynHAC: 423x faster dynamic hierarchical clustering","Localized updates for approximate HAC","DynHAC: near-static quality with dynamic HAC","Dynamic HAC: only recompute dirty partitions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument relies on the claim that every vertex whose largest incident merge-similarity increases lands in a partition that gets marked dirty and re-clustered; if an old partition is skipped while one of its vertices gains a heavier neighbor, an old good merge can silently become bad and the $(1+\\epsilon)$ guarantee no longer follows.","fun_headline_variants_meta":{"raw":{"variants":["First dynamic average-linkage HAC with 1+eps guarantee","DynHAC: 423x faster dynamic hierarchical clustering","Localized updates for approximate HAC","DynHAC: near-static quality with dynamic HAC","Dynamic HAC: only recompute dirty partitions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000859,"raw_usage":{"total_tokens":3708,"prompt_tokens":906,"completion_tokens":2802,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":2723}},"tokens_in":522,"tokens_out":2802,"duration_ms":20177,"temperature":1.0,"reasoning_tokens":2723,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:37:07.691859+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a small graph with a red/blue coloring in which a cluster $c$ formed by earlier merges has no red neighbor (so its partition id is $c$, a blue vertex), then insert a high-weight edge from $c$ to a new vertex. The dirty-partition algorithm marks the new partition but, by its condition that an old partition is only marked if it is not blue, does not mark $c$'s partition; computing the good-merge ratio $\\max(w_{\\max}(u), w_{\\max}(v)) / \\min(M(u), M(v), \\bar{w}(uv))$ for the kept merges that built $c$ after the insertion would settle whether any exceeds $1+\\epsilon$.","supporting_citations":[{"cited_title":"Terahac: Hierarchical agglomerative clustering of trillion-edge graphs,","cited_arxiv_id":null,"evidence_quote":"Supplies the SubgraphHAC routine, the definition of good merges, and the lemma that sequences of good merges yield $(1+\\epsilon)$-approximate dendrograms; DynHAC is built on this machinery."},{"cited_title":"Hierarchical agglomerative graph clustering in poly-logarithmic depth,","cited_arxiv_id":null,"evidence_quote":"Provides the static approximate graph HAC baseline used for speedup and NMI comparisons in the experiments."},{"cited_title":"A framework for parallelizing hierarchical clustering methods,","cited_arxiv_id":null,"evidence_quote":"Establishes the $(1+\\epsilon)$ approximation notion for parallelizing HAC that DynHAC adopts."},{"cited_title":"Parallel batch-dynamic minimum spanning forest and the efficiency of dynamic agglomerative graph clustering,","cited_arxiv_id":null,"evidence_quote":"Gives the worst-case lower bound showing dynamic HAC requires $n^{\\Omega(1)}$ time per update, the hardness result this work's practical approach navigates."},{"cited_title":"Scalable hierarchical clustering with tree grafting,","cited_arxiv_id":null,"evidence_quote":"Provides the tree-grafting dynamic hierarchical clustering baseline that the experiments compare against."},{"cited_title":"Online level-wise hierarchical clustering,","cited_arxiv_id":null,"evidence_quote":"Provides the online level-wise dynamic hierarchical clustering baseline and motivates the tradeoff between quality and approximation."}],"review_version":1}