Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs

• URL: http://arxiv.org/abs/2006.10643v4
• Date: Sun, 7 Mar 2021 20:10:53 GMT
• Title: Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
• Authors: Nikolaos Karalias, Andreas Loukas
• Abstract summary: This work proposes an unsupervised learning framework for Combinatorial optimization problems on graphs. Inspired by Erdos' probabilistic method, we use a neural network to parametrize a probability distribution over sets. We show that when the network is optimized w.r.t. a suitably chosen loss, the learned distribution contains, with controlled probability, a low-cost integral solution.
• Score: 35.14404918074861
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial optimization problems are notoriously challenging for neural networks, especially in the absence of labeled instances. This work proposes an unsupervised learning framework for CO problems on graphs that can provide integral solutions of certified quality. Inspired by Erdos' probabilistic method, we use a neural network to parametrize a probability distribution over sets. Crucially, we show that when the network is optimized w.r.t. a suitably chosen loss, the learned distribution contains, with controlled probability, a low-cost integral solution that obeys the constraints of the combinatorial problem. The probabilistic proof of existence is then derandomized to decode the desired solutions. We demonstrate the efficacy of this approach to obtain valid solutions to the maximum clique problem and to perform local graph clustering. Our method achieves competitive results on both real datasets and synthetic hard instances.

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)
• 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)
• 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)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation [19.582494782591386]
  This work proposes an unsupervised learning framework for optimization (CO) problems. Our key contribution is the observation that if the relaxed objective satisfies entry-wise concavity, a low optimization loss guarantees the quality of the final integral solutions. In particular, this observation can guide the design of objective models in applications where the objectives are not given explicitly while requiring being modeled in prior.
  arXiv  Detail & Related papers  (2022-07-13T06:44:17Z)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  We propose a radically different approach in that no data is required for training the neural networks that produce the solution. In particular, we reduce the optimization problem to a neural network and employ a dataless training scheme to refine the parameters of the network such that those parameters yield the structure of interest.
  arXiv  Detail & Related papers  (2022-03-15T19:21:31Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  Semi-supervised learning (SSL) over graph-structured data emerges in many network science applications. To efficiently manage learning over graphs, variants of graph neural networks (GNNs) have been developed recently. Despite their success in practice, most of existing methods are unable to handle graphs with uncertain nodal attributes. Challenges also arise due to distributional uncertainties associated with data acquired by noisy measurements. A distributionally robust learning framework is developed, where the objective is to train models that exhibit quantifiable robustness against perturbations.
  arXiv  Detail & Related papers  (2021-10-20T14:23:54Z)
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks [0.0]
  We show how graph neural networks can be used to solve optimization problems. We find that the neural network performs on par or outperforms existing solvers.
  arXiv  Detail & Related papers  (2021-07-02T16:54:35Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)
• Optimizing Wireless Systems Using Unsupervised and Reinforced-Unsupervised Deep Learning [96.01176486957226]
  Resource allocation and transceivers in wireless networks are usually designed by solving optimization problems. In this article, we introduce unsupervised and reinforced-unsupervised learning frameworks for solving both variable and functional optimization problems.
  arXiv  Detail & Related papers  (2020-01-03T11:01:52Z)

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.