\section{Introduction}

Curvature is one of the most basic geometric characteristics of space. The original definitions of curvature apply only to smooth Riemannian or Lorentzian manifolds, but there exist numerous extensions of curvature definitions applicable to graphs, simplicial complexes, and other discrete structures. For a variety of reasons, these extensions have recently seen a surge of interest in areas as diverse as network/data science and quantum gravity.

In network science, graph curvature is interesting in general since many real-world networks were found to possess different flavors of geometry~\cite{boguna2021network}. Measuring network curvature is then a way to learn what this geometry really is~\cite{lubold2020identifying}. On the application side, graph curvature was used to characterize congestion in telecommunication networks~\cite{narayan2011large,jonckheere2011euclidean}, detect cancer cells~\cite{sandhu2015graph}, predict COVID-19 spreading~\cite{souza2020using} and stock market fluctuations~\cite{akguller2018geodetic}, analyze robustness and other properties of the Internet, financial, and brain networks~\cite{ni2015ricci,sandhu2016ricci,tadic2018origin,tadic2019functional,farooq2019network}, and in a number of classic applications such as community inference~\cite{sia2019ollivier} and network embedding in machine learning~\cite{gu2019learning}. In a majority of these applications, graph curvature appears as a signature of a (pathological) event or property of interest. How reliable such a signature is for a task at hand depends on whether the used definition of graph curvature does what is intended---that it is indeed curvature, and not something else.

In general relativity, scalar Ricci curvature is a key player since it appears in the Einstein-Hilbert action whose least-action extremization leads to Einstein's equations~\cite{carroll2019spacetime}. Therefore, various extensions of Ricci curvature to discrete structures representing  ``quantum spacetimes'' have been considered. The first step in that direction was based on replacing continuum manifolds with simplicial complexes~\cite{ambjrn2012nonperturbative}. To that end, variations of the seminal definition of discrete curvature by Regge~\cite{regge1961general} were developed and utilized. More recently, a collection of more minimalistic structures was considered, such as causal sets~\cite{bombelli1987space,henson2009causal,surya2019causal,benincasa2010scalar,belenchia2016continuum,glaser2016hartlehawking,glaser2018finite,eichhorn2019spectral,eichhorn2019steps,cunningham2020dimensionally} and random graphs~\cite{trugenberger2017combinatorial,kelly2019assembly,kelly2021emergence,klitgaard2018introducing,klitgaard2018implementing,klitgaard2020quantum}. Yet another class of approaches aimed at explaining spacetime emergence from ``quantum bits'' appear in space-from-entanglement proposals such as ER=EPR or tensor networks~\cite{maldacena2013cool,raamsdonk2010building,cao2017space,bao2017sitter,swingle2018spacetime,orus2019tensor,cotler2019locality}. In all these examples, one can hope that a particular discrete structure represents Planck-scale gravitational physics, only if discrete curvature of this structure converges to Ricci curvature of classical spacetime in the continuum limit. If such convergence does not hold in a particular approach, then the approach does not agree with general relativity, so it cannot be considered realistic, regardless of how attractive it is in other respects.

Quite contrary to the continuum world of Riemannian and Lorentzian manifolds where there is no real ambiguity regarding the definition of curvature, there exist not one or two but quite many nonequivalent definitions of curvature applicable to graphs. We briefly review the most prominent definitions in the next section.
Unfortunately, none of these definitions are known to converge in the continuum limit to any traditional curvature of any Riemannian manifold. Therefore, it is often unclear how one should interpret different measurements of different curvatures in different graphs and networks, raising question concerning reliability and generalizability of predictions based on such measurements. Similarly, the evasiveness of classical limit in some approaches to quantum gravity can be often linked to unclarities concerning whether discrete ``quantum'' curvature converges to a continuous classical one. These and other problems related to curvature convergence become particularly acute in view of growing evidence that different graph curvature definitions may disagree even about the sign of curvature in some paradigmatic graphs and networks~\cite{samal2018comparative,prokhorenkova2020global}.

Here we show that Ollivier curvature~\cite{ollivier2007ricci,ollivier2009ricci,ollivier2010survey} of random geometric graphs~\cite{gilbert1961random,dall2002random,penrose2003random} in any Riemannian manifold converges to Ricci curvature of the manifold in the continuum limit. Unfortunately, this convergence does not and cannot hold for the standard definition of Ollivier curvature of microscopic one-link neighborhoods in sparse unweighted graphs~\cite{jost2014olliviers}. Fortunately, we find a natural generalization of Ollivier curvature applicable to mesoscopic neighborhoods in unweighted and weighted graphs. This generalization is a not-previously-considered key ingredient that allows us to prove the curvature convergence. Our proofs hold only when the sizes of mesoscopic graph neighborhoods fall within certain windows that depend on graph density and on how graph edges are weighted. We also perform large-scale simulations that agree with our proofs and suggest that the convergence windows are actually much wider than the limits imposed by our proof techniques.

These are the first result of the sort, linking rigorously a definition of graph curvature to the traditional Ricci curvature of a Riemannian manifold. To the best of our knowledge, the closest, in spirit, previous results are Cheeger {\it et al.}'s proof~\cite{cheeger1984curvature} of Regge's seminal observation~\cite{regge1961general} that an angle-defect-based curvature of increasingly finer-grained simplicial triangulations of a manifold converges to its Ricci curvature, and the more recent demonstration~\cite{benincasa2010scalar,belenchia2016continuum} that the Benincasa-Dowker action of causal sets converges to its classical counterpart in the continuum limit.

To proceed, we first recall the Ollivier curvature definition in perspective of other curvature definitions applicable to graphs and networks, Sec.~\ref{sec:curvature}. We then describe our generalization of the Ollivier curvature definition to mesoscopic neighborhoods in graphs in general and in random geometric graphs in particular, Sec.~\ref{sec:mesoscopic}. We then state our main results in Sec.~\ref{sec:results}, and conclude with a discussion of their implications and caveats in Sec.~\ref{sec:discussion}.

\section{Graph curvature definitions}~\label{sec:curvature}

There are many nonequivalent definitions of curvature applicable to graphs. It is impossible to list them all. Here we mention some notable ones due to Steiner~\cite{steiner1882uber}, Regge~\cite{regge1961general,cheeger1984curvature}, Bakry-\'Emery~\cite{bakry1985diffusions}, Gromov~\cite{gromov1987hyperbolic,jonckheere2008scaled}, Higuchi~\cite{higuchi2001combinatorial}, Eckmann-Moses~\cite{eckmann2002curvature}, Forman~\cite{forman2003bochners,sreejith2016forman,weber2018coarse}, Lin-Yau~\cite{lin2010ricci,lin2011ricci}, Knill~\cite{knill2010discrete,knill2012index}, Keller~\cite{keller2011curvature,keller2011cheeger}, and hybrids thereof~\cite{kempton2020large}. We first outline the taxonomy of these curvatures and basic ideas behind their definitions to put Ollivier curvature~\cite{ollivier2007ricci,ollivier2009ricci,ollivier2010survey} in perspective, and then recall the detailed definition of the latter for completeness.

With a few exceptions, the discrete curvature definitions above fall into the following classes.

\subsection{Direct approaches}

The first class of definitions comes from relatively direct extensions of continuous curvature to nonsmooth objects such as simplices, simplicial complexes, or more general complexes. Since graphs are 1-dimensional simplicial complexes, any notion of curvature applicable to complexes applies to graphs as well. Casting cliques in graphs as higher-dimensional simplices turns graphs into higher-dimensional complexes, so that curvature definitions applicable to higher-dimensional complexes are also applicable to graphs.

One subclass of such approaches first defines curvature of polyhedra using the Gauss-Bonnet theorem that relates the curvature of a surface to its Euler's characteristic. This definition is then extended to general simplicial complexes. Curvatures defined by Steiner~\cite{steiner1882uber}, Regge~\cite{regge1961general,cheeger1984curvature}, Knill~\cite{knill2010discrete,knill2012index}, and Keller~\cite{keller2011curvature,keller2011cheeger} all fall into this category.

Forman curvature~\cite{forman2003bochners,sreejith2016forman,weber2018coarse} follows similar ideas, but is slightly different in that it uses the Bochner-Weitzenb\"{o}ck formula that relates the Laplacian of a Riemannian manifold to its discrete approximation, which is then used to derive a discrete version of curvature applicable to a very general class of complexes. The definition of Forman curvature for unweighted graphs is one of the simplest. If a graph is considered as a 1-complex, so that only nodes (0-simplices) and links (1-simplices) are considered, then the Forman curvature $F_1(i,j)$ of a link between nodes $i$ and $j$ of degrees $k_i$ and $k_j$ is
$
	F_1(i,j) = 4 - (k_i + k_j).
$
If the graph is considered as a 2-complex, so that triangles are also considered, and $\Delta_{i,j}$ is the number of triangles containing the link, then the definition becomes
$
	F_2(i,j) = F_1(i,j) + 3 \Delta_{i,j}.
$

\subsection{Indirect approaches}

Another class of ideas behind discrete curvature are less direct as they are based on more sophisticated curvature-related properties of smooth spaces.

One such idea, pioneered by Bakry and Emery~\cite{bakry1985diffusions}, relies on the characterization of Ricci curvature via curvature-dimension inequalities.
The curvature-dimension inequality establishes a lower bound for the Ricci curvature of a Riemannian manifold based on the gradient of harmonic functions on it. The inequality is an immediate consequence of Bochner's identity that relates Ricci curvature to the gradient of harmonic functions.
It was an important insight by Bakry and Emery that the curvature-dimension inequality can be lifted from manifolds and considered as a substitute of the lower bound for Ricci curvature in spaces where direct discretizations of Ricci curvature are not possible. In addition to the Bakry-Emery definition~\cite{bakry1985diffusions}, the definitions of Lin-Yau~\cite{lin2010ricci,lin2011ricci} also fall into this category.

The key point behind this type of approaches to discrete curvature is to base its definitions on some fundamental nontrivial curvature-related properties that transcend well beyond the limits of smooth spaces.

\subsection{Ollivier curvature}

Ollivier curvature belongs to the second class of approaches outlined above. The fundamental aspect of Ricci curvature that Ollivier curvature embarks on to sail to the discrete world, is somewhat different from---although related to---the curvature-dimension inequalities. This aspect is of a less analytic and more geometric nature. It deals with how balls shrink or expand under parallel transport. Recall that if Ricci curvature of a space is negative, zero, or positive, then under parallel transport, balls in this space expand, stay the same, or shrink, respectively.

To capture this property, one needs to consider the Wasserstein a.k.a.\ transportation distance $W(\mu_1,\mu_2)$ between two probability distributions $\mu_1,\mu_2$ in \emph{any} nice (Polish to be exact) metric space:
\begin{equation}\label{eq:wasserstein}
  W(\mu_1,\mu_2) = \inf_{\mu\in\Gamma(\mu_1,\mu_2)}\int d(x,y)\mu(x,y)\,dx\,dy,
\end{equation}
where $d(x,y)$ is the distance between points $x$ and $y$ in the space, and the infimum is taken over all possible transportation plans which are joint probability distributions~$\mu$ whose marginals are $\mu_1$ and $\mu_2$. If $\mu_1,\mu_2$ are represented by sand piles, then $W(\mu_1,\mu_2)$ is the minimum cost to transport pile $\mu_1$ into pile $\mu_2$, where the grain of sand at $x$ gets transported to $y$ incurring cost~$d(x,y)$.

Let $x$ and $y$ be now two points at a small distance $d_M(x,y)=\delta$ in a Riemannian manifold $M$, and let $\mu_1=\mu_x$ and $\mu_2=\mu_y$ be the normalized restrictions of the volume form in $M$ onto the balls $B_M(x,\delta),B_M(y,\delta)$ of radius $\delta$ centered at $x,y$, i.e.,
\begin{align}
  \mu_{x}(z) &= \frac{\mathrm{vol}(z)}{\mathrm{vol}[B_M(x,\delta)]}\quad\text{if } z\in B_M(x,\delta),\\
  \mu_{y}(z) &= \frac{\mathrm{vol}(z)}{\mathrm{vol}[B_M(y,\delta)]}\quad\text{if } z\in B_M(y,\delta),
\end{align}
where $\mathrm{vol}(z)\,dz$ is the volume element in~$M$.
Ollivier curvature between $x$ and $y$ is then defined by
\begin{equation}\label{eq:ollivier}
  \kappa_M(x,y)=1 - \frac{W_M(\mu_x,\mu_y)}{\delta}.
\end{equation}
We note that this curvature definition depends on the ball radius $\delta$ which can be any positive real number. It was shown in~\cite{ollivier2009ricci} that
\begin{equation}\label{eq:ollivier-ricci}
  \lim_{\delta\to0}\frac{\kappa_M(x,y)}{\delta^2}=\frac{\mathrm{Ric}(v,v)}{2(D+2)},
\end{equation}
where $D$ is $M$'s dimension, and $\mathrm{Ric}(v,v)$ is the Ricci curvature at $x$ along $v$ which is the unit tangent vector at $x$ pointing along the geodesic from $x$ to $y$. Ricci curvature $\mathrm{Ric}(v,v)$ is equal to the average of sectional curvatures at $x$ over all tangent planes containing $v$.

In words, the important convergence result in~\eqref{eq:ollivier-ricci} says that in Riemannian manifolds, the rescaled Ollivier curvature converges to Ricci curvature in the limit of small ball sizes $\delta\to0$.

It is relatively straightforward to extend the definition of Ollivier curvature from manifolds $M$ to simple unweighted graphs $G$, but there are important differences. The most crucial one is that in smooth spaces $M$ the Ollivier ball radius $\delta$ appearing in the Ollivier curvature definition~\eqref{eq:ollivier} can be any positive real number, which can tend to zero to prove the convergence in~\eqref{eq:ollivier-ricci}. In unweighted graphs $G$, however, the possible nonzero values of the distance---and so of the $\delta$---are positive integers, the hop lengths of shortest paths between pairs of nodes. The smallest possible nonzero distance is $\delta=1$, the graph distance $d_G(x,y)$ between directly connected nodes~$x$ and~$y$. Presumably because of the ``$\delta$ better be small'' logic, the Ollivier ball radius $\delta$ was routinely set to its smallest possible value $\delta=1$ in the definition of Ollivier graph curvature appearing in the past literature, even though $\delta$ in graphs can certainly be set to any positive integer value.

If $\delta=1$, then the balls $B_G(x,1)$ and $B_G(y,1)$ of radius $1$ around nodes $x$ and $y$ are the sets of the neighbors of $x$ and $y$, while the probability distributions $\mu_x$ and $\mu_y$ become the uniform distributions over these sets: $\mu_x=1/k_x$ and $\mu_y=1/k_y$, where $k_x$ and $k_y$ are the degrees of $x$ and $y$. These distributions govern the standard random walk in the graph. Thus defined, Ollivier graph curvature was shown to be bounded by $-2$ and~$1$, with the bounds achieved on infinite double-stars and complete graphs~\cite{jost2014olliviers}. The Ollivier graph curvature in this definition was measured in a great variety of synthetic and real-world networks~\cite{sandhu2015graph,ni2015ricci,sandhu2016ricci,sia2019ollivier,samal2018comparative,prokhorenkova2020global,jost2014olliviers,bhattacharya2015exact}. It was also investigated at great depths in connection to quantum gravity~\cite{trugenberger2017combinatorial,kelly2019assembly,kelly2021emergence,klitgaard2018introducing,klitgaard2018implementing,klitgaard2020quantum}.

However, it is evident that Ollivier curvature of graphs as defined above cannot converge to Ricci curvature of manifolds under any circumstances, simply because $\delta$ is no longer real but integer, so that $\lim_{\delta\to0}$ makes no sense, and because Ollivier graph curvature is always between $-2$ and $1$, while Ricci curvature of a Riemannian manifold can be any real number. Therefore, in the next section, we generalize the Ollivier graph curvature definition to make it much more versatile, capturing a much wider spectrum of graph properties that are not necessarily microscopic.

\section{Mesoscopic graph neighborhoods}\label{sec:mesoscopic}

\subsection{General idea}

The main limitation of the Ollivier graph curvature definition in the previous section is that it is ``too microscopic.'' It limits the curvature-related considerations to graph balls/neighborhoods of the radius of one hop, $\delta=1$. Such neighborhoods may be too small to ``feel'' any curvature in a general case. Recall that microscopically, any smooth curved space is locally flat. This observation instructs us to consider much larger mesoscopic graph neighborhoods with $\delta\gg1$. Unfortunately, this instruction cannot be correct either, because to talk about any curvature convergence, we really need $\delta\ll1$ since $\delta$ must go to zero in the key convergence equation~\eqref{eq:ollivier-ricci}, which is the main motivation to set $\delta$ to its smallest possible value $1$ in graphs.

The combination of the calls for $\delta\ll1$ and $\delta\gg1$ looks like a clear sign of unhealthy pathology, suggesting to abandon any hopes for Ollivier-to-Ricci curvature convergence in graphs. And indeed we believe it is obvious that there cannot be any such convergence in unweighted graphs, simply because $\delta$ cannot be less than $1$ in them.

However, these observations do not preclude the curvature convergence in weighted graphs with positive real weights. In such graphs, the Ollivier ball radius $\delta$ is back to being a positive real number, which can tend to zero because link weights can tend to zero with some characteristic rate~$\epsilon$. Suppose also that $\epsilon$ and $\delta$ tend to zero
such that $\epsilon\ll\delta$.
Then, on the one hand, we have that $\delta\to0$ as needed for convergence~\eqref{eq:ollivier-ricci}, while on the other hand, the hop-wise lengths of the radii of Ollivier's balls are $\delta/\epsilon\gg1$, so that their sizes actually grow in terms of number of nodes. This way we simultaneously satisfy the two requirements above: the Ollivier balls are small ($\delta\ll1$) and large ($\delta/\epsilon\gg1$) at the same time, hence we call them \emph{mesoscopic}. It is intuitive to think of $\epsilon$ and $\delta$ as the microscopic and mesoscopic scales of the system.

The outlined approach is very general and can be implemented in a variety of situations. In particular, the graphs do not really have to be weighted, but $\delta$ must necessarily play a role of a properly rescaled graph distance. In the next section, we make these ideas concrete in application to random geometric graphs.

\subsection{Random geometric graphs}

To describe our implementation of the general ideas from the previous subsection in application to random geometric graphs (RGGs), we first recall what RGGs are.

Given any Riemannian manifold, which henceforth we will often call just {\it space}, the RGGs in it are defined constructively via the following two-step procedure: 1)~sprinkle points uniformly at random in the space via a Poisson point process of rate~$r>0$ driven by the volume form defined by the metric in the space~\cite{last2017lectures}, and 2)~connect by edges all pairs of points whose pairwise distances in the space are smaller than threshold $t>0$, Fig.~\ref{fig:fig1}(a). In topology, RGGs are a very fundamental object because they are $1$-skeletons of Vietoris-Rips complexes~\cite{kahle2011random} whose topology was proven to converge to the space topology under very mild assumptions~\cite{latschev2001vietoris}. In that context, our results below show that in a proper sense, the geometry of RGGs also converges to the space geometry.

\begin{figure}
  \centerline{\includegraphics[width=\linewidth]{figures/fig1.pdf}}
  \caption{{\bf Random geometric graphs in (a)~Riemannian space and (b)~Lorentzian spacetime.} The figure visualizes the flat two-dimensional Euclidian plane~(a) and Minkowski spacetime~(b), where distances are the $\ell_2$ and $\ell_1$ norms, respectively. Nodes are sprinkled randomly via the Poisson point process with rate $r=n$. The blue regions are the balls $B_M(x,\varepsilon_n)$ of radius $t=\varepsilon_n$ around node~$x$ located at the origin. In~(b) this ball is the intersection of the past light cone centered at time $t=\varepsilon_n$ with the future light cone centered at time $t=-\varepsilon_n$. Node~$x$ is connected to all other nodes in the graph that happen to lie within these blue balls. The yellow regions are the Ollivier balls $B_M(x,\delta_n)$ of radius~$\delta_n\geq\varepsilon_n$. Node~$y$ is at distance~$\delta_n$ from~$x$. Vector~$v$ (not shown) is the tangent vector at~$x$ towards~$y$. The probability distribution~$\mu_x$ is the uniform distribution over all the nodes $z$ that happen to lie within distance~$\delta_n$ from~$x$ in the graph, $z\in B_G(x,\delta_n)$. These are \emph{not} exactly the nodes lying with the yellow Ollivier balls, but at large~$n$ the difference is negligible, Appendix~\ref{ssec:aprrox-mu}.}\label{fig:fig1}
\end{figure}

We are now ready to describe our $\epsilon,\delta$-settings with RGGs in the continuum limit $n\to\infty$ suitable for curvature convergence investigations.

Given any nice $D$-dimensional Riemannian manifold~$M$, we first fix any point $x$ in it and any unit tangent vector~$v$ at $x$. We are concerned with Ricci curvature at $x$ in the $v$-direction. For a given $n$, we add the second point $y$ at distance $\delta_n$ from $x$, $d_M(x,y)=\delta_n$, along the geodesic from $x$ in the $v$-direction. The distance $\delta_n$ is also the radius of the balls in the Ollivier curvature definition above, so that it goes to zero in the limit, $\delta_n\to0$.

