# Note on the pinned distance problem over finite fields

Doowon Koh  Department of Mathematics
Chungbuk National University
Cheongju, Chungbuk 28644 Korea<EMAIL_ADDRESS>
###### Abstract.

Let $\mathbb{F}_{q}$ be a finite field with odd $q$ elements. In this article,
we prove that if $E\subseteq\mathbb{F}_{q}^{d},d\geq 2,$ and $|E|\geq q$, then
there exists a set $Y\subseteq\mathbb{F}_{q}^{d}$ with $|Y|\sim q^{d}$ such
that for all $y\in Y$, the number of distances between the point $y$ and the
set $E$ is similar to the size of the finite field $\mathbb{F}_{q}.$ As a
corollary, we obtain that for each set $E\subseteq\mathbb{F}_{q}^{d}$ with
$|E|\geq q,$ there exists a set $Y\subseteq\mathbb{F}_{q}^{d}$ with $|Y|\sim
q^{d}$ so that any set $E\cup\\{y\\}$ with $y\in Y$ determines a positive
proportion of all possible distances. An averaging argument and the pigeonhole
principle play a crucial role in proving our results.

###### 2010 Mathematics Subject Classification:

42B05, 11T23

Key words and phrases: Finite field, Pinned distance
This work was conducted during the research year of Chungbuk National
University in 2022, and was supported by Basic Science Research Programs
through National Research Foundation of Korea (NRF) funded by the Ministry of
Education (NRF-2018R1D1A1B07044469).

##  1\. Introduction

Let $\mathbb{F}_{q}^{d}$ be the $d$-dimensional vector space over the finite
field $\mathbb{F}_{q}$ with $q$ elements. In 2005, Iosevich and Rudnev [5]
initially posed and studied an analogue of the Falconer distance problem over
finite fields. They asked for the minimal exponent $\alpha>0$ such that if
$E\subseteq\mathbb{F}_{q}^{d}$ and $|E|\geq Cq^{\alpha}$ for a sufficiently
large constant $C>0$, then

$|\Delta(E)|\geq cq$

for some $0\leq c\leq 1,$ where $|\Delta(E)|$ denotes the cardinality of the
distance set $\Delta(E)$, defined by

$\Delta(E)=\\{||x-y||:x,y\in E\\}.$

Here we recall that $||\alpha||:=\sum\limits_{j=1}^{d}\alpha_{j}^{2}$ for
$\alpha=(\alpha_{1},\ldots,\alpha_{d})\in\mathbb{F}_{q}^{d}.$

By developing the discrete Fourier machinery, Iosevich and Rudnev [5] proved
that $|\Delta(E)|\sim q$ whenever $|E|\geq Cq^{(d+1)/2}.$ We recall that $A\ll
B$ means that $A\leq CB$ for some constant $C>0$, which is independent of $q$,
and we use $A\sim B$ if $A\ll B$ and $B\ll A.$ The authors in [3] showed that
the exponent $(d+1)/2$ is optimal for all odd dimensions $d\geq 3$ except for
the cases when $-1$ is not a square and $d=4k-1$ for $k\in\mathbb{N}.$
However, in any other cases including even dimensions $d\geq 2,$ it has been
conjectured by Iosevich and Rudnev [5] that in order to have a positive
proportion of all distances, the exponent $(d+1)/2$ can be improved to $d/2.$

######  Conjecture 1.1 (Iosevich-Rudnev’s Conjecture).

Let $E\subseteq\mathbb{F}_{q}^{d}.$ Suppose that $d\geq 2$ is even or
$d,q\equiv 3\mod{4}.$ Then if $|E|\geq Cq^{d/2}$ for a sufficiently large
constant $C>0$, we have $|\Delta(E)|\sim q.$

Iosevich-Rudnev’s Conjecture is still open and even the threshold $(d+1)/2$
has not been improved except for two dimensions. In the case of $d=2$ over
general finite fields, the authors in [2] obtained the $4/3$ exponent, which
is the first result to break down the exponent $(d+1)/2.$ This result was
obtained by applying the restriction estimates for the circles on the plane.
More precisely, they proved the following result with an explicit constant.

######  Theorem 1.2 ([2]).

Let $E$ be a subset of $\subset{\mathbb{F}}_{q}^{2}$ with $|E|\geq q^{4/3}.$
Then following statements hold:

  1. (1)

If $q\equiv 3\mod{4},$ then $|\Delta(E)|\geq\frac{q}{1+\sqrt{3}}.$

  2. (2)

If $q\equiv 1\mod{4},$ then $|\Delta(E)|\geq C_{q}q,$ where the constant
$C_{q}$ is defined by

$C_{q}:=\frac{\left(1-2q^{-1}\right)^{2}}{1+\sqrt{3}-\sqrt{3}q^{-2/3}}.$

Notice that $C_{q}>0$ for all $q\geq 3,$ and $C_{q}$ converges to
$\frac{1}{1+\sqrt{3}}$ as $q\to\infty.$ Since a convergent sequence is
bounded, we therefore choose a constant $c>0,$ independent of $q,$ such that
$C_{q}\geq c>0.$ From this observation, the following corollary is a direct
consequence of Theorem 1.2.

######  Corollary 1.3 ([2]).

Suppose that $E\subseteq\mathbb{F}_{q}^{2}$ with $|E|\geq q^{4/3}.$ Then we
have

$|\Delta(E)|\sim q.$

Using a group action approach, Bennett, Hart, Iosevich, Pakianathan, and
Rudnev [1] provided an alternative proof for the exponent $4/3$ in the above
corollary.

As a strong version of the Falconer distance problem, one has studied the
pinned distance problem over finite fields. Given
$E\subseteq\mathbb{F}_{q}^{d},d\geq 2,$ and $y\in\mathbb{F}_{q},$ the pinned
distance set with a pin $y$, denoted by $\Delta_{y}(E),$ is defined by

$\Delta_{y}(E)=\\{||x-y||:x\in E\\}.$

The Chapman, Erdog̃an, Hart, Iosevich, and Koh [2] showed that the exponent
$(d+1)/2$ due to Iosevich and Rudnev holds true for the pinned distance sets.
More precisely they proved the following.

######  Theorem 1.4 ([2]).

Let $E\subseteq\mathbb{F}_{q}^{d},d\geq 2.$ If $|E|\geq q^{\frac{d+1}{2}},$
then there exists a subset $E^{\prime}$ of $E$ with $|E^{\prime}|\sim|E|$ so
that for every $y\in E^{\prime}$, we have

$|\Delta_{y}(E)|\sim q.$

As seen in the conjecture of the Falconer distance set problem, the exponent
$(d+1)/2$ cannot be improved except for the cases when $d,q\equiv 3\mod{4}$ or
$d\geq 2$ is even. However, in those cases it have been believed that $d/2$
can be the best possible exponent for the pinned distance sets. As partial
evidence for this prediction, the $4/3$ exponent result was extended to the
pinned distance sets in $\mathbb{F}_{q}^{2}$ by Hanson, Lund, and Roche-Newton
[4], who successfully performed the bisector energy estimate.

######  Theorem 1.5 ([4]).

Let $E\subseteq\mathbb{F}_{q}^{2}.$ If $|E|\geq q^{4/3}$, then the conclusion
of Theorem 1.4 holds.

When $q$ is prime, the exponent $4/3$ have been improved to $5/4$ by Murphy,
Petridis, Pham, Rudnev, and Stevenson [6].

######  Theorem 1.6 ([6]).

Let $q$ be prime. Then if $E\subseteq\mathbb{F}_{q}^{2}$ with $|E|\geq
q^{\frac{5}{4}}$, we have

$\max\limits_{y\in E}|\Delta_{y}(E)|\sim q.$

Despite researchers’ efforts, the conjectured exponent $d/2$ has not been
proven. It is unlikely that one can establish the conjecture by using the
known techniques. Moreover, there is very little evidence to support that the
conjecture is true.

The main purpose of this paper is not to derive an improved result on the
distance problem, but to address that the probability that random sets satisfy
the distance conjecture is very high.

###  1.1. The statement of main results

Our main theorem is as follows.

######  Theorem 1.7.

Let $E\subseteq\mathbb{F}_{q}^{d}.$ Then given $a>1,$ there exists
$Y\subseteq\mathbb{F}_{q}^{d}$ with $|Y|\geq\frac{a-1}{a}q^{d}$ such that for
all $y\in Y$,

$|\Delta_{y}(E)|\geq\min\left\\{\frac{q}{2a},~{}\frac{|E|}{2a}\right\\}.$

The following result is a direct consequence of Theorem 1.7.

######  Corollary 1.8.

Suppose that $E\subseteq\mathbb{F}_{q}^{d},d\geq 2,$ with $|E|\geq q.$ Then
for any $a>1$, there exists $Y\subseteq\mathbb{F}_{q}^{d}$ with
$|Y|\geq\frac{a-1}{a}q^{d}$ so that for all $y\in Y,$ we have

$|\Delta(E\cup\\{y\\})|\geq\frac{q}{2a}.$

###### Proof.

Since $|E|\geq q,$ we have

$\min\left\\{\frac{q}{2a},~{}\frac{|E|}{2a}\right\\}=\frac{q}{2a}.$

In addtition, note that for all $y\in\mathbb{F}_{q},$ we have
$|\Delta(E\cup\\{y\\})|\geq|\Delta_{y}(E)|.$ Hence, the statement of the
corollary follows immediately from Theorem 1.7. ∎

##  2\. Proof of main result (Theorem 1.7)

We begin with the standard counting argument as in [2].

To find a lower bound of the cardinality of the $y$-pinned distance set
$\Delta_{y}(E)$, we consider the $y$-pinned counting function
$\nu_{y}:\mathbb{F}_{q}\to\mathbb{N}\cup\\{0\\},$ which maps an element $t$ in
$\mathbb{F}_{q}$ to the number of elements $x$ in $E$ such that $||x-y||=t.$
In other words, for $y\in\mathbb{F}_{q}^{d},t\in\mathbb{F}_{q},$ we have

$\nu_{y}(t)=\sum_{x\in E:||x-y||=t}1.$

Since $|E|^{2}=\left(\sum_{t\in\Delta_{y}(E)}\nu_{y}(t)\right)^{2},$ it
follows from the Cauchy-Schwarz inequality that

(2.1)
$|\Delta_{y}(E)|\geq\frac{|E|^{2}}{\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)}.$

###  2.1. Key lemmas

The average of $\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)$ over $y$ in
$\mathbb{F}_{q}^{d}$ is explicitly given as follows:

######  Lemma 2.1.

Let $E\subseteq\mathbb{F}_{q}^{d}.$ Then we have

$\frac{1}{q^{d}}\sum_{y\in\mathbb{F}_{q}^{d}}\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)=\frac{|E|^{2}}{q}+\frac{q-1}{q}|E|.$

###### Proof.

By the definition of the $y$-pinned counting function $\nu_{y}(t)$, we have
for each $y\in\mathbb{F}_{q},$

$\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)=\sum_{x,z\in E:||x-y||=||z-y||}1.$

Hence, the average of it over $y\in\mathbb{F}_{q}^{d}$ is given as follows:

