PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Combinatorial Optimization Algorithms over Graphs

Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, Le Song

arXiv:1704.01665v4cs.LGstat.ML

TL;DR

The paper addresses whether effective heuristics for recurring NP-hard graph optimization instances can be learned instead of designed manually. It combines reinforcement learning with graph embedding in a greedy meta-algorithm, and reports effective, scalable heuristics across Minimum Vertex Cover, Maximum Cut, and Traveling Salesman.

  • Problem

    Recurring graph optimization instances share structure but vary in data, motivating the question of whether better heuristics can be learned for unseen instances from a distribution D.

  • Method

    The framework combines reinforcement learning with a graph embedding network that determines actions while a greedy policy incrementally constructs solutions.

  • Results

    The learned heuristics are effective across Minimum Vertex Cover, Maximum Cut, and Traveling Salesman, including real-world datasets and graphs larger than the training graphs.

  • Takeaways & Limitations

    The framework is presented as a promising tool for automatically designing graph heuristics and discovering new algorithms.

  • Takeaways & Limitations

    The formulation assumes that the instance distribution D, helper function h, termination criterion t, and cost function c are given.

Abstract

from arXiv · show

The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error. Can we automate this challenging, tedious process, and learn the algorithms instead? In many real-world applications, it is typically the case that the same optimization problem is solved again and again on a regular basis, maintaining the same problem structure but differing in the data. This provides an opportunity for learning heuristic algorithms that exploit the structure of such recurring problems. In this paper, we propose a unique combination of reinforcement learning and graph embedding to address this challenge. The learned greedy policy behaves like a meta-algorithm that incrementally constructs a solution, and the action is determined by the output of a graph embedding network capturing the current state of the solution. We show that our framework can be applied to a diverse range of optimization problems over graphs, and learns effective algorithms for the Minimum Vertex Cover, Maximum Cut and Traveling Salesman problems.

1 Introduction

The paper asks whether heuristics for recurring graph optimization problems can be learned from instance distributions rather than designed through specialized trial-and-error. It combines reinforcement learning with graph embeddings to learn greedy meta-algorithms that generalize across graph problems and sizes.

  • Motivation: Recurring instances share combinatorial structure while differing mainly in data, creating an opportunity to learn reusable heuristics.This pattern appears in applications such as social-network influence targeting and daily package routing.
  • Problem: The central question is whether better heuristics can be learned for unseen instances sampled from a distribution D.
  • Approach: The framework combines reinforcement learning and graph embedding, with a policy that incrementally constructs solutions from the current solution state.
  • Approach: Structure2vec represents graph-aware node context, allowing the policy to distinguish nodes by usefulness and generalize across instance sizes.This contrasts with graph-agnostic sequence-to-sequence approaches.
  • Training: Fitted Q-learning trains the greedy policy to optimize the original problem objective while handling delayed rewards in a data-efficient way.Graph embeddings are updated after each greedy step to reflect the partial solution.
  • Results: Across Minimum Vertex Cover, Maximum Cut, and Traveling Salesman, the learned heuristics are effective and retain effectiveness on graphs larger than those used for training.

2 Common Formulation for Greedy Algorithms on Graphs

The paper expresses diverse graph optimization heuristics through a common greedy formulation: sequentially add nodes using a learned or specified evaluation function while maintaining feasibility and stopping at a problem-specific criterion.

  • Problem instances: The framework covers Minimum Vertex Cover, Maximum Cut, and Traveling Salesman on weighted graphs.These problems respectively minimize covered vertices, maximize cut weight, and minimize tour length.
  • Common greedy pattern: A greedy algorithm sequentially adds nodes to a partial solution S by maximizing an evaluation function Q defined in the current solution context.
  • State representation: The partial solution is an ordered node list, with candidate nodes and binary node features indicating membership in S.
  • Greedy update: After selecting v*, the algorithm appends it to S and repeats until a termination criterion is satisfied.
  • Problem-specific components: Different problems are represented through problem-specific helper functions, cost functions, and termination criteria, while D, h, t, and c are assumed given.
  • TSP specialization: For TSP, an insertion helper places each new node where it causes the smallest increase in tour length.

