Growing a graph matching from a handful of seeds

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.

References

1. F. Abel, N. Henze, E. Herder, and D. Krause. Interweaving Public User Profiles on the Web. In UMAP, HI, USA, pages 16--27, September 2010.
2. L. Babai, P. Erdös, and S. M. Selkow. Random Graph Isomorphism. SIAM J. Comput., 9(3):628--635, 1980.
3. L. Backstrom, C. Dwork, and J. M. Kleinberg. Wherefore art thou R3579X?: Anonymized Social Networks, Hidden Patterns, and Structural Steganography. Commun. ACM, 54(12):133--141, 2011.
4. A.-L. Barabási and R. Albert. Emergence of Scaling in Random Networks. science, 286(5439):509--512, 1999.
5. B. Bollobás and O. Riordan. The Diameter of a Scale-Free Random Graph. Combinatorica, 24(1):5--34, 2004.
6. F. Chung and L. Lu. Connected Components in Random Graphs with Given Expected Degree Sequences. Annals of Combinatorics, 6(2):125--145, 2002.
7. A. Egozi, Y. Keller, and H. Guterman. A Probabilistic Approach to Spectral Graph Matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(1):18--27, 2013.
8. P. Erdös and A. Rényi. On random graphs I. Publ. Math. Debrecen, 6:290--297, 1959.
9. M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990.
10. K. Henderson, B. Gallagher, L. Li, L. Akoglu, T. Eliassi-Rad, H. Tong, and C. Faloutsos. It's Who You Know: Graph Mining Using Recursive Structural Features. In SIGKDD, San Diego, CA, USA, pages 663--671, August 2011.
11. S. Janson, T. Luczak, T. Turova, and T. Vallier. Bootstrap Percolation On The Random Graph G_n,p. The Annals of Applied Probability, 22(5):1989--2047, 2012.
12. R. M. Karp, C. Schindelhauer, S. Shenker, and B. Vöcking. Randomized Rumor Spreading. In FOCS, Redondo Beach, California, USA, pages 565--574, November 2000.
13. G. Klau. A New Graph--Based Method for Pairwise Global Network Alignment. BMC Bioinformatics, 10(Suppl 1):S59, 2009.
14. N. Korula and S. Lattanzi. An Efficient Reconciliation Algorithm for Social Networks. PVLDB, 7(5):377--388, 2014.
15. J. Leskovec. Stanford Network Analysis Project. http://snap.stanford.edu/index.html.
16. A. Malhotra, L. C. Totti, W. M. Jr., P. Kumaraguru, and V. Almeida. Studying User Footprints in Different Online Social Networks. In ASONAM, Istanbul, Turkey, pages 1065--1070, August 2012.
17. S. Melnik, H. Garcia-Molina, and E. Rahm. Similarity Flooding: A Versatile Graph Matching Algorithm and Its Application to Schema Matching. In ICDE, San Jose, CA, USA, pages 117--128, 2002.
18. A. Mislove, B. Viswanath, P. K. Gummadi, and P. Druschel. You Are Who You Know: Inferring User Profiles in Online Social Networks. In WSDM, New York, NY, USA, pages 251--260, February 2010.
19. A. Narayanan and V. Shmatikov. De-anonymizing Social Networks. In S&P, Oakland, California, USA, pages 173--187, May 2009.
20. A. Nunes, P. Calado, and B. Martins. Resolving User Identities Over Social Networks Through Supervised Learning and Rich Similarity Features. In SAC, Riva, Trento, Italy, pages 728--729, March 2012.
21. P. Pedarsani, D. R. Figueiredo, and M. Grossglauser. A Bayesian Method for Matching Two Similar Graphs without Seeds. In Conference on Communication, Control, and Computing, Allerton Park, Monticello, IL, USA, pages 1598--1607, October 2013.
22. P. Pedarsani and M. Grossglauser. On the Privacy of Anonymized Networks. In SIGKDD, San Diego, CA, USA, pages 1235--1243, August 2011.
23. D. M. Powers. Evaluation: from Precision, Recall and F-measure to ROC, Informedness, Markedness and Correlation. Journal of Machine Learning Technologies, 2(1):37--63, 2011.
24. D. Shah. Gossip Algorithms. Now Publishers Inc, 2009.
25. R. Singh, J. Xu, and B. Berger. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Sciences, (35):12763--12768.
26. L. Torresani, V. Kolmogorov, and C. Rother. Feature Correspondence Via Graph Matching: Models and Global Optimization. In ECCV, Marseille, France, pages 596--609, October 2008.
27. B. Von Bahr and A. Martin-Löf. Threshold Limit Theorems for Some Epidemic Processes. Advances in Applied Probability, pages 319--349, 1980.
28. L. Wiskott, J.-M. Fellous, N. Kuiger, and C. Von Der Malsburg. Face Recognition by Elastic Bunch Braph Matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(7):775--779, 1997.
29. G. Wondracek, T. Holz, E. Kirda, and C. Kruegel. A practical attack to de-anonymize social network users. In S&P, Berleley/Oakland, California, USA, pages 223--238, May 2010.
30. L. Yartseva and M. Grossglauser. On the performance of percolation graph matching. In COSN, Boston, MA, USA, pages 119--130, October 2013.

Index Terms

• Computing methodologies

  • Machine learning

• Information systems

  • Data management systems

    • Database management system engines

• Mathematics of computing

  • Discrete mathematics

    • Graph theory