×

A semi-exact algorithm for quickly computing a maximum weight clique in large sparse graphs. (English) Zbl 07406493

Summary: This paper explores techniques to quickly solve the maximum weight clique problem (MWCP) in very large scale sparse graphs. Due to their size, and the hardness of MWCP, it is infeasible to solve many of these graphs with exact algorithms. Although recent heuristic algorithms make progress in solving MWCP in large graphs, they still need considerable time to get a high-quality solution. In this work, we focus on solving MWCP for large sparse graphs within a short time limit. We propose a new method for MWCP which interleaves clique finding with data reduction rules. We propose novel ideas to make this process efficient, and develop an algorithm called FastWClq. Experiments on a broad range of large sparse graphs show that FastWClq finds better solutions than state-of-the-art algorithms while the running time of FastWClq is much shorter than the competitors for most instances. Further, FastWClq proves the optimality of its solutions for roughly half of the graphs, all with at least \(10^5\) vertices, with an average time of 21 seconds.

MSC:

68Txx Artificial intelligence

Keywords:

heuristics; search

Software:

BBMCSP; KONECT; SCCWalk
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Balasundaram, B., & Butenko, S. (2006). Graph domination, coloring and cliques in telecommunications. InHandbook of Optimization in Telecommunications, pp. 865-890. · Zbl 1118.90008
[2] Ballard, D., & Brown, C. (1982).Computer Vision. New Jersey: Prentice Hall.
[3] Batagelj, V., & Zaverˇsnik, M. (2003). AnO(m)algorithm for cores decomposition of networks. CoRR,cs.DS/0310049.
[4] Benlic, U., & Hao, J.-K. (2013). Breakout local search for maximum clique problems.Computers & Operations Research,40(1), 192-206. · Zbl 1349.90005
[5] Busygin, S. (2006). A new trust region technique for the maximum weight clique problem.Discrete Applied Mathematics,154(15), 2080-2096. · Zbl 1111.90020
[6] Cai, S. (2015). Balance between complexity and quality: Local search for minimum vertex cover in massive graphs. InProceedings of IJCAI 2015, pp. 747-753.
[7] Cai, S., Li, Y., Hou, W., & Wang, H. (2019). Towards faster local search for minimum weight vertex cover on massive graphs.Information Sciences,471, 64-79. · Zbl 1441.68168
[8] Cai, S., & Lin, J. (2016). Fast solving maximum weight clique problem in massive graphs. In Proceedings of IJCAI 2016, pp. 568-574.
[9] Cai, S., Luo, C., Zhang, X., & Zhang, J. (2021). Improving local search for structured sat formulas via unit propagation based construct and cut initialization. InProceedings of CP 2021.
[10] Demange, M., de Werra, D., Monnot, J., & Paschos, V. T. (2002). Weighted node coloring: when stable sets are expensive. InInternational Workshop on Graph-Theoretic Concepts in Computer Science, pp. 114-125. Springer. · Zbl 1022.68092
[11] Fan, Y., Li, N., Li, C., Ma, Z., Latecki, L. J., & Su, K. (2017). Restart and random walk in local search for maximum vertex weight cliques with evaluations in clustering aggregation. In Proceedings of IJCAI 2017, pp. 622-630.
[12] Fang, Z., Li, C.-M., Qiao, K., Feng, X., & Xu, K. (2014). Solving maximum weight clique using maximum satisfiability reasoning. InProceedings of ECAI 2014, pp. 303-308. · Zbl 1366.90176
[13] Fellows, M. R., & Downey, R. (1998).Parameterized Complexity. Springer. · Zbl 0914.68076
[14] Gomez Ravetti, M., & Moscato, P. (2008). Identification of a 5-protein biomarker molecular signature for predicting Alzheimer’s disease.PloS one,3(9), e3111.
[15] Guturu, P., & Dantu, R. (2008). An impatient evolutionary algorithm with probabilistic tabu search for unified solution of some NP-hard problems in graph and set theory via clique finding. IEEE Trans. Systems, Man, and Cybernetics, Part B,38(3), 645-666.
[16] Hsu, H., & Chang, G. J. (2016). Max-coloring of vertex-weighted graphs.Graphs and Combinatorics,32(1), 191-198. · Zbl 1341.05075
[17] Jiang, H., Li, C., Liu, Y., & Many‘a, F. (2018). A two-stage MaxSAT reasoning approach for the maximum weight clique problem. InProceedings of AAAI 2018, pp. 1338-1346.
[18] Jiang, H., Li, C., & Many‘a, F. (2017). An exact algorithm for the maximum weight clique problem in large graphs. InProceedings of AAAI 2017, pp. 830-838.
[19] Karp, R. M. (1972). Reducibility among combinatorial problems. InComplexity of computer computations, pp. 85-103. Springer. · Zbl 1467.68065
[20] Konc, J., & Janezic, D. (2007). An improved branch and bound algorithm for the maximum clique problem.Communications in Mathematical and in Computer Chemistry,58, 569-590. · Zbl 1274.05452
[21] Kumlander, D. (2004). Fast maximum clique algorithms for large graphs. InProceedings of the fourth conference on engineering computational technology, pp. 202-208.
[22] Kunegis, J. (2013). Konect: the koblenz network collection. InProceedings of WWW 2013, pp. 1343-1350.
[23] Lamm, S., Schulz, C., Strash, D., Williger, R., & Zhang, H. (2019). Exactly solving the maximum weight independent set problem on large real-world graphs. InProceedings of ALENEX 2019, pp. 144-158. · Zbl 1430.68226
[24] Li, C.-M., Fang, Z., & Xu, K. (2013). Combining MaxSAT reasoning and incremental upper bound for the maximum clique problem. InProceedings of ICTAI 2013, pp. 939-946.
[25] Li, C.-M., Jiang, H., & Many‘a, F. (2017). On minimization of the number of branches in branchand-bound algorithms for the maximum clique problem.Computers & Operations Research, 84, 1-15.
[26] Li, C., Liu, Y., Jiang, H., Many‘a, F., & Li, Y. (2018). A new upper bound for the maximum weight clique problem.European Journal of Operational Research,270(1), 66-77. · Zbl 1403.90640
[27] Li, C. M., & Quan, Z. (2010). An efficient branch-and-bound algorithm based on MaxSAT for the maximum clique problem. InProceedings of AAAI 2010, pp. 128-133.
[28] Li, R., Hu, S., Cai, S., Gao, J., Wang, Y., & Yin, M. (2020). Numwvc: A novel local search for minimum weighted vertex cover problem.Journal of the Operational Research Society,71(9), 1498-1509.
[29] Massaro, A., Pelillo, M., & Bomze, I. M. (2002). A complementary pivoting approach to the maximum weight clique problem.SIAM Journal on Optimization,12(4), 928-948. · Zbl 1035.90072
[30] McCreesh, C., Prosser, P., Simpson, K., & Trimble, J. (2017). On maximum weight clique algorithms, and how they are evaluated. InProceedings of CP 2017, pp. 206-225.
[31] Osterg˚ard, P. R. J. (1999). A new algorithm for the maximum-weight clique problem.¨Electronic Notes in Discrete Mathematics,3, 153-156.
[32] Pullan, W. (2006). Phased local search for the maximum clique problem.Journal of Combinatorial Optimization,12(3), 303-323. · Zbl 1255.90122
[33] Pullan, W. (2008). Approximating the maximum vertex/edge weighted clique using local search. Journal of Heuristics,14(2), 117-134. · Zbl 1173.90569
[34] Pullan, W. (2009). Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers.Discrete Optimization,6(2), 214-219. · Zbl 1169.05383
[35] Pullan, W., & Hoos, H. H. (2006). Dynamic local search for the maximum clique problem.Journal of Artificial Intelligence Research,25, 159-185. · Zbl 1182.68065
[36] Rossi, R. A., & Ahmed, N. K. (2015). The network data repository with interactive graph analytics and visualization. InProceedings of AAAI 2015, pp. 4292-4293.
[37] Rossi, R. A., Gleich, D. F., Gebremedhin, A. H., & Patwary, M. (2014). Fast maximum clique algorithms for large graphs. InProceedings of WWW 2014, pp. 365-366.
[38] San Segundo, P., Furini, F., & Artieda, J. (2019). A new branch-and-bound algorithm for the maximum weighted clique problem.Computers & Operations Research,110, 18-33. · Zbl 1458.90624
[39] San Segundo, P., Lopez, A., & Pardalos, P. M. (2016). A new exact maximum clique algorithm for large and massive sparse graphs.Computers & Operations Research,66, 81-94. · Zbl 1349.90824
[40] San Segundo, P., Mat´ıa, F., Rodr´ıguez-Losada, D., & Hernando, M. (2013). An improved bit parallel exact maximum clique algorithm.Optimization Letters,7(3), 467-479. · Zbl 1268.90118
[41] Seidman, S. (1983). Network structure and minimum degree.Social Networks,5(3), 269-287.
[42] Singh, A., & Gupta, A. K. (2006a). A hybrid evolutionary approach to maximum weight clique problem.International Journal of Computational Intelligence Research,2(4), 349-355.
[43] Singh, A., & Gupta, A. K. (2006b). A hybrid heuristic for the maximum clique problem.Journal of Heuristics,12(1-2), 5-22. · Zbl 1122.90070
[44] Tomita, E., & Kameda, T. (2007). An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments.Journal of Global optimization,37(1), 95-111. · Zbl 1127.90079
[45] Tomita, E., & Seki, T. (2003). An efficient branch-and-bound algorithm for finding a maximum clique. InDiscrete mathematics and theoretical computer science, pp. 278-289. · Zbl 1038.68565
[46] Tomita, E., Sutani, Y., Higashi, T., Takahashi, S., & Wakatsuki, M. (2010). A simple and faster branch-and-bound algorithm for finding a maximum clique. InProceedings of WALCOM 2010, pp. 191-203. · Zbl 1274.05455
[47] Verma, A., Buchanan, A., & Butenko, S. (2015). Solving the maximum clique and vertex coloring problems on very large sparse networks.INFORMS Journal on Computing,27(1), 164-177. · Zbl 1327.90356
[48] Wang, Y., Cai, S., Chen, J., & Yin, M. (2020). SCCWalk: An efficient local search algorithm and its improvements for maximum weight clique problem.Artificial Intelligence,280, 103230. · Zbl 1476.68218
[49] Wang, Y., Cai, S., & Yin, M. (2016). Two efficient local search algorithms for maximum weight clique problem. InProceedings of AAAI 2016, pp. 805-811.
[50] Wu, Q., Hao, J.-K., & Glover, F. (2012). Multi-neighborhood tabu search for the maximum weight clique problem.Annals of Operations Research,196(1), 611-634. · Zbl 1251.90378
[51] Zhou, Y., Hao, J., & Go¨effon, A. (2017). PUSH: A generalized operator for the maximum vertex weight clique problem.European Journal of Operational Research,257(1), 41-54.
[52] Zuckerman, D. (2007). Linear degree extractors and the inapproximability of max clique and chromatic number.Theory of Computing,3(1), 103-128 · Zbl 1213.68322
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.