An exact algorithm with a new upper bound and reductions for maximum edge weighted clique in massive sparse graphs

Abstract

The maximum edge weighted clique (MEWC) problem is a generalization of the maximum clique problem and has widely been applied to model lots of problems arising in real-world applications. Due to its NP-hardness, previous work can hardly solve instances with large sizes. To further improve the performance of MEWC algorithms on massive instances, we develop a novel exact algorithm by combining the branch-and-bound framework and two main ideas, which is called BnBM. First, applying the two-level independent set partition a tighter upper bound is proposed to prune branches and improve the efficiency. Second, to remove as many redundant vertices as possible, a fast reduction mechanism is applied during the search. Extensive experiments are conducted to evaluate the performance of our algorithm. On the 139 real-world large instances, within the same cutoff time (7200 seconds), our proposed BnBM solves 24 instances more than the state-of-the-art exact solvers. Meanwhile, considering the efficiency BnBM achieves a speedup on 75 out of 139 instances. However, for 8 instances BnBM is slower than state-of-the-art solvers, and we conduct a deep analysis of the branching process and find the main reasons are the data structure and the structure of the original graph.

Graphical abstract

Keywords

maximum edge weighted clique / reduction / branching and bound / independent set partition / combinatorial optimization

References

[1] Palla G, Derényi I, Farkas I, Vicsek T . Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435( 7043): 814–818

[2] Guimerà R, Nunes Amaral L A . Functional cartography of complex metabolic networks. Nature, 2005, 433( 7028): 895–900

[3] Ma T, Jan Latecki L. Maximum weight cliques with mutex constraints for video object segmentation. In: Proceedings of 2012 IEEE Conference on Computer Vision and Pattern Recognition. 2012, 670−677

[4] Pavan M, Pelillo M. Generalizing the Motzkin-Straus theorem to edge-weighted graphs, with applications to image segmentation. In: Proceedings of the 4th International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition. 2003, 485−500

[5] Brown J B, Dukka Bahadur K C, Tomita E, Akutsu T. Multiple methods for protein side chain packing using maximum weight cliques. Genome Informatics, 2006, 17(1): 3−12

[6] Dijkhuizen G, Faigle U . A cutting-plane approach to the edge-weighted maximal clique problem. European Journal of Operational Research, 1993, 69( 1): 121–130

[7] Cavique L . A scalable algorithm for the market basket analysis. Journal of Retailing and Consumer Services, 2007, 14( 6): 400–407

[8] Pullan W . Approximating the maximum vertex/edge weighted clique using local search. Journal of Heuristics, 2008, 14( 2): 117–134

[9] Fontes D B M M, Goncalves J F, Fontes F A C C . An evolutionary approach to the maximum edge weight clique problem. Recent Advances in Electrical & Electronic Engineering, 2018, 11( 3): 260–266

[10] Li R, Wu X, Liu H, Wu J, Yin M . An efficient local search for the maximum edge weighted clique problem. IEEE Access, 2018, 6: 10743–10753

[11] Chu Y, Liu B, Cai S, Luo C, You H . An efficient local search algorithm for solving maximum edge weight clique problem in large graphs. Journal of Combinatorial Optimization, 2020, 39( 4): 933–954

[12] Cai S, Lin J. Fast solving maximum weight clique problem in massive graphs. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence. 2016, 568−574

[13] Jiang H, Li C-M, Manya F. An exact algorithm for the maximum weight clique problem in large graphs. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence. 2017, 830−838

[14] Xiong C, Liu H, Wu X, Deng N . A two-level meta-heuristic approach for the minimum dominating tree problem. Frontiers of Computer Science, 2023, 17( 1): 171406

[15] Pan S, Ma Y, Wang Y, Zhou Z, Ji J, Yin M, Hu S . An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem. Frontiers of Computer Science, 2023, 17( 4): 174326

[16] Hu S, Liu H, Wang Y, Li R, Yin M, Yang N . Towards efficient local search for the minimum total dominating set problem. Applied Intelligence, 2021, 51( 12): 8753–8767

[17] Gouveia L, Martins P . Solving the maximum edge-weight clique problem in sparse graphs with compact formulations. EURO Journal on Computational Optimization, 2015, 3( 1): 1–30

[18] Shimizu S, Yamaguchi K, Masuda S. Mathematical programming formulation for the maximum edge-weight clique problem. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (in Japanese), 2017, 100: 313−315

[19] Hosseinian S, Fontes D B, Butenko S . A nonconvex quadratic optimization approach to the maximum edge weight clique problem. Journal of Global Optimization, 2018, 72( 2): 219–240

[20] Shimizu S, Yamaguchi K, Masuda S. A branch-and-bound based exact algorithm for the maximum edge-weight clique problem. In Lee R, ed. Computational Science/Intelligence & Applied Informatics. Cham: Springer, 2018, 27−47

[21] San Segundo P, Coniglio S, Furini F, Ljubić I . A new branch-and-bound algorithm for the maximum edge-weighted clique problem. European Journal of Operational Research, 2019, 278( 1): 76–90

[22] Hosseinian S, Fontes D B M M, Butenko S . A lagrangian bound on the clique number and an exact algorithm for the maximum edge weight clique problem. INFORMS Journal on Computing, 2020, 32( 3): 747–762

[23] Shimizu S, Yamaguchi K, Masuda S . A maximum edge-weight clique extraction algorithm based on branch-and-bound. Discrete Optimization, 2020, 37: 100583

[24] Liu L, Xiao M, Zhou Y. A fast exact solver with theoretical analysis for the maximum edge-weighted clique problem. In: Proceedings of the 38th AAAI Conference on Artificial Intelligence. 2024, 20768−20776

[25] Marinelli F, Pizzuti A, Rossi F . LP-based dual bounds for the maximum quasi-clique problem. Discrete Applied Mathematics, 2021, 296: 118–140

[26] Chen X, Zhou Y, Hao J-K, Xiao M . Computing maximum k-defective cliques in massive graphs. Computers & Operations Research, 2021, 127: 105131

[27] Rossi R A, Ahmed N K . Coloring large complex networks. Social Network Analysis and Mining, 2014, 4( 1): 228

[28] Lin J, Cai S, Luo C, Su K. A reduction based method for coloring very large graphs. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence. 2017, 517−523

[29] Jiang H, Zhu D, Xie Z, Yao S, Fu Z-H. A new upper bound based on vertex partitioning for the maximum K-plex problem. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence. 2021, 1689−1696

RIGHTS & PERMISSIONS

Higher Education Press