×

SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem. (English) Zbl 1476.68218

Summary: The maximum weight clique problem (MWCP) is an important generalization of the maximum clique problem with wide applications. In this study, we develop two efficient local search algorithms for MWCP, namely SCCWalk and SCCWalk4L, where SCCWalk4L is improved from SCCWalk for large graphs. There are two main ideas in SCCWalk, including strong configuration checking (SCC) and walk perturbation. SCC is a new variant of a powerful strategy called configuration checking for local search. The walk perturbation procedure is used to lead the algorithm to leave the current area and come into a new area of feasible solution space. Moreover, to improve the performance on massive graphs, we apply a low-complexity heuristic called best from multiple selection to select the swapping vertex pair quickly and effectively, resulting in the SCCWalk4L algorithm. In addition, SCCWalk4L uses two recent reduction rules to decrease the scale of massive graphs. We carry out experiments to evaluate our algorithms on several popular benchmarks, which are divided into two groups, including classical benchmarks of small graphs namely DIMACS, BHOSLIB, winner determination problem, and graphs derived from clustering aggregation, as well as massive graphs, including a suite of massive real-world graphs and large-scale FRB graphs. Experiments show that, compared to state-of-the-art heuristic algorithms and exact algorithm, the proposed algorithms perform better on classical benchmarks, and obtain the best solutions for most massive graphs.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ballard, D.; Brown, C., Computer Vision, Englewood Cliffs (1982), Prentice Hall
[2] Balasundaram, B.; Butenko, S., Graph domination, coloring and cliques in telecommunications, (Handbook of Optimization in Telecommunications (2006), Springer), 865-890 · Zbl 1118.90008
[3] Gomez Ravetti, M.; Moscato, P., Identification of a 5-protein biomarker molecular signature for predicting Alzheimer’s disease, PLoS ONE, 3, 9, Article e3111 pp. (2008)
[4] Pattillo, J.; Youssef, N.; Butenko, S., Clique relaxation models in social network analysis, (Handbook of Optimization in Complex Networks (2012), Springer), 143-162 · Zbl 1247.91162
[5] Mascia, F.; Cilia, E.; Brunato, M.; Passerini, A., Predicting structural and functional sites in proteins by searching for maximum-weight cliques, (Twenty-Fourth AAAI Conference on Artificial Intelligence. Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA (July 2010)), 1274-1279
[6] Ma, T.; Latecki, L. J., Maximum weight cliques with mutex constraints for video object segmentation, (2012 IEEE Conference on Computer Vision and Pattern Recognition. 2012 IEEE Conference on Computer Vision and Pattern Recognition, CVPR (2012), IEEE), 670-677
[7] Zhian, H.; Sabaei, M.; Javan, N. T.; Tavallaie, O., Increasing coding opportunities using maximum-weight clique, (Computer Science and Electronic Engineering Conference (2013)), 168-173
[8] Wu, Q.; Hao, J.-K., Solving the winner determination problem via a weighted maximum clique heuristic, Expert Syst. Appl., 42, 1, 355-365 (2015)
[9] Karp, R., Reducibility among combinatorial problems, (Complexity of Computer Computations (1972)), 85-103
[10] Feige, U., Approximating maximum clique by removing subgraphs, SIAM J. Discrete Math., 18, 2, 219-225 (2004) · Zbl 1068.05052
[11] Tomita, E.; Seki, T., An efficient branch-and-bound algorithm for finding a maximum clique, (International Conference on Discrete Mathematics and Theoretical Computer Science (2003), Springer), 278-289 · Zbl 1038.68565
[12] Konc, J.; Janezic, D., An improved branch and bound algorithm for the maximum clique problem, Commun. Math. Comput. Chem., 58, 569-590 (2007) · Zbl 1274.05452
[13] Li, C. M.; Quan, Z., An efficient branch-and-bound algorithm based on MaxSAT for the maximum clique problem, (AAAI, vol. 10 (2010)), 128-133
[14] San Segundo, P.; Lopez, A.; Pardalos, P. M., A new exact maximum clique algorithm for large and massive sparse graphs, Comput. Oper. Res., 66, 81-94 (2016) · Zbl 1349.90824
[15] Jiang, H.; Li, C. M.; Manyà, F., Combining efficient preprocessing and incremental MaxSAT reasoning for MaxClique in large graphs, (ECAI (2016)), 939-947
[16] Li, C.-M.; Jiang, H.; Manyà, F., On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem, Comput. Oper. Res., 84, 1-15 (2017) · Zbl 1391.90607
[17] Babel, L., A fast algorithm for the maximum weight clique problem, Computing, 52, 1, 31-38 (1994) · Zbl 0791.68127
[18] Östergård, P. R., A new algorithm for the maximum-weight clique problem, Nord. J. Comput., 8, 4, 424-436 (2001) · Zbl 1003.68117
[19] Yamaguchi, K.; Masuda, S., A new exact algorithm for the maximum weight clique problem, (ITC-CSCC: 2008 (2008)), 317-320
[20] Shimizu, S.; Yamaguchi, K.; Saitoh, T.; Masuda, S., Optimal table method for finding the maximum weight clique, (Proc. of the 13th International Conference on Applied Computer Science (2013)), 84-90
[21] Fang, Z.; Li, C.-M.; Xu, K., An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem, J. Artif. Intell. Res., 55, 799-833 (2016) · Zbl 1352.05174
[22] Jiang, H.; Li, C.-M.; Manya, F., An exact algorithm for the maximum weight clique problem in large graphs, (AAAI (2017)), 830-838
[23] Jiang, H.; Li, C.-M.; Liu, Y.; Manya, F., A two-stage MaxSAT reasoning approach for the maximum weight clique problem, (Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (2018)), 1338-1346
[24] Singh, A.; Gupta, A. K., A hybrid heuristic for the maximum clique problem, J. Heuristics, 12, 1-2, 5-22 (2006) · Zbl 1122.90070
[25] Pullan, W.; Hoos, H. H., Dynamic local search for the maximum clique problem, J. Artif. Intell. Res., 159-185 (2006) · Zbl 1182.68065
[26] Pullan, W., Phased local search for the maximum clique problem, J. Comb. Optim., 12, 3, 303-323 (2006) · Zbl 1255.90122
[27] Guturu, P.; Dantu, R., 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. Syst. Man Cybern., Part B, Cybern., 38, 3, 645-666 (2008)
[28] Wu, Q.; Hao, J.-K., An adaptive multistart tabu search approach to solve the maximum clique problem, J. Comb. Optim., 26, 1, 86-108 (2013) · Zbl 1275.90084
[29] Benlic, U.; Hao, J.-K., Breakout local search for maximum clique problems, Comput. Oper. Res., 40, 1, 192-206 (2013) · Zbl 1349.90005
[30] Bomze, I. M.; Pelillo, M.; Stix, V., Approximating the maximum weight clique using replicator dynamics, IEEE Trans. Neural Netw., 11, 6, 1228-1241 (2000)
[31] Busygin, S., A new trust region technique for the maximum weight clique problem, Discrete Appl. Math., 154, 15, 2080-2096 (2006) · Zbl 1111.90020
[32] Pullan, W., Approximating the maximum vertex/edge weighted clique using local search, J. Heuristics, 14, 2, 117-134 (2008) · Zbl 1173.90569
[33] Wu, Q.; Hao, J.-K.; Glover, F., Multi-neighborhood tabu search for the maximum weight clique problem, Ann. Oper. Res., 196, 1, 611-634 (2012) · Zbl 1251.90378
[34] Cai, S.; Lin, J., Fast solving maximum weight clique problem in massive graphs, (Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI (2016)), 568-574
[35] Nogueira, B.; Pinheiro, R. G., A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs, Comput. Oper. Res., 90, 232-248 (2018) · Zbl 1391.90527
[36] Fan, Y.; Li, N.; Li, C.; Ma, Z.; Latecki, L. J.; Su, K., Restart and random walk in local search for maximum vertex weight cliques with evaluations in clustering aggregation, (IJCAI (2017)), 622-630
[37] Cai, S.; Su, K.; Sattar, A., Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Artif. Intell., 175, 9, 1672-1696 (2011) · Zbl 1225.68242
[38] Li, R.; Cai, S.; Hu, S.; Yin, M.; Gao, J., NuMWVC: a novel local search for minimum weighted vertex cover problem, (Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (2018)), 8107-8108
[39] Wang, Y.; Cai, S.; Yin, M., Local search for minimum weight dominating set with two-level configuration checking and frequency based scoring function, J. Artif. Intell. Res., 58, 267-295 (2017) · Zbl 1404.68146
[40] Wang, Y.; Cai, S.; Chen, J.; Yin, M., A fast local search algorithm for minimum weight dominating set problem on massive graphs, (IJCAI (2018)), 1514-1522
[41] Wang, Y.; Ouyang, D.; Zhang, L.; Yin, M., A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity, Sci. China Inf. Sci., 60, 6, Article 062103 pp. (2017)
[42] Wang, Y.; Li, C.; Sun, H.; Chen, J.; Yin, M., MLQCC: an improved local search algorithm for the set k-covering problem, Int. Trans. Oper. Res., 26, 3, 856-887 (2019)
[43] Cai, S.; Su, K., Configuration checking with aspiration in local search for sat, (Proceedings of AAAI 2012 (2012)), 334-340
[44] Cai, S.; Su, K., Local search for Boolean satisfiability with configuration checking and subscore, Artif. Intell., 204, 75-98 (2013) · Zbl 1334.68200
[45] Abramé, A.; Habet, D.; Toumi, D., Improving configuration checking for satisfiable random k-SAT instances, Ann. Math. Artif. Intell., 79, 1-3, 5-24 (2017) · Zbl 1404.68136
[46] Luo, C.; Cai, S.; Wu, W.; Jie, Z.; Su, K., CCLS: an efficient local search algorithm for weighted maximum satisfiability, IEEE Trans. Comput., 64, 7, 1830-1843 (2015) · Zbl 1360.68786
[47] Johnson, D. S., Cliques, coloring, and satisfiability: second DIMACS implementation challenge, DIMACS Ser. Discret. Math. Theor. Comput. Sci., 26, 11-13 (1993)
[48] Xu, K.; Boussemart, F.; Hemery, F.; Lecoutre, C., A simple model to generate hard satisfiable instances, (Proceedings of IJCAI (2005)), 337-342
[49] Wu, Q.; Hao, J.-K., A clique-based exact method for optimal winner determination in combinatorial auctions, Inf. Sci., 334, 103-121 (2016)
[50] Cai, S., Balance between complexity and quality: local search for minimum vertex cover in massive graphs, (Proceedings of IJCAI 2015 (2015)), 747-753
[51] Rossi, R. A.; Ahmed, N. K., The network data repository with interactive graph analytics and visualization, (Twenty-Ninth AAAI Conference on Artificial Intelligence (2015)), 4292-4293
[52] Wang, Y.; Cai, S.; Yin, M., Two efficient local search algorithms for maximum weight clique problem, (AAAI (2016)), 805-811
[53] Li, C. M.; Huang, W., Diversification and determinism in local search for satisfiability, (Proceedings of Theory and Applications of Satisfiability Testing. Proceedings of Theory and Applications of Satisfiability Testing, SAT 2005 (2005)), 158-172 · Zbl 1128.68472
[54] Glover, F., Tabu search – part I, ORSA J. Comput., 1, 3, 190-206 (1989) · Zbl 0753.90054
[55] Zhou, Y.; Hao, J.-K.; Goëffon Push, A., A generalized operator for the maximum vertex weight clique problem, Eur. J. Oper. Res., 257, 1, 41-54 (2017) · Zbl 1394.90506
[56] Cai, S.; Lin, J.; Luo, C., Finding a small vertex cover in massive sparse graphs: construct, local search, and preprocess, J. Artif. Intell. Res., 59, 463-494 (2017) · Zbl 1418.68164
[57] Lin, J.; Cai, S.; Luo, C.; Su, K., A reduction based method for coloring very large graphs, (Twenty-Sixth International Joint Conference on Artificial Intelligence (2017)), 517-523
[58] Cai, S.; Su, K.; Luo, C.; Sattar, A., NuMVC: an efficient local search algorithm for minimum vertex cover, J. Artif. Intell. Res., 687-716 (2013) · Zbl 1280.90098
[59] Ma, Z.; Fan, Y.; Su, K.; Li, C.; Sattar, A., Deterministic tournament selection in local search for maximum edge weight clique on large sparse graphs, (Australasian Joint Conference on Artificial Intelligence (2017), Springer), 353-364
[60] Rossi, R. A.; Gleich, D. F.; Gebremedhin, A. H.; Patwary, M. M.A., Fast maximum clique algorithms for large graphs, (Proceedings of the Companion Publication of the 23rd International Conference on World Wide Web Companion (2014)), 365-366
[61] Xu, K.; Boussemart, F.; Hemery, F.; Lecoutre, C., Random constraint satisfaction: easy generation of hard (satisfiable) instances, Artif. Intell., 171, 8, 514-534 (2007) · Zbl 1168.68554
[62] Xu, K.; Li, W., Exact phase transitions in random constraint satisfaction problems, J. Artif. Intell. Res., 12, 1, 93-103 (2000) · Zbl 0940.68099
[63] Xu, K.; Li, W., Many hard examples in exact phase transitions, Theor. Comput. Sci., 355, 3, 291-302 (2006) · Zbl 1088.68163
[64] Stern, R.; Dreiman, G.; Valenzano, R., Probably bounded suboptimal heuristic search, Artif. Intell., 267, 39-57 (2019) · Zbl 1478.68337
[65] Li, Z.; Chen, Q.; Koltun, V., Combinatorial optimization with graph convolutional networks and guided tree search, (Advances in Neural Information Processing Systems (2018)), 537-546
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.