Network Learning with Semi-Relaxed Gromov-Wasserstein¶

会议: NeurIPS 2026
arXiv: 2606.02223
代码: https://github.com/HongtengXu/SGWB-Graphon
领域: 图学习
关键词: 随机块模型, 图元估计, 半松弛Gromov-Wasserstein, 最优传输, 块坐标条件梯度

一句话总结¶

本文提出基于半松弛Gromov-Wasserstein（srGW）重心的非参数网络生成机制学习框架，将NP难的离散节点分配松弛为连续概率耦合，理论证明其与确定性分配的最优性差距随节点数以 $\mathcal{O}(1/n)$ 速率衰减，并在SBM与光滑Graphon下取得极小化极大最优收敛速率。

研究背景与动机¶

在大规模复杂网络分析中，从单张观测邻接矩阵推断底层的网络生成机制、聚类结构以及社区连接模式是统计机器学习的核心基础任务。此类问题广泛存在于社交网络分析、蛋白质-蛋白质相互作用（PPI）生物网络推断、网络推荐系统以及交通基础设施中。然而，真实网络往往高度稀疏、存在噪声且完全缺乏规范的节点标签（canonical node labeling）。这种置换不变性（permutation invariance）导致模型参数只能在节点置换意义下可辨识，本质上对应着未知设计点下的非参数回归问题。传统的矩阵误差度量（如Frobenius范数或 $\ell_2$ 范数）无法直接衡量估计器与真实生成机制之间的距离，给统计推断带来了根本性的概念与分析挑战。

在随机块模型（SBM）或连续非参数图元（Graphon）模型中，生成机制的推断通常需要联合估计低维块连接概率矩阵以及离散的节点到社区分配映射。这一问题在数学上可表述为最小二乘准则下的组合优化问题。然而，在 $n$ 个节点和 $k$ 个潜在块构成的候选空间中，离散分配映射的搜索空间大小达到 $k^n$，精确求解属于NP难问题，导致全局极大似然估计或组合最小二乘在计算上完全不可行。传统的谱聚类或度数排序方法虽然高效，但对度异质性敏感，且在非对角或反同配（dissociative）复杂网络结构中极易失效；而现有的图元估计方法如邻域平滑（NBDsmooth）或USVT无法提供紧凑低维且可解释的块结构表征。

最优传输领域的Gromov-Wasserstein（GW）距离通过比较网络内部节点的成对关系几何结构而非节点显式对应，为置换不变的网络比较提供了强有力的几何工具。然而，现有的GW图重心方法主要针对经验图平均，高度依赖破坏离散分配的熵正则化（如Sinkhorn平滑），缺乏对生成结构参数恢复的严格统计保证。核心 idea：将硬组合节点分配松弛为单侧边际自由的半松弛Gromov-Wasserstein（srGW）概率耦合，建立非凸松弛解向确定性离散划分集中的 $\mathcal{O}(1/n)$ 紧致有限样本最优性差距上界，并设计GPU加速的块坐标条件梯度算法，在多项式时间内同时实现极小化极大最优恢复速率与低维可解释生成模型重构。

方法详解¶

整体框架¶

本文构建了一个端到端的非参数网络生成机制学习框架。给定单个含 $n$ 个节点的无向无自环网络邻接矩阵 $E \in \{0, 1\}^{n \times n}$，目标是拟合一个包含至多 $k \ll n$ 个块的紧凑离散SBM块模型 $(B, \nu)$，以逼近未知的连续生成Graphon $W$ 或离散SBM真实参数。整体流水线分为三步：首先，将离散分配映射松弛为左边际为均匀分布、右边际自由的概率传输计划 $\pi \in \Pi_{[n], k}$，并通过块坐标最小化（BCM）交替求解srGW重心问题；随后，基于理论保证将收敛后的连续最优传输计划通过最大后验取整映射（rounding map）离散化为确定的社区标签 $\hat{z}$；最后，代入封闭解析解计算出最终的块连接概率矩阵 $\hat{B}$ 与块权重向量 $\hat{\nu}$。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["观测网络邻接矩阵<br/>E ∈ {0,1}nxn"] --> B["半松弛Gromov-Wasserstein目标构建<br/>解耦左均匀边际与自由右边际"]
    B --> C["块坐标交替求解算法<br/>闭式B更新与Frank-Wolfe传输优化"]
    C --> D["自修剪有效块选择<br/>自由右边际驱动非活跃块质量归零"]
    D --> E["有限样本确定性取整映射<br/>arg max分配且截断间隙O(1/n)"]
    E --> F["输出紧凑块模型<br/>参数B(z)与经验权重ν(z)"]

