Research map / Graph learning / Graph algorithms and clustering

Learning to Explore and Exploit with GNNs for Unsupervised Combinatorial Optimization

ICLR 2025 · Graph learning › Graph algorithms and clustering · approach: Neural combinatorial optimization on graphs

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes X²GNN, an unsupervised GNN-based learned heuristic for combinatorial optimization that combines exploration and exploitation to overcome limited search capability of prior learning-based heuristics.

Problem

Learning-based heuristics for NP-hard combinatorial optimization problems often have limited search capability when solving CO problems without supervision.

Approach

An unsupervised explore-and-exploit GNN (X²GNN) that is designed to explicitly balance exploration and exploitation during search, rather than relying on a single greedy-style decoding of a GNN's output.

Closest papers by meaning

• What’s Wrong with Deep Learning in Tree Search for Combinatorial Optimization (ICLR 2022 · similarity 0.91)
• COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.91)
• Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.89)
• GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.88)
• Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.88)
• Towards General Algorithm Discovery for Combinatorial Optimization: Learning Symbolic Branching Policy from Bipartite Graph (ICML 2024 · similarity 0.88)