Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization

Colin Doumont, Victor Picheny, Viacheslav Borovitskiy, Henry B. Moss

Abstract

This paper reveals that many popular, complex kernels used in combinatorial Bayesian Optimization (BO) are mathematically equivalent to "heat kernels" on graphs. By unifying these methods, we show that a surprisingly simple pipeline—standard RBF kernels applied to one-hot encoded data—can match or outperform state-of-the-art algorithms while being significantly faster and easier to implement. Our findings suggest that much of the complexity in current combinatorial BO literature can be collapsed into a single, robust category of heat-based kernels.

Introduction

Bayesian Optimization (BO) is a powerful tool for optimizing "black-box" functions that are expensive to evaluate, such as finding the best architecture for a neural network or the most stable protein sequence. While BO is well-understood for continuous spaces, it becomes significantly more complex in combinatorial spaces (e.g., choosing a sequence of categories or nodes in a graph).

Over the years, researchers have developed a "zoo" of specialized kernels—mathematical functions that measure similarity between points—to handle these discrete domains. Methods like CASMOPOLITAN, COMBO, and BOSS all use different mathematical justifications. This fragmentation makes it difficult for practitioners to know which kernel to choose and obscures the fact that many of these "novel" kernels are simply different perspectives on the same underlying mathematics.

Unifying Combinatorial Kernels via Heat Kernels

The authors introduce a unifying framework based on heat kernels (also known as diffusion kernels). Their key contributions include:

  1. Mathematical Unification: They prove that CASMOPOLITAN (which uses Hamming distance) and COMBO (which uses graph theory) are both equivalent to heat kernels on a "Hamming graph."
  2. The One-Hot Shortcut: They demonstrate that a heat kernel on a Hamming graph is exactly equivalent to taking categorical data, one-hot encoding it, and applying a standard RBF (Gaussian) kernel. This means practitioners can achieve state-of-the-art results using standard BO libraries without specialized graph-based software.
  3. Padded Sorting: To handle permutation invariance (where the order of elements doesn't matter, like a bag of ingredients), they propose a "padded sorting" trick. This allows the kernel to recognize similarity between sets of different sizes more effectively than standard sorting.

Experimental Results and Robustness

The framework was evaluated on a diverse set of benchmarks, including synthetic functions (Pest Control, LABS), biological design (RNA folding), and Neural Architecture Search (NAS-Bench-101/201).

Empirical Equivalence and Speed

In controlled experiments where only the kernel was changed, all heat-based and Hamming-based kernels achieved nearly identical performance across all benchmarks. Furthermore, the implementation of the heat kernel via the one-hot RBF shortcut is more than 2x faster than the original implementation of the COMBO kernel.

Robustness to Optima Location

A critical insight of this research is the "structural bias" found in some state-of-the-art kernels. Specialized kernels like BODi (HED) and BOSS (SSK) perform well only if the optimal solution has a specific structure (e.g., repeated values). When the authors "relocated" the optima to random positions, these specialized kernels failed to converge, while heat kernels remained robust.

Figure 1: Performance comparison across synthetic benchmarks. The top row shows standard benchmarks, while the bottom row shows performance when the optima are relocated. Heat kernels (including the one-hot RBF shortcut) show consistent performance and robustness compared to specialized baselines.

Discussion and Limitations

The paper argues against unnecessary complexity. By stripping away the overhead of nested embeddings or message-passing, the authors found that well-tuned "standard" components are often superior. On neural architecture search tasks, their permutation-invariant heat kernel even outperformed the specialized Weisfeiler-Lehman (WL) graph kernel.

However, there are limitations to this general-purpose approach. If a researcher has deep prior knowledge about a domain (e.g., specific chemical properties), specialized kernels or deep generative models might still be preferable. Additionally, while the math simplifies cleanly for categorical variables, ordinal variables (where order matters, like "small, medium, large") require further exploration, potentially using path graphs.

Conclusion

By identifying the omnipresence of heat kernels, this work simplifies the landscape of combinatorial Bayesian Optimization. The proposed one-hot RBF pipeline provides a powerful, fast, and easy-to-implement baseline that matches or exceeds the performance of far more complex specialized algorithms.

Summary updated

BibTeX
@inproceedings{doumont2025omnipresent,
  author = {Colin Doumont and Victor Picheny and Viacheslav Borovitskiy and Henry B. Moss},
  title = {{Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=hdT7UC7oG6},
}
Figure