Copyright Notice:

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Publications of SPCL

M. Besta, C. Miglioli, P. Sylos Labini, J. Tětek, P. Iff, R. Kanakagiri, S. Ashkboos, K. Janda, M. Podstawski, G. Kwasniewski, N. Gleinig, F. Vella, O. Mutlu, T. Hoefler:

 ProbGraph: High-Performance and High-Accuracy Graph Mining with Probabilistic Set Representations

(In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC'22), Nov. 2022)
SC22 Best Paper (1/82)

Abstract

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.

Documents

download article:
access preprint on arxiv:
download slides:
 

BibTeX

@inproceedings{,
  author={Maciej Besta and Cesare Miglioli and Paolo Sylos Labini and Jakub Tětek and Patrick Iff and Raghavendra Kanakagiri and Saleh Ashkboos and Kacper Janda and Michal Podstawski and Grzegorz Kwasniewski and Niels Gleinig and Flavio Vella and Onur Mutlu and Torsten Hoefler},
  title={{ProbGraph: High-Performance and High-Accuracy Graph Mining with Probabilistic Set Representations}},
  year={2022},
  month={11},
  booktitle={Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC'22)},
  doi={https://doi.org/10.48550/arXiv.2208.11469},
}