TTK-23-22, TTP23-038, P3H-23-063,

ZU-TH 57/23, ALBERTA-THY-6-23,

SI-HEP-2023-20, MPP-2023-190

The $Q_{1,2}$–$Q_{7}$ interference contributions to $b\to s\gamma$ at
${\mathcal{O}}(\alpha_{\mathrm{s}}^{2})$ for the physical value of $m_{c}$
M. Czaja1, M. Czakon2, T. Huber3, M. Misiak1, M. Niggetiedt4, A. Rehman5,6,
K. Schönwald7 and M. Steinhauser8
1 Institute of Theoretical Physics, Faculty of Physics, University of Warsaw,
02-093 Warsaw, Poland.
2 Institut für Theoretische Teilchenphysik und Kosmologie, RWTH Aachen
University,
52056 Aachen, Germany.
3 Theoretische Physik 1, Center for Particle Physics Siegen (CPPS),
Universität Siegen,
57068 Siegen, Germany.
4 Max Planck Institute for Physics, Föhringer Ring 6, 80805 München, Germany.
5 Department of Physics, University of Alberta, Edmonton, AB T6G 2E1, Canada.
6 National Centre for Physics, Quaid-i-Azam University Campus, Islamabad
45320, Pakistan.
7 Physik Institut, Universität Zürich, 8057 Zürich, Switzerland.
8 Institut für Theoretische Teilchenphysik, Karlsruhe Institute of Technology
(KIT),
76128 Karlsruhe, Germany.
Abstract

The $\bar{B}\to X_{s}\gamma$ branching ratio is currently measured with around
$5\%$ accuracy. Further improvement is expected from Belle II. To match such a
precision on the theoretical side, evaluation of
${\mathcal{O}}(\alpha_{\mathrm{s}}^{2})$ corrections to the partonic decay
$b\to X_{s}^{\rm part}\gamma$ are necessary, which includes the $b\to
s\gamma$, $b\to sg\gamma$, $b\to sgg\gamma$, $b\to sq\bar{q}\gamma$ decay
channels. Here, we evaluate the unrenormalized contribution to $b\to s\gamma$
that stems from the interference of the photonic dipole operator $Q_{7}$ and
the current-current operators $Q_{1}$ and $Q_{2}$. Our results, obtained in
the cut propagator approach at the 4-loop level, agree with those found in
parallel by Fael et al. who have applied the amplitude approach at the 3-loop
level. Partial results for the same quantities recently determined by Greub et
al. agree with our findings, too.

##  1 Introduction

Rare $B$-meson decays that receive the leading Standard Model (SM)
contributions from one-loop diagrams provide important constraints on popular
Beyond Standard Model (BSM) scenarios. Among them, the inclusive radiative
decay $\bar{B}\to X_{s}\gamma$ is of particular interest. Its isospin- and
${\mathrm{C}P}$-averaged branching ratio has been measured by CLEO [1], Belle
[3, 2], BABAR [4, 5, 6], and Belle II [7] for $E_{\gamma}>E_{0}$ in the
decaying meson rest frame, with various values of $E_{0}$, ranging from
$1.7\,{\rm GeV}$ to $2.0\,{\rm GeV}$. The current world average of these
measurements111 The most recent Belle II result [7] is not yet included in the
average (1.1). extrapolated to $E_{0}=1.6\,{\rm GeV}$ reads [8, 9]

${\mathcal{B}}(\bar{B}\to X_{s}\gamma)^{\rm exp}=(3.49\pm 0.19)\times
10^{-4}\,.$ (1.1)

An extrapolation in $E_{0}$ has been applied because measurements are less
precise for lower values of $E_{0}$ due to rapidly growing background — see,
e.g., Fig. 2 in Ref. [7]. On the other hand, theoretical estimates of non-
perturbative effects are less precise for higher values of $E_{0}$ — see Refs.
[10, 11] for the most recent analyses of this issue.

At $E_{0}=1.6\,{\rm GeV}$, the $\bar{B}\to X_{s}\gamma$ decay rate is well
approximated by the corresponding perturbative $b\to X_{s}^{p}\gamma$ decay
rate, where $X_{s}^{p}=s,sg,sgg,sq\bar{q},\ldots$ are the partonic final
states. Most relevant non-perturbative corrections to this approximation are
suppressed by powers of $(m_{B}-m_{b})/m_{b}$. The largest non-perturbative
contribution to the overall uncertainty arises from the so-called resolved
photon effects that have been extensively studied in Refs. [12, 13, 14, 15,
16].

As far as the dominant perturbative contributions are concerned, they need to
be evaluated including Next-to-Leading Order (NLO) electroweak and Next-to-
Next-to-Leading Order (NNLO) QCD corrections to match the experimental
accuracy. Some of the important NNLO QCD
(${\mathcal{O}}(\alpha_{\mathrm{s}}^{2})$) corrections that depend on the
charm quark mass $m_{c}$ have been calculated only in the limits $m_{c}=0$
[17] and $m_{c}\gg m_{b}$ [18]. Next, an interpolation between the two limits
was applied [17]. The resulting SM prediction obtained in 2015 [19] was
subsequently updated in 2020 [20] to yield

${\mathcal{B}}(\bar{B}\to X_{s}\gamma)^{\rm SM}=(3.40\pm 0.17)\times
10^{-4}\,,$ (1.2)

where the overall uncertainty contains $\pm 3\%$ from the
$m_{c}$-interpolation, $\pm 3\%$ from unknown higher-order effects, and $\pm
2.5\%$ from the input parameters (combined in quadrature). Non-perturbative
uncertainties are among the parametric ones, with the resolved photon
contributions treated along the lines of Ref. [13] — see Ref. [20] for
details.

While the results in Eqs. (1.1) and (1.2) are in perfect agreement, further
improvement on both the experimental and theoretical sides are expected. The
ultimate Belle II luminosity is going to allow for high-statistics
measurements using the hadronic tag method for the recoiling $B$ meson, which
efficiently suppresses the non-$B\bar{B}$ backgrounds [21] and makes the
determination of $E_{\gamma}$ in the decaying $B$-meson rest frame possible on
the event-by-event basis [4, 7]. As far as the perturbative calculations are
concerned, the main effort is being devoted to eliminating the
$m_{c}$-interpolation at ${\mathcal{O}}(\alpha_{\mathrm{s}}^{2})$ by
evaluation of the corresponding corrections at the physical value of $m_{c}$.

In the current paper, we present results of our calculation of the
unrenormalized $m_{c}$-dependent NNLO QCD corrections to the $b\to s\gamma$
decay rate at the physical value of $m_{c}$. They need to be supplemented in
the future with the corresponding bremsstrahlung contributions (with
$X_{s}^{p}=sg,sgg,sq\bar{q}$), for which our calculations are advanced but yet
unfinished. However, the observed agreement with the parallel calculation of
Ref. [22], as well as the published partial results of Ref. [23] makes us
confident that the two-body-final-state contributions in our calculation can
be treated as cross-checked, and are ready for publication.

The article is organized as follows. In the next section, we provide the
necessary definitions to specify the corrections we actually calculate. Next,
our method for evaluation of 4-loop propagator diagrams with unitarity cuts is
briefly described. In Section 3, our final results for the considered
corrections are presented for a sample physical value of
$z=m_{c}^{2}/m_{b}^{2}$, namely $z=0.04$. We conclude in Section 4.

##  2 Details of the calculation

We work in the framework of an effective theory that is obtained from the SM
via decoupling of the $W$ boson and all the heavier particles. The flavour-
changing weak interaction terms that affect the $b\to s\gamma$ transition take
then the form222 Terms that matter beyond the leading order in electroweak
interactions only and/or are suppressed by the small Cabibbo-Kobayashi-Maskawa
matrix element $V_{ub}$ are going to be ignored here, as we focus on
${\mathcal{O}}(\alpha_{\mathrm{s}}^{2})$ effects.

${\mathcal{L}}_{\rm
int}=\frac{4G_{F}}{\sqrt{2}}V_{ts}^{*}V_{tb}\sum_{i=1}^{8}C_{i}(\mu_{b})Q_{i}\,.$
(2.1)

The $\overline{\rm MS}$-renormalized Wilson coefficients $C_{i}(\mu_{b})$ are
already known up to NNLO in QCD at the renormalization scale $\mu_{b}\sim
m_{b}$. Explicit expressions for the operators $Q_{i}$ can be found, e.g., in
Eq. (1.6) of Ref. [17].333 We shall strictly follow the notation of Ref. [17]
throughout the current paper. For our present purpose, only three of them
matter, namely

$\displaystyle
Q_{1}=(\bar{s}_{L}\gamma_{\mu}T^{a}c_{L})(\bar{c}_{L}\gamma^{\mu}T^{a}b_{L}),\hskip
31.29802ptQ_{2}=(\bar{s}_{L}\gamma_{\mu}c_{L})(\bar{c}_{L}\gamma^{\mu}b_{L}),\hskip
31.29802ptQ_{7}=\frac{e}{16\pi^{2}}m_{b}(\bar{s}_{L}\sigma^{\mu\nu}b_{R})F_{\mu\nu}\,.$

The weak radiative $b$-quark decay rate can be written as

$\displaystyle\Gamma(b\to
X_{s}^{p}\gamma)=\frac{G_{F}^{2}\alpha_{\mathrm{e}m}m_{b,\rm
pole}^{5}}{32\pi^{4}}\left|V_{ts}^{*}V_{tb}\right|^{2}\sum_{i,j=1}^{8}C_{i}(\mu_{b})\,C_{j}(\mu_{b})\,\hat{G}_{ij}\,,$
(2.3)

