PaperlayerView exact revision on arXiv

Source-linked AI summary

Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero

Kenshin Abe, Zijian Xu, Issei Sato, Masashi Sugiyama

arXiv:1905.11623v2cs.LGstat.ML

TL;DR

Machine-learning methods for graph-based NP-hard optimization need better generalization beyond their training graphs. The paper introduces CombOpt Zero, an AlphaGo Zero-inspired MCTS training strategy adapted to variable-sized graphs and real-valued rewards. Across five NP-hard problem types, it generalizes better than S2V-DQN, with further gains from suitable GNNs and test-time MCTS.

  • Problem

    S2V-DQN can perform poorly on graph distributions differing from its random-graph training data, motivating improved generalization for graph combinatorial optimization.

    Source: §1 · p. 1

  • Method

    CombOpt Zero replaces Q-learning with AlphaGo Zero-inspired MCTS training, using GNNs for graph states and normalized rewards for non-binary outcomes.

    Source: §1 · p. 2, §2.2 · p. 2, §3.2 · p. 5

  • Results

    CombOpt Zero generalizes better than S2V-DQN across varied graphs and achieves further improvements when combined with appropriately selected GNN models.

    Source: §1 · p. 2, §4.1 · p. 8, §4.2 · p. 9

  • Takeaways & Limitations

    MCTS-based training strengthens action exploration, while test-time MCTS and suitable GNN choices can improve solution performance and stability.

    Source: §1 · p. 2, §5 · p. 10

    CombOpt Zero requires more powerful computing resources because MCTS makes self-play data generation slower, despite greater sample efficiency.

    Source: §4.4 · p. 10

Abstract

from arXiv · show

There have been increasing challenges to solve combinatorial optimization problems by machine learning. Khalil et al. proposed an end-to-end reinforcement learning framework, S2V-DQN, which automatically learns graph embeddings to construct solutions to a wide range of problems. To improve the generalization ability of their Q-learning method, we propose a novel learning strategy based on AlphaGo Zero which is a Go engine that achieved a superhuman level without the domain knowledge of the game. Our framework is redesigned for combinatorial problems, where the final reward might take any real number instead of a binary response, win/lose. In experiments conducted for five kinds of NP-hard problems including {\sc MinimumVertexCover} and {\sc MaxCut}, our method is shown to generalize better to various graphs than S2V-DQN. Furthermore, our method can be combined with recently-developed graph neural network (GNN) models such as the \emph{Graph Isomorphism Network}, resulting in even better performance. This experiment also gives an interesting insight into a suitable choice of GNN models for each task.

1 Introduction

The paper targets the difficulty of generalizing machine-learning methods for NP-hard graph optimization beyond training distributions. It replaces S2V-DQN’s Q-learning with an AlphaGo Zero-inspired strategy and reports stronger generalization across graph types.

Problem

  • NP-hard optimization problems matter in real-world applications, but general-purpose and problem-specific methods can require heavy implementation or sophisticated problem-specific rules.Source: §1 · p. 1

Motivation

  • S2V-DQN performs poorly on some synthetic and real-world graphs differing from its random-graph training distribution, possibly because Q-learning explores a limited action space.Source: §1 · p. 1

Contribution

  • CombOpt Zero replaces S2V-DQN’s Q-learning with an AlphaGo Zero-inspired learning strategy for graph combinatorial optimization.The framework is designed to learn without domain knowledge or a training dataset.Source: §1 · p. 2

Evaluation

  • CombOpt Zero is evaluated on five NP-hard problem types and tested across standard random, synthetic, and real-world graphs.Source: §1 · p. 2

Results

  • The method generalizes better than S2V-DQN, while test-time MCTS and suitable GNN choices further improve performance.Source: §1 · p. 2

2 Preliminary

The preliminary material defines the graph-optimization setting, reviews S2V-DQN and AlphaGo Zero, and introduces GNN architectures and representative NP-hard graph problems. These components motivate CombOpt Zero’s MCTS-based adaptation to variable-sized graphs and non-binary rewards.

2.1 Notations

  • The notation uses G = (V, E) for an undirected, unlabelled graph, with V(G) denoting its vertices and N(x) its one-hop neighbors.Source: §2.1 · p. 2

2.2 Machine Learning for Combinatorial Optimization

  • S2V-DQN uses reinforcement learning with a structure2vec graph-embedding Q-network to construct solutions across graph problems without requiring graph-algorithm knowledge.States encode partial solutions, and actions select feasible vertices through problem-dependent reductions.Source: §2.2 · p. 2

2.3 AlphaGo Zero

  • CombOpt Zero follows AlphaGo Zero’s self-play training pattern, in which the policy imitates an MCTS-enhanced policy and the value imitates self-play reward.Source: §2.3 · pp. 2–3
  • AlphaGo Zero’s MCTS repeatedly selects actions, expands unexplored states using network predictions, and backs up simulated evaluations into edge statistics.Edges store visit counts, total and mean action values, and prior probabilities.Source: §2.3 · p. 3

2.4 Graph Neural Network

  • GNNs aggregate neighboring feature vectors into node embeddings; GIN is highly expressive among MPNNs, while 2-IGN+ provides a scalable alternative to higher-order invariant graph networks.Source: §2.4 · p. 3
  • The experiments compare GNN models including GCN, GIN, 2-IGN+, and S2V for combinatorial optimization tasks.Source: §2.4 · p. 3

2.5 NP-hard Problems on Graphs

  • The paper studies unweighted graph problems including Minimum Vertex Cover, Max Cut, and Maximum Clique, alongside two additional problems described elsewhere.Source: §2.5 · pp. 3–4

3 Method

The method reduces graph optimization problems to deterministic MDPs, then extends AlphaGo Zero with reward normalization and graph-based Monte Carlo Tree Search. CombOpt Zero trains through self-play data generation, learning, and evaluation using normalized action rewards.

3.1 Reduction to MDP

  • Graph optimization is formulated as a deterministic MDP whose optimal reward sum equals the original problem objective.States are labeled graphs, actions induce deterministic transitions, and trajectories terminate at empty or problem-specific terminal states.Source: §3.1 · p. 4
  • The MDP reductions encode Minimum Vertex Cover, Max Cut, and Maximum Clique through problem-specific actions, transitions, terminal states, and rewards.Max Cut actions color and remove nodes while rewards count edges entering the cut; Minimum Vertex Cover minimizes transition steps, whereas Maximum Clique maximizes them.Source: §3.1 · p. 4

3.2 Ideas for CombOpt Zero

  • CombOpt Zero replaces Q-learning with an AlphaGo Zero-inspired MCTS strategy adapted to variable-size graphs and real-valued rewards.GNNs process graph states, while reward normalization compares actions with returns from random plays instead of using an unbounded raw value scale.Source: §3.2 · p. 5
  • The network outputs action probabilities and a vector of normalized action values, with each value predicting reward relative to random-play mean and standard deviation.MCTS restores unnormalized values using µ_s and σ_s, while W(s, a) and Q(s, a) accumulate normalized estimates during backup.Source: §3.2 · p. 5

3.3 Algorithms

  • MCTS repeatedly selects, expands, and backs up nodes, using random sampling for normalization and action-proportional iteration counts.CombOpt Zero adds Dirichlet noise only at the initial state and computes enhanced policies after sufficient iterations.Source: Figure 2 · p. 5, §3.3 · p. 6
  • Training alternates self-play data generation, learner updates, and model evaluation, with normalized cumulative rewards used as learning targets.The evaluator compares candidate and best models by mean performance on freshly generated random graph instances rather than win rates.Source: §3.3 · pp. 6–7

4 Experiments

Experiments show that CombOpt Zero generalizes better than S2V-DQN beyond training-like graphs, benefits from task-dependent GNN choices, and improves solutions further with test-time MCTS, at greater training cost.

4 Experiments

  • The experimental comparison used S2V-DQN as the main learning competitor alongside problem-specific heuristics and approximation algorithms.For MAXCUT, comparisons included semidefinite programming and two local-search heuristics; MINIMUMVERTEXCOVER used a randomized 2-approximation.Source: §4 · p. 7
  • Experiments used randomly generated ER graphs for training and tested ER, BA, real-world, and DIMACS graphs, with problem-specific sizes and features.Ten real-world graphs included citation, web, biological, and road-map networks.Source: §4 · pp. 7–8

