Cluster-Graph Edit Distance: Metric Proxies, Multiscale Embeddings, and Complexity

本文研究簇图（即完全子图的不相交并）上的聚类图编辑距离 $q^{\ast }(\lambda ,\mu )$，该距离定义为两个整数分拆 $\lambda ,\mu ⊢n$ 对应簇图之间在所有顶点重标号下的边对称差最小值。核心贡献在于揭示其与运输问题的深刻联系：$q^{\ast }(\lambda ,\mu )=\frac{\mathrm{\parallel }\lambda {\mathrm{\parallel }}_2^2+\mathrm{\parallel }\mu {\mathrm{\parallel }}_2^2}{2}-{\max }_{X\in T(\lambda ,\mu )}\mathrm{\parallel }X{\mathrm{\parallel }}_F^2$，其中 $T(\lambda ,\mu )$ 是行列和分别为 $\lambda$、$\mu$ 的非负整数矩阵集合。基于此恒等式，论文构建了两类最优的 ${\mathrm{\ell }}^1$-型度量代理——顶点质量度量 ${\delta }_1$（基于排序后度序列的 ${\mathrm{\ell }}^1$ 距离）满足 $\frac{1}{2}{\delta }_1\le q^{\ast }<\frac{3}{2}{\delta }_1$，常数均紧；块能量度量 $B$（基于二项式块大小向量的 ${\mathrm{\ell }}^1$ 距离）满足 $q^{\ast }\le B\le 2q^{\ast }-1$，上界常数 2 最优且不可达。由此导出 $O(n\log n)$ 时间近似算法，输出代价严格小于 $2q^{\ast }$ 的对齐方案，并给出精确区间定位 $q^{\ast }\in [\lceil (B+1)\mathrm{/}2\rceil ,B]$，从而证明 ${\mathrm{\ell }}^1$ 嵌入失真 $c_1(K_n)\le 2$。在欧氏嵌入方面，首次确定簇图族的欧氏失真阶为 $\mathrm{\Theta }(n^{1\mathrm{/}4})$，并构造一族可计算的多尺度坐标映射 $F^{(\gamma )}$，其维度低于 $4n$、计算时间为 $O(n)$；特别地，临界权重 $\gamma =1\mathrm{/}4$ 下的映射实现失真 $O(n^{1\mathrm{/}4}(\log n{)}^{1\mathrm{/}4})$，优于无权情形的 $\mathrm{\Theta }(n^{1\mathrm{/}4}\sqrt{\log n})$，且该改进由阶梯跳跃量化导出的逆能量不等式保证。计算复杂性方面，证明判定 $q^{\ast }(\lambda ,\mu )\le Q$ 是强 NP-完全问题，精确计算强 NP-难，不存在 FPTAS（除非 P=NP），而最远对齐问题可在多项式时间内求解。所有结果统一源于同一运输表示，兼具组合精确性与几何结构性。