PaperlayerView exact revision on arXiv

Source-linked AI summary

DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization

Zhiqing Sun, Yiming Yang

arXiv:2302.08224v2cs.LG

TL;DR

NP-complete combinatorial optimization remains difficult because traditional solvers require integer programming or expert-crafted heuristics. DIFUSCO introduces graph-conditioned diffusion over binary solution vectors, comparing Gaussian and Bernoulli noise with an accelerated inference schedule. It reports state-of-the-art results on TSP and MIS, including reduced gaps on large TSP benchmarks.

  • Problem

    Traditional NP-complete combinatorial optimization solvers rely on integer programming or hand-crafted heuristics requiring substantial expert effort.

  • Method

    DIFUSCO casts NP-complete problems as {0, 1}-vector optimization and uses graph-based denoising diffusion with Gaussian or Bernoulli noise.

  • Results

    DIFUSCO achieves state-of-the-art results on TSP and MIS, reducing the neural-solver gap from 1.76% to 0.46% on TSP-500 and from 2.46% to 1.17% on TSP-1000.

  • Takeaways & Limitations

    A single graph neural network architecture supports DIFUSCO across TSP and MIS while improving both accuracy and scalability over previous probabilistic NPC solvers.

  • Takeaways & Limitations

    The authors identify broader NP-complete coverage, equivariant networks for geometric problems, and accelerated inference as future work.

Abstract

from arXiv · show

Neural network-based Combinatorial Optimization (CO) methods have shown promising results in solving various NP-complete (NPC) problems without relying on hand-crafted domain knowledge. This paper broadens the current scope of neural solvers for NPC problems by introducing a new graph-based diffusion framework, namely DIFUSCO. Our framework casts NPC problems as discrete {0, 1}-vector optimization problems and leverages graph-based denoising diffusion models to generate high-quality solutions. We investigate two types of diffusion models with Gaussian and Bernoulli noise, respectively, and devise an effective inference schedule to enhance the solution quality. We evaluate our methods on two well-studied NPC combinatorial optimization problems: Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS). Experimental results show that DIFUSCO strongly outperforms the previous state-of-the-art neural solvers, improving the performance gap between ground-truth and neural solvers from 1.76% to 0.46% on TSP-500, from 2.46% to 1.17% on TSP-1000, and from 3.19% to 2.58% on TSP10000. For the MIS problem, DIFUSCO outperforms the previous state-of-the-art neural solver on the challenging SATLIB benchmark.

1 Introduction

DIFUSCO introduces graph-based diffusion solvers that represent NP-complete problems as binary selection vectors and denoise all variables in parallel. Across TSP and MIS, it improves on prior neural solvers in quality and scalability.

  • Motivation and approach: DIFUSCO formulates each NP-complete problem as selecting nodes or edges with a {0, 1}-valued vector and denoises these variables using a graph neural network.The framework uses message passing to encode the instance graph and predict clean variables.
  • Motivation and approach: Parallel inference with far fewer than N denoising steps avoids the sequential generation bottleneck of autoregressive constructive solvers.The model also uses iterative refinements to represent multimodal solution distributions.
  • Motivation and approach: DIFUSCO investigates continuous Gaussian and discrete Bernoulli diffusion, with an inference strategy designed to improve generation quality.The framework evaluates both diffusion types within the same graph-based setting.
  • Evaluation: A single anisotropic graph neural network backbone supports both Traveling Salesman Problem and Maximal Independent Set benchmarks of varying sizes.The experiments report improvements over previous probabilistic NP-complete solvers.

2 Related Work

Prior neural CO solvers trade off sequential scalability, distributional expressiveness, and reinforcement-learning efficiency. DIFUSCO uses iterative graph-based denoising to address these limitations while remaining compatible with heatmap search.

  • Existing neural solvers: Autoregressive constructive solvers sequentially grow partial solutions, creating high time and space costs for large-scale NP-complete problems.Their sequential decoding makes scaling difficult.
  • Existing neural solvers: Non-autoregressive solvers improve scalability by assuming conditional independence, but this limits their ability to capture multimodal high-quality solution distributions.Active search or MCTS is then used to increase expressive power.
  • DIFUSCO's distinction: DIFUSCO remains a non-autoregressive constructive heuristic solver but iteratively denoises the heatmap, enhancing expressive power relative to previous non-autoregressive methods.Its heatmaps can also benefit from search techniques such as MCTS.
  • Diffusion-based approaches: Earlier diffusion work for NP-complete optimization used image-based TSP representations, whereas DIFUSCO explicitly models node or edge selection on graphs.Graph-based diffusion for NP-complete problems had not previously been studied according to the authors.