where the quantities $\hat{G}_{ij}$ depend on the photon energy cut $E_{0}$,
the renormalization scale $\mu_{b}$, and the ratio $z=m_{c}^{2}/m_{b}^{2}$ of
the charm and bottom quark masses.444 The light $u$, $d$ and $s$ quark masses
are set to zero in ${\mathcal{O}}(\alpha_{\mathrm{s}}^{2})$ interference terms
involving the operator $Q_{7}$ that are of our interest here. However, they
need to be retained in numerically subleading terms to get rid of collinear
divergences — see, e.g., Refs. [24, 25]. Their perturbative expansion in
$\alpha_{\mathrm{s}}$ reads

$\hat{G}_{ij}=\hat{G}^{(0)}_{ij}+\frac{\alpha_{\mathrm{s}}}{4\pi}\,\hat{G}^{(1)}_{ij}+\left(\frac{\alpha_{\mathrm{s}}}{4\pi}\right)^{2}\hat{G}^{(2)}_{ij}+{\mathcal{O}}(\alpha_{\mathrm{s}}^{3})\,.$
(2.4)

Currently, the dominant uncertainty in Eq. (2.3) arises from the
$z$-dependence of $\hat{G}_{17}^{(2)}$ and $\hat{G}_{27}^{(2)}$. These are the
very quantities for which the interpolation mentioned in the Introduction has
been applied. Our discussion in the following is going to refer to
$\hat{G}_{27}^{(2)}$ for brevity. The calculation of $\hat{G}_{17}^{(2)}$ has
been done alongside – it differs by colour factors only. We shall present both
results in Section 3.

Let us split the unrenormalized (bare) interference term $\hat{G}_{27}^{(2)\rm
bare}$ into contributions from two-, three- and four-particle final states

$\hat{G}_{27}^{(2)\rm
bare}=\hat{G}_{27}^{(2)2P}+\hat{G}_{27}^{(2)3P}+\hat{G}_{27}^{(2)4P}\,.$ (2.5)

The two-particle contribution $\hat{G}_{27}^{(2)2P}$ can be further split into
a sum of two types of interferences

$\hat{G}_{27}^{(2)2P}=\Delta_{30}\hat{G}_{27}^{(2)2P}+\Delta_{21}\hat{G}_{27}^{(2)2P}\,,$
(2.6)

where each $\Delta_{kn}$ picks the interference of a $k$-loop amplitude with
the insertion of $Q_{2}$, and an $n$-loop amplitude with the insertion of
$Q_{7}$. There are only two terms in Eq. (2.6) because the one-loop $b\to
s\gamma$ matrix element of $Q_{2}$ turns out to vanish.

In the next section, we are going to present separate results for
$\Delta_{30}\hat{G}_{27}^{(2)2P}$ and $\Delta_{21}\hat{G}_{27}^{(2)2P}$. The
former can be calculated in two possible ways. One of them is to compute the
three-loop $b\to s\gamma$ matrix element of $Q_{2}$, and multiply its real
part555 The imaginary part would matter only for the ${\mathcal{O}}(V_{ub})$
correction that we neglect at the ${\mathcal{O}}(\alpha_{\mathrm{s}}^{2})$
level. Such an effect drops out after CP-averaging anyway. by the (real) tree-
level matrix element of $Q_{7}$. Such an “amplitude” approach was applied in
Ref. [22]. Partial results for $\Delta_{30}\hat{G}_{27}^{(2)2P}$ in Ref. [23]
were obtained using the same method, too.

Here, we apply the cut propagator approach, as it was done in Ref. [17] in the
$m_{c}=0$ case. It requires essentially the same effort as the amplitude
approach in the case of two-particle final states, but is likely more
convenient for higher-multiplicity final states. Following the well-known
procedure [26], we express the phase-space integrals in terms of regular loop
integrals but with cut propagators though, using the identity

$2\pi
i\delta(p^{2}-m^{2})=\frac{1}{p^{2}-m^{2}+i\varepsilon}-\frac{1}{p^{2}-m^{2}-i\varepsilon}\,.$
(2.7)

Once this is done, the usual Integration-By-Parts (IBP) algorithms can be used
to express the quantities in question in terms of Master Integrals (MIs). The
same algorithms are applied to derive Differential Equations (DEs) for the
MIs, which is essential for their efficient evaluation.

|  |
---|---|---
|  |
|  |
|  |
Figure 1:  Sample Feynman diagrams contributing to
$\Delta_{30}\hat{G}_{27}^{(2)2P}$ (upper row) and
$\Delta_{21}\hat{G}_{27}^{(2)2P}$ (lower row). Black squares denote insertions
of the $Q_{2}$ and $Q_{7}$ operators. The vertical dashed lines indicate which
propagators are cut.

Sample four-loop propagator diagrams that contribute to $\hat{G}_{27}^{(2)2P}$
in our approach are presented in Fig. 1. Let us note that there exist physical
cuts in some of these diagrams that do not go through the photon line, and
therefore should not be included. This means that we neither take the
imaginary part of the whole four-loop propagator, nor take advantage of the
optical theorem.

We generate the necessary diagrams with the help of QGRAF [27] and/or FeynArts
[28, 29] supplemented with self-written codes. The Feynman-’t Hooft gauge
fixing ($\xi=1$) is used. No diagrams with loop corrections on external (or
cut) lines are included, which matches the conventions of the corresponding
counterterm contributions in Eq. (2.1) of Ref. [30]. We skip the diagrams
where no gluon connects the charm loop (with the $Q_{2}$ vertex) to the
diagram remainder. Such diagrams contain subdiagrams that either vanish or sum
up to zero. We also skip the diagrams with ghost or gluon one-loop corrections
on the gluon lines. Their effects are read out from the corresponding massless
quark loops, and included in our results in the next section. Eventually, we
are left with 198 four-loop propagator diagrams that need to be calculated.

In each of the Feynman integrands, we sum over the external $b$-quark
polarizations, and evaluate the necessary Dirac traces with the help of FORM
[31]. Next, once all the Lorentz indices get contracted, the full
$\hat{G}_{27}^{(2)2P}$ becomes a linear combination of scalar integrals. Their
reduction to MIs is performed with the help of Kira [32, 33] that generates
and applies the IBP identities. Altogether, 447 MIs are found to be
independent.

The calculation of MIs is performed with the help of AMFlow [34]. An
artificial imaginary mass-squared parameter $\eta$ is introduced in each
denominator, and the IBP method is used to derive DEs in $\eta$ for the MIs.
Next, the DEs are numerically solved with initial conditions at very large
$|\eta|$. All the physical mass ratios and dimensionless kinematical
invariants are assigned fixed numerical values to facilitate the IBP
reduction.

##  3 Results

In our case, the only physical mass ratio involved is $z=m_{c}^{2}/m_{b}^{2}$.
No kinematical invariants are present, as we deal with a massive particle
decay to two massless ones. To fix the numerical value of $z$, we follow the
convention of Ref. [17] where $z=m_{c}^{\overline{\rm MS}}(\mu_{c})/m_{b,{\rm
kin}}$ was used in lower-order contributions, where $m_{b,{\rm kin}}\simeq
4.564\,{\rm GeV}$ denotes the $b$-quark mass in the kinetic scheme at
$\mu_{\rm kin}=1\,{\rm GeV}$. Below, we present our final results for $z=0.04$
that corresponds to $\mu_{c}\simeq m_{b}(m_{b})\simeq 4.2\,{\rm GeV}$.

Our expressions for $\Delta_{30}\hat{G}^{(2)2P}_{27}$ and
$\Delta_{30}\hat{G}^{(2)2P}_{17}$ at $z=0.04$ read

$\displaystyle\Delta_{30}\hat{G}^{(2)2P}_{27}(z=0.04)$ $\displaystyle\simeq$
$\displaystyle\frac{0.181070}{\epsilon^{3}}-\frac{6.063805}{\epsilon^{2}}-\frac{34.087329}{\epsilon}-127.624515$
$\displaystyle+$
$\displaystyle\left(\frac{0.482853}{\epsilon^{2}}+\frac{4.093615}{\epsilon}+10.984004\right)n_{b}$
$\displaystyle+$
$\displaystyle\left(\frac{0.482853}{\epsilon^{2}}+\frac{4.185427}{\epsilon}+19.194053\right)n_{c}$
$\displaystyle+$
$\displaystyle\left(\frac{0.482853}{\epsilon^{2}}+\frac{4.135795}{\epsilon}+19.647238\right)n_{l}\;,$
$\displaystyle\Delta_{30}\hat{G}^{(2)2P}_{17}(z=0.04)$ $\displaystyle\simeq$
$\displaystyle-\frac{1}{6}\Delta_{30}\hat{G}^{(2)2P}_{27}(z=0.04)+\frac{0.987654}{\epsilon^{2}}+\frac{6.383643}{\epsilon}+34.077780\,,$
(3.1)

where all the numerical coefficients have been truncated at the sixth decimal
place.

As far as $\Delta_{21}\hat{G}^{(2)2P}_{27}$ and
$\Delta_{21}\hat{G}^{(2)2P}_{17}$ are concerned, we find

