Source-linked AI summary
Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
Zhuwen Li, Qifeng Chen, Vladlen Koltun
TL;DR
The paper targets practical solution of graph-expressible NP-hard problems, where scalable and effective algorithms remain needed. It combines a graph convolutional network trained for diverse solution predictions with tree search and heuristic refinement, outperforming recent deep-learning methods and generalizing across datasets and graph sizes.
Problem
NP-hard problems require practical algorithms despite worst-case complexity and limitations in the scalability or guarantees of existing approaches.
Method
A graph convolutional network predicts vertex membership likelihoods, synthesizes diverse solutions, and guides tree search followed by heuristic refinement.
Results
The approach substantially outperforms recent deep-learning work, generalizes across datasets and problem types, and scales to graphs orders of magnitude larger than its training instances.
Takeaways & Limitations
Training a network to produce multiple solutions enables effective exploration of the solution space within a hybrid learning-and-search solver.
Takeaways & Limitations
The approach focuses primarily on MIS and did not solve Maximal Clique on large social and citation networks because complementary graphs were too dense for the evaluated approaches.
Abstract
from arXiv · showhide
We present a learning-based approach to computing solutions for certain NP-hard problems. Our approach combines deep learning techniques with useful algorithmic elements from classic heuristics. The central component is a graph convolutional network that is trained to estimate the likelihood, for each vertex in a graph, of whether this vertex is part of the optimal solution. The network is designed and trained to synthesize a diverse set of solutions, which enables rapid exploration of the solution space via tree search. The presented approach is evaluated on four canonical NP-hard problems and five datasets, which include benchmark satisfiability problems and real social network graphs with up to a hundred thousand nodes. Experimental results demonstrate that the presented approach substantially outperforms recent deep learning work, and performs on par with highly optimized state-of-the-art heuristic solvers for some NP-hard problems. Experiments indicate that our approach generalizes across datasets, and scales to graphs that are orders of magnitude larger than those used during training.
1 Introduction
The paper addresses practical NP-hard optimization by combining graph-based deep learning with heuristic search. Its method predicts solution membership, generates diverse candidates, and performs competitively across problems and datasets.
- NP-hard problems remain practically important across computing fields despite unfavorable worst-case complexity.Approximation algorithms offer guarantees, while heuristics are often judged by empirical performance and scalability.
- Learning-based methods may discover graph patterns that are difficult to specify manually.
- The proposed GCN predicts each vertex’s likelihood of belonging to an optimal solution and synthesizes diverse solution modes.This addresses diffuse likelihood maps caused by multiple optimal solutions.
- The trained GCN guides parallelized tree search to generate many candidate solutions, followed by refinement and selection of one candidate.
- On four canonical NP-hard problems and multiple benchmarks and real graphs, the approach substantially outperforms recent deep-learning methods and sometimes matches optimized solvers.The evaluated graphs include social networks with up to one hundred thousand nodes.
2 Background
Prior approaches include manually tuned heuristics and learning-based algorithms that seek useful data regularities. This work differs from recent reinforcement-learning methods through supervised learning, graph convolutions, and simultaneous diverse-solution generation.
- Classical practice combines approximation algorithms with provable guarantees and heuristics tuned for empirical performance.Common heuristics include greedy search, local search, genetic algorithms, simulated annealing, and particle swarm optimization.
- Learning-based approaches can learn useful patterns and regularities from large datasets that may escape human algorithm designers.
- Dai et al. trained a deep Q-network with reinforcement learning to incrementally construct solutions for graph-based NP-hard problems.
- This paper instead uses supervised learning, a graph convolutional network, and training that synthesizes diverse solutions simultaneously.The diversity mechanism enables rapid exploration of the solution space.
- An earlier graph-neural-network application to quadratic assignment did not surpass classic heuristics or pointer-network results.
3 Preliminaries
The paper focuses on graph formulations of four canonical NP-hard problems and converts several of them into MIS instances. Its algorithm overview combines graph reduction, probabilistic labeling, tree search, and local refinement.
- MIS seeks the largest vertex subset containing no adjacent pair, while MVC seeks the smallest vertex set incident to every edge.
- The algorithm reduces the input graph, produces multiple vertex-probability maps with a GCN, and iteratively labels vertices through tree search.
- Complete tree-search labelings are refined by rapid local search, and the best refined result becomes the final output.
- SAT asks for a Boolean assignment that makes a conjunction of clauses true, or determines that no satisfying assignment exists.
- MVC, MC, and SAT can be represented as MIS instances, so the experiments solve all four problems through equivalent MIS formulations.
4 Method
The method combines a graph convolutional network with greedy and tree-search heuristics to generate and refine feasible solutions for graph-based NP-hard problems. It addresses multimodal optimal-solution spaces by producing diverse probability maps, enabling broad parallel exploration.
- Initial approach: Directly rounding vertex probabilities can violate independence constraints, so predictions guide a greedy procedure that labels selected vertices and their neighbors.The procedure sorts vertices by predicted likelihood, selects them in order, and removes labeled vertices and incident edges.
- Network and training: The method trains a graph convolutional network to predict each vertex’s likelihood of belonging to an optimal solution.Training uses binary labels from optimal solutions and produces a likelihood map over graph vertices.
- Diversity and tree search: Multiple optimal solutions can confuse a single-output network, causing it to produce averaged probabilities that do not represent a useful discrete solution.The paper illustrates this failure with equivalent MIS solutions that induce different vertex labelings.
- Diversity and tree search: The revised network generates M diverse probability maps and uses hindsight loss so each training sample is evaluated by its most accurate generated solution.This loss lets the network spread its predictions across solution modes and produce sharper candidate maps.
- Diversity and tree search: Tree search expands incomplete solutions using the multiple maps, maintains a randomized queue to preserve diversity, and supports parallel execution.The parallelized procedure can generate up to 100K diverse solutions in 10 minutes for a 1,000-vertex graph; local search then refines candidates.
5 Experiments
Experiments evaluate the approach across SAT, MIS, MVC, and MC benchmarks, including real-world graphs with up to one hundred thousand nodes. The method solves all SAT instances in two reported datasets, generalizes across datasets and problem types, and performs competitively on large graphs.
- Experimental setup: 38,000 SATLIB instances train the network, with 1,000 each reserved for validation and testing; the SAT graphs contain about 1,200 vertices.The training data consists of satisfiable synthetic 3-SAT instances converted to equivalent MIS graphs.
- SAT results: 100% of SATLIB test instances are solved, compared with 89 for S2V-DQN+GR+LS and 79 for Classic+GR+LS; the approach matches Z3 and slightly exceeds Gurobi.The SATLIB test set contains 1,000 instances.
- Ablations and analysis: Increasing the number of intermediate solutions improves performance through M = 32, after which the fraction solved and average independent-set size plateau.This hyperparameter analysis uses the single-threaded tree search because the multi-threaded version solves all instances easily.
- SAT results: 100% of SAT Competition 2017 instances are solved, matching Z3 and ReduMIS and exceeding Classic+GR+LS at 75%, S2V-DQN+GR+LS at 80%, and Gurobi at 80%.Gurobi cannot return valid solutions for some instances, so its independent-set size is not listed.
- Cross-dataset results: 62.5% of BUAA-MC instances are solved optimally, versus 25% for ReduMIS, while the approach also outperforms all baselines on MIS and MVC.The network was trained only on synthetic SAT graphs from a different dataset, supporting the reported cross-dataset and cross-problem generalization.
- Large-scale graphs: On social and citation graphs, the approach and ReduMIS outperform other baselines, including on graphs with roughly 100,000 nodes and more than 10 million edges.The authors report generalization from synthetic SAT graphs to real-world networks and across graph scales.
6 Conclusion
The paper presents a graph-convolutional approach that combines dense prediction with classic heuristics to explore NP-hard solution spaces. It reports strong performance, cross-dataset generalization, and scaling to much larger instances, while acknowledging limits from focusing training on MIS.
- 6 Conclusion: The approach trains a deep network for dense graph prediction and uses multiple generated solutions to explore the solution space effectively.The method combines graph convolutional networks with classic algorithmic ideas.
- 6 Conclusion: The resulting algorithm convincingly outperforms recent work and generalizes across different datasets and instances orders of magnitude larger than its training examples.These findings are described as particularly encouraging in the conclusion.
- 6 Conclusion: The approach is not universal because the paper focuses on MIS and problems that can be easily mapped to it.The authors identify direct application to other problems as a desirable direction.
A Problem reductions
The paper reduces MVC, MC, and SAT to MIS representations, allowing these problems to be addressed through the MIS formulation. Each reduction relies on a structural correspondence between solutions.
- A Problem reductions: MVC solutions are complementary to MIS solutions: a set is independent exactly when its complement is a vertex cover.Thus, minimum vertex cover and maximal independent set can be represented as complementary solutions.
- A Problem reductions: A maximal clique in a graph corresponds to a maximal independent set in the graph’s complement.
- A Problem reductions: SAT instances can also be represented as MIS instances through a graph reduction described by the paper.The supplied passage introduces the SAT →MIS correspondence but truncates its construction details.
B Algorithms
The basic MIS algorithm ranks vertices by the network output, greedily labels selected vertices and their neighbors, then recursively processes the residual graph. It returns a labelling of all vertices.
- B Algorithms: Algorithm 1 takes a graph as input and outputs a labelling of all its vertices.
- B Algorithms: Vertices are processed in descending order of f(G; θ), with selected vertices labelled 1 and their neighbors labelled 0.Processing stops when an already labelled vertex is encountered.
- B Algorithms: After greedy labelling, the algorithm removes labelled vertices and recursively runs BasicMIS on the residual graph when it is nonempty.
C Classic elements
The enhanced algorithms add diversity, randomized queue exploration, parallelized tree search, and graph-reduction rules to the network-guided MIS procedure. Local search further improves solutions through valid two-vertex replacements.
- C.1 Local search: A 2-improvement replaces one selected vertex with two nonadjacent 1-tight neighbors, and a valid improvement can be found in O(E) time if it exists.An incremental variant maintains candidate nodes involved in such improvements.
- C.2 Diversity and tree search: The diversity-and-tree-search variant samples residual graphs from a queue and generates M candidate branches using distinct network outputs.Completed graphs update the best solution; incomplete residual graphs return to the queue.
- C.3 Parallelized tree search: The parallelized variant assigns tree-search work across T threads while sharing a queue of residual graphs.The queue is initialized with the original graph when empty.
- C.4 Graph reduction: Graph reduction removes or contracts structurally constrained vertices, including pendant vertices, foldable degree-two vertices, and unconfined vertices.Pendant vertices must belong to some MIS, while vertex folding merges a local three-vertex structure for later resolution.
D Real-world graphs
The paper reports statistics and descriptions for the real-world graphs used in its experiments, summarized in Table 7.
- Table 7 provides statistics for the real-world graphs used in the experiments.
- Table 7 describes the real-world graphs included in the experimental analysis.
- The real-world graph information is organized in a dedicated table of statistics and descriptions.
E Network width C
The study evaluates intermediate-layer width C using SATLIB validation results. C = 32 offers the best balance of performance and efficiency, while larger widths reduce performance.
- The experiment compares C = 16, 32, 64, 128 using solved-problem fractions and average MIS solution size.
- Performance decreases at C = 64 and C = 128, probably because model complexity raises computational cost and reduces search time.
- C = 32 provides the best balance of performance and efficiency.