3 DIFUSCO: Proposed Approach

DIFUSCO casts combinatorial optimization as binary-vector optimization and learns graph-conditioned diffusion models to recover clean solutions from corrupted variables. It combines Gaussian or Bernoulli noise with accelerated denoising schedules and an anisotropic GNN.

  • 3.1 Problem Definition: Each candidate solution is a binary vector x in X_s = {0, 1}^N, scored by task cost plus an infinite penalty for invalid solutions.The optimum minimizes c_s(x), with validity enforcing feasibility.
  • 3.1 Problem Definition: For TSP, vector entries select edges and validity requires a tour visiting every node exactly once before returning to the start.For MIS, entries select nodes and validity requires no selected nodes to be adjacent.
  • 3.2 Diffusion Models in DIFUSCO: Discrete diffusion corrupts one-hot binary variables with categorical transitions and trains the denoiser to predict clean data for the reverse process.Element-wise multiplication appears in the posterior expressions, and the reverse process substitutes the predicted clean data.
  • 3.2 Diffusion Models in DIFUSCO: Continuous diffusion rescales binary inputs into the {-1, 1} space, adds Gaussian noise, predicts the unscaled noise, and threshold-quantizes outputs back to binary variables.The reverse process uses a point estimate of the clean continuous data.
  • 3.3 Denoising Schedule for Fast Inference: Fast inference models reverse transitions on a selected increasing subsequence of diffusion timesteps rather than every latent timestep.Linear and cosine schedules are considered, with cosine allocating more steps to the low-noise regime.
  • 3.4 Graph-based Denoising Network: The denoising network receives noisy variables x_t and instance s, then predicts clean data x̂_0 for node-based MIS or edge-based TSP variables.An anisotropic graph neural network is used for both diffusion variants.
  • 3.4 Graph-based Denoising Network: The anisotropic message-passing network propagates node and edge features using learned transformations, neighborhood aggregation, gating, and nonlinear layers.The architecture uses sinusoidal timestep features and a final classification or regression head.

4 Experiments with TSP

Experiments on Euclidean TSP evaluate DIFUSCO across scales, diffusion configurations, decoding strategies, and generalization settings. Discrete diffusion with cosine scheduling performs strongly, and DIFUSCO achieves state-of-the-art results while generalizing across problem sizes.

  • Experimental Settings: TSP instances are sampled uniformly from the unit square, with evaluations spanning 50, 100, 500, 1000, and 10000 nodes.TSP-50 is the main configuration benchmark; larger instances test scalability.
  • Experimental Settings: Large-scale TSP graphs are sparsified by retaining each node’s nearest neighbors, avoiding quadratic edge growth as node count increases.The neighborhood size is 50 for TSP-500 and 100 for TSP-1000/10000.
  • Design Analysis: Discrete Bernoulli diffusion consistently outperforms continuous Gaussian diffusion beyond 5 diffusion steps, while cosine scheduling improves discrete diffusion over linear scheduling.Cosine and linear schedules perform similarly for continuous diffusion, so cosine is used thereafter.
  • Design Analysis: More diffusion iterations are generally more effective than more sampled solutions; 20 diffusion steps × 4 samples competes with 1 diffusion step × 1024 samples.The study compares diffusion steps from 1 to 200 and multiple parallel-sampling settings.
  • Main Results: DIFUSCO achieves state-of-the-art performance on TSP-50 and TSP-100 under both greedy and sampling settings for probabilistic solvers.The evaluation reports average tour length, relative performance gap, and total runtime.
  • Main Results: 1.76% to 0.46% gap reduction is achieved on TSP-500, while TSP-1000 improves from 2.46% to 1.17% and TSP-10000 from 3.19% to 2.58% with MCTS decoding.Most previous probabilistic solvers are untrainable at these scales and are compared using TSP-100-trained models.
  • Main Results: A model trained on TSP-50 performs well on TSP-1000 and TSP-10000, indicating strong cross-scale generalization.The reported performance uses greedy decoding with 2-opt.