3 Representation: Graph Embedding

The representation uses structure2vec to embed each node in the context of the current partial solution and graph topology. These embeddings parameterize the evaluation function that reinforcement learning trains without graph-level labels.

  • State-aware evaluation: The evaluation function must summarize a tagged graph state and estimate the value of adding a candidate node.Nodes in the partial solution receive binary tags, while graph edges encode connectivity.
  • Structure2vec: Structure2vec recursively computes a p-dimensional embedding μ_v for every node from the graph and current partial solution.
  • Message passing: Synchronous embedding updates propagate node features through graph neighbors using a nonlinear mapping F.
  • Message passing: After T iterations, each node embedding contains information from its T-hop neighborhood as determined by topology, features, and F.The paper illustrates two embedding iterations in Figure 1.
  • Architecture: Neighbor summation aggregates local information in a way that is invariant to permutations of neighboring nodes.The model uses ReLU nonlinearities and can incorporate additional node information.
  • Evaluation function: The learned embeddings define the parameterized evaluation function bQ for candidate actions.The network parameters Θ include seven parameter groups, and T is usually small, such as T = 4.
  • Training: The embedding parameters are trained end-to-end with reinforcement learning because graph-level training labels are unavailable.

4 Training: Q-learning

The framework formulates graph optimization as reinforcement learning, representing states and actions through graph embeddings and learning a Q-function for greedy solution construction. It combines n-step Q-learning with fitted Q-iteration to address delayed rewards and improve neural-network training.

  • Reinforcement-learning formulation: The reinforcement-learning formulation represents graph states and actions through p-dimensional embeddings, allowing the learned Q-function to operate across graphs of different sizes.States encode partial solutions, while actions correspond to selecting nodes not yet included in the current state.
  • Reinforcement-learning formulation: The reward is the change in the cost function after adding an action, so cumulative terminal reward matches the objective value of the resulting solution.The framework initializes the empty-state cost at zero and defines terminal cumulative reward as the final objective value.
  • Reinforcement-learning formulation: A deterministic greedy policy selects the available action with the highest learned Q-value, incrementally adding nodes to the partial solution.The graph-embedding parameterization approximates the optimal Q-function for each of the three optimization problems.
  • Learning algorithm: The parameters of the graph-embedding Q-function are learned end-to-end using n-step Q-learning and fitted Q-iteration.The training procedure uses experience collected across episodes and updates parameters with stochastic gradient descent over replayed tuples.
  • Learning algorithm: n-step Q-learning addresses delayed rewards by including multiple future rewards in its target, avoiding the myopic behavior of a one-step update.In these problems, the objective value may only become apparent after many node additions.
  • Learning algorithm: Fitted Q-iteration updates the Q-function using random samples from an experience dataset, which is reported to support faster convergence with neural-network function approximators.Episodes populate replay memory with state, action, multi-step reward, and successor-state tuples before stochastic-gradient updates.

5 Experimental Evaluation

