研究稀疏扰动下树形结构的稳定性,给出精确的变动范围预测。
On Hamming-Lipschitz Type Stability of the Subdominant (Minmax) Ultrametric: Theory and Simple Proofs

- 基于最小生成树分析扰动传播路径,定位影响范围。
- 单次修改最多改变 Θ(n²) 个超度量条目,且与树结构强相关。
- 适用于检测深度嵌入图中层次表示的脆弱性,适合算法安全分析者。
子主导(极小-极大)超度量是相异矩阵的典型树形摘要,等价于单链接聚类诱导的超度量。传统稳定性理论多基于 ℓ∞ 或 Gromov–Hausdorff 范式,难以刻画仅改变少数成对距离的稀疏扰动。本文建立 ℓ₀ 型稳定性理论,证明稀疏编辑仅通过最小生成树(MST)传播:一个超度量值变化当且仅当其树路径经过被编辑边或因非树边修改而暴露的新割。由此导出每编辑一次的暴露割评分及仅依赖树的全局包络,获得超度量条目变动数量的哈明-利普希茨界。我们还证明了紧致性结果:在严格割分离条件下,树边边界可被精确达到;对非树边编辑,存在显式族使得一次编辑影响 Θ(n²) 个超度量条目。此外,在编辑区域足够大且总重叠可忽略的条件下,建立了多重编辑的近似可加性原理。在深度嵌入图上的实验表明,所得结构评分能有效诊断层次表示的脆弱性。
原文摘要 · Abstract (English)
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 $\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 $Θ(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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。