Document Open Access Logo

Efficient Minimum Weight Vertex Cover Heuristics Using Graph Neural Networks

Authors Kenneth Langedal, Johannes Langguth , Fredrik Manne, Daniel Thilo Schroeder

PDF
Thumbnail PDF

File

LIPIcs.SEA.2022.12.pdf
  • Filesize: 0.7 MB
  • 17 pages

Document Identifiers

Author Details

Kenneth Langedal
  • University of Bergen, Norway
Johannes Langguth
  • Simula Research Laboratory, Oslo, Norway
Fredrik Manne
  • University of Bergen, Norway
Daniel Thilo Schroeder
  • Simula Research Laboratory, Oslo, Norway

Funding

The work has benefited from the Experimental Infrastructure project eX3, which is financially supported by the Research Council of Norway under contract 270053.
  • Langedal, Kenneth: Supported by the Research Council of Norway under contract 303404.
  • Langguth, Johannes: Supported by the Research Council of Norway under contract 303404.
  • Schroeder, Daniel Thilo: Supported by the Research Council of Norway under contract 303404.

Cite AsGet BibTex

Kenneth Langedal, Johannes Langguth, Fredrik Manne, and Daniel Thilo Schroeder. Efficient Minimum Weight Vertex Cover Heuristics Using Graph Neural Networks. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SEA.2022.12

Abstract

Minimum weighted vertex cover is the NP-hard graph problem of choosing a subset of vertices incident to all edges such that the sum of the weights of the chosen vertices is minimum. Previous efforts for solving this in practice have typically been based on search-based iterative heuristics or exact algorithms that rely on reduction rules and branching techniques. Although exact methods have shown success in solving instances with up to millions of vertices efficiently, they are limited in practice due to the NP-hardness of the problem. We present a new hybrid method that combines elements from exact methods, iterative search, and graph neural networks (GNNs). More specifically, we first compute a greedy solution using reduction rules whenever possible. If no such rule applies, we consult a GNN model that selects a vertex that is likely to be in or out of the solution, potentially opening up for further reductions. Finally, we use an improved local search strategy to enhance the solution further. Extensive experiments on graphs of up to a billion edges show that the proposed GNN-based approach finds better solutions than existing heuristics. Compared to exact solvers, the method produced solutions that are, on average, 0.04% away from the optimum while taking less time than all state-of-the-art alternatives.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
  • Theory of computation → Randomized local search
Keywords
  • Minimum weighted vertex cover
  • Maximum weighted independent set
  • Graph neural networks
  • Reducing-peeling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Ferhat Ay, Manolis Kellis, and Tamer Kahveci. Submap: aligning metabolic pathways with subnetwork mappings. Journal of Computational Biology, 18(3):219-235, 2011. Google Scholar
  2. Ken Been, Eli Daiches, and Chee Yap. Dynamic map labeling. IEEE Transactions on Visualization and Computer Graphics, 12(5):773-780, 2006. Google Scholar
  3. Shaowei Cai, Wenying Hou, Jinkun Lin, and Yuanjie Li. Improving local search for minimum weight vertex cover by dynamic strategies. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pages 1412-1418. International Joint Conferences on Artificial Intelligence Organization, July 2018. URL: https://doi.org/10.24963/ijcai.2018/196.
  4. Shaowei Cai, Kaile Su, and Abdul Sattar. Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artificial Intelligence, 175(9-10):1672-1696, 2011. Google Scholar
  5. Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. arXiv preprint, 2021. URL: http://arxiv.org/abs/2102.09544.
  6. Lijun Chang, Wei Li, and Wenjie Zhang. Computing a near-maximum independent set in linear time by reducing-peeling. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1181-1196, 2017. Google Scholar
  7. Timothy A. Davis and Yifan Hu. The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software, 38(1), December 2011. URL: https://doi.org/10.1145/2049662.2049663.
  8. Alexander Gellner, Sebastian Lamm, Christian Schulz, Darren Strash, and Bogdan Zavalnij. Boosting data reduction for the maximum weight independent set problem using increasing transformations. In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), pages 128-142. SIAM, 2021. Google Scholar
  9. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016. Google Scholar
  10. Demian Hespe, Sebastian Lamm, Christian Schulz, and Darren Strash. WeGotYouCovered: The winning solver from the pace 2019 challenge, vertex cover track. In 2020 Proceedings of the SIAM Workshop on Combinatorial Scientific Computing, pages 1-11. SIAM, 2020. Google Scholar
  11. Tomokazu Imamura and Kazuo Iwama. Approximating vertex cover on dense graphs. In Symposium on Discrete Algorithms: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, volume 23, pages 582-589, 2005. Google Scholar
  12. Raka Jovanovic and Milan Tuba. An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem. Applied Soft Computing, 11(8):5360-5366, 2011. Google Scholar
  13. Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, 1972. Google Scholar
  14. Marek Karpinski and Alexander Zelikovsky. Approximating dense cases of covering problems. Citeseer, 1996. Google Scholar
  15. Asifullah Khan, Anabia Sohail, Umme Zahoora, and Aqsa Saeed Qureshi. A survey of the recent architectures of deep convolutional neural networks. Artificial Intelligence Review, 53(8):5455-5516, December 2020. URL: https://doi.org/10.1007/s10462-020-09825-6.
  16. Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint, 2016. URL: http://arxiv.org/abs/1609.02907.
  17. Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F Werneck. Finding near-optimal independent sets at scale. In 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 138-150. SIAM, 2016. Google Scholar
  18. Sebastian Lamm, Christian Schulz, Darren Strash, Robert Williger, and Huashuo Zhang. Exactly solving the maximum weight independent set problem on large real-world graphs. In 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX), pages 144-158. SIAM, 2019. Google Scholar
  19. Ruizhi Li, Shuli Hu, Shaowei Cai, Jian Gao, Yiyuan Wang, and Minghao Yin. NuMWVC: A novel local search for minimum weighted vertex cover problem. Journal of the Operational Research Society, 71(9):1498-1509, 2020. Google Scholar
  20. Yuanjie Li, Shaowei Cai, and Wenying Hou. An efficient local search algorithm for minimum weighted vertex cover on massive graphs. In Asia-Pacific Conference on Simulated Evolution and Learning, pages 145-157. Springer, 2017. Google Scholar
  21. Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. arXiv preprint, 2018. URL: http://arxiv.org/abs/1810.10659.
  22. Sk Md Abu Nayeem and Madhumangal Pal. Genetic algorithmic approach to find the maximum weight independent set of a graph. Journal of Applied Mathematics and Computing, 25(1):217-229, 2007. Google Scholar
  23. Bruno Nogueira, Rian G.S. Pinheiro, and Anand Subramanian. A hybrid iterated local search heuristic for the maximum weight independent set problem. Optimization Letters, 12(3):567-583, 2018. Google Scholar
  24. Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review, 65(6):386, 1958. Google Scholar
  25. Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008. Google Scholar
  26. Changbing Tang, Ang Li, and Xiang Li. Asymmetric game: A silver bullet to weighted vertex cover of networks. IEEE Transactions on Cybernetics, 48(10):2994-3005, 2017. Google Scholar
  27. Yang Wang, Zhipeng Lu, and Abraham P Punnen. A fast and robust heuristic algorithm for the minimum weight vertex cover problem. IEEE Access, 9:31932-31945, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact