关于次优势（极小极大）超度量的 Hamming-Lipschitz 型稳定性：理论与简单证明

# 关于次主导（极小极大）超度量的汉明-利普希茨型稳定性：理论与简单证明  
来源：https://arxiv.org/html/2608.04014  
Alokendu Mazumder1,2∗，Arnab Roy1,3† ∗，Punit Rathore1,2  
1 罗伯特·博世信息物理系统中心，印度科学理工学院班加罗尔  
2 基础设施、可持续交通与城市规划中心，印度科学理工学院班加罗尔  
3 计算机科学与自动化系，印度科学理工学院班加罗尔  
\{alokendum, arnabroy, prathore\}@iisc\.ac\.in

###### 摘要

次主导（极小极大）超度量是相异性矩阵的一种典型树结构摘要，它等价地作为由单链接聚类诱导的超度量出现。虽然其经典稳定性理论通常以 l∞ 或格罗莫夫-豪斯多夫术语表述，但这类界不适用于仅改变少数成对距离的稀疏扰动。我们为该算子发展了一套 l0 型稳定性理论。我们的分析表明，稀疏编辑仅通过最小生成树（MST）传播：一个成对超度量值只有在它的树路径穿过一条被编辑的边，或一条被编辑的树外边新暴露的割时，才可能改变。这产生了一个尖锐的每编辑暴露割分数和一个仅依赖树的全局包络，从而得到关于可改变超度量条目数量的汉明-利普希茨界。我们还证明了尖锐性结果，表明这种对树几何的依赖是不可避免的：在严格割分离下，树边界的界被精确达到；对于树外编辑，存在显式族使得一个编辑距离改变 Θ(n2) 个超度量条目。此外，我们证明了在认证的大每编辑改变区域和可忽略的总重叠下，多重编辑的条件近似可加性原理。在深度嵌入图上的实验表明，所得结构分数为层次表示提供了有用的脆弱性诊断。  
† 工作完成于罗伯特·博世信息物理系统中心。∗ 表示联合共同作者。

###### 目录

