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

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.

References in corpus (23)

• Adam: A Method for Stochastic Optimization
• Fast Graph Representation Learning with PyTorch Geometric
• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• Learning Combinatorial Optimization Algorithms over Graphs
• Social Structure of Facebook Networks
• How Powerful are Graph Neural Networks?
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Benchmarking Graph Neural Networks
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Learning a SAT Solver from Single-Bit Supervision
• A Survey on The Expressive Power of Graph Neural Networks
• Generalization and Representational Limits of Graph Neural Networks
• Learn to Design the Heuristics for Vehicle Routing Problem
• Can Graph Neural Networks Count Substructures?
• Capacity Releasing Diffusion for Speed and Locality
• On Learning Paradigms for the Travelling Salesman Problem
• How hard is to distinguish graphs with graph neural networks?
• Discriminative structural graph classification
• Graph Neural Networks for Maximum Constraint Satisfaction
• It's Not What Machines Can Learn, It's What We Cannot Teach
• PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers
• A Short Introduction to Local Graph Clustering Methods and Software

Cited by in corpus (5)

• Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networks
• Learning Markov Random Fields for Combinatorial Structures via Sampling through Lovász Local Lemma
• Adversarial Deep Learning for Online Resource Allocation
• Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks
• An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem