11institutetext:  Centro Ricerche Enrico Fermi, Via Panisperna 89 A, 00184
Rome, Italy 22institutetext: Istituto Nazionale Fisica Nucleare, Unità Roma 1,
Dipartimento di Fisica, Università di Roma “Sapienza”, Piazzale Aldo Moro 2,
00185 Roma, Italia 33institutetext: Laboratoire de Physique Nucláire et de
Hautes Énergies, UPMC IN2P3 CNRS UMR 7585, Sorbonne Université, 4, place
Jussieu, 75252 Paris Cedex 05, France

# Gravitational collapse from cold uniform asymmetric initial conditions

Francesco Sylos Labini and Michael Joyce 112233

(Received / Accepted)

Using controlled numerical N-body experiments, we show how, in the collapse
dynamics of an initially cold and uniform distribution of particles with a
generic asymmetric shape, finite $N$ fluctuations and perturbations induced by
the anisotropic gravitational field compete to determine the physical
properties of the asymptotic quasi-stationary state. When finite $N$
fluctuations dominate the dynamics, the particle energy distribution changes
greatly and the final density profile decays outside its core as $r^{-4}$ with
an $N$-dependent amplitude. On the other hand, in the limit where the
anisotropic perturbations dominate, the collapse is softer and the density
profile shows a decay as $r^{-3}$, as is typical of halos in cosmological
simulations. However, even in this limit, convergence with $N$ of the
macroscopic properties of the virialized system, such as the particle energy
distributions, the bound mass, and the density profile, is very slow and not
clearly established, including for our largest simulations (with $N\sim
10^{6}$). Our results illustrate the challenges of accurately simulating the
first collapsing structures in standard-type cosmological models.

###### Key Words.:

methods: numerical; galaxies: elliptical and lenticular, cD; galaxies:
formation

##  1 Introduction

The evolution under Newtonian self-gravity of an isolated distribution of
particles that start from initial conditions (ICs) in which the particles are
initially at rest and are randomly distributed in a sphere with uniform mean
density has been studied by numerous authors since the earliest numerical
simulations of such systems. Numerous variants have also been explored,
notably with initial velocity dispersion (using radially dependent density
profiles) and for spheroidal boundaries (Henon, 1964, 1973; van Albada, 1982;
Merritt & Aguilar, 1985; Aarseth et al., 1988; Aguilar & Merritt, 1990; Theis
& Spurzem, 1999; Boily et al., 2002; Roy & Perez, 2004; Boily & Athanassoula,
2006; Barnes et al., 2009; Joyce et al., 2009; Sylos Labini, 2012, 2013;
Worrakitpoonpon, 2015; Sylos Labini et al., 2015; Benhaiem & Sylos Labini,
2015; Benhaiem et al., 2016; Benhaiem & Sylos Labini, 2017; Spera & Capuzzo-
Dolcetta, 2017; Sylos Labini et al., 2020; Worrakitpoonpon, 2020). Such
systems provide a natural and simple setting to explore the rich complexity of
the nonlinear phase of gravitational dynamics relevant to many different
problems in astrophysics and cosmology. Though in the context of structure
formation in cosmology structures are never strictly isolated, these simple
models are nonetheless highly relevant. Indeed, the so-called spherical
collapse model, which analytically describes a smooth spherical over-density
in an expanding universe, is a paradigmatic model that guides understanding of
the nonlinear cosmological structure formation (see, e.g., Peebles 1980).
Despite its simplicity, and indeed its breakdown in a singularity at a finite
time, it describes qualitatively well what is actually observed in $N$-body
simulations of standard cosmological models: Over-dense regions expand more
slowly on average until they “break off” from the expansion and undergo a
strong collapse, starting from conditions that are effectively those of an
isolated, initially cold configuration. The specific design of any set of
numerical experiments in either the astrophysical or cosmological context
varies depending on the motivation of the authors and the physical issues they
focus on. We report here a study of a very simple variant of this class of
models. It is designed to explore how deviations from spherical symmetry
compete with the density fluctuations intrinsic to the discrete particle
distribution in regulating the singularity in the limit of a cold uniform
collapse (i.e., of the spherical collapse model in cosmology). The
understanding of the dynamics that can result from the very simple class of
ICs we consider – with just one parameter in addition to the particle number –
is of broad interest. More specifically, as we explain, it gives insight into
the challenges of accurately simulating the first nonlinear structures in many
cosmological models.

One particular question that can be addressed in a controlled manner with
these systems is the extent to which the evolution of discrete $N$-body
systems approximate, and converge to, in an appropriate $N\rightarrow\infty$
limit, the continuum limit given by the Vlasov-Poisson system (or
collisionless Boltzmann equations) for a smooth phase-space density. Indeed,
for the relevant physical problems, the particles of the $N$-body simulations
are usually thought of not as physical particles but simply as a tool for
representing the physical phase-space density, the evolution of which is
described by these equations. In the cosmological context the physical
particles are usually microscopic dark matter particles, while the particles
of simulations are unphysical “macro-particles” with astrophysical-scale
masses. An important question is then to what extent the results obtained from
these simulations are dependent on $N$ and what the associated limit on their
accuracy is. In more physical terms the question can be formulated as to what
extent the fluctuations associated with the particle discretization play a
role in the dynamics in its nonlinear phase. This question of $N$-body
discretization effects in cosmology can be straightforwardly addressed using
isolated systems because, as noted, we can consider, in light of the exact
spherical collapse model, that nonlinear structure formation can be
approximated by the collapse of quasi-isolated initially cold clumps.

In current models of cosmological structure formation, there is always a
minimal scale in the initial spectrum of fluctuations, the physical size of
which varies greatly depending on whether the supposed dark matter is “cold”
or “warm” (see, e.g., Wang & White 2007, Kuhlen et al. 2012, and references
therein). The first clumps therefore form starting from fluctuations at this
scale and are initially highly uniform at smaller scales. In the discretized
version of the problem (i.e., as represented in an $N$-body simulation) there
are, in addition, the fluctuations associated with the particle
discretization. The question of discreteness effects thus appears to be well
and simply posed in terms of the $N$ dependence of the evolution of an
isolated, initially cold, uniform clump. However, things are not so simple
because, in spherical symmetry, the $N\rightarrow\infty$ limit has the finite
time collapse singularity of the spherical collapse model. Spheroidal clumps
are a simple alternative, but they are also characterized by a singularity in
the same limit due to their residual rotational symmetry (Lin et al., 1965;
Worrakitpoonpon, 2020).

In a recent article, Sylos Labini & Capuzzo-Dolcetta (2020) considered ICs
that are spherical but with a simple family of density fluctuations within the
sphere of which the amplitude is regulated by a single additional parameter.
This reproduces ICs that are expected to model clumps forming from preexisting
structures at smaller scales, as at later times in typical cosmological
models. Here we instead consider modeling the clumps as being uniform at small
scales but having an irregular shape. This is a good schematic representation
of the first collapsing structures in a standard cosmological model.

The cold uniform spherical case, with a single free parameter, $N$, has been
studied at length in, for example, Aarseth et al. (1988) and Joyce et al.
(2009). In this case the singularity in the $N\rightarrow\infty$ is thus
regularized by the density fluctuations associated with discreteness alone.
More specifically, it is found, for Poisson-distributed particles, that the
minimal system radius approximately scales as $r_{min}\sim N^{-1/3}$. This
behavior can be derived from the growth of the density perturbations in the
bulk, which evolve until the associated peculiar kinetic energy becomes on the
order of the gravitational potential energy. Thus, the smaller $N$ is (i.e.,
the larger the initial density fluctuations), the softer the collapse is: As a
consequence of the larger resulting particle peculiar velocities, the collapse
phase stops earlier. In addition, the properties of the virialized quasi-
stationary state (QSS; e.g., the amplitude of the density profile and the
particle energy distribution) that is attained rapidly after the collapse are
$N$ dependent. In the model considered by Sylos Labini & Capuzzo-Dolcetta
(2020), the particles are instead distributed in $N_{c}$ spherical sub-clumps
of radius $r$; $r$ is smaller than the radius of the system itself, $R$, which
allows the amplitude of initial fluctuations to be regulated. As their
amplitude is increased, the very violent collapse of the simple model is
progressively “softened”: While in the former case there is a large change in
the particle energy distribution driven by a strong variation in the system’s
mean field, in the latter there is a marginal change in the system’s phase-
space distribution. The properties of the QSS reached thus depend strongly on
whether the collapse was violent or soft: In particular, the final density
profile decreases as $\sim r^{-4}$ when it is very violent, while it decreases
as $\sim r^{-3}$ in the soft limit. In the model we explore here, we again see
these same limiting behaviors emerge.

The term “violent relaxation” that we employ here was introduced by Lynden-
Bell (1967) to describe the collective mean-field relaxation process that
drives a self-gravitating system prepared in an out-of-equilibrium IC to form
a QSS. Lynden-Bell also proposed a theory to calculate the resulting QSS using
a statistical approach based on the collisionless Boltzmann equation. The
predictions of this theory have, however, been shown by the results of
numerical experiments (see, e.g., Arad & Lynden-Bell 2005) to not account well
for the relaxed QSS of such systems. We note that, for the ICs we study here,
the theory of Lynden-Bell cannot be adequate for a very simple reason: It
assumes the mass and energy of the QSS to be that of the initial state, while
these systems are always characterized – because of the violence of the
relaxation – by the ejection of a very significant fraction of their initial
mass and energy. We note that a very different semi-analytic model of violent
relaxation that does admit the presence of ejected mass has been proposed by
Mangalam et al. (1999). It is based on the physical picture of strong and
short-lived interactions between the system’s potential fluctuations and
particle orbits and, interestingly, also accounts for an associated QSS
density profile decreasing as $\sim r^{-4}$.

In this work we introduce and use numerical experiments to study a simple toy
model in which the perturbations of shape and the finite $N$ fluctuations can
be varied independently by tuning two parameters: a “shape parameter,” $p$,
which controls the degree of the initial spherical symmetry breaking, and the
particle number, $N$, which controls the amplitude of discrete density
fluctuations. These latter fluctuations are chosen from two different types:
uncorrelated Poisson fluctuations and those in a highly uniform “glassy”
distribution This model thus allows us to study, in a controlled way, the
competition between finite $N$ fluctuations and anisotropic perturbations. We
show that the evolution, and thus the properties of the QSS formed after the
collapse, crucially depends on which of these two competing effects dominates
the dynamics. In addition, we show that even when shape perturbations are
predominant, the convergence as a function of $N$ is very slow.

The paper is organized as follows. In Sect. 2 we describe the generation of
ICs and give some details about the numerical simulations. In the following
section we present our results. Finally, in Sect. 4 we draw our conclusions,
in particular for what our study tells us about resolution issues related to
discretization in cosmological $N$-body simulations.

##  2 Initial conditions

The ICs for our numerical experiments consisted of particles distributed with
uniform mean density in a connected region with an asymmetric shape
characterized by a single dimensionless parameter, $p$. These ICs were
generated as follows. The region was defined by a sphere of radius $R_{0}$
(hereafter “the inner sphere”), to which a spherical shell divided into eight
identical contiguous sectors of solid angle $\Omega=\pi/2$ was added. The
outer radius of each shell was set equal to $R_{i}=R_{0}\times(1+p_{i}),$
where $p_{i}$ is a random number with uniform distribution in the range
$[0,p]$ and the index $i=1,...,8$ runs over the sectors (see Fig. 1). The
particle configurations were then generated inside this region in one of two
different ways. For the “Poisson” configurations, we first randomly
distributed (without correlation of position) $N_{0}$ particles in the inner
sphere such that their mean density in this region is

$n_{0}=\frac{3N_{0}}{4\pi R_{0}^{3}}\;.$ (1)

We then distributed in the $i^{th}$ sector ( for $i=1,...,8$) the number of
particles that gives the same mean number density in each sector, namely,

$N_{i}=\frac{\pi R_{i}^{3}n_{0}}{8}\;.$ (2)

The total number of particles is thus $N=\sum_{i}^{8}N_{i}$. For the “glass”
configurations we extracted a region with the appropriate shape and size from
a large glass, a very uniform configuration obtained by running an N-body
simulation with a repulsive $r^{-2}$ force in periodic boundary conditions
until an equilibrium configuration is obtained, following a procedure often
employed in the generation of “pre-initial” conditions that represent the
unperturbed universe for cosmological simulations (Springel, 2005).

The limit $p=0$ corresponds to spherical symmetry. For $p\neq 0$, all
rotational symmetry is broken, and the larger $p$ is the more asymmetrical the
distribution. We considered here only the range $0\leq p\leq 1$. For $p>1$,
the evolution typically leads to fragmentation into multiple substructures,
which then, on a longer timescale, merge together. In this case, the dynamics
is thus qualitatively different. In this work we explored up to $p=1,$ for
which the dynamics can be described as a single or a “monolithic” collapse.

We ran simulations for a “grid” of ICs in our two-parameter space: for each of
$p=0,0.2,0.4,0.6,0.8,$ and $1$. The particles were of equal mass and we took
$N_{0}$ in the range $10^{3}-10^{6}$. To designate results in the simulations,
we used, for given specified $p$, a label consisting of a letter and an
integer. The latter is simply $\log_{10}N_{0}$, while the letter is either $S$
or $G$: $S$ means that the particles are in a Poisson configuration, and $G$
means that they are in a glass configuration. For example, $S4$ indicates that
the particles were initially Poisson distributed and that $N_{0}=10^{4}$. We
note that we thus label our simulations by $N_{0}$, the number of particles
inside the inner sphere, and not by the (slightly different) total number of
particles. This is appropriate because it allows us to compare simulations at
a fixed (or varying) particle density.

Figure 1: Schematic representation (2D projection) of our ICs for $p=1$.

Hereafter, distances are given in units of the initial radius of the inner
spherical system, $R_{0}$, and time is given in units of

$\tau_{0}=\sqrt{\frac{\pi^{2}R_{0}^{3}}{8GM_{0}}}\;,$ (3)

where $M_{0}$ is the mass of the inner spherical system and $\tau_{0}$ is the
characteristic time corresponding to the time at which the maximal contraction
of the system is attained. Virialization occurs a short time later, and in all
our simulations the system is well relaxed to a QSS before $t=2$ in these
units.

We report results for the density profile, $\rho(r),$ normalized by the total
mass. Further, we calculate

$\Delta(t)=\frac{1}{\langle
e(0)\rangle}\sqrt{\frac{\sum_{i=1}^{N}(e_{i}(t)-e_{i}(0))^{2}}{N}},$ (4)

where $e_{i}(t)$ is the energy of particle $i$ at time $t$ and

$\langle e(0)\rangle=\left(\frac{\sum_{i=1}^{N}e_{i}(0)}{N}\right)\;$ (5)

is its initial average value. The $\Delta(t)$ thus gives a simple measure of
the total change of the particle energies relative to the initial time in
units of the initial average energy per particle. When $\Delta(t)>1$, the
energy change is large and the collapse is violent, while when $\Delta(t)<1$
the energy change is small and the collapse is soft (Sylos Labini & Capuzzo-
Dolcetta, 2020).

Numerical simulations were run using the code Gadget (Springel, 2005). We
refer to Sylos Labini & Capuzzo-Dolcetta (2020) for further discussion about
the details of the numerical integration: Here we just specify that the
gravitational softening length was taken to be $1/100$ of the minimal radius,
$r_{min}$, reached by the system during the collapse. We performed numerous
tests with smaller and larger softening to check the convergence, finding that
results do not depend significantly on $\varepsilon$ as long as
$\varepsilon<r_{min}$. Total energy is conserved to a precision better than a
few percent; we tested that this is enough to have good convergence of the
macroscopic quantities measured here.

##  3 Results

###  3.1 Particle energy distributions

The temporal evolution of the particle energy distribution, $P(e,t)$, is a key
statistical quantity that characterizes the collapse dynamics (Sylos Labini &
Capuzzo-Dolcetta, 2020). Figure 2 shows its behavior for the different $p$
simulated for Poisson-distributed particles and $N_{0}=10^{5}$ at $t=0$ and
$t=9$ (when, as noted above, the system is very well virialized).

The trend, which can be seen in Fig. 2, is very clear: In all cases the
virialized energy distribution is very different to, and in particular very
much broader than, the initial one. However, this difference is greatest at
$p=0$ and becomes progressively smaller as $p$ increases. This is readily
explained by considering that $p$ controls the violence of the collapse: When
$p=0$, the collapse is close to homologous and the singularity of the
$N\rightarrow\infty$ limit is regulated only by the density fluctuations
seeded by the initial discretization. On the other hand, for $p\neq 0$ the
collapse is no longer singular in this same limit because tidal effects
induced by spatial anisotropies change the collapse times of shells that are
initially located at different distances from the center and/or at different
angular locations. The larger $p$ is, the more important the effect of these
anisotropies in modifying the collapse is and the smaller the change of
$P(e,t=9)$ with respect to $P(e,t=0)$. One can also see in the plots that
there is a small additional peak around $e=0$ that appears at $p=0.2$ and
becomes ever more apparent as $p$ increases. Further, its position (in energy)
clearly coincides more closely with the center of the initial distribution as
$p$ increases. This feature is evidently a residual of the IC and gives a
further quantitative measure of how violent the collapse is.

Figure 2: Energy distribution at $t=0$ (black line) and at $t=9$ (red line)
for the series S5; each panel shows a different value of the initial breaking
of spherical symmetry, $p$.

Next we considered how the $N$ dependence of the energy distributions is
obtained from the different ICs. Figure 3 shows $P(e,t)$, again at $t=9$, for
$p=0$ (top panel) and $p=1$ (bottom panel) for the different indicated values
of $N_{0}$ and initial Poisson configurations. We observe that while for $p=0$
the energy distribution $P(e,t=9)$ depends strongly on $N$, for $p=1$ there
are only very much smaller residual finite $N$ effects. Nevertheless, in the
tails of the distribution for $p=1$ – for both the most bound and most
energetic unbound particles – there appears to still be some systematic
dependence on $N$, with the tails becoming marginally more spread for larger
values of $N$. The convergence to an $N$-independent result thus seems to be
slow, with visible evolution with $N$ still at $N_{0}=10^{6}$.

Figure 3: Energy distribution at $t=9$ for $p=0$ (upper panel) and $p=1$
(bottom panel) for the four realizations with a different number of Poisson-
distributed particles, i.e., $N_{0}=10^{3},10^{4},10^{5}$, and $10^{6}$.

###  3.2 Mean energy exchange

The upper panel of Fig. 4 shows the behavior of $\Delta(t=9)$, as defined
above in Eq. 4, as a function of $p$ for initial Poisson configurations with
different $N_{0}$. As for $P(e,t)$, the choice of the time $t=9$ is somewhat
arbitrary as this quantity is essentially time independent provided $t\geq 2$.
We observe that in all cases $\Delta>1$, which implies that the collapse is
always quite violent in the sense that the variation in the particle energy
distribution is large. In a collapse from cold ICs, $\Delta<1$ can be obtained
in the presence of initial fluctuations that are sufficiently large such that
clustering proceeds in a bottom-up manner (Sylos Labini & Capuzzo-Dolcetta,
2020). We observe that $\Delta(t=9)$ decreases monotonically as a function of
$p$ at a fixed value of $N_{0}$. The behavior simply reflects, once again,
that the collapse “softens” progressively as $p$ increases. On the other hand,
$\Delta(t=9)$ also increases with $N_{0}$ at any fixed $p$, which indicates
that the collapse is, in all cases, becoming more violent as $N$ increases.
There is, however, a clear weakening of this $N$ dependence as $p$ increases
and an apparent onset of good convergence for $p=1$ with the two runs with the
largest particle numbers close together. Thus, it appears that at $p=1$ we
attain, at $N_{0}\sim 10^{5}$, the limit where the collapse is regulated by
the shape fluctuations alone.

