Scaling Up k-Clique Densest Subgraph Detection

He, Y; Wang, K; Zhang, W; Lin, X; Zhang, Y

Scaling Up k-Clique Densest Subgraph Detection

He, Y Wang, K Zhang, W Lin, X Zhang, Y

Permalink

Publisher:: Association for Computing Machinery (ACM)
Publication Type:: Journal Article
Citation:: Proceedings of the ACM on Management of Data, 2023, 1, (1), pp. 1-26
Issue Date:: 2023-05-26

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted versionAdobe PDF (753.44 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	He, Y
dc.contributor.author	Wang, K
dc.contributor.author	Zhang, W
dc.contributor.author	Lin, X
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.date.accessioned	2024-03-04T04:11:45Z
dc.date.available	2024-03-04T04:11:45Z
dc.date.issued	2023-05-26
dc.identifier.citation	Proceedings of the ACM on Management of Data, 2023, 1, (1), pp. 1-26
dc.identifier.issn	2836-6573
dc.identifier.issn	2836-6573
dc.identifier.uri	http://hdl.handle.net/10453/176067
dc.description.abstract	<jats:p>In this paper, we study the k-clique densest subgraph problem, which detects the subgraph that maximizes the ratio between the number of k-cliques and the number of vertices in it. The problem has been extensively studied in the literature and has many applications in a wide range of fields such as biology and finance. Existing solutions rely heavily on repeatedly computing all the k-cliques, which are not scalable to handle large k values on large-scale graphs. In this paper, by adapting the idea of "pivoting", we propose the SCT-Index to compactly organize the k-cliques. Based on the SCT-Index, our SCTL algorithm can directly obtain the k-cliques from the index and efficiently achieve near-optimal approximation. To further improve SCTL, we propose SCTL* that includes novel graph reductions and batch-processing optimizations to reduce the search space and decrease the number of visited k-cliques, respectively. As evaluated in our experiments, SCTL* significantly outperform existing approaches by up to two orders of magnitude. In addition, we propose a sampling-based approximate algorithm that can provide reasonable approximations for any k value on billion-scale graphs. Extensive experiments on 12 real-world graphs validate both the efficiency and effectiveness of the proposed techniques.</jats:p>
dc.language	en
dc.publisher	Association for Computing Machinery (ACM)
dc.relation	http://purl.org/au-research/grants/arc/DP210101393
dc.relation	http://purl.org/au-research/grants/arc/DP230101445
dc.relation.ispartof	Proceedings of the ACM on Management of Data
dc.relation.isbasedon	10.1145/3588923
dc.rights	info:eu-repo/semantics/openAccess
dc.title	Scaling Up k-Clique Densest Subgraph Detection
dc.type	Journal Article
utslib.citation.volume	1
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
utslib.copyright.status	open_access	*
dc.date.updated	2024-03-04T04:11:44Z
pubs.issue	1
pubs.publication-status	Published
pubs.volume	1
utslib.citation.issue	1

Abstract:

In this paper, we study the k-clique densest subgraph problem, which detects the subgraph that maximizes the ratio between the number of k-cliques and the number of vertices in it. The problem has been extensively studied in the literature and has many applications in a wide range of fields such as biology and finance. Existing solutions rely heavily on repeatedly computing all the k-cliques, which are not scalable to handle large k values on large-scale graphs. In this paper, by adapting the idea of "pivoting", we propose the SCT*-Index to compactly organize the k-cliques. Based on the SCT*-Index, our SCTL algorithm can directly obtain the k-cliques from the index and efficiently achieve near-optimal approximation. To further improve SCTL, we propose SCTL* that includes novel graph reductions and batch-processing optimizations to reduce the search space and decrease the number of visited k-cliques, respectively. As evaluated in our experiments, SCTL* significantly outperform existing approaches by up to two orders of magnitude. In addition, we propose a sampling-based approximate algorithm that can provide reasonable approximations for any k value on billion-scale graphs. Extensive experiments on 12 real-world graphs validate both the efficiency and effectiveness of the proposed techniques.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/176067