11institutetext: Rényi Institute of Mathematics, Budapest, Hungary
11email<EMAIL_ADDRESS>ISTA (Institute of Science and
Technology Austria), Klosterneuburg, Austria
22email<EMAIL_ADDRESS>ISTA (Institute of Science and
Technology Austria), Klosterneuburg, Austria
33email<EMAIL_ADDRESS>Department of Computer
Science, ETH Zürich, Switzerland
44email<EMAIL_ADDRESS>
# Decomposition of Geometric Graphs
into Star-Forests††thanks: János Pach’s Research partially supported by
European Research Council (ERC), grant “GeoScape” No. 882971 and by the
Hungarian Science Foundation (NKFIH), grant K-131529. Work by Morteza
Saghafian is partially supported by the European Research Council (ERC), grant
No. 788183, and by the Wittgenstein Prize, Austrian Science Fund (FWF), grant
No. Z 342-N31.

János Pach 1122 0000-0002-2389-2035 Morteza Saghafian 33 0000-0002-4201-5775
Patrick Schnider 44 0000-0002-2172-9285

###### Abstract

We solve a problem of Dujmović and Wood (2007) by showing that a complete
convex geometric graph on $n$ vertices cannot be decomposed into fewer than
$n-1$ star-forests, each consisting of noncrossing edges. This bound is
clearly tight. We also discuss similar questions for abstract graphs.

##  1 Introduction

To determine the smallest number of subgraphs of some special kind that a
graph $G$ can be partitioned into is a large and classical theme in graph
theory. In particular, the parts may be required to be matchings (as in
Vizing’s theorem [12]), complete bipartite graphs (as in the Graham-Pollak
theorem [7]), paths and cycles (as in Lovász’ theorem [9]), forests (as in the
Nash-Williams theorem [10]), etc.

Most likely, it was Erdős who first realized that one can ask many interesting
new extremal questions for graphs drawn in the plane or in some other surface,
if we replace the purely combinatorial conditions by geometric ones; see [11].
For instance, we may require that the edges participating in a matching or a
path do not cross each other [4], [8]. In the 80s and 90s, the emergence of
Graph Drawing as a separate discipline gave fresh impetus to this line of
research.

A _geometric graph_ $G$ is a graph whose vertex set is a set of points in the
plane, no 3 of which are collinear, and whose edges are (possibly crossing)
line segments connecting certain pairs of vertices. If the vertices of $G$ are
in _convex position_ , that is, they form the vertex set of a convex polygon,
then $G$ is called a _convex geometric graph_. In the sequel, whenever we say
that a graph or a geometric graph $G$ _can be decomposed_ into certain parts,
we mean that its _edge set_ , $E(G)$, can be partitioned into such parts. Each
part can be regarded as a different _color class_ in the corresponding
coloring.

A _star_ is a graph consisting of a vertex together with some edges incident
to it. In particular, a single vertex is counted as a star. A graph whose
every connected component is a star is called a _star-forest_. The (edge set
of a) complete graph $K_{n}$ with $n$ vertices can be decomposed into $n-1$
stars. Akiyama and Kano [2] proved that fewer stars do not suffice. (This also
follows from the Graham-Pollak theorem [7], mentioned above.) However, it was
also shown in [2] that one can decompose $K_{n}$ into much fewer _star-
forests_ : one needs only $\lceil n/2\rceil+1$ of them. Can one also decompose
a _complete convex geometric graph_ on $n$ vertices into fewer than $n-1$
star-forests, if we insist that each star-forest is a _plane graph_ , that is,
its edges do not cross each other? This question was raised by Dujmović and
Wood [6] (Section 10).

The aim of this note is to answer this question in the negative.

###### Theorem 1

Let $n\geq 1$. The complete convex geometric graph with $n$ vertices cannot be
decomposed into fewer than $n-1$ plane star-forests.

On the other hand, there are complete geometric graphs where fewer than $n-1$
plane star-forests suffice: consider $P=A_{1}\cup A_{2}\cup A_{3}\cup A_{4}$ a
point set consisting of four pairwise disjoint sets $A_{1},\ldots,A_{4}$, each
of size $k$, such that for every choice $P_{1}\in A_{1},\ldots,P_{4}\in A_{4}$
we have that $P_{4}$ lies inside the convex hull of $P_{1},P_{2}$ and $P_{3}$.
Then, it can be seen that the complete geometric graph on $P$ can be
decomposed into $3k=3n/4$ plane star-forests, which come in three families:
the first family consists of stars emanating from points in $A_{1}$ connecting
to all points in $A_{1}$ and $A_{2}$ together with stars emanating from points
in $A_{3}$ connecting to all points in $A_{3}$ and $A_{4}$. Similarly, we draw
stars emanating from points in $A_{2}$ connecting to all points in $A_{2}$ and
$A_{3}$ and from points in $A_{4}$ connecting to all points in $A_{4}$ and
$A_{1}$, and for the last family stars from points in $A_{1}$ connecting to
all points in $A_{1}$ and $A_{3}$ and from points in $A_{2}$ connecting to all
points in $A_{2}$ and $A_{4}$.

The most important unsolved question in this direction is, how much the bound
in Theorem 1 can be improved if we drop the assumption that the vertices are
in convex position. We conjecture that the above example is optimal.

###### Conjecture 2

Let $n\geq 1$. There is no complete geometric graph with $n$ vertices that be
decomposed into fewer than $\lceil 3n/4\rceil$ plane star-forests.

Note that in the example above, all star-forests had exactly two components. A
star-forest consisting of at most $k$ connected components (stars) is said to
be a _$k$ -star-forest_.

It is also an interesting open problem to determine the minimum number of
plane $k$-star-forests that a complete (convex) geometric graph of $n$
vertices can be decomposed into. We do not even know the answer to the
analogous question for abstract graphs.

###### Problem 3

Let $k$ and $n$ be fixed positive integers. What is the minimum number of
$k$-star-forests that a complete graph $K_{n}$ of $n$ vertices can be
decomposed into?

As was mentioned earlier, for $k=1$, the minimum is $n-1$. The following
result settles the first nontrivial case.

###### Theorem 4

The complete graph with $n>3$ vertices can be decomposed into $\lceil
3n/4\rceil$ 2-star-forests. This bound cannot be improved.

In particular, this shows that any counterexample to Conjecture 2 would
require the use of star-forests with more than 2 components.

Many other variants of decomposing complete geometric graphs have been studied
in the literature, including decompositions into plane spanning trees. The
conjecture that every complete geometric graph on $2m$ vertices can be
decomposed into $m$ plane spanning trees has been recently disproved in [1].
Several notions of thickness studied in [6] are concerned with decompositions
of graphs into plane substructures. For many other interesting questions on
abstract and geometric graph parameters, consult [3].

In Sections 2 and 3, we prove Theorems 1 and 4, respectively.

##  2 Covering with plane star-forests–Proof of Theorem 1

Recall that a _plane star-forest_ is a star-forest which is a plane graph,
i.e., its edges do not cross each other. In this section, in a slight abuse of
notations, we will denote the complete convex geometric graph on $n$ points as
$K_{n}$. Instead of _decompositions_ of $K_{n}$ into plane star-forests, it
will be more convenient to consider _coverings_ , that is, to allow an edge to
belong to more than one star-forest (to have more than one “color”). This does
not change the problem, because by keeping just one color for each edge, we
turn any covering of the edge set of $K_{n}$ into a decomposition.

###### Definition 5

A collection of plane star-forests, $F_{1},F_{2},\ldots,F_{t}$ forms a
_covering_ of $K_{n}$ if every edge of $K_{n}$ belongs to _at least one_
$F_{i}$.

For the proof, we need to introduce some simple terminology. The graphs
consisting of just one vertex or a single edge are also regarded as stars.
Every star $S$ has a _center_. If $S$ is a vertex, then it is its own center.
If $S$ is a single edge, we arbitrarily fix one of its endpoints and call it
the center of $S$. The center of a star $S$ is also said to be the _center of
any edge_ of $S$. Accordingly, if $F$ is a (plane) star-forest, we always
assume that each of its components is a star with a _fixed center_.

######  Proof (Proof of Theorem 1)

For $n=1,2$, the statement is trivial. Assume for contradiction and let $n\geq
3$ be the smallest number for which the statement is not true. Let $K_{n}$ be
a complete convex geometric graph, and denote its vertices by
$P_{1},P_{2},\ldots,P_{n}$, in clockwise order. The indices are taken modulo
$n$, so that $P_{n+1}=P_{1},P_{n+2}=P_{2}$, etc.

Suppose that $K_{n}$ is covered by $t$ plane star-forests,
$F_{1},F_{2},\ldots,F_{t}$, for some $t<n-1$. Our goal is to move some edges
from one star-forest to another (i.e., to “recolor” them) in order to turn at
least one $F_{i}$ into a single star. We make sure that after each step of
this process, we obtain a covering of $K_{n}$ with plane star-forests. As soon
as one of the $F_{i}$s becomes a single star, we remove its center from
$K_{n}$, and contradict with $n$ being the smallest number for which we have a
covering of $K_{n}$ with fewer than $n-1$ plane star-forests.

For every $a,\,1\leq a\leq n,$ and for every $k,\,1<k<n$, we call the edge
$P_{a}P_{a+k}$ a $k$-edge. Note that every $k$-edge is also a $(n-k)$-edge.

###### Definition 6

A $k$-edge $P_{a}P_{a+k}$ is called _supported_ if there exists $F_{i}$ such
that $P_{a}P_{a+k}$ belongs to $F_{i}$, and

  1. (i)

either all edges $P_{a}P_{a+1},P_{a}P_{a+2},\ldots,P_{a}P_{a+k-1}$ belong to
$F_{i}$,

  2. (ii)

or all edges $P_{a+1}P_{a+k},P_{a+2}P_{a+k},\ldots,P_{a+k-1}P_{a+k}$ belong to
$F_{i}$.

Otherwise, we call it _unsupported_.

The goal is to recolor the edges step by step in order to make all the edges
supported. For this purpose, the following observation is useful for the
recoloring process.

###### Observation 7

Suppose that the complete geometric graph $K_{n}$ is covered by $t$ plane
star-forests, $F_{1},F_{2},\ldots F_{t}$. Let $S$ be a connected component of
$F_{i}$ (that is, a star) where $1\leq i\leq t$. Assume that no edge of $S$
crosses an edge of $F_{j}$ where $1\leq j\leq t$, $j\neq i$. Remove the edges
in $S$ from $F_{i}$ and add them to $F_{j}$. Then any edge that was supported
before is still supported.

###### Lemma 8

Suppose that the complete geometric graph $K_{n}$ can be covered by $t$ plane
star-forests, for some positive integer $t$.

Then, for every $k$, $1<k<n$, there exists a covering of $K_{n}$ by $t$ plane
star-forests $F_{1},F_{2}\ldots,F_{t}$ such that every $k^{\prime}$-edge with
$1<k^{\prime}\leq k$ is supported.

###### Proof

We prove the lemma by induction on $k$.

Suppose that $k=2$. By symmetry, it is sufficient to consider the $2$-edge
$P_{1}P_{3}$ (that is, $a=1)$. We can assume without loss of generality that
$P_{1}P_{3}$ belongs to $F_{i}$, for some $i$, and its center is $P_{1}$
(which implies that $P_{2}P_{3}$ is not in $F_{i}$). If $P_{1}P_{2}$ belongs
to $F_{i}$, condition (i) in Definition 6 is satisfied, and we are done. If
$P_{1}P_{2}$ does not belong to $F_{i}$, then add it to $F_{i}$. Obviously, it
cannot cross any other edge in $F_{i}$. The only problem that may occur is
that until now $P_{2}$ was a single vertex star in $F_{i}$, and now $F_{i}$
has two stars that have a point in common. In this case, simply erase the
single vertex star $P_{2}$ from $F_{i}$. Thus, the lemma is true for $k=2$.

Suppose next that $k>2$ and the statement has already been verified for $k-1$.
We want to prove it for $k$.

By symmetry, it is enough to consider the $k$-edge $P_{1}P_{k+1}$ and make it
supported without making the already supported edges unsupported. Suppose
without loss of generality that $P_{1}P_{k+1}$ belongs to a star in $F_{i}$
and the center of this star is $P_{1}$. The edges in $F_{i}$ are marked
_blue_.

Let $l<k+1$ be the _largest_ index such that $P_{1}P_{l}$ does _not_ belong to
$F_{i}$. Then the edges $P_{1}P_{l+1},\ldots,P_{1}P_{k+1}$ are all blue. If
there is no such index $l$, then we are done, because $F_{i}$ satisfies
condition (i) in Definition 6.

