Subgraph Matching On Massive Social Graphs

Graph is a kind of representation formalism of structured data based on vertices and edges. Compared with traditional form of database tables, it is very flexible, visualized and expressive. In recent years, social media like Twitter, Facebook, Micro-blog, and WeChat produces massive scale of social graph data. How to handle large scale graph data becomes a crucial research problem. Subgraph matching problem is a very basic and important problem. Both searching and pattern mining on graphs are based on efficient graph matching algorithms.Subgraph matching problem is an NP-hard problem, and previous research gives some pure algorithmic solutions, however, they cannot handle graphs large than 100,000 vertices. Other works tried to solve this problem by building kinds of indices requiring super-linear indexing time or super-linear indexing space. Unfortunately, those super-linear indexing methods are not feasible when graph data is as large as a real social graph.Distribute graph databases make storing and manipulating large scale graph data a reality. In this paper, depending on the work of Trinity which is a distributed graph database designed by Microsoft Research Aisa(MSRA), we study the subgraph matching problem, present an efficient subgraph matching algorithm using graph exploration and massive parallel computing technology. We demonstrate the correctness, completeness and non-repeatability of our algorithm. Experimental results show that our algorithm has quick response time and good scalability, indicating the feasibility of subgraph matching on large-scale graph.