4.1 Comparison of Generalization Ability

  • CombOpt Zero generalized better than S2V-DQN on BA, Watts-Strogatz, sparse regular, and real-world graphs, although S2V-DQN performed better on some instances.S2V-DQN performed better on the ER graphs used for training.Source: §4.1 · pp. 8–9, Table 1 · p. 8

4.2 Combination with Several GNN Models

  • CombOpt Zero with suitable GNN models outperformed S2V-DQN overall, but the best model depended on the problem and test instance.GIN performed best on MAXCUT, whereas GCN performed slightly better on MINIMUMVERTEXCOVER; GCN was significantly worse on MAXCUT but near-best on four other problems.Source: §4.2 · p. 9, Table 2 · p. 9, Table 3 · p. 9

4.3 Test-time MCTS

  • Test-time MCTS strictly improved MAXIMUMCLIQUE performance on 7 of 10 instances and matched or improved every instance, surpassing reported lower bounds on 6.A clique of size 30 was found on web-edu, compared with a previous bound of 16.Source: Table 4 · p. 9, §4.3 · p. 10
  • CombOpt Zero’s MCTS test-time search was evaluated on MAXIMUMCLIQUE because its smaller solution sizes and search depths made inference feasible within minutes.The study used a single process and GPU for this case study.Source: §4.3 · pp. 9–10

4.4 Tradeoffs between CombOpt Zero and S2V-DQN

  • CombOpt Zero requires more computational resources because MCTS makes self-play data generation slower, although it is more sample-efficient than S2V-DQN.Training used 32 processes and four GPUs for CombOpt Zero, versus one process and GPU for S2V-DQN.Source: §4.4 · p. 10
  • CombOpt Zero’s PyTorch implementation makes incorporating different GNN models relatively easy compared with S2V-DQN’s GPU-specific implementation.Source: §4.4 · p. 10

5 Conclusion

The paper concludes that CombOpt Zero uses training-time MCTS to improve exploration and generalization on graph combinatorial optimization, with stronger performance when combined with suitable GNNs. The appendix defines additional NP-hard problems and reviews the GNN architectures used.

5 Conclusion

  • CombOpt Zero improved exploration, generalization across graphs, and performance when combined with powerful GNN models; test-time MCTS also improved performance and stability.The framework solves graph combinatorial optimization without domain knowledge.Source: §5 · p. 10

A.1 Maximum Independent Set

  • Maximum Independent Set seeks a largest subset of pairwise nonadjacent vertices, while its MDP deletes a selected vertex and its neighbors and rewards each transition.The transition reward is R(s, x) = 1 because the objective is to maximize transition steps.Source: §A.1 · p. 13

A.2 Minimum Feedback Vertex Set

  • Minimum Feedback Vertex Set seeks the smallest vertex subset whose removal leaves a cycle-free induced graph, with terminal states defined by cycle-free graphs.Its MDP formulation otherwise follows the Minimum Vertex Cover formulation.Source: §A.2 · p. 13

B Graph Neural Networks

  • S2V, GCN, and GIN propagate node features through graph structure, whereas 2-IGN+ processes tensors initialized from adjacency and diagonal node features.GIN sums features from each node and its neighbors before applying multilayer perceptrons.Source: B Graph Neural Networks · p. 13, §B.1 · p. 13, §B.2 · p. 13

B.3 Graph Isomorphism Network / B.4 2-IGN+

  • GIN applies multilayer perceptrons after summing features among each node and its neighbors, while 2-IGN+ uses tensor blocks and equivariant linear layers for node outputs.The 2-IGN+ block applies multiple MLPs and feature-wise matrix multiplication before producing the next tensor.Source: §B.3 · p. 13, §B.4 · p. 14

C Experiment Settings

The experiments compare CombOpt Zero with S2V-DQN, randomized methods, heuristics, approximation algorithms, and exact solvers under differing computational environments. The study uses four NVIDIA Tesla P100 GPUs, while CPLEX runs separately on an eight-thread MacBook Pro.