Figure 4:  Quantifying the violence of the collapse. Upper panel: Energy
exchange $\Delta$ (see Eq. 4) at time $t=9$ as a function of $p$ (with
different $N_{0}$). Bottom panel: Same but the plotted quantity $f_{p}$ is the
fraction of ejected particles, i.e., particles that have positive energy after
the collapse

.

###  3.3 Ejected mass

The bottom panel of Fig. 4 shows the fraction of ejected particles, $f_{p}$,
as a function of the initial asymmetry, $p$, for simulations with
$N_{0}=10^{5}$. As described in detail in Joyce et al. (2009), Sylos Labini
(2012), and Sylos Labini & Capuzzo-Dolcetta (2020), these are essentially all
particles whose energy becomes positive in a very short interval around the
time of maximal contraction and remains positive thereafter. We note the very
large values (approximately one-third of the mass) attained for the spherical
IC (see Joyce et al. (2009) for further detail) characterized by the most
violent collapse. The behaviors seen are very similar to those in the previous
plot, except that there appears to be clearer evidence for convergence with
$N$ at the larger values of $p$.

###  3.4 Density profiles

Figure 5 shows normalized density profiles, $\rho(r)$, at $t=9$ for the
indicated simulations. We focus on the very well resolved regions, where $r$
is significantly larger than the gravitational softening. We have multiplied
by $r^{4}$ to facilitate a clearer comparison of the different cases: For the
case of $p=0$, the outer profile is, as described in previous studies (Joyce
et al., 2009; Sylos Labini, 2012; Sylos Labini & Capuzzo-Dolcetta, 2020),
characterized by a radial decay with $\rho(r)\sim r^{-4}$. Both the amplitude
of the (flat, approximately constant $\rho$) core at smaller scales and the
amplitude of this tail are strongly $N$ dependent. As discussed in Sylos
Labini & Capuzzo-Dolcetta (2020), the exponent $-4$ corresponds to the
limiting situation in which the system is in a Jeans’s equilibrium state; in
this state the mass is concentrated in the core, so that the system
gravitational potential decays as $\Phi\sim r^{-1}$ and bound particles in the
outskirts move on purely radial orbits (corresponding to an anisotropic
velocity parameter $\beta\rightarrow 1$). This configuration is reached only
when the collapse is so violent that the potential well of the core becomes
very deep and, correspondingly, as seen above, a very significant fraction of
mass and energy is ejected, leaving the bound particles with an energy much
lower than that of the initial state. If the collapse is much softer, however,
the mass distribution is less compact and the gravitational potential decays
more slowly than $\sim r^{-1}$. The particles have less strongly radial orbits
as these are a result of the energy ejection around maximal contraction.
Figure 5 shows behaviors that are also very consistent with these findings for
our ICs. As $p$ increases we see a very apparent transition from an $r^{-4}$
to an $r^{-3}$ outer tail in the profile. Further, in line with the previous
plots we have analyzed, we see that there appears to be good evidence for
convergence with $N$ as one approaches $p=1$. At $p=0.6$, however, there is
still a strong $N$ dependence in both the shape and amplitude of the profile,
and it remains unclear what the functional dependence may be as
$N\rightarrow\infty$.

Figure 5: Density profile multiplied by $r^{4}$ for $p=0$ (left panel),
$p=0.6$ (middle panel), and $p=1$ (right panel) obtained from Poisson
configurations with different values of $N_{0}$. The softening length is
$\varepsilon=3\times 10^{-4}$. The profile for $p=0$ is $N$ dependent and
decays as $r^{-4}$; for $p=1$ it converges to an $N$-independent $\approx
r^{-3}$ behavior but is still affected by finite $N$ effects at small scales.
A reference line corresponding to $\rho(r)\sim r^{-3}$ is reported in the
middle and left panels.

Figure 6 shows the measured density profile (multiplied by $r^{4}$) for glass
ICs with $N_{0}=5\times 10^{4}$ for different values of $p$. Its behavior is
qualitatively the same as what we saw above, with the same apparent transition
in the functional form as a function of $p$. We also find very similar
behavior for the other quantities we have analyzed, for both the dependence on
$p$ and on $N_{0}$. There is, however, a quantitative difference between the
Poisson and the glass ICs: At given $p$, the glass ICs with a given $N_{0}$
closely resemble the Poisson ICs at a slightly larger $N_{0}$. For instance, a
glass IC with $N_{0}\approx 10^{4}$ results in a profile that agrees well with
that of a Poissonian IC with $N_{0}\approx 10^{5}$. This result is completely
in line with what was anticipated: At a given $N_{0}$, the very uniform glass
configuration has density fluctuations that are more suppressed compared to
those of a Poisson configuration. Nevertheless, the quantitative effect,
though measurable, is relatively small and our conclusions for what concerns
convergence are not changed by our study of these ICs.

Figure 6: Density profiles multiplied by $r^{4}$ for simulations with glass
ICs and $N_{0}=5\times 10^{4}$ for different values of $p$. Two reference
lines with exponents $-4$ and $-3$ are also plotted. The softening length is
$\varepsilon=3\times 10^{-4}$.

##  4 Conclusions

We have numerically studied the collapse and virialization of isolated and
initially cold configurations of particles with uniform mean density and an
irregular asymmetric shape specified by a parameter, $p$, that characterizes
the deviation from sphericity. Such ICs can be considered as a simple
schematic representation of the first collapsing regions in cosmological
models with a lower cutoff in the spectrum of initial fluctuations. In this
context, the number of particles, $N$, is an unphysical parameter that arises
from the $N$-body discretization, and the model allows us to explore
convergence to results that do not depend on it. More generally, the model is
a simple toy model for studying how the collapse at finite $N$ in the
spherical limit may be modified by deviations from spherical symmetry.

Studying configurations with $p$ in a range where the collapse remains
monolithic (i.e., well characterized as a single collapse around a center) and
$N$ in the range $10^{3}$ to $10^{6}$, we have been able to see an apparent
transition in the qualitative nature of the collapse and the properties of the
virialized QSS that result from it. This is most evidently shown by the outer
density profile that changes from a power-law decay with an $r^{-4}$ behavior
in the cold spherical limit to a decay with $r^{-3}$ when the rotational
symmetry is broken sufficiently strongly. There are likewise differences that
reflect such a transition in the several other various macroscopic quantities
we have considered to characterize both the dynamics during the collapse and
the final relaxed QSS. The $p$ and $N$ dependence of all these quantities
leads to a very coherent interpretation in terms of a competition between the
density fluctuations associated with the deviations from spherical symmetry
and those associated with the discrete particle distribution. As $p$
increases, the $N$ dependence progressively weakens, and at the largest $p$
there is reasonable evidence for convergence to $N$-independent results.
Nevertheless, residual $N$ dependences are still clearly detectable in some
quantities – in the inner parts of the density profile and in the tails of the
particle energy distribution – even for the very largest $N$. In the case of
an initially spherical cloud, the transition between a density power-law decay
with an $r^{-4}$ behavior to a decay with $r^{-3}$ is regulated by density
fluctuations (Sylos Labini & Capuzzo-Dolcetta, 2020).

In relation to cosmological structure formation, our results qualitatively
illustrate two important points. Firstly, they show that a very simple
breaking of spherical symmetry in a cold collapse appears to be sufficient to
lead to the emergence of an $r^{-3}$ tail in the virialized state. Such a tail
(in the density profiles of halos, i.e., quasi-virialized clumps) is seen very
generically in cosmological simulations and has been proposed as a “universal”
that is independent of ICs (see, e.g., Navarro et al. 1996). Numerous studies
of cold collapse with much more complex ICs than ours have supported such
universality (see, e.g., Navarro et al., 2004; Wang et al., 2020), but its
origin has remained elusive. Our simple ICs provide a very simplified model
for studying this fundamental issue: The nature of the outer profiles of cold
dark matter halos is related to both the breaking of spherical symmetry in a
cold collapse and the effect of the density fluctuations.

Secondly, our results indicate that the resolution (i.e., particle density)
needed to resolve the continuum limit of the first cold collapses predicted in
many models of cosmological structure formation may be extremely difficult to
reach. Indeed, we have seen that even for quite asymmetric ICs (e.g.,
corresponding to $p=0.6$ in our model) we do not see an approach to
convergence of basic macroscopic quantities, even for $N=10^{6}$ particles.
This is many times larger than the typical number of particles inside the
first collapsing structures in simulations of warm dark matter models that
attempt to model such collapses (Wang & White, 2007; Kuhlen et al., 2012). On
the other hand, we have seen that the number of particles, $N$, needed to
reach convergence is manifestly strongly dependent on the parameter $p$, and
thus we cannot draw quantitative conclusions for the resolution needed in such
cosmological simulations. In future work we plan to address this issue by
trying to more precisely model how the breaking of spherical symmetry at the
onset of collapse can be characterized and determined in such cosmological
models.

###### Acknowledgements.

We are grateful to Lehman Garrison for having provided us the glassy
configuration. We thank Roberto Capuzzo Dolcetta, Andrea Gabrielli and
Pierfrancesco Di Cintio for useful discussions. Finally, we also thank the
referee for his useful comments.