By the induction hypothesis the edge $P_{1}P_{l}$ is supported, so there
exists a star-forest $F_{j},\,j\neq i,$ which contains $P_{1}P_{l}$ along with
all the edges $P_{1}P_{2},P_{1}P_{3},\ldots,P_{1}P_{l-1}$ or along with all
the edges $P_{2}P_{l},$ $P_{3}P_{l},\ldots,$ $P_{l-1}P_{l}$. The edges of
$F_{j}$ are marked _red_. We distinguish two cases depending on these two
possibilities.

Case 1: _The edges $P_{1}P_{2},P_{1}P_{3},\ldots,P_{1}P_{l}$ belong to
$F_{j}$._

We make two changes. See Figure 1.

Figure 1: In Case 1, recolor $P_{1}P_{2},\ldots,P_{1}P_{l}$ from red to blue,
and all blue stars spanned by $\\{P_{2},\ldots,P_{l}\\}$ to red. A dotted line
marks the absence of an edge.

Step 1: Remove the edges $P_{1}P_{2},P_{1}P_{3},\ldots,P_{1}P_{l}$ from
$F_{j}$ and add all of them to $F_{i}$ (unless they were already in $F_{i}$).

Then $P_{1}P_{k+1}$ will satisfy condition (i) of definition 6 in $F_{i}$
(with $a=1$). However, in the process, we may have created some crossings
within $F_{i}$, and $F_{i}$ may also cease to be a star-forest. Both of these
problems can be avoided by performing

Step 2: Remove from $F_{i}$ all (blue) edges connecting two elements of
$\\{P_{2},P_{3},\ldots,P_{l}\\}$ and add them to $F_{j}$.

Note that by recoloring the blue edges within $\\{P_{2},P_{3},\ldots,P_{l}\\}$
to red, we do not violate the condition that $F_{j}$ is a plane star-forest.
Indeed, unless $l=2$, originally, no element of
$\\{P_{2},P_{3},\ldots,P_{l}\\}$ was connected by a red edge to any vertex
other than $P_{1}$. Also by Observation 7, neither of the two steps results in
any previously supported edge becoming unsupported.

Case 2: _The edges $P_{2}P_{l},P_{3}P_{l},\ldots,P_{l-1}P_{l}$ belong to
$F_{j}$._

First, we will modify $F_{i}$ by including the edge $P_{1}P_{l}$. This will
require some care, to make sure that the new covering does not violate the
conditions. See Figure 2.

Figure 2: In Case 2, $P_{1}P_{l}$ will have two colors: red and blue. Remove
the color blue from all previously blue edges incident to $P_{l}$.

Step 1: Add the edge $P_{1}P_{l}$ to $F_{i}$, but also keep it in $F_{j}$.
Remove from $F_{i}$ all other edges incident to $P_{l}$.

Notice that after performing this step, we still have a covering of $K_{n}$ by
plane star-forests. It is a _covering_ , because all edges deleted from
$F_{i}$ also belonged, and continue to belong, to $F_{j}$. Obviously, $F_{i}$
remains a _star-forest_ : its component containing $P_{1}$ remains a star,
because we removed from $F_{i}$ any other edge incident to $P_{l}$. Finally,
$F_{i}$ remains a _plane graph_ , because its newly added edge, $P_{1}P_{l}$
cannot cross any other blue edge. Indeed, such an edge should be incident to
$P_{l+1}$, contradicting our assumption that $P_{1}P_{k+1}$ originally
belonged to a star in $F_{i}$, whose center is $P_{1}$. Also note that edges
incident to $P_{l}$ in $F_{i}$ form a connected component which is already in
$F_{j}$. So removing them is equivalent to recoloring them as red, which, by
Observation 7, does not make any already supported edge unsupported.

Now we go back to the beginning of the proof, and again find the largest index
$l^{\prime}$ such that $P_{1}P_{l^{\prime}}$ does not belong to $F_{i}$.
Obviously, we have $l^{\prime}<l$. As before, we distinguish two cases. In
Case 1, we conclude that $P_{1}P_{k+1}$ satisfies condition (i) of Definition
6 in $F_{i}$ (with $a=1$), and we are done with the induction step. In Case 2,
we can include the edge $P_{1}P_{l^{\prime}}$ in $F_{i}$. Continuing like
this, in fewer than $k$ steps, we arrive at a situation where either
$P_{1}P_{k+1}$ satisfies condition (i) of definition 6 in $F_{i}$, or one by
one, we manage to include all of the edges
$P_{1}P_{k+1},P_{1}P_{k},\ldots,P_{1}P_{3},P_{1}P_{2}$ in $F_{i}$, which again
means that $P_{1}P_{k+1}$ satisfies condition (i) of definition 6 in $F_{i}$.
This completes the proof of Lemma 8.

Applying the lemma with $k=n-1$ and $a=1$, we can construct a covering of
$K_{n}$ by fewer than $n-1$ plane star-forests such that one of them, again
denoted by $F_{i}$, has the property that either
$P_{1}P_{2},P_{1}P_{3},\ldots,P_{1}P_{n}$ belong to $F_{i}$, or
$P_{1}P_{n},P_{2}P_{n},\ldots,P_{n-1}P_{n}$ belong to $F_{i}$. That is,
$F_{i}$ is a single star of degree $n-1$, centered at $P_{1}$ or $P_{n}$.
Deleting $P_{1}$ or $P_{n}$, resp., from $K_{n}$, we obtain a covering of
$K_{n-1}$ with fewer than $n-2$ plane star-forests, which contradicts our
assumption that Theorem 1 is true for decompositions and, hence, for coverings
of the complete convex geometric graph $K_{n-1}$. This completes the proof of
Theorem 1.

##  3 2-Star-Forests–Proof of Theorem 4

###### Proof

Let $V$ be an $n$-element set, and let $V=V_{1}\cup V_{2}\cup V_{3}\cup V_{4}$
be a partition of $V$ into $4$ subsets as equal as possible. Suppose without
loss of generality that

$\lfloor n/4\rfloor\leq|V_{1}|\leq|V_{2}|\leq|V_{3}|\leq|V_{4}|\leq\lceil
n/4\rceil.$

Let $f:V_{2}\rightarrow V_{1}$ be a surjection (onto mapping). For every $u\in
V_{2}$, consider the two-star-forest $F_{u}$ consisting of all edges
connecting $u$ to a every vertex in $V_{2}\cup V_{3}$, and connecting $f(u)$
to every vertex in $V_{1}\cup V_{4}$. These two-star-forests completely cover
all edges within $V_{2}$ and $V_{1}$, and all edges in $V_{1}\times V_{4}$ and
in $V_{2}\times V_{3}$. In a similar manner, we can construct $|V_{4}|$ two-
star-forests that cover all edges within $V_{4}$ and $V_{3}$, and all edges in
$V_{4}\times V_{2}$ and $V_{3}\times V_{1}$. Finally, with $|V_{3}|$ two-star-
forests (with one center in $V_{3}$ and one in $V_{1}$), we can cover all
edges in $V_{3}\times V_{4}$ and $V_{1}\times V_{2}$. Thus, we covered $K_{n}$
with $|V_{2}|+|V_{3}|+|V_{4}|=\lceil 3n/4\rceil$ two-star-forests, as
required.

Next, we show that $K_{n}$ cannot be covered by fewer than $\lceil 3n/4\rceil$
two-star-forests, for any $n\geq 4$. The case $n=4$ is easy. The proof is by
contradiction. Let $n$ be the smallest value greater than $4$ for which there
exists a covering of $K_{n}$ by $t\leq\lceil 3n/4\rceil-1$ two-star-forests.
Denote the two-star-forests participating in such a covering by
$F_{1},\ldots,F_{t}$. If any $F_{i}$ has only one center, then deleting it
from $K_{n}$, together with all edges incident to it, we reduce the number of
vertices by $1$ and the number of two-star-forests by $1$. This would
contradict the minimal choice of $n$. Thus, we can and will assume that every
$F_{i},\ 1\leq i\leq t,$ has two centers.

Now consider a graph $G$ with the same set of vertices as $K_{n}$, and for
every 2-star-forest $F_{i}$, draw an edge in $G$ between the two centers of
stars in $F_{i}$. The resulting graph $G$ has at most $\lceil 3n/4\rceil-1$
edges and, therefore, at least $n-\lceil 3n/4\rceil+1$ connected components.
Note that $3(n-\lceil 3n/4\rceil+1)>\lceil 3n/4\rceil-1$, so there exists a
connected component $C$ in $G$ with fewer than $3$ edges.

If $C$ is a single vertex $u$, then by construction it cannot be the center of
any two-star-forest. Thus, we would need at least $n-1$ two-star-forests just
to cover the edges incident to $u$ in $K_{n}$. If $C$ consists of only one
edge $u_{1}u_{2}$, then neither of these vertices can be the center of any
other two-star-forest. Thus, the edge $u_{1}u_{2}$ was not covered by any two-
star-forest $F_{j}$, which is a contradiction. Finally, if $C$ consists of two
edges, $u_{1}u_{2}$ and $u_{1}u_{3}$, say, then it is not difficult to see
that at least one of the edges between $u_{1},u_{2},u_{3}$ in $K_{n}$ is not
covered by any two-star-forest $F_{j}$. In each of the above cases, we
obtained a contradiction. This completes the proof of Theorem 4.

In view of Theorem 4, we state the following conjecture.

###### Conjecture 9

For any $n\geq k\geq 2$, the number of $k$-star-forests needed to cover the
complete graph $K_{n}$ is at least
$\big{\lceil}\frac{(k+1)n}{2k}\big{\rceil}$.

For $k=2$, the conjecture is true, by Theorem 4. We construct an example
inspired by the construction in [2], showing that Conjecture 9, if true, is
best possible. For simplicity, we describe it only for the case where $n$ is
divisible by $2$. Assuming $n=2t$, and labeling the vertices by
$\\{v_{1},v_{2},\cdots,v_{n}\\}$, we create $t$ $2$-star-forests
$F_{1},F_{2},\cdots F_{t}$ by picking vertices $v_{i}$ and $v_{i+t}$ as
centers of $F_{i}$, $1\leq i\leq t$ and connecting $v_{i}$ to all vertices
$v_{j}$, $i<j<i+t$, and connecting $v_{i+t}$ to all vertices $v_{j+t}$,
$i<j<i+t$ (the indices are taken modulo n). The introduced $2$-star-forests
cover all edges of $K_{n}$, except the set of edges $v_{i}v_{i+t}$ which can
be simply decomposed into $\lceil\frac{n}{2k}\rceil$ $k$-star-forests.
Altogether, $K_{n}$ can be covered by $\frac{n}{2}+\lceil\frac{n}{2k}\rceil$
$k$-star-forests.

## References

  * [1] O. Aichholzer, J. Obenaus, J. Orthaber, R. Paul, P. Schnider, R. Steiner, T. Taubner, and B. Vogtenhuber: Edge partitions of complete geometric graphs. _38th International Symposium on Computational Geometry (SoCG 2022)_ (2022)
  * [2] J. Akiyama and M. Kano: Path factors of a graph. In: _Graphs and Applications (Boulder, Colo., 1982)_ , Wiley-Intersci. Publ., Wiley, New York, 1985, 1–21.
  * [3] G. Araujo, A. Dumitrescu, F. Hurtado, M. Noy, and J. Urrutia: On the chromatic number of some geometric type Kneser graphs, _Comput. Geom._ 32 (2005), no. 1, 59–69.
  * [4] S. Avital and H. Hanani: Graphs, continuation (in Hebrew), _Gilyonot Le’matematika_ 3 (1966), no. 2, 2–8.
  * [5] P. Bose, F. Hurtado, E. Rivera-Campo, and David R. Wood: Partitions of complete geometric graphs into plane trees, _Comput. Geom._ 34 (2006), no. 2, 116–125.
  * [6] V. Dujmović and D. R. Wood: Graph treewidth and geometric thickness parameters, _Discrete Comput. Geom._ 37 (2007), no. 4, 641–670.
  * [7] R. L. Graham and H. O. Pollak: On the addressing problem for loop switching, _Bell System Tech. J._ 50 (1971), 2495–2519.
  * [8] Y. S. Kupitz: _Extremal Problems of Combinatorial Geometry, Lecture Notes Series_ 53, Aarhus University, Denmark, 1979.
  * [9] L. Lovász: On covering of graphs. In: _Theory of Graphs (Proc. Colloq., Tihany, 1966),_ 231–236 Academic Press, New York, 1968, 231–266.
  * [10] C. St. J. A. Nash-Williams: Decomposition of finite graphs into forests, _J. London Math. Soc._ 39 (1964), 12.
  * [11] J. Pach: The beginnings of geometric graph theory, in: _Erdős centennial, Bolyai Soc. Math. Stud._ 25, János Bolyai Math. Soc., Budapest, 2013, 465–484.
  * [12] V. G. Vizing: On an estimate of the chromatic class of a p-graph (in Russian), _Diskret. Analiz_ (1964), no. 3, 25–30.


# Panoptic Scene Graph Generation with Semantics-Prototype Learning