$\displaystyle\Delta_{21}\hat{G}^{(2)2P}_{27}(z)$ $\displaystyle=$
$\displaystyle\frac{368}{243\epsilon^{3}}+\frac{736-324f_{0}(z)}{243\epsilon^{2}}+\frac{1}{\epsilon}\left(\frac{1472}{243}+\frac{92}{729}\pi^{2}-\frac{8f_{0}(z)+4f_{1}(z)}{3}\right)+p(z)\;,$
$\displaystyle\Delta_{21}\hat{G}^{(2)2P}_{17}(z)$ $\displaystyle=$
$\displaystyle-\frac{1}{6}\Delta_{21}\hat{G}^{(2)2P}_{27}(z)\,,$ (3.2)

where $p(z=0.04)\simeq 144.959811$. The large-$z$ expansion of $p(z)$ reads

$\displaystyle p(z)$ $\displaystyle=$
$\displaystyle\frac{138530}{6561}-\frac{3680}{729}\zeta(3)-\frac{6136}{243}L+\frac{5744}{729}L^{2}-\frac{1808}{729}L^{3}$
(3.3) $\displaystyle+$
$\displaystyle\frac{1}{z}\left(-\frac{4222952}{1366875}-\frac{602852}{273375}L+\frac{34568}{18225}L^{2}-\frac{532}{1215}L^{3}\right)$
$\displaystyle+$
$\displaystyle\frac{1}{z^{2}}\left(-\frac{33395725469}{26254935000}-\frac{111861263}{93767625}L+\frac{156358}{178605}L^{2}-\frac{172}{1215}L^{3}\right)+{\mathcal{O}}\left(\frac{1}{z^{3}}\right)\,,$

with $L=\log z$. The NLO functions $f_{0}(z)$ and $f_{1}(z)$ are defined
through

$\hat{G}_{27}^{(1)2P}=-\frac{92}{81\epsilon}+f_{0}(z)+\epsilon
f_{1}(z)+{\mathcal{O}}(\epsilon^{2})\,.$ (3.4)

Their expansions around $z=0$ were originally found in Refs. [35] and [30],
respectively. Fully analytical expressions for them in terms of harmonic
polylogarithms have been recently determined in Ref. [22]. Their numerical
values at $z=0.04$ are $f_{0}(z=0.04)\simeq-6.371045$ and
$f_{1}(z=0.04)\simeq-18.545805$.

Contributions from diagrams with quark loops on the gluon lines are present in
Eq. (3.1) only. They are marked with $n_{b}=1$ (bottom loops), $n_{c}=1$
(charm loops), and $n_{l}=3$ (light quark loops). The main new results of the
current paper are the remaining contributions that stem from diagrams with no
quark loops on the gluon lines.

In the case of Eq. (3.1), we find perfect agreement with the results of Ref.
[22], after taking into account their global normalization convention (see Eq.
(10) there). To perform the comparison, we have relied on the supplementary
material to that paper where deep expansions around $z=0$ of their quantities
$t_{2}$ and $t_{3}$ are given. We can also confirm the partial results of Ref.
[23], once we restrict to their subset of diagrams.

In the case of our Eq. (3.2), analytical expressions for all the
$\frac{1}{\epsilon^{n}}$ poles have been extracted from the former NLO QCD
calculations of the $\langle s\gamma|Q_{2}|b\rangle_{\rm 2\;loop}$ and
$\langle s\gamma|Q_{7}|b\rangle_{\rm 1\;loop}$ [36] matrix elements. They are
in full agreement with our current numerical results. As far as the finite
contribution $p(z)$ is concerned, it is determined for the first time here. It
could not have been extracted from the NLO results because dimensionally
regulated infrared (IR) divergences in $\langle s\gamma|Q_{7}|b\rangle_{\rm
1\;loop}$ make the so-far-unknown higher-order terms in the
$\epsilon$-expansion of $\langle s\gamma|Q_{2}|b\rangle_{\rm 2\;loop}$
relevant. The IR divergences are going to cancel out only after taking into
account the yet uncalculated NNLO contributions from diagrams with 3- and
4-body cuts.

##  4 Summary and outlook

We evaluated the unrenormalized corrections $\hat{G}^{(2)2P}_{17}$ and
$\hat{G}^{(2)2P}_{27}$ to the perturbative $b\to s\gamma$ decay rate. In the
future, they need to be supplemented with contributions from three- and four-
body final states to get rid of IR divergences. Next, they should be
renormalized using counterterm contributions in Eq. (2.1) of Ref. [30] where
all the necessary counterterm ingredients were calculated. We have already
tested such a renormalization in our expansions around the large-$m_{c}$ limit
that are going to provide initial conditions for the DEs in $z$. The highest
poles ($\frac{1}{\epsilon^{3}}$ and $\frac{1}{\epsilon^{2}}$) got properly
renormalized out. However, a missing piece with $\frac{1}{\epsilon}$
divergence in the three- and four-body bare contributions was identified, and
it is currently being evaluated.

Given that the complete (partial) results for
$\Delta_{30}\hat{G}^{(2)2P}_{17}$ and $\Delta_{30}\hat{G}^{(2)2P}_{27}$ in
Ref. [22] ([23]) agree with our findings, we have decided to present them now,
and supplement with $\Delta_{21}\hat{G}^{(2)2P}_{17}$ and
$\Delta_{21}\hat{G}^{(2)2P}_{27}$, even though no physical conclusion can be
drawn from unrenormalized results alone. Given the complexity of the necessary
calculations and the phenomenological relevance of the expected ultimate
result, presenting intermediate results allows for valuable cross-checks and
provides a boost for reaching the final goal.

Our results in the previous section have been presented only for a single
value of $z$. In the case of $\Delta_{30}\hat{G}^{(2)2P}_{17}$ and
$\Delta_{30}\hat{G}^{(2)2P}_{27}$, an exhaustive analysis of $z$-dependence
can be found in Ref. [22]. As far as the remaining contributions are
concerned, we are going to study their dependence on $z$ only at the level of
the fully inclusive and renormalized results for $\hat{G}^{(2)}_{17}$ and
$\hat{G}^{(2)}_{27}$.

## Acknowledgements

The research of M. Czakon, T. Huber, M. Niggetiedt (partially) and M.
Steinhauser was supported by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) under grant 396021762 — TRR 257 “Particle Physics
Phenomenology after the Higgs Discovery”. M. Czaja and M. Misiak acknowledge
partial support by the National Science Center, Poland, under the research
project 2020/37/B/ST2/02746. K. Schönwald was supported by the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme grant agreement 101019620 (ERC Advanced Grant TOPUP). M.
Niggetiedt was partially supported by the Deutsche Forschungsgemeinschaft
(DFG) under grant 400140256 - GRK 2497: “The physics of the heaviest particles
at the Large Hardon Collider.” The work of A. Rehman was supported by NSERC
grant SAPIN-2022-00020.