5 Experiments with MIS

MIS experiments evaluate DIFUSCO on SATLIB and Erdős-Rényi graphs, two challenging graph families. DIFUSCO strongly outperforms prior methods on SATLIB but performs poorly on ER-[700-800], potentially reflecting a backbone inductive-bias mismatch.

  • Experimental Settings: MIS evaluation uses SATLIB graphs reduced from CNF SAT instances and ER-[700-800] random graphs with connection probability p = 0.15.The benchmarks were selected because recent methods struggle on both graph types.
  • Experimental Settings: SATLIB and ER evaluations report independent-set size, optimality gap, and latency time without graph reduction or 2-opt local search.Local-search post-processing is disabled for fair comparison.
  • Results and Analysis: 0.63% to 0.21% gap reduction is achieved by DIFUSCO on the SATLIB benchmark.The result is reported relative to the gap between ground-truth and neural solvers.
  • Results and Analysis: DIFUSCO does not perform well on ER-[700-800], especially with discrete diffusion, unlike its SATLIB performance.The authors hypothesize that the edge-based Anisotropic GNN’s inductive bias may be unsuitable for ER graphs.

6 Concluding Remarks

The paper concludes that DIFUSCO is a graph-based diffusion framework for NP-complete combinatorial optimization, with discrete diffusion and cosine inference performing well on TSP and MIS. Its training can use near-optimal heuristic solutions, while broader problem coverage and improved architectures remain future work.

  • Concluding Remarks: DIFUSCO compares continuous Gaussian-noise and discrete Bernoulli-noise graph diffusion models for NP-complete combinatorial optimization.The framework represents solutions as discrete selection vectors and uses graph-based diffusion modeling.
  • Concluding Remarks: DIFUSCO achieves state-of-the-art results on TSP and MIS, surpassing previous probabilistic neural solvers in accuracy and scalability.The conclusion identifies discrete diffusion and cosine inference as important design choices.
  • Concluding Remarks: Future work targets broader NPC problems, equivariant graph neural networks for geometric tasks, and accelerated diffusion inference.Mixed Integer Programming is given as one example of a broader target problem class.
  • Concluding Remarks: DIFUSCO reaches state-of-the-art performance on TSP-500/1000/10000 when trained with near-optimal LKH-3 solutions instead of exact optima.The authors state that exact optimal solutions are not required for training.

A.2 This work simply applies discrete diffusion models to combinatorial optimization problems. Could you clarify the significance of this work in the field?

The work extends diffusion modeling from image and video generation to NP-complete combinatorial optimization through a graph-based formulation. Its significance lies in modeling node or edge selection explicitly while evaluating Gaussian and Bernoulli diffusion and an inference schedule.

  • DIFUSCO introduces graph-based diffusion models for solving NP-complete combinatorial optimization problems.
  • The framework uses diffusion models as a new approach for NP-complete problems rather than extending their established image- and video-generation applications.
  • The method formulates NP-complete problems as discrete {0, 1}-vector optimization and generates solutions with graph-based denoising diffusion.
  • DIFUSCO compares Gaussian-noise continuous diffusion with Bernoulli-noise discrete diffusion and introduces an inference schedule to improve generation quality.

A.4 Why is there no demonstration for the time-cost in the results shown in Table 1, and why are there some conflicts in the metrics of Length and Gaps?

Table 1 omits runtime because baseline methods used different hardware, making direct comparison uninformative. Reported Length and Gap conflicts may reflect rounding in prior papers, while a small DIFUSCO gap is attributed to Concorde’s integer-coordinate restriction.

  • Runtime is omitted from Table 1 because baseline methods were evaluated on different hardware, making comparison not meaningful.
  • Reported conflicts between Length and Gap metrics may be caused by rounding issues in numerical values copied from previous papers.
  • The -0.01 gap in DIFUSCO is attributed to Concorde accepting only integer coordinates, which can produce inaccurate non-optimal solutions after rounding.

A.5 How can we effectively evaluate the usefulness of the proposed method when the training time is also a consideration?

