Gravitation & Cosmology, Vol. 7 (2001), No. 1 (25), pp. 1–6 © 2001 Russian
Gravitational Society

A GEOMETRIC MODEL OF GRAVITATING MASS FORMATION
AND BARYON MASS SPECTRUM

Nikolay Popov111e-mail<EMAIL_ADDRESS>and Petr Roshchin
Computation Centre of the Russian Academy of Sciences

Received 31 May 2000

The operator of elementary particle mass spectrum is constructed on the basis
of the postulate of a six-dimensional space-time manifold having a Riemann-
Cartan space structure, proceeding only from its geometric properties. Special
solutions found for this operator well describe the mass spectrum of the known
quark triplet and hence of some baryon supermultiplets.

##  1\. Introduction

In [1], using a Riemann-Cartan six-dimensional manifold of signature
$(---+++)$, a purely geometric model has been successfully constructed,
describing the gravitational field produced by a point source of time axis
rotation in the temporal subspace. Thus one of the principal results of this
study is that, according to the proposed geometric model, the gravitating mass
concentrated at a given point of space originates due to rotation of the time
axis associated with that point. It is noted that the gravitational field
itself produced by such rotation coincides with the Schwarzschild field in the
four-dimensional space-time submanifold, while the point mass turns out to be
proportional to the squared angular velocity of time axis rotation. These
results, based on new geometrical notions of space and time, are rather
qualitative than quantitative and do not allow one to explain the existing
laws governing the elementary particle mass spectrum. To solve such a problem,
the formalism of quantum mechanics should be used.

If the above geometric model is sufficiently realistic, one would expect that
the elementary particle mass values, for particles considered, as a first
appoximation, as points, should represent eigenvalues of some invariant
operator, uniquely induced by the metric of the space-time manifold
constructed in [1]. A significant part in the mass spectrum formation should
be played, according to the geometric model, by the operator component that
acts in the three-dimensional temporal subspace. The present study is
concerned with solving this problem by establishing a strong relationship
between the new notions of physical space-time structure and the properties of
elementary particles.

##  2\. Statement of the problem

Let a six-dimensional manifold $M^{6}$ be equipped with a Riemann-Cartan space
structure, which is characterized by the metric $g_{ij}$ and the connection
$\Delta_{ij}$. The tangential subspace at each point of $M^{6}$ is the pseudo-
Euclidean space $R_{3,3}$ of signature ${(---+++)}$. It should be noted that
for the subsequent constructions it will be sufficient to know the metric $g$,
which is equivalent to assigning to $M^{6}$ the structure of a pseudo-
Riemannian space. However, proceeding in the spirit of [1], to which we shall
have to refer in what follows, we prefer to leave everything as it is. Let
$x_{1},...,x_{6}$ be pseudo-Euclidean coordinates in $M^{6}$, with respect to
which the following requirements are satisfied:

1\. The metric tensor field $g_{ij}(x)$ is continuously differentiable in the
entire manifold $M^{6}$, except the line $x_{1}=x_{2}=x_{3}=x_{5}=x_{6}=0$,
where the metric may be discontinuous.

2\. The metric components $g_{ij}\;i,j=1,...,4$ are independent of
$x_{4},x_{5},x_{6}$, while $g_{ij}$, $i,j=5,6$ depend on $x_{5},x_{6}$ only.

3\. $g_{ij}=g_{ji}=0$ for $i=1,2,3$ and $j=4,5,6$.

4\. The metric components $g_{ij}$ are invariant under orthogonal
transformations of the coordinates $x_{1},\ x_{2},$ $x_{3}$ and, separately,
$x_{5},\ x_{6}$.

5\. At infinity all the metric components tend to zero, except six, which have
the following limiting values:

$g_{11}=g_{22}=g_{33}=-1,\hskip 28.45274ptg_{44}=g_{55}=g_{66}=1.$

Our task is to construct, on the manifold $M^{6}$ with a given metric $g$, the
most general form of a self-adjoint differential operator of second order,
$\Delta_{3,3}$, which possesses the following properties:

$1^{\prime}.$ The operator $\Delta_{3,3}$ is invariant under the group of
transformations $O(3)\times O(2)$;

$2^{\prime}.$ $\Delta_{3,3}$ takes at infinity the following form:

$\Delta_{3,3}=\eta_{ij}\partial_{i}\,\partial_{j}\;,$

where $\eta_{ij}$ is the pseudo-Euclidean metric in the space $R_{3,3}$ (here
and henceforth $\partial_{i}\equiv\partial/\partial_{x_{i}}$ and, for any $z$,
$\partial_{z}\equiv\partial/\partial z$). We must then investigate its
spectrum and establish a direct relationship of this spectrum with the mass
spectra of some elementary particles.

##  3\. Construction of the operator $\bf{\Delta_{3,3}}$

Let us introduce the linear element

$ds={(g_{ij}\,dx_{i}\,dx_{j})}^{1/2}$

Then the most general form of the squared linear element, according to [1] and
taking into account the requirements 2–5, can be represented as

$\displaystyle ds^{2}$ $\displaystyle=$ $\displaystyle
F(r)dx_{4}^{2}+M(\rho)(dx_{5}^{2}+dx_{6}^{2})$ (1) $\displaystyle{}\
+N(\rho)(x_{5}dx_{5}+x_{6}dx_{6})^{2}$ $\displaystyle{}\
-G(r)(dx_{1}^{2}+d\,x_{2}^{2}+d\,x_{3}^{2})$ $\displaystyle{}\
-H(r)(x_{1}d\,x_{1}+x_{2}d\,x_{2}+x_{3}\,dx_{3})^{2},$

where

$\rho=(x_{5}^{2}+x_{6}^{2})^{1/2},\hskip
28.45274ptr=(x_{1}^{2}+x_{2}^{2}+x_{3}^{2})^{1/2}.$

The functions $F,\,G,\,H,\,M$ and $N$ have been found in [1], the first three
of them coinciding with similar functions for the Schwarzschild metric in the
four-dimensional manifold [2]. In the region
$r>\varepsilon_{2}\;,\rho>\varepsilon_{1}$, where
$\varepsilon_{1},\varepsilon_{2}$ are arbitrary but small quantities, these
functions have the form

$\displaystyle F(r)$ $\displaystyle=$ $\displaystyle
1-\frac{a}{(r^{3}+a^{3})^{1/3}},\quad G(r)=\frac{(r^{3}+a^{3})^{2/3}}{r^{2}},$
$\displaystyle{}H(r)$ $\displaystyle=$
$\displaystyle\frac{(r^{3}+a^{3})^{-4/3}\,r^{2}}{1-a(r^{3}+a^{3})^{-1/3}}-\frac{(r^{3}+a^{3})^{2/3}}{r^{4}},$
$\displaystyle{}M(\rho)$ $\displaystyle=$
$\displaystyle\frac{\rho^{2}+\beta^{2}}{\rho^{2}},\quad
N(\rho)=\frac{1}{\rho^{2}+\beta^{2}}-\frac{\rho^{2}+\beta^{2}}{\rho^{4}},$ (2)

where $a$ is the Schwarzschild radius and $\beta$ is a constant. The most
general form of a self-adjoint second-order differential operator which
satisfies the properties $(1^{\prime},2^{\prime})$ is as follows:

$\displaystyle{}\Delta_{3,3}=F(r)\partial^{2}_{4}-\sum_{k=5,6}\frac{1}{i}\partial_{x_{k}}M(\rho)\frac{1}{i}\partial_{x_{k}}$
$\displaystyle{}-\Bigl{(}\frac{1}{i}\partial_{x_{5}}x_{5}+\frac{1}{i}\partial_{x_{6}}x_{6}\Bigr{)}N(\rho)\Bigl{(}x_{5}\frac{1}{i}\partial_{x_{5}}+x_{6}\frac{1}{i}\partial_{x_{6}}\Bigr{)}$
$\displaystyle{}\hskip
72.26999pt+\sum_{k=1,2,3}\frac{1}{i}\partial_{x_{k}}\,G(r)\frac{1}{i}\partial_{x_{k}}$
$\displaystyle{}+\Bigl{(}\frac{1}{i}\partial_{x_{1}}x_{1}+\frac{1}{i}\partial_{x_{2}}x_{2}+\frac{1}{i}\partial_{x_{3}}x_{3}\Bigr{)}H(r)$
$\displaystyle{}\hskip 28.45274pt\hskip
28.45274pt\times\Bigl{(}x_{1}\frac{1}{i}\partial_{x_{1}}+x_{2}\frac{1}{i}\partial_{x_{2}}+x_{3}\frac{1}{i}\partial_{x_{3}}\Bigr{)},$
(3)

provided that $r>\varepsilon_{2}\,,\quad\rho>\varepsilon_{1}$. Formally, the
operator (3) is obtained from the squared linear element (1) by substituting
the Hermitian operator $(1/i)(\partial/\partial x_{j})$ for the differential
$dx_{j}$ and appropriate regrouping of the operator cofactors. Before
proceeding to determine the range of definition, $D\,(\Delta_{3,3})$, of the
operator (3), let us present it in new, partially spherical and partially
cylindrical coordinates $r,\,\theta,\,\varphi,\,\rho,\,\psi,\,t$ where
$x_{1}=r\sin{\theta}\cos{\varphi}$, $x_{2}=r\sin{\theta}\sin{\varphi}$,
$x_{3}=r\cos{\theta}$, $x_{4}=t$, $x_{5}=\rho\cos{\psi}$,
$x_{6}=\rho\sin{\psi}$, Then

$\displaystyle{}x_{5}\partial_{5}+x_{6}\partial_{6}=\rho\partial_{\rho}\,,$
$\displaystyle{}\partial^{2}_{5}+\partial^{2}_{6}=\partial^{2}_{\rho}+\frac{1}{\rho}\partial_{\rho}+\frac{1}{{\rho}^{2}}\partial^{2}_{\psi},$
$\displaystyle{}x_{1}\partial_{1}+x_{2}\partial_{2}+x_{3}\partial_{3}=r\partial_{r}\,,$
$\displaystyle{}\partial^{2}_{1}+\partial^{2}_{2}+\partial^{2}_{3}=\partial^{2}_{r}+\frac{2}{r}\partial_{r}+\frac{1}{r^{2}}\Lambda(\theta,\varphi)\;,$

where

$\Lambda(\theta,\varphi)=\partial^{2}_{\theta}+\frac{\cos\theta}{\sin\theta}\partial_{\theta}+\frac{1}{\sin^{2}\theta}\partial^{2}_{\varphi},$

and the operator (3) will be represented in the new coordinates as follows:

$\displaystyle\Delta_{3,3}$ $\displaystyle=$ $\displaystyle
F(r)\partial^{2}_{t}+(M+{\rho}^{2}N)\Bigl{(}\partial^{2}_{\rho}+\frac{1}{\rho}\partial_{\rho}\Bigr{)}$
$\displaystyle{}+(M^{\prime}+\rho^{2}N^{\prime}+\rho
N)\,\partial_{\rho}+\frac{M}{\rho^{2}}\partial^{2}_{\psi}$
$\displaystyle{}-(G+r^{2}H)\Bigl{(}\partial^{2}_{r}+\frac{2}{r}\partial_{r}\Bigr{)}-(G^{\prime}+r^{2}H^{\prime})\partial_{r}-\frac{G}{r^{2}}\Lambda(\theta,\varphi).$

The change from one coordinate system to another is achieved in a covariant
manner. The operator (4) may be written as a sum of two commutative operators,

$\Delta_{3,3}=\Delta^{(1)}_{3,3}+\Delta^{(2)}_{3,3},$

where