关键设计¶

1. 半松弛Gromov-Wasserstein连续松弛：摆脱组合搜索并赋予右边际模型选择能力 面对硬分配组合优化的计算障碍，本设计将离散分配映射 $z: [n] \to [k]$ 放宽为概率耦合矩阵 $\pi \in \mathbb{R}_{+}^{n \times k}$，其左边际严格约束为观测网络节点上的离散均匀测度，而右边际 $\nu(a) = \sum_{i=1}^n \pi_{i,a}$ 完全自由： $$\Pi_{[n],k} = \left\{\pi \in \mathbb{R}_{+}^{n \times k}: \sum_{a=1}^k \pi_{i,a} = \frac{1}{n}, \quad \forall i \in [n]\right\}$$ 当传输计划 $\pi$ 给定时，最小化重构损失的块连接矩阵 $B(\pi)$ 具有唯一的封闭最小二乘解析解： $$B(\pi)_{a,b} = \sum_{i,j=1}^n \frac{E_{i,j} \pi_{i,a} \pi_{j,b}}{\nu(a) \nu(b)}$$ 该设计将不可微的离散优化转化为连续紧凸集上的半松弛Gromov-Wasserstein重心优化问题。更为精妙的是，自由的右边际 $\nu$ 充当了隐式的模型复杂度正则化器：当设定的初始最大块数 $k_{\max}$ 大于真实或最优有效复杂度时，无法进一步降低传输成本的多余潜在块会自动被分配零概率质量并被剪枝，避免了繁琐的外层超参数搜索与交叉验证。

2. 确定性极值集中与独立于 $k$ 的 $\mathcal{O}(1/n)$ 最优性差距界：连接连续松弛与离散物理真相的桥梁 软概率松弛的核心隐忧在于所得最优解可能高度弥散，无法对应真实离散网络社区。本文揭示了半松弛GW目标所蕴含的内生确定性集中机制：由于右边际未受限制，局域极小值处的目标函数关于各节点分配呈现线性依赖结构。对于任意给定的块矩阵 $B$，定义一阶取整映射 $z(\pi)$： $$z(\pi)_i = \min \left\{ a \in \arg\max_{a' \in [k]} \pi_{i, a'} \right\}, \quad i \in [n]$$ 作者证明了任何局部极小值（及Frank-Wolfe驻点）处，节点仅在其使边际代价最小的块上分配正概率质量。通过构造两步消除微扰技术并对可能出现的平局（ties）进行非对称重平衡分析，消除了高阶项，最终建立了与块数 $k$ 完全无关的紧致有限样本最优性差距上界： $$0 \leq \mathcal{L}_{E, B}(\tilde{z}) - \mathcal{L}_{E, B}(\tilde{\pi}) \leq \frac{\|B\|_{\infty}^2}{n}$$ 这一理论突破至关重要：由于上界完全不依赖于潜在块数 $k$，使得当处理连续光滑Graphon时，即便允许块数随样本量发散（如 $k \asymp n^{1/(\alpha \wedge 1 + 1)}$），连续松弛产生的重构开销仍然被严格压制在 $\mathcal{O}(1/n)$ 阶以内，为后续非参数极小化极大统计最优性提供了严谨支撑。

