New theory reveals sparse edits only propagate through MST in clustering

A new paper from Alokendu Mazumder, Arnab Roy, and Punit Rathore tackles a blind spot in hierarchical clustering robustness. The subdominant (minmax) ultrametric — a tree-structured summary of a dissimilarity matrix that is equivalent to single-linkage clustering — has classic stability bounds in ℓ∞ or Gromov-Hausdorff terms. But those fail when perturbations are sparse, changing only a few pairwise distances. The authors introduce an ℓ0-type stability theory that measures how many ultrametric entries change, providing a sharper and more practical lens for real-world data corruption.

Their key finding: 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, resulting in Hamming-Lipschitz bounds on affected entries. The theory is tight: under strict cut separation, the tree-edge bound is attained exactly, and for off-tree edits there exist explicit families where a single edited distance changes Θ(n²) ultrametric entries. They also prove a conditional near-additivity principle for multiple edits when changed regions overlap negligibly. Experiments on deep-embedding graphs show these structural scores serve as useful vulnerability diagnostics for hierarchical representations, potentially helping engineers identify fragile clusters in embedding-based systems.