提出半松弛最优传输方法，高效还原大规模网络的生成结构。
Network Learning with Semi-relaxed Gromov-Wasserstein
- 用概率耦合放松节点匹配，构建半松弛吴尔夫斯坦目标函数。
- 解的误差以 $O(1/n)$ 速率趋近确定性分配，保证可解释性。
- 适用于社区模型与光滑图核，适合网络建模与统计分析研究者。
估计大规模网络的生成机制是统计机器学习中的基本挑战，需识别潜在连接结构，但因缺乏标准节点标签，通常为NP难组合问题。本文通过允许概率耦合，松弛节点分配问题，提出基于半松弛吴尔夫斯坦（semi-relaxed Gromov-Wasserstein）的目标函数，获得生成结构的低维表示。采用块坐标条件梯度算法求解，尽管存在松弛，最优解仍趋近于确定性分配，其优化间隙以 $O(1/n)$ 速率收敛，其中 $n$ 为节点数。该方法支持可解释的模型恢复和严格统计分析：在随机块模型与霍尔德光滑图核下，均实现一致性及极小极大最优收敛率。实现对合成与真实世界数据集高效扩展，具备良好可扩展性。
原文摘要 · Abstract (English)
Estimating the generative mechanism of large-scale networks is a fundamental challenge in statistical machine learning. It requires the identification of the latent connectivity structure, which is in general an NP-hard combinatorial problem due to the absence of canonical node labels. We address this challenge by allowing for probabilistic couplings, thereby relaxing the assignment problem. Our estimation framework can be formulated as a semi-relaxed Gromov-Wasserstein objective and provides a low-dimensional representation of the generative structure. We solve this via a block-coordinate conditional gradient algorithm. Despite the relaxation, the resulting solution is typically deterministic: in fact, we show that the optimality gap between the relaxed solution and the deterministic assignment vanishes at rate $O(1/n)$, where $n$ is the number of nodes. This allows for tractable recovery of the underlying model and enables rigorous statistical analysis: we establish consistency and minimax-optimal convergence rates for both stochastic block models and Holder-smooth graphons. Our implementation scales efficiently with $n$, as demonstrated on both synthetic and real-world datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。