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.

图神经网络在解决节点分类、图分类和链接预测等任务方面取得了巨大成功。然而，将图神经网络和机器学习应用于组合优化问题的研究相对较少。本文引入了一种新颖的图神经网络架构，利用复杂的滤波器组和局部化注意机制来解决图上的组合优化问题。我们展示了我们的方法如何与以往基于图神经网络的组合优化求解器区别开来，并在自监督学习设置下有效地应用于最大团、最小支配集和最大割问题。除了证明在各项任务上具有竞争力的整体性能外，我们还为最大割问题建立了最新的研究结果。