## References

  * [1] S. Chen et al. (CLEO Collaboration), Phys. Rev. Lett. 87 (2001) 251807 [hep-ex/0108032].
  * [2] T. Saito et al. (Belle Collaboration), Phys. Rev. D 91 (2015) 052004 [arXiv:1411.7198].
  * [3] A. Limosani et al. (Belle Collaboration), Phys. Rev. Lett. 103 (2009) 241801 [arXiv:0907.1384].
  * [4] B. Aubert et al. (BaBar Collaboration), Phys. Rev. D 77 (2008) 051103 [arXiv:0711.4889].
  * [5] J. P. Lees et al. (BaBar Collaboration), Phys. Rev. D 86 (2012) 052012 [arXiv:1207.2520].
  * [6] J. P. Lees et al. (BaBar Collaboration), Phys. Rev. Lett. 109 (2012) 191801 [arXiv:1207.2690].
  * [7] F. Abudinén et al. (Belle-II Collaboration), [arXiv:2210.10220].
  * [8] Y. S. Amhis et al. (Heavy Flavor Averaging Group (HFLAV)), Phys. Rev. D 107 (2023) 052008 [arXiv:2206.07501].
  * [9] R. L. Workman et al. (Particle Data Group), PTEP 2022 (2022) 083C01.
  * [10] F. U. Bernlochner et al. (SIMBA Collaboration), Phys. Rev. Lett. 127 (2021) 102001 [arXiv:2007.04320].
  * [11] B. Dehnadi, I. Novikov and F. J. Tackmann, JHEP 2307 (2023) 214 [arXiv:2211.07663].
  * [12] M. Benzke, S. J. Lee, M. Neubert and G. Paz, JHEP 1008 (2010) 099 [arXiv:1003.5012].
  * [13] A. Gunawardana and G. Paz, JHEP 1911 (2019) 141 [arXiv:1908.02812].
  * [14] M. Benzke and T. Hurth, Phys. Rev. D 102 (2020) 114024 [arXiv:2006.00624].
  * [15] M. Benzke and T. Hurth, [arXiv:2303.06447].
  * [16] T. Hurth and R. Szafron, Nucl. Phys. B 991 (2023) 116200 [arXiv:2301.01739].
  * [17] M. Czakon, P. Fiedler, T. Huber, M. Misiak, T. Schutzmeier and M. Steinhauser, JHEP 1504 (2015) 168 [arXiv:1503.01791].
  * [18] M. Misiak and M. Steinhauser, Nucl. Phys. B 840 (2010) 271 [arXiv:1005.1173].
  * [19] M. Misiak, H. Asatrian, R. Boughezal, M. Czakon, T. Ewerth, A. Ferroglia, P. Fiedler, P. Gambino, C. Greub, U. Haisch, T. Huber, M. Kamiński, G. Ossola, M. Poradziński, A. Rehman, T. Schutzmeier, M. Steinhauser and J. Virto, Phys. Rev. Lett. 114 (2015) 221801 [arXiv:1503.01789].
  * [20] M. Misiak, A. Rehman and M. Steinhauser, JHEP 2006 (2020) 175 [arXiv:2002.01548].
  * [21] E. Kou et al. (Belle-II Collaboration), PTEP 2019 (2019) 123C01 [arXiv:1808.10567].
  * [22] M. Fael, F. Lange, K. Schönwald and M. Steinhauser, “Three-loop $b\to s\gamma$ vertex with current-current operators,” CERN-TH-2023-148, P3H-23-059, TTP23-035, ZU-TH 56/23.
  * [23] C. Greub, H. M. Asatrian, F. Saturnino and C. Wiegand, JHEP 2305 (2023) 201 [arXiv:2303.01714].
  * [24] M. Kamiński, M. Misiak and M. Poradziński, Phys. Rev. D 86 (2012) 094004 [arXiv:1209.0965].
  * [25] H. M. Asatrian and C. Greub, Phys. Rev. D 88 (2013) 074014 [arXiv:1305.6464].
  * [26] C. Anastasiou and K. Melnikov, Nucl. Phys. B 646 (2002) 220 [hep-ph/0207004].
  * [27] P. Nogueira, J. Comput. Phys. 105 (1993) 279.
  * [28] J. Kublbeck, M. Bohm and A. Denner, Comput. Phys. Commun. 60 (1990) 165.
  * [29] T. Hahn, Comput. Phys. Commun. 140 (2001) 418 [hep-ph/0012260].
  * [30] M. Misiak, A. Rehman and M. Steinhauser, Phys. Lett. B 770 (2017) 431 [arXiv:1702.07674].
  * [31] B. Ruijl, T. Ueda and J. Vermaseren, arXiv:1707.06453.
  * [32] P. Maierhöfer, J. Usovitsch and P. Uwer, Comput. Phys. Commun. 230 (2018) 99, [arXiv:1705.05610].
  * [33] J. Klappert, F. Lange, P. Maierhöfer and J. Usovitsch, Comput. Phys. Commun. 266 (2021) 108024 [arXiv:2008.06494].
  * [34] X. Liu and Y. Q. Ma, Comput. Phys. Commun. 283 (2023) 108565 [arXiv:2201.11669].
  * [35] C. Greub, T. Hurth and D. Wyler, Phys. Lett. B 380 (1996) 385 [hep-ph/9602281].
  * [36] H. M. Asatrian, A. Hovhannisyan, V. Poghosyan, T. Ewerth, C. Greub and T. Hurth, Nucl. Phys. B 749 (2006) 325 [hep-ph/0605009].


# GMH: A General Multi-hop Reasoning Model for KG Completion

Yao Zhang1 Hongru Liang2 Adam Jatowt3 Wenqiang Lei4
Xin Wei5 Ning Jiang5 Zhenglu Yang1
1TKLNDST, CS, Nankai University, China, 2Sichuan University, China,
3University of Innsbruck, Austria, 4National University of Singapore,
Singapore,
5Mashang Consumer Finance Co., Ltd., China
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
$\left\\{\right.$xin.wei02<EMAIL_ADDRESS><EMAIL_ADDRESS>
Corresponding author.

###### Abstract

Knowledge graphs are essential for numerous downstream natural language
processing applications, but are typically incomplete with many facts missing.
This results in research efforts on multi-hop reasoning task, which can be
formulated as a search process and current models typically perform short
distance reasoning. However, the long-distance reasoning is also vital with
the ability to connect the superficially unrelated entities. To the best of
our knowledge, there lacks a general framework that approaches multi-hop
reasoning in mixed long-short distance reasoning scenarios. We argue that
there are two key issues for a general multi-hop reasoning model: i) where to
go, and ii) when to stop. Therefore, we propose a general model which resolves
the issues with three modules: 1) the local-global knowledge module to
estimate the possible paths, 2) the differentiated action dropout module to
explore a diverse set of paths, and 3) the adaptive stopping search module to
avoid over searching. The comprehensive results on three datasets demonstrate
the superiority of our model with significant improvements against baselines
in both short and long distance reasoning scenarios.

##  1 Introduction

Knowledge graphs (KGs) have become the preferred technology for representing,
sharing and adding factual knowledge to many natural language processing
applications like recommendation Wang et al. (2019); Lei et al. (2020) and
question answering Huang et al. (2019); Zhang et al. (2018). KGs store triple
facts (head entity, relation, tail entity) in the form of graphs, where
entities are represented as nodes and relations are represented as labeled
edges between entities (e.g., Figure 1 (a)). Although popular KGs already
contain millions of facts, e.g., YAGO Suchanek et al. (2007) and Freebase
Bollacker et al. (2008), they are far from being complete considering the
amount of existing facts and the scope of continuously appearing new
knowledge. This has become the performance bottleneck of many KG-related
applications, triggering research efforts on the multi-hop reasoning task.

Figure 1: Examples of (a) an incomplete knowledge graph, (b) a short distance
scenario (two-hop) about the reasoning of (Stephen Curry, teammate, $\star$),
and (c) a long distance scenario (four-hop) about the reasoning of (Stephen
Curry, opponent, $\star$). The dotted lines refer to the relations of
incomplete triples and solid lines refer to existing relations. The green,
blue and black boxes represent the entities of the incomplete triples, the
entities in the reasoning paths and the unrelated entities, respectively. As
it can be seen, the long distance reasoning is needed and more complex than
the short distance reasoning. Best viewed in color.

The multi-hop reasoning task can be formulated as a search process, in which
the search agent traverses a logical multi-hop path to find the missing tail
entity of an incomplete triple in KG. As shown in Figure 1 (b), the two-hop
path Stephen Curry $\xrightarrow[]{plays~{}for}$ Golden State Warriors
$\xleftarrow[]{plays~{}for}$ Klay Thompson is searched to reason Klay Thompson
as the missing entity of (Stephen Curry, teammate, $\star$), where $\star$
denotes the missing tail entity. Multi-hop reasoning methods Xiong et al.
(2017); Das et al. (2018) have been proposed to model the search process as a
sequential decision problem in reinforcement learning (RL) framework. Lin et
al. (2018) further optimized the reward function of RL framework based on Das
et al. (2018). However, these works have only scratched the surface of multi-
hop reasoning as they focus only on short distance reasoning scenarios (e.g.,
the two-hop case in Figure 1 (b)).

We observe that the long distance reasoning scenarios are vital in the
development of multi-hop reasoning and KG-related applications, because two
superficially unrelated entities may be actually deeply connected over a long
distance. With the significant expansion of KGs, the incompleteness of KG
becomes more prominent, and long distance scenarios are rapidly increasing. As
shown in Figure 1 (c), the missing entity James Harden in the incomplete
triple (Stephen Curry, opponent, $\star$) is inferred by a long reasoning
process, i.e., a four-hop path. Moreover, in practice, the long and short
distance reasoning scenarios are mixed. The ideal multi-hop reasoning model
should be competent on mixed short and long distances. Specifically, we argue
that there are two key issues in the traverse of KG that need to be resolved:

  * i)

Where to go? The search agent needs to decide where to go at next search step,
i.e., selecting an edge connected with the current node. Selecting the
positive edge means that the agent will move towards the target node,
otherwise, it will move away from the target. When the search distance
increases, the issue becomes more challenging because the agent needs to make
more decisions.

  * ii)

When to stop? The search agent needs to decide when to stop the search because
the exact search steps cannot be known in advance. An ideal search agent needs
to stop at a suitable time to avoid over searching and adapt to realistic
reasoning scenarios with mixed short and long distances.

Figure 2: An illustration of the GMH Model. We reuse the example in Figure1
(c) for explanation. The input includes the head entity and the relation of
the incomplete triple (Stephen Curry, opponent, $\star$) with the background
KG, and the output is the tail entity James Harden. The subgraph (a) is the
initial state of the search process. The subgraphs (b-d) show the search
process at step 4. Specifically, 1) we develop the local-global knowledge
fusion module to estimate the possible paths, 2) the differentiated action
dropout module to dilute the negative paths, and 3) the adaptive stopping
search module to avoid over searching. Best viewed in color.

To this end, we propose a General Multi-Hop reasoning model, termed GMH, which
solves the two above-listed issues in three steps: 1) the local-global
knowledge fusion module fuses the local knowledge learnt from history path and
the global knowledge learnt from graph structure; 2) the differentiated action
dropout module forces the search agent to explore a diverse set of paths from
a global perspective; and 3) the adaptive stopping search module uses a self-
loop controller to avoid over searching and resource wasting. We train the
policy network with RL and optimize the reward to find the target entity
effectively. In summary, the main contributions of this work are as follows:

  * •

We observe that the long distance reasoning scenarios are vital in the
development of multi-hop reasoning, and argue that an ideal multi-hop
reasoning model should be competent on mixed long-short distance reasoning
scenarios.

  * •

We propose a general multi-hop reasoning model, GMH, which can solve two key
issues in mixed long-short distance reasoning scenarios: i) where to go and
ii) when to stop.

  * •