## References

  * Aarseth et al. (1988) Aarseth, S., Lin, D., & Papaloizou, J. 1988, Astrophys. J., 324, 288
  * Aguilar & Merritt (1990) Aguilar, L. & Merritt, D. 1990, Astrophys. J., 354, 73
  * Arad & Lynden-Bell (2005) Arad, I. & Lynden-Bell, D. 2005, Mon. Not. R. Astron. Soc., 361, 385
  * Barnes et al. (2009) Barnes, E. I., Lanzel, P. A., & Williams, L. L. R. 2009, Astrophys. J., 704, 372
  * Benhaiem et al. (2016) Benhaiem, D., Joyce, M., Sylos Labini, F., & Worrakitpoonpon, T. 2016, Astron.Astrophys., 585, A139
  * Benhaiem & Sylos Labini (2015) Benhaiem, D. & Sylos Labini, F. 2015, Mon.Not.R.Astron.Soc., 448, 2634
  * Benhaiem & Sylos Labini (2017) Benhaiem, D. & Sylos Labini, F. 2017, Astron.Astrophys., 598, A95
  * Boily et al. (2002) Boily, C., Athanassoula, E., & Kroupa, P. 2002, Mon. Not. R. Astr. Soc., 332, 971
  * Boily & Athanassoula (2006) Boily, C. M. & Athanassoula, E. 2006, Mon. Not. R. Astr. Soc., 369, 608
  * Henon (1964) Henon, M. 1964, Ann. Astrophys., 27, 1
  * Henon (1973) Henon, M. 1973, Ann. Astrophys., 24, 229
  * Joyce et al. (2009) Joyce, M., Marcos, B., & Sylos Labini, F. 2009, Mon. Not. R. Astron. Soc., 397, 775
  * Kuhlen et al. (2012) Kuhlen, M., Vogelsberger, M., & Angulo, R. 2012, Physics of the Dark Universe, 1, 50, next Decade in Dark Matter and Dark Energy
  * Lin et al. (1965) Lin, C. C., Mestel, L., & Shu, F. H. 1965, Astrophys.J., 142, 1431
  * Lynden-Bell (1967) Lynden-Bell, D. 1967, Mon. Not. R. Astr. Soc., 136, 101
  * Mangalam et al. (1999) Mangalam, A., Nityananda, R., & Sridhar, S. 1999, Astrophys.J., 524, 623
  * Merritt & Aguilar (1985) Merritt, D. & Aguilar, L. A. 1985, Mon. Not. R. Ast. Soc, 217, 787
  * Navarro et al. (1996) Navarro, J. F., Eke, V. R., & Frenk, C. S. 1996, Mon.Not.R.Astron.Soc., 283, L72
  * Navarro et al. (2004) Navarro, J. F., Hayashi, E., Power, C., et al. 2004, Monthly Notices of the Royal Astronomical Society, 349, 1039
  * Peebles (1980) Peebles, P. J. E. 1980, The Large-Scale Structure of the Universe (Princeton University Press)
  * Roy & Perez (2004) Roy, F. & Perez, J. 2004, Mon. Not. R. Astr. Soc., 348, 62
  * Spera & Capuzzo-Dolcetta (2017) Spera, M. & Capuzzo-Dolcetta, R. 2017, Astrophys. Space Sci., 362, 233
  * Springel (2005) Springel, V. 2005, Mon.Not.R.Astron.Soc., 364, 1105
  * Sylos Labini (2012) Sylos Labini, F. 2012, Mon. Not. R. Astron. Soc., 423, 1610
  * Sylos Labini (2013) Sylos Labini, F. 2013, Mon. Not. R. Astron. Soc., 429, 679
  * Sylos Labini et al. (2015) Sylos Labini, F., Benhaiem, D., & Joyce, M. 2015, Mon.Not.R.Astron.Soc., 449, 4458
  * Sylos Labini & Capuzzo-Dolcetta (2020) Sylos Labini, F. & Capuzzo-Dolcetta, R. 2020, Astron.Astrophys., 643, A118
  * Sylos Labini et al. (2020) Sylos Labini, F., Pinto, L. D., & Capuzzo-Dolcetta, R. 2020, Phys.Rev.E, 102, 042108
  * Theis & Spurzem (1999) Theis, C. & Spurzem, R. 1999, Astron. Astrophys., 341, 361
  * van Albada (1982) van Albada, T. 1982, Mon. Not. R. Astr. Soc., 201, 939
  * Wang et al. (2020) Wang, J., Bose, S., Frenk, C. S., et al. 2020, Nature, 585, 39
  * Wang & White (2007) Wang, J. & White, S. D. M. 2007, Mon.Not.R.Acad.Soc., 380, 93
  * Worrakitpoonpon (2015) Worrakitpoonpon, T. 2015, Mon. Not. R. Astr. Soc., 466, 1335
  * Worrakitpoonpon (2020) Worrakitpoonpon, T. 2020, Mon.Not.R.Acad.Soc., 498, 310


# Advancing Visual Grounding with Scene Knowledge: Benchmark and Method

Zhihong Chen1,2,311footnotemark: 1 Ruifei Zhang211footnotemark: 1 Yibing
Song4,5 Xiang Wan3 Guanbin Li222footnotemark: 2
1The Chinese University of Hong Kong, Shenzhen 2Sun Yat-sen University
3Shenzhen Research Institute of Big Data 4Tencent AI Lab 5AI3 Institute, Fudan
University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Visual grounding (VG) aims to establish fine-grained alignment between vision
and language. Ideally, it can be a testbed for vision-and-language models to
evaluate their understanding of the images and texts and their reasoning
abilities over their joint space. However, most existing VG datasets are
constructed using simple description texts, which do not require sufficient
reasoning over the images and texts. This has been demonstrated in a recent
study [27], where a simple LSTM-based text encoder without pretraining can
achieve state-of-the-art performance on mainstream VG datasets. Therefore, in
this paper, we propose a novel benchmark of Scene Knowledge-guided Visual
Grounding (SK-VG), where the image content and referring expressions are not
sufficient to ground the target objects, forcing the models to have a
reasoning ability on the long-form scene knowledge. To perform this task, we
propose two approaches to accept the triple-type input, where the former
embeds knowledge into the image features before the image-query interaction;
the latter leverages linguistic structure to assist in computing the image-
text matching. We conduct extensive experiments to analyze the above methods
and show that the proposed approaches achieve promising results but still
leave room for improvement, including performance and interpretability. The
dataset and code are available at https://github.com/zhjohnchan/SK-VG.

**footnotetext: Equal contribution††footnotetext: Corresponding author

##  1 Introduction

Figure 1: An example from the proposed SK-VG dataset for scene knowledge-
guided visual grounding. The task requires a model to reason over the (image,
scene knowledge, query) triple to locate the target object referred to by the
query.

Visual grounding (VG), aiming to locate an object referred to by a description
phrase/text in an image, has emerged as a prominent attractive research
direction. It can be applied to various tasks (e.g., visual question answering
[51, 13, 38, 4] and vision-and-language navigation [1, 35, 11]) and also be
treated as a proxy to evaluate machines for open-ended scene recognition.
Typically, VG requires models to reason over vision and language and build
connections through single-modal understanding and cross-modal matching. Yet,
current VG benchmarks (e.g., RefCOCO [47], RefCOCO+ [47], RefCOCOg [29],
ReferItGame [17], and CLEVR-Ref+ [23]) can not serve as a good test bed to
evaluate the reasoning ability since they only focus on simple vision-language
alignment. In addition to the simple nature of constructed referring
expressions, this can be reflected in the recent state-of-the-art study [27],
where they showed that VG models are less affected by language modeling
through extensive empirical analyses.

Figure 2: Illustrations of four categories of grounding tasks, including
categories, phrases, linguistic expressions, and linguistic expression+scene
knowledge. The height of the input green and blue rectangles denotes its
relative information.

In this paper, we believe that the intrinsic difficulty of VG lies in the
difference between perceptual representations of images and cognitive
representations of texts. Specifically, visual features are obtained through
perceptual learning, which only maps visual appearances in images to semantic
concepts. However, open-ended queries might require VG models to understand
the whole scene knowledge before performing reasoning to locate the target
object. As shown in Figure 1, the perceptual features can encode the
information about “a wine glass”, but it would struggle to locate “Jake’s wine
glass” without the scene knowledge about “who is Jake?”. This is a challenging
task owing to two facts: (i) From the dataset perspective, there are no
relevant benchmarks for the VG researchers to evaluate their models; (ii) From
the model/algorithm perspective, it is not easy to design models to perform
reasoning among images, scene knowledge, and open-ended querying texts.

Therefore, we propose to break this limitation of current VG research and
construct a new benchmark requiring VG to perform reasoning over Scene
Knowledge (i.e., text-based stories). The benchmark named SK-VG contains
$\sim$40,000 referring expressions and 8,000 scene stories from 4,000 images,
where each image contains 2 scene stories with 5 referring expressions for
each story. Moreover, to evaluate the difficulty levels of queries, we curate
the test set by splitting the samples into easy/medium/hard categories to
provide a detailed evaluation of the vision-language models. Under this new
setting, we develop a one-stage approach (i.e., Knowledge-embedded Vision-
Language Interaction (KeViLI)) and a two-stage approach (i.e., Linguistic-
enhanced Vision-Language Matching (LeViLM)). In KeViLI, the scene knowledge is
firstly embedded into the image features, and then the interaction between the
image and the query is performed; In LeViLM, the image features and the text
features are first extracted, and then the matching between the (image)
regions and the (text) entities are computed, assisted by the structured
linguistic information. Through extensive experiments, we show that the
proposed approaches can achieve the best performance but still leave room for
improvement, especially in the hard split. It challenges the models from three
perspectives: First, it is an open-ended grounding task; Second, the scene
stories are long narratives consisting of multiple sentences; Third, it might
require the multi-hop reasoning ability of the models. In summary, the
contributions of this paper are three-fold:

  * •

We introduce a challenging task that requires VG models to reason over (image,
scene knowledge, query) triples and build a new dataset named SK-VG on top of
real images through manual annotations.

  * •

We propose two approaches to enhance the reasoning in SK-VG, i.e., one one-
stage approach KeViLI and one two-stage approach LeViLM.

  * •

Extensive experiments demonstrate the effectiveness of the proposed
approaches. Further analyses and discussions could be a good starting point
for future study in the vision-and-language field.

##  2 Background

###  2.1 Taxonomy of Visual Grounding Datasets

In the past few years, a variety of datasets have been proposed for visual
grounding. We propose a taxonomy of existing (generalized) VG datasets along
with the proposed dataset based on types of queries, as shown in Figure 2.

The datasets of the first type use fixed categories as queries.111Generally,
it is called object detection. We generalize it to visual grounding to
summarize and classify existing grounding datasets better. Grounding
categories in images are a fundamental task in computer vision and has
attracted much attention. One of the most representative examples is the MS-
COCO dataset [20], which contains 80 categories. Besides, PASCAL VOC 2007
[12], Visual Genome [18], and Object365 [34] are also popular datasets of this
type.

