Research map / Probabilistic and scientific modeling / Bayesian optimization
Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that CASMOPOLITAN, COMBO and other combinatorial kernels are equivalent to heat kernels on Hamming graphs, and that a simple heat-kernel GP pipeline with a genetic algorithm and trust region matches state-of-the-art combinatorial BO methods.
Problem
Combinatorial Bayesian optimization relies on many specialized kernels whose relationships are poorly understood, and benchmark comparisons are confounded by differing pipeline components.
Approach
Derives a unifying framework in which most combinatorial kernels are heat kernels on Hamming graphs (or members of the Hamming-kernel / Phi-kernel classes), giving closed-form expressions that avoid numerical eigendecomposition and showing that the heat-kernel pipeline is insensitive to the location of optima.
Key results
- CASMOPOLITAN, COMBO and the heat kernel obtain near-identical performance across problems, empirically confirming the theoretical equivalence.
- Performance of BODi (HED) and BOSS (SSK) degrades substantially when optima are relocated, while heat and Hamming kernels are unaffected.
- The simple heat-kernel pipeline (RBF after one-hot encoding, genetic algorithm, trust region) matches or outperforms baselines after relocation and has the third-lowest wall-clock time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use heat, Hamming, or related kernels instead of other kernels while keeping the BO pipeline fixed | Fixed combinatorial BO pipeline · Five combinatorial optimization problems | optimization performance | No clear effect |
| Relocate the optimum | BODi with HED · Combinatorial optimization problems from Bounce | optimization performance | Hurt |
| Relocate the optimum | BOSS with SSK · Combinatorial optimization problems from Bounce | optimization performance | Hurt |
| Relocate the optimum | Heat and Hamming kernels · Combinatorial optimization problems from Bounce | optimization performance | No clear effect |
| Use a simple heat-kernel pipeline with a one-hot RBF kernel, genetic algorithm, and trust region | Combinatorial BO · Combinatorial optimization benchmarks after relocating optima | optimization performance | Helped |
| Use a simple heat-kernel pipeline with a one-hot RBF kernel, genetic algorithm, and trust region | Combinatorial BO · Evaluated baselines | wall-clock time | Helped |
| Replace numerical eigendecomposition with the analytic heat-kernel expression | COMBO kernel implementation · Categorical variables | speed: more than $2\times$ improvement in speed | Helped |
| Incorporate additive structure | Heat-kernel methods · Standard combinatorial BO benchmarks | optimization performance | Hurt |
| Incorporate additive structure | Heat-kernel methods · Biological datasets | optimization performance | Helped |
| Use group-invariant heat kernels | Heat-kernel methods · Permutation-invariant functions | optimization performance | Helped |
| Use group-invariant heat kernels | Heat-kernel methods · String-kernel comparison | wall-clock time | Helped |
| Use group-invariant heat kernels | Heat-kernel methods · Neural-architecture-search problems | optimization performance | No clear effect |
Surprising findings
- SSK and HED degrade substantially when optima are relocated, suggesting sensitivity to the structure of the optimum rather than general performance.
- Counterexample shows Hamming kernels on unequal-size factors can have more distinct eigenvalues than Phi-kernels, so the equivalence requires equal set sizes.
Limitations
- Results hold only for settings with little or no a priori information; not for molecules or large pretrained libraries.
- Theory assumes categorical (unordered) variables; ordinal variables not covered by the theorems or experiments.
- Equivalence of Hamming and Phi-kernel classes requires equal-sized finite sets.
Experimental setup
Datasets: Pest Control LABS Cluster Expansion Contamination Control MaxSAT SFU test functions MCBO biological tasks MCBO logic-synthesis tasks
Benchmarks: Pest Control LABS Cluster Expansion Contamination Control MaxSAT SFU test functions MCBO biological tasks MCBO logic-synthesis tasks
Metrics: optimization performance over iterations wall-clock time
Baselines: COMBO CoCaBO BOSS CASMOPOLITAN BODi RDUCB Bounce
Builds on: CASMOPOLITAN COMBO Bounce BOSS MCBO benchmark
Closest papers by meaning
- Efficient Combinatorial Optimization via Heat Diffusion (NeurIPS 2024 · similarity 0.88)
- Automated Kernel Discovery Towards Understanding High-dimensional Bayesian Optimization (NeurIPS 2026 · similarity 0.87)
- Adaptive Kernel Design for Bayesian Optimization Is a Piece of CAKE with LLMs (NeurIPS 2025 · similarity 0.87)
- Bayesian Optimization of Functions over Node Subsets in Graphs (NeurIPS 2024 · similarity 0.87)
- Kernel-based guarantees for nonlinear parametric models in Bayesian optimization (NeurIPS 2026 · similarity 0.86)
- Regularized Langevin Dynamics for Combinatorial Optimization (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.