We evaluate GMH on three benchmarks, FC17, UMLS and WN18RR. The results
demonstrate the superiority of GMH with significant improvements over
baselines in mixed long-short distance reasoning scenarios and with
competitive performances in short distance reasoning scenarios.

##  2 Related Work

In this section, we summarize the related work and discuss their connections
to our model. Firstly, we introduce the two lines of work on the KG completion
task: multi-hop reasoning and KG embedding.

The multi-hop reasoning task focuses on learning logical multi-hop paths
reasoned from KG. The multi-hop reasoning models distill deep information from
paths thereby generating further directly interpretable results. Lao et al.
(2011); Das et al. (2017); Jiang et al. (2017); Yin et al. (2018) predicted
the missing relations of incomplete triples based on pre-computed paths. Xiong
et al. (2017) firstly adopted the RL framework to improve the reasoning
performance. The task of finding a missing entity is orthogonal to the
prediction of the missing relation in a complementary manner. Das et al.
(2018) used the history path to facilitate the search agent finding the
missing entity and Lin et al. (2018) optimized the reward function of RL
framework based on Das et al. (2018). Lv et al. (2019) adopted the meta
learning framework for multi-hop reasoning over few-shot relations. These
works are conditioned in short distance scenarios, and tend to rapidly lose
effectiveness as the distance increases. In contrast, we propose a general
model which can be sufficiently utilized in both the short and long distance
reasoning scenarios.

The KG embedding task is another line of work carried to alleviate the
incompleteness of KG. Embedding-based models project KGs in the embedding
space and estimate the likelihood of each triple using scoring functions.
Bordes et al. (2013); Wang et al. (2014); Lin et al. (2015); Ji et al. (2016)
defined additive scoring functions based on the translation assumption. Yang
et al. (2015); Trouillon et al. (2016) defined multiplicative scoring
functions based on linear map assumption. Moreover, recent models introduce
special neural networks like neural tensor network Socher et al. (2013),
convolution neural network Dettmers et al. (2018) and graph convolutional
network Nathani et al. (2019). Due to the neglection of deep information
within multi-hop paths, the results of the embedding-based models lack
interpretability, which is critical for KG-related applications. However,
embedding-based models are less sensitive to the reasoning distance because
they learn KG structure from the global perspective. Thus, we take advantage
of this strength to learn the global knowledge from graph structure and retain
the interpretability by reasoning from the history paths.

Secondly, we discuss the community research on long distance reasoning
scenarios. Tuan et al. (2019) formed a transition matrix for reasoning over
six-hop path in KG for the conversational reasoning task. It is however not
suitable for large-scale KGs, because the matrix multiplication requires large
calculation space. Wang et al. (2019) proposed a long-term sequential pattern
to encode long distance paths for the recommendation task. Because there is no
real reasoning process for the long distance paths, it is not suitable for the
KG completion. To summary, we are the first to study long distance reasoning
scenarios in the KG completion. We propose a general model that tackles both
short and long distance reasoning scenarios and works effectively on large-
scale KGs.

##  3 Methodology

Figure 2 illustrates the entire process of the GMH model. The input involves
the head entity and relation of the incomplete triple with the background KG.
The output is the missing tail entity. We systematize the model in three
steps: 1) the local-global knowledge fusion module to integrate knowledge of
history paths and graph structure; 2) the differentiated action dropout module
to diversify the reasoning paths; and 3) the adaptive stopping search module
to formulate the optimal steps of searching. The local-global knowledge fusion
and differentiated action dropout modules facilitate the agent to address the
issue of where to go. The adaptive stopping search module controls the search
steps to resolve the issue of when to stop.

###  3.1 Preliminary

We formally represent a KG as a collection of triples
$\mathcal{T}=\left\\{(e_{h},r,e_{t})|e_{h}\in\mathcal{E},e_{t}\in\mathcal{E},r\in\mathcal{R}\right\\}$,
where $e_{h}$, $r$ and $e_{t}$ denote the head entity, relation and tail
entity in one triple, $\mathcal{E}$ and $\mathcal{R}$ are the entity and
relation sets, respectively. Each directed link in KG represents a valid
triple (i.e., $e_{h}$ and $e_{t}$ are represented as the nodes and $r$ as the
labeled edge between them). For an incomplete triple, multi-hop reasoning can
be perceived as searching a target tail entity $e_{t}$ through limited steps
in KG, starting from head entity $e_{h}$ and based on the relation
$r\in\mathcal{R}$. We use query $q$ to represent $(e_{h},r)$ in the following
sections. At step $s$, the search agent will transfer to the entity $e_{s}$
updating the history path trajectory
$\mathcal{H}_{s}=\left\\{e_{h},r_{1},e_{1},...,r_{s},e_{s}\right\\}$, and the
available action set
$\mathcal{A}_{s}=\left\\{({{r_{s}^{i}}},{{e_{s}^{i}}})|({e}_{s},{{r_{s}^{i}}},{{e_{s}^{i}}})\in\mathcal{T}\right\\}$.
$\mathcal{A}_{s}$ consists of all outgoing relations and the associated
entities of ${e}_{s}$. The agent will select one action from $\mathcal{A}_{s}$
to transfer to the next entity ${e}_{s+1}$ through the correlated relation
${r}_{s+1}$ at next step.

###  3.2 Local-Global Knowledge Fusion

In this module, we learn local knowledge $lk_{s}$ and global knowledge
$gk_{s}$ to resolve the “where to go" issue, as shown in Figure 3. The local
knowledge indicates that the agent makes decisions on the basis of the history
path trajectory $\mathcal{H}_{s}$ at step $s$ from a local perspective. The
global knowledge is calculated through a pre-trained embedding-based models
from a global perspective. We use an aggregate (abbr. AGG) block to aggregate
$lk_{s}$ and $gk_{s}$, which has two types: summation ($lk_{s}+gk_{s}$) and
scalar product ($lk_{s}*gk_{s}$). The distribution
$p(\mathcal{A}_{s})\in\mathbb{R}^{\left|\mathcal{A}_{s}\right|}$ is calculated
through the AGG block and represents the confidence score for each available
entity in $\mathcal{A}_{s}$. The agent will select one action from
$\mathcal{A}_{s}$ according to the distribution $p(\mathcal{A}_{s})$ to
transfer to the next entity.

Local Knowledge Learning

The local knowledge $lk_{s}$ indicates from a local perspective that the agent
makes decisions based on the history path trajectory $\mathcal{H}_{s}$ at step
$s$. We adopt long short-term memory (LSTM) neural network and attention
mechanism to encode the history path trajectory and yield the local knowledge.

The history path trajectory
$\mathcal{H}_{s}=(e_{h},r_{1},e_{1},...,r_{s},e_{s})$ consists of the sequence
of entities and relations which the agent has selected over the last $s$
steps. We adopt an embedding layer to generate the embedding of entities and
relations. The embedding of query is
$\vec{q}=[\vec{e_{h}};\vec{r}]\in\mathbb{R}^{2dim}$, i.e., the concatenation
of the embeddings of the head entity $\vec{e_{h}}\in\mathbb{R}^{dim}$ and
relation $\vec{r}\in\mathbb{R}^{dim}$, where $dim$ is the dimension. We use an
LSTM to encode the embedding of $\mathcal{H}_{s}$ to yield the hidden state
embedding sequence $(\vec{h}_{0},...,\vec{h}_{s})$, where
$\vec{h}_{s}=LSTM(\vec{h}_{s-1},[{\vec{r_{s}}},{\vec{e_{s}}}])\in\mathbb{R}^{2dim}$
is the hidden state at step $s$, ${e_{s}}$ is the current entity and ${r_{s}}$
is the relation that connects ${e_{s-1}}$ and ${e_{s}}$.

Figure 3: An illustration of the local-global knowledge fusion module. We
reuse the search process in Figure 2 for detailed explanation. Best viewed in
color.

Prior works Das et al. (2018); Lin et al. (2018) use only the current hidden
state embedding (i.e., $\vec{h}_{s}$) to yield the next action and they
neglect the differentiated importance between the hidden states over the last
$s$ steps. Therefore, the attention weight value calculated between the hidden
state embedding sequence and the query embedding is introduced to optimize the
local knowledge $lk_{s}$. Each weight value is derived by comparing the query
${\vec{q}}$ with each hidden state $\vec{h}_{i}$:

$\alpha({\vec{q}},\vec{h}_{i})=\frac{\exp(f({\vec{q}},{\vec{h}_{i}}))}{\sum_{j=0}^{s}\exp(f({\vec{q}},{\vec{h}_{j}}))},$
(1)

where $i$ and $j$ stand for the $i$-th and $j$-th hidden state candidate,
respectively. Here, $f(\cdot)$ is represented as a query-based function:
$f({v_{q}},{h_{m}})={v_{q}}^{\top}{h_{m}}$. Ultimately, local knowledge
$lk_{s}\in\mathbb{R}^{\left|\mathcal{A}_{s}\right|}$, which reflects the
influence of the history path trajectory on each element in $\mathcal{A}_{s}$,
can be obtained:

$\vec{lk}_{s}={\mathcal{A}}_{s}\times{\bm{W}}_{1}\delta_{1}({\bm{W}}_{2}\sum_{m=1}^{s}\alpha({\vec{q}},\vec{h}_{m})\vec{h}_{m}),$
(2)

where ${\bm{W}}_{1}$ and ${\bm{W}}_{2}$ are the weights, and $\delta_{1}$ is
the activation function.

Global Knowledge Learning

