# Semantic Foundations of Seraph Continuous Graph Query Language

Emanuele Falzone<EMAIL_ADDRESS>Politecnico di Milano ,  Riccardo
Tommasini<EMAIL_ADDRESS>University of Tartu ,  Emanuele Della
Valle<EMAIL_ADDRESS>Politecnico di Milano ,  Petra Selmer
<EMAIL_ADDRESS>Neo4j ,  Stefan Plantikow<EMAIL_ADDRESS>Neo4j ,  Hannes Voigt<EMAIL_ADDRESS>Neo4j ,  Keith Hare
<EMAIL_ADDRESS>Neo4j ,  Ljubica Lazarevic<EMAIL_ADDRESS>Neo4j and  Tobias Lindaaker<EMAIL_ADDRESS>Neo4j

###### Abstract.

The scientific community has been studying graph data models for decades.
Their high expressiveness and elasticity led the scientific community to
design a variety of graph data models and graph query languages, and the
practitioners to use them to model real-world cases and extract useful
information. Recently, property graphs and, in particular, Cypher 9 (the first
open version of the well-known Neo4j Inc.’s language) are gaining popularity.
Practitioners find Cypher useful and applicable in many scenarios. However, we
are living in a streaming world where data continuously flows. A growing
number of Cypher’s users show interest in continuously querying graph data to
act in a timely fashion. Indeed, Cypher lacks the features for dealing with
streams of (graph) data and continuous query evaluation. In this work, we
propose Seraph, an extension of Cypher, as a first attempt to introduce
streaming features in the context of property graph query languages.
Specifically, we define Seraph semantics, we propose a first version of Seraph
syntax, and we discuss the potential impacts from a user perspective.

##  1\. Introduction

In the near future, graph processing systems and languages will have to
address several challenges like the combination of different workloads,
scalability beyond existing boundaries, and the need for new abstractions for
querying and analysing (DBLP:journals/corr/abs-2012-06171). In particular, we
are living in a world where data continuously flows, and users demand to
decide and act promptly to changes (DBLP:journals/expert/ValleCHF09). The
growing popularity of sensors and smart-devices is pushing the boundaries of
existing data systems. While real-time analytics is becoming central in data
science projects, new languages are emerging to allow data scientists to
express complex information needs and perform the analyses in real-time
(DBLP:journals/sigmod/HirzelBBVSV18). For instance, several streaming SQL
extensions allow writing queries that compute every minute the average number
of people crossing the road in the last 5 minutes. (DBLP:conf/edbt/0001SVJ20).
However, such SQL extensions are inadequate to deal with the connected nature
of many real-world scenarios, which, indeed, require graph data. Frequently,
in those scenarios, Data Engineers have to craft highly complex ad-hoc
solutions to perform continuous computations over streams of graphs. In
practice, a usable declarative language for graph stream processing is still
missing.

In recent years, different vendors put a lot of effort into designing graph
query languages (DBLP:journals/sigmod/Wood12; DBLP:conf/grades/RestHKMC16;
DBLP:conf/sigmod/AnglesABBFGLPPS18; DBLP:conf/sigmod/FrancisGGLLMPRS18;
DBLP:journals/tkde/SeoGL15; DBLP:conf/icpr/GiugnoS02;
DBLP:journals/csur/AnglesG08). In practice, the language ecosystem around
property graphs is flourishing, and it is the best on-ramp to the graph query
language (GQL) standard111https://www.gqlstandards.org/ being developed by
ISO. Among the others, Cypher (DBLP:conf/sigmod/FrancisGGLLMPRS18), which was
designed and implemented at Neo4j Inc. 222https://neo4j.com/ in 2011, proved
to be useful and applicable in many scenarios (cabra_2016;
drakopoulos2016evaluating; hawes2015frappe; lysenko2016representing;
robinson2013graph). Moreover, it was open-sourced in 2015 under the name of
OpenCypher333https://www.opencypher.org/ and is currently at the centre of the
standardization process. In this paper, we attack the problem of querying
streams of property graphs starting from OpenCypher. In particular, we specify
the syntax and the semantics of Seraph, a declarative language for the
continuous query evaluation over streams of property graphs, aiming at
answering the following research question:

Is it possible to compositionally extend the semantics and the syntax of
Cypher to handle streams of property graphs and continuous queries?

Outline. In Section 2, we briefly illustrate a step-by-step running example,
discussing the requirements that led to the formalization Seraph. We provide
an overview of the core of Cypher in Section 3, providing the preliminary
knowledge needed to formalize Seraph. The formal specification of the
semantics of Seraph is given in Section LABEL:section:formal-specification
together with an initial version of its syntax. A system prototype, along with
a performance evaluation, is presented in Section LABEL:section:system-
prototype. Section LABEL:section:industrial-use-cases illustrates real-world
use cases. Section LABEL:section:related-work covers related works on other
graph data models and graph query languages. Future work and conclusions are
given in Section LABEL:section:future-work and Section
LABEL:section:conclusions, respectively.

(a)

(b)

(c)

Figure 1. Stream of graphs representing the events captured into the Kafka
Hospital Deployment. Figure 2. Graph resulting from loading of the events from
9:12 AM to 9:36 AM into a Neo4j instance.

##  2\. Seraph by example

In this section, we introduce a running example, discussing the language
requirements that led to the formalization of the syntax and semantics of
Seraph.

The Princeton–Plainsboro Teaching Hospital (PPTH) is known as one of the
hospitals with the lowest mortality rate. To protect both patients and
hospital personnel, it has a series of strict policies to prevent the
diffusion of viruses inside the buildings. Such policies are continuously
revised, and Dr. Lisa Cuddy, the hospital’s head administrator, continuously
searches for new tools and methodologies that can contribute towards her goal.

Recently, she realizes that a system able to track the contacts between
infected patients and hospital personnel would be very efficient for
prevention. Indeed, identifying hospital operators that, in the last 4 hours,
have been in contact with a patient that tested positive for a specific virus
would be very useful: such operators would then be tested for the virus at the
beginning of the next shift. Considering the high transmissibility and
potential damage of viruses, Dr. Lisa Cuddy requires such information to be
computed in real-time to notify the hospital operator about the possible
infection. Such operators are required to objectively evaluate the risk and
adopt countermeasures to prevent the virus’s diffusion.

PPTH uses a complex system, Galileo, that assists each hospital operator in
daily routines and collects information about every event inside the hospital.
In particular, it stores every event in the form of property graphs inside the
Kafka Hospital Deployment (KHD).

The timeline reported in Figure 1 illustrates the events collected by Galileo
from 9:12 AM to 9:36 AM. Let us discuss the events in detail.

  * •

9:12 AM As typically happens in hospitals, nurses administrate medicines to
patients. Chase, a recently employed nurse, gives Aaron a dose of Cortisol.
Figure 1(a) depicts the graph representing such an event.

  * •

9:36 AM Patients are periodically tested for viruses for both diagnosis and
prevention purposes. Aroon tested positive for a Norovirus. Figure 1(b)
depicts the graph representing such an event.

  * •

9:28 AM Allison, an experienced doctor, Dr. Gregory House, a genius
diagnostician, and Chase are having a differential diagnosis meeting. Figure
1(c) depicts the graph representing such an event.

Unfortunately, Galileo is not able to track the contacts between infected
patients and hospital personnel. Consequently, Dr. Lisa Cuddy asks Elliot
Alderson, the lead data scientist, to investigate a solution. As a first step,
Elliot asks Angela Moss, a member of the data engineering team, to load the
events from 9:12 AM to 9:36 AM into a Neo4j instance, obtaining the graph
reported in Figure 2.

Then, with the help of Dr. House, Elliot designed a Cypher query that
retrieves the people to be tested for diseases. Dr. House realized that it is
not sufficient to retrieve the people that administer medicine to infected
patients. Due to the high transmissibility of the viruses, the colleagues, who
have been in contact with the potentially infected hospital operator, have to
be tested for the viruses.

⬇

1MATCH (i:Patient)-[:TESTED_FOR {positive:true}]->(v:Virus),

2 (p:Person)-[:ADMINISTERS|IS_WITH*1..3]-(i)

3RETURN DISTINCT p.name, v.name