We then add the Poisson point process (PPP) of rate $r\sim n$ in $M$ to the two nonrandom points $x,y$. Henceforth, $f(n)\sim g(n)$ means $f(n)/g(n) \to c\in(0,\infty)$, and $f(n)\approx g(n)$ means $c=1$. The connection distance threshold $t$ in RGGs defined on top of this PPP$+\{x,y\}$ is then set to $t=\epsilon_n\to0$.
That is, all pairs of points are linked in RGG $G$ if the distance between them in $M$ does not exceed $\epsilon_n$. In the continuum limit $n\to\infty$ of this setup, our PPP samples the manifold increasingly densely (as there are on average $r\sim n$ vertices in $G$ per unit volume in $M$), while the RGGs become increasingly ``microscopic'' (as their edges span $M$'s distances no greater than $\epsilon_n\to0$).

Every created edge is then weighted as described in the next section. For any two vertices $z_1$ and $z_2$ in RGG $G$, we thus have two distances defined: the manifold distance $d_M(z_1,z_2)$ and the graph distance $d_G(z_1,z_2)$, which is the length of the shortest path between $z_1$ and $z_2$ in the \emph{weighted graph} $G$.

Ollivier's balls centered at $x,y$ are then the sets of $G$'s vertices $z$ lying within \emph{weighted graph} distances $d_G\leq\delta_n$ from vertices $x,y$: $B_G(x,\delta_n)=\{z\in G:d_G(x,z)\leq\delta_n\}$, $B_G(y,\delta_n)=\{z\in G:d_G(y,z)\leq\delta_n\}$. The probability distributions $\mu_x,\mu_y$ are the uniform distributions on the vertex sets $B_G(x,\delta_n), B_G(y,\delta_n)$:
\begin{align}
  \mu_{x}(z) &= \frac{1}{\left|B_G(x,\delta_n)\right|}\quad\text{if } z\in B_G(x,\delta_n),\label{eq:mu_G_x}\\
  \mu_{y}(z) &= \frac{1}{\left|B_G(y,\delta_n)\right|}\quad\text{if } z\in B_G(y,\delta_n).\label{eq:mu_G_y}
\end{align}
Finally, Ollivier \emph{graph} curvature $\kappa_G(x,y)$ is defined by the same equation~\eqref{eq:ollivier}, except that probability distributions $\mu_x,\mu_y$ are given by~(\ref{eq:mu_G_x},\ref{eq:mu_G_y}), Fig.~\ref{fig:fig1}(a):
\begin{equation}\label{eq:ollivier-graph}
  \kappa_G(x,y)=1 - \frac{W_G(\mu_x,\mu_y)}{\delta_n}.
\end{equation}

We reiterate that as opposed to previous literature on Ollivier graph curvature, we do \emph{not} require the RGG connection radius $\varepsilon_n$ to be equal to the Ollivier ball radius $\delta_n$, Fig.~\ref{fig:fig1}(a). However, we do not exclude this possibility either. In fact, we will see in the next section that the Ollivier-to-Ricci curvature convergence does hold even with $\varepsilon_n=\delta_n$ if links are weighted by the manifold distances between the linked nodes, and if graphs are sufficiently dense. That is, our only requirements to $\varepsilon_n$ and $\delta_n$ are that they both must go zero, and that $\varepsilon_n\leq\delta_n$.

\section{Results}\label{sec:results}

We obtain curvature convergence results for two different schemes of edge weighting in our random geometric graphs. We consider them separately in the next two sections.

\subsection{Space distance weights}

We first state our results for the settings in the previous section with the weights $w_{ij}$ of all edges $i,j$ in RGGs $G$ set equal to the distances between $i$ and $j$ in manifold~$M$:
\begin{equation}\label{eq:distance-weights}
w_{ij}=d_M(i,j).
\end{equation}

With these settings, we can show that in the continuum limit, rescaled Ollivier curvature in random \emph{graph} $G$ converges to Ricci curvature in \emph{manifold} $M$,
\begin{equation}\label{eq:ollivier-ricci-hoorn}
    \lim_{n\to\infty} \left\langle\left|\frac{\kappa_G(x,y)}{\delta_n^2} - \frac{\mathrm{Ric}(v,v)}{2(D+2)}\right|\right\rangle = 0,
\end{equation}
if the RGG connectivity radius~$\varepsilon_n$ and Ollivier's ball radius~$\delta_n$ shrink to zero with~$n$ as
\begin{equation}\label{eq:delta_n}
  \varepsilon_n      \sim n^{-\alpha},\quad
  \delta_n  \sim n^{-\beta},
\end{equation}
with exponents $\alpha,\beta$ satisfying
\begin{equation}\label{eq:weighted-conditions}
  0 < \beta \leq \alpha,\quad
  \alpha+2\beta<\frac{1}{D}.
\end{equation}
The connectivity and Ollivier balls can be equal and can shrink at the same rate,
\begin{equation}
\epsilon_n\sim\delta_n\sim n^{-\alpha},
\end{equation}
in which case \eqref{eq:weighted-conditions} becomes
\begin{equation}\label{eq:weighted-conditions-alpha}
  \alpha<\frac{1}{3D}.
\end{equation}

The expectation $\ea{\cdot}$ in~\eqref{eq:ollivier-ricci-hoorn} is w.r.t.\ the RGG ensemble, in which $\kappa_G(x,y)$ is random. The result in~\eqref{eq:ollivier-ricci-hoorn} is strong in the sense that it implies not only the convergence of the expected value of Ollivier graph curvature to Ricci curvature generalizing~\eqref{eq:ollivier-ricci} to graphs,
\begin{equation}
    \lim_{n\to\infty}\frac{\ea{\kappa_G(x,y)}}{\delta_n^2}=\frac{\mathrm{Ric}(v,v)}{2(D+2)},
\end{equation}
but also the concentration of random $\kappa_G(x,y)$ around its expected value,
\begin{equation}
    \lim_{n\to\infty}\mathrm{Prob}\left[\left|\frac{\kappa_G(x,y)}{\delta_n^2}-\frac{\mathrm{Ric}(v,v)}{2(D+2)}\right|>\varepsilon\right]=0
\end{equation}
for any $\varepsilon>0$.

We note that the conditions~(\ref{eq:weighted-conditions}) allow graphs to be arbitrarily sparse, but not exactly ultrasparse. We call graphs \emph{dense}, \emph{sparse}, and \emph{ultrasparse} (also \emph{truly sparse}) if their expected average degree
\begin{equation}
    \bar{k}_n\sim n\,\mathrm{vol}[B_M(\cdot,\varepsilon_n)]\sim n\varepsilon_n^D \sim n^{1-\alpha D}
\end{equation}
is $O(n)$, $o(n)$, and $\sim const.$, respectively. Observe that the exponent $\beta$ in (\ref{eq:weighted-conditions}) cannot be exactly zero because Ollivier's balls must shrink for the sake of convergence, but it can be arbitrarily close to zero. The closer the $\beta$ to zero, the closer the $\alpha$ can be to $1/D$ according to~(\ref{eq:weighted-conditions}), while $\alpha=1/D$ corresponds to the ultrasparse case with $\bar{k}_n\sim const$. We note though that the closer the $\beta$ to zero, the slower the convergence, simply because Ollivier's balls shrink too slowly in this case.

Another important observation is that the case with $\varepsilon_n=\delta_n$ corresponds to the traditional definition of Ollivier graph curvature with microscopic one-hop neighborhoods. In this case, Eq.~\eqref{eq:weighted-conditions-alpha} says that we cannot prove the convergence anywhere close to the ultrasparse limit with $\alpha=1/D$, and our simulations suggest that there is no convergence there indeed.

In general, the sparser the graphs, the more problematic the convergence becomes. This is because, the sparser the graphs, the smaller the connection radius $\varepsilon_n$. As discussed in Section~\ref{sec:mesoscopic}, if $\varepsilon_n$ is too small, and if $\delta_n=\varepsilon_n$, then all balls are of the radius of one hop, and such microscopic neighborhoods may not ``feel'' any curvature; all they can ``feel'' is locally Euclidean flatness.

\subsubsection{Proofs}

Our proof of~\eqref{eq:ollivier-ricci-hoorn}, outlined in Appendix~\ref{sec:proof_weighted_graphs}, is not trivial. It consists of three major steps.

First, we extend the weighted shortest path distance in RGGs $G$ to space $M$. We do so by defining the following auxiliary distance in $M$. For any pair of points $x,y\in M$ we add $x$ and $y$ as nodes to the graph $G$, and connect them to all other nodes in $G$ within some distance $\lambda_n \ll \epsilon_n$ from $x,y$ in $M$. The auxiliary manifold distance between $x,y$ is then the distance between them in the extended graph. We must select $\lambda_n$ very carefully, to make sure the auxiliary distance is a sufficiently good approximation of the true distance in $M$.

Once we have this auxiliary distance in $M$, we need to approximate Ollivier's balls in RGGs $G$ with the corresponding balls in $M$. That is, on the one hand we have sets of nodes within graph distance $\delta_n$ from node $x$, while on the other hand we have sets of nodes within manifold distance $\delta_n$ from $x$. We work out this approximation by deriving an upper bound on the Wasserstein distance between the uniform probability distributions on these two balls. This allows us to work with balls defined by manifold distances, instead of graph distances.

Finally, the most nontrivial step, we must relate the discrete uniform probability distribution defined on finite sets of nodes in balls in $G$, to the corresponding nonuniform continuous distributions defined on the continuum of points in balls in $M$. To this end, using a result on matching two Poisson point processes, we first bound the Wasserstein distance between these two distributions in Euclidean space. We finally extend this result to non-Euclidean $M$, using the local flatness of the space together with the fact that the neighborhoods that we consider shrink as $\delta_n \to 0$.

Overall, at each step of this proof, we introduce an approximation error to the relation between the Wasserstein distances in graphs $G$ and manifold $M$. The crux of each step is that it must be done with care to ensure that the introduced error is upper-bounded by $\delta_n^3 \to 0$. This is because if the error is that small, then~\eqref{eq:ollivier-ricci-hoorn} follows from~\eqref{eq:ollivier-ricci}. The further details behind how we achieve this at each step of the proof can be found in Appendix~\ref{sec:proof_weighted_graphs}.

\subsubsection{Simulations}

The fact that we can prove the Ollivier$\to$Ricci convergence only under the conditions (\ref{eq:weighted-conditions}) does not mean that there is no convergence outside of this parameter region, and this is indeed what we observe in simulations.

For simulations we select the sphere, torus, and the Bolza surface as the three $2D$ manifolds of constant Ricci curvature $+1$, $0$, and $-1$. The Bolza surface~\cite{aurich1988periodic,ratcliffe2019foundations} is the simplest hyperbolic $2D$ manifold of genus $2$ with no boundaries.
We consider the Bolza surface, versus something simpler of negative curvature, such as a hyperbolic disk, because we want our manifolds to have no boundaries. We want this, because computing Ollivier curvature in simulations is a major challenge at large $n$, so that we do not want any boundary effects at any $n$.

We then fix $x$ and $y$ as described above, sprinkle $n$ points on the three manifolds uniformly at random according to the manifold volume form, and link all pairs of points at distances $\leq \varepsilon_n$ on the manifold. We then find Ollivier's balls $B_G(x,\delta_n), B_G(y,\delta_n)$, set up the uniform probability distributions $\mu_x=1/|B_G(x,\delta_n)|,\,\mu_y=1/|B_G(y,\delta_n)|$ on them, and compute all the pairwise distances $d_G(x_i,y_j)$ in graph $G$ between nodes $i\in B_G(x,\delta_n)$ and $j\in B_G(y,\delta_n)$ whose coordinates are $x_i$ and $y_j$. All this data allow us to compute the Wasserstein distance $W_G(\mu_x,\mu_y)$ by solving the linear program
\begin{equation}\label{eq:ricci_lp}
\begin{split}
W_G(\mu_x,\mu_y)&=\min_{\rho_{ij}}\sum\limits_{i,j}d_G(x_i,y_j)\rho_{ij}\mu_x,\text{ s.t.}\\
\sum\limits_i\rho_{ij}\mu_x&=\mu_y,\quad0\leq\rho_{ij}\leq 1,\quad\sum\limits_j\rho_{ij}=1,\\
\end{split}
\end{equation}
where the minimization is over transportation plans $\rho_{ij}$ whose entries describe pairwise movements of probability masses.
Having computed this $W_G(\mu_x,\mu_y)$, Ollivier curvature is finally given by~\eqref{eq:ollivier-graph}. Further details on the simulations are in Appendix~\ref{sec:simulations}.

\begin{figure}[!t]
\centering
\includegraphics[width=1.08\linewidth]{figures/results.pdf}
\caption{{\bf Ollivier-Ricci curvature convergence in constant-curvature random geometric graphs.}
Panel~(a) shows the simulation data for rescaled Ollivier curvature~\eqref{eq:ollivier-graph} in \eqref{eq:distance-weights}-weighted random geometric graphs on the ($D=2$)-dimensional torus, sphere, and Bolza surface. The scaling exponents of the connectivity and Ollivier's ball radii~\eqref{eq:delta_n} in the graphs are set to $\alpha=\beta=0.16<1/6$ lying within the proof-accessible regime~(\ref{eq:weighted-conditions-alpha}).
Panel~(b) shows apparent convergence for $\alpha=\{1/4,1/2\}$ and $\beta=1/4$. Both of these two settings lie well outside of the proof-accessible regime~(\ref{eq:weighted-conditions}), while $\alpha=1/2$ corresponds to truly sparse graphs with constant average degree. The error bars represent the standard error $\sigma/\sqrt{n_s}$, where $\sigma$ is the standard deviation and $n_s=10\cdot2^{17}/n$ is the number of sampled random graphs of size $n$.
The smallest graph size $n$ is chosen to ensure the graphs are connected, while the largest size $n=2^{17}$ is bounded by memory constraints of the MOSEK package.
}
\label{fig:results}
\end{figure}

The results are shown in Fig.~\ref{fig:results}.
Remarkably, we observe that rescaled Ollivier curvature in our RGGs converges to Ricci curvature of the underlying manifold not only in the parameter regime accessible to our proofs, Fig.~\ref{fig:results}(a), but also well outside of this regime, for much sparser graphs, Fig.~\ref{fig:results}(b). In particular, we observe that the convergence is as good for truly sparse graphs with constant average degree as for denser graphs.

\subsection{$\varepsilon_n$-weights}

On the one hand, we may be not too happy that the weighted RGGs considered in the previous section contain too much information about the manifold in their edge weights $w_{ij}=d_M(i,j)$, helping the convergence ``too much.'' On the other hand, we cannot be happy at all if edges are unweighted, $w_{ij}=1$, because in this case there cannot be any curvature convergence whatsoever for the reasons discussed in Section~\ref{sec:mesoscopic}.
The maximum-happiness point appears to be the middle-ground possibility discussed in Section~\ref{sec:mesoscopic}---all edges are weighted by the same weight decaying to zero and playing the role of a system scale, {\it a la} the Planck scale.
This ``Planck scale'' in our case is the RGG connectivity radius $\varepsilon_n$.
That is, the weights $w_{ij}$ of all edges $i,j$ in our RGGs in this section are
\begin{equation}\label{eq:e-weights}
w_{ij}=\varepsilon_n.
\end{equation}

This weighting scheme is equivalent to saying that we actually work with \emph{unweighted} graphs, except that we multiply by $\varepsilon_n$ all distances in them, which are hop lengths of shortest paths. If $d_G(z_1,z_2)$ is the shortest path hop distance between vertices $z_1$ and $z_2$ in the unweighted RGG $G$, then the rescaled graphs distance $d'_G(z_1,z_2)=\varepsilon_nd_G(z_1,z_2)$ is actually a good approximation to the manifold distance $d_M(z_1,z_2)$. Unfortunately, how good this approximation is (characterized by \emph{stretch} $d'_G/d_M$), has been rigorously quantified only for the RGGs in the Euclidean plane~\cite{diaz2016relation}. Since the distances we approximate are bounded by Ollivier's ball radius $\delta_n$ that tends to zero, and since any Riemannian manifold is locally Euclidean, our results below relying on~\cite{diaz2016relation} hold for any $2D$-manifold. In fact, it turns out that the results in~\cite{diaz2016relation} are strong enough for our proof strategy in the weighted case to work essentially without a change in this unweighted case as well, Appendix~\ref{sec:proof_graphs}. While our result below holds only for $D=2$, analogous results for higher dimensions can be worked out as soon as stretch results for higher dimensional RGGs are obtained.

The result in Appendix~\ref{sec:proof_graphs} is that with weights in~\eqref{eq:e-weights}, the Ollivier$\to$Ricci convergence holds in the same strong sense~\eqref{eq:ollivier-ricci-hoorn} if
\begin{equation}\label{eq:non-weighted_conditions}
  0<\beta<\frac{1}{9},\quad
  3\beta<\alpha<\frac{1-3\beta}{2}.
\end{equation}

Similar to the weighted case, these conditions allow for arbitrarily sparse but not ultrasparse graphs ($\beta\to0$, $\alpha\to1/2$). Unlike the weighted case, these conditions imply that, as expected, the convergence is slower: $\beta<1/9$ (2D unweighted) versus $\beta<1/6$ (2D weighted). Another difference with the weighted case is that these conditions do not allow for the connectivity radius $\varepsilon_n$ to be the same as Ollivier's ball radius $\delta_n$: $\alpha\geq3\beta\Rightarrow\delta_n\gg\varepsilon_n$. We believe this is not a deficiency in our proof techniques, but a reflection of reality. It seems obvious that one must consider mesoscopic neighborhoods of size $\delta_n\gg\varepsilon_n$ in unweighted graphs since one-hop microscopic $\varepsilon_n$-neighborhoods in these graphs are too small to feel any curvature.

\section{Discussion}\label{sec:discussion}

We have established a rigorous connection between curvatures of discrete and continuous objects---random graphs and Riemannian manifolds. Anecdotally, this connection is reminiscent of what Riemann had in mind working on the foundations of Riemannian geometry~\cite{riemann1873hypotheses}.
The closest result to ours, which deals with convergence of curvature of simplicial triangulations of manifolds in Regge calculus~\cite{regge1961general,cheeger1984curvature} and its many derivatives~\cite{loll1998discrete}, is very different. Informally, while any simplex in any simplicial triangulation of any manifold is a chunk of space, graphs are much more primordial objects in that they do not have any space attached to them whatsoever.

We saw why the convergence of discrete curvature to a continuous one is such a delicate matter. If we use the standard simple definition of Ollivier graph curvature, then the immediately obvious observation is that there cannot be any convergence. We really have to consider mesoscopic regions in graphs with properly rescaled distances for the convergence to take place, an observation that has been entirely overlooked in the past. Even then the graph density and mesoscopic region sizes cannot be arbitrary, but should enter in a delicate interplay. These nontrivial delicate points are one reason why there are so few results on discrete$\to$continuous curvature convergence.

Our convergence proofs can likely be improved since our simulations suggest that the convergence holds well outside of the parameter regimes accessible by our proof techniques. Our simulations can be improved as well. We could not simulate graphs large enough to see any convergence in $\varepsilon_n$-weighted graphs, where the convergence is slow. In any case, the investigation of the exact boundaries between regimes where the convergence does and does not take place is a wide open problem, both for Ollivier curvature and for all other discrete curvature definitions mentioned in Section~\ref{sec:curvature}, for most of which it is not even known under what circumstances, if any, they do converge.

If some discrete curvature does not converge to a continuous one for some discrete structure, then it may very well happen that this discrete curvature tells us something very different about the structure from what is intended. In such a case, why should we call this ``curvature'' \emph{curvature}? This problem is not semantic but practical. If we are sure that graph curvature converges to manifold curvature, then we can be also sure that our graph curvature can be used to learn reliably manifold geometry---an exciting news for manifold learning and many other network/data science applications mentioned in the introduction. As an example of the other extreme, if we are sure that curvature of some tensor network does not converge to Ricci curvature of classical spacetime, then we can be also sure that this tensor network is not a good model of quantum spacetime.

As far as possible applications to quantum gravity are concerned, our results are an important but very high-level step that does not touch on many critical aspects. We comment on some of them.

First of all, we proved the convergence of curvature only for graph links and paths. Their curvatures first need to be averaged to result in scalar Ollivier-Ricci curvature at a vertex, and then integrated over vertex sets to yield a discrete version of the Einstein-Hilbert action. Is there any convergence in this case, and if so, then under what circumstances? Such convergence results would indicate unambiguously that the discrete Einstein-Hilbert action can be constructed from Ollivier curvature.

A much more difficult problem is the following. What we have solved is the direct problem of graph curvature convergence to space curvature when space is there. The problem in quantum gravity is actually the inverse problem of geometrogenesis~\cite{wu2015emergent,trugenberger2017combinatorial,kelly2019assembly}---there is no space, only a discrete quantum structure, which must ``look like'' space in the classical limit. That is, an illusion of continuous space must somehow emerge in the limit.

One strategy to address this problem is conceptually similar to~\cite{krioukov2016clustering}. One can consider a canonical maximum-entropy Gibbs ensemble of random graphs with fixed values of Ollivier curvature on links, paths, or vertices. The questions then are: is this ensemble equivalent (in the continuum limit) to the ensemble of random geometric graphs on a Riemannian manifold with the corresponding values of Ricci curvature, and do we have any (second-order) phase transitions in this ensemble? If the answer to the first question is \emph{yes}, then the graphs in this ensemble do look like spatial graphs, even though there is no space in their definition. If the connection between Ollivier curvature and the Einstein-Hilbert action is there, then the temperature parameter in this ensemble must be analogous to the gravitational coupling constant. In that context, the settings considered in this paper are particularly interesting. Indeed, since Ollivier curvature~\eqref{eq:ollivier-graph} is well defined for any shortest path between any pairs of nodes $x,y$ located at any distance in the graph, one can probe graph curvature at \emph{any} scale for renormalization and other purposes.

Finally, yet another critical issue is the issue of time, causality, and Lorentzian metric signature. There are two schools of thought concerning the issue. The first school believes that time and Lorentzian signature must be also emergent. This route is followed, for example, in the combinatorial quantum gravity program~\cite{trugenberger2017combinatorial,kelly2019assembly}, where time and causality are expected to appear only in the continuum limit above a certain scale, below which spacetime is Riemannian, turning into a random graph at a second-order phase transition defining quantum gravity nonperturbatively.

The second school builds in time and causality {\it ab initio}, as in causal sets or causal dynamical triangulation. For our results to be applicable in these settings, one needs first to extend them from Riemannian spaces to Lorentzian spacetimes. To the best of our knowledge, no notion of random geometric graphs or Rips complexes has been defined for Lorentzian manifolds. Since intersections of past and future light cones, Fig.~\ref{fig:fig1}(b), known as \emph{causal diamonds} or \emph{Alexandroff sets}, play the role of balls in Lorentzian geometry---specifically, the topology defined by Alexandroff sets agrees with the base topology in any nice Lorentzian spacetime~\cite{kronheimer1967structure}---we propose to define Lorentzian random geometric graphs as shown in Fig.~\ref{fig:fig1}(b). This definition is very different from causal sets, where any two time-like-separated nodes are linked, and there are no other links. In the Fig.~\ref{fig:fig1}(b) definition of Lorentzian random geometric graphs, there are both time-like and space-like links but only between nodes within causal diamonds of a finite size. Can Ollivier curvature be defined for these graphs and shown to converge to Ricci curvature of the underlying Lorentzian manifold?

\begin{acknowledgments}
We thank R.~Loll, B.~Dittrich, S.~Surya, D.~Rosset, E.~Andersen, Y.~Zhou, J.~Jost, and A.~Aranovich for useful discussions, suggestions, and comments.
This work was supported by ARO Grant Nos.~W911NF-16-1-0391 and W911NF-17-1-0491, and by NSF Grant Nos.~IIS-1741355 and DMS-1800738. Research at Perimeter Institute is supported by the Government of Canada through the Department of Innovation, Science, and Economic Development and by the Province of Ontario through the Ministry of Colleges and Universities. Experiments were conducted using the Discovery cluster, supported by Northeastern University's Research Computing team, and the B\'eluga, Graham, and Cedar clusters, supported by Compute Canada and its regional partners Calcul Qu\'ebec, Compute Ontario, and Westgrid.
\end{acknowledgments}

\onecolumngrid
\clearpage
\twocolumngrid


\section{Introduction}

The region-based object detectors~\cite{rcnn,fastrcnn,fasterrcnn,fpn,cascade,ecr} popularized by R-CNN framework~\cite{rcnn} are conceptually intuitive and flexible, and have achieved top accuracies on challenging benchmarks like MS-COCO~\cite{coco}. Region-based detectors first generate a sparse set of object proposals, and then refine the proposal locations and classify them as one of the foreground classes or as background using a detection head. One crucial module in such a proposal-driven pipeline is the RoIPool~\cite{fastrcnn} or RoIAlign~\cite{maskrcnn} operator, which is responsible for extracting RoI (Region of Interests) features aligned with the proposal locations for the detection head.

\begin{figure}[t]
	\centering
	\subfloat[Filtering out noisy detections.] {\includegraphics[width=0.48\columnwidth]{figs/motivation_1.pdf} }
	\subfloat[Recognizing indistinctive objects.]  {\includegraphics[width=0.48\columnwidth]{figs/motivation_2.pdf} }
	\scriptsize
	\caption{Motivation and example results of our Hierarchical Context Embedding (HCE) framework. By incorporating discriminative context information, our framework can effectively filter out the noisy false positive background detections, and correctly classify objects (\textit{e.g.}, ``\texttt{skateboard}'') which possess no distinctive appearances.}
	\label{fig:motivation}
\end{figure}

In this paper, we revisit the RoI features in region-based detectors from the perspective of context information embedding. Our key motivation relies on the fact that while each RoI in very deep CNNs may have a very large theoretical receptive field that often spans the entire input image~\cite{fastrcnn}. However, the effective receptive field~\cite{Luo2016} may only occupy a fraction of the full theoretical receptive field, making the RoI features insufficient for characterizing objects that are highly dependent on context information, such as ``\texttt{bowl}'', ``\texttt{skateboard}'' etc. Here, the contextual information means any auxiliary information that can assist in suppressing the false positive detections in noisy backgrounds, or recognizing objects that have no distinctive appearances themselves. For example, as shown in~Fig.~\ref{fig:motivation} (a), the semantic features of ``\texttt{motorcycle}'' are strong evidences for filtering out the activations of irrelevant object categories like ``\texttt{spoon}'', ``\texttt{bowl}'', and ``\texttt{sink}''. On the other hand, as shown by~Fig.~\ref{fig:motivation} (b), the scene and even the human pose are useful clues for correctly classifying a proposal as ``\texttt{skateboard}'', rather than ``\texttt{tennis racket}''.

Recently, several works exploited the region-level context information to improve the localization ability of two-stage detectors. Chen~\textit{et al.}~\cite{context} demonstrated that rich contextual information from neighboring regions can better refine the proposal locations for two-stage detectors. Kantorov~\textit{et al.}~\cite{kantorov2016contextlocnet} leveraged the surrounding context regions to improve weakly supervised object localization. However, to the best of our knowledge, currently there is no enabling framework which is systematically designed for embedding context information to improve the \textit{classification ability} of region-based detectors.

In this paper, we present a novel Hierarchical Context Embedding (HCE) framework for region-based object detectors. Our framework consists of three modules. Firstly, we consider that the simplest way to break the contextual limit in object detection, is to partially cast the object-level feature learning as an image-level multi-label classification task. Building upon this realization, we design an image-level categorical embedding module, which in essence is a multi-label classifier upon the detection backbone, in parallel with the existing region-based detection head. It enables the backbone to exploit the whole image context to learn discriminative features for context-dependent object categories. Even as a standalone enhancement, our image-level categorical embedding module can lead to improvements over existing region-based detectors.

Upon the image-level categorical embedding module, at the instance-level, we design a simple but effective process to generate hierarchical contextual RoI features which can be directly utilized by the region-wise detection head. Because our contextual RoI features are enhanced by image-level categorical supervisions and exploit larger contexts, they are by nature complementary to conventional RoI features, which is trained by region-based detectors and only exploits limited context. Later, the early-and-late strategies, \emph{i.e.}, feature fusion and confidence fusion, are designed to make full use of our contextual RoI features. By quantitative experiments, we demonstrate that they can be combined to further boost the classification accuracy of the detection head.

In general, our proposed HCE framework is easy to implement and is end-to-end trainable. We conduct extensive experiments on MS-COCO 2017~\cite{coco} to validate the effectiveness of our HCE framework. Without bells and whistles, our HCE framework delivers consistent accuracy improvements for almost all existing mainstream region-based detectors, including FPN~\cite{fpn}, Mask R-CNN~\cite{maskrcnn} and Cascade R-CNN~\cite{cascade}. We also conduct ablation studies to verify the effectiveness of each module involved in our HCE framework. Fig.~\ref{fig:motivation} gives the example images of the baseline method and our method, which demonstrates that our framework can effectively filter out the noisy background detections and correctly classify indistinctive objects by leveraging the context information it exploited.

\section{Related Work}

\subsection{Region-based Object Detection}
Convolutional neural networks have lead to a paradigm shift of object detection in the past decades~\cite{liu2019deep}. Among a large number of approaches, the two-stage R-CNN series~\cite{rcnn,fastrcnn,fasterrcnn,fpn,cascade} have become the leading detection framework. The pioneer work, \emph{i.e.}, R-CNN~\cite{rcnn}, extracts region proposals from image with selective search~\cite{uijlings2013selective}, and applies a convolutional network to classify each region of interests independently. Fast R-CNN~\cite{fastrcnn} improves R-CNN by sharing convolutional features among RoIs, which enables fast training and inference. Then, Faster R-CNN~\cite{fasterrcnn} advances the region proposal generation with a Region Proposal Network (RPN). RPN shares the feature extraction backbone with the detection head, which in essence is a Fast R-CNN~\cite{fasterrcnn}. Faster R-CNN is a famous two-stage detection framework, and is the foundation for many follow-up works~\cite{dai2016r,fpn}.

Over very recent years, several algorithms have been proposed to further improve the two-stage Faster R-CNN framework. For example, Feature Pyramid Networks (FPN)~\cite{fpn} constructed inherent CNN feature pyramids, which can largely improve the detection performance of small objects. Mask R-CNN~\cite{maskrcnn} extended Faster RCNN by constructing the mask branch, and boosted the performance of both object detection and instance segmentation. Cascade R-CNN~\cite{cascade} utilized multi-stage training strategy to progressively improve the quality of region proposals, and demonstrated significant gains for high quality (measured by higher IoUs) object detection. Complementary to these works, in this paper, we focus on developing a Hierarchical Context Embedding (HCE) framework to improve the \textit{classification ability} of all region-based detectors. Thanks to the simplicity and generalization ability of our HCE framework, it brings consistent and significant improvements over aforementioned leading region-based detectors, \textit{e.g.}, FPN, Mask R-CNN and Cascade R-CNN.

\subsection{Context Information for Object Detection}
In object detection, both global context~\cite{galleguillos2010context} and local context~\cite{rabinovich2007objects} are widely exploited for improving performance, especially when object appearances are insufficient due to small object size, occlusion, or poor image quality. Our work is inspired by some of previous works, but the key motivation or implementation significantly differ with these works. Next, we review several topics in object detection, which are closely related to our work.

\subsubsection{Combined Localization and Classification.} Before the era of deep learning, Harzallah \textit{et al.}~\cite{harzallah2009combining} proposed to combine two closely related tasks, \textit{i.e.}, object localization and image classification. They demonstrated that classification can improve detection by a contextual combination and vice versa. Similar in spirit, we utilize the fully image-level context to learn object-level concepts. But differently, we utilize global context to learn CNN features rather than hand-crafted features adopted in~\cite{harzallah2009combining}. Furthermore, we integrate hierarchical contextual clues beneath both whole images and interested regions to modern region-based CNN detectors, rather than the traditional sliding window detector used by~\cite{harzallah2009combining}.

