TY - JOUR
T1 - Scalable mining of maximal quasi-cliques
T2 - An algorithm-system codesign approach
AU - Guo, Guimu
AU - Yan, Da
AU - Özsu, M. Tamer
AU - Jiang, Zhe
AU - Khalil, Jalal
N1 - Publisher Copyright:
© VLDB Endowment. All rights reserved.
PY - 2020
Y1 - 2020
N2 - Given a user-specified minimum degree threshold γ, a γ-quasi-clique is a subgraph д = (Vд, Eд ) where each vertex v ∈ Vд connects to at least γ fraction of the other vertices (i.e., ⌈γ · (|Vд | − 1)⌉ vertices) in д. Quasi-clique is one of the most natural definitions for dense structures useful in finding communities in social networks and discovering significant biomolecule structures and pathways. However, mining maximal quasi-cliques is notoriously expensive. In this paper, we design parallel algorithms for mining maximal quasi-cliques on G-thinker, a distributed graph mining framework that decomposes mining into compute-intensive tasks to fully utilize CPU cores. We found that directly using G-thinker results in the straggler problem due to (i) the drastic load imbalance among different tasks and (ii) the difficulty of predicting the task running time. We address these challenges by redesigning G-thinker’s execution engine to prioritize long-running tasks for execution, and by utilizing a novel timeout strategy to effectively decompose long-running tasks to improve load balancing. While this system redesign applies to many other expensive dense subgraph mining problems, this paper verifies the idea by adapting the state-of-the-art quasi-clique algorithm, Quick, to our redesigned G-thinker. Extensive experiments verify that our new solution scales well with the number of CPU cores, achieving 201× runtime speedup when mining a graph with 3.77M vertices and 16.5M edges in a 16-node cluster.
AB - Given a user-specified minimum degree threshold γ, a γ-quasi-clique is a subgraph д = (Vд, Eд ) where each vertex v ∈ Vд connects to at least γ fraction of the other vertices (i.e., ⌈γ · (|Vд | − 1)⌉ vertices) in д. Quasi-clique is one of the most natural definitions for dense structures useful in finding communities in social networks and discovering significant biomolecule structures and pathways. However, mining maximal quasi-cliques is notoriously expensive. In this paper, we design parallel algorithms for mining maximal quasi-cliques on G-thinker, a distributed graph mining framework that decomposes mining into compute-intensive tasks to fully utilize CPU cores. We found that directly using G-thinker results in the straggler problem due to (i) the drastic load imbalance among different tasks and (ii) the difficulty of predicting the task running time. We address these challenges by redesigning G-thinker’s execution engine to prioritize long-running tasks for execution, and by utilizing a novel timeout strategy to effectively decompose long-running tasks to improve load balancing. While this system redesign applies to many other expensive dense subgraph mining problems, this paper verifies the idea by adapting the state-of-the-art quasi-clique algorithm, Quick, to our redesigned G-thinker. Extensive experiments verify that our new solution scales well with the number of CPU cores, achieving 201× runtime speedup when mining a graph with 3.77M vertices and 16.5M edges in a 16-node cluster.
UR - http://www.scopus.com/inward/record.url?scp=85099134140&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85099134140&partnerID=8YFLogxK
U2 - 10.14778/3436905.3436916
DO - 10.14778/3436905.3436916
M3 - Article
AN - SCOPUS:85099134140
SN - 2150-8097
VL - 14
SP - 573
EP - 585
JO - Proceedings of the VLDB Endowment
JF - Proceedings of the VLDB Endowment
IS - 4
ER -