(2.2)
$\displaystyle\frac{1}{q^{d}}\sum_{y\in\mathbb{F}_{q}^{d}}\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)$
$\displaystyle=\frac{1}{q^{d}}\sum_{x,z\in
E:x=z}\sum_{y\in\mathbb{F}_{q}^{d}:||x-y||=||z-y||}1+\frac{1}{q^{d}}\sum_{x,z\in
E:x\neq z}\sum_{y\in\mathbb{F}_{q}^{d}:||x-y||=||z-y||}1$
$\displaystyle=|E|+\frac{1}{q^{d}}\sum_{x,z\in E:x\neq
z}\sum_{y\in\mathbb{F}_{q}^{d}:||x-y||=||z-y||}1.$

∎

Now, we notice that for $x,z\in E$ with $x\neq z$, we have

(2.3) $\sum_{y\in\mathbb{F}_{q}^{d}:||x-y||=||z-y||}1=q^{d-1}.$

In fact, since $x\neq z$, the quantity
$\sum_{y\in\mathbb{F}_{q}^{d}:||x-y||=||z-y||}1$ is the number of the elements
in the hyper-plane which bisects the line segment joining $x$ and $z$.
Alternatively we can prove this rigorously by using the finite field Fourier
analysis. To see this, let $\chi$ denote a nontrivial additive character of
$\mathbb{F}_{q}.$ Then by the orthogonality of $\chi$, we see that if $x\neq
z,$ then

$\displaystyle\sum_{y\in\mathbb{F}_{q}^{d}:||x-y||=||z-y||}1$
$\displaystyle=q^{-1}\sum_{y\in\mathbb{F}_{q}^{d}}\sum_{s\in\mathbb{F}_{q}}\chi(s(||x-y||-||z-y||))$
$\displaystyle=q^{d-1}+q^{-1}\sum_{y\in\mathbb{F}_{q}^{d}}\sum_{s\neq
0}\chi(s(||x-y||-||z-y||)).$

Applying the orthogonality of $\chi$ to the sum over $y$, we see that the
second term above is zero since $\chi(s(||x-y||-||z-y||))=\chi(-2s(x-z)\cdot
y)\chi(s(||x||-||z||))$ and $s(x-z)$ is not a zero vector. Hence, the equation
(2.3) holds.

Finally, combining the above two estimates (2.2), (2.3), we obtain the
desirable estimate.

The following result can be obtained by the pigeonhole principle together with
Lemma 2.1.

######  Lemma 2.2.

Let $E\subseteq\mathbb{F}_{q}^{d}.$ Then for any $a>1,$ there exists
$Y\subseteq\mathbb{F}_{q}^{d}$ with $|Y|\geq\frac{a-1}{a}q^{d}$ such that for
every $y\in Y$,

$\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)\leq\frac{a}{q}|E|^{2}+\frac{a(q-1)}{q}|E|.$

###### Proof.

Let us fix $a>1.$ Define

$Y=\left\\{y\in\mathbb{F}_{q}^{d}:\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)\leq\frac{a}{q}|E|^{2}+\frac{a(q-1)}{q}|E|\right\\}.$

To complete the proof, it remains to show that

$|Y|\geq\frac{a-1}{a}q^{d}.$

By contradiction, let us assume that

(2.4) $|Y|<\frac{a-1}{a}q^{d}.$

It is clear that

(2.5) $\mathbb{F}_{q}^{d}\setminus
Y=\left\\{y\in\mathbb{F}_{q}^{d}:\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)>\frac{a}{q}|E|^{2}+\frac{a(q-1)}{q}|E|\right\\}.$

We also notice that for all $y\in\mathbb{F}_{q}^{d},$

(2.6)
$\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)\geq\sum_{t\in\mathbb{F}_{q}}\nu_{y}(t)=|E|.$

Now by Lemma 2.1, it follows that

(2.7)
$\frac{1}{q^{d}}\sum_{y\in\mathbb{F}_{q}^{d}}\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)=\frac{|E|^{2}}{q}+\frac{q-1}{q}|E|.$

However, we can also estimate it as follows. Using (2.5) and (2.6), we have

$\displaystyle\frac{1}{q^{d}}\sum_{y\in\mathbb{F}_{q}^{d}}\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)$
$\displaystyle=\frac{1}{q^{d}}\sum_{y\in
Y}\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)+\frac{1}{q^{d}}\sum_{y\in\mathbb{F}_{q}^{d}\setminus
Y}\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)$
$\displaystyle>\frac{1}{q^{d}}|Y||E|+\frac{1}{q^{d}}(q^{d}-|Y|)\left(\frac{a}{q}|E|^{2}+\frac{a(q-1)}{q}|E|\right)$
$\displaystyle=\frac{a|E|^{2}}{q}+\frac{a(q-1)|E|}{q}+\left(\frac{|E|}{q^{d}}-\frac{a|E|^{2}}{q^{d+1}}-\frac{a(q-1)|E|}{q^{d+1}}\right)|Y|.$

Since $a>1$, in the third term above, the coefficient of $|Y|$ is negative.
Hence, we can combine the above estimate with (2.4) to deduce that

$\frac{1}{q^{d}}\sum_{y\in\mathbb{F}_{q}^{d}}\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)>\frac{a|E|^{2}}{q}+\frac{a(q-1)|E|}{q}+\left(\frac{|E|}{q^{d}}-\frac{a|E|^{2}}{q^{d+1}}-\frac{a(q-1)|E|}{q^{d+1}}\right)\left(\frac{a-1}{a}q^{d}\right)$

Simplifying the RHS of the above equation, we get

$\frac{1}{q^{d}}\sum_{y\in\mathbb{F}_{q}^{d}}\sum_{t\in\mathbb{F}_{q}}\nu_{y}^{2}(t)>\frac{|E|^{2}}{q}+\frac{q-1}{q}|E|+\frac{a-1}{a}|E|,$

which contradicts the equation (2.7) since $a>1.$ ∎

###  2.2. Proof of Theorem 1.7

Combining (2.1) and Lemma 2.2, we get the required result:

$|\Delta_{y}(E)|\geq\frac{|E|^{2}}{\frac{a}{q}|E|^{2}+\frac{a(q-1)}{q}|E|}\geq\min\left\\{\frac{q}{2a},~{}\frac{q|E|}{2a(q-1)}\right\\}\geq\min\left\\{\frac{q}{2a},~{}\frac{|E|}{2a}\right\\}.$

## References

  * [1] M. Bennett, D. Hart, A. Iosevich, J. Pakianathan, and M. Rudnev, Group actions and geometric combinatorics in $\mathbb{F}_{q}^{d},$ Forum Math. 29 (2017), 91-110.
  * [2] J. Chapman, M. Erdog̃an, D. Hart, A. Iosevich, and D. Koh, Pinned distance sets, Wolff’s exponent in finite fields and sum-product estimates, Math.Z. 271, (2012), 63-93
  * [3] D. Hart, A. Iosevich, D. Koh and M. Rudnev, Averages over hyperplanes, sum-product theory in vector spaces over finite fields and the Erdös-Falconer distance conjecture, Trans. Amer. Math. Soc. Volume 363, Number 6, (2011), 3255–3275.
  * [4] B. Hanson, B. Lund, and O. Roche-Newton, On distinct perpendicular bisectors and pinned distances in finite fields, Finite Fields Appl. 37 (2016), 240-264.
  * [5] A. Iosevich, M. Rudnev, Erdős distance problem in vector spaces over finite fields, Trans. Amer. Math. Soc. 359 (2007), 6127-6142.
  * [6] B. Murphy, G. Petridis, T. Pham, M. Rudnev, and S. Stevenson, On the pinned distances problem in positive characteristic, to appear in Journal of London Mathematical Society, 2021, arXiv:2003.00510.
  * [7] G. Mockenhaupt, and T. Tao, _Restriction and Kakeya phenomena for finite fields_ , Duke Math. J. 121 (2004), 1, 35-74.
  * [8] M. Rudnev and I. Shkredov, _On the restriction problem for discrete paraboloid in lower dimension_ , Adv. Math. 339 (2018), 657-671.


# A Genetic Algorithm with Tree-structured Mutation for Hyperparameter
Optimisation of Graph Neural Networks

Yingfang Yuan  School of Mathematical
and Computer Sciences
Heriot-Watt University
Edinburgh, United Kingdom
<EMAIL_ADDRESS>Wenjun Wang  School of Mathematical
and Computer Sciences
Heriot-Watt University
Edinburgh, United Kingdom
<EMAIL_ADDRESS>Wei Pang* * Corresponding author School of Mathematical
and Computer Sciences
Heriot-Watt University
Edinburgh, United Kingdom
<EMAIL_ADDRESS>
###### Abstract

In recent years, graph neural networks (GNNs) have gained increasing
attention, as they possess the excellent capability of processing graph-
related problems. In practice, hyperparameter optimisation (HPO) is critical
for GNNs to achieve satisfactory results, but this process is costly because
the evaluations of different hyperparameter settings require excessively
training many GNNs. Many approaches have been proposed for HPO, which aims to
identify promising hyperparameters efficiently. In particular, the genetic
algorithm (GA) for HPO has been explored, which treats GNNs as a black-box
model, of which only the outputs can be observed given a set of
hyperparameters. However, because GNN models are sophisticated and the
evaluations of hyperparameters on GNNs are expensive, GA requires advanced
techniques to balance the exploration and exploitation of the search and make
the optimisation more effective given limited computational resources.
Therefore, we proposed a tree-structured mutation strategy for GA to alleviate
this issue. Meanwhile, we reviewed the recent HPO works, which gives room for
the idea of tree-structure to develop, and we hope our approach can further
improve these HPO methods in the future.

###### Index Terms:

generic algorithm, tree-structured mutation, graph neural network,
hyperparameter optimisation

††publicationid: pubid: 978-1-7281-8393-0/21/$31.00 ©2021 IEEE

##  I Introduction

Graph is a data type used to describe the structured objects consisting of
nodes and edges, such as citation networks, molecules, and road networks. In
graph-related learning and prediction problems, traditional machine learning
methods require using feature engineering to process graph data before
training or prediction [1]. In contrast, graph neural networks (GNNs) are
proposed to directly operate on graphs to solve graph-related problems in an
end-to-end manner [1]. GNNs exploit neural networks to model graphs and
perform representation learning, which requires that GNNs are set with
appropriate hyperparameters (e.g., learning rate, the number of neural network
layers) to control the learning process. From our perspective, more
sophisticated neural architectures are required to process graph data, which
may result in challenging HPO tasks for GNNs. Falkner et al. [2] pointed out
that deep learning algorithms are very sensitive to many hyperparameters. The
work presented in [3] demonstrated that HPO for GNNs is vital for achieving
satisfactory results in practice. Therefore, research on effective HPO
approaches for GNNs is critical and of great value for GNN applied to various
real-world problems.

In brief, HPO is a trial-and-error process to obtain optimal solutions via
iteratively generating and evaluating hyperparameter settings until the preset
stopping condition(s) are satisfied. Commonly, the objective function of GNNs
is selected as the fitness function of HPO to evaluate hyperparameters.
However, the evaluation is often very expensive because training GNN models
would take a lot of computational resources. On the other hand, with the
development of deep learning, neural networks have an increasing number of
layers or various other optional hyperparameters (e.g., activation functions,
optimisation methods), which results in a large search space and increasing
the difficulty of HPO. So, existing works of HPO have been conducted based on
the issues of how to find the best solutions with fewer trials, reducing
evaluation cost, and improving the capability of exploration. In this paper, a
trial denotes a complete process of evaluating a hyperparameter setting
(solution) on the fitness function (objective function).

