Scaling betweenness centrality using communication-efficient sparse matrix multiplication

Edgar Vadimovich Solomonik, Maciej Besta, Flavio Vella, Torsten Hoefler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Betweenness centrality (BC) is a crucial graph problem that measures the significance of a vertex by the number of shortest paths leading through it. We propose Maximal Frontier Betweenness Cen-trality (MFBC): a succinct BC algorithm based on novel sparse matrix multiplication routines that performs a factor of p1/3 less communication on p processors than the best known alternatives, for graphs withn vertices and average degreek = n/p2/3. Weformulate, implement, and prove the correctness of MFBC for weighted graphs by leveraging monoids instead of semirings, which enables a surprisingly succinct formulation. MFBC scales well for both extremely sparse and relatively dense graphs. It automatically searches a space of distributed data decompositions and sparse matrix multiplication algorithms for the most advantageous configuration. The MFBC implementation outperforms the well-known CombBLAS library by up to 8x and shows more robust performance. Our design methodology is readily extensible to other graph problems.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450351140
DOIs
StatePublished - Nov 12 2017
EventInternational Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017 - Denver, United States
Duration: Nov 12 2017Nov 17 2017

Publication series

NameProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017

Other

OtherInternational Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017
CountryUnited States
CityDenver
Period11/12/1711/17/17

Fingerprint

Communication
Decomposition

Keywords

  • Betweenness centrality
  • Communication cost
  • Parallel algorithm
  • Sparse matrix multiplication

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software

Cite this

Solomonik, E. V., Besta, M., Vella, F., & Hoefler, T. (2017). Scaling betweenness centrality using communication-efficient sparse matrix multiplication. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017 [47] (Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017). Association for Computing Machinery, Inc. https://doi.org/10.1145/3126908.3126971

Scaling betweenness centrality using communication-efficient sparse matrix multiplication. / Solomonik, Edgar Vadimovich; Besta, Maciej; Vella, Flavio; Hoefler, Torsten.

Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017. Association for Computing Machinery, Inc, 2017. 47 (Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Solomonik, EV, Besta, M, Vella, F & Hoefler, T 2017, Scaling betweenness centrality using communication-efficient sparse matrix multiplication. in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017., 47, Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017, Association for Computing Machinery, Inc, International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017, Denver, United States, 11/12/17. https://doi.org/10.1145/3126908.3126971
Solomonik EV, Besta M, Vella F, Hoefler T. Scaling betweenness centrality using communication-efficient sparse matrix multiplication. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017. Association for Computing Machinery, Inc. 2017. 47. (Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017). https://doi.org/10.1145/3126908.3126971
Solomonik, Edgar Vadimovich ; Besta, Maciej ; Vella, Flavio ; Hoefler, Torsten. / Scaling betweenness centrality using communication-efficient sparse matrix multiplication. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017. Association for Computing Machinery, Inc, 2017. (Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017).
@inproceedings{d5c33085c83a49c9b286fca69dc6ab25,
title = "Scaling betweenness centrality using communication-efficient sparse matrix multiplication",
abstract = "Betweenness centrality (BC) is a crucial graph problem that measures the significance of a vertex by the number of shortest paths leading through it. We propose Maximal Frontier Betweenness Cen-trality (MFBC): a succinct BC algorithm based on novel sparse matrix multiplication routines that performs a factor of p1/3 less communication on p processors than the best known alternatives, for graphs withn vertices and average degreek = n/p2/3. Weformulate, implement, and prove the correctness of MFBC for weighted graphs by leveraging monoids instead of semirings, which enables a surprisingly succinct formulation. MFBC scales well for both extremely sparse and relatively dense graphs. It automatically searches a space of distributed data decompositions and sparse matrix multiplication algorithms for the most advantageous configuration. The MFBC implementation outperforms the well-known CombBLAS library by up to 8x and shows more robust performance. Our design methodology is readily extensible to other graph problems.",
keywords = "Betweenness centrality, Communication cost, Parallel algorithm, Sparse matrix multiplication",
author = "Solomonik, {Edgar Vadimovich} and Maciej Besta and Flavio Vella and Torsten Hoefler",
year = "2017",
month = "11",
day = "12",
doi = "10.1145/3126908.3126971",
language = "English (US)",
series = "Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017",
publisher = "Association for Computing Machinery, Inc",
booktitle = "Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017",

}

TY - GEN

T1 - Scaling betweenness centrality using communication-efficient sparse matrix multiplication

AU - Solomonik, Edgar Vadimovich

AU - Besta, Maciej

AU - Vella, Flavio

AU - Hoefler, Torsten

PY - 2017/11/12

Y1 - 2017/11/12

N2 - Betweenness centrality (BC) is a crucial graph problem that measures the significance of a vertex by the number of shortest paths leading through it. We propose Maximal Frontier Betweenness Cen-trality (MFBC): a succinct BC algorithm based on novel sparse matrix multiplication routines that performs a factor of p1/3 less communication on p processors than the best known alternatives, for graphs withn vertices and average degreek = n/p2/3. Weformulate, implement, and prove the correctness of MFBC for weighted graphs by leveraging monoids instead of semirings, which enables a surprisingly succinct formulation. MFBC scales well for both extremely sparse and relatively dense graphs. It automatically searches a space of distributed data decompositions and sparse matrix multiplication algorithms for the most advantageous configuration. The MFBC implementation outperforms the well-known CombBLAS library by up to 8x and shows more robust performance. Our design methodology is readily extensible to other graph problems.

AB - Betweenness centrality (BC) is a crucial graph problem that measures the significance of a vertex by the number of shortest paths leading through it. We propose Maximal Frontier Betweenness Cen-trality (MFBC): a succinct BC algorithm based on novel sparse matrix multiplication routines that performs a factor of p1/3 less communication on p processors than the best known alternatives, for graphs withn vertices and average degreek = n/p2/3. Weformulate, implement, and prove the correctness of MFBC for weighted graphs by leveraging monoids instead of semirings, which enables a surprisingly succinct formulation. MFBC scales well for both extremely sparse and relatively dense graphs. It automatically searches a space of distributed data decompositions and sparse matrix multiplication algorithms for the most advantageous configuration. The MFBC implementation outperforms the well-known CombBLAS library by up to 8x and shows more robust performance. Our design methodology is readily extensible to other graph problems.

KW - Betweenness centrality

KW - Communication cost

KW - Parallel algorithm

KW - Sparse matrix multiplication

UR - http://www.scopus.com/inward/record.url?scp=85040162024&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85040162024&partnerID=8YFLogxK

U2 - 10.1145/3126908.3126971

DO - 10.1145/3126908.3126971

M3 - Conference contribution

AN - SCOPUS:85040162024

T3 - Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017

BT - Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017

PB - Association for Computing Machinery, Inc

ER -