3. GPU加速的块坐标条件梯度算法（BCM）：无投影的大规模网络高效求解 针对srGW目标非凸且包含四阶张量乘积的计算瓶颈，设计了交替块坐标迭代算法。算法在外层交替进行：固定当前耦合 $\pi^{(t)}$ 时直接利用矩阵张量缩并以 $\mathcal{O}(nk)$ 复杂度解析刷新块连接矩阵 $B^{(t+1)}$；固定 $B^{(t+1)}$ 时，调用无投影的Frank-Wolfe条件梯度子程序更新传输耦合 $\pi^{(t+1)}$。在Frank-Wolfe迭代中，线搜索步长由精确一维解析步长公式确定，内层线性子问题完全解耦为每个节点在 $k$ 个候选块上的独立最小线性指派（即对 $n \times k$ 梯度矩阵每行执行 arg min），避免了昂贵的全局二分图匹配或投影开销。整个迭代流程高度适宜于并行化张量计算，结合Python最优传输库（POT）可在现代GPU上数秒内完成数千节点规模网络的完整推断。

损失函数 / 训练策略¶

网络的整体联合目标函数定义为： $$\min_{\pi \in \Pi_{[n],k}, B \in [0,1]^{k \times k}} \mathcal{L}_E(\pi, B) := \sum_{i,j=1}^n \sum_{a,b=1}^k |E_{i,j} - B_{a,b}|^2 \pi_{i,a} \pi_{j,b}$$ 优化策略采用外层相对误差截断准则：当连续两次外层迭代的重构损失相对变化满足 $|\mathcal{L}_E^{(t+1)} - \mathcal{L}_E^{(t)}| / \mathcal{L}_E^{(t)} < 10^{-6}$ 时终止迭代。实践中对于 $n$ 高达 $10^4$ 的网络，通常不到 50 次外层迭代即可收敛。关于初始化，Graphon模型采用基于邻接矩阵谱嵌入的 $k$-means 离散硬标签初始化以防止陷入局部劣解，而标准SBM模型采用双边际独立乘积测度初始化即可获得最快收敛速度。

实验关键数据¶

主实验¶

在 $n = 2000$ 的基准设置下，对比四种随机块模型（S1-S4）和六种不同光滑度连续图元（G1-G6），以真值与估计之间的Gromov-Wasserstein距离（$\times 10^{-3}$）为评估指标，各进行 20 次独立蒙特卡洛实验。对比基线包括最大间隙法（LG）、邻域平滑法（NBDsmooth）、排序平滑法（SAS）以及通用奇异值阈值法（USVT）。

模型类别	结构编号	LG	NBDsmooth	SAS	USVT	本文方法 (Ours)
SBM	S1 (2-block 强同配)	$88.4_{\pm 2.9}$	$0.82_{\pm 0.007}$	$81.3_{\pm 11.0}$	$0.32_{\pm 0.007}$	$0.013_{\pm 0.0003}$
SBM	S2 (2-block 反同配)	$88.6_{\pm 2.6}$	$0.82_{\pm 0.007}$	$82.2_{\pm 9.8}$	$0.32_{\pm 0.007}$	$0.31_{\pm 0.0003}$
SBM	S3 (非对称规模)	$71.9_{\pm 17.0}$	$0.82_{\pm 0.004}$	$0.97_{\pm 0.19}$	$0.32_{\pm 0.004}$	$0.31_{\pm 0.0004}$
SBM	S4 (3-block 混合)	$40.7_{\pm 14.0}$	$0.81_{\pm 0.010}$	$5.8_{\pm 3.5}$	$0.45_{\pm 0.010}$	$0.24_{\pm 0.001}$
Graphon	G1 ($W=u \cdot v$)	$2.8_{\pm 0.66}$	$0.70_{\pm 0.012}$	$0.46_{\pm 0.011}$	$0.18_{\pm 0.005}$	$0.61_{\pm 0.05}$
Graphon	G2 ($W=0.5(u+v)$)	$2.2_{\pm 0.39}$	$1.0_{\pm 0.009}$	$0.62_{\pm 0.009}$	$1.7_{\pm 0.07}$	$0.80_{\pm 0.06}$
Graphon	G3 ($W=e^{-\max(u,v)^{0.75}}$)	$1.3_{\pm 0.12}$	$1.2_{\pm 0.011}$	$1.0_{\pm 0.019}$	$0.73_{\pm 0.016}$	$0.81_{\pm 0.10}$
Graphon	G4 ($W=	u-v	$)	$42.6_{\pm 1.1}$	$0.88_{\pm 0.007}$	$42.0_{\pm 1.1}$
Graphon	G5 ($W=1-	u-v	$)	$42.8_{\pm 1.2}$	$0.91_{\pm 0.010}$	$41.9_{\pm 1.1}$
Graphon	G6 ($W=0.5+0.5\sin(2\pi u)\sin(2\pi v)$)	$55.7_{\pm 9.8}$	$0.93_{\pm 0.015}$	$54.3_{\pm 11.0}$	$0.34_{\pm 0.008}$	$0.92_{\pm 0.05}$

