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

2020/06/18 by Nikolaos Karalias, Karalias, Nikolaos, Andreas Loukas +1 · 21 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Graph Neural Networks #Data Quality and Management #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2006.10643

openalex publication_date 2020/06/18 · arxiv created 2021/03/07 · arxiv updated 2021/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Towards a General Framework for Predicting and Explaining the Hardness of Graph-based Combinatorial Optimization Problems using Machine Learning and Association Rule Mining
• Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis
• Diffusion-Augmented Markov Decision Processes for Maximum Entropy Reinforcement Learning
• ARM-Explainer -- Explaining and improving graph neural network predictions for the maximum clique problem using node features and association rule mining
• Unsupervised Graph Neural Network Framework for Balanced Multipatterning in Advanced Electronic Design Automation Layouts
• Geometric Algorithms for Neural Combinatorial Optimization with Constraints
• Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval
• BioBlobs: Unsupervised Discovery of Functional Substructures for Protein Function Prediction
• A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problem
• Smoothing Binary Optimization: A Primal-Dual Perspective
• Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking
• FORGE: Foundational Optimization Representations from Graph Embeddings
• Unsupervised Learning for the Elementary Shortest Path Problem
• PyG 2.0: Scalable Learning on Real World Graphs
• Binarizing Physics-Inspired GNNs for Combinatorial Optimization
• On Training-Test (Mis)alignment in Unsupervised Combinatorial Optimization: Observation, Empirical Exploration, and Analysis
• Primal-Dual Neural Algorithmic Reasoning
• Learning for Dynamic Combinatorial Optimization without Training Data
• G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning
• RIDGECUT: Learning Graph Partitioning with Rings and Wedges
• Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs
• Taming Treewidth DP with Modulators: A General Booster for Graph Heuristics

Related

• Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation
• Annealed Training for Combinatorial Optimization on Graphs
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks
• Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search