The Flickr30K Entities dataset222Although there are some studies locating the
entities using the context provided by the dataset, we refer in particular to
those using only the phrases as in [27]. [30] belongs to the second type,
where the queries are short phrases. Similar to the first type, an image might
contain multiple objects referred to by a phrase following the one-to-many
mappings. The most distinct characteristic of this type from the first type is
that it is an open-vocabulary grounding problem instead of using fixed
categories. Most recently, researchers constructed relevant datasets of this
type, i.e., PhraseCut [39] and LVIS [14], with a larger scale.

The third type aims at localizing a specific object in the image based on an
expression in the form of natural language. In the narrow sense, the term
visual grounding refers to this type of dataset in previous studies. Various
benchmark datasets (e.g., RefCOCO [47], RefCOCO+ [47], RefCOCOg [29], and
CLEVR-Ref+ [23]) have been constructed to test the ability to refer expression
comprehension of existing vision-language models. In general, expressions in
these datasets are written according to the visual appearance and spatial
location of an object, where the visual appearance includes visual categories,
color, and other visual attributes, and the spatial location describes the
absolute or relative location. Different from the aforementioned two types, an
expression in this type of dataset points to a unique object in the image
following the one-to-one mapping.

Our proposed SK-VG is the first dataset of the fourth type, where for each
image, we provide human-written scene knowledge to describe its content. By
doing so, the VG models need to have a good understanding of the scene stories
and then locate the queried object in the image according to both querying
expressions and scene stories. Although there exists a dataset [36]
introducing knowledge to the visual grounding model, it only focuses on the
commonsense knowledge, which interprets the concept in the referring
expressions, e.g., the interpretation of the target object ‘banana’. There are
also some datasets on grounding complex/compositional visual description,
e.g., the human-centric HumanCog dataset [45] and the Cops-Ref dataset [5].
HumanCog requires the model to understand human-centric commonsense (e.g., the
mental aspect), and Cops-Ref proposed a difficult task to require a model to
identify an object described by a compositional referring expression from a
curated set of images. We can still classify them into the first three
categories since the knowledge is more about referring expressions, while the
knowledge in our dataset is a comprehensive description of the scene.

Figure 3: Statistics of the proposed SK-VG dataset: (i) the length
distribution of the knowledge description; (ii) the referred objects of high-
frequency; (iii) the size distribution of referred objects.

###  2.2 Visual Grounding Models

Existing methods can be categorized into two classes: (i) two-stage methods
[46, 37, 21, 2, 25] and (ii) one-stage methods [44, 28, 42, 50, 8,
15].333Grounding categories is a very hot topic, where there are many research
works [32, 24, 31, 22]. Yet we mainly discuss existing studies of grounding
phrases/expressions, which are more related to this work. The former generates
region proposals first and then exploits the language expression to select the
best-matching region; The latter directly predicts the bounding boxes through
vision-and-language interaction to avoid the computation-intensive object
proposal generation and region feature extraction in the two-stage paradigm.
Among these methods, some work [37, 40, 41, 6, 10] perform explicit reasoning
by modeling the attributes of objects and the relations between objects to
improve interpretability. However, limited by the simplicity of existing
datasets, they can not take full advantage of their algorithms and do not
model complicated semantic relations in images and texts. Besides,
pretraining-based methods [16, 19, 49, 43] have been applied to VG to improve
the open-vocabulary grounding ability.

##  3 Dataset Construction

In this section, we present the SK-VG dataset. Compared to existing VG tasks,
the key difference is that each image is paired with scene knowledge to
describe its content. We detail the image collection, the annotation process,
the dataset statistics, and splits in the following subsections.

###  3.1 Image Collection

To facilitate and ease the writing of a text story, we identify three
significant aspects a qualified image should fulfill:

  * •

Humans are the main body of a story. A satisfying image is better full of
multiple characters with interactions to create complex and dramatic stories.

  * •

Objects are also essential and necessary to complement the details of a story.
The number and category of objects also impact our SK-VG task, making it more
challenging and interesting.

  * •

Scenes are the third factors we can not ignore since the scenes determine the
background and starting point of stories. Complex and real scenes (e.g.,
theaters, classrooms, and parks) can inspire diverse stories.

Based on the above consideration, we select the existing Visual Commonsense
Reasoning dataset [48], which is designed for the visual question answering
task and contains more than 110,000 movie scene images. Thanks to the movie
attribute of these images, they are more likely to meet our requirements and
are suitable for our task. Therefore, through careful manual filtering and
selection, 4,000 images serve as the ingredients of our SK-VG dataset.

###  3.2 Image Annotation

To facilitate the annotation process, we develop software. For each image, the
annotation mainly includes two phases: (i) Annotators are asked to create two
different story descriptions based on a given image; (ii) Given each story,
the annotators are asked to write five referring expressions related to the
given image and story and annotate the corresponding object bounding boxes as
the ground truth. The required rules for each step are detailed as follows:
(i) Knowledge Annotation serves as a foundation stone of our annotation,
determining the scope and quality of query sentences. A satisfying story
should be related but beyond the image content. Specifically, the story should
cover the person who occurred in one image with accurate visual descriptions,
thus providing significant clues and evidence to match the image object and
knowledge entity. Besides, the story is required to contain more context
beyond the image, such as background, character relationship, mental state,
and emotion, so as to promote the design of more challenging and flexible
query expression. (ii) Query Expression Annotation plays an essential role in
our task and ought to obey the following criteria:

  * •

Knowledge Relevance: The main insight of our SK-VG task is to advance the
traditional VG task by introducing extra scene knowledge descriptions. Based
on this consideration and prospect, the first principle is that query
sentences must be highly relevant to knowledge instead of directly visually
distinguishable. Taking Figure 1 as an example, “The black glasses” is not
qualified since it does not involve knowledge information.

  * •

Uniqueness: To give a unique bounding box of the referred object, the query
should be clear and unambiguous. For instance, queries like “The person
holding a wine glass” or “Jake’s friend” are not satisfied in Figure 1 since
they involve several objects in the image.

  * •

Diversity: For one thing, the referring objects should be diverse; For
another, the lexical expression of the query sentence is also required to be
diversified. For example, the general terms (e.g., “person”) could be replaced
by other specific alternatives (e.g., “colleague”).

###  3.3 Dataset Statistics

To further dive into the proposed SK-VG dataset, we demonstrate its
characteristics from three aspects:

  * •

Length of scene knowledge: As shown in Figure 3(i), the word-based length of
most stories ranges from 50 to 70. This puts high demands on models to capture
long-range dependency to understand text content.

  * •

Categories of referred objects: As an open-world task, referred objects of our
dataset are not limited to a fixed number of categories. Figure 3(ii) exhibits
100 referred object classes with the highest frequency. Benefiting from the
diverse stories and scenes, we introduce extensive referred targets with
various expressions, increasing the difficulty of recognition and
localization.

  * •

Size of referred objects: We report the size of referred objects in Figure
3(iii), which indicates that the objects in our dataset fall into a wide range
of sizes. Further, we define small, medium, and large concepts according to
the area of the objects, following the boundary of $64\times 64$ and
$128\times 128$. We can observe that large objects dominate our dataset, while
small and medium instances hold a small proportion.

Figure 4: Illustration of the proposed approaches: (i) the one-stage
algorithm, where the knowledge is embedded into the image features before the
image-query interaction; (ii) the two-stage algorithm, where the image
features and text features are firstly extracted, and then the structured
linguistic information is leveraged to assist in computing the region-entity
similarities.

###  3.4 Dataset Splits

We randomly sample 60% of images and their annotations as the training set.
For the remaining (image, scene knowledge, query) triples, we sample parts of
them for annotating their difficulty levels and use them as the test set while
the remaining triples are used as the validation set.444The images in the
training set have no overlap with those in the validation and test sets. We
follow the following rule to annotate the difficulty level. The core principle
is that more knowledge-related but less visual-distinguishable expressions
deserve a higher difficulty level: (i) Easy: The referring expression contains
obvious appearance, object relationship, or other visual clues; (ii) Medium:
The expression only mentions weak visual information; (iii) Hard: The answer
is required to be entirely derived from the scene knowledge without visual
bias. We show examples of different difficulty levels in §4.5.

##  4 Algorithmic Analysis

###  4.1 Algorithm 1: KeViLI

To perform SK-VG, we introduce a one-stage algorithm: Knowledge-embedded
Vision-Language Interaction (KeViLI). Given an image $I$ and its corresponding
scene knowledge $K$, the goal is to locate the object referred to by a
querying text $T$ by predicting the coordinates of its corresponding bounding
box directly.

In detail, given $I$, we use an image encoder to encode $I$ to the image patch
features $H_{I}$; given $K$ and $T$, we use a language encoder to encode them
to the knowledge features $H_{K}$ and the text subword features $H_{T}$,
respectively. Afterward, we embed the scene knowledge into the image features
before the image-query interaction. As an intuitive illustration, in Figure 1,
the visual features of “person” in the image is not only about the concept
“person” but also about the specific refer “Jake” after embedding knowledge,
which can assist in grounding “Jake’s wine glasses”. The embedding procedure
is implemented using a cross-attention Transformer, which is stacked by self-
attention, cross-attention, and feed-forward sub-layers. The attention
mechanism is applied in the self-attention and cross-attention sub-layers and
is defined as

$\text{ATTN}(\boldsymbol{Q},\boldsymbol{K},\boldsymbol{V})=\operatorname{Softmax}\left(\boldsymbol{Q}\boldsymbol{K}^{\top}/\sqrt{D_{k}}\right)\cdot\boldsymbol{V},$
(1)

In the self-attention sub-layer, the patch features interact with each other
through $H^{I}=\text{ATTN}(H^{I},H^{I},H^{I})$; In the cross-attention sub-
layer, the knowledge is embedded into the image features by
$H^{I}=\text{ATTN}(H^{I},H^{K},H^{K})$.555We overload the notations here for
simplicity. Subsequently, $H_{I}$ and $H_{T}$ are input to a Transformer with
a learnable regression token [REG] to perform the image-query interaction. The
output of [REG] is input to a two-layer multilayer perceptron (MLP) to produce
to predict the coordinates directly without region proposals. The model is
trained to minimize the generalized IoU loss [33] (GIoU loss):

