  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.