$\displaystyle{}\Delta^{(1)}_{3,3}=(M+{\rho}^{2}N)\Bigl{(}\partial^{2}_{\rho}+\frac{1}{\rho}\partial_{\rho}\Bigr{)}$
$\displaystyle{}\hskip 28.45274pt\hskip
28.45274pt+\Bigl{(}M^{\prime}+\rho^{2}N^{\prime}+\rho
N\Bigr{)}\partial_{\rho}+\frac{M}{\rho^{2}}\partial^{2}_{\psi},$ (5)
$\displaystyle{}\Delta^{(2)}_{3,3}=F(r)\partial^{2}_{t}-(G+r^{2}H)\Bigl{(}\partial^{2}_{r}+\frac{2}{r}\partial_{r}\Bigr{)}$
$\displaystyle{}\hskip 28.45274pt\hskip
28.45274pt-\Bigl{(}G^{\prime}+r^{2}\,H^{\prime}\Bigr{)}\partial_{r}-\frac{G}{r^{2}}\Lambda(\theta,\varphi).$
(6)

The range of definition $D(\Delta^{(1)}_{3,3})$ of the operator (5) consists
of doubly differentiable, quadratically integrable functions of the parameters
$\rho,\ \psi$ relative to the measure $d\mu_{1}=\rho\,d\rho\,d\psi$ which
satisfy the condition

$\int_{0}^{\infty}|g|^{2}\rho^{-3}d\rho<\infty.$ (7)

The condition (7) is sufficient to ensure that

${\Delta}^{(1)}_{3,3}\,g\in L^{2}(R_{2},\mu_{1})\qquad\mbox{for any}\qquad
g\in D(\Delta^{(1)}_{3,3}).$

Taking into account that the operator $\Delta^{(1)}_{3,3}$ in the form (5) is
defined only for $\rho>\varepsilon_{1}$, let us confine ourselves to
considering the action of the operator $\Delta^{(1)}_{3,3}$ upon functions
belonging to $D(\Delta^{(1)}_{3,3})$ and defined in the domain

$R_{2}\setminus O_{1},\quad\mbox{where }\quad
O_{1}=\\{\rho:\rho<\varepsilon_{1}\\}\,.$

The range of definition $D(\Delta^{(1)}_{3,3})$ of the operator (6) consists
of twice differentiable and square-integrable functions of the parameters
$r,\theta,\varphi,t$ relative to the measure
$d\mu_{2}=r^{2}\sin\theta\,dr\,d\theta\,d\varphi\,dt$, which satisfy the
condition

$\int_{0}^{\infty}|g|^{2}\,r^{-2}dr<\infty.$ (8)

Integration in the parameter $t$ is done in an arbitrary compact. The
condition (8) is sufficient for the operator $\Delta^{(2)}_{3,3}$ to be
essentially self-adjoint. Since the operator $\Delta^{(2)}_{3,3}$ in the form
(6) is only defined at $r>\varepsilon_{2}$, let us restrict ourselves to
considering its action upon the functions constituting $D(\Delta^{(2)}_{3,3})$
and defined in the domain

$R_{3,1}\setminus O_{2}\,,\quad\mbox{where}\;\ \
O_{2}=\\{r:r<\varepsilon_{2}\\}\,.$

##  4\. Eigenvalues of the operator $\bf{\Delta^{(1)}_{3,3}}$

With Eq. (2), one can represent the operator (5) in the form

$\displaystyle{}\Delta^{(1)}_{3,3}=\frac{\rho^{2}}{\rho^{2}+\beta^{2}}\,\partial^{2}_{\rho}+\Bigl{(}\frac{2\,\rho\,\beta^{2}}{(\rho^{2}+\beta^{2})^{2}}+\frac{\rho^{2}+\beta^{2}}{\rho^{3}}\Bigr{)}\partial_{\rho}$
$\displaystyle{}\hskip
72.26999pt+\frac{\rho^{2}+\beta^{2}}{\rho^{4}}\partial^{2}_{\psi}\;.$ (9)

We will only be interested in positive eigenvalues of the operator (9). It can
be noted that the essential spectrum of the formally self-adjoint operator (9)
represents a negative semiaxis; therefore, all non-negative eigenvalues belong
to a discrete spectrum. Accordingly, the problem of finding the eigenvalues
reduces to that of solving the differential equation

$\Delta^{(1)}_{3,3}g={\lambda}^{2}g,\hskip 28.45274ptg\in
D(\Delta^{(1)}_{3,3}).$ (10)

We will seek the function $g$ in (10) in the form

$g(\rho,\psi)={\,\rm e}^{im\psi}g(\rho),\quad m=0,\
\pm{{\textstyle\frac{1}{2}}},\ \pm 1,\ldots.$ (11)

Substituting (11) into (10) and neglecting the terms containing the first
derivative with coefficient $\beta/\rho$ in powers 2 and higher yields

$\,\Bigl{[}\frac{{\rho}^{2}}{{\rho}^{2}+{\beta}^{2}}\Bigl{(}\partial^{2}_{\rho}+\frac{1}{\rho}\partial_{\rho}\Bigr{)}-\frac{\rho^{2}+\beta^{2}}{\rho^{4}}m^{2}\Bigr{]}g(\rho)={\lambda}^{2}g(\rho).$
(12)

Let us introduce the new variable $x=\beta^{2}/\rho^{2}$,
$x\in(0,\beta^{2}/\varepsilon_{1}^{2})$, then the relation (12) assumes the
form

$\displaystyle{}\,\biggl{[}\frac{4x^{3}}{{\beta^{2}}(x+1)}\Bigl{(}\partial^{2}_{x}+\frac{1}{x}\partial_{x}\Bigr{)}-\frac{x(x+1)}{{\beta}^{2}}m^{2}\biggr{]}g(x)=\lambda^{2}g(x),$

and the function $g$ should be square-integrable in the region
$(0,\beta^{2}/\varepsilon_{1}^{2})$ over the measure
$d\mu=[\beta^{2}/(2x^{2})]dx$, or, taking into account the condition (7), we
arrive at the requirement
$\displaystyle\int_{0}^{\beta^{2}\varepsilon_{1}^{-2}}|g|^{2}\,dx<\infty$. For
$x>0$, we can write down Eq. (13) in the form

$\displaystyle\biggl{(}\partial^{2}_{x}+\frac{1}{x}\partial_{x}-\frac{m^{2}}{4}-\frac{m^{2}}{2x}-\frac{m^{2}+{\beta}^{2}{\lambda}^{2}}{4x^{2}}\qquad$
$\displaystyle{}-\frac{{\lambda}^{2}{\beta}^{2}}{4x^{3}}\biggr{)}g(x)=0.$ (14)

We will seek the function $g(x)$ in (14) in the form $g=x^{-1/2}v$, then for
$v$ we get the equation

$\,v^{\prime\prime}-\frac{m^{2}}{4}v-\frac{m^{2}}{2}\frac{v}{x}-\frac{m^{2}+\beta^{2}\lambda^{2}-1}{4x^{2}}v-\frac{\beta^{2}\lambda^{2}}{4x^{3}}v=0.$
(15)

##  5\. Finding a partial spectrum of $\bf{\Delta^{(1)}_{3,3}}$

Let as set $\lambda=0$ in (15) and find the eigenfunctions and allowed values
of the parameter $m$ which correspond to the eigenvalue $\lambda=0$ of the
operator $\Delta^{(1)}_{3,3}$. Consider the equation

$v^{\prime\prime}-\frac{m^{2}}{4}v-\frac{m^{2}}{2}\frac{v}{x}+\frac{1-m^{2}}{4x^{2}}v=0.$
(16)

We will seek its solution in the form

$v={\,\rm e}^{-mx/2}\sum_{k=-1}^{\infty}C_{k}x^{r+1+k}\;.$ (17)

The lower limit of the sum in (17) is chosen on the basis of the requirement
of quadratic integrability of the function $v\,x^{-1/2}$ near zero.
Substituting (17) to (16) and denoting
$y=\sum\limits_{k=-1}^{\infty}C_{k}x^{r+1+k}$, we arrive at the relation

$y^{\prime\prime}-my^{\prime}-\frac{m^{2}}{2x}y+\frac{1-m^{2}}{4x^{2}}y=0.$
(18)

From (18) we obtain an infinite set of recurrent relations:

$\displaystyle{}\Bigl{[}(r+k)(r+k+1)+{\textstyle\frac{1}{4}}(1-m^{2})\Bigr{]}C_{k}$
$\displaystyle{}\qquad-m\Bigl{(}r+k+\frac{m}{2}\Bigr{)}C_{k-1}=0,\qquad
k=0,1,2,...\;,$

with a condition on $r$ in the form

$r=-\frac{B}{2}+\frac{m}{2}-\frac{1}{3},\quad\mbox{where}\quad
B=\frac{1}{3}\;.$

Hence,

$\displaystyle
C_{k}=\frac{m\Bigl{(}m-\frac{B}{2}+k-\frac{1}{3}\Bigr{)}}{k\;(m+k)}C_{k-1}\;,\quad
k=0,1,...\;.$ (19)

From (19) it follows that the sum
$\sum\limits_{k=-1}^{\infty}C_{k+1}x^{r+1+k}$ should contain a finite number
of terms to assure that the function $v$ be square integrable. If $m\neq 0$,
then at some $m,k,B$ the equality

$k-\frac{1}{3}+m-\frac{B}{2}=0$ (20)

should hold. The parameters $\lambda\beta,\,m,\,k-\frac{1}{3},\,B$ admit the
following physical interpretation: let $Q$ be the quark charge, $B$ the baryon
charge, $I$ the isotopic spin, $I_{3}$ a projection of the isotopic spin, $S$
the particle strangeness, then

$S=-2\lambda\beta,\quad Q=k-{\textstyle\frac{1}{3}},\quad I=|m|,\ \
I_{3}=-|m|,...,|m|.$

It can be noted that the idea to consider the isospin as a spin of a particle
in the three-dimensional time-space was first advanced in [3]. From (20) we
obtain the following relation:

$S=-2\,I_{3}-B+2\,Q$ (21)

for the case $S=0$. The relation (21) is nothing else but the Nishijima
formula for the baryon supermultiplet. If $S=0$ and $m=1/2$, then
$I_{3}=\pm{{\textstyle\frac{1}{2}}}$, $Q=-\frac{1}{3}\,,\frac{2}{3}\,,$ which
corresponds to the quark doublet $(u,d)$.

Let us consider Eq. (15) with $m=0$, then we obtain the following relation:

$v^{\prime\prime}+\frac{1-\lambda^{2}\beta^{2}}{4x^{2}}\,v-\frac{\lambda^{2}\beta^{2}}{4x^{3}}\,v=0.$
(22)

We will seek its solution in the form

$v={\,\rm e}^{-\lambda\beta/\sqrt{x}}\,y.$ (23)

Substituting (23) into (22), we come to the following set of equations for
$y$:

$\displaystyle
y^{\prime\prime}+\frac{1-\lambda^{2}\beta^{2}}{4\;x^{2}}y=0,\hskip
28.45274pty^{\prime}-\frac{3}{4}\;\frac{y}{x}=0.$ (24)

The system (24) has the solution $y=cx^{3/4}$ only if
$\lambda\beta={{\textstyle\frac{1}{2}}}$. This means that the Nishijima
formula is true in the case
$\lambda\beta=\frac{1}{2}\>,\;I_{3}=0\>,\;B=\frac{1}{3}\>,\;Q=-\frac{1}{3}\>,$
which corresponds to the quark $s$.

Thus we have found two eigenvalues $0$ and $1/(2\beta)$ of the operator
$\Delta^{(1)}_{3,3}$, which correspond to the quark triplet $(u,\ d,\ s)$. It
can already be seen at this stage of the investigation that the $s$ quark mass
differs from the masses of $u$ and $d$ quarks.

