ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph

Ehab Abdelhamid; Ibrahim Abdelaziz; Panos Kalnis; Zuhair Khayyat; Fuad Tarek Jamour

doi:10.1109/SC.2016.60

ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph

Ehab Abdelhamid, Ibrahim Abdelaziz, Panos Kalnis, Zuhair Khayyat, Fuad Tarek Jamour

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

71 Scopus citations

Abstract

Frequent Subgraph Mining is an essential operation for graph analytics and knowledge extraction. Due to its high computational cost, parallel solutions are necessary. Existing approaches either suffer from load imbalance, or high communication and synchronization overheads. In this paper we propose ScaleMine; a novel parallel frequent subgraph mining system for a single large graph. ScaleMine introduces a novel two-phase approach. The first phase is approximate; it quickly identifies subgraphs that are frequent with high probability, while collecting various statistics. The second phase computes the exact solution by employing the results of the approximation to achieve good load balance; prune the search space; generate efficient execution plans; and guide intra-task parallelism. Our experiments show that ScaleMine scales to 8,192 cores on a Cray XC40 (12× more than competitors); supports graphs with one billion edges (10× larger than competitors), and is at least an order of magnitude faster than existing solutions.

Original language	English (US)
Title of host publication	SC16: International Conference for High Performance Computing, Networking, Storage and Analysis
Subtitle of host publication	The International Conference for High Performance Computing, Networking, Storage and Analysis
Publisher	IEEE Computer Society
Pages	716-727
Number of pages	12
ISBN (Electronic)	9781467388153
ISBN (Print)	9781467388153
DOIs	https://doi.org/10.1109/SC.2016.60
State	Published - Mar 13 2017
Event	2016 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2016 - Salt Lake City, United States Duration: Nov 13 2016 → Nov 18 2016

Publication series

Name	International Conference for High Performance Computing, Networking, Storage and Analysis, SC
ISSN (Print)	2167-4329
ISSN (Electronic)	2167-4337

Other

Other	2016 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2016
Country/Territory	United States
City	Salt Lake City
Period	11/13/16 → 11/18/16

Bibliographical note

KAUST Repository Item: Exported on 2021-08-20
Acknowledgements: For computer time, this research used the resources of the Supercomputing Laboratory at King Abdullah University of Science & Technology (KAUST) in Thuwal, Saudi Arabia.

ASJC Scopus subject areas

Computer Networks and Communications
Computer Science Applications
Hardware and Architecture
Software

Access to Document

10.1109/SC.2016.60

Cite this

Abdelhamid, E., Abdelaziz, I., Kalnis, P., Khayyat, Z., & Jamour, F. T. (2017). ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph. In SC16: International Conference for High Performance Computing, Networking, Storage and Analysis: The International Conference for High Performance Computing, Networking, Storage and Analysis (pp. 716-727). Article 7877139 (International Conference for High Performance Computing, Networking, Storage and Analysis, SC). IEEE Computer Society. https://doi.org/10.1109/SC.2016.60

Abdelhamid, Ehab ; Abdelaziz, Ibrahim ; Kalnis, Panos et al. / ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph : Scalable Parallel Frequent Subgraph Mining in a Single Large Graph. SC16: International Conference for High Performance Computing, Networking, Storage and Analysis: The International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Computer Society, 2017. pp. 716-727 (International Conference for High Performance Computing, Networking, Storage and Analysis, SC).

@inproceedings{7a4718d9b4a940218407e3d408ddd647,

title = "ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph",

abstract = "Frequent Subgraph Mining is an essential operation for graph analytics and knowledge extraction. Due to its high computational cost, parallel solutions are necessary. Existing approaches either suffer from load imbalance, or high communication and synchronization overheads. In this paper we propose ScaleMine; a novel parallel frequent subgraph mining system for a single large graph. ScaleMine introduces a novel two-phase approach. The first phase is approximate; it quickly identifies subgraphs that are frequent with high probability, while collecting various statistics. The second phase computes the exact solution by employing the results of the approximation to achieve good load balance; prune the search space; generate efficient execution plans; and guide intra-task parallelism. Our experiments show that ScaleMine scales to 8,192 cores on a Cray XC40 (12× more than competitors); supports graphs with one billion edges (10× larger than competitors), and is at least an order of magnitude faster than existing solutions.",

author = "Ehab Abdelhamid and Ibrahim Abdelaziz and Panos Kalnis and Zuhair Khayyat and Jamour, {Fuad Tarek}",

note = "KAUST Repository Item: Exported on 2021-08-20 Acknowledgements: For computer time, this research used the resources of the Supercomputing Laboratory at King Abdullah University of Science & Technology (KAUST) in Thuwal, Saudi Arabia.; 2016 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2016 ; Conference date: 13-11-2016 Through 18-11-2016",

year = "2017",

month = mar,

day = "13",

doi = "10.1109/SC.2016.60",

language = "English (US)",

isbn = "9781467388153",

series = "International Conference for High Performance Computing, Networking, Storage and Analysis, SC",

publisher = "IEEE Computer Society",

pages = "716--727",

booktitle = "SC16: International Conference for High Performance Computing, Networking, Storage and Analysis",

address = "United States",

}