消融实验¶

针对优化初值敏感性与自适应模型截断行为，在代表性生成机制下评估不同初始化策略对GW恢复误差及有效块数选择的影响。

初始化策略	SBM (S1) GW误差 ($\times 10^{-3}$)	SBM 有效块数 $\hat{k}$ (真值=2)	Graphon (G4) GW误差 ($\times 10^{-3}$)	Graphon 运行耗时 (s, CPU)
$k$-means 谱聚类初始化 (默认)	$0.015_{\pm 0.001}$	2.1	$0.72_{\pm 0.12}$	12.4
谱聚类 (Spectral) 初始化	$0.021_{\pm 0.003}$	2.2	$1.15_{\pm 0.18}$	14.8
独立外积 (Product) 初始化	$0.013_{\pm 0.0003}$	2.0	$4.85_{\pm 0.95}$	8.2
均匀随机 (Uniform) 初始化	$0.182_{\pm 0.045}$	3.5	$8.40_{\pm 1.20}$	18.5

关键发现¶

双模态一致优越性：本文方法是全场唯一在SBM离散结构与Graphon连续结构上均保持前列的估计器。在SBM中，误差较次优基线降低高达一个数量级（S1达 $0.013 \times 10^{-3}$）；而传统低维方法如LG或SAS在周期性或绝对差值图元（G4-G6）上发生灾难性崩溃（误差超过 $40 \times 10^{-3}$）。
可解释性与紧凑性：虽然USVT在纯低秩图元（如秩1的G1）中依靠奇异值截断取得了最小GW距离，但其输出为 $n \times n$ 的稠密连续矩阵，完全丧失了社区聚合能力与低维紧凑解释性；而本文方法重构出只有 $k$ 个离散块的高保真可解释生成模型。
自适应剪枝特性：实验验证了自由右边际的自剪枝效应，只要初始设置 $k_{\max} \geq 2k_{\mathrm{opt}}$，多余的块被赋予零测度，最终GW估计误差对 $k_{\max}$ 呈现出高度稳健的平台期。

亮点与洞察¶

巧妙证明了半松弛Gromov-Wasserstein重心问题的极值解天然趋向确定性分配，且松弛代价上界为与块数 $k$ 无关的 $\mathcal{O}(1/n)$，彻底打通了连续松弛与离散估计之间的理论鸿沟。
打破了传统图元恢复依赖无约束 $n \times n$ 矩阵去噪的定势，通过非参数块逼近实现了集降维压缩、结构推断与置换不变性于一体的统一框架。
提出的无投影Frank-Wolfe与闭式B更新交替方案具备完全的并行化优势，使千节点级网络的全局非参数图元拟合从以往的小时级骤降至数秒，极大扩展了最优传输在图表示学习中的应用边界。

局限与展望¶

理论局限：当前的统计收敛保证依赖于全局极小值性质，而实用的条件梯度算法在非凸景观中理论上仅能保证收敛至一阶Karush-Kuhn-Tucker（KKT）或Frank-Wolfe平稳点，算法平稳点与全局极小之间的间隙在理论上尚未完全闭合。
显式稀疏惩罚缺失：虽然自由右边际展现了经验上的自剪枝倾向，但模型尚未引入显式的块数 $L_0$ 或稀疏正则项，在极端噪声背景下 $k$-means 初值可能轻微高估有效块数。
扩展方向：可进一步将框架拓展至动态时变网络、超图（Hypergraphs）以及结合节点高维文本/向量属性的富属性图元生成机制推断。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次从统计推断视角系统阐明srGW连续松弛的确定性收敛机理，给出了与 $k$ 无关的 $\mathcal{O}(1/n)$ 紧致差距界。
实验充分度: ⭐⭐⭐⭐⭐ 覆盖10种合成机制、2020次蒙特卡洛检验、多种初值消融以及脑电EEG与航线真实网络案例。
写作质量: ⭐⭐⭐⭐⭐ 结构逻辑环环相扣，从数学直觉、理论推导到算法设计与实证分析层层递进。
价值: ⭐⭐⭐⭐⭐ 兼具深刻的数学理论美感与突出的工程落地实用性，为非参数图统计推断提供了全新范式。

