Yang Xu, Qiao Hong, Liu Zhi-Yong
IEEE Trans Neural Netw Learn Syst. 2018 Jul;29(7):3295-3300. doi: 10.1109/TNNLS.2017.2712794. Epub 2017 Jul 4.
We propose a weighted common subgraph (WCS) matching algorithm to find the most similar subgraphs in two labeled weighted graphs. WCS matching, as a natural generalization of equal-sized graph matching and subgraph matching, has found wide applications in many computer vision and machine learning tasks. In this brief, WCS matching is first formulated as a combinatorial optimization problem over the set of partial permutation matrices. Then, it is approximately solved by a recently proposed combinatorial optimization framework-graduated nonconvexity and concavity procedure. Experimental comparisons on both synthetic graphs and real-world images validate its robustness against noise level, problem size, outlier number, and edge density.
我们提出了一种加权公共子图（WCS）匹配算法，用于在两个带标签的加权图中找到最相似的子图。WCS匹配作为等规模图匹配和子图匹配的自然推广，已在许多计算机视觉和机器学习任务中得到广泛应用。在本简报中，WCS匹配首先被表述为部分置换矩阵集合上的组合优化问题。然后，通过最近提出的组合优化框架——梯度非凸性和凹性过程对其进行近似求解。在合成图和真实世界图像上的实验比较验证了其在噪声水平、问题规模、异常值数量和边密度方面的鲁棒性。
