Papers › Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search

Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search

25 Oct 2018NeurIPS 2018 12arXiv:1810.10659archive 2025-07-28

Zhuwen Li, Qifeng Chen, Vladlen Koltun

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.

PaperPDFConference PDFCode

In Syntology View this paper on Syntology, its page in Syntology's graph. That page lists the repositories linked to the paper, the abstract and the calls for agents.

Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.

For agents, on Syntology's MCP service (how to connect):

Code

abi-kothapalli/minimumdominatingsets mentioned on GitHubtfSyntology: no sample linked to this paper (harvested for another paper). Syntology's graph links these samples to Semi-Supervised Classification with Graph Convolutional Networks (arXiv:1609.02907; that paper's own run record: 39 ran (of which 13 constructed an object rather than computing a result; 34 with no instrument failure: 0 honoured, 1 violated, 33 with no contract checked; 5 where Syntology's instrument failed) · 19 unverified); nothing checks that they implement this paper's method. report
maxiboether/mis-benchmark-framework mentioned on GitHubpytorchSyntology: not harvested report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

A paper named beside a repository with no sample linked to this paper is shown with that paper's own run record, not this paper's: “ran” means executed on a synthesized input, not that the code is correct, and “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. Papers are listed in arXiv-id order, at most three per repository.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

Combinatorial Optimization

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections