Parallel Counting of Subgraphs in Large Graphs: Pruning and Hierarchical Clustering Algorithms

As part of the 2018 MIT-Amazon Graph Challenge on subgraph isomorphism, we propose a novel joint hierarchical clustering and parallel counting framework called MEGA that can compute the exact number of triangles in large graphs. The MEGA framework consists of first pruning followed by hierarchical clustering based on geodesic distance and then triangle counting in parallel. This allows scalable software framework such as MapReduce/Hadoop to count triangles inside each cluster as well as those straddling between clusters in parallel. We characterize the performance of the MEGA framework mathematically, and its performance evaluation using representative graphs including random graphs demonstrates its computational efficiency over other existing techniques.