模型类别	结构编号	LG	NBDsmooth	SAS	USVT	本文方法 (Ours)
SBM	S1 (2-block 强同配)	\(88.4_{\pm 2.9}\)	\(0.82_{\pm 0.007}\)	\(81.3_{\pm 11.0}\)	\(0.32_{\pm 0.007}\)	\(0.013_{\pm 0.0003}\)
SBM	S2 (2-block 反同配)	\(88.6_{\pm 2.6}\)	\(0.82_{\pm 0.007}\)	\(82.2_{\pm 9.8}\)	\(0.32_{\pm 0.007}\)	\(0.31_{\pm 0.0003}\)
SBM	S3 (非对称规模)	\(71.9_{\pm 17.0}\)	\(0.82_{\pm 0.004}\)	\(0.97_{\pm 0.19}\)	\(0.32_{\pm 0.004}\)	\(0.31_{\pm 0.0004}\)
SBM	S4 (3-block 混合)	\(40.7_{\pm 14.0}\)	\(0.81_{\pm 0.010}\)	\(5.8_{\pm 3.5}\)	\(0.45_{\pm 0.010}\)	\(0.24_{\pm 0.001}\)
Graphon	G1 (\(W=u \cdot v\))	\(2.8_{\pm 0.66}\)	\(0.70_{\pm 0.012}\)	\(0.46_{\pm 0.011}\)	\(0.18_{\pm 0.005}\)	\(0.61_{\pm 0.05}\)
Graphon	G2 (\(W=0.5(u+v)\))	\(2.2_{\pm 0.39}\)	\(1.0_{\pm 0.009}\)	\(0.62_{\pm 0.009}\)	\(1.7_{\pm 0.07}\)	\(0.80_{\pm 0.06}\)
Graphon	G3 (\(W=e^{-\max(u,v)^{0.75}}\))	\(1.3_{\pm 0.12}\)	\(1.2_{\pm 0.011}\)	\(1.0_{\pm 0.019}\)	\(0.73_{\pm 0.016}\)	\(0.81_{\pm 0.10}\)
Graphon	G4 ($W=	u-v	$)	\(42.6_{\pm 1.1}\)	\(0.88_{\pm 0.007}\)	\(42.0_{\pm 1.1}\)
Graphon	G5 ($W=1-	u-v	$)	\(42.8_{\pm 1.2}\)	\(0.91_{\pm 0.010}\)	\(41.9_{\pm 1.1}\)
Graphon	G6 (\(W=0.5+0.5\sin(2\pi u)\sin(2\pi v)\))	\(55.7_{\pm 9.8}\)	\(0.93_{\pm 0.015}\)	\(54.3_{\pm 11.0}\)	\(0.34_{\pm 0.008}\)	\(0.92_{\pm 0.05}\)

初始化策略	SBM (S1) GW误差 (\(\times 10^{-3}\))	SBM 有效块数 \(\hat{k}\) (真值=2)	Graphon (G4) GW误差 (\(\times 10^{-3}\))	Graphon 运行耗时 (s, CPU)
\(k\)-means 谱聚类初始化 (默认)	\(0.015_{\pm 0.001}\)	2.1	\(0.72_{\pm 0.12}\)	12.4
谱聚类 (Spectral) 初始化	\(0.021_{\pm 0.003}\)	2.2	\(1.15_{\pm 0.18}\)	14.8
独立外积 (Product) 初始化	\(0.013_{\pm 0.0003}\)	2.0	\(4.85_{\pm 0.95}\)	8.2
均匀随机 (Uniform) 初始化	\(0.182_{\pm 0.045}\)	3.5	\(8.40_{\pm 1.20}\)	18.5