Li Li1, Wei Ji1*, Yiming Wu2, Mengze Li3, You Qin1, Lina Wei4, Roger
Zimmermann1 Corresponding Author.

###### Abstract

Panoptic Scene Graph Generation (PSG) parses objects and predicts their
relationships (predicate) to connect human language and visual scenes.
However, different language preferences of annotators and semantic overlaps
between predicates lead to biased predicate annotations in the dataset, i.e.
different predicates for the same object pairs. Biased predicate annotations
make PSG models struggle in constructing a clear decision plane among
predicates, which greatly hinders the real application of PSG models. To
address the intrinsic bias above, we propose a novel framework named ADTrans
to adaptively transfer biased predicate annotations to informative and unified
ones. To promise consistency and accuracy during the transfer process, we
propose to observe the invariance degree of representations in each predicate
class, and learn unbiased prototypes of predicates with different intensities.
Meanwhile, we continuously measure the distribution changes between each
presentation and its prototype, and constantly screen potentially biased data.
Finally, with the unbiased predicate-prototype representation embedding space,
biased annotations are easily identified. Experiments show that ADTrans
significantly improves the performance of benchmark models, achieving a new
state-of-the-art performance, and shows great generalization and effectiveness
on multiple datasets. Our code is released at https://github.com/lili0415/PSG-
biased-annotation.

## Introduction

Panoptic Scene Graph Generation (PSG) (Yang et al. 2022) aims to
simultaneously detect instances and their relationships within visual scenes
(Chang et al. 2023). Instead of coarse bounding boxes used in Scene Graph
Generation (SGG) (Li et al. 2021b; Xu et al. 2017; Lin et al. 2020; Li et al.
2021a; Chen et al. 2020b; Yao et al. 2022, 2021), PSG proposed to construct
more comprehensive scene graphs with panoptic segmentation (Kirillov et al.
2019). PSG methods have the potential to bridge the gap between visual scenes
and human languages and thus has the ability to contribute to related vision-
language tasks, such as image retrieval (Johnson et al. 2015; Wang et al.
2022a, b; Lv et al. 2023), image captioning (Chen et al. 2020a; Wei et al.
2022), and visual question answering (Teney, Liu, and van den Hengel 2017; Li
et al. 2022b; Antol et al. 2015; Xiao et al. 2022; Fang et al. 2023).

Figure 1: (a) Exemplar panoptic segmentation results of an input image. (b)
present annotation transfer process. Our proposed method promotes the original
dataset (annotations in red) by identifying biased annotation and potentially
positive samples, and then adaptively and accurately transferring them to
target triplet pairs (annotation in green).

However, PSG methods currently suffer from suboptimal performance due to
biased and noisy information in generated scene graphs, stemming from the
problem of _biased annotations_.

Exploring the inference mechanism of PSG and SGG models, it is translating
visual scenes to linguistic descriptions, i.e., mapping visual instances to
subjects/objects, and their relationships to predicates. We regard the problem
above as the semantic ambiguity between predicates, and the contradictory
mappings from visual to linguistics. There are a lot of semantic overlaps and
hierarchical relationships among predicates, e.g., the superclass predicate on
for its subclass predicate standing on. Because of the semantic overlaps and
the inconsistent preferences of annotators, contradictory mappings from visual
to linguistics unavoidably exist in the training dataset, and deteriorate the
long-tail distribution problem of the training dataset. As shown in Fig. 1,
with the difficulty of applying a unified standard for annotation, annotators
tend to annotate general predicate labels (e.g., “on” and “beside”) for
simplicity instead of informative ones (e.g., “standing on” and “looking at”).
As a result, models cannot learn a consistent mapping from visual to
semantics, instead, they entangle predicate labels and the prior knowledge of
long-tail distribution, leading to serious harm for model training stage.

Previous works (Zellers et al. 2018; Yu et al. 2020; Yao et al. 2022; Xu et
al. 2017; Tang et al. 2019, 2020; Lin et al. 2020) exploit numerous model
architectures to alleviate the bias problem, but these models trained by
biased datasets achieve relatively limited performances, and cannot
fundamentally solve the problem. Zhang et al. (2022) have proposed to enhance
the training dataset by a data transfer framework, which transfers head
predicate labeled samples to tail predicate labeled ones. However, their
framework inaccurately transfers a significant number of samples, leading to
imbalanced performance among predicates.

To alleviate the biased annotation problem, we propose to construct a promised
and reasonable dataset, which includes plentiful samples with consistent
predicate annotation. Specifically, there exist two types of predicates that
need to be refined: indistinguishable triplet pairs with semantic ambiguity
and potentially positive samples missed by annotators (Zhang et al. 2022). We
transfer these two kinds of biased annotations to high-quality consistent
predicate annotations (Zhang et al. 2023; Lv et al. 2022).

We introduce a new adaptive data transfer framework named ADTrans for PSG. Our
framework emphasizes consistency during the data transfer process, and
performs the data transfer process adaptively and accurately. Besides the
prior knowledge of dataset distribution, we believe textual information
alignment helps in building consistency during the data transfer process. A
general way is leveraging language models to extract semantic embeddings,
however, words embedding vectors generated by language models often have high
similarity because of the broad class intersection of the open world, leading
to the misalignment of the textual domain and the relationship domain. Thus,
we propose a prototype-based predicate representation learning method.
Unbiased predicate representations are expected to share invariant features
within each predicate class. Thus, we employ contrastive learning to increase
intra-class cohesion and inter-class separation, while focusing more on hard
samples (visually similar predicates). Meanwhile, we observe the invariance
degree of representations in each predicate class, and learn predicate
prototypes with dynamic intensities. We continuously measure the distribution
changes between each presentation and its prototype, and constantly screen
potentially biased data. Finally, with the unbiased predicate representation
embedding space, biased annotations are easily identified and transferred.

In summary, the following contributions are made in this paper:

  * •

A novel, plug-and-play framework named ADTrans is proposed, which aims at
adaptively and accurately performing data transfer to promise a reasonable
dataset with informative and standard-unified labels, and more solid training
samples.

  * •

We propose a new prototype-based predicate representation learning method,
aiming at a reasonable information alignment process between the textual
domain and the relationship domain, to promise consistency during the data
transfer process.

  * •

Comprehensive experiments demonstrate that the proposed method shows validity
on two datasets, and significantly enhances the performance of benchmark
models, achZieving new state-of-the-art performances.

## Related Work

Panoptic Scene Graph Generation. SGG has gained increasing attention from the
computer vision community for its promising future in high-level vision-
language tasks (Teney, Liu, and van den Hengel 2017; Li et al. 2022b; Antol et
al. 2015; Chen et al. 2020a; Johnson et al. 2015). Early two-stage methods
divide the whole task into objects locating process and relationships
prediction process, and struggle for a better feature extraction network (Xu
et al. 2017; Zellers et al. 2018; Tang et al. 2019; Lin et al. 2020). More
recently, a novel task named Panoptic Scene Graph Generation (PSG) (Yang et
al. 2022), which points out that it will contain noisy and ambiguous pixels if
only coarse bounding boxes are provided, and aims at constructing more
comprehensive scene graphs with panoptic segmentation rather than coarse
bounding boxes. In addition, the provided ground truth panoptic segmentation
can also significantly promote the performance of even the most classic SGG
method, IMP (Xu et al. 2017).

Towards Debiasing Scene Graph Generation. (Zellers et al. 2018) first
introduces the biased prediction problem in SGG. (Tang et al. 2019) and (Chen
et al. 2019) provide a more reasonable metric (Mean Recall) aiming at
calculating the recall of each predicate label independently. To directly face
the problem, causal inference framework (Tang et al. 2020; Zhang and An 2022)
is applied to alleviate data bias during the inference process, and CogTree
(Yu et al. 2020) is designed to train models with the ability to make
informative predictions on predicate labels. More recently, (Zhang et al.
2022; Li et al. 2023a) argues that performance could be promoted if there is a
reasonable and sound dataset. However, the data transfer method in (Zhang et
al. 2022) is efficient but so rigid and inflexible that a huge number of
positive samples will be wrongly transferred due to its simple and coarse
transfer method, which will lead to a remarkable decline in recall rate of
head predicate labels. In this paper, we provide a new approach for SGG and
PSG datasets debiasing.

Figure 2: Illustration of the overall pipeline. It learns unbiased semantics-
prototypes and the learned prototypes help to promise the consistency during
data transfer process.

## Method

In this section, we first introduce the biased annotation identifying method.
Then we introduce relation representation extraction. After that, we provide
the detailed semantics-prototype learning method. Finally, the data transfer
method and resampling method are introduced.

Target Identifying. Following Zhang et al. (2022), we identify
indistinguishable triplet pairs by checking the inconsistency between the
model’s predictions and the ground truth labels. To be more specific, we use a
pre-trained model (e.g. VCTree(Tang et al. 2019)) to predict predicate labels
for every pair of ground truth subject and object pairs in the PSG training
dataset and identify possible indistinguishable predicate labels. For
potentially positive samples, we also use a pre-trained model to predict
predicate labels for every pair of ground truth subject and object labels that
have not yet been annotated with predicate labels, also known as NA samples.

### Relation Representation Extraction

To make the language model more sensitive to predicate semantics, we fine-tune
the language model with contrastive relation representation training (Li et
al. 2022a).

Robust Contrastive Training. We first collect all of the triplets that appear
in the training set. Each triplet will be converted to a sentence for language
model processing. For example, $\textless$ person, standing on, snow
$\textgreater$ will be converted to The person is standing on the snow.

Formally, given a sentence $s_{i}$ with predicate $p_{i}$ in the batch
$S=\left\\{s_{k}\right\\}_{i=k}^{N}$, we can construct its positive set
${PS}_{i}=\\{s_{k}|p_{i}=p_{k}\\}_{k\neq i}$ and negative set
${PN}_{i}=\\{s_{k}|p_{i}\neq p_{k}\\}_{k\neq i}$. With the training data, we
use a InfoNCE loss to optimize the language model:

$L_{lm}=\sum_{\mathrm{i}=1}^{\mathrm{N}}-\log\frac{f_{pos}}{f_{pos}+f_{neg}},$
(1)

where:

$f_{pos}=\sum_{s_{j}\in PS_{i}}e^{\sin\left(h_{i},h_{j}\right)/\mathrm{T}},$
(2) $f_{neg}=\sum_{s_{g}\in
NG_{i}}e^{\sin\left(h_{i},h_{g}\right)/\mathrm{T}}.$ (3)

$\mathrm{T}$ is a temperature hyper-parameter, N is batch size, $h_{i,j,g}$
are language model generated sentence representations for $s_{i,j,g}$, and
$sim\left(h_{i},h_{j}\right)$ is the cosine similarity.

To further boost the sensitivity to predicate similarity, we additionally
introduce an angular margin $m$ for the positive pairs. Formally, instead of
using the previously defined $e^{sim(h_{i},h_{j})/T}$, we use:

$e^{sim(h_{i},h_{j})/\mathrm{T}}\to e^{cos(\theta_{i,j}+m)/\mathrm{T}},$ (4)

where $\theta_{i,j}$ is the arc-cosine similarity between $i$ and $j$. Thus,
$f_{pos}$ becomes:

$f_{pos}=\sum_{s_{j}\in PS_{i}}e^{cos(\theta_{i,j}+m)/\mathrm{T}}.$ (5)

Alignment with Visual Domain. There is typically a domain gap between the
visual domain and the textual domain, i.e., the textual similar predicates are
not visually similar. To align the language model with the visual domain (Li
et al. 2023b; Fang et al. 2022), we try to incorporate some visual prior
knowledge into the language model fine-tuning.

Specifically, we take advantage of the confusion matrix
$C\in\mathbf{R}^{Q\times Q}$ generated by a pre-trained VCTree model, where
$Q$ is the number of predicates in the dataset, and $C_{i,j}$ denotes the
averaged prediction score for predicate $p_{j}$ on all examples annotated with
$p_{i}$. When $C_{i,j}$ is near to 1 (very high), $p_{i}$ and $p_{j}$ are
visually similar and when $C_{i,j}$ is near to 0 (very low), $p_{i}$ and
$p_{j}$ are visually different.

For the language model training, we expect the language model to be aligned
with the visual domain similarity judgment. Thus, the language model should
also distinguish the visually different predicate pairs but avoid the visually
similar predicate pairs from being too distant in the feature space. The
metric $1-C_{i,j}$ can satisfy our requirement.

Formally, we add $1-C_{i,j}$ as a weight for negative pairs:

$e^{cos\left(\theta_{i,j}\right)/\mathrm{T}}\to\left(1-C_{i,j}\right)\times
e^{cos\left(\theta_{i,j}\right)/\mathrm{T}}.$ (6)

Then, the $f_{neg}$ becomes:

$f_{neg}=\sum_{s_{g}\in
PN_{i}}\left(1-C_{i,g}\right)e^{\cos\left(\theta_{i,g}\right)/\mathrm{T}}.$
(7)

