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, Z. Vonarburg-Shmaria, Y. Schaffner, L. Schwarz, G. Kwasniewski, L. Gianinazzi, J. Beranek, K. Janda, T. Holenstein, S. Leisinger, P. Tatkowski, E. Ozdemir, A. Balla, M. Copik, P. Lindenberger, P. Kalvoda, M. Konieczny, O. Mutlu, T. Hoefler:

 GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra

(In Proceedings of the 47th International Conference on Very Large Data Bases (VLDB'21), Aug. 2021)

Abstract

We propose GraphMineSuite (GMS): the first benchmarking suite for graph mining that facilitates evaluating and constructing high-performance graph mining algorithms. First, GMS comes with a benchmark specification based on extensive literature review, prescribing representative problems, algorithms, and datasets. Second, GMS offers a carefully designed software platform for seamless testing of different fine-grained elements of graph mining algorithms, such as graph representations or algorithm subroutines. The platform includes parallel implementations of more than 40 considered baselines, and it facilitates developing complex and fast mining algorithms. High modularity is possible by harnessing set algebra operations such as set intersection and difference, which enables breaking complex graph mining algorithms into simple building blocks that can be separately experimented with. GMS is supported with a broad concurrency analysis for portability in performance insights, and a novel performance metric to assess the throughput of graph mining algorithms, enabling more insightful evaluation. As use cases, we harness GMS to rapidly redesign and accelerate state-of-the-art baselines of core graph mining problems: degeneracy reordering (by up to >2x), maximal clique listing (by up to >9x), k-clique listing (by 1.1x), and subgraph isomorphism (by up to 2.5x), also obtaining better theoretical performance bounds.

Documents

download article:
access preprint on arxiv:
download slides:
 

BibTeX

@inproceedings{,
  author={Maciej Besta and Zur Vonarburg-Shmaria and Yannick Schaffner and Leonardo Schwarz and Grzegorz Kwasniewski and Lukas Gianinazzi and Jakub Beranek and Kacper Janda and Tobias Holenstein and Sebastian Leisinger and Peter Tatkowski and Esref Ozdemir and Adrian Balla and Marcin Copik and Philipp Lindenberger and Pavel Kalvoda and Marek Konieczny and Onur Mutlu and Torsten Hoefler},
  title={{GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra}},
  year={2021},
  month={08},
  booktitle={Proceedings of the 47th International Conference on Very Large Data Bases (VLDB'21)},
}