There are many state-of-the-art HPO approaches with different search
strategies. For example, TPE [4] and BOHB [2] are proposed based on Bayesian
optimisation (BO) which are suitable for the functions that are expensive to
evaluate. However, the former uses density functions to model two sets (good
and bad) of hyperparameters, instead of using Gaussian process as in [5, 6] as
a standard surrogate model to approximate the distribution over the objective
function. Furthermore, BOHB combines Bayesian optimisation and bandit-based
methods to ensure good performance at anytime and speed up the process towards
optimal solutions. In general, BO-based methods balance the exploration and
exploitation by acquisition function. On the contrary, CMA-ES [7] and HESGA
[3] are evolutionary approaches that exploit high-quality individuals to guide
the generation of promising offspring, while they rely on evolutionary
operators to explore search space. CMA-ES employs an adaptive multivariate
distribution to sample individuals, and HESGA uses a genetic algorithm that
relies on crossover and mutation operators to generate better individuals. To
deepen the work of HESGA [3], our research focuses on improving the
exploration capability of the mutation operator.

Genetic algorithm with hierarchical evaluation strategy (HESGA) [3] utilises
the elite archive to preserve excellent individuals, from which a parent can
be selected to generate offspring. Meanwhile, the fast evaluation strategy has
been introduced in HESGA to speed up optimisation and save computational
resources. Furthermore, HSEGA uses the single point mutation as in [8, 9, 10]
which is one factor for preventing GA from getting stuck in local optima and
maintains the diversity of population [11]. However, we believe that the
mutation operation in HSEGA can be further explored as only classical mutation
operation was used in HSEGA. Therefore, in this research, we propose a tree-
structured mutation (TSM) which employs the tree structure to store
hierarchical historical information to guide mutation. In this way, GA can
explore the whole search space more adaptively and effectively. Meanwhile, the
idea of TSM is also compatible and scalable to other HPO algorithms that
hierarchise historical information for future discovery.

Our contributions are summarised as follows:

  * •

We have developed a tree-structured mutation operation for GA to adaptively
maintain the balance between exploration and exploitation for searching the
hyperparameter space of GNNs while retaining the randomness of mutation
operator.

  * •

We conducted a review of advanced HPO methods, and we found that the tree-
structured approach has the potential to be integrated into other approaches.

  * •

Our research contributes to the development of molecular machine learning [12]
as well as HPO for GNNs in general.

The rest of this paper is organised as follows. Section II introduces relevant
work on HPO. In Section III, the details of our tree-structured mutation are
presented. The experiments are reported and the results are analysed in
Section IV. Finally, Section V concludes the paper and explores some
directions in future work.

##  II Related Work

In this section, we will first review some popular HPO methods. The genetic
algorithm with hierarchical evaluation strategy (HESGA) [3] will then be
introduced because our tree-structured mutation is proposed upon it. Finally,
some mutation strategies will be reviewed.

###  II-A Hyperparameter Optimisation Methods

There have been a lot of state-of-the-art HPO methods, and these methods can
be classified into black-box optimisation and multi-fidelity optimisation
approaches [13]. The former focus on the effectiveness of the search
algorithms and the latter focuses on efficiently using computational resources
in search algorithms [14, 15, 16].

Black-box optimisation [17, 18] implies that the details of the objective
function and its gradient information is unknown during searching optimal
solutions. In HPO, hyperparameters can be evaluated on the objective function,
but we do not have access to any information about the model. Random search
[19] and grid search are two simple and commonly used methods for HPO.
Bergstra et al. [4] hold the point that random search is more efficient than
grid search given a fixed limited computation budget for HPO. However, facing
the problems with expensive evaluations, it is very challenging for random
search and grid search to achieve satisfactory performance.

The use of Bayesian optimisation (BO) can alleviate the issue of high
computational cost [14, 18]. The framework of BO is concluded in the
sequential model-based algorithm [20] that iteratively exploits historical
data to fit surrogate models or other transformations, while the most
promising candidate is drawn according to a predefined criterion (i.e.
acquisition function). The work presented in [4, 6, 5, 21] makes use of
Gaussian processes (GPs) to approximate the distribution over the objective
function, and the candidate is selected by the acquisition function:
probability of improvement (PI) or expected improvement (EI). In contrast, TPE
[4] employs Parzen estimators as a surrogate to directly model promising and
unpromising hyperparameters, and the candidate solutions are drawn according
to EI that is proportional to the ratio of two density functions. During
searching optimal solutions, the acquisition function plays a significant role
in balancing exploration and exploitation.

Furthermore, evolutionary computation has demonstrated the capability of
solving HPO problems [22, 23, 7, 3]. CMA-ES [7] imitates the biological
evolution, assuming that no matter what kind of gene changes, the results
(traits) always follow a Gaussian distribution of a variance and zero-mean.
Meanwhile, the generated population is evaluated on the objective function,
and a portion of the individuals with excellent performance is selected to
suggest evolution, moving to the area where better individuals would be drawn
with higher probability.

Successive halving [24] is a bandit-based multi-fidelity method for
efficiently allocating computational resource that gives the most budget to
the most promising individuals. Meanwhile, successive halving is an iterative
process in which the best half of individuals are retained, and half of the
individuals with lower performance are discarded when a portion of the total
computational resource runs out. Hyperband [25] and BOHB [2] are proposed
based on the successive halving, but the former proposed a modification that
frequently performs the successive halving method with different budget
allocations to find the best solutions. Li et al. [25] pointed out that
because the terminal losses are unknown, the trials of different allocations
are helpful to recognise high-quality solutions. For example, two individuals
might not have a significant difference on fitness in the $30^{th}$ epoch, but
a greater difference may be observed in the $50^{th}$ epoch if more
computational resources (i.e., epochs) are allocated. Furthermore, BOHB
combines Hyperband and BO to chase an ideal state in which performance and
computational cost are both covered.

###  II-B Genetic Algorithm

Genetic algorithm (GA) is a class of evolutionary computation has been applied
to HPO [26, 27, 3]. GA evaluates the qualities of individuals in the
population by using a fitness function. To search for high-quality
individuals, GA relies on crossover, mutation, and selection operators. The
selection is inspired by natural selection, which means GA selects individuals
as parents according to the probabilities (e.g., roulette wheel) to generate
next-generation by crossover and mutation, and the probabilities are
proportional to their quality (fitness). There are many crossover techniques
such as uniform crossover [28], single-point [29], and heuristic crossover
[30]; they aim to recombine genes from the parents to generate offspring. In
the evolutionary process, mutation operators as the last step are generally
assigned with a low probability to be invoked. However, it plays a significant
role for preventing GA from getting stuck in local optima. Similar to the
probabilistic sampling of solutions in BO-based optimisation, the mutation is
employed to endue GA with the exploration capability of solutions.

Variable length genetic algorithm [31] has been proposed to solve neural
network HPO problem by increasing the length of the chromosome (i.e., enlarge
search space) if the fitness does not satisfy preset conditions. Moreover,
HESGA [3] introduced the elite archive mechanism that stores some current
optimal individuals. According to the roulette wheel, parents are selected
from the elite archive and the population (Fig. 1). In this way, new offspring
always own at least a portion of the strong genes from the parent in the elite
archive if crossover occurs. Meanwhile, HESGA provides the strategy of using
fast and full evaluation methods, to alleviate the expensive evaluations. Fast
evaluation is applied to the whole population. The individuals with the most
difference of fitness in the early training stage (10% $\sim$ 20% of the total
epochs) are considered promising, and it assumes that individuals with a
steeper learning curve have more significant potential to achieve satisfactory
results. Meanwhile, the full evaluation is employed to measure a small portion
of individuals selected by fast evaluation. The fast and full evaluation can
be considered multi-fidelity optimisation, which focuses on decreasing the
evaluation cost by combining many low cost evaluations with low-fidelity and a
small number of costly evaluation with high-fidelity.

###  II-C Mutation

Many mutation strategies have been proposed for GA, and we only present some
of them which are related to our research. Random (uniform) mutation and non-
uniform mutation have been proposed in [32]. In random mutation, where a gene
is replaced with a random value drawn from a defined range. On the other hand,
in non-uniform mutation, the strength of mutation decreases along with the
increasing number of generations. In adaptive mutation [33, 34], each solution
is assigned with a mutation rate to maintain the diversity of the population
without affecting algorithm performance. Based on Gaussian mutation, self-
adaptive mutation [35] allows GA to vary the mutation strength during the
evolution, while self-adaptive Gaussian mutation based adaptation of
population size is proposed in [36]. In Pointed directed (PoD) mutation [37],
each gene is tightly associated with a single bit that guides the direction of
mutation which the gene may follow. Compared with Gaussian mutation, Deep et
al. [38] reported that PoD mutation is more advantageous in unconstrained
benchmark problems. The above mentioned mutation operators exploit the
historical information which is generated during evolution to adjust the
mutation strategy dynamically, which inspired our TSM to improve the naive
single point mutation used in [3].

##  III Method

In this section, the design of tree-structured mutation (TSM) will be
described. Meanwhile, we will introduce the use of TSM in HESGA.

###  III-A HESGA

Figure 1: Genetic Algorithm with Hierarchical Evaluation Strategy [3] Figure
2: Binary Crossover and Mutation [3]

The framework of HESGA [3] is shown in Fig. 1. The TSM is proposed as a
further improvement of HESGA. The original HESGA uses the binary encoding
scheme for hyperparameters on HPO: each hyperparameter is assigned with a
fixed-length binary code with a step size (i.e., resolution). For example, if
the batch size ranges from 8 to 512 with a step size of 8, and then a batch
size of 16 is represented by $[0,0,0,0,0,0,1]$. Single point crossover and
mutation are employed in HESGA. Fig. 2 shows that both the mutation and
crossover are implemented by a uniform distribution to randomly generate a
position $p$ at first. The bits on the right of the point $p$ are swapped
between the two parent chromosomes for the crossover, and the bit on the
position $p$ changes the value from 0 to 1, or vice versa for mutation. In
initialisation, all randomly generated individuals are assessed by full
evaluation, and some individuals with higher fitness values are selected to be
included in the elite archive by Step (1) and (2) as shown in Fig. 1. To
update the elite archive, the offspring is generated by operating crossover
and mutation on the two parents that are respectively selected by roulette
wheel from the elite archive and population in Steps (3), (4) and (5). Then,
in Step (6), fast evaluation is operated to find a small number of individuals
(candidates) which have better fitness values, and these individuals are
further accessed by full evaluation in Step (8). The elite archive is updated
if candidates are better than some of the individuals in the elite archive in
Step (9). The work presented in [3] demonstrated that HESGA had achieved
satisfactory performance on HPO for GNNs.

###  III-B Tree-structured Mutation