Invariant Representation Exploration. We propose the invariant representation
exploration to further promise the unbiased representation of predicates.

Specifically, we say that an unbiased representation $\Phi:X\to H$ elicits an
invariant predictor $\omega$ across positive set $\varepsilon$ if there is an
optimizer $\omega:H\to Y$ simultaneously optimal for all samples from the
positive set. The learning objective can be formulated as:

$\omega\in argmin_{\bar{\omega}:H\to Y}O^{e}(\omega,\Phi).$ (8)

Eq. 8 tries to learn a feature representation from $\Phi(\cdot)$ that can
induce an optimizer $\omega(\cdot)$ which is simultaneously optimal for all
$e\in\varepsilon$. Thus, we propose the invariant representation
regularization which can be formulated as:

$L_{irm}=\sum_{i=1}^{N}\lambda Var(L^{i}),$ (9)

where $L^{i}=\left\\{L_{lm}\left(j\right)|p_{i}=p_{j}\right\\}$ denotes the
loss values of samples from the positive set, and $\lambda$ is a hyper-
parameter. The minimization of variances of loss values encourages unbiased
representation learning for each predicate class (Arjovsky et al. 2020).

Method | Scene Graph Generation
---|---
R@20 | R@50 | R@100 | mR@20 | mR@50 | mR@100 | PR@20 | PR@50 | PR@100
Two-Stage | IMP (Xu et al. 2017) | 16.5 | 18.2 | 18.6 | 6.52 | 7.05 | 7.23 | 12.9 | 13.7 | 13.9
+IETrans (Zhang et al. 2022) | 14.5 | 15.9 | 16.4 | 10.2 | 11.0 | 11.3 | 14.5 | 15.4 | 15.7
+ADTrans | 15.0 | 16.5 | 17.0 | 12.5 | 13.5 | 14.0 | 16.0 | 17.1 | 17.5
VCTree (Tang et al. 2019) | 20.6 | 22.1 | 22.5 | 9.70 | 10.2 | 10.2 | 16.0 | 16.8 | 16.9
+IETrans (Zhang et al. 2022) | 17.5 | 18.9 | 19.3 | 17.1 | 18.0 | 18.1 | 19.6 | 20.5 | 20.7
+ADTrans | 17.9 | 19.5 | 19.9 | 18.0 | 18.9 | 19.0 | 20.2 | 21.2 | 21.4
MOTIFS (Zellers et al. 2018) | 20.0 | 21.7 | 22.0 | 9.10 | 9.57 | 9.69 | 15.5 | 16.3 | 16.5
+IETrans (Zhang et al. 2022) | 16.7 | 18.3 | 18.8 | 15.3 | 16.5 | 16.7 | 18.2 | 19.4 | 19.7
+ADTrans | 17.1 | 18.6 | 19.0 | 17.1 | 18.0 | 18.5 | 19.4 | 20.4 | 20.8
GPSnet (Lin et al. 2020) | 17.8 | 19.6 | 20.1 | 7.03 | 7.49 | 7.67 | 13.6 | 14.4 | 14.7
+IETrans (Zhang et al. 2022) | 14.6 | 16.0 | 16.7 | 11.5 | 12.3 | 12.4 | 15.3 | 16.2 | 16.5
+ADTrans | 17.8 | 19.2 | 19.5 | 16.5 | 17.5 | 17.6 | 19.3 | 20.3 | 20.5
One-Stage | PSGTR (Yang et al. 2022) | 28.4 | 34.4 | 36.3 | 16.6 | 20.8 | 22.1 | 21.9 | 26.3 | 27.6
+IETrans (Zhang et al. 2022) | 25.3 | 28.8 | 29.2 | 23.1 | 27.2 | 27.5 | 24.9 | 28.4 | 28.7
+ADTrans | 26.0 | 29.6 | 30.0 | 26.4 | 29.7 | 30.0 | 27.1 | 30.2 | 30.5
Table 1: The results (R@K, mR@K and PR@K) on SGDet task of our method and
other baselines on PSG dataset. IETrans and ADTrans denote models equipped
with different dataset-enhancement methods.

### Semantics-prototype Learning

The extracted relation representation may be suffered from possibly biased
annotations. Thus, we utilize dynamic prototype learning to maximize the
discriminative power between predicate classes. We measure the invariance
within each predicate class, and discard biased data by stage. This promise
unbiased predicate representation embedding space for accurate data transfer.

Dynamic Prototype Updating. To build an unbiased embedding space for
predicates, we further propose to construct the prototype space for
predicates. Specifically, we specify the total prototype space
$P_{type}\in\mathbf{R}^{L\times Q}$, where $L$ is the same as the size of
semantic embedding. Then we dynamically update the prototype space depending
on the degree of invariance during the robust contrastive training process.

Given a batch $S$, we can construct multiple positive sets
$PS=\left\\{ps_{1},ps_{2},...,ps_{P}\right\\}$ with different predicates,
where $P$ is the number of different predicates in the batch $S$.

For every positive set in the $PS$ with predicate $p_{i}$, we obtain its
average predicate representation embedding as follows:

$H_{aver}^{p_{i}}=\frac{1}{N^{p_{i}}}{\textstyle\sum_{s=1}^{N^{p_{i}}}}h_{i},$
(10)

where $N^{p_{i}}$ denotes the number of samples with predicate $p_{i}$ in the
batch $S$, and $h_{i}$ denotes the predicate representation embedding. We
average the summation of all predicate representations with the same predicate
in the batch to get the average feature embedding.

With the help of observed invariant representation, we update the prototype
space for predicate $p_{i}$ with a moving average approach:

$P_{type}^{p_{i}}=\beta P_{type}^{p_{i}}+(1-\beta)\underbrace{\frac{1}{\gamma
Var(L^{i})N^{p_{i}}}}_{Approach\;Speed}(H_{aver}^{p_{i}}-P_{type}^{p_{i}}),$
(11)

where $\beta$ and $\gamma$ are hyper-parameters.

Multistage Data Filtration. Biased and noisy samples in the training dataset
are certain to influence the unbiased predicate representation learning
process. Thus, We design the multistage data filtration to multistage-ly
filter out these bad samples. Specifically, we take advantage of the invariant
representation regularization and the sample-prototype distribution shift as
the measurements for the sample’s quality.

Figure 3: R@100 for predicates under SGDet task among plain PSGTR, and PSGTR
with ADTrans. ADTrans achieves more balanced and effective predicate
discrimination among predicates with different frequencies than plain PSGTR
(The horizontal axis, moving from left to right, illustrates predicates
arranged in order of high frequency to low frequency).

For every training epoch, we collect $V\in\mathbf{R}^{G}$ from Eq. 9, which
denotes the variance of loss values of every training sample in the training
dataset with $G$ samples. Then we average the collected variances on predicate
labels, getting $V_{aver}\in\mathbf{R}^{Q}$. For every sample $S_{i}$ with
predicate label $p_{i}$ and variance $V_{i}$ in the training dataset, we judge
whether it is part of potentially biased and noisy samples, which can be
formulated as:

$P_{bn}=\left\\{S_{i}|V_{i}>\mu
V_{aver}^{i}(H_{aver}^{p_{i}}-P_{type}^{p_{i}})\right\\},$ (12)

where $V_{aver}^{i}$ denotes the averaged variance on predicate label $p_{i}$,
and $\mu$ is a hyper-parameter. We further sort $P_{bn}$ by the loss value
derived from Eq. 1 and drop out the top $D\%$ of training data. If there are
fewer than 100 samples in a predicate class, we do not drop out any more
samples from it.

The multistage data filtration avoids the influence of a large number of
biased annotations (outlier noise). Thus, the whole unbiased predicate
representation learning process promises the unbiased representation of
predicates.

### Data Transfer

As a result, a similarity matrix $S\in\mathbf{R}^{Q\times Q}$ can be generated
by calculating the cosine similarities between all prototypes.

For indistinguishable triplets, we directly use the similarity score as an
adaptive transfer ratio.

For potentially positive samples, we further define an influence factor, where
the intuition is to transfer more data for the scarce relation triplets with
low NA scores.

Formally, the influence factor is:

${E}_{\left(s_{i},p_{i},o_{i}\right)}=\sqrt{-log\left({NA}_{score}\right)\times{\rm
c}_{\left(si,oi\right)}\times{c}_{p_{i}}},$ (13)

where $-log(NA_{score})$ is the NA score, $c(s_{i},o_{i})$ is the scarcity of
triplets with subject $s_{i}$ and $o_{i}$, and $c_{p_{i}}$ is the scarcity of
triplets with predicate $p_{i}$.

In practice, we further normalize $c_{(s_{i},o_{i})}$ with softmax.

To judge whether a NA sample should be transferred, we rank all potential
target triplet pairs according to their influence factors, and conduct the
transfer of top $K_{g}\%$ pairs.

### Resampling

Without conflicts, we can directly integrate the transferred indistinguishable
pairs and potentially positive pairs. Furthermore, a special re-sampling
method is introduced on the integrated dataset to enhance it further. We
propose a new repeat factor for the task. For every triplet
$(s_{i},p_{i},o_{i})$ in each image, we calculate its repeat factor as:

${R}=max\left(1,t\times{\rm
c}_{\left(si,oi\right)}\times{c}_{\left(p_{i}\right)}\right),$ (14)

where t is a hyper-parameter controlling the possible repeat times. The
maximum value of the repeat factor within each image is then selected.

## Experiment

### Dataset and Evaluation Metrics

Dataset. We evaluate our method on Visual Genome (Krishna et al. 2017) and PSG
dataset (Yang et al. 2022).

Figure 4: Visualization of plain PSGTR model and PSGTR equipped with our
ADTrans. PSGTR with ADTrans can predict relationships between instances with
greater accuracy and also select predicates that better match the visual
scene.

Evaluation Metric. Following previous works (Tang et al. 2020; Zellers et al.
2018), we take recall@K (R@K) and mean recall@K (mR@K)(Tang et al. 2019; Chen
et al. 2019) as evaluation metrics. We also adopt a new evaluation metrics
named percentile recall (PR), which can be formulated as
$PR=30\%R+60\%mR+10\%PQ$, where PQ measures the quality of a predicted
panoptic segmentation relative to the ground truth (Kirillov et al. 2019). For
conventional SGG tasks on the VG dataset, we also adopt an overall metric F@K
(Zhang et al. 2022), which is the harmonic average of R@K and mR@K.

Method | Predicate Classification
---|---
mR@20 | @50 | @100 | F@20 | @50 | @100
MOTIFS | 11.7 | 15.2 | 16.2 | 19.5 | 24.5 | 26.0
+ADTrans | 29.0 | 36.2 | 38.8 | 36.1 | 41.7 | 43.5
VCTree | 14.0 | 16.3 | 17.7 | 22.7 | 26.0 | 28.0
+ADTrans | 30.0 | 32.9 | 35.5 | 37.2 | 40.5 | 42.5
GPSnet | 13.2 | 15.0 | 16.0 | 21.7 | 24.4 | 25.8
+ADTrans | 27.3 | 32.0 | 34.7 | 34.8 | 40.2 | 42.1
Table 2: The results (mR@K and F@K) on PREDCLS task of our method and other
baselines on VG dataset.

### Tasks and Implementation Details

Tasks. We evaluate our method on three classic SGG tasks: Predicate
Classification (PREDCLS), Scene Graph Classification (SGCLS) and Scene Graph
Generation (SGDET).

Implementation Details. For the pre-trained language model, we use pre-trained
BERT-base (Devlin et al. 2019). The decision margin m is set to 10 degrees,
the temperature hyper-parameter T is set to 0.05, and we use an AdamW
(Loshchilov and Hutter 2017) optimizer with a learning rate 2e-5. The hyper-
parameter $\lambda$ is set to 0.3, $\beta$ is set to 5e5, and $\gamma$ is set
to 1.5. The $D$ in multistage data filtration is set to 50. For NA sample
transfer, the value of $K_{g}$ is set to 0.05, and for the re-sampling
process, the value of $t$ is set to 3e7.

### Qualitative Analysis

As shown in Figure 4, we can compare results predicted by plain PSGTR and
PSGTR equipped with our ADTrans. Obviously, PSGTR with ADTrans can predict
more accurate relationships between instances and also predict predicate that
better fits the scene. We believe our method helps construct a more
comprehensive scene graph.

### Comparison with State-of-the-Art Methods

In this section, we report the results for ADTrans on different datasets,
tasks, and baseline methods. All models use ResNet-50 (He et al. 2016) as
their backbones.

