Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization
Authors: Colin Doumont
Victor Picheny
Viacheslav Borovitskiy
Henry Moss
Venue: NeurIPS 2025 poster ()
Keywords: Bayesian Optimization
Combinatorial Spaces
Heat Kernels
Primary area: probabilistic_methods

Abstract: 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.

Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization
Colin Doumont
Victor Picheny
ETH Zürich
Secondmind
University of Cambridge Tübingen Al Center
Viacheslav Borovitskiy
Henry Moss
ETH Zürich University of Edinburgh
University Cambridge
Lancaster University
Abstract
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 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-ee results, matching or even outperforming certain slow or complex algorithms.
Introduction
Many real-world challenges can be framed as optimization problems, where the objective functions expensive-to-evaluse and black-box. For this type of problems. Bayesian Optimization (BO) has emerged as a preferred approach, successfully solving problems from tuning machine- learning algorithms (Snock et al., 2012) to designing detectors for particle physics (Cisbani al., 2020).
Although BO has mostly been concerned with continuous domains, recent years, multiple methods have been developed to extend BO to combinatorial domains, such as strings in genetic design (Moss al., 2020) or graphs in neural architecture search (Ru al., 2020b). These new methods often consist of pipeline involving multiple components, making it hard to know how each individual component affects the overall empirical performance. For example, the pipelines from CASMOPOLITAM (Wan et al., 2021) and COMBO (Oh et al., 2019) are often chosen baselines for other methods, but their components are never evaluated individually.
In first attempt to bridge this gap, Dreczkowski et al. (2024) introduced modular benchmark, divid- ing combinatorial BO pipelines into three key components: (i) combinatorial kernel, function optimizer, and (iii) presence of trust region. Using this distinction, the authors are able
(ii) acquisition-
Equal supervision.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

