Feb, 2024

低维情况下匹配相关高斯几何模型的 Umeyama 算法

PDF
TL;DR通过研究匹配两个相关的随机几何图的问题，我们研究了通过潜在节点排列相互关联的两个高斯几何模型的匹配问题。我们证明了在低维情况下，当噪声参数小于等于 O (d^-3 * n^-2/d) 时，Umeyama 算法能够准确恢复隐藏的顶点对应关系 π*，当噪声参数小于等于 O (d^-3 * n^-1/d) 时，能够实现几乎准确恢复。我们的结果接近了低维情况下的信息门限，只有一个 poly (d) 的因子差异。
发现论文，激发创造
  • 通过凸松弛求解图匹配问题

    本文介绍了一种应对图匹配问题的新型凸松弛算法，通过闭合迭代的镜像下降方案，实现了在相关高斯维格纳模型下对应的唯一解高概率收敛，进一步确立了输入矩阵的新充要条件，并将其应用于噪声下的地面实况恢复中。

    Oct, 2023

  • 从受审查的边缘测量中解码二进制节点标签：相变和高效恢复

    利用半定规划及二元变量，针对含有噪声的观测变量和图的边缘矩阵进行数据重构和分析，可以对图中两个社区及其相关性进行分析与检测。

    Apr, 2014

  • 关于相关随机块模型的精确图匹配的高效算法

    本研究提出了一种有效的图匹配算法，该算法以基于每个节点的分区树之间的比较为基础，将大邻域划分为不同社区的统计指标来实现在稠密图中高概率完全匹配相关 SBMs 的第一个多项式时间算法。

    May, 2023

  • 有向无权图中的度量恢复

    本文展示了在至少需要 ω(n^(2/(d+2))) 的节点度时（其中 d 为维度），可以从有向无权图中恢复欧几里得度量和相关密度的估计，其中我们的估计器基于有向图上的随机游走的特征化和相应连续极限。

    Nov, 2014

  • 揭示隐藏社区的信息限制

    研究对称数据矩阵中的隐藏社区的恢复问题，聚焦于两种渐近恢复保证类型：弱恢复和精确恢复，并推导出恢复的充分条件和必要条件。结果表明，算法提供弱恢复时，可以通过简单的投票程序在额外线性时间内升级以实现精确恢复。

    Sep, 2015

  • 图匹配：松弛与否？

    本研究考虑权重无向图的精确和非精确匹配问题，通过定义 “friendly graphs” 和发展准确和近似解的确切条件和界限，以及优化找到最优近似同构的能力的凸松弛技术进行解决。

    Jan, 2014

  • 使用图拓扑的不确定性感知高效子图同构

    在没有节点标签的情况下，我们提出了一种在不精确匹配的情况下识别子图与完整图之间节点对应关系的方法，该方法包括两个步骤：提取子图的最小唯一拓扑保持子集及在全图中查找可行匹配，实现基于边界可交换性的独特路径配对扩展匹配集，并通过共识算法。

    Sep, 2022

  • ShapeFit: 从损坏的成对方向中精确恢复位置

    解决位置恢复问题的新算法，针对每个位置的观测，使用一个简单的凸规划方案，可以精确高概率地恢复一组 $n$ 个高斯位置，其中部分受到恶意损坏的观测。

    Jun, 2015

  • 对齐嵌入和几何随机图：Procrustes-Wasserstein 问题的信息结果和计算方法

    我们研究了 Procrustes-Wasserstein 问题，使用欧几里得传输成本作为性能度量，提出了 Ping-Pong 算法，用于匹配高维点云，并与现有方法进行比较。

    May, 2024

  • 使用图神经网络进行随机几何图对齐

    通过研究在存在顶点特征信息时，图神经网络在图对齐问题中的表现，我们证明在特征向量的稀疏性和噪声水平满足一定条件的情况下，经过精心设计的一层图神经网络能够高概率地恢复出两个图的顶点之间正确的对应关系，并且我们还证明了对于噪声水平的条件是近似最优的。最后，我们将图神经网络与直接解决带有噪声顶点特征的分配问题进行了性能比较，结果表明，当噪声水平至少是一个常数时，直接匹配无法完美恢复，而图神经网络可以容忍噪声水平增长至图的大小的某个幂次。

    Feb, 2024