# FLIVVER: Fly Lobula Inspired Visual Velocity Estimation & Ranging

Bryson Lingenfelter*, Arunava Nag†, and Floris van Breugel† *Department of
Computer Science and Engineering., University of Nevada, Reno. Email:
<EMAIL_ADDRESS>of Mechanical Engineering., University
of Nevada, Reno. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The mechanism by which a tiny insect or insect-sized robot could estimate its
absolute velocity and distance to nearby objects remains unknown. However,
this ability is critical for behaviors that require estimating wind direction
during flight, such as odor-plume tracking. Neuroscience and behavior studies
with insects have shown that they rely on the perception of image motion, or
optic flow, to estimate relative motion, equivalent to a ratio of their
velocity and distance to objects in the world. The key open challenge is
therefore to decouple these two states from a single measurement of their
ratio. Although modern SLAM (Simultaneous Localization and Mapping) methods
provide a solution to this problem for robotic systems, these methods
typically rely on computations that insects likely cannot perform, such as
simultaneously tracking multiple individual visual features, remembering a 3D
map of the world, and solving nonlinear optimization problems using iterative
algorithms. Here we present a novel algorithm, FLIVVER111Flivver: (n) a cheap
car or aircraft, especially one in bad condition, which combines the geometry
of dynamic forward motion with inspiration from insect visual processing to
directly estimate absolute ground velocity from a combination of optic flow
and acceleration information. Our algorithm provides a clear hypothesis for
how insects might estimate absolute velocity, and also provides a theoretical
framework for designing fast analog circuitry for efficient state estimation,
which could be applied to insect-sized robots.

##  I Introduction

To navigate complex environments, robots and animals require accurate
information about their current state relative to their surroundings. Two key
components of that state are their absolute ground velocity and the distance
to nearby objects. Humans, as well as other similarly scaled animals or
robots, can estimate the distance to an object based on the relative position
of that object on the two retinas. This mechanism is referred to as binocular
parallax. Changes of these distance measurements over time provide an estimate
of velocity. For smaller animals such as insects and insect-sized robots [1,
2], however, the error in stereo-based depth and velocity estimates is
exponentially larger [3, 4]. In this paper we present a bio-inspired and bio-
plausible algorithm for estimating velocity directly from image motion and
acceleration information.

We begin with a brief review of insect motion-vision. Over the past 30 years,
the visual system of insects, including blow flies (_Calliphora_), fruit flies
(_Drosophila_), locusts, and others has received a great deal of attention
from neuroscientists. These studies have discovered a variety of neurons that
respond to apparent image motion, also known as optic flow [5].
Mathematically, optic flow is the image angular velocity $\dot{\alpha}$,
defined for each receptor angle, $\alpha$, across the eye’s retina. Insects
calculate optic flow using a feature-agnostic neural circuit that implements a
“delay-and-correlate” calculation between pairs of receptors [6, 7, 8]. These
individual optic flow measurements are then pooled together by myriad neurons.
The most celebrated of these are located in the lobula plate, and integrate
optic flow across the entire field of view to respond to rotations about
specific axes [9, 10, 11]. Other related wide field cells are selective for
looming stimuli [12]. In _Calliphora_ , directionally sensitive cells with
smaller receptive fields ($\sim$40°) have also been described, referred to as
FD (figure detection) cells [13]. Finally, a recently described class of cells
in _Drosophila_ referred to as the lobula columnar cells have smaller
receptive fields and are sensitive expanding stimuli and motion of small
objects [14]. Still other neurons remain to be fully characterized [15]. The
diverse optic flow sensitive neurons described in insects can broadly be
thought of as matched-filters for specific types of motion with different
spatial receptive fields [16]. Matched filtered optic flow has, previously,
been used for obstacle avoidance and control in small quad-rotors [17]. In
this paper, we take loose inspiration from these observations by using
matched-filters and spatial-pooling of optic flow to solve an otherwise ill-
conditioned mathematical problem.

Optic flow is geometrically proportional to the ratio of velocity and distance
(see Section III). Drawing on a nonlinear observability analysis, it can be
shown that velocity and distance can be extracted from a sequence of
measurements of their ratios, but only when a measurable and non-zero
acceleration is applied [3]. Although possible, developing algorithms to solve
this problem that are robust and efficient remains an active area of research
in computer vision and robotics.

##  II Related Work

Algorithms designed to solve the state estimation problem are generally
referred to as SLAM (Simultaneous Localization and Mapping) algorithms.
Developing SLAM algorithms that rely on a combination of visual and inertial
information (VI-SLAM) has been of particular interest, because cameras and
inertial measurement units (IMUs) are cheap and ubiquitous. The simplest SLAM
algorithms for resolving scale ambiguity require two cameras, and rely on the
known distance between the cameras to resolve the metric scaling of estimates
(for example, [18]). With a single camera, IMU data is required to estimate
the scale factor.

Monocular visual-inertial (VI) SLAM has recently received significant
attention (for a concise review see [19]). Although some efforts have been
made to use optic flow for VI-SLAM [20], this approach relies on a neural
network trained on specific images. As such, the scale factor does not
reliably generalize to other environments. Most other approaches rely on
tracking individual visual features across frames [21][22]. Because of the
computational cost of tracking features, most real-time systems use sparse
collections of visual features [23]. Even when tracking individual features,
however, the problem is quite challenging. One solution is to use a nonlinear
Kalman Filter (e.g. an Extended Kalman Filter) to fuse data from the visual
features and the IMU to estimate the scale factor [24]. This approach,
however, requires the integration of sensor measurements over the course of
10-15 seconds before the algorithm converges and proper SLAM can begin. With
the growing interest in the field of monocular SLAM, Stumberg et. al [22] took
an approach of dynamic configuration of the scaling factor. Here, an initial
arbitrary scale was assumed instead of delaying the initialization required to
observe all the parameters. Although this approach allows initial state
estimates to be made immediately, the algorithm still requires considerable
time for the iterative method to converge to achieve an optimum scale.

In general terms, most existing monocular SLAM algorithms rely on nonlinear
joint optimizations of the visual and inertial measurements across sliding
windows [25]. These computations require remembering past key frames, building
and remembering a (sparse) 3D map of the world, and iteratively solving
complex optimizations that are not guaranteed to converge using, for example,
Gauss-Newton methods or Extended Kalman filters. By contrast, the FLIVVER
algorithm directly computes absolute velocity without the need for memory
beyond a few frames.

##  III Geometry of Forward Motion

Although optic flow algorithms provide an estimate at each pixel, for
visualization we consider only a single point. This is illustrated in Figure
1. The relationship between the forward distance $d$, and the lateral distance
$l$ to a visual feature can be written as

$tan(\alpha)=\frac{l}{d},$ (1)

Figure 1: Change in relationship to scene geometry over time during forward
motion.

where $\alpha$ is the angle between the center of the viewpoint and the visual
feature. We derive Eqn 1 with respect to time using the chain rule to find
$\dot{\alpha}$, the optic flow:

$\frac{\dot{\alpha}}{cos^{2}(\alpha)}=\frac{\frac{\partial}{\partial
t}l}{d}-\frac{l\frac{\partial}{\partial t}d}{d^{2}}.$ (2)

Flies spend the majority ($80\%$) of their time flying in straight lines [26],
which simplifies their visual experience by limiting it to pure forward
translation. Flies are able to keep a straight heading using mechanosensory
structures called halteres, which are thought to act as gyroscopes [27, 28].
Inspired by this behavioral tendency to fly straight, our paper exclusively
considers straight forward motion, though we discuss future extensions in
Section VIII. Assuming perfectly straight motion, $\frac{\partial}{\partial
t}l=0$, $l=dtan(\alpha)$, and $-\frac{\partial}{\partial t}d$ is simply the
forward velocity, $v$. Plugging these values in and solving for
$\dot{\alpha}$, we get the following relationship,

$\dot{\alpha}=\frac{-v}{d}cos(\alpha)sin(\alpha).$ (3)

If neither $v$ nor $d$ is known, optic flow alone does not give enough
information to compute either. However, by taking the time derivative of
$\frac{v}{d}$, the equation can be rewritten in a way that separates $v$ and
$d$:

$\frac{\partial}{\partial t}\frac{(-v)}{d}=\frac{\frac{\partial}{\partial
t}(-v)}{d}-\frac{(-v)^{2}}{d^{2}}=\frac{-a}{d}-\Big{(}\frac{v}{d}\Big{)}^{2},$
(4)

where $a$ is the forward acceleration. This equation can now be rewritten as
the following,

$d=\frac{-a}{\big{(}\frac{v}{d}\big{)}^{2}-\frac{\partial}{\partial
t}\frac{v}{d}},$ (5)

which we simplify by introducing a new variable,

$r=\frac{v}{d},$ (6)

such that Eqn 5 becomes222Note that we define velocity in the forward
direction here, whereas a previous publication defined $-v$ as the forward
direction resulting in all three terms being positive,

$d=\frac{-a}{r^{2}-\dot{r}}.$ (7)

Thus, so long as acceleration is non-zero, the distance to a visual feature in
the forward direction can be estimated using measurements of acceleration,
optic flow, and the derivative of optic flow. By combining Eqn 7 with the
relationship $d=v/r$, we can also find the equivalent relationship for
estimating velocity,

$v=\frac{-ar}{r^{2}-\dot{r}}.$ (8)

Note that Eqn 8 is defined for each $\alpha$ in the visual field,
corresponding to a receptor in the biological case, and to a pixel in the
mechanical case. The velocity and acceleration, $v$ and $a$, however, are
defined in the forward direction, and should therefore be identical for each
pixel. We can take advantage of this by estimating $v$ for each pixel then
computing the average to improve the overall estimate.

Although these mathematical relationships show that it is theoretically
possible to estimate velocity and distance, in practice several issues arise.
First, the calculations are extremely sensitive to $\dot{r}$, which is
difficult to estimate given noisy optic flow measurements. Second, the
geometry is defined based on the image motion of an individual visual feature,
not the motion seen by a given pixel. Thus, calculating $\dot{r}$ requires
following features from one moment to the next, which is computationally
expensive to do for a large number of features. If instead we attempt to
calculate $\dot{r}$ on a per-pixel basis, new objects that come into, or
leave, the field of view will dramatically change $\dot{r}$. Third, close to
$\alpha=0$, Equations 6, 7, and 8, approach $\frac{0}{0}$, which causes the
estimates to be unreliable in real world implementations. In the next section
we draw on inspiration from a fly’s visual processing to overcome these three
issues.

##  IV Bio-inspiration

To circumvent the practical issues that arise in implementing Eqn 8, we take
inspiration from what is known about the visual processing circuitry in
insects. In particular, we note that (a) the majority of fly visual processing
circuitry throughout the lobula and lobula plate operate as matched filters,
in that they are sensitive to particular kinds of motion, and (b) these
neurons pool information across receptive fields that range from $\sim
20-200^{\circ}$. Both operations can dramatically reduce noise in the
measurements of $r$, which helps produce a better estimate of $\dot{r}$.
Matched filtering reduces noise by only using optic flow information that
matches what is expected based on the type of motion. For example, if the
motion is straight forward, the optic flow field must be radiating out from
the center. Any deviations from this are by definition noise and can be
ignored (Fig. 2). Spatial pooling further helps to reduce noise.
Mathematically we can describe the spatial pooling by rewriting Eqn 8 as
follows,

$\overline{\bigg{(}\frac{v}{a}\bigg{)}_{f_{k}}}=\overline{\Bigg{(}\frac{-r}{r^{2}-\dot{r}}\Bigg{)}_{f_{k}}},$
(9)

where $f_{k}$ represents a particular receptive field (region of interest)
over which the mean is calculated. Rewriting this expression to the following
equivalent,