Prior works Das et al. (2018); Lin et al. (2018) use the local knowledge and
neglect the long distance cases which requires higher decision accuracy of the
agent. We introduce the global knowledge $gk_{s}$ learnt from graph structure
by a pre-trained embedding-based model.

Embedding-based models map the graph structure in continuous vector space by
using a scoring function $\psi(e_{h},r,e_{t})$. We generate the new triple
$(e_{h},r,e_{s}^{i})$ by concatenating the head entity and relation with
available entity $e_{s}^{i}\in{\mathcal{E}}_{t}^{\mathcal{A}}$, where
${\mathcal{E}}_{t}^{\mathcal{A}}\in\mathbb{R}^{\left|\mathcal{A}_{s}\right|\times
dim}$ contains all available entities in $\mathcal{A}_{s}$. As we consider
that the positive available entity is closer to the target tail entity in
vector space, combining the positive available entity in $\mathcal{A}_{s}$
with the query will get a higher score than that using negative available
entities. Formally, we adopt a pre-trained embedding-based model to calculate
these new triples to obtain the global knowledge $gk_{s}$:

$\vec{gk}_{s}=[\psi({\vec{e}_{h}},\vec{r},{\vec{e}_{s}}^{~{}1});...;\psi({\vec{e}_{h}},\vec{r},\vec{e}_{s}^{~{}\left|\mathcal{A}_{s}\right|})].$
(3)

Concatenating each of new triples’ scores gives the global knowledge
$gk_{s}\in\mathbb{R}^{\left|\mathcal{A}_{s}\right|}$. The selection of scoring
function $\psi(\cdot)$ is discussed in Section 4.3.

###  3.3 Differentiated Action Dropout

In the multi-hop reasoning task, it is important to enforce effective
exploration of a diverse set of paths and dilute the impact of negative paths.
Lin et al. (2018) forced the agent to explore a diverse set of paths using
action dropout technique which randomly masks some available actions in
$\mathcal{A}_{s}$, i.e., blocking some outgoing edges of the agent. However,
in the case of reasoning over long distances, the number of paths is much
greater than that in the short distance scenarios because the search space
grows exponentially. The random action dropout technique is inefficient
because it cannot discriminate paths of different qualities. We then propose
the differentiated action dropout (DAD) technique based on the global
knowledge $gk_{s}$ to mask available actions, since we believe that higher-
scoring actions are more likely to exist in a high-quality path. In
particular, the mask matrix
$M_{t}\in\mathbb{R}^{\left|\mathcal{A}_{s}\right|}$ is sampled from the
Bernoulli distribution:

$\vec{M}_{t}\sim Bernoulli(sigmoid(\vec{gk}_{s})).$ (4)

The element in $M_{t}$ is binary, where 1 indicates the action is reserved and
0 indicates abandonment. The fusion of local-global knowledge and
differentiated action dropout modules helps the agent to tackle the key
problem where to go jointly.

###  3.4 Adaptive Stopping Search

For the second key issue of when to stop, we devise the adaptive stopping
search (ASS) module inspired by the early stopping strategy Prechelt (1997)
which is used to avoid overfitting when training a learner with an iterative
method. We add a self-loop action $($self-loop$,e_{s})$ to give the agent an
option of not expanding from $e_{s}$. When the agent chooses the self-loop
action for several times, we consider it means that the agent has found the
target tail entity, thus it can choose to end early.

In this module, we devise a self-loop controller to avoid over searching and
resource wasting. The self-loop controller has a dual judgment mechanism based
on the the maximum search step $S$ and the maximum loop number $N$. When the
search step reaches the maximum $S$, or the agent selects the self-loop action
for $N$ consecutive times, the search process will be stopped. Using the ASS
strategy improves our model’s scalability on both short and long distances and
effectively avoids wasting of resources caused by over-searching.

Input: The training samples set $\mathcal{D}_{train}$; background KG
($\mathcal{T}$, $\mathcal{E}$, $\mathcal{R}$); the maximum search step $S$;
the maximum loop number $N$; the randomly initialized parameters $\theta$

Output: The optimized parameters $\theta$

1

2repeat

3 Sample a triple $(e_{h},r,e_{t})$ from $\mathcal{D}_{train}$;

4 Initialize: $s=0$; $n=0$; $e_{s}=e_{h}$;
$\mathcal{H}_{s}=\left\\{e_{h}\right\\}$;
$\mathcal{A}_{s}=\left\\{({{r_{s}^{i}}},{{e_{s}^{i}}})|({e}_{h},{{r_{s}^{i}}},{{e_{s}^{i}}})\in\mathcal{T}\right\\}$;

5 for  _$s <S$ and $n<N$_ do

6 Calculate $lk_{s}$ (Eq. 2) and $gk_{s}$ (Eq. 3);

7 Fuse $lk_{s}$ and $gk_{s}$ to yield the final score;

8 Dropout actions from $\mathcal{A}_{s}$ (Eq. 4);

9 Select the next entity $e_{s+1}$ and the related relation $r_{s+1}$;

10 if  _$r_{s+1}=$ self-loop_ then

11 $n\leftarrow n+1$;

12

13 update
$His_{s+1}\leftarrow\mathcal{H}_{s}\cup\left\\{r_{s+1},e_{s+1}\right\\}$;
$\mathcal{A}_{s+1}\leftarrow\left\\{({{r_{s+1}^{i}}},{{e_{s+1}^{i}}})|({e}_{s+1},{{r_{s+1}^{i}}},{{e_{s+1}^{i}}})\in\mathcal{T}\right\\}$;

14 $s\leftarrow s+1$;

15 $\hat{e_{t}}=e_{s}$; calculate the reward $R(\hat{e_{t}}|e_{h},r,e_{t})$
and update $\theta$ (Eq. 6);

16until  _model converged_ ;

Algorithm 1 Training process of GMH

###  3.5 Training

Following Das et al. (2018), we frame the search process as a Markov Decision
Process (MDP) on the KG and adopt the on-policy RL method to train the agent.
We design a randomized history-dependent policy network
$\pi=(p(\mathcal{A}_{1}),...,p(\mathcal{A}_{s}),...,p(\mathcal{A}_{S}))$. The
policy network is trained by maximizing the expected reward over all training
samples $\mathcal{D}_{train}$:

$\displaystyle J(\theta)=$
$\displaystyle\mathbb{E}_{(e_{h},r,e_{t})\sim\mathcal{D}_{train}}$ (5)
$\displaystyle[\mathbb{E}_{A_{1},...,A_{S}\sim\pi}[R(\hat{e_{t}}|e_{h},r,e_{t})]].$

where $\theta$ denotes the set of parameters in GMH, $R(\cdot)$ is the reward
function and $\hat{e_{t}}$ is the final entity chosen by the agent. If
$\hat{e_{t}}={e}_{t}$, then the terminal reward is assigned +1 and 0
otherwise.

The optimization is conducted using the REINFORCE algorithm Williams (1992)
which iterates through all $(e_{h},r,e_{t})$ triples in $\mathcal{D}_{train}$
and updates $\theta$ with the following stochastic gradient:

$\bigtriangledown_{\theta}J(\theta)\approx\bigtriangledown_{\theta}\sum\nolimits_{s}R(\hat{e_{t}}|e_{h},r,e_{t})\log\pi_{\theta}.$
(6)

The training process is detailed in Algorithm 1. During a search process, for
each search step, the agent takes three operations: local-global knowledge
fusion (lines 5-6), differentiated action dropout (line 7) and adaptive
stopping search (lines 8-10). After finding the tail entity, the reward is
calculated and the parameters are updated (line 13). Finally, the optimized
parameters are output.

##  4 Experiment

###  4.1 Setup

Dataset Existing popular benchmarks, such as UMLS Stanley and Pedro (2007) and
WN18RR Dettmers et al. (2018), focus on the multi-hop reasoning in short111
Considering that the current multi-hop reasoning works are concentrated on two
or three-hop paths, we regard the path hop number greater than three as a long
distance scenario. distance scenarios. Thus, they are unsuitable for
evaluating complex cases requiring both long and short distance learning. To
this end, we adopt the large-scale dataset FC17 Neelakantan et al. (2015)
which contains triples based on Freebase Bollacker et al. (2008) enriched with
the information fetched from ClueWeb Orr et al. (2013). Because the data with
distance type larger than five is relatively small, we maintain the data with
distance type between 2 and 5. The sample number of each distance type (2-5)
is 63k, 53k, 11k, 5k, respectively. Note that, there are extra relations
served in the background KG plus 46 relation types in the train/valid/test
sets of FC17. We also evaluate our model on the other short distance datasets,
i.e., UMLS and WN18RR. Table 1 summarizes the basic statistics of datasets.

Table 1: Statistics of datasets w.r.t. the number of entities and edges (the
middle two columns) and the separation of the train/valid/test sets (the right
three columns).

| entity | relation | train | valid | test
---|---|---|---|---|---
FC17 | 49k | 6k | 125k | 4k | 5k
UMLS | 135 | 46 | 5k | 652 | 661
WN18RR | 41k | 11 | 87k | 3k | 3k

Table 2:  MRR (%) and HITS@N (%) scores ($\pm$ standard deviation) for multi-
hop reasoning task on FC17, UMLS and WN18RR (pairwise t-test at 5%
significance level). Higher values mean better performances and the best
solution is marked in bold for each case.

