# Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 47 references that are in the map.
- First posted on arXiv 30 Oct 2025.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search](https://mlsanity.com/paper/2001.00326/) (2020)
- [NAS-Bench-101: Towards Reproducible Neural Architecture Search](https://mlsanity.com/paper/1902.09635/) (2019)
- [Combinatorial Bayesian Optimization using the Graph Cartesian Product](https://mlsanity.com/paper/1902.00448/) (2019)
- [Mat'ern Gaussian Processes on Graphs](https://mlsanity.com/paper/2010.15538/) (2020)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [Bayesian Optimisation over Multiple Continuous and Categorical Inputs](https://mlsanity.com/paper/1906.08878/) (2019)
- [BOSS: Bayesian Optimization over String Spaces](https://mlsanity.com/paper/2010.00979/) (2020)
- [Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces](https://mlsanity.com/paper/2102.07188/) (2021)
- [NAS-Bench-Suite: NAS Evaluation is (Now) Surprisingly Easy](https://mlsanity.com/paper/2201.13396/) (2022)
- [Are Random Decompositions all we need in High Dimensional Bayesian Optimisation?](https://mlsanity.com/paper/2301.12844/) (2023)
- [Bounce: Reliable High-Dimensional Bayesian Optimization for Combinatorial and Mixed Spaces](https://mlsanity.com/paper/2307.00618/) (2023)
- [Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings](https://mlsanity.com/paper/2303.01774/) (2023)
- [Group kernels for Gaussian process metamodels with categorical inputs](https://mlsanity.com/paper/1802.02368/) (2018)
- [Additive Gaussian Processes Revisited](https://mlsanity.com/paper/2206.09861/) (2022)
- [Framework and Benchmarks for Combinatorial and Mixed-variable Bayesian Optimization](https://mlsanity.com/paper/2306.09803/) (2023)
- [AI-optimized detector design for the future Electron-Ion Collider: the dual-radiator RICH case](https://mlsanity.com/paper/1911.05797/) (2019)
- [Return of the Latent Space COWBOYS: Re-thinking the use of VAEs for Bayesian Optimisation of Structured Spaces](https://mlsanity.com/paper/2507.03910/) (2025)
- [Low Autocorrelation Binary Sequences](https://mlsanity.com/paper/1512.02475/) (2015)
- [Isotropic Gaussian Processes on Finite Spaces of Graphs](https://mlsanity.com/paper/2211.01689/) (2022)
- [Bayesian Optimisation of Functions on Graphs](https://mlsanity.com/paper/2306.05304/) (2023)
- [Invariances of random fields paths, with applications in Gaussian Process Regression](https://mlsanity.com/paper/1308.1359/) (2013)

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

- [Heat and Mat'ern Kernels on Matchings](https://mlsanity.com/paper/2604.14331/) (2026)

## Abstract (arXiv)

Bayesian Optimization (BO) has the potential to solve various combinatorial tasks, ranging from materials science to neural architecture search. However, BO requires specialized kernels to effectively model combinatorial domains. Recent efforts have introduced several combinatorial kernels, but the relationships among them are not well understood. To bridge this gap, we develop a unifying framework based on heat kernels, which we derive in a systematic way and express as simple closed-form expressions. Using this framework, we prove that many successful combinatorial kernels are either related or equivalent to heat kernels, and validate this theoretical claim in our experiments. Moreover, our analysis confirms and extends the results presented in Bounce: certain algorithms' performance decreases substantially when the unknown optima of the function do not have a certain structure. In contrast, heat kernels are not sensitive to the location of the optima. Lastly, we show that a fast and simple pipeline, relying on heat kernels, is able to achieve state-of-the-art results, matching or even outperforming certain slow or complex algorithms.