to assess the performance of the individual components, rather than the full pipeline. However, it remains unelear how different combinatorial kernels (i.e. the first component) relate to one another and what properties are responsible for their success.
In this paper, we aim to provide clearer picture of combinatorial kemnels and unify them into common framework based on heat kernels. First, we present the necessary background information on combinatorial BO and the associated combinatorial kernels (Section 2). To relate these kernels, we then present our unifying framework, based on heat kernels, as well as our generalizations and extensions thereof (Sections 3). Finally, we analyze and validate our theoretical framework using empirical experiments (Section 4), and conclude by discussing our contributions (Section 5).
2 Background and related work
In the next sections, we give a short introduction to (continuous) Bayesian optimization (Section 2.1) and combinatorial Bayesian optimization (Section 2.2), as well as provide overview of existing combinatorial kernels (Section 2.3).
2.1 Bayesian optimization
Bayesian optimization (Garnett, 2023) aims to find the global optimum x" E X of an expensive black-box function f X' + R. BO constructs probabilistic model of f. often using a Gaussian Process (GP). which estimates (x) at previously unseen locations of such estimates. The probabilistic model is used to define an acquisition function a(x), which balances exploration and exploitation. The next point to evaluate is selected by maximizing the acquisition function:
X. and quantifies uncertainty
X arg max (x). xeX
By iteratively updating the model with new observations and selecting points that maximize a, BO aims to efficiently converge to the global optimum, while minimizing the number of costly evaluations of f.
The GP is specified by a mean function and a covariance function or kernel k(x, x') X x X + I (Rasmussen and Williams, 2006). When X' C RR"," common choice is the RBF kernel:
(z; x1a) 2 i=1
1
ky (xxxx) = cxp
where 4 are the lengthscales. By assigning one lengthscale per dimension rather than a single global lengthscale, the model can automatically assess the importance of each input dimension. This feature is also known as Automatic Relevance Determination (ARD).
2.2 Combinatorial Bayesian optimization
In this paper, instead of considering Euclidean input spaces, we assume X' a product X X x X; of finite sets X, By defining X' in this way. encompass many domains of interest for real-world applications, such as categorical variables, strings, or even graphs. However, we emphasize that the above definition of X' does not encompass ordinal variables, since define X; sets (unordered) and not sequences (ordered). As a result, all theorems in this paper hold for categorical variables, but not necessarily for ordinal variables. Nevertheless, in Appendix B. we argue that truly ordinal variables are a rare exception in combinatorial Bayesian optiiization, and the results in this paper thus apply to nearly all previous works in the field.
Performing Bayesian optimization on this combinatorial input space consists of two major chal- lenges: surrogate modeling and acquisition ffncciinn optimization. Often, the two challenges treated separately, with different combinatorial BO methods having either the same surrogate model the same rgquisition-functioo optimizer (Dreczkowski al., 2024). In this work, only focus on surrogate modeling and use pre-existing methods for acquisition-function optimization.
There are three primary ways to define surrogate models combinatorial spaces:

---

1. Use inherently discrete models, such as random forests in SMAC (Hutter et al., 201 I), the Tree-structured Parzen Estimator in TPE (Bergstra al., 2011) 1) or a sparse Bayesian linear model in BOCS (Baptista and Poloczek, 2018).
2. Map input points to a Euclidean space, after which a continuous model (often GP) can be used. This is usually done for tasks where there already exists a large library of relevant structures, enabling deep generative models to create continuous latent space (Griffiths and Hemández-Lobatto 2020; Moss et al., 2025). A common example of such a library is the ZINC database (Irwin and Shoichet, 2005), which is curated collection of commercially available chemical compounds.
3. Use combinatorial kernels, which we define as kernels k(x,x') x - IR that directly take elements combinatorial space input. Through the development of custom- custom-made combinatorial kernels for specific tasks, GPs have successfully achieved performance on Bayesian optimization problems across different combinatorial domains (Ru et al., 2020b; Moss et al., 2020; Tripp and Hernández-Lobato, 2024).
For tasks where little or no prior information is available, GPs with combinatorial kernels have consistently outperformed other models (Papenmeier al., 2023; Dreczkowski et al., 2024), and are therefore the focus of this paper. We present a short overview of combinatorial kernels in the following section.
2.3 Kernels on combinatorial spaces
The Hamming distance is recurring element in the literature on combinatorial kernels, because it represents a natural way of defining the similarity between two points x and x' in the combinatorial space X. Essentially, the Hamming distance measures the minimum number of substitutions required change one vector x into the other vector x'. More formally, we define the Hamming distance as h (x, x') = Σx= 5 x/), where x, x' E X' are vectors of size and 8 (-,-) is the Kronecker delta function. Therefore, the Hamming distance in fact nothing more than one-hot encoding the data followed by the squared Euclidean distance (divided by two). That is,
h (x,x') = 1z-2'11//2
(I)
where z, z' f0, 1).d are the one-hot encoded versions of x X, with Σn= | Equation 1 a first step in providing more unified view on combinatorial kernels, and implicitly used the following paragraph to present existing combinatorial kernels in terms of only the Hamming distance, rather than a mixture of Hamming and Euclidean distances (after one-hot encoding).
Hamming-ban based kernels large proportion existing combinatorial kernels rely on the Hamming distance in form another. For example, CASMOPOLITAN and Bounce use the well-known RBF and Matérn kernels, respectively, but replace the squared Euclidean distance by the Hamming distance (Wan et al., 2021; Papenmeier al., 2023). Rather than using the Hamming distance directly, COMBO proposes to model X' as a Hamming graph G = (X¹,E) E) (Imrich et al., 2000), where the nodes x, x' E X are connected by an edge only when they have Hamming distance of one (Oh al., 2019). Once X' has been transformed into G, graph kernel (Kondor and Lafferty. 2002) is applied on G. Although this graph-based approach appears different to the more direct approach taken in CASMOPOLITAN and Bounce, we show in Section 3 that both approaches are closely related. Similarly to COMBO. Deshwal et (2023) also propose to first transform the input space X' before applying kernel on this transformed space. More specifically, the authors introduce the idea of Hamming Embedding via Dictionaries (HED), which embeds categorical inputs into an ordinal feature space, on which standard continuous kernels can be applied. They name the method BODi.
Kernels for specific domains Some onte-of-the-art kernels have been developed with specific spaces X' in mind. For example, for string spaces, Moss et al. (2020) introduce BOSS, which uses an efficient dynamic programming algorithm to compute the Sub-sequence String Kernel (SSK) from Lodhi al. (2002). Similarly, for graphs, Ru et al. (2020b) develop NASBOWL, which uses the - (WL) kernel from Shervashidze et al. (2011) to perform neural architecture search.
3

---

3 Unifying framework
In this section, we show that most of the general-purpose kernels from the combinatorial BO literature are in fact closely related or even identical. Specifically, we provide a unifying framework based on heat kernels (Section 3.1), showing that most combinatorial kernels are either heat kernels (Sec- tions 3.2 and 3.3) or part of certain generalized class containing heat kernels (Section 3.4). Moreover, we extend our heat-kernel framework to group invariances and additive structures (Section 3.5).
3.1 Heat kernels for combinatorial Bayesian optimization
Heat kernels, also called diffusion kernlls, are natural family of kernels on graphs (but not between graphs). More specifically, these graph kernels are based on the heat equation and can be regarded as the discrete counterparts of the familiar RBF kernel over Euclidean spaces. We refer readers to Kondor and Lafferty (2002) for more detailed explanation.
Before defining heat kernels more formally, we first clarify the necessary terminology. For the remainder of this paper, when we consider arbitrary graph 9 (V, we assume this graph to be unweighted, undirected and without loops. Additionally, we define the graph Laplacian of g gas A D A, where A is the adjacency matrix and D is the diagonal degree matrix, namely D: E == A.j. Using the graph Laplacian, we can define heat kernels as follows.
Definition 1. Let (Aj be the eigenpairs of the Laplacian of a graph g (V, then the heat kernel is given by
M
Kg 2x, = Σ 2A
(z)
1=1
where x, x' E V and is hyperparameter.
Transforming X' into G Since we defined the input space X' as being the product of finite sets X; (see Section 2.2), we can naturally view X' as being product graph 9, where each subgraph G, = (X, & contains the elements of X, as nodes. To specify the set of edges & between these nodes, different options may seem natural depending on the setting at hand. Possible examples include cycle graph or simple path structures, but, for our setting, perhaps the most straightforward are complete graphs. By connecting all elements in X, we explicitly incorporate the fact that all elements are "equally distant", which seems reasonable when we have no prior information about X, We call this transformed input space the Hamming graph and define as follows.
Definition 2. Assume X' is an n-dimensional space that decomposes as 3=1 Xr, where each X, is finite set. Then, we can transform X' into a corresponding Hamming graph G = (X,E)(e by
g
Gi
where D is the graph Cartesian product and G. (Xg, E,) are complete unweighted graphs (Imrich et al., 2000).
Kondor and Lafferty (2002) show that, when applied to the Hamming graph of Definition 2, the heat kernel from Equation 2 simplifies to
-89.
6 (m.
( x') &
(gi 1)e- 39:
where g. = | and 3 > 0 is the same hyperparameter as in Equation 2. Additionally, when 3 is replaced with 3, we obtain the ARD version. Among others, the above simplification is due to the graphs G, being complete, which means the eigenpairs can be computed analytically, and there is no need for expensive numerical eigendecooposition.
In Appendix C, we argue that heat kernels provide natural measure of covariances on combinatorial spaces, arising from two natural explicit assumptions. Furthermore, in Appendix D.2, we demonstrate that relaxing one of these assumptions allows us to easily extend heat kernels to additive structures, connecting them to well well-known combinatorial kernels.

---

3.2 CASMOPOLITAN and COMBO are heat kernels
CASMOPOLITAN (Wan et al., 2021) and COMBO (Oh et al., 2019) are two established methods for combinatorial BO, and are included in all recent benchmarks (Deshwal et al., 2023; Papenmeier et al., 2023: Dreczkowski al., 2024). For surrogate modeling, both methods use GP and introduce the following combinatorial kernels.
Definition 3. Let .) be the Kronecker delta function, then the CASMOPOLITAN kernel is given by
kr (x.x') exp 1 Σ (
where x, x' E N' and & > 0 are hyperparameters (the lengthscales).
As hinted in Section 2.3, CASMOPOLITAN be seen the analog of the RBF kernel, where the squared Euclidean distance is replaced by the ARD version of the Hamming distance. In fact, by virtue of Equation 1, the non-ARD version of CASMOPOLITAN equivalent to one-hot encoding x, x' E X' and using the RBF kernel.
Definition 4. Let 9 = (X, E) be a Hamming graph as in Definition and (f) be the eigenpairs of the Laplacian the graph G. = (X,, E,), then the COMBO kernel is given by
ka (x,
II
e - (1.) ()
(5)
=1
where x, x' E X' and 3: > 0 are hyperparameters.
Although at first sight the kernels from CASMOPOLITAM and COMBO might seem like two separate methods, they are in fact closely related and can both be seen as heat kernels on Hamming graph. We formalize this statement in the following theorem.
Theorem 5. The kernels from CASHOPOLITAN and COMBO equivalent to heat kernels Hamming graph. That is, Equations and are proportional to (the ARD version of) Equation
Proof. See Appendix A.I.
3.3
New insights into combinatorial kernels
Theorem results in multiple new insights, both theoretical and practical.
3.3.1
CASMOPOLITAN and COMBO rely on the same kernel
This result follows directly from Theorem 5, since Equation 4 and 5 are now also equivalent. To the best of our knowledge, this equivalence between the kernlss of CASMOPOLITAN and COMBO has never been established before, with most recent papers using the two methods on the same benchmarks (Deshwal al., 2023; Papenmeier et al., 2023). However, because both kernels are often benchmarked with markedly different hyperparameter priors and acquisition-funee with implementation errors (Papenmeier al., 2023), this theoretical equivalence has never been visible empirically (Dreczkowski et al., 2024). In Section 4, we control for these different factors, and demonstrate that this theoretical equivalence also translates an empirical equivalence. That is, the kernels from CASMOPOLITAL and COMBO, as well as the heat kernel (on Hamming graph) from Equation 3, obtain the same performance our experiments.
optimizers, sometimes even
3.3.2 Heat kernels (on Hamming graphs) are RBF kernels after one-hot encoding
Combining Theorem 5 and Equation 1, we have: heat kernlls (on Hamming graphs) are equivalent to CASMOPOLITAN's kernel, which itself equivalent the RBF kernel after one-hot encoding. This connection means that heat kernels (on Hamming graphs) can easily be implemented, requiring only one additional line to one-hot encode data before using standard implementations of the RBF kemel. For the ARD version, however, this equivalence does not hold, and Equation 3 should be used instead. Borovitskiy al. (2023) demonstrate similar relationship for binary variables, but, to the best of our knowledge, the extension to categorical variables has never been shown before.
5

---

3.3.3 Faster implementation of COMBO (for categorical variables)
The existing implementations of COMBO (Oh et al., 2019; Dreczkowski et al., 2024) currently happen as follows: (i) perform numerical eigendecomposition obtain the eigenpairs (x.. fj)) and (ii) use these eigenpairs to compute Equation 5. Instead, Theorem presents a faster solution: use Equation 4 (or the ARD version of Equation 3), which implicitly computes the analytic eigendecomposition, rather than relying on expensive numerical eigendecomposition. As a result, the current implementation of COMBO's kerel can be improved from O ( [xa]) to O (n). For our experiments in Section 4,
this improved implementation resulted more than 2x improvement in speed (see Appendix E.6). Although this result is only true for categorical variables, we note that most recent benchmarks in combinatorial Bayesian optimization do not contain any ordinal variables (Deshwal et al., 2023; Papenmeier et al., 2023; Dreczkowski et al., 2024).
3.4 Generalizing heat kernels: Hamming- and graph-based approaches
This connection between the Hamming- approach from CASMOPOLITAN and the graph- based approach from COMBO leads us to wonder how closely related these two approaches are. In the next sections, formally define both approaches and show that they deeply connected.
3.4.1 Hamming-bawe based approach
To generalize CASMOPOLITAN into a broader class kernels, we identify its main idea: leveraging a well-known continuous (isotropic) kernel (i.e. the RBF kemne), but substituting the standard Euclidean distance with the square root of the Hamming distance. Based on this foundational idea, we define the following class of kernels.
Definition 6. We define Hamming kernels as being kernels who only depend on x and x' through the square root of the Hamming distance h(x,, x'), namely
k k(x,x') x') k (Vh(x,x)))
for some k: : {0, VI, V2....
vn R.
Examples of Hamming kernels include CASMOPOLITAN and Bounce, and can be obtained by selecting following functions for k:
d²
(d) exp
for CASMOPOLITAN, or
v
5d
v5d L
kg (d) = +
exp
382
for Bounce, with d == / / x') and > 0 hyperparameter. In fact, we will show in the following proposition, by choosing ((d) to be any (continuous) isotropic kernel (with |x - x'122), we always obtain a valid Hamming kernel k.
Proposition 7. Let k IR"
IR" + R be symmetric positive semi-definite and
kizz = (| x2112),
with z, z' E TR""
for some k. R - R. Then, the kernel
<x(xxx'= lk (vh(x,x')),
with x E XX
always symmetric positive semi-definite.
Proof. See Appendix A.2.
Using Proposition 7, we arrive general procedure for generating new combinatorial kernels: choose any (continuous) isotropic kernel and replace the Euclidean distance by the square root of the Hamming distance. For instance, an interesting new kernel can constructed by defining ik as the well-known rational quadratic kernel (Rasmussen and Williams, 2006).

---

3.4.2 Graph-based approach
To generalize COMBO into a broader class of kernels, we identify its main idea: transforming the input space X' into Hamming graph 9, and then applying a graph kernel. While numerous graph kemelss exist, one prominent family is the class of Φ-kernels (Smola and Kondor, 2003; Borovitskiy et al., 2023), which define the kernel terms of a regularization function (A) of the graph's 'ss eigenvalues.
Definition 8. Let (z) be the eigenpairs of the Laplacian of graph 9 (V, E), then O-kernels are given by
M
Kg (I, 1
Σ s (a)))
fy) (x) (z').
(6)
where z, x' E V and 23 : R - [0, 00), with / a (set of) hyperparameterr().
By selecting &g (A) exp (-3 in Equation 6 and applying the simplification from Kondor and Lafferty (2002), we recover Equation 5 (without ARD), demonstrating that COMBO is indeed (the ARD version of) 4-kernel. Additionally, this connection with d-kernels is yet another way to come up with new kernels. By transforming X' into G and selecting any function + R - [0, oo), arrive a valid combinatorial kernel k which is again guaranteed to be symmetric and positive semi-definit.. Rather than coming up with new definitions of & (A), further work could first try well-known, sfat-oof-hee-an ø-kernels, such as the graph Matérn kernel (Borovitskiy et al., 2021) or the sum-of-inverse polynomial kernel (Wan et al., 2024).
3.4.3 Equivalence of Hamming- and graph-based approaches
Because of Theorem 5, we know there is at least one kernel from the class of Hamming kernels, namely CASMOPOLITAN, that corresponds to an equivalent kernel in the class of d-kernels, namely COMBO. In fact, we show in Theorem 9 that, for finite sets X; of equal size, any Hamming kernel must be a Ø--krnel for some choice of Φ, and vice versa. Note that Theorem does not hold for finite sets of different sizes; see Appendix for counter example. Although this assumption might seem restrictive, we point out that it still holds for every single problem considered in recent benchmarks (Deshwal al., 2023; Papenmeier al., 2023; Dreczkowski et al., 2024), including this paper.
Theorem 9. Let Hamming kernels on X' coincides with the class of 4-kernels on G.
EX,E) be Hamming graph with [&i]
1.K. Then, the class of
Proof. See Appendix A.3.
Theorem 9 shows that, for finite sets of equal size, Hamming- and graph-based approaches are fundamentally the same, and that using one amounts to using the other. This equivalence appears to be new, as most combinatorial BO papers present CASMOPOLITAN and COMBO as using different approaches (e.g. Deshwal al., 2023), and not different perspectives of the same approach.
3.5 Extending heat kernels: incorporating invariances and additive structures
Group invariances In Appendix D.I, we review different methods to incorporate any group invariance within heat kernels. Moreover, we propose simple trick that significantly improves performance on permutation-invarian functions, and matches the SSK with only a fraction of the wall-time and compute (Figure 8). Lastly, using irvuriinvariant heat kemels,, we match the WL graph kernel on a set of www.-aacchcetreeeeseeeeeee incorporating group invariances for real-world tasks.
problems (Figure 10), showcasing the advantage of
Additive structures In Appendix D.2, we use our systematic derivation from Appendix to establish clear connection between heat kernels and additive-based kernels, such CoCaBO and RDUCB, as well as propose new "explainable" kernel. Although incorporating additive structure often decreases performance for standard benchmarks (Figures 1 and 4), note clear improvement in performance when applied to biological datasets (Figures 6 and 7), which we discuss in Appendix E.4.
Although the above extension allows us to connect heat kernels to even wider group of well- known kernels-noo also containing CoCaBO and RDUCB- we argue that BODi 's HED kernel still fundamentally different from heat kernels (or variations thereof), and provide proof in Appendix A.4.
7

---

4 Experiments
Benchmarks and baselines Our analysis is performed wide range of challenging combinatorial optimization problems: Pest Control, LABS and Cluster Expansion are displayed below in Figures and 2, and Contamination Control and MaxSAT have been moved Appendix E.3 (due to space constraints). All five problems are taken from Bounce (Papenmeier et al., 2023), and are described in more detail in Appendix E.I. Additionally, in Appendices E.4 and E.5, we experiment on five (discretized) permutation-invariant Simon Fraser University (SFU) test functions (Surjanovic and Bingham, 2013), well as two biological and logic-synthesis tasks from the MCBO benchmark.
We compare against several competitive baselines, including: COMBO (Oh et al., 2019), CoCaBO (Ru et al., 2020a), BOSS (Moss et al., 2020), CASMOPOLITAN (Wan et al., 2021), BODi (Deshwal et al., 2023), RDUCB (Ziomek and Ammar, 2023) and Bounce (Papenmeier et al., 2023). All basclines evaluated using their corresponding implementation in the MCBO benchmark, except for Bounce, which is not present in MCBO and was evaluated using the authors' original implementation.
Experimental set-up In Figure 1, we keep fixed pipeline and only change the combinatorial kernel, so that differences other (confounding) factors of the pipeline do not affect results. Based on the ablation study from the MCBO paper, we choose the following pipeline: the genetic algorithm used in BOSS (Moss al., 2020), together with the trust region from CASMOPOLITAN (Wan et al., 2021). In Figure 2, we combine this pipeline with a heat kernel, and compare it against other, well-know pipelines. In both figures, and as done in Bounce (Papenmeier et al., 2023), we display the originally published formulation, as well as modification with the optimal point moved to a random location (marked by [reloc.]). All methods have been evaluated for at least 20 different random seeds, with more noisy datasets having up 60 seeds (e.g. the biological tasks from Appendix E.4). Further details regarding our experimental set-up are described in Appendix E.2, and our implementation can be found at: https: // //g gitbuu...... con/ www.ont//tocoo//ooooooo wwwtmottnnttttteeeeeeeeeeeeeeeee hhweeeeatttteeeeeeeeeeeeee -ertels-eell---ll 4- BD. git.
Pest Control (25D)
LABS (50D)
Cluster Exp. (125D)
1000
Objective value
-1000
12
50
100
1,50
200
50
100
1.50
200
50
100
150
200
Pest Control (25D) [reloc.]
LABS (50D) [relor.]
Cluster Exp. (125D) [reloc.]
1000
-2
Objectivve value
16
14
3
-1000
-4
1.50
200
150
200
100
Iteration
Iteration
Iteration
Heat (Kondor & Lafferty)
One bot Matern (Bounce)
Rand. decomp. (RDUCB)
Heat (CASMOPOLITAA))
One bot RQ
HED (BODI)
Heat (COMBO)
Graph Matern
SSK (BOSS)
Heat (one-hot RRP)
Overlap (CoCaBO)
Random search
Figure 1: When keeping the pipeline fixed and varying only the kernel choice, our unifying framework becomes visible empirically: all heat (and Hamming) kernels achieve near-identical results.
4.1 Empirical evidence for the theoretical claims of the unifying framework
In Sections 3.1-3.3, we proved that the following four kernels are theoretically equivalent: the RBF kernel (after one-hot encoding), and the kernels found in Kondor & Lafferty (Equation 3),
8

---

CASMOPOLITAN (Equation 4) and COMBO (Equation 5). Additionally. in Section 3.4, we argued that these four kernels are closely taiteddthhrough the concept of "Hamming kernels" pernels"-te to Bounce's 's Matérn kernel (after one-hot encoding), the graph Matérn kernel (Borovitskiy et al., 2021), and the Rational Quadratic (RQ) kernel after one-hot encoding (proposed in Section 3.4.2). Now, we show that these seven kernels are also empirically equivalent: on all problems from Figures 1, 4 and 6, the seven kernels (indicated by a solid line) achieve nearly indistinguishable performance.
4.2 Sensitivity of BODi and BOSS to the location of the optima
In Figures and 4, BODi's ' HED kernel and BOSS' SSK achieve significantly worse results when the optima are relocated. For BODi (HED), Papenmeier et al. (2023) provide an extended analysis, arguing that this behavior is due the kernel's higher probability of sampling the last category, which is often the most "rewarding" category (at least in the original version of the above problems). For BOSS (SSK), we believe we are the first to report this behavior, and attribute it to misuse of the kernel: the SSK was designed specifically for strings, and not arbitrary categorical inputs (e.g. as is done in MCBO). Specifically, we hypothesize that the SSK performs well because it favors points with repeated categorical values, which are more "rewarding" in the original version of the above problems (but not necessarily in the modified ones, hence the performance degradation). We provide a more detailed explanation in Appendix E.5, In contrast, heat (and Hamming) kernels, as well as the related CoCaBO and RDUCB kernels (see Appendix D.2), are unaffected when the optimum is relocated.
Pest Control (25D)
LABS (50D)
Cluster Exp. (125D)
1000
2.0
Objective value
16
-25
-1000
-3.5
12
-40
100
200
100
200
100
200
Pest Control (25D) [reloc.]
LABS (50D) [reloc.]
Cluster Exp. (125D) [reloc.]
-2.0
Objective value
16
-25
330
-1000
3.5
-.00
100
200
100
200
100
200
Iterationn
Iteration
Iteration
CASMOPOLITAN
(one-hot RBF)
BOD
COMBO
CoCaBO
BOSS
Bounce
RDUCB
Random seurch
Figure 2: A fast and simple pipeline, relying on heat kernels, achieves state-of-the-ee results (after relocation of the optima), matching even outperforming more complex or slow basclines.
4.3 Fast and simple heat-kernel pipeline with state-of-the-art performance
In Figures 2 and 5, all baselines are matched or outperformed (after relocation of the optima) by our heat-kernel pipeline, which consists of three components: (i) the RBF kernel (after one-hot encoding). (ii) a genetic algorithm, and (iii) trust region. We argue that this pipeline is simple, relying on established concepts from different fields, without introducing any new, convoluted ideas. In contrast, Bounce's 's sophisticated nested-embeddings, or RDUCB's tree-decomposition with message-passing might make these methods less approachable for industry practitioners. Furthermore, this simple pipeline is fast, achieving the third lowest wall-clock time from all the evaluated baselines, closely following CoCaBO and Bounce (sce Figure 3, with details in Appendix E.6).

---

Average wall-time ratio compared to fastest method (ranked)
40
Avenue ratio (higher slower)
20
15
CoCaBO
Heat tous-be RBN
Bounce
CASMOPOLITAN
RDUCB
BODi
Reat (COMBI)
BOSS
COMBO
Figure 3: Our simple heat-kernel pipeline achieves the third-lowest wall-clock time, arriving closely after CoCaBO and Bounce.
5 Discussion and conclusion
In this paper, we have related different well-known combinatorial BO methods by presenting unifying framework, based on heat kernels. This framework aims to provide a clearer picture of the existing combinatorial kernels, leading to new theoretical and practical insights.
Among others, we prove that CASMOPOLITAN and COMBO are equivalent to heat kemelss (on Hamming graphs), and that both methods amount to using the RBF kernel (after one-hot encoding). By generalizing heat kernels, we establish new links with existing combinatorial kernels (e.g. Bounce) and obtain principled framework for generating new combinatorial kernels, guaranteed to be symmetric positive remi-definite. Similarly, by extending our framework with additive structure and group-invariance, we can again link heat kernels to well-known combinatorial kernels (e.g. CoCaBO and RDUCB), and achieve competitive performance on a real-world permutation permutation-invarian invariant task (e.g. neural architecture search).
In our experiments, we validate these theoretical claims with empirical evidence, showing that all the above heat (and even Hamming) kernels achieve near-identical results on five different problems. Moreover, are the first observe the SSK's degradation after relocation of the optima, extending the recent results found in Bounce (Papenmeier et al., 2023). Lastly, we propose a simple and fast heat-kernel pipeline with state-of-ther ofrtt---ttttttee results, hopefully making combinatorial BO more accessible.
Limitations While heat kernels show great performance on all the evaluated problems, we priori information. When there
emphasize that this is only true for settings with little already exists a large library of relevant structures, or when the inputs are known to have certain properties (e.g. molecules), other methods might be preferred. Moreover, our pipeline only considers categorical variables, although the extension to mixed variables (i.e. categorical and continuous) is straightforward (see Ru al., 2020a; Papenmeier et al., 2023, for example). Lastly, our experiments do not contain (truly) ordinal variables, but we note that this is standard recent combinatorial BO papers (Deshwal et al., 2023; Papenmeier et al., 2023).
Societal impact Although our main contribution is theoretical (i.e. a unifying framework), it does lead to number of practical improvements for combinatorial Bayesian optimization. For example, simple pipeline proposed in Section 4.3 could facilitate the use of combinatorial BO by wider public. Similarly, the faster implementation described in Section 3.3.3 leads to similar results with lower computational resources, increasing its accessibility. However, we believe these improvements carry minimal risks beyond the standard concerns about possible misuse of the underlying technology.
10

---

Acknowledgments
VB was supported by ELSA (European Lighthouse Secure and Safe AI) funded by the European Union under grant agreement No. 101070617. HM was supported by Schmidt Sciences and Research England under the Expanding Excellence in England (E3) funding stream, which was awarded to MARS: Mathematics for AI in Real-world Systems in the School Mathematical Sciences at Lancaster University.
References
Bacchus, F., Järvisalo, M., and Martins, R., editors (2018). MaxSAT Evaluation 2018: Solver and Benchmark Descriptions. Department of Computer Science, University of Helsinki. Cited on page 25.
Baptista, R. and Poloczek, M. (2018). Bayesian optimization of combinatorial structures. In International Conference on Machine Learning. Cited on page
Bergstra, J., Bardenet, R., Bengio, Y., and Kégl, B. (2011). Algorithms for hyper-parameter optimiza- tion. Advances in Neural Information Processing Systems, 24. Cited on page 3.
Borovitskiy, V., Azangulov, I., Terenin, A., Mostowsky, P., Deisenroth, M., and Durrande, N. (2021). Matérn Gaussian processes on graphs. International Conference on Artificial Intelligence and Statistics. Cited on pages 7 and 9.
Borovitskiy, V., Karimi, M. R., Somnath, R., and Krause, A. (2023). Isotropic Gaussian processes on finite spaces of graphs. In International Conference on Artificial Intelligence and Statistics. Cited on pages 5, 7, 22, and 31.
Cisbani, E., Del Dotto, A., Fanelli, C., Williams, M., Alfred, M., Barbosa, F,, Barion, L., Berdnikov, V., Brooks, W., Cao, T., et al. (2020). Al-optimized detector design for the future Electron-Ion Collider: the dual-radiater RICH case. Journal of Instrumentation. Cited on page 1.
Deshwal, A., Ament, S., Balandat, M., Bakshy, E., Doppa, J. R., and Eriksson, D. (2023). Bayesian optimization over high-dimensional combinatorial spaces via dictionary- baased embeddings. In International Conference Artificial Intelligence and Statistics. Cited pages 3, 5, 6, 7, 8, 10, 19, 24, and 25.
Domingo, J., Diss, G., and Lehner, B. (2018). Pairwise and higher-order genetic interactions during the evolution of tRNA. Nature. Cited page 27.
Dong, X. and Yang, Y. (2020). NAS-Bench-201: Extending the scope of reproducible neural architecture search. Cited on page 30.
Dreczkowski, K., Grosnit, A., and Bou Ammar, H. (2024). Framework and benchmarks for combi- natorial and viriale Bayesian optimization. Advances in Neural Information Processing Systems. Cited on pages 1, 2, 3, 5, 6, 7, 24, 25, and 27.
Durrande, N., Ginsbourger, D., and Roustant, O. (2012). Additive covariance kernels for high- dimensional Gaussian process modeling. In Annales de la Faculté des sciences de Toulouse: Mathématiques. Cited on page 23.
Duvenaud, D. (2014). Automatic model construction with Gaussian processes. PhD thesis, University of Cambridge. Cited on pages 22, 28, and 29.
Duvenaud, K., Nickisch, H., and Rasmussen, 12. Additive Gaussian processes. Advances in Neural Information Processing Systems. Cited on pages 23 and 24.
Faure, A. J., Martí-Aranda, A., Midalgo-Carcede C., Beltran, A., Schmiedel, J. M., and Lehner, B. (2024). The genetic architecture of protein stability. Nature. Cited on page 27.
Garnett, R. (2023). Bayesian Optimization. Cambridge University Press. Cited on page 2.
Ginsbourger, D., Roustant, O., and Durrande, (2013). Invariances of random fields paths, with applications in Gaussian process regression. arXiv preprint arXiv:1308, 1359. Cited on page 22.
11

---

Griffiths, R.-R. and Srrnánddz-LLbbatee J. M. (2020). Constrained Bayesian optimization for automatic chemical design using variational autoencoders. Chemical Science. Cited on page 3.
Hu, Y., Hu, J., Xu, Y., Wang, F., and Cao, R. Z. (2010). Contamination control in food supply chain. In Proceedings of the 2010 Winter Simulation Conference. Cited on page 24.
Hutter, F., Hoos, H. H., and Seyton-Brown, K. (2011). Sequential model-based optimization for
general algorithm configuration. In Learning and Intelligent Optimization. Cited on page 3.
Imrich, W., Klavžar, S., and Hammack, R. H. (2000). Product graphs: structure and recognition. Wiley New York. Cited on pages 3, 4, and 16.
Irwin, J. J. and Shoichet, B. K. (2005). ZINC free database of commercially available compounds for virtual screening. Journal of Chemical Information and Modeling. Cited on page 3.
Jones, D. R., Schonlau, M., and Welch, W. J. (1998). Efficient global optimization of expensive black-box functions. Journal of Global optimization. Cited pages 25 and 30.
Kingma, D. and Ba, J. (2015). Adam: method for stochastic optimization. In International Conference on Learning Representations. Cited on pages 25 and 30.
Kondor, R. and Lafferty, J. (2002). Diffusion kernels on graphs and other discrete structures. In International Conference on Machine Learning. Cited on pages 3, 4, 7, 14, and 20.
Lodhi, H., Saunders, C., Shawe-Taylor, J., Cristianini, N., and Watkins, C. (2002). Text classification using string kernels. Journal of Machine Learning Research. Cited page 3.
Lu, X., Boukouvalas, A., and Hensman, J. (2022). Additive Gaussian processes revisited. In International Conference Machine Learning. Cited on pages 23 and 24.
Mehta, Y., White, C., Zela, A., Krishnakumar, A., 7abergja, G., Moradian, S., Safari, M., Yu, K., and BeBeennhhSuiite NAS evaluation is (now) surprisingly easy. In International Conference on Learning Representations. Cited on page 30.
Hutter, F. (2022).
Močkus, J. (1975). On Bayesian methods for seeking the extremum, In Optimization techniques IFIP technical conference. Cited pages 25 and 30.
Moss, H., Leslie, D., Beck, D., Gonzalez, and Rayson, P. (2020). BOSS: Bayesian optimization over string spaces. Advances in Neural Information Processing Systems. Cited on pages 1, 3, and 8.
Moss, H., Ober, S. W., and Diethe, T. (2025). Return of the latent space COWBOYS: Re-thinking the use of VAEs for Bayesian optimisation of structured spaces. In International Conference Machine Learning. Cited on page 3.
Oh, C., Tomezak, J., Gavves, E., and Welling, M. (2019). Combinatorial Bayesian optimization using the graph Cartesian product. Advances Neural Information Processing Systems. Cited on pages 1, 3, 5, 6, 8, 20, 24, and 25,
Packebusch, T. and Mertens, S. (2016). Low autocorrelation binary sequences. Journal of Physics A: Mathematical and Theoretical. Cited on page 24.
Papenmeier, L., Nardi, L., and Poloczek, M. (2023). Bounce: Reliable high-dimensional Bayesian optimization for combinatorial and mixed spaces. Advances in Neural Information Processing Systems. Cited on pages 3, 5, 6, 7, 8, 9, 10, 24, 25, and 28.
Rasmussen, C. E. and Williams, C. K. I. (2006). Gaussian Processes for Machine Learning. MIT Press. Cited on pages 2 and 6.
Robinson, D. J. (2003). An Introduction to Abstract Algebra. de Gruyter. Cited on page 16.
Roustant, O.,, Padonou, E., Deville, Y., Clément, A., Perrin, G., Giorla, J., and Wynn, H. (2020). Group kernels for Gaussian process metamodels with categorical inputs. SIAM/ASA Journal on Uncertainty Quantification. Cited page 21.
12

---

Ru, B., Alvi, A., Nguyen, V., Osborne, M. A., and Roberts, S. (2020a). Bayesian optimisation over multiple continuous and categorical inputs. In International Conference on Machine Learning. Cited on pages 8, 10, and 23.
Ru, B., Wan, X., Dong. X., and Osborne, M. (2020b). Interpretable neural architecture search via Bayesian optimisation with Seisfeiler-Lehmaee kernels. In International Conference on Learning Representations. Cited pages 1, 3, 29, 30, and 31.
Shervashidze, N., Schweitzer, P., Van Leeuwen, E. J., Mehlhorn, K., and Borgwardt, K. M. (2011), 1). Weisfeiler-Lchman graph kernels. Journal of Machine Learning Research. Cited on pages and 29.
Smola, A. J. and Kondor, R. (2003). Kernels and regularization on graphs. In Learning Theory and Kernel Machines. Cited on page 7.
Snoek, J., Larochelle, H., and Adams, R. P. (2012). Practical Bayesian optimization of machine learning algorithms. Advances in Neural Information Processing Systems. Cited on page 1.
Surjanovic, S. and Bingham, D. (2013). Virtual library of simulation experiments: Test functions and ssuur ano/ ackley html. Cited pages 8 and 24.
datasets. sttps://wwwt sfu. ca/"ssur]]
Tripp, A. and Hernández-Lobato
M. (2024). Basic Bayesian optimization is underrated for molecule design. In ICML 2024 Al for Science Workshop. Cited on page 3.
Wan, X., Nguyen, V., Ha, H., Ru, B., Lu, C., and Osborne, M. A. (2021). Think global and act local: Bayesian optimisation over high-dimensional categorical and mixed search spaces. International Conference on Machine Learning. Cited on pages 1, 3, 5, 8, 24, and 25.
Wan, X., Osselin, P., Kenlay, H., Ru, B., Osborne, M. A., and Dong, X. (2024). Bayesian optimisation of functions on graphs. Advances in Neural Information Processing Systems. Cited on page
Ying, C., Klein, A., Christiansen, E., Real, E., Murphy, K., and Hutter, F. (2019). PAS-Bench-100 Towards reproducible neural architecture search. In International Conference Machine Learning. Cited on page 30.
Ziomek, J. K. and Ammar, H. B. (2023). Are random decompositions all we need in high dimensional Bayesian optimisation? In International Conference on Machine Learning. Cited pages and 23.
13

---

A Proofs
A.1 Proof of Theorem
Theorem 5. The kernels from CASHOPOLITAN and COKBO are equivalent to heat kernels on Hamming graph. That is, Equations and are proportional (the ARD version of) Equation 3.
Proof. For CASMOPOLITAN, we can rewrite Equation 4 as
n & (ot,
h (xxx)) exp
-IIexp exp (7/ 8 (x),)())
n
where 71- and l > are hyperparameters. Now, if we define "/ as
1 -
Y = -n
1 (9: 1)e Bigi 1)e-B.si
we recover
1-5(2
Bigs
e -
k (xx,')=
II
1 (gi 1:9-
1 (gi 1)e Big:
which is the ARD version of Equation 3. For COMBO, rewrite Equation 5
n (x:) = II
k(x,
D.
hy (z.
i1j=1
where
x
ki (2i1, 24) =
Σ
B. (1:) (xf)
Now, Kondor and Lafferty (2002) show that, when the subgraphs G3 complete, which is the for the Hamming graph of Definition 2, k; (I,, x/) becomes
(g. Poo0
if x x/
k; (I;, x1)
P.9.
if + L//,
9:
where 9i = ||x] is the number of vertices the complete subgraph G. = (K, E.). Using this simplified k; (Ii, ær),, we obtain
6(
Big. 1-6(0,0)))
k (xxx''
II
(gi
1)e
-19:
Seg:
1 -
91
9i
1=1
1-0(2.0)))
-iig
e
Bigi
1
(gi
1)e
9.gt
1=1
which is the ARD version of Equation
A.2 Proof of Proposition
Proposition 7. Let k 1R 1R + R. be symmetric positive semi-definite and
k(a,2') (||2 x'112), with z, z' TR.".
for some l. R + RR. Then, the kernel
xx(xx')= (Vh(x,x')),
with x E X,
is always symmetric positive semi-definite.
14

---

Without loss of generality, assume z' are the one-hot encoded versions of x, x,x'. Now, we have ks k'xx,))
Proof.
k 11000=--iinn (xx(xx)') = k z' / v2) (1z-2'la/
x k(z, 2').
Since we assumed & to be symmetric positive semi-definite, it follows that h- is also symmetric positive semi-definit.
A.3 Proof of Theorem 9
We prove Theorem 9 by showing that (1) every 0-kernel isotropic, (2) every isotropic kernel is a Hamming kernel and vice versa, (3) every Hamming kernel is 4-kernl. First, introduce the class of isotropic kernels.
Definition 10. A kernel l: X X and only if k(0(x),0(x')) = k(x, x'),
called isotropic (with respect to the graph g = (X, E))
x, E X,
0 E Aut(G),
where (g) denotes the group of automorphisms of the graph G. This group consists of maps 0 X X such that (0(x), ((x))) E is equivalent (x, x') e & for all x, x X.
It is easy prove that every -ekeell is isotropic. Moreover, this holds for general graphs 9 without restriction.
Lemma 11. Let k X X + R be a 4-kernel in the sense of Defimition 8, where X' is the node set of an arbitrary graph G (x, Then, have that k isotropic with respect to G.
Proof. Take 0 E Aul(g). We prove (0(x), xx,x'). For convenience, we denote |X| =
In this proof, is more convenient to view the eigenfunctions fj as vectors = -(.
the graph Laplacian as its matrix A, and 6, a permutation of the set (1.....9].. as the permutation matrix O such that (vi,,... (U1,,...?)) ,.)) the adjacency matrix of G and is the degree matrix, i.e. the diagonal matrix with D Σ Aij.
(19(1)-..-.. ()(g)) T. By definition, A D A where A
In matrix form, the fact that E Aut(g) means θ AA = A, which is equivalent to AO = AA, because θ is an orthogonal matrix. Thus, A OA and Af, = A implies Δ Of, This, together with orthogonality of O implies that { is an orthonormal basis of eigenvectors corresponding to eigenvalues Xy. same as {f,) What the same, (ʃf o 0 is an orthonormal basis of eigenfunctions corresponding to eigenvalues Ay. Since ø-kernll do not depend on the choice of an orthonormal basis of eigenfunctions, we have
9 k(0(x),0(xx)) (())))((())))) -(xxx))
proving that i is isotropic.
Remark. The converse of Lemma 11 is not, in general, true. Intuitively, when the group Aut(G) is small, it becomes easier to be isotropic, and the class of isotropic kernels can become larger than the class of k-kernels. For example, in the extreme case when Au)(G) trivial all kernels are isotropic, but not all kernels are &ekernels.
To continue working with isotropic kernels, need to characterize the automorphisms of G. Let us start with the simplest case. If G is a complete graph with | = g nodes, then any bijection x + X is automorphism. All such bijections are permutations of a a g-element set and form the symmetric group S., therefore Aut(G) = Sy-
Now, let us consider the Hamming graphs of Definition 2. Specifically, we consider G =
k== 9
where G; (2;, &,) are complete graphs and assume all factors to of the same size, i.e. [gg |. In this case, we can assume G1 Gn without loss of generality.
X
15

---

Lemma 12. Consider g = = G: with G1 = In complete graphs having 9 nodes. If 0 E Ag) then
On 0(1 I..) (01 On(Ho)))))
where a E Sn is permutation of the set ..] and 0; E Aut( = Sg. That is, Aut(g) = S Sn, where denotes the semidirect product of groups (see, e.g., Robinson (2003) for the definition of semidirect product).
Proof. Follows from Imrich et al. (2000, Theorem 4.15).
With this, we can connect Hamming kernels to the isotropic kernels.
Lemma 13. Let G = (X,E) be a Hamming graph from Definition 2, with | = - Re
then & X X IR. is isotropic (with respect 9) if and only if k. is a function of Hamming distance.
Proof. To simplify notation, assume, without loss of generality, X; = 10, ......9--- -1). Take
x, x E X. Consider 0 & (g) with 0(x) = (0) (x1),.... On (n(xn)). Take 0, with (x() = 0 and
Oc(2))) k This constitutes valid automorphism of G. Thus, have
kxx, x') k(@(xx,, (xx)) k(x,0), 0).
where x = (#1..... mx) and ã; 0 if x, xz or ã; otherwise. We can further con- sider 8 Aut(G) such that f(x) (Fo(1)...... (n)) where is such that ((x) is of form (1, (1,1,...,1,,,00 .., 0). If (x), then
x(x x') k(x,0) 0) k(x,0)
It follows that h depends only on the number of indices i for which x; = 2/ but not on particular values of 24, x and not on the particular indices That is, only depends on the Hamming distance between x and x'.
Conversely, assume k is function of Hamming distance, rather of its square root, as stated in Definition 6. Take 0 E (g) We prove k(0(x), (xx)) = k(x, x'). J. Here, the key observation is that (((x))x((x))) h(x, x'). which is obvious from the form of This immediately implies
k k(0(x), 0 Ic (Vh(e(x).,(x))) 1 (Vh(x,x') x(x,x')
and proves the claim.
Finally, prove that Hamming kernel is 4-kernel.
Lemma 14. Ifk X x X' + TR. is a kernel which is a function of Hamming distance, then & is d-kernel.
Proof. Let us start with the simplest case, when G = Gi is a complete graph with X' (0,.... 9 }}. For such G. the first eigenfunction fi of the Laplacian is the constant function f1(x) 1, which correspond to eigenvalue O. Other eigenfunctions f2, . fy are an arbitrary orthonormal basis in the linear space of functions that up to O: {f: x R E f(i) 0), which correspond to eigenvalue y-
On the other hand, in this case we have k(x, = al e=w' + -1 values, depending on whether r is equal to x' or not. We prove that k is a 4-kernel using Mercer's s theorem. For this, we check that the eigenfunctions of the Laplacian f/ are also eigenfunctions of the covariance operator (kf)(x) = Σi-1 k(æ,, (x))" Furthermore, we verify that two eigenfunctions Sú, correspond the same eigenvalue À of the Laplacian, then they correspond to the same eigenvalue X' noto that can differ from of the covariance operator k i.e that Af. = Aft and Af, Xf, implies kf = fr. kf, Xfg.
may only take two distinct
Let us show that fi is an eigenfunction of k. Write
9-1
9-1
Σ Ma, (a,x'))(('))
Σ
Mx = a (g 1)8 = (a (g 1)
=
16

---

Similarly, we can show that , fg are eigenfunctions of k. Take j 2 2 and write
-1,62)
((,)") = aff(a)+ 3
Σ
15(2)= = - (a-))(a)))
0S
z'zz
This also shows that the eigenvalue corresponding fy with is the same and completes the proof for the simple case when G = G1.
The next step is to consider Hamming graph = P i=1 G. where G; (X, E, are complete graphs with Xi| = |21
= | = g. Without loss of generality, we assume G1 = G2 = gn. Let f, denote the eigenfunctions of the graph Laplacian an orthonormal basis, exactly as in the simple case considered above. Then, an orthonormal basis consisting of eigenfunctions of the graph Laplacian on can be obtained by considering all possible products Ji (f1,...,, ,.n) = fJ (I1) S3n. (In):
the factors Gg such that fi..... form
A Aipn.ng = (2 +.... + >)a)) Jiimnnnn
Since A1 0 and A2 (i....., in) and (jn have the same number of zeros.
Ag 9. have Air... Aprnnndd if and only if the tuples
Under our assumptions, k must be of form k(x,x') x') = k(ll)==f =zzz........ ==,= ) for some K (0, 13" + R. Let us prove that fin....hn are also eigenfunctions of the operator (x) = Exex k(x, fxx and that kff.....d = Ny....... fj.....h where Ny....... only depends on the number of zeros in the tuple (fi,..., Jn). ). By Mercer's 's theorem, this implies that i is #-kenel.
Without loss of generality, assume f(x) = fj. (z1) (x2) (21) for some S n, where J1.J2,.... J 2, i.e. is product of 1 non-constant eigenfunctions and constant ones, ordered such that the non-constant ones come first. Denote X (x)) , N.
X; x x Xn.
and (xx: [s. (2:) ... .3. (21). Write
(x)))()) Σ k(xxx))
Σ x'EX'
1((2 1m2 1 1s==,, ff(x)
x'EX
g
= Σ
k(L,, ma! Lngmaty.... ..,1,,11 1e.=x,),,, f2.((()))
11==0
Now, using the fact that Eusa,
Sg-1 1 Fyz (x1) = -fūi (x1). continue
(x1( Σ
(k(1, 1 1os le.=ot) - <((0, Ams=zs........ (en=si)) fo (x2.)
Xg. ENZ2:
92-1
(11
M(1, 1 12
1am (T22 fa.(x(s)
Xy. Ed:::
- (1)
Σ
x(0, 1 I ...., 1x -,,= (12))())
(x(s)
x==0
Σ (n(11, 1, 1x,=x() =xx) - 1i(1,0, 1z.=x )) fa: (xg.)
Xy
Σ Ex
(x(0, 1...., 1mm br.= - x(00, ... lam=s fs. (x
Repeating the same steps multiple times, we arrive at
= ( (f))))
Σ (-1)
Σ
x(a (.q.....00 01, Anti 1 1e,=s,)
aE(0.1)'
X EX141:
constant, denote it by A
17

---

It follows that (x) Xf()), where À is the eigenvalue, equal to the alternating sum of above. Importantly, since & function of Hamming distance, only depend on the number of occurrences of in its arguments, thus X only depends on I, or, equivalently, on L, which is precisely the number zeros the tuple of indexes. This proves the claim.
Theorem 9. Let (X,E) be Hamming graph with [y =... [n Then, the class of Hamming kernels on X' coincides with the class of Ø-kernels on G.
Proof. By Lemma 14, every Hamming kernel is a Ø-kernel. By the combination of Lemma 11 and Lemma 13, every ø-kernel a Hamming kernel.
We now show that this is not, in general, the case for Hamming graphs for which [Ag (2l.. (el....., [ can differ.
Example. Consider X1 X22 {0. 1 and X3 {0, 1, the respective complete graphs
G. (X, &4), and their product G Di G. with G (x,8), X1 X2 A3.
Since G is a Cartesian product of Gr. every eigenvalue of the graph Laplacian on G is of form À + X2 + X3, where A; is eigenvalue of the graph Laplacian 9z. On G1 G2, there two distinct eigenvalues: 0 and 2. The distinct eigenvalues on G3 are and 4. This means that there 5 distinct cigenvalues on g:
0 = 0++++0
2 0=2+0+0=000 0+2+0
4=2+2+0=0+00
6 6=2+0+4=0++
8 8-2+2+4
follows that eigenvalues all é-kernels are form ((0), (2),, 2(4,, ((),, 9(8), which implies that 0-kernel on G can have more than distinct eigenvalues. We will show example of a kernel X x > which a function of the Hamming distance on G, and which has distinct cigenvalues. This will prove that the class of k-kenllss on is strictly smaller than the class of Hamming kernels.
Consider the kernel k 1x x X + R defined by
10,
h(x, x') = O,
6,
h(x,x') = 1,
k(x, x') =
4,
h(x,x') 2,
3,
h(x,x') =3,
where h((,-") is the Hamming distance G. Consider the ordering of all possible inputs in the following way:
(0,0, 0), (0,0, 1), (0,0,2), 2), (0,0,3), (0,1,0), (0,1,1), (0, 1,,1,), (0, 1,3),
(1, (1,0, 1), (1,0, 2). (1,0,3), (1,1,0), (1,1, (1,1,2), (1,1,3).
Then can be represented as matrix of size |
x |X|
16. This matrix
10
6
6
4
4
4
6
4
4
3
3
6
10
6
4
4
4
6
4
4
3
6
10
4
6
4
4
3
3
6
6
10
4
4
6
4
6
3
3
6
4
4
10
6
6
4
3
3
4
4
4
4
4
6
6
4
3
6
4
6
6
6
10
6
3
3
3
4
4
6
4
4
4
6
10
3
4
6
4
4
3
3
3
10
6
6
4
4
4
4
4
3
3
10
6
6
4
6
3
3
4
3
6
6
10
6
4
6
4
4
4
3
6
10
4
3
6
4
4
4
6
4
4
10
6
6
6
3
3
4
4
4
6
4
10
6
3
4
4
4
6
4
4
4
4
6
10
6
3
3
4
4
6
4
6
6
10
18

---

Its eigenvalues, repeated according to multiplicities, are 77, 15, 3,,
There are 6 unique eigenvalues: 77, 15, 9, 5,3, 1, showing that the class of Hamming kernels is larger than the class of 4-kernels on G.
A.4 Proof that BODi is not (variation of a) heat kernel
As outlined in Definition 6: kernel is Hamming Kernel (HK) if and only if depends on x, x' X through the square root of the Hamming distance /xx,, x'). That is,
kak x, x') = (v/VVViee ((xxxxx))
for some f Z R.
In contrast, the BODi kernel depends on x, x'x 2 through the term kBODI (x, (xxxx)
= : x=: 9 - (x(xx)) 112)
with
g(d) = 1 55d
5
/dd l
exp
362
Here, g(.) is the Matérn-5/2 function, where we note that g(-) constitutes a bijective function.
Additionally, (-)-) denotes the mapping towards the HED embedding (see Section 4 of Deshwal al., 2023), namely:
[x)())]; h(a., x),
with a, E A one of the M anchor points in dictionary A.
For BODi to be a Hamming kernel, there thus needs to exist function, say u(-). such that
(Vh(xxx)) = (x) - (x(')
this function u(-) exists, we can define f /=
u, obtaining
Kaaos (x, x') = - (u
(x
(Vh(xxx))) ( =
( (Vx(x,))) = Axxx (x, x')
However, as becomes clear by looking the mapping (*()), there does not exist a function u(-)
satisfying the above claim. We provide small counter-example with M = 1 below.
In scenario A, have:
x [1,11,,], x' = -1,1,2) and a = [1, 1],
which gives us
Vh(xxx)) = and (xxxx) - (x')1113 =
In scenario B, we have:
x [1,1,,2, x' [1] and a1 = [1,
which gives us
v hxxxx') and | (x) db (x (x))1 0.
For uu-) to work in both scenarios, we would need to have:
u (1) = and u(1) = 0,
which is clearly not possible. As result, we conclude that BODi is not Hamming kernel, and therefore also not heat kernel (or a direct generalization thereof).
In fact, using the above proof structure, we can show an even stronger result: BDDi is not part of an (even broader) general class of kernels, which includes not only Hamming- and graph- kernels, but also additive kernels such CoCaBO and RDUCB (see Appendix D.2). With this, we feel confident our answer that BODi cannot be seen as a heat-kernel variation in some sense, and HED kernel thus fundamentally different from the kernels grouped by unifying framework.
19

---

B Ordinal variables in combinatorial Bayesian optimization
Combinatorial Bayesian optimization is often used umbrella term to denote variety of discrete search spaces, resulting in potential misunderstandings. In this paper, we argue combinatorial BO is centered on three main types of variables: categorical, ordinal, and dusseretequantiiattvee" Categorical variables can take elements from a discrete, finite, and unordered set, where the distances between the different elements of the set are unknown. For ordinal variables, the same definition applies, except the set is now ordered (but distances are still undefined). In contrast, discrete- quantitative variables-whiit are often mistakenly referred to as ordinal variables- not only possess an order between the different elements, but also specific distance.
As general example, we consider the number of layers in neural network. Here, although the variable is discrete, there a clear distance between the different categories (namely the Euclidean distance). Therefore, according to our definition, this is not ordinal variable, but rather discrete- quantitative variable. As can be imagined, truly ordinal variables are rare, and are in fact not considered in any of the kernels/methoos that we compare against in this paper (to the best of our knowledge).
For discrete- quantitative variables, we believe the associated kernels are rather straightforward: any (continuous) isotropic kernel, along with an appropriate distance function (usually Euclidean). As such, these kernels can simply be seen continuous kernels, which is why we did not explicitly address them in our unifying framework. For ordinal variables (although rarely considered in the field), we suggest replacing the complete graphs G; from Definition 2 by path graphs, where nodes are only connected to the category right above or below in the ordered set X. This approach is similar to what is proposed in Oh al. (2019), and allows to connect ordinal variables with unifying framework centered on heat kernels.
Unfortunately, the above connection is also where the analysis stops. Since path graphs do not contain the same type of symmetries as complete graphs, the eigenvalues of the corresponding Laplacian do not simplify much as for categorical variables. Therefore, we do not obtain a simple closed-form form solution. In other words, Equations or cannot be simplified to something like Equations or 4.
C Deriving heat kernels from general combinatorial kernels
In Appendix C.I, we define the most general combinatorial kernel and show that this leads to an explosion in degrees of freedom. In Appendix C.2, we demonstrate that applying two simple assumptions significantly reduces the degrees of freedom associated with the kernel. In Appendix C.3, we put both pieces together and arrive at Equation 3, therefore deriving heat kernels in a clear and systematic way.
C.1 Defining general combinatorial kernels
For a finite input space X' there are only a finite amount of pairs (x,x') x') E X x X' at which a kernel function k(:))) can be evaluated. As such, can represent this function k(-,)) matrix K, with rows and columns indexed by the elements of X' and related to the kernel function by Kx k(x, x') (Kondor and Lafferty, 2002). From this, it becomes clear that defining combinatorial kernel amounts to defining a symmetric positive semi-definite matrix K.
|X [X']
To define the most general combinatorial kernel k., and update those by maximizing the marginal log likelihood. By doing so, any pair of points xx,x') E X x X' can be assigned any covariance k(x, x'), resulting in the most expressive kernel k. To ensure symmetry and positive semi memii-dffiiteness, we can parameterize Cholesky factor of K CC resulting in | (I-*) + 1) 2 hyperparameters.
simply populate K with hyperparameters
Clearly, for most combinatorial input spaces of interest, this number of hyperparameters far exceeds the number of datapoints typically considered in BO tasks. To significantly reduce the number of typeeparrmeeees, we can impose two simple assumptions on the parameterization of K: product decomposition and compound symmetry.
20

---

C.2 Reducing degrees of freedom using simple assumptions
Instead of parameterizing using the Cholesky decomposition, we can instead define K as being Kronecker product of smaller matrices K,, similarly to how the standard (continuous) RBF kernel k(x,x') can be seen as a product one-dimensional kemelss (I;, z(), each acting on its own variable.
Assumption 15 (Product Decomposition), Given a combinatorial input space = x X, the associated kernel matrix K can be written
K
K,
where X is the Kronecker product and K; are symmetric positive semi-defiitte matrices of size [x x [.
By imposing Assumption 15, we reduce the degrees freedom from 0 ((x1)) down to
O - x1P). we see x E X' as an n-dimensional vector of categorical variables, then Assumption 15 minimizes the explosion in the number of hyperparameters due the increase in the number of variables, but not due to the increase in the number of categories per variable. For the latter, can impose a certain structure on each K,
Assumption 16 (Compound Symmetry). For kernel matrix K satisfying Assumption 15, we have
K I
x
Vi
=f== ff
a/v E (-1/ - 1),
Ci
where and are hyperparumeters.
Each matrix K; satisfying Equation 7 is positive semi-definite (Roustant et al., 2020).
By imposing Assumption 16, we obtain matrices K; with only two different values: diagonals v, namely the variances, and off-diagonals c,, namely the covariances. In essence, for each variable T; the covariances between the different categories are now considered equal, no matter which two categories getting compared. By imposing both assumptions, now have 2n hyperparameters. This number can be reduced further to + hyperparameters, as will be shown in the next section.
C.3 Deriving heat kernels
In the previous two sections, we have represented k(:,)) in terms of matrices, so to easily represent the number of hyperparameters involved. In this section, we return to the function view and, after applying Assumptions 15 and 16, obtain
x(x,x') II ha (1),))) with ky (1i, x/)) =
Vi if if
x
and ci/u: (-11 (|2 - 1), Now, putting both assumptions together gives us
5( b(x..s)) 1-6(x.x))
1- (e,,a))
k(x, II ke (z,, x/)
U/
Ci
P3
(8)
Us
where 6(---) is the Kronecker delta function and E (-1/ -1)1-1),11
From Equation 8, it becomes clear that only + hyperparameters are needed, where the addi- tional hyperparameter comes from the fact that we now need to explicitly add a signal variance o². Furthermore, choosing
9.g:
Pi
1 (g:
1)e
P.g.
get
T2
5 (2.1))
9:9 -
I 1-8 (0(
f(x,x))
P:
+ (gi
1)e
1=1
21

---

which is the ARD version of the heat kernel expressed in Equation 3. Similar to Appendix A, B 2 0 hyperparameters and 9i | leading to
e- 9igs
P - / (8,) + (g: 1
-1))((
E
-)),
therefore ensuring the base kernels le (2i, æ/} are still positive semi-definite.
D Extending heat kernels: incorporating invariances and additive structures
In Section 3, we have presented unifying framework describing general classes of combinatorial kernels. In this appendix, we show that these classes of kernels can easily be modified and extended to incorporate invariances (Section D.I) and additive structure (Section D.2).
D.1 Incorporating (permutation) invariance
In combinatorial BO, is not uncommon for the objective function f possess certain symmetries, with permutation invariance perhaps being the most prevalent. When these symmetries are known, incorporating them into the kernel can significantly improve predictive accuracy (Borovitskiy et al., 2023), and therefore also sample efficiency.
Formally, let G be group acting X, then function XX R is called G-invariant if
f [g (x)) = f(x) E G
Vx X.
Essentially, this means that f remains unchanged under the action of any element of on X. Now, for f ~ GP (0, k), we have that f is G-invariant if and only if is G-invariant, which we define as being
k xx,x') (g1 (x), .92 (x')) Vgi. 92 G x' E X.
We refer the reader to Ginsbourger et al. (2013) for proof.
Given finite group G, Duvenaud (2014) propose three different methods convert kernel k into its G-invariant version kya:
1. summation
Ksum (x, x)) = Σ Σ g'xxx)
DEGF D'EG
2. projection onto a fundamental domain
Kiproj (x, x') 1: (x), Ac(x)))
3. multiplication:
kprod (x, x')
II II k(g(x),g(xx)), gEG g'EG
Here, Ag is mapping used transform x into canonical representation Ag (x) under G. For example, for the group S,, of permutations size n set, Duvenaud (2014) suggest the fundamental domain (x1, (I,,...,Ty 3i order. For permutation invariance, this sorting method is often much faster to execute than summation or multiplication, making it the preferred method of choice.
S In). which can easily be mapped by sorting x in ascending
Padding for permutation invariance Although sorting x will indeed result in a permutation- invariant kernel, it does not necessarily lead to good distances between different points. For example, consider the following two vectors, before and after sorting:
x 00, 0,0, 3, 4 00, x' 4, 4,4,,,,,1
0, 0. 1,
1, 3,
Here, we expect both vectors to have a relatively low Hamming distance, since only the first two variables have been changed between x and x'. However, after sorting, both vectors look very different, and their Hamming distance is quite large (i.c. 7).
22

---

To overcome this problem, we propose a simple trick: padded sorting. To do so, we introduce the new category "*" and add it to our existing set of categories. In our previous example, all vectors in (O..... 4) will then be mapped into O..... 4]5+10 like this:
x 10,,0,,11,2,,,333 4 [0, 0,
*, 0,4,4,
x [. 4,,00,1,,,,,,,,33
[0,
*, 4, 4, 4,
As a result, the Hamming distance (after padded sorting) is now 2 + +++0+++++ = 4. which is much more reasonable. In fact, with padded sorting, the distance between two sequences is something very intuitive: for every category in {I..... }), we compute the difference between the number of entries of this category in the first vector and the number of entries of this category in the second vector, and then we sum these numbers up. Although this trick is relatively simple, it has never been introduced in the Bayesian optimization literature (to the best of our knowledge).
In Appendix E.5, we use synthetic permutation-invarine permutation-invariint heat kernels, well the increase in performance by switching to padded sorting. In Appendix F, we showcase the potential of permutation-invarian heat kernels for solving real-world problems, with an example on neural architecture search.
functions to demonstrate the power of
D.2 Incorporating additive structure
Incorporating additive structure has proven successful for tackling -igh-dimensional problems or obtaining explainable models (Duvenaud et al., 2011: Durrande et al., 2012; Lu et al., 2022), and may thus prove useful in combinatorial context. In this section, using our derivation from Appendix C, extend the heat-kerne' framework such additive-based structures (in straightforward way).
In Appendix C, we started from the most general combinatorial kernel and applied two simple assumptions (Assumptions 15 and 16), naturally obtaining heat kernels expressed as
x(x,x)= II
hs (I x!),,
with
if if if
1
=
+
E 91
(10)
Now, relax Assumption 15: replace the product decomposition of Equation 9 by more general decomposition
x(x,x')= f (k1 (01, ki, (Inn
Here, some care needs to be exerted in picking a decomposition f. such that the obtained kernel k(x,'') x') remains valid (i.e. symmetric positive semi-definite). Using this general decomposition f, we obtain an expressive class of kernels, which spans many well-known combinatorial kernels (including all Hamming k-kernels from Section 3.4).
Connection to CoCaBO and RDUCB To extend the heat-kernel framework to additive structures, keep the base kernels k; (ar,,z)) from Equation 10 and select to be additive function. For example, if we choose f to be simple first-order sum, we obtain
x(x,x'=
kss (1,, x!),
which is exactly the (additive) kernel used in CoCaBO (Ru et al., 2020a). Similarly, to obtain RDUCB's random-decomposition kernel, select be
x(x,x'==
EII hy (c,,
CEC sEC
with e C (1....,r) and C (random) collection of different components c. Here, if two dimensions i and j do not appear together in any of the sets c, the kernel will not model interactions between them (Ziomek and Ammar, 2023). By choosing other (additive) functions for f. we have a principled way of coming up with new combinatorial kernels. We give example in the following paragraph.
23

---

New explainable kernel In the continuous Gaussian process literature, there exist a number of udditive-based kernels with an "explainable" or "interpretable" character. With the above framework, it becomes easy to extend them to combinatorial input spaces: keep the combinatorial base-kernels from Equation 10, and select the same additive decomposition f as the original (continuous) kernel. For example, to adapt the explainable (additive) kernel from Duvenaud et al. 2011), we choose
a
xxx,''==
Σ od
EII hg (I), /c/=diEn
with S {I,...,.y nt.. Here, the dy are hyperparameters that will indicate how strong the effect is of different degrees of interactions, thus giving the kernel an "explainable" character. Our principled approach is general and can therefore be used extend many other (continuous) explainable kernels to combinatorial input spaces. One promising candidate the Orthogonal Additive Kernel (OAK) from Lu et al. (2022), which presents improved version of the above kernel from Duvenaud et al. (2011). Although an interesting direction for further research, experimenting with these new kernels falls outside the scope of this paper.
E
MCBO experiments
E.1 Overview of benchmark problems
SFU functions (20D) The MCBD benchmark (Dreczkowski et al.. 2024) contains 21 test functions from Simon Fraser University (SFU), which have been generalized to d-dimensional domains (Sur- janovic and Bingham, 2013). Moreover, in MCBO, these continuous functions have been discretized by only allowing the model to evaluate points on a regular grid (with n values per dimension). These functions cover range of optimization difficulties such steep ridges, many local minima, valley-shape functions, and bowl-shaped functions. Out of these 21 SFU test functions, we select permutation-invarie functions with different properties, and choose d 20 and 11 in Dreczkowski et al. (2024). Therefore, the benchmarks feature 20 categorical variables with 11 values each.
Pest Control (25D) The Pest Control benchmark features 25 categorical variables with 5 values each, representing a chain of pest control stations (Oh al., 2019). It models dynamic optimization problem where pesticide prices decrease with frequent purchases, while effectiveness diminishes with repeated use due pest tolerance. The objective minimize both pesticide costs and crop damage across the control chain. Pest Control has been included as benchmark in COMBO (Oh et al.. 2019), CASMOPOLITAN (Wan al., 2021), BODi (Deshwal al., 2023), Bounce (Papenmeier et al., 2023) and MCBO (Dreczkowski et al., 2024).
Contamination Control (25D) The Contamination Control benchmark features 25 binary variables, representing whether to quarantine uncontaminated food products (Hu et al., 2010). Similar Pest Control, it features sequential decision-making with dynamic interactions, but represents a slightly simpler problem due to the use of binary rather than categorical variables. The objective function balances minimizing both the number of contaminated products reaching consumers and the costs associated with preventive quarantine measures. Contamination Control has been included as benchmark COMBO (Oh al., 2019), CASMOPOLITAN (Wan et al., 2021) and Bounce (Papenmeier et al., 2023).
LABS (50D) The Low-Autocorrelation Binary Sequences (LABS) benchmark features 50 binary variables, representing a sequence S of length 50 with elements in 11, The objective is to find sequence that minimizes the energy function E(S) = Σ (S)), where Cx)(S) represents the autocorrelation at shift k: Alternatively, the objective can expressed as maximizing the merit factor
F(S)= = 2F(ST This benchmark has practical applications in diverse fields, including communication engineering. radar and sonar ranging, satellite applications, and digital signal processing (Packebusch and Mertens, 2016). LABS has been included as benchmark in BODi (Deshwal al., 2023) and Bounce (Papenmeier al., 2023).
,,²
24

---

MaxSAT (60D) The MaxSAT benchmark features 60 binary variables, representing the booleans in a weighted Maximum SATisfiability (MaxSAT) problem (Bacchus et al., 2018). The objective is to assign the boolean values such that the sum of the weighted clauses is maximized. Following Bounce (Papenmeier al., 2023), we normalize these weights to have zero mean and unit standard deviation. MaxSAT has been included as benchmark in COMBO (Oh et al., 2019), CASMOPOLITAN (Wan et al., 2021), BODi (Deshwal et al., 2023) and Bounce (Papenmeier et al., 2023).
Cluster Expansion (125D) The Cluster Expansion benchmark features 125 binary variables, and is derived from world MaxSAT instance in materials science (Bacchus al., 2018). As with the MaxSAT benchmark, the objective is to maximize the total weight of satisfied clauses, while treating the problem weights for Cluster Expansion, whereas this is not done in Bounce (Papenmeier et al., 2023). To the best of our knowledge, Cluster Expansion was introduced as new combinatorial BO benchmark in Bounce (Papenmeier et al., 2023).
black box. To maintain consistency with MaxSAT, also normalize the
E.2 Implementation details
The MCBO benchmark, introduced in Dreczkowski al. (2024), consists of a collection of problems and algorithms for combinatorial BO. The benchmark is open-source (with MIT license), and allows us perform all the experiments of Section 4 and Appendix with minimal changes. The original benchmark is available at https::/ //ggtbu....... com com/huawei. -nwah /HEBO/EBB/// t/ttteeeemmstteeeee iaaater/MBBB and our modified version can be found in the supplementary material. To prevent bias or overfitting, our experimental uet-up relies as much as possible on the default values present in MCBO. We highlight some key elements of the configuration below.
Experimental set-up We use 20 initialization points, opt for a batch size of I and allow up to 200 iterations. As hyperparameter optimizer and acquisition function, we use the ubiquitous Adam optimizer (Kingma and Ba, 2015) and Expected Improvement (EI) (Močkus, 1975; Jones et al., 1998), respectively. To optimize the acquisition function in the pipelines of Figures 1, 4, 6 and 8, we use genetic algorithm and include a trust region (see Appendices F and G of Dreczkowski et al. (2024) for detailed description). No priors were imposed on the hyperparameters, and therefore we use MLE and not MAP inference. We standardize all black-box function values using the mean and standard deviation of all previously observed values, and transform it back at prediction. The experiments repeated across 20 random seeds, except for Contami comminatiin Control and LABS, which are noisier and therefore require double the amount of runs (i.e. 40 random seeds). Similarly, the biological and logic-synthesis datasets from Figures 5 and 6 require triple the amount of runs (i.e. 60 random seeds). Moreover, due to its significant computational requirements, we have halved the number of seeds for pipelines involving the SSK, as well as stopped their runs at 100 iterations on Cluster Expans i on. The MCBO plots in this paper display the mean and standard error of the mean (with respect to the seeds) as solid/dotted line and shaded area, respectively.
Out of all our baselines in Section 4 and Appendix E, Bounce (Dreczkowski et al., 2024) is the only one which is not implemented in MCBO. Therefore, we instead rely on the authors' open-source Because
implementation (with MIT license), available https://g/ thub. Coon/LeoIV/boune Bounce first explores lower-dimensional subspaces, we adhere to the authors' recommended set- up of 5 initialization points. This is visible on Figures 2 and 5, where Bounce starts with lower objective-values than the other baselines (at around 20 iterations).
Relocation of the optima Following the approach in Bounce (Papenmeier et al., 2023), we relocate the optima (indicated by [reloc.]) using fixed randomization procedure for each benchmark for all algorithms and repetitions. For binary problems, we flip each input variable independently with probability 0.5. For categorical problems, we randomly permute the order of the categories.
Computational resources We were able to run all evaluated baselines on single-core CPUs with IGB of RAM. The only notable exception is SSK (or BOSS), which is prohibitively slow on CPUs and was run on NVIDIA RTX6000 GPUs with 24GB of RAM. Table gives an overview of the amount of time needed to run each method.
25

---

Contamination Control (25D)
MaxSAT (60D)
22.50
100
Objestive value
22.25
-12
22.00
Hest (Konder & Lafferty
21.75
Heat (CASMOPOLITAN)
175
Host (COMBO)
21.50
Heat (ome hot RBF)
-200
One-bot Matern (Beunce)
One-hot
Contamination Control (25D) [reloc.]
MaxSAT (60D) [reloc.]
Gruph Matern
22.50
Overlap (CoCaBO)
-100
Objective vahie
22.25
Rand. decompp. (RDUCB)
125
HED (BOD))
22.00
SSK (BOSS)
150
Randem search
21.75
-175
21.50
100
200
100
200
Iteration
lieration
Figure 4: Extension of Figure (when keeping the pipeline fixed and varying only the kernel choice, unifying framework becomes visible empirically).
E.3
Additional synthetic tasks
Figures and 5 extend the results of Figures 1 and 2, respectively, to two new problems: Contamination in Control and MaxSAT. These extended results fit the three takeaways presented in Section 4:
1. all heat (and even Hamming) kernels obtain nearly indistinguishable performance,
2. BODi (HED) and BOSS (SSK) experience significant drop in performance after relocation of the optima,
3. simple and fast pipeline, relying on heat kernels, achieves state-of-the-art performance.
Contamination Control
MaxSAT (60D)
22.50
-100
Objective value
-125
-150
CASMOPOLITAN
175
COMBO
50
100
150
200
50
100
150
200
(one-hor RBF)
Contamination Control (25D) [reloc.]
MaxSAT (60D) [reloc.]
CoCaBO
23.50
RDUCH
-100
BOD;
Objectvv valne
23.25
BOSS
125
Random search
23,00
-150
21.75
21.50
200
100
150
200
Iteration
Iteration
Figure 5: Extension of Figure 2 (a fast and simple pipeline, relying heat kernels, achieves state-of- the-art results).
26

---

E.4 Biological and logic-synthesis tasks
Figures 6 and 7 extend the results of Figures and 2, respectively, to four new problems: Antibody Design, AIG/MIG Optimization, and RNA Inverse Folding. Here, the only exception RDUCB, which was not evaluated on Antibody Design because its implementation (by the original authors) does not support input constraints (which are needed for this task). We refer to Dreczkowski et al. (2024) for a detailed description of all four problems.
These extended results on four new datasets mostly fit the three takeaways presented in Section 4, as well as lead new insights:
1. On all four datasets, all Hamming indicated by solid lines Figure 6 6-obtain nearly indistinguishable performance (as is the case for the other datasets presented in the paper).
2. On all four datasets, SSX (BOSS) and HED (BODi) do not seem particularly sensitive to relocation of the optima (a similar behavior was observed on LABS in Figures 1 and 2).
3. On all four datasets, our fast and simple heat-kernel pipeline achieves identical performance to Bounce, which is currently the state-of-the of-the--rt method. Interestingly, although both methods (Bounce and ours) are among the top performers on AIG/MIG Optimization, this Antibody Design and RNA Inverse Folding.
is not the
On these two datasets, there is new trend: additive kernels, namely Overlap (CoCaBO) and Rand. decomp. (RDUCB), are able to outperform Hamming kernels for the first time. This is not necessarily surprising: in related biological tasks, there exists evidence that first- and second-order interactions lead to strong predictive performance (Domingo et al., 2018; Faure et al., 2024). The MCBO paper (Dreczkowski al., 2024) also contains potential evidence for this low-order hypothesis: a genetic algorithm, which only mutates few variables at time and does not inherently model high-order interactions, performs remarkably well on RNA Inverse Folding, significantly outperforming all BO methods.
If such additive structure is known a priori, leading to methods such as (but not limited to) RDUCB and CoCaBD (see Appendix D.2). Nevertheless, besides the kernel, the crquisition-functtinn optimizer seems to play an im- portant role for these two biological datasets: CASMOPOLITAN (simple heat kernel) outper- forms CoCaBO (additive-basse based heat kernel), although their respective kernels with fixed acquisition-fume functionn optimizer lead to do the opposite ranking.
easily incorporate it into the heat-kernel,
Antibody Design (1ID)
Antibody Design (1ID) [reloc.]
AIG Opt. (20D)
AIG Opt. (20D) [reloc.]
2,00
2.00
-110
-110
Objective
-120
-120
1.95
1.95
100
200
100
200
100
200
100
200
RNA Inv. Folding (40D)
RNA Inv. Folding (40D) [reloc.]
MIG Opt. (20D)
MIG Opt. (20D) [reloc.]
Objective value
1.0
1.0
12.5
12.5
10.0
10.0
0.8
0.8
7.5
7.5
100
200
100
200
100
200
100
200
Iseration
Iteration
Iteration
Ireaaion
Heat (Kondor& & Lafferty)
One-hot Matern (Bounce)
Rand. decomp. (RDUCB)
Heat (CASMOPOLITAN)
One-hot RQ
HED (BODi)
Heat (COMBO)
Graph Matern
SSK (BOSS)
Heat (one het RBF)
Overlap (CoCaBO)
Random search
Figure 6: Extension of Figure I (when keeping the pipeline fixed and varying only the kernel choice, our unifying framework becomes visible empirically).
27

---

Antibody Design (1ID)
Antibody Design (IID) [reloc.]
AIG Opt. (20D)
ATG Opt. (20D) [reloc.]
Objective value
2,00
2,00
-110
-110
-120
-120
1.95
1.95
-130
100
200
100
200
100
200
100
200
RNA Inv. Folding (40D)
RNA Inv. Folding (40D) [reloe]]
MIG Opt. (20D)
MIG Opt. (20D) [reloc.]
Objective value
1.0
10.0
10.0
0.8
0.8
7.5
7.5
Iteration
Ieraaioo
Iteration
Iteration
CASMOPOLITAN
Hest (onc-hot RBF)
BOSS
COMBO
CoCaBO
Random search
Bounce
BODi
RDUCB
Figure 7: Extension of Figure 2 (a fast and simple pipeline, relying on heat kernels, matches the state-of-the-ar method Bounce).
E,5 Permutation-invarian SFU functions
In Section 4.2, we discuss the SSK's (or BOSS') sensitivity to the location of the optima and present simple hypothesis: the SSK favors points with repeated categorical values. Although a complete theoretical analysis of the mechanisms behind the SSK's bias lies outside the scope this paper, we do present intuitive example for our hypothesis. Consider substring $ [1. 1] compared to the string X1 = [1, 1, 1, 1]. and another substring $2 = [1, 2] compared to the string x2 [2, 1, 1). Here, both substrings contain similar categorical values as their corresponding strings, but the SSK will generate six matches between S1 and X1, and only one match between $2 and X2. Therefore, we hypothesize that the SSK will have a biased perception of distance when it comes to points with repeated categorical values, due to these points accumulating a disproportionate amount matches.
To empirically analyze this theoretical hypothesis, we rely on synthetic permutation invariant tions, for which the global optima consist of repeated categorical values. As expected, Figure displays a clear degradation of performance for SSK after relocation of the optima. This result is consistent with our hypothesis, since the random relocation means the optima will not necessarily consist of repeated categorical values.
germutation-invariant func-
Additionally, if we know the problem is permutation-iinvariant, we can instead rely on the tech- niques described in Appendix D.I. In Figure 8, Heat (proj.) refers to (x x') from Duvenaud (2014), which in this case amounts only to sorting the data before uing a heat kernel. As such, Heat (pad. proj.) represents our "padded sorting" approach proposed in Appendix D.I. From Figure we conclude that padded sorting a significant improvement over regular sorting. Moreover, even when the objective functions are tionally intensive SSK, since Heat (pad. proj.) achieves similar performance on all five functions (except maybe for Ackley Function).
there is no need to use the computa-
Including "strategic" f'eatures When the objective function is invariant to groups other than the permutation group, the general techniques from Appendix D.1 can be used, whereas the SSK will not work. However, depending on the invariance group, these techniques can sometimes be computationally expensive. A more lightweight alternative, though perhaps less principled, is to include additional "strategic" features. For example, in the Bounce paper (Papenmeier et al., 2023), the authors argue that BODi achieves its performance mostly due to its way of doing "uniform" sampling of anchor points, which turns out to be heavily skewed towards points with certain type of structure. a consequence, BODi's HED embeddings or features contain clear distance metric to anchor points with a certain structure, which can become useful signal to navigate towards certain
28

---

Ackley (20D)
Ackley (20D) [reloc]
Schwefel (20D)
Schwefel (20D) [reloc.]
Objective value
30
20
5000
5000
10
2500
2500
100
200
100
200
100
200
100
200
Rastrigin (20D)
Rastrigin (20D) [reloc.]
Styb.-Tang (20D)
S (20D) [reloc.]
Objective value
-250
-250
100
-500
-500
100
200
100
200
100
200
100
200
Sphere (20D)
Sphere (20D) [reloc.]
Hoaf
Objective value
Heat (nmj))
100
100
Heat (pad. pmj.)
Overlap (CoCaBO)
Rand. decomp. (RDUCB)
(BODI)
SSK (BOSS)
100
200
100
200
Random search
Ireration
Iteration
Figure 8: Our padded version of kpnij (x, x'), proposed in Appendix D.I, outperforms the non-padded version from Duvenaud (2014), well as matches the SSK nearly all problems.
optima. The same idea can easily be integrated within our heat-kernel framework: sample anchor points according to the desired type of structure, and add the relevant features (i.e. the Hamming distance to these anchor points) to the existing heat-kernel. We believe this general idea might be an interesting direction for further research, but leave it to future works.
E.6 Wall-clock time
Table 1 displays the wall-clock time (in seconds) of different pipelines. This speed measurement is concerned only with the algorithms themselves, and therefore does not include the time needed for evaluation of the objective function. All baselines are measured on a single-core CPU, except for BOSS, whose speed measurements should be interpreted with caution given that they are based on highly-vectorized code run on a GPU. A clear pattern is visible for nearly all methods across the different benchmarks: as the dimensionality of the problem increases, so does the wall-clock time. Suprisingly, this is not the case for Bounce, where the wall-clock time stays roughly constant across varying dimensionalities. We hypothesize that this is due to Bounce's ess nested embeddings, which significantly reduce the dimensionality of the problem for most of the iterations.
Figure 3 summarizes the results from Table 1 follows: divide the wall-clock time of each method by that of the fastest method (i.e. CoCaBO), and then take the average of these ratios across all benchmarks. Using this summary, from Section 3.3.3: one-hot RBF is more than 2x faster than COMBO's s kernel (on average across all five problems). Additionally, the simple heat-kernel pipeline proposed in Section 4.3 is also fast, with only minimal overhead compared to CoCaBO or Bounce.
clearly observe the benefits of our faster implementation
F NASLib experiments
To highlight the power of group-invariant heat kernels, we provide simple example on real-world permutation-invarian problem: Neural Architecture Search (NAS). To the best of our knowledge, in the subfield of Bayesian optimization for NAS, the current state-of-the-ar method is Ru et al. (2020b), which uses a Gaussian process with the Weisfeiler-Lehman (WL) kernel from Shervashidze al. 12011). In this appendix, we benchmark a (permutation-invarian version of) heat kernels against the
29

---

Table The wall-clock time (in seconds) increases together with the dimensionality of the problem.
Method
Pest Control (25D)
Contam. Control (25D)
LABS (50D)
MaxSAT (6DD)
Cluster Exp. (125D)
CoCaBO
227. + 8.32
233.18 + 5.61
369.27 + 6.56
435.30 8.88
857.51 + 15.44
Bounce
548.42 13:57
448.51 6.56
496. 14 12.97
434.04 11.57
471.77 : 9:25
(ona-bot RBF)
403.97
375.80 6.54
565.01
610.68 9.20
1082.23 15.71
RDOCB
413.60 + 3.04
394.50 +: 4.15
639.97 8.96
812.95 +: 7.47
1593.04 15.98
CASMOPOLITAN
534.19 + 6.16
521.41 + 10.50
727.54 = 13.60
793.97 + 21.80
1298.76 :: 79.95
BOD1
615.64 + 9.53
577.63 # 12.40
733.76 + 7.12
791.20 + 12.76
1131,67 + 24.87
Heat (CINBO)
764.70 9.06
691.53 11.67
1173.37 18.92
1367.53 13.52
2672.81 25.69
BOSS
1782.29
4662.90
5376.22
7370.48
CONBO
6163.21 144.18
4522.70 66.74
11982.25 195.49
19359.63 766.23
49606.75 1630.83
WL graph kernel, following the set-up of Ru et (2020b) using the NASLib package (Mehta et al., 2022).
E1 Overview of benchmark problems
NAS-Bench-101
Ying et al. (2019) introduce HAS-Bench-110, tabular dataset containing 423,624 unique convolutional neural network architectures exhaustively generated from a fixed graph-based search space and evaluated CIFAR-10. Each architecture is represented with up to 9 vertices and 7 edges, where operations include 3x3 convolution, 1xl convolution, and 3x3 max-pooling. The dataset provides over million trained models, with each architecture trained multiple times at various training budgets (4, 12, 36, and 108 epochs) and evaluated three times each, reporting metrics including soiniing/validation/eeee accuracy, number of parameters, and training time.
directed acyelic graph
NAS-Bench-201 Dong and Yang (2020) introduce NAS-Bench-201 which extends the scope of reproducible NAS research by providing a cell-based search space with 15,625 unique architectures evaluated across three datasets: CIFAR- 10, CIFAR- 100, and ImageNet-16-1200 Each architecture is represented as a connecl-connected directed acyclic graph with 4 nodes, where edges are selected from 5 operations: none, skip connection, 1x1 convolution. 3x3 convolution, and 3x3 average pooling. Unlike NAS-Bench-101, this benchmark is applicable to almost any up-to-date NAS algo- rithm, including parameter sharing and differentiable methods, and provides fine-grained diagnostic information such as epoch-by-eee by-epoch training/validationness loss and accuracy.
F.2 Implementation details
The NASLib benchmark, introduced in Mehta et al. (2022), consists of collection of problems and algorithms for neural architecture search. The benchmark open-source (with Apache 2.0 license), and allows us to perform all the experiments of Appendix F with minimal changes. The original benchmark is available https://githi:: be found in the supplementary material. To prevent bias or overfitting, our experimental set-up relies as much as possible on the default values present in NASLib and Ru al. (2020b). We highlight some key elements of the configuration below.
com/ automm/NASLib. and our modified version can
Experimental set-up We use 10 initialization points, opt for batch size of 5 and allow up to 150 iterations. As hyperparameter optimizer and acquisition function, we use the ubiquitous Adam optimizer (Kingma and Ba, 2015) and Expected Improvement (EI) (Močkus, 1975; Jones et al., 1998), respectively. We transform all black-box function values (i.e. the test errors) by converting them to log-scale and standardizing them using the mean and standard deviation of all previously observed values. As above, we transform these values back at prediction. All experiments are repeated across 20 random seeds, and all NASLib plots this paper display the median and standard errors (with respect to the seeds) as solid line and shaded area, respectively. To optimize the acquisition function, we use a pool size of 200, where one half is generated from random sampling and the other half generated from mutating the top-10 10 best performing architectures already queried (see Appendix F.2
30

---

of Ru et al. (2020b) for detailed description). No priors were imposed on the hyperparameters, and therefore we use MLE and not MAP inference.
Permutation-invariance for graphs In order to apply the heat kernel to the labeled graphs of varying nodes found in MAS-Bench-101/200
transform the input space following Borovitskiy et al. (2023). More specifically, to deal with the varying sizes, we pad all graphs with additional disconnected nodes, such that all graphs now have the same order as the graph in the dataset with the maximal number of nodes. Additionally, to deal with the labels of the graph, we assign certain types of nodes pre-specified groups of vertices, thus aligning different data samples better (see Figure of Borovitskiy et al., 2023). Lastly, to account for graph automorphisms, we use the group-invariant kernel kum (x, x') from Section D.1 and approximate the large sum as in Borovitskiy al. (2023), namely using Monte Carlo sampling:
Ksum X,
Σ
Σ
S Sn
Sea iid U(S.).
S
Ti 0
where S, denotes the set of all permutations and ((S,)) ) is the uniform distribution over Sn- For all NASLib experiments in this paper, we have used |S] 200.
F.3 Regression problems and Bayesian optimization
As done in Ru et (2020b), we analyze the regression and different kernels on NASLib. For the regression problems, we use different training sizes, ranging from 25 to 200 datapoints, and a test size of 200 datapoints. Here, all datapoints are sampled uniformly at random. Again, similarly to Ru et al. (2020b), we choose the Spearman's ''s rank correlation between predicted and true accuracy as the performance metric, as what matters for selecting architectures in BO loops is their relative, and not absolute, performance. For Bayesian optimization, we provide more detailed explanation of our set-up in Appendix F.2.
performance of
NB101 (CIFAR- 10)
NB201 (CIFAR- 10)
0.98
Rank cocrelation
0.85
0.90
0.85
0.75
100
200
WL
NB201 (CIFAR-100)
NB201 (ImageNet166 6-10))
Heat
Heat (sum)
Rank correlation
0.85
0.85
0.80
0.80
0.75
0.70
0.70
50
100
150
200
50
100
150
200
Number training samples
Nomber of training samples
Figure 9: For regression problems on the NASLib benchmark, the Heat kernel performs comparably to the state-of-the-arr WL kernel. An averaged version of this Heat kernel, indicated Heat (sum), outperforms the WL kernel.
In Figures 9 and 10, we compare three kernels: the oftte-of-the-an Weisfeiler-Lehman (WL) kernel, the "standard" heat kernel (Heat), and its cormutation-invarian version kumm (x, x'). indicated by Heat (sum). For this last one, we use the Monte Carlo approximation from Appendix F.2 with 200 random permutations. On datasets, Heat (sum) outperforms Heat, and achieves similar or better performance compared to WL. We argue that this is strong result, given that the WL kernel is designed specifically for graphs, whereas heat kernels are general and lead strong performance on range of different combinatorial structures.
31

---

NB101 (CIFAR-1O) 10)
NB201 (CIFAR-1O) 10)
6.75
Text emnr (%)
6.50
10.0
6.25
9.5
6.00
9.0
5.75
8.5
50
100
150
50
100
150
Random Search
NB201 (CIFAR-100)
NB201 1mmageNet6-1122)
56
Heat (sum)
Test ettor (%)
55
28
54
27
53
150
Namber of architectures
Number of architectures
Figure 10: For Bayesian optimization on the NASLib benchmark, an averaged version of the Heat kernel, indicated by Heat (sum), achieves similar performance to the sfate-of-the-art WL kernel.
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The theoretical claims from the abstract and introduction are outlined in Section 3 (with proofs in Appendix A), and the empirical claims are detailed in Section (with additional figures in the appendix).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We provide an explicit paragraph mentioning limitations (see Section 5).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
33

---

Answer: [Yes]
Justification: Assumptions are stated in the theorems themselves, and complete proofs can be found in Appendix A.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Careful descriptions of our implementations for the NCBO and NASLib bench- marks can be found in Appendices E.2 and F.2, respectively. Additionally, we release our code-base at https: // g thub. com/ co colmont/ heat www.-keenelleeee 4 B-B0. git.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
34

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Our (anonymized) code-base provides instructions how install the necessary packages, and contains scripts to reproduce all experiments found in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
public/guine httiii/gguidees/eeembiiiiii wewiaiissssoooipyoooooooci for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //iiss... wwwpcc/pppc/.aee..c...ccce.cetle pwmblc/gguides....//ee/ /ttegguuuddeeeoeeuubiiiiiii /wt////oodiisiiiioooo soi.bbiiissioooccccccccoo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: All the training and test details are outlined in Appendices E,2 and F.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All our figures contain shaded regions, displaying the standard error of the mean. More information about this standard error can be found in Appendices E.2 and F.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
35

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The computer resources used for our experiments are outlined in Appen- dices E.2 and F.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https : http:///ee.u.eeeeeeeeeeee cc cc/ cc/public////ccccccccccccccccccc ceabblicc/hhiii het//hhisssuiiiieeeeeeeeeeeeaeae sescuideeines?
Answer: [Yes]
Justification: To the best of our knowledge, the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., s if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: provide an explicit paragraph discussing societal impacts (see Section 5). Guidelines:
The answer NA means that there is no societal impact of the work performed.
36

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release data or models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: In Appendices E.2 and F.2, we reference the original papers introducing the MCBO, NASLib and Bounce packages. Moreover, explicitly state their respective licenses, as well as respect the terms of use described therein.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should citep the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
37

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We release our (anonymized) code-base with appropriate documentation, including license.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowd-sourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowd-sourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
38

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: : //neruurpp.... wwc/onnereeccs///0000 for what should or should not be described.
39


Reviews:
[{"review_id": "cD8pZb6iBt", "reviewer": "Reviewer_b9FW", "summary": "This paper discusses algorithms for combinatorial Bayesian optimization (CBO), a problem that occurs in many practical applications. Specifically, this paper focuses on heat or diffusion kernels that operate on a graph that models the search space and Matern-class kernels (including the RBF kernel) relying on the Hamming distance.\n\nThe authors show that these Matern-class kernels _are_ heat-kernels if one considers categorical problems where the graph is modeled as a Hamming graph. Furthermore, they show that any Hamming kernel is a $\\Phi$-kernel, which is a generalization of the Heat kernel.\n\nBased on these insights, the authors propose a faster implementation of the heat kernel based on the Hamming distance.\n\nThe authors benchmark their kernel against various baselines on different categorical benchmark problems. They show that their simplified heat kernel is competitive with the state of the art. They also use random permutations of the categorical variables as proposed by Papenmeier et al. (2023) and show that the SSK kernel is also sensitive to those permutations (Papenmeier et al. have shown this for BODi and COMBO).", "questions": "* Why do we need Figures 2 and 4? Aren't they showing mostly the same thing?\n* Do you have concrete ideas on how one could extend the analysis to ordinal problems?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "__Strengths__\n\n* The paper is well written and follows a clear structure. The problem is relevant - categorical BO has various applications.\n* Showing that an RBF kernel with Hamming distance is equivalent to COMBO reduces the computational complexity of running COMBO drastically.\n* The authors show that yet another algorithm (BOSS) is sensitive to permutations of categories. This is highly relevant because categorical problems have no notion of 'order'. In most cases, it is arguably unexpected that randomly permuting the order of the categories affects performance, and the methods that are affected by this have not stated this implicit bias. Hence, it is arguably not by design.\n* The authors are open about the fact that the analysis only holds for categorical problems.\n\n__Weaknesses__\n\nI see two main weaknesses. 1) The analysis only holds for categorical problems. 2) The proposed algorithm method is very close to already existing methods. I am not particularly concerned about 2) since the empirical performance is not the focus of this paper, and acts more as a sanity check. 1) is a bigger limitation, even though the authors argue that ordinal problems might not be as prevalent in practice.", "was_revised": true, "final_justification": "As discussed under strengths, this paper addresses a relevant topic (combinatorial BO) and, for purely categorical problems, provides a computationally more efficient method of running BO with Heat kernels. This is possible due to an equivalence between using RBF kernels with Hamming distance and heat kernels discovered by the authors. Finally, the authors show that BOSS is sensitive to a permutation of categories, following up on a recent analysis of this issue. \n\nOverall, this paper has several strong contributions but is focused on purely categorical problems - the analysis does not extend to, e.g., ordinal variables.", "rebuttal": "We are delighted to see the reviewer found the paper to be well-written, and the problem to be relevant. We appreciate  the reviewer's insights, and are happy to answer their questions.\n\n>Why do we need Figures 2 and 4? Aren't they showing mostly the same thing?\n    \nYes, that is correct: Figures 2 and 4 depict the same baselines, only on different datasets. The same is true for Figures 1 and 3. Due to space constraints, we decided to move some datasets to the appendix. In the camera-ready version, we have now more clearly described the relationship between these two pairs of figures (2/4 and 1/3). We are thankful to the reviewer for pointing out this possible point of confusion.\n    \n>Do you have concrete ideas on how one could extend the analysis to ordinal problems?\n    \nOn line 139 of our submitted paper, we explain how to transform the discrete domain $\\mathcal{X}$ into a graph $\\mathcal{G}$. Specifically, we define the graphs $\\mathcal{G}_i$ as complete graphs, and argue that this is a natural choice when the underlying variables $x_i \\in \\mathcal{X}_i$ are categorical variables. However, for other types of discrete variables, the graphs $\\mathcal{G}_i$ can (and probably should) have different structures (as hinted at on line 143). For example, for an ordinal variable $x_i \\in \\mathcal{X}_i$, it is natural to define $\\mathcal{G}_i$ as a path graph, where nodes are not equidistant anymore (whereas this is the case for complete graphs). In fact, this path-graph structure for ordinal variables is also suggested in the `COMBO` paper [1].\n    \nUsing the above idea, there is a clear way to connect ordinal variables to our unifying framework. First, define the graphs $\\mathcal{G}_i$ according to the nature of their underlying variables $x_i \\in \\mathcal{X}_i$ (complete graph for categorical, path graph for ordinal, etc.). Second, create the graph $\\mathcal{G}$ as the graph Cartesian product of all $\\mathcal{G}_i$ (similar to what is done in Definition 2 of our paper). Lastly, apply the diffusion kernel from Equation 2 or 5 on this product-graph $\\mathcal{G}$. This connection has now been made more explicit in the camera-ready-version, where we have greatly expanded our discussion regarding ordinal variables. We believe this is a meaningful addition, and are grateful to the reviewer for highlighting this aspect.\n\nUnfortunately, the above connection is also where the analysis stops. Since path graphs do not contain the same type of symmetries as complete graphs, the eigenvalues of the corresponding Laplacian do not simplify as much as for categorical variables. Therefore, we do not obtain a simple closed-form solution. In other words, Equation 2 or 5 cannot be simplified to something like Equation 3 or 4.\n\nLastly, we would like to refer to our answer given to Reviewer `oZnX`, where we argue that most combinatorial BO papers do not include _truly_ ordinal variables. As a consequence, we cannot unify many well-known kernels into one unifying framework (as we did for categorical variables), since there simply do not exist many kernels designed for ordinal variables. We have now stressed this argument in the updated version of the paper.\n\n[1] Oh, Changyong, et al. _Combinatorial Bayesian Optimization using the Graph Cartesian Product._ NeurIPS (2019)."}, {"review_id": "ytfeeAfl8T", "reviewer": "Reviewer_opDa", "summary": "Recent works on combinatorial BO have studied the impact of acquision function optimisation, the use of trust regions and the surrogate models. \nWhile GP-based approaches are SOTA in general combinatorial BO in the absense of prior information, there is still a gap in the understanding of the impact of the kernel choice \non the BO performance. In this work the authors aims at bridging this gap, not only by empirically assessing the merits of the standard combinatorial kernels \n(proposed in COMBO, CASMOPOLITAN, ...) but by actually revealing that most of these standard kernels are somewhat equivalent and belong to a larger family of Hamming-based kernels.", "questions": "Please see above", "limitations": "ok", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper is clearly written and easy to follow.\n- The unifying framework presenting Casmopolitan and COMBO kernels as heat kernels is theoretically sound, and offers a new perspective on the combinatorial kernel landscape.\n- The experiments support the equivalence claim and the proposed pipeline is simple and fast.\n- The proposed generalization to Hamming-based kernels open the way to new investigation.\n\nWeakness:\n- One could say the main results is simply derived given the results of Kondor and Lafferty on the diffusion kernel for the complete graph (though it is true that it was not exploited or noticed before)\n- It could be interesting to consider more real-world black-boxes (such as the ones from the MCBO library); Please evaluate on those: \n\n\nMinor comments:\n- line 229: it should be \"by choosing k\", not \"\\mathbb{k}\"\n- Have a line style distinct for heat-based and non-heat-based to ease the analysis\n\nExtra question:\n- Is there a way to see the kernel from BODi as a heat kernel variation in some sense?", "was_revised": true, "final_justification": "Great paper and the rebuttal addressed all my comments.", "rebuttal": "We are pleased to see the reviewer found the paper to be \"clearly written\" and our framework to be \"theoretically sound\". We are grateful for the reviewer's input and will be addressing their comments.\n\n>It could be interesting to consider more real-world black-boxes (such as the ones from the MCBO library); Please evaluate on those:\n    \nIn the `MCBO` library, there a four categorical benchmarks left on which we did not evaluate: two biological benchmarks (`RNA Inverse Folding` and `Antibody Design`) and two logic-synthesis optimization benchmarks (`AIG Optimization` and `MIG Optimization`). Since `Antibody Design` and `MIG Optimization` contain much slower simulators (`MIG Optimization` can be up to $200.000\\times$ slower), we focus our efforts in this limited time-window on `RNA Inverse Folding` and `AIG Optimization`. As a result, the camera-ready paper now also contains one biological and one logic-synthesis optimization task. We believe this makes the experimental section of the paper more complete, and are grateful to the reviewer for this suggestion. \n    \nUnfortunately, the NeurIPS policy this year does not allow us to show or link images in any way whatsoever. Consequently, we use text to describe the main trends observed on the new plots:\n1. On both `RNA Inverse Folding` and `AIG Optimization`, all Hamming kernels obtain nearly indistinguishable performance (as is the case for the other datasets presented in the paper).\n2. On both datasets, `SSK` (`BOSS`) and `HED` (`BODi`) do not seem particularly sensitive to relocation of the optima (a similar behavior was observed on `LABS` in Figures 1 and 2 of the paper).\n3. On both datasets, our fast and simple heat-kernel pipeline achieves identical performance to `Bounce`, which is currently the state-of-the-art method. Interestingly, although both methods (`Bounce` and ours) are the top performers on `AIG Optimization`, this is not the case on `RNA Inverse Folding`. On this last dataset, there is a new trend: additive kernels, namely `CoCaBO` and `RDUCB`, are able to outperform Hamming kernels for the first time. This is not necessarily surprising: in related biological tasks, there exists evidence that first- and second-order interactions lead to strong predictive performance [1-2]. The `MCBO` paper also contains potential evidence for this low-order hypothesis: a genetic algorithm, which only mutates a few variables at a time and does not inherently model high-order interactions, performs remarkably well on `RNA Inverse Folding`, significantly outperforming all BO methods. Lastly, we note that if such additive structure is known _a priori_, one can easily incorporate it into the heat-kernel, leading to methods such as (but not limited to) `RDUCB` and `CoCaBO` (see Appendix C.2).\n\n[1] Domingo, Júlia, Guillaume Diss, and Ben Lehner. _Pairwise and higher-order genetic interactions during the evolution of a tRNA._ Nature (2018).\n    \n[2] Faure, Andre J., et al. _The genetic architecture of protein stability._ Nature (2024).\n\n>line 229: it should be \"by choosing k\", not \"mathbb{k}\"\n\nWe acknowledge that our notation in the mentioned paragraph is confusing, and are thankful to the reviewer for bringing this to our attention. However, we do not believe that replacing \"mathbb{$k$}\" by \"$k$\" is correct. In the updated camera-ready version, we have now written: \"by choosing mathbb{$k$}$(d)$ to be any (continuous) isotropic kernel (with $d = \\lVert\\mathbf{x} - \\mathbf{x}'\\rVert^2_2$), we always obtain a valid Hamming kernel $k$.\" We are happy to address any further questions the reviewer might have.\n    \n>Have a line style distinct for heat-based and non-heat-based to ease the analysis\n    \nWe thank the reviewer for this great suggestion. We have made use of it for the camera-ready version of the paper, which now contains improved plots.\n    \n>Is there a way to see the kernel from BODi as a heat kernel variation in some sense?\n\nWe appreciate the reviewer's excellent question, and believe the answer is \"no\". In fact, we have constructed a short sketch for why `BODi` is not part of the Hamming-kernel class, and, as a consequence, cannot be seen as a (generalized) heat kernel. This proof has now been included in the appendix, and is referenced in the main part of the paper. We believe this is a meaningful addition to the paper, and thank the reviewer for highlighting this point.\n\nAs outlined in Definition 6: a kernel is a Hamming kernel (`HK`) if and only if it depends on $\\mathbf{x}, \\mathbf{x}' \\in \\mathcal{X}$ through the square root of the Hamming distance $h(\\mathbf{x}, \\mathbf{x}')$. That  is,\n$$k_{\\texttt{HK}}(\\mathbf{x}, \\mathbf{x}') := f\\left(\\sqrt{h(\\mathbf{x}, \\mathbf{x}')}\\right),$$\nfor some $f : \\mathbb{Z}_0^+ \\rightarrow \\mathbb{R}$.\n    \nIn contrast, the `BODi` kernel depends on $\\mathbf{x}, \\mathbf{x}' \\in \\mathcal{X}$ through the term\n$$k_{\\texttt{BODi}}(\\mathbf{x}, \\mathbf{x}') := g\\left(\\lVert\\phi_{\\mathbf{A}}(\\mathbf{x})-\\phi_{\\mathbf{A}}(\\mathbf{x}')\\rVert^2_2\\right),$$\nwith\n$$g(d): =\\left( 1 + \\frac{\\sqrt{5} d}{\\ell} + \\frac{5 d^2}{3 \\ell^2} \\right) \\exp \\left( -\\frac{\\sqrt{5} d}{\\ell} \\right).$$\nHere, $g(\\cdot)$ is the Matérn-5/2 function, where we note that $g(\\cdot)$ constitutes a bijective function. Additionally, $\\phi_{\\mathbf{A}}(\\cdot)$ denotes the mapping towards the `HED` embedding (see section 4 of [3]), namely:\n$$\\left[ \\phi_\\mathbf{A}(\\mathbf{x}) \\right]_i := h(\\mathbf{a}_i, \\mathbf{x}),$$\nwith $\\mathbf{a}_i \\in \\mathbf{A}$ one of the $M$ anchor points in dictionary $\\mathbf{A}$.\n    \nFor `BODi` to be a Hamming kernel, there thus needs to exist a function, say $u(\\cdot)$, such that \n $$u\\left(\\sqrt{h(\\mathbf{x}, \\mathbf{x}')}\\right) = \\lVert\\phi_{\\mathbf{A}}(\\mathbf{x})-\\phi_{\\mathbf{A}}(\\mathbf{x}')\\rVert^2_2.$$\nIf this function $u(\\cdot)$ exists, we can define $f:= g \\circ u$, obtaining \n$$\nk_{\\texttt{BODi}}(\\mathbf{x}, \\mathbf{x}') = g\\left(\\lVert\\phi_{\\mathbf{A}}(\\mathbf{x})-\\phi_{\\mathbf{A}}(\\mathbf{x}')\\rVert^2_2\\right)\n= g\\left(u\\left(\\sqrt{h(\\mathbf{x}, \\mathbf{x}')}\\right)\\right)\n= f\\left(\\sqrt{h(\\mathbf{x}, \\mathbf{x}')}\\right)\n= k_{\\texttt{HK}}(\\mathbf{x}, \\mathbf{x}').\n$$\n    \nHowever, as becomes clear by looking at the mapping $\\phi_{\\mathbf{A}}(\\cdot)$, there does not exist a function $u(\\cdot)$ satisfying the above claim. We provide a small counter-example with $M=1$ below. \n\nIn scenario A, we have:\n$$\\mathbf{x} = [1,1,1], \\text{ } \\mathbf{x'} = [1,1,2] \\text{ and } \\mathbf{a}\\_1 = [1,1,1],$$\nwhich gives us\n$$\\sqrt{h(\\mathbf{x}, \\mathbf{x}')} = 1 \\text{ and } \\lVert\\phi_{\\mathbf{A}}(\\mathbf{x})-\\phi_{\\mathbf{A}}(\\mathbf{x}')\\rVert^2_2 = 1.$$\n    \nIn scenario B, we have:\n$$\\mathbf{x} = [1,1,2], \\text{ } \\mathbf{x'} = [1,1,3] \\text{ and } \\mathbf{a}\\_1 = [1,1,1],$$\nwhich gives us\n$$\\sqrt{h(\\mathbf{x}, \\mathbf{x}')} = 1 \\text{ and } \\lVert\\phi_{\\mathbf{A}}(\\mathbf{x})-\\phi_{\\mathbf{A}}(\\mathbf{x}')\\rVert^2_2 = 0.$$\n\nFor $u(\\cdot)$ to work in both scenarios, we would need to have:\n$$u(1) = 1 \\text{ and } u(1) = 0,$$\nwhich is clearly not possible. As a result, we conclude that `BODi` is not a Hamming kernel, and therefore also not a heat kernel (or a direct generalization thereof).\n\nIn fact, using the above proof-structure, we can show an even stronger result: `BODi` is not part of an (even broader) general class of kernels, which includes not only Hamming- and graph-based kernels, but also additive kernels such as `CoCaBO` and `RDUCB` (see Appendix C.2). With this, we feel confident in our answer that `BODi` cannot be seen as a heat-kernel variation in some sense.\n\n[3] Deshwal, Aryan, et al. _Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-Based Embeddings._ AISTATS (2023)."}, {"review_id": "jHpef1vlWE", "reviewer": "Reviewer_ot94", "summary": "The paper presents a unifying review of methods in combinatorial BO. Authors show that the kernels of popular CASMOPOLITAN and COMBO methods are mathematically equivalent and that they both belong to a wider class of heat kernels. This finding has profound implications. First of all, it means that the only differences between CASMOPOLITAN and COMBO we empirically observed in the past were not coming from differences in surrogate models, which authors empirically demonstrate by running both methods with exact same settings and showing their performance is indistinguishable. Secondly, it means one can perform the computation of the COMBO kernel much faster, which authors demonstrate achieving 2x speedup. Lastly, authors show that a basic form of the heat kernel with the best performing acquisition optimiser and trust region is sufficient to achieve state-of-the-art performance across a number of problems.", "questions": "How do you think one could incorporate continuous variables into the heat kernel framework in the Mixed-space BO problem setting?", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The paper unravels a vital connection between two well-known methods that the community was previously oblivious to.\n- The paper supports this surprising theoretical result with convincing and comprehensive experiments \n- The papers draws a number of important conclusions from their theoretical results that are incredibly useful to practitioners, for example, that given the same hyperparameters and acquisition optimiser, CASMOPOLITAN and COMBO will perform the same and that the computation of COMBO kernel can be massively sped up\n- The paper provides clear guidance to practitioners, proposing a simple, yet powerful baseline\n- The paper is accompanied by an extensive appendix, which discusses how to adopt the heat kernels to invariances or how to incorporate an additive structure into them\n\nWeaknesses:\n- I do not think there are any significant weaknesses, however, I believe the presentation of the paper could be slightly improved. A lot of important results and insights appear only in the appendix. Authors should think carefully about how to best use the additional page in camera-ready version and move the most important parts of the appendix there. It would also be nice to report the number of seeds used for each run in the main text.\n- (typo): I believe equation 4 should have a minus inside the exponent", "was_revised": true, "final_justification": "I did not have any major concerns regarding the submission, my questions were mostly points that I wanted to clarify. After authors clarified them, I maintain my positive evaluation of the work.", "rebuttal": "We are excited and encouraged to see the reviewer's strong positive response, and are happy to reply to their questions below.\n\n>I do not think there are any significant weaknesses, however, I believe the presentation of the paper could be slightly improved. A lot of important results and insights appear only in the appendix. Authors should think carefully about how to best use the additional page in camera-ready version and move the most important parts of the appendix there. It would also be nice to report the number of seeds used for each run in the main text.\n    \nWe would like to thank the reviewer for highlighting this aspect. During this rebuttal period, we have taken great care to migrate the most important parts of the appendix to the additional page of the camera-ready version. We have also made sure to include the number of seeds of each run in the main paper.\n    \n>(typo): I believe equation 4 should have a minus inside the exponent\n    \nWe politely disagree with the reviewer, and provide a short derivation below to explain our intuition. Here, we start with an RBF kernel applied to one-hot encoded data, namely $\\mathbf{z}, \\mathbf{z}' \\in \\\\{0,1\\\\}$:\n$$\\exp\\left(-\\frac{\\lVert\\mathbf{z} - \\mathbf{z}'\\rVert^2_2}{2\\ell}\\right).$$\nAs expected, this kernel has a minus inside the exponent. Afterwards, we use the equivalence from Equation 1 in the paper: \n$$h(\\mathbf{x}, \\mathbf{x}') = \\frac{\\lVert\\mathbf{z} - \\mathbf{z}'\\rVert_2^2}{2},$$ \nwhere $h(\\mathbf{x}, \\mathbf{x}')$ is the Hamming distance between categorical variables $\\mathbf{x}, \\mathbf{x}' \\in \\mathcal{X}$. Using this equivalence, and explicitly writing out the Hamming distance in terms of Kronecker-delta functions $\\delta(\\cdot,\\cdot)$, we get:\n$$\n\\exp\\left(-\\frac{\\lVert\\mathbf{z} - \\mathbf{z}'\\rVert^2_2}{2\\ell}\\right) = \\exp\\left(-\\frac{h\\left(\\mathbf{x}, \\mathbf{x}'\\right)}{\\ell}\\right)\n= \\exp\\left(-\\frac{1}{\\ell} \\left[n - \\sum_{i=1}^n \\delta(x_i, x_i')\\right] \\right)\n\\propto \\exp\\left(\\sum_{i=1}^n \\frac{\\delta(x_i, x_i')}{\\ell}\\right),\n$$\nwhere the minus sign has now disappeared. If we replace $\\ell$ by $\\ell_i$ to allow for ARD, and re-parameterize with $\\ell_i := n/\\gamma_i$, we obtain\n$$\\exp\\left(\\frac{1}{n}\\sum_{i=1}^n \\gamma_i \\delta(x_i, x_i')\\right),$$\nwhich is exactly the kernel proposed in Equation 1 of [1] (and presented in Equation 4 of our paper). We hope that this derivation was able to clarify the reason for the missing minus sign, and are happy to address any remaining questions the reviewer might have.\n\n[1] Wan, Xingchen, et al. _Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces._ ICML (2021)."}, {"review_id": "mQWN7jwrEL", "reviewer": "Reviewer_oZnX", "summary": "The paper mainly presents an analysis to unify different kernels used commonly in categorical BO. The paper states that these common kernels, e.g. kernels in CASMOPOLITAN, COMBO, Bounce, CoCaBO, etc., are either heat kernels (diffusion kernels), or parts of a certain generalized class containing heat kernels. Notable claims include: (1) CASMOPOLITAN and COMBO are both fundamentally heat kernels, (2) CASMOPOLITAN and Bounce come from the class of Hamming-based heat kernel (3) COMBO comes from the class of graph-based heat kernel, (4) Hamming-based and graph-based kernels are equivalent under a non-trivial assumption, (5) heat kernels can be extended to relate to CoCaBO and RDUCB kernels. All claims are supported with theoretical analysis. Experiments demonstrate the equivalence of certain kernels, and show that a simple heat kernel pipeline can have equivalent performance to the state-of-the-art baselines.", "questions": "-\tGiven the simplicity of heat kernel pipeline, can the authors implement the discussed new ideas in Hamming-based approach in Sec. 3.4.1(via rational quadratic kernel), and similarly for Graph-based kernels in Sec. 3.4.2 (via graph Matern kernel and sum-of-inverse polynomial kernel)?\n-\tIs there any way to make heat kernel enjoy the same benefit of BODi and BOSS kernels such that the performance is also great in problems with special structure? It would be much better if a kernel can work well in both scenarios.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n-\tThe paper proposes a unifying framework for many common kernels in categorical BO, which is very interesting and important to understand this field of BO.\n-\tThe paper is well written and easy to follow.\n-\tThere are many theoretical results that clearly state the assumptions and drawbacks.\n-\tExperimental results provide interesting insights on the equivalence of many kernels.\n\nWeaknesses:\n\n-\tI think the authors could leverage the ideas and propose more effective kernels that can empirically outperform the state-of-the-art baselines. See my questions. \n-\tI do not think no-ordinal variables is a standard in combinatorial BO papers (line 350). In my opinion, many recent papers either treat ordinal variables as categorical or avoid addressing them due to the additional complexity involved, especially when their methods already demonstrate strong performance on categorical inputs. Hence the ordinal variables have received less attention. In fact, many real-world tasks require the ordinal variables, notably in HPO (number of trees or max depth in random forests, number of layers and units in neural networks, etc.). Examples in other fields include [1-3], which have all been used in BO works [4-5].\n-\tThe empirical performance is only on par with the state-of-the-art, slightly reducing the contribution of the work.\n\n[1] Kohira, Takehisa, et al. \"Proposal of benchmark problem based on real-world car structure design optimization.\" Proceedings of the Genetic and Evolutionary Computation Conference Companion. 2018.\n\n[2] Dreifuerst, Ryan M., et al. \"Optimizing coverage and capacity in cellular networks using machine learning.\" ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2021.\n\n[3] Wang, Boqian, et al. \"Harnessing a novel machine-learning-assisted evolutionary algorithm to co-optimize three characteristics of an electrospun oil sorbent.\" ACS Applied Materials & Interfaces 12.38 (2020): 42842-42849.\n\n[4] Daulton, Samuel, et al. \"Bayesian optimization over discrete and mixed spaces via probabilistic reparameterization.\" Advances in Neural Information Processing Systems 35 (2022): 12760-12774.\n\n[5] Daulton, Samuel, et al. \"Multi-objective bayesian optimization over high-dimensional search spaces.\" Uncertainty in Artificial Intelligence. PMLR, 2022.", "was_revised": true, "final_justification": "The authors answered adequately to all of my questions, therefore, I keep my original score for this paper, which is Accept.", "rebuttal": "We are gratified to see the reviewer found the paper to be well-written, and our unifying framework to be \"very interesting and important\". We thank the reviewer for this thoughtful response, and reply to the mentioned points below.\n\n>I do not think no-ordinal variables is a standard in combinatorial BO papers (line 350). In my opinion, many recent papers either treat ordinal variables as categorical or avoid addressing them due to the additional complexity involved, especially when their methods already demonstrate strong performance on categorical inputs. Hence the ordinal variables have received less attention. In fact, many real-world tasks require the ordinal variables, notably in HPO (number of trees or max depth in random forests, number of layers and units in neural networks, etc.). Examples in other fields include [1-3], which have all been used in BO works [4-5].\n\nWe believe a slight misunderstanding took place, and thank the reviewer for bringing it to our attention. Since different sources rely on different definitions for _ordinal variables_, we now explicitly specify ours: \"Ordinal data is a categorical, statistical data type where the variables have natural, ordered categories and _the distances between the categories are not known_.\" This is the main definition on Wikipedia [6], which cites [7] as being the source for this definition. We have carefully examined all the variables in the suggested benchmarks [1-3], and conclude, to the best of our knowledge, that none of them are ordinal variables (according to our definition). As a general example, we consider the number of layers in neural networks. Here, although the variable is discrete, there is a clear distance between the different categories (namely the Euclidean distance). Therefore, according to our definition, this is not an ordinal variable. For lack of a better word, we will refer to these discrete variables (containing an inherent notion of distance) as \"discrete-quantitative variables\".\n\nIn light of the above clarification, we believe our claim holds true: \"our experiments do not contain ordinal variables, but we note that this is standard in recent combinatorial BO papers\" (line 350). Following this insightful discussion with the reviewer, we have updated the camera-ready version of the paper: we have included a more explicit categorization of the different possible discrete variables, as well as an expanded discussion of how existing works fit into this categorization.\n\nAs pointed out by the reviewer, combinatorial BO papers do often contain discrete-quantitative variables. For such variables, we believe the associated kernels are rather straightforward: use any (continuous) isotropic kernel, along with an appropriate distance function (usually Euclidean). As such, these kernels can simply be seen as continuous kernels, which is why we did not explicitly address them in our unifying framework. Additionally, although discrete-quantitative variables can borrow their kernels from continuous BO, we note that this is not true for their acquisition-function optimizers, which need to be discrete (e.g. genetic algorithm). We are grateful to the reviewer for highlighting this additional type of discrete variable, and have included an additional paragraph in the camera-ready version that discusses this relevant topic.\n\nLastly, for ordinal variables (according to our definition of the term), we would like to mention our answer provided to Reviewer `b9FW`. In this answer, we explain how to model ordinal variables using path graphs $\\mathcal{G}_i$, therefore connecting them to our existing heat-kernel framework.\n\n[6] [https://en.wikipedia.org/wiki/Ordinal_data](https://en.wikipedia.org/wiki/Ordinal_data)\n    \n[7] Agresti, Alan. _Categorical Data Analysis._ John Wiley & Sons (2002).\n\n>Given the simplicity of heat kernel pipeline, can the authors implement the discussed new ideas in Hamming-based approach in Sec. 3.4.1(via rational quadratic kernel), and similarly for Graph-based kernels in Sec. 3.4.2 (via graph Matern kernel and sum-of-inverse polynomial kernel)?\n\nWe have implemented two of the above three kernels: the Hamming-based rational-quadratic kernel and the graph-based Matérn kernel. To the best of our understanding, the sum-of-inverse polynomial kernel is fundamentally an ARD kernel, and turning this into a non-ARD kernel would not be sensible. Since our experimental evaluation considers only non-ARD kernels, we believe it would be confusing for the reader to add an ARD kernel, which is why we have omitted it.\n\nUnfortunately, the NeurIPS policy this year does not allow us to show or link images in any way whatsoever. Fortunately, in this case, it should not be a problem, as the results are easy to describe: on all seven benchmarks (including the additional two suggested by Reviewer `opDa`), the Hamming-based rational-quadratic kernel and the graph-based Matérn kernel achieve near-identical performance compared to the five other Hamming kernels evaluated in the paper. As a result, we are now left with one single rainbow-colored line, which includes seven different kernels that all obtain the exact same empirical performance. To the best of our knowledge, we believe we are the first to demonstrate the empirical (and partly theoretical) equivalence between these seven kernels for combinatorial BO, which were previously linked to distinct methods.\n    \nMoreover, in Section 3.4 of the paper, we show that Hamming- and graph-based kernels can be seen as broader (generalized) versions of heat kernels, and that these two classes also coincide (for $|\\mathcal{X}_1| = \\ldots = |\\mathcal{X}_n|$). With these new experiments, we now have additional empirical evidence for these theoretical results. We believe these experiments meaningfully improve the paper, and sincerely thank the reviewer for suggesting them.\n\n>Is there any way to make heat kernel enjoy the same benefit of BODi and BOSS kernels such that the performance is also great in problems with special structure? It would be much better if a kernel can work well in both scenarios.\n\nThe short answer is \"yes\", and we see two ways of doing this: incorporating group-invariances, or including additional features.\n\nWhen it is known that the problem at hand has a certain type of structure, this structure can often be modeled by incorporating invariance to a certain group $G$ directly into the kernel. As explained in Section 3.5 and Appendix C.1, our heat-kernel framework allows for the incorporation of _any_ group-invariance, and this through a straightforward procedure. In a way, this is also what the `SSK` (kernel from `BOSS`) does, since it models certain string-invariances, which seems to be a powerful inductive bias for certain types of optima. In Figures 5 and 7, we empirically demonstrate the advantages of incorporating such group-invariances, resulting in state-of-the-art performance. However, in general, modeling invariances can quickly become expensive, as can be seen by `BOSS`' high computational cost in Figure 6 (and the fact that it needs highly-vectorized code and high-memory GPUs to get to this speed). \n\nA more lightweight alternative, though perhaps less principled, is to include additional \"strategic\" features. For example, in the `Bounce` paper [8], the authors argue that `BODi` achieves its performance mostly due to its way of doing \"uniform\" sampling of anchor points, which turns out to be heavily skewed towards points with a certain type of structure. As a consequence, `BODi`'s `HED` embeddings or features $\\phi_{\\mathbf{A}}(\\mathbf{x})$ contain a clear distance metric to anchor points with a certain structure, which can become a useful signal to navigate towards certain optima. The same idea can easily be integrated within our heat-kernel framework: sample anchor points according to the desired type of structure, and add the relevant features (i.e. the Hamming distance to these anchor points) to the existing heat-kernel. We believe this general idea might be an interesting direction for further research, and have added it to the camera-ready version of the paper. Once again, we appreciate the reviewer's efforts to improve the paper and make it more complete.\n\n[8] Papenmeier, Leonard, Luigi Nardi, and Matthias Poloczek. _Bounce: Reliable High-Dimensional Bayesian Optimization for Combinatorial and Mixed Spaces_. NeurIPS (2023)."}]

Author rebuttal:

Meta-review: This paper considers the problem of Bayesian Optimization (BO) over combinatorial spaces, specifically the space of categorical variables. The key contribution of the paper is to show that Matern-class kernels including the RBF kernel are heat-kernels if one considers categorical problems where the graph is modeled as a Hamming graph (e.g., COMBO). The paper also shosw that any Hamming kernel is a $\Phi$-kernel, a generalization of the Heat kernel. The consequence of this understanding is that we have a computationally-efficient method of running BO with Heat kernels. The paper also show that BOSS (prior method) is sensitive to a permutation of categories building on a recent analysis. Experimental results are also strong.

All the reviewers' liked the paper and the author rebuttal/discussion further reinforced this positive opinion. I recommend accepting the paper and strongly encourage the authors' to incorporate all the discussion into the final paper and also release the code.

There are a couple of papers which explored some of the relevant concepts in this paper.
Equation 3 from the paper is the same as Equation 4.7 in HyBO paper (https://arxiv.org/abs/2106.04682)
Analytical form of COMBO was also explored in MerCBO paper (https://arxiv.org/pdf/2012.07762)
Decision: Accept (poster)