Method | Scene Graph Classification
---|---
mR@20 | @50 | @100 | F@20 | @50 | @100
MOTIFS | 6.0 | 8.0 | 8.5 | 10.1 | 13.1 | 13.8
+ADTrans | 14.8 | 17.0 | 17.8 | 20.2 | 22.5 | 23.7
VCTree | 6.3 | 7.5 | 8.0 | 10.7 | 12.5 | 13.3
+ADTrans | 16.0 | 19.0 | 19.8 | 20.3 | 23.7 | 24.5
GPSnet | 10.0 | 11.8 | 12.6 | 15.7 | 17.9 | 18.9
+ADTrans | 15.5 | 18.2 | 18.8 | 19.9 | 22.5 | 23.7
Table 3: The results (mR@K and F@K) on SGCLS task of our method and other
baselines on VG dataset.

Effectiveness of ADTrans. From the results, we observe that our method can
effectively improve the performance of baseline networks in nearly all
metrics. Fig. 3 presents a comparison between our method and plain PSGTR of
the detailed recall@100 of SGDet task on part of predicate classes. ADTrans
performs better than plain PSGTR on almost all the above predicate classes.
When compared to IETrans (Zhang et al. 2022), our method shows significant
improvements in both recall and mean recall on all baseline models, indicating
that our method can enhance the training dataset more effectively, avoiding
noisy or redundant transfer processes. When it comes to PR, which takes into
account both recall and mean recall, our method outperforms all the original
models by significant margins. This suggests that our method not only improves
the recall of the models but also balances the performance across different
predicate labels, resulting in a more comprehensive evaluation of the models’
performance.

Method | Scene Graph Generation
---|---
mR@20 | @50 | @100 | F@20 | @50 | @100
MOTIFS | 4.8 | 6.2 | 7.1 | 8.0 | 10.3 | 11.8
+ADTrans | 10.6 | 15.5 | 18.1 | 13.4 | 18.9 | 22.0
VCTree | 5.2 | 6.7 | 7.9 | 8.7 | 11.0 | 13.0
+ADTrans | 9.7 | 12.5 | 16.9 | 12.2 | 16.3 | 20.3
GPSnet | 5.2 | 5.9 | 7.1 | 8.6 | 9.9 | 11.8
+ADTrans | 12.3 | 15.8 | 19.2 | 15.1 | 18.6 | 21.9
Table 4: The results (mR@K and F@K) on SGDET task of our method and other baselines on VG dataset. Module | Scene Graph Generation
---|---
IT | PT | RE | R/mR@20 | R/mR@50 | R/mR@100
✗ | ✗ | ✗ | 28.4 / 16.6 | 34.4 / 20.8 | 36.3 / 22.1
✔ | ✗ | ✗ | 26.2 / 24.9 | 30.3 / 28.2 | 30.7 / 29.2
✔ | ✔ | ✗ | 25.5 / 25.6 | 29.2 / 29.1 | 29.7 / 29.6
✔ | ✔ | ✔ | 26.0 / 26.4 | 29.6 / 29.7 | 30.0 / 30.0
Table 5: Ablation study on model components. IT: Indistinguishable Triplet
Transfer; PT: Potential Positive Transfer; RE: re-sampling.

Expansibility of ADTrans. Applied with our ADTrans, the performances of all
baseline models trained on all the datasets on all the tasks are greatly
improved. With the observation that all the baseline models trained on the VG
dataset have poorer performances compared to the same baseline models trained
on the PSG dataset, VG dataset is more challenging for our ADTrans due to more
biased annotations. Our method shows great expansibility on VG dataset,
baseline models trained on the dataset achieve competitive performances on all
the tasks.

Figure 5: Visualization of the original dataset and a new dataset enhanced by
our ADTRans. For the same image, we visualize its original biased annotations,
and new annotations enhanced by our method. The enhanced dataset shows more
informative annotations than the original one. These informative annotations
promise the consistent training of models.

### Ablation Studies

Different components in ADTrans framework. We evaluate the importance of each
component in our ADTrans. As shown in Table. 5, we incrementally add one
component to the plain baseline PSGTR (Yang et al. 2022) to validate their
effectiveness. The indistinguishable triplet transfer component provides the
most promotion on performance. The reason is that, we transfer these
inconsistent annotations to informative and consistent ones, so that models
can learn a consistent mapping from visual to predicates. The potentially
positive transfer component additionally provides performance promotion. Our
ADTrans transfers original NA samples, which are probably missed by
annotators, to informative annotations. This step provides more reasonable
training samples to construct a consistent training dataset.

Data Processing Method | SGDet
---|---
mR@20 | mR@50 | mR@100
Original | 16.6 | 20.8 | 22.1
Remove | 20.0 | 24.6 | 25.3
Triplet Transfer | 24.9 | 28.2 | 29.2
Table 6: Ablation study on data processing methods. Triplet Transfer:
Indistinguishable triplet transfer. Remove: simply removing all
indistinguishable triplet pairs. Original: baseline method on the original
dataset.

Different data processing methods during triplet transfer. To prove the
effectiveness of our indistinguishable triplet transfer method and the harm of
biased annotation, we design another simple method to process
indistinguishable triplet pairs. Instead of adaptively transferring them to
target pairs, we simply remove them from the original training dataset. As
shown in Table. 6, when comparing the simply removing method and the original
baseline, the simply removing method surprisingly greatly overtakes the
baseline model, indicating the serious conflict resulting from biased
annotation within the original dataset. These biased annotated samples can not
help the model during the training process, but will make it difficult for the
model to distinguish each predicate label, resulting in a sharp decline in
model performance. When comparing the triplet transfer method and the simply
removing method, there are also great margins between these two methods. With
the fact that our triplet transfer method greatly outperforms the simply
removing method, we observe a promising textual information alignment process
and the effectiveness of our adaptive triplet transfer method is proved.

Contrastive Learning Method | SGDet
---|---
mR@20 | mR@50 | mR@100
Original | 16.6 | 20.8 | 22.1
InfoNCE | 21.0 | 25.8 | 26.3
RCT | 26.4 | 29.7 | 30.0
Table 7: Ablation study on contrastive learning methods. InfoNCE: the classic
contrastive learning method. Original: the performance of original PSGTR. RCT:
the proposed robust contrastive training method.

Different contrastive learning methods. As shown in Table. 7, though we
observe improvement with the help of the InfoNCE, we can promote the model to
a higher level with our method. An simply InfoNCE method increase the intra-
class cohesion and inter-class separability, but cannot learn unbiased
predicate representations because of biased annotations. As a result, biased
annotations are inconspicuous and hard to be identified in a biased predicate
representation embedding space. Our method utilizes invariant representation
exploration and multistage data filtration to avoid the influence of biased
annotations, and performs accurate biased-annotation identification.

## Conclusion

We introduce a novel framework named ADTrans to alleviate the biased
annotation problem in SGG. ADTrans transfers indistinguishable samples and
potentially positive samples to promise a reasonable training dataset with
more informative and standard-unified labels. Experiments demonstrate that
ADTrans greatly enhances the models’ performance on two datasets, achieving a
new SOTA performance.

## Acknowledgements

This research was supported in part by the National Key R&D Program of China
(2022ZD0119103), in part by the National Natural Science Foundation of China
(Grant No. 62006123). This research was supported by the MSIT (Ministry of
Science, ICT), Korea, under the ITRC (Information Technology Research Center)
support program (IITP-2023-2020-0-01789) supervised by the IITP (Institute for
Information & Communications Technology Planning & Evaluation).

## References

  * Antol et al. (2015) Antol, S.; Agrawal, A.; Lu, J.; Mitchell, M.; Batra, D.; Zitnick, C. L.; and Parikh, D. 2015.  VQA: Visual Question Answering.  In _ICCV_.
  * Arjovsky et al. (2020) Arjovsky, M.; Bottou, L.; Gulrajani, I.; and Lopez-Paz, D. 2020.  Invariant Risk Minimization.
  * Chang et al. (2023) Chang, X.; Ren, P.; Xu, P.; Li, Z.; Chen, X.; and Hauptmann, A. 2023.  A Comprehensive Survey of Scene Graphs: Generation and Application.  _TPAMI_.
  * Chen et al. (2020a) Chen, S.; Jin, Q.; Wang, P.; and Wu, Q. 2020a.  Say As You Wish: Fine-Grained Control of Image Caption Generation With Abstract Scene Graphs.  In _CVPR_.
  * Chen et al. (2020b) Chen, T.; Kornblith, S.; Norouzi, M.; and Hinton, G. 2020b.  A Simple Framework for Contrastive Learning of Visual Representations.  In _ICML_.
  * Chen et al. (2019) Chen, T.; Yu, W.; Chen, R.; and Lin, L. 2019.  Knowledge-Embedded Routing Network for Scene Graph Generation.  In _CVPR_.
  * Devlin et al. (2019) Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In _NAACL_.
  * Fang et al. (2022) Fang, X.; Liu, D.; Zhou, P.; and Hu, Y. 2022.  Multi-modal cross-domain alignment network for video moment retrieval.  _TMM_.
  * Fang et al. (2023) Fang, X.; Liu, D.; Zhou, P.; and Nan, G. 2023.  You Can Ground Earlier than See: An Effective and Efficient Pipeline for Temporal Sentence Grounding in Compressed Videos.  In _CVPR_.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep Residual Learning for Image Recognition.  In _CVPR_.
  * Johnson et al. (2015) Johnson, J.; Krishna, R.; Stark, M.; Li, L.-J.; Shamma, D.; Bernstein, M.; and Fei-Fei, L. 2015.  Image Retrieval Using Scene Graphs.  In _CVPR_.
  * Kirillov et al. (2019) Kirillov, A.; He, K.; Girshick, R.; Rother, C.; and Dollar, P. 2019.  Panoptic Segmentation.  In _CVPR_.
  * Krishna et al. (2017) Krishna, R.; Zhu, Y.; Groth, O.; Johnson, J.; Hata, K.; Kravitz, J.; Chen, S.; Kalantidis, Y.; Li, L.-J.; Shamma, D. A.; Bernstein, M. S.; and Fei-Fei, L. 2017\.  Visual Genome: Connecting Language and Vision Using Crowdsourced Dense Image Annotations.  _IJCV_.
  * Li et al. (2023a) Li, L.; Wang, C.; Qin, Y.; Ji, W.; and Liang, R. 2023a.  Biased-Predicate Annotation Identification via Unbiased Visual Predicate Representation.  In _ACM Multimedia_.
  * Li et al. (2023b) Li, M.; Wang, H.; Zhang, W.; Miao, J.; Zhao, Z.; Zhang, S.; Ji, W.; and Wu, F. 2023b.  Winner: Weakly-supervised hierarchical decomposition and alignment for spatio-temporal video grounding.  In _CVPR_.
  * Li et al. (2022a) Li, M.; Wang, T.; Zhang, H.; Zhang, S.; Zhao, Z.; Zhang, W.; Miao, J.; Pu, S.; and Wu, F. 2022a.  Hero: Hierarchical spatio-temporal reasoning with contrastive action correspondence for end-to-end video object grounding.  In _ACM Multimedia_.
  * Li et al. (2021a) Li, R.; Zhang, S.; Wan, B.; and He, X. 2021a.  Bipartite Graph Network With Adaptive Message Passing for Unbiased Scene Graph Generation.  In _CVPR_.
  * Li et al. (2022b) Li, Y.; Wang, X.; Xiao, J.; Ji, W.; and Chua, T.-S. 2022b.  Invariant Grounding for Video Question Answering.  In _CVPR_.
  * Li et al. (2021b) Li, Y.; Yang, X.; Shang, X.; and Chua, T.-S. 2021b.  Interventional Video Relation Detection.  In _ACM Multimedia_.
  * Lin et al. (2020) Lin, X.; Ding, C.; Zeng, J.; and Tao, D. 2020.  GPS-Net: Graph Property Sensing Network for Scene Graph Generation.  In _CVPR_.
  * Loshchilov and Hutter (2017) Loshchilov, I.; and Hutter, F. 2017.  Decoupled Weight Decay Regularization.
  * Lv et al. (2022) Lv, Z.; Wang, F.; Zhang, S.; Kuang, K.; Yang, H.; and Wu, F. 2022.  Personalizing Intervened Network for Long-tailed Sequential User Behavior Modeling.  _arXiv preprint arXiv:2208.09130_.
  * Lv et al. (2023) Lv, Z.; Zhang, W.; Zhang, S.; Kuang, K.; Wang, F.; Wang, Y.; Chen, Z.; Shen, T.; Yang, H.; Ooi, B. C.; et al. 2023.  DUET: A Tuning-Free Device-Cloud Collaborative Parameters Generation Framework for Efficient Device Model Generalization.  In _WWW_.
  * Tang et al. (2020) Tang, K.; Niu, Y.; Huang, J.; Shi, J.; and Zhang, H. 2020.  Unbiased Scene Graph Generation From Biased Training.  In _CVPR_.
  * Tang et al. (2019) Tang, K.; Zhang, H.; Wu, B.; Luo, W.; and Liu, W. 2019.  Learning to Compose Dynamic Tree Structures for Visual Contexts.  In _CVPR_.
  * Teney, Liu, and van den Hengel (2017) Teney, D.; Liu, L.; and van den Hengel, A. 2017.  Graph-Structured Representations for Visual Question Answering.  In _CVPR_.
  * Wang et al. (2022a) Wang, C.; Huang, Y.; Liu, X.; Pei, J.; Zhang, Y.; and Yang, J. 2022a.  Global in local: A convolutional transformer for SAR ATR FSL.  _GRSL_.
  * Wang et al. (2022b) Wang, C.; Pei, J.; Yang, J.; Liu, X.; Huang, Y.; and Mao, D. 2022b.  Recognition in Label and Discrimination in Feature: A Hierarchically Designed Lightweight Method for Limited Data in SAR ATR.  _TGRS_.
  * Wei et al. (2022) Wei, M.; Chen, L.; Ji, W.; Yue, X.; and Chua, T.-S. 2022.  Rethinking the Two-Stage Framework for Grounded Situation Recognition.  _AAAI_.
  * Xiao et al. (2022) Xiao, J.; Yao, A.; Liu, Z.; Li, Y.; Ji, W.; and Chua, T.-S. 2022.  Video as Conditional Graph Hierarchy for Multi-Granular Question Answering.  In _AAAI_.
  * Xu et al. (2017) Xu, D.; Zhu, Y.; Choy, C. B.; and Fei-Fei, L. 2017.  Scene Graph Generation by Iterative Message Passing.  In _CVPR_.
  * Yang et al. (2022) Yang, J.; Ang, Y. Z.; Guo, Z.; Zhou, K.; Zhang, W.; and Liu, Z. 2022.  Panoptic Scene Graph Generation.  In _ECCV_.
  * Yao et al. (2022) Yao, Y.; Chen, Q.; Zhang, A.; Ji, W.; Liu, Z.; Chua, T.-S.; and Sun, M. 2022.  PEVL: Position-enhanced Pre-training and Prompt Tuning for Vision-language Models.  In _EMNLP_.
  * Yao et al. (2021) Yao, Y.; Zhang, A.; Zhang, Z.; Liu, Z.; Chua, T.-S.; and Sun, M. 2021.  CPT: Colorful Prompt Tuning for Pre-trained Vision-Language Models.
  * Yu et al. (2020) Yu, J.; Chai, Y.; Hu, Y.; and Wu, Q. 2020.  CogTree: Cognition Tree Loss for Unbiased Scene Graph Generation.  In _IJCAI_.
  * Zellers et al. (2018) Zellers, R.; Yatskar, M.; Thomson, S.; and Choi, Y. 2018.  Neural Motifs: Scene Graph Parsing With Global Context.  In _CVPR_.
  * Zhang et al. (2022) Zhang, A.; Yao, Y.; Chen, Q.; Ji, W.; Liu, Z.; Sun, M.; and Chua, T.-S. 2022.  Fine-Grained Scene Graph Generation with Data Transfer.  In _ECCV_.
  * Zhang and An (2022) Zhang, R.; and An, G. 2022.  Causal Property based Anti-Conflict Modeling with Hybrid Data Augmentation for Unbiased Scene Graph Generation.  In _ACCV_.
  * Zhang et al. (2023) Zhang, W.; Lv, Z.; Zhou, H.; Liu, J.-W.; Li, J.; Li, M.; Tang, S.; and Zhuang, Y. 2023.  Revisiting the Domain Shift and Sample Uncertainty in Multi-source Active Domain Transfer.  _arXiv preprint arXiv:2311.12905_.