Usefulness should be assessed primarily through inference-time and solution-quality behavior across deployment instances, while recognizing that training time is treated differently in neural-solver comparisons. The supplied evaluations expose diffusion-step, sampling, decoding, generalization, and runtime trade-offs.

  • Inference time is the primary focus because a trained model can process virtually unlimited unseen graph instances during deployment.
  • Performance evaluation: Figure 4 compares performance gaps for continuous and discrete diffusion across diffusion steps and parallel sample counts without 2-opt post-processing.
  • Runtime evaluation: Figure 5 decomposes per-instance runtime into neural-network execution, greedy decoding, and 2-opt components.
  • Generalization evaluation: Generalization tests evaluate discrete DIFUSCO across TSP scales with and without 2-opt post-processing.

C Additional Results

Additional experiments examine diffusion choices, decoding, runtime, generalization, and extensions beyond graph-based problems. Across these tests, discrete diffusion and DIFUSCO's search strategies show strong performance, including on real-world TSPLIB data.

  • Discrete diffusion models consistently outperform continuous counterparts on TSP-100 across various settings.
  • 20 diffusion steps × 4 samples significantly outperforms 1 diffusion step × 1024 samples while using 18.5× less runtime, without 2-opt post-processing.
  • 2-opt consumes a non-negligible portion of runtime, especially when only 1 or 2 diffusion steps are used.
  • DIFUSCO remains significantly ahead of DIMES when both use 2-opt post-processing on large-scale TSP instances.
  • 0.29% gap versus 1.48% for the best baseline is reported on real-world TSPLIB data, with DIFUSCO trained on synthetic TSP instances.
  • MCTS decoding improves DIFUSCO performance when applied to diverse heatmaps, although using 2x or 4x decoding increases runtime.
  • The {0, 1}^N vector-space formulation can represent non-graph-based NPC problems such as mixed integer programming with linear or quadratic constraints.

E Additional Experiment Details

The experiments define evaluation metrics, training and hardware settings, decoding procedures, and diffusion inference mechanisms. DIFUSCO uses greedy or sampling-based decoding, with MCTS as an advanced TSP search strategy.

  • TSP evaluation reports average predicted tour Length, relative-performance Gap, and total solution-generation Time.
  • MIS evaluation reports average independent-set Size, with Gap and Time defined analogously to TSP.
  • All methods use 8× NVIDIA Tesla V100 GPUs for training and one V100 GPU plus 40 Intel Xeon CPUs for evaluation.
  • DIFUSCO reports results averaged over 5 random seeds because diffusion models can generate arbitrary samples from their learned distribution.
  • Greedy decoding samples one solution from pθ(x0), while parallel sampling starts diffusion models from different noise values and selects the best solution.
  • For TSP, MCTS samples k-opt actions guided by diffusion heatmaps and repeats simulation, selection, and back-propagation until no improving actions remain.
  • DDIM accelerates continuous-diffusion inference by defining the forward process on an increasing subsequence of diffusion time steps.
  • Discrete diffusion uses an analogous marginal and posterior construction, with transition products represented by Qt′,t = Qt′+1 ... Qt.

H Experiment Baselines

The experiments compare DIFUSCO with traditional operations-research solvers and learning-based neural methods across TSP and MIS benchmarks. Qualitative figures additionally illustrate schedules, diffusion steps, and success or failure cases.

  • TSP-50/100: TSP-50 and TSP-100 evaluations compare DIFUSCO with 10 baselines spanning exact, heuristic, and learning-based methods.
  • TSP-500/1000/10000: Large-scale TSP-500, TSP-1000, and TSP-10000 evaluations use 9 baselines, including Concorde, Gurobi, LKH-3, Farthest Insertion, and neural solvers.
  • Qualitative results: Qualitative discrete-DIFUSCO figures vary diffusion steps and schedules across TSP-50, TSP-100, and TSP-500 examples.
  • Qualitative results: A continuous-DIFUSCO figure compares linear and cosine schedules using 20 diffusion steps.
  • TSP-500/1000/10000: Except for Att-GCN and DIMES, the listed large-scale TSP baselines are trained on small graphs and tested on large graphs.
  • MIS: MIS comparisons include Gurobi and KaMIS alongside reinforcement-learning solvers LwD and DIMES and supervised-learning solvers Intel and DGL.
  • Qualitative results: A TSP-100 qualitative figure contrasts a successful tour with a failure that does not visit every node exactly once.
Loading 2302.08224v2…