Abdelhamid, E, Abdelaziz, I, Kalnis, P, Khayyat, Z & Jamour, FT 2017, ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph. in SC16: International Conference for High Performance Computing, Networking, Storage and Analysis: The International Conference for High Performance Computing, Networking, Storage and Analysis., 7877139, International Conference for High Performance Computing, Networking, Storage and Analysis, SC, IEEE Computer Society, pp. 716-727, 2016 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2016, Salt Lake City, United States, 11/13/16. https://doi.org/10.1109/SC.2016.60

ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph. / Abdelhamid, Ehab; Abdelaziz, Ibrahim; Kalnis, Panos et al.
SC16: International Conference for High Performance Computing, Networking, Storage and Analysis: The International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Computer Society, 2017. p. 716-727 7877139 (International Conference for High Performance Computing, Networking, Storage and Analysis, SC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph

T2 - 2016 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2016

AU - Abdelhamid, Ehab

AU - Abdelaziz, Ibrahim

AU - Kalnis, Panos

AU - Khayyat, Zuhair

AU - Jamour, Fuad Tarek

N1 - KAUST Repository Item: Exported on 2021-08-20 Acknowledgements: For computer time, this research used the resources of the Supercomputing Laboratory at King Abdullah University of Science & Technology (KAUST) in Thuwal, Saudi Arabia.

PY - 2017/3/13

Y1 - 2017/3/13

N2 - Frequent Subgraph Mining is an essential operation for graph analytics and knowledge extraction. Due to its high computational cost, parallel solutions are necessary. Existing approaches either suffer from load imbalance, or high communication and synchronization overheads. In this paper we propose ScaleMine; a novel parallel frequent subgraph mining system for a single large graph. ScaleMine introduces a novel two-phase approach. The first phase is approximate; it quickly identifies subgraphs that are frequent with high probability, while collecting various statistics. The second phase computes the exact solution by employing the results of the approximation to achieve good load balance; prune the search space; generate efficient execution plans; and guide intra-task parallelism. Our experiments show that ScaleMine scales to 8,192 cores on a Cray XC40 (12× more than competitors); supports graphs with one billion edges (10× larger than competitors), and is at least an order of magnitude faster than existing solutions.

AB - Frequent Subgraph Mining is an essential operation for graph analytics and knowledge extraction. Due to its high computational cost, parallel solutions are necessary. Existing approaches either suffer from load imbalance, or high communication and synchronization overheads. In this paper we propose ScaleMine; a novel parallel frequent subgraph mining system for a single large graph. ScaleMine introduces a novel two-phase approach. The first phase is approximate; it quickly identifies subgraphs that are frequent with high probability, while collecting various statistics. The second phase computes the exact solution by employing the results of the approximation to achieve good load balance; prune the search space; generate efficient execution plans; and guide intra-task parallelism. Our experiments show that ScaleMine scales to 8,192 cores on a Cray XC40 (12× more than competitors); supports graphs with one billion edges (10× larger than competitors), and is at least an order of magnitude faster than existing solutions.

UR - http://hdl.handle.net/10754/670692

UR - http://ieeexplore.ieee.org/document/7877139/

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

U2 - 10.1109/SC.2016.60

DO - 10.1109/SC.2016.60

M3 - Conference contribution

SN - 9781467388153

T3 - International Conference for High Performance Computing, Networking, Storage and Analysis, SC

SP - 716

EP - 727

BT - SC16: International Conference for High Performance Computing, Networking, Storage and Analysis

PB - IEEE Computer Society

Y2 - 13 November 2016 through 18 November 2016

ER -

Abdelhamid E, Abdelaziz I, Kalnis P, Khayyat Z, Jamour FT. ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph. In SC16: International Conference for High Performance Computing, Networking, Storage and Analysis: The International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Computer Society. 2017. p. 716-727. 7877139. (International Conference for High Performance Computing, Networking, Storage and Analysis, SC). doi: 10.1109/SC.2016.60

ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph

Abstract

Publication series

Other

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this