$L=L_{\text{smooth\\_l1}}(b,\hat{b})+L_{\text{giou}}(b,\hat{b}),$ (2)

where $b$ and $\hat{b}$ refer to the ground-truth and prediction boxes,
respectively and $L_{\text{smooth\\_l1}}(\cdot)$ and $L_{\text{giou}}(\cdot)$
are the smooth L1 loss and GIoU loss, respectively.

###  4.2 Algorithm 2: LeViLM

We further introduce a two-stage algorithm: Linguistic-enhanced Vision-
Language Matching (LeViLM). In LeViLM, we follow GLIP [19] to initialize the
backbone model, which had been trained from large-scale datasets to detect
objects of open-vocabulary classes.

In detail, the grounding process is disentangled into two stages, i.e., region
proposal and scoring, where the former aims to find all the objects in the
image, and the latter aims to score the proposal regions. In the region
proposal stage, given the scene knowledge $K$ and the query $T$, we construct
a manual prompt text $P$: “Query: $T$. Knowledge: $K$.”. Then we use a
language encoder to encode $P$ into the prompt features $H_{P}$ and an image
encoder to encode $I$ to the image features $H_{I}$. Afterward, we perform the
image-text fusion using a stack of $L$ layers. In each layer, there is one
self-attention layer for text encoding and one Dynamic Head layer [7] for
image encoding, and two cross-attention layers for cross-modal fusion. The
text encoding and image encoding process can be formulated as
$H_{P}=\operatorname{ATTN}(H_{P},H_{P},H_{P})$ and
$H_{I}=\operatorname{DynamicHead}(H_{I})$, respectively. The cross-modal
information fusion process can be formalized as
$H_{P}=\operatorname{ATTN}(H_{P},H_{I},H_{I}),H_{I}=\operatorname{ATTN}(H_{I},H_{P},H_{P})$,
where the cross-attention mechanism is applied to exchange the image and text
information. Subsequently, a region proposal layer is applied to $H_{I}$ to
obtain the region features. For simplicity, we denote the after-fusion image
(region) features and text (subword) features as $Z_{I}\in\mathrm{R}^{N\times
d}$ and $Z_{P}\in\mathrm{R}^{M\times d}$, where $N$ refers to the number of
proposed regions and $M$ represents the number of subwords. In the region
scoring stage, we extract structured linguistic information from the query $T$
and the scene knowledge $K$. Specifically, given $T$, we perform syntactic
dependency parsing to obtain its dependency tree and apply a set of rules to
extract the subject of $T$, which we denote as the head entity $E_{h}$.
Besides, we also build the connection between $T$ and $K$ through coreference
resolution to find all mentions $E_{m}$ in $K$ refer to the same underlying
entity $E_{h}$. Therefore, during the training procedure, we have the bounding
box annotation for $E_{h}$ and its co-referred $E_{m}$ since $E_{h}$ and
$E_{m}$ share the same object. Then we can take the representations of $E_{h}$
and $E_{m}$ from $Z_{P}$, denoted as $Z_{E}\in\mathrm{R}^{(E+1)\times d}$,
where $E$ represents the number of co-referred mentions. Afterward, we can
compute the alignment scores between the image regions and the entities in the
prompt:

$Score=Z_{I}Z_{e}^{\top},$ (3)

where $Score\in\mathrm{R}^{N\times(E+1)}$. Finally, the model is trained to
minimize the following loss:

$L=L_{xe}(Score,Target),$ (4)

where $L_{xe}$ is the cross entropy loss and
$Target\in\mathbb{R}^{N\times(E+1)}$, where each element indicates if a region
and an entity are matched or not.

###  4.3 Implementation Details

For KeViLI, the input image is resized to $640\times 640$, and the max (token-
based) length for $T$ and $K$ are set to 32 and 256, respectively. During
training, the model is optimized with the batch size set to 64 using AdamW
optimizer [26], where the initial learning rate of the vision encoder and
language encoder is set to $10^{-5}$ and the learning rate of the remaining
parameters are set to $10^{-4}$. Similar to [8], the vision encoder is
initialized from the DETR model [3], and the language encoder is initialized
with the BERT model [9]. The model is trained for 90 epochs with a learning
rate dropped by a factor of 10 after the 60th epoch. For LeViLM, we initialize
the backbone model from [19]. We train the model with the batch size set to
32. Similarly, the learning rate is set to $10^{-5}$ for the text encoder and
$10^{-4}$ for the remaining parameters. During training, the learning rate is
decayed at 67% and 89% of the total training steps.

To evaluate LeViLM on the SK-VG dataset, we testify different experimental
settings:

  * •

Data: Query-only (Q), Query-knowledge (Q+K), and Query-knowledge-linguistic-
structure (Q+K+S);

  * •

Training: (i) Zero-shot (ZS): We directly evaluated the pre-trained model
without finetuning; (ii) Linear-probing (LP): We fixed the backbone model;
(iii) Finetuning (FT): We tuned all the parameters of the model.

  * •

Evaluation666Since the LeViLM model might predict multiple bounding boxes, we
adapt different evaluation strategies for analysis.: (i) Selecting the
prediction with the highest score (H), (ii) Randomly picking the prediction
whose score is over 0.5 (R), (iii) Selecting the ground-truth one if its score
is larger than 0.5 (U).777The U strategy is adopted to analyze the reasoning
error of the model.

For the evaluation metric, we adopt Intersection-over-Union (IoU), which
measures the overlap degree between the prediction and the ground truth.
Following previous studies [47, 29, 8], we use<EMAIL_ADDRESS>as the prediction
accuracy.

###  4.4 Experimental Results and Analyses

Method | [46] | [21] | [25] | [44] | [42] | KeViLI | LeViLM
---|---|---|---|---|---|---|---
Acc | 25.28 | 25.24 | 26.08 | 16.3 | 36.68 | 30.01 | 72.57

Table 1: Comparisons of our approaches with existing studies.

|  |  |  |  | Difficulty-level | Area-level
---|---|---|---|---|---|---
Method | Text | Criteria | ID | Overall Acc | Accde | Accdm | Accdh | Accas | Accam | Accal
| Q | - | 1 | 28.71 | 32.53 | 25.23 | 25.70 | 0.80 | 14.44 | 34.02
KeViLI | Q + K | - | 2 | 30.01 | 33.75 | 26.55 | 27.14 | 1.20 | 12.85 | 35.94
|  | H | 3 | 29.75 | 49.97 | 18.23 | 6.71 | 24.20 | 33.33 | 29.64
|  | R | 4 | 29.77 | 48.28 | 18.88 | 9.01 | 23.20 | 33.12 | 29.79
| Q | U | 5 | 38.13 | 54.23 | 29.56 | 19.16 | 30.20 | 39.38 | 38.67
|  | H | 6 | 7.55 | 13.08 | 4.38 | 1.26 | 2.20 | 5.94 | 8.36
|  | R | 7 | 7.78 | 12.88 | 4.71 | 2.12 | 2.20 | 5.73 | 8.69
LeViLM (ZS) | Q + K | U | 8 | 8.79 | 13.34 | 6.02 | 3.79 | 2.20 | 6.05 | 9.93
|  | H | 9 | 44.97 | 72.03 | 31.86 | 11.70 | 50.60 | 57.54 | 42.13
|  | R | 10 | 44.82 | 66.91 | 32.68 | 19.16 | 48.20 | 56.48 | 42.36
| Q | U | 11 | 63.09 | 77.51 | 54.90 | 46.64 | 52.60 | 64.86 | 63.79
|  | H | 12 | 35.71 | 60.40 | 25.07 | 3.96 | 41.20 | 48.51 | 32.84
|  | R | 13 | 35.89 | 57.00 | 24.41 | 11.24 | 39.40 | 47.13 | 33.49
| Q + K | U | 14 | 47.71 | 64.40 | 41.43 | 25.30 | 43.20 | 55.52 | 46.72
|  | H | 15 | 37.25 | 62.09 | 26.98 | 4.88 | 42.20 | 49.47 | 34.54
|  | R | 16 | 36.91 | 58.03 | 25.83 | 11.82 | 40.20 | 46.92 | 34.76
LeViLM (LP) | Q + K + S | U | 17 | 50.47 | 66.61 | 44.77 | 28.40 | 44.40 | 56.69 | 49.92
|  | H | 18 | 57.18 | 80.35 | 46.80 | 27.83 | 65.00 | 66.77 | 54.67
|  | R | 19 | 57.29 | 80.15 | 46.63 | 28.74 | 65.00 | 65.39 | 55.06
| Q | U | 20 | 63.79 | 83.45 | 55.17 | 38.67 | 68.60 | 71.23 | 61.97
|  | H | 21 | 70.70 | 84.51 | 63.16 | 54.62 | 68.20 | 72.51 | 70.62
|  | R | 22 | 70.49 | 84.28 | 62.67 | 54.73 | 68.80 | 72.51 | 70.29
| Q + K | U | 23 | 74.95 | 86.49 | 68.20 | 61.96 | 71.00 | 76.11 | 75.12
|  | H | 24 | 72.57 | 84.08 | 65.52 | 59.95 | 70.00 | 71.02 | 73.10
|  | R | 25 | 71.93 | 83.72 | 64.97 | 58.75 | 70.00 | 71.44 | 72.21
LeViLM (FT) | Q + K + S | U | 26 | 77.31 | 86.59 | 71.59 | 67.18 | 72.60 | 76.96 | 77.83

Table 2: The performance of two proposed approaches. In the text column, Q, K,
and S represent query, knowledge, and linguistic structure, respectively. In
the criteria column, H, R, and U represent the criteria to pick the detected
bounding boxes by adopting the boxes with the highest scores, the random
boxes, and the upper-bound scores that can be achieved, respectively. For the
metrics, the overall accuracy, the difficulty-level accuracy, and the area-
level accuracy are shown.