##  6\. Finding a partial spectrum of $\bf{\Delta^{(2)}_{3,3}}$

With Eq. (2), one can represent the operator (6) in the form

$\displaystyle\Delta^{(2)}_{3,3}$ $\displaystyle=$ $\displaystyle
f_{4}\partial^{2}_{t}-f_{1}r^{4}\partial^{2}_{r}-\frac{f_{2}}{r^{4}}\Lambda(\theta,\varphi)$
(25)
$\displaystyle{}\quad-\Bigl{(}\frac{2\,f_{2}}{r^{3}}+4\,f_{1}r^{3}+f^{\prime}_{1}\,r^{4}\Bigr{)}\partial_{r},$

where $f_{1}=G/r^{4}+H/r^{2},\ f_{2}=r^{2}G,\ f_{4}=F$.

Accordingly, the problem of finding the eigenvalues reduces to that of solving
the differential equation

$\Delta^{(2)}_{3,3}\;g=\Delta^{2}\,g\;,$ (26)

where $g\in D(\Delta^{(2)}_{3,3})$. We will seek the function $g$ in (26) in
the form

$g(t,r,\theta,\varphi)=G(t)R_{l,n}(r)Y_{l}(\theta,\varphi)$ (27)

where $Y_{l}$ is an eigenfunction of the operator $\Lambda(\theta,\varphi)$,
corresponding to the eigenvalue $-l\,(l+1)$, so that

$\Lambda(\theta,\varphi)\,Y_{l}(\theta,\varphi)=-l(l+1)Y_{l}(\theta,\varphi)\,;$
(28)

$G(t)$ is an eigenfunction of the formally self-adjoint operator
$-\partial^{2}_{t}$, which has only an essential spectrum in the domain
$(0,\infty)$, so that

$\partial^{2}_{t}\,G(t)=\alpha^{2}\,G(t).$ (29)

Taking into account the relations (25), (27), (28), (29), one can represent
Eq. (26) in the form

$\displaystyle\Bigl{[}f_{4}\alpha^{2}-f_{1}r^{4}\partial^{2}_{r}-\Bigl{(}\frac{2\,f_{2}}{r^{3}}+4\,f_{1}r^{3}+f_{1}^{\prime}r^{4}\Bigl{)}\partial_{r}\quad$
$\displaystyle{}+\frac{f_{2}}{r^{4}}l\,(l+1)\Bigl{]}R_{l,n}=\Delta^{2}R_{l,n}.$
(30)

The essential spectrum of the formally self-adjoint operator in the left-hand
side of Eq. (30) is represented by the range $(\alpha^{2}\,,\infty)$,
therefore all non-negative eigenvalues of the operator $\Delta^{(2)}_{3,3}$
restricted above by the value $\alpha^{2}$ are discrete. From the condition
$f_{1}\,r^{4}\neq 0$ for $r\in(\varepsilon_{2},\infty)$ it follows:

$\displaystyle\biggl{[}\partial^{2}_{r}+\Bigl{(}\frac{4}{r}+\frac{f_{1}^{\prime}}{f_{1}}+2\frac{f_{2}}{r^{7}f_{1}}\Bigr{)}\partial_{r}-\frac{f_{4}}{f_{1}r^{4}}\alpha^{2}\qquad\
\ $
$\displaystyle{}-\frac{f_{2}}{f_{1}r^{8}}l(l+1)+\frac{\Delta^{2}}{f_{1}r^{4}}\biggr{]}\,R_{l,n}=0.$
(31)

We will seek its solution in the form

$R_{l,n}=\exp\biggl{[}-\frac{1}{2}\int\Bigl{(}\frac{4}{r}+\frac{f_{1}^{\prime}}{f_{1}}+\frac{2\,f_{2}}{r^{7}\,f_{1}}\Bigr{)}\,dr\biggr{]}v_{l,n}.$
(32)

After substitution of (32), Eq. (31) may be rewritten in the form

$v_{l,n}^{\prime\prime}-\Bigl{(}{\textstyle\frac{1}{4}}P^{2}+{{\textstyle\frac{1}{2}}}P^{\prime}+Q\Bigr{)}v_{l,n}=0,$
(33)

where [4]

$P=\frac{4}{r}{+}\frac{f_{1}^{\prime}}{f_{1}}{+}\frac{2\,f_{2}}{r^{7}f_{1}};\
Q=\frac{f_{4}}{f_{1}\,r^{4}}\alpha^{2}+\frac{f_{2}}{f_{1}\,r^{8}}l(l{+}1)-\frac{\Delta^{2}}{f_{1}\,r^{4}}.$

Taking into account that

$\displaystyle{}\frac{1}{f_{1}r^{4}}\sim
1-\frac{a}{r}+o\Bigl{(}\frac{a^{2}}{r^{2}}\Bigr{)},\
\frac{f_{4}}{f_{1}r^{4}}\sim
1-\frac{2a}{r}+\frac{a^{2}}{r^{2}}+o\Bigl{(}\frac{a^{2}}{r^{2}}\Bigr{)},$
$\displaystyle{}\frac{f_{2}}{f_{1}r^{6}}\sim
1-\frac{a}{r}+o\Bigl{(}\frac{a^{2}}{r^{2}}\Bigr{)},\quad\frac{1}{4}P^{2}+\frac{1}{2}P^{\prime}\sim
o\Bigl{(}\frac{a^{2}}{r^{2}}\Bigr{)}$

and neglecting the terms containing $\frac{a}{r}$ in powers 3 and higher
yields

$\displaystyle
v_{l,n}^{\prime\prime}-(\alpha^{2}-\Delta^{2})v_{l,n}+\frac{a}{r}(2\,\alpha^{2}-\Delta^{2})v_{l,n}\qquad$
$\displaystyle{}-\frac{a^{2}\alpha^{2}+l(l+1)}{r^{2}}\,v_{l,n}=0.$ (34)

We will seek the solution of Eq. (34) in the form

$v=\exp[-(\alpha^{2}-\Delta^{2})^{1/2}r]y_{l,n},$ (35)

where $y_{l,n}=\sum\limits_{k=0}^{\infty}C_{k}r^{\nu+k}$. Substituting (35)
into (34), we come to the following relation for $y_{l,n}$:

$\displaystyle
y_{l,n}^{\prime\prime}-2\,(\alpha^{2}-\Delta^{2})^{1/2}y_{l,n}^{\prime}+(2\alpha^{2}-\Delta^{2})\frac{a}{r}\,y_{l,n}$
$\displaystyle{}-\frac{l(l+1)+a^{2}\alpha^{2}}{r^{2}}\,y_{l,n}=0\;.$ (36)

Eq. (36) gives an infinite set of recurrent relations

$\displaystyle{}[(\nu+k+1)(\nu+k)-l(l+1)-a^{2}\alpha^{2}\,)]\,C_{k+1}$
$\displaystyle{}\quad-[2(\alpha^{2}-\Delta^{2})^{1/2}(\nu+k)-(2\alpha^{2}-\Delta^{2})a]C_{k}=0,$

where $k=0,1,2,\ldots$ and

$\nu={{\textstyle\frac{1}{2}}}\pm{{\textstyle\frac{1}{2}}}\sqrt{1+4\,l(l+1)+4\,a^{2}\alpha^{2}}.$
(37)

Hence,

$C_{k+1}=\frac{2(\alpha^{2}{-}\Delta^{2})^{1/2}(\nu{+}k)-(2\alpha^{2}-\Delta^{2})a}{(\nu+k+1)(\nu+k)-l(l+1)-a^{2}\alpha^{2}}C_{k}.$
(38)

From (38) it follows that the sum $\sum\limits_{k=0}^{\infty}C_{k}\,r^{\nu+k}$
should contain a finite number of terms to assure that the function $v_{l,n}$
be square-integrable in the region $(\varepsilon_{2},\infty)$. Thus at some
$k=n$ the equality

$2(\alpha^{2}-\Delta^{2})^{1/2}(\nu+n)-2\Bigl{(}\alpha^{2}-\frac{\Delta^{2}}{2}\Bigr{)}a=0.$
(39)

should hold, and for all $k<n$ the inequality

$(\nu+k+1)(\nu+k)-l(l+1)-a^{2}\alpha^{2}\neq 0$

is valid. Solving Eq. (39) for $\Delta^{2}$, we obtain

$\displaystyle{}\Delta_{1,2}^{2}=2\biggl{[}\alpha^{2}-\Bigl{(}\frac{\nu+n}{a}\Bigr{)}^{2}\biggr{]}\pm
2\biggl{[}\alpha^{2}-\Bigr{(}\frac{\nu+n}{a}\Bigr{)}^{2}\biggr{]}$
$\displaystyle{}\hskip
72.26999pt\times\biggl{[}1-\frac{\alpha^{2}}{\alpha^{2}-[(\nu+n)/a]^{2}}\biggr{]}^{1/2}.$
(40)

From (40) it follows

$\Bigl{(}\frac{\nu+n}{a}\Bigr{)}^{2}>\alpha^{2}$ (41)

because $1-{\displaystyle\frac{\alpha^{2}}{\alpha^{2}-[(\nu+n)/a]^{2}}}\geq
0$. Hence from (37), (40) and (41) we obtain for $\alpha^{2}$ and $\Delta^{2}$
the following relations:

$\alpha^{2}=\frac{\nu(\nu-1)-l(l+1)}{a^{2}},\quad\Delta^{2}=\frac{2}{a^{2}}A\biggl{[}\frac{|\nu+n|}{A^{1/2}}-1\biggr{]},$

where $A=(\nu+n)^{2}+l(l+1)-\nu(\nu-1)$, $l$ is the spin moment of a particle,
while the physical meaning of the quantum parameters $\nu$ and $n$ remains
obscure.

##  7\. Partial spectrum of $\bf{\Delta_{3,3}}$ and the mass spectrum of the
quark triplet

The obtained partial spectra of the operators $\Delta_{3,3}^{(1)}$ and
$\Delta_{3,3}^{(2)}$ lead to a partial spectrum of the operator
$\Delta_{3,3}$:

$\Delta_{3,3}g=(\lambda^{2}+\Delta^{2})g,$

or in an expanded form

$\displaystyle{}\Delta_{3,3}\,g=\biggl{[}\Bigl{(}\frac{2Q-B-2I_{3}}{\beta}\Bigr{)}^{2}+\frac{2}{a^{2}}A\Bigl{(}\frac{\nu+n}{A^{1/2}}-1\Bigr{)}\biggr{]}g.$

If $Q=-\frac{1}{3},\ \frac{2}{3},\ B=\frac{1}{3},\ I_{3}=-\frac{1}{2},\
\frac{1}{2},\ 0,\ l=\frac{1}{2}$, then this set of quantum characteristics
corresponds to the quark triplet $d,\ u,\ s$. From (42), for the mass doublet
of the quarks $(d,u)$ and the quark $s$ we get the following relations:

$\displaystyle{}m_{d,u}=\biggl{\\{}\frac{2}{a^{2}}\biggl{[}(\nu+n)^{2}-\nu(n-1)+\frac{3}{4}\biggr{]}$
$\displaystyle{}\hskip
28.45274pt\times\biggl{[}\Bigl{(}1-\frac{\nu(\nu-1)-3/4}{(\nu+n)^{2}}\Bigr{)}^{-1/2}-1\biggr{]}\biggr{\\}}^{1/2},$
(43) $\displaystyle{}m_{s}=(\beta^{-2}+m_{d,u}^{2})^{1/2}.$ (44)

