Towards a General GNN Framework for Combinatorial Optimization

Autor:	Wenkel, Frederik, Cantürk, Semih, Perlmutter, Michael, Wolf, Guy
Rok vydání:	2024
Předmět:	Computer Science - Machine Learning Computer Science - Artificial Intelligence Computer Science - Discrete Mathematics 68T07 (Primary) 68T20 90C35 05C62 (Secondary) F.2.2 I.2.6
Druh dokumentu:	Working Paper
Popis:	Graph neural networks (GNNs) have achieved great success for a variety of tasks such as node classification, graph classification, and link prediction. However, the use of GNNs (and machine learning more generally) to solve combinatorial optimization (CO) problems is much less explored. Here, we introduce a novel GNN architecture which leverages a complex filter bank and localized attention mechanisms designed to solve CO problems on graphs. We show how our method differentiates itself from prior GNN-based CO solvers and how it can be effectively applied to the maximum clique, minimum dominating set, and maximum cut problems in a self-supervised learning setting. In addition to demonstrating competitive overall performance across all tasks, we establish state-of-the-art results for the max cut problem. Comment: 15 pages, 1 figure
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2405.20543 Zobrazit plný text záznamu View this record from Arxiv