Department of Physics, ETH Zurich - Lugano, Switzerland Institute of
Computational Science, Università Svizzera Italiana - Lugano, Switzerland
Italian Institute of Technology - Genova, Italy

# OPES: On-the-fly Probability Enhanced Sampling Method

Michele Invernizziinst:ethinst:usiinst:iit
inst:ethinst:ethinst:usiinst:usiinst:iitinst:iit

###### Abstract

Molecular simulations are playing an ever increasing role, finding
applications in fields as varied as physics, chemistry, biology and material
science. However, many phenomena of interest take place on time scales that
are out of reach of standard molecular simulations. This is known as the
sampling problem and over the years several enhanced sampling methods have
been developed to mitigate this issue. We propose a unified approach that puts
on the same footing the two most popular families of enhanced sampling
methods, and paves the way for novel combined approaches. The on-the-fly
probability enhanced sampling method provides an efficient implementation of
such generalized approach, while also focusing on simplicity and robustness.

##  1 Introduction

Despite the remarkable improvements over the last decades, both in
computational power and in algorithms efficiency, molecular simulations are
still limited in their scope by the sampling problem. Many phenomena of
interest, such as protein-ligand binding or crystal nucleation, are rare
events that take place on macroscopic time scales and thus would require an
impractical amount of computation to be simulated using standard molecular
dynamics or Markov-chain Monte Carlo. To circumvent this problem, a plethora
of enhanced sampling methods have been developed that aim at allowing a
simulation to visit all the relevant metastable states, without being hindered
by kinetic bottlenecks. Apart from some remarkable exceptions [1, 2], all the
most popular enhanced sampling techniques can be roughly grouped in two main
families, that we will refer to as collective variables methods and expanded
ensembles methods. We propose a unified perspective on enhanced sampling, that
allows us to develop a general method to perform both kinds of sampling in a
robust and efficient way. This new perspective makes enhanced sampling more
accessible and simpler to use and can also open up to novel sampling
strategies. The method we developed, called on-the-fly probability enhanced
sampling (OPES), is described in detail in Refs. [3] and [4]. Here we present
its main features in a synthetic fashion.

##  2 Unified approach

The goal of enhanced sampling is to increase the probability of observing in a
simulation certain rare events, and to do it in such a way that it is still
possible to retrieve statistics about the original system. We call target
distribution the modified probability distribution that is sampled instead of
the Boltzmann one. Rather than focusing on the various computational
techniques used by the different enhanced sampling methods, we propose to
group them according to how they define the target distribution they aim to
sample. Following this criteria we can identify two main families.

A first family is the one of methods such as umbrella sampling [5] and
metadynamics [6]. These methods make use of collective variables (CVs) or
order parameters that are smooth functions of the atomistic coordinates and
encode the slow modes of the system. In this family, the target distribution
is defined by requiring that its marginal probability distribution over such
CVs has a given functional form. Typically the marginal is chosen to be a
constant flat distribution, as in adaptive umbrella sampling [7], but other
choices are possible, such as the well-tempered distribution often used in
metadynamics [8].

A second family includes tempering methods, such as simulated tempering [9]
and replica exchange [10]. These methods define their target distribution as
the combination of slightly different versions of the original system, for
example the same system but at higher temperatures. These target distribution
are also known as generalized ensembles or expanded ensembles [11].

The OPES method can be used to sample either kind of target distributions. It
does so by adding to the potential energy of the system $U(\mathbf{x})$ a bias
potential $V(\mathbf{x})$ such that the sampled distribution is not the
equilibrium Boltzmann distribution, $P(\mathbf{x})\propto e^{-\beta
U(\mathbf{x})}$, but the target one, $p^{\text{tg}}(\mathbf{x})$. This bias
potential is defined as

$V(\mathbf{x})=-\frac{1}{\beta}\log\frac{p^{\text{tg}}(\mathbf{x})}{P(\mathbf{x})}\,,$
(1)

where $\beta$ is the inverse Boltzmann temperature. The bias potential is not
known a priori, but it is self-consistently learned during the simulation via
an on-the-fly estimate of the probability distributions. Statistics of the
unbiased system can be retrieved via a reweighting procedure, by assuming that
the bias is updated in an adiabatic way. Given any observable $O(\mathbf{x})$,
its ensemble average $\langle O\rangle$ over the unbiased system can be
estimated via ensemble averages over the sampled biased system:

$\langle O\rangle=\frac{\langle Oe^{\beta V}\rangle_{V}}{\langle e^{\beta
V}\rangle_{V}}\,.$ (2)

In this way also free energy differences and free energy surfaces can be
estimated [3, 4].

##  3 OPES for collective variables sampling

Given a set of collective variables $\mathbf{s}=\mathbf{s}(\mathbf{x})$, one
can define the marginal probability

$P(\mathbf{s})=\int
P(\mathbf{x})\,\delta[\mathbf{s}(\mathbf{x})-\mathbf{s}]\,d\mathbf{x}\,.$ (3)

The well-tempered ensemble with respect to these CVs is obtained by requiring
that the marginal of the target distribution is
$p^{\text{WT}}(\mathbf{s})\propto[P(\mathbf{s})]^{1/\gamma}$, where $\gamma>1$
is know as bias factor. Notice that the exact target distribution
$p^{\text{tg}}(\mathbf{x})$ is not known but this does not constitute a
problem. In fact, the core requirements are that the corresponding bias
potential can be expressed and that the target distribution is easy to sample,
thus the kinetic bottlenecks between metastable states are removed. This is
indeed guaranteed for the well-tempered distribution, given that the CVs are
chosen properly and the bias factor is large enough. The case of uniform
marginal target distribution can be seen as a special case of the well-
tempered one, where $\gamma=\infty$.

When using OPES for CVs sampling we need to estimate $P(\mathbf{s})$. To do
so, we use a weighted kernel density estimation with an automatic kernel
merging algorithm, that is explained in detail in Ref. [3]. We also introduce
a regularization term $\epsilon$ and a normalization $Z$ over the explored CV-
space. At step $n$ the bias, Eq. (1), can be written as a function of the CVs:

$V_{n}(\mathbf{s})=(1-1/\gamma)\frac{1}{\beta}\log\left(\frac{P_{n}(\mathbf{s})}{Z_{n}}+\epsilon\right)\,,$
(4)

where $P_{n}(\mathbf{s})$ is the estimate of $P(\mathbf{s})$ obtained via
reweighting. Reference [3] presents the full derivation of this expression.

##  4 OPES for expanded ensembles sampling

To define the expanded ensemble target distribution, we first define a class
of probability distributions $P_{\lambda}(\mathbf{x})\propto e^{-\beta
U_{\lambda}(\mathbf{x})}$, where $\lambda$ can be a parameter (e.g. the
temperature) or a set of parameters, and $U_{0}$ is the original system
potential. For simplicity we only consider nonweighted expanded ensembles, as
done in Ref. [4]. The expanded ensemble contains a discrete set
$\\{\lambda\\}$ of $N_{\\{\lambda\\}}$ parameters such that the corresponding
$P_{\lambda}(\mathbf{x})$ have an overlap in the configuration space. We can
write the expanded target distribution as:

$p_{\\{\lambda\\}}(\mathbf{x})=\frac{1}{N_{\\{\lambda\\}}}\sum_{\lambda}P_{\lambda}(\mathbf{x})\,.$
(5)

One can then define the expansion collective variables as $\Delta
u_{\lambda}(\mathbf{x})=\beta U_{\lambda}(\mathbf{x})-\beta U_{0}(\mathbf{x})$
and use them to write the bias potential at step $n$:

$V_{n}(\mathbf{x})=-\frac{1}{\beta}\log\left(\frac{1}{N_{\\{\lambda\\}}}\sum_{\lambda}e^{-\Delta
u_{\lambda}(\mathbf{x})+\beta\Delta F_{n}(\lambda)}\right)\,,$ (6)

where $\Delta F_{n}(\lambda)$ are the estimates of the free energy differences
between the unbiased system $U_{0}$ and the one at a given $\lambda$. These
are obtained via on-the-fly reweighting, similarly to $P_{n}(\mathbf{s})$ in
Sec. 3, but this time without the need for kernel density estimation as
$\\{\lambda\\}$ is a discrete set. The details of the derivation are explained
in Ref. [4].

Finally, we notice that often it is possible to rewrite Eq. (6) so that,
similarly to Eq. (4), the bias is a function of only a small number of CVs.
For example, in case of a multithermal expanded target distribution the bias
can be expressed as a function of the potential energy only [4].

##  5 Example: alanine dipeptide

Figure 1: Marginal probabilities over the $\phi$ angle and the potential
energy for OPES simulations of alanine dipeptide with different target
distributions. The Boltzmann distribution as obtained via reweighting is also
shown. Top row: well-tempered distribution over $\phi$, $\gamma=50$. Bottom
row: temperature-expanded ensemble, from 300 to 1000 K.

As an example we consider alanine dipeptide in vacuum at 300 K, which is a
prototypical system for enhanced sampling. It presents two main metastable
basins, that can be characterized using as CV the torsion angle $\phi$. The
most stable one contains two minima and lays in the region where $\phi$ is
negative, while the second basin has one minimum at $\phi\simeq 1$. A standard
unbiased simulation would suffer the sampling problem and almost never make
transitions between the two basins. In Fig. 1 we show different target
distributions that can be used to study alanine, by plotting their marginal
along $\phi$ and the potential energy. On the top, Fig. 1a, is the well-
tempered ensemble over $\phi$ ($\gamma=50$), which allows the system to easily
visit both basins, and greatly increases the probability of sampling
intermediate configurations around $\phi=0$. On the bottom, Fig. 1b, is an
expanded ensemble that combines four different temperatures, starting from 300
K up to 1000 K. At higher temperatures alanine explores configurations with
higher energy where the barrier between the two basins is smaller. Also in
this case the probability of visiting configurations around $\phi=0$ is
increased, but less sensibly. On the other hand from this second simulation it
is possible to retrieve statistics about a whole range of temperatures,
instead of 300 K only. The two target distributions presented are clearly
different but we can see that, once reweighting is performed, one retrieves
the same underlying Boltzmann probability (dashed lines).

