U.S. Department of Energy

Pacific Northwest National Laboratory

Percolator: Scalable Pattern Discovery in Dynamic Graphs

Publish Date: 
Tuesday, February 6, 2018
We demonstrate Percolator, a distributed system for graph pattern discovery in dynamic graphs. In contrast to conventional mining systems, Percolator advocates efficient pattern mining schemes that (1) support pattern detection with keywords; (2) integrate incremental and parallel pattern mining; and (3) support analytical queries such as trend analysis. The core idea of Percolator is to dynamically decide and verify a small fraction of patterns and their in- stances that must be inspected in response to buffered updates in dynamic graphs, with a total mining cost independent of graph size. We demonstrate a) the feasibility of incremental pattern mining by walking through each component of Percolator, b) the efficiency and scalability of Percolator over the sheer size of real-world dynamic graphs, and c) how the user-friendly GUI of Percolator inter- acts with users to support keyword-based queries that detect, browse and inspect trending patterns. We also demonstrate two user cases of Percolator, in social media trend analysis and academic collaboration analysis, respectively.
Choudhury S., S. Purohit, P. Lin, Y. Wu, L.B. Holder, and K. Agarwal. 2018. "Percolator: Scalable Pattern Discovery in Dynamic Graphs." In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining (WSDM 2018), February 5-9, 2018, Los Angeles, California, 759-762. New York, New York:ACM. PNNL-SA-128916. doi:10.1145/3159652.3160589
| Pacific Northwest National Laboratory