\subsubsection{Region Proposal Refinement.} Recently, Chen \textit{et al.}~\cite{context} explored the rich contextual information to refine the region proposals for object detection. The neighboring regions with useful contexts can benefit the localization quality of region proposals, which further lead to better detection performance. Instead of refining proposals, we focus on improving the \textit{classification ability} of region-based detectors by embedding hierarchical contextual clues.

\subsubsection{Weakly-Supervised Object Detection.}
In weakly supervised object detection, the bounding box annotations are not provided, and only image-level categorical labels are available. The common practice~\cite{cinbis2016weakly,weakly,bilen2015weakly,kantorov2016contextlocnet} in this area is to first generate a set of noisy object proposals, and then learn from these noisy proposals with specially designed robust algorithms. Among them, Kantorov \textit{et al.}~\cite{kantorov2016contextlocnet} proposed a context-aware deep network which leverages the surrounding context regions to improve localization. Unlike the usage of region-level context information~\cite{kantorov2016contextlocnet} for weakly supervised detection, we focus on the task of fully-supervised object detection, and particularly exploit global image-level context to advance the recognition of context-dependent object categories.

\subsection{Context Information for Other Vision Tasks}
Beyond object detection, context information has also been utilized to improve other vision tasks. For example, Wang \textit{et al.}~\cite{rnn_attention} leveraged attention mechanisms and LSTMs to discover semantic-aware regions and capture the long-range contextual dependencies for multi-label image recognition. He \textit{et al.}~\cite{adaptive} proposed an adaptive context module to generate multi-scale context representations for semantic segmentation. Qu \textit{et al.}~\cite{deshadownet} embedded multi-context information (the appearance of the input image and semantic understanding) to obtain the shadow matte. Byeon \textit{et al.} ~\cite{contextvp} leveraged the LSTM units to capture the entire available past context on video prediction. Li \textit{et al.}~\cite{derain}  adopted the dilated convolution to acquire more contextual information for single image deraining.

\section{Approach}

\subsection{Framework Overview}
We begin by briefly describing our Hierarchical Context Embedding (HCE) framework (see Fig.~\ref{fig:model}) for region-based object detection. Firstly, an image-level categorical embedding module is employed to advance the feature learning of the objects that are highly dependent on larger context clues. Then, hierarchical contextual RoI features are generated by fusing both instance-level and global-level information derived from the image-level categorical embedding module. Finally, early-and-late fusion modules are designed to make full use of the contextual RoI features to improve the classification performance. Our HCE framework is flexible and generalizable, as it can be applied as a plug-and-play component for almost all mainstream region-based object detectors.

\begin{figure}[t]
	\centering
	\includegraphics[width=1.0\textwidth]{figs/model.pdf}
	\caption{Overview of our Hierarchical Context Embedding (HCE) framework.
	At the image-level, we design an \emph{image-level categorical embedding} module upon the detection backbone, which enables the network to learn object-level concepts from global-level context. At the instance-level, we generate \emph{hierarchical contextual RoI features} that are complementary to conventional RoI features, and design the early-and-late fusion strategies (\emph{i.e.}, \emph{feature fusion} and \emph{confidence fusion}) to make full use of the contextual RoI features for improving the classification accuracy of the detection head.
	}
	\label{fig:model}
\end{figure}

\subsection{Image-Level Categorical Embedding}

As aforementioned, conventional RoI-based training for region-based detectors may lack the context information, which is crucial for learning discriminative filters for context-dependent objects. To break this limitation, in parallel with the RoI-based branch, we exploit image-level categorical embedding upon the detection backbone, enabling the backbone to learn object-level concepts adaptively from \textit{global-level} context.
Our image-level categorical embedding module does not require additional annotations, as the image-level labels can be conveniently obtained by collecting all instance-level categories in an image.

Essentially, our image-level categorical embedding module is based on a multi-label classifier. As shown in Fig.~\ref{fig:model} and Fig.~\ref{fig:module} (a), we first apply a $3 \times 3$ convolution layer on the output of ResNet conv$_5$ to obtain the input feature map, and then employ both global max-pooling (GMP) and global average-pooling (GAP) for feature aggregation (as in~\cite{woo2018cbam}). Here, the additional $3 \times 3$ convolution layer aims to alleviate the possible slide effects over the original detection backbone.

We refer to the input feature map to our image-level embedding module as \emph{context-embedded image feature}. This is because the input feature map conveys whole image context for learning all object categories that appear in the image, and in turn, each location of the feature map is supervised by all object categories. By contrast, conventional RoI-based trained by region-based detectors only exploits limited context for learning each object category.

Formally, let $\bm{X} \in \mathbb{R}^{d \times h \times w}$ denote the input feature map, where $d$ is the channel dimensionality, $h$ and $w$ are the height and width, respectively. Then, the multi-label classifier is constructed by $C$ binary classifiers for all categories:
\begin{equation}
	\hat{\bm{y}}_{cls} = f_{cls}((f_{gmp}(\bm{X}) + f_{gap}(\bm{X}))) \in \mathbb{R}^{C} \,,
\end{equation}
where $C$ denotes the number of categories, each element of $\hat{\bm{y}}_{cls}$ is a confidence score (logits), and $f_{cls}$ is binary classifier modeled as one fully-connected layer. We assume that the ground truth label of an image is $\bm{y} \in \mathbb{R}^{C}$, where $y^{i} = \{0, 1\}$ denotes whether object of category $i$ appears in the image or not. The multi-label loss can be formulated as follows

\begin{equation}
	\mathcal{L}_{mll}= - \sum_{c=1}^{C}y^{c}\log(\sigma(\hat{y}^{c}_{cls})) + (1-y^{c})\log(1-\sigma(\hat{y}^{c}_{cls})) \,,
\end{equation}
where $\sigma(\cdot)$ is the sigmoid function.

\begin{figure}[t]
	\centering
	\subfloat[Image-level categorical embedding.] {\includegraphics[width=0.48\columnwidth]{figs/image_level_embedding.pdf} }
	\subfloat[Hierarchical contextual RoI feature.]  {\includegraphics[width=0.48\columnwidth]{figs/roi_generation.pdf} }
	\caption{The design of our image-level categorical embedding module and hierarchical contextual RoI feature generation module.}
	\label{fig:module}
\end{figure}

Because the global feature learning strategy is complementary to RoI-based training, our image-level categorical embedding module standalone can boost the performance of existing region-based detectors (demonstrated later by experiments, cf. Table~\ref{table:context}). However, one limitation of image-level categorical embedding might be that the derived context-embedded image feature can not be directly used by the detection head.

\subsection{Hierarchical Contextual RoI Feature Generation}

To further benefit region-wise classification, we generate hierarchical contextual RoI features by combining the instance-level and global-level information from the context-embedded image features. The hierarchical contextual RoI feature generation process is shown in Fig.~\ref{fig:module} (b).

\subsubsection{Context-Embedded Instance-Level Feature}

We apply RoIAlign~\cite{maskrcnn} with proposals generated by RPN on the context-embedded feature map $\bm{X}$ to obtain RoI features $\bm{x}_{instance}$:
\begin{equation}
	\bm{x}_{instance} = f_{RoIAlign}(\bm{X}; h', w') \in \mathbb{R}^{d \times 7 \times 7} \,,
	\label{eq:instance}
\end{equation}
where $f_{RoIAlign}(\cdot)$ is the RoIAlign operation and $h'$ and $w'$ are the height and width of the RoI, respectively. As $\bm{x}_{instance}$ is extracted from the context-embedded image feature $\bm{X}$, we term it as \emph{context-embedded instance-level feature}.

\subsubsection{Context-Aggregated Global-Level Feature} To leverage larger context, we exploit RoIAlign on the context-embedded image feature $\bm{X}$ to aggregate the global-level context. We refer to the derived RoI feature as \emph{context-aggregated global-level feature} $\bm{x}_{global}$:
\begin{equation}
	\bm{x}_{global} = f_{RoIAlign}(\bm{X}; H, W) \in \mathbb{R}^{d \times 7 \times 7} \,,
	\label{eq:global}
\end{equation}
where $H$ and $W$ are the height and width of the input image, respectively.

Once context-embedded instance-level feature $\bm{x}_{instance}$ and context-aggregated global-level feature $\bm{x}_{global}$ obtained, we concatenate these two RoI features and apply a $1 \times 1$ convolution layer to obtain our hierarchical contextual RoI feature $\bm{x}_{context}$:
\begin{equation}
	\bm{x}_{context} = f_{conv}([\bm{x}_{instance} : \bm{x}_{global}]) \in \mathbb{R}^{d \times 7 \times 7} \,,
\end{equation}
where $f_{conv}(\cdot)$ denotes the $1 \times 1$ convolution operation, $[:]$ refers to concatenation and the ReLU nonlinearity operations are performed following the convolution layer. As the resulting hierarchical contextual RoI feature $\bm{x}_{context}$ absorbs rich context information from the context-embedded image feature $\bm{X}$, it is by nature complementary to the conventional RoI feature extracted from the feature pyramid network (FPN)~\cite{fpn}.

\subsection{Early-and-Late Fusion and Inference}

To make full use of our contextual RoI feature $\bm{x}_{context}$, we design the early-and-late fusion strategies, \emph{i.e.}, feature fusion and confidence fusion, which has been proven effective in many applications~\cite{gunes2005affect,ebersbach2017fusion}. We show that early-and-late fusion is also well suited to improve region-wise detectors, as it can fully absorb hierarchically embedded information from different levels.

\subsubsection{Feature Fusion} To incorporate our contextual RoI features $\bm{x}_{context}$ into region-based detection pipeline, the simplest way is fusing them with the original RoI features extracted from the feature pyramid network (FPN)~\cite{fpn} with element addition. Formally, let $\bm{x}_{FPN}$ denote the original RoI feature extracted from FPN, and $\bm{x}_{fusion}$ denote the fused RoI feature, then we have:
\begin{equation}
	\bm{x}_{fusion} = \bm{x}_{context} + \bm{x}_{FPN} \in \mathbb{R}^{d \times 7 \times 7}.
\end{equation}

As shown in Fig.~\ref{fig:model}, the fused feature map $\bm{x}_{fusion}$ is then fed into the 2$fc$ detection head to produce refined bounding boxes and classification scores.

