Graph Matching Via the Lens of Supermodularity
Graph Matching Via the Lens of Supermodularity
复制标题
DOI：
10.1109/tkde.2020.3008128
复制
发表时间：
2022-05
影响因子：
8.9
通讯作者：
Aritra Konar;N. Sidiropoulos
中科院分区：
文献类型：
--
作者：
Aritra Konar;N. Sidiropoulos
图形匹配是对准一对图的问题，以最大程度地减少其边缘分歧，由于其在数据科学中的广泛应用，因此受到了宽度的关注。已经提出了近似算法，以获得高质量的次优溶液。以前未经想的观点是，我们可以将图形匹配为最大化单调的超模块化设置功能，但要受到矩阵相交的约束。迭代构造的功能，并在每个步骤上最大化一系列全局下限。两分图中的问题与先前的方法区分，算法利用了问题中固有的组合结构，以生成一系列具有单调性非保证目标价值的迭代序列。该算法相对于现行的最新最先进的经验有效性。
Graph matching, the problem of aligning a pair of graphs so as to minimize their edge disagreements, has received widespread attention owing to its broad spectrum of applications in data science. As the problem is NP–hard in the worst-case, a variety of approximation algorithms have been proposed for obtaining high quality, suboptimal solutions. In this article, we approach the task of designing an efficient polynomial-time approximation algorithm for graph matching from a previously unconsidered perspective. Our key result is that graph matching can be formulated as maximizing a monotone, supermodular set function subject to matroid intersection constraints. We leverage this fact to apply a discrete optimization variant of the minorization-maximization algorithm which exploits supermodularity of the objective function to iteratively construct and maximize a sequence of global lower bounds on the objective. At each step, we solve a maximum weight matching problem in a bipartite graph. Differing from prior approaches, the algorithm exploits the combinatorial structure inherent in the problem to generate a sequence of iterates featuring monotonically non-decreasing objective value while always adhering to the combinatorial matching constraints. Experiments on real-world data demonstrate the empirical effectiveness of the algorithm relative to the prevailing state-of-the-art.