To analyze the performance of different baselines, we consider the following
questions and conduct analyses to answer them with the results reported in
Table 1 and 2.

Q1: Is SK-VG a hard task for traditional VG models? As shown in Table 1,
existing models did not achieve promising results An interesting finding is
that ReSC, which uses texts to recursively refine the text-conditional visual
features, achieved the best result ($\sim$36%) among these existing models,
which matches our intuition that it can better use long-form story
information.

Q2: Which one is better, KeViLI or LeViLM? It can be observed in Table 2 that
the performance of LeViLM (ID 3-26) is consistently better than KeViLI (ID
1-2), even without any finetuning (ID 3-4). We can explain this by the reason
that the task’s inherent difficulty is understanding open-ended stories,
queries, and their relations with the images. For KeViL, the one-stage
optimization to directly output bounding boxes of such open-ended target
objects could be difficult. Instead, for LeViLM, after dividing and conquering
the process (i.e., region proposing and scoring), it is easier to ensure each
stage works well, e.g., to guarantee its basic detection ability before
complex grounding using a pre-trained VG backbone.

Q3: Are linear-probing or finetuning necessary for LeViLM? We can investigate
the effects of linear probing and finetuning by comparing the results (ID 3-8,
ID 9-14, and ID 18-23). When adapting LeViLM on this dataset, the performance
follows this pattern: finetuning > linear-probing > zero-shot. The reason
behind this is that finetuning can guide the model to use the scene knowledge
in a better way.

Q4: Is the scene knowledge critical for accurate prediction? To answer this
question, we need to take the different evaluation strategies into account.
Specifically, in the ZS and LP setting, it can be observed that the knowledge
is harmful to the model performance by comparing ID 3-5 and ID 6-8 (or
comparing ID 9-11 and ID 12-17). This is due to two reasons: (i) The texts of
the pretraining datasets of LeViLM are relatively short, yet the length of
scene knowledge in our dataset is much longer than that; (ii) The majority of
the LeViLM pretraining datasets are about perception, i.e., detecting all the
objects in the images instead of reasoning over the images and texts.
Therefore, it is not enough to exploit the knowledge under the zero-shot and
linear-probing settings. On the contrary, the knowledge has a considerably
positive effect when full-finetuning LeViLM on the proposed dataset, which can
be explained by the fact that LeViLM learns to reason over the images,
knowledge, and querying texts after adaptation. Besides, bridging the scene
knowledge and the queries in an appropriate way (ID 24-25) can further promote
performance. The conclusion is that knowledge is critical for finetuning but
can not be exploited appropriately in the zero-shot and linear-probing
settings.

Figure 5: The illustration of samples from the proposed SK-VG dataset, where a
scene story and its four referring expressions are shown with the grounding
results from four baseline methods.

Q5: What is the advantage of exploiting the knowledge? For this question,
there are two interesting observations from the results. First, when using the
knowledge, the model can achieve a higher upper-bound result (comparing ID 20,
23, and 26), which means that the model can detect more objects in the images.
We can explain this phenomenon by one of the possible instances: the querying
text might contain different names of persons, and the model might not know
the name refers to a person, which can be inferred from the knowledge. Second,
with the knowledge, the model is able to perform more accurate reasoning,
which can be observed by comparing the reasoning errors (the results of $U-H$)
of Q and Q+K (or Q+K+S). This is because the knowledge can alleviate the
reasoning uncertainty when grounding the objects. The answer is that scene
knowledge can not only assist in detecting more objects but also reduce the
uncertainty of locating/reasoning the target objects.

Q6: What do the approaches still struggle to do? Before answering this
question, we can investigate the effects of the area of objects. As shown in
Table 2, it is not challenging for LeViLM to detect small objects. By
observing the difficulty-level accuracy, we can obtain the message that LeViLM
is not capable of performing complicated (multi-hop) reasoning over the scene
knowledge and producing accurate predictions. Besides, the prediction process
is black-box and can not be explainable, which can be further studied in the
future. The answer is that (i) The current baselines can only achieve strong
results on easy or medium tasks and are unable to perform well on the hard
task; (ii) The interpretability of the baselines is poor.

###  4.5 Case Study

To further investigate the effects of knowledge, we perform qualitative
analysis on four cases in the SK-VG dataset. Figure 5 shows the grounding
results of four baselines on four referring expressions. It is observed that
in the first case, all the baselines can ground the “cane” in the image even
without the knowledge since there is only one cane presented. In the second
case, the finetuned LeViLM can detect the target object even without
knowledge, while it can not detect the “Brandon’s servant” without knowledge
in the third case. In the last case, all the baselines can not ground the
referred object correctly, and the last three baselines all treat the “Spider-
Man” as the “enemy”. This shows that the baseline models can not perform
accurate reasoning in some complicated cases, demonstrating the challenges.

##  5 Concluding Remarks

The visual grounding field has emerged as a prominent attractive research
direction, where the models are required to reason over vision and language to
ground the target objects. Yet, the language part of the existing VG
benchmarks is only simple description texts, which can not evaluate the
reasoning capability of the models comprehensively. To take a step in this
direction, we propose a new benchmark dataset called SK-VG, which requires
models to reason over the (image, scene knowledge, query) triples to perform
accurate reasoning. We propose two approaches to perform this new task:
Knowledge-embedded Vision-Language Interaction and Linguistic-enhanced Vision-
Language Matching. Experimental results confirm the validity of the proposed
approaches but also show that there is still substantial room for improvement,
e.g., reasoning and interpretability.

## Acknowledgement

This work was supported in part by the Chinese Key-Area Research and
Development Program of Guangdong Province (2020B0101350001), in part by the
Guangdong Basic and Applied Basic Research Foundation (NO. 2020B1515020048),
in part by the National Natural Science Foundation of China (NO. 61976250), in
part by the Shenzhen Science and Technology Program (NO.
JCYJ20220530141211024, NO. JCYJ20220818103001002), in part by the Fundamental
Research Funds for the Central Universities under Grant 22lgqb25 and in part
by the Guangdong Provincial Key Laboratory of Big Data Computing, The Chinese
University of Hong Kong, Shenzhen. This work was also sponsored by Tencent CCF
Open Fund (NO. RBFR2022009).