- [1 引言](https://arxiv.org/html/2608.04014#S1)
  - [1.1 先前理论的空白与动机](https://arxiv.org/html/2608.04014#S1.SS1)
  - [1.2 现代机器学习中的极小极大超度量](https://arxiv.org/html/2608.04014#S1.SS2)
  - [1.3 贡献：](https://arxiv.org/html/2608.04014#S1.SS3)
- [2 记号、假设与预备知识](https://arxiv.org/html/2608.04014#S2)
  - [2.1 贯穿全文的两个 MST 事实](https://arxiv.org/html/2608.04014#S2.SS1)
- [3 稀疏局部化扰动与成对影响](https://arxiv.org/html/2608.04014#S3)
- [4 实证案例研究 - I：深度嵌入的脆弱性图](https://arxiv.org/html/2608.04014#S4)
  - [4.1 协议](https://arxiv.org/html/2608.04014#S4.SS1)
  - [4.2 结果](https://arxiv.org/html/2608.04014#S4.SS2)
- [5 实证案例研究 - II：基于 MST 的超像素分割](https://arxiv.org/html/2608.04014#S5)
  - [5.1 设置](https://arxiv.org/html/2608.04014#S5.SS1)
  - [5.2 安全编辑曲线](https://arxiv.org/html/2608.04014#S5.SS2)
  - [5.3 结果](https://arxiv.org/html/2608.04014#S5.SS3)
- [6 实证案例研究 - III：半监督聚类的主动 MST 边验证](https://arxiv.org/html/2608.04014#S6)
  - [6.1 任务的比较范围](https://arxiv.org/html/2608.04014#S6.SS1)
  - [6.2 数据集](https://arxiv.org/html/2608.04014#S6.SS2)
  - [6.3 通用预处理流程](https://arxiv.org/html/2608.04014#S6.SS3)
  - [6.4 稀疏图构建与公共 MST 骨干](https://arxiv.org/html/2608.04014#S6.SS4)
  - [6.5 未验证的基线聚类](https://arxiv.org/html/2608.04014#S6.SS5)
  - [6.6 主动验证协议](https://arxiv.org/html/2608.04014#S6.SS6)
  - [6.7 我们的方法：结构分数 Sunion(e)](https://arxiv.org/html/2608.04014#S6.SS7)
  - [6.8 基准基线](https://arxiv.org/html/2608.04014#S6.SS8)
    - [6.8.1 原始权重基线](https://arxiv.org/html/2608.04014#S6.SS8.SSS1)
    - [6.8.2 缩放权重基线](https://arxiv.org/html/2608.04014#S6.SS8.SSS2)
    - [6.8.3 质心间隔基线](https://arxiv.org/html/2608.04014#S6.SS8.SSS3)
    - [6.8.4 Ward 桥基线](https://arxiv.org/html/2608.04014#S6.SS8.SSS4)
    - [6.8.5 Fisher 桥基线](https://arxiv.org/html/2608.04014#S6.SS8.SSS5)
    - [6.8.6 随机基线](https://arxiv.org/html/2608.04014#S6.SS8.SSS6)
  - [6.9 评估指标](https://arxiv.org/html/2608.04014#S6.SS9)
  - [6.10 基准分数的高效计算](https://arxiv.org/html/2608.04014#S6.SS10)
  - [6.11 本实验测试的内容](https://arxiv.org/html/2608.04014#S6.SS11)
  - [6.12 实证目标](https://arxiv.org/html/2608.04014#S6.SS12)
  - [6.13 实证总结](https://arxiv.org/html/2608.04014#S6.SS13)
- [7 结论](https://arxiv.org/html/2608.04014#S7)
- [参考文献](https://arxiv.org/html/2608.04014#bib)
- [A 技术引理的证明](https://arxiv.org/html/2608.04014#A1)
  - [A.1 引理 2.3 的证明](https://arxiv.org/html/2608.04014#A1.SS1)
  - [A.2 引理 2.4 的证明](https://arxiv.org/html/2608.04014#A1.SS2)
- [B 主要定理与推论的证明](https://arxiv.org/html/2608.04014#A2)
  - [B.1 定理 3.1 的证明](https://arxiv.org/html/2608.04014#A2.SS1)
  - [B.2 定理 3.2 的证明](https://arxiv.org/html/2608.04014#A2.SS2)
  - [B.3 定理 3.3 的证明](https://arxiv.org/html/2608.04014#A2.SS3)
  - [B.4 推论 3.4 的证明](https://arxiv.org/html/2608.04014#A2.SS4)
- [C 推论 1(ii) 中渐近条件的实证依据](https://arxiv.org/html/2608.04014#A3)

## 1 引言

层次聚类[Ward Jr, 1963](https://arxiv.org/html/2608.04014#bib.bib32)通过嵌套划分和树状图提供了一种表示关系数据的基本方式[Shepard, 1962](https://arxiv.org/html/2608.04014#bib.bib30)。在所有可能的层次结构中，次主导（或极小极大）超度量[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)占据了一个典型的位置：它是被给定相异性最大支配的次主导超度量，并在层次聚类和度量几何中起着典型作用。形式上，给定一个度量空间 \((X,d)\)，minimax 超度量可以看作算子 \(U:(X,d)\mapsto(X,u_d)\) 的输出，其中 \(u_d:X\times X\mapsto\mathbb{R}\) 是与 \(d\) 关联的 minimax 超度量。该算子将相异性映射到其相关的次主导超度量，等价地映射为单链接聚类的合并高度函数。Carlsson 等人 [2010](https://arxiv.org/html/2608.04014#bib.bib3) 建立了*单链接聚类*（SLC）的树状图与 minimax 超度量是同一层次结构的等价表示。该量恰好等于两点在单链接树状图中的合并高度。因此，单链接层次聚类可视为计算*被原始距离支配的最大超度量*，从而在树状图与超度量之间提供了精确的几何对应关系。此外，Carlsson 等人 [2010](https://arxiv.org/html/2608.04014#bib.bib3) 通过将层次聚类视为从有限度量空间到超度量空间的映射，建立了严格的数学框架。他们的关键理论结果是，minimax 超度量映射关于格罗莫夫-豪斯多夫（\(\mathcal{GH}\)）度量是 1-利普希茨（非扩张）的。因此，minimax 超度量（SLC 的树状图）在 \(\mathcal{GH}\) 意义下对输入度量的任意扰动是非扩张的，这意味着距离的小变化不会在诱导的超度量中被放大。相比之下，其他基于链接的算子，如完全链接或平均链接，不满足这一非扩张性质。他们的稳定性定理将单链接确立为唯一层次一致且利普希茨稳定的超度量投影。关于扰动的假设，他们的分析是完全一般的；不施加概率或噪声模型。唯一要求是度量扰动在格罗莫夫-豪斯多夫意义下有界，即两个度量空间之间的所有成对距离至多相差一个小的加性 \(\varepsilon\)。在此假设下，每个超度量距离至多改变 \(\varepsilon\)。因此，他们的稳定性定理刻画了度量的均匀全局扰动，但没有处理稀疏或局部化的对抗性编辑。Chowdhury 等人 [2016](https://arxiv.org/html/2608.04014#bib.bib6) 进一步在更具体的范数下分析了稳定性。他们证明了 minmax 超度量算子 \(U:(X,d)\mapsto(X,u_d)\) 在 sup 范数下是 1-利普希茨的。数学上，\(\|u_d-u_{\tilde{d}}\|_\infty \leqslant \|d-\tilde{d}\|_\infty\)，对于 \(X\) 上的所有度量 \(d,\tilde{d}\)。关键是，他们形式化了 Gromov 树嵌入与 SLC 产生的超度量结构之间的对偶性。他们引入了偏离超度量性的度量，量化有限度量空间偏离完美树状的程度。通过这种对偶性，他们证明了单链接树状图计算的是在依赖于空间的超度量性和倍维数的界内最小化加性失真的超度量。本质上，单链接树状图对应于一个最优的超度量树嵌入，其失真同时反映了数据的局部*超度量性*和其内在维数复杂度。这些结果共同将单链接树状图定位为既是最优低失真树嵌入，又是从度量数据到层次结构的全局稳定（利普希茨连续）映射。最近，Mikhailov [2025](https://arxiv.org/html/2608.04014#bib.bib23) 将 Carlsson 等人 [2010](https://arxiv.org/html/2608.04014#bib.bib3) 的稳定性结果推广到所有（可能有界的）度量空间的完整格罗莫夫-豪斯多夫类。他证明了由 Carlsson–Memoli 构造得到的典型次主导（min–max）超度量映射 \(U:(X,d)\mapsto(X,u_d)\) 不仅在有界空间上，而且在任意度量空间上都关于格罗莫夫-豪斯多夫距离是*1-利普希茨*的。这一观点将 \(U\) 解释为*云*（即有限格罗莫夫-豪斯多夫距离下的空间等价类）之间的非扩张映射。此外，对于任何点连通度量空间 \(A\)，他展示了 \(U\) 与 \(A\) 的笛卡尔积之间的逆关系：在有界超度量空间的云上，映射 \(\Psi:X\mapsto X\times A\) 是等距嵌入，且 \(d_{\mathcal{GH}}\bigl(U(\Psi(X)),X\bigr)=0\)，因此 \(U(\Psi(X))\) 与 \(X\)（在格罗莫夫-豪斯多夫意义下）等距，而超度量空间恰好是 \(U\) 的不动点。概念上，这将超度量化算子置于格罗莫夫-豪斯多夫景观上的全局利普希茨稳定变换位置，进一步将度量几何与层次聚类联系起来。

### 1.1 先前理论的空白与动机

针对 minimax 超度量 \(u_d\) 的现有稳定性结果处理的是*均匀*扰动，证明在逐项 l∞ 度量下的非扩张性，并通过标准比较延伸到格罗莫夫-豪斯多夫框架。这些保证限制了处处变化的*幅度*，但对扰动的*稀疏性*和*局部性*不敏感：单个大编辑会使 \(\|d-\tilde{d}\|_\infty\) 变大，由此得到的界允许 \(u_d\) 的每个条目都移动该幅度，即使真实效应仅限于一小部分点对。特别是，均匀理论对稀疏扰动下 \(u_d\) 中诱导变化的*范围*（支撑大小）没有任何控制。我们通过在成对相异性矩阵的汉明型设置中分析超度量映射 \(U:(X,d)\mapsto(X,u_d)\) 来弥补这一空白。具体来说，对于有限度量 \(d\) 定义在 \(X\) 上，我们将 \(d\) 编码为其上三角距离向量，并为该空间配备汉明度量
\[
d_H(d,\tilde{d}) \;=\; \#\bigl\{\{x,y\}\subseteq X:d(x,y)\neq\tilde{d}(x,y)\bigr\},
\tag{1}
\]
即相异性被编辑的点对数量。等价地，\(d_H(d,\tilde{d})=\|d-\tilde{d}\|_0\)，其中 \(\|\cdot\|_0\) 计算非零坐标的个数。尽管 \(\|\cdot\|_0\) 不是范数，它诱导了真正的汉明度量 \(d_H\)，并且我们建立了一种对稀疏性敏感的 l0 型理论，其中改变点对集合由每编辑的暴露割区域控制。特别地，该分析产生了一个仅依赖树的全局包络 \(\bar{L}_T\)，给出如下形式的界：
\[
\|u_d-u_{\tilde{d}}\|_0 \leq \bar{L}_T \,\|d-\tilde{d}\|_0.
\]
\(\bar{L}_T\) 仅依赖于 MST 结构；在 \(n\) 节点图上的最坏情况下，\(\bar{L}_T \leqslant \binom{n}{2}\)。因此，我们的结果沿正交轴补充了经典的 l∞/\(\mathcal{GH}\) 非扩张性：先前的理论控制均匀噪声下条目*移动多少*，而我们的汉明度量保证控制稀疏编辑下*多少条目*可能改变。它们共同构成了一个以前对超度量算子不可用的幅度-范围稳定性图景。

表 1：minimax/次主导超度量的稳定性区间。经典一致界控制变化的*幅度*（\(l_\infty/GH\)），而我们的汉明空间（\(l_0\)）界控制稀疏编辑下变化的*范围*。

### 1.2 现代机器学习中的极小极大超度量

Zhu 等人 [2017](https://arxiv.org/html/2608.04014#bib.bib35) 指出，在常见的层次聚类方法中，只有单链接（即极小极大超度量）在输入权重（相异性）的小扰动下是稳定的，并且在无限样本极限下是一致的。具体来说，他们证明了 SLC 是唯一满足以下条件的方法：*如果 i.i.d. 样本点数趋于无穷，则输出的超度量（在格罗莫夫-豪斯多夫意义下，几乎必然）收敛到数据分布支撑的真实多尺度结构*。Dey 等人 [2017](https://arxiv.org/html/2608.04014#bib.bib10) 通过为每个时间切片拟合超度量并强制小的时间间失真来研究时间层次聚类。他们表明，一般的 l∞ 最近超度量拟合在度量扰动下可能不稳定，因此他们用*极小极大超度量* \(u_d\) 替换它，定义为沿 MST 路径的最大边权；\(u_d\) 是唯一不增加任何输入距离的 l∞-最近超度量。这一选择产生了时间上连贯的单链接树状图（因为 \(u_d\) 是单链接/极小极大超度量），同时在其时间目标中恢复了稳定性。Devijver 等人 [2024](https://arxiv.org/html/2608.04014#bib.bib9) 通过在图形 lasso 之前插入单链接层次聚类步骤来研究高维网络推断中的稳定性，并证明了由此产生的树状图（因此也是单链接背后的极小极大超度量）在数据扰动下是稳定的，这与平均链接不同。具体来说，经典的两步分解首先通过单链接对变量进行聚类……