基于有向图的度量空间混合与融合：加权度量、图运算与平均距离控制

《Discrete Mathematics》：Mixing and merging metric spaces using directed graphs

　　

设 (X₁,d₁),…,(X_N,d_N) 为度量空间，其中 d_i:X_i×X_i→[0,1]，并设 X=∏_i=1^NX_i。设 G 为顶点集 [N]={1,…,N}、边集 E(G) 的有向图。给定边权 P={p_ij∈(0,1]:(i,j)∈E(G)}，定义闭入邻域 B_j(G):={j}∪{i:(i,j)∈E(G)}，并令 p_jj=1。对 g,h∈X，定义 d_X,G,P(g,h):=1?(1/N)∑_j=1^N∏_i∈Bj(G)(1?d_i(g_i,h_i))^1/p_ij。研究人员证明 d_X,G,P 是度量，并分析其在图运算（不相交并、笛卡尔积）下的行为。该族度量受两个定量原则支配：(i) 边稠密化（添加边）在逐点和期望意义下增大距离，并具有精确的单边增量公式和一致的 1/N 灵敏度界；(ii) 权重单调性：增大边权 p_ij 会使度量减小。当各坐标对独立时，可获得平均距离的闭式分解。在离散特例 X=F_q^N、d_i∈{0,1} 且 G 为有向无环图时，将 G 替换为推论1.4中的有向自反传递闭包 G_? 后，未归一化距离 D_X,G?,P:=Nd_X,G?,P 等于支撑集的遗传闭包大小，从而通过对下理想的计数得到偏序集/有向图球填充界。最后，研究人员给出该构造的连续类比，通过显式积分公式在 C([0,1],C) 上得到度量。这些结果统一并推广了编码理论中若干基于图的度量，同时为平均距离控制提供了新的设计杠杆。

研究背景与问题：度量空间是编码理论、机器学习、数据融合与生态网络等领域的基本工具。实际应用中往往需要把多个具有不同度量特征的坐标分量组合起来，例如混合信道或不同调制方案；传统偏序集度量（poset metric）和有向图度量虽能处理单一结构，但缺乏通过任意有向图和边权灵活混合多个归一化坐标度量的统一框架。为此，Mahir Bilen Can与Shantanu Chakrabartty提出一种图加权度量构造：对闭入邻域（closed in-neighborhood）B_j(G) 上的坐标距离做加权乘积后取平均，再转化为距离值。研究人员证明了该构造满足度量公理，并系统分析其在有向图半环的不相交并和笛卡尔积两种运算下的行为。主要意义在于统一并推广了编码理论中若干基于图的度量，并为平均距离控制提供了显式设计杠杆。

主要技术方法：研究以数学证明为主，辅以数值实验。核心工具包括：利用Sch?nberg型变换引理证明坐标距离经 φ_α(t)=1?(1?t)^α 变换后仍为度量，并用乘积度量引理证明闭入邻域上的子度量；通过非负伪度量线性组合证明主度量；利用有向自反传递闭包与偏序集下理想（lower ideal）计数证明离散特例和球填充界；用期望分解和Jensen不等式给出平均距离的闭式与界；通过图极限（graphon）获得连续度量。数值实验使用合成有向图：连续坐标均匀采样自 [0,1]^N，基距离取 d_i(g_i,h_i)=1/2|g_i?h_i|；离散实验在 {0,1}^N 上使用 {0,1} 值离散度量。

主要结果：
（1）主定理与图运算行为。主定理证明 d_X,G,P 是归一化度量。在图运算方面，若 G 是两个子图 G₁、G₂ 的不相交并，则总距离等于两子距离按坐标数 N₁/N、N₂/N 的加权平均；若采用笛卡尔积 G₁□G₂，则距离公式是顶点集上的乘积平均，一般不能分解；但在存活矩阵可乘分离且两个因子图为加权入正则时，1?d 可分解为两个因子 S₁(r)S₂(c)，等价地 d=d₁(B)+d₂(A)?d₁(B)d₂(A)，其中 A、B 为加权入度。

（2）离散特例与球填充界。当 X=F_q^N、d_i∈{0,1} 且 G 为有向无环图（DAG）时，将 G 换成其有向自反传递闭包 G_? 后，未归一化距离 D_X,G?,P=Nd_X,G?,P 等于支撑集 supp(g,h) 的遗传闭包大小。由此得到球填充界：若码 C 的最小未归一化 G-距离为 D_min，则 |C| 不超过 q^N 除以半径为 ?(D_min?1)/2? 的闭球体积，并可进一步用大小不超过该半径的下理想数目 J_G(s) 求和给出 |C|≤q^N/∑_s=0^{?(D_min?1)/2?}J_G(s)(q?1)^s。

（3）连续graphon极限。在 ρ(u,v)=?log(1?d(u,v)) 为度量的条件下，研究人员给出当 N→∞ 且图序列收敛到图极限（graphon）W 时的连续模拟：d_G,W(g,h)=1?E_x[exp(E_y[log(1?d(g(y),h(y)))W(x,y)])]，该式在 C([0,1],C) 上定义度量。

（4）平均距离与敏感性原理。在坐标对独立的概率度量 μ 下，平均距离 M_μ(G,P)=1?(1/N)∑_j∏_i∈Bj(G)m_i(1/p_ij)，其中 m_i(t)=E[(1?d_i)^t]。添加一条边 (i→j) 的逐点增量为 (1/N)Q_j(G)(1?(1?d_i)^1/p)，且不超过 1/N；因此任意图 G?G′ 的均值差不超过 |E(G′)?E(G)|/N。增大边权 p_ij 会减小度量；当坐标对独立同分布且边权相等时，平均距离由入度决定。这些结果解释了边稠密化使经验距离直方图右移的现象。

讨论与结论：讨论部分指出，该框架适用于具有异质坐标和结构化交互的机器学习与数据融合，以及具有网络化依赖的生态系统；加边可在受控范围内提高期望距离，调节权重可预测地降低或提高距离，从而为体系结构选择提供原则。结论部分可译为：该研究引入了一种新的度量空间，利用任意有向图来度量距离，使其适用于表示不同离散对象的图和子图；通过合成图展示了由所提距离度量得到的统计量可揭示多种图性质；研究人员认为该度量空间将广泛应用于通常采用距离算法的可视化与分析任务，如机器学习中的聚类；对于某些问题和数据结构，该框架可省去开发新数学方法的必要，尤其是在AI模型训练数据稀疏时；Wasserstein距离在生成式AI模型性能提升中的成功也说明了这种相关性。