Figure 3: Tree-structured hyperparameter space, the internal nodes of
$s,l,f,n$ represent the different hyperparameters and used to define their
hyperparameter subspace with different subscripts, such as $s_{0}$ and $s_{1}$
respectively correspond to lower and upper portion of the hyperparameter $s$.
$n_{s}$ denotes the maximum width of the tree and $n_{h}$ is the dimension of
hyperparameter settings

In HPO using GA, the mutation operator is a way for GA to explore the
hyperparameter search space. All mutation operators discussed in Section II-C
are proposed based on the core principle of effective mutation towards optimal
solutions. Most of the black-box optimisation methods utilise historical
information to carry out effective exploration. Here, back to GA, we expect
that the historical information can also be exploited with the tree to suggest
mutations.

Considering that TPE [4] used tree structure to model the sampling of
hyperparameter settings, we propose to employ a binary tree to build the
hierarchical search space, as shown in Fig. 3. Each pathway from the root node
to a leaf node represents a subspace of the whole hyperparameter space. For
example, from root to node $c_{0}$, the child nodes
($s_{0},l_{0},f_{0},n_{0}$) define the corresponding ranges of hyperparameters
(batch size, learning rate, the size of graph convolution layer, and the size
of fully-connected layer), which forms a subspace of the whole search space
and can be represented by a binary string $0000$. Meanwhile, the left and
right child nodes define the lower and higher ranges of hyperparameters by
thresholds. For example, if $s$ ranges from $8$ to $512$, the median value
$256$ is chosen as the threshold to give two subspace with the same size.
$s_{0}$ indicate a range from $8$ to $255$ and $s_{1}$ ranges from $256$ to
$512$. In this way, the whole search space is divided into many subspaces, and
the number of subspaces equals the total number of leaf nodes $c$ (i.e., the
maximum width ${n_{s}}$), or the square of the dimension of hyperparameter
settings ${n_{h}}^{2}$, where $n_{h}$ is also the maximum depth of the tree
without leaf nodes.

To use the tree to suggest mutations, the internal and leaf nodes take the
responsibility to record historical information. The internal nodes are used
to store the times of mutation that occurred on different dimensions in a
subspace. Concurrently, a leaf node $c$ is used to record the times of a
subspace that has been visited. For example, when a hyperparameter setting
$\lambda$ sampled from the subspace ($s_{0},l_{0},f_{0},n_{0}$) has been
evaluated on an objective function, the value of node $c_{0}$ will increase by
1. If $\lambda$ underwent a mutation on batch size, then the counter in the
$s_{0}$ node will increase by 1. In this way, the whole search space is
hierarchised which increase the ability of exploration for mutation.

In this research, based on the framework of HESGA, we use TSM to replace the
single point mutation, considering that a more sophisticated mutation may lead
to better performance. We observed that there might exist the same individuals
in elite archive and populations that waste computational resources for
evaluating them during the experiments. Many reasons may lead to this issue.
For example, an extremely excellent individual in the population will be
selected to be included in the elite archive while outperforms other
individuals in the elite archive; it means this individual has a higher
probability of being selected as both Parent A and B in the next generation.
Two identical parents will invalid crossover by which the same individuals
will be generated. To solve this issue, we set the condition in Step (5.2)
(Fig. 4) to prohibit duplicates. If the duplication is detected, the mutation
is forcibly invoked. Based on TSM, we use two strategies: TSM with a given
individual and TSM without a given individual respectively for the situation:
mutation is invoked with preset probability in Steps (5.1 and 5.2) and force
mutation when duplicates are detected in Steps (5.3 and 5.4), as shown in Fig.
4.

Figure 4: Genetic Algorithm with Hierarchical Evaluation Strategy with TSM
mutation

####  III-B1 TSM with A Given Individual

HESGA operates the single point mutation with the probability of 0.2, as
indicated by Step (5) in Fig. 1. TSM is also invoked with the same probability
in Step (5.1) in Fig. 4. TSM uses historical information recorded in the tree
to generate a probability distribution to guide the mutation compared with the
change of a bit of binary encoding under a uniform distribution. Specifically,
when mutation is activated, for the individual concerned, its corresponding
subspace (i.e., pathway) along the tree will be identified. In that pathway,
the times $t$ of previously occurred mutation respectively according to the
mutated position stored in the internal nodes will be given to Equation (1) to
compute probabilities. In Equation (1), $i$ is the depth of an internal node
given pathway $p$, and $t_{i}$ represents the times recorded in that node. $f$
is a reciprocal function, $j$ are the depth of all internal nodes (e.g.,
$n_{1}$ with depth 4, $f_{0}$ with depth 3, $l_{0}$ with depth 2, and $s_{0}$
with depth 1 ) in pathway $p$, and $t_{j}$ is the times stored in those nodes
respectively. The probabilities will determine where the mutation happens
following the roulette wheel method, and the mutated individual will be used
to update the tree to determine future mutation. In this way, in a subspace,
the dimension that has been previously explored frequently will have less
probability to be explored in the future. When the dimension is sampled, the
new value is drawn from the search space defined in that node by the uniform
distribution. For example, when $s_{0}$ is selected, a new value from 8 to 255
with the resolution of 8 will be drawn and converted into binary coding to
replace the original fragment. The TSM with a given individual is summarised
in Algorithm 1.

$\mathcal{P}\left(t_{i}\right)=\frac{f\left(t_{i}\right)}{\sum_{j=1}^{n_{h}}f\left(t_{j}\right)}\
i,j\in\\{1,2,...,n_{h}\\},\text{given~{}}p.$ (1)

Algorithm 1 TSM with A Given Individual

1:Input an individual $s$, $tree$, $t=[~{}]$

2:$p$ = $tree(s)$ $\triangleright$ pathway $p$ identification in tree

3:for $j=1$ $\rightarrow$ $n_{h}$ do $\triangleright$ in pathway $p$, the
maximum depth of tree without leaf nodes $n_{h}$

4: $t_{total}+=f\left(t_{j}\right)$ $\triangleright$ $t_{j}$ denotes the times
recorded in node $j$, $f$ is reciprocal function

5: $t$.append($f(t_{j})$)

6:end for

7:$t^{\prime}$ $\leftarrow$ each element in $t$ is divided by $t_{total}$

8:$i$ = $rws$($n_{h}$, $t^{\prime}$) $\triangleright$ node $i$, $rws$ roulette
wheel selection

9:$r\leftarrow$ the defined value range in node $i$

10:$v=uniform(r)$ $\triangleright$ mutated value $v$

11:$s^{\prime}$ $\leftarrow$ $s_{i}$ is replaced with $binary(v)$
$\triangleright$ for $s$, $s_{i}$ the fragment of binary coding for mutation

12:Output individual $s^{\prime}$

####  III-B2 TSM without A Given Individual

To avoid duplicated individuals existing in the elite archive, in Fig. 1, Step
(9) is added with a duplication detection mechanism. The duplicates will be
deleted except the one with the best fitness value (in our experiments, there
exist fluctuations when evaluating the same hyperparameter settings due to the
randomness in the GNN training and evaluation process). Meanwhile, if the
duplicates are found in the population, we will take TSM without a given
individual (shown in Fig. 4, Steps (5.3 and 5.4)) to generate a new individual
to replace them. TSM with a given individual is also feasible to deal with the
duplication issue, but here we proposed the TSM without a given individual to
increase the population diversity.

Similar to Algorithm 1, TSM without a given individual (Algorithm 2) also
exploits the information stored in the tree and follows the roulette wheel to
select mutation points. However, the latter selects a subspace to sample new
individuals (mutated ones) rather than given a subspace to select a dimension
to mutate. Practically, the mutation starts by computing the probabilities of
each subspace by Equation 2, where $c$ are the indexes of leaf nodes, $n_{s}$
is the total number of leaf nodes (i.e., maximum width), $f$ is the reciprocal
function. Each leaf node corresponds to a subspace, and the times of a
subspace being explored is recorded on it. Eq. (2) indicates that the subspace
with a large number of $t$ will have less probability to be explored by
mutation. In this way, exploitation can be achieved by crossover and elite
archive, and exploration is facilitated by mutations. The pseudo-code is shown
in Algorithm 2.

$\mathcal{P}\left(t_{i}\right)=\frac{f\left(t_{i}\right)}{\sum_{c=1}^{n_{s}}f\left(t_{c}\right)}\
i,c\in\\{1,2,3...n_{s}\\},\text{given leaf nodes}.$ (2)

Algorithm 2 TSM without A Given Individual

1:Input $tree$, $t=[~{}]$

2:for $c=1$ $\rightarrow$ $n_{s}$ do

3: $t_{total}+=f\left(t_{c}\right)$ $\triangleright$ $t_{c}$ denotes the times
recorded in node $c$, $f$ is reciprocal function

4: $t$.append($f(t_{c})$)

5:end for

6:$t^{\prime}$ $\leftarrow$ each element in $t$ is divided by $t_{total}$

7:$i$ = roulette wheel($n_{s}$, $t^{\prime}$) $\triangleright$ subspace $i$

8:$v=[~{}]$

9:for $j=1$ $\rightarrow$ $n_{h}$ do $\triangleright$ in subspace $i$

10: $r_{j}\leftarrow$ the defined value range in node with depth $j$

11: $v_{j}=uniform(r_{j})$ $\triangleright$ mutated value $v_{j}$ by sampling
from a uniform distribution given range $r_{j}$

12: $v$.append$(binary(v_{j}))$

13:end for

14:$s$ = $v$

15:Output individual $s$

##  IV Experiments

To assess the effectiveness of TSM, we conducted the experiments to compare
HESGA with single-point mutation [3] and HESGA equipped with TSM. The HESGA in
our experiments is modified to reject duplication, and the duplicates found in
the population will be forcibly re-sampled by TSM without a given individual
(as mentioned in Section III-B) or single-point mutation. The settings of
HESGA are as follows: the max generation is set to 10, the probabilities of
crossover and mutation are 0.8 and 0.2, which are the same as the original
experimental settings [3]. Meanwhile, the proportion of the size of elite
archive to the population size is 0.5, as considering that 0.1 may lead to the
selection pressure.

Our experiments have been conducted on three benchmark datasets: ESOL,
FreeSolv, and Lipophilicity from [12]. They are three molecular property
prediction datasets that are used to assess the performance of GNNs.
Meanwhile, there are many types of GNN algorithms, but the neural fingerprint
graph model (GC) [39] has been selected because it was proposed to be used for
molecular machine learning. GC exploits the neural architectures to model
circular fingerprint [40] for learning the molecular representations for
prediction tasks. There are four hyperparameters selected for HPO, including
$s_{b}$ (batch size), $l_{r}$ (learning rate), $s_{g}$ (the size of graph
convolution layer), and $s_{f}$ (the size of fully-connect layer); the search
space is constructed as follows: the range of $s_{b}$ is $8\sim 512$ with step
size 8, the range of $l_{r}$ is $0.0001\sim 0.0032$ with step size 0.0001, the
range of $s_{g}$ is 8 $\sim$ 512 with step size 8, and the range of $s_{f}$ is
32 $\sim$ 1024 with step size 32. As mentioned in Section III-B, TSM requires
thresholds to divide the whole search space into many subspace, and we uses
the median values of $s_{b}$, $l_{r}$, $s_{g}$, and $s_{f}$, which are 256,
0.0016, 256, and 512, respectively to build the binary tree in experiments.

