Parallel Subgraph Matching on Massive Graphs

While numerous applications, such as social networks, protein-protein interaction networks, and bibliographic networks, mainly consist of graph-structured data, massive graphs, of which the scales range from million nodes to billion nodes, are common-place. Searching within these kinds of graphs is urged to be efficient. Unfortunately, since the subgraph isomorphism problem is NP-complete, querying on large graphs is still challenging. Most of existing approaches employ various pruning rules to facilitate the matching process on a single machine. When a data graph is large and dense, auxiliary information, known as index, and intermediate results could easily run out of computational resources. Recently, inspired by the popularity of parallel programming models, such as MapReduce and Pregel, there is a trend to solve the subgraph matching problem upon them. However, caused by the incompleteness of graph data in each cluster machine, parallel solutions of subgraph matching are often proposed in a brute-force way. In this paper, we propose a parallel subgraph matching framework which uses k-hop replication based partitioning approach to distribute the graph data across cluster machines. Benefiting from the proposed framework, the completeness of local searching can be ensured. Hence, previous studies on indexing graph data become usable and valuable for the parallel graph querying problem. For the consideration of efficiency, taking a light-weight neighborhood-based index as an example, we also propose two potential optimization opportunities for reducing intermediate results. We implement the proposed framework on Hadoop/MapReduce. Our experimental results on real-world data sets demonstrate its effectiveness on very large graphs.