Figure 3. Cypher query to retrieve the hospital personnel to be tested for
viruses.

Consider the query reported in Figure 3. Line 1 exploits the MATCH clause to
retrieve the patients i that tested positive for a virus v. Line 2 uses a
variable-length path on ADMINISTERS and IS_WITH relationships to match the
people p to match the people that the infected patient i may have met.
Finally, Line 3 uses the RETURN clause to project the name of the virus v and
the name of the people p to be tested for such a virus. Table 1 reports the
result of the query evaluation. As expected, both Chase, Allison, and House
should be tested for the Norovirus.

"Person" |  "Virus"
---|---
"Chase" |  "Norovirus"
"House" |  "Norovirus"
"Allison" |  "Norovirus"
Table 1. Results of the Cypher query evaluation.

Elliot is now provided with the query that computes the information need.
However, there are aspects of the data pipeline that Elliot cannot directly
configure. Indeed, the query has to be continuously evaluated on the events
triggered in the last 4 hours. Moreover, Elliot expects the results to be
computed as soon as the underlying data is available. In particular, he wants
to get Chase returned at 9:28 AM and Allison and House at 9:36 AM. Usually,
Elliot relies on Angela to configure such aspects of the data pipeline.

However, Angela acts like a bottleneck: every time Elliot has a new
information need, he has to wait for Angela to deploy and configure the data
pipeline. Elliot would like to have the ability to manage these aspects
through the query language directly. In this way, Elliot would no longer
depend on Angela. Moreover, Angela could spend all her time taking care of the
management of the technological infrastructure.

Elliot and Angela worked together on a solution. They envision an expressive
language that is provided with:

  1. R1

Precise control on data ingestion from the event stream. The language should
offer operators that easily specify the input stream and the input stream’s
portion to consider.

  2. R2

Precise control on evaluation time instant. The language should offer
operators that intuitively allow for the specification of the evaluation time
instants.

  3. R3

Precise control on output processing and emitting phase. The language should
offer operators that allow for processing the output and for specifying the
output stream where the result should be pushed.

Moreover, to design a generic, easy to use solution, the language should
fulfill the following requirements:

  1. R4

Ease of specification. The language should allow for a declarative and easy
specification of the information need.

  2. R5

Backwards compatibility. It should be possible to use an existing Cypher query
to express the information need.

  3. R6

Generalization and specialization. The language should allow a sufficient
level of generality to be automatically applied for different data schema
while allowing specialization on any given domain.

###  2.1. Solving the problem with Seraph

Seraph aims at solving the problems discussed in the previous section. To this
extent, Seraph builds upon the continuous-evaluation paradigm
(DBLP:journals/vldb/ArasuBW06), which, as a consequence, influences the
definition of Seraph query language. We go in-depth into the semantics of
Seraph in Section LABEL:section:formal-specification, but here we provide some
intuitions about it. The sense of this choice is that the continuous
evaluation can be viewed, at least when specifying the semantics, as a
sequence of instantaneous evaluations (DBLP:conf/sigmod/TerryGNO92).
Therefore, given a fixed time instant, the operators can work in a time-
agnostic way composing the semantics of Cypher in the one of Seraph.

The extension that we need to introduce is threefold:

  * •

Window operators. We need to let the Cypher operators process time-changing
data, introducing window operators able to select a portion of the graphs
contained in the stream (R1,R4,R6).

  * •

Streaming operators. We need to work on the query’s output to generate streams
as output by introducing a new class of streaming operators that take as input
time-varying tables and produce sequences of timestamped tables (R3,R4,R6).

  * •

Continuous evaluation semantics. We need to extend the one-time Cypher
semantics (R5), defining the sequence of the evaluation time instants (R2),
and composing Seraph semantics with Cypher one, i.e., building Seraph
evaluation around the evaluation process of Cypher (R4,R6).

Elliot, exploiting Seraph capabilities, can compute the hospital personnel to
be tested for viruses. The Seraph query depicted in Figure 4 continuously
monitors the people to be tested.

⬇

1REGISTER QUERY people_to_be_tested {

2 FROM STREAM kafka://event-topic

3 STARTING FROM Latest

4 WITH WINDOW RANGE PT4H

5 MATCH

6 (i:Patient)-[:TESTED_FOR {positive:true}]->(v:Virus),

7 (p:Person)-[:ADMINISTERS|IS_WITH*1..3]-(i)

8 RETURN DISTINCT p.name,

9 v.name

10 EMIT ON ENTERING EVERY 1 Event

11 INTO kafka://result-topic

12}

Figure 4. Computing the people to be notified with Seraph. Figure 5. Graphs resulting from the union of event occurred from 8:58 AM to 9:28 AM. Figure 6. Graphs resulting from the union of event occurred from 9:06 AM to 9:36 AM. "Person" |  "Virus"
---|---
"Chase" |  "Norovirus"
Table 2. Outputs of Seraph continuous query at 9:28 AM. "Person" |  "Virus"
---|---
"Allison" |  "Norovirus"
"House" |  "Norovirus"
Table 3. Outputs of Seraph continuous query at 9:36 AM.

Let us discuss the query. The REGISTER QUERY clause at Line 1 allows for
registering the query into the system that manages Seraph queries444The query
handler permits to pause, restart, stop, start, and delete queries.. At Line 2
the FROM STREAM clause is used to specify the source stream. The STARTING FROM
clause specifies the initial time instant that is used to define the sequence
of the evaluation time instants. In this case, Latest means that the first
evaluation time instant is related to the last event processed. The WINDOW
RANGE operator at Line 4 sets up a 4 hours wide time-based sliding window. The
MATCH and RETURN clauses are the same as whose depicted in Figure 3. Line 10
specifies the EMIT clause. In particular, the ON ENTERING operator restricts
the reporting to new combinations of people and viruses so that each person is
notified only once for the same virus. The EVERY operator specifies the
frequency of the evaluation process. Specifically, the code EVERY 1 Event
tells that each new event triggers the evaluation process, thus notifying
Chase at 9:28 AM and Allison and House at 9:36 AM, in the example. At last,
the INTO clause is used to specify the target destination.

To summarize, every time a new event arrives, the system collects the events
that occurred in the last 4 hours under a unique graph, and it queries such a
graph to retrieve the people who have been in contact with an infected
patient. The resulting stream, which consists of tables, is pushed into a
Kafka topic.

Let us analyze the output of the query at different time instants.

  * •

9:12 AM The only event captured is the one depicted in Figure 1(a). No
patients have been tested positive. Thus no hospital personnel should be
notified.

  * •

9:13-9:27 AM The query emits no event.

  * •

9:28 AM The graphs in Figure 1(a) and Figure 1(b) are merged as shown in
Figure 5. Such an operation is automatically performed by Seraph under the
unique name assumption (tao2010integrity). The graph is then queried to
retrieve the people to be tested. Chase has to be notified of the potential
exposure to Norovirus. The output of the query is depicted in Table 2.

  * •

9:29-9:35 AM The query emits no event.

  * •

9:36 AM The graphs in Figure 1 are unified as shown in Figure 6. Such a graph
is then queried to retrieve the people to be tested for viruses. However,
since we do not want to notify the same people for the same virus twice, only
new combinations of person and virus w.r.t. the previous evaluation time
instant, are reported. As expected, only Allison and House have to be notified
of the potential exposure to Norovirus. The output of the query is depicted in
Table 3.

Figure 7. Localization events whenever a person is in a room.

Producing a stream of graphs. The query depicted in Figure 4 produces a stream
of tables. However, one can be interested in producing a stream of graphs
instead of a stream of tables. This allows for re-using the produced stream as
input for other Seraph queries.

Doctors and nurses are equipped with a Smart Identification Tag (SIT). Besides
displaying information about the hospital operator, such a tag integrates a
small Beacon that emits Bluetooth Low Energy signals. Rooms, corridors, and
stairs are provided with antennas that, exploiting the signals sent by the
SITs, allows for the identification of the positions of people inside the
hospital. Each antenna is responsible for triggering localization events
whenever a person is in a room. An example of localization events is depicted
in Figure 7. The query produces a stream of events that whenever two or more
people are in the same room is depicted in Figure 8.