As in [3], the root mean square error (RMSE) of GC is used as the fitness
function for HPO, and it is also used to measure the HPO performance. The best
hyperparameter setting found by an HPO method (HESGA and HESGA+TMS) will be
given to GC to run 30 times, and the mean of the 30 RMSEs are used to measure
the performance of HPO. Meanwhile, in order to make the comparisons more
convincing, $t$-test with a significance level of two tails 10% is employed to
compare the performance of HESGA and HESGA + TSM and see if there exists a
significant difference. In $t$-test, negative $t$ value and the hypothesis
$h=1$ indicates that HESGA outperforms HESGA+TSM; positive $t$ value and the
hypothesis $h=1$ indicates that HESGA+TSM significantly outperform HESGA; or
$h=0$ (the null hypothesis) means that there is no significant difference
between HESGA and HESGA+TSM.

In the experiments on ESOL (Table I), HESGA+TSM has a smaller mean and
standard deviation of RMSEs than HESGA. However, there is no significant
difference between HESGA and HESGA+TSM at the significance level
$\alpha=10\%$. We considered that the size of the ESOL dataset constrains the
performance of HESGA+TSM, because a sufficient amount of data is a
prerequisite for GC possessing better performance with a more complex
architecture. In Table I, HESGA+TSM found larger $s_{g}$ and $s_{f}$, which
means the GC with more parameters, and they require more training data to tune
them for better performance. Furthermore, if we set the significance level
$\alpha=20\%$, HESGA+TSM outperforms HESGA in the validation data set.
Meanwhile, it is obvious that two hyperparameter settings are completely
different and come from different two subspaces, which indicates the complex
and multi-modal nature of the underlying hyperparameter search space, and the
discovery in different subspaces is meaningful.

In the experiments on FreeSolv (Table II), HESGA presents better performance
than HESGA+TSM. FreeSolv is the smallest dataset used in our experiments. The
small size of the dataset is intrinsically challenging for GC to learn and
keep a stable performance, which may lead to the underperformance of HESGA+TSM
since its strength is exploration, stable and accurate feedback (i.e., the
results of evaluation on GC) is essential for conducting efficient
exploration.

Furthermore, when duplicates appear in the population, HESGA uses single-point
mutation which retains most of the genes from parents, and relatively speaking
the strength of the mutation is small, while HESGA+TMS is guided by the tree-
based mutation, which explores the search space more broadly compared with
HESGA. Therefore, we considered that when the size of a dataset is relatively
small, global exploration may bring more fluctuation and unknown factors upon
the instability of GC, which brings more difficulties to the problems. In
contrast “local” exploration might be more effective since it reduces the
underlying unknown risks from the global area.

In contrast, Lipophilicity is the largest dataset in our experiments, and as
shown in Table III, HESGA+TSM outperforms HESGA in this dataset with a
significant difference, and lower standard deviation means the result of
HESGA+TSM is more stable. When the size of dataset increased, the full
evaluation becomes more accurate, and it provides more helpful information for
GA to generate strong offspring in terms of exploitation. Meanwhile, more
effective exploration becomes necessary, and HESGA+TSM shows better
performance because TSM uses historical information to search hyperparameter
space rather than search each part of the hyperparameter space with equal
probability.

TABLE I: The Results on ESOL Dataset ESOL | Hyperparameters | Train | Validation | Test |
---|---|---|---|---|---
HESGA |  $s_{b}$=64 | 0.2847 | 0.8843 | 0.8862 | Mean RMSE
$l_{r}$=0.0028
$s_{g}$=304 | 0.0424 | 0.0509 | 0.0506 | Mean STD
$s_{f}$=64
HESGA \+ TSM |  $s_{b}$=48 | 0.2734 | 0.86585 | 0.8743 | Mean RMSE
$l_{r}$=0.0012
$s_{g}$=320 | 0.0333 | 0.0357 | 0.0463 | Mean STD
$s_{f}$=320
|  $t$-test on results
---
with significance level of $\alpha=10\%$
$t=1.1249,~{}h=0~{}~{}$ | $t=1.5963,~{}h=0~{}~{}$ | $t=0.9311,~{}h=0~{}~{}$ |
TABLE II: The Results on FreeSolv Dataset FreeSolv | Hyperparameters | Train | Validation | Test |
---|---|---|---|---|---
HESGA |  $s_{b}$=24 | 0.5498 | 1.0970 | 1.0370 | Mean RMSE
$l_{r}$=0.0030
$s_{g}$=208 | 0.1251 | 0.1199 | 0.1246 | Mean STD
$s_{f}$=224
HESGA \+ TSM |  $s_{b}$=8 | 1.1181 | 1.4083 | 1.3508 | Mean RMSE
$l_{r}$=0.0010
$s_{g}$=480 | 0.2692 | 0.2408 | 0.2874 | Mean STD
$s_{f}$=576
|  $t$-test on results
---
with significance level of $\alpha=10\%$
$t=-10.3063,h=1$ | $t=-6.2298,h=1$ | $t=-5.3940,h=1$ |
TABLE III: The Results on Lipophilicity Dataset Lipophilicity | Hyperparameters | Train | Validation | Test |
---|---|---|---|---|---
HESGA |  $s_{b}$=136 | 0.3656 | 0.7402 | 0.7293 | Mean RMSE
$l_{r}$=0.0031
$s_{g}$=232 | 0.0881 | 0.0476 | 0.0462 | Mean STD
$s_{f}$=1024
HESGA \+ TSM |  $s_{b}$=168 | 0.2390 | 0.6962 | 0.7021 | Mean RMSE
$l_{r}$=0.0011
$s_{g}$=304 | 0.0676 | 0.0284 | 0.0269 | Mean STD
$s_{f}$=864
|  $t$-test on results
---
with significance level of $\alpha=10\%$
$t=6.1358,~{}h=1~{}~{}$ | $t=4.2642,~{}h=1~{}~{}$ | $t=2.7381,~{}h=1~{}~{}$ |

##  V Conclusion and Future Work

In this paper, we proposed TSM for genetic algorithm as applied to HPO of
GNNs, which improved the performance of HESGA on the largest dataset in our
experiments. Compared with operating HPO on a relatively small dataset, the
achieved improvement of HPO performance on the larger dataset is more
meaningful since the evaluations are more expensive. Meanwhile, the research
of GA-based HPO for GNN is in an early stage; our work will help other
researchers to better explore this area. On the other hand, our research
contributes to the development of molecular machine learning, which may
facilitate the research from the relevant domain such as materials science,
biology and drug discovery. Furthermore, the idea of utilising tree structure
to hierarchise search space and record the historical information can be
applied to other HPO methods. Finally, in future, we believe more research can
be done along further developing TSM for evolutionary HPO. We list some
potential directions as follows.

###  V-A Reward and Rejection Mechanism

Currently, the inner and leaf nodes are used to store the times of previous
exploration. Inspired by reinforcement learning [41], the results of
evaluations on fitness function can be recorded as rewards with the times
together to affect future discovery by reconstructing Eqs. (1) and (2), and in
this way, TSM is not only for increasing the exploration ability, but also for
improving the exploitation in the later stage by introducing a reward
mechanism. Meanwhile, the times and rewards can also work together in a
surrogate model to reject those unpromising trials according to historical
information.

###  V-B Adaptive Threshold

In TSM, the binary tree requires thresholds to be specified to generate child
nodes. In our experiments, we choose median values as thresholds. However, it
is easy to observe that $s_{b}$ in all experiments are from the lower range
(i.e. the left child node). If the thresholds are adaptive and can be updated
by the rewards referring to the percentile in TPE [4], TSM may be further
improved to better focus on adaptively adjusted subspace.

## ACKNOWLEDGMENTS

This research is supported by the Engineering and Physical Sciences Research
Council (EPSRC) funded Project on New Industrial Systems: Manufacturing
Immortality (EP/R020957/1). The authors are also grateful to the Manufacturing
Immortality consortium.

## Data Statement

All data used in our experiments are from MoleculeNet [12], which are publicly
available in http://moleculenet.ai/datasets-1.

