Source-linked AI summary
Combinatorial optimization and reasoning with graph neural networks
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, Petar Veličković
TL;DR
Combinatorial optimization traditionally solved related problem instances in isolation, despite practical structure shared across data distributions. This survey synthesizes GNN applications as direct CO solvers, exact-solver enhancements, and algorithmic reasoners, while examining extrapolation and architectural limitations. It concludes that GNNs offer a broad but constrained framework for CO, with scalability and approximation limits remaining important boundaries.
Problem
CO methods traditionally focused on isolated instances, while practical applications often require handling related distributions, graph structure, and out-of-distribution inputs.
Method
The paper provides a structured conceptual survey of GNNs for primal and dual CO methods, algorithmic reasoning, and raw-input approaches.
Results
The survey reports that GNNs have been applied both to predict CO solutions and to enhance existing solvers, including constraint programming, decision diagrams, and logic solving.
Takeaways & Limitations
GNN-based algorithmic reasoning can support data-efficient application of classical combinatorial algorithms to natural inputs and can improve out-of-distribution behavior when architectures are algorithmically aligned.
Takeaways & Limitations
Stronger GNN variants can overcome basic graph-distinguishability limitations but typically do not scale to large graphs, while some GNNs achieve suboptimal approximation ratios or lack sufficient computational capacity.
Abstract
from arXiv · showhide
Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolation, ignoring that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning, especially graph neural networks (GNNs), as a key building block for combinatorial tasks, either directly as solvers or by enhancing exact solvers. The inductive bias of GNNs effectively encodes combinatorial and relational input due to their invariance to permutations and awareness of input sparsity. This paper presents a conceptual review of recent key advancements in this emerging field, aiming at optimization and machine learning researchers.
1. Introduction
Combinatorial optimization addresses hard, graph-structured problems whose practical instances often share patterns, motivating machine-learning methods that generalize across related data. This survey reviews GNNs as direct solvers, exact-solver components, and algorithmic reasoners while identifying their challenges and limitations.
- Motivation: CO problems are hard discrete optimization tasks with applications including vehicle routing and scheduling, yet practical instances often exhibit specific shared characteristics or patterns.Historically, methods focused on solving individual instances.
- Motivation: Graphs are central to CO because many problems naturally encode interactions between variables and constraints as sparse network structures.The TSP and vehicle-routing problems are prominent graph-based examples.
- Challenges: GNN-based CO methods must handle permutation invariance, sparsity, structural patterns, side information, scalability, data efficiency, and out-of-distribution transfer.The survey highlights a trade-off among scalability, expressivity, and generalization.
- GNNs: GNNs aggregate neighboring-node features into learned representations that are invariant or equivariant by design and can encode graph structures useful for CO.They are trained end-to-end against a loss function using first-order optimization.
- Survey scope: The survey examines GNNs that predict solutions, enhance existing solvers, and support end-to-end algorithmic reasoning across diverse CO settings.It covers both heuristic and exact algorithms and surveys recent algorithmic reasoners.
- Beyond classical algorithms: Raw real-world inputs often require costly, error-prone feature engineering to induce the graph used by classical CO methods, motivating end-to-end approaches from raw data to solving.The survey also identifies shortcomings and open research directions.
2. Preliminaries
The preliminaries introduce notation and the formal background needed for combinatorial optimization, machine-learning regimes, and graph neural networks.
- This section establishes notation and formal background for combinatorial optimization, machine-learning regimes, and GNNs.
2.1 Notation
The notation defines finite sets, graphs, labeled graphs, neighborhoods, and graph isomorphism through edge- and label-preserving mappings.
- For a finite set S, 2^S denotes its power set; [n] denotes {1, . . . , n} for n ≥ 1, and {{. . . }} denotes a multiset.
- A graph G=(V,E) consists of finite nodes and edges, while a labeled graph adds a label function over nodes and edges.The neighborhood N(v) contains nodes adjacent to v.
- Two graphs are isomorphic when an edge-preserving bijection maps one node set to the other, with corresponding labels preserved for labeled graphs.
2.2 Combinatorial Optimization
Combinatorial optimization selects a minimum-cost feasible subset from a finite ground set, with feasibility encoded by a family of allowed solutions; the TSP is a canonical example.
- A CO instance is represented by a finite ground set, a feasible-solution family, and a cost function over subsets.The formal tuple is (Ω, F, w), with feasible solutions drawn from F.
- The optimal solution S* is a feasible element minimizing the cost function over F.The formulation uses minimization without loss of generality.
- The decision version asks whether some feasible solution has cost at most a specified threshold k.
- Traveling Salesperson Problem: The TSP seeks a minimum-cost cycle that visits every graph node exactly once, with a corresponding threshold decision problem.
Example 1 (Traveling Salesperson Problem)
The TSP is formulated on a complete directed graph with edge costs, seeking a minimum-cost permutation of nodes that defines the tour.
- The input is a complete directed graph whose edges carry costs.
- The output is a permutation of the nodes representing a candidate tour.
- The selected permutation minimizes the total tour cost over all possible permutations.
- TSP instances can be solved in practice using integer linear programs and associated algorithms such as branch-and-cut.
2.3 General Optimization Frameworks: ILPs, SAT, and Constrained Problems
The section introduces linear, integer, mixed-integer, satisfiability, and constraint-based frameworks for modeling combinatorial optimization problems and explains their associated solution concepts.
- Linear programs minimize a linear objective over a polyhedral feasible set, but continuous variables cannot encode general combinatorial feasibility.
- Integer linear programs add integrality constraints, enabling discrete modeling and solution through branch-and-bound methods.
- The TSP ILP uses binary edge-selection variables and positive travel costs to encode tours and optimize their total cost.
- The TSP constraints enforce exactly one incoming and outgoing edge per city and eliminate subtours.
- Mixed-integer programs combine integer and continuous variables in a constrained linear optimization model.
- SAT asks whether a Boolean assignment satisfies a propositional formula, and its optimization variants can maximize satisfied soft constraints.
Definition 3 (SAT)
The section surveys SAT, constraint-based formulations, and major algorithmic frameworks used to solve combinatorial optimization problems, from incomplete heuristics to exact methods.
- Definition 3 (SAT): SAT is an NP-complete decision problem whose modern solvers can handle industrial-scale instances and practical applications.
- Constraint satisfaction and optimization: Constraint satisfaction assigns values from variable domains while satisfying all specified constraints.
- Constraint satisfaction and optimization: Constraint optimization extends CSPs with an objective and permits nonlinear objectives and constraints without fixed underlying assumptions.
- Exact methods: Exact ILP methods combine LP relaxations, cutting planes, and branching to prove optimality or infeasibility.
- Local search and metaheuristics: Local search explores neighboring solutions incompletely and therefore provides no optimality guarantee.
- Approximation algorithms: Approximation algorithms provide feasible solutions with guarantees on their distance from optimality, including schemes parameterized by ǫ.
2.4 Machine Learning
The section reviews supervised, unsupervised, reinforcement, and imitation learning, then motivates GNNs for graph-structured combinatorial optimization.
- Supervised learning: Supervised learning fits model parameters using labeled examples by minimizing empirical loss with optional regularization.
- Unsupervised learning: Unsupervised learning learns representative data features without target values by minimizing a loss dependent on input samples.
- Reinforcement learning: Reinforcement learning trains an agent to maximize discounted cumulative rewards through actions and state transitions.
- Imitation learning: Imitation learning trains sequential decision policies by imitating expert behavior, either offline or through online expert queries.
2.5 Graph Neural Networks
GNNs represent graph nodes by iteratively aggregating neighboring features, using learnable transformations and permutation-invariant aggregation functions. These representations are trained end-to-end for downstream prediction tasks.
- Each GNN layer updates a node’s features using information aggregated from its neighborhood.The aggregation and nonlinear transformation are repeated across layers.
- The basic update uses parameter matrices to transform features and a component-wise nonlinear function such as a sigmoid or ReLU.
- Neighborhood aggregation can use permutation-invariant differentiable functions, while node and neighborhood representations are merged through learnable functions.
- The aggregation and merge parameters are optimized end-to-end, typically with stochastic gradient descent alongside a classification or regression network.
- Biases are omitted from the presentation for clarity.
3. GNNs for Combinatorial Optimization: The State of the Art
GNNs support both sides of combinatorial optimization: finding good feasible solutions and certifying optimality or infeasibility. They can represent problem instances, iterative algorithm states, or both, often alongside handcrafted features.
- GNNs can serve both the primal goal of finding good feasible solutions and the dual goal of certifying optimality or infeasibility.
- For these tasks, GNNs may represent problem instances, states of iterative algorithms, or both.
3.1 On the Primal Side: Finding Feasible Solutions
The primal literature uses GNNs to obtain high-quality feasible solutions, either directly or by guiding search and exact solvers. Approaches span supervised, unsupervised, reinforcement-learning, and hybrid methods, with constraint handling remaining important.
- Motivation: Primal methods prioritize quickly obtaining high-quality feasible solutions when optimality or approximation guarantees are unnecessary or slower than practical decision-making allows.Early solutions can support manual analysis, early solver termination, or warm starts.
- Motivation: Standalone heuristics can provide warm starts to exact solvers or high-quality initial solutions for local search.
- Supervised Learning: Supervised GNN approaches learn from optimal or near-optimal training solutions, but single-solution labels are inherently limited when combinatorial problems have multiple optima.
- Supervised Learning: Some methods combine GNN predictions with greedy decoding, beam search, tree search, or local search to construct valid solutions.
- Graph matching and related problems: GNN-based graph matching methods learn node embeddings and similarity scores for comparing or aligning graphs.
- Unsupervised Learning: Unsupervised methods can produce integral solutions that satisfy problem-specific constraints with high probability and provide theoretical guarantees.
3.2 On the Dual Side: Proving Optimality
On the dual side, GNNs guide solver components that establish optimality or bounds, especially branching decisions in branch-and-bound. Reported advances include improved generalization and solving time, alongside inference-cost and credit-assignment challenges.
- Dual methods use relaxations and learned solver components to prove optimality, infeasibility, or bounded optimality gaps.
- Integer programming: Branch-and-bound recursively partitions feasible regions and computes relaxations, with variable selection strongly affecting execution time through the search-tree size.
- Integer programming: GNNs currently represent the state of the art for learning branch-and-bound variable-selection policies, including imitation of computationally expensive strong branching.
- Integer programming: Hybrid GNN–MLP branching improves performance on CPU-only hardware, while scalable training has produced policies performing well on the heterogeneous MIPLIB benchmark at significant computational cost.
- Integer programming: Imitation learning cannot outperform its expert strong branching policy, motivating reinforcement-learning alternatives when the expert performs poorly on some problem families.
- Integer programming: Large branch-and-bound trees make reinforcement-learning credit assignment difficult, although tree structure can simplify it and accelerate convergence.
- Integer programming: GNNs have also been applied to cut selection, variable-value prediction, node exploration, and solver warm starts beyond variable selection.
- Constraint programming: In constraint programming, GNN policies or action-value functions can guide value selection within backtracking search, but generic tripartite representations may become prohibitively large.
3.3 Algorithmic Reasoning
Algorithmic reasoning aligns neural modules with classical algorithmic operations to improve out-of-distribution execution, then transfers learned processors to natural inputs. The surveyed blueprint combines algorithmic alignment, latent-space processing, and learned raw-input encoders, while noting practical and methodological limitations.
- Algorithmic alignment: Algorithmic reasoning builds neural networks whose modules and control flow align with invariants and operations of classical algorithms.This paradigm supports studying neural execution and applying algorithmic structure to combinatorial problems over natural, noisy inputs.
- Algorithmic alignment: Out-of-distribution execution remains difficult because neural networks often lose predictive power when test graphs exceed training sizes.This makes extrapolation a central requirement for reasoning systems intended to handle plausible inputs beyond their training distribution.
- Algorithmic alignment: Algorithmic alignment can improve extrapolation by making neural components learn simpler functions that match the target algorithm’s computation.For Bellman-Ford, an edge-wise linear update followed by minimization motivates matching message functions and aggregation to those operations.
- Reasoning on natural inputs: A pretrained processor can be frozen and connected to learned encoders and decoders, yielding an end-to-end differentiable pipeline from raw inputs to algorithmic outputs.The processor operates through matrix multiplications in a high-dimensional latent space, while the raw encoder learns the mapping into the algorithmic input space.
- Reasoning on natural inputs: Neural algorithmic cores have improved data efficiency in reinforcement learning and, in challenging environments, can surpass a hard-coded hybrid pipeline.The VI executor substantially improves a model-free baseline, while XLVIN illustrates how learned algorithmic cores can apply classical procedures to natural inputs.
4. Limitations and Research Directions
The survey identifies limitations in GNN-based combinatorial optimization, spanning data quality, graph expressivity, generalization, computational cost, and support for natural inputs. It proposes research directions centered on understanding deployment trade-offs, extending reasoning primitives, and integrating GNNs into practical CO pipelines.
- Limitations: GNNs cannot distinguish some non-isomorphic graphs, while stronger expressive variants typically do not scale to large graphs.The limitation follows from the 1-dimensional Weisfeiler-Leman upper bound and creates indistinguishable MIP instances.
- Limitations: Over-smoothing and bottleneck effects can prevent GNNs from capturing global or long-range information needed by problems such as shortest path.Empirical architectural remedies exist, but their theoretical understanding remains limited.
- Limitations: Large inference costs can erase solver speedups when GNN decisions are repeated thousands of times inside sequential CO procedures.One proposed mitigation is to run the GNN once and use an MLP with its embedding for subsequent decisions.
- Limitations: GNN performance metrics may be over-inflated because polynomial-time generators for NP-hard problems can sample easier subproblems.The practical translation of this result remains unclear because real-world instances are rarely worst-case.
- Research Directions: Open directions include characterizing when GNNs speed up solvers, adding missing reasoning primitives, supporting natural inputs, and simplifying solver integration.The survey highlights trade-offs among expressivity, scalability, and generalization, alongside the need for practical modeling frameworks.
5. Implementation Frameworks
Implementation frameworks for GNN-based CO are developing, but integrating machine learning into state-of-the-art solvers remains cumbersome. Existing libraries provide reusable GNN models and CO data-generation or modeling components.
- Available Libraries: Open-source libraries such as PyTorch Geometric and Deep Graph Library support implementation of custom GNN architectures.These libraries provide readily available models from the literature.
- CO Tooling: CO-oriented libraries and CLRS provide components intended to simplify machine learning workflows for combinatorial optimization.CLRS includes relevant data-generation pipelines and several popular literature models.
6. Conclusions
The paper surveys recent applications of GNNs in combinatorial optimization, covering direct solution methods, solver enhancement, and algorithmic reasoning. It also synthesizes limitations and open challenges to guide future research and practice.
- Scope: The survey organizes GNN applications into primal approaches for finding solutions, dual approaches for proving optimality, and algorithmic reasoning approaches.It also introduces CO, machine learning regimes, and GNNs for readers across optimization, operations research, and machine learning.
- Outlook: The paper identifies shortcomings and critical challenges intended to stimulate research on GNN-based CO.The authors present the survey as a handbook of graph representation learning methods, perspectives, and limitations for practitioners.
- Impact: The review aims to support novel research and future avenues in the emerging intersection of graph representation learning and combinatorial optimization.Its intended audience includes CO, operations research, and machine learning researchers and practitioners.