Let us discuss the query. The REGISTER QUERY clause at Line 1 allows for
registering the query. At Line 2 the FROM STREAM clause is used to specify the
source stream, which is the same as the one in the previous query. The
STARTING FROM Latest clause specifies the initial time instant that is used to
define the sequence of the evaluation time instants. The WINDOW RANGE operator
at Line 4 sets up a 2 minutes wide time-based sliding window. The MATCH clause
retrieves all the pairs of people in the same room. The code CONSTRUCT CREATE
… RETURN GRAPH clause at Line 10 specifies that a new stream of graphs should
be returned. In particular, the CREATE statement at Line 8 allows for creating
new IS_WITH relationships connecting two people that happened to be in the
same room in 2 minutes time range. At Line 11 the EMIT ON ENTERING operator
allows for obtaining only the elements entering into the window. The EVERY
operator specifies the frequency of the evaluation process. In this case, a
minute is specified using PT1M. The INTO clause then specifies the target
destination of the stream, which is the same used as the input stream in the
query depicted in Figure 4.

In this section, we briefly showcased the capabilities of Seraph with the aid
of a running example. In Section LABEL:section:industrial-use-cases, real-
world use cases are shown to highlight the industrial exploitability of the
introduced language.

⬇

1REGISTER QUERY people_in_the_same_location {

2 FROM STREAM kafka://room-topic

3 STARTING FROM Latest

4 WITH WINDOW RANGE PT2M

5 MATCH

6 (p1:Person)-[:IN]->(room:Room),

7 (p2:Person)-[:IN]->(room)

8 CONSTRUCT CREATE

9 (p1)-[:IS_WITH]->(p2)

10 RETURN GRAPH

11 EMIT ON ENTERING EVERY PT1M

12 INTO kafka://event-topic

13}

Figure 8. Seraph query to compute the people in the same room.

##  3\. Background: the Cypher language

In the following, we provide the formal specification of the core of Cypher,
which is a declarative query language for property graphs. The core of Cypher
consists of:

  * •

a data model that includes values, graphs, and tables;

  * •

a query language that includes expressions, patterns, clauses, and queries.

Section 3.1 discusses the data model, while Section
LABEL:section:backgroud:evaluation-semantic defines the evaluation semantic of
the query language. For brevity, we only report the definitions that we need
to formally define Seraph. However, we invite the interested reader to consult
(DBLP:conf/sigmod/FrancisGGLLMPRS18) for the whole Cypher formalization.

###  3.1. Data model

###### Definition 3.1.

Values. We consider three disjoint sets $\mathcal{K}$ of property keys,
$\mathcal{N}$ of node identifiers, and $\mathcal{R}$ of relationship
identifiers. These sets are all assumed to be countably infinite. For this
presentation of the model, we assume two base types: the integers
$\mathbb{Z}$, and the type of finite strings over a finite alphabet $\Sigma$.

The set $\mathcal{V}$ of values is inductively defined as follows:

  * •

Identifiers, i.e. elements of $\mathcal{N}$ and $\mathcal{R}$, are values

  * •

Base types (elements of $\mathbb{Z}$ and $\Sigma\ast$) are values

  * •

true, false and null are values

  * •

$list()$ is a value (empty list), and if $v_{1},v_{2},\dots,v_{m}$ are values,
for $m>0$, then $list(v_{1},v_{2},\dots,v_{m})$ is a value

  * •

$map()$ is a value (empty map), and if $k_{1},k_{2},\dots,k_{m}$ are distinct
property keys and $v_{1},v_{2},\dots,v_{m}$ are values, for $m>0$, then
$map((k_{1},v_{1}),(k_{2},v_{2}),\dots,(k_{m},v_{m}))$) is a value

  * •

If $n$ is a node identifier, then $path(n)$ is a value. If
$n_{1},n_{2},\dots,n_{m}$ are node ids and $r_{1},r_{2},\dots,r_{m-1}$ are
relationship ids, for $m>1$, then
$path(n_{1},r_{1},n_{2},r_{2},\dots,n_{m-1},r_{m-1},n_{m})$ is a value.


# Deformable Capsules for Object Detection

Rodney LaLonde
Kitware Inc.
Carrboro, NC
<EMAIL_ADDRESS>
&Naji Khosravan
Zillow Group Inc.
Seattle, WA
<EMAIL_ADDRESS>
Ulas Bagci
Dept of ECE, BME, and Radiology
Northwestern University
Chicago, IL, 6011
<EMAIL_ADDRESS>
Equal contribution to the first author

###### Abstract

In this study, we introduce a new family of capsule networks, deformable
capsules (DeformCaps), to address a very important problem in computer vision:
object detection. We propose two new algorithms associated with our
DeformCaps: a novel capsule structure (SplitCaps), and a novel dynamic routing
algorithm (SE-Routing), which balance computational efficiency with the need
for modeling a large number of objects and classes, which have never been
achieved with capsule networks before. We demonstrate that the proposed
methods allow capsules to efficiently scale-up to large-scale computer vision
tasks for the first time, and create the first-ever capsule network for object
detection in the literature. Our proposed architecture is a one-stage
detection framework and obtains results on MS COCO which are on-par with
state-of-the-art one-stage CNN-based methods, while producing fewer false
positive detections, generalizing to unusual poses/viewpoints of objects.

##  1 Introduction

Capsule networks promise many potential benefits over convolutional neural
networks (CNNs). These include practical benefits, such as requiring less data
for training or better handling unbalanced class distributions [1]. There are
important theoretical benefits in using capsules such as building-in stronger
internal representations of objects [2], and modeling the agreement between
those intermediate representations which combine to form final object
representations (e.g. part-whole relationships) [3, 4]. Although these
benefits might not be seen yet in the performance metrics (e.g. average
precision) on standard benchmark computer vision datasets, they are important
for real-world applications. As an example, it was found by [5] that CNNs fail
to recognize 97% of their pose space, while capsule networks have been shown
to be far more robust to pose variations of objects [6]; further, real-world
datasets are not often as extensive and cleanly distributed as ImageNet or MS
COCO.

These benefits are achieved in capsule networks by storing richer vector (or
matrix) representations of features, rather than the simple scalars of CNNs,
and dynamically choosing how to route that information through the network.
The instantiation parameters for a feature are stored in these capsule vectors
and contain information (e.g. pose, deformation, hue, texture) useful for
constructing the object being modeled. Early studies have shown strong
evidence that these vectors do in fact capture important local and global
variations across objects’ feature components (or parts) within a class [2,
4]. Inside their networks, capsules dynamically route their information,
seeking to maximize the agreement between these vector feature representations
and the higher-level feature vectors they are attempting to form.

Despite their potential benefits, many have remained unconvinced about the
general applicability of capsule networks to large-scale computer vision
tasks. To date, no capsule-based study has achieved classification performance
comparable to a CNN on datasets such as ImageNet, instead relegated to smaller
datasets such as MNIST or CIFAR. Worse still, to the best of our knowledge, no
capsule network has shown successful results in object detection, a very
important problem in computer vision, robotics, and medical imaging. Now, the
argument can be made that standard benchmark datasets such as ImageNet or MS
COCO likely contain majority of objects in that $3\%$ range of usual poses,
and thus CNNs will appear to perform extremely well when measured in terms of
accuracy, stripping capsule networks of one of their largest advantages.
However, until capsule networks can perform on-par with CNNs on these typical
object poses, few will care about the benefits of stronger internal
representations and better generalization to unseen poses.

Summary of Our Contributions: (1) We propose the first ever capsule-based
object detection framework in the literature. Our network is a one-stage
(single-shot) architecture, where objects are both localized and classified
using capsules, and can perform on-par with the state-of-the-art CNNs on a
large-scale dataset (MS COCO). (2) We address the geometric constraint of
convolutional capsules (and locally-constrained routing) by introducing
deformable capsules, where parent capsules learn to adaptively sample child
capsules, effectively eliminating rigid spatial restrictions while remaining
memory efficient. (3) We design a new capsule-based prediction head structure,
SplitCaps, which reformulates the projections of an objects’ instantiation
parameters, presence, and class, eliminating the previous dimensional increase
of capsules by the number of classes. This crucial addition enables the
training of capsule networks on large-scale computer vision datasets for the
first time in the literature. (4) To route information across SplitCaps’
unique structure, we introduce a novel Squeeze-and-Excitation inspired dynamic
routing algorithm, SE-Routing, which seeks to maximize agreement between child
capsule projections, without the need of iterative loops