## References

  * [1] J. Zhou, G. Cui, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun, “Graph neural networks: A review of methods and applications,” _arXiv preprint arXiv:1812.08434_ , 2018.
  * [2] S. Falkner, A. Klein, and F. Hutter, “Bohb: Robust and efficient hyperparameter optimization at scale,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 1437–1446.
  * [3] Y. Yuan, W. Wang, G. M. Coghill, and W. Pang, “A novel genetic algorithm with hierarchical evaluation strategy for hyperparameter optimisation of graph neural networks,” _arXiv preprint arXiv:2101.09300_ , 2021.
  * [4] J. Bergstra, R. Bardenet, Y. Bengio, and B. Kégl, “Algorithms for hyper-parameter optimization,” in _25th annual conference on neural information processing systems (NIPS 2011)_ , vol. 24. Neural Information Processing Systems Foundation, 2011.
  * [5] J. Snoek, H. Larochelle, and R. P. Adams, “Practical bayesian optimization of machine learning algorithms,” _arXiv preprint arXiv:1206.2944_ , 2012.
  * [6] R. Martinez-Cantin, “Bayesopt: a bayesian optimization library for nonlinear optimization, experimental design and bandits.” _J. Mach. Learn. Res._ , vol. 15, no. 1, pp. 3735–3739, 2014.
  * [7] N. Hansen, “The cma evolution strategy: A tutorial,” _arXiv preprint arXiv:1604.00772_ , 2016.
  * [8] K. Deb, R. B. Agrawal _et al._ , “Simulated binary crossover for continuous search space,” _Complex systems_ , vol. 9, no. 2, pp. 115–148, 1995.
  * [9] S. M. Lim, A. B. M. Sultan, M. N. Sulaiman, A. Mustapha, and K. Y. Leong, “Crossover and mutation operators of genetic algorithms,” _International journal of machine learning and computing_ , vol. 7, no. 1, pp. 9–12, 2017.
  * [10] D. Whitley, “A genetic algorithm tutorial,” _Statistics and computing_ , vol. 4, no. 2, pp. 65–85, 1994.
  * [11] S. Mirjalili, “Genetic algorithm,” in _Evolutionary algorithms and neural networks_. Springer, 2019, pp. 43–55.
  * [12] Z. Wu, B. Ramsundar, E. N. Feinberg, J. Gomes, C. Geniesse, A. S. Pappu, K. Leswing, and V. Pande, “Moleculenet: a benchmark for molecular machine learning,” _Chemical science_ , vol. 9, no. 2, pp. 513–530, 2018.
  * [13] R. Elshawi, M. Maher, and S. Sakr, “Automated machine learning: State-of-the-art and open challenges,” _arXiv preprint arXiv:1906.02287_ , 2019.
  * [14] J. Wu, S. Toscano-Palmerin, P. I. Frazier, and A. G. Wilson, “Practical multi-fidelity bayesian optimization for hyperparameter tuning,” in _Uncertainty in Artificial Intelligence_. PMLR, 2020, pp. 788–798.
  * [15] Y. Yang and P. Perdikaris, “Conditional deep surrogate models for stochastic, high-dimensional, and multi-fidelity systems,” _Computational Mechanics_ , vol. 64, no. 2, pp. 417–434, 2019.
  * [16] Y.-Q. Hu, Y. Yu, W.-W. Tu, Q. Yang, Y. Chen, and W. Dai, “Multi-fidelity automatic hyper-parameter tuning via transfer series expansion,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, no. 01, 2019, pp. 3846–3853.
  * [17] D. Golovin, B. Solnik, S. Moitra, G. Kochanski, J. Karro, and D. Sculley, “Google vizier: A service for black-box optimization,” in _Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining_ , 2017, pp. 1487–1495.
  * [18] K. Kandasamy, K. R. Vysyaraju, W. Neiswanger, B. Paria, C. R. Collins, J. Schneider, B. Poczos, and E. P. Xing, “Tuning hyperparameters without grad students: Scalable and robust bayesian optimisation with dragonfly,” _Journal of Machine Learning Research_ , vol. 21, no. 81, pp. 1–27, 2020\.
  * [19] J. Bergstra and Y. Bengio, “Random search for hyper-parameter optimization.” _Journal of machine learning research_ , vol. 13, no. 2, 2012.
  * [20] F. Hutter, H. H. Hoos, and K. Leyton-Brown, “Sequential model-based optimization for general algorithm configuration,” in _International conference on learning and intelligent optimization_. Springer, 2011, pp. 507–523.
  * [21] J. Wu, X.-Y. Chen, H. Zhang, L.-D. Xiong, H. Lei, and S.-H. Deng, “Hyperparameter optimization for machine learning models based on bayesian optimization,” _Journal of Electronic Science and Technology_ , vol. 17, no. 1, pp. 26–40, 2019.
  * [22] I. Loshchilov and F. Hutter, “Cma-es for hyperparameter optimization of deep neural networks,” _arXiv preprint arXiv:1604.07269_ , 2016.
  * [23] P. R. Lorenzo, J. Nalepa, L. S. Ramos, and J. R. Pastor, “Hyper-parameter selection in deep neural networks using parallel particle swarm optimization,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2017, pp. 1864–1871.
  * [24] K. Jamieson and A. Talwalkar, “Non-stochastic best arm identification and hyperparameter optimization,” in _Artificial Intelligence and Statistics_. PMLR, 2016, pp. 240–248.
  * [25] L. Li, K. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar, “Hyperband: A novel bandit-based approach to hyperparameter optimization,” _The Journal of Machine Learning Research_ , vol. 18, no. 1, pp. 6765–6816, 2017.
  * [26] C. Di Francescomarino, M. Dumas, M. Federici, C. Ghidini, F. M. Maggi, W. Rizzi, and L. Simonetto, “Genetic algorithms for hyperparameter optimization in predictive business process monitoring,” _Information Systems_ , vol. 74, pp. 67–83, 2018.
  * [27] J.-H. Han, D.-J. Choi, S.-U. Park, and S.-K. Hong, “Hyperparameter Optimization Using a Genetic Algorithm Considering Verification Time in a Convolutional Neural Network,” _Journal of Electrical Engineering & Technology_, vol. 15, no. 2, pp. 721–726, Mar. 2020. [Online]. Available: http://link.springer.com/10.1007/s42835-020-00343-7
  * [28] E. Semenkin and M. Semenkina, “Self-configuring genetic algorithm with modified uniform crossover operator,” in _International Conference in Swarm Intelligence_. Springer, 2012, pp. 414–421.
  * [29] M. Srinivas and L. M. Patnaik, “Genetic algorithms: A survey,” _computer_ , vol. 27, no. 6, pp. 17–26, 1994.
  * [30] J. Grefenstette, R. Gopal, B. Rosmaita, and D. Van Gucht, “Genetic algorithms for the traveling salesman problem,” in _Proceedings of the first International Conference on Genetic Algorithms and their Applications_ , vol. 160, no. 168. Lawrence Erlbaum, 1985, pp. 160–168.
  * [31] X. Xiao, M. Yan, S. Basodi, C. Ji, and Y. Pan, “Efficient hyperparameter optimization in deep learning using a variable length genetic algorithm,” _arXiv preprint arXiv:2006.12703_ , 2020.
  * [32] Z. Michalewicz, _Genetic algorithms+ data structures= evolution programs_. Springer Science & Business Media, 2013.
  * [33] M. Srinivas and L. M. Patnaik, “Adaptive probabilities of crossover and mutation in genetic algorithms,” _IEEE Transactions on Systems, Man, and Cybernetics_ , vol. 24, no. 4, pp. 656–667, 1994.
  * [34] D. Whitley and T. Starkweather, “Genitor ii: A distributed genetic algorithm,” _Journal of Experimental & Theoretical Artificial Intelligence_, vol. 2, no. 3, pp. 189–214, 1990.
  * [35] R. Hinterding, “Gaussian mutation and self-adaption for numeric genetic algorithms,” in _Proceedings of 1995 IEEE International Conference on Evolutionary Computation_ , vol. 1, 1995, pp. 384–.
  * [36] R. Hinterding, Z. Michalewicz, and T. C. Peachey, “Self-adaptive genetic algorithm for numeric functions,” in _Parallel Problem Solving from Nature — PPSN IV_ , H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996, pp. 420–429.
  * [37] A. Berry and P. Vamplew, “Pod can mutate: A simple dynamic directed mutation approach for genetic algorithms,” 2004.
  * [38] K. Deep and M. Thakur, “A new mutation operator for real coded genetic algorithms,” _Applied mathematics and Computation_ , vol. 193, no. 1, pp. 211–230, 2007.
  * [39] D. Duvenaud, D. Maclaurin, J. Aguilera-Iparraguirre, R. Gómez-Bombarelli, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams, “Convolutional networks on graphs for learning molecular fingerprints,” _arXiv preprint arXiv:1509.09292_ , 2015.
  * [40] R. C. Glen, A. Bender, C. H. Arnby, L. Carlsson, S. Boyer, and J. Smith, “Circular fingerprints: flexible molecular descriptors with applications from physical chemistry to adme,” _IDrugs_ , vol. 9, no. 3, p. 199, 2006\.
  * [41] H. Van Seijen, M. Fatemi, J. Romoff, R. Laroche, T. Barnes, and J. Tsang, “Hybrid reward architecture for reinforcement learning,” _arXiv preprint arXiv:1706.04208_ , 2017.


# Unitary paradox of cosmological perturbations

Ngo Phuc Duc Loc<EMAIL_ADDRESS>Department of Physics and Astronomy,
University of New Mexico, Albuquerque, NM 87131, USA

###### Abstract

If we interpret the Bekenstein-Hawking entropy of the Hubble horizon as
thermodynamic entropy, then the entanglement entropy of the superhorizon modes
of curvature perturbation entangled with the subhorizon modes will exceed the
Bekenstein-Hawking bound at some point; we call this the unitary paradox of
cosmological perturbations by analogy with black hole. In order to avoid a
fine-tuned problem, the paradox must occur during the inflationary era at the
critical time $t_{c}=\ln(3\sqrt{\pi}/\sqrt{2}\epsilon_{H}H_{inf})/2H_{inf}$
(in Planck units), where $\epsilon_{H}=-\dot{H}/H^{2}$ is the first Hubble
slow-roll parameter and $H_{inf}$ is the Hubble rate during inflation. If we
instead accept the fine-tuned problem, then the paradox will occur during the
dark energy era at the critical time
$t_{c}^{\prime}=\ln(3\sqrt{\pi}H_{inf}/\sqrt{2}fe^{2N}H_{\Lambda}^{2})/2H_{\Lambda}$,
where $H_{\Lambda}$ is the Hubble rate dominated by dark energy, $N$ is the
total number of e-folds of inflation, and $f$ is a purification factor that
takes the range $0<f<3\sqrt{\pi}H_{inf}/\sqrt{2}e^{2N}H_{\Lambda}^{2}$.

###### Contents

  1. I Introduction
  2. II Bekenstein-Hawking entropy
  3. III Entanglement entropy
  4. IV Unitary paradox without fine-tuning
  5. V Unitary paradox with fine-tuning
  6. VI Discussions and Outlooks

##  I Introduction

Let us first provide a brief description of the unitary paradox of black hole.
Here is the main assumption known as the central dogma: As seen from the
outside, the black hole can be described as a usual quantum system that
evolves unitarily. Of course, there is a singularity at the hole’s center that
will require some knowledge of quantum gravity. But the singularity is hidden
inside the horizon, so the black hole as seen from the outside should be
reasonably considered as an ordinary quantum system. The Bekenstein-Hawking
entropy of black hole is area ; area2

$S_{BH}=\frac{A}{4},$ (1)

where $A$ is the area of the black hole’s horizon 111In this paper, we will
use Planck units in which $\hbar=c=k_{b}=G=1$ (unless otherwise mentioned), so
that all quantities are dimensionless.. Bekenstein-Hawking entropy is
thermodynamic entropy (also called coarse-grained entropy) of black hole and
it is the maximum number of degrees of freedom (d.o.f.) available inside the
hole that can be entangled with the outgoing Hawking quanta. It can also be
thought of as the number of different possible configurations (or microstates)
that can form the same macrostate of black hole 222Strictly speaking, we
should say $e^{S}$ d.o.f. or $e^{S}$ microstates (or $2^{S}$ microstates
depending on the context). But we want to be a bit less mouthful. . As the
black hole evaporates, its horizon’s area shrinks and hence $S_{BH}$ decreases
asymptotically to zero 333There is a caveat: When the black hole size is
comparable to the Planck length, the semiclassical description is no longer
reliable since we will enter the full quantum gravity regime. However, this
subtlety cannot affect our arguments in any significant way as the paradox
occurs well before that moment happens.. According to Hawking’s calculation,
entanglement entropy444Entanglement entropy is also sometimes called Von
Neumann entropy or fine-grained entropy. of Hawking radiation grows as more
and more Hawking quanta are entangled with black hole’s interior d.o.f., and
it saturates at a value higher than the initial Bekenstein-Hawking entropy of
the hole. But this doesn’t make sense, because the entanglement entropy of
Hawking radiation should be equal to the entanglement entropy of black hole
(if the black hole was formed from a pure state), but the entanglement entropy
of black hole cannot be higher than its thermodynamic entropy (if we believe
in the central dogma and the interpretation of Bekenstein-Hawking entropy).
Therefore, we expect that the entanglement entropy of Hawking radiation should
only increase until the Page time, when half of the black hole’s d.o.f. have
gone, and then decrease afterwards (see Fig. 1). The entanglement entropy of
Hawking radiation should follow the Page curve instead of the original
Hawking’s calculation. This is called the unitary paradox. There are some
calculations in Ref. ahmed  that can produce the correct Page curve.

Figure 1: Bekenstein-Hawking entropy versus entanglement entropy of black
hole. The unitary paradox occurs at the Page time. (Figure is taken from Ref.
ahmed  with permission.)

