Growing a graph matching from a handful of seeds
Authors:
Open Access
- 1 June 2015
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 8 (10) , 1010-1021
Abstract
In many graph--mining problems, two networks from different domains have to be matched. In the absence of reliable node attributes, graph matching has to rely on only the link structures of the two networks, which amounts to a generalization of the classic graph isomorphism problem. Graph matching has applications in social--network reconciliation and de-anonymization, protein--network alignment in biology, and computer vision. The most scalable graph--matching approaches use ideas from percolation theory, where a matched node pair "infects" neighbouring pairs as additional potential matches. This class of matching algorithm requires an initial seed set of known matches to start the percolation. The size and correctness of the matching is very sensitive to the size of the seed set. In this paper, we give a new graph--matching algorithm that can operate with a much smaller seed set than previous approaches, with only a small increase in matching errors. We characterize a phase transition in matching performance as a function of the seed set size, using a random bigraph model and ideas from bootstrap percolation theory. We also show the excellent performance in matching several real large-scale social networks, using only a handful of seeds.Keywords
This publication has 22 references indexed in Scilit:
- Bootstrap percolation on the random graph $G_{n,p}$The Annals of Applied Probability, 2012
- Wherefore art thou R3579X?Communications of the ACM, 2011
- Adaptive least squares support vector machines filter for hand tremor canceling in microsurgeryInternational Journal of Machine Learning and Cybernetics, 2011
- Interweaving Public User Profiles on the Web2010
- A new graph-based method for pairwise global network alignmentBMC Bioinformatics, 2009
- Global alignment of multiple protein interaction networks with application to functional orthology detectionProceedings of the National Academy of Sciences, 2008
- The Diameter of a Scale-Free Random GraphCombinatorica, 2004
- Connected Components in Random Graphs with Given Expected Degree SequencesAnnals of Combinatorics, 2002
- Face recognition by elastic bunch graph matchingIEEE Transactions on Pattern Analysis and Machine Intelligence, 1997
- Random Graph IsomorphismSIAM Journal on Computing, 1980