##  2 Deformable capsules: Fixing locally-constrained dynamic routing

The capsule network architecture proposed by [4] acted on global information,
where digit capsules represented the pose and presence of digits in an image
regardless of spatial location. The information from all children in the
previous layer was sent to every parent in the following layer, weighted via
the routing coefficients found in a cosine similarity routing algorithm. While
this proved to be a highly-effective strategy, it was also computationally
expensive, limiting its use to only small-scale datasets. Recent works
attempted to scale up capsule networks to larger problems such as biomedical
image segmentation [7] or action detection in video [8] by using convolutional
capsules and locally-constraining the routing algorithm. Although efficient
solutions were presented in those studies, the representation power of capsule
networks was fundamentally limited due to imposing local constraints. This is
because convolutions, by design, have a fixed geometric structure [9], and
such a geometric constraint significantly inhibits capsules’ ability to model
part-whole relationships, relying on parts of objects to fall within a fixed
local grid. Therefore, it is unreasonable to expect a capsule to effectively
represent the pose and deformations of an object when the information related
to the parts of that object are locked into a fixed spatial relationship.
Locally-constrained routing was a needed step to make capsules viable on
larger-scale problems, but in some ways it was fundamentally a step in the
wrong direction.

In this study, we propose to effectively solve this aforementioned problem by
introducing a method that balances efficiency with the ability for a capsule
to represent any pose and deformation of an object (i.e. where child capsules
can be found in different spatial relationships to one another for the same
parent). In such a formulation, global information is not explicitly required,
but it does require parent capsules to have more flexibility over which child
capsules they draw information from. Our proposed solution is deformable
capsules. The idea behind the proposed algorithm is simple: if parent capsules
are supposed to capture common deformations of the objects they represent
within their vectors, then the choice of which children to aggregate
information from must be handled in a deformable manner as well. Deformable
capsules allow parents to adaptively gather projections from a non-spatially-
fixed set of children, and thus effectively and efficiently model objects’
poses.

To achieve this overall goal, we follow the same efficient convolutional
capsule paradigm, where projection vectors are formed via a convolution
operation with a kernel centered on the parent capsules’ spatial location, but
now we learn an additional set of weights for each parent capsule. These
learnable weights are the same shape as each parent’s kernel, and represent
the offset values for the spatial sampling of child capsules for that parent.
Based on the child capsule representation vectors in the previous layer, these
weights learn which children a parent capsule should adaptively sample from
for a given input image. Dynamic routing then determines how to weight the
information coming from each of these children based on their agreement for
each projected parent.

Let us give a concrete example to better illustrate the parameter savings of
this technique. Given a $H=128$ by $W=128$ grid of child capsules with
$c_{i}=32$ capsule types of $a_{i}=8$ atoms each, being routed to a set of
$c_{j}=10$ parent capsule types of $a_{j}=16$ atoms each, the fully-connected
capsules of [4] would require $H\times W\times c_{i}\times a_{i}\times
c_{j}\times a_{j}\Rightarrow 128\times 128\times 32\times 8\times 10\times
16\approx 671$M parameters for this layer alone (assuming the goal is
classification, with detection requiring a multiplicative increase by the
detection grid size). Instead, using our proposed deformable capsules with a
$k^{2}=5^{2}$ kernel, we only require $2\times k\times k\times a_{i}\times
c_{j}\times a_{j}\Rightarrow 2\times 5\times 5\times 8\times 10\times
16\approx 64$K parameters. Convolutional capsules with locally-constrained
routing require $32$K parameters, not needing the additional spatial offsets
kernel, but as mentioned above, they are fundamentally limited in the poses
and deformations that they can represent. In our experiments, we found
deformable capsules to converge faster and to much higher performance than
convolutional capsules.

##  3 Objects as capsules: SplitCaps with SE-Routing

We propose a novel one-stage (single-shot) capsule network architecture for
object detection, called DeformCaps, where objects are detected, classified,
and modeled with capsules. Our overall network architecture, shown in Fig. 1,
is built upon CenterNet by [10] who proposed to represent objects in images as
scalar point values located at the center of their bounding boxes. The authors
then regress the remaining characteristics of the object (e.g. height, width,
depth) for each center-point detected. In our work, we follow the same center-
point detection paradigm, but represent our objects with capsule vectors
instead. Since several recent studies have found utilizing a CNN backbone
before forming capsule types to be beneficial to overall performance [8, 3,
11], we adopt the preferred backbone of CenterNet, DLA-34 [12], as this gave
the best trade-off between speed and accuracy. Features extracted from the
backbone are sent to our capsule object detection head and a bounding box
regression head. In order to perform object detection using capsules, we
introduce a new capsule structure, called SplitCaps, composed of class-
agnostic and class-presence capsules, and a novel routing algorithm, called
SE-Routing.

Figure 1: Deformable capsule architecture for object detection.

###  3.1 SplitCaps: Class-agnostic capsules and class-presence capsules

As discussed in Section 2, the original CapsNet by [4] was extremely expensive
in computation and our proposed deformable capsules is a best possible
solution to balance non-rigid deformations of objects while remaining memory
efficient. However, there is a more significant memory hurdle capsule networks
must overcome when scaling up to large-scale datasets, such as MS COCO. In
their current implementation, capsule networks represent each class with its
own parent capsule vector. On small scale classification datasets (and using
deformable routing), this is not an issue; it amounts to $2\times k\times
k\times a_{i}\times c_{j}\times a_{j}$ parameters and $N\times c_{i}\times
c_{j}\times a_{j}\times 4$ bytes to store the intermediate representations to
be routed for the parents, where $c_{j}$ is usually around $10$ classes to
represent. Let us suppose we have $5\times 5$ kernels with $32$ input capsule
types of $8$ atoms per capsule, $10$ output capsule types of $16$ atoms per
capsule, and a batch size of $32$. In total, we would have $2\times 5\times
5\times 8\times 10\times 16=64$K parameters and $32\times 32\times 10\times
16\times 4\approx 655$ KB.

When we scale this up to object detection, we now need to store
representations for every possible object location, and for MS COCO we need to
represent 80 possible classes. This gives us $2\times k\times k\times
a_{i}\times c_{j}\times a_{j}\Rightarrow 2\times 5\times 5\times 8\times
80\times 16=512$K parameters and $N\times H\times W\times c_{i}\times
c_{j}\times a_{j}\times 4$ bytes $\Rightarrow 32\times 128\times 128\times
32\times 80\times 16\times 4\approx 86$ GB for the intermediate
representations, where we assume the output grid of detections is $128\times
128$ with a single detection (i.e. bounding box) predicted per class per
location. The problem is not any better for large-scale classification
datasets such as ImageNet either, where we lose the grid of predictions but
grow to $1000$ classes, which would require $2\times 5\times 5\times 8\times
1000\times 16=6.4$M parameters and $32\times 32\times 1000\times 16\times
4\approx 66$ GB for the intermediate representations. Clearly, with most GPU
memories limited to $12$–$24$ GB, a solution is needed to be found for capsule
networks to scale up to larger-scale computer vision tasks.

To overcome this issue, we propose a new type of capsule architecture,
SplitCaps, to more efficiently scale capsule networks to large-scale computer
vision tasks. SplitCaps contains two parent capsule types, each with a
different number of atoms per capsule, for each location of the detection
grid. As before, the idea is to balance efficiency with the ability to learn
powerful representations. Towards this goal, SplitCaps proposes to divide up
between its two parent capsules the tasks of (i) learning the instantiation
parameters necessary to model the possible variations of an object and (ii)
predicting which classes of objects are present in a given input. The first
capsule type we refer is our class-agnostic object instantiation capsules, and
the second we refer is class presence capsules.

