Apr, 2024

抵抗力是关键：图上有效抵抗力与某些最优输运问题的等价性

PDF
TL;DR图上的有效电阻和最优传输领域与组合数学、几何学、机器学习等具有广泛关联。本文提出了一个大胆的观点，即这两个领域应被理解为相同的，仅在于选择 $p$。通过引入参数化的 $p$-Beckmann 距离家族来确立这一观点，并将其与某些 Wasserstein 距离紧密关联。进而，我们揭示了一系列结果，包括与图上最优停时、随机行走、图 Sobolev 空间以及 $2$-Beckmann 距离的 Benamou-Brenier 公式的明确联系。我们还进一步探讨了在图数据的无监督学习领域中的实证意义，并建议进一步研究在计算中 Wasserstein 距离可能存在的瓶颈问题。
发现论文，激发创造
  • 有向、加权图的最优运输距离：以细胞间通信网络为例的案例研究

    比较最优输运的图表近期引起了相当大的关注，由于最优输运所引发的距离既提供了图表之间的合理度量，又给出了关联图表之间在输运计划方面的可解释描述；由于缺乏对称性，在通常考虑的形式中引入了挑战，因此图表的最优输运距离主要针对无向图进行了开发。在本文中，我们提出了两种基于变种最优输运的距离度量来比较有向图：(i) 汉明距离 (Wasserstein) 和 (ii) Gromov-Wasserstein (GW) 距离。我们评估了这两种距离，并讨论了它们在模拟图表数据和从单细胞 RNA 测序数据推断的真实世界有向细胞间通信图表中的相对性能。

    Sep, 2023

  • GOT: 一种图比较的最优传输框架

    我们提出了一个完全新的基于最优传输的框架，用于比较图形，该框架能够有效地解决不同任务，如图形对齐，图形分类和图形信号预测问题，通过显式解析 Wasserstein 距离的表达式，其中图拉普拉斯矩阵被用来描述类似于曲面的图形信号分布的概率分布，最终优化处理的难点是用基于贝叶斯探索的随机算法来破解图形对齐问题的非凸性。

    Jun, 2019

  • 图的双调距离及其高阶变体：理论性质及在中心性和聚类中的应用

    基于 biharmonic 和 k-harmonic 距离的连接性、聚类算法和边缘中心性。

    Jun, 2024

  • 连续图传输距离

    该论文提出了一种基于图顶点的概率分布最优传输方法，它不仅满足三角不等式，而且具有更好的可扩展性和与连续传输理论的联系，同时提供了一个适用于该方法的时间离散化方法并验证了其有效性。

    Mar, 2016

  • 估算有效电阻的本地算法

    本文设计了几种本地算法来估计图的有效电阻，可以在对数时间内近似计算两个顶点之间的电阻，通过基准数据的广泛实证研究，验证了算法的性能。

    Jun, 2021

  • 关于不可比空间的最优输运问题的贡献

    该论文讨论了 Optimal Transport 在不同空间中的运用，尤其是研究了如何在图形和结构化数据之间定义和应用 Optimal Transport，特别是在这些数据属于不可比较空间时如何完成适应操作。该文提出了一组 Optimal Transport 工具，其中包括对 Gromov-Wasserstein 距离的研究，其性质可以定义不同空间中的有趣运输问题。我们分析了各种工具的数学性质，建立了计算它们的算法解决方案，并研究了它在许多机器学习场景中的适用性，其中包括分类和简化、结构数据分区以及异构域适应。

    Nov, 2020

  • 基于子空间投影的最优运输在机器学习应用中的利用

    使用投影和子空间的替代方法优化原始的最优输运问题，同时研究其在不同领域的应用，包括黎曼流形、不平衡最优输运问题、梯度流和概率测度空间中的 Busemann 函数以及 Gromov-Wasserstein 距离的推广。

    Nov, 2023

  • 基于近似有效 $p$- 阻抗的多类图聚类

    本文提出了一种近似值来计算 (有效的)$p$- 电阻，并将其应用于多类聚类，将其与其他 $p$-Laplacian 基于方法进行了比较。

    Jun, 2023

  • 似曾相识度量是最优传输距离，并且可以高效计算

    我们提出了一种新的框架，用于在马尔科夫链之间制定最佳输运距离的形式化。我们将此问题转化为在约化空间中求解线性规划的问题，并且通过 Sinkhorn Value Iteration 方法计算最佳输运距离，从而得到与马尔科夫链的 bisimulation metrics 完全匹配的结果。

    Jun, 2024

  • 随机最短路径理论的进展及图节点距离比较

    发展了一种参数化距离的理论，主要包括随机最短路径不相似度和自由能距离，并比较了这些距离在图节点聚类和分类任务中的应用，结果表明自由能距离表现最好。

    Dec, 2012