Figure 2: Marginal probabilities over the $\phi$ angle and the potential
energy for OPES simulations of alanine dipeptide with different expanded
target distributions. The Boltzmann distribution as obtained via reweighting
is also shown. Top row: multiumbrella distribution over $\phi$, with 43 evenly
spaced umbrellas. Notice that it looks quite different from Fig. 1a, even
though in the limit of infinite umbrellas and $\gamma=\infty$ they would both
sample a uniform distribution over $\phi$. Bottom row: combined multithermal
and multiumbrella distribution, with 43 umbrellas and temperature range from
300 to 1000 K.

It is well known that is possible to enhance the sampling along a CV also
using an expanded ensemble as target, e.g. by combining multiple umbrella
sampling distributions [12]. In Fig. 2a one can see that a multiumbrella
target over $\phi$ can look very different from a well-tempered target over
the same CV, Fig. 1a. However, in both cases the system easily transitions
from one metastable basin to the other and the probability of being in the
transition region (around $\phi=0$) is greatly increased compared to the
unbiased case. By increasing the number of umbrellas in the target we can
eventually reach a uniform marginal, similar to the well-tempered one with
$\gamma=\infty$. Finally, it is also possible to combine different expansions
in the same target, as shown in Fig. 2b, where the used bias is a function
both of the angle $\phi$ and of the potential energy $U$.

All the simulation details, together with the inputs and the trajectories are
available online on the PLUMED-NEST repository (www.plumed-nest.org,
plumID:21.006) [13].

##  6 Conclusion

We briefly presented a target distribution perspective on enhanced sampling
and the on-the-fly probability enhanced sampling method (OPES), that have been
developed in Refs. [3, 4]. OPES is a general and flexible method that can be
used to sample different types of target distributions. It is also easy to use
and robust with respect to suboptimal collective variables [14]. It has been
implemented as a contributed module in the open source library PLUMED [15,
16], and has been already used for various applications [17, 18, 19, 20, 21].
We believe OPES can be a handy tool for anyone interested in enhanced sampling
and it also has the capability of supporting novel types of target
distributions.

###### Acknowledgements.

The author thanks Luigi Bonati for carefully reading the manuscript. This
research was supported by the NCCR MARVEL, funded by the Swiss National
Science Foundation, and European Union Grant No. ERC-2014-AdG-670227/VARMET.

## References

  * [1] Bolhuis P. G. et al. Annu. Rev. Phys. Chem. 5320021
  * [2] Skilling J. Tech. Rep.120064
  * [3] Invernizzi M. Parrinello M. J. Phys. Chem. Lett.1120207
  * [4] Invernizzi M., Piaggi P. M. Parrinello M. Phys. Rev. X1020204
  * [5] Torrie G. M. Valleau J. P. Chem. Phys. Lett.2819744
  * [6] Laio A. Parrinello M. P. Natl. Acad. Sci.99200220
  * [7] Mezei M. J. Comput. Phys.6819871
  * [8] Barducci A., Bussi G. Parrinello M. Phys. Rev. Lett.10020082
  * [9] Marinari E. Parisi G. Europhys. Lett.1919926
  * [10] Sugita Y. Okamoto Y. Chem. Phys. Lett.3141991-2
  * [11] Lyubartsev A. P. et al. J. Chem. Phys.9619923
  * [12] Sugita Y., Kitao A. Okamoto Y. J. Chem. Phys.113200015
  * [13] The PLUMED consortium. Nat. Methods1620198
  * [14] Invernizzi M. Parrinello M. J. Chem. Theory Comput.1520194
  * [15] Tribello G. A. et al. Comput. Phys. Commun.18520142
  * [16] www.plumed.org/doc-master/user-doc/html/_o_p_e_s.html
  * [17] Mandelli D., Hirshberg B. Parrinello M. Phys. Rev. Lett.12520202
  * [18] Bonati L., Rizzi V. Parrinello M. J. Phys. Chem. Lett.1120208
  * [19] Rizzi V. et al. Nat. Commun.1220211
  * [20] Piaggi P. M. et al. arXiv preprint2021arXiv:2101.04806
  * [21] Karmakar T. et al. arXiv preprint2021arXiv:2101.03150


With similar notations and techniques we find for
$Z=(X_{1},\dots,X_{\tau_{2}})$