Class-agnostic object instantiation capsules: The purpose of these capsules is
similar to those in previous works: model the possible variations (in pose,
deformation, texture, etc.) of objects within a vector of instantiation
parameters, the span of which should cover all possible variations for that
object at test (hence why capsules are better than CNNs at generalizing to
unseen poses). While previous capsule networks did this in a class-wise
manner, we argue such a formulation is not required and possibly it is
redundant. Many variations (e.g. rotation, skew, stroke thickness) may be
class-independent, and thus to model these variations class-wise would require
repetition across each capsule type. Instead, we propose to model all classes
within a single capsule type (i.e. class-agnostic). In this way, while class-
dependent variations would each require their own dimensions of the vector,
class-independent variations can each be modeled along a single dimension for
all possible objects. Since it is reasonable to assume there will be at least
some class-specific variations, we increase the default capsule vector
dimension from $16$ to $64$ to accommodate for possible class-specific
instantiation parameters.

During training, if an object is present at a given spatial location, the
64-dimensional capsule vector for that location is fed to a reconstruction
regularization sub-network to construct the mask of that object as similar to
the reconstruction regularization used by [4] for classification. This sub-
network is a relatively small and fast addition: a set of three ReLU-activated
$1\times 1$ convolutional layers with $256$ filters each, followed by a final
sigmoid-activated $1\times 1$ convolution with $N=n^{2}=28^{2}=784$ filters,
before reshaping outputs to $n\times n$. Since objects’ scales vary
dramatically, we scale normalize all objects’ ground-truth masks to be
$28\times 28$ (by following [13]). Supervised training is conducted by
computing the Dice loss [14] between the predicted reconstruction, $r$, and
the object’s mask, $m$

$\mathcal{L}_{r}=\frac{2\sum_{i}^{N}r_{i}m_{i}}{\sum_{i}^{N}r_{i}^{2}+\sum_{i}^{N}m_{i}^{2}}\textrm{,}$
(1)

where $\mathcal{L}_{r}$ is used to provide a regularization signal to the
instantiation parameters being learned.

Class presence capsules: The class presence capsules attempt to model which
classes of objects are present in the input at each spatial location, if any.
We accomplish this by setting the atoms per capsule to the number of classes
being represented (i.e. 80 for MS COCO). Just as [6] separately modeled pose
(with a matrix) and activation (with a scalar), this 80-dimensional vector can
be viewed as a class-dependent set of activation values. The activation values
are then passed through a sigmoid function and thresholded; if one or more
activation values are above the threshold, an object is determined to be at
that spatial location with the strongest activated dimension determining the
class label.

In order to produce a smooth loss function during training, we create a
ground-truth heatmap by fitting a Gaussian distribution rather than a single
point, to the center-point of each object’s bounding box, with variance
proportional to the size of the box following [10]. More specifically, we
create a heatmap ${H\in[0,1]^{\frac{X}{d}\times\frac{Y}{d}\times K}}$
containing each down-scaled ground truth center-point
$\tilde{p}=\big{(}\frac{p_{x}}{d},\frac{p_{y}}{d}\big{)}$ for class $k\in K$
using a Gaussian kernel
${H_{xyk}=\exp\left(-\frac{(x-\tilde{p}_{x})^{2}+(y-\tilde{p}_{y})^{2}}{2\sigma_{p}^{2}}\right)}$,
where $d$ is the amount of downsampling in the network and $\sigma_{p}$ is an
object-size-adaptive standard deviation [15]. In the case of overlapping
Gaussians, we take the element-wise maximum. To handle the large class
imbalance between objects and background in our heatmaps, we use a penalty-
reduced pixel-wise logistic regression with a focal loss [16]:

$\mathcal{L}_{h}=\frac{-1}{P}\sum_{xyk}\begin{cases}(1-\hat{H}_{xyk})^{\alpha}\log(\hat{H}_{xyk})&\\!\text{if}\
H_{xyk}=1,\vspace{2mm}\\\
(1-H_{xyk})^{\beta}(\hat{H}_{xyk})^{\alpha}\log(1-\hat{H}_{xyk}),&\\!\text{otherwise;}\end{cases}$
(2)

where $\alpha,\beta$ are hyper-parameters of the focal loss, $P$ is the number
of center-points in the input, used to normalize all positive focal loss
instances to $1$ [10]. We use $\alpha=2$ and $\beta=4$ in all our experiments,
following [15]. At test, to efficiently retrieve the object’s exact center, we
run a $3\times 3$ max-pooling over the thresholded spatial map.

To predict the height and width of the bounding boxes of objects and recover
the $x,y$ offsets needed to map back to the upscaled image dimensions, we
follow the same formulation as [10] and pass the backbone features through a
$3\times 3$ convolutional layer with $256$ feature maps, then a $1\times 1$
convolutional layer with $2$ feature maps. These layers predict the local
offset, $\hat{O}\in\mathbb{R}^{\frac{W}{d}\times\frac{H}{d}\times 2}$, and
size prediction, $\hat{S}\in\mathbb{R}^{\frac{W}{d}\times\frac{H}{d}\times
2}$, for each center-point and are supervised by

$\mathcal{L}_{o}=\frac{1}{P}\sum_{p}\left|\hat{O}_{\tilde{p}}-\left(\frac{p}{d}-\tilde{p}\right)\right|,$
(3)

and

$\quad\mathcal{L}_{s}=\frac{1}{P}\sum_{p}\left|\hat{S}_{p}-(x_{2}-x_{1},y_{2}-y_{1})\right|,$
(4)

respectively. Our final objective function is thus defined as
$\mathcal{L}=\mathcal{L}_{h}+\lambda_{r}\mathcal{L}_{r}+\lambda_{s}\mathcal{L}_{s}+\lambda_{o}\mathcal{L}_{o}$.
We keep $\lambda_{s}=0.1$ and $\lambda_{o}=1$ as done in [10], and set
$\lambda_{r}=0.1$ initially, then step up to $\lambda_{r}=2.0$ at the half-way
in training.

Figure 2: Proposed deformable SplitCaps formulation which, in one-shot,
localizes all objects to their centers, determines their classes, and models
their instantiation parameters in two parallel parent capsule types.
Information is dynamically routed from children to parents by passing three
chosen child capsule descriptors through a two-layer Squeeze-and-Excitation
(S&E) bottleneck.

###  3.2 SE-Routing: SplitCaps new routing algorithm

As a core component of capsule networks, dynamic routing seeks to maximize the
agreement between child capsule projections for parent capsules and to fully-
leverage the richer representations being stored. Since SplitCaps introduces a
unique capsule head structure, where instantiation parameters and activations
are split across different capsule types, previous dynamic routing algorithms
can no longer be directly applied. To overcome this, we propose a new dynamic
routing algorithm that takes inspiration from Squeeze-and-Excitation networks
[17], which we call SE-Routing, and illustrated in Fig. 2.

Previously proposed dynamic routing algorithms (e.g. [4] and [6]) were
typically iterative, requiring a hand-tuned loop of routing iterations, which
proved to be slow and temperamental in practice. Different studies found
different numbers of iterations to be effective, and one meta-study of five
different iterative dynamic routing algorithms found them all to be largely
ineffective [18]. To avoid this pitfall, we propose a new routing algorithm to
dynamically assign weights to child capsule projections based on their
agreement, computed in a single forward pass using a simple gating mechanism
with sigmoid activation. Unlike [4] which uses a routing softmax to force a
one-hot mapping of information from each child to parents, our proposed SE-
Routing learns a non-mutually-exclusive relationship between children and
parents to allow multiple children to be emphasised for each parent.

Creating child capsule projection descriptors (squeeze): Following the
Squeeze-and-Excitation paradigm, we first must compute the squeeze (i.e. a set
of descriptors which summarize relevant information about each feature) to
create a set of child capsule projection descriptors. In [17], the authors
proposed to use the global average activation of each channel with the goal of
modeling channel interdependencies. In this study, our goal is to maximize the
agreement between child projections, for both the instantiation parameters and
class presence of the object being modeled. With that motivation, we compute
three separate descriptors which are fed into the excitation phase of the
routing: (i) cosine angle between the mean projection vector and each child’s
projection, which captures object instantiation agreement; (ii)
Kullback–Leibler (KL) divergence of each child’s predicted class distribution
and an aggregated distribution, which captures class presence agreement; and
(iii) variance of each child’s predicted class distribution, which captures
class presence uncertainty.

