# Generalized Fourier quasicrystals and almost periodic sets

Sergii Yu.Favorov  Sergii Favorov,
iii Karazin’s Kharkiv National University
iii Svobody sq., 4, Kharkiv, Ukraine 61022<EMAIL_ADDRESS>
> Abstract. Let $\mu$ be a positive measure on the real line with locally
> finite support $\Lambda$ and integer masses such that its Fourier transform
> in the sense of distributions is a purely point measure. An explicit form is
> found for an entire almost periodic function with a set of zeros $\Lambda$,
> taking multiplicities into account. A necessary and sufficient condition for
> the exponential growth of this function is also found.
>
> Our constructions are based on the properties of almost periodic sets on the
> line. In particular, in the article we find a simple representation of such
> sets.
>
> AMS Mathematics Subject Classification: 42A75, 42A38, 52C23
>
> Keywords: Fourier quasicrystal, Fourier transform of distribution, pure
> point measure, almost periodic function, almost periodic sets, entire
> function with a given zero set

##  1\. Introduction

A crystalline measure on ${\mathbb{R}}^{d}$ is a complex measure with discrete
locally finite support, which is temperate distribution and its distributional
Fourier transform $\hat{\mu}$ is also a measure with locally finite support;
if, in addition, the measures $|\mu|$ and $|\hat{\mu}|$ are temperate
distributions, then $\mu$ is called the Fourier quasicrystal.

The Fourier quasicrystal may be considered as a mathematical model for atomic
arrangement having a discrete diffraction pattern. There are a lot of papers
devoted to study properties of Fourier quasicrystals or, more generally,
crystalline measures. For example, one can mark collections of papers [2],
[16], in particular, the basic paper [11].

Measures of the form

(1) $\mu=\sum_{\lambda\in\Lambda}c_{\lambda}\delta_{\lambda},\qquad
c_{\lambda}\in{\mathbb{N}},$

are the most important cases of Fourier quasicrystal. Recently A.Olevslskii
and A.Ulanovskii [14], [15] give a complete description of these measures as
zero sets of an exponential polynomial with pure imaginary exponents, where
$c_{\lambda}$ is just the multiplicity of the zero $\lambda$ of the
polynomial.

In the present paper we give an analog of the above result for measures (1)
with the distributional Fourier transform

(2) $\hat{\mu}=\sum_{\gamma\in\Gamma}b_{\gamma}\delta_{\gamma},$

where $\Gamma$ is an arbitrary countable set. In this case the corresponding
Poisson’s formula

$\sum_{\lambda\in\Lambda}c_{\lambda}\hat{f}(\lambda)=\sum_{\gamma\in\Gamma}b_{\gamma}f(\gamma).$

also takes place for every function $f$ from Schwarz’s class. In order to
describe such measures, we use the concept of almost periodic sets, which was
introduced by M. Krein and B. Levin ([9], Appendix VI). In modern notations
(cf.[12], [17]), a locally finite set $\Lambda$ with multiplicities
$c_{\lambda}$ at points $\lambda\in\Lambda$ is almost periodic, if the
convolution of measure (1) with every continuous function with compact support
is almost periodic function. We will write an almost periodic set like the
sequence $A=\\{a_{n}\\}_{n\in{\mathbb{Z}}}$, where each point $a_{n}=\lambda$
occurs $c_{\lambda}$ times. Therefore, almost periodic sets are in fact
multisets.

In Section 2 we give the original definition of almost periodic sets given by
Krein and Levin, which is equivalent to the one given above. Also we prove
some properties of almost periodic sets, in particular, show that such sets
have the form $\\{\alpha n+\phi(n)\\}_{n\in{\mathbb{N}}}$ with $\alpha>0$ and
an almost periodic mapping $\phi:\,{\mathbb{Z}}\to{\mathbb{R}}$.

Note that the zero set of every entire almost periodic function is almost
periodic (cf.[18]). On the other hand, it was proved in [7] that every almost
periodic set $A\subset{\mathbb{R}}$ is exactly the zero set of some entire
almost periodic function. In section 3 we consider measure $\mu$ of the form
(1) under additional conditions that $\hat{\mu}$ is a measure and
$|\hat{\mu}|$ is a temperate distribution. If this is the case, the almost
periodicity of measure $\mu$, in other words, almost periodicity of
corresponding multiset $A$, is equivalent to the property of $\hat{\mu}$ to be
pure point. Here we find an almost periodic entire function with zero set $A$
in an explicit form depending only on $\gamma$ and $b_{\gamma}$ from equality
(2). Also we find a criterion for $A$ to be the zero set of an almost periodic
entire function of the exponential growth. Note that according to the
Phragmen-Lindelöf principle any entire function bounded on ${\mathbb{R}}$
cannot grow less than exponentially.

##  2\. Almost periodic sets

######  Definition 1 (for example, see [1], [10]).

A continuous function on a strip

$S=\\{z=x+iy:\,-\infty\leq a<y<b\leq+\infty\\}\subset{\mathbb{C}}$

is almost periodic if for any $\alpha,\,\beta$ such that
$[\alpha,\beta]\subset(a,b)$ and $\varepsilon>0$ the set of
$\varepsilon$-almost periods

$E_{\alpha,\beta,\varepsilon}=\\{\tau\in{\mathbb{R}}:\,\sup_{x\in{\mathbb{R}},\alpha\leq
y\leq\beta}|g(x+\tau+iy)-g(x+iy)|<\varepsilon\\}$

is relatively dense, i.e.,
$E_{\alpha,\beta,\varepsilon}\cap(x,x+L)\neq\emptyset$ for all
$x\in{\mathbb{R}}$ and some $L$ depending on $\varepsilon,\alpha,\beta$.

Just as it was done in [7], we could define an almost periodic set in a strip.
But we need it only for the case of sets on the real line, so we can give this
definition here in a simplified form.

######  Definition 2 (M. Krein and B. Levin [9], Appendix VI).

A discrete locally finite multiset
$A=\\{a_{n}\\}_{n\in{\mathbb{Z}}}\subset{\mathbb{R}}$ is almost periodic if
for any $\varepsilon>0$ the set of its $\varepsilon$-almost periods

(3) $E_{\varepsilon}=\\{\tau\in{\mathbb{R}}:\,\exists\ \text{ a bijection
}\sigma:{\mathbb{Z}}\to{\mathbb{Z}}\quad\text{such that}\ \sup_{n}|a_{n}+\tau-
a_{\sigma(n)}|<\varepsilon\\}$

has nonempty intersection with every interval $(x,x+L_{\varepsilon})$.

Set $\mu_{A}=\sum_{n}\delta_{a_{n}}$. Clearly, the mass of $\mu_{A}$ in any
point $x\in{\mathbb{R}}$ is equal to the multiplicity of this point in the
sequence $\\{a_{n}\\}_{n\in{\mathbb{Z}}}$.

It was proved in [7] that almost periodicity of $A$ is equivalent to almost
periodicity of convolution $\mu_{A}\star\varphi$ for every
$C^{\infty}$-function $\varphi(x),\,x\in{\mathbb{R}}$, with compact support.
But it is easy to replace $C^{\infty}$-functions by continuous functions with
compact support.

Indeed, take $C^{\infty}$-function $\varphi\geq 0$ such that $\varphi(x)\equiv
1$ for $0<x<1$. If $\mu_{A}\star\varphi$ is almost periodic, then it is
uniformly bounded, hence $\mu_{A}[x,x+1]<K$ for all $x\in{\mathbb{R}}$ with
some constant $K$. For any continuous function $\psi$ with support in $(0,1)$
one can take $\varphi\in C^{\infty}$ such that
$\sup_{x\in{\mathbb{R}}}|\psi(x)-\varphi(x)|<\varepsilon/K$. We obtain that
every $\varepsilon$-almost period of $\mu_{A}\star\varphi$ is
$2\varepsilon$-almost period of $\mu_{A}\star\psi$.

By the way, we gave the proof of the following proposition

######  Proposition 1 ([7]).

For any almost periodic set there is $k_{1}\in{\mathbb{N}}$ such that
$\\#A\cap[x,x+1]\leq k_{1}$. Also, $\\#A\cap[x,x+h)\leq k_{1}(h+1)$.

Here and below, $\\#H$ means the number of points in the set $H$.

Note that the above proposition implies that $\mu_{A}(-r,r)=O(r)$ as
$r\to\infty$, therefore $\mu_{A}$ is a temperate distribution.

######  Proposition 2.

For any almost periodic set there is $k_{2}\in{\mathbb{N}}$ such that for
every $h$ and every half-intervals $[x_{1},x_{1}+h),\,[x_{2},x_{2}+h)$ we have
$|\\#A\cap[x_{1},x_{1}+h)-\\#A\cap[x_{2},x_{2}+h)|\leq k_{2}$. Also, for every
$x\in{\mathbb{R}},\,h>0,\,M\in{\mathbb{N}}$

(4) $|\\#A\cap[x,x+h)-(1/M)\\#A\cap[x,x+Mh)|\leq k_{2}.$

Proof. Let $L_{1},\,E_{1}$ be defined in (3), and $\tau\in
E_{1}\cap[x_{1}-x_{2},L_{1}+x_{1}-x_{2})$. Since
$[x_{2},x_{2}+h)+\tau\subset[x_{1},x_{1}+L_{1}+h)$, we see that to each
$a_{n}\in[x_{2},x_{2}+h)$ assign a point
$a_{\sigma(n)}\in[x_{1}-1,x_{1}+L_{1}+h+1)$. Therefore,

$\\#A\cap[x_{2},x_{2}+h]\leq\\#A\cap[x_{1},x_{1}+h)+\\#A\cap[x_{1}-1,x_{1})+\\#A\cap[x_{1}+h,x_{1}+h+L_{1}+1).$

By Proposition 1, the last two terms are bounded by $k_{1}+(L_{1}+2)k_{1}$.
The proof of the opposite inequality is the same.

To prove the second assertion, we have to add together all the inequalities

$\\#A\cap[x,x+h)-k_{2}\leq\\#A\cap[x+(m-1)h,x+mh)\leq
k_{2}+\\#A\cap[x,x+h),\quad m=1,2,\dots,M.$

######  Proposition 3.

Let $A$ be an almost periodic set. There is a strictly positive density $d$
such that for any $\eta>0$ and any half-interval $I$ with length
$l(I)>N_{\eta}$ we have