We note that the relations (43) and (44) are given in provisional units of
measurement $h=1$, $c=1$, $e=1$. Knowing the mass spectrum of the quark
triplet, we can readily find the mass spectrum of, e.g., the baryon decuplet,
ignoring the spin-spin and spin-orbital interactions. The result
satisfactorily describes the nature of the supermultiplet spectrum.

##  8\. Conclusion

The very attempt to relate the geometric properties of the space-time
continuum to the properties of elementary particles, in particular, to the
quark mass spectrum appears, judging from the results that have been obtained,
to be promising. Apparently, the first theoretical substantiation of the
Nishijima formula for the quark triplet $(u,\ d,\ s)$ on the basis of the
geometrical properties of space and time is not coincidental.

The main achievement of the suggested work is apparently the construction of
an unlimited self-adjoined operator, possessing a discrete spectrum adequately
describing the quark triplet mass spectrum.

## References

  * [1] N. Popov, Grav. & Cosmol. 4, 2 (14), 151 (1998).
  * [2] K. Schwarzschild, Sitzungsber. d. Berlin Akad., 1916, S. 189.
  * [3] N. Popov, in: “Quantum Field Theory and Gravity”, Tomsk, 1997, pp. 229–233.
  * [4] V.V. Stepanov, “Differential equations”, Fizmatgiz, Moscow, 1958, p. 243 (in Russian).
  * [5] F.E. Close, “An Introduction to Quarks and Partons”, Mir, Moscow, 1982, p. 49 (Russian translation).


# Combining Latent Space and Structured Kernels for Bayesian Optimization over
Combinatorial Spaces

Aryan Deshwal
School of EECS
Washington State University
<EMAIL_ADDRESS>
&Janardhan Rao Doppa
School of EECS
Washington State University
<EMAIL_ADDRESS>

###### Abstract

We consider the problem of optimizing combinatorial spaces (e.g., sequences,
trees, and graphs) using expensive black-box function evaluations. For
example, optimizing molecules for drug design using physical lab experiments.
Bayesian optimization (BO) is an efficient framework for solving such problems
by intelligently selecting the inputs with high utility guided by a learned
surrogate model. A recent BO approach for combinatorial spaces is through a
reduction to BO over continuous spaces by learning a latent representation of
structures using deep generative models (DGMs). The selected input from the
continuous space is decoded into a discrete structure for performing function
evaluation. However, the surrogate model over the latent space only uses the
information learned by the DGM, which may not have the desired inductive bias
to approximate the target black-box function. To overcome this drawback, this
paper proposes a principled approach referred as LADDER. The key idea is to
define a novel structure-coupled kernel that explicitly integrates the
structural information from decoded structures with the learned latent space
representation for better surrogate modeling. Our experiments on real-world
benchmarks show that LADDER significantly improves over the BO over latent
space method, and performs better or similar to state-of-the-art methods.

##  1 Introduction

A huge range of science and engineering applications involve optimizing
combinatorial spaces (e.g., sequences, trees, graphs) using expensive black-
box function evaluations [18, 70, 17]. For example, in drug design
application, each candidate structure is a molecule and evaluation involves
performing an expensive physical lab experiment. Bayesian optimization (BO)
[59, 20] is an effective framework for optimizing expensive black-box
functions and has shown great success in practice [63, 74, 21, 6, 5]. The key
idea is to learn a cheap-to-evaluate surrogate statistical model, e.g.,
Gaussian process (GP), from past function evaluations and employ it to select
inputs with high-utility for evaluation. BO for combinatorial spaces is a
relatively less-studied problem with many challenges in the small-data setting
(number of function evaluations is small).

A recent approach to solve some of these challenges is through a reduction to
BO over continuous spaces, which we refer as BO over latent space [26, 68].
This method relies on two ideas. First, we learn a latent space representation
from a database of unsupervised structures (i.e., function evaluations are not
available) using a encoder-decoder style deep generative model (DGM) [37, 33].
Second, we build a surrogate model over this latent space to perform BO. Each
selected input from the latent space is decoded into a structured object for
performing function evaluation. BO over latent space has shown good success
when the number of function evaluations is large [26, 68, 19, 34]. However, we
conjecture that this approach may not be effective in the small-data settings
for the following reasons. 1) The surrogate model over the latent space only
uses the information learned by the DGM, which may not have the desired
inductive bias to approximate the target black-box function. 2) The learned
surrogate model may not generalize well beyond the training instances from the
latent space. Indeed, our experiments on real-world problems demonstrate the
ineffectiveness of this Naïve surrogate model over the latent space.

In this paper, we propose a novel approach referred as LADDER to overcome the
above drawbacks for the small-data setting. We name it LADDER because it acts
as a ladder in connecting the rich structural information of structures in the
combinatorial space with their corresponding latent space representations.
Intuitively, it improve surrogate modeling by combining the best of both
representations. We provide a principled Gaussian process based method to
integrate the latent space representation with the structural information from
decoded structures using a novel structure-coupled kernel. The key insight is
to extend a kernel over the latent space (with its hyper-parameters estimated
on the evaluated points) to non-evaluated points in the space by utilizing the
features of structured kernels defined over combinatorial spaces (e.g., string
kernels and graph kernels). LADDER has multiple advantages. First, we can
leverage a large body of research on kernels over structured data. Second,
allows the use of deep generative models (DGMs) to learn latent space as a
plug-and-play technology. This means advances in DGMs will directly improve
the effectiveness of LADDER. Our experiments on real-world benchmarks show
that LADDER performs better or similar to state-of-the-art methods, and
significantly better than the Naïve latent space BO approach in our problem
setting. We also empirically demonstrate that superiority of LADDER’s
performance is due to better surrogate model resulting from the proposed
method to combine representations.

Contributions. The key contribution of this paper is the development and
evaluation of the LADDER approach to perform BO over combinatorial spaces in
the small-data setting. Specific list includes:

  * •

Identifying the key reasons for the ineffectiveness of the Naïve latent space
BO method in the small-data setting and providing empirical evidence on real-
world problems.

  * •

Development of a principled Gaussian process approach for improved surrogate
modeling by combining the structural information from decoded structures with
the learned latent space representation using a novel structure-coupled
kernel.

  * •

Experiments on real-world benchmarks to show the efficacy of LADDER over prior
methods in our problem setting. The code and data are available on the GitHub
repository link https://github.com/aryandeshwal/LADDER.

##  2 Problem Setup and Background

Let $\mathcal{X}$ be a space of combinatorial structures (e.g., sequences,
trees, and graphs). We assume the availability of a black-box objective
function $f:\mathcal{X}\mapsto\mathbb{R}$ defined over the combinatorial space
$\mathcal{X}$. Evaluating each candidate structure $\mathbf{x}\in\mathcal{X}$
using function $f$ (also called an experiment) is expensive in terms of the
resources consumed and produces an output $y$ = $f(\mathbf{x})$. For example,
in the drug design application, each $\mathbf{x}\in\mathcal{X}$ is a molecule,
and $f(\mathbf{x})$ corresponds to running a physical lab experiment. Our
overall goal is to find a structure $\mathbf{x}\in\mathcal{X}$ that
approximately optimizes $f$ by minimizing the number of experiments and
observing their outcomes.

We are also provided with a database of unsupervised structures
$\mathcal{X}_{u}\subset\mathcal{X}$. Unsupervised means that we do not know
the function evaluations $f(x)$ for structures in $\mathcal{X}_{u}$. This
assumption is satisfied by many scientific applications including chemical
design and material design. We assume the availability of a latent space
$\mathcal{Z}$ learned from unsupervised structures $\mathcal{X}_{u}$ using a
encoder-decoder style deep generative model, e.g., variational autoencoders
(VAEs) for structured data such as junction tree VAE [33] and grammer VAE
[37]. Formally, the encoder denoted by $\Upsilon$ embeds a given combinatorial
structure $\mathbf{x}\in\mathcal{X}$ into a point in the latent space
$\mathbf{z}\in\mathbb{R}^{d}$ = $\Upsilon(x)$ where $d$ is the number of
dimensions of the latent space $\mathcal{Z}$ and the decoder denoted by $\Phi$
converts a given point from latent space $\mathbf{z^{\prime}}\in\mathcal{Z}$
into a structured object $\mathbf{x^{\prime}}\in\mathcal{X}$ =
$\Phi(\mathbf{z^{\prime}})$. Encoder $\Upsilon$ and decoder $\Phi$ are
typically realized by neural networks.

Bayesian optimization. To solve optimization problems using black-box
evaluations of expensive objective functions, Bayesian optimization (BO) is an
efficient framework. BO algorithms select inputs with high utility guided by a
learned surrogate statistical model from past observations. The three key
elements of BO are as follows: 1) Surrogate model of the black-box function
$f(\mathbf{x})$, e.g., Gaussian process; 2) Acquisition function to score the
utility of evaluating candidate inputs using the surrogate model, e.g.,
expected improvement; and 3) Acquisition function optimizer to select the
input with maximum utility. In each BO iteration, we select one input for
function evaluation and update the statistical model based on the new training
example. BO has shown great success for continuous spaces, but BO over
combinatorial spaces is a relatively less-studied problem space.

Naïve latent space BO. This approach reduces the problem of BO over
combinatorial space $\mathcal{X}$ to BO over the latent space $\mathcal{Z}$,
which is continuous. We construct surrogate model $\mathcal{M}_{\mathcal{Z}}$
over the latent space $\mathcal{Z}$ using training points selected from
$\mathcal{Z}$ for evaluation. Each selected input $\mathbf{z}\in\mathcal{Z}$
is decoded into a structured object using the decoder $\Phi$. We perform
function evaluation using the decoded structure $\Phi(\mathbf{z})$ and the
surrogate model $\mathcal{M}_{\mathcal{Z}}$ is updated using the new training
example ($\mathbf{z}$, $f(\Phi(\mathbf{z}))$). This reduction approach allows
us to leverage prior research on BO for continuous spaces and has shown
success when the the number of function evaluations is large [26, 68, 19, 34].
In this paper, we study the small data setting (number of function evaluations
is small) by addressing the drawbacks of this Naïve latent space BO approach
in a principled manner.

##  3 LADDER: Latent Space BO guided by Decoded Structures

In this section, we first discuss the challenges with the Naïve latent space
BO approach. Next, we describe our proposed LADDER approach with a focus on
the novel surrogate model by combining kernels over structured data and latent
space representation, which is our key technical contribution.

###  3.1 Challenges with the Naïve latent space BO approach

As mentioned above, the Naïve latent space BO approach builds a surrogate
model over the latent space using kernels for continuous spaces (e.g., Matern
or Squared Exponential kernel) and performs acquisition function optimization
in the latent space using optimizers for continuous spaces (e.g., gradient-
based methods) to select point $\mathbf{z}\in\mathcal{Z}$ for evaluation.
However, the expensive objective function $f(\mathbf{x})$ is defined over the
space of combinatorial structures $\mathcal{X}$ and not the latent space
$\mathcal{Z}$. Therefore, we need to decode this point $\mathbf{z}$ using the
decoder $\Phi$ to get the corresponding combinatorial structure
$\mathbf{x}$=$\Phi(z)$ for function evaluation $f(\mathbf{x})$. All the
existing work on BO over latent space do not account for this decoding
process. As a consequence, we need to deal with two inter-related challenges,
which are especially significant for small-data settings.

  * •

Challenge #1: The kernel over the latent space only uses the information
learned by the deep generative model. It doesn’t explicitly incorporate
information about the decoded structure. This means the corresponding Gaussian
process surrogate model may not have the desired inductive bias to approximate
the black-box objective function. Therefore, we are not able to leverage this
potentially useful inductive bias and rich structural information available in
decoded structures.

  * •

