关于次主导（最小最大）超度量的 Hamming-Lipschitz 类型稳定性：理论和简单证明

摘要

arXiv:2608.04014v1 Announce Type: new Abstract: The subdominant (minmax) ultrametric is a canonical tree-structured summary of a dissimilarity matrix, arising equivalently as the ultrametric induced b...

tree ultrametric the that only for edits edited edge cut

2026-08-06 1 阅读约1分钟阅读 Alokendu Mazumder, Arnab Roy, Punit Rathore

arXiv:2608.04014v1 公告类型：新摘要：次主导（最小最大）超度量是相异矩阵的规范树结构摘要，与单链接聚类引发的超度量等效。虽然其经典稳定性理论通常用 $\ell_\infty$ 或 Gromov--Hausdorff 项来表述，但这样的界限不太适合仅改变几个成对距离的稀疏扰动。我们为该算子开发了 $\ell_0$ 型稳定性理论。我们的分析表明，稀疏编辑仅通过最小生成树（MST）传播：仅当其树路径穿过已编辑的边或由已编辑的离树边新暴露的切割时，成对超度量值才能更改。这会产生尖锐的每次编辑暴露剪切分数和仅限树的全局包络，从而导致可更改的超度量条目数量的 Hamming-Lipschitz 界限。我们还证明了锐度结果，表明这种对树几何形状的依赖是不可避免的：在严格的切割分离下，可以准确地获得树边缘边界，并且对于离树编辑，存在显式族，其中一个编辑距离会改变 $\Theta(n^2)$ 超度量条目。此外，我们证明了在经认证的大每次编辑更改区域和可忽略的聚合重叠下进行多次编辑的条件近可加性原理。深度嵌入图的实验表明，所得的结构分数为层次表示提供了有用的漏洞诊断。

订阅66必读