论文标题
通过嵌入密集图匹配
Matching through Embedding in Dense Graphs
论文作者
论文摘要
在密集图中找到最佳匹配是在社会，运输和生物网络中具有一般兴趣，尤其重要的。虽然为各种匹配问题开发最佳解决方案很重要，但是最快的最佳匹配算法的运行时间太昂贵了。但是，当图形的顶点是$ r^d $和边缘权重与欧几里得距离相对应的点时，可用的最佳匹配算法的速度要快得多。在本文中，我们提出了一种新型的基于网络嵌入的启发式算法，以解决密集图中的各种匹配问题。特别是，使用现有的网络嵌入技术，我们首先在$ r^d $中找到图形顶点的低维表示，然后在嵌入式顶点上运行更快的可用可用匹配算法。据我们所知，这是第一个应用网络嵌入以解决各种匹配问题的工作。实验结果证明了我们提出的算法的功效。
Finding optimal matchings in dense graphs is of general interest and of particular importance in social, transportation and biological networks. While developing optimal solutions for various matching problems is important, the running times of the fastest available optimal matching algorithms are too costly. However, when the vertices of the graphs are point-sets in $R^d$ and edge weights correspond to the euclidean distances, the available optimal matching algorithms are substantially faster. In this paper, we propose a novel network embedding based heuristic algorithm to solve various matching problems in dense graphs. In particular, using existing network embedding techniques, we first find a low dimensional representation of the graph vertices in $R^d$ and then run faster available matching algorithms on the embedded vertices. To the best of our knowledge, this is the first work that applies network embedding to solve various matching problems. Experimental results validate the efficacy of our proposed algorithm.
