A Novel Method for Graph Matching

Graph matching is a fundamental NP-hard problem in computer science. We propose an approximate graph matching method. To match the nodes of two graphs, our method first constructs an association graph. For each pair of nodes within the association graph, our method computes their mutual consistency on the basis of the distance information and angle information of the original graphs' nodes. The consistencies of all pairs of nodes form an affinity matrix. With the affinity matrix, our method then performs random walks on the association graph to achieve a stable quasi-stationary distribution. Discretizing the distribution on the basis of the Hungarian algorithm, our method finally obtains the matching between the nodes of the two original graphs. The experimental results demonstrate the effectiveness of our method on graph matching.