The cosine angle descriptor, $\bm{a}$, is calculated in a similar manner to
[4]. A mean projection vector,
$\bm{\tilde{u}}=1/N\sum_{i}^{N}\bm{\hat{u}}_{i}$, is first computed using the
set of child capsule projections,
$\bm{\hat{U}}=\\{\bm{\hat{u}}_{1},\bm{\hat{u}}_{2},...,\bm{\hat{u}}_{N}\\}$.
Then we compute a set of cosine angles between each individual projection and
this mean, $\bm{a}=\\{a_{1},a_{2},...,a_{N}\\}$, where
$a_{i}=(\bm{\tilde{u}}\cdot\bm{\hat{u}}_{i})/(\lvert\bm{\tilde{u}}\rvert\cdot\lvert\bm{\hat{u}}_{i}\rvert)$.

In a similar fashion, we compute a KL divergence descriptor, $\bm{b}$, by
first creating an aggregate object class distribution. To create this
aggregate distribution, we follow the work of [19], insofar as each child
capsule type is treated as an expert giving its prediction about the true
underlying class distribution. First, we compute a simple linear opinion pool
[20], $\bm{p(\tilde{z})}=\sum_{i}^{N}\sigma_{s}(\bm{z}_{i})/N$, where
$\bm{p(\tilde{z})}$ is the aggregated probability distribution,
$\bm{Z}=\\{\bm{z}_{1},\bm{z}_{2},...,\bm{z}_{N}\\}$ is the set of child class
presence projection vectors, and
$\sigma_{s}(\bm{z}_{i})_{j}=e^{\bm{z}_{ij}}/\sum_{k}^{K}e^{\bm{z}_{ik}}\textrm{
for }j=\\{1,...,K\\},i=\\{1,...,N\\}$ is the softmax function used to
transform projection vectors into normalized probability distributions over
the $K$ classes. Then, we measure the agreement between each child’s predicted
distributions, $\sigma_{s}(\bm{z}_{i})$, and the aggregate distribution,
$\bm{p(\tilde{z})}$, as the KL divergence between them
$b_{i}=\sum_{k}^{K}p(\tilde{z}_{k})\log(p(\tilde{z}_{k})/\sigma_{s}(z_{i})_{k})$.

Lastly, we take our child capsules’ predicted distributions,
$\sigma_{s}(\bm{z}_{i})$, and compute their variance to estimate the
uncertainty each child has:
$c_{i}=\sum_{k}^{K}(\sigma_{s}(z_{i})_{k}-\sum_{k}^{K}\sigma_{s}(z_{i})_{k})^{2}$.
Our three sets of descriptors are efficiently computed for all capsules
simultaneously (i.e. for entire batch and across spatial locations) on GPU in
parallel with matrix operations. They are then concatenated,
$\bm{s}=\bm{a}\oplus\bm{b}\oplus\bm{c}$, and fed to the excitation layers of
our routing mechanism (Fig. 2).

Determining routing coefficients (excitation): The excitation stage of the SE-
Routing algorithm has the task of learning a mapping from the concatenated set
of capsule descriptors, $\bm{s}$, into a set of routing coefficients for the
child capsule projections. Since parents capsules types are no longer
different classes in our formulation, but rather two separated aspects of
modeling objects, we compute a single set of routing coefficients at each
spatial location for both parents. Formally, this mapping is computed as
$\bm{r}=\sigma(\bm{W}_{2}\delta(\bm{W}_{1}\bm{s}))$, where
$\bm{W}_{1}\in\mathbb{R}^{\frac{3N}{t}\times 3N}$,
$\bm{W}_{2}\in\mathbb{R}^{N\times\frac{3N}{t}}$, $\delta$ is the ReLU
activation function, $\sigma$ is the sigmoid activation function, and $t$ is
the reduction ratio used to form this mapping into a two fully-connected (FC)
layer bottleneck. A brief note: although excitation routing has interesting
parallels to self-attention (e.g. dynamically conditioned on the input), our
learned mapping is non-mutually-exclusive, while self-attention and CapsNet’s
dynamic routing both rely on applying a softmax function over outputs.

Finally, with the determined routing coefficients
$\bm{r}=\\{r_{1},r_{2},...,r_{N}\\}$, we can compute the output of the
SplitCaps detection head. Projection vectors from each child to each parent
are computed using the proposed deformable capsules (as described in Section
2). These projections are then combined and weighted by the routing
coefficients to form the final parent capsules. These final parents contain
the instantiation parameters,
$\bm{v}_{obj}=\sum_{i}^{N}r_{i}\bm{\hat{u}}_{obj|i}$, and class presence,
$\bm{v}_{cls}=\sum_{i}^{N}r_{i}\bm{\hat{u}}_{cls|i}$, of any objects being
represented at the given spatial location within the detection grid.

##  4 Deformable capsules on MS COCO

We evaluated our deformable capsule object detection framework on the MS COCO
dataset [21], which contains $118$K training, $5$K validation and $20$K hold-
out testing images. Average precision (AP) is reported over all IOU thresholds
and at thresholds $0.5$ (AP50) and $0.75$ (AP75). We followed the training
procedure proposed in [10], training on $512\times 512$ pixel inputs, yielding
$128\times 128$ detection grids, using random flip, random scaling (between
0.6 to 1.3), cropping, and color jittering as data augmentation, and Adam [22]
to optimize our objective function. Due to limited compute resources, we
initialized the backbone network weights from CenterNet and train for $40$
epochs only with a batch size of $12$ and learning rate of 5e-4 with $5\times$
drops at $5$, $15$, and $25$ epochs. Longer training would likely yield
superior results, as found by [10] who obtained better results for CenterNet
when increasing from $140$ to $230$ epochs.

In Table 1, we provide results of our proposed deformable capsule network with
and without flip and multi-scale augmentations following [10]. Inference time
on our hardware (Intel Xeon E5-2687 CPU, Titan V GPU, Pytorch 1.2.0, CUDA
10.0, and CUDNN 7.6.5) was consistent with those reported by [10].111We will
make our code publicly available for the community for reproducible research.
While DeformCaps performs slightly inferior to the CenterNet in terms of AP,
it does so while producing far fewer false positive detections, as shown in
Table 1 in Appendix. For ablations, we trained a version of DeformCaps which
replaces the proposed deformable capsules with the standard locally-
constrained convolutional capsules (non-DeformCaps), and a version which
removed the routing procedures (No-Routing). These ablations show the
contribution of each component of the proposed method.

Method | Backbone | FPS | AP | AP50 | AP75 | APS | APM | APL
---|---|---|---|---|---|---|---|---
MaskRCNN [13] | ResNeXt-101 | 11 | 39.8 | 62.3 | 43.4 | 22.1 | 43.2 | 51.2
Deform-v2 [23] | ResNet-101 | - | 46.0 | 67.9 | 50.8 | 27.8 | 49.1 | 59.5
SNIPER [24] | DPN-98 | 2.5 | 46.1 | 67.0 | 51.6 | 29.6 | 48.9 | 58.1
PANet [25] | ResNeXt-101 | - | 47.4 | 67.2 | 51.8 | 30.1 | 51.7 | 60.0
TridentNet [26] | ResNet-DCN | 0.7 | 48.4 | 69.7 | 53.5 | 31.8 | 51.3 | 60.3
YOLOv3 (Redmon et al., 2018) | DarkNet-53 | 20 | 33.0 | 57.9 | 34.4 | 18.3 | 25.4 | 41.9
RetinaNet [16] | ResNeXt-FPN | 5.4 | 40.8 | 61.1 | 44.1 | 24.1 | 44.2 | 51.2
RefineDet [27] | ResNet-101 | - | 36.4 / 41.8 | 57.5 / 62.9 | 39.5 / 45.7 | 16.6 / 25.6 | 39.9 / 45.1 | 51.4 / 54.1
CenterNet [10] | DLA-34 | 28 |  39.2 / 41.6 |  57.1 / 60.3 |  42.8 / 45.1 |  19.9 / 21.5 |  43.0 / 43.9 |  51.4 / 56.0
DeformCaps (Ours) | DLA-34 | 15 |  38.0 / 40.6 |  55.5 / 58.6 |  41.3 / 43.9 |  20.0 / 23.0 |  42.5 / 42.9 |  51.8 / 56.4
Non-DeformCaps | DLA-34 | 20 | 27.2 / 30.1 | 41.8 / 45.9 | 29.6 / 32.6 | 13.3 / 15.6 | 30.0 / 30.8 | 35.0 / 40.6
No-Routing | DLA-34 | 15 | 35.9 / 38.9 | 52.7 / 56.0 | 39.1 / 42.4 | 17.8 / 20.9 | 40.6 / 42.0 | 48.2 / 54.4