In this paper, we study the corresponding cosmological version of the unitary
paradox. In cosmology, the physical Hubble sphere with radius $H^{-1}$ plays a
role similar to black hole’s horizon. The central dogma version of cosmology
is: the exterior region of the Hubble horizon can be described from the inside
as a usual quantum system that evolves unitarily. As pointed out in Ref. edgar
, the central dogma conjecture for cosmological horizon has not had a firm
basis yet, but we can reasonably take this as our assumption. As pointed out
in subsequent sections, if we also interpret the Bekenstein-Hawking entropy of
the Hubble horizon as thermodynamic entropy, then there exists a cosmological
unitary paradox as well when the entanglement entropy of curvature
perturbation exceeds the Bekenstein-Hawking bound. The goal of this paper is
to estimate the critical time when the paradox occurs.

The rest of this paper is organized as follows. We discuss about the
interpretation and evolution of Bekenstein-Hawking entropy of the Hubble
horizon in Sec. II. We then talk about entanglement entropy of curvature
perturbation in Sec. III. We point out in Sec. IV that, if we do not allow
fine-tuning, the unitary paradox must occur during inflation. If we instead
accept the fine-tuned problem, then the unitary paradox occurs during the dark
energy era, as shown in Sec. V. Discussions and outlooks are in Sec. VI.

##  II Bekenstein-Hawking entropy

By analogy with black hole (see Eq. 1), the Bekenstein-Hawking entropy of the
Hubble horizon is

$S_{BH}=\frac{A}{4}=\frac{\pi}{H^{2}},$ (2)

where $H$ is the Hubble rate. The subscript “BH” means Bekenstein-Hawking, not
black hole. We interpret the Bekenstein-Hawking entropy of the Hubble horizon
as thermodynamic entropy.

There are two insightful ways to think about the Bekenstein-Hawking entropy of
the Hubble horizon. First, one can draw an analogy to the case of black hole.
When we throw something into the black hole, it cannot escape. The black
hole’s horizon area will increase and hence the Bekenstein-Hawking entropy
will increase. This means that the hole’s horizon now encodes more information
about the hole’s interior (which, of course, gives some sense of nonlocality).
Similarly, if we throw something outside the Hubble horizon, it will never
come back due to the superluminal expansion of the exterior region. The area
of the Hubble horizon will increase (since $A\propto H^{-2}$ and
$H^{2}\propto\rho$) and hence the Bekenstein-Hawking entropy will increase
(since $S_{BH}\propto A$). This means that the Hubble horizon now encodes more
information about its exterior region.

Second and related to the first point, one can note that the comoving Hubble
radius is $(aH)^{-1}$. During the inflationary era (or during the dark energy
era), the comoving Hubble radius decreases and hence the Bekenstein-Hawking
entropy for the corresponding comoving area decreases. This means that the
observer inside the Hubble horizon has less and less fraction of information
about the global Universe. But during the radiation or matter dominated era,
the comoving Hubble radius increases and hence the Bekenstein-Hawking entropy
for the corresponding comoving area increases. This means that the observer
inside the Hubble horizon has more and more fraction of information about the
global Universe.

In our subsequent discussions, we prefer using the physical Hubble horizon.
During the inflationary era with the Hubble rate $H_{inf}$, the Bekenstein-
Hawking entropy is

$S_{BH}^{inf}=\frac{\pi}{H_{inf}^{2}}.$ (3)

During the radiation-dominated era with the Hubble rate $H_{r}$, the scale
factor grows as $a\propto t^{1/2}$, so the Bekenstein-Hawking entropy is

$S_{BH}^{rad}=\frac{\pi}{H_{r}^{2}}=4\pi t^{2}.$ (4)

During the matter-dominated era with the Hubble rate $H_{m}$, the scale factor
grows as $a\propto t^{2/3}$, so the Bekenstein-Hawking entropy is

$S_{BH}^{mat}=\frac{\pi}{H_{m}^{2}}=\frac{9\pi t^{2}}{4}.$ (5)

During the dark energy era with the Hubble rate $H_{\Lambda}$, the Bekenstein-
Hawking entropy is

$S_{BH}^{DE}=\frac{\pi}{H_{\Lambda}^{2}}.$ (6)

Note that $H_{inf}$ and $H_{\Lambda}$ are roughly constant.

Since entanglement entropy will be calculated in momentum space, it is
necessary to interpret the Bekenstein-Hawking entropy appropriately in this
context:

> The Bekenstein-Hawking entropy of the Hubble horizon is conjectured to be
> the maximum number of available d.o.f. of the unobserved superhorizon modes.

This is similar to the interpretation of Bekenstein-Hawking entropy of black
hole when it bounds the unobserved d.o.f. inside the hole. The difference is
that, while the Hilbert space is decomposed on a spatial slice for black hole,
the Hilbert space for cosmological perturbations is conveniently decomposed in
momentum space based on the comparison of modes’ wavelength with the size of
Hubble horizon (which will be discussed in the next section). In both cases,
though, the deep meaning of Bekenstein-Hawking entropy is still that it bounds
unobserved d.o.f.: for black hole, it bounds unobserved d.o.f. inside the
hole; for cosmological horizon, it bounds unobserved d.o.f. whose wavelength
is greater than the size of the horizon.

##  III Entanglement entropy

During inflation, a hypothetical inflaton field is responsible for the
accelerating expansion. In comoving gauge, the inflaton field is unperturbed
and all scalar perturbations are carried by the curvature perturbation
$\xi(\textbf{x},t)$ of the metric555Some people might prefer the notation
$\mathcal{R}(\textbf{x},t)$.. If we just stop at the quadratic level of the
action of curvature perturbation, each perturbation mode will evolve
independently with a time-dependent mass due to the expansion of the Universe.
But if we consider the cubic term of the action, then there exists interaction
between perturbation modes. This interaction is due to the nonlinearity of
general relativity and is the minimal kind of interaction that must be
present. It has been shown that this interaction is the minimal mechanism
responsible for decoherence during inflation nelson . There are many terms in
the cubic action, but the most dominant term responsible for decoherence is of
the form $\xi_{L}(\partial_{i}\xi_{S})^{2}$, where $\xi_{L}$ is the long-
wavelength mode and $\xi_{S}$ is the short-wavelength mode. We can decompose
the total Hilbert space as
$\mathcal{H}_{tot}=\mathcal{H}_{k>aH}\otimes\mathcal{H}_{k<aH}$, where
$\mathcal{H}_{k>aH}$ is the Hilbert space of the subsystem containing
subhorizon modes and $\mathcal{H}_{k<aH}$ is the Hilbert space of the
subsystem containing superhorizon modes.

Here is the basic picture of decoherence in the early Universe. We can treat
the superhorizon modes as the system of interest, and the subhorizon modes as
the environment (or bath modes). Decoherence happens via the interaction
between the superhorizon modes and the subhorizon modes. When the modes exit
the horizon during inflation, they do not immediately become classical
perturbation because the coupling of interaction, which is proportional to the
slow-roll parameters, is very small. It took a few e-folds of interaction for
the system to be decohered and becomes classical. Because of the interaction,
the superhorizon modes (the system) becomes entangled with the subhorizon
modes (the environment). The entanglement entropy per physical volume of the
superhorizon modes entangled with the subhorizon modes during inflation was
calculated to be 666As a matter of illustration, here we assumed that
$\ln(\lambda^{2})\sim O(1)$, where $\lambda$ is the coupling of the
interacting Hamiltonian. Also note that we are using the Planck units with
$\hbar=c=k_{B}=G=1$, so the reduced Planck mass is
$M_{pl}=m_{pl}/\sqrt{8\pi}=1/\sqrt{8\pi}$. brahma

$s_{ent}\sim\frac{\epsilon_{H}H_{inf}^{2}a^{2}}{\sqrt{8\pi}},$ (7)

where $H_{inf}$ is roughly constant during inflation,
$\epsilon_{H}\equiv-\dot{H}/H^{2}$ is the first Hubble slow-roll parameter and
$a\propto\exp(Ht)$ is the scale factor. The entanglement entropy grows with
time as more and more modes of perturbations exit the horizon.

If we assume that the global Universe was formed from a pure state, which is a
reasonable assumption but cannot be proved easily, then the entanglement
entropy of superhorizon modes must be equal to the entanglement entropy of
subhorizon modes as they will combine to form a pure state. With that
assumption, we can convert Eq. 7 to the entanglement entropy by multiplying
the physical volume of the Hubble sphere

$S_{ent}=s_{ent}\times\frac{4\pi}{3H_{inf}^{3}}=\frac{\sqrt{2\pi}\epsilon_{H}}{3H_{inf}}\exp(2H_{inf}t).$
(8)

##  IV Unitary paradox without fine-tuning

From Eqs. 3 and 8, we can obtain the critical time at which the entanglement
entropy exceeds the Bekenstein-Hawking entropy 777Note that $H_{inf}$ and
$\epsilon_{H}$ are approximately constant during inflation.

$t_{c}=\frac{\ln\left(3\sqrt{\pi}/\sqrt{2}\epsilon_{H}H_{inf}\right)}{2H_{inf}}.$
(9)

This is the time when the unitary paradox occurs. If we interpret the
Bekenstein-Hawking entropy as the maximum number of available d.o.f. of the
unobserved superhorizon modes888Note that modes must exit the horizon to be
decohered and must re-enter the horizon to be observed. , then the
entanglement entropy between the subhorizon modes and superhorizon modes
cannot exceed the Bekenstein-Hawking entropy because that would violate
unitarity. See Fig. 2 for a sketch 999Of course, in practice the Bekenstein-
Hawking entropy will grow smoothly between different eras, but as a matter of
conceptual illustration we are discussing an approximate model..

Figure 2: Evolution of Bekenstein-Hawking entropy of the Hubble horizon
(colorful lines) and entanglement entropy of curvature perturbations (black
line). The unitary paradox occurs at the critical time $t_{c}$ that is given
in Eq. 9. (Figure is not to scale.)

On the one hand, the positivity condition for the above critical
time101010Which just means the condition for the initial entanglement entropy
to be less than the Bekenstein-Hawking entropy. is

$\epsilon_{H}<3\sqrt{\frac{\pi}{2}}\frac{1}{H_{inf}}.$ (10)

If we convert this upper bound to the conventional natural units, we get
$\epsilon_{H}<3\sqrt{\frac{\pi}{2}}\frac{m_{pl}}{H_{inf}}$. Given the fact
that the typical energy scale of inflation is of order $10^{15}$ GeV and the
Planck scale is of order $10^{19}$ GeV, this upper bound is actually much
milder than the usual condition $\epsilon_{H}<1$ for inflation to happen. In
fact, the Planck’s observation planck  indicates that $\epsilon_{H}<0.0063$
$(95\%$ C.L.), which means that our upper bound is well satisfied.

On the other hand, we note that the typical timescale of inflation is
$t_{reh}\sim N/H_{inf}$, where $N$ is the total number of e-folds that is at
least $\sim 70$ to solve the horizon and flatness problems 111111The subscript
“reh” means reheating - the moment when inflation ends.. Therefore, the
critical time happens before reheating if $t_{c}<t_{reh}$, which implies

$\epsilon_{H}>3\sqrt{\frac{\pi}{2}}\frac{1}{e^{2N}H_{inf}}.$ (11)