$\displaystyle\mathds{E}(\tau_{2}(T,\mathcal{D}^{\prime})\operatorname{KL}(\mathcal{D}^{\prime},\mathcal{D})$
$\displaystyle=\operatorname{KL}\left(\mathds{P}_{\mathcal{D}^{\prime}}^{Z},\mathds{P}_{\mathcal{D}}^{Z}\right)$
$\displaystyle\geq\operatorname{KL}\left(\mathds{P}_{\mathcal{D}^{\prime}}(\tau_{2}<\infty),\mathds{P}_{\mathcal{D}}(\tau_{2}<\infty)\right)$
$\displaystyle\geq\operatorname{KL}(1-\delta,\delta)$ $\displaystyle\geq\log
1/3\delta\;.$

Finally we can deduce

$\displaystyle\mathds{E}(\tau_{2}(T,\mathcal{D}^{\prime}))\geq\frac{\log
1/3\delta}{\operatorname{KL}(\mathcal{D}^{\prime},\mathcal{D})}\;.$

∎

###  A.2  Lower bound for testing closeness in the general case $n\geq 2$

We propose the following lower bounds for testing closeness in general case

######  Lemma A.2.

Let $T$ a stopping rule for testing $\mathcal{D}_{1}=\mathcal{D}_{2}$ vs
${\operatorname{TV}(\mathcal{D}_{1},\mathcal{D}_{2})>\varepsilon}$ with an
error probability $\delta$. Let $\tau_{1}$ and $\tau_{2}$ the associated
stopping times. We have

  * •

$\mathds{E}(\tau_{1}(T,\mathcal{D}_{1},\mathcal{D}_{2}))\geq\frac{\log
1/3\delta}{\inf_{\mathcal{D}^{\prime}_{1,2}\text{s.t.}\operatorname{TV}(\mathcal{D}_{1}^{\prime},\mathcal{D}^{\prime}_{2})>\varepsilon}\operatorname{KL}(\mathcal{D}_{1},\mathcal{D}^{\prime}_{1})+\operatorname{KL}(\mathcal{D}_{2},\mathcal{D}^{\prime}_{2})}$
if  $\mathcal{D}_{1}=\mathcal{D}_{2}$.

  * •

$\mathds{E}(\tau_{2}(T,\mathcal{D}_{1},\mathcal{D}_{2}))\geq\frac{\log
1/3\delta}{\inf_{\mathcal{D}}\operatorname{KL}(\mathcal{D}_{1},\mathcal{D})+\operatorname{KL}(\mathcal{D}_{2},\mathcal{D})}$
if ${\operatorname{TV}(\mathcal{D}_{1},\mathcal{D}_{2})>\varepsilon}$.

###### Proof.

Similarly as in the previous proof, we consider the two different cases
$\mathcal{D}^{\prime}=\mathcal{D}$ and
$\operatorname{TV}(\mathcal{D}^{\prime},\mathcal{D})>\varepsilon$.

##### The case $\mathcal{D}_{1}=\mathcal{D}_{2}$.

We denote by $\mathds{P}_{\mathcal{D}_{1},\mathcal{D}_{2}}$ the probability
distribution on $([n]\times[n])^{\mathds{N}}$ with independent marginals
$(X_{i},Y_{i})$ of distribution $\mathcal{D}_{1}\otimes\mathcal{D}_{2}$. Let
$Z=(X_{1},Y_{1}\dots,X_{\tau_{1}},Y_{\tau_{1}})$. Let
$\mathcal{D}^{\prime}_{1},\mathcal{D}^{\prime}_{2}$ be two distributions such
that
$\operatorname{TV}(\mathcal{D}^{\prime}_{1},\mathcal{D}^{\prime}_{2})>\varepsilon$.
Data processing property of Kullback-Leibler’s divergence implies

$\displaystyle\operatorname{KL}\left(\mathds{P}_{\mathcal{D}_{1},\mathcal{D}_{2}}^{Z},\mathds{P}_{\mathcal{D}^{\prime}_{1},\mathcal{D}^{\prime}_{2}}^{Z}\right)\geq\operatorname{KL}\left(\mathds{P}_{\mathcal{D}_{1},\mathcal{D}_{2}}(\tau_{1}<\infty),\mathds{P}_{\mathcal{D}^{\prime}_{1},\mathcal{D}^{\prime}_{2}}(\tau_{1}<\infty)\right)\;.$
(4)

By definition of $\tau_{1}$ we have
$\mathds{P}_{\mathcal{D}_{1},\mathcal{D}_{2}}(\tau_{1}<\infty)\geq 1-\delta$
and
$\mathds{P}_{\mathcal{D}^{\prime}_{1},\mathcal{D}^{\prime}_{2}}(\tau_{1}<\infty)\leq\delta$.
Tensorization property and Wald’s lemma (B.4) lead to

$\displaystyle\operatorname{KL}\left(\mathds{P}_{\mathcal{D}_{1},\mathcal{D}_{2}}^{Z},\mathds{P}_{\mathcal{D}^{\prime}_{1},\mathcal{D}^{\prime}_{2}}^{Z}\right)=\mathds{E}(\tau_{1}(T,\mathcal{D}_{1},\mathcal{D}_{1}))\operatorname{KL}(\mathcal{D}_{1},\mathcal{D}^{\prime}_{1})+\mathds{E}(\tau_{1}(T,\mathcal{D}_{1},\mathcal{D}_{2}))\operatorname{KL}(\mathcal{D}_{2},\mathcal{D}^{\prime}_{2})\;.$

The inequality 4 becomes

$\displaystyle\mathds{E}(\tau_{1}(T,\mathcal{D}_{1},\mathcal{D}_{2}))\operatorname{KL}(\mathcal{D}_{1},\mathcal{D}^{\prime}_{1})+\mathds{E}(\tau_{1}(T,\mathcal{D}_{1},\mathcal{D}_{2}))\operatorname{KL}(\mathcal{D}_{2},\mathcal{D}^{\prime}_{2})\geq\operatorname{KL}(1-\delta,\delta)\geq\log
1/3\delta\;,$

which is valid for all distribution $\mathcal{D}^{\prime}_{1}$ and
$\mathcal{D}_{2}^{\prime}$ such that
$\operatorname{TV}(\mathcal{D}^{\prime}_{1},\mathcal{D}^{\prime}_{2})>\varepsilon$,
consequently

$\displaystyle\mathds{E}(\tau_{1}(T,\mathcal{D}_{1},\mathcal{D}_{2}))\geq\frac{\log
1/3\delta}{\inf_{\mathcal{D}^{\prime}_{1,2}\text{s.t.
}\operatorname{TV}(\mathcal{D}^{\prime}_{1},\mathcal{D}^{\prime}_{2})>\varepsilon}\operatorname{KL}(\mathcal{D}_{1},\mathcal{D}^{\prime}_{1})+\operatorname{KL}(\mathcal{D}_{2},\mathcal{D}^{\prime}_{2})}\;.$

##### The case
$\operatorname{TV}(\mathcal{D}_{1},\mathcal{D}_{2})>\varepsilon$.

Likewise we prove for $Z=(X_{1},Y_{1}\dots,X_{\tau_{2}},Y_{\tau_{2}})$ and
$\mathcal{D}$ a distribution on $[n]$.

$\displaystyle\mathds{E}(\tau_{2}(T,\mathcal{D}_{1},\mathcal{D}_{2}))\operatorname{KL}(\mathcal{D}_{1},\mathcal{D})+\mathds{E}(\tau_{2}(T,\mathcal{D}_{1},\mathcal{D}_{2}))\operatorname{KL}(\mathcal{D}_{2},\mathcal{D})$
$\displaystyle=\operatorname{KL}\left(\mathds{P}_{\mathcal{D}_{1},\mathcal{D}_{2}}^{Z},\mathds{P}_{\mathcal{D},\mathcal{D}}^{Z}\right)$
$\displaystyle\geq\operatorname{KL}\left(\mathds{P}_{\mathcal{D}_{1},\mathcal{D}_{2}}(\tau_{2}<\infty),\mathds{P}_{\mathcal{D},\mathcal{D}}(\tau_{2}<\infty)\right)$
$\displaystyle\geq\operatorname{KL}(1-\delta,\delta)$ $\displaystyle\geq\log
1/3\delta\;.$

which is valid for all distribution $\mathcal{D}$, consequently

$\displaystyle\mathds{E}(\tau_{2}(T,\mathcal{D}_{1},\mathcal{D}_{2}))\geq\frac{\log
1/3\delta}{\inf_{\mathcal{D}}\operatorname{KL}(\mathcal{D}_{1},\mathcal{D})+\operatorname{KL}(\mathcal{D}_{2},\mathcal{D})}.$

∎

##  Appendix B Technical lemmas

###  B.1 Kullback-Leibler divergence

######  Definition B.1 (Kullback Leibler divergence).

The Kullback Leibler divergence is defined for two distributions $p$ and $q$
on $[n]$ as

$\displaystyle\operatorname{KL}(p,q)=\sum_{i=1}^{n}p_{i}\log\left(\frac{p_{i}}{q_{i}}\right)\;.$

We denote by
$\operatorname{KL}(p,q)=\operatorname{KL}(\mathcal{B}(p),\mathcal{B}(q))$.

Kullback-Leibler’s divergence satisfies data-processing and tensorization
properties:

######  Proposition B.2.

Let $p,p^{\prime},q$ and $q^{\prime}$ distributions on $[n]$, we have

  * •

Non negativity $\operatorname{KL}(p,q)\geq 0$.

  * •

Data processing Let $X$ a random variable and $g$ a function. Define the
random variable $Y=g(X)$, we have

$\displaystyle\operatorname{KL}\left(p^{X},q^{X}\right)\geq\operatorname{KL}\left(p^{Y},q^{Y}\right).$
(5)

  * •

Tensorization

$\displaystyle\operatorname{KL}(p\otimes p^{\prime},q\otimes
q^{\prime})=\operatorname{KL}(p,q)+\operatorname{KL}(p^{\prime},q^{\prime}).$

###  B.2 Poissonization

The Poisson law of parameter $\lambda$ is denoted $Poi(\lambda)$ and defined
as follows.

$\displaystyle\forall
k\in\mathds{N},~{}~{}~{}~{}\mathds{P}(Poi(\lambda)=k)=\frac{\lambda^{k}}{k!}e^{-\lambda}\;.$

Poisson law is important for the analysis of testing’ algorithms. In fact,
some important random variables becomes independent when we take a number of
samples following a Poisson law.

######  Lemma B.3 (Poissonization).

Let $k\sim Poi(\tau)$ and $X=(X_{1},\dots,X_{k})$ i.i.d samples from a
distribution $p$ on $[n]$. For $i\in[n]$, we denote $Y_{i}$ the number of
times $i$ appears in the tuple $X$. We have

  1. 1.

$\\{Y_{1},\dots,Y_{n}\\}$ are independent.

  2. 2.

For all $i\in[n]$, $Y_{i}\sim Poi(\tau p_{i})$.

###  B.3 Wald’s lemma

######  Lemma B.4 (Wald (1944)).

Let $(X_{n})_{n\geq 0}$ i.i.d random variables and $N\in\mathds{N}$ a random
variable independent of $(X_{n})_{n}$. Suppose that $N$ and $X_{1}$ have
finite expectations. we have

$\displaystyle\mathds{E}(X_{1}+\dots+X_{N})=\mathds{E}(N)\mathds{E}(X_{1})\;.$

###  B.4 Tools for non asymptotic inequalities

We group here different lemmas that help us to deal with the kl-divergence or
logarithmic relations in order to find non asymptotic results. We start by
giving some useful lemmas for the Kullback-Leibler’s divergence between
Bernoulli variables.

######  Lemma B.5 (Lemmas for kl-divergence.).

Let $q>p$ two numbers in $[0,1]$. Then

  * •

$2(p-q)^{2}\leq\operatorname{KL}(p,q)\leq\frac{(p-q)^{2}}{q(1-q)},$

  * •

$\operatorname{KL}(p,q)\underset{q\rightarrow
p}{\sim}\frac{(p-q)^{2}}{2q(1-q)},$

  * •

$\operatorname{KL}(q,p)=\int_{p}^{q}du\int_{p}^{u}dv\frac{1}{v(1-v)}.$

##### Sketch of proof.

The LHS of the first inequality is Pinsker’s inequality, the RHS can be proven
using the inequality $\log(1+x)\leq x$, the second equivalence can be found by
developing the $\log$ function and the third equality is proven by calculating
the integral.

######  Lemma B.6.

[Developing kl]Let $q,\varepsilon$ and $\alpha$ positive real numbers such
that $q+\varepsilon<1$ and $\alpha<1$, we have for $\alpha$ close enough to
$1$

$\displaystyle\frac{1}{\operatorname{KL}(q+\alpha\varepsilon,q)}\leq\frac{1}{\operatorname{KL}(q+\varepsilon,q)}+(1-\alpha)\sup_{[q,q+\varepsilon]}\frac{1}{x(1-x)}\;.$

###### Proof.

We use the inequality $\frac{1}{1-x}\leq 1+2x$ for $0<x<1/2$. We write

$\displaystyle\frac{1}{\operatorname{KL}(q+\alpha\varepsilon,q)}=\frac{1}{\operatorname{KL}(q+\varepsilon,q)(1-x)}\;,$

where
$x=\frac{\operatorname{KL}(q+\varepsilon,q)-\operatorname{KL}(q+\alpha\varepsilon,q)}{\operatorname{KL}(q+\varepsilon,q)}<\frac{1}{2}$
if $\alpha$ is close enough to $1$. Hence

$\displaystyle\frac{1}{\operatorname{KL}(q+\alpha\varepsilon,q)}$
$\displaystyle\leq\frac{1}{\operatorname{KL}(q+\varepsilon,q)(1-x)}$
$\displaystyle\leq\frac{1}{\operatorname{KL}(q+\varepsilon,q)}(1+2x)$
$\displaystyle\leq\frac{1}{\operatorname{KL}(q+\varepsilon,q)}+2\frac{\operatorname{KL}(q+\varepsilon,q)-\operatorname{KL}(q+\alpha\varepsilon,q)}{\operatorname{KL}(q+\varepsilon,q)^{2}}$
$\displaystyle\leq\frac{1}{\operatorname{KL}(q+\varepsilon,q)}+\frac{2}{\operatorname{KL}(q+\varepsilon,q)^{2}}\int_{q+\alpha\varepsilon}^{q+\varepsilon}du\int_{q}^{u}dv\frac{1}{v(1-v)}$
$\displaystyle\leq\frac{1}{\operatorname{KL}(q+\varepsilon,q)}+\frac{2(1-\alpha)\varepsilon^{2}}{\operatorname{KL}(q+\varepsilon,q)^{2}}\sup_{[q,q+\varepsilon]}\frac{1}{v(1-v)}$
$\displaystyle\leq\frac{1}{\operatorname{KL}(q+\varepsilon,q)}+\frac{2(1-\alpha)\varepsilon^{2}}{2\varepsilon^{2}}\sup_{[q,q+\varepsilon]}\frac{1}{v(1-v)}$
$\displaystyle\leq\frac{1}{\operatorname{KL}(q+\varepsilon,q)}+(1-\alpha)\sup_{[q,q+\varepsilon]}\frac{1}{v(1-v)}\;.$

∎

When we deal with inequalities involving $t$ and $\log t$ (or $\log\log t$)
and want to deduce inequalities only on $t$, the following lemma proves to be
useful.

######  Lemma B.7.

Let $t,a>1$ and $b$ real numbers. We have the following implications:

  * •

If $b\geq a+1:$

$\displaystyle t\geq b+2a\log(b)\Rightarrow t\geq b+a\log(t)\;,$

  * •

If $b\geq 1:$

$\displaystyle t\geq b-a\log(t)\Rightarrow t\geq b-a\log(b)\;,$

  * •

If $b\geq 2a:$

$\displaystyle t\geq b+2a\log(\log(b)+1)\Rightarrow t\geq
b+a\log(\log(t)+1)\;.$

###### Proof.

We prove only the first statement, the others being similar. Let
$f(t)=t-b-a\log(t)$, we have $f^{\prime}(t)=1-a/t$ thus $f$ is increasing on
$(a,+\infty)$. Let $t\geq b+2a\log(b)>a$,

$\displaystyle f(t)\geq f(b+2a\log(b))$
$\displaystyle=b+2a\log(b)-b-a\log(b+2a\log(b))$
$\displaystyle=a\log(b)-a\log(1+2a\log(b)/b))$ $\displaystyle\geq
a\log(1+a)-a\log(1+2ab/eb)\ \ \text{ because }\log(b)\leq b/e$
$\displaystyle\geq 0\;.$

∎

For instance, by applying this lemma, we can obtain:

######  Lemma B.8.

Recall the definition of $N_{\eta}$:

$\displaystyle
N_{\eta}=\max\Bigg{\\{}\frac{128}{C^{2}}\frac{\log(\frac{\pi^{2}}{3\delta})}{\eta^{2}}+\frac{512e}{C^{2}\eta^{2}}\log\left(\log\left(\frac{128\log(\frac{\pi^{2}}{3\delta})}{\eta^{2}C^{2}}\right)+1\right)+\frac{16c^{2}}{C^{2}\eta^{2}},$
$\displaystyle\left(\frac{128}{C^{2}}\frac{n^{2}\log(\frac{\pi^{2}}{3\delta})}{\eta^{4}}+\frac{512en^{2}}{C^{2}\eta^{4}}\log\left(\log\left(\frac{128}{C^{2}}\frac{n^{2}\log(\frac{\pi^{2}}{3\delta})}{\eta^{4}}\right)+1\right)+\frac{16c^{2}n^{2}}{\eta^{4}C^{2}}\right)^{1/3},$
$\displaystyle\left(\frac{128}{C^{2}}\frac{n\log(\frac{\pi^{2}}{3\delta})}{\eta^{4}}+\frac{512en}{C^{2}\eta^{4}}\log\left(\log\left(\frac{128}{C^{2}}\frac{n\log(\frac{\pi^{2}}{3\delta})}{\eta^{4}}\right)+1\right)+\frac{16c^{2}n}{\eta^{4}C^{2}}\right)^{1/2}\Bigg{\\}}\;.$

Let $\eta>0$, if $t\geq N_{\eta}$, then

$\displaystyle\min\left\\{t\eta,\frac{t^{2}\eta^{2}}{n},\frac{t^{3/2}\eta^{2}}{\sqrt{n}}\right\\}\geq\frac{4}{C}\sqrt{2t\log\left(\frac{\pi^{2}}{3\delta}\right)+4et\log(\log(t)+1)}+\frac{2c}{C}\sqrt{t}\;.$

Finally, the next lemma shows that the complexity of Alg. 4 cannot exceed
$N_{d\vee\varepsilon}$ very much.

######  Lemma B.9.

We have for all $d>0$: $\sum_{t\geq
N_{d}}e^{-\frac{C^{2}}{16}\min\left\\{td^{2},\frac{t^{3}d^{4}}{n^{2}},\frac{t^{2}d^{4}}{n}\right\\}}\leq
N_{d}$.

###### Proof.

We have

$\displaystyle\sum_{t\geq
N_{d}}e^{-\frac{C^{2}}{16}\min\left\\{td^{2},\frac{t^{3}d^{4}}{n^{2}},\frac{t^{2}d^{4}}{n}\right\\}}$
$\displaystyle\leq\sum_{t\geq nd^{-2}}e^{-\frac{C^{2}}{16}td^{2}}+\sum_{n\geq
t\geq
N_{d}-1}e^{-\frac{C^{2}}{16}\frac{t^{3}d^{4}}{n^{2}}}+\sum_{nd^{-2}>t>n}e^{-\frac{C^{2}}{16}\frac{t^{2}d^{4}}{n}}$
$\displaystyle\leq\sum_{t\geq nd^{-2}}e^{-\frac{C^{2}}{16}td^{2}}+\sum_{n\geq
t\geq
N_{d}-1}e^{-2C^{1/3}\frac{td^{4/3}}{n^{2/3}}}+\sum_{nd^{-2}>t>n}e^{-\frac{C}{2}\frac{td^{2}}{\sqrt{n}}}$
$\displaystyle\leq\frac{1}{1-e^{-\frac{C^{2}}{16}d^{2}}}+\frac{1}{1-e^{-2C^{1/3}\frac{d^{4/3}}{n^{2/3}}}}+\frac{1}{1-e^{-\frac{C}{2}\frac{d^{2}}{\sqrt{n}}}}$
$\displaystyle\leq\frac{32}{C^{2}d^{2}}+\frac{n^{2/3}}{C^{1/3}d^{4/3}}+\frac{4\sqrt{n}}{Cd^{2}}\
\ \text{ since }1-e^{-x}\geq x/2\text{ for }0<x<1$ $\displaystyle\leq
N_{d}\;.$

∎