(Nearly) efficient algorithms for the graph matching problem on correlated random graphs
December 2019
Article No.: 824, Pages 9190 - 9198
Abstract
We consider the graph matching/similarity problem of determining how similar two given graphs G0, G1 are and recovering the permutation n on the vertices of G1 that minimizes the symmetric difference between the edges of G0 and π(G1). Graph matching/similarity has applications for pattern matching, computer vision, social network anonymization, malware analysis, and more. We give the first efficient algorithms proven to succeed in the correlated Erdös-Rényi model (Pedarsani and Grossglauser, 2011). Specifically, we give a polynomial time algorithm for the graph similarity/hypothesis testing task which works for every constant level of correlation between the two graphs that can be arbitrarily close to zero. We also give a quasi-polynomial (nO(log n) time) algorithm for the graph matching task of recovering the permutation minimizing the symmetric difference in this model. This is the first algorithm to do so without requiring as additional input a "seed" of the values of the ground truth permutation on at least nΩ(1) vertices. Our algorithms follow a general framework of counting the occurrences of subgraphs from a particular family of graphs allowing for tradeoffs between efficiency and accuracy.
References
[1]
Timothee Cour, Praveen Srinivasan, and Jianbo Shi. Balanced graph matching. In Advances in Neural Information Processing Systems, pages 313-320, 2007.
[2]
Minsu Cho and Kyoung Mu Lee. Progressive graph matching: Making a move of graphs via probabilistic voting. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on, pages 398-405. IEEE, 2012.
[3]
Alexander C Berg, Tamara L Berg, and Jitendra Malik. Shape matching and object recognition using low distortion correspondences. In Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, volume 1, pages 26-33. IEEE, 2005.
[4]
Rohit Singh, Jinbo Xu, and Bonnie Berger. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Sciences, 105(35):12763-12768, 2008.
[5]
Joshua T Vogelstein, John M Conroy, Louis J Podrazik, Steven G Kratzer, Eric T Harley, Donniell E Fishkind, R Jacob Vogelstein, and Carey E Priebe. Large (brain) graph matching via fast approximate quadratic programming. arXiv preprint arXiv:1112.5507, 2011.
[6]
Nitish Korula and Silvio Lattanzi. An efficient reconciliation algorithm for social networks. Proceedings of the VLDB Endowment, 7(5):377-388, 2014.
[7]
Arvind Narayanan and Vitaly Shmatikov. De-anonymizing social networks. In Security and Privacy 2009 30th IEEE Symposium on, pages 173-187. IEEE, 2009.
[8]
Younghee Park, Douglas Reeves, Vikram Mulukutla, and Balaji Sundaravel. Fast malware classification by automated behavioral graph matching. In Proceedings of the Sixth Annual Workshop on Cyber Security and Information Intelligence Research, CSIIRW '10, pages 45:1-45:4, New York, NY, USA, 2010. ACM.
[9]
Lorenzo Livi and Antonello Rizzi. The graph matching problem. Pattern Analysis and Applications, 16(3):253-283, 2013.
[10]
Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento. Thirty years of graph matching in pattern recognition. International journal of pattern recognition and artificial intelligence, 18(03):265-298, 2004.
[11]
Pedram Pedarsani and Matthias Grossglauser. On the privacy of anonymized networks. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1235-1243. ACM, 2011.
[12]
Lyudmila Yartseva and Matthias Grossglauser. On the performance of percolation graph matching. In Proceedings of the first ACM conference on Online social networks, pages 119-130. ACM, 2013.
[13]
Vince Lyzinski, Donniell E Fishkind, and Carey E Priebe. Seeded graph matching for correlated erdös-rényi graphs. Journal of Machine Learning Research, 15(1):3513-3540, 2014.
[14]
Ehsan Kazemi, S Hamed Hassani, and Matthias Grossglauser. Growing a graph matching from a handful of seeds. Proceedings of the VLDB Endowment, 8(10):1010-1021, 2015.
[15]
Daniel Cullina and Negar Kiyavash. Improved achievability and converse bounds for erdos-renyi graph matching. In ACM SIGMETRICS Performance Evaluation Review, volume 44, pages 63-72. ACM, 2016.
[16]
Daniel Cullina and Negar Kiyavash. Exact alignment recovery for correlated erdos renyi graphs. arXiv preprint arXiv:1711.06783, 2017.
[17]
Hugo Gascon, Fabian Yamaguchi, Daniel Arp, and Konrad Rieck. Structural detection of android malware using embedded call graphs. In Proceedings of the 2013 ACM workshop on Artificial intelligence and security, pages 45-54. ACM, 2013.
[18]
Neha Runwal, Richard M Low, and Mark Stamp. Opcode graph similarity and metamorphic detection. Journal in Computer Virology, 8(1-2):37-52, 2012.
[19]
John W Raymond, Eleanor J Gardiner, and Peter Willett. Heuristics for similarity searching of chemical graphs using a maximum common edge subgraph algorithm. Journal of chemical information and computer sciences, 42(2):305-316, 2002.
[20]
Masahiro Hattori, Yasushi Okuno, Susumu Goto, and Minoru Kanehisa. Heuristics for chemical compound matching. Genome Informatics, 14:144-153, 2003.
[21]
Maureen Heymans and Ambuj K Singh. Deriving phylogenetic trees from the similarity analysis of metabolic pathways. Bioinformatics, 19(suppl_1):i138-i146, 2003.
[22]
V. Lyzinski, D. E. Fishkind, M. Fiori, J. T. Vogelstein, C. E. Priebe, and G. Sapiro. Graph matching: Relax at your own risk. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(1):60-73, Jan 2016.
[23]
Jon M Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM), 46(5):604-632, 1999.
[24]
Sergey Melnik, Hector Garcia-Molina, and Erhard Rahm. Similarity flooding: A versatile graph matching algorithm and its application to schema matching. In Proceedings 18th International Conference on Data Engineering, pages 117-128. IEEE, 2002.
[25]
Elizabeth A Leicht, Petter Holme, and Mark EJ Newman. Vertex similarity in networks. Physical Review E, 73(2):026120, 2006.
[26]
Laura A Zager and George C Verghese. Graph similarity scoring and matching. Applied mathematics letters, 21(1):86-94, 2008.
[27]
Yunsheng Bai, Hao Ding, Yizhou Sun, and Wei Wang. Convolutional set matching for graph similarity. arXiv preprint arXiv:1810.10866, 2018.
[28]
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, WSDM '19, pages 384-392, New York, NY, USA, 2019. ACM.
[29]
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826, 2018.
[30]
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016.
[31]
Béla Bollobás. Random graphs. pages 80-102. Cambridge University Press, 1981.
[32]
Vince Lyzinski, Sancar Adali, Joshua T Vogelstein, Youngser Park, and Carey E Priebe. Seeded graph matching via joint optimization of fidelity and commensurability. arXiv preprint arXiv:1401.3813, 2014.
[33]
Svante Janson, Tomasz Luczak, Tatyana Turova, Thomas Vallier, et al. Bootstrap percolation on the random graph gn,p. The Annals of Applied Probability, 22(5):1989-2047, 2012.
Index Terms
- (Nearly) efficient algorithms for the graph matching problem on correlated random graphs
Index terms have been assigned to the content through auto-classification.
Recommendations
Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs
The Induced Graph Matching problem asks to find $$k$$ k disjoint induced subgraphs isomorphic to a given graph $$H$$ H in a given graph $$G$$ G such that there are no edges between vertices of different subgraphs. This problem generalizes the classical Independent Set and ...
Efficient algorithms for Roman domination on some classes of graphs
A Roman dominating function of a graph G=(V,E) is a function f:V->{0,1,2} such that every vertex x with f(x)=0 is adjacent to at least one vertex y with f(y)=2. The weight of a Roman dominating function is defined to be f(V)=@?"x"@?"Vf(x), and the ...
On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
Clique separators in graphs are a helpful tool used by Tarjan as a divide-and-conquer approach for solving various graph problems such as the Maximum Weight Stable Set (MWS) Problem, Maximum Clique, Graph Coloring and Minimum Fill-in, but few examples ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 2019
15947 pages
Copyright © 2019 Neural Information Processing Systems Foundation, Inc.
In-Cooperation
Publisher
Curran Associates Inc.
Red Hook, NY, United States
Publication History
Published: 08 December 2019
Qualifiers
- Chapter
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 40Total Downloads
- Downloads (Last 12 months)30
- Downloads (Last 6 weeks)8
Reflects downloads up to 25 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in