$\left|\frac{\\#A\cap I}{l(I)}-d\right|<\eta.$

This result was generalized to all Euclidean spaces in [6].

Proof of Proposition 3. Let
$I_{1}=[x_{1},x_{1}+h_{1}),I_{2}=[x_{2},x_{2}+h_{2})$ be two half-intervals
such that $h_{1}/h_{2}=p/q,\,p,q\in{\mathbb{N}}$. We have

$\frac{\\#A\cap I_{1}}{h_{1}}-\frac{\\#A\cap I_{2}}{h_{2}}=\frac{\\#A\cap
I_{1}}{h_{1}}-\frac{\\#A\cap qI_{1}}{qh_{1}}+\frac{\\#A\cap
qI_{1}}{qh_{1}}-\frac{\\#A\cap pI_{2}}{ph_{2}}+\frac{\\#A\cap
pI_{2}}{ph_{2}}-\frac{\\#A\cap I_{2}}{h_{2}}.$

Applying Proposition 2, we get

(5) $\left|\frac{\\#A\cap I_{1}}{h_{1}}-\frac{\\#A\cap
I_{2}}{h_{2}}\right|\leq\frac{k_{2}}{h_{1}}+\frac{k_{2}}{qh_{1}}+\frac{k_{2}}{h_{2}}\leq
k_{2}\left(\frac{2}{h_{1}}+\frac{1}{h_{2}}\right).$

Take half-interval $I^{\prime}=[x_{1},x_{1}+h^{\prime})$ such that
$h_{1}<h^{\prime}<h_{1}+1$ and $h^{\prime}/h_{2}$ rational. We have

$\left|\frac{\\#A\cap I_{1}}{h_{1}}-\frac{\\#A\cap
I^{\prime}}{h^{\prime}}\right|\leq\frac{\\#A\cap[x_{1}+h_{1},x_{1}+h^{\prime})}{h_{1}}+\frac{\\#A\cap[x_{1},x_{1}+h^{\prime})}{h_{1}h^{\prime}}.$

By Proposition 1, we obtain

$\left|\frac{\\#A\cap I_{1}}{h_{1}}-\frac{\\#A\cap
I^{\prime}}{h^{\prime}}\right|\leq\frac{k_{1}}{h_{1}}+\frac{k_{1}(h^{\prime}+1)}{h_{1}h^{\prime}}.$

Applying (5) with $I^{\prime}$ instead of $I_{1}$, we obtain for all
$I_{1},\,I_{2}$

$\left|\frac{\\#A\cap I_{1}}{h_{1}}-\frac{\\#A\cap I_{2}}{h_{2}}\right|\leq
k_{2}\left(\frac{2}{h_{1}}+\frac{1}{h_{2}}\right)+k_{1}\left(\frac{2}{h_{1}}+\frac{1}{h_{1}h^{\prime}}\right).$

Therefore there is a limit

$d=\lim_{l(I)\to\infty}\frac{\\#A\cap I}{l(I)}.$

Since the set $A$ is relatively dense, this limit is strictly positive.

######  Theorem 1.

Let $A=\\{a_{n}\\}\subset{\mathbb{R}}$ be an almost periodic set of density
$d$ such that $a_{n}\leq a_{n+1}$ for all $n\in{\mathbb{Z}}$. Then

(6) $a_{n}=n/d+\phi(n)\quad\text{with an almost periodic
mapping}\quad\phi:\,Z\to{\mathbb{R}}.$

Remark. The wrong proof of this Theorem was given in [5].

Proof of Theorem 1. After replacing $A$ with $A/d$ we may suppose $d=1$. Also,
we may suppose that $a_{0}<a_{1}$. It follows from Proposition 1 that every
interval of length $1$ contains at least one subinterval of length
$1/(2k_{1})$ that does not intersect $A$. Take
$\varepsilon<\min\\{1/(6k_{1}),(a_{1}-a_{0})/3\\}$. Divide ${\mathbb{R}}$ into
an infinite number of disjoint semiintervals
$I_{j}=(t_{j},t_{j+1}],\,j\in{\mathbb{Z}}$ such that $t_{j+1}-t_{j}<2$ and
$A\cap(t_{j}-2\varepsilon,t_{j}+2\varepsilon)=\emptyset$ for all $j$.

Therefore, if $\sigma$ is any bijection that satisfies (3), then
$\rho(j)\in{\mathbb{Z}}$ corresponds to any $j$ such that $\sigma$ is the
bijection of $A\cap I_{j}$ to $A\cap I_{\rho(j)}$. Let $\sigma_{j}$ is the
monotone increasing bijection of $A\cap I_{j}$ on $A\cap I_{\rho(j)}$. Check
that

(7) $|a_{n}+\tau-a_{\sigma_{j}(n)}|<\varepsilon\qquad\forall\,a_{n}\in I_{j}.$

Suppose the contrary. Let $n_{0}$ be the minimal number such that (7) does not
satisfy. If $a_{n_{0}}+\tau+\varepsilon\leq a_{\sigma_{j}(n_{0})}$, then
$a_{n}+\tau+\varepsilon\leq a_{k}$ for all $n\leq n_{0}$ and
$k\geq\sigma_{j}(n_{0})$, $a_{n}\in I_{j},\,a_{k}\in I_{\rho(j)}$. Therefore,
$k\neq\sigma(n)$ for these numbers, and $\sigma$ may give a correspondence
between points from the set $\\{n\leq n_{0}:\,a_{n}\in I_{j}\\}$ and points
only from the set $\\{k<\sigma_{j}(n_{0}):\,a_{k}\in I_{\rho(j)}\\}$. But by
definition of $\sigma_{j}$, we have

$\\#\\{n\leq n_{0}:\,a_{n}\in I_{j}\\}=\\#\\{k\leq\sigma_{j}(n_{0}):\,a_{k}\in
I_{\rho(j)}\\}>\\#\\{k<\sigma_{j}(n_{0}):\,a_{k}\in I_{\rho(j)}\\}.$

We get a contradiction.

If $a_{n_{0}}+\tau\geq a_{\sigma_{j}(n_{0})}+\varepsilon$, then
$a_{n}+\tau\geq a_{k}+\varepsilon$ for all $n\geq n_{0}$ and
$k\leq\sigma_{j}(n_{0})$, $a_{n}\in I_{j},\,a_{k}\in I_{\rho(j)}$. Therefore,
$k\neq\sigma(n)$ for these numbers, and $\sigma$ may give a correspondence
between points from the set $\\{n\geq n_{0}:\,a_{n}\in I_{j}\\}$ and points
only from the set $\\{k>\sigma_{j}(n_{0}):\,a_{k}\in I_{\rho(j)}\\}$. But
$\\#(A\cap I_{j})=\\#(A\cap I_{\rho(j)})$, hence by definition of
$\sigma_{j}$, we have

$\\#\\{n\geq n_{0}:\,a_{n}\in I_{j}\\}=\\#\\{k\geq\sigma_{j}(n_{0}):\,a_{k}\in
I_{\rho(j)}\\}>\\#\\{k>\sigma_{j}(n_{0}):\,a_{k}\in I_{\rho(j)}\\}.$

We get a contradiction as well.

Since numbers $A\cap I_{j}$ and $A\cap I_{\rho(j)}$ coincide, we see that the
differences between indices of the first elements in these sets coincide for
all $j$. Hence a number $h\in{\mathbb{Z}}$ corresponds to every $\tau\in
E_{\varepsilon}$ such that (3) satisfies with $\sigma(n)=n+h$.

It follows from the definition of $\tau$ for all $k\in{\mathbb{N}}$

$\tau-\varepsilon<a_{kh}-a_{(k-1)h}<\tau+\varepsilon.$

Therefore the length of interval that contains points with numbers from
$(k-1)h+1$ till $kh$ is between $\tau-\varepsilon$ and $\tau+\varepsilon$, and
the length of interval that contains points with numbers from $1$ till $Nh$ is
between $N(\tau-\varepsilon)$ and $N(\tau+\varepsilon)$. Since $d=1$, we get
the inequality $\tau-\varepsilon\leq h\leq\tau+\varepsilon$. Set
$\phi(n):=a_{n}-n$. We obtain for all $n\in{\mathbb{Z}}$

$\phi(n+h)-\phi(n)=a_{n+h}-a_{n}-h=a_{\sigma(n)}-(a_{n}+\tau)+(\tau-h).$

Using (3), we obtain $|\phi(n+h)-\phi(n)|<2\varepsilon$. Therefore, $h$ is
$2\varepsilon$-almost period of the function $\phi$. The set of
$\varepsilon$-almost periods $\tau$ of $A$ is relatively dense, therefore the
set of such integers $h$ is relatively dense as well.

######  Corollary 1.

For any almost periodic set $A=\\{a_{n}\\}$ such that $0\not\in A$ there is a
finite limit

$\alpha_{0}=\lim_{N\to\infty}\sum_{|a_{n}|<N}1/a_{n}.$

Moreover, for any $z\in{\mathbb{C}}\setminus A$ the sum

$\alpha_{z}=\frac{1}{z-a_{0}}+\sum_{n\in{\mathbb{N}}\setminus\\{0\\}}\left[\frac{1}{z-a_{n}}+\frac{1}{z-a_{-n}}\right].$

converges absolutely.

Proof. Let $A=\\{n/d+\phi(n)\\}_{n\in{\mathbb{Z}}}$. Since the numbers
$\phi(n)$ are uniformly bounded, we see that the sums

$\sum_{n\in{\mathbb{Z}},|a_{n}|<N}\frac{1}{a_{n}}\quad\mbox{and}\quad\sum_{n\in{\mathbb{Z}},|n|<N}\frac{1}{n/d+\phi(n)}$

differ for a uniformly bounded with respect to $N$ number of terms, and each
of these terms tends to $0$ as $N\to\infty$. Then

$\sum_{n\in{\mathbb{Z}},0<|n|<N}\frac{1}{n/d+\phi(n)}=\sum_{n\in{\mathbb{N}},0<n<N}\frac{\phi(n)+\phi(-n)}{\phi(n)\phi(-n)+n\phi(-n)/d-n\phi(n)/d-(n/d)^{2}}.$

The first assertion follows from Cauchy criterium. The second one follows from
the absolutely convergence of the series

$\sum_{n\in{\mathbb{N}}\setminus\\{0\\}}\left[\frac{1}{z-a_{n}}+\frac{1}{z-a_{-n}}\right]=\sum_{n\in{\mathbb{N}}\setminus\\{0\\}}\left[\frac{2z-\phi(-n)-\phi(n)}{(n/d+\phi(n)-z)(-n/d+\phi(-n)-z)}\right].\phantom{XXX}\leavevmode\nobreak\
\hfill\rule{7.0pt}{7.0pt}$

In [9], Appendix VI, M.Krein and B.Levin considered zero sets $Z_{f}$ of
entire almost periodic functions $f$ of exponential growth. They proved that
if $Z_{f}\subset{\mathbb{R}}$, then its zeros $a_{n}$ form an almost periodic
set, which satisfy (6) and

(8)
$\sup_{\tau\in{\mathbb{Z}}}\sum_{n\in{\mathbb{Z}}\setminus\\{0\\}}n^{-1}[\phi(n+\tau)-\phi(n)]<\infty.$

On the other hand, they proved that any almost periodic set
$A\subset{\mathbb{R}}$ satisfying conditions (6) and (8) is the set of zeros
of an entire almost periodic function of exponential growth.

It follows from Theorem 1 that condition (6) can be omitted in the last
result.

Theorem 1 was generalized by W.Lawton [8] to almost periodic sets in
${\mathbb{R}}^{d},\,d>1,$, whose spectrum is contained in a finitely generated
additive group.

##  3\. Almost periodic zeros of entire functions

In this section we suppose that $\mu$ is a measure of form (1), which is a
temperate distribution and its Fourier transform $\hat{\mu}$ is a measure of
form (2) such that $|\hat{\mu}|$ is also a temperate distribution. It follows
from [4], Lemma 1, that the multiset $A=\\{a_{n}\\}_{n\in{\mathbb{Z}}}$, where
each point $a_{n}=\lambda$ occurs $c_{\lambda}$ times, is an almost periodic
set. In what follows we will suppose that $0\not\in A$. Set

(9) $f(z)=(1-z/a_{0})\prod_{n\in{\mathbb{N}}}(1-z/a_{n})(1-z/a_{-n}).$

It follows from Corollary 1 that $A$ satisfies Lindelof’s condition, hence,
$f$ is an entire function of exponential type.

Remark that for any measure $\mu$ of form (1) with an almost periodic $A$
condition ”$\hat{\mu}$ is a measure” implies ”$\hat{\mu}$ is a pure point
measure” (cf.[13], Theorem 5.5).

Set

${\mathbb{R}}_{+}:=\\{x\in{\mathbb{R}}:x>0\\},\,{\mathbb{R}}_{-}:=-{\mathbb{R}}_{+},\,{\mathbb{C}}_{+}:=\\{z\in{\mathbb{C}}:\mbox{Im
}z>0\\},\,{\mathbb{C}}_{-}:=-{\mathbb{C}}_{+},$

and

$a_{z}(t)=\begin{cases}-2\pi ie^{2\pi itz}&\text{if }t>0,\\\ 0&\text{if }t\leq
0,\end{cases}\quad z\in{\mathbb{C}}_{+},\quad\qquad a_{z}(t)=\begin{cases}2\pi
ie^{2\pi itz}&\text{if }t<0,\\\ 0&\text{if }t\geq 0,\end{cases}\quad
z\in{\mathbb{C}}_{-}.$

It is not hard to check that in the sense of distributions
$\hat{a}_{z}(\lambda)=1/(z-\lambda)$ for
$z\in{\mathbb{C}}_{+}\cup{\mathbb{C}}_{-}$.

######  Proposition 4.

Let $A,\,\mu,\,\hat{\mu}$ be as above. Then for all
$z=x+iy\in{\mathbb{C}}_{+}$

(10)
$\frac{f^{\prime}(z)}{f(z)}=\frac{1}{z-a_{0}}+\sum_{n\in{\mathbb{N}}}\left[\frac{1}{z-a_{n}}+\frac{1}{z-a_{-n}}\right]=-2\pi
i\sum_{\gamma\in\Gamma\cap{\mathbb{R}}_{+}}b_{\gamma}e^{2\pi i\gamma z},$

and for all $z=x+iy\in{\mathbb{C}}_{-}$

(11)
$\frac{f^{\prime}(z)}{f(z)}=\frac{1}{z-a_{0}}+\sum_{n\in{\mathbb{N}}}\left[\frac{1}{z-a_{n}}+\frac{1}{z-a_{-n}}\right]=2\pi
i\sum_{\gamma\in\Gamma\cap{\mathbb{R}}_{-}}b_{\gamma}e^{2\pi i\gamma z}.$

The function $f^{\prime}(z)/f(z)$ is almost periodic on each line $y=y_{0}\neq
0$.

Proof. Let $\varphi(t)$ be any even nonnegative $C^{\infty}$-function such
that $\operatorname{supp}\varphi\subset(-1,1)$ and $\int\varphi(t)dt=1$. Set
$\varphi_{\varepsilon}(t)=\varepsilon^{-1}\varphi(t/\varepsilon)$ for
$\varepsilon>0$. Fix $z=x+iy\in{\mathbb{C}}_{+}$. The functions
$a_{z}(t)\star\varphi_{\varepsilon}(t)$ and
$\hat{\alpha}_{z}(\lambda)\hat{\varphi}_{\varepsilon}(\lambda)$ belong to
Schwartz space of $C^{\infty}$-functions. Therefore,

(12)
$(\hat{\mu},a_{z}(t)\star\varphi_{\varepsilon}(t))=(\mu,\hat{\alpha}_{z}(\lambda)\hat{\varphi}_{\varepsilon}(\lambda)).$

Then for any $T_{0}<\infty$

$(\hat{\mu},(a_{z}\star\varphi_{\varepsilon})(t))-(\hat{\mu},\alpha_{z}(t))$
(13) $=-2\pi i\sum_{\gamma\geq T_{0}}b_{\gamma}e^{2\pi i\gamma
z}\int_{-\varepsilon}^{\varepsilon}(e^{-2\pi
isz}-1)\varphi_{\varepsilon}(s)ds-2\pi i\sum_{0<\gamma<T_{0}}b_{\gamma}e^{2\pi
i\gamma z}\int_{-\varepsilon}^{\varepsilon}(e^{-2\pi
isz}-1)\varphi_{\varepsilon}(s)ds.$

The first sum is majorized by

(14) $2\pi(e^{2\pi\varepsilon y}+1)\sum_{\gamma\geq
T_{0}}|b_{\gamma}|e^{-2\pi\gamma y}.$

Set $M(t)=\sum_{\gamma\in\Gamma:\,0<\gamma\leq t}|b_{\gamma}|$. Then

(15) $\sum_{\gamma\geq r}|b_{\gamma}|e^{-2\pi\gamma
y}=\int_{r}^{\infty}e^{-2\pi ty}dM(t)\leq\lim_{T\to\infty}M(T)e^{-2\pi
Ty}+2\pi y\int_{r}^{\infty}e^{-2\pi ty}M(t)dt.$

It is easy to check (cf.[3]) that if $|\hat{\mu}|$ is a temperate
distribution, then $|\hat{\mu}|(-r,r)=O(r^{\kappa})$ as $r\to\infty$ with some
$\kappa<\infty$. Hence, (14) is less than any $\eta>0$ for $T_{0}$ large
enough.

The last sum in (13) is less than

(16) $2\pi(e^{2\pi\varepsilon y}-1)\sum_{0<\gamma<T_{0}}|b_{\gamma}|.$

Since $\hat{\mu}$ is a measure, we see that
$\sum_{0<\gamma<T_{0}}|b_{\gamma}|<\infty$, therefore (16) is less than $\eta$
for small $\varepsilon$. Hence we obtain from (12)

$\lim_{\varepsilon\to
0}(\mu,\hat{\alpha}_{z}(\lambda)\hat{\varphi}_{\varepsilon}(\lambda))=(\hat{\mu},\alpha_{z}(t))=-2\pi
i\sum_{\gamma\in\Gamma\cap{\mathbb{R}}_{+}}b_{\gamma}e^{2\pi i\gamma z}.$

On the other hand, we have

(17)
$(\mu,\hat{\alpha}_{z}(\lambda)\hat{\varphi}_{\varepsilon}(\lambda))=\frac{\hat{\varphi}(\varepsilon
a_{0})}{z-a_{0}}+\sum_{n\in{\mathbb{N}}}\left[\frac{\hat{\varphi}(\varepsilon
a_{n})}{z-a_{n}}+\frac{\hat{\varphi}(\varepsilon a_{-n})}{z-a_{-n}}\right].$

The function $\hat{\varphi}(t)$ tends to $1$ as $t\to 0$ and
$|\hat{\varphi}(t)|\leq 1$. We have

$\left[\frac{\hat{\varphi}(\varepsilon
a_{n})}{z-a_{n}}+\frac{\hat{\varphi}(\varepsilon
a_{-n})}{z-a_{-n}}\right]=\hat{\varphi}(\varepsilon
a_{-n})\left[\frac{1}{z-a_{n}}+\frac{1}{z-a_{-n}}\right]+\frac{1}{z-a_{n}}[\hat{\varphi}(\varepsilon
a_{n})-\hat{\varphi}(\varepsilon a_{-n})].$

Since $\hat{\varphi}$ is even, we get with bounded $\theta(n)$ and $\phi(n)$

$\hat{\varphi}(\varepsilon a_{n})-\hat{\varphi}(\varepsilon
a_{-n})=\hat{\varphi}(\varepsilon
n+\varepsilon\phi(n))-\hat{\varphi}(-\varepsilon
n+\varepsilon\phi(-n))=\hat{\varphi}^{\prime}(\varepsilon
n+\varepsilon\theta(n))\varepsilon|\phi(n)-\phi(-n)|.$

Since $\hat{\varphi}(t)$ belongs to Schwartz space, we see that
$\hat{\varphi}^{\prime}(t)=O(1/|t|)$ as $t\to\infty$. Hence for
$\varepsilon\geq 1/|n+\theta(n)|$

$|\varepsilon[\hat{\varphi}^{\prime}(\varepsilon n+\varepsilon\theta(n))]|\leq
C|n|^{-1}$

with a constant $C<\infty$. The same estimate (with another constant $C$) is
valid for $\varepsilon<1/|n+\theta(n)|$, that for all $n\in{\mathbb{N}}$ and
$\varepsilon>0$

$|\hat{\varphi}(\varepsilon a_{n})-\hat{\varphi}(\varepsilon
a_{-n})|\leq(C/n)2\sup_{n}|\phi(n)|.$

Hence the right-hand side of (17) for all $\varepsilon>0$ is majorized by the
sum

(18)
$\frac{1}{|z-a_{0}|}+\sum_{n\in{\mathbb{N}}}\left|\frac{1}{z-a_{n}}+\frac{1}{z-a_{-n}}\right|+\sum_{n\in{\mathbb{N}}}\frac{C^{\prime}}{n|z-a_{n}|}.$

By Theorem 1, we have $1/(z-a_{n})=O(1/n)$. Taking into account also Corollary
1, we get the convergence of both sums in (18). Therefore we can go to the
limit in (17) as $\varepsilon\to 0$ and obtain (10).

By (15), $\sum_{\gamma\geq 1}|b_{\gamma}|e^{-2\pi\gamma y_{0}}<\infty$ for
$y_{0}>0$, and $\sum_{0<\gamma<1}|b_{\gamma}|<\infty$. Therefore the series in
right-hand part of (10) absolutely converges, and $f^{\prime}(z)/f(z)$ is
almost periodic on the line $y=y_{0}$.

Furthermore, the measure $\mu$ is real-valued, hence,
$b_{-\gamma}=\bar{b}_{\gamma}$. Therefore, in the case $y_{0}<0$ we can apply
(10) to the function $\overline{f(\bar{z})}$ and obtain (11).

######  Theorem 2.

For measures $\mu$, $\hat{\mu}$, and the almost periodic set
$A=\\{a_{n}\\}_{n\in{\mathbb{Z}}}$ as above there is the almost periodic
entire function of the form

(19) $F(z)=e^{g(z)}f(z),$

where $f(z)$ is defined in (9) and

(20) $g(z):=\sum_{\gamma\in\Gamma,0<\gamma<1}b_{\gamma}\frac{e^{2\pi i\gamma
z}-1}{\gamma}.$

Proof. The sum $\sum_{\gamma\in\Gamma\cap{\mathbb{R}}_{+}}b_{\gamma}e^{2\pi
i\gamma z}$ is majorized by

$\sum_{\gamma\in\Gamma,o<\gamma<1}|b_{\gamma}|+\sum_{\gamma\geq
1}|b_{\gamma}|e^{-2\pi\gamma y}.$

Since $\hat{\mu}$ is a measure, the first sum is finite, the second one is
also finite due to (15). In particular, the function

$g(z)=\sum_{k=1}^{\infty}\frac{(2\pi
iz)^{k}}{k!}\sum_{\gamma\in\Gamma,0<\gamma<1}\gamma^{k-1}b_{\gamma}$

is well-defined and holomorphic for all $z\in{\mathbb{C}}$. Using (10) for
$z=x+iy\in{\mathbb{C}}_{+}$ and changing the order of summing and integrating,
we get

(21) $\log f(z)-\log
f(iy)=\int_{0}^{x}\frac{f^{\prime}(t+iy)}{f(t+iy)}dt=-\left[\sum_{\gamma\in\Gamma\cap{\mathbb{R}}_{+}}b_{\gamma}e^{-2\pi\gamma
y}\frac{e^{2\pi i\gamma x}-1}{\gamma}\right].$

Also, both sums

$\sum_{\gamma\in\Gamma,\gamma\geq 1}\gamma^{-1}e^{-2\pi\gamma
y}\,b_{\gamma}(1-e^{2\pi i\gamma
x})\quad\mbox{and}\quad\sum_{\gamma\in\Gamma,0<\gamma<1}\frac{e^{-2\pi\gamma
y}-1}{\gamma}b_{\gamma}(1-e^{2\pi i\gamma x})$

are uniformly bounded in every strip $\\{z:\,0<\alpha\leq\mbox{Im
}z\leq\beta<\infty\\}$. Therefore in this strip

(22) $\log
f(z)=-\sum_{\gamma\in\Gamma,0<\gamma<1}b_{\gamma}\gamma^{-1}[e^{2\pi i\gamma
z}-1]+O(1).$

In particular, the function $\log|f(z)|+\mbox{Re }g(z)$ is bounded in this
strip, and the function $F(z)$ is uniformly bounded in every closed horizontal
substrip of a finite width in ${\mathbb{C}}_{+}$.

Arguing by the same way, we get for $z=x+iy\in{\mathbb{C}}_{-}$

$\log f(z)=\sum_{\gamma\in\Gamma,-1<\gamma<0}b_{\gamma}\gamma^{-1}[e^{2\pi
i\gamma z}-1]+O(1).$

Since $b_{-\gamma}=\bar{b}_{\gamma}$, we see that the real part of the right-
hand side of the equality equals

$-\mbox{Re
}\sum_{\gamma\in\Gamma,0<\gamma<1}\bar{b}_{\gamma}\gamma^{-1}[e^{-2\pi i\gamma
z}-1]+O(1)=-\mbox{Re
}\sum_{\gamma\in\Gamma,0<\gamma<1}b_{\gamma}\gamma^{-1}[e^{2\pi
i\gamma\bar{z}}-1]+O(1).$

Taking into account that

$\left|\sum_{\gamma\in\Gamma,0<\gamma<1}b_{\gamma}\gamma^{-1}[e^{2\pi
i\gamma\bar{z}}-1]-\sum_{\gamma\in\Gamma,0<\gamma<1}b_{\gamma}\gamma^{-1}[e^{2\pi
i\gamma
z}-1]\right|\leq\sum_{\gamma\in\Gamma,0<\gamma<1}|b_{\gamma}|\left|\frac{e^{2\pi\gamma
y}-e^{-2\pi\gamma y}}{\gamma y}\right||y|,$

we obtain that the function $\log|f(z)|+\mbox{Re }g(z)$ is bounded in every
strip $\\{z:\,-\infty<\alpha\leq\mbox{Im }z\leq\beta<0\\}$, and the function
$F(z)$ is uniformly bounded in every closed horizontal substrip of a finite
width in ${\mathbb{C}}_{-}$ as well.

Furthermore, in any strip $\\{z:\,|\mbox{Im }z|<M\\}$

(23)
$|g(z)-g(x)|\leq\sum_{\gamma\in\Gamma,0<\gamma<1}|b_{\gamma}|\left|\frac{e^{2\pi
i\gamma x}(e^{2\pi\gamma y}-1)}{\gamma y}\right||y|<C(M),$

and

(24)
$|g(x)|\leq\left[\sum_{\gamma\in\Gamma,0<\gamma<\varepsilon}+\sum_{\gamma\in\Gamma,\varepsilon\leq\gamma<1}\right]|b_{\gamma}|\left|\frac{1-e^{2\pi
i\gamma x}}{\gamma}\right|\leq
2\pi|x|\sum_{o<\gamma<\varepsilon}|b_{\gamma}|+2\varepsilon^{-1}\sum_{\varepsilon\leq\gamma<T_{0}}|b_{\gamma}|.$

Since $\sum_{o<\gamma<\varepsilon}|b_{\gamma}|$ is arbitrary small, we see
that $g(x)=o(|x|)$ as $x\to\infty$. Therefore the function $g(z)$ has the same
growth in any horizontal strip of the finite width. Also, $\log|f(z)|\leq
O(|z|)$ in this strip. Applying Fragment-Lindelof Principle, we obtain that
$F(z)$ is bounded in every such strip.

It follows from (22) that the function $\log F(z)=\log f(z)+g(z)$ is bounded
on any line $y=\operatorname{const}$. Then we have

$(\log F(x+iy))^{\prime}=f^{\prime}(x+iy)/f(x+iy)+2\pi
i\sum_{\gamma\in\Gamma,0<\gamma<1}b_{\gamma}e^{2\pi i\gamma x-2\pi y}.$

Since the function $f^{\prime}(x+iy)/f(x+iy)$ is almost periodic in $x$, we
see that Bohr’s theorem (cf.[10], Theorem 1.2.1) implies almost periodicity of
the function $\log F(x+iy)$ and then $F(x+iy)$. By ([10], Theorem 1.2.3), the
function $F(z)$ is almost periodic in every strip, where it is bounded, hence
it is almost periodic in ${\mathbb{C}}$.

######  Theorem 3.

In conditions of the previous theorem, $A$ to be the zero set of an almost
periodic entire function of exponential type if and only if the function
$g(z)$ from (20) is uniformly bounded on ${\mathbb{R}}$. If this is the case,
the entire function (9) is almost periodic.

Proof. Let $g(z)$ be uniformly bounded for $z\in{\mathbb{R}}$. By (23), the
function $g(x+iy)$ is also bounded in $x$ for any fixed $y>0$. It follows from
(22) that the function $\log f(x+iy)$ is also bounded in $x\in{\mathbb{R}}$.
But $(\log f(x+iy))^{\prime}$ is almost periodic, hence, by Bohr’s Theorem,
the functions $\log f(x+iy)$ and $f(x+iy)$ are almost periodic too. The
function $f$ is the exponential type, and by Fragment-Lindelof Principle, it
is bounded on every horizontal strip of a finite width. Hence, it is almost
periodic on such strips, consequently, $f$ is an almost periodic entire
function with the given zero set $A$.

Now suppose that $G(z)$ is an entire almost periodic function of exponential
type with zero set $A$. Clearly, $G(z)=K_{1}e^{K_{2}z}f(z)$ with
$K_{1},\,K_{2}\in{\mathbb{C}}$. Since zero set of $G(z)$ coincides with $A$,
we get, using Lemma 1 from [9], Ch.6, that for every $\varepsilon>0$ and
$M<\infty$ there is $m(\varepsilon)>0$ such that

$|G(z)|\geq m(\varepsilon)\quad\mbox{for}\quad\\{z:\,|\mbox{Im }z|\leq
M,\,z\not\in A(\varepsilon)\\},\quad\mbox{where}\quad
A(\varepsilon):=\\{z:\,\operatorname{dist}(z,A)<\varepsilon\\}.$

By Proposition 1, for $\varepsilon$ small enough each connected component of
$A(\varepsilon)$ contains no segment of length $1$, hence its diameter is less
than $1$. Let $F$ be the almost periodic function that defined in (19). The
holomorphic function $F(z)/G(z)$ is uniformly bounded on the set
$\\{z:\,|\mbox{Im }z|<M,\,z\not\in A(\varepsilon)\\}$, therefore it is
uniformly bounded on the whole strip $|\mbox{Im }z|<M$. Then $|G(x+iy)|\geq
m(\varepsilon)$ for any $y=y_{0}>\varepsilon$, therefore $F(x+iy)/G(x+iy)$ is
almost periodic in $x$ for $y=y_{0}$. Consequently, it is almost periodic for
every $|y|<M$, in particular, on the real line. Moreover, $F(z)/G(z)$ has no
zeros, hence the same Lemma 1 from [9] implies that $|F(x)/G(x)|\geq c>0$ for
all $x$. Now by Theorem 2.7.1 from [10],

$F(x)/G(x)=e^{h(x)+i\omega x},\qquad\omega\in{\mathbb{R}},$

with almost periodic $h(x)$. Therefore the function $g(x)-K_{2}x-i\omega
x=h(x)$ is bounded on ${\mathbb{R}}$. By (24), $g(x)=o(|x|)$ as $x\to\infty$,
hence, $K_{2}=-i\omega$ and $g(x)$ is bounded on ${\mathbb{R}}$.

######  Corollary 2.

If $\sum_{\gamma\in\Gamma,0<\gamma<1}\gamma^{-1}|b_{\gamma}|<\infty$, then $A$
is the zero set of some almost periodic entire function of exponential type.

## References

  * [1] C.Corduneanu. Almost Periodic Functions, Second English ed. Chelsea, New-York, 1989 (Distributed by AMS and Oxford University Press).
  * [2] Directions in Mathematical Quasicrystals, M.Baake, R.Moody, eds. CRM Monograph series 2000 13, AMS, Providence RI, 379p.
  * [3] S.Yu.Favorov. Uniqueness Theorems for Fourier Quasicrystals and Temperate Distributions with Discrete Support. Proc. Amer. Math. Soc. 149 (2021), 4431-4440
  * [4] S.Yu.Favorov Large Fourier Quasicrystals and Wiener’s Theorem, Journal of Fourier Analysis and Applications, 25, Issue 2, (2019), 377-392, DOI 10.1007/s00041-017-9576-0
  * [5] S.Yu.Favorov, Ye.Yu.Kolbasina. Perturbations of discrete lattices and almost periodic sets. Algebra and Discrete Mathematica, 9 (2) (2010), 48-58.
  * [6] S.Yu.Favorov, Ye.Yu.Kolbasina. Almost periodic discrete sets// Journal of Mathematical Physics, Analysis, Geometry. v.6 (2010), No.1, 1-14.
  * [7] S.Yu.Favorov, A.Yu.Rashkovskii, and L.I.Ronkin. Almost periodic divisors in a strip //Journal d’Analyse Mathematique, Vol.74 (1998), 325-345.
  * [8] W.Lawton Bohr Almost Periodic Sets of Toral Type. The Journal of Geometric Analysis 32:60, (2022).
  * [9] B.Ja.Levin, Distributions of Zeros of Entire Functions. Transl. of Math. Monograph, Vol.5, AMS Providence, R1, 1980.
  * [10] B.M.Levitan, Almost periodic functions. Gostehizdat, 1953, Moskow. 396 p. (In Russian)
  * [11] J.C.Lagarias Mathematical Quasicrystals and the Problem of Diffraction, in [2], 61-93.
  * [12] Y.Meyer Quasicrystals, Almost Periodic Patterns, Mean–periodic Functions, and Irregular Sampling, African Diaspora Journal of Mathematics, 13 no.1, (2012) 1-45.
  * [13] Y.Meyer, Global and local estimates on trigonometric sums, Trans. R. Norw. Soc. Sci. Lett. 2018(2) 1-25.
  * [14] Olevskii, A., Ulanovskii A. A Simple Crystalline Measure. arXiv:2006.12037v2, (2020).
  * [15] Olevskii, A., Ulanovskii A. Fourier quasicrystals with unit masses. arXiv:2009.12810v1, (2020).
  * [16] Quasicrystals and Discrete Geometry. J.Patera,ed., Fields Institute Monographs 1998, AMS, Providence RI, 289p.
  * [17] L.I.Ronkin, L.I. Almost Periodic Distributions and Divisors in Tube Domains, Zap. Nauchn. Sem. POMI 247 (1997) 210–236 (Russian).
  * [18] Tornehave,H. On the zeros of entire almost periodic function. The Harald Bohr Centenary (Copenhagen 1987). Math. Fys. Medd. Danske, 42, no.3 (1989), 125-142.


# BGT-Net: Bidirectional GRU Transformer Network for Scene Graph Generation

Naina Dhingra Florian Ritter Andreas Kunz
Innovation Center Virtual Reality  ETH Zurich
$\\{$ndhingra<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Scene graphs are nodes and edges consisting of objects and object-object
relationships, respectively. Scene graph generation (SGG) aims to identify the
objects and their relationships. We propose a bidirectional GRU (BiGRU)
transformer network (BGT-Net) for the scene graph generation for images. This
model implements novel object-object communication to enhance the object
information using a BiGRU layer. Thus, the information of all objects in the
image is available for the other objects, which can be leveraged later in the
object prediction step. This object information is used in a transformer
encoder to predict the object class as well as to create object-specific edge
information via the use of another transformer encoder. To handle the dataset
bias induced by the long-tailed relationship distribution, softening with a
log-softmax function and adding a bias adaptation term to regulate the bias
for every relation prediction individually showed to be an effective approach.
We conducted an elaborate study on experiments and ablations using open-source
datasets, i.e., Visual Genome, Open-Images, and Visual Relationship Detection
datasets, demonstrating the effectiveness of the proposed model over state of
the art.

##  1 Introduction

Visual understanding of scenes are broadly covered by object detection [30,
23] and localization [29, 6] for single or multiple objects. Evolved from
detection of various objects, image segmentation [7, 1] is another research
topic which helps to understand the attributes of the scene. While these
techniques supply some useful information of the image, but a scene also
largely depends on the interactions or relations between objects. This idea
led to scene graphs which describe the scene by incorporating the objects and
their pairwise relations. This relation is represented by a directed edge
pointing from the subject to the object. Evaluating a scene by detecting the
objects and the relationships between them allows building a graph consisting
of nodes representing the objects and the edges representing the relations. It
consists of number of triplets represented in $<$subject-relationship-
object$>$ form. They help in aiding deep understanding of the scene for
various vision tasks such as visual reasoning [28], image captioning [40, 16],
image retrieval [12, 27, 26] and visual question answering [47, 8, 34]. To
improve these applications and their benefits, it is crucial to have a well
performing model which generates scene graphs that corresponds to the actual
visual scene.

The directional nature of a triplet in scene graph defines the subject and
object in a triplet. Scene graph generation (SGG) is considered a complex
problem in computer vision because of the imbalanced nature of the datasets
and intricate relationship information. As stated in MOTIFS [45], combinations
of at least two triplets appear in many images. So, the presence of some
objects highly increase the probability of the presence of other objects.
Communication i.e. information flow between the detected objects has been
shown to be beneficial for improving the performance of scene graph generation
models [45, 4].

Figure 1: Two different scene graphs of the same given image on the left. Top:
The ground-truth scene graph as annotated in the Visual Genome dataset. Below:
A generated scene graph. As in many cases, the generated scene graph does
capture the visual scene correctly, since the scene graph generation model
only predicts frequently appearing relationships.

The frequency distribution of the relationship within the Visual Genome
dataset is long-tailed [13]. Due to this, scene graph detection models can
already achieve good performance by only predicting the most frequent
relationship for the respective subject-object pair. Figure 1 illustrates the
problem almost every SGG model faces. In many object pairings, the
relationship is trivial and mostly possessive or geometric (e.g. on, under, or
next to). The detailed descriptive and semantic relationships such as jumping
over as shown in Figure 1 (given in the ground-truth) will not often be
predicted since it rarely occurs. For creating models that represent less
frequent relationships more precisely, an approach to handle dataset bias must
be found. Since the bias in the dataset can also be beneficial, e.g. the
probability for the relationship reading will be much higher than for eating
if the subject-object pair given is person and book [32], traditional
debiasing methods will most likely strongly harm the performance of the model.
For this reason, the handling of the bias in the dataset is one of the most
under-explored properties of the scene graph generation task.

In this paper, we propose a novel model for SGG. The objects present in an
image are highly dependent on the presence of other objects, for instance, if
there is a bike in the scene, then there will be two tyres in the same scene
with a very high probability. This model uses a bidirectional GRU (BiGRU)
layer to send information from every object to every other. This allows
benefiting from the fact that some objects will increase the possibility for
specific other objects to be present.

Subsequently to this layer that covers the object-object communication, a
transformer encoder layer is used to predict the object classes. Objects and
their preferred or observed relations are closely connected. To extract the
information for the edge, a similar approach as in [45] is followed to specify
the edge context for every detected object. We use an additional transformer
encoder layer for this task of extracting the edge context features.

Using the object representations, their respective edge context is then used
for the relationship prediction. In this procedure, a log-softmax function is
applied to the subject-object pairwise relationship distribution. Following
this Frequency Softening (FS), a Bias Adaptation (BA) approach [21] is used.
The bias for every subject-object is controlled by the bias adaptation term
which takes scene-specific inputs to vary the amount of added bias.

The contribution summary of the proposed BGT-Net is given in four modules to
improve scene graph generation performance: (1) Object-object communication is
performed using the BiGRU’s. (2) A transformer encoder with scaled-dot-product
attention is used to predict object classes after they have received
information about the other objects present in the scene. (3) For every
object, a second transformer encoder is used to gather information for the
edges. (4) To tackle the bias in the relationship distribution, FS and BA [21]
is adopted.

The evaluation efficacy of the proposed BGT-Net is performed on three SGG
datasets: Visual Genome (VG) [13], OpenImages (OI) [14], and Visual
Relationship Detection (VRD) [22]. We perform extensive experiments and
ablation study to demonstrate the effectiveness of BGT-Net. Experimental
results illustrate that the proposed BGT-Net outperforms the state of the art
SGG results on a common metric Recall@K and on different datasets to the best
of our knowledge.

The framework of BGT-Net uses Faster R-CNN (with VGG-16 or ResNext-101 as the
backbone) to get the visual features and spatial locations of object
proposals. It includes various sub-modules for the task of SGG: (1) New
technique of using BiGRU for object-object communication, (2) Novel method of
using a transformer encoder with scaled-dot-product attention for predicting
object classes after they have received information of the other objects
present in the scene, (3) Additional transformer encoder is used to get the
edge features, (4) FS and BA are used for dealing with the bias in the
dataset.

##  2 Related Work

From the ongoing research in scene graph generation, two different approaches
for scene graph construction have developed. In the less common two-stage
approach [33, 10, 4, 33], attributes of the scene graph are used in the second
training step to refine the results produced by the first stage. Much more
common are the one-stage approaches [4, 45, 5, 37, 39, 21, 18, 22, 17, 24]
which focus only on object detection and relationship classification, while
almost neglecting intrinsic features. The proposed BGT-Net follows a one step
approach and has the following advantages as compared to the literature work:
(1) It uses object-object communication which improves the performance in SGG;
(2) It deploys transformer encoder for object and edge context prediction
which has shown to be highly beneficial in optimizing the parameters of SGG;
(3) It is easy to train.

The MOTIFS [45] stated in the early days of scene graph generation, that there
are different combinations of triplets that appear in a lot of images.
Therefore, a dependency between object appearances is present in the datasets.
To leverage this information object communication has been examined in the
CMAT model [4] and improved the performance of the model. All of the published
works show difficulties with the bias present in the Visual Genome dataset,
which is widely used in the scene graph generation task. This bias arrives
from the long-tailed relationship distribution. The GPS-Net [21] tackled this
problem with FS and BA which worked well compared to the previous works. The
overall performance of the model could be improved as well as improvements in
mean Recall@K were achieved, which gives reasoning about the positive effect
of their approach in handling the dataset bias. So, motivated from GPS-Net,
BGT-Net uses FS and BA. While the GPS-Net changed the way the model was built,
another recent work [32] developed a Scene Graph Diagnosis toolkit that can be
used on a casually built scene graph. This tool kit is based on casual
inference. Drawing the counterfactual causality to the proposed graph allows
inferring with the bad bias. This approach did largely improve the mean
Recall@K but decreased the other metrics significantly. Similarly [38],
adaptively changed the weights of the loss by using the correlation between
the relationship classes. This work improved mean Recall@K but had overall
quite low Recall@K results.

##  3 Approach

The illustration of the BGT-Model can be found in Figure 1. The regions of
interest and object proposals are obtained by employing a Faster R-CNN object
detector [25]. Following the VG-split [37], there are 151 object categories
(including ’background’) and 50 relationship categories (including ’no
relation’). For every proposal $i$, the visual feature
$\boldsymbol{\hat{x_{i}}}$ is formed by concatenating the ROI (region of
interest) feature $\boldsymbol{f_{i}}\in\mathbb{R}^{2048}$, the class
confidence scores $\boldsymbol{s_{i}}\in\mathbb{R}^{151}$, and the spatial
feature of the proposal bounding box $\boldsymbol{s_{i}}\in\mathbb{R}^{4}$.
For the next step, the $\boldsymbol{x_{i}}\in\mathbb{R}^{512}$ gets
transformed by the projection of $\boldsymbol{\hat{x_{i}}}$ into a
512-dimensional subspace. For the relationship classification, the union
feature $\boldsymbol{u_{i,j}}\in\mathbb{R}^{2048}$ for every pair of objects
$i$ and $j$ is extracted in the object detection stage. These feature vectors
representing the scene are used in the following modules of the BGT-Model. In
Section 3.1, the object communication step implemented with a BiGRU is
explained in detail. Section 3.2, introduces the object classification and
edge information generation step using transformers. In Section 3.3, the FS of
the long-tailed relationship distribution and the BA as a pre-processing for
the relationship classification is described.

###  3.1 Object Communication

The object communication module takes the visual features $\boldsymbol{x_{i}}$
as input. The communication between the objects is implemented by a BiGRU. Due
to the architecture of BiGRU, information from every object can flow to every
other object. This information flow can be regulated by the BiGRU by learning
which information shall be passed and which information shall be blocked. The
output of the object communication step is therefore given by:

$\hat{O}=BiGRU([x_{i}]_{i=1,2,...,n})$ (1)

Where $\hat{O}=\\{\hat{o}_{1},\hat{o}_{2},...,\hat{o}_{n}\\}$ are the object
features after the communication step. The $\hat{o}_{i}\in\mathbb{R}^{1028}$
is obtained by concatenating the outputs $\overrightarrow{\hat{o}}_{i}$ (left
to right in BiGRU) and $\overleftarrow{\hat{o}}_{i}$ (right to left in BiGRU),
such that:

$\hat{o}_{i}=[\overrightarrow{\hat{o}}_{i},\overleftarrow{\hat{o}}_{i}]\in\mathbb{R}^{1028}$
(2)

###  3.2 Object and Edge Transformers

The output $\hat{O}$ is projected to a 512-dimensional subspace to be fed into
the Object transformer encoder. This transformer encoder follows the model
architecture proposed by [35], and takes the encoder block of the complete
transformer model. This transformer encoder is built up by a Multi-Head
attention layer, an Add & Norm layer, a Feed Forward layer, and another Add &
Norm layer.

The three inputs to the Multi-Head Attention layer are the values $V$, the
keys $K$ and the queries $Q$. According to [35], these three inputs are
obtained from a single input. Using three different feed-forward fully-
connected layers, yields the queries, keys, and values. For every attention
head $i$ (here i=1,2,..,8) these values are calculated by:

$Q_{i}=\hat{O}*W^{Q}_{i}$ (3) $K_{i}=\hat{O}*W^{K}_{i}$ (4)
$V_{i}=\hat{O}*W^{V}_{i}$ (5)

Where $W^{Q}_{i}\in\mathbb{R}^{512\times d_{k}}$,
$W^{K}_{i}\in\mathbb{R}^{512\times d_{k}}$ and
$W^{V}_{i}\in\mathbb{R}^{512\times d_{v}}$ are learnable parameter matrices.
Also, $d_{k}=d_{v}=64$ are the same for this application. From these values,
the Scaled Dot-Product attention is calculated, such that the output of each
attention head is given by:

$Z_{i}=softmax(\frac{Q_{i}*K_{i}^{T}}{\sqrt{d_{k}}})*V_{i}$ (6)

Concatenating $Z_{i}$’s give the output of the Multi-Head Scaled Dot-Product
layer as $Z$. This is then fed through another fully-connected layer to bring
it back to the dimension of the input matrix $\hat{O}$.

$Z=concatenate(Z_{1},Z_{2},...,Z_{n_{heads}})$ (7)

The Add & Norm layer adds the input of the previous Multi-Head Attention layer
as a residual connection to the output of the attention layer. The
normalization applied is a normalization layer following the approach of [2].
Here, it is suggested that the ‘covariate shift’ problem can be reduced by
changing the mean and the variance of the summed inputs in every layer. This
is followed by a Feed Forward layer with two linear transformations and a ReLU
activation followed by another Add & Norm layer. This transformer encoder
block gets repeated 6 times. The output $Z_{6}$ of the last repetition is then
used to predict the object labels:

$O=softmax(W_{o}*Z_{6}^{\prime})$ (8)

Where $W_{o}\in\mathbb{R}^{512\times 151}$ predicts the object class
distribution for each detected object. Repeating this procedure but using the
output $Z_{6}$ of the Object transformer as input to the Edge transformer
yields feature vectors having information about the edges for every object.
Similarly to [45], this information then can be used in the relationship
prediction step. This edge information is given formally by:

$E=TransformerEncoder(Z_{6})$ (9)

Where $E=\\{e_{1},e_{2},...,e_{n}\\}$ contains the edge information for every
object.

###  3.3 Frequency Softening(FS), Bias Adaptation(BA)

To handle the long-tailed relationship distribution present in the Visual
Genome dataset, the procedure of softening this distribution and adapting the
bias term for every subject-object pair form [21] is adopted. The used
features in this step is different than in the GPS-Net [21] , but the
principle stays the same. The softening of the relationship distribution is
done by applying a log-softmax function to the original distribution. The
softened frequency distribution is therefore given by Eq. 10. The probability
distribution $p_{i\rightarrow j}$ of every object pair $i$ and $j$ must be
softened separately. Based on this definition, softening does not take any
information of the respective visual scene into account.

$\tilde{p}_{i\rightarrow j}=log\ softmax(p_{i\rightarrow j})$ (10)

BA is used to get a case-specific adaptation of the above term. BA allows us
to adjust the bias in the relationship prediction step. This adaptation term
takes the appearance of the subject-object pair $i$, $j$ into account, by
using their union feature $u_{i,j}$. The BA term $d$ can be calculated by:

$d=W_{p}*u_{i,j}$ (11)

Where $W_{p}\in\mathbb{R}^{2048}$ is the transformation matrix and $u_{i,j}$
is the union feature of the subject-object pair. In the relationship
prediction step, this bias term can be used as follows:

$p_{i,j}=softmax(W_{r}(o^{\prime}_{i}*o^{\prime}_{j}*u_{i,j})+d\odot\tilde{p}_{i\rightarrow
j})$ (12)

In this equation, the bias $d\odot\tilde{p}_{i\rightarrow j}$ can be adjusted
by changing $d$ accordingly. Here, $o^{\prime}_{i}=[o_{i},e_{i}]$ (same for
$o^{\prime}_{j}$) with ’[-,-]’ denotes the concatenation function representing
the object features obtained in earlier steps. $W_{r}$ is the classifier that
projects the features to the relationship class dimension. $\odot$ denotes the
Hadamard Product and $*$ the fusion function. The fusion function for $(x*y)$
is given by:

$(x*y)=(W_{x}x+W_{y}y)-(W_{x}x-W_{y}y)\odot(W_{x}x-W_{y}y)$ (13)

With the parameter matrices $W_{x}$ and $W_{y}$, the fusion function is
proposed to learn to count objects in images. [51].

The predicted relationship between objects $i$ and $j$ is given by:

$r_{i,j}=argmax(p_{i,j}(r))$ (14)

Where $r$ lies in the set of relationship classes including background BG.

##  4 Experiments

We performed experiments using three different datasets, i.e., Visual Genome
(VG) [13], Visual Relationship Detection (VRD) [22], and OpenImages (OI) [14].

###  4.1 Visual Genome

Visual Genome dataset [13] is the most frequently used dataset for the SGG
task. We use the same data statistics and evaluation metrics as widely used by
the state of the art in this field, i.e., 150 object categories and 50
relationship categories are used. 70% of the dataset is used for training and
30% for testing. An additional 5000 images are taken from the training set and
are used for validation. As used by the state of the art, we also employed
Faster R-CNN [25] with VGG-16 or ResNext-101 as a backbone to get the
characteristics of object proposals. To keep the fairness in the comparison
with state-of-the-art, we chose same experimental factors as chosen by [21].

Performance Diagnosis: The scene graph generation model is evaluated in three
different sub-tasks: (1) Predicate classification, (2) Scene graph
classification, and (3) Scene graph generation. These are the three protocols
for which the model’s performance is evaluated separately. Predicate Detection
is used to specify the relation of given objects. This protocol evaluates the
set of possible relations between a pair of given objects. The prediction of
relationships without the effect of object detection is examined. In Phrase
Detection, the input is an image and the outputs are triplets of subject-
predicate-object. Additionally, one bounding box must have an overlap of at
least 0.5 with the corresponding ground truth. For Relation Detection, the
same input and output as in Phrase Detection is used. In this case, not only
one but two bounding boxes of the pair of objects must have at least 0.5
overlap with the ground truth.

Metrics. The evaluated metrics for the diagnosis of the model performance is
Recall at K (R@K), no graph constraint Recall at K (nGR@K), zero-shot Recall
at K (zsR@K), and mean Recall (mR@K), where $K$=20, 50, and 100, respectively.

Object Detector: A pretrained Faster R-CNN object detector with a VGG-16 net
[9] or ResNeXt-101-FPN [36] as a backbone is used which is taken from [21].
This detector was trained on the VG dataset, with batch size 8 and initial
learning rate $8*10^{-3}$ which is decayed at the $30k^{th}$ and $40k^{th}$
iteration by the factor of 10. After training this detector on 4 2080Ti GPU,
28.14 mAP (with 0.5 IoU) was achieved.

Scene Graph Generation: The scene graph generation is trained with an SGD
optimizer [3]. The learning rate is set at $10^{-3}$ for all three protocols.
This learning rate was decayed by a factor of 10 twice after hitting a
validation performance plateau. Per-Class non-maximal suppression (NMS) was
applied with 0.5 IoU. 160 RoIs for each image were sampled. In contrast to
previous works, we also considered non-overlapping regions for relationship
prediction. To generalize the scene graph generation task, we used similar
settings as used in literature [21]. For model training, an RTX Titan was
used. The batch size was set to 12 and the learning rate started at $10^{-3}$
and was reduced two times by a factor of 10 after hitting a validation
performance plateau. The number of solver iterations was set to 18000.

###  4.2 OpenImages

The training and validation sets of the OpenImages dataset contain 53,953 and
3,234 images. For comparison, we use the same Faster R-CNN detector with a
pre-trained ResNeXt- 101-FPN backbone as used by [21, 50]. Also, the same data
processing and evaluation metrics are used as in these previous works [21,
50]. The evaluation metrics are Recall$@$50, weighted mean average precision
(AP) of relationships wmAPrel, and weighted mean AP of phrase wmAPphr. The
final score is given by<EMAIL_ADDRESS>which was
adopted from the OpenImages challenge formula [49], where the mAP was replaced
by its weighted counterpart. The replacement of the mAP with the wmAP was done
[49] due to the extreme predicate class imbalance. The wmAP is achieved by
scaling each predicate category by their relative ratios in the val set from
the mAP. Important to note is that the wmAPrel evaluates the AP of the
predicted triplet where both the subject and object boxes have an IoU of at
least 0.5 with ground truth. The wmAPphr is quite similar but is utilized for
the union box of the subject and the object.

###  4.3 Visual Relation Detection

The Visual Relation Detection (VRD) dataset was introduced by [22]. We adopt
the same detectors as [49]. Specifically, we use a pre-trained Faster R-CNN
detector with VGG-16 backbone trained on the COCO dataset [20]. The evaluation
process is given by [22] and the metrics used are R$@$50 and R$@$100.

###  4.4 Implementation Details

We follow the same implementation parameters as used by [21]. To ensure a fair
comparison with state of the art, we used VGG-16 and ResNext-101 as backbone.
We use the 10-3 as the learning rate and 6 as the batch-size which is the same
as used by [21]. We use SGD with momentum as the optimizer for the training
process. We use the relationship between overlapped bounding boxes and
subject-object pairs for the SGDet process. NMS with an IoU of 0.3 is used and
the topmost 64 object proposals are chosen. The ratio of 3:1 is maintained
during training between the subject-object pairs with and without any
relationship.

###  4.5 Comparisons with State-of-the-Art Methods

|  |  | SGdet |  |  |  | SGCls |  |  |  | PredCls |  |  |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Model |  | $R@20$ | $R@50$ | $R@100$ |  | $R@20$ | $R@50$ | $R@100$ |  | $R@20$ | $R@50$ | $R@100$ |  | Mean
MOTIFS $\star$ [45] |  | 21.4 | 27.2 | 30.3 |  | 32.9 | 35.8 | 36.5 |  | 58.5 | 65.2 | 67.1 |  | 43.7
FREQ $\star$ [45] |  | 20.1 | 26.2 | 30.1 |  | 29.3 | 32.3 | 32.9 |  | 53.6 | 60.6 | 62.2 |  | 40.7
VCTREE-SL $\star$ [33] |  | 21.7 | 27.7 | 31.1 |  | 35.0 | 37.9 | 38.6 |  | 59.8 | 66.2 | 67.9 |  | 44.9
VCTREE-HL $\star$ [33] |  | 22.0 | 27.9 | 31.3 |  | 35.2 | 38.1 | 38.8 |  | 60.1 | 66.4 | 68.1 |  | 45.1
GB Net $\star$ [44] |  | - | 26.3 | 29.9 |  | - | 37.3 | 38 |  | - | 66.6 | 68.2 |  | 44.4
NODIS $\star$ [43] |  | 21.5 | 27.4 | 30.7 |  | 36 | 39.8 | 40.7 |  | 58.9 | 66 | 67.9 |  | 45.4
GPS-Net $\star$ [21] |  | 22.6 | 28.4 | 31.7 |  | 36.1 | 39.2 | 40.1 |  | 60.7 | 66.9 | 68.8 |  | 45.9
CMAT $\star$ [4] |  | 22.1 | 27.9 | 31.2 |  | 35.9 | 39 | 39.8 |  | 60.2 | 66.4 | 68.1 |  | 45.4
KERN $\star$ [5] |  | - | 27.1 | 29.8 |  | - | 36.7 | 37.4 |  | - | 65.8 | 67.6 |  | 44.1
Graph R-CNN $\star$ [39] |  | - | 11.4 | 13.7 |  | - | 29.6 | 31.6 |  | - | 54.2 | 59.1 |  | 33.3
IMP $\star$ [37] |  | - | 3.44 | 4 .24 |  | - | 21.72 | 24.38 |  | - | 44.75 | 53.08 |  | 25.3
BGT-Net (no BiGRU) $\star$ |  | 23.61 | 30.4 | 34.81 |  | 33.81 | 37.22 | 38.12 |  | 57.98 | 64.75 | 66.63 |  | 46.9
BGT-Net $\star$ |  | 23.1 | 28.6 | 32.2 |  | 38.0 | 40.9 | 43.2 |  | 60.9 | 67.3 | 68.9 |  | 46.9
BGT-Net $\diamond$ |  | 25.5 | 32.8 | 37.3 |  | 41.7 | 45.9 | 47.1 |  | 60.9 | 67.1 | 68.9 |  | 49.9

[Recall@K Model comparison with state-of-the-arts on the VG dataset.]Recall@K
Model comparison with state-of-the-arts on the VG dataset. We compare R@20,
R@50, and R@100. For some literature work, the R@20 is not given. We used
’$-$’ which denotes that the result is unavailable. So, the mean is calculated
using values of R@50 and R@100 to have fair comparison with state of the art.
Models using the same VGG backbone are denoted with ’$\star$’ and the BGT-Net
with ResNext-101 background is marked with ’$\diamond$’.

|  | SGdet |  | SGCls |  | PredCls |  |
---|---|---|---|---|---|---|---|---
Model |  | $mR@100$ |  | $mR@100$ |  | $mR@100$ |  | Mean
GB Net $\star$ [44] |  | 8.5 |  | 13.4 |  | 24 |  | 15.3
IMP $\star$ [37] |  | 4.8 |  | 6.0 |  | 10.5 |  | 7.1
GPS-Net $\star$ [21] |  | 9.8 |  | 12.6 |  | 22.8 |  | 15.1
VCTREE-HL $\star$ [33] |  | 8.0 |  | 10.8 |  | 19.4 |  | 12.8
MOTIFS $\star$ [45] |  | 6.6 |  | 8.2 |  | 15.3 |  | 10.0
KERN $\star$ [5] |  | 7.3 |  | 10 |  | 19.2 |  | 12.2
BGT-Net $\star$ |  | 9.6 |  | 13.7 |  | 23.2 |  | 15.5

Table 1: Comparison on mR@100 between various methods across all 50
relationship categories.

|  |  | SGdet |  |  |  | SGCls |  |  |  | PredCls |
---|---|---|---|---|---|---|---|---|---|---|---|---
Model |  | $nGR@20$ | $nGR@50$ | $nGR@100$ |  | $nGR@20$ | $nGR@50$ | $nGR@100$ |  | $nGR@20$ | $nGR@50$ | $nGR@100$
GB Net $\star$ [44] |  | - | 29.3 | 35 |  | - | 46.9 | 50.3 |  | - | 83.5 | 90.3
CMAT $\star$ [4] |  | 23.7 | 31.6 | 36.8 |  | 41 | 48.6 | 52 |  | 68.9 | 83.2 | 90.1
KERN $\star$ [5] |  | - | 30.9 | 35.8 |  | - | 45.9 | 49 |  | - | 65.8 | 67.6
BGT-Net (no BiGRU) $\diamond$ |  | 24.23 | 32.88 | 39.06 |  | 38.55 | 46.28 | 50.04 |  | 65.92 | 80.51 | 87.82
BGT-Net $\diamond$ |  | 27.24 | 36.91 | 43.72 |  | 47.83 | 57.67 | 62.29 |  | 69.1 | 83.71 | 90.55
Model |  | $mR@20$ | $mR@50$ | $mR@100$ |  | $mR@20$ | $mR@50$ | $mR@100$ |  | $mR@20$ | $mR@50$ | $mR@100$
GB Net $\star$ [44] |  | - | 7.1 | 8.5 |  | - | 12.7 | 13.4 |  | - | 22.1 | 24
GPS-Net$\star$[21] |  | - | - | 9.8 |  | - | - | 12.6 |  | - | - | 22.8
KERN $\star$[5] |  | - | 6.4 | 7.3 |  | - | 9.4 | 10 |  | - | 17.7 | 19.2
BGT-Net (no BiGRU) $\diamond$ |  | 4.62 | 6.55 | 7.85 |  | 7.31 | 9.14 | 9.71 |  | 12.14 | 15.59 | 17.05
BGT-Net $\diamond$ |  | 5.69 | 7.81 | 9.25 |  | 10.41 | 12.77 | 13.61 |  | 16.8 | 20.56 | 22.98
Model |  | $zsR@20$ | $zsR@50$ | $zsR@100$ |  | $zsR@20$ | $zsR@50$ | $zsR@100$ |  | $zsR@20$ | $zsR@50$ | $zsR@100$
Motifs $\star$[31] |  | 0 | 0.05 | 0.11 |  | 0.32 | 0.91 | 1.39 |  | 1.35 | 3.63 | 5.36
IMP $\star$[37] |  | 0.18 | 0.38 | 0.77 |  | 2.01 | 3.03 | 3.92 |  | 12.17 | 17.66 | 20.25
BGT-Net $\diamond$ |  | 1.22 | 2.38 | 3.42 |  | 4.8 | 7.37 | 8.78 |  | 12.23 | 18.31 | 21.51

[No Graph Constraint Recall Results of transformer Model]nGR@K, mR@K and zsR@K
comparison with state-of-the-art on the VG dataset. The version of the BGT-
Net, i.e., the BGT-Net (no BiGRU) is also compared.

|  | Predicate Detection | Relation Detection |  | Phrase Detection |  |
---|---|---|---|---|---|---|---
Model |  | $R@50$ | $R@50$ | $R@100$ |  | $R@50$ | $R@100$ |  | Mean
VTransE [48] |  | 44.8 | 19.4 | 22.4 |  | 14.1 | 15.2 |  | 23.2
ViP-CNN [11] |  | - | 17.3 | 20.0 |  | 22.8 | 27.9 |  | 22
VRL [19] |  | - | 18.2 | 20.8 |  | 21.4 | 22.6 |  | 20.8
KL distilation [42] |  | 55.2 | 19.2 | 21.3 |  | 23.1 | 24.0 |  | 28.6
MF-URLN [46] |  | 58.2 | 23.9 | 26.8 |  | 31.5 | 36.1 |  | 35.3
Zoom-Net $\diamond$ [41] |  | 50.7 | 18.9 | 21.4 |  | 24.8 | 28.1 |  | 28.8
CAI + SCA-M $\diamond$ [41] |  | 56.0 | 19.5 | 22.4 |  | 25.2 | 28.9 |  | 30.4
RelDN $\star$ [49] |  | - | 25.3 | 28.6 |  | 31.3 | 36.4 |  | 30.4
GPS-Net $\star$ [21] |  | 63.4 | 27.8 | 31.7 |  | 33.8 | 39.2 |  | 39.2
BGT-Net $\star$ |  | 64.1 | 28.5 | 31.9 |  | 34.4 | 39.4 |  | 39.6

Table 2: Comparison on the VRD dataset [22]. ’$\star$’ and ’$\diamond$’ denote
the models using the same object detector. The object detector with a VGG-16
backbone trained on COCO is used as in RelDN and GPS-Net to have fair
comparison.

|  |  |  |  |  |  APrel per class
---|---|---|---|---|---|---
Model |  | $R@50$ | $wmAP_{rel}$ | $wmAP_{phr}$ | $score_{wtd}$ | at | on | holds | plays | interacts with | wears | hits | inside of | under
RelDN, $L_{0}$ [49] |  | 74.67 | 34.63 | 37.89 | 43.94 | 32.40 | 36.51 | 41.84 | 36.04 | 40.43 | 5.70 | 55.40 | 44.17 | 25.00
RelDN [49] |  | 74.94 | 35.54 | 38.52 | 44.61 | 32.90 | 37.00 | 43.09 | 41.04 | 44.16 | 7.83 | 51.04 | 44.72 | 50.00
GPS-Net [21] |  | 77.29 | 38.78 | 40.15 | 47.03 | 35.10 | 38.90 | 51.47 | 45.66 | 44.58 | 32.35 | 71.71 | 47.21 | 57.28
BGT-Net |  | 77.98 | 39.56 | 40.75 | 47.67 | 36.23 | 39.05 | 50.96 | 46.78 | 44.56 | 31.45 | 72.17 | 48.03 | 57.64

Table 3: Comparison on OpenImages dataset [15]. The BGT-Net uses a ResNext-101
backbone. Additionally, the same data processing and evaluation metrics as
[21, 49] are followed to a ensure fair comparison.

Visual Genome: BGT-Net outperforms all the compared previous literature work
as shown in Table 4.5 on R@K for all values of K . BGT-Net performs better
than a recent model named GPS-net [21] by 6$\%$ and by 12$\%$ on average at
R@50 and R@100 over the three protocols when VGG-19 or ResNext-101 is used as
the base for the Faster-RCNN, respectively. It also outperforms when an
individual evaluation protocol is compared. The improvement is by 16.6$\%$ for
SGDet, 17.3$\%$ for SGCls, and for 0.2$\%$ for PredCls. When compared to the
classic MOTIFS [45], it showed an improvement of 7.3$\%$ and 14$\%$ on average
at R@50 and R@100 over the three protocols when VGG-19 or ResNext-101 is used
as a backbone for the Faster-RCNN, respectively. BGT-Net outperforms FREQ
[45], VCTREE-SL [33], VCTREE-HL [33], GB-NET [44] , NODIS [43], CMAT [4], KERN
[5], Graph R-CNN [39], IMP [37] by 14.9$\%$, 4.3$\%$, 3.9$\%$, 5.6$\%$,
3.2$\%$, 3.2$\%$, 6.3$\%$, 40.9$\%$, 85.4$\%$, respectively, on average at
R@50 and R@100 over the three protocols when VGG-19 is used as a backbone for
the Faster-RCNN and by 22.2$\%$, 11$\%$, 10.5$\%$, 12.3$\%$, 9.8$\%$, 9.8$\%$,
13.1$\%$, 49.9$\%$, 97.3$\%$, respectively, on average at R@50 and R@100 over
the three protocols when ResNext-101 is used as a backbone for the Faster-
RCNN.

We evaluate Mean Recall of BGT-Net to understand its performance on the class
imbalance problem. So, we study its performance by conducting experiments to
calculate its Mean Recall [5, 33, 21]. We see in Figure 2 and Table 1 that
BGT-Net performs well considering the Mean Recall evaluation metric. The mean
of the Mean Recall over all the three evaluation metrics (SGDet, SGCls,
PredCls) is 15.5 for BGT-Net and hence outperforms GB-Net and GPS-Net which
are the best state-of-the-art on class imbalance handling having good
performance on both mean R@K and R@K results. This gives a positive indication
that BGT-Net can tackle the problem of class imbalance while simultaneously
giving high R@K as compared to the other existing solutions to best of our
knowledge.

Why BiGRU? We investigated BGT-Net without BiGRU but BGT-Net (no BiGRU) has
lower SGCls and PredCls results (see Table 4.5). The deciding factor for using
BiGRU in BGT-Net is mR@K and nGR@K. Both these metrics significantly improve
for all three: SGDet, SGCls, PredCls when BGT-Net is with BiGRU as shown in
Table 4.5.
Also shown in Table 4.5, BGT-Net has high improvement on zsR@K as compared to
[37] and [45] which shows that it is able to better detect those subject-
predicate-object combinations which are not present in the training set.

Figure 2: The increase in R@100 in PredCls of BGT-Net compared with the MOTIFS
[45] and VCTREE [33]. The Top-35 relationship categories are selected
according to their alphabetic occurrence.

OpenImages: The results in Table 3 show that BGT-Net performs very well on the
OpenImages dataset. The overall score is 0.64 points higher than the GPS-Net
model performance. This increase in performance is achieved by an overall
increase in performance in all three evaluated metrics R$@$K, wmAPrel, and
wmAPphr. An evaluation of the per-class AP is also shown. In this evaluation,
some classes were chosen as in GPS-Net [21] and RelDN [49] to show class-
specific performance. The performances of GPS-Net and the BGT-Net are quite
close. For ”holds”, ”interacts with” and ”wears”, the GPS-Net shows a higher
AP while for the others the BGT-Net shows the highest AP. The overall
performance of the BGT-Net outperforms the state-of-the-art performance of the
GPS-Net model.

Visual Relationship Detection: The evaluation results on VRD Dataset are
illustrated in Table 2. The BGT-Net uses the same Detector as RelDN and GPS-
Net. The BGT-Net outperforms the state-of-the-art models in all three
evaluation metrics. So, BGT-Net shows the best to the date performance on the
VRD dataset as well to the best of our knowledge, and which is better than
GPS-Net and RelDN (previous best performing networks).

###  4.6 Ablation Studies

To evaluate and analyze our proposed BGT-Net, we conducted a number of
ablations as shown in Table 4.6, Table 4.6, and Table 4.6.

Network Performance with a different combination of Modules. In this study, we
evaluate the effectiveness of the network in the presence of the three
modules, i.e., Transformer, BiGRU, and FS, individually and collectively. The
performance of the network increases with the presence of all three modules.
Firstly, we evaluated for an individual module and then permutated the modules
with each other to make a combination to evaluate the performance of different
resulting configurations. As illustrated in Table 4.6, for all the three
evaluation protocols, i.e., SGDet, SGCls, and PredCls, our proposed network
with all the three modules outperforms the other network configurations with
individual modules. When modules are used together, the network performance
improves which shows that each individual module plays a significant role in
predicting objects and their relationships.

The FS and BA were adapted from [20]. In [21], they performed ablation study
with and without FS and BA. It was shown that these modules improve the
PredCls for all three R@20, R@50, and R@100. We included in our ablation the
effect of using FS which showed that zsR@20, zs@50, and zsR@100 improved
drastically for all three: SGDet, SGCls, PredCl, when using FS as shown in
Table 4.6.

Performance with different number of Transformer Heads. We performed this
ablation to validate the optimized number of transformer heads in the network.
As illustrated in Table 4.6, we can see that when 1, 2, or 6 number of
transformer heads are used, the network with 6 transformer heads performs
better in all the experiments than others for all the three evaluation
protocols. This ablation shows that the number of transformer heads also
effect the performance of the model and hence this factor is critical while
designing the network for the SGG. This study motivated us to use six
transformer heads in the novel BGT-Net.

Performance with different number of Bidirectional GRU Layers. We compare
networks with different number of BiGRU layers. To keep the comparison fair,
we use all other same parameters in the experiments except the number of BiGRU
layers. As shown in Table 4.6, it is evident that increasing the number of
BiGRU layers does not significantly improve the performance, but it does
increase the computational power and training time. Hence, in the BGT-Net, we
only use one BiGRU layer.

|  | Transformer | GRU | FS |  | R @ 20 | R @ 50 | R @ 100 | nG R @ 20 | nG R @ 50 | nG R @ 100 | zs R @ 20 | zs R @ 50 | zs R @ 100 | mR @ 20 | mR @ 50 | m R @ 100
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
|  | x | - | - |  | 23.61 | 30.4 | 34.81 | 24.23 | 32.88 | 39.06 | 0 | 0 | 0 | 4.62 | 6.55 | 7.85
|  | - | x | - |  | 24.1 | 31.2 | 35.5 | 25.37 | 34.59 | 41.14 | 0 | 0 | 0.03 | 4.07 | 5.49 | 6.51
SGDet |  | - | - | x |  | 22.3 | 28.17 | 32.56 | 25.04 | 34.58 | 41.23 | 0.95 | 1.27 | 2.21 | 4.47 | 5.98 | 7.65
|  | x | x | x |  | 24.68 | 31.87 | 36.18 | 26.23 | 35.87 | 42.46 | 1.22 | 2.38 | 3.42 | 5.69 | 7.81 | 9.25
|  | x | - | - |  | 33.81 | 37.22 | 38.12 | 38.55 | 46.28 | 50.04 | 0.15 | 0.45 | 0.7 | 7.31 | 9.14 | 9.71
|  | - | x | - |  | 40.03 | 44 | 45.02 | 45.61 | 54.82 | 59.26 | 0.19 | 0.69 | 0.99 | 7.92 | 9.85 | 10.55
SGCls |  | - | - | x |  | 35.63 | 38.92 | 39.77 | 39.41 | 47.92 | 55.56 | 3.25 | 4.99 | 5.78 | 8.2 | 10.65 | 11.34
|  | x | x | x |  | 41.72 | 45.69 | 46.74 | 47.96 | 57.42 | 61.92 | 4.12 | 6.72 | 8.06 | 10.41 | 12.77 | 13.61
|  | x | - | - |  | 57.98 | 64.75 | 66.63 | 65.92 | 80.51 | 87.82 | 0.64 | 2.06 | 3.69 | 12.14 | 15.59 | 17.05
|  | - | x | - |  | 58.52 | 65.19 | 67.08 | 65.76 | 80.38 | 87.83 | 0.68 | 2.52 | 4.46 | 12.33 | 15.79 | 17.16
PredCls |  | - | - | x |  | 56.73 | 63.48 | 65.53 | 64.87 | 79.56 | 87.2 | 11.9 | 17.78 | 20.97 | 12.05 | 15.22 | 16.46
|  | x | x | x |  | 58.71 | 65.25 | 67.1 | 67.27 | 82.05 | 89.29 | 12.06 | 18.22 | 21.49 | 14.36 | 17.88 | 19.44

[Recall@K comparison of BGT-Net with Model Performance of different
Modules.]Ablation study performed on evaluation of three models. All the
experimental factors are kept same except the ones which are being evaluated
to have fair comparison. The evaluation is conducted using Recall@K, nGR@K,
zsR@K, and mR@K.

|  | Transformer Heads |  | R @ 20 | R @ 50 | R @ 100 | nG R @ 20 | nG R @ 50 | nG R @ 100 | zs R @ 20 | zs Recall @ 50 | zs R @ 100 | mR @ 20 | mR @ 50 | m R @ 100
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
|  | 1 |  | 23.78 | 31.15 | 35.4 | 25.76 | 34.8 | 41.78 | 0.99 | 2.11 | 2.67 | 4.75 | 7.32 | 7.96
SGDet |  | 2 |  | 24.54 | 31.77 | 36.11 | 26.05 | 35.64 | 42.39 | 1.07 | 2.18 | 3.37 | 5.57 | 7.52 | 8.8
|  | 6 |  | 24.68 | 31.87 | 36.18 | 26.23 | 35.87 | 42.46 | 1.22 | 2.38 | 3.42 | 5.69 | 7.81 | 9.25
|  | 1 |  | 38.62 | 42.54 | 43.66 | 45.01 | 52.1 | 58.78 | 2.67 | 4.31 | 4.89 | 8.21 | 9.98 | 10.32
SGCls |  | 2 |  | 39.37 | 43.42 | 44.51 | 45.25 | 54.51 | 59.17 | 3.32 | 5.37 | 6.48 | 9.01 | 11.14 | 11.89
|  | 6 |  | 41.72 | 45.69 | 46.74 | 47.96 | 57.42 | 61.92 | 4.12 | 6.72 | 8.06 | 10.41 | 12.77 | 13.61
|  | 1 |  | 58.03 | 64.8 | 66.89 | 66.23 | 81.06 | 87.89 | 11.06 | 17.39 | 19.45 | 12.55 | 16.21 | 17.51
PredCls |  | 2 |  | 58.45 | 64.98 | 67.03 | 66.89 | 81.66 | 88.34 | 11.9 | 18.11 | 21.34 | 12.91 | 16.75 | 18.92
|  | 6 |  | 58.71 | 65.25 | 67.1 | 67.27 | 82.05 | 89.29 | 12.06 | 18.22 | 21.49 | 14.36 | 17.88 | 19.44

[Model Performance for different Transformer Heads.]Various R@K performance
for the different numbers of Transformer Heads in BGT-Net using VG dataset.

|  | Bi-GRU |  | R @ 20 | R @ 50 | R @ 100 | nG R @ 20 | nG R @ 50 | nG R @ 100 | zs R @ 20 | zs Recall @ 50 | zs R @ 100 | mR @ 20 | mR @ 50 | m R @ 100
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
|  | 1 |  | 25.54 | 32.87 | 37.3 | 27.24 | 36.91 | 43.72 | 4.8 | 7.37 | 8.78 | 10.41 | 12.77 | 13.61
SGDet |  | 2 |  | 24.54 | 31.77 | 36.11 | 26.05 | 35.64 | 42.39 | 1.07 | 2.18 | 3.37 | 9.91 | 12.28 | 13.12
|  | 6 |  | 23.93 | 31.01 | 35.37 | 25.47 | 35.02 | 41.63 | 1.12 | 2.11 | 3.1 | 5.49 | 7.53 | 8.86
|  | 1 |  | 41.69 | 45.96 | 47.06 | 47.83 | 57.67 | 62.29 | 2.67 | 4.31 | 4.89 | 8.21 | 9.98 | 10.32
SGCls |  | 2 |  | 41.72 | 45.69 | 46.74 | 47.96 | 57.42 | 61.92 | 4.12 | 6.72 | 8.06 | 9.01 | 11.14 | 11.89
|  | 6 |  | 41.08 | 45.57 | 46.23 | 46.98 | 57.12 | 61.3 | 4.02 | 6.56 | 7.79 | 8.54 | 11.81 | 13.01
|  | 1 |  | 59.21 | 65.68 | 67.45 | 67.69 | 82.42 | 89.45 | 12.23 | 18.31 | 21.51 | 14.7 | 18.46 | 20.08
PredCls |  | 2 |  | 58.71 | 65.25 | 67.1 | 67.27 | 82.05 | 89.29 | 12.06 | 18.22 | 21.49 | 14.36 | 17.88 | 19.44
|  | 6 |  | 58.22 | 65.45 | 66.74 | 66.91 | 81.87 | 88.69 | 11.83 | 18.07 | 21.1 | 14.22 | 17.59 | 19.21

[Model Performance for different Numbers of Bidirectional GRU Layers.]Various
R@K performance comparison in relation to the number of BiGRU layers present
in network when trained on VG dataset.

Figure 3: Qualitative results showing scene graphs generated by the BGT-Net.
For both examples, (a) shows the scene graph generated in the SGDet protocol,
and (b) the one generated in SGCls. The green arrow denotes that the detection
object or relationship corresponding to the ground-truth. Orange arrows denote
the detections that are not available in ground-truth but do represent the
image properly. Red marks errors that are used for undetected relationships or
wrongly detected objects.

Qualitative Results. In Figure 3, Left: shows the qualitative results. In
SGCls, the bounding boxes are given and the model has to predict the object
class and the relationships. In SGDet, no information is given. In SGDet up to
160 objects in an image can be detected but to keep the illustrations clean
not every object detection is shown. It detected relationships present in the
ground truth along with the additional feasible relationships. Figure 3 Top:
in SGCls the predicted scene graph fully corresponds to the ground truth scene
graph for this image. There is no additional relationship predicted between
other objects. Looking at the scene graph for SGDet, the difference between
these two protocols can be seen very well. Also, the performance of the model
is really good in this case. Additionally to the ground truth objects, the
object ”motorcycle” and ”person” are detected. These two detections are
correct and feasible. While the only ground truth relation (woman - wearing -
shirt) is still being detected, three other relationships that are totally
feasible are detected (woman - on - motorcycle), (person - on - motorcycle)
and (wheel - on - motorcycle). The performance of the BGT-Net on this image is
outstanding. No problems or specialties in the SGDet can be found.

In Figure 3 Right: In SGDet, the model even fails to give the correct
relationship (car - on - track). But, it correctly detects the whole train,
which was not specified in the ground truth and the correct relationship
(train - on - track). It is special in this case and it might also be in a lot
of other images that the model detects many objects that were not shown in the
ground truth. It also shows a lot of relationships between these additionally
shown objects. But, most likely with a higher amount of detected objects in an
image, these triplets, that are not in the ground truth, leads the model to
miss some of the relationships that would also be found in the ground truth.

##  5 Conclusion

We proposed a novel method BGT-Net to address the main challenges in SGG. BGT-
Net solves the problems by 1) using the object-object communication by
employing Bi-directional GRUs; 2) using transformer encoder with scaled-dot-
product attention for predicting object classes after they have received
feature information from other objects; 3) getting edge feature from second
transformer encoder; 4) Utilising Frequency Softening and Bias Adaptation for
dealing the with bias in the SGG. We validated the effectiveness of the
proposed BGT-Net using extensive experiments and conducting elaborative
ablation studies using three open-source datasets.