Challenge #2: The surrogate statistical model itself might not generalize well
beyond the training examples from the latent space (set of points in the
latent space and their corresponding function evaluations). This is especially
true in the small-data setting for latent spaces learned using DGMs in real-
world scientific applications, where the number of dimensions of latent space
can be large when compared to the standard BO setup.

Indeed, we provide empirical evidence to demonstrate these challenges and our
key hypothesis in Figure 2. We show that by incorporating the rich structural
information from the decoded output, we can address both these challenges to
improve the overall BO performance.

Figure 1: High-level conceptual illustration of our proposed LADDER approach,
which acts as a “ladder” in connecting the rich structural information of each
structure in the combinatorial space with its corresponding latent space
representation. Structure-coupled kernel is the key element that enables this
connection to build an effective Gaussian process based surrogate model.

###  3.2 Overview of LADDER algorithm and key advantages

LADDER is an instantiation of the latent space BO framework that employs a
novel surrogate statistical model to address the two challenges with the Naïve
method. The surrogate model is a Gaussian process that combines the
complementary strengths of the latent space representation with the rich
structural information from decoded outputs using structured kernels (e.g.,
string kernels and graph kernels). The key idea is to define a structure-
coupled kernel that extends the continuous kernel on the evaluated points in
the latent space to unknown points using the rich information from structured
kernels. We employ expected improvement (EI) as the acquisition function. For
optimizing the acquisition function to select high utility inputs from the
latent space, we employ evolutionary search due to its recent successes [39]
including policy search in high-dimensional spaces [55].

Figure 1 shows a high-level illustration of LADDER and Algorithm 1 provides
the complete pseudo-code. We use a small set of initial training data in the
form of points in the latent space and their corresponding function
evaluations to bootstrap the GP based surrogate model using the structure-
coupled kernel. In each iteration $t$, we optimize the acquisition function to
select a point $\mathbf{z}_{t}$ from the latent space $\mathcal{Z}$ for
evaluation. The corresponding decoded structure
$\mathbf{x}_{t}$=$\Phi(\mathbf{z}_{t})$ is evaluated to measure the outcome
$f(\mathbf{x}_{t})$. The GP model with structure-coupled kernel is updated
using the new 3-tuple training example
$\\{\mathbf{z}_{t},\mathbf{x}_{t},f(\mathbf{x}_{t})\\}$. We repeat these
sequence of steps until covergence or maximum query budget and then return the
best uncovered combinatorial structure $\mathbf{\hat{x}}\in\mathcal{X}$ as the
output.

Advantages of LADDER. Some of the key advantages of our proposed approach are
listed below.

  * •

We are allowed to employ any existing trained deep generative model for
structured data in a plug-and-play manner with LADDER. Therefore, any advances
in the latent-space generative modeling technology will directly improve the
overall BO performance.

  * •

LADDER is a generic approach that is applicable to any combinatorial space of
structures (e.g., sequences, trees, graphs, sets, and permutations). This
method just requires an appropriate structured kernel over the given
combinatorial space. Therefore, we can leverage a large body of research on
generic kernels over structured data (e.g., string kernels and graph kernels)
and hand-designed kernels based on domain knowledge for specific applications.
For example, in our experiments, we employ sub-sequence string kernel
(generic) and fingerprint kernel (domain-specific) to concretely instantiate
the LADDER approach for strings and molecules respectively to demonstrate its
flexibility.

  * •

Combines the complementary strengths of latent space representations and
structured kernels in a principled manner to create highly-effective surrogate
statistical models.

Algorithm 1 Latent Space Bayesian Optimization guided by Decoded Structures
(LADDER)

1: Input: Objective function $f(\mathbf{x})$, Encoder ($\Upsilon$) - Decoder
($\Phi$) style model for latent space $\mathcal{Z}$, Kernel for latent space
$l(\mathbf{z_{i}}\in\mathcal{Z},\mathbf{z_{j}}\in\mathcal{Z})$, Kernel for
combinatorial space
$k(\mathbf{x_{i}}\in\mathcal{X},\mathbf{x_{j}}\in\mathcal{X})$

2: Initialize dataset $\mathcal{D}_{0}$ by evaluating few random points:
$\mathcal{D}_{0}\leftarrow\\{\mathbf{Z}_{0},\mathbf{X}_{0},f(\mathbf{X}_{0})\\}$;
$t\leftarrow 0$ // slight abuse of notation here since $\mathbf{Z}_{0}$ is the
set of initial points from latent space $\mathcal{Z}$ and $\mathbf{X}_{0}$ is
the set of corresponding decoded structures from $\mathcal{X}$ with function
evaluations $f(\mathbf{X}_{0})$

3: repeat

4: Learn Gaussian process model on the dataset $\mathcal{D}_{t}$ with the
proposed kernel in Equation 4

5: Optimize acquisition function over the latent space $\mathcal{Z}$ to find
the next point $\mathbf{z}_{t}$ for evaluation

6: Compute the decoded structure $\mathbf{x}_{t}$ for point $\mathbf{z}_{t}$
using decoder $\Phi$

7: Evaluate the combinatorial structure $\mathbf{x}_{t}$ to get
$f(\mathbf{x}_{t})$

8: Add new training triple:
$\mathcal{D}_{t+1}\leftarrow\mathcal{D}_{t}\cup\\{\mathbf{z}_{t},\mathbf{x}_{t},f(\mathbf{x}_{t})\\}$;
increment the iteration $t\leftarrow t+1$

9: until convergence or maximum iterations

10: Output: best uncovered structure $\mathbf{\hat{x}}$ and the corresponding
function value $f(\mathbf{\hat{x}})$

###  3.3 Novel surrogate statistical model via structure-coupled kernel

We consider Gaussian process (GP) [52] as the surrogate model of the expensive
black-box objective function $f(\mathbf{x}\in\mathcal{X})$. GPs are known to
have excellent statistical properties including principled uncertainty
quantification, which is critical for the effectiveness of BO algorithms. A GP
model defines a prior distribution on functions which is entirely
characterized by a kernel defined over a pair of inputs. Most of the existing
work on latent space BO employs a standard continuous space kernel represented
by $l(\mathbf{z_{i}}\in\mathcal{Z},\mathbf{z_{j}}\in\mathcal{Z})$, e.g.,
Radial Basis Function (RBF) / Gaussian and Matern kernels, over points in the
latent space to create the GP model. However, this surrogate model is highly-
ineffective for small data settings, especially when the number of dimensions
of latent space is large, which is the common case for deep generative models
for scientific applications.

Structure-coupled kernel. We propose to utilize the rich structural
information that is available from the decoded combinatorial structure
$\mathbf{x}$ corresponding to each point $\mathbf{z}$ from the latent space
$\mathcal{Z}$. The key idea behind our approach is to integrate the structure
information from the decoded outputs with the learned representation of inputs
from the latent space to achieve better surrogate modeling performance. To
include this structure information in a principled manner within a GP model,
we leverage the Generalized Nystrom extension idea [57, 69] to extrapolate the
eigenfunctions of the kernel matrix over latent space ($\mathbf{L}$ =
$\\{L_{ij}$ =
$l(\mathbf{z_{i}},\mathbf{z_{j}})|\mathbf{z_{i}},\mathbf{z_{j}}\in\mathcal{Z}\\}$)
with basis functions from a kernel
$k(\mathbf{x}_{i}\in\mathcal{X},\mathbf{x}_{j}\in\mathcal{X})$ defined over
the decoded combinatorial structures.

Without loss of generality, let $m$ be the number of evaluated inputs from the
latent space, which are denoted as $\mathbf{Z}$ =
$\\{\mathbf{z_{1}},\mathbf{z_{2}},\cdots,\mathbf{z_{m}}\\}$. For example,
these are the points accumulated after $m$ iterations of the latent space BO
approach. Let the corresponding set of decoded structures be $\mathbf{X}$ =
$\\{\mathbf{x_{1}}$ = $\Phi(\mathbf{z_{1}}),\mathbf{x_{2}}$ =
$\Phi(\mathbf{z_{2}}),\cdots,\mathbf{x_{m}}$ = $\Phi(\mathbf{z_{m}})\\}$ with
their function evaluations
$\\{f(\mathbf{x_{1}}),f(\mathbf{x_{2}}),\cdots,f(\mathbf{x_{m}})\\}$. Given
kernels $l:\mathbf{z}\times\mathbf{z}\to\Re$ and
$k:\mathbf{x}\times\mathbf{x}\to\Re$ with $\mathbf{L}$ and $\mathbf{K}$
representing their corresponding kernel matrices, Generalized Nystrom
extension generates an $m$-dimensional feature vector
$\mathbf{\xi(\mathbf{z})}$ for a point $\mathbf{z}$ in the latent space. The
$i$th component of $\mathbf{\xi(\mathbf{z})}$ is given as follows:

$\displaystyle\xi_{i}(\mathbf{z})=\mathbf{k_{z}}^{T}\mathbf{K}^{-1}v_{i}\quad
i\in\\{1,2,\cdots,m\\}$ (1)

where $\mathbf{k_{z}}$ is an $m$-dimensional vector evaluated between
$\mathbf{x}$ (decoded output of latent space input $\mathbf{z}$) and other
combinatorial structures from $\mathbf{X}$:

$\displaystyle\mathbf{k_{z}}=\left[k\left(\Phi(\mathbf{z}),\Phi(\mathbf{z_{1}})\right),\cdots,k\left(\Phi(\mathbf{z}),\Phi(\mathbf{z_{m}})\right)\right]=\left[k\left(\mathbf{x},\mathbf{x_{1}}\right),\cdots,k\left(\mathbf{x},\mathbf{x_{m}}\right)\right]$
(2)

$\mathbf{K}$ is an $m\times m$ kernel matrix for combinatorial structures in
the set $\mathbf{X}$, i.e.,
$K_{ij}=k(\Phi(\mathbf{z_{i}}),\Phi(\mathbf{z_{j}}))=k(\mathbf{x_{i}},\mathbf{x_{j}})$,
and $v_{i}$ is the eigenvalue-scaled eigenvector of the kernel matrix
$\mathbf{L}$ defined over the latent space inputs in the set $\mathbf{Z}$,
i.e. $V=[v_{1},v_{2},\cdots v_{m}]=U\Sigma^{1/2}$, where $U$ and $\Sigma$ are
eigenvectors and eigenvalues of $\mathbf{L}$ respectively.

The reader should note that the term
$k(\Phi(\mathbf{z_{i}}),\Phi(\mathbf{z_{j}}))$ in (2) means that the
structured kernel is applied to the decoded structures $\mathbf{x_{i}}$ =
$\Phi(\mathbf{z_{i}})$ and $\mathbf{x_{j}}$ = $\Phi(\mathbf{z_{j}})$ of latent
space inputs $\mathbf{z_{i}}$ and $\mathbf{z_{j}}$ respectively. This is a key
term in the above expression because it integrates each input from latent
space with its decoded structure in the new feature map $\xi(\mathbf{z})$. For
any two inputs $\mathbf{z}$ and $\mathbf{z^{\prime}}$ in the latent space, the
resulting structure-coupled kernel denoted as
$c(\mathbf{z},\mathbf{z^{\prime}})$ is defined as the dot product of their
corresponding feature vectors $\xi(\mathbf{z})$ and
$\mathbf{\xi(\mathbf{z^{\prime}})}$:

$\displaystyle c(\mathbf{z},\mathbf{z^{\prime}})$
$\displaystyle=\mathbf{\xi(\mathbf{z})}^{T}\mathbf{\xi(\mathbf{z^{\prime}})}$
(3) $\displaystyle c(\mathbf{z},\mathbf{z^{\prime}})$
$\displaystyle=\mathbf{k_{z}}^{T}\mathbf{K}^{-1}\mathbf{L}\mathbf{K}^{-1}\mathbf{k_{z^{\prime}}}$
(4)

