A Weighted Common Subgraph Matching Algorithm
This incremental method addresses graph matching for computer vision and machine learning tasks, offering improved robustness in specific applications.
The authors tackled the problem of finding the most similar subgraphs in two labeled weighted graphs by proposing a weighted common subgraph (WCS) matching algorithm, which was validated experimentally to be robust against noise, problem size, outliers, and edge density.
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 the equal-sized graph matching or subgraph matching, finds wide applications in many computer vision and machine learning tasks. In this paper, the 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 (GNCCP). Experimental comparisons on both synthetic graphs and real world images validate its robustness against noise level, problem size, outlier number, and edge density.