On Hamming-Lipschitz Type Stability of the Subdominant (Minmax) Ultrametric: Theory and Simple Proofs

# On Hamming–Lipschitz Type Stability of the Subdominant (Minmax) Ultrametric: Theory and Simple Proofs
Source: [https://arxiv.org/html/2608.04014](https://arxiv.org/html/2608.04014)
Alokendu Mazumder1,2∗Arnab Roy1,3†∗Punit Rathore1,2 1Robert Bosch Center for Cyber Physical Systems, IISc Bengaluru 2Centre for Infrastructure, Sustainable Transportation and Urban Planning, IISc Bengaluru 3Department of Computer Science and Automation, IISc Bengaluru \{alokendum, arnabroy, prathore\}@iisc\.ac\.in

###### Abstract

The subdominant \(minmax\) ultrametric is a canonical tree\-structured summary of a dissimilarity matrix, arising equivalently as the ultrametric induced by single\-linkage clustering\. While its classical stability theory is usually formulated inℓ∞\\ell\_\{\\infty\}or Gromov–Hausdorff terms, such bounds are poorly suited to sparse perturbations that alter only a few pairwise distances\. We develop anℓ0\\ell\_\{0\}\-type stability theory for this operator\. Our analysis shows that sparse edits propagate only through the*minimum spanning tree*\(MST\): a pairwise ultrametric value can change only if its tree path crosses an edited edge or a cut newly exposed by an edited off\-tree edge\. This yields a sharp per\-edit exposed\-cut score and a tree\-only global envelope, leading to Hamming–Lipschitz bounds on the number of ultrametric entries that can change\. We also prove sharpness results showing that this dependence on tree geometry is unavoidable: under strict cut separation the tree\-edge bound is attained exactly, and for off\-tree edits there are explicit families in which one edited distance changesΘ​\(n2\)\\Theta\(n^\{2\}\)ultrametric entries\. In addition, we prove a conditional near\-additivity principle for multiple edits under certified large per\-edit changed regions and negligible aggregate overlap\. Experiments on deep\-embedding graphs show that the resulting structural scores provide useful vulnerability diagnostics for hierarchical representations\.

†work done at Robert Bosch Center for Cyber Physical Systems\. ∗denotes joint co\-authorship\.

###### Contents

1. [1Introduction](https://arxiv.org/html/2608.04014#S1)1. [1\.1Gaps in Previous Theory and Motivation](https://arxiv.org/html/2608.04014#S1.SS1) 2. [1\.2Minmax Ultrametrics in Modern Machine Learning](https://arxiv.org/html/2608.04014#S1.SS2) 3. [1\.3Contributions:](https://arxiv.org/html/2608.04014#S1.SS3)
2. [2Notation, Assumptions, and Preliminaries](https://arxiv.org/html/2608.04014#S2)1. [2\.1Two MST Facts Used Throughout](https://arxiv.org/html/2608.04014#S2.SS1)
3. [3Sparsity\-Localized Perturbations and Pairwise Impact](https://arxiv.org/html/2608.04014#S3)
4. [4Empirical Case Study \- I: Vulnerability Maps of Deep Embeddings](https://arxiv.org/html/2608.04014#S4)1. [4\.1Protocol](https://arxiv.org/html/2608.04014#S4.SS1) 2. [4\.2Results](https://arxiv.org/html/2608.04014#S4.SS2)
5. [5Empirical Case Study \- II: MST based Superpixel Segmentation](https://arxiv.org/html/2608.04014#S5)1. [5\.1Setup](https://arxiv.org/html/2608.04014#S5.SS1) 2. [5\.2Safe\-edit curves](https://arxiv.org/html/2608.04014#S5.SS2) 3. [5\.3Results](https://arxiv.org/html/2608.04014#S5.SS3)
6. [6Empirical Case Study \- III: Active MST\-Edge Verification for Semi\-Supervised Clustering](https://arxiv.org/html/2608.04014#S6)1. [6\.1Task and scope of the comparison](https://arxiv.org/html/2608.04014#S6.SS1) 2. [6\.2Datasets](https://arxiv.org/html/2608.04014#S6.SS2) 3. [6\.3Common preprocessing pipeline](https://arxiv.org/html/2608.04014#S6.SS3) 4. [6\.4Sparse graph construction and common MST backbone](https://arxiv.org/html/2608.04014#S6.SS4) 5. [6\.5Unverified baseline clustering](https://arxiv.org/html/2608.04014#S6.SS5) 6. [6\.6Active verification protocol](https://arxiv.org/html/2608.04014#S6.SS6) 7. [6\.7Our method: the structural scoreSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)](https://arxiv.org/html/2608.04014#S6.SS7) 8. [6\.8Benchmark baselines](https://arxiv.org/html/2608.04014#S6.SS8)1. [6\.8\.1Raw\-weight baseline](https://arxiv.org/html/2608.04014#S6.SS8.SSS1) 2. [6\.8\.2Scaled\-weight baseline](https://arxiv.org/html/2608.04014#S6.SS8.SSS2) 3. [6\.8\.3Centroid\-gap baseline](https://arxiv.org/html/2608.04014#S6.SS8.SSS3) 4. [6\.8\.4Ward\-bridge baseline](https://arxiv.org/html/2608.04014#S6.SS8.SSS4) 5. [6\.8\.5Fisher\-bridge baseline](https://arxiv.org/html/2608.04014#S6.SS8.SSS5) 6. [6\.8\.6Random baseline](https://arxiv.org/html/2608.04014#S6.SS8.SSS6) 9. [6\.9Evaluation metrics](https://arxiv.org/html/2608.04014#S6.SS9) 10. [6\.10Efficient computation of the benchmark scores](https://arxiv.org/html/2608.04014#S6.SS10) 11. [6\.11What this experiment tests](https://arxiv.org/html/2608.04014#S6.SS11) 12. [6\.12Empirical goal](https://arxiv.org/html/2608.04014#S6.SS12) 13. [6\.13Empirical summary](https://arxiv.org/html/2608.04014#S6.SS13)
7. [7Conclusion](https://arxiv.org/html/2608.04014#S7)
8. [References](https://arxiv.org/html/2608.04014#bib)
9. [AProofs of Technical Lemmas](https://arxiv.org/html/2608.04014#A1)1. [A\.1Proof of Lemma2\.3](https://arxiv.org/html/2608.04014#A1.SS1) 2. [A\.2Proof of Lemma2\.4](https://arxiv.org/html/2608.04014#A1.SS2)
10. [BProofs of Major Theorems and Corollary](https://arxiv.org/html/2608.04014#A2)1. [B\.1Proof of Theorem3\.1](https://arxiv.org/html/2608.04014#A2.SS1) 2. [B\.2Proof of Theorem3\.2](https://arxiv.org/html/2608.04014#A2.SS2) 3. [B\.3Proof of Theorem3\.3](https://arxiv.org/html/2608.04014#A2.SS3) 4. [B\.4Proof of Corollary3\.4](https://arxiv.org/html/2608.04014#A2.SS4)
11. [CSubstantiation of the Asymptotic Condition in Corollary 1\(ii\)](https://arxiv.org/html/2608.04014#A3)

## 1Introduction

Hierarchical clustering\[Ward Jr,[1963](https://arxiv.org/html/2608.04014#bib.bib32)\]provides a fundamental way to represent relational data through nested partitions and dendrograms\[Shepard,[1962](https://arxiv.org/html/2608.04014#bib.bib30)\]\. Among all possible hierarchies, the subdominant \(or minmax\) ultrametric\[Sibson,[1971](https://arxiv.org/html/2608.04014#bib.bib31); Hartigan,[1985](https://arxiv.org/html/2608.04014#bib.bib14); Jain and Dubes,[1988](https://arxiv.org/html/2608.04014#bib.bib16)\]occupies a canonical position: it is the subdominant ultrametric that is maximally dominated by the given dissimilarity and plays a canonical role in hierarchical clustering and metric geometry\. Formally, given a metric space\(X,d\)\(X,d\), the minmax ultrametric can be viewed as the output of an operatorU:\(X,d\)↦\(X,ud\)U:\(X,d\)\\mapsto\(X,u\_\{d\}\), whereud:X×X↦ℝu\_\{d\}:X\\times X\\mapsto\\mathbb\{R\}is the minmax ultrametric associated withdd\. This operator maps a dissimilarity to its associated subdominant ultrametric, equivalently the merge\-height function of single\-linkage clustering\.Carlsson et al\. \[[2010](https://arxiv.org/html/2608.04014#bib.bib3)\]established that the dendrogram of*single linkage clustering*\(SLC\) and the minmax ultrametric are equivalent representations of the same hierarchical structure\. This quantity coincides exactly with the merge height of the two points in the single\-linkage dendrogram\. Hence, single\-linkage hierarchical clustering can be viewed as computing the*maximal ultrametric dominated by the original distances*, providing a precise geometric correspondence between dendrograms and ultrametrics\. Further,Carlsson et al\. \[[2010](https://arxiv.org/html/2608.04014#bib.bib3)\]formulated a rigorous mathematical framework for hierarchical clustering by identifying it with a mapping from finite metric spaces to ultrametric spaces\. Their key theoretical result is that the minmax ultrametric map is 1\-Lipschitz \(non\-expansive\) with respect to Gromov\-Hausdorff\(𝒢​ℋ\)\(\\mathcal\{GH\}\)metric\. Thus, the minmax ultrametric \(dendrogram of SLC\) is non\-expansive under arbitrary perturbations of the input metric in𝒢​ℋ\\mathcal\{GH\}sense, implying that small changes in distances cannot amplify in the induced ultrametric\. In contrast, other linkage\-based operators such as complete or average linkage, fail to satisfy this non\-expansive property\. Their stability theorem establishes single linkage as the unique hierarchically consistent and Lipschitz stable ultrametric projection\. Regarding assumptions on perturbations, their analysis is fully general; no probabilistic or noise model is imposed\. The only requirement is that the metric perturbation be bounded in the Gromov–Hausdorff sense, meaning that all pairwise distances between the two metric spaces differ by at most a small additiveε\\varepsilon\. Under this assumption, every ultrametric distance changes by at mostε\\varepsilon\. Thus, their stability theorem captures uniform, global perturbations of the metric, but does not address sparse or localized adversarial edits\.

Chowdhury et al\. \[[2016](https://arxiv.org/html/2608.04014#bib.bib6)\]further analyzed stability in more concrete norms\. They prove that the minmax ultrametric operatorU:\(X,d\)↦\(X,ud\)U:\(X,d\)\\mapsto\(X,u\_\{d\}\)is 1\-Lipschitz under the sup norm\. Mathematically,‖ud−ud~‖∞⩽‖d−d~‖∞\\\|\\,u\_\{d\}\-u\_\{\\tilde\{d\}\}\\,\\\|\_\{\\infty\}\\leqslant\\\|\\,d\-\\tilde\{d\}\\,\\\|\_\{\\infty\}, for all metricsd,d~d,\\tilde\{d\}onXX\. Crucially, they formalized a duality between Gromov’s tree embedding and the ultrametric structure produced by SLC\. They introduced a measure of deviation from ultrametricity, quantifying how far a finite metric space is from being perfectly treelike\. Through this duality, they proved that the single\-linkage dendrogram computes the ultrametric that minimizes additive distortion up to a bound depending on the space’s ultrametricity and doubling dimension\. In essence, the single\-linkage dendrogram corresponds to an optimal ultrametric tree embedding whose distortion reflects both the local*ultrametricity*of the data and its intrinsic dimensional complexity\. Together, these results position the single\-linkage dendrogram as both an optimal low\-distortion tree embedding and a globally stable \(Lipschitz\-continuous\) map from metric data to hierarchical structure\.

Recently,Mikhailov \[[2025](https://arxiv.org/html/2608.04014#bib.bib23)\]extended the stability result ofCarlsson et al\. \[[2010](https://arxiv.org/html/2608.04014#bib.bib3)\]to the full Gromov–Hausdorff class of all \(possibly unbounded\) metric spaces\. He showed that the canonical subdominant \(min–max\) ultrametricization mappingU:\(X,d\)↦\(X,ud\)U:\(X,d\)\\mapsto\(X,u\_\{d\}\), obtained from the Carlsson–Memoli construction, is*1\-Lipschitz*with respect to the Gromov–Hausdorff distance, not only on bounded spaces but on arbitrary metric spaces\. This viewpoint interpretsUUas a non\-expansive map between*clouds*, i\.e\., equivalence classes of spaces at finite Gromov–Hausdorff distance\. Moreover, for any dotted connected metric spaceAA, he exhibited an inverse relationship betweenUUand Cartesian products withAA: on the cloud of bounded ultrametric spaces, the mapΨ:X↦X×A\\Psi:X\\mapsto X\\times Ais an isometric embedding andd𝒢​ℋ​\(U​\(Ψ​\(X\)\),X\)=0d\_\{\\mathcal\{GH\}\}\\bigl\(U\(\\Psi\(X\)\),X\\bigr\)=0, so thatU​\(Ψ​\(X\)\)U\(\\Psi\(X\)\)is \(Gromov–Hausdorff\) isometric toXX, while ultrametric spaces are precisely the fixed points ofUU\. Conceptually, this places the ultrametricization operator as a globally Lipschitz\-stable transformation over the Gromov–Hausdorff landscape, further linking metric geometry with hierarchical clustering\.

### 1\.1Gaps in Previous Theory and Motivation

Existing stability results for the minimax ultrametricudu\_\{d\}address*uniform*perturbations, proving non\-expansiveness in the entrywiseℓ∞\\ell\_\{\\infty\}metric, and via standard comparisons, in the Gromov–Hausdorff framework\. These guarantees bound the*magnitude*of change everywhere but are agnostic to the*sparsity*and*locality*of the perturbation: a single large edit renders‖d−d~‖∞\\\|d\-\\tilde\{d\}\\\|\_\{\\infty\}large, and the resulting bound allows every entry ofudu\_\{d\}to move by that amount, even when the true effect is confined to a tiny portion of pairs\. In particular, the uniform theory provides no control over the*extent*\(support size\) of the induced change inudu\_\{d\}when perturbations are sparse\.

We close this gap by analyzing the ultrametric mapU:\(X,d\)↦\(X,ud\)U:\(X,d\)\\mapsto\(X,u\_\{d\}\)in a Hamming\-type setting on pairwise dissimilarity matrices\. Concretely, for a finite metricddonXX, we encodeddas its upper\-triangular distance vector and equip this space with the Hamming metric

dH​\(d,d~\)=\#​\{\{x,y\}⊆X:d​\(x,y\)≠d~​\(x,y\)\},d\_\{H\}\(d,\\tilde\{d\}\)\\;=\\;\\\#\\bigl\\\{\\\{x,y\\\}\\subseteq X:d\(x,y\)\\neq\\tilde\{d\}\(x,y\)\\bigr\\\},\(1\)i\.e\., the number of pairs whose dissimilarities are edited\. Equivalently,dH​\(d,d~\)=‖d−d~‖0d\_\{H\}\(d,\\tilde\{d\}\)=\\\|d\-\\tilde\{d\}\\\|\_\{0\}, where∥⋅∥0\\\|\\cdot\\\|\_\{0\}counts nonzero coordinates\. Although∥⋅∥0\\\|\\cdot\\\|\_\{0\}is not a norm, it induces the bonafide Hamming metricdHd\_\{H\}, and we establish a sparsity\-sensitiveℓ0\\ell\_\{0\}\-type theory in which the changed\-pair set is controlled by per\-edit exposed\-cut regions\. In particular, the analysis yields a tree\-only global envelopeL¯T\\bar\{L\}\_\{T\}, giving bounds of the form‖ud−ud~‖0≤L¯T​‖d−d~‖0\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq\\bar\{L\}\_\{T\}\\,\\\|d\-\\tilde\{d\}\\\|\_\{0\}\.L¯T\\bar\{L\}\_\{T\}depends only on the MST structure; in the worst case on annn\-node graph,L¯T⩽\(n2\)\\bar\{L\}\_\{T\}\\leqslant\\binom\{n\}\{2\}\. Thus, our result complements the classicalℓ∞\\ell\_\{\\infty\}/𝒢​ℋ\\mathcal\{GH\}non\-expansiveness along an orthogonal axis: the prior theory controls*how much*entries may move under uniform noise, while our Hamming\-metric guarantee controls*how many*entries can change under sparse edits\. Together, these yield a magnitude\-versus\-extent stability picture that was previously unavailable for the ultrametric operator\.

Table 1:Stability regimes for the minimax/subdominant ultrametric\. Classical uniform bounds control*magnitude*\(ℓ∞\\ell\_\{\\infty\}/GH\), while our Hamming\-space \(ℓ0\\ell\_\{0\}\) bound controls the*extent*of change under sparse edits\.
### 1\.2Minmax Ultrametrics in Modern Machine Learning

Zhu et al\. \[[2017](https://arxiv.org/html/2608.04014#bib.bib35)\]noted that among common hierarchical clustering methods, only single\-linkage \(the minmax ultrametric\) is stable under small perturbations of the input weights \(dissimilarities\) and consistent in the infinite\-sample limit\. Specifically, they prove that SLC is the sole method satisfying:*if the number of i\.i\.d\. sample points goes to infinity, the output ultrametric converges \(a\.s\., in Gromov\-Hausdorff sense\) to the true multiscale structure of the data distribution’s support*\.Dey et al\. \[[2017](https://arxiv.org/html/2608.04014#bib.bib10)\]study temporal hierarchical clustering by fitting each time slice with an ultrametric and enforcing small inter\-time distortions\. They show that the genericℓ∞\\ell\_\{\\infty\}nearest\-ultrametric fit can be unstable under metric perturbations, and therefore replace it with the*minmax ultrametric*udu\_\{d\}, defined as the maximum edge weight along the MST path;udu\_\{d\}is the uniqueℓ∞\\ell\_\{\\infty\}\-closest ultrametric that does not increase any input distance\. This choice yields temporally coherent single\-linkage dendrograms \(sinceudu\_\{d\}is the single\-linkage/minmax ultrametric\) while restoring stability in their temporal objective\.

Devijver et al\. \[[2024](https://arxiv.org/html/2608.04014#bib.bib9)\]studied the stability in high\-dimensional network inference by inserting a single\-linkage hierarchical clustering step before graphical lasso, and proves that the resulting dendrogram, hence the minmax ultrametric underlying single linkage is stable under data perturbations, unlike average linkage\. Concretely, the classical two\-step decomposition first clusters variables via single linkage on a similarity derived from absolute sample covariances, then fits graphical lasso inside the resulting modules; prior work shows this Step\-1 clustering is exactly SLC on that similarity, making the dendrogram the algorithm’s structural backbone\. The authors provide theoretical bounds controlling distances between dendrograms built from two samples and show in simulations and real data that single linkage based modules are markedly more stable than alternatives, while complete/average linkage can be unstable\. Overall, the paper is a recent, theory\-driven application where the minmax ultrametric \(via single linkage/MST path\-max\) is explicitly used to stabilize hierarchical decomposition before sparse graphical model estimation\.

Recent methods leverage ultrametrics as algorithmic backbones for broader clustering objectives and pipelines, e\.g\., showing that center\-based objectives can be solved optimally on ultrametrics and producing rich cluster hierarchies\[Draganov et al\.,[2025](https://arxiv.org/html/2608.04014#bib.bib11)\], and, in density\-based settings, building MST/minmax style hierarchies whose slices enjoy formal stability/consistency\[Rolle and Scoccola,[2024](https://arxiv.org/html/2608.04014#bib.bib28); Ritzert et al\.,[2025](https://arxiv.org/html/2608.04014#bib.bib27)\]\.

Beyond classical hierarchical clustering, recent work formulates ultrametric fitting as an optimization problem amenable to gradient\-based learning and end\-to\-end training\. Learning an ultrametric therefore, amounts to inducing a hierarchy from data rather than merely running a procedural agglomeration\.Chierchia and Perret \[[2019](https://arxiv.org/html/2608.04014#bib.bib5)\]proposed a continuous optimization framework for learning ultrametrics: they replace the ultrametric constraint by a minmax formulation so one can optimize over ultrametric matrices with standard gradients\. Their objective flexibly combines closest ultrametric fidelity with task\-driven terms \(e\.g\., Dasgupta’s HC objective, cluster\-size regularization, triplet constraints\), and scales to large graphs with performance comparable to strong agglomerative baselines\. In a related vein,Chen et al\. \[[2024](https://arxiv.org/html/2608.04014#bib.bib4)\]cast tree–Wasserstein regression as ultrametric learning: they learn a tree metric \(ultrametric\) so that the induced tree–Wasserstein distance approximates the underlying*optimal transport*\(OT\) distance, using projected gradient descent \(projection via a hierarchical map\)\. The learned ultrametric trees outperform several baselines on synthetic and real distributional data\. Other optimization\-driven approaches include differentiable losses on component trees\[Perret and Cousty,[2022](https://arxiv.org/html/2608.04014#bib.bib26)\]\(end\-to\-end learning of hierarchical segmentations\), which directly tune the altitudes \(merge levels\) of a hierarchy\.

Deep methods increasingly enforce ultrametric structure during training\.Lapertot et al\. \[[2024](https://arxiv.org/html/2608.04014#bib.bib18)\]introduce a differentiable ultrametric layer that maps predicted pairwise dissimilarities to an ultrametric, enabling end\-to\-end learning of hierarchical image segmentations with hierarchy\-aware losses \(e\.g\., hierarchical Rand index\)\. In 3D vision\[He et al\.,[2024](https://arxiv.org/html/2608.04014#bib.bib15)\], ultrametric feature fields impose an ultrametric contrastive loss so latent features satisfy the ultrametric inequality, yielding view\-consistent hierarchical segmentations that outperform flat baselines\. At a more foundational level, ultrametric neural networks \(v\-PuNNs\)\[N’guessan,[2025](https://arxiv.org/html/2608.04014#bib.bib24)\]withpp\-adic weights deliver transparent hierarchical representations: each neuron encodes app\-adic ball, guaranteeing a perfectly ultrametric output metric; empirically, these models recover large taxonomies with near\-perfect leaf accuracy and zero triangle\-inequality violations\.

Collectively, these works treat the subdominant ultrametric not merely as a byproduct of single\-linkage, but as a stable, computable projection from metrics to trees that supports temporal coherence, statistical stability of dendrograms, and fast algorithmic reductions in modern hierarchical clustering\.

Takeaway:The above works show that the minmax \(single\-linkage\) ultrametric is not a relic of classical clustering, but an actively used stability tool in modern hierarchical pipelines: it is chosen precisely because it behaves well under perturbations and admits clean algorithmic structure\. Our results refine this picture along a complementary axis: instead of only controlling how*far*an ultrametric can move under metric noise, we control*how many*pairwise relations can change and which parts of the tree they can reach\. In settings such as temporal HC or hierarchical graphical models that already rely onudu\_\{d\}for robustness, our Hamming–Lipschitz bounds provide principled tools to \(i\) localize the effect of sparse perturbations and \(ii\) identify load\-bearing cuts where instability or model misspecification is structurally concentrated\.

### 1\.3Contributions:

At a high level, this paper makes the following contributions\.

- •A sparsity\-aware view of ultrametric stability\.We move beyond classicalℓ∞\\ell\_\{\\infty\}/ Gromov–Hausdorff results and study the minmax ultrametric in a Hamming setting, where the cost of a perturbation is the*number*of pairwise distances that are edited, not how large the edits are\.
- •Which pairs can actually change?We show that sparse edits do*not*propagate arbitrarily through the hierarchy \(Theorem[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)\)\. Instead, we give a simple structural rule that says exactly which pairs can be affected and when those pairs are guaranteed to remain unchanged\.
- •A data\-dependent Lipschitz constant\.For each edited pair, we define the sharp per\-edit affected size, which localizes the pairs that can change through the cuts actually exposed by that edit \(Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)\)\. We also introduce a tree\-only envelopeL¯T\\bar\{L\}\_\{T\}, obtained by maximizing the union of cut\-rectangles along MST paths\. This yields a structural bound on how many entries ofudu\_\{d\}can move under a sparse perturbation, while cleanly separating the edit\-dependent sharp quantity from the tree\-only global one\.
- •Sharpness and worst\-case behavior\.We show that our bound is attained exactly for tree\-edge edits under strict cut separation and is attained on explicit off\-tree families \(Theorem[3\.3](https://arxiv.org/html/2608.04014#S3.Thmtheorem3)\)\. In particular, there are examples where changing a single pairwise distance forces a quadratic number of ultrametric entries to change, so no substantially smaller instance\-independent bound is possible\.
- •When changes almost add up?For multi\-edit perturbations, we give a conditional near\-additivity principle: if one can certify per\-edit changed regions that nearly saturate the exposed\-region scores and have negligible aggregate overlap, then the total number of changed ultrametric entries is asymptotically close to the sum of those scores \(Corollary[3\.4](https://arxiv.org/html/2608.04014#S3.Thmtheorem4)\)\.
- •Simple case studies as diagnostics\.Finally, we use the theorem\-motivated structural scoreSunion​\(e\)=\|Ae\|​\|Be\|S\_\{\\mathrm\{union\}\}\(e\)=\|A\_\{e\}\|\|B\_\{e\}\|as a diagnostic tool in two small case studies:*\(i\)*deep embeddings \(DINO\+UMAP\) of CIFAR\-10, ImageNet\-10, and STL\-10, and*\(ii\)*a superpixel segmentation of the Cameraman image\. In both cases, high\-score edges line up with empirically fragile parts of the hierarchy, illustrating that the theory can inform practical vulnerability maps even though the experiments are diagnostic rather than task\-optimized\.

*All proofs of our proposed theorems and corollaries are deferred to Appendix due to space constraints\.*

## 2Notation, Assumptions, and Preliminaries

LetS=\{1,…,n\}S=\\\{1,\\dots,n\\\}be a finite index set, and letd:S×S→ℝ⩾0d:S\\times S\\to\\mathbb\{R\}\_\{\\geqslant 0\}be a symmetric dissimilarity withd​\(i,i\)=0d\(i,i\)=0for alli∈Si\\in S\. We write∥⋅∥\\\|\\cdot\\\|,∥⋅∥∞\\\|\\cdot\\\|\_\{\\infty\}, and∥⋅∥0\\\|\\cdot\\\|\_\{0\}for theℓ2\\ell\_\{2\}norm, theℓ∞\\ell\_\{\\infty\}norm, and theℓ0\\ell\_\{0\}pseudo\-norm, respectively \(always applied to the vector of upper\-triangular entries unless stated otherwise\)\. Because∥⋅∥0\\\|\\cdot\\\|\_\{0\}counts upper\-triangular matrix entries, all Hamming counts in this paper are over unordered pairs\. We viewddin three equivalent ways: \(i\) as a function on ordered pairs\(i,j\)∈S×S\(i,j\)\\in S\\times S; \(ii\) as a symmetric matrix𝐃∈ℝn×n\\mathbf\{D\}\\in\\mathbb\{R\}^\{n\\times n\}with entries𝐃i​j=d​\(i,j\)\\mathbf\{D\}\_\{ij\}=d\(i,j\); and \(iii\) as an edge\-weight function on the complete undirected graphG=\(V,E\)G=\(V,E\)with vertex setV=SV=Sand edge setE=\{\{i,j\}:1⩽i<j⩽n\}E=\\\{\\\{i,j\\\}:1\\leqslant i<j\\leqslant n\\\}\. When convenient, we writed​\(e\)d\(e\)for the weight of an edgee=\{i,j\}∈Ee=\\\{i,j\\\}\\in E\. We define the set of all unordered pairs as\(V2\):=\{\{i,j\}:i,j∈V,i≠j\}\\binom\{V\}\{2\}:=\\bigl\\\{\\\{i,j\\\}:i,j\\in V,\\ i\\neq j\\bigr\\\}\. LetT=\(V,E​\(T\)\)T=\(V,E\(T\)\)denote the unique MST ofddonGG\(we assume a strict lexicographic tie\-breaking rule to guarantee uniqueness; see Assumption[2\.1](https://arxiv.org/html/2608.04014#S2.Thmtheorem1)for details\)\. For each tree edgee=\{a,b\}∈E​\(T\)e=\\\{a,b\\\}\\in E\(T\), we writeCe=\(Ae,Be\)C\_\{e\}=\(A\_\{e\},B\_\{e\}\)for the fundamental cut obtained by removingeefromTT, so thatAe,Be⊆VA\_\{e\},B\_\{e\}\\subseteq Vare the vertex sets of the two connected components ofT∖\{e\}T\\setminus\\\{e\\\}\. We can then define the associated cut\-pair setℛe:=\{\{i,j\}∈\(V2\):i∈Ae,j∈Be\}\\mathcal\{R\}\_\{e\}:=\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:i\\in A\_\{e\},\\ j\\in B\_\{e\}\\bigr\\\}\. Thusℛe\\mathcal\{R\}\_\{e\}is the unordered\-pair analogue of the rectangleAe×BeA\_\{e\}\\times B\_\{e\}\.

We abbreviatewe:=d​\(e\)w\_\{e\}:=d\(e\)and define the alternative cut minimum

we\+​\(d\):=min⁡\{d​\(x,y\):x∈Ae,y∈Be,\{x,y\}≠e\},w\_\{e\}^\{\+\}\(d\):=\\min\\\{d\(x,y\):x\\in A\_\{e\},\\ y\\in B\_\{e\},\\ \\\{x,y\\\}\\neq e\\\},\(2\)and the corresponding cut gap

Δe​\(d\):=we\+​\(d\)−we≥0\.\\Delta\_\{e\}\(d\):=w\_\{e\}^\{\+\}\(d\)\-w\_\{e\}\\geq 0\.\(3\)
To ensure a unique MST, we adopt the standard assumption of lexicographic tie\-breaking: whenever two edges have identical weights, their order is resolved by a fixed, secondary lexicographic ordering \(for instance, based on endpoint indices or edge identifiers\)\. This convention is not restrictive, it is a widely accepted device in both theoretical analyses and algorithmic implementations of MST\-related problems\. Recent works across theory and systems routinely employ the same assumption to guarantee determinism and analytical clarity, including sublinear and dynamic formulations\[Patlin and van den Brand,[2025](https://arxiv.org/html/2608.04014#bib.bib25); de Vos and Grilnberger,[2025](https://arxiv.org/html/2608.04014#bib.bib8)\], massively parallel and distributed MST algorithms\[Azarmehr et al\.,[2025](https://arxiv.org/html/2608.04014#bib.bib2); Sanders and Schimek,[2023](https://arxiv.org/html/2608.04014#bib.bib29)\], and polymatroid\-based theoretical generalizations\[Harb et al\.,[2023](https://arxiv.org/html/2608.04014#bib.bib13)\]\. Thus, lexicographic tie\-breaking serves as a benign technical convention rather than a substantive limitation, ensuring well\-definedness without affecting optimality or generality\.

###### Assumption 2\.1\.

Fix a deterministic total order≺\\precon edges \(e\.g\., lexicographic\)\. We compare edges by the lexicographic pair\(w​\(e\),rank≺​\(e\)\)\(w\(e\),\\mathrm\{rank\}\_\{\\prec\}\(e\)\)\. Equivalently, conceptually perturb

w′​\(e\)=w​\(e\)\+η​rank≺​\(e\),with a single infinitesimal​η\>0,w^\{\\prime\}\(e\)\\;=\\;w\(e\)\\;\+\\;\\eta\\,\\mathrm\{rank\}\_\{\\prec\}\(e\),\\qquad\\text\{with a single infinitesimal \}\\eta\>0,\(4\)
and run Kruskal onw′w^\{\\prime\}\(ties inwware broken by≺\\prec\)\. This yields a unique MSTTTand a strictly ordered MST edge list\. This infinitesimal perturbation is used only to select a unique MST and a deterministic processing order among equal\-weight edges; all quantitiesd​\(e\)d\(e\),udu\_\{d\},we\+​\(d\)w\_\{e\}^\{\+\}\(d\), andΔe​\(d\)\\Delta\_\{e\}\(d\)refer to the original unperturbed dissimilarity values unless explicitly stated otherwise\.

Under Assumption[2\.1](https://arxiv.org/html/2608.04014#S2.Thmtheorem1), the MST is unique and its tree edges are strictly ordered under the lexicographically perturbed weights\. We next recall the minmax ultrametric and the standard MST facts used in our analysis\. In general,Δe​\(d\)\\Delta\_\{e\}\(d\)need not be strictly positive: lexicographic tie\-breaking guarantees a unique MST and a deterministic edge order, but it does not alter the original numeric edge weights\. We say that a tree edgee∈E​\(T\)e\\in E\(T\)is strictly cut\-separated ifΔe​\(d\)\>0\\Delta\_\{e\}\(d\)\>0\.

Given a perturbed dissimilarityd~:S×S→ℝ⩾0\\tilde\{d\}:S\\times S\\to\\mathbb\{R\}\_\{\\geqslant 0\}, we measure the size of the perturbation by the number of edited pairs, i\.e\., in theℓ0\\ell\_\{0\}sense:

‖d−d~‖0:=\#​\{\{i,j\}⊆S:i<j,d​\(i,j\)≠d~​\(i,j\)\}\.\\\|d\-\\tilde\{d\}\\\|\_\{0\}\\;:=\\;\\\#\\bigl\\\{\\,\\\{i,j\\\}\\subseteq S:i<j,\\ d\(i,j\)\\neq\\tilde\{d\}\(i,j\)\\,\\bigr\\\}\.\(5\)
Let\(hr\)r=1n−1\(h\_\{r\}\)\_\{r=1\}^\{n\-1\}denote the increasing list of MST edge weightshr∈\{we:e∈E​\(T\)\}h\_\{r\}\\in\\\{w\_\{e\}:e\\in E\(T\)\\\}, and similarly\(h~r\)r=1n−1\(\\tilde\{h\}\_\{r\}\)\_\{r=1\}^\{n\-1\}for the MST ofd~\\tilde\{d\}\.

##### Ultrametric operator in index notation\.

In the introduction we viewed the subdominant \(min–max\) ultrametric as the output of an operator

U:\(X,d\)↦\(X,ud\)\.U:\(X,d\)\\mapsto\(X,u\_\{d\}\)\.\(6\)
In this finite\-index setting we work directly with the indexed version: for each dissimilarityddonSS, we denote byud:S×S→ℝ⩾0u\_\{d\}:S\\times S\\to\\mathbb\{R\}\_\{\\geqslant 0\}the associated subdominant ultrametric, and we write

U​\(d\)=ud,ud​\(i,j\)​for the\(i,j\)\-entry of the ultrametric\.U\(d\)=u\_\{d\},\\qquad u\_\{d\}\(i,j\)\\text\{ for the $\(i,j\)$\-entry of the ultrametric\.\}\(7\)
All of our subsequent theorems and inequalities will be stated in terms of indicesi,j∈Si,j\\in S, the MSTTTonSS, and the entries ofddandudu\_\{d\}\.

We now formally define the minmax ultrametric below:

###### Definition 2\.2\(Minmax subdominant ultrametric\)\.

Given a finite setSSwith dissimilarity functiond:S×S→ℝ⩾0d:S\\times S\\to\\mathbb\{R\}\_\{\\geqslant 0\}, the minmax subdominant ultrametricud:S×S→ℝ⩾0u\_\{d\}:S\\times S\\to\\mathbb\{R\}\_\{\\geqslant 0\}is the largest ultrametric dominated bydd\. Explicitly, for anyi,j∈Si,j\\in Swithi≠ji\\neq j, it is constructed by minimizing the bottleneck over all possible paths betweeniiandjj:

ud​\(i,j\)=minP∈𝒫​\(i,j\)⁡max1⩽t⩽m⁡d​\(vt−1,vt\)u\_\{d\}\(i,j\)=\\min\_\{P\\in\\mathcal\{P\}\(i,j\)\}\\max\_\{1\\leqslant t\\leqslant m\}d\(v\_\{t\-1\},v\_\{t\}\)\(8\)where𝒫​\(i,j\)\\mathcal\{P\}\(i,j\)denotes the set of all finite pathsP=\(v0,v1,…,vm\)P=\(v\_\{0\},v\_\{1\},\\dots,v\_\{m\}\)fromv0=iv\_\{0\}=itovm=jv\_\{m\}=j\.

### 2\.1Two MST Facts Used Throughout

Our analysis repeatedly uses two standard facts about the minimum spanning treeTTofdd\. These are common Lemmas on MST, one can easily find them in the standard algorithms textbook byCormen et al\. \[[2022](https://arxiv.org/html/2608.04014#bib.bib7)\]\.

###### Lemma 2\.3\(MST characterization\)\.

IfTTis any minimum spanning tree \(MST\) of the complete graph with weights given by the dissimilarity functiondd, thenud​\(i,j\)=maxe∈pathT​\(i,j\)⁡d​\(e\)∀i≠j\.u\_\{d\}\(i,j\)=\\max\_\{e\\in\\mathrm\{path\}\_\{T\}\(i,j\)\}d\(e\)\\quad\\forall i\\neq j\.

###### Lemma 2\.4\(Cut property, with uniqueness\)\.

Let\(A,B\)\(A,B\)be any cut ofVVand lete⋆∈Ee^\{\\star\}\\in Ebe an edge with one endpoint inAAand one inBB\. Ifd​\(e⋆\)<d​\(f\)d\(e^\{\\star\}\)<d\(f\)for every other cut edgeffacross\(A,B\)\(A,B\), thene⋆e^\{\\star\}belongs to*every*MST ofdd\.

## 3Sparsity\-Localized Perturbations and Pairwise Impact

Our first theorem establishes a localization principle for the subdominant ultrametric under sparse edge edits\. At the level of the MST, it shows that if the tree path between two points contains no edited tree edges, then their ultrametric value cannot increase, and it remains unchanged whenever no edited off\-tree edge creates a cheaper crossing across any fundamental cut along that path\. Globally, the theorem identifies a set of potentially affected tree edges and proves that every changed ultrametric entry must lie in the union of the associated cut\-pair sets\. This yields an explicit combinatorial upper bound on the support ofud−ud~u\_\{d\}\-u\_\{\\tilde\{d\}\}in terms of the forest obtained by deleting those affected edges from the MST\. For single\-linkage clustering, the interpretation is that sparse perturbations can only propagate through edited or newly exposed cuts: subtrees separated from these cuts remain rigid, while only the corresponding branches of the hierarchy can move\. Thus, Theorem[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)gives both a structural description of where changes may occur and a worst\-case bound on how many pairwise merge heights can be altered by a sparse perturbation\.

###### Theorem 3\.1\(Localization of ultrametric under sparse edge edits\)\.

Letd:\(V2\)↦ℝ⩾0d:\\binom\{V\}\{2\}\\mapsto\\mathbb\{R\}\_\{\\geqslant 0\}, and letT=\(V,E​\(T\)\)T=\(V,E\(T\)\)be the \(tie\-broken under Assumption[2\.1](https://arxiv.org/html/2608.04014#S2.Thmtheorem1)\) MST ofdd\. LetF⊆\(V2\)F\\subseteq\\binom\{V\}\{2\}be a set of edited edges and letd~\\tilde\{d\}be any dissimilarity withd~​\(e\)=d​\(e\)\\tilde\{d\}\(e\)=d\(e\)for alle∉Fe\\notin F\(no restriction one∈Fe\\in F\)\.

Fori≠ji\\neq jletPT​\(i,j\)P\_\{T\}\(i,j\)be the uniqueii–jjpath inTT\. By Lemma[2\.3](https://arxiv.org/html/2608.04014#S2.Thmtheorem3),ud​\(i,j\)=maxe∈PT​\(i,j\)⁡weu\_\{d\}\(i,j\)=\\ \\max\_\{e\\in P\_\{T\}\(i,j\)\}w\_\{e\}, and therefore the following holds:

- \(i\)\(Monotone upper bound, no editedTT\-edges on the path\) IfPT​\(i,j\)∩F=∅P\_\{T\}\(i,j\)\\cap F=\\varnothing, thenud~​\(i,j\)≤ud​\(i,j\)u\_\{\\tilde\{d\}\}\(i,j\)\\ \\leq\\ u\_\{d\}\(i,j\)\.
- \(ii\)\(Sufficient conditions for equality\) IfPT​\(i,j\)∩F=∅P\_\{T\}\(i,j\)\\cap F=\\varnothingand for everye∈PT​\(i,j\)e\\in P\_\{T\}\(i,j\), all edited edgesf∈Ff\\in FcrossingCeC\_\{e\}satisfyd~​\(f\)⩾we\\tilde\{d\}\(f\)\\geqslant w\_\{e\}, thenud~​\(i,j\)=ud​\(i,j\)u\_\{\\tilde\{d\}\}\(i,j\)=u\_\{d\}\(i,j\)\.
- \(iii\)\(Pair\-count bound for possible changes\) Define the set of potentially affected MST edges ℰ:=\{e∈E​\(T\):e∈F​or​∃f∈F​crossing​Ce​with​d~​\(f\)<we\}\.\\mathcal\{E\}:=\\bigl\\\{e\\in E\(T\):e\\in F\\text\{ or \}\\exists f\\in F\\text\{ crossing \}C\_\{e\}\\text\{ with \}\\tilde\{d\}\(f\)<w\_\{e\}\\bigr\\\}\.\(9\)Then the number of unordered pairs whose ultrametric value changes satisfies \|\{\{i,j\}∈\(V2\):ud~​\(i,j\)≠ud​\(i,j\)\}\|=‖ud−ud~‖0≤\|⋃e∈ℰℛe\|=\(n2\)−∑t=1m\(\|Ct\|2\),\\bigl\|\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:u\_\{\\tilde\{d\}\}\(i,j\)\\neq u\_\{d\}\(i,j\)\\bigr\\\}\\bigr\|=\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq\\left\|\\bigcup\_\{e\\in\\mathcal\{E\}\}\\mathcal\{R\}\_\{e\}\\right\|=\\binom\{n\}\{2\}\-\\sum\_\{t=1\}^\{m\}\\binom\{\|C\_\{t\}\|\}\{2\},\(10\)whereC1,…,CmC\_\{1\},\\dots,C\_\{m\}are the vertex sets of the connected components of the forestT−ℰT\-\\mathcal\{E\}\.

![Refer to caption](https://arxiv.org/html/2608.04014v1/visual_of_theorems/image1_original_mst.png)\(a\)
![Refer to caption](https://arxiv.org/html/2608.04014v1/visual_of_theorems/Exposed_Cut.png)\(b\)
![Refer to caption](https://arxiv.org/html/2608.04014v1/visual_of_theorems/image3_fundamental_cut.png)\(c\)

Figure 1:Illustration of Theorems[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)and[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)\. \(a\) Initial MST \(green\)\. \(b\) A sparse off\-tree edit on edge\{1,4\}\\\{1,4\\\}\(dotted blue\) that exposes the MST edge\{4,5\}\\\{4,5\\\}\. \(c\) The affected region \(red\), given by the cut\-pair setℛ\{4,5\}=\{\{i,4\}:i∈\{0,1,2,3\}\},\\mathcal\{R\}\_\{\\\{4,5\\\}\}=\\bigl\\\{\\\{i,4\\\}:i\\in\\\{0,1,2,3\\\}\\bigr\\\},upper\-bounds the total number of changed ultrametric entries, i\.e\.‖ud−ud~‖0\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\.Remark\.*Theorem[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)reveals an important asymmetry\. If the tree pathPT​\(i,j\)P\_\{T\}\(i,j\)contains no edited tree edge, then the original tree bottleneck remains available underd~\\tilde\{d\}, so the ultrametric valueud~​\(i,j\)u\_\{\\tilde\{d\}\}\(i,j\)can never exceedud​\(i,j\)u\_\{d\}\(i,j\)\. In that regime, a change can only occur through a strictly cheaper off\-tree crossing of one of the fundamental cuts alongPT​\(i,j\)P\_\{T\}\(i,j\)\. Thus sparse perturbations act in two qualitatively different ways: edits on the tree path can raise or lower merge heights directly, whereas off\-tree edits can only lower them by opening cheaper alternative connections across MST cuts\.*

Also, it gives a first coarse localization result: it shows that all changes in the ultrametric are confined to a union of cut\-pair sets associated with a small set of MST edges determined by the edit pattern\. However, this description is still global across edits and does not yet yield a Hamming–Lipschitz inequality that separates the contribution of individual edited pairs\. To sharpen the picture, we pass to the level of a single edited pairf=\{x,y\}f=\\\{x,y\\\}\. For each suchff, we isolate the subset of tree edges whose cuts are actually exposed by that edit; these are the exposed cutsΞ​\(f\)\\Xi\(f\)\. Formally, for an edited pairf=\{x,y\}∈Ff=\\\{x,y\\\}\\in F, define the set of exposed cuts byΞ​\(f\):=\(\{f\}∩E​\(T\)\)∪\{e∈E​\(T\):f​crosses​Ce​and​d~​\(f\)<we\}\.\\Xi\(f\):=\(\\\{f\\\}\\cap E\(T\)\)\\cup\\bigl\\\{e\\in E\(T\):f\\text\{ crosses \}C\_\{e\}\\text\{ and \}\\tilde\{d\}\(f\)<w\_\{e\}\\bigr\\\}\.The next theorem defines the sharp per\-edit exposed\-cut score

Sunion​\(f\):=\|⋃e∈Ξ​\(f\)ℛe\|,S\_\{\\mathrm\{union\}\}\(f\):=\\left\|\\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\\right\|,\(11\)and shows that every ultrametric entry changed by the edit must lie inside this exposed region\. By further enlarging the exposed cuts to the full tree pathPT​\(x,y\)P\_\{T\}\(x,y\), we obtain a tree\-only global envelopeL¯T\\bar\{L\}\_\{T\}, which yields a Hamming–Lipschitz type bound for arbitrary sparse perturbations\.

###### Theorem 3\.2\(Hamming–Lipschitz bound via exposed cuts\)\.

Letd:\(V2\)→ℝ≥0d:\\binom\{V\}\{2\}\\to\\mathbb\{R\}\_\{\\geq 0\}be a dissimilarity on a finite setVV, and letT=\(V,E​\(T\)\)T=\(V,E\(T\)\)be the \(tie\-broken under Assumption[2\.1](https://arxiv.org/html/2608.04014#S2.Thmtheorem1)\) MST ofdd\. Letd~\\tilde\{d\}be any perturbed dissimilarity, and letF:=\{f∈\(V2\):d~​\(f\)≠d​\(f\)\}F:=\\bigl\\\{f\\in\\tbinom\{V\}\{2\}:\\tilde\{d\}\(f\)\\neq d\(f\)\\bigr\\\}be its edit support\. For an edited pairf=\{x,y\}∈Ff=\\\{x,y\\\}\\in F, define the set of exposed cuts by

Ξ​\(f\):=\(\{f\}∩E​\(T\)\)∪\{e∈E​\(T\):f​crosses​Ce​and​d~​\(f\)<we\}\.\\Xi\(f\):=\(\\\{f\\\}\\cap E\(T\)\)\\cup\\bigl\\\{e\\in E\(T\):f\\text\{ crosses \}C\_\{e\}\\text\{ and \}\\tilde\{d\}\(f\)<w\_\{e\}\\bigr\\\}\.\(12\)LetC:=\{\{i,j\}∈\(V2\):ud~​\(i,j\)≠ud​\(i,j\)\}C:=\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:u\_\{\\tilde\{d\}\}\(i,j\)\\neq u\_\{d\}\(i,j\)\\bigr\\\}denote the set of unordered pairs whose ultrametric values change\. Further, define the sharp per\-edit exposed\-cut sizeSunion​\(f\):=\|⋃e∈Ξ​\(f\)ℛe\|\.S\_\{\\mathrm\{union\}\}\(f\):=\\left\|\\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\\right\|\.For an edited pairf=\{x,y\}f=\\\{x,y\\\}, define the tree\-only path envelopeS¯T​\(f\):=\|⋃e∈PT​\(x,y\)ℛe\|,\\bar\{S\}\_\{T\}\(f\):=\\left\|\\bigcup\_\{e\\in P\_\{T\}\(x,y\)\}\\mathcal\{R\}\_\{e\}\\right\|,and the global tree\-only constantL¯T:=maxf∈\(V2\)⁡S¯T​\(f\)\.\\bar\{L\}\_\{T\}:=\\max\_\{f\\in\\binom\{V\}\{2\}\}\\bar\{S\}\_\{T\}\(f\)\.

Then:

- \(i\)C⊆⋃f∈F⋃e∈Ξ​\(f\)ℛe\.C\\subseteq\\bigcup\_\{f\\in F\}\\ \\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\.Consequently,‖ud−ud~‖0=\|C\|≤\|⋃f∈F⋃e∈Ξ​\(f\)ℛe\|\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\|C\|\\leq\\left\|\\bigcup\_\{f\\in F\}\\ \\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\\right\|\.
- \(ii\)for every edited pairf∈Ff\\in F, Sunion​\(f\)≤S¯T​\(f\)≤L¯T,S\_\{\\mathrm\{union\}\}\(f\)\\leq\\bar\{S\}\_\{T\}\(f\)\\leq\\bar\{L\}\_\{T\},\(13\)and therefore ‖ud−ud~‖0≤∑f∈FSunion​\(f\)≤∑f∈FS¯T​\(f\)≤L¯T​\|F\|=L¯T​‖d−d~‖0\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\\leq\\sum\_\{f\\in F\}\\bar\{S\}\_\{T\}\(f\)\\leq\\bar\{L\}\_\{T\}\\,\|F\|=\\bar\{L\}\_\{T\}\\,\\\|d\-\\tilde\{d\}\\\|\_\{0\}\.\(14\)In particular, L¯T≤\(\|V\|2\)\.\\bar\{L\}\_\{T\}\\leq\\binom\{\|V\|\}\{2\}\.\(15\)

Remark\.*Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)separates two distinct layers of control\. The quantitySunion​\(f\)S\_\{\\mathrm\{union\}\}\(f\)is the sharp, edit\-dependent score: it records only those MST cuts that are actually exposed by the specific perturbation offf\. In contrast,S¯T​\(f\)\\bar\{S\}\_\{T\}\(f\)andL¯T\\bar\{L\}\_\{T\}are tree\-only envelopes obtained by enlarging the exposed region to the full MST path of the edited pair\. Thus the theorem distinguishes the mechanism of propagation, which is localized through exposed cuts, from a coarser but globally uniform capacity of the tree to transmit sparse perturbations\.*

It yields a Hamming–Lipschitz upper bound that is both localized and structurally interpretable: sparse perturbations can propagate only through exposed MST cuts, and their total effect is controlled by the associated union of cut\-pair sets\. This naturally raises the next question: are these quantities merely proof\-level upper bounds, or do they capture the true scale of instability of the subdominant ultrametric? In particular, one would like to know whether the sharp per\-edit scoreSunion​\(f\)S\_\{\\mathrm\{union\}\}\(f\)can actually be attained, and whether the resulting dependence on tree geometry is intrinsic\. Theorem[3\.3](https://arxiv.org/html/2608.04014#S3.Thmtheorem3)answers this by showing exact attainability for tree\-edge edits under strict cut separation, and sharpness on explicit off\-tree families, including worst\-case examples in which a single sparse edit changesΘ​\(n2\)\\Theta\(n^\{2\}\)ultrametric entries\.

###### Theorem 3\.3\(Analysis of the Hamming–Lipschitz bound\)\.

Letd:\(V2\)→ℝ⩾0d:\\binom\{V\}\{2\}\\to\\mathbb\{R\}\_\{\\geqslant 0\}be a dissimilarity and letT=\(V,E​\(T\)\)T=\(V,E\(T\)\)be the \(tie\-broken under Assumption[2\.1](https://arxiv.org/html/2608.04014#S2.Thmtheorem1)\) MST ofdd\. For an edited pairf=\{x,y\}f=\\\{x,y\\\}and edited dissimilarityd~\\tilde\{d\}withd~​\(g\)=d​\(g\)\\tilde\{d\}\(g\)=d\(g\)forg∉\{f\}g\\notin\\\{f\\\}, define

Ξ​\(f\):=\(\{f\}∩E​\(T\)\)∪\{e∈E​\(T\):f​crosses​Ce​and​d~​\(f\)<we\},Sunion​\(f\):=\|⋃e∈Ξ​\(f\)ℛe\|\.\\Xi\(f\)\\ :=\\ \(\\\{f\\\}\\cap E\(T\)\)\\ \\cup\\ \\\{\\,e\\in E\(T\):\\ f\\ \\text\{crosses\}\\ C\_\{e\}\\ \\text\{and\}\\ \\tilde\{d\}\(f\)<w\_\{e\}\\,\\\},\\qquad S\_\{\\mathrm\{union\}\}\(f\):=\\left\|\\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\\right\|\.\(16\)Then:

1. \(i\)\(*Tree\-edge edit under strict cut separation*\) Iff=e∈E​\(T\)f=e\\in E\(T\)andeeis strictly cut\-separated, i\.e\.Δe​\(d\)=we\+​\(d\)−we\>0,\\Delta\_\{e\}\(d\)=w\_\{e\}^\{\+\}\(d\)\-w\_\{e\}\>0,then there existsd~\\tilde\{d\}supported on\{f\}\\\{f\\\}such that ‖ud−ud~‖0=\|Ae\|​\|Be\|=Sunion​\(f\)\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\|A\_\{e\}\|\|B\_\{e\}\|=S\_\{\\mathrm\{union\}\}\(f\)\.\(17\)
2. \(ii\)\(*Off\-tree sharpness on an explicit family*\) There exist dissimilaritiesdd, off\-tree edgesf∉E​\(T\)f\\notin E\(T\), and single\-edge editsd~\\tilde\{d\}supported on\{f\}\\\{f\\\}such that ‖ud−ud~‖0=\|⋃e∈Ξ​\(f\)ℛe\|=Sunion​\(f\)=Θ​\(n2\)\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\\left\|\\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\\right\|=S\_\{\\mathrm\{union\}\}\(f\)=\\Theta\(n^\{2\}\)\.\(18\)Thus, the upper bound of Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)is attained on explicit off\-tree instances, and in the worst case a single off\-tree edit can force a quadratic number of ultrametric changes\.
3. \(iii\)\(*Necessity of instance dependence*\) Consequently, no universal subquadratic functionc​\(n\)=o​\(n2\)c\(n\)=o\(n^\{2\}\)can satisfy ‖ud−ud~‖0≤c​\(n\)​‖d−d~‖0\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq c\(n\)\\,\\\|d\-\\tilde\{d\}\\\|\_\{0\}\(19\)for all instances\.

Remark\.*Theorem[3\.3](https://arxiv.org/html/2608.04014#S3.Thmtheorem3)shows that the exposed\-cut quantities from Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)are not artifacts of the proof\. In particular, the instability of the subdominant ultrametric is governed by the geometry of the MST itself: a single sparse edit can trigger changes on the scale of an entire cut\-pair set, and in explicit off\-tree families this propagation reaches quadratic size\. Thus the dependence on tree geometry is intrinsic to the operator, rather than a byproduct of our bounding technique\.*

Theorem[3\.3](https://arxiv.org/html/2608.04014#S3.Thmtheorem3)resolves the single\-edit case: it shows that the exposed\-cut score can be attained exactly in structured settings and that, in the worst case, even one edited distance can induceΘ​\(n2\)\\Theta\(n^\{2\}\)ultrametric changes\.*The next natural question is how multiple sparse edits interact\.*If their exposed regions substantially overlap, the total number of changed entries may be far smaller than the sum of the individual scores; if they are largely disjoint, one expects an approximately additive effect\. Corollary[3\.4](https://arxiv.org/html/2608.04014#S3.Thmtheorem4)formalizes this latter regime in a conditional form: whenever one can certify large per\-edit changed regions with negligible aggregate overlap, the overall Hamming change is asymptotically close to the sum of the corresponding exposed\-cut scores\.

###### Corollary 3\.4\.

Fix a minimum spanning treeTTofdd, an edit setF⊆\(V2\)F\\subseteq\\binom\{V\}\{2\}, and edited weightsd~\\tilde\{d\}supported onFF\. For eachf∈Ff\\in F, define the exposed regionR​\(f\):=⋃e∈Ξ​\(f\)ℛe,R\(f\):=\\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\},so that\|R​\(f\)\|=Sunion​\(f\)\.\|R\(f\)\|=S\_\{\\mathrm\{union\}\}\(f\)\.Assume that for eachf∈Ff\\in Fthere exists a certified changed\-pair setQ​\(f\)⊆R​\(f\)Q\(f\)\\subseteq R\(f\)such that every pair inQ​\(f\)Q\(f\)indeed changes under the common edited dissimilarityd~\\tilde\{d\}, i\.e\.Q​\(f\)⊆\{\{i,j\}∈\(V2\):ud~​\(i,j\)≠ud​\(i,j\)\}\.Q\(f\)\\subseteq\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:u\_\{\\tilde\{d\}\}\(i,j\)\\neq u\_\{d\}\(i,j\)\\bigr\\\}\.

Then:

- \(i\)\|⋃f∈FQ​\(f\)\|≤‖ud−ud~‖0≤\|⋃f∈FR​\(f\)\|≤∑f∈FSunion​\(f\)\.\\left\|\\bigcup\_\{f\\in F\}Q\(f\)\\right\|\\leq\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq\\left\|\\bigcup\_\{f\\in F\}R\(f\)\\right\|\\leq\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\.
- \(ii\)Moreover, consider any asymptotic regime of instances \(for example,\|V\|=n→∞\|V\|=n\\to\\infty\) in which ∑f∈F\|Q​\(f\)\|=\(1−o​\(1\)\)​∑f∈FSunion​\(f\),\\sum\_\{f\\in F\}\|Q\(f\)\|=\(1\-o\(1\)\)\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\),and the certified regions have asymptotically negligible total overlap: ∑f,f′∈Ff<f′\|Q​\(f\)∩Q​\(f′\)\|=o​\(∑f∈F\|Q​\(f\)\|\)\.\\sum\_\{\\begin\{subarray\}\{c\}f,f^\{\\prime\}\\in F\\\\ f<f^\{\\prime\}\\end\{subarray\}\}\|Q\(f\)\\cap Q\(f^\{\\prime\}\)\|=o\\\!\\left\(\\sum\_\{f\\in F\}\|Q\(f\)\|\\right\)\.Then ‖ud−ud~‖0=\(1−o​\(1\)\)​∑f∈FSunion​\(f\)\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\(1\-o\(1\)\)\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\.

Remark\.*Corollary[3\.4](https://arxiv.org/html/2608.04014#S3.Thmtheorem4)isolates two logically distinct tasks\. The first is a*geometric*task: identify exposed regionsR​\(f\)R\(f\)that contain all pairs that could possibly change\. The second is a*certification*task: exhibit subsetsQ​\(f\)⊆R​\(f\)Q\(f\)\\subseteq R\(f\)whose pairs are guaranteed to change under the common perturbation\. Once such certified regions are available, the global Hamming count is governed purely by set overlap\. In this sense, the corollary turns the multi\-edit problem from one of ultrametric analysis into one of certifiable combinatorial packing\.*

Corollary[3\.4](https://arxiv.org/html/2608.04014#S3.Thmtheorem4)completes the picture by showing how the single\-edit geometry from Theorems[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)–[3\.3](https://arxiv.org/html/2608.04014#S3.Thmtheorem3)extends to sparse multi\-edit regimes\. The key issue is no longer the effect of an individual edit, but the interaction among their exposed regions\. When these regions overlap heavily, different edits compete for the same ultrametric entries and the total effect can be far smaller than the sum of their individual scores\. When one can instead certify large per\-edit changed regions with negligible aggregate overlap, the total Hamming change becomes asymptotically additive\. Thus the corollary identifies the precise structural mechanism behind near\-additivity: it is not sparsity alone, but sparsity together with low\-overlap exposure in the MST geometry\.

## 4Empirical Case Study \- I: Vulnerability Maps of Deep Embeddings

Our contribution is primarily theoretical, so the role of this section is diagnostic rather than benchmark\-driven\. Theorems[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)and[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)show that sparse metric edits can change the ultrametric only through edited or newly exposed MST cuts, and that the extent of propagation is controlled by the associated cut\-pair sets\. This suggests a concrete empirical question:*in representation graphs arising from real data, are there only a few load\-bearing MST edges whose perturbation causes substantial ultrametric damage, while most edges are comparatively harmless?*The experiment below is designed to probe exactly that question\.

##### Motivation from the theory\.

For a tree edgee∈E​\(T\)e\\in E\(T\), Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)reduces the per\-edit exposed region to the single cut\-rectangle associated withee, whose cardinality isSunion​\(e\)=\|Ae\|​\|Be\|\.S\_\{\\mathrm\{union\}\}\(e\)=\|A\_\{e\}\|\\,\|B\_\{e\}\|\.ThusSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)is the natural structural score predicted by the theory: it quantifies how many unordered pairs can potentially be affected when the hierarchy is stressed across that cut\. Our main empirical goal is therefore to test whether this score meaningfully ranks edges by realized vulnerability in real representation graphs\.

### 4\.1Protocol

We use three 10\-class image datasets: CIFAR\-10, ImageNet\-10, and STL\-10\. For each dataset, we start from precomputed DINO\-ViT features, apply UMAP to obtain a 20\-dimensional embedding, and subsample a few thousand points for efficiency\. On each embedding, we build the complete Euclidean graph, compute its tie\-broken MSTTT, and obtain the induced subdominant ultrametricudu\_\{d\}via the MST bottleneck formula\. We then compute the structural scoreSunion​\(e\)=\|Ae\|​\|Be\|S\_\{\\mathrm\{union\}\}\(e\)=\|A\_\{e\}\|\|B\_\{e\}\|for every tree edgee∈E​\(T\)e\\in E\(T\)\. Theorem[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)predicts that ultrametric changes must remain localized to unions of such cut\-rectangles, while Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)identifiesSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)as the sharp tree\-edge quantity controlling the size of the exposed region\. Figure[2](https://arxiv.org/html/2608.04014#S4.F2)therefore serves two purposes: the bottom row visualizes the empirical distribution of this theorem\-motivated score across the MST, and the top row evaluates whether targeting high\-score edges indeed produces larger realized ultrametric damage\.

![Refer to caption](https://arxiv.org/html/2608.04014v1/risk_profile/CIFAR-10_l0_comparison.png)
![Refer to caption](https://arxiv.org/html/2608.04014v1/risk_profile/ImageNet-10_l0_comparison.png)
![Refer to caption](https://arxiv.org/html/2608.04014v1/risk_profile/STL-10_l0_comparison.png)
![Refer to caption](https://arxiv.org/html/2608.04014v1/risk_profile/CIFAR-10_risk_hist.png)
![Refer to caption](https://arxiv.org/html/2608.04014v1/risk_profile/ImageNet-10_risk_hist.png)
![Refer to caption](https://arxiv.org/html/2608.04014v1/risk_profile/STL-10_risk_hist.png)

Figure 2:Top row:normalized ultrametric damageΔ0​\(ud,ud~\)\\Delta\_\{0\}\(u\_\{d\},u\_\{\\tilde\{d\}\}\)under targeted \(top\-risk\) versus random sparse perturbations for CIFAR\-10, ImageNet\-10, and STL\-10\.Bottom row:histograms of the theorem\-motivated structural scorelog10⁡Sunion​\(e\)\\log\_\{10\}S\_\{\\mathrm\{union\}\}\(e\)over MST edges for the same three datasets\. It shows that structural risk is concentrated in a small high\-score tail, while the top row shows that targeting that tail causes substantially larger realized Hamming damage than random edits with the same budget, consistent with Theorems[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)and[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)\.To test this, we fix a sparse edit budgetmmequal to10%10\\%of the MST edges and compare two strategies:

- •Structural attack \(top\-risk\):choose themmtree edges with largestSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)\.
- •Random baseline:choosemmtree edges uniformly at random from the same pool\.

In both cases, we construct a perturbed metricd~\\tilde\{d\}by sharply inflating the selected tree\-edge weights, recompute the MST and the induced ultrametricud~u\_\{\\tilde\{d\}\}, and measure the normalized Hamming distortion

Δ0​\(ud,ud~\):=‖ud−ud~‖0\(n2\)\.\\Delta\_\{0\}\(u\_\{d\},u\_\{\\tilde\{d\}\}\):=\\frac\{\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\}\{\\binom\{n\}\{2\}\}\.\(20\)This is a stress test inspired by the tree\-edge exposed\-cut analysis\. It is not intended as a literal validation of the sharpness theorem edge\-by\-edge, but rather as an empirical probe of whether the score from Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)tracks practical vulnerability\.

### 4\.2Results

Figure[2](https://arxiv.org/html/2608.04014#S4.F2)\(bottom row\) shows that the distribution oflog10⁡Sunion​\(e\)\\log\_\{10\}S\_\{\\mathrm\{union\}\}\(e\)is strongly skewed for all three datasets\. Most MST edges lie in a low\-score bulk, corresponding to leaf\-like or weakly load\-bearing cuts, while a small number of bridge\-like edges form a thin high\-score tail\. This is precisely the type of heterogeneity suggested by Theorems[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)and[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2): sparse perturbations should not propagate uniformly through the hierarchy, but instead concentrate around a small set of structurally important cuts\.

Figure[2](https://arxiv.org/html/2608.04014#S4.F2)\(top row\) shows that this structural heterogeneity is not merely combinatorial\. Across CIFAR\-10, ImageNet\-10, and STL\-10, the top\-risk attack consistently induces much larger normalized Hamming damage than the random baseline at the same edit budget\. In particular, even in budgets where random edits leaveΔ0​\(ud,ud~\)\\Delta\_\{0\}\(u\_\{d\},u\_\{\\tilde\{d\}\}\)close to zero, editing the highest\-score edges already flips a visible fraction of ultrametric entries\. The practical conclusion is that the theorem\-motivated scoreSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)identifies a small set of load\-bearing edges whose perturbation produces disproportionate global impact\.

Overall, this case study should be read as a diagnostic interpretation of the theory\. Theorem[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)explains*where*propagation can occur, while Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)supplies the natural per\-edge structural score\. Figure[2](https://arxiv.org/html/2608.04014#S4.F2)shows that, on real deep\-embedding graphs, these quantities yield a meaningful vulnerability map: most MST edges are structurally benign, but a small high\-score tail captures the edges whose sparse perturbation can ripple widely through the induced hierarchy\. Taken together, these experiments provide an empirical counterpart to the theoretical picture: the structural scoreSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)identifies a small set of load\-bearing MST edges whose perturbation has disproportionate global impact, while most edges are comparatively benign\.

## 5Empirical Case Study \- II: MST based Superpixel Segmentation

This section provides a complementary low\-dimensional illustration of the structural scoreSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)in a downstream image\-segmentation setting\. Whereas the experiment in Section[4](https://arxiv.org/html/2608.04014#S4)directly measures ultrametric Hamming distortion on representation graphs, the present experiment studies whether the same score can identify*safe*versus*fragile*tree edges in a superpixel hierarchy\.

##### Motivation from the theory\.

Theorems[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)and[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)say that sparse edits propagate through the ultrametric only via edited or newly exposed MST cuts, and that for tree\-edge edits the natural structural quantity is again

Sunion​\(e\)=\|Ae\|​\|Be\|\.S\_\{\\mathrm\{union\}\}\(e\)=\|A\_\{e\}\|\\,\|B\_\{e\}\|\.\(21\)In the segmentation setting, this suggests the following heuristic question: if one wants to perturb edges while causing as little downstream damage as possible, is it better to choose edges with small structural score than edges that merely have small local weight? The experiment below is designed to compare exactly those two notions of “safe” edits\.

### 5\.1Setup

We use the classical Cameraman image, shown in Figure[3](https://arxiv.org/html/2608.04014#S5.F3.7)\. The grayscale image is converted to floating\-point values in\[0,1\]\[0,1\]and oversegmented intoKKSLIC superpixels\. Each superpixel becomes a node in a region adjacency graph; neighboring superpixels are connected, and each edge is assigned a feature distance based on mean intensity and normalized centroid coordinates\.

We then compute the tie\-broken MSTTTand the induced ultrametricudu\_\{d\}\. A reference segmentation is obtained by cutting theK−1K\-1heaviest MST edges and taking the resulting connected components; this is the standard MST view of single linkage\. The resulting reference partitions forK=7,8,9,10K=7,8,9,10are shown in the top row of Figure[4](https://arxiv.org/html/2608.04014#S5.F4)\.

![Refer to caption](https://arxiv.org/html/2608.04014v1/cameraman.png)Figure 3:The classic Cameraman image\.For each tree edgee=\{a,b\}e=\\\{a,b\\\}, we compute three quantities:

- •the structural score Sunion​\(e\)=\|Ae\|​\|Be\|;S\_\{\\mathrm\{union\}\}\(e\)=\|A\_\{e\}\|\\,\|B\_\{e\}\|;\(22\)
- •the raw edge weightw​\(e\)w\(e\), representing local boundary contrast;
- •the worst\-case segmentation impact impact​\(e\):=max⁡\{1−ARI​\(base,decrease​\(e\)\),1−ARI​\(base,increase​\(e\)\)\},\\mathrm\{impact\}\(e\):=\\max\\Bigl\\\{1\-\\mathrm\{ARI\}\\bigl\(\\mathrm\{base\},\\mathrm\{decrease\}\(e\)\\bigr\),\\,1\-\\mathrm\{ARI\}\\bigl\(\\mathrm\{base\},\\mathrm\{increase\}\(e\)\\bigr\)\\Bigr\\\},\(23\)wheredecrease​\(e\)\\mathrm\{decrease\}\(e\)andincrease​\(e\)\\mathrm\{increase\}\(e\)are the segmentations obtained after multiplying the weight ofeeby10−210^\{\-2\}or10210^\{2\}, respectively\.

### 5\.2Safe\-edit curves

For each MST edgeee, we therefore have a structural scoreSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\), a local scorew​\(e\)w\(e\), and an empirical damage scoreimpact​\(e\)\\mathrm\{impact\}\(e\)\. For each ranking rule \(SunionS\_\{\\mathrm\{union\}\}orww\), we sort MST edges in ascending order, so that smaller score means “safer\.” For a prefix sizekk\(shown on the x\-axis as a fraction of all MST edges\), we take the bottom\-kkedges under that ranking as the safe\-to\-edit set and report the maximumimpact​\(e\)\\mathrm\{impact\}\(e\)inside that set\. This produces the two safe\-edit curves shown in the bottom row of Figure[4](https://arxiv.org/html/2608.04014#S5.F4)\.

The comparison is intentionally aligned with the theory\. The scorew​\(e\)w\(e\)is a purely local boundary heuristic, whereasSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)is derived from the exposed\-cut geometry of Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)\. Thus, if the theory is capturing a meaningful notion of structural vulnerability, then ranking edges bySunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)should produce safer edit sets than ranking them by raw weight alone\.

![Refer to caption](https://arxiv.org/html/2608.04014v1/cameraman_7.png)
![Refer to caption](https://arxiv.org/html/2608.04014v1/cameraman_8.png)
![Refer to caption](https://arxiv.org/html/2608.04014v1/cameraman_9.png)
![Refer to caption](https://arxiv.org/html/2608.04014v1/cameraman_10.png)
![Refer to caption](https://arxiv.org/html/2608.04014v1/cameraman_segmentation/K7_curve.png)\(a\)K=7K=7Curves
![Refer to caption](https://arxiv.org/html/2608.04014v1/cameraman_segmentation/K8_curve.png)\(b\)K=8K=8Curves
![Refer to caption](https://arxiv.org/html/2608.04014v1/cameraman_segmentation/K9_curve.png)\(c\)K=9K=9Curves
![Refer to caption](https://arxiv.org/html/2608.04014v1/cameraman_segmentation/K10_curve.png)\(d\)K=10K=10Curves

Figure 4:Safe\-edit curves \(bottom row\) and corresponding reference segmentations \(top row\) for Cameraman image acrossK=7K=7–1010\. For eachKK, we report worst\-case1−ARI1\-\\mathrm\{ARI\}when edits are restricted to bottom\-kkMST edges ranked bySunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)or byw​\(e\)w\(e\)\.
### 5\.3Results

Figure[4](https://arxiv.org/html/2608.04014#S5.F4)\(bottom row\) shows that, acrossK=7,8,9,10K=7,8,9,10, the safe\-edit curve based onSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)consistently lies below the curve based onw​\(e\)w\(e\)\. In other words, when the safe\-edit budget is fixed, the worst damage incurred by editing low\-SunionS\_\{\\mathrm\{union\}\}edges is smaller than the worst damage incurred by editing edges selected solely by local boundary contrast\. This indicates that the structural score derived from the theory yields a more reliable notion of “safe directions to perturb” than a purely local heuristic\.

## 6Empirical Case Study \- III: Active MST\-Edge Verification for Semi\-Supervised Clustering

##### Motivation\.

Our perturbation analysis identifies a simple structural quantity for a tree edge,

Sunion​\(e\)=\|Ae\|​\|Be\|,S\_\{\\mathrm\{union\}\}\(e\)=\|A\_\{e\}\|\\,\|B\_\{e\}\|,whereAeA\_\{e\}andBeB\_\{e\}are the two connected components obtained by deletingeefrom the MST\. This score measures how many cross\-component pairs are exposed by a cut and therefore how many pairwise ultrametric relations can potentially change when that edge is corrected\. This suggests a concrete human\-in\-the\-loop use case for hierarchical clustering: if a practitioner can verify only a small number of MST edges using a human annotator, metadata source, or trusted secondary model, which edges should be checked first? We study this question as a budgeted*active MST\-edge verification*problem and use it to evaluate whether the theory\-derived scoreSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)yields a strong query policy in practice\.

### 6\.1Task and scope of the comparison

We consider a fixed\-backbone active verification problem\. Starting from a common feature representation, we build a single sparse graph, compute a single minimum spanning tree, and evaluate several edge\-ranking rules on that same tree\. Thus, the experiment is*not*a comparison of different end\-to\-end clustering pipelines or different graph\-construction schemes\. Instead, it asks a narrower and cleaner question:

> *Given a fixed sparse single\-linkage backbone and a limited verification budget, which MST\-edge priority rule most effectively improves the resulting clustering?*

This shared\-backbone design is deliberate\. If each baseline were allowed to build its own graph and its own tree, then differences in performance would conflate two effects: the quality of the backbone itself and the quality of the query rule imposed on that backbone\. By holding the backbone fixed, we isolate the practical question relevant to a user who already has a hierarchical clustering and can only afford to verify a small number of edges\.

### 6\.2Datasets

The benchmark is run on the following full datasets:

- •MNIST\[LeCun et al\.,[2002](https://arxiv.org/html/2608.04014#bib.bib19)\],
- •USPS\[Liu et al\.,[2018](https://arxiv.org/html/2608.04014#bib.bib20)\],
- •HAR\[Anguita et al\.,[2013](https://arxiv.org/html/2608.04014#bib.bib1)\],
- •Olivetti Faces\(Credit to Cambridge University\),
- •OptDigits\[Kaynak,[1995](https://arxiv.org/html/2608.04014#bib.bib17)\]\.

These datasets span handwritten digits, human activity recognition, and face recognition, and therefore provide a heterogeneous test bed for active verification on MST\-induced hierarchies\. The goal of this suite is not to optimize performance for any one modality, but to test whether the query rules behave consistently across datasets with different geometry, class counts, and sample sizes\.

### 6\.3Common preprocessing pipeline

All methods share the same preprocessing pipeline\. For each dataset, the raw features are:

1. 1\.standardized,
2. 2\.projected to3232dimensions by PCA whenever the ambient dimension exceeds3232,
3. 3\.and thenℓ2\\ell\_\{2\}\-normalized\.

This produces a common normalized feature space in which the sparse neighborhood graph and the MST are constructed\.

Using a fixed preprocessing pipeline is important here\. The aim is not to perform dataset\-specific tuning for each baseline, but to compare edge\-ranking policies under the same representation and the same hierarchical backbone\.

### 6\.4Sparse graph construction and common MST backbone

Let the preprocessed dataset be

𝒳=\{x1,…,xn\},yi∈\{1,…,K\}\.\\mathcal\{X\}=\\\{x\_\{1\},\\dots,x\_\{n\}\\\},\\qquad y\_\{i\}\\in\\\{1,\\dots,K\\\}\.The labels are used only to simulate the oracle and to evaluate the final clustering; none of the query rules uses label information\.

To scale the benchmark to full datasets, we do not construct the complete weighted graph\. Instead, for each point we compute itskknearest neighbors in feature space with

and retain only those sparse neighborhood edges\. Let

di​jraw=‖xi−xj‖2d^\{\\mathrm\{raw\}\}\_\{ij\}=\\\|x\_\{i\}\-x\_\{j\}\\\|\_\{2\}denote the raw Euclidean distance on the retainedkk\-NN graph\.

To reduce sensitivity to local density variation, we use a locally scaled metric\. Letσi\\sigma\_\{i\}be the distance from pointiito itsk0k\_\{0\}\-th nearest neighbor in the raw neighborhood graph, with

The locally scaled edge weight is then

di​jls=di​jrawσi​σj\.d^\{\\mathrm\{ls\}\}\_\{ij\}=\\frac\{d^\{\\mathrm\{raw\}\}\_\{ij\}\}\{\\sqrt\{\\sigma\_\{i\}\\sigma\_\{j\}\}\}\.We compute the MST of this sparse graph under the locally scaled weights\. The resulting tree is the common combinatorial backbone for all query policies\.

This choice should be interpreted carefully\. For example, the raw\-weight baseline does*not*build a separate raw\-distance MST\. Rather, it ranks the edges of the common locally scaled MST by their raw Euclidean lengths\. Likewise, the structural and feature\-aware baselines are all evaluated on the same fixed tree\. This keeps the candidate edge set identical across methods\.

### 6\.5Unverified baseline clustering

Before any active verification, we form an*unverified baseline clustering*by cutting the\(K−1\)\(K\-1\)heaviest edges of the common MST under the backbone ordering\. This produces exactlyKKconnected components and serves as the reference clustering against which all budgeted query policies are compared\.

Formally, if the common MST edges are ordered by decreasing backbone weight as

e\(1\),e\(2\),…,e\(n−1\),e\_\{\(1\)\},e\_\{\(2\)\},\\dots,e\_\{\(n\-1\)\},then the unverified baseline partition is obtained by deleting

\{e\(1\),…,e\(K−1\)\}\.\\\{e\_\{\(1\)\},\\dots,e\_\{\(K\-1\)\}\\\}\.

### 6\.6Active verification protocol

A query policy provides an ordering of MST edges\. Given a query budgetbb, we inspect the firstbbedges in that policy’s ranking\. For a queried edge

e=\{u,v\}∈ET,e=\\\{u,v\\\}\\in E\_\{T\},the oracle returns

eis wrong⇔yu≠yv\.\\text\{$e$ is wrong\}\\iff y\_\{u\}\\neq y\_\{v\}\.Let

𝒞b=\{e∈ET:ewas queried among the firstbedges and declared wrong\}\\mathcal\{C\}\_\{b\}=\\\{e\\in E\_\{T\}:\\text\{$e$ was queried among the first $b$ edges and declared wrong\}\\\}denote the set of queried edges that are found to be incorrect\.

The post\-verification clustering is obtained in two stages:

1. 1\.every edge in𝒞b\\mathcal\{C\}\_\{b\}is forced to be cut;
2. 2\.if fewer than\(K−1\)\(K\-1\)cuts have been made, we cut additional heaviest edges from the same common backbone ordering until the forest has exactlyKKconnected components\.

Thus, all methods are compared under the same supervision budget, the same oracle, the same target number of clusters, and the same final backbone\-completion rule\. This protocol should therefore be viewed as a comparison of*which queried corrections are most useful within a shared sparse single\-linkage correction pipeline*, not as a comparison of fully independent end\-to\-end algorithms\.

This distinction matters\. Because the final partition is completed using the common backbone order, the benchmark isolates the value of the*verified cuts selected by each policy*while keeping the downstream completion mechanism fixed\. That makes the protocol practically relevant for settings where the backbone hierarchy is treated as given and only a limited number of corrections can be injected into it\.

##### Budgets\.

Since an MST onnnvertices has

edges, we use the budget set

b∈\{0,⌈0\.005​m⌉,⌈0\.01​m⌉,⌈0\.02​m⌉,⌈0\.05​m⌉,⌈0\.10​m⌉\}\.b\\in\\left\\\{0,\\;\\left\\lceil 0\.005m\\right\\rceil,\\;\\left\\lceil 0\.01m\\right\\rceil,\\;\\left\\lceil 0\.02m\\right\\rceil,\\;\\left\\lceil 0\.05m\\right\\rceil,\\;\\left\\lceil 0\.10m\\right\\rceil\\right\\\}\.Equivalently, we inspect approximately0%0\\%,0\.5%0\.5\\%,1%1\\%,2%2\\%,5%5\\%, and10%10\\%of the tree edges\.

##### Random baseline\.

For the random policy, we selectbbMST edges uniformly at random without replacement\. Because this baseline is stochastic, we report the mean and standard deviation over1010independent trials at each budget\.

### 6\.7Our method: the structural scoreSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)

For an MST edgee∈ETe\\in E\_\{T\}, deletingeepartitions the tree into two connected components,

Ae⊔Be=V\.A\_\{e\}\\sqcup B\_\{e\}=V\.Our theory\-derived score is

Sunion​\(e\)=\|Ae\|​\|Be\|\.S\_\{\\mathrm\{union\}\}\(e\)=\|A\_\{e\}\|\\,\|B\_\{e\}\|\.
##### Interpretation\.

This quantity counts the number of cross\-component pairs exposed by cutting the edge\. Every pair\(i,j\)\(i,j\)withi∈Aei\\in A\_\{e\}andj∈Bej\\in B\_\{e\}has its unique tree path crossingee, so any structural change ateecan potentially affect the ultrametric relation of all such pairs\. Large values ofSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)therefore identify*load\-bearing*edges: edges whose correction can affect a large portion of the induced hierarchy\.

##### Connection to the theory\.

This is precisely the viewpoint suggested by the Hamming\-stability analysis\. Sparse perturbations do not propagate uniformly through the tree; their effect is mediated by the exposed cut\-pair set\. The quantity\|Ae\|​\|Be\|\|A\_\{e\}\|\|B\_\{e\}\|is exactly the size of that exposed set for a single edge\. The resulting score is therefore not an ad hoc heuristic, but the operational form of the structural quantity singled out by the perturbation analysis\.

##### Query rule\.

Our method ranks MST edges by decreasingSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)and verifies them in that order\.

### 6\.8Benchmark baselines

We compare against the following baselines, all evaluated on the same common MST backbone\.

#### 6\.8\.1Raw\-weight baseline

For an MST edge

the raw\-weight score\[Zahn,[2006](https://arxiv.org/html/2608.04014#bib.bib33)\]is

wraw​\(e\)=du​vraw\.w\_\{\\mathrm\{raw\}\}\(e\)=d^\{\\mathrm\{raw\}\}\_\{uv\}\.This baseline ranks edges by decreasing raw Euclidean length\. It is the most direct local heuristic: long edges are treated as suspicious bridges\. However, it uses only endpoint geometry and ignores the structural role of the edge inside the tree\.

#### 6\.8\.2Scaled\-weight baseline

The scaled\-weight\[Zelnik\-Manor and Perona,[2004](https://arxiv.org/html/2608.04014#bib.bib34)\]baseline ranks edges by their backbone weight,

wls​\(e\)=du​vls\.w\_\{\\mathrm\{ls\}\}\(e\)=d^\{\\mathrm\{ls\}\}\_\{uv\}\.Relative to raw edge length, this score discounts purely density\-driven effects and therefore provides a stronger local geometric baseline on the shared sparse tree\.

#### 6\.8\.3Centroid\-gap baseline

For an edgeee, letAeA\_\{e\}andBeB\_\{e\}be the two connected components obtained by deletingee\. Define their centroids by

μAe=1\|Ae\|​∑i∈Aexi,μBe=1\|Be\|​∑i∈Bexi\.\\mu\_\{A\_\{e\}\}=\\frac\{1\}\{\|A\_\{e\}\|\}\\sum\_\{i\\in A\_\{e\}\}x\_\{i\},\\qquad\\mu\_\{B\_\{e\}\}=\\frac\{1\}\{\|B\_\{e\}\|\}\\sum\_\{i\\in B\_\{e\}\}x\_\{i\}\.The centroid\-gap score\[McQueen,[1967](https://arxiv.org/html/2608.04014#bib.bib22)\]is

Gcg​\(e\)=‖μAe−μBe‖22\.G\_\{\\mathrm\{cg\}\}\(e\)=\\\|\\mu\_\{A\_\{e\}\}\-\\mu\_\{B\_\{e\}\}\\\|\_\{2\}^\{2\}\.This baseline ignores the local edge weight and instead asks whether the two sides of the cut are well separated in feature space\.

#### 6\.8\.4Ward\-bridge baseline

The Ward\-bridge score\[Ward Jr,[1963](https://arxiv.org/html/2608.04014#bib.bib32)\]is

GWard​\(e\)=\|Ae\|​\|Be\|\|Ae\|\+\|Be\|​‖μAe−μBe‖22\.G\_\{\\mathrm\{Ward\}\}\(e\)=\\frac\{\|A\_\{e\}\|\|B\_\{e\}\|\}\{\|A\_\{e\}\|\+\|B\_\{e\}\|\}\\,\\\|\\mu\_\{A\_\{e\}\}\-\\mu\_\{B\_\{e\}\}\\\|\_\{2\}^\{2\}\.This is the usual Ward merge penalty written as a split score on the tree\. It combines centroid separation with component size and therefore acts as a stronger, size\-aware feature baseline\.

#### 6\.8\.5Fisher\-bridge baseline

Let

r​\(Ae\)=1\|Ae\|​∑i∈Ae‖xi−μAe‖22,r​\(Be\)=1\|Be\|​∑i∈Be‖xi−μBe‖22r\(A\_\{e\}\)=\\frac\{1\}\{\|A\_\{e\}\|\}\\sum\_\{i\\in A\_\{e\}\}\\\|x\_\{i\}\-\\mu\_\{A\_\{e\}\}\\\|\_\{2\}^\{2\},\\qquad r\(B\_\{e\}\)=\\frac\{1\}\{\|B\_\{e\}\|\}\\sum\_\{i\\in B\_\{e\}\}\\\|x\_\{i\}\-\\mu\_\{B\_\{e\}\}\\\|\_\{2\}^\{2\}denote the mean squared within\-component radii\. The Fisher\-bridge score\[Fisher,[1936](https://arxiv.org/html/2608.04014#bib.bib12)\]is

GFisher​\(e\)=‖μAe−μBe‖22r​\(Ae\)\+r​\(Be\)\+ε,G\_\{\\mathrm\{Fisher\}\}\(e\)=\\frac\{\\\|\\mu\_\{A\_\{e\}\}\-\\mu\_\{B\_\{e\}\}\\\|\_\{2\}^\{2\}\}\{r\(A\_\{e\}\)\+r\(B\_\{e\}\)\+\\varepsilon\},whereε\>0\\varepsilon\>0is a small numerical constant for numerical stability\. This baseline favors cuts whose two sides are well separated relative to their internal spread\.

#### 6\.8\.6Random baseline

Finally, we include a random\-query baseline that selects edges uniformly at random\. This provides a lower\-bound reference and checks that any observed gains are due to meaningful prioritization rather than merely the presence of supervision\.

### 6\.9Evaluation metrics

After each budgeted verification step, we compare the resulting clustering against the ground\-truth labels using four metrics\.

##### Cluster purity\.

If the final clustering is

𝒫=\{C1,…,CM\},\\mathcal\{P\}=\\\{C\_\{1\},\\dots,C\_\{M\}\\\},its purity is

Purity​\(𝒫,y\)=1n​∑m=1Mmaxc∈\{1,…,K\}⁡\|\{i∈Cm:yi=c\}\|\.\\mathrm\{Purity\}\(\\mathcal\{P\},y\)=\\frac\{1\}\{n\}\\sum\_\{m=1\}^\{M\}\\max\_\{c\\in\\\{1,\\dots,K\\\}\}\\bigl\|\\\{i\\in C\_\{m\}:\\ y\_\{i\}=c\\\}\\bigr\|\.Purity is easy to interpret, though it is relatively forgiving to fragmentation\.

##### Normalized Mutual Information \(NMI\)\.

We report the normalized mutual information between the recovered cluster labels and the ground\-truth labels\. NMI measures global agreement between the two partitions\.

##### Adjusted Rand Index \(ARI\)\.

We also report the adjusted Rand index, which evaluates pairwise agreement between the recovered clustering and the ground truth while correcting for chance\.

##### Verified wrong edges\.

Finally, we report the number of queried edges that are actually incorrect,

Wb=\#​\{e​queried at budget​b:yu≠yv\}\.W\_\{b\}=\\\#\\\{e\\text\{ queried at budget \}b:y\_\{u\}\\neq y\_\{v\}\\\}\.This diagnostic is useful because a good query policy need not maximize only the raw count of wrong edges discovered; what matters is whether the queried wrong edges are consequential for the final hierarchy\.

### 6\.10Efficient computation of the benchmark scores

All methods share the same preprocessing, sparse graph construction, and MST computation stages\. The main computational distinction lies in how the candidate edges are scored once the tree has been built\.

##### Structural score\.

The scoreSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)depends only on subtree sizes\. After rooting the MST once, all valuesSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)are obtained in a single tree pass, which costs

followed by

to sort the edges\.

##### Raw\-weight and scaled\-weight baselines\.

These baselines already have one scalar value per MST edge, so after the tree is built they require only sorting:

##### Centroid\-gap, Ward\-bridge, and Fisher\-bridge baselines\.

These baselines require component\-level feature statistics\. In the implementation, subtree sizes, subtree sums, and subtree squared\-norm sums are computed in one rooted\-tree pass\. This yields all required centroids and within\-component radii for every edge in

after which sorting again costs

Hence the total post\-MST complexity for these feature\-aware baselines is

O​\(n​d\+n​log⁡n\)\.O\(nd\+n\\log n\)\.

### 6\.11What this experiment tests

This benchmark separates several distinct notions of edge importance:

1. 1\.local geometric salience, captured by raw and scaled edge weights;
2. 2\.pure structural exposure, captured bySunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\);
3. 3\.component\-level separation, captured by centroid\-gap;
4. 4\.size\-aware feature separation, captured by Ward\-bridge;
5. 5\.separation relative to internal spread, captured by Fisher\-bridge\.

This makes the experiment substantially more informative than a simple comparison against raw edge length or random querying\. IfSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)outperforms the local geometric baselines, then the theory is identifying more than long\-edge effects\. If it remains competitive with the feature\-aware baselines, then the perturbation\-theoretic notion of a load\-bearing edge is capturing a practically useful structural proxy for meaningful corrections in the hierarchy\.

### 6\.12Empirical goal

The empirical goal is therefore modest and well defined: to test whether the theory\-derived score

Sunion​\(e\)=\|Ae\|​\|Be\|S\_\{\\mathrm\{union\}\}\(e\)=\|A\_\{e\}\|\\,\|B\_\{e\}\|provides an effective and computationally cheap priority rule for budgeted edge verification on a fixed sparse MST backbone\. In this sense, the experiment serves as a practical validation of the structural quantity identified by the perturbation analysis\.

### 6\.13Empirical summary

Results are shown in Fig\.[5](https://arxiv.org/html/2608.04014#S6.F5)\. Across the benchmark suite, querying bySunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)consistently improves clustering quality more rapidly than raw\-weight, scaled\-weight, and random querying, and remains competitive with the stronger component\-level baselines such as centroid\-gap, Fisher\-bridge, and Ward\-bridge\. This is the practical machine\-learning role of the theory: the Hamming\-stability\-derived structural score yields an efficient active\-verification policy for hierarchical clustering on full real datasets\.

![Refer to caption](https://arxiv.org/html/2608.04014v1/results_full_sparse_expanded_baselines/har_sparse_verification_expanded_baselines.png)

![Refer to caption](https://arxiv.org/html/2608.04014v1/results_full_sparse_expanded_baselines/mnist_784_sparse_verification_expanded_baselines.png)

![Refer to caption](https://arxiv.org/html/2608.04014v1/results_full_sparse_expanded_baselines/olivetti_faces_sparse_verification_expanded_baselines.png)

![Refer to caption](https://arxiv.org/html/2608.04014v1/results_full_sparse_expanded_baselines/optdigits_sparse_verification_expanded_baselines.png)

![Refer to caption](https://arxiv.org/html/2608.04014v1/results_full_sparse_expanded_baselines/usps_sparse_verification_expanded_baselines.png)

Figure 5:Budgeted active MST\-edge verification for semi\-supervised clustering\. Clustering quality and verified\-wrong\-edge counts versus verification budget on a fixed sparse single\-linkage backbone\. The theory\-derived scoreSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)provides an effective and computationally cheap query rule, outperforming raw/scaled\-weight and random baselines and remaining competitive with stronger feature\-aware policies\.An important qualitative takeaway is that the purely structural scoreSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)is often on par with the more feature\-aware Ward\-bridge baseline\. This is notable because the two rules arise from different principles\. Ward\-bridge is a classical geometric criterion based on between\-component separation and component size, whereasSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)emerges directly from our ultrametric perturbation analysis as the number of cross\-component pairs exposed by a cut\. Thus, the experiments suggest that the load\-bearingness identified by the theory is not merely a graph\-theoretic curiosity: it aligns closely with strong feature\-aware notions of meaningful splits while remaining simpler, tree\-only, and theoretically motivated\.

Furthermore, comparing the clustering performance against the raw count of verified wrong edges \(Fig\.[5](https://arxiv.org/html/2608.04014#S6.F5), bottom rows\) reveals a critical dynamic\. The local geometric baselines—raw and scaled weight—successfully identify the highest absolute number of incorrect edges, yet correcting them yields almost no improvement in global clustering quality\. In contrast,Sunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)and Ward\-bridge trigger massive gains despite discovering significantly fewer incorrect edges in total\. This empirically validates the core thesis of our perturbation analysis: not all tree edges are structurally equal\. Local heuristics waste the supervision budget snipping off isolated, structurally irrelevant outliers, whereasSunion​\(e\)S\_\{\\mathrm\{union\}\}\(e\)successfully targets the load\-bearing bridges whose correction resolves macroscopic ultrametric violations across large component

## 7Conclusion

We developed a sparsity\-aware stability theory for the subdominant \(minmax\) ultrametric, complementing classicalℓ∞\\ell\_\{\\infty\}/Gromov–Hausdorff results with anℓ0\\ell\_\{0\}\-type perspective that controls the extent of change under sparse edits\. Our analysis shows that propagation is mediated by the MST: only pairs whose tree paths traverse edited or newly exposed cuts can change, yielding a localization in terms of exposed cut\-pair sets, a sharp per\-edit scoreSunion​\(f\)S\_\{\\mathrm\{union\}\}\(f\), and a tree\-only global envelopeL¯T\\bar\{L\}\_\{T\}\. We further proved that this instance dependence is unavoidable by exhibiting single\-edit constructions withΘ​\(n2\)\\Theta\(n^\{2\}\)changes, and identified explicit single\-edit sharpness examples together with conditional multi\-edit regimes in which the upper bound is asymptotically tight\. Together, these results offer a structural, interpretable account of how local perturbations can \(or cannot\) ripple through single\-linkage hierarchies, and motivate using the associated risk scores as practical diagnostics for locating robust versus load\-bearing edges in real data\.

## References

- Anguita et al\. \[2013\]Davide Anguita, Alessandro Ghio, Luca Oneto, Xavier Parra, Jorge Luis Reyes\-Ortiz, et al\.A public domain dataset for human activity recognition using smartphones\.In*Esann*, volume 3, pages 3–4, 2013\.
- Azarmehr et al\. \[2025\]Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram, Jakub Lącki, Vahab Mirrokni, and Peilin Zhong\.Massively parallel minimum spanning tree in general metric spaces\.In*Proceedings of the 2025 Annual ACM\-SIAM Symposium on Discrete Algorithms \(SODA\)*, pages 143–174\. SIAM, 2025\.
- Carlsson et al\. \[2010\]Gunnar E Carlsson, Facundo Mémoli, et al\.Characterization, stability and convergence of hierarchical clustering methods\.*J\. Mach\. Learn\. Res\.*, 11\(Apr\):1425–1470, 2010\.
- Chen et al\. \[2024\]Samantha Chen, Puoya Tabaghi, and Yusu Wang\.Learning ultrametric trees for optimal transport regression\.In*Proceedings of the AAAI Conference on Artificial Intelligence*, volume 38, pages 20657–20665, 2024\.
- Chierchia and Perret \[2019\]Giovanni Chierchia and Benjamin Perret\.Ultrametric fitting by gradient descent\.*Advances in neural information processing systems*, 32, 2019\.
- Chowdhury et al\. \[2016\]Samir Chowdhury, Facundo Mémoli, and Zane T Smith\.Improved error bounds for tree representations of metric spaces\.*Advances in Neural Information Processing Systems*, 29, 2016\.
- Cormen et al\. \[2022\]Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein\.*Introduction to algorithms*\.2022\.
- de Vos and Grilnberger \[2025\]Tijn de Vos and Mara Grilnberger\.Dynamic matroids: Base packing and covering\.*arXiv preprint arXiv:2511\.15460*, 2025\.
- Devijver et al\. \[2024\]Emilie Devijver, Rémi Molinier, and Mélina Gallopin\.Stable network inference in high\-dimensional graphical model using single\-linkage\.*arXiv preprint arXiv:2406\.09865*, 2024\.
- Dey et al\. \[2017\]Tamal K\. Dey, Alfred Rossi, and Anastasios Sidiropoulos\.Temporal Hierarchical Clustering\.In Yoshio Okamoto and Takeshi Tokuyama, editors,*28th International Symposium on Algorithms and Computation \(ISAAC 2017\)*, volume 92 of*Leibniz International Proceedings in Informatics \(LIPIcs\)*, pages 28:1–28:12, Dagstuhl, Germany, 2017\. Schloss Dagstuhl – Leibniz\-Zentrum für Informatik\.ISBN 978\-3\-95977\-054\-5\.doi:10\.4230/LIPIcs\.ISAAC\.2017\.28\.URL[https://drops\.dagstuhl\.de/entities/document/10\.4230/LIPIcs\.ISAAC\.2017\.28](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.28)\.
- Draganov et al\. \[2025\]Andrew Draganov, Pascal Weber, Rasmus Skibdahl Melanchton Jørgensen, Anna Beer, Claudia Plant, and Ira Assent\.I want’em all \(at once\)–ultrametric cluster hierarchies\.*arXiv preprint arXiv:2502\.14018*, 2025\.
- Fisher \[1936\]Ronald A Fisher\.The use of multiple measurements in taxonomic problems\.*Annals of eugenics*, 7\(2\):179–188, 1936\.
- Harb et al\. \[2023\]Elfarouk Harb, Kent Quanrud, and Chandra Chekuri\.Convergence to lexicographically optimal base in a \(contra\) polymatroid and applications to densest subgraph and tree packing\.*arXiv preprint arXiv:2305\.02987*, 2023\.
- Hartigan \[1985\]John A Hartigan\.Statistical theory in clustering\.*Journal of classification*, 2\(1\):63–76, 1985\.
- He et al\. \[2024\]Haodi He, Colton Stearns, Adam W Harley, and Leonidas J Guibas\.View\-consistent hierarchical 3d segmentation using ultrametric feature fields\.In*European Conference on Computer Vision*, pages 268–286\. Springer, 2024\.
- Jain and Dubes \[1988\]Anil K Jain and Richard C Dubes\.*Algorithms for clustering data*\.Prentice\-Hall, Inc\., 1988\.
- Kaynak \[1995\]C Kaynak\.Methods of combining multiple classifiers and their applications to handwritten digit recognition\.*Unpublished master’s thesis, Bogazici University*, 1995\.
- Lapertot et al\. \[2024\]Raphael Lapertot, Giovanni Chierchia, and Benjamin Perret\.End\-to\-end ultrametric learning for hierarchical segmentation\.In*International Conference on Discrete Geometry and Mathematical Morphology*, pages 286–297\. Springer, 2024\.
- LeCun et al\. \[2002\]Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner\.Gradient\-based learning applied to document recognition\.*Proceedings of the IEEE*, 86\(11\):2278–2324, 2002\.
- Liu et al\. \[2018\]Ling Liu, Yanzhao Wu, Wenqi Wei, Wenqi Cao, Semih Sahin, and Qi Zhang\.Benchmarking Deep Learning Frameworks: Design Considerations, Metrics and Beyond\.In*2018 IEEE 38th International Conference on Distributed Computing Systems \(ICDCS\)*, pages 1258–1269, July 2018\.doi:10\.1109/ICDCS\.2018\.00125\.
- Martínez\-Pérez \[2015\]A Martínez\-Pérez\.Gromov–hausdorff stability of linkage\-based hierarchical clustering methods\.*Advances in Mathematics*, 279:234–262, 2015\.
- McQueen \[1967\]James B McQueen\.Some methods of classification and analysis of multivariate observations\.In*Proc\. of 5th Berkeley Symposium on Math\. Stat\. and Prob\.*, pages 281–297, 1967\.
- Mikhailov \[2025\]IN Mikhailov\.Ultrametric spaces and clouds\.*arXiv preprint arXiv:2501\.19346*, 2025\.
- N’guessan \[2025\]Gnankan Landry Regis N’guessan\.v\-punns: van der put neural networks for transparent ultrametric representation learning\.*arXiv preprint arXiv:2508\.01010*, 2025\.
- Patlin and van den Brand \[2025\]Gryphon Patlin and Jan van den Brand\.Sublinear\-time algorithm for mst\-weight revisited\.In*2025 Symposium on Simplicity in Algorithms \(SOSA\)*, pages 46–53\. SIAM, 2025\.
- Perret and Cousty \[2022\]Benjamin Perret and Jean Cousty\.Component tree loss function: Definition and optimization\.In*International Conference on Discrete Geometry and Mathematical Morphology*, pages 248–260\. Springer, 2022\.
- Ritzert et al\. \[2025\]Martin Ritzert, Polina Turishcheva, Laura Hansel, Paul Wollenhaupt, Marissa A Weis, and Alexander S Ecker\.Hierarchical clustering with maximum density paths and mixture models\.*arXiv preprint arXiv:2503\.15582*, 2025\.
- Rolle and Scoccola \[2024\]Alexander Rolle and Luis Scoccola\.Stable and consistent density\-based clustering via multiparameter persistence\.*Journal of Machine Learning Research*, 25\(258\):1–74, 2024\.
- Sanders and Schimek \[2023\]Peter Sanders and Matthias Schimek\.Engineering massively parallel mst algorithms\.In*2023 IEEE International Parallel and Distributed Processing Symposium \(IPDPS\)*, pages 691–701\. IEEE, 2023\.
- Shepard \[1962\]Roger N Shepard\.The analysis of proximities: multidimensional scaling with an unknown distance function\. i\.*Psychometrika*, 27\(2\):125–140, 1962\.
- Sibson \[1971\]Robin Sibson\.*Mathematical taxonomy*\.Wiley, 1971\.
- Ward Jr \[1963\]Joe H Ward Jr\.Hierarchical grouping to optimize an objective function\.*Journal of the American statistical association*, 58\(301\):236–244, 1963\.
- Zahn \[2006\]Charles T Zahn\.Graph\-theoretical methods for detecting and describing gestalt clusters\.*IEEE Transactions on computers*, 100\(1\):68–86, 2006\.
- Zelnik\-Manor and Perona \[2004\]Lihi Zelnik\-Manor and Pietro Perona\.Self\-tuning spectral clustering\.*Advances in neural information processing systems*, 17, 2004\.
- Zhu et al\. \[2017\]Dekang Zhu, Dan P Guralnik, Xuezhi Wang, Xiang Li, and Bill Moran\.Statistical properties of the single linkage hierarchical clustering estimator\.*Journal of Statistical Planning and Inference*, 185:15–28, 2017\.

## Appendix AProofs of Technical Lemmas

### A\.1Proof of Lemma[2\.3](https://arxiv.org/html/2608.04014#S2.Thmtheorem3)

###### Lemma A\.1\(MST characterization\)\.

IfTTis any minimum spanning tree \(MST\) of the complete graph with weights given by the dissimilarity functiondd, thenud​\(i,j\)=maxe∈pathT​\(i,j\)⁡d​\(e\)∀i≠j\.u\_\{d\}\(i,j\)=\\max\_\{e\\in\\mathrm\{path\}\_\{T\}\(i,j\)\}d\(e\)\\quad\\forall i\\neq j\.

###### Proof\.

Fixi≠ji\\neq jand letPT​\(i,j\)P\_\{T\}\(i,j\)be the uniqueii–jjpath inTT\. Let

λ:=maxe∈PT​\(i,j\)⁡d​\(e\),\\lambda:=\\max\_\{e\\in P\_\{T\}\(i,j\)\}d\(e\),and choose an edgee⋆∈PT​\(i,j\)e^\{\\star\}\\in P\_\{T\}\(i,j\)withd​\(e⋆\)=λd\(e^\{\\star\}\)=\\lambda\. Removinge⋆e^\{\\star\}splitsTTinto two componentsAAandBBwithi∈Ai\\in Aandj∈Bj\\in B\.

BecauseTTis an MST, the tree edgee⋆e^\{\\star\}is a minimum\-weight edge across its fundamental cut\(A,B\)\(A,B\)\. Hence every pathPPfromiitojjmust contain some edge crossing\(A,B\)\(A,B\), and every such crossing edge has weight at leastλ\\lambda\. Therefore

maxe∈P⁡d​\(e\)≥λfor every path​P∈𝒫​\(i,j\),\\max\_\{e\\in P\}d\(e\)\\geq\\lambda\\qquad\\text\{for every path \}P\\in\\mathcal\{P\}\(i,j\),which implies

ud​\(i,j\)=minP∈𝒫​\(i,j\)⁡maxe∈P⁡d​\(e\)≥λ\.u\_\{d\}\(i,j\)=\\min\_\{P\\in\\mathcal\{P\}\(i,j\)\}\\max\_\{e\\in P\}d\(e\)\\geq\\lambda\.
On the other hand, the specific tree pathPT​\(i,j\)P\_\{T\}\(i,j\)has bottleneck exactlyλ\\lambda, so

ud​\(i,j\)≤maxe∈PT​\(i,j\)⁡d​\(e\)=λ\.u\_\{d\}\(i,j\)\\leq\\max\_\{e\\in P\_\{T\}\(i,j\)\}d\(e\)=\\lambda\.Combining the two inequalities yields

ud​\(i,j\)=maxe∈PT​\(i,j\)⁡d​\(e\),u\_\{d\}\(i,j\)=\\max\_\{e\\in P\_\{T\}\(i,j\)\}d\(e\),as claimed\. ∎

### A\.2Proof of Lemma[2\.4](https://arxiv.org/html/2608.04014#S2.Thmtheorem4)

###### Lemma A\.2\(Cut property, with uniqueness\)\.

Let\(A,B\)\(A,B\)be any cut ofVVand lete⋆∈Ee^\{\\star\}\\in Ebe an edge with one endpoint inAAand one inBB\. Ifd​\(e⋆\)<d​\(f\)d\(e^\{\\star\}\)<d\(f\)for every other cut edgeffacross\(A,B\)\(A,B\), thene⋆e^\{\\star\}belongs to*every*MST ofdd\.

###### Proof\.

Suppose, toward a contradiction, that there exists an MSTT′=\(V,E​\(T′\)\)T^\{\\prime\}=\(V,E\(T^\{\\prime\}\)\)withe⋆∉E​\(T′\)e^\{\\star\}\\notin E\(T^\{\\prime\}\)\. ThenT′∪\{e⋆\}T^\{\\prime\}\\cup\\\{e^\{\\star\}\\\}contains a unique simple cycleCC\. Sincee⋆e^\{\\star\}crosses\(A,B\)\(A,B\), any cycle crosses a cut an even number of times; hence there exists an edgef∈C∩Ef\\in C\\cap Ewithf≠e⋆f\\neq e^\{\\star\}that also crosses\(A,B\)\(A,B\)\. By the strict minimality ofe⋆e^\{\\star\}across the cut,d​\(f\)\>d​\(e⋆\)d\(f\)\>d\(e^\{\\star\}\)\. Define

E′′:=E​\(T′\)∪\{e⋆\}∖\{f\}\.E^\{\\prime\\prime\}\\ :=\\ E\(T^\{\\prime\}\)\\cup\\\{e^\{\\star\}\\\}\\setminus\\\{f\\\}\.\(24\)ThenE′′E^\{\\prime\\prime\}is acyclic and has\|V\|−1\|V\|\-1edges, so\(V,E′′\)\(V,E^\{\\prime\\prime\}\)is a spanning tree\. Its total weight satisfies

∑e∈E′′d​\(e\)=∑e∈E​\(T′\)d​\(e\)\+d​\(e⋆\)−d​\(f\)<∑e∈E​\(T′\)d​\(e\),\\sum\_\{e\\in E^\{\\prime\\prime\}\}d\(e\)\\ =\\ \\sum\_\{e\\in E\(T^\{\\prime\}\)\}d\(e\)\+d\(e^\{\\star\}\)\-d\(f\)\\ <\\ \\sum\_\{e\\in E\(T^\{\\prime\}\)\}d\(e\),\(25\)contradicting the minimality ofT′T^\{\\prime\}\. Hence every MST must containe⋆e^\{\\star\}\. ∎

## Appendix BProofs of Major Theorems and Corollary

### B\.1Proof of Theorem[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)

###### Theorem B\.1\(Localization of ultrametric under sparse edge edits\)\.

Letd:\(V2\)↦ℝ⩾0d:\\binom\{V\}\{2\}\\mapsto\\mathbb\{R\}\_\{\\geqslant 0\}, and letT=\(V,E​\(T\)\)T=\(V,E\(T\)\)be the \(tie\-broken under Assumption[2\.1](https://arxiv.org/html/2608.04014#S2.Thmtheorem1)\) MST ofdd\. Fore=\{a,b\}∈E​\(T\)e=\\\{a,b\\\}\\in E\(T\)letCe=\(Ae,Be\)C\_\{e\}=\(A\_\{e\},B\_\{e\}\)be its fundamental cut inTT, and writewe:=d​\(e\)w\_\{e\}:=d\(e\)\. we define the associated cut\-pair setℛe:=\{\{i,j\}∈\(V2\):i∈Ae,j∈Be\}\.\\mathcal\{R\}\_\{e\}:=\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:i\\in A\_\{e\},\\ j\\in B\_\{e\}\\bigr\\\}\.LetF⊆\(V2\)F\\subseteq\\binom\{V\}\{2\}be a set of edited edges and letd~\\tilde\{d\}be any dissimilarity withd~​\(e\)=d​\(e\)\\tilde\{d\}\(e\)=d\(e\)for alle∉Fe\\notin F\(no restriction one∈Fe\\in F\)\.

Fori≠ji\\neq jletPT​\(i,j\)P\_\{T\}\(i,j\)be the uniqueii–jjpath inTT\. From MST bottleneck representationud​\(i,j\)=maxe∈PT​\(i,j\)⁡weu\_\{d\}\(i,j\)=\\ \\max\_\{e\\in P\_\{T\}\(i,j\)\}w\_\{e\}, the following holds:

- \(i\)\(Monotone upper bound, no editedTT\-edges on the path\) IfPT​\(i,j\)∩F=∅P\_\{T\}\(i,j\)\\cap F=\\varnothing, thenud~​\(i,j\)≤ud​\(i,j\)u\_\{\\tilde\{d\}\}\(i,j\)\\ \\leq\\ u\_\{d\}\(i,j\)\.
- \(ii\)\(Sufficient conditions for equality\) IfPT​\(i,j\)∩F=∅P\_\{T\}\(i,j\)\\cap F=\\varnothingand for everye∈PT​\(i,j\)e\\in P\_\{T\}\(i,j\), all edited edgesf∈Ff\\in FcrossingCeC\_\{e\}satisfyd~​\(f\)⩾we\\tilde\{d\}\(f\)\\geqslant w\_\{e\}, thenud~​\(i,j\)=ud​\(i,j\)u\_\{\\tilde\{d\}\}\(i,j\)=u\_\{d\}\(i,j\)\.
- \(iii\)\(Pair\-count bound for possible changes\) Define the set of potentially affected MST edges ℰ:=\{e∈E​\(T\):e∈F​or​∃f∈F​crossing​Ce​with​d~​\(f\)<we\}\.\\mathcal\{E\}:=\\bigl\\\{e\\in E\(T\):e\\in F\\text\{ or \}\\exists f\\in F\\text\{ crossing \}C\_\{e\}\\text\{ with \}\\tilde\{d\}\(f\)<w\_\{e\}\\bigr\\\}\.\(26\)Then the number of unordered pairs whose ultrametric value changes satisfies \|\{\{i,j\}∈\(V2\):ud~​\(i,j\)≠ud​\(i,j\)\}\|=‖ud−ud~‖0≤\|⋃e∈ℰℛe\|=\(n2\)−∑t=1m\(\|Ct\|2\),\\bigl\|\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:u\_\{\\tilde\{d\}\}\(i,j\)\\neq u\_\{d\}\(i,j\)\\bigr\\\}\\bigr\|=\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq\\left\|\\bigcup\_\{e\\in\\mathcal\{E\}\}\\mathcal\{R\}\_\{e\}\\right\|=\\binom\{n\}\{2\}\-\\sum\_\{t=1\}^\{m\}\\binom\{\|C\_\{t\}\|\}\{2\},\(27\)whereC1,…,CmC\_\{1\},\\dots,C\_\{m\}are the vertex sets of the connected components of the forestT−ℰT\-\\mathcal\{E\}\.

###### Proof\.

*\(i\)*IfPT​\(i,j\)∩F=∅P\_\{T\}\(i,j\)\\cap F=\\varnothing, then all edges on theTT\-path are unchanged, i\.e\.d~​\(e\)=d​\(e\)\\tilde\{d\}\(e\)=d\(e\)for alle∈PT​\(i,j\)e\\in P\_\{T\}\(i,j\)\.

Hence,

ud~​\(i,j\)\\displaystyle u\_\{\\tilde\{d\}\}\(i,j\)=minP∈𝒫​\(i,j\)⁡maxf∈P⁡d~​\(f\)\\displaystyle=\\min\_\{P\\in\\mathcal\{P\}\(i,j\)\}\\ \\max\_\{f\\in P\}\\tilde\{d\}\(f\)\(28\)⩽maxe∈PT​\(i,j\)⁡d~​\(e\)=maxe∈PT​\(i,j\)⁡d​\(e\)=ud​\(i,j\)\.\\displaystyle\\leqslant\\max\_\{e\\in P\_\{T\}\(i,j\)\}\\tilde\{d\}\(e\)=\\max\_\{e\\in P\_\{T\}\(i,j\)\}d\(e\)=u\_\{d\}\(i,j\)\.
*\(ii\)*Fix distinct pointsi,ji,jsuch that the MST pathPT​\(i,j\)P\_\{T\}\(i,j\)contains no edited edges\. Lete∈PT​\(i,j\)e\\in P\_\{T\}\(i,j\)be arbitrary, and letPPbe anyii–jjpath in the complete graph\. Since deletingeeseparatesiiandjj, the pathPPmust cross the fundamental cutCeC\_\{e\}\. Letggbe any edge ofPPthat crossesCeC\_\{e\}\.

We claim that

d~​\(g\)⩾we\.\\tilde\{d\}\(g\)\\geqslant w\_\{e\}\.\(29\)Indeed, there are two cases\.

Ifg∈Fg\\in F, thenggis an edited edge crossingCeC\_\{e\}\. By assumption, every edited edge crossingCeC\_\{e\}has weight at leastwew\_\{e\}underd~\\tilde\{d\}\. In particular,

d~​\(g\)⩾we\.\\tilde\{d\}\(g\)\\geqslant w\_\{e\}\.\(30\)
Ifg∉Fg\\notin F, thend~​\(g\)=d​\(g\)\\tilde\{d\}\(g\)=d\(g\)\. Moreover, sinceeeis an MST edge defining the fundamental cutCeC\_\{e\}, every edge crossingCeC\_\{e\}has weight at leastwew\_\{e\}; otherwise replacingeeby a strictly lighter crossing edge would produce a lighter spanning tree \(cut\-property argument; cf\. Lemma[2\.4](https://arxiv.org/html/2608.04014#S2.Thmtheorem4)\)\. Hence

d~​\(g\)=d​\(g\)⩾we\.\\tilde\{d\}\(g\)=d\(g\)\\geqslant w\_\{e\}\.\(31\)
Thus in all cases the crossing edgeggonPPsatisfiesd~​\(g\)⩾we\\tilde\{d\}\(g\)\\geqslant w\_\{e\}, and therefore

maxf∈P⁡d~​\(f\)⩾d~​\(g\)⩾wefor all​e∈PT​\(i,j\)\.\\max\_\{f\\in P\}\\tilde\{d\}\(f\)\\geqslant\\tilde\{d\}\(g\)\\geqslant w\_\{e\}\\qquad\\text\{for all \}e\\in P\_\{T\}\(i,j\)\.\(32\)Consequently,

maxf∈P⁡d~​\(f\)⩾maxe∈PT​\(i,j\)⁡we=ud​\(i,j\),\\max\_\{f\\in P\}\\tilde\{d\}\(f\)\\ \\geqslant\\ \\max\_\{e\\in P\_\{T\}\(i,j\)\}w\_\{e\}\\;=\\;u\_\{d\}\(i,j\),\(33\)and therefore

ud~​\(i,j\)=minP∈𝒫​\(i,j\)⁡maxf∈P⁡d~​\(f\)⩾ud​\(i,j\)\.u\_\{\\tilde\{d\}\}\(i,j\)=\\min\_\{P\\in\\mathcal\{P\}\(i,j\)\}\\max\_\{f\\in P\}\\tilde\{d\}\(f\)\\;\\geqslant\\;u\_\{d\}\(i,j\)\.\(34\)Together with part \(i\), which givesud~​\(i,j\)⩽ud​\(i,j\)u\_\{\\tilde\{d\}\}\(i,j\)\\leqslant u\_\{d\}\(i,j\), we conclude that

ud~​\(i,j\)=ud​\(i,j\)\.u\_\{\\tilde\{d\}\}\(i,j\)=u\_\{d\}\(i,j\)\.\(35\)
*\(iii\)*We will prove the following statements \(P,Q,RP,Q,R\) to complete the proof:

- •P:\{\{i,j\}∈\(V2\):ud~​\(i,j\)≠ud​\(i,j\)\}⊆⋃e∈ℰℛe\.P:\\ \\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:u\_\{\\tilde\{d\}\}\(i,j\)\\neq u\_\{d\}\(i,j\)\\bigr\\\}\\;\\subseteq\\;\\bigcup\_\{e\\in\\mathcal\{E\}\}\\mathcal\{R\}\_\{e\}\.
- •Q:⋃e∈ℰℛe=\{\{i,j\}∈\(V2\):i​and​j​in different components of​T−ℰ\}\.Q:\\ \\bigcup\_\{e\\in\\mathcal\{E\}\}\\mathcal\{R\}\_\{e\}\\;=\\;\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:\\ i\\ \\text\{and\}\\ j\\ \\text\{in different components of \}T\-\\mathcal\{E\}\\bigr\\\}\.
- •R:\|⋃e∈ℰℛe\|=\(n2\)−∑t=1m\(\|Ct\|2\)\.R:\\ \\left\|\\ \\bigcup\_\{e\\in\\mathcal\{E\}\}\\mathcal\{R\}\_\{e\}\\ \\right\|\\;=\\;\\binom\{n\}\{2\}\-\\sum\_\{t=1\}^\{m\}\\binom\{\|C\_\{t\}\|\}\{2\}\.

Proof of \(P\): Fix\{i,j\}∈\(V2\)\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}such that

ud~​\(i,j\)≠ud​\(i,j\)\.u\_\{\\tilde\{d\}\}\(i,j\)\\neq u\_\{d\}\(i,j\)\.\(36\)We show that\{i,j\}∈ℛe\\\{i,j\\\}\\in\\mathcal\{R\}\_\{e\}for somee∈ℰe\\in\\mathcal\{E\}\.

First suppose that

PT​\(i,j\)∩F≠∅\.P\_\{T\}\(i,j\)\\cap F\\neq\\varnothing\.\(37\)Choose any edgee∈PT​\(i,j\)∩Fe\\in P\_\{T\}\(i,j\)\\cap F\. Sinceeeis an edited tree edge, by definition

e∈ℰ\.e\\in\\mathcal\{E\}\.\(38\)Becauseeelies on the unique tree path fromiitojj, deletingeeseparatesiiandjj, and hence

\{i,j\}∈ℛe\.\\\{i,j\\\}\\in\\mathcal\{R\}\_\{e\}\.\(39\)
Now suppose instead that

PT​\(i,j\)∩F=∅\.P\_\{T\}\(i,j\)\\cap F=\\varnothing\.\(40\)Since

ud~​\(i,j\)≠ud​\(i,j\),u\_\{\\tilde\{d\}\}\(i,j\)\\neq u\_\{d\}\(i,j\),\(41\)the conclusion of part \(ii\) fails\. Part \(ii\) states that if

PT​\(i,j\)∩F=∅P\_\{T\}\(i,j\)\\cap F=\\varnothing\(42\)and if for everye∈PT​\(i,j\)e\\in P\_\{T\}\(i,j\)every edited edge crossingCeC\_\{e\}satisfies

d~​\(f\)⩾we,\\tilde\{d\}\(f\)\\geqslant w\_\{e\},\(43\)then

ud~​\(i,j\)=ud​\(i,j\)\.u\_\{\\tilde\{d\}\}\(i,j\)=u\_\{d\}\(i,j\)\.\(44\)Therefore, since the first condition already holds in the present case, the second condition must fail\. Hence there exist some edgee∈PT​\(i,j\)e\\in P\_\{T\}\(i,j\)and some edited edgef∈Ff\\in FcrossingCeC\_\{e\}such that

d~​\(f\)<we\.\\tilde\{d\}\(f\)<w\_\{e\}\.\(45\)Therefore, by the definition ofℰ\\mathcal\{E\},

e∈ℰ\.e\\in\\mathcal\{E\}\.\(46\)Again, becauseeelies on the unique tree path fromiitojj, deletingeeseparatesiiandjj, so

\{i,j\}∈ℛe\.\\\{i,j\\\}\\in\\mathcal\{R\}\_\{e\}\.\(47\)
In either case,\{i,j\}\\\{i,j\\\}belongs toℛe\\mathcal\{R\}\_\{e\}for somee∈ℰe\\in\\mathcal\{E\}\. Therefore

\{\{i,j\}∈\(V2\):ud~​\(i,j\)≠ud​\(i,j\)\}⊆⋃e∈ℰℛe\.\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:u\_\{\\tilde\{d\}\}\(i,j\)\\neq u\_\{d\}\(i,j\)\\bigr\\\}\\subseteq\\bigcup\_\{e\\in\\mathcal\{E\}\}\\mathcal\{R\}\_\{e\}\.\(48\)
Proof of \(Q\): If\{i,j\}∈ℛe\\\{i,j\\\}\\in\\mathcal\{R\}\_\{e\}for somee∈ℰe\\in\\mathcal\{E\}, then removingeeseparatesiiandjjinTT, so they lie in different connected components ofT−ℰT\-\\mathcal\{E\}\. Conversely, ifiiandjjlie in different components ofT−ℰT\-\\mathcal\{E\}, then the unique tree pathPT​\(i,j\)P\_\{T\}\(i,j\)contains at least one edgee∈ℰe\\in\\mathcal\{E\}\. For that edge, one endpoint lies inAeA\_\{e\}and the other inBeB\_\{e\}, so

\{i,j\}∈ℛe\.\\\{i,j\\\}\\in\\mathcal\{R\}\_\{e\}\.\(49\)Hence

⋃e∈ℰℛe=\{\{i,j\}∈\(V2\):i​and​j​lie in different connected components of​T−ℰ\}\.\\bigcup\_\{e\\in\\mathcal\{E\}\}\\mathcal\{R\}\_\{e\}=\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:i\\text\{ and \}j\\text\{ lie in different connected components of \}T\-\\mathcal\{E\}\\bigr\\\}\.\(50\)
Proof of \(R\): There are\(n2\)\\binom\{n\}\{2\}unordered pairs in total\. The unordered pairs not in⋃e∈ℰℛe\\bigcup\_\{e\\in\\mathcal\{E\}\}\\mathcal\{R\}\_\{e\}are exactly those whose two endpoints lie in the same componentCtC\_\{t\}ofT−ℰT\-\\mathcal\{E\}, and there are\(\|Ct\|2\)\\binom\{\|C\_\{t\}\|\}\{2\}such pairs insideCtC\_\{t\}\. Summing over components and subtracting yields

\|⋃e∈ℰℛe\|=\(n2\)−∑t=1m\(\|Ct\|2\)\.\\left\|\\bigcup\_\{e\\in\\mathcal\{E\}\}\\mathcal\{R\}\_\{e\}\\right\|=\\binom\{n\}\{2\}\-\\sum\_\{t=1\}^\{m\}\\binom\{\|C\_\{t\}\|\}\{2\}\.\(51\)
Combining the previous steps, we obtain

\|\{\{i,j\}∈\(V2\):ud~​\(i,j\)≠ud​\(i,j\)\}\|=‖ud−ud~‖0≤\|⋃e∈ℰℛe\|=\(n2\)−∑t=1m\(\|Ct\|2\)\.\\bigl\|\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:u\_\{\\tilde\{d\}\}\(i,j\)\\neq u\_\{d\}\(i,j\)\\bigr\\\}\\bigr\|=\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq\\left\|\\bigcup\_\{e\\in\\mathcal\{E\}\}\\mathcal\{R\}\_\{e\}\\right\|=\\binom\{n\}\{2\}\-\\sum\_\{t=1\}^\{m\}\\binom\{\|C\_\{t\}\|\}\{2\}\.\(52\)
∎

### B\.2Proof of Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)

###### Theorem B\.2\(Hamming–Lipschitz bound via exposed cuts\)\.

Letd:\(V2\)→ℝ≥0d:\\binom\{V\}\{2\}\\to\\mathbb\{R\}\_\{\\geq 0\}be a dissimilarity on a finite setVV, and letT=\(V,E​\(T\)\)T=\(V,E\(T\)\)be the \(tie\-broken under Assumption 1\) MST ofdd\. For each tree edgee=\{a,b\}∈E​\(T\)e=\\\{a,b\\\}\\in E\(T\), letCe=\(Ae,Be\)C\_\{e\}=\(A\_\{e\},B\_\{e\}\)be its fundamental cut inTT, and writewe:=d​\(e\)w\_\{e\}:=d\(e\)\. Letd~\\tilde\{d\}be any perturbed dissimilarity, and letF:=\{f∈\(V2\):d~​\(f\)≠d​\(f\)\}F:=\\bigl\\\{f\\in\\tbinom\{V\}\{2\}:\\tilde\{d\}\(f\)\\neq d\(f\)\\bigr\\\}be its edit support\. For an edited pairf=\{x,y\}∈Ff=\\\{x,y\\\}\\in F, define the set of exposed cuts by

Ξ​\(f\):=\(\{f\}∩E​\(T\)\)∪\{e∈E​\(T\):f​crosses​Ce​and​d~​\(f\)<we\}\.\\Xi\(f\):=\(\\\{f\\\}\\cap E\(T\)\)\\cup\\bigl\\\{e\\in E\(T\):f\\text\{ crosses \}C\_\{e\}\\text\{ and \}\\tilde\{d\}\(f\)<w\_\{e\}\\bigr\\\}\.\(53\)For each tree edgee∈E​\(T\)e\\in E\(T\), the set of associated cut\-pairsℛe:=\{\{i,j\}∈\(V2\):i∈Ae,j∈Be\}\.\\mathcal\{R\}\_\{e\}:=\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:i\\in A\_\{e\},\\ j\\in B\_\{e\}\\bigr\\\}\.LetC:=\{\{i,j\}∈\(V2\):ud~​\(i,j\)≠ud​\(i,j\)\}C:=\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:u\_\{\\tilde\{d\}\}\(i,j\)\\neq u\_\{d\}\(i,j\)\\bigr\\\}denote the set of unordered pairs whose ultrametric values change\. Further, define the sharp per\-edit exposed\-cut sizeSunion​\(f\):=\|⋃e∈Ξ​\(f\)ℛe\|\.S\_\{\\mathrm\{union\}\}\(f\):=\\left\|\\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\\right\|\.For an edited pairf=\{x,y\}f=\\\{x,y\\\}, define the tree\-only path envelopeS¯T​\(f\):=\|⋃e∈PT​\(x,y\)ℛe\|,\\bar\{S\}\_\{T\}\(f\):=\\left\|\\bigcup\_\{e\\in P\_\{T\}\(x,y\)\}\\mathcal\{R\}\_\{e\}\\right\|,and the global tree\-only constantL¯T:=maxf∈\(V2\)⁡S¯T​\(f\)\.\\bar\{L\}\_\{T\}:=\\max\_\{f\\in\\binom\{V\}\{2\}\}\\bar\{S\}\_\{T\}\(f\)\.

Then:

- \(i\)C⊆⋃f∈F⋃e∈Ξ​\(f\)ℛe\.C\\subseteq\\bigcup\_\{f\\in F\}\\ \\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\.Consequently,‖ud−ud~‖0=\|C\|≤\|⋃f∈F⋃e∈Ξ​\(f\)ℛe\|\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\|C\|\\leq\\left\|\\bigcup\_\{f\\in F\}\\ \\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\\right\|\.
- \(ii\)for every edited pairf∈Ff\\in F, Sunion​\(f\)≤S¯T​\(f\)≤L¯T,S\_\{\\mathrm\{union\}\}\(f\)\\leq\\bar\{S\}\_\{T\}\(f\)\\leq\\bar\{L\}\_\{T\},\(54\)and therefore ‖ud−ud~‖0≤∑f∈FSunion​\(f\)≤∑f∈FS¯T​\(f\)≤L¯T​\|F\|=L¯T​‖d−d~‖0\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\\leq\\sum\_\{f\\in F\}\\bar\{S\}\_\{T\}\(f\)\\leq\\bar\{L\}\_\{T\}\\,\|F\|=\\bar\{L\}\_\{T\}\\,\\\|d\-\\tilde\{d\}\\\|\_\{0\}\.\(55\)In particular, L¯T≤\(\|V\|2\)\.\\bar\{L\}\_\{T\}\\leq\\binom\{\|V\|\}\{2\}\.\(56\)

###### Proof\.

*\(i\)*We first prove the localization statement\. Let

E^:=⋃f∈FΞ​\(f\)⊆E​\(T\)\.\\widehat\{E\}:=\\bigcup\_\{f\\in F\}\\Xi\(f\)\\subseteq E\(T\)\.\(57\)By the definition ofΞ​\(f\)\\Xi\(f\), a tree edgee∈E​\(T\)e\\in E\(T\)belongs toE^\\widehat\{E\}if and only if at least one of the following holds:

e∈F∩E​\(T\),e\\in F\\cap E\(T\),\(58\)or

∃f∈F​such that​f​crosses​Ce​and​d~​\(f\)<we\.\\exists f\\in F\\text\{ such that \}f\\text\{ crosses \}C\_\{e\}\\text\{ and \}\\tilde\{d\}\(f\)<w\_\{e\}\.\(59\)Hence

E^=\{e∈E​\(T\):e∈F∩E​\(T\)​or​∃f∈F​crossing​Ce​with​d~​\(f\)<we\}\.\\widehat\{E\}=\\bigl\\\{e\\in E\(T\):e\\in F\\cap E\(T\)\\ \\text\{or\}\\ \\exists f\\in F\\text\{ crossing \}C\_\{e\}\\text\{ with \}\\tilde\{d\}\(f\)<w\_\{e\}\\bigr\\\}\.\(60\)
But this is exactly the set of potentially affected tree edges appearing in Theorem[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)\-\(iii\)\. Therefore, by Theorem[3\.1](https://arxiv.org/html/2608.04014#S3.Thmtheorem1)\-\(iii\), the changed\-pair set satisfies

C⊆⋃e∈E^ℛe\.C\\subseteq\\bigcup\_\{e\\in\\widehat\{E\}\}\\mathcal\{R\}\_\{e\}\.\(61\)SinceE^=⋃f∈FΞ​\(f\)\\widehat\{E\}=\\bigcup\_\{f\\in F\}\\Xi\(f\), we obtain

C⊆⋃f∈F⋃e∈Ξ​\(f\)ℛe,C\\subseteq\\bigcup\_\{f\\in F\}\\ \\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\},\(62\)which proves the claimed localization\. Taking cardinalities yields

‖ud−ud~‖0=\|C\|≤\|⋃f∈F⋃e∈Ξ​\(f\)ℛe\|\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\|C\|\\leq\\left\|\\bigcup\_\{f\\in F\}\\ \\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\\right\|\.\(63\)
*\(ii\)*We now derive the per\-edit bound\. By definition,

Sunion​\(f\)=\|⋃e∈Ξ​\(f\)ℛe\|\.S\_\{\\mathrm\{union\}\}\(f\)=\\left\|\\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\\right\|\.\(64\)Applying the union bound to the previous inclusion gives

‖ud−ud~‖0≤∑f∈F\|⋃e∈Ξ​\(f\)ℛe\|=∑f∈FSunion​\(f\)\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq\\sum\_\{f\\in F\}\\left\|\\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\\right\|=\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\.\(65\)
It remains to compare the sharp exposed\-cut score with a tree\-only envelope\. Fix an edited pairf=\{x,y\}∈Ff=\\\{x,y\\\}\\in F\. We claim that every exposed cut forfflies on the tree pathPT​\(x,y\)P\_\{T\}\(x,y\):

Ξ​\(f\)⊆PT​\(x,y\)\.\\Xi\(f\)\\subseteq P\_\{T\}\(x,y\)\.\(66\)Indeed, ife∈Ξ​\(f\)∩E​\(T\)e\\in\\Xi\(f\)\\cap E\(T\)becausee=fe=f, then triviallyeelies onPT​\(x,y\)P\_\{T\}\(x,y\)\. Otherwise,e∈Ξ​\(f\)e\\in\\Xi\(f\)means thatf=\{x,y\}f=\\\{x,y\\\}crosses the cutCe=\(Ae,Be\)C\_\{e\}=\(A\_\{e\},B\_\{e\}\), so one endpoint offflies inAeA\_\{e\}and the other lies inBeB\_\{e\}\. In a tree, removingeeseparatesxxandyyif and only ifeelies on the unique path between them\. Therefore

e∈PT​\(x,y\)\.e\\in P\_\{T\}\(x,y\)\.\(67\)This proves the claim\.

Hence

⋃e∈Ξ​\(f\)ℛe⊆⋃e∈PT​\(x,y\)ℛe\.\\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\\subseteq\\bigcup\_\{e\\in P\_\{T\}\(x,y\)\}\\mathcal\{R\}\_\{e\}\.\(68\)Taking cardinalities gives

Sunion​\(f\)≤S¯T​\(f\)\.S\_\{\\mathrm\{union\}\}\(f\)\\leq\\bar\{S\}\_\{T\}\(f\)\.\(69\)By the definition ofL¯T\\bar\{L\}\_\{T\},

S¯T​\(f\)≤L¯T\\bar\{S\}\_\{T\}\(f\)\\leq\\bar\{L\}\_\{T\}\(70\)for everyf∈\(V2\)f\\in\\binom\{V\}\{2\}\. Therefore

Sunion​\(f\)≤S¯T​\(f\)≤L¯T\.S\_\{\\mathrm\{union\}\}\(f\)\\leq\\bar\{S\}\_\{T\}\(f\)\\leq\\bar\{L\}\_\{T\}\.\(71\)
Summing overf∈Ff\\in Fyields

‖ud−ud~‖0≤∑f∈FSunion​\(f\)≤∑f∈FS¯T​\(f\)≤L¯T​\|F\|\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\\leq\\sum\_\{f\\in F\}\\bar\{S\}\_\{T\}\(f\)\\leq\\bar\{L\}\_\{T\}\\,\|F\|\.\(72\)SinceFFis exactly the support of the perturbation,

\|F\|=‖d−d~‖0,\|F\|=\\\|d\-\\tilde\{d\}\\\|\_\{0\},\(73\)and therefore

‖ud−ud~‖0≤L¯T​‖d−d~‖0\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq\\bar\{L\}\_\{T\}\\,\\\|d\-\\tilde\{d\}\\\|\_\{0\}\.\(74\)
Finally, for every pairf=\{x,y\}f=\\\{x,y\\\}we trivially have

S¯T​\(f\)≤\|\(V2\)\|=\(\|V\|2\),\\bar\{S\}\_\{T\}\(f\)\\leq\\left\|\\binom\{V\}\{2\}\\right\|=\\binom\{\|V\|\}\{2\},\(75\)hence

L¯T≤\(\|V\|2\)\.\\bar\{L\}\_\{T\}\\leq\\binom\{\|V\|\}\{2\}\.\(76\)This completes the proof\. ∎

### B\.3Proof of Theorem[3\.3](https://arxiv.org/html/2608.04014#S3.Thmtheorem3)

###### Theorem B\.3\(Analysis of the Hamming–Lipschitz bound\)\.

Letd:\(V2\)→ℝ⩾0d:\\binom\{V\}\{2\}\\to\\mathbb\{R\}\_\{\\geqslant 0\}be a dissimilarity and letT=\(V,E​\(T\)\)T=\(V,E\(T\)\)be the \(tie\-broken under Assumption[2\.1](https://arxiv.org/html/2608.04014#S2.Thmtheorem1)\) MST ofdd\. Fore∈E​\(T\)e\\in E\(T\)write its fundamental cutCe=\(Ae,Be\)C\_\{e\}=\(A\_\{e\},B\_\{e\}\)andwe=d​\(e\)w\_\{e\}=d\(e\)\. For an edited pairf=\{x,y\}f=\\\{x,y\\\}and edited dissimilarityd~\\tilde\{d\}withd~​\(g\)=d​\(g\)\\tilde\{d\}\(g\)=d\(g\)forg∉\{f\}g\\notin\\\{f\\\}, define

Ξ​\(f\):=\(\{f\}∩E​\(T\)\)∪\{e∈E​\(T\):f​crosses​Ce​and​d~​\(f\)<we\},Sunion​\(f\):=\|⋃e∈Ξ​\(f\)ℛe\|\.\\Xi\(f\)\\ :=\\ \(\\\{f\\\}\\cap E\(T\)\)\\ \\cup\\ \\\{\\,e\\in E\(T\):\\ f\\ \\text\{crosses\}\\ C\_\{e\}\\ \\text\{and\}\\ \\tilde\{d\}\(f\)<w\_\{e\}\\,\\\},\\qquad S\_\{\\mathrm\{union\}\}\(f\):=\\left\|\\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\\right\|\.\(77\)Then:

1. \(i\)\(*Tree\-edge edit under strict cut separation*\) Iff=e∈E​\(T\)f=e\\in E\(T\)andeeis strictly cut\-separated, i\.e\.Δe​\(d\)=we\+​\(d\)−we\>0,\\Delta\_\{e\}\(d\)=w\_\{e\}^\{\+\}\(d\)\-w\_\{e\}\>0,then there existsd~\\tilde\{d\}supported on\{f\}\\\{f\\\}such that ‖ud−ud~‖0=\|Ae\|​\|Be\|=Sunion​\(f\)\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\|A\_\{e\}\|\|B\_\{e\}\|=S\_\{\\mathrm\{union\}\}\(f\)\.\(78\)
2. \(ii\)\(*Off\-tree sharpness on an explicit family*\) There exist dissimilaritiesdd, off\-tree edgesf∉E​\(T\)f\\notin E\(T\), and single\-edge editsd~\\tilde\{d\}supported on\{f\}\\\{f\\\}such that ‖ud−ud~‖0=\|⋃e∈Ξ​\(f\)ℛe\|=Sunion​\(f\)=Θ​\(n2\)\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\\left\|\\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\}\\right\|=S\_\{\\mathrm\{union\}\}\(f\)=\\Theta\(n^\{2\}\)\.\(79\)Thus, the upper bound of Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)is attained on explicit off\-tree instances, and in the worst case a single off\-tree edit can force a quadratic number of ultrametric changes\.
3. \(iii\)\(*Necessity of instance dependence*\) Consequently, no universal subquadratic functionc​\(n\)=o​\(n2\)c\(n\)=o\(n^\{2\}\)can satisfy ‖ud−ud~‖0≤c​\(n\)​‖d−d~‖0\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq c\(n\)\\,\\\|d\-\\tilde\{d\}\\\|\_\{0\}\(80\)for all instances\.

###### Proof\.

Throughout, recall from Lemma[2\.3](https://arxiv.org/html/2608.04014#S2.Thmtheorem3)the MST bottleneck representationud​\(i,j\)=maxe∈PT​\(i,j\)⁡weu\_\{d\}\(i,j\)=\\max\_\{e\\in P\_\{T\}\(i,j\)\}w\_\{e\}and from Lemma[2\.4](https://arxiv.org/html/2608.04014#S2.Thmtheorem4), the cut property argument: everyii–jjpath must cross every fundamental cutCeC\_\{e\}withe∈PT​\(i,j\)e\\in P\_\{T\}\(i,j\); if a crossing edge has weight<we<w\_\{e\}, then the bottleneck along someii–jjpath is<we<w\_\{e\}\.

*\(i\) Tree\-edge edit\.*Fix a tree edgee∈E​\(T\)e\\in E\(T\)that is strictly cut\-separated, so that

Δe​\(d\)=we\+​\(d\)−we\>0\.\\Delta\_\{e\}\(d\)=w\_\{e\}^\{\+\}\(d\)\-w\_\{e\}\>0\.\(81\)Chooseε\\varepsilonsuch that

0<ε<Δe​\(d\),0<\\varepsilon<\\Delta\_\{e\}\(d\),\(82\)and defined~​\(e\):=we\+ε\\tilde\{d\}\(e\):=w\_\{e\}\+\\varepsilon, whiled~​\(g\):=d​\(g\)\\tilde\{d\}\(g\):=d\(g\)for allg≠eg\\neq e\. Consider any unordered pair\{i,j\}∈ℛe\\\{i,j\\\}\\in\\mathcal\{R\}\_\{e\}\. Sincee∈PT​\(i,j\)e\\in P\_\{T\}\(i,j\), the MST bottleneck representation from Lemma[2\.3](https://arxiv.org/html/2608.04014#S2.Thmtheorem3)gives

ud​\(i,j\)=we\.u\_\{d\}\(i,j\)=w\_\{e\}\.\(83\)Underd~\\tilde\{d\}, the tree path bottleneck becomeswe\+εw\_\{e\}\+\\varepsilon\. Moreover, every other edgeggcrossing the cutCeC\_\{e\}satisfies

d​\(g\)≥we\+​\(d\)=we\+Δe​\(d\)\>we\+ε,d\(g\)\\geq w\_\{e\}^\{\+\}\(d\)=w\_\{e\}\+\\Delta\_\{e\}\(d\)\>w\_\{e\}\+\\varepsilon,\(84\)so no alternativeii–jjpath can have bottleneck belowwe\+εw\_\{e\}\+\\varepsilon\. Hence

ud~​\(i,j\)=we\+ε\>ud​\(i,j\),u\_\{\\tilde\{d\}\}\(i,j\)=w\_\{e\}\+\\varepsilon\>u\_\{d\}\(i,j\),\(85\)and the pair changes\.

If\{i,j\}∉ℛe\\\{i,j\\\}\\notin\\mathcal\{R\}\_\{e\}, thene∉PT​\(i,j\)e\\notin P\_\{T\}\(i,j\)\. No cut alongPT​\(i,j\)P\_\{T\}\(i,j\)has acquired a strictly lighter crossing than its tree\-edge weight, and none of the tree edges onPT​\(i,j\)P\_\{T\}\(i,j\)was edited\. By the cut argument \(as in the proof of Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)\), this impliesud~​\(i,j\)=ud​\(i,j\)u\_\{\\tilde\{d\}\}\(i,j\)=u\_\{d\}\(i,j\)\. Hence*exactly*the pairs inℛe\\mathcal\{R\}\_\{e\}change, so‖ud−ud~‖0=\|Ae\|​\|Be\|=Sunion​\(e\)\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\|A\_\{e\}\|\|B\_\{e\}\|=S\_\{\\mathrm\{union\}\}\(e\)\.

*\(ii\) Off\-tree sharpness on an explicit family\.*LetV=A∪BV=A\\cup Bwith\|A\|=⌊n/2⌋\|A\|=\\lfloor n/2\\rfloorand\|B\|=⌈n/2⌉\|B\|=\\lceil n/2\\rceil\. Defineddby

d​\(i,j\)=1if​\{i,j\}⊆A​or​\{i,j\}⊆B,d\(i,j\)=1\\quad\\text\{if \}\\\{i,j\\\}\\subseteq A\\text\{ or \}\\\{i,j\\\}\\subseteq B,\(86\)and

d​\(i,j\)=10if​i∈A,j∈B,d\(i,j\)=10\\quad\\text\{if \}i\\in A,\\ j\\in B,\(87\)except for one distinguished cross edgee⋆=\{a⋆,b⋆\}e^\{\\star\}=\\\{a^\{\\star\},b^\{\\star\}\\\}with

d​\(e⋆\)=8\.d\(e^\{\\star\}\)=8\.\(88\)Then the unique MSTTTconsists of a unit\-weight tree onAA, a unit\-weight tree onBB, and the bridgee⋆e^\{\\star\}of weight88\.

Pick any other cross edgef=\{a,b\}∈A×Bf=\\\{a,b\\\}\\in A\\times B,f≠e⋆f\\neq e^\{\\star\}, and defined~\\tilde\{d\}by

d~​\(f\)=2,d~​\(g\)=d​\(g\)​for​g≠f\.\\tilde\{d\}\(f\)=2,\\qquad\\tilde\{d\}\(g\)=d\(g\)\\ \\text\{for \}g\\neq f\.\(89\)
We first identify the exposed\-cut setΞ​\(f\)\\Xi\(f\)\. Sincef∉E​\(T\)f\\notin E\(T\), the first term in the definition vanishes\. Along the tree pathPT​\(a,b\)P\_\{T\}\(a,b\), every edge internal toAAorBBhas weight11, while the unique bridge edgee⋆e^\{\\star\}has weight88\. Becaused~​\(f\)=2\\tilde\{d\}\(f\)=2, the edit does not expose any unit\-weight tree edge, but it does expose the bridge cut:

2≮1,2<8\.2\\not<1,\\qquad 2<8\.\(90\)Hence

Ξ​\(f\)=\{e⋆\},Sunion​\(f\)=\|ℛe⋆\|=\|A\|​\|B\|\.\\Xi\(f\)=\\\{e^\{\\star\}\\\},\\qquad S\_\{\\mathrm\{union\}\}\(f\)=\|\\mathcal\{R\}\_\{e^\{\\star\}\}\|=\|A\|\|B\|\.\(91\)
Now take anyi∈Ai\\in Aandj∈Bj\\in B\. Underdd, everyii–jjtree path must crosse⋆e^\{\\star\}, so

ud​\(i,j\)=8\.u\_\{d\}\(i,j\)=8\.\(92\)Underd~\\tilde\{d\}, the path

i↝a→f→b↝ji\\rightsquigarrow a\\;\\to\\;f\\;\\to\\;b\\rightsquigarrow j\(93\)has edge weights1,2,11,2,1, hence bottleneck22\. Therefore

ud~​\(i,j\)≤2<8=ud​\(i,j\),u\_\{\\tilde\{d\}\}\(i,j\)\\leq 2<8=u\_\{d\}\(i,j\),\(94\)so every cross pair changes\. For pairs contained entirely insideAAor entirely insideBB, the original unit\-weight tree paths remain available and still have bottleneck11, while the edited cross edgeffcannot produce a path of bottleneck below11\. Hence within\-side pairs do not change\.

Therefore the changed\-pair set is exactly

\{\{i,j\}∈\(V2\):i∈A,j∈B\},\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:i\\in A,\\ j\\in B\\bigr\\\},\(95\)and

‖ud−ud~‖0=\|A\|​\|B\|=Sunion​\(f\)=Θ​\(n2\)\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\|A\|\|B\|=S\_\{\\mathrm\{union\}\}\(f\)=\\Theta\(n^\{2\}\)\.\(96\)This proves exact attainability of the Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2)bound on an explicit off\-tree family\.

∎

*\(iii\) Necessity of instance dependence\.*This follows immediately from part \(ii\), which exhibits a single\-edge edit with

‖d−d~‖0=1and‖ud−ud~‖0=Θ​\(n2\)\.\\\|d\-\\tilde\{d\}\\\|\_\{0\}=1\\quad\\text\{and\}\\quad\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\\Theta\(n^\{2\}\)\.\(97\)

### B\.4Proof of Corollary[3\.4](https://arxiv.org/html/2608.04014#S3.Thmtheorem4)

###### Corollary B\.4\.

Fix a minimum spanning treeTTofdd, an edit setF⊆\(V2\)F\\subseteq\\binom\{V\}\{2\}, and edited weightsd~\\tilde\{d\}supported onFF\. For eachf∈Ff\\in F, define the exposed regionR​\(f\):=⋃e∈Ξ​\(f\)ℛe,R\(f\):=\\bigcup\_\{e\\in\\Xi\(f\)\}\\mathcal\{R\}\_\{e\},so that\|R​\(f\)\|=Sunion​\(f\)\.\|R\(f\)\|=S\_\{\\mathrm\{union\}\}\(f\)\.Assume that for eachf∈Ff\\in Fthere exists a certified changed\-pair setQ​\(f\)⊆R​\(f\)Q\(f\)\\subseteq R\(f\)such that every pair inQ​\(f\)Q\(f\)indeed changes under the common edited dissimilarityd~\\tilde\{d\}, i\.e\.Q​\(f\)⊆\{\{i,j\}∈\(V2\):ud~​\(i,j\)≠ud​\(i,j\)\}\.Q\(f\)\\subseteq\\bigl\\\{\\\{i,j\\\}\\in\\tbinom\{V\}\{2\}:u\_\{\\tilde\{d\}\}\(i,j\)\\neq u\_\{d\}\(i,j\)\\bigr\\\}\.

Then:

- \(i\)\|⋃f∈FQ​\(f\)\|≤‖ud−ud~‖0≤\|⋃f∈FR​\(f\)\|≤∑f∈FSunion​\(f\)\.\\left\|\\bigcup\_\{f\\in F\}Q\(f\)\\right\|\\leq\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq\\left\|\\bigcup\_\{f\\in F\}R\(f\)\\right\|\\leq\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\.
- \(ii\)Moreover, consider any asymptotic regime of instances \(for example,\|V\|=n→∞\|V\|=n\\to\\infty\) in which ∑f∈F\|Q​\(f\)\|=\(1−o​\(1\)\)​∑f∈FSunion​\(f\),\\sum\_\{f\\in F\}\|Q\(f\)\|=\(1\-o\(1\)\)\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\),and the certified regions have asymptotically negligible total overlap: ∑f,f′∈Ff<f′\|Q​\(f\)∩Q​\(f′\)\|=o​\(∑f∈F\|Q​\(f\)\|\)\.\\sum\_\{\\begin\{subarray\}\{c\}f,f^\{\\prime\}\\in F\\\\ f<f^\{\\prime\}\\end\{subarray\}\}\|Q\(f\)\\cap Q\(f^\{\\prime\}\)\|=o\\\!\\left\(\\sum\_\{f\\in F\}\|Q\(f\)\|\\right\)\.Then ‖ud−ud~‖0=\(1−o​\(1\)\)​∑f∈FSunion​\(f\)\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\(1\-o\(1\)\)\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\.

###### Proof\.

*\(i\)*Let

C:=\{\{i,j\}:ud~​\(i,j\)≠ud​\(i,j\)\}C:=\\bigl\\\{\\\{i,j\\\}:u\_\{\\tilde\{d\}\}\(i,j\)\\neq u\_\{d\}\(i,j\)\\bigr\\\}denote the set of unordered pairs whose ultrametric value changes\.

We first prove the finite\-sample sandwich bound\.

By Theorem[3\.2](https://arxiv.org/html/2608.04014#S3.Thmtheorem2), every changed pair must lie in the exposed region of at least one edited edge\. Therefore

C⊆⋃f∈FR​\(f\)\.C\\subseteq\\bigcup\_\{f\\in F\}R\(f\)\.Taking cardinalities gives

\|C\|≤\|⋃f∈FR​\(f\)\|\.\|C\|\\leq\\left\|\\bigcup\_\{f\\in F\}R\(f\)\\right\|\.Since the cardinality of a union is at most the sum of the cardinalities,

\|⋃f∈FR​\(f\)\|≤∑f∈F\|R​\(f\)\|=∑f∈FSunion​\(f\)\.\\left\|\\bigcup\_\{f\\in F\}R\(f\)\\right\|\\leq\\sum\_\{f\\in F\}\|R\(f\)\|=\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\.Hence

\|C\|≤\|⋃f∈FR​\(f\)\|≤∑f∈FSunion​\(f\)\.\|C\|\\leq\\left\|\\bigcup\_\{f\\in F\}R\(f\)\\right\|\\leq\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\.
*\(ii\)*On the other hand, by assumption, each certified setQ​\(f\)Q\(f\)consists only of pairs that do change under the common edited dissimilarityd~\\tilde\{d\}\. Thus

Q​\(f\)⊆Cfor every​f∈F,Q\(f\)\\subseteq C\\qquad\\text\{for every \}f\\in F,and therefore

⋃f∈FQ​\(f\)⊆C\.\\bigcup\_\{f\\in F\}Q\(f\)\\subseteq C\.Taking cardinalities yields

\|⋃f∈FQ​\(f\)\|≤\|C\|\.\\left\|\\bigcup\_\{f\\in F\}Q\(f\)\\right\|\\leq\|C\|\.
Combining the lower and upper bounds on\|C\|=‖ud−ud~‖0\|C\|=\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}, we obtain

\|⋃f∈FQ​\(f\)\|≤‖ud−ud~‖0≤\|⋃f∈FR​\(f\)\|≤∑f∈FSunion​\(f\)\.\\left\|\\bigcup\_\{f\\in F\}Q\(f\)\\right\|\\leq\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq\\left\|\\bigcup\_\{f\\in F\}R\(f\)\\right\|\\leq\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\.This proves the first claim\.

We now prove the asymptotic near\-additivity statement\. By the elementary first\-order inclusion–exclusion bound,

\|⋃f∈FQ​\(f\)\|≥∑f∈F\|Q​\(f\)\|−∑f,f′∈Ff<f′\|Q​\(f\)∩Q​\(f′\)\|\.\\left\|\\bigcup\_\{f\\in F\}Q\(f\)\\right\|\\geq\\sum\_\{f\\in F\}\|Q\(f\)\|\-\\sum\_\{\\begin\{subarray\}\{c\}f,f^\{\\prime\}\\in F\\\\ f<f^\{\\prime\}\\end\{subarray\}\}\|Q\(f\)\\cap Q\(f^\{\\prime\}\)\|\.Under the aggregate\-overlap assumption

∑f,f′∈Ff<f′\|Q​\(f\)∩Q​\(f′\)\|=o​\(∑f∈F\|Q​\(f\)\|\),\\sum\_\{\\begin\{subarray\}\{c\}f,f^\{\\prime\}\\in F\\\\ f<f^\{\\prime\}\\end\{subarray\}\}\|Q\(f\)\\cap Q\(f^\{\\prime\}\)\|=o\\\!\\left\(\\sum\_\{f\\in F\}\|Q\(f\)\|\\right\),it follows that

\|⋃f∈FQ​\(f\)\|=\(1−o​\(1\)\)​∑f∈F\|Q​\(f\)\|\.\\left\|\\bigcup\_\{f\\in F\}Q\(f\)\\right\|=\(1\-o\(1\)\)\\sum\_\{f\\in F\}\|Q\(f\)\|\.Using the additional assumption

∑f∈F\|Q​\(f\)\|=\(1−o​\(1\)\)​∑f∈FSunion​\(f\),\\sum\_\{f\\in F\}\|Q\(f\)\|=\(1\-o\(1\)\)\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\),we conclude that

\|⋃f∈FQ​\(f\)\|=\(1−o​\(1\)\)​∑f∈FSunion​\(f\)\.\\left\|\\bigcup\_\{f\\in F\}Q\(f\)\\right\|=\(1\-o\(1\)\)\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\.
Finally, from the already established sandwich bound,

\|⋃f∈FQ​\(f\)\|≤‖ud−ud~‖0≤∑f∈FSunion​\(f\)\.\\left\|\\bigcup\_\{f\\in F\}Q\(f\)\\right\|\\leq\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}\\leq\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\.The lower bound is asymptotically\(1−o​\(1\)\)​∑f∈FSunion​\(f\)\(1\-o\(1\)\)\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\), while the upper bound is exactly∑f∈FSunion​\(f\)\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\. Therefore

‖ud−ud~‖0=\(1−o​\(1\)\)​∑f∈FSunion​\(f\)\.\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\(1\-o\(1\)\)\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\.This proves the corollary\. ∎

## Appendix CSubstantiation of the Asymptotic Condition in Corollary 1\(ii\)

To substantiate the asymptotic condition in Corollary 1\(ii\), we construct a stylized “star of subtrees” regime\. This demonstrates how simultaneous sparse edits can yield certified changed regions with asymptotically negligible aggregate overlap\.

##### Graph Construction\.

Let the minimum spanning treeT=\(V,E​\(T\)\)T=\(V,E\(T\)\)consist of a central hub nodev0v\_\{0\}andmmdistinct branches \(subtrees\)B1,…,BmB\_\{1\},\\dots,B\_\{m\}, each containing exactlyMMnodes\. The total number of nodes isn=m​M\+1n=mM\+1\.

We assign the original dissimilarityddas follows:

- •d​\(e\)=0d\(e\)=0for all internal subtree MST edges\.
- •d​\(ei\)=1d\(e\_\{i\}\)=1for each of themmhub\-to\-branch MST edgeseie\_\{i\}\.
- •d​\(e′\)=3d\(e^\{\\prime\}\)=3for every non\-tree edgee′e^\{\\prime\}crossing any branch cut\.

This ensures each branch edgeeie\_\{i\}is strictly cut\-separated, as the alternative crossing weight is strictly greater than the tree edge weight \(Δei=3−1=2\>0\\Delta\_\{e\_\{i\}\}=3\-1=2\>0\)\.

##### Sparse Simultaneous Perturbation\.

Let the perturbation setFFconsist ofkkdistinct hub\-to\-branch edges, wherek=o​\(m\)k=o\(m\)\. For each edited edgefi∈Ff\_\{i\}\\in F, the edited dissimilarity is strictly inflated tod~​\(fi\)=2\\tilde\{d\}\(f\_\{i\}\)=2\. All other distances remain unchanged\.

##### Certification of Changed Regions\.

For each edited branch edgefif\_\{i\}, its fundamental cut inTTseparates the branchBiB\_\{i\}from the rest of the graphV∖BiV\\setminus B\_\{i\}\. The exposed cut\-pair set is:

R​\(fi\)=\{\{x,y\}∈\(V2\):x∈Bi,y∈V∖Bi\}\.R\(f\_\{i\}\)=\\left\\\{\\\{x,y\\\}\\in\\binom\{V\}\{2\}:x\\in B\_\{i\},y\\in V\\setminus B\_\{i\}\\right\\\}\.By definition, the structural score isSunion​\(fi\)=\|R​\(fi\)\|=M​\(n−M\)S\_\{\\mathrm\{union\}\}\(f\_\{i\}\)=\|R\(f\_\{i\}\)\|=M\(n\-M\)\.

We must certify that every pair inR​\(fi\)R\(f\_\{i\}\)genuinely changes under the joint perturbation\. Before the edits, every path fromBiB\_\{i\}toV∖BiV\\setminus B\_\{i\}had an MST bottleneck ofud​\(x,y\)=1u\_\{d\}\(x,y\)=1\. Under the joint perturbationd~\\tilde\{d\}, the weight offif\_\{i\}increases to 2\. Because every non\-tree cross\-edge has a weight of 3, no alternative path betweenBiB\_\{i\}andV∖BiV\\setminus B\_\{i\}can achieve a bottleneck below 2\. Therefore, the ultrametric value strictly increases toud~​\(x,y\)=2u\_\{\\tilde\{d\}\}\(x,y\)=2for all\{x,y\}∈R​\(fi\)\\\{x,y\\\}\\in R\(f\_\{i\}\)\.

This guarantees that the certified changed regionQ​\(fi\)Q\(f\_\{i\}\)equals the entire exposed region:

\|Q​\(fi\)\|=\|R​\(fi\)\|=M​\(n−M\)\.\|Q\(f\_\{i\}\)\|=\|R\(f\_\{i\}\)\|=M\(n\-M\)\.

##### Asymptotic Aggregate Overlap\.

For any pair of distinct editsfi,fj∈Ff\_\{i\},f\_\{j\}\\in F\(i≠ji\\neq j\), the intersectionQ​\(fi\)∩Q​\(fj\)Q\(f\_\{i\}\)\\cap Q\(f\_\{j\}\)consists exclusively of pairs that cross both fundamental cuts\. In this topology, these are exactly the pairs with one endpoint inBiB\_\{i\}and the other inBjB\_\{j\}\. The size of this exact overlap is:

\|Q​\(fi\)∩Q​\(fj\)\|=\|Bi\|​\|Bj\|=M2\.\|Q\(f\_\{i\}\)\\cap Q\(f\_\{j\}\)\|=\|B\_\{i\}\|\|B\_\{j\}\|=M^\{2\}\.
Summing the overlap across all\(k2\)\\binom\{k\}\{2\}pairs of edits yields the aggregate overlap:

∑i<j\|Q​\(fi\)∩Q​\(fj\)\|=\(k2\)​M2=k​\(k−1\)2​M2\.\\sum\_\{i<j\}\|Q\(f\_\{i\}\)\\cap Q\(f\_\{j\}\)\|=\\binom\{k\}\{2\}M^\{2\}=\\frac\{k\(k\-1\)\}\{2\}M^\{2\}\.
The sum of the individual certified regions is:

∑i=1k\|Q​\(fi\)\|=k​M​\(n−M\)=k​M​\(m​M\)=k​m​M2\.\\sum\_\{i=1\}^\{k\}\|Q\(f\_\{i\}\)\|=kM\(n\-M\)=kM\(mM\)=kmM^\{2\}\.
Evaluating the ratio of the aggregate overlap to the total sum of the certified regions yields:

∑i<j\|Q​\(fi\)∩Q​\(fj\)\|∑i=1k\|Q​\(fi\)\|=k​\(k−1\)2​M2k​m​M2=k−12​m\.\\frac\{\\sum\_\{i<j\}\|Q\(f\_\{i\}\)\\cap Q\(f\_\{j\}\)\|\}\{\\sum\_\{i=1\}^\{k\}\|Q\(f\_\{i\}\)\|\}=\\frac\{\\frac\{k\(k\-1\)\}\{2\}M^\{2\}\}\{kmM^\{2\}\}=\\frac\{k\-1\}\{2m\}\.
In the asymptotic regime wherek=o​\(m\)k=o\(m\), we have:

limm→∞k−12​m=0\.\\lim\_\{m\\to\\infty\}\\frac\{k\-1\}\{2m\}=0\.
This confirms that the aggregate overlap iso​\(∑f∈F\|Q​\(f\)\|\)o\\left\(\\sum\_\{f\\in F\}\|Q\(f\)\|\\right\)\. Consequently, the conditions for Corollary 1\(ii\) are satisfied, and the total Hamming damage scales near\-additively:‖ud−ud~‖0=\(1−o​\(1\)\)​∑f∈FSunion​\(f\)\\\|u\_\{d\}\-u\_\{\\tilde\{d\}\}\\\|\_\{0\}=\(1\-o\(1\)\)\\sum\_\{f\\in F\}S\_\{\\mathrm\{union\}\}\(f\)\.