$\overline{v_{f_{k}}}=a\Bigg{(}\frac{-\overline{r_{f_{k}}}}{\overline{r_{f_{k}}^{2}}-\dot{\overline{r_{f_{k}}}}}\Bigg{)},$
(10)

where $a$ is the measured acceleration, allows us to spatially pool
$\overline{r_{f_{k}}}$ before calculating $\dot{\overline{r_{f_{k}}}}$,
reducing the effect of measurement noise on the derivative. Note, however,
that $\overline{r_{f_{k}}^{2}}\neq{(\overline{r_{f_{k}}})^{2}}$. We can
efficiently combine both the spatial pooling and matched filtering operations
into a single step by taking the dot product between $r$, and $f_{k}$ and
summing the resulting 2D matrix. This is equivalent to what small field optic
flow sensitive neurons in a flies lobula accomplish. Repeating this
calculation for many different receptive fields yields a collection of
velocity estimates which can then be averaged to find a more accurate velocity
estimate.

Figure 2: Matched filtering can reduce noise when the expected flow profile is
known. In this figure, noisy optic flow from forward motion is filtered
according to the expected flow created by forward motion. (A) Shows the result
for a full field filter, whereas (B) is for a smaller receptive field.

##  V Dataset

We test our method using an Intel RealSense D435i depth camera. The camera
provides monocular RGB images, depth images, accelerometer data, and gyroscope
data. The depth camera is moved horizontally on a track surrounded by several
objects. To collect ground-truth translation data for evaluation, we track the
velocity of the depth camera using a second overhead camera. Our data
collection setup is shown in Figure 3.

RGB and depth data are recorded at 30 frames per second, and odometry data is
recorded at 250 frames per second. We average the odometry data such that
there are 30 readings per second to be consistent with the camera data. To
collect the dataset, the camera was moved forward and backward on a track for
80 seconds with varying acceleration.

Figure 3: Setup used for tracking ground-truth velocity.

##  VI FLIVVER Implementation

Figure 4: Summary the FLIVVER algorithm for directly estimating velocity from
optic flow and acceleration. Figure designed using FigureFirst [29].

###  VI-A Estimating Optic Flow

Optic flow ($\dot{\alpha}$), the angular velocity at each pixel in the image,
can be estimated using a variety of dedicated VLSI hardware systems [30, 31,
32], and computer vision algorithms including Lucas Kanade [33, 34], and the
more recent deep neural network, FlowNet 2.0 [35]. To compute optic flow, we
use NVIDIA’s Pytorch implementation of the FlowNet 2.0 model [36] with the
pre-trained model provided by the FlowNet 2.0 authors. Computer vision
techniques for optic flow estimation give results in units of $pixels/frame$,
which we convert to $radians/second$ using the camera’s field of view and
image resolution.

30 frames per second of RGB data is useful for obtaining many samples to
construct estimates from, but is problematic for calculating optic flow which
is far more inaccurate when motion is very small. To deal with this, we
stagger flow calculations as shown in Figure 4. Flow at each frame is
calculated as the flow between that frame and the flow six frames forward.
This provides us a flow estimate every $\frac{1}{30}$ seconds, even though
each individual flow calculation is using frames $\frac{1}{5}$ seconds apart.

Figure 5: Comparison of algorithms for estimating depth directly from optic
flow, and the velocity estimates provided by the FLIVVER algorithm described
in Fig. 4. Note that the $CVX\big{(}(v/d)^{-1}\big{)}*\hat{v}$ approach
provides significantly better estimates, at the cost of the computation time.
The image sequence chosen here is for positive velocity and negative
acceleration.

###  VI-B Estimating Velocity Over Distance

Pure forward translation places substantial constraints on the flow field; if
the scene is rigid, computation of optic flow is reduced to a 1D search
problem [37],[38]. Assuming strictly forward motion, flow should be directed
out of the center of the image. We ensure this constraint holds by aligning
images using gyroscope data to remove rotation. We then multiply the output of
FlowNet by the full matched filter shown in Figure 2, restricting the
direction of the flow. Finally, we divide each pixel by
$cos(\alpha)sin(\alpha)$ to obtain an estimate of $\frac{v}{d}$. This is done
twice, once with horizontal angles and the horizontal component of flow and
once with vertical angles and the vertical component of flow. Our final
estimate of $\frac{v}{d}$ is the average of these two.

The general flow of the algorithm for calculating dense $\frac{v}{d}$ maps is
shown in Figure 4. First, optic flow is computed using two images 200
milliseconds apart. Next, the flow is aligned using a matched filter. Finally,
the aligned flow is divided by $cos(\alpha)sin(\alpha)$ to produce an estimate
of $\frac{v}{d}$. The $\frac{v}{d}$ estimate is highly noisy in the center of
the image, where angles are very small, but otherwise reasonably approximates
ground-truth $\frac{v}{d}$.

###  VI-C Estimating Velocity

Because of the challenges associated with differentiating noisy measurements
of $v/d$, we use the receptive fields approach to described in Section IV to
spatially pool our noisy $v/d$ measurements. In our implementation we use $90$
matched filters, each with a field of view of $5^{\circ}\times 5^{\circ}$,
spanning the entire field of view. For each receptive field, we calculate
$\overline{r_{f_{k}}}$ and $\overline{r_{f_{k}}^{2}}$. To estimate
$\dot{\overline{r_{f_{k}}}}$, we first apply a Butterworth filter to
$\overline{r_{f_{k}}}$ and then take a staggered finite difference derivative,
so each value of $\overline{r_{f_{k}}}$ is compared to the value of
$\overline{r_{f_{k}}}$ 5 frames previously. This delay further helps reduce
noise in the estimates. Together, these three terms and the acceleration
provide a velocity estimate for each receptive field according to Eqn 10. We
then find the median velocity estimate.

The resulting velocity estimates are still quite noisy, so we smooth them
using a Butterworth filter. Estimates from the filter are in terms of forward
velocity, so if there there was some amount of rotation this velocity is not
the total velocity of the camera. We correct this by multiplying the velocity
by $cos(a)$, where $a$ is the rotation change between the two frames. In our
dataset this term is small enough to be negligible. For all Butterworth
filtering we used a first-order filter with $w_{n}=0.04N_{f}$ where $N_{f}$ is
the Nyquist frequency.

###  VI-D Estimating Depth

Because our method provides estimates of $\frac{v}{d}$ and $v$, it is simple
to invert $\frac{v}{d}$ and multiply by $v$ to obtain depth estimates. In
practice, this approach causes issues near the epipole. If the camera is not
moving perfectly straight, the epipole (where $\dot{\alpha}=0$) is not aligned
with $\alpha=0$. This offset results in pixels where $v/d=\epsilon/0$ instead
of exactly $0/0$, causing $v/d$ to be erroneously large. Additionally, any
noise in $\dot{\alpha}$ near the epipole will have a similar effect. These
issues are avoided in the velocity calculations through spatial pooling, but
for creating a dense depth map that is accurate near the epipole, they must be
addressed.

Future work will focus on efficient, bio-inspired, and bio-plausible methods.
In this paper we present a preliminary approach that works well, but is too
computationally expensive to run in real time. Our approach is to find
$\hat{\dot{\alpha}}$, an estimate for the optic flow that is better aligned
with $\alpha$. To find $\hat{\dot{\alpha}}$, we minimize the following loss
function,

$L=\sum(\dot{\alpha}-\hat{\dot{\alpha}})^{2}+\gamma\;\sum\Bigg{(}\frac{\partial}{\partial\alpha}\bigg{(}\frac{\hat{\dot{\alpha}}+\hat{\beta}}{cos(\alpha)sin(\alpha)}\bigg{)}\Bigg{)}^{2},$
(11)

where $\hat{\beta}$ is a constant offset, and $\gamma$ is a tuning parameter.
The first term in $L$ ensures that $\hat{\dot{\alpha}}$ will remain faithful
to the measured $\alpha$. The second term penalizes spatial derivative of
$v/d$, and is equivalent to penalizing the total variation of $v/d$, so we can
rewrite Eqn 11 as follows,

$L=\sum(\dot{\alpha}-\hat{\dot{\alpha}})^{2}+\gamma\;TV\bigg{(}\frac{\hat{\dot{\alpha}}+\hat{\beta}}{cos(\alpha)sin(\alpha)}\bigg{)}.$
(12)

The tuning parameter, $\gamma$ determines the balance between the faithfulness
of $\hat{\dot{\alpha}}$ and the smoothness of $v/d$. $L$ is convex, and can
efficiently be solved using convex optimization tools (such as cvxpy [39] and
the MOSEK solver).

Alternatively, we can compute depth directly from optic flow. Once we have
computed velocity we can reconstruct camera rotation and translation using
gyroscope data. This allows us to use traditional methods for computing depth
from optic flow. The plane+parallax representation can be used to compute
depth estimates if the scene is rigid [40]. These estimates are ill-defined
near the epipole, but otherwise reasonably approximate scene geometry. Depth
maps for all methods are shown in Figure 5.

##  VII Evaluation

###  VII-A Accuracy of Velocity and Depth Estimates

We evaluate the FLIVVER algorithm by comparing the velocity estimates to
ground truth data collected using an external tracking camera (see Section V).
FLIVVER locks onto the correct absolute velocity in a few seconds, and
achieves an $RMS$ error of $0.13$ (Fig. 6A-B). By comparison, naively
integrating the acceleration results in the signal drifting away from the
correct estimate within 5-10 seconds. For certain trajectories, a Kalman
filter (cyan) may provide a better output than the simple Butterworth filter
we use in the FLIVVER algorithm. However, for this dataset it does not improve
the estimates ($RMSE=0.129$). Finally, we compare the three methods for
estimating dense depth maps described in Fig. 5 to the ground truth data from
the RealSense camera (Fig. 6C). Generally, both the velocity and depth
estimates are worst for high velocities, likely stemming from high levels of
motion blur in the RGB images.

Figure 6: FLIVVER performance. (A) Comparison between ground truth velocity
(dashed black) and the FLIVVER algorithm summarized in Fig. 4 (magenta).
Without true velocity estimates, integrating the acceleration accumulates
large errors before long (green). Replacing the butterworth smoothing step
with a constant acceleration Kalman smoother does not improve performance in a
significant way. (B) FLIVVER velocity estimate errors as a function of time.
(C) Error in depth estimates for the three methods shown in Fig. 5

###  VII-B Computation Time

A significant advantage of the FLIVVER approach is the potential for very fast
computations times compared with feature-based tracking methods. This is
because the majority of the computations can be done in parallel, and
primarily consist of matrix multiplication or simple filtering. Our
implementation prototype resulted in a total computation time of 110ms per
frame. Almost all of this time is consumed by the computation of optic flow
using FlowNet 2.0, as shown in Table I.

TABLE I: Velocity estimation computation times for a 448x640 pixel image stream. Flownet2 calculations were done on an NVIDIA GTX 1080 TI GPU. All other calculations were done on an Intel Xeon CPU E5-2620 @ 2.10GHz Step | Description | Compute | Parallel
---|---|---|---
|  | time | threads
1A | Image alignment (optional) | 13ms | no
1B | Optic flow from Flownet2 | 93ms | no
2 | (Time to contact)-1 | $7\mu s$ | no
3 | $\\{\overline{r_{f_{k}}},\;\dot{\overline{r_{f_{k}}}},\;\overline{r^{2}_{f_{k}}}\\}$ | 3.8ms | yes
4 | Raw vel estimate | $0.3\mu s$ | yes
5 | Median vel estimate | $8\mu s$ | no
6 | Filtered vel estimate | $1\mu s$ | no
| Total | 110ms |

