# Efficient Combinatorial Optimization via Heat Diffusion

arXiv: https://arxiv.org/abs/2403.08757 · HTML: https://mlsanity.com/paper/2403.08757/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 64 references that are in the map.
- First posted on arXiv 13 Mar 2024.

## Builds on (most cited first, 16 of 16)

- [Diffusion Models: A Comprehensive Survey of Methods and Applications](https://mlsanity.com/paper/2209.00796/) (2022)
- [A Survey of Quantization Methods for Efficient Neural Network Inference](https://mlsanity.com/paper/2103.13630/) (2021)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [Traffic flow optimization using a quantum annealer](https://mlsanity.com/paper/1708.01625/) (2017)
- [Accelerating Score-based Generative Models with Preconditioned Diffusion Sampling](https://mlsanity.com/paper/2207.02196/) (2022)
- [Efficient Optimization with Higher-Order Ising Machines](https://mlsanity.com/paper/2212.03426/) (2022)
- [Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods](https://mlsanity.com/paper/2312.16775/) (2023)
- [Gradient-Based Adaptive Stochastic Search for Non-Differentiable Optimization](https://mlsanity.com/paper/1301.1333/) (2013)
- [Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing](https://mlsanity.com/paper/2108.08064/) (2021)
- [Network of Evolvable Neural Units: Evolving to Learn at a Synaptic Level](https://mlsanity.com/paper/1912.07589/) (2019)

## Built on by (most cited first, 2 of 2)

- [Graph Coloring Using Heat Diffusion](https://mlsanity.com/paper/2404.14457/) (2024)
- [Binary Quadratic Quantization: Beyond First-Order Quantization for Real-Valued Matrix Compression](https://mlsanity.com/paper/2510.18650/) (2025)

## Abstract (arXiv)

Combinatorial optimization problems are widespread but inherently challenging due to their discrete nature. The primary limitation of existing methods is that they can only access a small fraction of the solution space at each iteration, resulting in limited efficiency for searching the global optimal. To overcome this challenge, diverging from conventional efforts of expanding the solver's search scope, we focus on enabling information to actively propagate to the solver through heat diffusion. By transforming the target function while preserving its optima, heat diffusion facilitates information flow from distant regions to the solver, providing more efficient navigation. Utilizing heat diffusion, we propose a framework for solving general combinatorial optimization problems. The proposed methodology demonstrates superior performance across a range of the most challenging and widely encountered combinatorial optimizations. Echoing recent advancements in harnessing thermodynamics for generative artificial intelligence, our study further reveals its significant potential in advancing combinatorial optimization.