Recent Advances in Statistical Inference on Big Graph Data

• Activity Number: 258
• Type: Contributed
• Date/Time: Monday, August 10, 2015 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Li Chen* and Youngser Park and Carey E. Priebe
• Companies: Intel Corporation and The Johns Hopkins University and The Johns Hopkins University
• Keywords: Big graph data ; Vertex nomination ; Seeded graph matching ; Markov chain Monte Carlo ; Parallelization ; Scalability

Abstract

In this work, we discuss recent advances in scaling random graph inference methodologies to big graph data. In particular, we consider two random graph inferential tasks: vertex nomination and seeded graph matching. We present the recent effort in scaling the best possible vertex nomination scheme to large graphs via Markov Chain Monte Carlo, and parallelizing seeded graph matching for large graphs via a divide--and--conquer technique. We discuss the theoretical guarantees and the computational complexity of these scalable methods, and demonstrate their effectiveness via simulation and real data experiments.