Experiments evaluate S2V-DQN against learned, approximation, heuristic, and solver-based methods on synthetic and realistic graph instances. The method generalizes from small training graphs to much larger test graphs, while balancing solution quality and runtime and revealing interpretable heuristics.

  • Experimental setup: The evaluation uses ER and BA graphs for MVC and MAXCUT, DIMACS-based 2-D TSP instances, and solver-derived reference solutions.Testing reports results on 1000 held-out graphs, with approximation ratios measured against the best solver solution found within one hour.
  • Generalization to larger instances: S2V-DQN achieves strong approximation ratios and remains effective when trained on 50–100-node graphs and tested on graphs with up to 1200 nodes.The reported larger-graph results use average approximation ratios over 1000 test instances.
  • Scalability: On MVC graphs with 1200 nodes, S2V-DQN finds a solution within 11 seconds using one GPU, with an approximation ratio of 1.0062.Its construction has polynomial complexity O(k|E|), where k is the number of greedy steps.
  • Runtime-quality trade-off: On MVC, S2V-DQN is slightly slower than approximation algorithms but obtains a much better approximation ratio than those methods.Compared with CPLEX, its solutions can be higher quality at similar or shorter times, although GPU use makes some comparisons imperfect.
  • Real-world datasets: S2V-DQN significantly outperforms competing methods on realistic MVC, MAXCUT, and TSP instances.The realistic-data results are summarized in Table 3 using average approximation ratios.
  • Interpreting learned algorithms: The learned heuristics differ by problem structure: MVC balances node degree against remaining-graph connectivity, while MAXCUT avoids cancelling existing cut edges.These behaviors were interpreted as new, intuitive algorithms that had not previously been analyzed.

6 Conclusions

The paper presents an end-to-end framework combining graph embedding and reinforcement learning to automatically design greedy heuristics for hard graph optimization problems. Experiments across multiple problem types, graph types, and graph sizes support the effectiveness of the learned heuristics.

  • The framework automatically designs greedy heuristics for hard combinatorial optimization problems on graphs.
  • It combines deep graph embedding with reinforcement learning to learn greedy heuristics.
  • The framework also addresses Set Covering, although Set Covering is not itself a graph problem but can be formulated as one.
  • For Set Covering, the learned policy adds candidate nodes until all nodes in U are covered, receiving reward -1 at each action.

C Experimental Results on Realistic Data

Experiments on realistic and publicly available instances evaluate S2V-DQN across MVC, MAXCUT, TSP, and SCP. The method achieves near-optimal or best-comparing performance on the reported benchmarks.

  • The realistic-data experiments cover MVC and SCP using MemeTracker, MAXCUT using physics benchmarks, and TSP using transportation benchmarks.
  • Minimum Vertex Cover: 1.002: S2V-DQN finds a 474-node MVC cover versus the 473-node optimum, outperforming MVCApprox and MVCApprox-Greedy.The competing approximation ratios are 1.408 and 1.222, respectively.
  • Maximum Cut: S2V-DQN finds near-optimal MAXCUT solutions, including optimal solutions on 3/10 instances, and outperforms competing methods.
  • Traveling Salesman Problem: 1.05: S2V-DQN has the smallest average TSP approximation ratio and finds the best tour on all but 6 instances.
  • Set Covering Problem: 1.001: S2V-DQN’s average SCP approximation ratio is slightly behind LP’s 1.0009 and ahead of Greedy’s 1.03.

D.4 Experiment Configuration of S2V-DQN

The configuration section describes how experiments tune S2V-DQN and organize generalization evaluations across problem types, graph distributions, and graph sizes. The reported MVC configuration includes ER and BA graph settings, while TSP evaluations use random and clustered graphs.

  • S2V-DQN hyperparameters are tuned on graphs with fewer than 50 nodes and then fixed for larger graphs.
  • The generalization evaluations include MVC on ER and BA graphs and MAXCUT on ER and BA graphs.
  • The TSP generalization evaluations include random and clustered graphs.
  • Figure D.1 reports approximation ratios on 1000 test graphs, with training and testing graphs generated from the same distribution.

D.5 Stabilizing the training of S2V-DQN

