|
Abstract:
|
The graph matching problem seeks to find the vertex correspondence between two observed graphs that best preserves the topological structure and has applications in the de-anonymization of social networks, PPI networks alignment in bioinformatics, and pattern recognition. We propose a mutual nearest neighbor graph matching algorithm that starts with a partial correspondence between a subset of node pairs allowing for noise. Our algorithm corrects erroneous matches and expands the match to the rest of the graphs. The intuition here is that a pair of nodes that have the most matched neighboring pairs among all the other candidates for both nodes is a promising match. Under a flexible model for correlated random graphs, we provide assumptions on the graph structure and the initial match for accomplishing self-correction and conditions for achieving high precision. Our approach is fast and scalable to matching very large graphs and the time complexity for each iteration is O(n^2). Lastly, we demonstrate the effectiveness of our algorithm in matching large-scale graphs in terms of both accuracy and running time using synthesized and real data experiments.
|
