The graph matching problem seeks to find an alignment between the nodes of two graphs that minimizes the number of adjacency disagreements. Solving the graph matching is increasingly important due to it's applications in operations research, computer vision, neuroscience, and more. However, current state-of-the-art algorithms are inefficient in matching very large graphs, though they produce good accuracy. The main computational bottleneck of these algorithms is the linear assignment problem, which must be solved at each iteration. In this paper, we leverage the recent advances in the field of optimal transport to replace the accepted use of linear assignment algorithms. We present GOAT, a modification to the state-of-the-art graph matching approximation algorithm "FAQ" (Vogelstein, 2015), replacing its linear sum assignment step with the "Lightspeed Optimal Transport" method of Cuturi (2013). The modification provides improvements to both speed and empirical matching accuracy. The effectiveness of the approach is demonstrated in matching graphs in simulated and real data examples.
翻译：图形匹配问题试图在两个图形的节点之间找到匹配点, 以最大限度地减少相邻差异的数量。 解决图形匹配因其在操作研究、 计算机视觉、 神经科学等方面的应用而变得越来越重要。 但是, 目前最先进的算法在匹配非常大的图表方面效率不高, 尽管它们能产生良好的准确性 。 这些算法的主要计算瓶颈是线性分配问题, 必须在每次迭代中加以解决 。 在本文中, 我们利用最佳运输领域的最新进展来取代所接受的线性分配算法的使用。 我们展示了GOAT, 对最先进的图表匹配近似算法“ FAQ”( Vogelstein, 2015) 的修改, 将其线性总运步替换为“ Lightspeace Opptimal Transport” 方法 。 修改提供了速度和实证匹配准确性两方面的改进。 该方法的有效性表现在模拟和真实数据示例中的匹配图形中。
相关内容
微信扫码咨询专知VIP会员