\subsubsection{Confidence Fusion} We also consider a simple confidence fusion strategy which is complementary to feature fusion. We apply the 2$fc$ head on our hierarchical contextual RoI feature $\bm{x}_{context}$ to produce a classification confidence (logits), and then fuse it with that from the corresponding FPN RoI feature $\bm{x}_{FPN}$ by addition. Formally, let $\hat{\bm{y}}_{fusion}$ denote the fused the confidence:
\begin{equation}
	\hat{\bm{y}}_{fusion} = f_{2fc}(\bm{x}_{context}) + f_{2fc}(\bm{x}_{FPN}) \in \mathbb{R}^{C}.
\end{equation}
The fused confidence is transformed by a soft-max layer to produce a novel classification score.

For each proposal, the classification score $\hat{\bm{y}}_{fusion}$, paired with the refined bounding box predicted the FPN RoI feature, forms another prediction in parallel with the prediction from the feature fusion branch. It is worth mentioning that the weights of the 2$fc$ head applied on different RoI features are shared.

\subsubsection{Inferences} Our early-and-late fusion strategy produces two different predictions for a single object proposal. To obtain the final result, as shown by the pipeline in Fig.~\ref{fig:model}, we firstly collect all the boxes and confidences from two prediction branches (\emph{i.e.}, feature fusion and confidence fusion), and then perform NMS over all these boxes. Furthermore, as demonstrated later in experiments, while our two fusion strategies are complementary during training, using only one prediction branch during inference will not cause obvious performance drop but reduce computational cost. However, the performance by only using one fusion strategy for training is inferior to that by using two fusion strategies together.

\subsubsection{Loss Function}
The whole network is trained end-to-end, and the overall loss is computed as follows:
\begin{equation}
	\mathcal{L} = \mathcal{L}_{feat} + \mathcal{L}_{conf} + \mathcal{L}_{mll} + \mathcal{L}_{rpn} \,,
\end{equation}
where $\mathcal{L}_{feat}$ and $\mathcal{L}_{conf}$ are the losses for the feature fusion and confidence fusion branches, respectively. All loss terms are considered equally important, without extra hyper-parameters to characterize the trade-off between them, which reveals HCE is generalized and not tricky.

\section{Experiments}
We conduct extensive experiments on the MS-COCO 2017 dataset~\cite{coco} to demonstrate the effectiveness and generalization ability of our hierarchical context embedding framework.
MS-COCO 2017 is the most popular benchmark for general object detection, which contains 80 object categories, 118K images for training, 5K images for validation (\texttt{val}) and 20K for testing (\texttt{test-dev}).
We report the standard COCO-style Average Precision (AP) with different IoU thresholds from 0.5 to 0.95 with an interval of 0.05 as metric. All models are trained on COCO training set and evaluate on the \texttt{val} set. For fair comparisons with the state-of-the-art, we also report the results on the \texttt{test-dev} set.

\subsection{Implementation Details}

We implement our method and re-implement all baseline methods based on MMDetection codebase~\cite{mmdetection}. The re-implementations of the baselines strictly follow the default settings of MMDetection. Images are resized such that the short edge has 800 pixels while the long edge has less than 1333 pixels. We use no data augmentation except horizontal flipping for training. The ResNet is exploited as backbone, which is pre-trained on ImageNet~\cite{imagenet}. Models are trained in a batch size of 16 on 8 GPUs. We train all models with SGD optimizer for 12 epochs in the total, with the initial learning rate as 0.02 and decreased by a factor of 0.1 at 8th epoch and 11th epoch. Weight decay and momentum are set as 0.0001 and 0.9, respectively. We also adopt the linear warming up strategy to begin the training of our model.

\subsection{Comparisons with Baselines}

\begin{table}[t]
\centering
\setlength{\tabcolsep}{1.3mm}
\caption{Compared with baselines (FPN~\cite{fpn}, Mask R-CNN~\cite{maskrcnn} and Cascade R-CNN~\cite{cascade}) on MS-COCO 2017 \texttt{val}. ``HCE'' denotes that the models are trained and inferred on both feature fusion and confidence fusion.
Clearly, our HCE framework achieves consistent accuracy gains overall all baseline detectors on all evaluation metrics.
}
\begin{tabular}{c|c|c|ccc|ccc}
\hline
Backbone                         & Method & HCE  & AP   & AP$^{50}$ & AP$^{75}$ & AP$^{S}$ & AP$^{M}$ & AP$^{L}$ \\
\hline
\multirow{6}{*}{ResNet-50-FPN}   & \multirow{2}{*}{FPN} & & 36.3 & 58.3 & 39.1 & 21.6 & 40.2 & 46.9 \\
                                 & & \checkmark & \textbf{38.4} & \textbf{61.0} & \textbf{41.8} & \textbf{22.9} & \textbf{42.5} & \textbf{49.1} \\ \cline{2-9}
                                 & \multirow{2}{*}{Mask R-CNN}  &             & 37.3 & 59.1 & 40.3 & 22.2 & 41.1 & 48.3 \\
                                 &  & \checkmark  & \textbf{38.8} & \textbf{61.3} & \textbf{42.1} & \textbf{23.2} & \textbf{42.8} & \textbf{49.7} \\ \cline{2-9}
                                 & \multirow{2}{*}{Cascade R-CNN} &         & 40.5 & 58.7 & 44.1 & 22.3 & 43.6 & 53.8 \\
                                 & & \checkmark & \textbf{41.7} & \textbf{60.5} & \textbf{45.0} & \textbf{23.4} & \textbf{44.9} & \textbf{55.2} \\
\hline
\multirow{6}{*}{ResNet-101-FPN}  & \multirow{2}{*}{FPN}   &      & 38.3 & 60.1 & 41.7 & 22.8 & 42.8 & 49.8 \\
                                 &  & \checkmark & \textbf{40.0} & \textbf{62.3} & \textbf{43.4} & \textbf{24.0} & \textbf{44.1} & \textbf{51.9} \\ \cline{2-9}
                                 & \multirow{2}{*}{Mask R-CNN} &           & 39.4 & 60.9 & 43.0 & 23.3 & 43.7 & 51.5 \\
                                 &  & \checkmark & \textbf{40.5} & \textbf{62.6} & \textbf{44.0} & \textbf{24.4} & \textbf{44.5} & \textbf{53.4} \\ \cline{2-9}
                                 & \multirow{2}{*}{Cascade R-CNN} & & 41.9  & 60.1 & 45.7 & 23.2 & 45.9 & 56.2 \\
                                 &   & \checkmark & \textbf{43.0} & \textbf{61.6} & \textbf{46.9} & \textbf{24.6} & \textbf{46.6} & \textbf{57.4} \\
\hline
\end{tabular}
\label{table:baseline}
\end{table}

To demonstrate the generality of our HCE framework, we consider three well-known region-based object detectors as our baseline systems, including Feature Pyramid Network (FPN)~\cite{fpn}, Mask R-CNN~\cite{maskrcnn} and Cascade R-CNN~\cite{cascade}. All detectors are instantiated with two different backbones, \emph{i.e.}, ResNet-50 and ResNet-101 with FPN. Integrating our framework with Mask R-CNN and Cascade R-CNN is as straightforward as with FPN. For example, we apply our framework within each training stage of Cascade R-CNN.

Comparison results on MS-COCO 2017 \texttt{val} are shown in Table~\ref{table:baseline}. Our HCE framework achieves consistent accuracy gains overall all baseline detectors on all evaluation metrics. Specifically, without the bells and whistles, our method improves 2.1\% and 1.7\% AP for FPN with ResNet-50 and ResNet-101 backbones, respectively. While for more advanced Mask R-CNN and Cascade R-CNN, our method also brings more than 1\% AP improvement on both ResNet-50 and ResNet-101 backbones, \textit{e.g.,} improving the AP for Mask R-CNN with ResNet-50-FPN from 37.3\% to 38.8\%.

Additionally, it can be observed that our improvements for Mask R-CNN and Cascade R-CNN baselines are not as significant as FPN. We conjecture that this is because Mask R-CNN and Cascade R-CNN themselves integrate mechanisms for better feature learning, which might overlap with the performance gains with our method. Specifically, Mask R-CNN benefits from extra accurate instance-level mask supervisions, while Cascade R-CNN enjoys IoU-specific multi-stage training to progressively refine object proposals and learn discriminative features for IoU-specific proposals. However, even in these cases, our method can also obtain $+1\%$ AP improvement over these competing baseline methods.

\subsection{Error Analyses}