Intuitively, by this construction, we are extending the kernel over the latent
space $l$ on the evaluated points $\mathbf{Z}$ to non-evaluated points in the
latent space by utilizing the rich structural features from kernel $k$ defined
over combinatorial spaces. For training points (candidate inputs from latent
space along with their function evaluations), the resulting kernel matrix will
be $\mathbf{L}$ since Equation 4 becomes
$\mathbf{K}\mathbf{K}^{-1}\mathbf{L}\mathbf{K}^{-1}\mathbf{K}=\mathbf{L}$. For
latent space points not in the training set, the structured kernel $k$ acts
like a smooth extrapolating kernel. It can also be seen by interpreting the
Equation 4 through the definition of a kernel in terms of the empirical kernel
map 111We refer to empirical kernel map as commonly defined in [56]
(Definition 3)(with respect to the decoded structured outputs) endowed with a
dot product induced by the positive 222Positive definiteness of
$\mathbf{K}^{-1}\mathbf{L}\mathbf{K}^{-1}$ can be easily seen as a consequence
of the following three facts: i) $\mathbf{K}$ and $\mathbf{L}$, being kernel
matrices, are positive definite; ii) inverse of a psd matrix is psd; and iii)
$MNM$ is psd if $M$ and $N$ are two psd matrices. definite matrix
$\mathbf{K}^{-1}\mathbf{L}\mathbf{K}^{-1}$, i.e.,

$\displaystyle
c(\mathbf{z},\mathbf{z^{\prime}})=\text{<}\mathbf{k_{z}},\mathbf{k_{z^{\prime}}}\text{>}_{\mathbf{K}^{-1}\mathbf{L}\mathbf{K}^{-1}}=\text{<}\mathbf{k_{z}},{\mathbf{K}^{-1}\mathbf{L}\mathbf{K}^{-1}}\mathbf{k_{z^{\prime}}}\text{>}$
(5)

Importantly, the above general construction of structure-coupled kernel allows
us to leverage extensive research on kernel methods for highly-structured
data, which try to exploit structural features of combinatorial objects. For
example, string kernels [38] count the number of common sub-strings in string
inputs, fingerprint kernels [51] capture neighborhood-aggregated properties of
molecules, and features such as number of random walks and shortest paths are
utilized by graph kernels [7].

##  4 Experiments and Results

In this section, we empirically evaluate the effectiveness of the proposed
LADDER approach on real-world benchmarks, and perform comparison with baseline
methods.

###  4.1 Real-world benchmarks

We employ two widely used real-world benchmarks for combinatorial Bayesian
optimization.

Arithmetic expressions optimization. In this benchmark, the goal is to search
in the space of uni-variate arithmetic expressions (generated from a given
grammar) to find the best expression that fits a given target expression [37].
As described in [37], the latent space model is trained on 100K randomly
generated expressions from the following grammar:

S $\rightarrow$ S ’+’ T | S ’*’ T | S ’/’ T | T T $\rightarrow$ ’(’ S ’)’ | ’sin(’ S ’)’ | ’exp(’ S ’)’ T $\rightarrow$ ’v’ | ’1’ | ’2’ | ’3’

We follow the same setup as discussed in the state-of-the-art paper for this
benchmark [68]. We consider the log mean-squared error between an expression
$\mathbf{x}$ and the target expression $\mathbf{x}^{*}$ = $1/3\cdot
v\cdot\sin(v^{2})$ (computed over 1000 evenly-spaced values of $v$ in the
interval $[-10,10]$) as the objective function which should be minimized.

Chemical design optimization. This benchmark considers finding molecules with
best drug-like properties [37] and is similar in prototype for many scientific
applications. Specifically, the goal is to maximize the water-octanol
partition coefficient (logP) over the space of molecules. The latent space
model is trained on the Zinc molecule dataset of 250K molecules. For
consistency purposes, all our results are shown as minimization obtained by
taking a negation of the logP objective.

###  4.2 Experimental setup

Configuration of algorithms. The BO part of the source code is written using
the popular GpyTorch [22] and BoTorch [2] libraries for all BO methods
including LADDER. We employ ARD (automatic relevance determination) Matern
kernel for the latent space inputs in all our experiments. Matern kernel is
commonly advocated as a better choice than RBF kernel for BO algorithms since
the sample functions from the latter are impractically smooth [63].
Hyperparameters of Gaussian process models are fitted by marginal likelihood
maximization after every BO iteration. We employed Junction tree VAE [33] and
Grammar VAE [37] as the latent-space model for chemical design and arithmetic
expression optimization benchmarks respectively. Both pretrained encoder-
decoder models are taken from the source code provided by the authors’ of [68]
333https://github.com/cambridge-mlg/weighted-retraining/. We employed expected
improvement (EI) as the acquisition function for all the BO methods. All
experiments are performed on a machine with the following configuration:
Intel(R) Core(TM) i9-7960X CPU @ 2.80GHz with 128 GB RAM.

LADDER instantiations. In addition to the encoder-decoder style latent space
model, which is same as the Naïve latent space BO (LSBO), LADDER also requires
an appropriate structured kernel for the given combinatorial space. To
demonstrate the generality of our proposed approach, we instantiate LADDER
with two different kernels for our two optimization benchmarks. We employed
sub-sequence string kernel for the arithmetic expressions task and
fingerprints kernel for the chemical design task. We briefly describe both
kernels below.

  * •

Sub-sequence string kernel. This kernel captures the similarity between two
strings by counting the number of matching substrings, where the substrings
can be non-contiguous [38, 10]. Following the notation in [42], given an
alphabet $\Pi$, the kernel between two strings $s_{1}$ and $s_{2}$ is given
as: $k(s_{1},s_{2})=\sum_{u\in\Pi^{n}}\rho(s_{1})\rho(s_{2})$ where $\rho(s)$
=
$\lambda_{m}^{|u|}\cdot\text{\Large$\Sigma$}_{1<i_{1}<\cdots<i_{|u|}<|s|}\left(\lambda_{g}^{i_{|u|}-i_{1}}\mathbf{1}_{u}(s_{i_{1}},\cdots,s_{i_{|u|}})\right)$
for any string $s$ where $\lambda_{g}$ and $\lambda_{m}$ are gap decay and
match decay hyper-parameters. Since arithmetic expressions are naturally
represented as strings, we use this kernel for the arithmetic expressions
task.

  * •

Fingerprints kernel. There is a large body of work in the chemical informatics
literature for designing structural features for molecular inputs. These hand-
engineered features by domain experts are commonly known as molecular
fingerprints [41]. We employ Morgan fingerprints [53] which are high-
dimensional binary features to capture different substructures in a molecule
while being invariant to atom relabeling. Since combinatorial structures in
the chemical design task are molecules, given two molecules $m_{1}$ and
$m_{2}$, we consider the dot product of their Morgan fingerprints as the
structured kernel for the chemical design task. Hence, we refer to this kernel
as the Fingerprints kernel. We employed 2048-bit fingerprints with a bond
radius of 3 [43].

In all our results and figures, the corresponding structured kernel for LADDER
is denoted in the parenthesis, e.g., LADDER (String). We employed the
evolutionary search algorithm CMA-ES [28] as the acquisition function
optimizer for LADDER. The parameters of CMA-ES444https://github.com/CMA-
ES/pycma were fixed with sigma = 0.2 and a population size of 50. The
performance of CMA-ES was found to be highly robust to different choice of
these parameters. We ran CMA-ES from 10 different starting inputs for 10
iterations each and picked the best optimizer found. As discussed later, we
consider one instance of Naïve LSBO with the same configuration of CMA-ES
optimizer for fair comparison and to test our key hypothesis that surrogate
modeling within LADDER is better. We use 10 random points (uniformly picked
from the dataset) to initialize the GP models.

Evaluation metric. We evaluate all methods on the best objective (log MSE for
the arithmetic expressions task and logP for the chemical design task) value
uncovered as a function of the number of experiments (expensive function
evaluations). The method that finds high-performing structures with less
number of function evaluations is considered better.

We ran each method on all benchmarks for 10 different runs with the same
initialization (small number of randomly selected structures and function
evaluations). We plot the mean and two times the standard error for all our
experimental results.

(a) Arithmetic expression optimization

(b) Chemical design optimization

Figure 2: Mean absolute error results comparing the quality of model fit for
varying sizes of training sets with two models: GP model with Matern kernel
(Naïve LSBO) and GP model with the proposed structure-coupled kernel (LADDER).
Lower MAE values mean better surrogate model.

###  4.3 Results and discussion

Comparison of surrogate models. Recall that the key hypothesis of this paper
is that surrogate model employed by the Naïve LSBO approach (GP model with
Matern kernel in our case) is ineffective and GP model with our proposed
structure-coupled kernel for small-data settings. To test this hypothesis, we
compare the quality of the model fit for these two GP models (Naïve LSBO and
LADDER) by evaluating the mean absolute error (MAE) of their predictions on a
testing set. To perform this experiment, we generate 50 (uniformly) random
training sets of different sizes and evaluate the models on 20 random testing
sets. The averaged MAE results over these 1000 training and testing set pairs
are shown in Figure 2. We make following observations. 1) The standard GP
model on latent space denoted by Naïve LSBO shows some improvement in MAE for
the arithmetic expressions task while the improvement is minimal for the
chemical design task. 2) Our proposed surrogate model, i.e., GP with
structure-coupled kernel, denoted by LADDER has significantly lower MAE than
Naïve LSBO on both the benchmarks and continuously decreases as a function of
the training set size. These strong results corroborate our key hypothesis and
demonstrate the effectiveness of our proposed surrogate model with the
structure-coupled kernel.

Naïve latent space BO vs. LADDER. A natural question based on the above
results is whether improved surrogate modeling results in better overall BO
performance. To answer this question, we compare the BO performance (best
uncovered or incumbent objective value vs. number of function evaluations or
iterations) of Naïve LSBO and LADDER. We consider two choices for acquisition
function optimizer within the Naïve LSBO approach: zeroth order CMA based
optimizer (same as LADDER) and second-order gradient based optimizer (L-BFGS).
We make the following observations from the results shown in Figure 3. 1)
LADDER consistently uncovers significantly better structures than those from
the Naïve LSBO approach on both benchmarks. This is a direct consequence of
the better surrogate model of LADDER since the acquisition function optimizer
is kept the same for both methods, i.e., CMA. 2) L-BFGS based acquisition
function optimizer slightly improves the BO performance of Naïve LSBO but
still cannot match the performance of LADDER.

(a) Arithmetic expression dataset

(b) Chemical design dataset

Figure 3: Results comparing the BO performance of LADDER and Naïve latent
space BO.

(a) Arithmetic expression dataset

(b) Chemical design dataset

Figure 4: Results comparing the BO performance of LADDER and different state-
of-the-art methods.

LADDER vs. State-of-the-art. To further analyze LADDER, we compare its
performance with a set of state-of-the-art methods. We include weighted
retraining approach which was recently proposed [68] to update the latent
space model as the BO algorithm progresses (Naïve LSBO w/ retraining). We also
consider design by adaptive sampling (DbAS) [8], the cross-entropy method with
probability of improvement (CEM-PI) [54], the feedback VAE (FB-VAE) [27], and
reward-weighted regression (RWR) [49]. We employ the publicly available
implementation of these baseline methods. We make the following observations
from the results shown in Figure 4. 1) LADDER performs significantly better on
the arithmetic expressions task and similar to the best method on the chemical
design task. We verify the similar performance of LADDER on the chemical
design task by performing a two-sided paired Wilcoxon test at 1% significance.
The performance of LADDER and Naïve LSBO w/ retraining is statistically
similar on the chemical design task (p-value = 0.0489). 2) Retraining the
latent space model helps in improving the performance of Naïve LSBO on both
tasks. 3) DbAS and CEM-PI perform similar to Naïve LSBO w/ retraining since
they are special case of retraining method as described in [68]. The
discrepancy in LADDER’s performance on the chemical design benchmark can be
attributed to the low-flexibility of fingerprint kernel which doesn’t include
any hyper-parameters (as opposed to string kernel) to tune it for a specific
dataset.

