Towards a General Recipe for Combinatorial Optimization with Multi-Filter GNNs

• URL: http://arxiv.org/abs/2405.20543v2
• Date: Sun, 24 Nov 2024 23:57:33 GMT
• Title: Towards a General Recipe for Combinatorial Optimization with Multi-Filter GNNs
• Authors: Frederik Wenkel, Semih Cantürk, Stefan Horoi, Michael Perlmutter, Guy Wolf,
• Abstract summary: We introduce GCON, a novel GNN architecture that leverages a complex filter bank and localized attention mechanisms to solve CO problems on graphs. GCON is competitive across all tasks and consistently outperforms other specialized GNN-based approaches.
• Score: 13.871690454501389
• License:
• Abstract: 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 GCON, a novel GNN architecture that leverages a complex filter bank and localized attention mechanisms 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 cut, minimum dominating set, and maximum clique problems in a unsupervised learning setting. GCON is competitive across all tasks and consistently outperforms other specialized GNN-based approaches, and is on par with the powerful Gurobi solver on the max-cut problem. We provide an open-source implementation of our work at https://github.com/WenkelF/copt.

Related papers

• Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems [0.0]
  Graph Neural Networks (GNNs) show promise for researchers in solving Combinatorial optimization (CO) problems. This study investigates the effectiveness of GNNs in solving the maximum independent set (MIS) problem.
  arXiv  Detail & Related papers  (2024-11-06T09:12:31Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  We introduce a novel algorithm, denoted hereafter as QRF-GNN, leveraging the power of GNNs to efficiently solve Combinatorial optimization (CO) problems. It relies on unsupervised learning by minimizing the loss function derived from QUBO relaxation. Results of experiments show that QRF-GNN drastically surpasses existing learning-based approaches and is comparable to the state-of-the-art conventionals.
  arXiv  Detail & Related papers  (2024-07-23T13:34:35Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• Combinatorial Optimization with Automated Graph Neural Networks [28.19349828026972]
  We present a new class of textbfAUTOmated textbfGNNs for solving NP-hard CO problems, namely textbfAutoGNP. The idea of AutoGNP is to use graph neural architecture search algorithms to automatically find the best GNNs for a given NP-hard optimization problem.
  arXiv  Detail & Related papers  (2024-06-05T02:43:41Z)
• Graph Q-Learning for Combinatorial Optimization [44.8086492019594]
  Graph Neural Networks (GNNs) have been shown to be effective at solving prediction and inference problems on graph data. We propose and demonstrate that GNNs can be applied to solve Combinatorial Optimization problems.
  arXiv  Detail & Related papers  (2024-01-11T01:15:28Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• Learning Branching Heuristics from Graph Neural Networks [1.4660170768702356]
  We first propose a new graph neural network (GNN) model designed using a probabilistic method. Our approach introduces a new way of applying GNNs towards enhancing the classical backtracking algorithm used in AI.
  arXiv  Detail & Related papers  (2022-11-26T00:01:01Z)
• Distributed Graph Neural Network Training: A Survey [51.77035975191926]
  Graph neural networks (GNNs) are a type of deep learning models that are trained on graphs and have been successfully applied in various domains. Despite the effectiveness of GNNs, it is still challenging for GNNs to efficiently scale to large graphs. As a remedy, distributed computing becomes a promising solution of training large-scale GNNs.
  arXiv  Detail & Related papers  (2022-11-01T01:57:00Z)
• Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with Heterophily [58.76759997223951]
  We propose a new metric based on von Neumann entropy to re-examine the heterophily problem of GNNs. We also propose a Conv-Agnostic GNN framework (CAGNNs) to enhance the performance of most GNNs on heterophily datasets.
  arXiv  Detail & Related papers  (2022-03-19T14:26:43Z)
• A Unified Lottery Ticket Hypothesis for Graph Neural Networks [82.31087406264437]
  We present a unified GNN sparsification (UGS) framework that simultaneously prunes the graph adjacency matrix and the model weights. We further generalize the popular lottery ticket hypothesis to GNNs for the first time, by defining a graph lottery ticket (GLT) as a pair of core sub-dataset and sparse sub-network.
  arXiv  Detail & Related papers  (2021-02-12T21:52:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.