C.1 Environment

  • The experiments ran on Intel Xeon E5-2695 v4 hardware with four NVIDIA Tesla P100 GPUs, GCC 5.4.0, and CUDA 9.2.148.CPLEX was instead run on an eight-thread 2.4 GHz MacBook Pro.Source: §C.1 · p. 14, §C.2 · p. 14

C.2 Competitors

  • CombOpt Zero is compared primarily with S2V-DQN, alongside randomized algorithms, problem-specific heuristics, approximation methods, and CPLEX.The additional methods provide reference comparisons rather than fully matched computational baselines.Source: §C.2 · p. 14
  • Randomized baselines used the best objective from 100 runs, while MAXCUT heuristics had a 10-minute time limit and CPLEX used an eight-thread, 10-minute limit.These settings make the running environments difficult to compare directly because several baselines do not use GPUs or training time.Source: §C.2 · p. 14

C.3 Hyperparameters

The study specifies GNN, MCTS, and training configurations before comparing Minimum Vertex Cover methods. Results vary by graph family and architecture: CombOpt Zero can outperform CPLEX on large random graphs but can lag behind simple approximation methods on sparse real-world networks.

C.3 Hyperparameters

  • The experiments use S2V with p = 64 and L = 5, five-layer GCN and GIN networks, and a two-block 2-IGN+ network.GIN uses five-layer MLPs with hidden dimension 16, while 2-IGN+ uses hidden dimension 8.Source: §C.3 · p. 14
  • MCTS adds first-move Dirichlet noise and uses citer = 4 for several problems but citer = 3 for Minimum Vertex Cover and Minimum Feedback Vertex Set.The test-time temperature is τ = 0, selecting an action with maximum visit count.Source: §C.3 · pp. 14–15

D.1 Minimum Vertex Cover

  • CombOpt Zero found near-optimal Minimum Vertex Cover solutions on large random graphs despite training on small random graphs, and some models outperformed CPLEX.Both CombOpt Zero and S2V-DQN failed to find an optimum on the 200-node ER graph er200_10.Source: §D.1 · p. 15, Table 6 · p. 16
  • On some large sparse real-world networks, CombOpt Zero performed worse than a simple 2-approximation algorithm, motivating possible hybrid reduction-and-learning approaches.The paper explicitly keeps its method free of domain knowledge.Source: §D.1 · p. 15
  • The Minimum Vertex Cover comparison reports smaller values as better, with bold entries marking the best reinforcement-learning values; 2-IGN+ sometimes exceeded the two-hour testing limit.Its inference cost is Θ(n3) per action.Source: Table 6 · p. 16

D.2 Max Cut

Across MaxCut, Maximum Clique, and Maximum Independent Set, CombOpt Zero often benefits from GIN and test-time MCTS, but performance depends on the graph family and computational cost. The strongest reported comparisons include outperforming S2V-DQN and selected classical baselines.

D.2 Max Cut

  • MAXCUT uses a 0.878-approximation SDP reference, but the SDP method was applied only to graphs with at most 200 nodes because of its large size.The comparison also includes a MAXCUT solver by Dunning et al.Source: §D.2 · p. 16
  • CombOpt Zero with GIN outperformed S2V-DQN on MaxCut and surpassed the 0.878-approximation SDP algorithm in all reported GIN results.It also exceeded state-of-the-art heuristics on instances including citeseer and rt_damascus, while GCN performed poorly.Source: §D.2 · p. 16, Table 7 · p. 17

D.3 Maximum Clique

  • For Maximum Clique, GIN performed best among the four tested models and outperformed S2V-DQN, especially on random graphs.Test-time MCTS improved solutions and stabilized weaker GCN and 2-IGN+ models.Source: §D.3 · p. 17
  • Test-time MCTS improves Maximum Clique solutions and stability but requires n times larger time complexity, limiting use on large instances or short time limits.The limitation is especially relevant when solution sizes are large.Source: §D.3 · p. 17

D.4 Maximum Independent Set

  • For Maximum Independent Set, recursive-reduction randomization can approach optimality on large sparse networks, whereas CombOpt Zero and S2V-DQN are stronger on ER graphs.CombOpt Zero with GIN obtained a better solution than CPLEX on one DIMACS instance.Source: §D.4 · p. 17

D.5 Minimum Feedback Vertex Set