We see that this lower bound is exponentially suppressed. Although we expect
that the slow-roll parameter $\epsilon_{H}$ should be less than unity to
achieve inflation, it is unlikely that this parameter can have such a very
tiny value that can violate this lower bound. Because
$\epsilon_{H}=-\dot{H}/H^{2}$ changes very slowly during inflation, it must
change abruptly near the end of inflation to reach $\epsilon_{H}=1$ to
terminate inflation. In this sense, if we do not allow such a fine-tuned
problem, the paradox must occur during inflation.

##  V Unitary paradox with fine-tuning

If we instead accept the fine-tuned problem, the paradox will still occur but
in the dark energy era. The real reason for this possibility is that inflation
has to end to set the stage for subsequent epochs. The entanglement entropy at
the end of inflation is

$S_{ent}(t=t_{reh})=\frac{\sqrt{2\pi}}{3}\frac{e^{2N}}{H_{inf}}.$ (12)

During the radiation and matter dominated eras, the modes of cosmological
perturbation re-enter the horizon and purify with the modes already inside. We
therefore expect that entanglement entropy will decrease. We parameterize this
purification process with a purification factor called $f$. We absorbed all
the details into this purification factor to discuss the relevant conceptual
viewpoint. The entanglement entropy at the beginning of dark energy dominated
era is then

$S_{ent}(t=t_{DE})=f\frac{\sqrt{2\pi}}{3}\frac{e^{2N}}{H_{inf}}.$ (13)

During the dark energy dominated era, the modes of perturbations exit the
horizon again and entanglement entropy increases again. We can assume
reasonably that it grows as $\propto\exp(2H_{\Lambda}t)$ similar to the case
of inflation. Therefore, the entanglement entropy during the dark energy era
is

$S_{ent}(t>t_{DE})=f\frac{\sqrt{2\pi}}{3}\frac{e^{2N}}{H_{inf}}\exp(2H_{\Lambda}t).$
(14)

From Eqs. 6 and 14, the paradox occurs at the critical time

$t_{c}^{\prime}=\frac{\ln(3\sqrt{\pi}H_{inf}/\sqrt{2}fe^{2N}H_{\Lambda}^{2})}{2H_{\Lambda}},$
(15)

where the purification factor $f$ satisfies

$0<f<3\sqrt{\frac{\pi}{2}}\frac{H_{inf}}{e^{2N}H_{\Lambda}^{2}}.$ (16)

The lower bound is trivial, while the upper bound comes from the fact that
$S_{ent}(t=t_{DE})<S_{BH}^{DE}$. We can see that, besides the fine-tuned
problem of $\epsilon_{H}$ discussed earlier, we also have a fine-tuned problem
for the purification factor when its upper bound is exponentially suppressed.

##  VI Discussions and Outlooks

Black hole physics contains lots of paradoxes that can give us useful lessons
towards a more complete and profound picture of our (effective) reality. It
seems like we are trying to put everything we have on the table with the black
hole at the center as a tool to connect everything we know in a consistent
manner, and also to guess what are still missing. Now we are also trying to
see how the whole Universe itself helps in the context of cosmology/black hole
correspondence.

As seen from the outside, black hole behaves like an ordinary quantum system
evolving unitarily. Because the Hubble horizon is like an inverted black hole
pushing things away from each other, we can think of it as an ordinary quantum
system as seen from the inside. In momentum space, the Bekenstein-Hawking
entropy of the Hubble horizon is interpreted as the maximum number of
available d.o.f. of the unobserved superhorizon modes. With those
observations, we pointed out that there is a corresponding unitary paradox of
cosmological perturbations when entanglement entropy exceeds the Bekenstein-
Hawking bound. In order to avoid the fine-tuned problems of the slow-roll
parameter $\epsilon_{H}$ and the purification factor $f$, the paradox must
occur during the inflationary era at the critical time
$t_{c}=\ln(3\sqrt{\pi}/\sqrt{2}\epsilon_{H}H_{inf})/2H_{inf}$ (in Planck
units). If we instead accept the fine-tuned problem, then the paradox will
occur during the dark energy era at the critical time
$t_{c}^{\prime}=\ln(3\sqrt{\pi}H_{inf}/\sqrt{2}fe^{2N}H_{\Lambda}^{2})/2H_{\Lambda}$,
where the purification factor $f$ takes the range
$0<f<3\sqrt{\pi}H_{inf}/\sqrt{2}e^{2N}H_{\Lambda}^{2}$. We remind the readers
the list of major assumptions that led to these conclusions: (i) The central
dogma of cosmological horizon is correct; (ii) Bekenstein-Hawking entropy of
the Hubble horizon is thermodynamic entropy, which means that it is the
maximum number of available d.o.f. of superhorizon modes; (iii) The global
state of the Universe is pure. What is then the solution?

Figure 3: The Page curve reaches a maximum at the point with coordinate
$\\{1/2,\ln(\dim\mathcal{H}_{AB})/2\\}$.

Consider a total Hilbert space $\mathcal{H}_{AB}$ with two subsystems A and B
with Hilbert space $\mathcal{H}_{A}$ and $\mathcal{H}_{B}$ respectively. The
state in $\mathcal{H}_{AB}$ is pure, but the states in $\mathcal{H}_{A}$ and
$\mathcal{H}_{B}$ can be entangled with each other. From the definition of
entanglement entropy

$S_{vN}(\rho)=-\mathrm{Tr}\left(\rho\ \ln\ \rho\right),$ (17)

it is clear that $S_{vN}(A)\leq\ln(\dim\mathcal{H}_{A})$ and similarly for
system B with equality if and only if all $\rho_{n}$ are equal, where
$\rho_{n}$ are the eigenvalues of the density matrix $\rho$. Due to the
entanglement between A and B, we also have
$S_{vN}(A)=S_{vN}(B)\leq\ln(\dim\mathcal{H}_{B})$. In the limit of large
Hilbert space, entanglement entropy of subsystem A follows the Page curve page
; mathew

$S_{vN}(A)\sim\min\\{\ln(\dim\mathcal{H}_{A}),\ln(\dim\mathcal{H}_{B})\\},$
(18)

which is sketched in Fig. 3. A quick qualitative understanding of this result
is the following. If the size of Hilbert space of subsystem A is smaller than
that of B, then $S_{vN}(A)\sim\ln(\dim\mathcal{H}_{A})$ because all d.o.f. in
A are maximally entangled with B, but there are still redundant d.o.f. in B
that are not entangled with A. When the size of Hilbert space of A increases,
more and more d.o.f. of A are entangled with B and hence $S_{vN}(A)$ increases
until it reaches a maximum when $\dim\mathcal{H}_{A}=\dim\mathcal{H}_{B}$. If
the size of subsystem A continues to increase, then $S_{vN}(A)$ decreases as
there are more and more redundant d.o.f. in A that are not entangled with B,
so we have $S_{vN}(A)\sim\ln(\dim\mathcal{H}_{B})$ and the Page curve is
realized. This is a general feature of entanglement between two subsystems of
a random pure state with a large Hilbert space.

In the case of black hole or cosmological horizon, we also expect to have this
Page-like curve but we will have to justify thoroughly for its origin since
black hole and cosmological horizon are nontrivial quantum systems with
classical general relativity is present. There are some directions to go from
here. First, one can try to put the cosmological dogma conjecture on a firmer
basis. Second, one can do detailed calculations for entanglement entropy
during the radiation and matter dominated eras to get the precise value of the
purification factor $f$ (if one feels okay with fine-tuning.). Third and most
importantly, one can try to find a new method to compute the correct
entanglement entropy that does not violate unitarity. We leave these for
future works.

—Notes added: After we submitted our paper, we were directed to Ref. 10  that
also discusses similar things. However, there are 3 main
improvements/differences in our paper:

  1. 1.

The author of 10  missed an important assumption that the global state of the
Universe must be pure. The entanglement entropy per physical volume was
calculated by tracing over the subhorizon modes. If the global Universe was
formed from a pure state, the entanglement entropy of superhorizon modes will
be equal to that of subhorizon modes and one can therefore multiply by the
physical Hubble volume to obtain entanglement entropy within the Hubble
horizon. If the global Universe was instead formed from a mixed state, the
above statement is not true. We also need the global pure state assumption to
apply the Page-curve argument.

  2. 2.

The author of 10  estimated the upper bound of the total e-folding number $N$
by demanding that the total amount of entanglement entropy generated during
inflation is less than the Bekenstein-Hawking entropy by the end of inflation.
This leads to a bound that is close to the Trans-Planckian Censorship
Conjecture condition: $N<\ln(M_{pl}/H)$. However, this will require the energy
scale of inflation to be much smaller than the conventional value $\sim
10^{15}$ GeV to ensure that this upper bound is greater than 70, because we
need at least $\sim 70$ e-folds for inflation to resolve the horizon and
flatness problems. In our paper, we did not have that demand and the energy
scale of inflation could be large. The entanglement entropy will therefore
exceed the Bekenstein-Hawking bound well before the end of inflation and we
estimated the critical time when the paradox occurs.

  3. 3.

We also discussed about the possibility that the paradox can happen during the
dark energy dominated era due to the purification process (which is not
discussed in 10 ). While we are currently not aware of any specific way to
ease the fine-tuned problems discussed in this paper, we want to leave the
door open for possible future investigations.

We were also noticed of Ref. hao  in which the authors considered the unitary
paradox of de Sitter space in the framework of DS/dS correspondence. While
their non-perturbative approach is not directly related to the curvature
perturbation discussed here, they made an interesting point of deriving the
Page-like curve by constructing entanglement islands.

## Acknowledgment

The author is grateful for financial support from the Department of Physics
and Astronomy at UNM through the Origins of the Universe Award. The author
also thanks Prof. Rouzbeh Allahverdi for correspondence.

## References

  * (1) Jacob D. Bekenstein, Black Holes and Entropy, Phys. Rev. D 7, 2333 (1973).
  * (2) S. W. Hawking, Particle creation by black holes, Commun. Math. Phys. 43, 199–220 (1975).
  * (3) Ahmed Almheiri, Thomas Hartman, Juan Maldacena, Edgar Shaghoulian, and Amirhossein Tajdini, The entropy of Hawking radiation, Rev. Mod. Phys. 93, 035002 (2021).
  * (4) Edgar Shaghoulian, The central dogma and cosmological horizons, J. High Energ. Phys. 2022, 132 (2022).
  * (5) Elliot Nelson, Quantum Decoherence During Inflation from Gravitational Nonlinearities, JCAP 03, 022 (2016).
  * (6) Suddhasattwa Brahma, Omar Alaryani, and Robert Brandenberger, Entanglement entropy of cosmological perturbations, Phys. Rev. D 102, 043529 (2020).
  * (7) Y. Akrami et al. (Planck Collaboration), Planck 2018 results. X. Constraints on inflation, Astronomy and Astrophysics 641, A10 (2020), arXiv:1807.06211v2
  * (8) Don N. Page, Information in black hole radiation, Phys. Rev. Lett. 71, 3743 (1993).
  * (9) Matthew Headrick, Lectures on entanglement entropy in field theory and holography, arXiv:1907.08126 [hep-th].
  * (10) Suddhasattwa Brahma, Constraints on the duration of inflation from entanglement entropy bounds, arXiv:2104.02840.
  * (11) Hao Geng, Yasunori Nomura, and Hao-Yu Sun, Information paradox and its resolution in de Sitter holography, Phys. Rev. D 103, 126004 (2021).