##  5 Related Work

In this section, we discuss the most closely related work for the problem
setting studied in this paper.

Deep generative models for structured data. Scientific domains including
chemistry and molecular biology involve highly structured data [58]. To
address the challenges of structured data, there is a growing body of work on
deep generative models (DGMs). Some notable examples include grammar VAE [37],
junction tree VAE [33] and syntax-directed VAE [11]. This line of work is
complementary to our work as advances in DGMs will automatically improve the
BO performance of LADDER.

Kernels over structured data. There is a large body of research on generic
kernels over structured data including strings [38, 10], trees [61], graphs
[7], sets [9], and permutations [32]. LADDER allows us to leverage this prior
research to perform sample-efficient BO over combinatorial spaces.

BO over latent space. The use of DGMs to learn a latent space and to perform
BO in this continuous space was first started by Gomez-Bombarelli et al., for
chemical design [26]. This led to a lot of followup work motivated by
applications from multiple domains [40, 19, 34, 33]. A recent work by Tripp et
al., [68] noted that this decoupled approach of training DGM and BO process
can make the overall optimization problem hard; and proposed an approach
referred as weighted retraining. The key idea is to periodically retrain the
DGM by giving more weight to inputs with high function values. Our LADDER
approach and weighted retraining have complementary strengths. For small-data
settings, LADDER is much more effective than weighted retraining as
demonstrated by our experiments.

BO over combinatorial space. We can categorize these methods based on the
choice of surrogate model and search strategies for acquisition function
optimization. Linear models [3], Gaussian processes with kernels over discrete
structures [46, 15, 24, 36], and random forest [30] are considered for
surrogate modeling. Search strategies include mathematical optimization [3,
13, 15], heuristic search methods [30, 46, 14], and combination thereof [16,
66, 44]. [31] provided a BO approach for tree structured spaces. LADDER is
complementary to this line of work. First, it allows to combine the
complementary strengths of two pieces of knowledge, namely, generic/domain-
specific kernels over structured data and data-driven representations learned
using DGMs, for improved surrogate modeling. Second, it is well known in the
AI search literature that effective search strategies varies from one problem
to another. For example, a recent work on BO over string spaces [42], showed
that we need to specialize genetic algorithms for different problems. In
contrast, we can use generic search strategies for continuous spaces with
LADDER.

Reinforcement learning (RL) formulations are also studied to solve this
optimization problem [71, 73, 47, 62, 50, 1, 60]. RL is very effective for
simulated environments where collection of large amount of data to improve the
policy is possible. Unfortunately, this requirement is impractical when we
need to perform expensive experiments to collect new training examples.

##  6 Discussion and Limitations

The main contribution of this paper is to improve the performance of latent-
space BO methods. However, an alternative approach to solve the problem
discussed in this paper is to perform BO directly on the structured space. We
evaluate one instance of this approach (BO with Fingerprints kernel) on the
chemical design task and results are shown in the below table. We make two
observations: 1) LADDER has better accuracy for a large number of initial BO
iterations compared to BO w/ Fingerprints approach; and 2) BO with
Fingerprints kernel alone reached slightly better accuracy than LADDER in the
end. It should be noted that if we improve the latent space by training deep
generative models on larger amounts of unsupervised structures, LADDER will be
able to achieve comparable or better accuracy when compared to the BO with
Fingerprints kernel approach.

| Iteration: 15 | Iteration: 25 | Iteration: 50 | Iteration: 75 | Iteration: 100
---|---|---|---|---|---
BO w/ Fingerprints | 2.46 +- 0.32 | 2.80 +- 0.23 | 3.11 +- 0.11 | 3.32 +- 0.23 | 3.36 +- 0.23
LADDER | 2.78 +- 0.26 | 2.93 +- 0.23 | 3.18 +- 0.20 | 3.25 +- 0.18 | 3.25 +- 0.18

Moreover, there is a general argument to justify the research direction of
combining the strengths of latent space and structured kernels. Given a
perfect kernel that captures all the relevant domain-specific
characteristics/structure, then the utility for latent space BO methods or
LADDER will be limited. However, generic kernels over combinatorial structures
(e.g., strings, trees, and graphs) may not always capture the critical domain-
specific characteristics. Consider the example of optimizing Metal-Organic
Framework (MOF) materials [17] for adsorption property, e.g, storage of gases
for hydrogen-powered vehicles. For this problem, we can use graph kernels over
the graph representation of MOF materials, but they won’t be able to capture
some critical characteristics such as pore size, which is important to predict
the adsorption property of MOF materials. In such scenarios, domain experts
and practitioners can either spend time to engineer a hand-designed kernel
(e.g, Fingerprints kernel from the chemical sciences community) or use large
amounts of unsupervised structures data to learn a latent representation to
capture these domain-specific characteristics in an automated manner. This
paper takes the first step to synergistically combine the advantages of latent
space and generic/domain-specific kernels to automate the overall BO workflow,
which is highly advantageous for scientists and engineers who are the real-
users of this technology. We do not claim that LADDER is the optimal algorithm
to achieve this goal, but our hope is that LADDER will inspire the BO
community to explore this important research direction to develop better
algorithms in the future555There is concurrent paper [45] at NeurIPS-2021 that
leverages epistemic uncertainty of the decoder to guide the optimization
process..

One potential limitation of LADDER might be selecting the right choice of
structured kernel for a given task. Theoretically, the representation power of
kernels is studied in terms of properties including universal and
characteristic [64]. Satisfying these properties is a basic requirement for
selecting a kernel. However, since many known kernels are universal, this
criterion might not be enough for all problem settings. Nevertheless, for
combinatorial spaces, most of the generic kernels are roughly defined in terms
of counting the number of common substructures in a given pair of
combinatorial structures [25]. Kernels that capture large sub-structures are
generally more powerful in terms of their representational capacity. However,
there is a trade-off between representation power and time complexity of
kernel computation. For our problem setting of optimizing combinatorial spaces
using expensive function evaluations, an instance of small data problem (i.e.,
with a small number of structure and function evaluation pairs), it is best to
select a kernel with the highest representation power and some hyper-
parameters that can be optimized in a data-driven manner.

##  7 Summary and Future Work

We introduced a sample-efficient Bayesian optimization (BO) approach for
combinatorial spaces called LADDER. The key idea behind LADDER is a Gaussian
process based surrogate model that combines the complementary strengths of
latent space representation with rich information about decoded outputs using
structured kernels. We showed that the BO performance of LADDER is better or
similar than state-of-the-art methods and significantly better than the Naïve
latent space BO method. Since LADDER’s key contribution is in the surrogate
model part of the BO procedure, it provides the flexibility to use any
acquisition function, which opens up an avenue for various type of extensions
including multi-objective [4, 12, 48, 65], multi-fidelity [67, 35, 72], and
constrained BO [29, 23].

Acknowledgements. This research is supported in part by NSF grants
IIS-1845922, OAC-1910213, and SII-2030159. The authors’ would like to thank
the anonymous reviewers for their constructive feedback and suggestions to
improve the paper.