## References

  * [1] Jose M Alvarez, Theo Gevers, Yann LeCun, and Antonio M Lopez.  Road scene segmentation from a single image.  In European Conference on Computer Vision, pages 376–389. Springer, 2012.
  * [2] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton.  Layer normalization, 2016.
  * [3] Léon Bottou.  Stochastic gradient descent tricks.  In Neural networks: Tricks of the trade, pages 421–436. Springer, 2012.
  * [4] Long Chen, Hanwang Zhang, Jun Xiao, Xiangnan He, Shiliang Pu, and Shih-Fu Chang.  Counterfactual critic multi-agent training for scene graph generation.  In Proceedings of the IEEE International Conference on Computer Vision, pages 4613–4623, 2019.
  * [5] Tianshui Chen, Weihao Yu, Riquan Chen, and Liang Lin.  Knowledge-embedded routing network for scene graph generation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6163–6171, 2019.
  * [6] Ciarán O Conaire, Noel E O’Connor, and Alan F Smeaton.  An improved spatiogram similarity measure for robust object localisation.  In 2007 IEEE International Conference on Acoustics, Speech and Signal Processing-ICASSP’07, volume 1, pages I–1069. IEEE, 2007.
  * [7] Martin C Cooper.  The tractability of segmentation and scene analysis.  International Journal of Computer Vision, 30(1):27–42, 1998.
  * [8] Shalini Ghosh, Giedrius Burachas, Arijit Ray, and Avi Ziskind.  Generating natural language explanations for visual question answering using scene graphs and visual attention.  arXiv preprint arXiv:1902.05715, 2019.
  * [9] Song Han, Jeff Pool, John Tran, and William Dally.  Learning both weights and connections for efficient neural network.  In Advances in neural information processing systems, pages 1135–1143, 2015.
  * [10] Roei Herzig, Moshiko Raboh, Gal Chechik, Jonathan Berant, and Amir Globerson.  Mapping images to scene graphs with permutation-invariant structured prediction.  In Advances in Neural Information Processing Systems, pages 7211–7221, 2018.
  * [11] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural computation, 9:1735–80, 12 1997.
  * [12] Justin Johnson, Ranjay Krishna, Michael Stark, Li-Jia Li, David Shamma, Michael Bernstein, and Li Fei-Fei.  Image retrieval using scene graphs.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3668–3678, 2015.
  * [13] Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A. Shamma, Michael S. Bernstein, and Fei-Fei Li.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  CoRR, abs/1602.07332, 2016.
  * [14] Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper R. R. Uijlings, Ivan Krasin, Jordi Pont-Tuset, Shahab Kamali, Stefan Popov, Matteo Malloci, Tom Duerig, and Vittorio Ferrari.  The open images dataset V4: unified image classification, object detection, and visual relationship detection at scale.  CoRR, abs/1811.00982, 2018.
  * [15] Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper R. R. Uijlings, Ivan Krasin, Jordi Pont-Tuset, Shahab Kamali, Stefan Popov, Matteo Malloci, Tom Duerig, and Vittorio Ferrari.  The open images dataset V4: unified image classification, object detection, and visual relationship detection at scale.  CoRR, abs/1811.00982, 2018.
  * [16] Xiangyang Li and Shuqiang Jiang.  Know more say less: Image captioning based on scene graphs.  IEEE Transactions on Multimedia, 21(8):2117–2130, 2019.
  * [17] Yikang Li, Wanli Ouyang, Bolei Zhou, Jianping Shi, Chao Zhang, and Xiaogang Wang.  Factorizable net: an efficient subgraph-based framework for scene graph generation.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 335–351, 2018.
  * [18] Yikang Li, Wanli Ouyang, Bolei Zhou, Kun Wang, and Xiaogang Wang.  Scene graph generation from objects, phrases and region captions.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1261–1270, 2017.
  * [19] Xiaodan Liang, Lisa Lee, and Eric P. Xing.  Deep variation-structured reinforcement learning for visual relationship and attribute detection.  CoRR, abs/1703.03054, 2017.
  * [20] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In European conference on computer vision, pages 740–755. Springer, 2014.
  * [21] Xin Lin, Changxing Ding, Jinquan Zeng, and Dacheng Tao.  Gps-net: Graph property sensing network for scene graph generation, 2020\.
  * [22] Cewu Lu, Ranjay Krishna, Michael Bernstein, and Li Fei-Fei.  Visual relationship detection with language priors.  In European Conference on Computer Vision, 2016.
  * [23] Constantine Papageorgiou and Tomaso Poggio.  A trainable system for object detection.  International journal of computer vision, 38(1):15–33, 2000.
  * [24] Mengshi Qi, Weijian Li, Zhengyuan Yang, Yunhong Wang, and Jiebo Luo.  Attentive relational networks for mapping images to scene graphs.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3957–3966, 2019.
  * [25] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In Advances in neural information processing systems, pages 91–99, 2015.
  * [26] Brigit Schroeder and Subarna Tripathi.  Structured query-based image retrieval using scene graphs.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 178–179, 2020.
  * [27] Sebastian Schuster, Ranjay Krishna, Angel Chang, Li Fei-Fei, and Christopher D Manning.  Generating semantically precise scene graphs from textual descriptions for improved image retrieval.  In Proceedings of the fourth workshop on vision and language, pages 70–80, 2015.
  * [28] Jiaxin Shi, Hanwang Zhang, and Juanzi Li.  Explainable and explicit visual reasoning over scene graphs.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 8376–8384, 2019.
  * [29] Josephine Sullivan, Andrew Blake, Michael Isard, and John MacCormick.  Bayesian object localisation in images.  International Journal of Computer Vision, 44(2):111–135, 2001.
  * [30] Christian Szegedy, Alexander Toshev, and Dumitru Erhan.  Deep neural networks for object detection.  In Advances in neural information processing systems, pages 2553–2561, 2013.
  * [31] Kaihua Tang.  A scene graph generation codebase in pytorch, 2020.  https://github.com/KaihuaTang/Scene-Graph-Benchmark.pytorch.
  * [32] Kaihua Tang, Yulei Niu, Jianqiang Huang, Jiaxin Shi, and Hanwang Zhang.  Unbiased scene graph generation from biased training.  arXiv preprint arXiv:2002.11949, 2020.
  * [33] Kaihua Tang, Hanwang Zhang, Baoyuan Wu, Wenhan Luo, and Wei Liu.  Learning to compose dynamic tree structures for visual contexts.  CoRR, abs/1812.01880, 2018.
  * [34] Damien Teney, Lingqiao Liu, and Anton van Den Hengel.  Graph-structured representations for visual question answering.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1–9, 2017.
  * [35] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  CoRR, abs/1706.03762, 2017.
  * [36] Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He.  Aggregated residual transformations for deep neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1492–1500, 2017.
  * [37] Danfei Xu, Yuke Zhu, Christopher B. Choy, and Li Fei-Fei.  Scene graph generation by iterative message passing.  CoRR, abs/1701.02426, 2017.
  * [38] Shaotian Yan, Chen Shen, Zhongming Jin, Jianqiang Huang, Rongxin Jiang, Yaowu Chen, and Xian-Sheng Hua.  Pcpl: Predicate-correlation perception learning for unbiased scene graph generation.  In Proceedings of the 28th ACM International Conference on Multimedia, pages 265–273, 2020.
  * [39] Jianwei Yang, Jiasen Lu, Stefan Lee, Dhruv Batra, and Devi Parikh.  Graph r-cnn for scene graph generation.  In Proceedings of the European conference on computer vision (ECCV), pages 670–685, 2018.
  * [40] Xu Yang, Kaihua Tang, Hanwang Zhang, and Jianfei Cai.  Auto-encoding scene graphs for image captioning.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 10685–10694, 2019.
  * [41] Guojun Yin, Lu Sheng, Bin Liu, Nenghai Yu, Xiaogang Wang, Jing Shao, and Chen Change Loy.  Zoom-net: Mining deep feature interactions for visual relationship recognition.  CoRR, abs/1807.04979, 2018.
  * [42] Ruichi Yu, Ang Li, Vlad I. Morariu, and Larry S. Davis.  Visual relationship detection with internal and external linguistic knowledge distillation.  CoRR, abs/1707.09423, 2017.
  * [43] Cong Yuren, Hanno Ackermann, Wentong Liao, Michael Ying Yang, and Bodo Rosenhahn.  Nodis: Neural ordinary differential scene understanding.  arXiv preprint arXiv:2001.04735, 2020.
  * [44] Alireza Zareian, Svebor Karaman, and Shih-Fu Chang.  Bridging knowledge graphs to generate scene graphs.  In Proceedings of the European conference on computer vision (ECCV), August 2020.
  * [45] Rowan Zellers, Mark Yatskar, Sam Thomson, and Yejin Choi.  Neural motifs: Scene graph parsing with global context.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5831–5840, 2018.
  * [46] Yibing Zhan, Jun Yu, Ting Yu, and Dacheng Tao.  On exploring undetermined relationships for visual relationship detection.  CoRR, abs/1905.01595, 2019.
  * [47] Cheng Zhang, Wei-Lun Chao, and Dong Xuan.  An empirical study on leveraging scene graphs for visual question answering, 2019.
  * [48] Hanwang Zhang, Zawlin Kyaw, Shih-Fu Chang, and Tat-Seng Chua.  Visual translation embedding network for visual relation detection.  CoRR, abs/1702.08319, 2017.
  * [49] Ji Zhang, Kevin J. Shih, Ahmed Elgammal, Andrew Tao, and Bryan Catanzaro.  Graphical contrastive losses for scene graph generation.  CoRR, abs/1903.02728, 2019.
  * [50] Ji Zhang, Kevin J Shih, Ahmed Elgammal, Andrew Tao, and Bryan Catanzaro.  Graphical contrastive losses for scene graph parsing.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 11535–11543, 2019.
  * [51] Yan Zhang, Jonathon S. Hare, and Adam Prügel-Bennett.  Learning to count objects in natural images for visual question answering.  CoRR, abs/1802.05766, 2018.