Course contentsShow
← Machine Learning and Deep Learning
Lesson 2531 of 3,53854. Graph Neural NetworksFree lesson

Combinatorial Optimization with GNNs

Using graph neural networks to solve NP-hard problems like TSP, graph coloring, and satisfiability.

Combinatorial Optimization with GNNs

You'll learn how graph neural networks can tackle notoriously hard optimization problems by learning heuristics from graph structure.

The Challenge of NP-Hard Problems

Combinatorial optimization problems like the Traveling Salesman Problem (TSP), graph coloring, and Boolean satisfiability (SAT) are NP-hard—meaning no known algorithm solves them efficiently for all cases. Traditional approaches use hand-crafted heuristics or exact solvers that become impractically slow as problem size grows.

How GNNs Enter the Picture

GNNs offer a learned approach: they can discover patterns in problem structure by processing graphs directly. For TSP, cities become nodes and distances become edges. For graph coloring, the graph itself is the input. For SAT, variables and clauses form a bipartite graph.

The key insight: these problems have underlying graph structure, and message passing can capture local constraints and global patterns simultaneously.

Learning to Optimize

Instead of solving problems from scratch, GNNs learn to:

  • Predict solution quality: Score partial solutions to guide search
  • Generate heuristics: Output node/edge probabilities indicating which choices are promising
  • Refine iteratively: Apply multiple message passing layers to improve solutions

For example, in TSP, a GNN might output edge probabilities indicating which city-to-city connections belong in the optimal tour. You train it on many TSP instances, and it learns structural patterns that generalize.

Why It Works

GNNs leverage permutation invariance—the solution doesn't depend on how you label nodes—and neighborhood aggregation captures local constraint satisfaction. They won't always find the global optimum, but they can find good solutions fast, making them practical for large-scale real-world problems.

Key Takeaway: GNNs transform combinatorial optimization from hand-crafted heuristics to learned, graph-structured reasoning, offering scalable approximations to NP-hard problems by exploiting their inherent graph nature.