## References

  * [1] Peter Anderson, Qi Wu, Damien Teney, Jake Bruce, Mark Johnson, Niko Sünderhauf, Ian Reid, Stephen Gould, and Anton Van Den Hengel.  Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3674–3683, 2018.
  * [2] Mohit Bajaj, Lanjun Wang, and Leonid Sigal.  G3raphground: Graph-based language grounding.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4281–4290, 2019.
  * [3] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In European conference on computer vision, pages 213–229. Springer, 2020.
  * [4] Zhenfang Chen, Jiayuan Mao, Jiajun Wu, Kwan-Yee Kenneth Wong, Joshua B Tenenbaum, and Chuang Gan.  Grounding physical concepts of objects and events through dynamic visual reasoning.  In ICLR, 2021.
  * [5] Zhenfang Chen, Peng Wang, Lin Ma, Kwan-Yee K Wong, and Qi Wu.  Cops-ref: A new dataset and task on compositional referring expression comprehension.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10086–10095, 2020.
  * [6] Zhenfang Chen, Kexin Yi, Yunzhu Li, Mingyu Ding, Antonio Torralba, Joshua B Tenenbaum, and Chuang Gan.  Comphy: Compositional physical reasoning of objects and events from videos.  In ICLR, 2022.
  * [7] Xiyang Dai, Yinpeng Chen, Bin Xiao, Dongdong Chen, Mengchen Liu, Lu Yuan, and Lei Zhang.  Dynamic head: Unifying object detection heads with attentions.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 7373–7382, 2021.
  * [8] Jiajun Deng, Zhengyuan Yang, Tianlang Chen, Wengang Zhou, and Houqiang Li.  Transvg: End-to-end visual grounding with transformers.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1769–1779, 2021.
  * [9] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171–4186, 2019.
  * [10] Mingyu Ding, Zhenfang Chen, Tao Du, Ping Luo, Josh Tenenbaum, and Chuang Gan.  Dynamic visual reasoning by learning differentiable physics models from video and language.  Advances In Neural Information Processing Systems, 34:887–899, 2021\.
  * [11] Mingyu Ding, Yan Xu, Zhenfang Chen, David Daniel Cox, Ping Luo, Joshua B. Tenenbaum, and Chuang Gan.  Embodied concept learner: Self-supervised learning of concepts and mapping through instruction following.  In 6th Annual Conference on Robot Learning, 2022.
  * [12] Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman.  The pascal visual object classes (voc) challenge.  International journal of computer vision, 88(2):303–338, 2010.
  * [13] Chuang Gan, Yandong Li, Haoxiang Li, Chen Sun, and Boqing Gong.  Vqs: Linking segmentations to questions and answers for supervised attention in vqa and question-focused semantic segmentation.  In Proceedings of the IEEE international conference on computer vision, pages 1811–1820, 2017.
  * [14] Agrim Gupta, Piotr Dollar, and Ross Girshick.  Lvis: A dataset for large vocabulary instance segmentation.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 5356–5364, 2019.
  * [15] Binbin Huang, Dongze Lian, Weixin Luo, and Shenghua Gao.  Look before you leap: Learning landmark features for one-stage visual grounding.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16888–16897, 2021.
  * [16] Aishwarya Kamath, Mannat Singh, Yann LeCun, Gabriel Synnaeve, Ishan Misra, and Nicolas Carion.  Mdetr-modulated detection for end-to-end multi-modal understanding.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1780–1790, 2021.
  * [17] Sahar Kazemzadeh, Vicente Ordonez, Mark Matten, and Tamara Berg.  Referitgame: Referring to objects in photographs of natural scenes.  In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 787–798, 2014.
  * [18] Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, et al.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  International journal of computer vision, 123(1):32–73, 2017.
  * [19] Liunian Harold Li, Pengchuan Zhang, Haotian Zhang, Jianwei Yang, Chunyuan Li, Yiwu Zhong, Lijuan Wang, Lu Yuan, Lei Zhang, Jenq-Neng Hwang, et al.  Grounded language-image pre-training.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10965–10975, 2022.
  * [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] Daqing Liu, Hanwang Zhang, Feng Wu, and Zheng-Jun Zha.  Learning to assemble neural module tree networks for visual grounding.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4673–4682, 2019.
  * [22] Li Liu, Wanli Ouyang, Xiaogang Wang, Paul Fieguth, Jie Chen, Xinwang Liu, and Matti Pietikäinen.  Deep learning for generic object detection: A survey.  International journal of computer vision, 128(2):261–318, 2020\.
  * [23] Runtao Liu, Chenxi Liu, Yutong Bai, and Alan L Yuille.  Clevr-ref+: Diagnosing visual reasoning with referring expressions.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4185–4194, 2019.
  * [24] Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott Reed, Cheng-Yang Fu, and Alexander C Berg.  Ssd: Single shot multibox detector.  In European conference on computer vision, pages 21–37. Springer, 2016.
  * [25] Xihui Liu, Zihao Wang, Jing Shao, Xiaogang Wang, and Hongsheng Li.  Improving referring expression grounding with cross-modal attention-guided erasing.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 1950–1959, 2019.
  * [26] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In International Conference on Learning Representations, 2018.
  * [27] Gen Luo, Yiyi Zhou, Jiamu Sun, Shubin Huang, Xiaoshuai Sun, Qixiang Ye, Yongjian Wu, and Rongrong Ji.  What goes beyond multi-modal fusion in one-stage referring expression comprehension: An empirical study.  arXiv preprint arXiv:2204.07913, 2022.
  * [28] Gen Luo, Yiyi Zhou, Xiaoshuai Sun, Liujuan Cao, Chenglin Wu, Cheng Deng, and Rongrong Ji.  Multi-task collaborative network for joint referring expression comprehension and segmentation.  In Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition, pages 10034–10043, 2020.
  * [29] Junhua Mao, Jonathan Huang, Alexander Toshev, Oana Camburu, Alan L Yuille, and Kevin Murphy.  Generation and comprehension of unambiguous object descriptions.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 11–20, 2016.
  * [30] Bryan A Plummer, Liwei Wang, Chris M Cervantes, Juan C Caicedo, Julia Hockenmaier, and Svetlana Lazebnik.  Flickr30k entities: Collecting region-to-phrase correspondences for richer image-to-sentence models.  In Proceedings of the IEEE international conference on computer vision, pages 2641–2649, 2015.
  * [31] Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi.  You only look once: Unified, real-time object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 779–788, 2016.
  * [32] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  Advances in neural information processing systems, 28, 2015.
  * [33] Hamid Rezatofighi, Nathan Tsoi, JunYoung Gwak, Amir Sadeghian, Ian Reid, and Silvio Savarese.  Generalized intersection over union: A metric and a loss for bounding box regression.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 658–666, 2019.
  * [34] Shuai Shao, Zeming Li, Tianyuan Zhang, Chao Peng, Gang Yu, Xiangyu Zhang, Jing Li, and Jian Sun.  Objects365: A large-scale, high-quality dataset for object detection.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 8430–8439, 2019.
  * [35] Adam Vogel and Dan Jurafsky.  Learning to follow navigational directions.  In Proceedings of the 48th annual meeting of the association for computational linguistics, pages 806–814, 2010.
  * [36] Peng Wang, Dongyang Liu, Hui Li, and Qi Wu.  Give me something to eat: referring expression comprehension with commonsense knowledge.  In Proceedings of the 28th ACM International Conference on Multimedia, pages 28–36, 2020.
  * [37] Peng Wang, Qi Wu, Jiewei Cao, Chunhua Shen, Lianli Gao, and Anton van den Hengel.  Neighbourhood watch: Referring expression comprehension via language-guided graph attention networks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1960–1968, 2019.
  * [38] Xinyu Wang, Yuliang Liu, Chunhua Shen, Chun Chet Ng, Canjie Luo, Lianwen Jin, Chee Seng Chan, Anton van den Hengel, and Liangwei Wang.  On the general value of evidence, and bilingual scene-text visual question answering.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10126–10135, 2020.
  * [39] Chenyun Wu, Zhe Lin, Scott Cohen, Trung Bui, and Subhransu Maji.  Phrasecut: Language-based image segmentation in the wild.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10216–10225, 2020.
  * [40] Sibei Yang, Guanbin Li, and Yizhou Yu.  Dynamic graph attention for referring expression comprehension.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4644–4653, 2019.
  * [41] Sibei Yang, Guanbin Li, and Yizhou Yu.  Graph-structured referring expression reasoning in the wild.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9952–9961, 2020.
  * [42] Zhengyuan Yang, Tianlang Chen, Liwei Wang, and Jiebo Luo.  Improving one-stage visual grounding by recursive sub-query construction.  In European Conference on Computer Vision, pages 387–404. Springer, 2020.
  * [43] Zhengyuan Yang, Zhe Gan, Jianfeng Wang, Xiaowei Hu, Faisal Ahmed, Zicheng Liu, Yumao Lu, and Lijuan Wang.  Unitab: Unifying text and box outputs for grounded vision-language modeling.  In European Conference on Computer Vision, pages 521–539. Springer, 2022.
  * [44] Zhengyuan Yang, Boqing Gong, Liwei Wang, Wenbing Huang, Dong Yu, and Jiebo Luo.  A fast and accurate one-stage approach to visual grounding.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4683–4693, 2019.
  * [45] Haoxuan You, Rui Sun, Zhecan Wang, Kai-Wei Chang, and Shih-Fu Chang.  Find someone who: Visual commonsense understanding in human-centric grounding.  arXiv preprint arXiv:2212.06971, 2022.
  * [46] Licheng Yu, Zhe Lin, Xiaohui Shen, Jimei Yang, Xin Lu, Mohit Bansal, and Tamara L Berg.  Mattnet: Modular attention network for referring expression comprehension.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1307–1315, 2018.
  * [47] Licheng Yu, Patrick Poirson, Shan Yang, Alexander C Berg, and Tamara L Berg.  Modeling context in referring expressions.  In European Conference on Computer Vision, pages 69–85. Springer, 2016.
  * [48] Rowan Zellers, Yonatan Bisk, Ali Farhadi, and Yejin Choi.  From recognition to cognition: Visual commonsense reasoning.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 6720–6731, 2019.
  * [49] Haotian Zhang, Pengchuan Zhang, Xiaowei Hu, Yen-Chun Chen, Liunian Harold Li, Xiyang Dai, Lijuan Wang, Lu Yuan, Jenq-Neng Hwang, and Jianfeng Gao.  Glipv2: Unifying localization and vision-language understanding.  arXiv preprint arXiv:2206.05836, 2022.
  * [50] Yiyi Zhou, Rongrong Ji, Gen Luo, Xiaoshuai Sun, Jinsong Su, Xinghao Ding, Chia-Wen Lin, and Qi Tian.  A real-time global inference network for one-stage referring expression comprehension.  IEEE Transactions on Neural Networks and Learning Systems, 2021\.
  * [51] Yuke Zhu, Oliver Groth, Michael Bernstein, and Li Fei-Fei.  Visual7w: Grounded question answering in images.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4995–5004, 2016.

##  Appendix A Limitations and Future Work

In this section, we highlight several limitations of this work. First, the
annotation of scene knowledge/stories is a creative process that requires the
imagination of the annotators. Therefore, the scene knowledge annotated by
different annotators could vary significantly. Besides, it could be biased due
to the different genders, cultural backgrounds, and interests of the
annotators. Second, compared to existing visual grounding datasets that only
require the annotations of the referring expressions, the whole annotation
process of the proposed dataset is much more time-consuming. Although we
developed software to improve the annotation efficiency, the scale of our
dataset is still smaller than the popular datasets, e.g., RefCOCO, RefCOCO+,
and RefCOCOg. Third, for the methodology, the two-stage approach LeViLM can
achieve relatively decent overall performance, especially in the easy/medium
split. However, it still struggles to obtain promising results in the hard
split.

This work could support and advance the research in the field of visual
grounding. In the future, we can study more techniques (e.g., knowledge
distillation) to leverage visual knowledge in the linguistic form to promote
the performance of various downstream vision-and-language tasks by embedding
knowledge into the visual representations.

##  Appendix B The annotation software

We developed software to promote the annotation procedure. The illustration of
the software is shown in Figure 6.

##  Appendix C More examples

We show more examples of the proposed SK-VG dataset. For ease of reading, we
make a figure for each example and show them in Figure 7-14.

Figure 6: The illustration of the annotation software. Figure 7: An example of
the training set. Figure 8: An example of the training set. Figure 9: An
example of the training set. Figure 10: An example of the training set. Figure
11: An example of the training set. Figure 12: An example of the test set.
Each query is assigned a difficulty level according to the significance of
knowledge for the query. Specifically, Q1 (“The microscope”) and Q2 (“A
bottle”) are visually-obvious and thus classified into Easy level. Q3 and Q4
are knowledge-relevant but provide some visual clues (“recording data” and
“observing cells”), rated as Medium level. Q5 relies heavily on the knowledge
and deserves a Hard label. Figure 13: An example of the test set. Each query
is assigned a difficulty level according to the significance of knowledge for
the query. Specifically, Q1 (“The painting”) and Q2 (“The mobile phone”) are
visually-obvious and thus classified into Easy level. Q3 and Q4 are knowledge-
relevant but provide some visual clues (“a painting in her hands” and
“admiring the painting”), rated as Medium level. Q5 relies heavily on the
knowledge and deserves a Hard label. Figure 14: An example of the test set.
Each query is assigned a difficulty level according to the significance of
knowledge for the query. Specifically, Q1 (“tie”) and Q2 (“A ladder”) are
visually-obvious and thus classified into Easy level. Q3 and Q4 are knowledge-
relevant but provide some visual clues (“opening the skylight” and
“reluctant”), rated as Medium level. Q5 relies heavily on the knowledge and
deserves a Hard label.