ProbGraph: High-Performance and High-Accuracy Graph Mining with Probabilistic Set Representations
| Autor: | Maciej Besta, Cesare Miglioli, Paolo Sylos Labini, Jakub Tětek, Patrick Iff, Raghavendra Kanakagiri, Saleh Ashkboos, Kacper Janda, Michał Podstawski, Grzegorz Kwaśniewski, Niels Gleinig, Flavio Vella, Onur Mutlu, Torsten Hoefler |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
K Minimum Values Graph Sketching Computer Science - Distributed Parallel and Cluster Computing Approximate Graph Mining Approximate Triangle Counting High-Performance Graph Computations Computer Science - Data Structures and Algorithms Approximate Community Detection MinHash Data Structures and Algorithms (cs.DS) Distributed Parallel and Cluster Computing (cs.DC) Approximate Graph Clustering Approximate Graph Pattern Matching Bloom Filters |
| Zdroj: | Besta, M, Miglioli, C, Labini, P S, Tetek, J, Iff, P, Kanakagiri, R, Ashkboos, S, Janda, K, Podstawski, M, Kwasniewski, G, Gleinig, N, Vella, F, Mutlu, O & Hoefler, T 2022, ProbGraph : High-Performance and High-Accuracy Graph Mining with Probabilistic Set Representations . in Proceedings of SC 2022 : International Conference for High Performance Computing, Networking, Storage and Analysis . IEEE, International Conference for High Performance Computing, Networking, Storage and Analysis, SC, vol. 2022-November, pp. 1-17, 2022 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2022, Dallas, United States, 13/11/2022 . https://doi.org/10.1109/SC41404.2022.00048 |
| DOI: | 10.48550/arxiv.2208.11469 |
| Popis: | Important graph mining problems such as Clustering are computationally demanding. To significantly accelerate these problems, we propose ProbGraph: a graph representation that enables simple and fast approximate parallel graph mining with strong theoretical guarantees on work, depth, and result accuracy. The key idea is to represent sets of vertices using probabilistic set representations such as Bloom filters. These representations are much faster to process than the original vertex sets thanks to vectorizability and small size. We use these representations as building blocks in important parallel graph mining algorithms such as Clique Counting or Clustering. When enhanced with ProbGraph, these algorithms significantly outperform tuned parallel exact baselines (up to nearly 50x on 32 cores) while ensuring accuracy of more than 90% for many input graph datasets. Our novel bounds and algorithms based on probabilistic set representations with desirable statistical properties are of separate interest for the data analytics community. Comment: Best Paper Award at ACM/IEEE Supercomputing'22 (SC22) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|