Towards Fast and Scalable Graph Pattern Mining

Authors: 

Anand Padmanabha Iyer, UC Berkeley; Zaoxing Liu and Xin Jin, JHU; Shivaram Venkataraman, Microsoft Research / University of Wisconsin; Vladimir Braverman, JHU; Ion Stoica, UC Berkeley

Abstract: 

While there has been a tremendous interest in processing graph-structured data, existing distributed graph processing systems take several minutes or even hours to mine simple patterns on graphs. In this paper, we try to answer the question of whether it is possible to build a graph pattern mining engine that is both fast and scalable. Leveraging the observation that in several pattern mining tasks, providing an approximate answer is good enough, we propose the use of approximation for graph pattern mining. However, we find that existing approximation techniques do not work for this purpose. Based on this, we present a new approach for approximate graph pattern mining that leverages recent advancements in graph approximation theory. Our preliminary evaluations show encouraging results: compared to state-of-the-art, finding 3-motifs in Twitter graph is 165× faster while incurring only 5% error. We conclude by discussing several systems challenges to make our proposal practical.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {216857,
author = {Anand Padmanabha Iyer and Zaoxing Liu and Xin Jin and Shivaram Venkataraman and Vladimir Braverman and Ion Stoica},
title = {Towards Fast and Scalable Graph Pattern Mining},
booktitle = {10th {USENIX} Workshop on Hot Topics in Cloud Computing (HotCloud 18)},
year = {2018},
address = {Boston, MA},
url = {https://www.usenix.org/conference/hotcloud18/presentation/iyer-pattern},
publisher = {{USENIX} Association},
}