Directly computing baseline depth maps from velocity and $\frac{v}{d}$ only
requires scalar inversion and multiplication, and can therefore be computed in
microseconds. The convex optimization method, however, takes roughly 20
seconds per frame and is therefore not feasible for real-time applications.

##  VIII Discussion

In this paper we describe a novel algorithm, FLIVVER, for directly estimating
forward velocity from a single camera using optic flow and acceleration. The
goal of this research is two-fold: (a) to provide a concrete hypothesis for
how insects might estimate their absolute ground velocity, and (b) to provide
an efficient method for state estimation that could be implemented on size-
power-weight constrained flying autonomous vehicles. Since FLIVVER provides a
direct estimate of velocity without the need for algorithm convergence, it
could also help reduce the convergence time for existing visual-inertial SLAM
algorithms. The following subsections discuss limitations, and future focus
areas.

###  VIII-A Limitations: Optic Flow

The FLIVVER algorithm relies on high quality estimates of optic flow. In our
implementation we used Flownet2, which does a good job of estimating optic
flow even in texture-poor regions but is by far the slowest portion of our
pipeline. Other, more efficient implementations may be less reliable. To
reduce the effect of bad estimates resulting from low texture regions, the
median calculation (step 5), could use weighted estimates, where the weighting
is proportional to the quality of the optic flow estimate, based on the
quality of the texture in a given window.

###  VIII-B Limitations: Acceleration

Any monocular SLAM algorithm requires non-zero accelerations to provide
accurate absolute velocity estimates [3]. FLIVVER is no different. Real-world
implementations on robotic systems would likely benefit from the addition of a
Kalman filter where the co-variance of the raw velocity estimate is inversely
proportional to the magnitude of the acceleration. This would help improve
velocity estimates for portions of the trajectory that have constant, and non-
zero velocity.

###  VIII-C Future Directions: Incorporating Rotation

In the current implementation, we focused exclusively on straight forward
motion. This is inspired by the observation that flies spend the majority of
their time moving along straight paths, simplifying their visual experience.
In the future, we will use a combination of gyroscopic measurements, and fly-
inspired wide field matched filters to estimate rotation, allowing our
algorithm to estimate both forward and rotational velocity. To estimate full
6-DOF velocity components will also require us to estimate lateral and
vertical velocity. For this, we plan to develop bio-inspired algorithms for
estimating the location of the epipole, rather than assuming it is in the
center of the field of view.

###  VIII-D Future Directions: Reducing Computation Times for Depth Estimates

Our primary goal is to present an algorithm for estimating velocity. However,
given that the combination of velocity estimates and optic flow make it
possible to estimate dense depth maps, we present preliminary results for
these as well. Estimating depth away from the epipole can be done very
quickly. Close to the epipole, however, additional computation time is
required to solve a convex optimization problem. Future work will focus on
discovering a bio-plausible and efficient approach for these calculations,
such as training an artificial neural network to accomplish the same task.

###  VIII-E Future Directions: Analog Circuitry

A major advantage of the FLIVVER algorithm for velocity estimation is that
each computational step can, in theory, be implemented using analog circuitry,
resulting in very fast state estimation. Although neural networks themselves
can also, in principle, be implemented using analog circuits [41], these
circuits would require more custom hardware and significantly more components.
Finally, the FLIVVER algorithm does not require any learning methods, and is
therefore easier to implement in a general manner. Table II summarizes the
types of calculations involved in each step of FLIVVER’s velocity estimation,
and their analog equivalents.

TABLE II: Summary of the types of calculations FLIVVER uses (see Fig. 4), and candidate analog equivalents. Step | Description | Current | Analog
---|---|---|---
Step | Description | Approach | Equivalent
|  |  | Analog VLSI
1 |  $\dot{\alpha}$ from Flownet2 | Neural net | Optic Flow
|  |  | [30, 31, 32]
2 | (Time to contact)-1 | Matrix Multiplication | [42]
3 | $\\{\overline{r_{f_{k}}},\;\dot{\overline{r_{f_{k}}}},\;\overline{r^{2}_{f_{k}}}\\}$ | Matrix Multiplication | [42]
4 | Raw vel estimate | Matrix Multiplication | [42]
5 | Median vel estimate | Median Calculation | [43]
6 | Filtered vel estimate | Butterworth filter | RLC circuit

## Acknowledgements

The authors thank James Hanna and Matteo Aureli for enlightening discussions
leading to the selection of our algorithm’s acronym.

## References

  * [1] K. Y. Ma, P. Chirarattananon, S. B. Fuller, and R. J. Wood, “Controlled flight of a biologically inspired, insect-scale robot,” _Science_ , vol. 340, no. 6132, pp. 603–607, May 2013. [Online]. Available: https://doi.org/10.1126/science.1231806
  * [2] D. Floreano and R. J. Wood, “Science, technology and the future of small autonomous drones,” _Nature_ , vol. 521, no. 7553, pp. 460–466, May 2015\. [Online]. Available: https://doi.org/10.1038/nature14542
  * [3] F. van Breugel, K. Morgansen, and M. H. Dickinson, “Monocular distance estimation from optic flow during active landing maneuvers,” _Bioinspiration & Biomimetics_, vol. 9, no. 2, p. 025002, May 2014.
  * [4] A. Verri and V. Torre, “Absolute depth estimate in stereopsis,” _Journal of the Optical Society of America A_ , vol. 3, no. 3, p. 297, Mar. 1986. [Online]. Available: https://doi.org/10.1364/josaa.3.000297
  * [5] N. Malcolm and J. J. Gibson, “The perception of the visual world.” _The Philosophical Review_ , vol. 60, no. 4, p. 594, Oct. 1951. [Online]. Available: https://doi.org/10.2307/2181436
  * [6] B. Hassenstein and W. Reichardt, “Systemtheoretische analyse der zeit-, reihenfolgen- und vorzeichenauswertung bei der bewegungsperzeption des rüsselkäfers chlorophanus,” _Zeitschrift für Naturforschung B_ , vol. 11, no. 9-10, pp. 513–524, Oct. 1956. [Online]. Available: https://doi.org/10.1515/znb-1956-9-1004
  * [7] H. H. Yang and T. R. Clandinin, “Elementary motion detection in drosophila: Algorithms and mechanisms,” _Annual Review of Vision Science_ , vol. 4, no. 1, pp. 143–163, Sep. 2018. [Online]. Available: https://doi.org/10.1146/annurev-vision-091517-034153
  * [8] A. Borst, J. Haag, and A. S. Mauss, “How fly neurons compute the direction of visual motion,” _Journal of Comparative Physiology A_ , Nov. 2019. [Online]. Available: https://doi.org/10.1007/s00359-019-01375-9
  * [9] H. G. Krapp and R. Hengstenberg, “Estimation of self-motion by optic flow processing in single visual interneurons,” _Nature_ , vol. 384, no. 6608, pp. 463–466, Dec. 1996. [Online]. Available: https://doi.org/10.1038/384463a0
  * [10] B. Schnell, M. Joesch, F. Forstner, S. V. Raghu, H. Otsuna, K. Ito, A. Borst, and D. F. Reiff, “Processing of horizontal optic flow in three visual interneurons of the drosophila brain,” _Journal of Neurophysiology_ , vol. 103, no. 3, pp. 1646–1657, Mar. 2010. [Online]. Available: https://doi.org/10.1152/jn.00950.2009
  * [11] M. P. Suver, A. Huda, N. Iwasaki, S. Safarik, and M. H. Dickinson, “An array of descending visual interneurons encoding self-motion in drosophila,” _The Journal of Neuroscience_ , vol. 36, no. 46, pp. 11 768–11 780, Nov. 2016. [Online]. Available: https://doi.org/10.1523/jneurosci.2277-16.2016
  * [12] N. C. Klapoetke, A. Nern, M. Y. Peek, E. M. Rogers, P. Breads, G. M. Rubin, M. B. Reiser, and G. M. Card, “Ultra-selective looming detection from radial motion opponency,” _Nature_ , vol. 551, no. 7679, pp. 237–241, Nov. 2017\. [Online]. Available: https://doi.org/10.1038/nature24626
  * [13] M. Egelhaaf, “On the neuronal basis of figure-ground discrimination by relative motion in the visual system of the fly,” _Biological Cybernetics_ , vol. 52, pp. 195–209, Jul. 1985. [Online]. Available: https://link.springer.com/article/10.1007/BF00339948
  * [14] M. Wu, A. Nern, W. R. Williamson, M. M. Morimoto, M. B. Reiser, G. M. Card, and G. M. Rubin, “Visual projection neurons in the drosophila lobula link feature detection to distinct behavioral programs,” _eLife_ , vol. 5, Dec. 2016. [Online]. Available: https://doi.org/10.7554/elife.21022
  * [15] H. Wei, H. Y. Kyung, P. J. Kim, and C. Desplan, “The diversity of lobula plate tangential cells (LPTCs) in the drosophila motion vision system,” _Journal of Comparative Physiology A_ , Nov. 2019. [Online]. Available: https://doi.org/10.1007/s00359-019-01380-y
  * [16] M. O. Franz and H. G. Krapp, “Wide-field, motion-sensitive neurons and matched filters for optic flow fields,” _Biological Cybernetics_ , vol. 83, no. 3, pp. 185–197, Aug. 2000. [Online]. Available: https://doi.org/10.1007/s004220000163
  * [17] J. Conroy, G. Gremillion, B. Ranganathan, and J. S. Humbert, “Implementation of wide-field integration of optic flow for autonomous quadrotor navigation,” _Autonomous Robots_ , vol. 27, no. 3, pp. 189–198, Aug. 2009\. [Online]. Available: https://doi.org/10.1007/s10514-009-9140-0
  * [18] Ma, Bai, Wang, and Fang, “Robust stereo visual-inertial odometry using nonlinear optimization,” _Sensors_ , vol. 19, no. 17, p. 3747, Aug. 2019\. [Online]. Available: https://doi.org/10.3390/s19173747
  * [19] G. Huang, “Visual-inertial navigation: A concise review,” _arXiv_ , 2019.
  * [20] B. Ummenhofer, H. Zhou, J. Uhrig, N. Mayer, E. Ilg, A. Dosovitskiy, and T. Brox, “Demon: Depth and motion network for learning monocular stereo,” in _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , July 2017.
  * [21] R. Mur-Artal and J. D. Tardós, “Visual-inertial monocular slam with map reuse,” _IEEE Robotics and Automation Letters_ , vol. 2, no. 2, pp. 796–803, 2017.
  * [22] L. Von Stumberg, V. Usenko, and D. Cremers, “Direct sparse visual-inertial odometry using dynamic marginalization,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 2510–2517.
  * [23] J. Engel, V. Koltun, and D. Cremers, “Direct sparse odometry,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 40, no. 3, pp. 611–625, Mar. 2018. [Online]. Available: https://doi.org/10.1109/tpami.2017.2658577
  * [24] G. Nützi, S. Weiss, D. Scaramuzza, and R. Siegwart, “Fusion of imu and vision for absolute scale estimation in monocular slam,” _Journal of Intelligent & Robotic Systems_, vol. 61, no. 1, pp. 287–299, Jan 2011.
  * [25] S. Leutenegger, S. Lynen, M. Bosse, R. Siegwart, and P. Furgale, “Keyframe-based visual–inertial odometry using nonlinear optimization,” _The International Journal of Robotics Research_ , vol. 34, no. 3, pp. 314–334, Dec. 2014. [Online]. Available: https://doi.org/10.1177/0278364914554813
  * [26] F. van Breugel and M. H. Dickinson, “The visual control of landing and obstacle avoidance in the fruit fly drosophila melanogaster,” _Journal of Experimental Biology_ , vol. 215, no. 11, pp. 1783–1798, May 2012. [Online]. Available: https://doi.org/10.1242/jeb.066498
  * [27] J. Pringle, “The gyroscopic mechanism of the halteres of diptera,” _Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences_ , vol. 233, no. 602, pp. 347–384, Nov. 1948. [Online]. Available: https://doi.org/10.1098/rstb.1948.0007
  * [28] B. H. Dickerson, A. M. de Souza, A. Huda, and M. H. Dickinson, “Flies regulate wing motion via active control of a dual-function gyroscope,” _Current Biology_ , vol. 29, no. 20, pp. 3517–3524.e3, Oct. 2019. [Online]. Available: https://doi.org/10.1016/j.cub.2019.08.065
  * [29] T. Lindsay, P. Weir, and F. van Breugel, “FigureFirst: A layout-first approach for scientific figures,” in _Proceedings of the 16th Python in Science Conference_. SciPy, 2017. [Online]. Available: https://doi.org/10.25080/shinma-7f4c6e7-009
  * [30] R. Harrison, “A biologically inspired analog IC for visual collision detection,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 52, no. 11, pp. 2308–2318, Nov. 2005. [Online]. Available: https://doi.org/10.1109/tcsi.2005.853517
  * [31] V. Mahalingam, K. Bhattacharya, N. Ranganathan, H. Chakravarthula, R. R. Murphy, and K. S. Pratt, “A VLSI architecture and algorithm for lucas–kanade-based optical flow computation,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 18, no. 1, pp. 29–38, Jan. 2010. [Online]. Available: https://doi.org/10.1109/tvlsi.2008.2006900
  * [32] G. L. Barrows and C. Neely, “Mixed-mode vlsi optic flow sensors for in-flight control of a micro air vehicle,” in _Critical Technologies for the Future of Computing_ , S. Bains and L. J. Irakliotis, Eds. SPIE, Nov. 2000. [Online]. Available: https://doi.org/10.1117/12.409204
  * [33] B. D. Lucas and T. Kanade, “An iterative image registration technique with an application to stereo vision (ijcai),” in _Proceedings of the 7th International Joint Conference on Artificial Intelligence (IJCAI ’81)_ , April 1981, pp. 674–679.
  * [34] S. Baker and I. Matthews, “Lucas-kanade 20 years on: A unifying framework,” _International Journal of Computer Vision_ , vol. 56, no. 3, pp. 221–255, Feb. 2004. [Online]. Available: https://doi.org/10.1023/b:visi.0000011205.11775.fd
  * [35] E. Ilg, N. Mayer, T. Saikia, M. Keuper, A. Dosovitskiy, and T. Brox, “Flownet 2.0: Evolution of optical flow estimation with deep networks,” in _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , Jul 2017.
  * [36] F. Reda, R. Pottorff, J. Barker, and B. Catanzaro, “flownet2-pytorch: Pytorch implementation of flownet 2.0: Evolution of optical flow estimation with deep networks,” https://github.com/NVIDIA/flownet2-pytorch, 2017.
  * [37] M. Irani, P. Anandan, and M. Cohen, “Direct recovery of planar-parallax from multiple frames,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 24, no. 11, pp. 1528–1534, 2002.
  * [38] J. Wulff, L. Sevilla-Lara, and M. J. Black, “Optical flow in mostly rigid scenes,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 4671–4680.
  * [39] S. Diamond and S. Boyd, “CVXPY: A Python-embedded modeling language for convex optimization,” _Journal of Machine Learning Research_ , vol. 17, no. 83, pp. 1–5, 2016.
  * [40] Z. Li, T. Dekel, F. Cole, R. Tucker, N. Snavely, C. Liu, and W. T. Freeman, “Learning the depths of moving people by watching frozen people,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 4521–4530.
  * [41] Y. Du, L. Du, X. Gu, J. Du, X. S. Wang, B. Hu, M. Jiang, X. Chen, S. S. Iyer, and M.-C. F. Chang, “An analog neural network computing engine using CMOS-compatible charge-trap-transistor (CTT),” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 38, no. 10, pp. 1811–1819, Oct. 2019. [Online]. Available: https://doi.org/10.1109/tcad.2018.2859237
  * [42] C. R. Schlottmann and P. E. Hasler, “A highly dense, low power, programmable analog vector-matrix multiplier: The FPAA implementation,” _IEEE Journal on Emerging and Selected Topics in Circuits and Systems_ , vol. 1, no. 3, pp. 403–411, Sep. 2011. [Online]. Available: https://doi.org/10.1109/jetcas.2011.2165755
  * [43] P. Dietz and L. Carley, “An analog circuit technique for finding the median,” in _Proceedings of IEEE Custom Integrated Circuits Conference - CICC_. IEEE, 1993. [Online]. Available: https://doi.org/10.1109/cicc.1993.590571


# Fact-Tree Reasoning for N-ary Question Answering
over Knowledge Graphs

Yao Zhang1 Peiyao Li1 Hongru Liang2 Adam Jatowt3 Zhenglu Yang1
1TKLNDST, CS, Nankai University, China, 2Sichuan University, China,
3University of Innsbruck, Austria
$\left\\{\right.$yaozhang<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
Corresponding author.

###### Abstract

Current Question Answering over Knowledge Graphs (KGQA) task mainly focuses on
performing answer reasoning upon KGs with binary facts. However, it neglects
the $n$-ary facts, which contain more than two entities. In this work, we
highlight a more challenging but under-explored task: $n$-ary KGQA, i.e.,
answering $n$-ary facts questions upon $n$-ary KGs. Nevertheless, the multi-
hop reasoning framework popular in binary KGQA task is not directly applicable
on $n$-ary KGQA. We propose two feasible improvements: 1) upgrade the basic
reasoning unit from entity or relation to fact, and 2) upgrade the reasoning
structure from chain to tree. Therefore, we propose a novel fact-tree
reasoning framework, FacTree, which integrates the above two upgrades. FacTree
transforms the question into a fact tree and performs iterative fact reasoning
on the fact tree to infer the correct answer. Experimental results on the
$n$-ary KGQA dataset we constructed and two binary KGQA benchmarks demonstrate
the effectiveness of FacTree compared with state-of-the-art methods.

##  1 Introduction

The task of Question Answering over Knowledge Graphs (KGQA) has provided new
avenues to the recent development of QA systems by utilizing the advantages of
KGs Yu et al. (2017); Dubey et al. (2019); Huang et al. (2019); Zhang et al.
(2021). Current KGQA studies mainly consider performing answer reasoning upon
KGs with binary facts, which encode binary relations between pairs of
entities, e.g., Golden State Warriors’ arena is Chase Center111Entities are
underlined.. However, $n$-ary facts that involve more than two entities are
also ubiquitous in reality Guan et al. (2019); Abboud et al. (2020); Wang et
al. (2021), e.g., the ternary fact Golden State Warriors won the NBA
championship in 2018. Compared to binary facts, $n$-ary facts have more
information content. This makes the answer reasoning for questions involving
$n$-ary facts more intractable, exposing open challenges in KGQA. In this
work, we aim to study the under-explored $\bm{n}$-ary KGQA task, i.e.,
answering $n$-ary facts questions upon $n$-ary KGs.

The multi-hop reasoning KGQA method Das et al. (2018); Qiu et al. (2020);
Saxena et al. (2020); Ren et al. (2021) has become popular for its high
efficiency and interpretability. Specifically, the reasoning process can be
expressed as a chain, starting from an entity extracted from the question and
then walking on the KG by connected relations and entities until arriving at
the answer entity. See Figure 1 (b) for an example, to answer the question,
what is the address of the arena of the Golden State Warriors, the reasoning
chain starts from Golden State Warriors, to walk through
“arena$\rightarrow$Chase Center$\rightarrow$address", and it ends at 1
Warriors Way, i.e., the answer. Multi-hop reasoning has been studied widely on
the binary KGQA task. Here, we first try to execute it on the $n$-ary KGQA
task.

Figure 1:  (a) A KG fragment, where entities are represented by round
rectangles. Win and join are two ternary relations. (b) and (c) are two QA
examples, where the correct answer is marked by a star. The multi-hop
reasoning method can be used to answer Q1, and the reasoning process can be
visualized as a chain (b). However, for the more complex Q2, the multi-hop
reasoning method is not applicable. We use fact as the basic reasoning unit to
construct the reasoning process. As shown in (c), the reasoning process can be
visualized as a fact tree: fact 2 and fact 3 are leaf nodes need to be
inferred first, and then the two inferred entities (Los Angeles Lakers and
2018) are transmitted to the root node (fact 1). Finally the root node infers
the answer entity (LeBron James).

However, we find that multi-hop reasoning is not directly applicable on
$n$-ary KGQA. We take the $n$-ary facts question in Figure 1 (c) as an example
to explain. First, the essence of multi-hop reasoning is to construct a
reasoning chain by treating the relation as the translation between two
entities Bordes et al. (2013); Ren and Leskovec (2020), naturally in a linear
structure. However, the transition from binary to $n$-ary facts is similar to
the transition from a line to a plane. For a single $n$-ary fact (e.g., Golden
State Warriors won the NBA championship in 2018), the reasoning chain could
only include two entities Golden State Warriors and NBA championship and a
relation win involving them, leading to the possible loss of important
information 2018. To overcome this weakness, we propose that upgrading the
basic reasoning unit from an entity or relation to the fact to expand the
coverage of information during reasoning.

Nevertheless, multi-hop reasoning would still be less capable in more complex
reasoning scenarios where a question involves multiple $n$-ary facts. For
example, the question in Figure 1 (c) is composed of three facts. When using
fact as the basic reasoning unit, the whole reasoning process can be
represented as a tree structure, where nodes represent facts and edges reflect
the reasoning order. Specifically, in the fact tree, the entities (Los Angeles
Lakers and 2018) which are missing in the two leaf nodes (fact 2 and fact 3)
are first inferred and then passed to the root node (fact 1). The root node
can then finally infer the correct answer entity LeBron James. Obviously, the
chain structure used in the multi-hop reasoning framework is evidently
insufficient to cope with the tree structure. Therefore, to improve the
ability to cope with more complex reasoning scenarios, we propose that
upgrading the reasoning structure from chian to tree.

In this work, we propose a novel fact-tree reasoning framework, namely,
FacTree, which integrates the above two upgrades and pipelines the answer
reasoning process into three steps: 1) fact tree construction, which
transforms an input natural language (NL) question into an NL fact tree; 2)
fact location, which locates the NL fact onto the KG; and 3) fact reasoning,
which iterates intra-fact and inter-fact reasoning to infer the answer. During
the intra-fact reasoning, the $n$-ary KG embedding model Guan et al. (2020) is
plugged in to alleviate the deficiency of KG incompleteness. The explicit tree
reasoning structure makes the results strongly interpretable. Furthermore, we
develop a new dataset called WikiPeopleQA to foster research on $n$-ary KGQA.
We then conduct comprehensive experiments on WikiPeopleQA dataset to show that
FacTree has the desired ability to perform effective reasoning on $n$-ary fact
questions. Besides, on two binary KGQA datasets, FacTree also indicates a
strong ability to infer answers compared with state-of-the-art methods
accurately.

Our study fundamentally contributes to bridging the gap between binary KGQA
and $n$-ary KGQA. The proposed FacTree can serve as a preliminary foundation
for the $n$-ary KGQA. To summarize, our contributions are:

Figure 2:  Overview of FacTree. It takes the question (Q) as an input, passes
through a three-stage pipeline processing: 1) fact tree construction (Sec.
3.1), 2) fact location (Sec. 3.2) and 3) fact reasoning (Sec. 3.3), and
finally gets the answer entity (A). Placeholders $\Box$ in the NL and KG fact
trees indicate the entities to be inferred.

  * $\bullet$

We highlight a more challenging task: $n$-ary KGQA than a standard binary KGQA
task setting. We further observe that the multi-hop reasoning framework
popular in binary KGQA is no longer applicable to $n$-ary KGQA.

  * $\bullet$

We propose a novel fact-tree reasoning framework, FacTree, which can serve as
a preliminary foundation for $n$-ary KGQA study. And we develop a new dataset:
WikiPeopleQA to foster research on $n$-ary KGQA.

  * $\bullet$

We conduct comprehensive experiments to show that our framework has the
desired reasoning ability for both $n$-ary and binary KGQA tasks.

##  2 Related Work

The previous series of KGQA models Liang et al. (2011); Berant et al. (2013);
Yih et al. (2014); Lan and Jiang (2020); Sun et al. (2020); Wolfson et al.
(2020) synthesize a structured query graph from the question and then match
the query with KG to get the answer. This type of model has high
interpretability but is challenged by the incomplete nature of KGs. Then
another series models compute the semantic similarity of the question and each
candidate answer directly in the latent space Bordes et al. (2015); Dong et
al. (2015); Hamilton et al. (2018); Zhang et al. (2018b). This type of model
overcomes the limitation of incomplete KG, but lacks sufficient
interpretability. FacTree uses facts as the basic reasoning unit to alleviate
the deficiency of KG incompleteness and the explicit tree reasoning structure
to realize strongly interpretable.

Multi-hop reasoning framework has attracted widespread attention due to its
high flexibility and high interpretability in recent years Fu et al. (2020).
Current efforts build an explicit reasoning chain through training a
reinforcement learning agent to walk on the KG Das et al. (2018); Qiu et al.
(2020); Kaiser et al. (2021), or construct implicit reasoning chains through
memory network Sukhbaatar et al. (2015); Miller et al. (2016); Chen et al.
(2019) or in the latent space Bordes et al. (2014); Saxena et al. (2020); Ren
and Leskovec (2020); He et al. (2021); Ren et al. (2021). This kind of method
performs well on binary fact questions but has difficulties in dealing with
$n$-ary fact questions. Of course, one could construct and synthesize multiple
reasoning chains to tackle $n$-ary KGQA. But this would inevitably lead to an
exponential increase in the reasoning difficulty and computational complexity,
which in turn affects the reasoning performance.

Our work first highlights the $n$-ary KGQA task. The research of $n$-ary KG
provides a feasible research foundation for $n$-ary KGQA. KG embedding
learning on $n$-ary facts Wen et al. (2016); Zhang et al. (2018a); Fatemi et
al. (2019); Guan et al. (2019, 2020); Abboud et al. (2020) has grown
considerably in recent years. The $n$-ary KG embedding model Guan et al.
(2020) is plugged in FacTree to alleviate the reasoning difficulties caused by
the KG incompleteness.

##  3 Fact-tree Reasoning

Figure 3: An example of NL fact tree construction (partial steps). The
eliminations of nodes in the order of
❶$\rightarrow$❷$\rightarrow$❸$\rightarrow$❹$\rightarrow\cdots$. Best viewed in
color.

We illustrate the fact-tree reasoning framework for $n$-ary KGQA in Figure 2.
It takes the question (Q) as an input, passes through a three-stage pipeline
processing, and finally gets the answer entity (A). In the first fact tree
construction stage, we construct the NL fact tree from the NL question (Sec.
3.1). In the second fact location stage, we locate the NL fact onto the KG to
obtain the KG fact tree (Sec. 3.2). This helps to bridge the semantic and
structure gap between the unstructured NL and the structured KG. In the last
fact reasoning stage, we perform intra-fact and inter-fact reasoning
iteratively on the KG fact tree to infer the answer entity (Sec. 3.3).

We use fact as the basic reasoning unit in the fact-tree reasoning framework.
In the NL fact tree, the fact is represented as a sequence of words and
placeholders, where the words are taken from the NL question, and the
placeholders refer to the missing entities to be inferred, e.g., the fact
($\Box$ joined $\Box$ in the year $\Box$). In the KG fact tree, following Guan
et al. (2020), we represent the $n$-ary fact as

$fact\\!=\\!(s,p,o),\left\\{a_{1}\\!:\\!v_{1},a_{2}\\!:\\!v_{2},...,a_{m}\\!:\\!v_{m}\right\\}\\!,$
(1)

where $(s,p,o)$ denotes the subject-predicate-object information in the fact,
named primary triple; each
$\\!a_{i}\\!:\\!v_{i}~{}(i\\!\in\\!\\{1,2,...,m\\})$ is an attribute value
pair, a.k.a., the auxiliary description to the primary triple. For example,
the ternary fact LeBron James joined Los Angeles Lakers in 2018 is formalized
as (LeBron James, join, Los Angeles Lakers), {time: 2018}. Note that the
binary fact only contains the primary triple.

###  3.1 Fact tree construction

In FacTree, we use fact as the basic reasoning unit and use the tree structure
to represent the associations among facts. Here, we design an automatic NL
fact tree construction algorithm to transfer the NL question to the NL fact
tree. Since the syntax tree naturally expresses the hierarchical relation of
the elements of the sentence and in order to facilitate the subsequent
locating of the NL facts into KG, we use the syntax tree222We use the Stanford
Parser to generate the syntax tree. The leaf nodes are words or phrases of Q
and the branch nodes are syntax labels, e.g., NP (Noun Phrase) and VP (Verb
Phrase). of Q as the initial structure. We expect the constructed NL fact tree
to satisfy the following characteristics: 1) the leaf nodes are words or
phrases of Q; and 2) if the leaf nodes share the same parent node, they belong
to the same fact. Therefore, the NL fact tree construction algorithm can be
viewed as an iterative eliminating of nodes in the syntax tree to achieve
clustering of nodes within facts and differentiation between facts.

The node elimination process starts from the antepenult level of the syntax
tree and proceeds from bottom to top. We observe that two semantically
different questions may be parsed into the same syntax structure except for
the leaf nodes. Therefore, disregarding leaf nodes makes our algorithm more
adaptable. Also, the parent node of a leaf node needs to be reserved for
identifying the leaf node. Figure 3 shows a specific example 333Due to the
space limitation, only part of the syntax tree and the corresponding
elimination steps are shown here.. As shown in (a), the pruning starts from
the node VP (❶, colored in red). To decide whether to eliminate this node or
not, we extract a subtree that contains the node and its neighbor nodes
(colored in blue). This subtree is fed into a classifier $f(\cdot)$, which is
composed of a Graph Convolutional Network (GCN) as embedding layer and a
fully-connected layer. If $f(\cdot)$ outputs “eliminate”, the node will be
eliminated and its children will be directly connected to its parent, as shown
in (b). Otherwise, this node will be retained. This process continues until
the iteration meets the root node. Finally, we remove non-leaf nodes and keep
the hierarchical structure of leaf nodes. The nodes in the upper-layer facts
that are connected to the lower-layer facts are replaced with placeholders, as
shown in (c). We summarize the construction of NL fact tree in Algorithm 1.

Input: The question Q, empty node stacks $\mathbb{V},\mathbb{V}^{\prime}$;

Output: The NL fact tree FT;

1

2Initialization

3 $\rm FT=Parse(\text{\bf Q})$,

4 $\mathbb{V}=$BFS(FT);

5 while $\mathbb{V}$ do

6 $v=\mathbb{V}.pop()$;

7 if $v.isLeaf()$ or $v.children.isLeaf()$ then

8 continue;

9 else

10 $\mathbb{V}^{\prime}.push(v)$;

11 end if

12

13 end while

14

15while $v\neq\rm{FT}.root$ do

16 $v=\mathbb{V}^{\prime}.pop()$;

17
$T_{v}=\left\\{v\right\\}\cup\left\\{v.parent\right\\}\cup\left\\{v.children\right\\}$;

18 if $f(T_{v})==eliminate$ then

19 update

20 for each $child$ in $v.children$ do

21 $child.set\\_parent(v.parent,\text{FT})$

22 end for

23 FT$.delete(v)$

24 end if

25

26 end while

Algorithm 1 NL Fact Tree Construction

Specifically, for the GCN, we use the propagation rule for calculating the
node embedding update for each layer as follows:

$\bm{h}_{v}^{(i+1)}=\sigma_{i}(\bm{h}_{v}^{(i)}\bm{W}_{0}^{(i)}+\sum_{u\in
T_{v}\setminus v}\bm{h}_{u}^{(i)}\bm{W}_{1}^{(i)}),$ (2)

where $v$ and $T_{v}$ follow the definitions in Algorithm 1, $u$ is one of the
neighbors of $v$, $\bm{h}_{*}^{(i)}$ represents the hidden layer activations
of nodes in the $i^{th}$ layer, $\sigma_{i}(\cdot)$ is the activation
function, and $\bm{W}_{0,1}^{(i)}$ are the $i$-layer weight matrices.

###  3.2 Fact Location

This stage aims to transfer the NL fact tree to the KG fact tree,
specifically, to locate each NL fact in the tree to a KG fact. It is divided
into three specific steps: 1) entity linking, 2) structure matching, and 3)
relation extraction.

During entity linking, following the standard setting in KGQA Saxena et al.
(2020), we assume that the entities of the question are given and linked to
nodes on the KG. Note that the placeholders are directly reserved and they
indicate the entities that need to be inferred.

The key of structure matching is to locate the subject $s$, predicate $p$,
object $o$, attribute $a$ and value $v$ in the NL fact. We view this process
as a sequence labelling task, as shown in Figure 4. We believe that location
labels are more strongly associated with syntax labels, compared to word
sequences. Therefore, the input is the sequence formed by the syntax labels of
each node in the NL fact. The output is the sequence of location labels, and
the label set is $\left\\{s,p,o,a,v\right\\}$. Here,we adopt the BiLSTM-CRF
model Huang et al. (2015) to perform sequence labelling.

Figure 4: Example of a structure matching process.

After entity matching, we conduct relation extraction, i.e., transferring the
word sequences labelled $p$ or $a$ to the corresponding relations (predicates
or attributes) in KG. Specifically, we adopt pre-trained SBERT model Reimers
and Gurevych (2019) to get the embeddings of the relation in KG (i.e.,
$\bm{r}$) and the word sequences (i.e., $\bm{w}$). Then we use cosine
similarity as a scoring function $s(\cdot)$ to assign scores to the two
embeddings and select the relation with the highest score:

$\begin{split}s(r,w)\\!=\\!\frac{r\cdot
w}{\left\|r\right\|\\!\left\|w\right\|}\\!=\\!\frac{{\textstyle\sum_{i=1}^{n}\\!r_{i}w_{i}}}{\sqrt{\sum_{i=1}^{n}\\!r_{i}^{2}}\\!\sqrt{\sum_{i=1}^{n}\\!w_{i}^{2}}}.\end{split}$
(3)

Finally, combining the predicted location labels, and linked entities and
extracted relations, NL facts can be transformed into KG facts (cf. Figure 2).
Placeholders are the bridge between upper-layer and lower-layer facts.
Interestingly, due to the variability of NL organization, there may be no
placeholder in the lower-layer fact. It is because when constructing the NL
fact tree, the placeholder (usually value) is assigned to upper-layer fact
according to the syntax structure. Therefore, we directly copy the upper-layer
placeholder directly to the lower-layer fact. For example, in Figure 2, the
fact the Warriors won the NBA championship will be transformed to (Golden
State Warriors, win, NBA championship), {time:2018}, where the attribute time
is copied from the upper-layer fact.

###  3.3 Fact Reasoning

In this stage, we perform the inter-fact and intra-fact reasoning iteratively
based on the KG fact tree to find the answer entity. One example of iterative
reasoning process is shown in Figure 5.

Figure 5: Example of an iterative reasoning process. The order of reasoning is
❶$\rightarrow$❷$\rightarrow$❸$\rightarrow$❹$\rightarrow$❺.

Inter-fact Reasoning The whole process of inter-fact reasoning is carried out
in a bottom-up manner. Specifically, the entity inferred from the lower-layer
fact will be transferred to the upper-layer fact. For example, the entity 2018
inferred from fact 3 will be transferred to fact 1, i.e., the second step in
Figure 5.

Table 1: Statistics of WikiPeopleQA, WC2014 and PathQuestion, as well as their
subsets. Note that the $n$-ary here means that $n$ is greater than $2$.

Dataset | # Question-Answer Pair | Background KG
---|---|---
Total | Subset | # Fact | # Entity | # Relation(binary) | # Relation($n$-ary)
WikiPeopleQA (1F/2F/3F) | 4,491 | 2,365 / 1,497 / 629 | 56,426 | 28,043 | 150 | 557
WC2014 (1H/2H/C) | 10,162 | 6,482 / 1,472 / 2,208 | 6,482 | 1,127 | 6 | 0
PathQuestion (2H/3H) | 7,106 | 1,908 / 5,198 | 4,049 | 2,215 | 14 | 0

Intra-fact reasoning This module aims to infer the missing entity of each
incomplete fact. We formulate this process as the KG completion task. KG
embedding models Bordes et al. (2013); Dettmers et al. (2018); Guan et al.
(2019, 2020) are studied to deal with this task, by learning entity and
relation embeddings and designing a scoring function to infer the missing
entity. In this work, we use NeuInfer Guan et al. (2020), a KG embedding model
that can perform on binary and $n$-ary facts, to implement intra-fact
reasoning.

However, comparing with the traditional KG completion task, the missing entity
needs not only to complete the current fact, but also to satisfy the upper-
layer fact. For example, in fact 2, Sunset Boulevard and Los Angeles Lakers
are all located in Los Angeles. While, considering the upper-layer fact 1, the
missing entity needs to satisfy the fact that the predicate is join.
Therefore, we introduce a score amplification mechanism: if an alternative
entity can satisfy the upper-layer fact, its corresponding score will be
magnified $\lambda$ times.

###  3.4 Training

The classifier $f(\cdot)$ and BiLSTM-CRF model are trained in a supervised
manner, where the training signals are obtained from manually labeled (syntax
tree, NL fact tree) and (syntax label sequence, location label sequence)
pairs, respectively. We observe the syntax structure of different questions
may be similar or even consistent. Therefore, we reduce the the input space by
using syntax-related information rather than NL, to relieve the manual
annotation pressure and also the learning difficult.

##  4 Experiments

###  4.1 Dataset

In this work, we target at studying the $n$-ary KGQA task. Considering the
popular KGQA datasets involve almost exclusively binary facts, we develop an
$n$-ary KGQA dataset: WikiPeopleQA (abbr. WP), in which questions involve
multiple $n$-ary facts and the background KG is also composed of $n$-ary
facts. We also conduct evaluation on two binary KGQA benchmarks: WC2014 (abbr.
WC) Zhang et al. (2016) and PathQuestion (abbr. PQ) Zhou et al. (2018).
Depending on the number of Facts or Hops involved in the question444Note that,
for a binary fact question, the hop number is generally equal to the fact
number., WikiPeopleQA is divided into WP-1F, WP-2F and WP-3F. WC2014 is
divided into WC-1H and WC-2H, as well as a conjunctive question set WC-C.
PathQuestion is divided into PQ-2H and PQ-3H. We partition the three datasets
into train/valid/test subsets with a proportion of 8 : 1 : 1. The detailed
statistics are shown in Table 1.

###  4.2 Experimental Setup

####  4.2.1 Training Details

During training the classifier, the embedding size of node is 50, the learning
rate is $1e{-5}$, and the number of GCN layers is 3. During training the
BiLSTM-CRF model, the embedding size of node is 100, the learning rate is
$2e{-5}$. We use Adam optimizer for optimization for above training process.
The hyper-parameter $\lambda$ is set to 1.5. The training process of the KG
embedding model used in the fact reasoning stage is following Guan et al.
(2020). The experimental results are all averaged across three training
repetitions.

Model | WP | WP-1F | WP-2F | WP-3F | WC | WC-1H | WC-2H | WC-C | PQ | PQ-2H | PQ-3H
---|---|---|---|---|---|---|---|---|---|---|---
MemNN Sukhbaatar et al. (2015) | 32.9 | 34.2 | 39.6 | 12.5 | 52.4 | 71.6 | 55.5 | 73.3 | 86.8 | 89.5 | 79.2
KV-MemNN Miller et al. (2016) | 24.5 | 15.0 | 40.0 | 16.0 | 76.7 | 87.0 | 87.0 | 78.8 | 85.2 | 91.5 | 79.4
EmbedKGQA Saxena et al. (2020) | 26.4 | 35.4 | 22.3 | 3.5 | 52.5 | 59.6 | 79.0 | 52.0 | 36.7 | 51.0 | 30.6
IRN-weak Zhou et al. (2018) | - | - | - | - | 78.6 | 83.4 | 92.1 | 83.7 | 85.8 | 91.9 | 83.3
MINERVA Das et al. (2018) | 10.9 | 20.5 | 0.3 | 0.2 | 89.6 | 87.2 | 93.1 | 82.4 | 73.1 | 75.9 | 71.2
SRN Qiu et al. (2020) | 13.3 | 24.9 | 0.3 | 0.8 | 96.5 | 98.9 | 97.8 | 87.3 | 89.3 | 96.3 | 89.2
QGG Lan and Jiang (2020) | 24.9 | 41.8 | 1.1 | 0.0 | 94.0 | 94.9 | 92.9 | 99.9 | 40.4 | 67.8 | 28.9
FacTree | 54.4 | 63.1 | 47.0 | 40.1 | 99.5 | 99.9 | 96.3 | 99.9 | 92.8 | 98.4 | 90.8

Table 2: Model Performance on $n$-ary KGQA task (WikiPeopleQA dataset) and
binary KGQA task (WC2014 and PathQuestion datasets) under the accuracy(%)
metric (pairwise t-test at 5% significance level). The best performance
results are shown in bold, and the second best results are shown in
underlined.

####  4.2.2 Baselines

We compare our framework with a series of popular multi-hop reasoning baseline
approaches. According to the form of the reasoning chain, these baselines can
be divided into two categories. The first category baseline builds an explicit
reasoning chain through training an agent to walk on the KG: IRN-weak Zhou et
al. (2018), MINERVA Das et al. (2018) and SRN Qiu et al. (2020); the second
category baseline builds an implicit reasoning chain through memory network or
in the latent space: MemNN Sukhbaatar et al. (2015), KV-MemNN Miller et al.
(2016) and EmbedKGQA Saxena et al. (2020). We also compare with QGG Lan and
Jiang (2020), which synthesizes a query graph from the question and then match
the query with KG to get the answer. When evaluating explicit multi-hop
reasoning methods and QGG, we use the dummy entity to divide $n$-ary facts in
the KG of WikiPeopleQA into binary facts.

###  4.3 Main Results

Performance of FacTree Table 2 presents the statistics of model’s performances
both on the $n$-ary and binary KGQA tasks. We can see that FacTree achieves
significantly higher accuracy than state-of-the-art baselines on the $n$-ary
KGQA task. Specifically, compared with the best performing multi-hop reasoning
baseline MemNN, FacTree improves accuracy by 21.5% (w.r.t., WP). We have
following discoveries:

  * $\bullet$

FacTree shows large advantages on coping with complex questions with multiple
facts. On the WP-3F sub-dataset, comparing with baselines, FacTree has made a
qualitative leap on accuracy (16.0$\rightarrow$40.1). This confirms that
multi-hop reasoning methods are inapplicable to more complex reasoning
scenarios.

  * $\bullet$

Interestingly, the explicit multi-hop reasoning methods (e.g., SRN) are
obviously weaker than implicit methods (e.g., EmbedKGQA). This is because the
$n$-ary facts are split by dummy entities, adding difficulty to build explicit
reasoning chains. Implicit methods weaken the distinction between binary and
$n$-ary facts, which makes it more flexible in dealing with $n$-ary facts.

  * $\bullet$

The QGG method directly matches the generated query graph to the KG, resulting
in performing well on questions with less facts, but clearly lacking
flexibility for question with more facts.

Besides, fact-tree reasoning also achieves a good performance on binary KGQA.
We observe a large performance gap between multi-hop reasoning methods on
binary and $n$-ary KGQA tasks. Therefore, it would be valuable to pay more
attention to the study of $n$-ary KGQA.

Figure 6: Staged evaluation of FacTree. $\rm{FL}^{*}$ and $\rm{intraFR}^{*}$
denote turning off the FL and intraFR components respectively. Note that the
accuracy of FacTree($\rm{FL}^{*}$+$\rm{intraFR}^{*}$+$\rm{interFR}^{*}$) is
100%. Figure 7:  Error instances in the fact location, intra-fact and inter-
fact reasoning stages, respectively.

Staged Evaluation We test the capability of each stage of FacTree. Because the
fact-tree reasoning framework is a pipeline structure, the reasoning error
always occurs in cascade. We turn off the components on the pipeline from the
beginning to see the impact on the overall effect. “Turn off a component”
means to replace the real output with the ground truth, that is, the component
is perfect by default. We test three components of FacTree: fact location
(FL), intra-fact reasoning (intraFR) and inter-fact reasoning (interFR). The
error caused by the fact tree construction stage is negligible here because of
the relatively small number of NL fact tree types in the datasets. Figure 6
shows turning off the components in turn will lead to an accuracy increase of
22.3% (FL), 18.2% (intraFR) and 5.1% (interFR) respectively (w.r.t., WP).
Impressively, transferring the NL fact tree to KG fact tree and inferring
missing entities of incomplete facts are the two keys that affect the
reasoning accuracy. Moreover, the influence of the inter-fact reasoning module
becomes apparent as the number of facts increases. This is because it may
happen that an entity satisfying the lower-layer fact may not be able to
satisfy the upper-layer fact. For instances of errors in each module, please
see Section 4.4.

###  4.4 Analysis of FacTree

Performance w.r.t. Incomplete KGs As the capacity of the KG continues to
expand, current KGs are typically incomplete with many facts missing.
Incomplete KGs put forward higher requirements on the capabilities of KGQA
models. Therefore, we conduct an experiment on FacTree and two popular
baselines to test their reasoning capability for incomplete KGs. As shown in
Table 3, when the KG is reduced by half, the effect of our model decreases the
least. This is because we adopt KG embedding models to perform intra-fact
reasoning in FacTree. This design relaxes the requirements for KG
completeness. SRN requires the construction of query graph or explicit
reasoning chain on KG, so it is more sensitive to the incompleteness of KG.
EmbedKGQA also uses KG embedding models. The performance gap between it and
our FacTree corroborates the superiority of the fact-tree reasoning framework.

Zero-shot Learning w.r.t. Classifier $f(\cdot)$ We conduct a zero-shot
learning experiment to test the capability of our proposed classifier
$f(\cdot)$ in the fact construction stage though a 5-fold cross validation. We
evaluate the accuracy of the constructed NL fact tree on the mixed dataset
combined with three datasets (WikiPeopleQA, WC2014 and PathQuestion). The
mixed dataset is divided into five parts according to the NL fact tree
classes. For each fold, the fact tree classes in the testing set do not appear
in the training set. Based on this setting, our classifier can reach 81.2%
accuracy with a standard deviation of 0.098. This indicates our classifier has
the scalable ability to construct unseen fact trees.

Model | WP | WP-50% | WC | WC-50%
---|---|---|---|---
SRN | 13.3 | 0.1 ($\downarrow$99%) | 96.5 | 0.0 ($\downarrow$100%)
EmbedKGQA | 26.4 | 6.5 ($\downarrow$75%) | 52.5 | 11.0 ($\downarrow$79%)
FacTree | 54.4 | 17.8 ($\downarrow$67%) | 99.5 | 37.2 ($\downarrow$63%)

Table 3: Performance on incomplete KGs. $\downarrow$ indicates the decrease in
accuracy when the KG is halved.

Effectiveness of GCN We also test the effect of the execution range of the GCN
on the accuracy of the fact tree construction. The range of GCN execution is a
subtree of the syntax tree containing the central node to be eliminated and
its neighbor nodes. A total of five range types are tested depending on
whether the father, siblings and child of the central node were included. As
shown in Table 4, the optimal subtree range includes the central node and its
father and child nodes. Interestingly, the addition of sibling nodes did not
bring significant effect improvement.

Size | O | O+F | O+C | O+F+C | O+F+C+S
---|---|---|---|---|---
Acc. | 52.9 | 53.9 | 63.1 | 91.4 | 91.0

Table 4: Performance of different subtree range w.r.t. fact tree construction
stage. “F”, “C” and “S” denote the father, child and sibling nodes of the
central node “O”, respectively.

Error Analysis We conduct a qualitative study on error instances, as shown in
Figure 7, and analysis the directions for future work. In the fact location
stage, introducing more effective relation extraction techniques can
contribute to reduce relation extraction error. In the intra-fact reasoning
stage, it is necessary to improve KG embedding model’s capability. There is a
false negative error case. For example, the fact (Liu Cang, sibling, Liu Yan)
is true, but is not included by KG, resulting in the inferred answer being
judged as wrong. So, adopting broader KGs is suggested in future studies. In
the inter-fact reasoning stage, entities can be incompatible when transferred
between facts. Therefore, intra- and inter-factual reasoning needs to act more
closely together to reduce the incompatibility.

##  5 Conclusion

This work highlights a more challenging task: $n$-ary KGQA, and it advocates
that the multi-hop reasoning framework popular in binary KGQA is no longer
applicable to $n$-ary KGQA. A novel fact-tree reasoning framework FacTree is
proposed, which pipelines the $n$-ary KGQA into three steps: fact tree
construction, fact location, and fact reasoning to infer the correct answer.
The quantitative and qualitative experimental results have demonstrated that
FacTree has superior reasoning ability on $n$-ary and binary fact questions.

##  6 Acknowledgements

This work was supported in part by National Natural Science Foundation of
China under Grant No.62006101, and in part by the China Postdoctoral Science
Foundation under Grant No.2021TQ0222 and No.2021M700094.

## References

  * Abboud et al. (2020) Ralph Abboud, İsmail İlkan Ceylan, Thomas Lukasiewicz, and Tommaso Salvatori. 2020.  Boxe: A box embedding model for knowledge base completion.  In _Proceedings of NeurIPS_.
  * Berant et al. (2013) Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. 2013.  Semantic parsing on freebase from question-answer pairs.  In _Proceedings of EMNLP_ , pages 1533–1544.
  * Bordes et al. (2014) Antoine Bordes, Sumit Chopra, and Jason Weston. 2014.  Question answering with subgraph embeddings.  In _Proceedings of EMNLP_ , pages 615–620.
  * Bordes et al. (2015) Antoine Bordes, Nicolas Usunier, Sumit Chopra, and Jason Weston. 2015.  Large-scale simple question answering with memory networks.  In _arXiv preprint arXiv:1506.02075_.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Durán, Jason Weston, and Oksana Yakhnenko. 2013.  Translating embeddings for modeling multi-relational data.  In _Proceedings of NeurIPS_ , pages 2787–2795.
  * Chen et al. (2019) Yu Chen, Lingfei Wu, and Mohammed J. Zaki. 2019.  Bidirectional attentive memory networks for question answering over knowledge bases.  In _Proceedings of NAACL-HLT_ , pages 2913–2923.
  * Das et al. (2018) Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishnamurthy, Alex Smola, and Andrew McCallum. 2018.  Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning.  In _Proceedings of ICLR_.
  * Dettmers et al. (2018) Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018.  Convolutional 2d knowledge graph embeddings.  In _Proceedings of AAAI_ , pages 1811–1818.
  * Dong et al. (2015) Li Dong, Furu Wei, Ming Zhou, and Ke Xu. 2015.  Question answering over Freebase with multi-column convolutional neural networks.  In _Proceedings of ACL-IJCNLP_ , pages 260–269.
  * Dubey et al. (2019) Mohnish Dubey, Debayan Banerjee, Abdelrahman Abdelkawi, and Jens Lehmann. 2019.  Lc-quad 2.0: A large dataset for complex question answering over wikidata and dbpedia.  In _Proceedings of ISWC_ , pages 69–78.
  * Fatemi et al. (2019) Bahare Fatemi, Perouz Taslakian, David Vazquez, and David Poole. 2019.  Knowledge hypergraphs: Prediction beyond binary relations.  In _arXiv preprint arXiv:1906.00137_.
  * Fu et al. (2020) Bin Fu, Yunqi Qiu, Chengguang Tang, Yang Li, Haiyang Yu, and Jian Sun. 2020.  A survey on complex question answering over knowledge base: Recent advances and challenges.  In _arXiv preprint arXiv:2007.13069_.
  * Guan et al. (2020) Saiping Guan, Xiaolong Jin, Jiafeng Guo, Yuanzhuo Wang, and Xueqi Cheng. 2020.  NeuInfer: Knowledge inference on N-ary facts.  In _Proceedings of ACL_ , pages 6141–6151.
  * Guan et al. (2019) Saiping Guan, Xiaolong Jin, Yuanzhuo Wang, and Xueqi Cheng. 2019.  Link prediction on n-ary relational data.  In _Proceedings of WWW_ , pages 583–593.
  * Hamilton et al. (2018) William L. Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. 2018.  Embedding logical queries on knowledge graphs.  In _Proceedings of NeurIPS_ , pages 2030–2041.
  * He et al. (2021) Gaole He, Yunshi Lan, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen. 2021.  Improving multi-hop knowledge base question answering by learning intermediate supervision signals.  In _Proceedings of WSDM_ , pages 553–561.
  * Huang et al. (2019) Xiao Huang, Jingyuan Zhang, Dingcheng Li, and Ping Li. 2019.  Knowledge graph embedding based question answering.  In _Proceedings of WSDM_ , pages 105–113.
  * Huang et al. (2015) Zhiheng Huang, Wei Xu, and Kai Yu. 2015.  Bidirectional lstm-crf models for sequence tagging.  In _arXiv preprint arXiv:1508.01991_.
  * Kaiser et al. (2021) Magdalena Kaiser, Rishiraj Saha Roy, and Gerhard Weikum. 2021.  Reinforcement learning from reformulations in conversational question answering over knowledge graphs.  In _Proceedings of SIGIR_.
  * Lan and Jiang (2020) Yunshi Lan and Jing Jiang. 2020.  Query graph generation for answering multi-hop complex questions from knowledge bases.  In _Proceedings of ACL_ , pages 969–974.
  * Liang et al. (2011) Percy Liang, Michael Jordan, and Dan Klein. 2011.  Learning dependency-based compositional semantics.  In _Proceedings of ACL_ , pages 590–599.
  * Miller et al. (2016) Alexander Miller, Adam Fisch, Jesse Dodge, Amir-Hossein Karimi, Antoine Bordes, and Jason Weston. 2016.  Key-value memory networks for directly reading documents.  In _Proceedings of EMNLP_ , pages 1400–1409.
  * Qiu et al. (2020) Yunqi Qiu, Yuanzhuo Wang, Xiaolong Jin, and Kun Zhang. 2020.  Stepwise reasoning for multi-relation question answering over knowledge graph with weak supervision.  In _Proceedings of WSDM_ , pages 474–482.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.  In _Proceedings of EMNLP_ , pages 3982–3992.
  * Ren et al. (2021) Hongyu Ren, Hanjun Dai, Bo Dai, Xinyun Chen, Michihiro Yasunaga, Haitian Sun, Dale Schuurmans, Jure Leskovec, and Denny Zhou. 2021.  Lego: Latent execution-guided reasoning for multi-hop question answering on knowledge graphs.  In _Proceedings of ICML_ , pages 8959–8970.
  * Ren and Leskovec (2020) Hongyu Ren and Jure Leskovec. 2020.  Beta embeddings for multi-hop logical reasoning in knowledge graphs.  In _Proceedings of NeurIPS_.
  * Saxena et al. (2020) Apoorv Saxena, Aditay Tripathi, and Partha Talukdar. 2020.  Improving multi-hop question answering over knowledge graphs using knowledge base embeddings.  In _Proceedings of ACL_ , pages 4498–4507.
  * Sukhbaatar et al. (2015) Sainbayar Sukhbaatar, arthur szlam, Jason Weston, and Rob Fergus. 2015.  End-to-end memory networks.  In _Proceedings of NeurIPS_ , pages 2440–2448.
  * Sun et al. (2020) Yawei Sun, Lingling Zhang, Gong Cheng, and Yuzhong Qu. 2020.  Sparqa: Skeleton-based semantic parsing for complex questions over knowledge bases.  In _Proceedings of AAAI_ , pages 8952–8959.
  * Wang et al. (2021) Quan Wang, Haifeng Wang, Yajuan Lyu, and Yong Zhu. 2021.  Link prediction on n-ary relational facts: A graph-based approach.  In _Proceedings of Findings of ACL-IJCNLP_ , pages 396–407.
  * Wen et al. (2016) Jianfeng Wen, Jianxin Li, Yongyi Mao, Shini Chen, and Richong Zhang. 2016.  On the representation and embedding of knowledge bases beyond binary relations.  In _Proceedings of IJCAI_ , pages 1300–1307.
  * Wolfson et al. (2020) Tomer Wolfson, Mor Geva, Ankit Gupta, Matt Gardner, Yoav Goldberg, Daniel Deutch, and Jonathan Berant. 2020.  Break It Down: A Question Understanding Benchmark.  In _TACL Journal_ , volume 8, pages 183–198.
  * Yih et al. (2014) Wen-tau Yih, Xiaodong He, and Christopher Meek. 2014.  Semantic parsing for single-relation question answering.  In _Proceedings of ACL_ , pages 643–648.
  * Yu et al. (2017) Mo Yu, Wenpeng Yin, Kazi Saidul Hasan, Cicero dos Santos, Bing Xiang, and Bowen Zhou. 2017.  Improved neural relation detection for knowledge base question answering.  In _Proceedings of ACL_ , pages 571–581.
  * Zhang et al. (2021) Jing Zhang, Bo Chen, Lingxi Zhang, Xirui Ke, and Haipeng Ding. 2021.  Neural-symbolic reasoning on knowledge graphs.  In _AI Open Journal_.
  * Zhang et al. (2016) Liwen Zhang, John Winn, and Ryota Tomioka. 2016.  Gaussian attention model and its application to knowledge base embedding and question answering.  In _arXiv preprint arXiv:1611.02266_.
  * Zhang et al. (2018a) Richong Zhang, Junpeng Li, Jiajie Mei, and Yongyi Mao. 2018a.  Scalable instance reconstruction in knowledge bases via relatedness affiliated embedding.  In _Proceedings of WWW_ , pages 1185–1194.
  * Zhang et al. (2018b) Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander Smola, and Le Song. 2018b.  Variational reasoning for question answering with knowledge graph.  In _Proceedings of AAAI_ , pages 6069–6076.
  * Zhou et al. (2018) Mantong Zhou, Minlie Huang, and Xiaoyan Zhu. 2018.  An interpretable reasoning network for multi-relation question answering.  In _Proceedings of ACL_ , pages 2010–2022.

##  Appendix A Methodology Details

###  A.1 NL Fact Tree Construction Algorithm

The construction of NL fact tree is summarized in Algorithm 1. The input is
the NL question and two empty node stacks. The output is the NL fact tree. We
initialize the NL fact tree as a syntax tree, which is parsed from Q (Line 2).
One of the empty node stack $\mathbb{V}$ stores the nodes of FT in the order
of breadth first searching (Line 3). The other stack $\mathbb{V}^{\prime}$
reverse this order in Line 4-10, so that the pruning (Line 12-22) is from the
the bottom to the top as well as from the right to the left. The entire
elimination process does not involve the leaf nodes and their parents nodes
(Line 6-10).

###  A.2 Score Amplification Mechanism

We devise a simple method to evaluate whether an entity is able to satisfy the
upper-layer fact. For an entity $e$, the related predicate or attribute in the
upper-layer fact is $p$ or $a$. We retrieve in KG, whether there is an fact of
entity $e$ associated with $p$ or $a$. If there is, then we consider that
entity $e$ is satisfying the upper-layer fact, and vice versa.

##  Appendix B Experimental Details

###  B.1 Dataset Construction

In this work, we develop an $n$-ary KGQA dataset: WikiPeopleQA, in which
questions involve multiple $n$-ary facts and the background KG is also
composed of $n$-ary facts. The specific construction process is as follows:

Figure 8: The fact combination modes.

  * i)

We selected WikiPeople Guan et al. (2019) as the background KG. This $n$-ary
KG is constructed based on Wikidata555https://www.wikidata.org and consists of
character facts, e.g., Marie Curie received Nobel Prize in Chemistry in 1911.

  * ii)

To build complex questions involving multiple facts, we set the maximum number
of facts in a question to three, and set four fact combinations modes in
advance, as shown in Figure 8. As the number of facts increases, the fact
combination mode becomes more complicated.

  * iii)

Based on the fact combination modes, we sampled a large number of fact
combinations from KG. We masked off the entities in the fact combinations, and
extracted the frequently occurring fact combinations. We transformed the
frequent fact combinations to question templates. Here we have constructed a
total of 33 question templates, listed in Table 5.

  * iv)

We populated the entities into the question templates according to KG.
Inspired by the construction process of PathQuestion Zhou et al. (2018), in
order to enrich the problematic syntactic structure and surface wording, we
replaced the phrases and words in the question with synonyms.

Due to the limitation of fact diversity in WikiPeople, we only considered
three facts at most. In order to contribute to the progress of $n$-ary KGQA
research, it is necessary to increase the richness of the facts to improve the
question complexity. Therefore, developing more complex $n$-ary KGQA datasets
and evaluating FacTree on more datasets are our future research directions.

###  B.2 Baselines

We compare our framework with a series of baselines. The following is a detail
description of the baselines:

  * $\bullet$

MemNN Sukhbaatar et al. (2015): This model adopts an memory network to store
all KG facts or related Wikipedia documents in the memory units. Three
embedding matrices are employed to convert the memory information and
questions into vectors for similarity calculation.

  * $\bullet$

KV-MemNN Miller et al. (2016): This model is based on MemNN. Instead of
considering the whole KG facts like MemNN, it firstly stores facts in a key-
value structured memory. The key-value structure is suitable for binary facts,
but not for $n$-ary facts.

  * $\bullet$

EmbedKGQA Saxena et al. (2020): This model follows the basic multi-hop
reasoning framework and utilizes KG embedding methods to alleviate the
negative impact of KG incompleteness.

  * $\bullet$

IRN-weak Zhou et al. (2018): This model considers the whole path from the
topic entity to the answer entity. It focuses on finding a path to the answer,
so IRN needs a pre-labelled path record during training process.

  * $\bullet$

MINERVA Das et al. (2018): This model uses reinforcement learning technique to
perform multi-hop reasoning on KG. Taking the input natural language question,
this model averages the word embeddings as the question embedding, and then
walks on KG under the supervision of the question embedding, and finally
arrives at the answer entity.

  * $\bullet$

SRN Qiu et al. (2020): This model uses RL method to perform multi-hop
reasoning on KG. It proposes a potential-based reward shaping strategy to
alleviate the delayed and sparse reward problem caused by weak supervision.

  * $\bullet$

QGG Lan and Jiang (2020): This model generates a modified staged query graph
to deal with complex questions with both multi-hop relations and constraints.

Here we explain the source of the results in Table 2. On the WikiPeopleQA
dataset, for each baseline, we run the source code of each baseline that is
open source or reproduced by developers.

  * $\bullet$

MemNN: https://github.com/berlino/MemNN (reproduced)

  * $\bullet$

KV-MemNN: https://github.com/lc222/key-value-MemNN (reproduced)

  * $\bullet$

EmbedKGQA: https://github.com/malllabiisc/EmbedKGQA (open source)

  * $\bullet$

MINERVA: https://github.com/shehzaadzd/MINERVA (open source)

  * $\bullet$

SRN: https://github.com/DanSeb1295/multi-relation-QA-over-KG (reproduced)

  * $\bullet$

QGG: https://github.com/lanyunshi/Multi-hopComplexKBQA (open source)

IRN-weak needs the pre-labelled path records for training, which is not
applicable to the $n$-ary KGQA task. So we do not evaluate IRN-weak.

For two binary KGQA datasets WC2014 and PathQuestion, the results of EmbedKGQA
and QGG are obtained by our own tests. Other baseline results all cited from
Qiu et al. (2020).

###  B.3 Training Details

Note that in the NL fact tree, there is overlap between facts. When we
construct the (syntax tree, NL fact tree) training samples, the overlap will
be maintained in the lower-layer fact if it belongs to the primary triple, and
in the upper-layer fact if the overlap belongs to the auxiliary description.
For example, in Figure 2, the overlapping part of fact 1 and fact 2 “an NBA
team” belongs to the primary triple, so it is maintained in fact 2.
Conversely, “in the year” is the auxiliary description and is maintained in
fact 3.

##  Appendix C Example of NL Fact Tree Construction

Here we display a visual example of the NL fact tree construction with the
question Who joined an NBA team in Los Angeles in the year the Warriors won
the NBA championship.

Firstly, we use the Stanford Parser to generate the syntax tree (cf. Figure
9). Then we preprocess the syntax tree (cf. Figure 10) to reduce the
subsequent elimination operations according to the following rules:

  * $\bullet$

Pruning the punctuation node and its parent node, e.g., node “?” and “.”.

  * $\bullet$

If all the grandchildren of a NP node are leaf nodes (more than one), we prune
the parents, and combine the grandchildren to a unified leaf node, whose
parent is changed to the NP node. For example, the, NBA and championship in
Figure 9 are combined as the NBA championship, whose parent is “NP”.

  * $\bullet$

If a node has only one child and only one grandchild, which is a leaf node, we
remove the child node and let the leaf node be the only child of this node.
For example, who in Figure 9 will be connected directly to its grandfather
node WHNP.

Next we start eliminating nodes from the the bottom to the top as well as from
the right to the left. Note that we start the elimination operation from the
third-to-last layer of the tree. For each selected node, we extract a subtree
that contains this node (colored in red) and its neighbor nodes (colored in
blue). This subtree is fed into a classifier. The output of the classifier
determines whether to eliminate this node. Figure 12 shows the specific
elimination process. The previously selected node will no longer be selected,
e.g., the node “SBAR” in Figure 12 (f).

After the elimination process, we delete non-leaf nodes and retain the
hierarchical structure of leaf nodes. For the continuous nodes in the lower-
layer, set a common placeholder node in the upper-layer. For example, the
continuous nodes a team, in and Los Angeles in Figure 12 (j) will be connected
to a common placeholder node (i.e., the blue node in Figure 11). The
interrogative pronouns, e.g., who are also replaced directly with
placeholders. Now, the NL fact tree is constructed (see Figure 11). It
satisfies 1) the leaf nodes are words or phrases of the question; and 2) if
the leaf nodes share the same parent, they belong to the same fact.

Figure 9: Syntax tree. Figure 10: Syntax tree after preprocessing. Figure 11:
NL fact tree. The red, blue and purple blank nodes are placeholder nodes.

(a) VP is eliminated.

(b) SBAR is retained.

(c) NP is eliminated.

(d) PP is eliminated.

(e) PP is eliminated.

(f) NP is retained.

(g) VP is eliminated.

(h) SQ is eliminated.

(i) SBARQ is eliminated.

(j) Elimination ends.

Figure 12: Node elimination process.

ID | Template | Mode
---|---|---
1 | who win $\left\\{\right\\}$ award in the time $\left\\{\right\\}$ | 1
2 | who is sibling of $\left\\{\right\\}$ | 1
3 | what is the profession of $\left\\{\right\\}$ | 1
4 | what is the country of $\left\\{\right\\}$ | 1
5 | what political party did $\left\\{\right\\}$ join | 1
6 | who is the spouse of $\left\\{\right\\}$ | 1
7 | what is the gener of $\left\\{\right\\}$ | 1
8 | who was educated at $\left\\{\right\\}$ until $\left\\{\right\\}$ | 1
9 | when did $\left\\{\right\\}$ die | 1
10 | where was $\left\\{\right\\}$ born in | 1
11 | who work at the place $\left\\{\right\\}$ | 1
12 | who was nominated for the prize $\left\\{\right\\}$ in the time $\left\\{\right\\}$ | 1
13 | who is the mother of whose father is $\left\\{\right\\}$ | 2
14 | who is the father of whose mother is $\left\\{\right\\}$ | 2
15 | who win award $\left\\{\right\\}$ in the time when $\left\\{\right\\}$ win the $\left\\{\right\\}$ | 2
16 | who is the father of who has ever won $\left\\{\right\\}$ | 2
17 | who is the child of who has ever won $\left\\{\right\\}$ | 2
18 | who was nominated for $\left\\{\right\\}$ in the time when $\left\\{\right\\}$ win the $\left\\{\right\\}$ | 2
19 | what political party did the father of $\left\\{\right\\}$ join | 2
20 | what is the profession of the person who has ever won the $\left\\{\right\\}$ | 2
21 | who died in the place where $\left\\{\right\\}$ born in | 2
22 | who born in the place where $\left\\{\right\\}$ died in | 2
23 | which field did the person who has ever educated at $\left\\{\right\\}$ work for | 2
24 | who is the spouse of the person who born in $\left\\{\right\\}$ | 2
25 | who is the father of the person who born in $\left\\{\right\\}$ | 2
26 | what is the country of the person whose father is the one has ever won the prize $\left\\{\right\\}$ | 3
27 | who born in the place where the father of $\left\\{\right\\}$ died in | 3
28 | who died in the place where the mother of $\left\\{\right\\}$ born in | 3
29 | who was educated at the school where the person who won the prize $\left\\{\right\\}$ was also educated at | 3
30 | who is the child of the person whose father is the one who is the sibling of $\left\\{\right\\}$ | 3
31 | who work in the field that the person from the country $\left\\{\right\\}$ work for | 3
32 | who join the political party that the person from the country $\left\\{\right\\}$ has erver joined | 3
33 | when did the person from $\left\\{\right\\}$ won the prize that $\left\\{\right\\}$ has ever won | 4
34 | who joined a team in $\left\\{\right\\}$ in the year $\left\\{\right\\}$ won the NBA championship | 4

Table 5: List of question templates and their fact combination mode. The curly
braces $\left\\{\right\\}$ indicate the entities to be filled.