\begin{figure}[t!]
	\centering
	\includegraphics[width=1.0\textwidth]{figs/error.pdf}
	\caption{Error Analyses: These illustrations show the percentage of different error types in the top N detections (N = \# objects in that category).}
	\label{fig:error}
\end{figure}

In the following, we perform error analyses to further understand in what aspects our HCE framework improves the region-based object detectors.
Following the settings of~\cite{yolo}, we choose the top N predictions for each category during inference time. Each prediction is classified based on the type of error:
\begin{itemize}
	\item Correct: correct class and IOU $>$ 0.5
	\item Location Error: correct class and 0.1 $<$ IOU $<$ 0.5
	\item Background Error: IOU $<$ 0.1 for any object
	\item Classification Error: class is wrong and IOU $>$ 0.5
	\item Other: class is wrong and 0.1 $<$ IOU $<$ 0.5
\end{itemize}

We compare different error types between the FPN baseline and our method with ResNet-50 as backbone on MS-COCO 2017 \texttt{val}. Fig.~\ref{fig:error} shows the results of each error type averaged across all 80 categories, and each error type for ``\texttt{hot dog}'', ``\texttt{snowboard}'' and ``\texttt{baseball glove}'' which are highly dependent on context information. Obviously, our method can effectively improve the classification ability of region-based detector and reduce the background errors to a large extent, without compromising the localization performance or increasing other type of errors. Our improvements are particularly noticeable for context-dependent object categories. For example, the (normalized) correctly recognized instances of ``\texttt{hot dog}'' increase from 44.8\% to 51.2\%, while the background false positive detections reduce from 17.6\% to 14.4\%. These observations validate that our HCE framework can indeed improve the classification ability.

\subsection{Ablation Studies}
In this section, we conduct three series of ablation experiments to analyze the proposed method, using ResNet-50 as backbone on MS-COCO 2017 \texttt{val}.

\subsubsection{Context Embedding Operations}
We first investigate the impacts of different context embedding operations in our HCE framework. Specifically, there are three context embedding operations involved in our framework. Firstly, the image-level categorical embedding module employs multi-label learning (denoted as ``MLL'') to embed global-level context to advance the learning of context-dependent categories. Then, for further improving region-based classification, both the context-embedded instance-level feature (denoted as ``Instance'') and the context-aggregated global-level feature (denoted as ``Global'') are combined to generate hierarchical contextual RoI feature.

Table~\ref{table:context} shows the performance improvements by progressively integrating more context embedding operations. Solely applying MLL on the detection backbone gives $0.5\%$ AP improvement. This verifies that image-level categorical embedding advances the feature learning for context-dependent object categories.
Then, the context-embedded instance-level feature which can be directly utilized by the detection head brings another $1.0\%$ AP improvement. Finally, global-level context embedding for contextual RoI feature improves $0.6\%$ AP. These results suggest that the context embedding operations in our framework are complementary with each other.

\begin{table}[t]
\centering
\setlength{\tabcolsep}{2.8pt}
\caption{Impacts of different context embedding operations on MS-COCO 2017 \texttt{val}. ``MLL'' means we leverage the image-level categorical embedding module to advance the learning of context-dependent categories. ``Instance'' and ``Global'' denotes that we utilize instance-level (cf. Eq~(\ref{eq:instance})) or global-level (cf. Eq~(\ref{eq:global})) contextual features to further improve the region-wise detection head.}
\begin{tabular}{c|ccc|ccc|ccc}
\hline
Method                        & MLL & Instance    & Global    & AP   & AP$^{50}$ & AP$^{75}$ & AP$^{S}$  & AP$^{M}$ & AP$^{L}$ \\
\hline
\multirow{4}{*}{FPN} &             &            &            & 36.3 & 58.3 & 39.1 & 21.6 & 40.2 & 46.9 \\
                                  & \checkmark  &            &            & 36.8 & 58.9 & 39.7 & 21.9 & 40.5 & 47.2 \\
                                  & \checkmark  & \checkmark &            & 37.8 & 59.9 & 40.9 & 22.2 & 41.4 & 48.9 \\
                                  & \checkmark  & \checkmark & \checkmark & \textbf{38.4} & \textbf{61.0} & \textbf{41.8} & \textbf{22.9} & \textbf{42.5} & \textbf{49.1} \\
\hline
\end{tabular}
\label{table:context}
\end{table}

\begin{table}[t]
\centering
\setlength{\tabcolsep}{5pt}
\caption{Effects of different fusion strategies during \textit{training}, evaluated by detection performance on MS-COCO 2017 \texttt{val}. The models share the same backbone network ResNet50-FPN. ``FF Train'' means that we apply feature fusion (FF) for training, while ``CF Train'' means confidence fusion (CF) are applied for training.}
\begin{tabular}{c|cc|ccc|ccc}
\hline
Method                            & FF Train   & CF Train & AP   & AP$^{50}$ & AP$^{75}$ & AP$^{S}$  & AP$^{M}$ & AP$^{L}$ \\
\hline
\multirow{4}{*}{FPN} &            &             & 36.8 & 58.9 & 39.7 & 21.9 & 40.5 & 47.2 \\
                                  & \checkmark &             &  37.6 & 60.3 & 40.7 & 22.5 & 41.4 & 48.2\\
                                  &            & \checkmark  &
                                  37.4 & 60.2 & 40.1 & 23.0 & 41.1 & 47.6\\
                                  & \checkmark & \checkmark  & \textbf{38.4} & \textbf{61.0} & \textbf{41.8} & \textbf{22.9} & \textbf{42.5} & \textbf{49.1} \\
\hline
\end{tabular}
\label{table:head}
\end{table}

\begin{table}[t]
\centering
\setlength{\tabcolsep}{4pt}
\caption{Effects of different fusion strategies in testing, which are evaluated by the inference time and detection performance on MS-COCO 2017 \texttt{val}. Note that all models are trained with both fusion strategies. ``FF Test'' denotes that we evaluate the feature fusion (FF) strategy during inference, while ``CF Test'' means the results are evaluated by confidence fusion (CF) strategy. Inference speed is evaluated on a single 1080ti GPU.}
\begin{tabular}{c|cc|c|ccc|ccc}
\hline
Method                            & FF Test & CF Test & Speed & AP   & AP$^{50}$ & AP$^{75}$ & AP$^{S}$ & AP$^{M}$ & AP$^{L}$ \\
\hline
\multirow{4}{*}{FPN}  &                  &                & 0.087s & 36.3 & 58.3 & 39.1 & 21.6 & 40.2 & 46.9 \\
                                   & \checkmark       &                & 0.090s & 38.2 & 60.8 & 41.5 & 22.6 & 42.2 & 49.0 \\
                                   &                  & \checkmark     & 0.094s & 38.3 & 60.8 & 41.6 & 22.8 & 42.3 & 49.0 \\
                                   & \checkmark       & \checkmark     & 0.100s & \textbf{38.4} & \textbf{61.0} & \textbf{41.8} & \textbf{22.9} & \textbf{42.5} & \textbf{49.1} \\
\hline
\end{tabular}
\label{table:test}
\end{table}

\subsubsection{Fusion Strategies in Training}
We consider the proposed two fusion strategies, feature fusion and confidence fusion, are complementary to each other. To verify this, we evaluate the performance by training the model with feature fusion and confidence fusion individually, as well as both of them. Table~\ref{table:head} shows the results of different fusion strategies. Specifically, ``FF Train" means that we apply feature fusion (FF) for training, while ``CF Train" means confidence fusion (CF) are applied for training. Utilizing feature fusion and confidence fusion individually for training can outperform the baseline (FPN with MLL) by $0.8\%$ and $0.6\%$ AP, respectively. Training with both fusion strategies achieves the best result, and is clearly better than using each individual fusion strategy separately.

\subsubsection{Fusion Strategies in Testing}
We also evaluate each fusion strategy independently during inference, with all HCE models trained with both fusion strategies. Table~\ref{table:test} shows the results of each fusion strategy and the combined fusion strategies. ``FF Test'' denotes that we evaluate the feature fusion (FF) strategy during inference, while ``CF Test'' means that the results are evaluated by confidence fusion (CF) strategy. We can see that once the model is trained with both fusion strategies, using only one fusion branch for inference will not cause obvious accuracy drop, but brings computational economy. For example, using the feature fusion branch for inference adds very minimal time cost (0.003s) to the baseline, but increases the AP from 36.3\% to 38.2\%. These results also prove the complementarity of the proposed two fusion strategies.

\begin{table}[t]
\centering
\setlength{\tabcolsep}{1pt}
\caption{Comparisons with the state-of-the-art single-model detectors on MSCOCO 2017 \texttt{test-dev}. ``*'' denotes using tricks (with bells and whistles) during inference.}
\begin{tabular}{c|c|cccccc}
\hline
Method                                           & Backbone                 & AP   & AP$^{50}$ & AP$^{75}$ & AP$^{S}$  & AP$^{M}$ & AP$^{L}$ \\
\hline
YOLOv3~\cite{yolov3}                             & Darknet-53               & 33.0 & 57.9 & 34.4 & 18.3 & 35.4 & 41.9 \\
SSD513~\cite{ssd}                                & Res101                   & 31.2 & 50.4 & 33.3 & 10.2 & 34.5 & 49.8 \\
RetinaNet~\cite{focalloss}                       & Res101-FPN               & 39.1 & 59.1 & 42.3 & 21.8 & 42.7 & 50.2 \\
FCOS~\cite{fcos}                                 & Res101-FPN               & 41.5 & 60.7 & 45.0 & 24.4 & 44.8 & 51.6 \\
\hline
FPN~\cite{fpn}                                   & Res101-FPN               & 36.2 & 59.1 & 39.0 & 18.2 & 39.0 & 48.2 \\
Mask R-CNN~\cite{maskrcnn}                       & Res101-FPN               & 38.2 & 60.3 & 41.7 & 20.1 & 41.1 & 50.2 \\
Cascade R-CNN~\cite{cascade}                     & Res101-FPN               & 42.8 & 62.1 & 46.3 & 23.7 & 45.5 & 55.2 \\
Deformable R-FCN*~\cite{deformable}              & Aligned-Inception-ResNet & 37.5 & 58.0 & 40.8 & 19.4 & 40.1 & 52.5 \\
DCNv2*~\cite{dv2}                                & Res101-DeformableV2      & 46.0 & \textbf{67.9} & \textbf{50.8} & \textbf{27.8} & 49.1 & \textbf{59.5} \\
IoU-Net~\cite{iounet}                            & Res101-FPN               & 40.6 & 59.0 & --   & --   & --   & --   \\
TridentNet~\cite{trident}                        & Res101                   & 42.7 & 63.6 & 46.5 & 23.9 & 46.6 & 56.6 \\
Cascade +Rank-NMS~\cite{ranking}                 & Res101-FPN               & 43.2 & 61.8 & 47.0 & 24.6 & 46.2 & 55.4 \\
\hline
HCE FPN                                      & Res101-FPN               & 41.0 & 63.5 & 44.7 & 23.4 & 44.2 & 52.2 \\
HCE Mask R-CNN                               & Res101-FPN               & 41.6 & 63.9 & 45.4 & 23.7 & 44.7 & 53.1 \\
HCE Cascade R-CNN                            & Res101-FPN               & 44.1 & 63.2 & 47.9 & 25.2 & 46.9 & 57.0 \\
HCE Cascade R-CNN*                           & Res101-FPN               & \textbf{46.5} & 65.6 & 50.6 & 27.4 & \textbf{49.9} & 59.4 \\
\hline
\end{tabular}
\label{table:soa}
\end{table}

\subsection{Comparisons with State-of-the-art}
We compare our proposed method with state-of-the-art on MS-COCO 2017 \texttt{test-dev}. For fair comparisons, we report the performance of all methods with single-model inference. Specifically, we apply our method on FPN, Mask R-CNN and Cascade R-CNN in 2$\times$ training scheme without bells and whistles. Table~\ref{table:soa} shows all comparison results.

Our hierarchical context embedding framework, when integrated with FPN, Mask R-CNN and Cascade R-CNN object detectors, consistently outperforms state-of-the-art object detectors using the same backbone network. For fairly comparisons with Deformable R-FCN* and DCNv2* which adopt multi-scale 3x training scheme and multi-scale testing, we follow the same experimental setting to train our HCE Cascade R-CNN*. It gives an AP of 46.5\%, which surpasses R-FCN* and DCNv2*. These results demonstrate the superior performance of the proposed context embedding framework.

\section{Conclusions}

In this paper, we investigated the limitation of context information on conventional region-based detectors, and proposed a novel and effective Hierarchical Context Embedding (HCE) framework to facilitate the classification ability of current region-based detectors. Comprehensive experiments demonstrated the consistent outperforming accuracy on almost all existing mainstream region-based detectors, include FPN, Mask R-CNN and Cascade R-CNN. In the future, we will concentrate in extending the usage scope of our HCE framework and adapting it to one-stage detection paradigm.\\

\noindent
\textbf{Acknowledgements}:
Z.-M. Chen's contribution was made when he was an intern in Megvii Research Nanjing. This research was supported by the National Key Research and Development Program of China under Grant 2017YFA0700800, the National Natural Science Foundation of China under Grants 61772257 and  the Fundamental Research Funds for the Central Universities 020914380080.

\clearpage
\bibliographystyle{splncs04}