论文标题
随机图中的熵最佳传输
Entropic Optimal Transport in Random Graphs
论文作者
论文摘要
在图形分析中，经典任务包括计算（组）节点之间的相似性度量。在潜在空间随机图中，节点与未知的潜在变量相关联。然后，可以仅使用图形结构，寻求直接在潜在空间中计算距离。在本文中，我们表明，可以始终如一地估计潜在空间中节点组之间的熵调查最佳转运（OT）距离。对于成本矩阵的扰动，我们为熵OT提供了一般稳定性结果。然后，我们将其应用于多个随机图的示例，例如歧管上的图形或$ε$ - 图。在此过程中，我们证明了所谓的通用奇异值阈值估计器以及歧管上的大地距离估计的新浓度结果。
In graph analysis, a classic task consists in computing similarity measures between (groups of) nodes. In latent space random graphs, nodes are associated to unknown latent variables. One may then seek to compute distances directly in the latent space, using only the graph structure. In this paper, we show that it is possible to consistently estimate entropic-regularized Optimal Transport (OT) distances between groups of nodes in the latent space. We provide a general stability result for entropic OT with respect to perturbations of the cost matrix. We then apply it to several examples of random graphs, such as graphons or $ε$-graphs on manifolds. Along the way, we prove new concentration results for the so-called Universal Singular Value Thresholding estimator, and for the estimation of geodesic distances on a manifold.