| FC17 | UMLS | WN18RR
---|---|---|---
MRR | MRR($\leq 3$) | MRR($\geq 4$) | HITS@N |  MRR | HITS@N |  MRR | HITS@N
@1 |  @1 |  @10 |  @1 |  @10
TransE | 11.91 $\pm$0.20 | 12.38 $\pm$0.16 | 9.37 $\pm$0.28 | 6.90 $\pm$0.13 |  86.3 |  85.9 |  88.2 |  40.2 |  39.9 |  43.2
Distmult | 12.99 $\pm$0.67 | 13.57 $\pm$0.42 | 10.63 $\pm$0.43 | 8.53 $\pm$0.71 |  86.8 |  82.1 |  96.7 |  46.2 |  43.1 |  52.4
ComplEx | 14.73 $\pm$0.32 | 15.53 $\pm$0.37 | 10.91 $\pm$0.54 | 9.68 $\pm$0.53 |  93.4 |  89.0 |  99.2 |  43.7 |  41.8 |  48.0
ConvE | 18.98 $\pm$0.63 | 19.75 $\pm$0.63 | 15.31 $\pm$0.68 | 10.43 $\pm$0.85 |  95.7 |  93.2 |  99.4 |  44.9 |  40.3 |  54.0
MINERVA | 18.70 $\pm$0.42 | 19.92$\pm$0.36 | 13.84$\pm$0.45 | 9.08 $\pm$0.94 |  82.5 |  72.8 |  96.8 |  46.3 |  41.3 |  51.3
MultiHop | 20.28 $\pm$0.71 | 21.63 $\pm$0.65 | 14.07$\pm$0.76 | 10.53 $\pm$0.84 |  94.0 |  90.2 |  99.2 |  47.2 |  43.7 |  54.2
GMH |  23.75$\pm$0.52 |  25.06$\pm$0.52 |  18.52$\pm$0.56 |  12.98$\pm$0.76 |  96.2 |  93.9 |  99.9 |  46.5 |  45.3 |  55.8

Table 3: MRR (%) scores ($\pm$ standard deviation) for long distance multi-hop
reasoning task (pairwise t-test at 5% significance level). The testing samples
are divided into four types according to the distance.

| Distance Type
---|---
4 | 5 | 6 | 7
ConvE | 16.43$\pm$0.59 | 10.45$\pm$0.53 | 13.64$\pm$0.63 | 9.38$\pm$0.97
MINERVA | 17.60$\pm$0.73 | 10.90$\pm$0.61 | 10.65$\pm$0.88 | 5.09$\pm$0.87
MultiHop | 17.61$\pm$0.62 | 12.58$\pm$0.89 | 12.99$\pm$0.85 | 5.68$\pm$0.95
GMH | 20.53$\pm$0.56 | 14.62$\pm$0.85 | 14.12$\pm$0.65 | 9.74$\pm$0.83

Baselines

We compare GMH with 1) the embedding-based models involving TransE Bordes et
al. (2013), DistMult Yang et al. (2015), ComplEx Trouillon et al. (2016), and
ConvE Dettmers et al. (2018); as well as 2) the multi-hop reasoning models
involving MINERVA Das et al. (2018) and MultiHop Lin et al. (2018).

Implementation Details GMH is implemented on PyTorch and runs on a single
TITAN XP. Following Das et al. (2018), we augment KG with the reversed link
$(e_{t},r^{-1},e_{h})$ for each triple. We exclude the triples from the
training set if they occur in the validation or testing sets. For the
baselines and GMH, we set the maximum search step $S$ to five because the
entity pair’s distance is up to five in FC17. For the short distance datasets,
UMLS and WN18RR, $S$ is set to three. The maximum loop number $N$ for all
datasets is set to two. We employ softmax function as the activation function.
All hyper-parameters are tuned on the validation set can be found in
supplementary materials The pre-trained embedding-based model that we adopt is
ConvE. We optimize all models with Adam Kingma and Ba (2015)222We will release
the processed dataset and source code, after the paper is published. The
description of datasets and other details can be found in supplementary
materials. .

Metrics We follow the evaluation protocol of Lin et al. (2018) that records
the rank of the available entities at final step in a decreasing order of
confidence score for each query, and adopts mean reciprocal rank (MRR) and
HITS@N to evaluate the results. All results given in our experiments are the
mean and standard deviation values of three training repetitions.

###  4.2 Multi-hop Reasoning

Table 2 shows the results obtained on FC17 and two short distance datasets,
UMLS and WN18RR based on MRR (%) and HITS@N (%) measures. On the FC17 dataset,
GMH achieves 23.75% MRR score surpassing the second-best model MultiHop with
3.47% improvement based on the MRR metric. This includes 3.43% improvement on
short distance samples and 4.45% improvement on long distance samples. We
observe that multi-hop reasoning models outperform most embedding-based
models, but their performance declines when the distance increases. We assume
this may be attributed to the significantly increasing difficulty of building
long paths when predicting long distance relations. The embedding-based models
appear to be less sensitive to the distance variations, but they neglect the
deep information existing in multi-hop paths, which limits the interpretative
ability of predicting results. We further evaluate the short-distance
reasoning performance on UMLS and WN18RR. The results of the baselines are
cited from Lin et al. (2018). GMH performs comparably well in reasoning in the
short distance scenarios, yet its effectiveness in the long-short compound
reasoning or long distance reasoning scenarios is more obvious. For the WN18RR
dataset, GMH performs weaker than MultiHop. We speculate that this is because
the number of relations in WN18RR is extremely smaller than the number of
entities, which will make it difficult to accurately learn the relation
embeddings. Choosing a superior pre-trained embedding-based model is critical
for our model.

Multi-Hop Reasoning in long distance scenarios As we noticed in Table 2, GMH
achieves new state-of-the-art results on FC17 dataset which contains both
short distance and long distance types. We further evaluate its performance in
terms of reasoning on the relations in longer distances, which have been
rarely examined by the existing works. Therefore, we extract the relations
from FC17 whose distances span from 4 to 7 and in this way we construct a
subdataset, called FC17-8, which contains eight query relation types . Table 3
displays the results of reasoning on the four distance types based on the MRR
metric. Compared with GMH and the multi-hop reasoning models, the embedding-
based model seems less sensitive to the distance variations, while its
reasoning performance is inferior to the compared models on all distance
types. GMH consistently yields the best performance on the long distance
reasoning scenarios. We observe that all the models perform better on the even
distance type (4 and 6) than odd distance type (5 and 7). There are two
possible reasons: 1) there is an imbalance between the difficulty and the
number of different distance types; 2) the models are better at reasoning on
symmetric paths like the four-hop path Stephen Curry
$\xrightarrow[]{plays~{}for}$ Golden State Warriors
$\xrightarrow[]{compete~{}in}$ NBA $\xleftarrow[]{compete~{}in}$ Houston
Rockets $\xleftarrow[]{plays~{}for}$ James Harden.

In addition to the superior reasoning capability of GMH as demonstrated in
Table 2 and Table 3, other promising potentials pave the way for GMH in
advanced applications. First, GMH is explainable because it considers the path
information, which is beyond the scope of the existing embedding-based models.
Second, the global knowledge learnt from graph structure, which has been
overlooked by the existing multi-hop reasoning models, is incorporated in GMH.

###  4.3 Analysis of GMH

In this section, we conducted an extensive analysis of GMH from two aspects:
1) modules (c.f., Table 4); 2) hyper-parameters (c.f., Figure 4); and 3)
scoring functions and aggregators (c.f., Figure 5).

Local Knowledge vs. Global Knowledge We fuse two components (i.e., the local
knowledge $lk_{s}$ and the global knowledge $gk_{s}$) to enable the search
agent to find the target tail entity. Thus, an extensive experiment is
conducted to test the contributions of $lk_{s}$ and $gk_{s}$ in the multi-hop
reasoning task. The top three lines of Table 4 reveal that fusing $lk_{s}$ and
$gk_{s}$ achieves the best results under different evaluation metrics.
Removing either knowledge yields a significant performance drop. Concretely,
removing the local knowledge causes a 9.10% MRR degradation, and removing the
global knowledge results in a 4.05% MRR degradation. This suggests that the
local knowledge may be more beneficial for the search agent than the global
knowledge, and using only the local knowledge to find a path in KG may be
ineffective in the training process. Still we argue that the importance of the
global knowledge should not be neglected, especially when it is combined with
the local knowledge to handle the “where to go” issue.

Table 4: Analysis of GMH on FC17: GKL, LKL, DAD, and ASS represent the global
knowledge learning, local knowledge learning, differentiated action dropout,
and adaptive stopping search respectively.

| MRR | HITS@N
---|---|---
@1 | @10
GKL | 13.28 | 6.47 | 13.39
LKL | 18.33 | 9.86 | 25.17
LKL+GKL | 22.38 | 11.65 | 28.05
LKL+GKL+DAD | 23.25 | 12.10 | 28.29
GMH (LKL+GKL+DAD+ASS) | 23.75 | 12.98 | 29.86

Figure 4: MRR (%) scores and running time of GMH over different (a) maximum
search step $S$ and (b) maximum loop number $N$ on FC17. Best viewed in color.

Performance w.r.t. Differentiated Action Dropout The differentiated action
dropout module is adopted to increase the diversity of search paths in the
training stage. The fourth line of Table 4 shows the validity of this module.
We also test the effect of randomly action dropout (22.15% under MRR), and
there is a gap with our model. This illustrates that the reason why the
differentiated action dropout performs well is because the mask operation is
based on the global knowledge rather than on random strategy.