The section presents a randomized parameterized algorithm for MINIMUMFEEDBACKVERTEXSET and compares it with learning-based and randomized approaches across graph instances.

Randomized Algorithm

  • The algorithm iteratively reduces the graph, selects a random node, increments the feedback-vertex-set size, and removes that node, with reductions enforcing minimum degree at least 3.Reductions remove self-loop vertices into the feedback vertex set, cap multiedge multiplicity at 2, and suppress degree-2 vertices by joining their neighbors.Source: §D.5 · p. 19
  • The randomized algorithm provides a minimum feedback vertex set with probability greater than 1/4^k, where k is the optimal solution size.The bound follows from selecting vertices according to degree after reductions ensure minimum degree at least 3.Source: §D.5 · pp. 18–19

Full results

  • CombOpt Zero did not show significant overall superiority over S2V-DQN, although solution sizes differed substantially on datasets including web-edu, bio-SC-LC, and socfb-bowdoin47.The authors attribute some S2V-DQN behavior to convergence of all five models into local optima.Source: §D.5 · p. 19, Table 10 · p. 19
  • The randomized algorithm worked effectively on large real-world networks with biased degrees, whereas CombOpt Zero and S2V-DQN performed better on ER graphs.This contrast links performance to differences in degree variation across graph types.Source: §D.5 · p. 19

D.6 Training Convergence

The convergence comparison shows that CombOpt Zero generates fewer trajectories than S2V-DQN but requires fewer samples to reach training convergence.

Training Convergence

  • The MAXCUT curves measure average cut size on 100 fixed random ER graphs over two hours of training.CombOpt Zero's curve begins after 15 minutes because its best models are logged only after that point.Source: §D.6 · p. 20
  • CombOpt Zero required about 2,000 training samples to converge, compared with about 50,000 for S2V-DQN.The authors characterize this as substantially greater sample efficiency for CombOpt Zero.Source: §D.6 · p. 20
  • S2V-DQN generated about 225,000 data points in two hours, whereas CombOpt Zero generated only 5,000 data points using four GPUs.CombOpt Zero's lower generation rate is attributed to the time required by MCTS for self-play data generation.Source: §D.6 · p. 20

E Comparison of Reduction Rules

CombOpt Zero differs from S2V-DQN by explicitly shrinking its graph state and allowing actions beyond selecting a single vertex.

State representation

  • CombOpt Zero represents each state as a single current labeled graph that usually becomes smaller as actions proceed, unlike S2V-DQN's original graph-plus-selected-nodes state.Smaller graphs make GNN inference faster, while S2V-DQN performs graph-size reduction more implicitly.Source: E Comparison of Reduction Rules · pp. 20–21

Action space

  • CombOpt Zero permits actions that select both a vertex and a color, whereas S2V-DQN restricts actions to selecting one vertex.This formulation lets MAXCUT be expressed as coloring every node with two colors and extends naturally to K-COLORING.Source: E Comparison of Reduction Rules · p. 21
  • The broader action space provides more intuitive termination criteria and supports a wider range of combinatorial problems.For K-COLORING, an action is represented as (x, c), where x is a vertex and c is a permitted color.Source: E Comparison of Reduction Rules · p. 21

F Visualization

The visualizations show CombOpt Zero learning effective MAXCUT action patterns, including opposite-color propagation and depth-first-search-like traversal on trees.

Tree visualization

  • CombOpt Zero found an optimal MAXCUT solution on a tree, with an action order similar to depth-first search.Because depth-first search yields an optimal two-coloring for trees, the learned sequence matches an effective algorithm for this case.Source: F Visualization · p. 21, Figure 6 · p. 23

Action flexibility

  • CombOpt Zero can also skip immediate neighbors and color two-hop nodes with the same color as the current node.The authors relate this flexibility to the five-layer message-passing GNN's access to five-hop neighborhood information.Source: F Visualization · p. 21

ER-graph visualization

  • On ER graphs, CombOpt Zero learned to color neighboring nodes one by one with the opposite color.The visualization presents this as a learned ordering of node selections and color assignments.Source: F Visualization · p. 21, Figure 5 · p. 22

Related papers

Loading 1905.11623v2…