Table 1: Single-scale / multi-scale results on COCO test-dev. Top: Two-stage
detectors; Middle: One-stage detectors; Bottom: Ablation studies on deformable
capsules and SE-Routing. Two lines (DeformCaps and CenterNet) are highlighted.

### Qualitative Results on MS COCO

Included in this section are a number of qualitative examples for CenterNet
[10] and the proposed DeformCaps on the MS COCO test-dev dataset [21] using
both flip and multi-scale augmentations. Results for CenterNet were obtained
using the official code and trained models provided by the authors [10]. While
we do not make any sweeping claims, we wish to comment on a few general
patterns that seemed to emerge in these examples. In Figure 3, we show a
prototypical example of the general trend we are describing. In Figures 4– 6
(in appendix), we include more examples of this trend. In Figures 7– 8 (in
appendix), we include a set of interesting examples of unusual object
viewpoints or poses being better captured by DeformCaps than by CenterNet.

First, DeformCaps tends to be more conservative with its detections than
CenterNet. This can be observed both by the slightly lower confidence scores
(typically 0.1 less than CenterNet for most detections), and by the overall
fewer amount of boxes placed in scenes. Second, CenterNet tends to produce far
more false positives than DeformCaps, both in the case of incorrect detections
and of multiple detections for the same object which failed to be suppressed
by the NMS algorithm. Though DeformCaps producing slightly lower confidence
scores might account for some of the reduction in false positives, we observe
CenterNet consistently producing fairly confident false predictions (e.g.
$>0.4$) while DeformCaps does not produce a detection in the same region at
all.

This observation of less false positive detection is consistent with what we
would expect from a capsule network with dynamic routing as compared to a
traditional convolutional neural network (CNN). Where a CNN passes on all
activations to the next layer, capsule networks utilize a dynamic routing
algorithm to only pass on activations if there is agreement amongst the child
capsule projections. In our proposed method specifically, with a SplitCaps
structure and SE-Routing, the agreement is computed for projections of both
the pose and class of the object being represented. It follows naturally that
this would limit the amount of false positive detection which are produced, by
reducing the amount of activations that get passed on. Further, we find from a
survey of these qualitative examples that DeformCaps is better able to detect
objects when being presented in an unusual pose or from an usual viewpoint
than its CenterNet counterpart. This gives empirical support to one of the
purported benefits of capsule networks, to be able to better generalize to
unseen poses and viewpoints.

Figure 3: Qualitative example for CenterNet [10] (leftmost), the proposed
DeformCaps (center), and the ground-truth annotations (rightmost) on the MS
COCO test-dev dataset. While CenterNet produces slightly higher average
precision (AP) values than DeformCaps, it also seems to produce more false
positives on average than DeformCaps.

##  5 Related works

###  5.1 Capsule networks

The idea of capsules was first introduced by [28]. [4] extended this and
proposed dynamic routing between capsules. The EM routing algorithm was then
modified by [6]. Recently, capsule networks could achieve the state-of-the-art
performance for a wide range of applications: video object segmentation [29],
point cloud segmentation [30], explainable medical diagnosis [31], text
classification [32], sentiment analysis [33], and various other applications
[34].

###  5.2 Object detection

Region proposal-based approaches: R-CNN was one of the first successful deep
object detectors, in which a selective search algorithm was used to select a
number of region proposals, CNN features were extracted from each of the
region proposals and were used to both classify the object and regress its
bounding box [35]. The later addition of Fast R-CNN [36] provided end-to-end
training and addressed the speed and efficiency issues of R-CNN.

Anchors-based approaches: Anchors-based approaches sample fixed-shape bounding
boxes (anchors) around a low-resolution image grid, then attempt to classify
anchors into object classes. Faster R-CNN [37] generates region proposals in a
first stage network, then attempts to classify and regress bounding boxes for
the top-$k$ highest scoring anchors in a second stage network. Later studies
such as [38] dramatically speed up the process by converting the proposal
classifier to a multi-class one-stage detector. Since then, researchers have
been working on improving one-stage detectors by including shape priors [39,
40], multiple feature resolutions [41], re-weighting the loss among different
samples [16], or modeling channel-wise attention [42].

Keypoint estimation-based approaches: CornerNet [15] attempts to detect
objects by predicting two bounding box corners as keypoints. ExtremeNet [43]
extends CornerNet’s approach by estimating all corners and the center of the
objects’ bounding box. However, these methods rely on significantly slow
combinatorial grouping post-processing stage. [10] proposed CenterNet which
attempts to predict only an objects’ center point, and regress all other
necessary values from there without the need for grouping or post-processing.

##  6 Discussions, limitations, & future work

Our proposed (DeformCaps) with SplitCaps object-class representations and
Squeeze-and-Excitation inspired SE-Routing algorithm represents an important
step for capsule networks to scale-up to large-scale computer vision problems,
such as object detection or large-scale classification. Our proposed one-stage
object detection capsule network is able to obtain results on MS COCO which
are on-par with other state-of-the-art one-stage CNN-based networks for the
first time in the literature, while also producing fewer false positives.
Examining the qualitative results lends empirical evidence that DeformCaps can
better generalize to unusual poses/viewpoints of objects than CenterNet [10].
We hope our work will inspire future research into the considerable potential
of capsule networks.

It is important to note that our work is the first-ever capsule network for
object detection and large-scale vision problems in general, requiring three
major contributions to achieve; it is typical of such works to under-perform
state-of-the-art. Further, it might be worth to note that some of the main
benefits of capsules (e.g. robustness to viewpoint/pose) are not captured well
by standard AP metrics, where objects in unusual poses represent a very small
fraction of examples.

Limitations: Our study has some limitations too. Briefly, (1) we had
difficulty integrating the bounding box regression values into our capsule
object detection head; (2) the choice of descriptors used in the squeeze is
somewhat handcrafted, and is open to further investigation; (3) the choice of
dimensions to model the class-agnostic instantiation parameters of objects was
chosen semi-arbitrarily and could likely improve from fine-search; and (4) the
choice of reconstructing objects’ masks versus image patches is not thoroughly
explored.

Future directions: The reconstruction sub-network of DeformCaps could possibly
be trained to produce a fast single-shot instance segmentation framework. At
test, potentially detected objects could have their instantiation vectors
reconstructed into objects’ masks, then these masks would simply be resized to
the predicted bounding-boxes, similar to [13] but without needing to have the
initial reshape and ROI alignment required in their two-stage approach. Such
an approach would likely need a rigorous balancing of the relative objective
functions, as well as careful consideration of the length of the instantiation
vectors relative to the complexity of the data being modeled.

Our goal is to make it computationally feasible to scale capsules up to large-
scale tasks such as detection for the first time, a problem which has
significantly held back research on capsule networks. It is our hope that
utilizing Deformable SplitCaps with SE-Routing, deeper investigations into
unique capsule properties on a wide range of large scale tasks can follow.