Training stabilization uses learning-rate decay, exploration annealing, problem-specific discount factors, reward normalization, and reward-sign adjustments for TSP insertion. The authors note that reward design remains challenging, while convergence is reported for MVC, MAXCUT, and SCP.

  • The learning rate decays exponentially, while exploration probability ϵ is annealed linearly from 1.0 to 0.05.
  • The discount factor is 1.0 for MVC, MAXCUT, and SCP, but 0.1 for TSP.
  • Intermediate rewards are normalized by the maximum number of nodes, and Q-learning separates actual Q from obsolete ˜Q.
  • For TSP with an insertion helper, negating the designed reward improves performance by shifting emphasis toward future rewards.
  • Reward-function design remains challenging for learning combinatorial algorithms and is identified as future work.
  • The algorithm converges nicely on MVC, MAXCUT, and SCP, while TSP is harder to learn from graph structure because its graph is essentially fully connected.

D.8 Additional analysis of the trade-off between time and approx. ratio

The analysis evaluates heuristics by asking both how well CPLEX performs within the heuristic’s time and how long CPLEX needs to match or exceed its solution. Across MVC and MAXCUT, S2V-DQN provides strong quality-time trade-offs against heuristic and optimization baselines.

  • Evaluation criteria: The analysis compares each heuristic by equal-time solution quality and by the additional time CPLEX needs to match or beat its solution.These are reported as “Approx. Ratio of Best Solution” and “Additional Time Needed.”
  • MVC: Higher MVC values for S2V-DQN indicate that its quickly found solutions are higher quality than those of MVCApprox/Greedy.
  • MAXCUT: On most MAXCUT graphs, CPLEX finds no solution within the same time as S2V-DQN or MaxcutApprox.The comparison also reports that SDP is not time-efficient under the same-time analysis.
  • MAXCUT: On ER MAXCUT graphs, CPLEX cannot beat S2V-DQN or MaxcutApprox on many instances within the 10-minute cutoff.When CPLEX does find a better solution, S2V-DQN’s solutions take significantly more time to beat than MaxcutApprox and SDP’s.
  • Experimental scope: The trade-off results are summarized for 100 MVC and 100 MAXCUT graphs with 200–300 nodes in Tables D.10 and D.11.

D.9 Visualization of solutions

The visualizations show how S2V-DQN constructs solutions for MVC, MAXCUT, and TSP. The examples illustrate structured node-selection behavior and near-optimal tours on small instances.

  • MVC and MAXCUT: For MVC and MAXCUT, S2V-DQN finds the optimal solution in two step-by-step examples on 18-node Erdős–Rényi graphs.The visualizations mark selected nodes, partial solutions, covered edges, and cut edges across iterations.
  • MVC: For MVC, the agent balances edge coverage with maintaining graph connectivity during node selection.The visualization indicates that it may sacrifice intermediate edge coverage to preserve connectivity.
  • MAXCUT: For MAXCUT, the agent sometimes avoids the node with the largest immediate reward and seldom selects nodes that cancel existing cut edges.This behavior is presented as evidence that the graph-state representation informs node-selection decisions.
  • TSP: S2V-DQN produces TSP tours within 0.07% and 0.5% of optimum on the random and clustered instances, respectively.The examples contain 18 and 15 points, respectively.
  • Comparison with greedy heuristics: Figure D.7 compares S2V-DQN with two greedy heuristics and shows a strategy that maintains graph connectivity during node picking and edge removal.

D.11 Experiment Configuration of PN-AC

This section documents the PN-AC implementation and its experimental configuration. It notes possible implementation differences from prior work and reports approximation-ratio comparisons for TSP settings.

  • Implementation caveat: The PN-AC implementation may differ slightly from Bello et al.’s implementation, potentially causing lower performance than reported in that paper.
  • Experimental configuration: PN-AC experiments use mini-batches of 128 padded sequences and represent TSP nodes with coordinates or graph-problem nodes with rank-8 SVD features.
  • Experimental configuration: The paper applies the insertion heuristic to PN-AC and reports all PN-AC results with that heuristic.
  • Consistency with prior results: For TSP20, TSP50, and TSP100, the reported PN-AC approximation ratios are 1.03, 1.07, and 1.09, versus Bello et al.’s 1.02, 1.05, and 1.07.
Loading 1704.01665v4…