QClique: optimizing performance and accuracy in maximum weighted clique

Qasim Abbas; Mohsen Koohi Esfahani; Ian Overton; Hans Vandierendonck

doi:10.1007/978-3-031-69583-4_7

QClique: optimizing performance and accuracy in maximum weighted clique

Qasim Abbas^*, Mohsen Koohi Esfahani, Ian Overton, Hans Vandierendonck

^*Corresponding author for this work

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

24 Downloads (Pure)

Abstract

The Maximum Weighted Clique (MWC) problem remains challenging due to its unfavourable time complexity. In this paper, we analyze the execution of exact search-based MWC algorithms and show that high-accuracy weighted cliques can be discovered in the early stages of the execution if searching the combinatorial space is performed systematically.

Based on this observation, we introduce QClique as an approximate MWC algorithm that processes the search space as long as better cliques are expected. QClique uses a tunable parameter to trade-off between accuracy vs. execution time and delivers 4.7-$82.3 time speedup in comparison to previous state-of-the-art MWC algorithms while providing 91.4% accuracy and achieves a parallel speedup of up to 56x on 128 threads.

Additionally, QClique accelerates the exact MWC computation by replacing the initial clique of the exact algorithm. For WLMC, an exact state-of-the-art MWC algorithm, this results in 3.3x on average.

Original language	English
Title of host publication	30th International European Conference on Parallel and Distributed Computing(Euro-Par 2024: Parallel Processing): proceedings, part III
Editors	Jesus Carretero, Sameer Shende, Javier Garcia-Blas, Ivona Brandic, Katzalin Olcoz, Martin Schreiber
Publisher	Springer
Pages	88-102
Number of pages	15
ISBN (Electronic)	9783031695834
ISBN (Print)	9783031695827
DOIs	https://doi.org/10.1007/978-3-031-69583-4_7
Publication status	Published - 26 Aug 2024
Event	30th International European Conference on Parallel and Distributed Computing, Euro-Par 2024 - Madrid, Spain Duration: 26 Aug 2024 → 30 Aug 2024

Publication series

Name	Lecture Notes in Computer Science
Volume	14803
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Name	European Conference on Parallel Processing

Conference

Conference	30th International European Conference on Parallel and Distributed Computing, Euro-Par 2024
Abbreviated title	EURO-PAR 2024
Country/Territory	Spain
City	Madrid
Period	26/08/2024 → 30/08/2024

Keywords

QClique
optimizing performance and accuracy
maximum weighted clique

Access to Document

10.1007/978-3-031-69583-4_7Licence: Unspecified

QClique: optimizing performance and accuracy in maximum weighted clique
Copyright 2024 The Authors. This manuscript is distributed under a Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium, provided the author and source are cited.
Accepted author manuscript, 594 KBLicence: CC BY

Cite this

Abbas, Q., Koohi Esfahani, M., Overton, I., & Vandierendonck, H. (2024). QClique: optimizing performance and accuracy in maximum weighted clique. In J. Carretero, S. Shende, J. Garcia-Blas, I. Brandic, K. Olcoz, & M. Schreiber (Eds.), 30th International European Conference on Parallel and Distributed Computing(Euro-Par 2024: Parallel Processing): proceedings, part III (pp. 88-102). (Lecture Notes in Computer Science; Vol. 14803), (European Conference on Parallel Processing). Springer. https://doi.org/10.1007/978-3-031-69583-4_7

Abbas, Qasim ; Koohi Esfahani, Mohsen ; Overton, Ian et al. / QClique: optimizing performance and accuracy in maximum weighted clique. 30th International European Conference on Parallel and Distributed Computing(Euro-Par 2024: Parallel Processing): proceedings, part III. editor / Jesus Carretero ; Sameer Shende ; Javier Garcia-Blas ; Ivona Brandic ; Katzalin Olcoz ; Martin Schreiber. Springer, 2024. pp. 88-102 (Lecture Notes in Computer Science). (European Conference on Parallel Processing).

@inproceedings{b35755db61244869b246ef3229a46731,

title = "QClique: optimizing performance and accuracy in maximum weighted clique",

abstract = "The Maximum Weighted Clique (MWC) problem remains challenging due to its unfavourable time complexity. In this paper, we analyze the execution of exact search-based MWC algorithms and show that high-accuracy weighted cliques can be discovered in the early stages of the execution if searching the combinatorial space is performed systematically.Based on this observation, we introduce QClique as an approximate MWC algorithm that processes the search space as long as better cliques are expected. QClique uses a tunable parameter to trade-off between accuracy vs. execution time and delivers 4.7-$82.3 time speedup in comparison to previous state-of-the-art MWC algorithms while providing 91.4% accuracy and achieves a parallel speedup of up to 56x on 128 threads.Additionally, QClique accelerates the exact MWC computation by replacing the initial clique of the exact algorithm. For WLMC, an exact state-of-the-art MWC algorithm, this results in 3.3x on average.",

keywords = "QClique, optimizing performance and accuracy, maximum weighted clique",

author = "Qasim Abbas and {Koohi Esfahani}, Mohsen and Ian Overton and Hans Vandierendonck",

year = "2024",

month = aug,

day = "26",

doi = "10.1007/978-3-031-69583-4_7",

language = "English",

isbn = "9783031695827",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "88--102",

editor = "Jesus Carretero and Sameer Shende and Javier Garcia-Blas and Ivona Brandic and Katzalin Olcoz and Martin Schreiber",

booktitle = "30th International European Conference on Parallel and Distributed Computing(Euro-Par 2024: Parallel Processing): proceedings, part III",

note = "30th International European Conference on Parallel and Distributed Computing, Euro-Par 2024, EURO-PAR 2024 ; Conference date: 26-08-2024 Through 30-08-2024",

}