Performance w.r.t. Adaptive Stopping Search As mentioned before, we have
devised the adaptive stopping search module to avoid wasting of resources
caused by over-searching, i.e., the “when to stop” issue. As can be seen from
the bottom two rows of Table 4, ASS also has a slight effect on the
performance. This is because the module can partially prevent the search agent
from continuing to search when the target tail entity has been found.

Maximum Search Step As shown in Figure 4, GMH achieves best performance at
$S=5$. Using a large $S$ will cause wasting of resources, while if using a
small $S$, it will affect the performance on the long distance reasoning
samples. Meanwhile, the running time rises sharply when increasing $S$.
Therefore, the introduction of adaptive stopping search module is necessary
and rational.

Maximum Loop Number We divide the self-loop action into two types: positive
and negative. The positive self-loop action means the agent arrives at the
target tail entity, while the negative self-loop action means the current
entity is not the target. See Figure 4, a small $N$ may cause the agent to
misrecognize negative actions as positive actions, while a large $N$ may lead
to lose the advantage of reducing time consumption. Compared with not using
the adaptive stopping search module (i.e., $N=1$), using it has resulted in a
significant improvement with the optimal number of 2.

(a) Scoring Function Type

(b) Aggregator Type

Figure 5: MRR (%) and HITS@N (%) scores comparison of GMH over different
scoring functions and aggregators on FC17. Best viewed in color.

Scoring Function Types The pre-trained embedding-based model that we adopt is
ConvE. For more extensive ablation analysis, we have conducted the experiments
by incorporating effective embedding-based models (i.e., TransE, DistMult,
ComplEx, and ConvE). As shown in Figure 5(a), ConvE has a superb ability to
learn the global semantic representation than other embedding-based models.

Aggregator Types We next investigate the performance of our model w.r.t
different aggregator types. We adopt two types of aggregators: summation and
scalar product, to fuse the local knowledge $lk_{s}$ and global knowledge
$gk_{s}$. We can see from Figure 5(b) that the scalar product outperforms the
summation. The advantage of the scalar product aggregator is that the
multiplication operation can increase the discrimination between available
actions.

##  5 Conclusions

We have studied the multi-hop reasoning task in long distance scenarios and
proposed a general model which could tackle both short and long distance
reasoning scenarios. Extensive experiments showed the effectiveness of our
model on three benchmarks. We will further consider the feasibility of
applying our model to complex real-world datasets with more long distance
reasoning scenarios and more relation types. Besides, we have noticed that
there are other “interference” in long distance reasoning. For example, noise
from the KG itself, i.e., the fact that it lacks validity. These noises can
gradually accumulate during long distance reasoning and affect the result
confidence. We leave the further investigation to future work.

##  6 Acknowledgements

We sincerely thank Jun Wang and Xu Zhang for their constructive suggestions on
this paper. This work was supported by the China Postdoctoral Science
Foundation (No.2021TQ0222).

## References

  * Bollacker et al. (2008) Kurt D. Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008\.  Freebase: A collaboratively created graph database for structuring human knowledge.  In _Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD’08)_ , pages 1247–1250.
  * 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 the 26th Conference on Neural Information Processing Systems (NeurIPS’13)_ , pages 2787–2795.
  * 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 the 6th International Conference on Learning Representations (ICLR’18)_.
  * Das et al. (2017) Rajarshi Das, Arvind Neelakantan, David Belanger, and Andrew McCallum. 2017.  Chains of reasoning over entities, relations, and text using recurrent neural networks.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics (EACL’17)_ , pages 132–141.
  * Dettmers et al. (2018) Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018.  Convolutional 2d knowledge graph embeddings.  In _Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI’18)_ , pages 1811–1818.
  * Huang et al. (2019) Xiao Huang, Jingyuan Zhang, Dingcheng Li, and Ping Li. 2019.  Knowledge graph embedding based question answering.  In _Proceedings of the 12th ACM International Conference on Web Search and Data Mining (WSDM’19)_ , pages 105–113.
  * Ji et al. (2016) Guoliang Ji, Kang Liu, Shizhu He, and Jun Zhao. 2016.  Knowledge graph completion with adaptive sparse transfer matrix.  In _Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI’16)_ , pages 985–991.
  * Jiang et al. (2017) Xiaotian Jiang, Quan Wang, Baoyuan Qi, Yongqin Qiu, Peng Li, and Bin Wang. 2017\.  Attentive path combination for knowledge graph completion.  In _Proceedings of The 9th Asian Conference on Machine Learning (ACML’17)_ , pages 590–605.
  * Kingma and Ba (2015) Diederik Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  In _Proceedings of the 3rd International Conference on Learning Representations (ICLR’15)_.
  * Lao et al. (2011) Ni Lao, Tom Mitchell, and William W. Cohen. 2011.  Random walk inference and learning in a large scale knowledge base.  In _Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing (EMNLP’11)_ , pages 529–539.
  * Lei et al. (2020) Wenqiang Lei, Xiangnan He, Maarten de Rijke, and Tat-Seng Chua. 2020.  Conversational recommendation: Formulation, methods, and evaluation.  In _Proceedings of the 43rd International ACM SIGIR Conference on Research & Development in Information Retrieval (SIGIR’20)_, pages 2425–2428.
  * Lin et al. (2018) Xi Victoria Lin, Richard Socher, and Caiming Xiong. 2018.  Multi-hop knowledge graph reasoning with reward shaping.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP’18)_ , pages 3243–3253.
  * Lin et al. (2015) Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. 2015.  Learning entity and relation embeddings for knowledge graph completion.  In _Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI’15)_ , pages 2181–2187.
  * Lv et al. (2019) Xin Lv, Yuxian Gu, Xu Han, Lei Hou, Juanzi Li, and Zhiyuan Liu. 2019.  Adapting meta knowledge graph information for multi-hop reasoning over few-shot relations.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP’19)_ , pages 3376–3381.
  * Nathani et al. (2019) Deepak Nathani, Jatin Chauhan, Charu Sharma, and Manohar Kaul. 2019.  Learning attention-based embeddings for relation prediction in knowledge graphs.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (ACL’19)_ , pages 4710–4723.
  * Neelakantan et al. (2015) Arvind Neelakantan, Benjamin Roth, and Andrew McCallum. 2015.  Compositional vector space models for knowledge base completion.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (ACL’15)_ , pages 156–166.
  * Orr et al. (2013) Dave Orr, Amarnag Subramanya, Evgeniy Gabrilovich, and Michael Ringgaard. 2013.  11 billion clues in 800 million documents: A web research corpus annotated with freebase concepts.
  * Prechelt (1997) Lutz Prechelt. 1997.  Early stopping - but when? _Neural Networks: Tricks of the Trade_ , 1524(2):55–69.
  * Socher et al. (2013) Richard Socher, Danqi Chen, Christopher D. Manning, and Andrew Y. Ng. 2013.  Reasoning with neural tensor networks for knowledge base completion.  In _Proceedings of the 26th International Conference on Neural Information Processing Systems ((NeurIPS’13))_ , page 926–934.
  * Stanley and Pedro (2007) Kok Stanley and Domingos Pedro. 2007.  Statistical predicate invention.  In _Proceedings of the 24th International Conference on Machine Learning (ICML’07)_ , pages 433–440.
  * Suchanek et al. (2007) Fabian M. Suchanek, Gjergji Kasneci, and Gerhard Weikum. 2007.  Yago: A core of semantic knowledge.  In _Proceedings of the 16th International Conference on World Wide Web (WWW’07)_ , pages 697–706.
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016.  Complex embeddings for simple link prediction.  In _Proceedings of the 33rd International Conference on Machine Learning (ICML’16)_ , pages 2071–2080.
  * Tuan et al. (2019) Yi-Lin Tuan, Yun-Nung Chen, and Hung-yi Lee. 2019.  DyKgChat: Benchmarking dialogue generation grounding on dynamic knowledge graphs.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP’19)_ , pages 1855–1865.
  * Wang et al. (2019) Xiang Wang, Dingxian Wang, Canran Xu, Xiangnan He, Yixin Cao, and Tat-Seng Chua. 2019.  Explainable reasoning over knowledge graphs for recommendation.  In _Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI’19)_ , pages 5329–5336.
  * Wang et al. (2014) Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014.  Knowledge graph embedding by translating on hyperplanes.  In _Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI’14)_ , pages 1112–1119.
  * Williams (1992) Ronald J. Williams. 1992.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine Learning_ , 8(3-4):229–256.
  * Xiong et al. (2017) Wenhan Xiong, Thien Hoang, and William Yang Wang. 2017.  Deeppath: A reinforcement learning method for knowledge graph reasoning.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing (EMNLP’17)_ , pages 564–573.
  * Yang et al. (2015) Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015.  Embedding entities and relations for learning and inference in knowledge bases.  In _Proceedings of the 3rd International Conference on Learning Representations (ICLR’15)_.
  * Yin et al. (2018) Wenpeng Yin, Yadollah Yaghoobzadeh, and Hinrich Schütze. 2018.  Recurrent one-hop predictions for reasoning over knowledge graphs.  In _Proceedings of the 27th International Conference on Computational Linguistics (COLING’18)_ , pages 2369–2378.
  * Zhang et al. (2018) Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander J Smola, and Le Song. 2018\.  Variational reasoning for question answering with knowledge graph.  In _Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI’18)_ , pages 6069–6076.