## References

  * [1] Christof Angermueller, David Dohan, David Belanger, Ramya Deshpande, Kevin Murphy, and Lucy Colwell.  Model-based reinforcement learning for biological sequence design.  In International Conference on Learning Representations, 2019.
  * [2] Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Ben Letham, Andrew G Wilson, and Eytan Bakshy.  BoTorch: A framework for efficient monte-carlo bayesian optimization.  In Advances in Neural Information Processing Systems, 2020.
  * [3] Ricardo Baptista and Matthias Poloczek.  Bayesian optimization of combinatorial structures.  In Proceedings of the 35th International Conference on Machine Learning, pages 462–471, 2018.
  * [4] Syrine Belakaria and Aryan Deshwal.  Max-value entropy search for multi-objective bayesian optimization.  In Advances in Neural Information Processing Systems, 2019.
  * [5] Syrine Belakaria, Aryan Deshwal, Nitthilan Kannappan Jayakodi, and Janardhan Rao Doppa.  Uncertainty-aware search framework for multi-objective Bayesian optimization.  In AAAI conference on Artificial Intelligence, 2020.
  * [6] Syrine Belakaria, Derek Jackson, Yue Cao, Janardhan Rao Doppa, and Xiaonan Lu.  Machine learning enabled fast multi-objective optimization for electrified aviation power system design.  In IEEE Energy Conversion Congress and Exposition, 2020.
  * [7] Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-López, Leslie O’Bray, and Bastian Rieck.  Graph kernels: state-of-the-art and future challenges.  arXiv preprint arXiv:2011.03854, 2020.
  * [8] David H Brookes and Jennifer Listgarten.  Design by adaptive sampling.  arXiv preprint arXiv:1810.03714, 2018.
  * [9] Poompol Buathong, David Ginsbourger, and Tipaluck Krityakierne.  Kernels over sets of finite sets using RKHS embeddings, with application to bayesian (combinatorial) optimization.  In International Conference on Artificial Intelligence and Statistics, pages 2731–2741. PMLR, 2020.
  * [10] Nicola Cancedda, Eric Gaussier, Cyril Goutte, and Jean Michel Renders.  Word sequence kernels.  Journal of Machine Learning Research, 3:1059–1082, 2003.
  * [11] Hanjun Dai, Yingtao Tian, Bo Dai, Steven Skiena, and Le Song.  Syntax-directed variational autoencoder for structured data.  In International Conference on Learning Representations, 2018.
  * [12] Samuel Daulton, Maximilian Balandat, and Eytan Bakshy.  Differentiable expected hypervolume improvement for parallel multi-objective bayesian optimization.  arXiv preprint arXiv:2006.05078, 2020.
  * [13] Aryan Deshwal, Syrine Belakaria, and Janardhan Rao Doppa.  Scalable combinatorial Bayesian optimization with tractable statistical models.  CoRR, abs/2008.08177, 2020.
  * [14] Aryan Deshwal, Syrine Belakaria, and Janardhan Rao Doppa.  Bayesian optimization over hybrid spaces.  In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages 2632–2643, 2021.
  * [15] Aryan Deshwal, Syrine Belakaria, and Janardhan Rao Doppa.  Mercer features for efficient combinatorial Bayesian optimization.  In AAAI conference on Artificial Intelligence, 2021.
  * [16] Aryan Deshwal, Syrine Belakaria, Janardhan Rao Doppa, and Alan Fern.  Optimizing discrete spaces via expensive evaluations: a learning to search framework.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3773–3780, 2020.
  * [17] Aryan Deshwal, Cory Simon, and Janardhan Rao Doppa.  Bayesian optimization of nanoporous materials.  Molecular Systems Design and Engineering, Royal Society of Chemistry, 2021.
  * [18] Janardhan Rao Doppa.  Adaptive experimental design for optimizing combinatorial structures.  In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI), pages 4940–4945, 2021.
  * [19] Stephan Eissman, Daniel Levy, Rui Shu, Stefan Bartzsch, and Stefano Ermon.  Bayesian optimization and attribute adjustment.  In Proceedings of the Thirty Fourth Conference on Uncertainty in Artificial Intelligence, 2018.
  * [20] Peter I Frazier.  A tutorial on bayesian optimization.  arXiv preprint arXiv:1807.02811, 2018.
  * [21] Peter I Frazier and Jialei Wang.  Bayesian optimization for materials design.  In Information Science for Materials Discovery and Design, pages 45–75. Springer, 2016.
  * [22] Jacob Gardner, Geoff Pleiss, Kilian Q Weinberger, David Bindel, and Andrew G Wilson.  GPyTorch: Blackbox matrix-matrix gaussian process inference with gpu acceleration.  In Advances in Neural Information Processing Systems, volume 31, 2018.
  * [23] Jacob R Gardner, Matt J Kusner, Zhixiang Eddie Xu, Kilian Q Weinberger, and John P Cunningham.  Bayesian optimization with inequality constraints.  In International Conference on Machine Learning, volume 2014, pages 937–945, 2014.
  * [24] Eduardo C Garrido-Merchán and Daniel Hernández-Lobato.  Dealing with categorical and integer-valued variables in bayesian optimization with gaussian processes.  Neurocomputing, 380:20–35, 2020.
  * [25] Thomas Gärtner.  A survey of kernels for structured data.  ACM SIGKDD explorations newsletter, 5(1):49–58, 2003.
  * [26] Rafael Gómez-Bombarelli, Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez-Lengeling, Dennis Sheberla, Jorge Aguilera-Iparraguirre, Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik.  Automatic chemical design using a data-driven continuous representation of molecules.  ACS Central Science, 4(2):268–276, 2018.
  * [27] Anvita Gupta and James Zou.  Feedback GAN for DNA optimizes protein functions.  Nature Machine Intelligence, 1(2):105–111, 2019.
  * [28] Nikolaus Hansen.  The cma evolution strategy: a comparing review.  Towards a new evolutionary computation, pages 75–102, 2006.
  * [29] José Miguel Hernández-Lobato, Michael A. Gelbart, Ryan P. Adams, Matthew W. Hoffman, and Zoubin Ghahramani.  A general framework for constrained bayesian optimization using information-based search.  Journal of Machine Learning Research, 17(1):5549–5601, 2016.
  * [30] Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown.  Sequential model-based optimization for general algorithm configuration.  In International conference on Learning and Intelligent Optimization, pages 507–523, 2011.
  * [31] Rodolphe Jenatton, Cedric Archambeau, Javier González, and Matthias Seeger.  Bayesian optimization with tree-structured dependencies.  In International Conference on Machine Learning, pages 1655–1664. PMLR, 2017.
  * [32] Yunlong Jiao and Jean-Philippe Vert.  The kendall and mallows kernels for permutations.  In International Conference on Machine Learning, pages 1935–1944. PMLR, 2015.
  * [33] Wengong Jin, Regina Barzilay, and Tommi Jaakkola.  Junction tree variational autoencoder for molecular graph generation.  In International Conference on Machine Learning, pages 2323–2332. PMLR, 2018.
  * [34] Hiroshi Kajino.  Molecular hypergraph grammar with its application to molecular optimization.  In International Conference on Machine Learning, pages 3183–3191. PMLR, 2019.
  * [35] Kirthevasan Kandasamy, Gautam Dasarathy, Junier Oliva, Jeff Schneider, and Barnabás Póczos.  Gaussian process optimisation with multi-fidelity evaluations.  In Advances in Neural Information Processing Systems, 2016.
  * [36] Jungtaek Kim, Michael McCourt, Tackgeun You, Saehoon Kim, and Seungjin Choi.  Bayesian optimization over sets.  arXiv preprint arXiv:1905.09780, 2019.
  * [37] Matt J Kusner, Brooks Paige, and José Miguel Hernández-Lobato.  Grammar variational autoencoder.  In International Conference on Machine Learning, pages 1945–1954. PMLR, 2017.
  * [38] Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, and Chris Watkins.  Text classification using string kernels.  Journal of Machine Learning Research, 2(Feb):419–444, 2002.
  * [39] Ilya Loshchilov, Marc Schoenauer, and Michèle Sebag.  Bi-population CMA-ES agorithms with surrogate models and line searches.  In Proceedings of the 15th Annual Conference Companion on Genetic and Evolutionary Computation, pages 1177–1184, 2013.
  * [40] Xiaoyu Lu, Javier Gonzalez, Zhenwen Dai, and Neil D Lawrence.  Structured variationally auto-encoded optimization.  In International Conference on Machine Learning, pages 3267–3275. PMLR, 2018.
  * [41] Andrea Mauri, Viviana Consonni, Manuela Pavan, and Roberto Todeschini.  Dragon software: an easy approach to molecular descriptor calculations.  Match, 56(2):237–248, 2006.
  * [42] Henry B Moss, Daniel Beck, Javier González, David S Leslie, and Paul Rayson.  BOSS: Bayesian optimization over string spaces.  arXiv preprint arXiv:2010.00979, 2020.
  * [43] Henry B Moss and Ryan-Rhys Griffiths.  Gaussian process molecule property prediction with flowmo.  arXiv preprint arXiv:2010.01118, 2020.
  * [44] Dang Nguyen, Sunil Gupta, Santu Rana, Alistair Shilton, and Svetha Venkatesh.  Bayesian optimization for categorical and category-specific continuous inputs.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5256–5263, 2020.
  * [45] Pascal Notin, José Miguel Hernández-Lobato, and Yarin Gal.  Improving black-box optimization in vae latent space using decoder uncertainty.  arXiv preprint arXiv:2107.00096, 2021.
  * [46] Changyong Oh, Jakub Tomczak, Efstratios Gavves, and Max Welling.  Combinatorial bayesian optimization using the graph cartesian product.  In Advances in Neural Information Processing Systems, pages 2910–2920, 2019.
  * [47] Marcus Olivecrona, Thomas Blaschke, Ola Engkvist, and Hongming Chen.  Molecular de-novo design through deep reinforcement learning.  Journal of cheminformatics, 9(1):48, 2017.
  * [48] Biswajit Paria, Kirthevasan Kandasamy, and Barnabás Póczos.  A flexible framework for multi-objective bayesian optimization using random scalarizations.  In Uncertainty in Artificial Intelligence, pages 766–776. PMLR, 2020.
  * [49] Jan Peters and Stefan Schaal.  Reinforcement learning by reward-weighted regression for operational space control.  In International Conference on Machine Learning, pages 745–750, 2007.
  * [50] Mariya Popova, Olexandr Isayev, and Alexander Tropsha.  Deep reinforcement learning for de novo drug design.  Science Advances, 4(7):eaap7885, 2018.
  * [51] Liva Ralaivola, Sanjay J Swamidass, Hiroto Saigo, and Pierre Baldi.  Graph kernels for chemical informatics.  Neural Networks, 18(8):1093–1110, 2005.
  * [52] Carl Edward Rasmussen and Christopher K. I. Williams.  Gaussian processes for machine learning.  Adaptive Computation and Machine Learning. MIT Press, 2006.
  * [53] David Rogers and Mathew Hahn.  Extended-connectivity fingerprints.  Journal of Chemical Information and Modeling, 50(5):742–754, 2010\.
  * [54] Reuven Rubinstein.  The cross-entropy method for combinatorial and continuous optimization.  Methodology and Computing in Applied Probability, 1(2):127–190, 1999.
  * [55] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever.  Evolution strategies as a scalable alternative to reinforcement learning.  arXiv preprint arXiv:1703.03864, 2017.
  * [56] Bernhard Scholkopf, Sebastian Mika, Chris JC Burges, Philipp Knirsch, K-R Muller, Gunnar Ratsch, and Alexander J Smola.  Input space versus feature space in kernel-based methods.  IEEE transactions on neural networks, 10(5):1000–1017, 1999.
  * [57] Anton Schwaighofer, Volker Tresp, and Kai Yu.  Learning gaussian process kernels via hierarchical bayes.  In Advances in Neural Information Processing Systems, pages 1209–1216, 2005.
  * [58] Daniel Schwalbe-Koda and Rafael Gómez-Bombarelli.  Generative models for automatic chemical design.  In Machine Learning Meets Quantum Physics, pages 445–467. Springer, 2020.
  * [59] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas.  Taking the human out of the loop: a review of bayesian optimization.  Proceedings of the IEEE, 104(1):148–175, 2016.
  * [60] Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang.  Graphaf: a flow-based autoregressive model for molecular graph generation.  arXiv preprint arXiv:2001.09382, 2020.
  * [61] Kilho Shin, Marco Cuturi, and Tetsuji Kuboyama.  Mapping kernels for trees.  In International Conference on Machine Learning, 2011.
  * [62] Gregor Simm, Robert Pinsler, and José Miguel Hernández-Lobato.  Reinforcement learning for molecular design guided by quantum mechanics.  In International Conference on Machine Learning, pages 8959–8969. PMLR, 2020.
  * [63] Jasper Snoek, Hugo Larochelle, and Ryan P. Adams.  Practical bayesian optimization of machine learning algorithms.  In Advances in Neural Information Processing Systems - Volume 2, page 2951–2959, 2012.
  * [64] Bharath K Sriperumbudur, Kenji Fukumizu, and Gert RG Lanckriet.  Universality, characteristic kernels and rkhs embedding of measures.  Journal of Machine Learning Research, 12(7), 2011.
  * [65] Shinya Suzuki, Shion Takeno, Tomoyuki Tamura, Kazuki Shitara, and Masayuki Karasuyama.  Multi-objective bayesian optimization using pareto-frontier entropy.  In International Conference on Machine Learning, pages 9279–9288. PMLR, 2020.
  * [66] Kevin Swersky, Yulia Rubanova, David Dohan, and Kevin Murphy.  Amortized bayesian optimization over discrete spaces.  In Conference on Uncertainty in Artificial Intelligence, pages 769–778. PMLR, 2020.
  * [67] Shion Takeno, Hitoshi Fukuoka, Yuhki Tsukada, Toshiyuki Koyama, Motoki Shiga, Ichiro Takeuchi, and Masayuki Karasuyama.  Multi-fidelity bayesian optimization with max-value entropy search and its parallelization.  In International Conference on Machine Learning, pages 9334–9345. PMLR, 2020.
  * [68] Austin Tripp, Erik Daxberger, and José Miguel Hernández-Lobato.  Sample-efficient optimization in the latent space of deep generative models via weighted retraining.  Advances in Neural Information Processing Systems, 33, 2020.
  * [69] Christopher Williams and Matthias Seeger.  Using the nyström method to speed up kernel machines.  In Annual Conference on Neural Information Processing Systems, 2001\.
  * [70] Kevin K Yang, Zachary Wu, and Frances H Arnold.  Machine-learning-guided directed evolution for protein engineering.  Nature methods, 16(8):687–694, 2019.
  * [71] Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec.  Graph convolutional policy network for goal-directed molecular graph generation.  In Advances in Neural Information Processing Systems, pages 6410–6421, 2018.
  * [72] Yehong Zhang, Trong Nghia Hoang, Bryan Kian Hsiang Low, and Mohan Kankanhalli.  Information-based multi-fidelity bayesian optimization.  In NIPS Workshop on Bayesian Optimization, 2017.
  * [73] Zhenpeng Zhou, Steven Kearnes, Li Li, Richard N Zare, and Patrick Riley.  Optimization of molecules via deep reinforcement learning.  Scientific Reports, 9(1):1–10, 2019.
  * [74] Zhiyuan Zhou, Syrine Belakaria, Aryan Deshwal, Wookpyo Hong, Janardhan Rao Doppa, Partha Pratim Pande, and Deukhyoun Heo.  Design of multi-output switched-capacitor voltage regulator via machine learning.  In DATE, 2020.