Abbas, Q, Koohi Esfahani, M, Overton, I & Vandierendonck, H 2024, QClique: optimizing performance and accuracy in maximum weighted clique. in J Carretero, S Shende, J Garcia-Blas, I Brandic, K Olcoz & M Schreiber (eds), 30th International European Conference on Parallel and Distributed Computing(Euro-Par 2024: Parallel Processing): proceedings, part III. Lecture Notes in Computer Science, vol. 14803, European Conference on Parallel Processing, Springer, pp. 88-102, 30th International European Conference on Parallel and Distributed Computing, Euro-Par 2024, Madrid, Spain, 26/08/2024. https://doi.org/10.1007/978-3-031-69583-4_7

QClique: optimizing performance and accuracy in maximum weighted clique. / Abbas, Qasim; Koohi Esfahani, Mohsen; Overton, Ian et al.
30th International European Conference on Parallel and Distributed Computing(Euro-Par 2024: Parallel Processing): proceedings, part III. ed. / Jesus Carretero; Sameer Shende; Javier Garcia-Blas; Ivona Brandic; Katzalin Olcoz; Martin Schreiber. Springer, 2024. p. 88-102 (Lecture Notes in Computer Science; Vol. 14803), (European Conference on Parallel Processing).

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

TY - GEN

T1 - QClique: optimizing performance and accuracy in maximum weighted clique

AU - Abbas, Qasim

AU - Koohi Esfahani, Mohsen

AU - Overton, Ian

AU - Vandierendonck, Hans

PY - 2024/8/26

Y1 - 2024/8/26

N2 - The Maximum Weighted Clique (MWC) problem remains challenging due to its unfavourable time complexity. In this paper, we analyze the execution of exact search-based MWC algorithms and show that high-accuracy weighted cliques can be discovered in the early stages of the execution if searching the combinatorial space is performed systematically.Based on this observation, we introduce QClique as an approximate MWC algorithm that processes the search space as long as better cliques are expected. QClique uses a tunable parameter to trade-off between accuracy vs. execution time and delivers 4.7-$82.3 time speedup in comparison to previous state-of-the-art MWC algorithms while providing 91.4% accuracy and achieves a parallel speedup of up to 56x on 128 threads.Additionally, QClique accelerates the exact MWC computation by replacing the initial clique of the exact algorithm. For WLMC, an exact state-of-the-art MWC algorithm, this results in 3.3x on average.

AB - The Maximum Weighted Clique (MWC) problem remains challenging due to its unfavourable time complexity. In this paper, we analyze the execution of exact search-based MWC algorithms and show that high-accuracy weighted cliques can be discovered in the early stages of the execution if searching the combinatorial space is performed systematically.Based on this observation, we introduce QClique as an approximate MWC algorithm that processes the search space as long as better cliques are expected. QClique uses a tunable parameter to trade-off between accuracy vs. execution time and delivers 4.7-$82.3 time speedup in comparison to previous state-of-the-art MWC algorithms while providing 91.4% accuracy and achieves a parallel speedup of up to 56x on 128 threads.Additionally, QClique accelerates the exact MWC computation by replacing the initial clique of the exact algorithm. For WLMC, an exact state-of-the-art MWC algorithm, this results in 3.3x on average.

KW - QClique

KW - optimizing performance and accuracy

KW - maximum weighted clique

U2 - 10.1007/978-3-031-69583-4_7

DO - 10.1007/978-3-031-69583-4_7

M3 - Conference contribution

SN - 9783031695827

T3 - Lecture Notes in Computer Science

SP - 88

EP - 102

BT - 30th International European Conference on Parallel and Distributed Computing(Euro-Par 2024: Parallel Processing): proceedings, part III

A2 - Carretero, Jesus

A2 - Shende, Sameer

A2 - Garcia-Blas, Javier

A2 - Brandic, Ivona

A2 - Olcoz, Katzalin

A2 - Schreiber, Martin

PB - Springer

T2 - 30th International European Conference on Parallel and Distributed Computing, Euro-Par 2024

Y2 - 26 August 2024 through 30 August 2024

ER -

Abbas Q, Koohi Esfahani M, Overton I , Vandierendonck H. QClique: optimizing performance and accuracy in maximum weighted clique. In Carretero J, Shende S, Garcia-Blas J, Brandic I, Olcoz K, Schreiber M, editors, 30th International European Conference on Parallel and Distributed Computing(Euro-Par 2024: Parallel Processing): proceedings, part III. Springer. 2024. p. 88-102. (Lecture Notes in Computer Science). (European Conference on Parallel Processing). doi: 10.1007/978-3-031-69583-4_7

QClique: optimizing performance and accuracy in maximum weighted clique

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this