Maximal Directed Quasi -Clique Mining

Guimu Guo; Da Yan; Lyuheng Yuan; Jalal Khalil; Cheng Long; Zhe Jiang; Yang Zhou

doi:10.1109/ICDE53745.2022.00188

Maximal Directed Quasi -Clique Mining

Guimu Guo
, Da Yan
, Lyuheng Yuan
, Jalal Khalil
, Cheng Long
, Zhe Jiang
, Yang Zhou

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

Abstract

Quasi-cliques are a type of dense subgraphs that generalize the notion of cliques, important for applications such as community/module detection in various social and biological networks. However, the existing quasi-clique definition and algorithms are only applicable to undirected graphs. In this paper, we generalize the concept of quasi-cliques to directed graphs by proposing (?1, ?2) -quasi-cliques which have density requirements in both inbound and outbound directions of each vertex in a quasi-clique subgraph. An efficient recursive algorithm is proposed to find maximal (?1,?2)-quasi-cliques which integrates many effective pruning rules that are validated by ablation studies. We also study the finding of top-k large quasi-cliques directly by bootstrapping the search from more compact quasi-cliques, to scale the mining to larger networks. The algorithms are parallelized with effective load balancing, and we demonstrate that they can scale up effectively with the number of CPU cores.

Original language	English (US)
Title of host publication	Proceedings - 2022 IEEE 38th International Conference on Data Engineering, ICDE 2022
Publisher	IEEE Computer Society
Pages	1900-1913
Number of pages	14
ISBN (Electronic)	9781665408837
DOIs	https://doi.org/10.1109/ICDE53745.2022.00188
State	Published - 2022
Externally published	Yes
Event	38th IEEE International Conference on Data Engineering, ICDE 2022 - Virtual, Online, Malaysia Duration: May 9 2022 → May 12 2022

Publication series

Name	Proceedings - International Conference on Data Engineering
Volume	2022-May

Conference

Conference	38th IEEE International Conference on Data Engineering, ICDE 2022
Country/Territory	Malaysia
City	Virtual, Online
Period	5/9/22 → 5/12/22

ASJC Scopus subject areas

Software
Signal Processing
Information Systems

Access to Document

10.1109/ICDE53745.2022.00188

Cite this

@inproceedings{d8530fe6660b4512bf445a1fe2ab9067,

title = "Maximal Directed Quasi -Clique Mining",

abstract = "Quasi-cliques are a type of dense subgraphs that generalize the notion of cliques, important for applications such as community/module detection in various social and biological networks. However, the existing quasi-clique definition and algorithms are only applicable to undirected graphs. In this paper, we generalize the concept of quasi-cliques to directed graphs by proposing (?1, ?2) -quasi-cliques which have density requirements in both inbound and outbound directions of each vertex in a quasi-clique subgraph. An efficient recursive algorithm is proposed to find maximal (?1,?2)-quasi-cliques which integrates many effective pruning rules that are validated by ablation studies. We also study the finding of top-k large quasi-cliques directly by bootstrapping the search from more compact quasi-cliques, to scale the mining to larger networks. The algorithms are parallelized with effective load balancing, and we demonstrate that they can scale up effectively with the number of CPU cores.",

author = "Guimu Guo and Da Yan and Lyuheng Yuan and Jalal Khalil and Cheng Long and Zhe Jiang and Yang Zhou",

note = "Publisher Copyright: {\textcopyright} 2022 IEEE.; 38th IEEE International Conference on Data Engineering, ICDE 2022 ; Conference date: 09-05-2022 Through 12-05-2022",

year = "2022",

doi = "10.1109/ICDE53745.2022.00188",

language = "English (US)",

series = "Proceedings - International Conference on Data Engineering",

publisher = "IEEE Computer Society",

pages = "1900--1913",

booktitle = "Proceedings - 2022 IEEE 38th International Conference on Data Engineering, ICDE 2022",

address = "United States",

}

Guo, G, Yan, D, Yuan, L, Khalil, J, Long, C, Jiang, Z & Zhou, Y 2022, Maximal Directed Quasi -Clique Mining. in Proceedings - 2022 IEEE 38th International Conference on Data Engineering, ICDE 2022. Proceedings - International Conference on Data Engineering, vol. 2022-May, IEEE Computer Society, pp. 1900-1913, 38th IEEE International Conference on Data Engineering, ICDE 2022, Virtual, Online, Malaysia, 5/9/22. https://doi.org/10.1109/ICDE53745.2022.00188

Maximal Directed Quasi -Clique Mining. / Guo, Guimu; Yan, Da; Yuan, Lyuheng et al.
Proceedings - 2022 IEEE 38th International Conference on Data Engineering, ICDE 2022. IEEE Computer Society, 2022. p. 1900-1913 (Proceedings - International Conference on Data Engineering; Vol. 2022-May).

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

TY - GEN

T1 - Maximal Directed Quasi -Clique Mining

AU - Guo, Guimu

AU - Yan, Da

AU - Yuan, Lyuheng

AU - Khalil, Jalal

AU - Long, Cheng

AU - Jiang, Zhe

AU - Zhou, Yang

PY - 2022

Y1 - 2022

N2 - Quasi-cliques are a type of dense subgraphs that generalize the notion of cliques, important for applications such as community/module detection in various social and biological networks. However, the existing quasi-clique definition and algorithms are only applicable to undirected graphs. In this paper, we generalize the concept of quasi-cliques to directed graphs by proposing (?1, ?2) -quasi-cliques which have density requirements in both inbound and outbound directions of each vertex in a quasi-clique subgraph. An efficient recursive algorithm is proposed to find maximal (?1,?2)-quasi-cliques which integrates many effective pruning rules that are validated by ablation studies. We also study the finding of top-k large quasi-cliques directly by bootstrapping the search from more compact quasi-cliques, to scale the mining to larger networks. The algorithms are parallelized with effective load balancing, and we demonstrate that they can scale up effectively with the number of CPU cores.

AB - Quasi-cliques are a type of dense subgraphs that generalize the notion of cliques, important for applications such as community/module detection in various social and biological networks. However, the existing quasi-clique definition and algorithms are only applicable to undirected graphs. In this paper, we generalize the concept of quasi-cliques to directed graphs by proposing (?1, ?2) -quasi-cliques which have density requirements in both inbound and outbound directions of each vertex in a quasi-clique subgraph. An efficient recursive algorithm is proposed to find maximal (?1,?2)-quasi-cliques which integrates many effective pruning rules that are validated by ablation studies. We also study the finding of top-k large quasi-cliques directly by bootstrapping the search from more compact quasi-cliques, to scale the mining to larger networks. The algorithms are parallelized with effective load balancing, and we demonstrate that they can scale up effectively with the number of CPU cores.

UR - https://www.scopus.com/pages/publications/85134767103

UR - https://www.scopus.com/pages/publications/85134767103#tab=citedBy

U2 - 10.1109/ICDE53745.2022.00188

DO - 10.1109/ICDE53745.2022.00188

M3 - Conference contribution

T3 - Proceedings - International Conference on Data Engineering

SP - 1900

EP - 1913

BT - Proceedings - 2022 IEEE 38th International Conference on Data Engineering, ICDE 2022

PB - IEEE Computer Society

T2 - 38th IEEE International Conference on Data Engineering, ICDE 2022

Y2 - 9 May 2022 through 12 May 2022

ER -

Maximal Directed Quasi -Clique Mining

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this