## References

  * [1] Amelia Jiménez-Sánchez, Shadi Albarqouni, and Diana Mateus.  Capsule networks against medical imaging data challenges.  In Intravascular Imaging and Computer Assisted Stenting and Large-Scale Annotation of Biomedical Data and Expert Label Synthesis, pages 150–160. Springer, 2018.
  * [2] Arjun Punjabi, Jonas Schmid, and Aggelos K Katsaggelos.  Examining the benefits of capsule neural networks.  arXiv preprint arXiv:2001.10964, 2020.
  * [3] Adam Kosiorek, Sara Sabour, Yee Whye Teh, and Geoffrey E Hinton.  Stacked capsule autoencoders.  In Advances in Neural Information Processing Systems, pages 15486–15496, 2019.
  * [4] Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton.  Dynamic routing between capsules.  In Advances in neural information processing systems, pages 3856–3866, 2017.
  * [5] Michael A Alcorn, Qi Li, Zhitao Gong, Chengfei Wang, Long Mai, Wei-Shinn Ku, and Anh Nguyen.  Strike (with) a pose: Neural networks are easily fooled by strange poses of familiar objects.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 4845–4854, 2019.
  * [6] Geoffrey E Hinton, Sara Sabour, and Nicholas Frosst.  Matrix capsules with em routing.  In International Conference on Learning Representations (ICLR), 2018\.
  * [7] Rodney LaLonde and Ulas Bagci.  Capsules for object segmentation.  In Medical Imaging with Deep Learning (MIDL), 2018.
  * [8] Kevin Duarte, Yogesh Rawat, and Mubarak Shah.  Videocapsulenet: A simplified network for action detection.  In Advances in Neural Information Processing Systems, pages 7610–7619, 2018.
  * [9] Jifeng Dai, Haozhi Qi, Yuwen Xiong, Yi Li, Guodong Zhang, Han Hu, and Yichen Wei.  Deformable convolutional networks.  In The IEEE International Conference on Computer Vision (ICCV), pages 764–773, 2017.
  * [10] Xingyi Zhou, Dequan Wang, and Philipp Krähenbühl.  Objects as points.  arXiv preprint arXiv:1904.07850, 2019.
  * [11] Yao-Hung Hubert Tsai, Nitish Srivastava, Hanlin Goh, and Ruslan Salakhutdinov.  Capsules with inverted dot-product attention routing.  In International Conference on Learning Representations (ICLR), 2020\.
  * [12] Fisher Yu, Dequan Wang, Evan Shelhamer, and Trevor Darrell.  Deep layer aggregation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2403–2412, 2018.
  * [13] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 2961–2969, 2017.
  * [14] Fausto Milletari, Nassir Navab, and Seyed-Ahmad Ahmadi.  V-net: Fully convolutional neural networks for volumetric medical image segmentation.  In 2016 Fourth International Conference on 3D Vision (3DV), pages 565–571. IEEE, 2016.
  * [15] Hei Law and Jia Deng.  Cornernet: Detecting objects as paired keypoints.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 734–750, 2018.
  * [16] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In The IEEE International Conference on Computer Vision (ICCV), pages 2980–2988, 2017.
  * [17] Jie Hu, Li Shen, and Gang Sun.  Squeeze-and-excitation networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7132–7141, 2018.
  * [18] Inyoung Paik, Taeyeong Kwak, and Injung Kim.  Capsule networks need an improved routing algorithm.  arXiv preprint arXiv:1907.13327, 2019.
  * [19] Robert T Clemen and Robert L Winkler.  Combining probability distributions from experts in risk analysis.  Risk analysis, 19(2):187–203, 1999.
  * [20] Mervyn Stone.  The opinion pool.  The Annals of Mathematical Statistics, pages 1339–1342, 1961.
  * [21] 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 Proceedings of the European Conference on Computer Vision (ECCV), pages 740–755. Springer, 2014.
  * [22] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In International Conference on Learning Representations (ICLR), 2014\.
  * [23] Xizhou Zhu, Han Hu, Stephen Lin, and Jifeng Dai.  Deformable convnets v2: More deformable, better results.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 9308–9316, 2019.
  * [24] Bharat Singh, Mahyar Najibi, and Larry S Davis.  Sniper: Efficient multi-scale training.  In Advances in neural information processing systems, pages 9310–9320, 2018.
  * [25] Shu Liu, Lu Qi, Haifang Qin, Jianping Shi, and Jiaya Jia.  Path aggregation network for instance segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8759–8768, 2018.
  * [26] Yanghao Li, Yuntao Chen, Naiyan Wang, and Zhaoxiang Zhang.  Scale-aware trident networks for object detection.  In Proceedings of the IEEE international conference on computer vision, pages 6054–6063, 2019.
  * [27] Shifeng Zhang, Longyin Wen, Xiao Bian, Zhen Lei, and Stan Z Li.  Single-shot refinement neural network for object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4203–4212, 2018.
  * [28] Geoffrey E Hinton, Alex Krizhevsky, and Sida D Wang.  Transforming auto-encoders.  In International conference on artificial neural networks, pages 44–51. Springer, 2011.
  * [29] Kevin Duarte, Yogesh S. Rawat, and Mubarak Shah.  Capsulevos: Semi-supervised video object segmentation using capsule routing.  In The IEEE International Conference on Computer Vision (ICCV), October 2019.
  * [30] Yongheng Zhao, Tolga Birdal, Haowen Deng, and Federico Tombari.  3d point capsule networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1009–1018, 2019.
  * [31] Rodney LaLonde, Drew Torigian, and Ulas Bagci.  Encoding visual attributes in capsules for explainable medical diagnoses.  In International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI). Springer, 2020.
  * [32] Wei Zhao, Jianbo Ye, Min Yang, Zeyang Lei, Suofei Zhang, and Zhou Zhao.  Investigating capsule networks with dynamic routing for text classification.  arXiv preprint arXiv:1804.00538, 2018.
  * [33] Yequan Wang, Aixin Sun, Jialong Han, Ying Liu, and Xiaoyan Zhu.  Sentiment analysis by capsules.  In Proceedings of the World Wide Web Conference, pages 1165–1174, 2018.
  * [34] T Vijayakumar.  Comparative study of capsule neural network in various applications.  Journal of Artificial Intelligence, 1(01):19–27, 2019.
  * [35] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 580–587, 2014.
  * [36] Ross Girshick.  Fast r-cnn.  In The IEEE International Conference on Computer Vision (ICCV), pages 1440–1448, 2015.
  * [37] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In Advances in neural information processing systems, pages 91–99, 2015.
  * [38] 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 (CVPR), pages 779–788, 2016.
  * [39] Joseph Redmon and Ali Farhadi.  Yolo9000: better, faster, stronger.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 7263–7271, 2017.
  * [40] Joseph Redmon and Ali Farhadi.  Yolov3: An incremental improvement.  arXiv preprint arXiv:1804.02767, 2018.
  * [41] Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott Reed, Cheng-Yang Fu, and Alexander C Berg.  Ssd: Single shot multibox detector.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 21–37. Springer, 2016.
  * [42] Zhe Chen, Jing Zhang, and Dacheng Tao.  Recursive context routing for object detection.  International Journal of Computer Vision, pages 1–19, 2020.
  * [43] Xingyi Zhou, Jiacheng Zhuo, and Philipp Krahenbuhl.  Bottom-up object detection by grouping extreme and center points.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 850–859, 2019.

##  Appendix A Supplementary Materials - Further Qualitative Results on MS
COCO

Included in this section are a number of qualitative examples for CenterNet
[10] and the proposed DeformCaps on the MS COCO test-dev dataset [21] using
both flip and multi-scale augmentations. Results for CenterNet were obtained
using the official code and trained models provided by the authors [10].

Figure 4: CenterNet [10] (leftmost) consistently produces a higher number of
false positives than the proposed DeformCaps (center), as compared to the
ground-truth annotations (rightmost) on the MS COCO test-dev dataset.

Figure 5: CenterNet [10] (leftmost) consistently produces a higher number of
false positives than the proposed DeformCaps (center), as compared to the
ground-truth annotations (rightmost) on the MS COCO test-dev dataset.

Figure 6: Some more qualitative examples showing CenterNet [10] (leftmost)
consistently producing a higher number of false positive detections than the
proposed DeformCaps (center), as compared to the ground-truth annotations
(rightmost) on the MS COCO test-dev dataset.

Figure 7: Qualitative examples showing CenterNet [10] (leftmost) struggling to
detect objects being presented in unusual poses or from unusual viewpoints,
while the proposed DeformCaps (center) successfully captures these cases, as
compared to the ground-truth annotations (rightmost) on the MS COCO test-dev
dataset.

Figure 8: A few more qualitative examples showing CenterNet [10] (leftmost)
struggling to detect objects being presented in in unusual poses or from
unusual viewpoints, while the proposed DeformCaps (center) successfully
captures these cases, as compared to the ground-truth annotations (rightmost)
on the MS COCO test-dev dataset.