# Short $\&$ simple introduction to
Bellman filtering and smoothing

Rutger-Jan Lange
Econometric Institute, Erasmus University Rotterdam, Netherlands I thank Dick
van Dijk, Simon Donker van Heel and Ramon de Punder for useful comments.

###### Abstract

Based on Bellman’s dynamic-programming principle, Lange (2024) presents an
approximate method for filtering, smoothing and parameter estimation for
possibly non-linear and/or non-Gaussian state-space models. While the approach
applies more generally, this pedagogical note highlights the main results in
the case where (i) the state transition remains linear and Gaussian while (ii)
the observation density is log-concave and sufficiently smooth in the state
variable. I demonstrate how Kalman’s (1960) filter and Rauch et al.’s (1965)
smoother can be obtained as special cases within the proposed framework. The
main aim is to present non-experts (and my own students) with an accessible
introduction, enabling them to implement the proposed methods.

Keywords: state-space model, Kalman filter, Rauch Tung Striebel smoother,
particle filter

##  1 State-space model

State-space model with general observation density. For discrete times
$t=1,\ldots,n$, a state-space model with a linear Gaussian state-transition
equation but a general observation density can be written as

observation equation: $\displaystyle\quad\bm{y}_{t}$ $\displaystyle\sim
p(\bm{y}_{t}|\bm{x}_{t}),$ (1) state-transition equation:
$\displaystyle\quad\bm{x}_{t}$
$\displaystyle=\bm{c}\,+\,\bm{T}\,\bm{x}_{t-1}\,+\,\bm{R}\,\bm{\eta}_{t},\quad\bm{\eta}_{t}\sim\text{i.i.d.}\mathrm{N}(\bm{0},\bm{Q}),$
(2)

which roughly matches the notation in Harvey (1990) and Durbin and Koopman
(2012, p. 209-10). These authors write $\bm{\alpha}_{t}$ where I write
$\bm{x}_{t}$; the latter is apparently more common in statistics and
engineering (e.g. Katzfuss et al., 2016). It is implicitly assumed that
$\bm{x}_{t}$ takes values in $\mathbb{R}^{d}$, where $d$ is the dimension of
the state space. The dimension of the column vector $\bm{y}_{t}$ is left
implicit and need _not_ match that of $\bm{x}_{t}$.

Observation equation. Equation (1) says that $\bm{y}_{t}$ is drawn from a
conditional density $p(\cdot|\bm{x}_{t})$. While purists may object to the
(abuse of) notation, equation (1) is nevertheless common in econometrics (e.g.
Durbin and Koopman, 2012, pp. 209-10). The observation density
$p(\cdot|\bm{x}_{t})$ may further depend on static shape parameters or
exogenous variables that are known at time $t-1$, but for simplicity these
dependencies are suppressed. When the data $\bm{y}_{t}$ are discrete (e.g. in
the case of count data), $p(\cdot|\bm{x}_{t})$ can be interpreted as a
probability rather than a density. For each (fixed) $\bm{y}$, our standing
assumptions are that $\log p(\bm{y}|\bm{x})$ is (i) concave and (ii) twice
continuously differentiable in the state variable $\bm{x}\in\mathbb{R}^{d}$.
These assumptions imply that the Hessian matrix of $\log p(\bm{y}|\bm{x})$
with respect to $\bm{x}$ is well-defined and negative semi-definite for all
$\bm{x}$ and all $\bm{y}$.

State-transition equation. Equation (2) says that the unobserved state
$\bm{x}_{t}$ follows linear dynamics with an intercept $\bm{c}$, transfer
matrix $\bm{T}$, selection matrix $\bm{R}$ (which typically contains ones and
zeros) and independent and identically distributed (i.i.d.) Gaussian
increments $\bm{\eta}_{t}$ with mean zero and positive semi-definite
covariance matrix $\bm{Q}$, where the nomenclature is taken from Durbin and
Koopman (2012, pp. 43-4). It is convenient (and nonrestrictive) to assume that
the transfer matrix $\bm{T}$ contains at least _some_ non-zero elements;
otherwise, there would be no persistence in the latent state. For simplicity I
assume that $\bm{c}$, $\bm{T}$, $\bm{R}$ and $\bm{Q}$ are static, but
following Durbin and Koopman (2012, p. 43) these quantities could be allowed
to depend deterministically or stochastically on time; at least, as long as
the relevant quantities at time $t$ are known to the researcher at time $t-1$.

Three aims. We are interested in (i) filtering, (ii) smoothing and (iii)
parameter estimation. Filtering means estimating the most _recent_ state
$\bm{x}_{t}$ for all $t\leq n$ based on the real-time (i.e. expanding)
information set $\\{\bm{y}_{i}\\}_{i=1,\ldots,t}$. Smoothing means estimating
_all_ states $\\{\bm{x}_{i}\\}_{i=1,\ldots,n}$ based on the whole (i.e. fixed)
data set $\\{\bm{y}_{i}\\}_{i=1,\ldots,n}$. The third aim is to estimate,
additionally, the static parameters in equations (1)–(2).

Special case: Linear Gaussian observation equation. A famous example of the
general state-space model above is the linear Gaussian state-space model, in
which case the general observation equation (1) is replaced by its linear
Gaussian version that in the notation of Harvey (1990, pp. 100-1) or Durbin
and Koopman (2012, p. 85) reads

$\text{observation
equation:}\qquad\bm{y}_{t}=\bm{d}\,+\,\bm{Z}\,\bm{x}_{t}\,+\,\bm{\varepsilon}_{t},\qquad\bm{\varepsilon}_{t}\sim\text{i.i.d.}\mathrm{N}(\bm{0},\bm{H}),$
(3)

while the state transition follows equation (2). As the entire state-space
model (2)–(3) is now linear and Gaussian, this is the standard case to which
Kalman’s (1960) filter and Rauch et al.’s (1965) smoother apply. Here,
$\bm{y}_{t}$ is a linear transformation of the latent state $\bm{x}_{t}$, with
intercept $\bm{d}$ and coefficient matrix $\bm{Z}$, while the additive
observation noise $\bm{\varepsilon}_{t}$ is i.i.d. Gaussian with mean zero and
covariance matrix $\bm{H}$, which for simplicity is assumed to be positive
definite. (By a standard limiting argument, the results below remain valid if
$\bm{H}$ is only positive _semi_ -definite.) It is again convenient (and
nonrestrictive) to assume that $\bm{Z}$ contains at least _some_ non-zero
elements, as otherwise the observations would be entirely uninformative about
states.

##  2 Statement of Bellman filter for model (1)–(2)

Background. Using Bellman’s (1957) dynamic-programming principle, Lange (2024)
derives an approximate filter based on recursively estimating the most likely
value of $\bm{x}_{t}$, i.e. the mode. While the approach is generally
applicable, the resulting filter takes a particularly attractive form if we
are content to maintain the classic assumption of a linear Gaussian state
equation (2), while allowing the general observation density (1).

Notation. Like the Kalman filter, the Bellman filter keeps track of one-step-
ahead predicted estimates of $\bm{x}_{t}$, denoted $\hat{\bm{x}}_{t|t-1}$, and
real-time (i.e. ‘filtered’) estimates of $\bm{x}_{t}$, denoted
$\hat{\bm{x}}_{t|t}$. The corresponding measures of uncertainty are denoted
$\bm{P}_{t|t-1}$ and $\bm{P}_{t|t}$, respectively, which can be roughly
interpreted as covariance matrices; this interpretation is exact when the
Kalman filter applies.

Fisher’s information. Fisher’s information matrix (in $\mathbb{R}^{d\times
d}$) is defined as an expectation, over $\bm{y}$, of the negative Hessian
matrix of $\log p(\bm{y}|\bm{x})$, conditional on $\bm{x}$, i.e.

$\bm{\mathcal{I}}(\bm{x})\;:=\;\int\left[-\nabla^{2}\log
p(\bm{y}|\bm{x})\right]p(\bm{y}|\bm{x})\,\mathrm{d}\bm{y},\qquad\bm{x}\in\mathbb{R}^{d},$
(4)

where the integral can be replaced by a summation in the case of discrete
observations. The information quantity $\bm{\mathcal{I}}(\bm{x})$ can be
evaluated at any state variable $\bm{x}$; below, we need
$\bm{\mathcal{I}}(\hat{\bm{x}}_{t|t})$. Throughout, the gradient
$\nabla:=\mathrm{d}/\mathrm{d}\bm{x}$ and Hessian operator
$\nabla^{2}:=\nabla\nabla^{\prime}=\mathrm{d}^{2}/(\mathrm{d}\bm{x}\mathrm{d}\bm{x}^{\prime})$,
where a prime denotes a transpose, are understood as acting on the state
variable $\bm{x}$. Fisher’s information $\bm{\mathcal{I}}(\bm{x})$ can often
be computed in closed form; moreover, it is positive semi-definite under our
standing assumptions.

Prediction step. Let $t\geq 1$ and suppose that $\bm{P}_{t-1|t-1}$ is positive
definite with bounded eigenvalues. The proposed prediction steps in Lange
(2024, Table 3) coincide with those of the Kalman filter (e.g. Harvey, 1990,
pp. 105-6 and Durbin and Koopman, 2012, p. 86):

$\displaystyle\hat{\bm{x}}_{t|t-1}$
$\displaystyle=\bm{c}+\bm{T}\,\hat{\bm{x}}_{t-1|t-1},$ (5)
$\displaystyle\bm{P}_{t|t-1}$
$\displaystyle=\bm{T}\bm{P}_{t-1|t-1}\bm{T}^{\prime}+\bm{R}\,\bm{Q}\,\bm{R}^{\prime}.$
(6)

Intuitively, the level prediction (5) mimics the true dynamics (2), while the
uncertainty prediction (6) can be analogously derived. The predicted
uncertainty measure $\bm{P}_{t|t-1}$ is positive definite, because
$\bm{P}_{t-1|t-1}$ is assumed positive definite and $\bm{T}$ contains at least
some non-zero elements, while $\bm{R}\bm{Q}\bm{R}^{\prime}$ is positive semi-
definite (as $\bm{Q}$ is positive semi-definite).

Updating step. The Bellman-filtered update as postulated in Lange (2024, eq.
16) is

$\displaystyle\hat{\bm{x}}_{t|t}$
$\displaystyle=\arg\max_{\bm{x}\in\mathbb{R}^{d}}\Big{\\{}\log
p(\bm{y}_{t}|\bm{x})-\frac{1}{2}(\bm{x}-\hat{\bm{x}}_{t|t-1})^{\prime}\bm{P}_{t|t-1}^{-1}(\bm{x}-\hat{\bm{x}}_{t|t-1})\Big{\\}},$
(7) $\displaystyle\bm{P}_{t|t}$
$\displaystyle=\big{[}\bm{P}_{t|t-1}^{-1}+\bm{\mathcal{I}}(\hat{\bm{x}}_{t|t})\big{]}^{-1},$
(8)

where $(\cdot)^{-1}$ denotes a matrix inverse.

Interpretation of level update (7). Equation (7) says that the researcher’s
filtered state $\hat{\bm{x}}_{t|t}$ maximises the current log-likelihood
contribution, $\log p(\bm{y}_{t}|\bm{x})$, subject to a quadratic penalty
centred around the prediction $\hat{\bm{x}}_{t|t-1}$. The strength of the
penalty is determined by $\bm{P}_{t|t-1}^{-1}$, such that the penalty is
weaker when the predicted uncertainty is larger; in effect, more weight is
then placed on the observation $\bm{y}_{t}$, while the influence of the
prediction $\hat{\bm{x}}_{t|t-1}$ is diminished. This interpretation reveals a
close connection with stochastic proximal point methods (e.g. Toulis and
Airoldi, 2017, Patrascu and Necoara, 2018 and Asi and Duchi, 2019), because
update (7) can be viewed as computing a new ‘point’ $\hat{\bm{x}}_{t|t}$ that
is ‘stochastic’ due to the observation $\bm{y}_{t}$, while remaining
‘proximal’ (i.e. close) to the prediction $\hat{\bm{x}}_{t|t-1}$. Hence the
Kalman filter—a special case of equation (7), as shown in section 4—is, in
fact, a stochastic proximal point method; to my knowledge, this fact has not
been explicitly recognised. This may be because proximal methods are typically
used for gradually ‘learning’ unknown _static_ parameters (see section 3),
while we are interested in tracking a _time-varying_ unobserved state.
Recasting the Kalman filter as an instance of a (dynamic) proximal method is
relevant as the latter permits favourable properties that are well known in
the literature (e.g. stability and contractivity).

Equation (7) can also be understood as computing the posterior mode in a
Bayesian setting, in which case the quadratic penalty is interpreted as a
Gaussian prior with mean $\hat{\bm{x}}_{t|t-1}$ and covariance matrix
$\bm{P}_{t|t-1}$. This interpretation reveals a connection with Laplace
approximations methods in both the Bayesian (e.g. Rue et al., 2009) and
frequentist literature (e.g. Koyama et al., 2010). The analogy with these
methods breaks down when considering more general dynamics than the linear
Gaussian state equation (2); see Lange (2024, sec. 3) for a discussion of the
Bellman filter in the more general case.

Interpretation of uncertainty update (8). Equation (8) says that the updated
measure of uncertainty, $\bm{P}_{t|t}$, is the inverse of the expectation of
the negative Hessian matrix of the objective function, evaluated at the peak.
As Fisher’s information is positive semi-definite, the resulting matrix
$\bm{P}_{t|t}$ is positive definite as desired. Several authors (e.g.
Fahrmeir, 1992, p. 504 and Lambert et al., 2022, eq. 36) write Kalman’s
covariance update as in our equation (8), but their generalisations of
Kalman’s level update differ from ours.

In equation (8), Fisher’s information quantity
$\bm{\mathcal{I}}(\hat{\bm{x}}_{t|t})$ may be replaced, when convenient, by
its ‘realised’ version $-\nabla^{2}\log p(\bm{y}_{t}|\hat{\bm{x}}_{t|t})$,
which is similarly positive semi-definite under our standing assumptions.
Indeed, this would yield the approximate covariance update in Ollivier (2018,
eq. 2.1). As suggested in Lange (2024, sec. 8), we may also employ a weighted
average of $\bm{\mathcal{I}}(\hat{\bm{x}}_{t|t})$ and $-\nabla^{2}\log
p(\bm{y}_{t}|\hat{\bm{x}}_{t|t})$. While we have assumed that $\log
p(\bm{y}_{t}|\bm{x})$ is concave in $\bm{x}$, taking a weighted average may be
particularly useful when this assumption is violated; in this case, a
sufficiently large weight should be placed on the Fisher information matrix to
ensure that the weighted sum is positive definite. These approaches are
identical for the linear Gaussian observation equation (3), for then, as shown
in section 4, the negative Hessian is constant and (hence) equals the Fisher
information matrix.

Initialisation. Transformations (6) and (8) preserve positive definiteness of
the uncertainty measures $\smash{\\{\bm{P}_{t|t-1}\\}_{t=1,\ldots,n}}$ and
$\smash{\\{\bm{P}_{t|t}\\}_{t=1,\ldots,n}}$ under our standing assumptions on
$\log p(\bm{y}|\bm{x})$ along with the fact that $\bm{T}$ contains at least
some non-zero elements. This means that the Bellman filter can be initialised
with any positive definite matrix $\bm{P}_{0|0}$ (and an arbitrary
$\hat{\bm{x}}_{0|0}$), such that recursions (5) through (8) remain well-
defined for all $t=1,\ldots,n$.

###  2.1 Computing the filtered state

Importantly for computation, $\hat{\bm{x}}_{t|t}$ is guaranteed to exist (i.e.
uniquely), because the objective function, in curly brackets in equation (7),
is _strongly concave_ in $\bm{x}\in\mathbb{R}^{d}$. Strong concavity of a
twice-continuously differentiable function means that the largest eigenvalue
of the Hessian matrix is negative and bounded away from zero by some
(positive) constant on the entire state space. Intuitively, the objective
function looks like an inverted parabola, for which the second derivative is
similarly negative and uniformly bounded away from zero.

In equation (7), the Hessian matrix $\smash{\nabla^{2}\log
p(\bm{y}_{t}|\bm{x})-\bm{P}_{t|t-1}^{-1}}$ satisfies these criteria under our
standing assumptions on $\log p(\bm{y}|\bm{x})$ in combination with the
positive definiteness of $\smash{\bm{P}_{t|t-1}^{-1}}$. As the Hessian of
$\log p(\bm{y}_{t}|\bm{x})$ is only negative _semi_ -definite, the smallest
eigenvalue of $\bm{P}_{t|t-1}^{-1}$ being positive is crucial in delivering
uniformity; this is guaranteed if $\bm{P}_{t|t-1}$ has finite (positive)
eigenvalues. It follows that $\hat{\bm{x}}_{t|t}$ is the location of the
unique stationary point, which can typically be found using standard (e.g.
quasi-Newton) optimisation techniques. Users may implement their own
optimisation algorithms or employ black-box optimisation tools. It may
occasionally be useful to note that, even if $\log p(\bm{y}|\bm{x})$ fails to
be (globally) concave in $\bm{x}$, optimisation (7) remains well defined if
the smallest eigenvalue of $\bm{P}_{t|t-1}^{-1}$ is sufficiently large; e.g.
Lange (2024, sec. 8) encounters no difficulties in several non-concave cases.

###  2.2 Theoretical guarantees

While the conditions discussed above guarantee that the Bellman filter can be
feasibly implemented, they are not (yet) sufficient to guarantee any
particular performance level. For example, we would like
$\bm{\mathcal{I}}(\hat{\bm{x}}_{t|t})$ to remain positive definite in the long
run, as this would ensure, via recursions (6) and (8), that the largest
eigenvalue of $\bm{P}_{t|t}$ remains uniformly bounded over time. We can
guarantee this by requiring the log-likelihood contribution $\log
p(\bm{y}|\bm{x})$ _itself_ to be strongly concave in $\bm{x}$ (for all
$\bm{y}$), as would the case for the linear Gaussian observation equation (3).
It can then be shown that the updating step (7) is contractive to a small
region around the true state at every time step (Lange, 2024, sec. 5), where
the ‘minimal contraction strength’ is the same for all time steps. Under some
additional conditions, the mean squared filtering error can then be shown to
remain uniformly bounded over time (Lange, 2024, sec. 5).

##  3 Online learning as a special case

In the online-learning literature (e.g. Orabona, 2019), the unobserved state
$\bm{x}_{t}$ is static (i.e. constant over time); hence, it is typically
viewed as an unknown parameter rather than an unobserved state. The researcher
is then interested in gradually ‘learning’ this parameter as more data becomes
available. This setup can be viewed as a special case of the state-transition
equation (2) by taking $\bm{c}=\bm{0}$ and $\bm{Q}=\bm{0}$, while setting
$\bm{T}$ equal to the identity matrix. We then have a setting similar to
Toulis and Airoldi (2017, eq. 7), who perform the parameter update, at each
time step, using the stochastic proximal method (7).

Under the above constraints on the state-transition equation (i.e.
$\bm{c}=\bm{0}$, $\bm{Q}=\bm{0}$, and $\bm{T}$ being the identity), equations
(6) and (8) yield $\bm{P}_{t|t-1}=\bm{P}_{t-1|t-1}$ and
$\bm{P}_{t|t}^{-1}=\bm{P}_{t-1|t}^{-1}+\bm{\mathcal{I}}(\hat{\bm{x}}_{t|t})$,
respectively. Together, this implies that $\bm{P}_{t|t}^{-1}$ is bigger, in a
positive semi-definite sense, than $\bm{P}_{t-1|t-1}^{-1}$ at every time step.
If the additive part $\bm{\mathcal{I}}(\hat{\bm{x}}_{t|t})$ is positive
definite in the long run, then $\bm{P}_{t|t}^{-1}=O(t)$, such that
$\bm{P}_{t|t}=O(1/t)$. This means that our estimate $\hat{\bm{x}}_{t|t}$
converges, in the long run, to a constant vector; i.e. eventually we ‘learn’
the true state with perfect precision (e.g. Ollivier, 2018, p. 2938). When
$\bm{Q}$ is nonzero, however, the Bellman filter remains perpetually
responsive, which makes sense when the true state continues to vary. We are
then interested in ‘tracking’ some path rather than ‘learning’ some parameter;
as such, there is no longer any ‘convergence’ to a static long-run
equilibrium.

##  4 Kalman filter as a special case

Predictions (5)–(6) are identical to those in the Kalman filter. While the
Bellman filter’s updating steps (7)–(8) are formulated more generally, they
collapse to the standard expressions in the setting of the linear Gaussian
observation equation (3), as shown here.

Score and Hessian. For the linear Gaussian observation equation (3), the
logarithmic observation density along with the score and Hessian read

log density: $\displaystyle\log p(\bm{y}|\bm{x})$
$\displaystyle\propto-\smash{\frac{1}{2}}(\bm{y}-\bm{d}-\bm{Z}\bm{x})^{\prime}\bm{H}^{-1}(\bm{y}-\bm{d}-\bm{Z}\bm{x}),$
score: $\displaystyle\nabla\log p(\bm{y}|\bm{x})$
$\displaystyle=\bm{Z}^{\prime}\bm{H}^{-1}(\bm{y}-\bm{d}-\bm{Z}\bm{x}),$ (9)
Hessian: $\displaystyle\nabla^{2}\log p(\bm{y}|\bm{x})$
$\displaystyle=-\bm{Z}^{\prime}\bm{H}^{-1}\bm{Z}.$ (10)

The score (9) is linear in $\bm{x}$; hence, the Hessian matrix (10) is
constant. Hence Fisher’s information (4) equals
$\bm{\mathcal{I}}(\bm{x})=\bm{Z}^{\prime}\bm{H}^{-1}\bm{Z}$, which is positive
definite as $\bm{H}$ is assumed positive definite, while $\bm{Z}$ contains at
least _some_ non-zero elements. The Hessian matrix is negative definite for
the same reasons; hence, $\log p(\bm{y}|\bm{x})$ is strongly concave in
$\bm{x}$ (for all $\bm{y}$) such that the theoretical guarantees in section
2.2 apply.

Level update. To show that the Kalman-filter level update is a special case of
the Bellman filter’s optimisation (7), I write down the first-order condition
of the latter, i.e. $\bm{0}=\nabla\log
p(\bm{y}_{t}|\hat{\bm{x}}_{t|t})-\bm{P}_{t|t-1}^{-1}(\hat{\bm{x}}_{t|t}-\hat{\bm{x}}_{t|t-1})$,
and substitute the score (9) to yield

$\bm{0}=\bm{Z}^{\prime}\bm{H}^{-1}(\bm{y}_{t}-\bm{d}-\bm{Z}\hat{\bm{x}}_{t|t})-\bm{P}_{t|t-1}^{-1}(\hat{\bm{x}}_{t|t}-\hat{\bm{x}}_{t|t-1}).$

By several steps of straightforward linear algebra, this equation can be
solved for $\hat{\bm{x}}_{t|t}$ to yield the classic Kalman-filter update:

$\displaystyle\small\hat{\bm{x}}_{t|t}$
$\displaystyle\small=(\bm{Z}^{\prime}\bm{H}^{-1}\bm{Z}+\bm{P}^{-1}_{t|t-1})^{-1}[\bm{Z}^{\prime}\bm{H}^{-1}(\bm{y}_{t}-\bm{d})+\bm{P}_{t|t-1}^{-1}\hat{\bm{x}}_{t|t-1}],$
$\displaystyle\small=(\bm{Z}^{\prime}\bm{H}^{-1}\bm{Z}+\bm{P}^{-1}_{t|t-1})^{-1}[\bm{Z}^{\prime}\bm{H}^{-1}(\bm{y}_{t}-\bm{d})+(\bm{P}_{t|t-1}^{-1}+\underbrace{\bm{Z}^{\prime}\bm{H}^{-1}\bm{Z}-\bm{Z}^{\prime}\bm{H}^{-1}\bm{Z}}_{=\bm{0}})\hat{\bm{x}}_{t|t-1}],$
$\displaystyle\small=\hat{\bm{x}}_{t|t-1}+(\bm{Z}^{\prime}\bm{H}^{-1}\bm{Z}+\bm{P}^{-1}_{t|t-1})^{-1}\bm{Z}^{\prime}\bm{H}^{-1}(\bm{y}_{t}-\bm{d}-\bm{Z}\hat{\bm{x}}_{t|t-1}),$
$\displaystyle\small=\hat{\bm{x}}_{t|t-1}+\bm{P}_{t|t-1}\bm{Z}^{\prime}(\bm{Z}\bm{P}_{t|t-1}\bm{Z}^{\prime}+\bm{H})^{-1}(\bm{y}_{t}-\bm{d}-\bm{Z}\hat{\bm{x}}_{t|t-1}),$
(11)

where the last line, which follows from a standard matrix-inversion lemma (see
equation (16) below), is the standard Kalman-filter level update; see e.g.
Harvey (1990, p. 106) or Durbin and Koopman (2012, p. 86).

Uncertainty update. Taking the Bellman-filter uncertainty update (8) and
substituting the specific (constant) Fisher information
$\bm{\mathcal{I}}(\bm{x})=\bm{Z}^{\prime}\bm{H}^{-1}\bm{Z}$ yields

$\displaystyle\bm{P}_{t|t}=[\bm{P}_{t|t-1}^{-1}+\bm{\mathcal{I}}(\hat{\bm{x}}_{t|t})]^{-1}$
$\displaystyle=[\bm{P}_{t|t-1}^{-1}+\bm{Z}^{\prime}\bm{H}^{-1}\bm{Z}]^{-1},$
$\displaystyle=\bm{P}_{t|t-1}-\bm{P}_{t|t-1}\bm{Z}^{\prime}(\bm{Z}\bm{P}_{t|t-1}\bm{Z}^{\prime}+\bm{H})^{-1}\bm{Z}\bm{P}_{t|t-1}.$
(12)

The second line, which employs the Woodbury matrix-inversion lemma (see
equation (17) below), is exactly Kalman’s covariance-matrix updating step;
again, see Harvey (1990, p. 106) or Durbin and Koopman (2012, p. 86).

In the context of the linear Gaussian observation equation (3), therefore, the
Bellman-filter updating steps (7) and (8) reduce to the standard Kalman-filter
updating steps (11) and (12), respectively. Equations (7) and (8) have the
possible advantage that they are easier to grasp, at an intuitive level, than
the more specific results (11) and (12), while also suggesting immediate
extensions of the latter when the assumptions of a linear and/or Gaussian
observation equation fail.

###  4.1 (Iterated) extended Kalman filter as a special case

The link between optimisation methods and the Kalman filter has been known
since Bell and Cathey (1993), at least in the context of nonlinear models with
additive Gaussian disturbances. To derive these classic results in our setup,
we may consider the non-linear (but still Gaussian) observation equation
$\bm{y}_{t}=\bm{d}+\bm{Z}(\bm{x}_{t})+\bm{\varepsilon}_{t}$, where
$\bm{\varepsilon}_{t}\sim\text{i.i.d.}\mathrm{N}(\bm{0},\bm{H})$ and
$\bm{Z}(\cdot)$ is now a non-linear vector function. When performing our
proposed update (7) using Gauss-Newton optimisation steps initialised at the
prediction $\hat{\bm{x}}_{t|t-1}$, while ignoring (i.e. setting to zero)
second-order derivatives of $\bm{Z}(\cdot)$, we obtain the iterated extended
Kalman filter as a special case (for details, see Lange, 2024, sec. 4.3).

##  5 Bellman smoother equals Kalman smoother

The Bellman smoother, derived in Lange (2024, sec. 7), combines both forward-
and backward dynamic-programming arguments. In the context of the linear
Gaussian state equation (2), but a possibly non-linear and/or non-Gaussian
observation equation (1), the Bellman smoother turns out to be _identical_ to
the classic Rauch-Tung-Striebel (RTS, 1965) smoother, which is often referred
to as the Kalman smoother (e.g. Durbin and Koopman, 2012, p. 91). Assuming the
data $\\{\bm{y}_{t}\\}_{t=1,\ldots,n}$ are fixed, the RTS smoother can be
written as (e.g. Harvey, 1990, p. 154 or Durbin and Koopman, 2012, pp. 96-7):

$\displaystyle\hat{\bm{x}}_{t|n}$
$\displaystyle=\hat{\bm{x}}_{t|t}+\bm{P}_{t|t}\bm{T}^{\prime}\bm{P}^{-1}_{t+1|t}(\hat{\bm{x}}_{t+1|n}-\hat{\bm{x}}_{t+1|t}),$
(13) $\displaystyle\bm{P}_{t|n}$
$\displaystyle=\bm{P}_{t|t}-\bm{P}_{t|t}\bm{T}^{\prime}\bm{P}^{-1}_{t+1|t}(\bm{P}_{t+1|t}-\bm{P}_{t+1|n})\bm{P}^{-1}_{t+1|t}\bm{T}\bm{P}_{t|t},$
(14)

which is a backward recursion for $t=1,\ldots,n$ that can be initialised at
$t=n$ using the output of the filter. The only difference relative to the
classic setting is that these expressions now apply in a possibly approximate
context, where the forward recursion may be executed by running the Bellman
(rather than the Kalman) filter. In the case of the linear Gaussian
observation equation (3), the Bellman filter/smoother combination collapses to
the standard Kalman filter/smoother.

##  6 Static (hyper-)parameter estimation

Apart from estimating the unobserved states, researchers also require a method
to estimate the static (hyper-)parameter vector, denoted here as $\bm{\psi}$.
The vector $\bm{\psi}$ contains (i) unknown shape parameters in the
observation density $p(\bm{y}|\bm{x})$ and (ii) unknown static parameters in
the state-transition equation (2), e.g. unknown parameters in $\bm{c}$,
$\bm{T}$, $\bm{R}$ and $\bm{Q}$. An approximate parameter-estimation method
based on the output of the Bellman filter, consisting of recursions (5)
through (8), is provided in Lange (2024, sec. 7) as

$\footnotesize\widehat{\bm{\psi}}:=\underset{\bm{\psi}}{\arg\max}\sum_{t=1}^{n}\Bigg{\\{}\log
p(\bm{y}_{t}|\hat{\bm{x}}_{t|t})-\Big{[}\frac{1}{2}\log\frac{\det(\bm{P}_{t|t-1})}{\det(\bm{P}_{t|t})}+\frac{1}{2}(\hat{\bm{x}}_{t|t}-\hat{\bm{x}}_{t|t-1})^{\prime}\,\bm{P}^{-1}_{t|t-1}\,(\hat{\bm{x}}_{t|t}-\hat{\bm{x}}_{t|t-1})\Big{]}\Bigg{\\}}.$
(15)

This estimator equals the standard maximum-likelihood estimator in the setting
of the linear Gaussian observation equation (3); otherwise, it can be viewed
as maximising a second-order approximation of the standard prediction-error
decomposition. Estimator (15) can be implemented using standard numerical
optimisation techniques, which is feasible as long as the dimension of
$\bm{\psi}$ is not too large (e.g. not exceeding $20$). For a wide variety of
models, Lange (2024, sec. 8) finds estimator (15) to be roughly as accurate as
(more computationally intensive) simulation-based methods, e.g. importance
samplers and particle filters.

Interpretation of estimator (15). The first term, $\log
p(\bm{y}_{t}|\hat{\bm{x}}_{t|t})$, can be viewed as measuring the ‘goodness of
fit’ of the Bellman-filtered state $\hat{\bm{x}}_{t|t}$, relative to the
observation $\bm{y}_{t}$. The term in square brackets, which appears with a
minus sign in front of it, can be viewed as a penalty that penalizes
deviations of $\hat{\bm{x}}_{t|t}$ from $\hat{\bm{x}}_{t|t-1}$ to prevent
overfitting. The nonnegativity of this penalty follows from the nonnegativity
of the quadratic expression along with the fact that
$\det(\bm{P}_{t|t-1})\geq\det(\bm{P}_{t|t})$. The latter follows from
uncertainty update (8), which implies that $\bm{P}_{t|t-1}$ is weakly
‘larger’, in a positive semi-definite sense, than $\bm{P}_{t|t}$. In estimator
(15), the trade-off between maximising the ‘fit’ of the filtered states and
minimising their ‘distance’ from the predictions gives rise to a meaningful
optimisation problem.

##  7 Matrix-inversion lemmas

The ‘matrix cookbook’ (eqns. 156 and 158, which can be found here) states two
useful matrix-inversion lemmas for positive-definite matrices $\bm{A}$,
$\bm{B}$ and an arbitrary (size-compatible) matrix $\bm{C}$:

$\displaystyle(\bm{A}+\bm{C}^{\prime}\bm{B}^{-1}\bm{C})^{-1}$
$\displaystyle\bm{C}^{\prime}\bm{B}^{-1}=\bm{A}^{-1}\bm{C}^{\prime}(\bm{B}+\bm{C}\bm{A}^{-1}\bm{C}^{\prime})^{-1}.$
(16) $\displaystyle(\bm{A}+\bm{C}^{\prime}\bm{B}^{-1}\bm{C})^{-1}$
$\displaystyle=\bm{A}^{-1}-\bm{A}^{-1}\bm{C}^{\prime}(\bm{B}+\bm{C}\bm{A}^{-1}\bm{C}^{\prime})^{-1}\bm{C}\bm{A}^{-1}.$
(17)

The second identity is a special case of the Woodbury matrix identity (e.g.
Sherman and Morrison, 1950 and Henderson and Searle, 1981). For the first
identity, however, no proof is provided in the cookbook or the reference cited
there. While the identity itself appears to be well-known (e.g. it is implied
by equations 9 and 10 of Henderson and Searle, 1981), a direct reference is
hard to find. For clarity, I provide a joint proof of both identities.

For positive-definite (hence invertible) matrices $\bm{A}$ and $\bm{B}$ and an
arbitrary (but size-compatible) matrix $\bm{C}$, consider the following block
matrix, $\bm{M}$, and its proposed inverse:

$\footnotesize\bm{M}:=\left[\begin{array}[]{cc}\bm{A}&\bm{C}^{\prime}\\\
\bm{C}&-\bm{B}\end{array}\right],\quad\bm{M}^{-1}=\left[\begin{array}[]{cc}(\bm{A}+\bm{C}^{\prime}\bm{B}^{-1}\bm{C})^{-1}&(\bm{A}+\bm{C}^{\prime}\bm{B}^{-1}\bm{C})^{-1}\bm{C}^{\prime}\bm{B}^{-1}\\\
(\bm{B}+\bm{C}\bm{A}^{-1}\bm{C}^{\prime})^{-1}\bm{C}\bm{A}^{-1}&-(\bm{B}+\bm{C}\bm{A}^{-1}\bm{C}^{\prime})^{-1}\end{array}\right].$
(18)

The correctness of the proposed inverse $\bm{M}^{-1}$ can be verified by
computing $\bm{M}^{-1}\bm{M}$ to yield the identity matrix. Alternatively,
$\bm{M}^{-1}$ can be expressed as

$\small\bm{M}^{-1}=\left[\begin{array}[]{cc}\bm{A}^{-1}-\bm{A}^{-1}\bm{C}^{\prime}(\bm{B}+\bm{C}\bm{A}^{-1}\bm{C}^{\prime})^{-1}\bm{C}\bm{A}^{-1}&\bm{A}^{-1}\bm{C}^{\prime}(\bm{B}+\bm{C}\bm{A}^{-1}\bm{C}^{\prime})^{-1}\\\
(\bm{B}+\bm{C}\bm{A}^{-1}\bm{C}^{\prime})^{-1}\bm{C}\bm{A}^{-1}&-(\bm{B}+\bm{C}\bm{A}^{-1}\bm{C}^{\prime})^{-1}\end{array}\right],$
(19)

which can again be verified by computing $\bm{M}^{-1}\bm{M}$ to yield the
identity. All required matrix inverses in expressions (18) and (19) exist,
relying only on the (assumed) positive definiteness of $\bm{A}$ and $\bm{B}$.
Hence $\bm{M}^{-1}$ exists. As $\bm{M}^{-1}$ is unique, the expressions in
equations (18) and (19) must be equal. Comparing both top-right blocks yields
equation (16), while comparing the top-left blocks yields equation (17).

##  8 Computational complexity

The computational complexity of the Bellman filter and smoother is similar to
that of the Kalman filter and smoother, enabling scalability to high-
dimensional state spaces, e.g. $150$ dimensions in Lange (2024, sec. 9). In
such high-dimensional settings, it is advisable to implement the Bellman
filter update (7) using a computationally efficient optimisation technique
that avoids repeated large-matrix inversions, e.g. the
Broyden–Fletcher–Goldfarb– Shanno (BFGS) algorithm. The Bellman filter’s
approach to ‘filtering by optimisation’ avoids the curse of dimensionality
faced by other methods (e.g. particle filters) that aim to approximate the
mean. Intuitively, optimising a smooth strongly concave function in $150$
dimensions is easier than integrating it. Lange (2024, sec. 9) finds that, in
such a high-dimensional setting, the Bellman filter can outperform the
particle filter in terms of both speed and precision: the former by a factor
${\sim}10^{3}$ and the latter by a factor of ${\sim}2$, even when the particle
filter employs very many particles (e.g. one million).

##  9 Computer code

Matlab code for Bellman filtering, smoothing and parameter estimation for
several state-space models is available from the _Journal of Econometrics_
website or my homepage.

## References

  * Asi and Duchi (2019) Asi, H. and J. C. Duchi (2019).  Stochastic (approximate) proximal point methods: Convergence, optimality, and adaptivity.  SIAM Journal on Optimization 29(3), 2257–2290.
  * Bell and Cathey (1993) Bell, B. M. and F. W. Cathey (1993).  The iterated Kalman filter update as a Gauss-Newton method.  IEEE Transactions on Automatic Control 38(2), 294–297.
  * Bellman (1957) Bellman, R. E. (1957).  Dynamic programming.  Princeton University Press.
  * Durbin and Koopman (2012) Durbin, J. and S. J. Koopman (2012).  Time series analysis by state space methods, Volume 38.  Oxford University Press.
  * Fahrmeir (1992) Fahrmeir, L. (1992).  Posterior mode estimation by extended Kalman filtering for multivariate dynamic generalized linear models.  Journal of the American Statistical Association 87(418), 501–509.
  * Harvey (1990) Harvey, A. C. (1990).  Forecasting, structural time series models and the Kalman filter.  Cambridge University Press.
  * Henderson and Searle (1981) Henderson, H. V. and S. R. Searle (1981).  On deriving the inverse of a sum of matrices.  SIAM Review 23(1), 53–60.
  * Kalman (1960) Kalman, R. E. (1960).  A new approach to linear filtering and prediction problems.  Journal of Basic Engineering 82(1), 35–45.
  * Katzfuss et al. (2016) Katzfuss, M., J. R. Stroud, and C. K. Wikle (2016).  Understanding the ensemble Kalman filter.  The American Statistician 70(4), 350–357.
  * Koyama et al. (2010) Koyama, S., L. Castellanos Pérez-Bolde, C. R. Shalizi, and R. E. Kass (2010).  Approximate methods for state-space models.  Journal of the American Statistical Association 105(489), 170–180.
  * Lambert et al. (2022) Lambert, M., S. Bonnabel, and F. Bach (2022).  The recursive variational Gaussian approximation (R-VGA).  Statistics and Computing 32(10), 1–24.
  * Lange (2024) Lange, R.-J. (2024).  Bellman filtering and smoothing for state–space models.  Journal of Econometrics 238(2), 105632.
  * Ollivier (2018) Ollivier, Y. (2018).  Online natural gradient as a Kalman filter.  Electronic Journal of Statistics 12(2), 2930–2961.
  * Orabona (2019) Orabona, F. (2019).  A modern introduction to online learning.  arXiv preprint arXiv:1912.13213.
  * Patrascu and Necoara (2018) Patrascu, A. and I. Necoara (2018).  Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization.  Journal of Machine Learning Research 18(198), 1–42.
  * Rauch et al. (1965) Rauch, H. E., F. Tung, and C. T. Striebel (1965).  Maximum likelihood estimates of linear dynamic systems.  AIAA Journal 3(8), 1445–1450.
  * Rue et al. (2009) Rue, H., S. Martino, and N. Chopin (2009).  Approximate Bayesian inference for latent Gaussian models by using integrated nested Laplace approximations.  Journal of the Royal Statistical Society Series B: Statistical Methodology 71(2), 319–392.
  * Sherman and Morrison (1950) Sherman, J. and W. J. Morrison (1950).  Adjustment of an inverse matrix corresponding to a change in one element of a given matrix.  The Annals of Mathematical Statistics 21(1), 124–127.
  * Toulis and Airoldi (2017) Toulis, P. and E. M. Airoldi (2017).  Asymptotic and finite-sample properties of estimators based on stochastic gradients.  Annals of Statistics 45(4), 1694–1727.


# Rethinking Graph Convolutional Networks in Knowledge
Graph Completion

Zhanqiu Zhang1, Jie Wang1,2,∗, Jieping Ye3,4, Feng Wu1 1CAS Key Laboratory of
Technology in GIPAS
University of Science and Technology of China 2Institute of Artificial
Intelligence
Hefei Comprehensive National Science Center<EMAIL_ADDRESS>jiewangx<EMAIL_ADDRESS>3University of Michigan4KE Holdings Inc.
<EMAIL_ADDRESS>
(2022)

###### Abstract.

Graph convolutional networks (GCNs)—which are effective in modeling graph
structures—have been increasingly popular in knowledge graph completion (KGC).
GCN-based KGC models first use GCNs to generate expressive entity
representations and then use knowledge graph embedding (KGE) models to capture
the interactions among entities and relations. However, many GCN-based KGC
models fail to outperform state-of-the-art KGE models though introducing
additional computational complexity. This phenomenon motivates us to explore
the real effect of GCNs in KGC. Therefore, in this paper, we build upon
representative GCN-based KGC models and introduce variants to find which
factor of GCNs is critical in KGC. Surprisingly, we observe from experiments
that the graph structure modeling in GCNs does not have a significant impact
on the performance of KGC models, which is in contrast to the common belief.
Instead, the transformations for entity representations are responsible for
the performance improvements. Based on the observation, we propose a simple
yet effective framework named LTE-KGE, which equips existing KGE models with
linearly transformed entity embeddings. Experiments demonstrate that LTE-KGE
models lead to similar performance improvements with GCN-based KGC methods,
while being more computationally efficient. These results suggest that
existing GCNs are unnecessary for KGC, and novel GCN-based KGC models should
count on more ablation studies to validate their effectiveness. The code of
all the experiments is available on GitHub at https://github.com/MIRALab-
USTC/GCN4KGC.

Knowledge graph completion, Graph convolutional networks

$\ast$ Corresponding Author

††journalyear: 2022††copyright: acmcopyright††conference: Proceedings of the
ACM Web Conference 2022; April 25–29, 2022; Virtual Event, Lyon,
France††booktitle: Proceedings of the ACM Web Conference 2022 (WWW ’22), April
25–29, 2022, Virtual Event, Lyon, France††price: 15.00††doi:
10.1145/3485447.3511923††isbn: 978-1-4503-9096-5/22/04††ccs: Computing
methodologies Reasoning about belief and knowledge

##  1\. Introduction

Knowledge graphs (KG) contains quantities of factual triplets—(head entity,
relation, tail entity)—which are widely used in many areas, such as e-commerce
(Luo et al., 2020; Luo et al., 2021), finance (Cheng et al., 2020; Liu et al.,
2020b), and social networks (Wang et al., 2019a; Liu et al., 2020a). Since
knowledge graphs are usually incomplete and manually finding all factual
triplets is expensive, how to automatically perform knowledge graph completion
(KGC) has attracted great attention. In the past few years, many knowledge
graph completion models have been proposed. For example, knowledge graph
embeddings (KGE) (Bordes et al., 2013; Yang et al., 2015; Trouillon et al.,
2016; Dettmers et al., 2018; Sun et al., 2019; Zhang et al., 2021) are popular
KGC models due to their simplicity and effectiveness. KGE models embed
entities and relations in a knowledge graph as low-dimensional representations
(embeddings) and define scoring functions on embedding spaces to measure the
plausibility of triplets. In general, valid triplets are supposed to have
higher scores than invalid triplets.

Recently, graph convolutional network (GCNs) have been increasingly popular
(Schlichtkrull et al., 2018; Shang et al., 2019; Ye et al., 2019; Nathani et
al., 2019; Vashishth et al., 2020b) in KGC, as GCNs are effective in modeling
graph structures. As shown in Figure 1, GCN-based KGC models usually use an
encoder-decoder framework, in which GCNs and KGE models serve as encoders and
decoders, respectively. Specifically, GCNs generate expressive representations
for entities and relations based on their neighbor entities and relations; KGE
models (such as TransE (Bordes et al., 2013), DistMult (Yang et al., 2015),
and ConvE (Dettmers et al., 2018)) model the interactions among entities and
relations using the representations generated by GCNs. Notably, different from
classical GCNs that only aggregate information from neighbor nodes (Kipf and
Welling, 2017; Hamilton et al., 2017), GCNs in KGC take edges (relations) in
knowledge graphs into account. Many works (Schlichtkrull et al., 2018; Shang
et al., 2019; Vashishth et al., 2020b) have demonstrated that adding GCNs
before KGE models leads to better performance.

Figure 1. The encoder-decoder framework of GCN-based KGC. GCNs are encoders to
generate entity and relation representations based on graph structure. KGE
models are decoders to recover the structure of knowledge graphs (KG)
according to the entity and relation representations generated by encoders.
The predicted unseen links are marked by red dashed line.

However, though researchers have made persistent efforts to optimize the
architectures and training strategies of GCNs, many GCN-based KGC models fail
to outperform state-of-the-art KGE models. For example, the state-of-the-art
GCN-based KGC model CompGCN (Vashishth et al., 2020b) achieves mean reciprocal
rank (MRR, higher is better) of 0.355 and 0.479 on the FB15k-237 (Dettmers et
al., 2018) and WN18RR (Toutanova and Chen, 2015) datasets respectively, while
the state-of-the-art KGE model ComplEx+N3 (Lacroix et al., 2018) attains MRR
of 0.366 and 0.489 (Zhang et al., 2020). That is to say, GCN-based models do
not show great advantages compared with KGE models while introducing
additional computational complexity. This phenomenon raises a question worth
consideration: ”What is the real effect of GCNs in the KGC task?”

In this paper, we try to explore the real effect of GCNs in KGC via extensive
experiments. We build upon representative GCN-based KGC models and introduce
variants to find which factor of GCNs is critical in KGC. Surprisingly, our
experiments demonstrate that randomly breaking adjacency tensors used in GCNs
does not have a significant impact on the performance of GCN-based KGC models.
By further noticing a bijection between adjacency tensors and graph
structures, we conclude that while GCNs improve the performance of KGE models,
the graph structure modeling in GCNs does not account for the performance
gain. The result overturns the consensus that the main advantage of GCNs is
the ability to model graph structures. Besides, we test the effect of the
usage of neighbor information and self-loop information, and transformations
for relations. Finally, we find that so long as a GCN can distinguish entities
with different semantics by its generated entity representations, the
transformations for entity representations effectively improve the performance
of KGE models. Based on the observations, we propose a simple yet effective
framework named LTE-KGE, which equips existing KGE models with linearly
transformed entity representations. Experiments demonstrate that LTE-KGE
models lead to similar performance improvements to KGE models compared with
GCN-based models, while avoiding heavy computational loads in GCN aggregation.
Further, we show that though LTE-KGE models do not explicitly aggregate
information from graph neighborhoods, they behave like a single GCN layer.
These results suggest that existing GCNs are unnecessary for the KGC task, and
we should conduct more ablation studies when designing complicated GCN
architectures for KGC.

##  2\. Preliminaries

###  2.1. Knowledge Graphs (KGs)

Given a set of entities $\mathcal{E}$ and a set of relations $\mathcal{R}$, a
knowledge graph
$\mathcal{K}=\\{(e_{i},r_{j},e_{k})\\}\subset\mathcal{E}\times\mathcal{R}\times\mathcal{E}$
is a set of triplets, where $e_{i}$ and $r_{j}$ are the $i$-th entity and
$j$-th relation, respectively. Usually, we call $e_{i}$ and $e_{k}$ the head
entity and tail entity, and use $h_{i}$ and $t_{k}$ to distinguish them. A
knowledge graph can be uniquely determined by a third-order binary tensor
$\mathcal{X}\in\\{0,1\\}^{|\mathcal{E}|\times|\mathcal{R}|\times|\mathcal{E}|}$,
which is also called the adjacency tensor of $\mathcal{K}$. The $(i,j,k)$
entry $\mathcal{X}_{ijk}=1$ if $(h_{i},r_{j},t_{k})$ is valid or otherwise
$\mathcal{X}_{ijk}=0$.

###  2.2. Knowledge Graph Completion (KGC)

The goal of KGC is to predict valid but unobserved triplets based on known
triplets in $\mathcal{K}$. KGC models define a score function
$s:\mathcal{E}\times\mathcal{R}\times\mathcal{E}\rightarrow\mathbb{R}$ to
associate a score $s(h_{i},r_{j},t_{k})$ with each potential triplet
$(h_{i},r_{j},t_{k})\in\mathcal{E}\times\mathcal{R}\times\mathcal{E}$. The
scores measure the plausibility of triplets. For a query $(h_{i},r_{j},?)$ or
$(?,r_{j},t_{k})$, KGC models first fill the blank with each entity in the
knowledge graphs and then score the resulted triplets. Valid triplets are
expected to have higher scores than invalid triplets.

Knowledge graph embedding (KGE) models are popular KGC models, which associate
each entity $e_{i}\in\mathcal{E}$ (either be head or tail entities) and
relation $r_{j}\in\mathcal{R}$ with an embedding $\textbf{e}_{i}$ and
$\textbf{r}_{j}$ on carefully picked embedding spaces. Then, they directly
define a scoring function to model the interactions among entities and
relations. We review three representative KGE models as follows.

####  2.2.1. TransE (Bordes et al., 2013)

TransE uses the Minkowski distances to define scoring functions on the real
space. Specifically, given the embeddings $\textbf{h},\textbf{r},\textbf{t}$,
the scoring function is

$\displaystyle f(h,r,t)=-\|\textbf{h}+\textbf{r}-\textbf{t}\|_{1/2},$

where $\|\cdot\|_{1/2}$ means that the distance can be $L_{1}$ or $L_{2}$
distance.

####  2.2.2. DistMult (Yang et al., 2015)

DistMult uses the inner product to define scoring functions on the real space.
Specifically, given the embeddings $\textbf{h},\textbf{r},\textbf{t}$, the
scoring function is

$\displaystyle f(h,r,t)=\textbf{h}^{\top}\textbf{R}\textbf{t},$

where R is a diagonal matrix whose diagonal elements are r.

Table 1. The embedding update processes of three popular GCNs in KGC. For a given entity $e$, the set $\mathcal{N}_{in}(e)$ consists of all head entity and relation pairs $(h,r)$ such that $(h,r,e)$ is valid. The set $\mathcal{N}_{out}(e)$ consists of all relation and tail entity pairs $(r,t)$ such that $(e,r,t)$ is valid. W are trainable linear transformations. $\phi_{in}/\phi_{out}$ are direction-dependent composition operators. | Entity Aggregation | Entity Update | Relation
---|---|---|---
RGCN (Schlichtkrull et al., 2018) | $\textbf{m}_{e}^{l+1}=\sum_{(h,r)\in\mathcal{N}_{in}(e)}\textbf{W}_{r}^{l}\textbf{h}^{l}+\sum_{(r,t)\in\mathcal{N}_{out}(e)}\textbf{W}_{r}^{l}\textbf{t}^{l}+\textbf{W}_{0}^{l}\textbf{e}^{l}$ | $\textbf{e}^{l+1}=\sigma(\textbf{m}_{e}^{l+1})$ | $\textbf{r}^{l+1}=\textbf{r}^{l}$
WGCN (Shang et al., 2019) | $\textbf{m}_{e}^{l+1}=\sum_{(h,r)\in\mathcal{N}_{in}(e)}\textbf{W}^{l}(\alpha_{r}^{l}\textbf{h}^{l})+\sum_{(r,t)\in\mathcal{N}_{out}(e)}\textbf{W}^{l}(\alpha_{r}^{l}\textbf{t}^{l})+\textbf{W}_{0}^{l}\textbf{e}^{l}$ | $\textbf{e}^{l+1}=\sigma(\textbf{m}_{e}^{l+1})$ | $\textbf{r}^{l+1}=\textbf{r}^{l}$
CompGCN (Vashishth et al., 2020b) | $\textbf{m}_{e}^{l+1}=\sum_{(h,r)\in\mathcal{N}_{in}(e)}\textbf{W}_{r}^{l}\phi_{in}(\textbf{h}^{l},\textbf{r}^{l})+\sum_{(r,t)\in\mathcal{N}_{out}(e)}\textbf{W}_{r}^{l}\phi_{out}(\textbf{t}^{l},\textbf{r}^{l})+\textbf{W}_{0}^{l}\textbf{e}^{l}$ | $\textbf{e}^{l+1}=\sigma(\textbf{m}_{e}^{l+1})$ | $\textbf{r}^{l+1}=\textbf{W}_{rel}^{l}\textbf{r}^{l}$

####  2.2.3. ConvE (Dettmers et al., 2018)

ConvE uses convolutional neural networks to define scoring functions. The
scoring function is

$\displaystyle
f(h,r,t)=\sigma(\text{vec}(\sigma([\bar{\textbf{r}},\bar{\textbf{h}}]*\omega))W)^{\top}\textbf{t},$

where $\sigma$ denotes an activation function, $*$ denotes 2D convolution,
$\omega$ denotes a filter in convolutional layers, $\bar{\cdot}$ denotes 2D
shaping for real vectors, and $W$ is a trainable weight matrix.

###  2.3. Graph Convolutional Network Based KGC

Many popular GCNs follow an iterative aggregate and update scheme. In each
iteration, node representations are updated using information aggregated from
nodes’ neighborhoods (both nodes and edges). When applied to KGs, GCNs are
modified to model the interactions among entities and relations. As shown in
Figure 1, GCN-based KGC models usually use an encoder-decoder framework
(Schlichtkrull et al., 2018), where GCNs perform as the encoder and KGE models
(e.g., TransE, DistMult, and ConvE) perform as the decoder. First, the encoder
generates representations for entities and relations in a KG. Compared with
directly using trainable vectors in embedding spaces, representations
generated by GCNs are expected to capture more structure information around
entities and relations. Then, the decoder uses the generated representations
to predict values in the adjacency tensors. Since there exists a bijection
between adjacency tensors and graph structures, the prediction can be seen as
a recovery of the original graph structures. When recovering graph structure,
the decoder can predict links missing in the original graph, i.e., complete
the knowledge graph. Note that KGE models can also be interpreted under this
encoder-decoder framework, where the encoder is an identity function from the
embedding space and the decoder is the KGE model itself.

##  3\. Experimental Setup

In this section, we introduce our experimental setups, including models, loss
functions, datasets, and training/evaluation protocols.

###  3.1. Models

To investigate the effect of GCNs (encoders) in KGC, we study three
representative models, including Relational-GCN (RGCN) (Schlichtkrull et al.,
2018), Weighted-GCN (WGCN) (Shang et al., 2019), and CompGCN (Vashishth et
al., 2020b), all of which are specially designed for multi-relational graphs.
Specifically, RGCN extends vanilla GCN with relation-specific linear
transformations, without considering relation representations. WGCN treats the
relation as learnable weights of edges and applies vanilla GCN on the simple
weighted graph. CompGCN jointly embeds both entities and relations in
knowledge graphs and uses composition operators to model the interactions
among entities and relations. The embedding update processes of these three
models are summarized in Table 1. We can see that the embedding update
processes have three main parts: 1) aggregating information from graph
neighborhoods, 2) transformations for aggregated entity representations, and
3) transformations for relation representations.

As to KGE models (decoders), we use three popular models: TransE, DistMult,
and ConvE (T, D, C for short). We choose $L_{1}$ norm for TransE to achieve
its best performance.

###  3.2. Loss Functions

Many existing state-of-the-art GCN-based KGC models (Schlichtkrull et al.,
2018; Shang et al., 2019; Vashishth et al., 2020b) use the following binary
cross entropy (BCE) loss

$\displaystyle L$ $\displaystyle=\frac{1}{|S|}\sum_{(h,r,\cdot)\in
S}\left(\frac{1}{|\mathcal{E}|}\sum_{t\in\mathcal{E}}y_{(h,r,t)}\cdot\log
f(h,r,t)\right.$ (1)
$\displaystyle\left.+(1-y_{(h,r,t)})\cdot\log(1-f(h,r,t))\vphantom{\sum_{t\in\mathcal{E}}}\right),$

where $S$ is the set consisting of all known valid triplets, $y_{(h,r,t)}$ is
the label of the triplet $(h,r,t)$. Label smoothing is used to prevent models
from overfitting. The labels $y_{(h,r,t)}$ are smoothed to be numbers between
$[0,1]$. Using this loss, we regard all the triplets not seen in the training
set as negative samples.

###  3.3. Datasets

We use two popular knowledge graph completion datasets FB15k-237 (FB237) and
WN18RR, which are subsets of FB15k (Bordes et al., 2013) and WN18 (Bordes et
al., 2013), respectively. Since FB15k and WN18 suffer from the test set
leakage problem (Dettmers et al., 2018; Toutanova and Chen, 2015), we do not
include the results on FB15k and WN18 in the experiments. The statistics of
these two datasets are summarized in Appendix A.

###  3.4. Training and Evaluation Protocols

Training. We re-implement RGCN, WGCN, and CompGCN with DGL (Wang et al.,
2019b). As we aim to isolate the effects of GCNs instead of benchmarking the
performance of GCN-based KGC models, we follow the guidelines provided by the
original GCN papers (Schlichtkrull et al., 2018; Shang et al., 2019; Vashishth
et al., 2020b) or official implementations for model selection and do not
spend time in tuning hyper-parameters. Since there is no suggested hyper-
parameters for RGCN on WN18RR in the original papers or implementations, we
omit the corresponding results. Nonetheless, it does not affect our overall
conclusions.  Notably, further tuning hyper-parameters does not affect our
conclusions. First, for original GCN models, since we use their suggested best
hyper-parameters, the performance of re-implemented models is comparable to
the reported performance in Vashishth et al. (2020b) (see Section 4.1).
Second, for model variants, so long as they achieve competitive performance
with the original models, we can make our conclusion. The performance of
current implementations has already met our demands. Further tuning hyper-
parameters for these variants may improve their performance, while it makes no
difference to the conclusion. Besides, the strategy that does not tune hyper-
parameters for model variants is widely used in works revisiting existing
models (Yang and Xu, 2020; Mesquita et al., 2020; Liu et al., 2019). We follow
their settings in our experiments.

Table 2. Comparison of MRR between the state-of-the-art KGE and GCN-based KGC models. *, †, and $\diamond$ indicate that the results are taken from (Ruffinelli et al., 2020), (Zhang et al., 2020), and (Vashishth et al., 2020b), respectively. | FB237 | WN18RR
---|---|---
TransE* | .288 | .202
DistMult* | .347 | .447
ConvE* | .344 | .447
ComplEx* | .351 | .477
ComplEx-N3† | .366 | .489
RGCN+ConvE$\diamond$ | .342 | -
WGCN+ConvE$\diamond$ | .344 | -
CompGCN+ConvE$\diamond$ | .355 | .479

Evaluation. For each triplet $(h,r,t)$ in test sets, we replace either $h$ or
$t$ with candidate entities to create candidate triplets. We then rank the
candidate triplets in descending order by their scores (Bordes et al., 2013).
We use the “Filtered” setting (Bordes et al., 2013) that does not take
existing valid triplets into accounts at ranking. We use Mean Rank (MR), Mean
Reciprocal Rank (MRR), and Hits at N (H@N) as the evaluation metrics. Lower MR
and higher MRR/H@N indicate better performance.

##  4\. Real effect of GCNs in KGC

GCNs can generate expressive node representations, which is supposed to
benefit downstream tasks. However, as shown in Table 2, GCN-based KGC models
do not show a great advantage over state-of-the-art KGE models though
introducing additional computational complexity. For example, the state-of-
the-art GCN model CompGCN (Vashishth et al., 2020b) achieves MRR of 0.355 and
0.479 on FB237 (Dettmers et al., 2018) and WN18RR (Toutanova and Chen, 2015)
respectively, while the KGE model ComplEx+N3 (Lacroix et al., 2018) attains
MRR of 0.366 and 0.489 (Zhang et al., 2020). The results raise a natural
question: ”What is the real effect of GCNs in the KGC task?” To answer the
question, we decompose it into the following two sub-questions.

  1. (1)

Do GCNs really bring performance gain?

  2. (2)

Which factor of GCNs is critical in KGC?

###  4.1. Do GCNs Really Bring Performance Gain?

Some GCN-based KGC works show impressive performance gain (Schlichtkrull et
al., 2018; Shang et al., 2019; Vashishth et al., 2020b), while the baseline
results are taken from the original papers of KGE models. As advanced training
strategies can significantly boost the performance of KGE models (Ruffinelli
et al., 2020) and baseline KGE models do not use these strategies, the benefit
of GCNs may be overestimated. Thus, we conduct experiments to validate whether
GCNs really bring performance gain over KGE models.

Table 3. Comparison of MRR between models without (w/o) and with GCNs. ”O” indicates that the results are taken from their original papers, while ”R” indicates that we reproduce the results using DGL. T: TransE. D: DistMult. C: ConvE. | FB237 | WN18RR
---|---|---
| T | D | C | T | D | C
w/o GCN (O) | .294 | .241 | .325 | - | - | -
RGCN (O) | .281 | .324 | .342 | - | - | -
WGCN (O) | .267 | .324 | .344 | - | - | -
CompGCN (O) | .337 | .338 | .353 | - | - | .479
w/o GCN (R) | .332 | .279 | .319 | .205 | .410 | .462
RGCN (R) | .324 | .332 | .337 | - | - | -
WGCN (R) | .272 | .329 | .340 | .222 | .422 | .462
CompGCN (R) | .335 | .342 | .353 | .206 | .430 | .469

Table 3 show that in most cases, GCNs, especially the state-of-the-art
CompGCN, significantly improve the performance of KGE models. Notably, on
FB237, WGCN+TransE performs worse than TransE in both the original and
reproduced cases. A similar phenomenon can also be observed for
WGCN+DistMult/ConvE on WN18RR. It demonstrates that not all GCNs can improve
the performance of all KGE models. Moreover, the reproduced performance of
DistMult and TransE is significantly better than their reported performance,
showing the influence of different training strategies.

In summary, the answer to the first question is ”Yes”. GCNs do bring
performance gain over KGE models for the KGC task.

Table 4. MRR for GCNs with random adjacency tensors (RAT) and without neighbor information (WNI).  | FB237 | WN18RR
---|---|---
| T | D | C | T | D | C
RGCN | .324 | .332 | .337 | - | - | -
RGCN + RAT | .322 | .331 | .333 | - | - | -
RGCN + WNI | .324 | .332 | .335 | - | - | -
WGCN | .272 | .329 | .340 | .222 | .422 | .462
WGCN + RAT | .325 | .330 | .354 | .213 | .426 | .470
WGCN + WNI | .337 | .334 | .355 | .235 | .425 | .473
CompGCN | .335 | .342 | .353 | .206 | .430 | .469
CompGCN + RAT | .336 | .336 | .351 | .208 | .420 | .467
CompGCN + WNI | .339 | .335 | .352 | .214 | .435 | .465

###  4.2. Which Factor of GCNs is Critical in KGC?

There is a consensus that the performance improvements of GCNs mainly comes
from their ability to model graph structures. However, whether graph structure
modeling of GCNs is critical in KGC is less explored, and which factor of GCNs
is critical in KGC is unclear. Thus, we conduct extensive experiments to test
the effect of graph structures, neighbor information, self-loop information,
and linear transformations for relations.

####  4.2.1. Graph Structures

GCNs are known to be effective in modeling graph structures. Therefore, if we
break graph structures, the performance of GCN-based KGC models is expected to
decrease significantly. Since graph structure information of a knowledge graph
is represented by its adjacency tensors (please refer to Section 2.2 for a
detailed definition), we conduct experiments with randomly broken adjacency
tensors to explore the effect of the graph structures. Specifically, when
building the adjacency tensor for message passing, given a valid triplet
$(h_{i},r_{j},t_{k})$, we replace the tail entity $t_{k}$ with a random entity
in the knowledge graph. Note that we only use the random adjacency tensors in
message passing, while the training/validation/test triplets remain unchanged.

Table 5. MRR results for GCNs without self-loop information (WSI) and random
adjacency tensors (RAT).

| FB237 | WN18RR
---|---|---
| T | D | C | T | D | C
RGCN | .324 | .332 | .337 | - | - | -
RGCN + WSI | .323 | .337 | .339 | - | - | -
RGCN + WSI+RAT | .320 | .317 | .318 | - | - | -
WGCN | .272 | .329 | .340 | .222 | .422 | .462
WGCN + WSI | .263 | .330 | .341 | .181 | .408 | .426
WGCN + WSI + RAT | .322 | .319 | .340 | .168 | .353 | .408
CompGCN | .335 | .342 | .353 | .206 | .430 | .469
CompGCN + WSI | .320 | .338 | .352 | .181 | .408 | .426
CompGCN + WSI + RAT | .317 | .297 | .342 | .168 | .353 | .408

Table 4 shows the results for GCNs with random adjacency tensors (X+RAT).
Surprisingly, randomly breaking the adjacency tensors, i.e., the graph
structures, does not affect the overall performance of GCN-based KGC models on
both datasets. The models with random adjacency tensors attain comparative
performance to their normal adjacency tensor counterparts. For WGCN+TransE,
random graph structures even improve the performance on FB237. The results
demonstrate that, although GCN encoders can improve the performance of KGE
models, graph structure modeling in GCNs is not critical for the performance
improvements.

####  4.2.2. Neighbor Information

To further explore the relationship between graph structure modeling in GCNs
and the performance improvements, we conduct experiments that do not use
neighbor information in the aggregation process. That is to say, the graph
used in GCNs has no edges (relations) between nodes (entities), and the new
representation of an entity is generated only based on the entity’s previous
representation.

Table 4 shows that on both datasets, the models without using neighbor
information (X+WNI) perform competitively with the original models. It
demonstrates that the performance gain does not come from the neighborhood
aggregation.

####  4.2.3. Self-loop Information

To determine whether self-loop information is necessary for the performance
gain, we conduct experiments without self-loop information. That is to say,
the representation of an entity is generated only based on the representations
of its neighborhood entities and relations.

Results on FB237. Table 5 shows the results without self-loop information
(X+WSI). Surprisingly, leaving out the self-loop information does not have a
significant impact on the performance of most models as well. In most cases,
only aggregating the neighbor information achieves comparative results to full
GCN-based KGC models. Further, we randomly break the adjacency tensors while
leaving out self-loop information. Since we only use neighbor information, we
expect the random adjacency tensors to reduce the performance significantly.
However, as shown in Table 5 (X+WSI+RAT), the performance is only slightly
affected for most of the decoders. That is, only aggregating randomly
generated neighbor information achieve comparative results to full GCN-based
KGC models.

(a) WGCN+X

(b) CompGCN+X

Figure 2. MRR results for no self-loop information and random sampled neighbor
entities on FB237, where the dash lines indicate performance without GCNs.

(a) WGCN+X

(b) CompGCN+X

Figure 3. MRR for random sampled neighbors on FB237, where the dash lines
indicate performance without GCNs.

Until now, we have known that the following operations do not have a
significant effect on the performance of GCN-based KGC models on FB237: 1)
only using self-loop information; 2) only using neighbor information; 3) only
using randomly generated neighbor information. The three cases have one common
property: they can distinguish entities having different semantics with high
confidence. Specifically, if we only use self-loop information, the
representation of each entity is independent and thus can be distinguished. If
we only use neighbor information, two entities will have similar
representations only if they have similar neighbor representations, which is
consistent with an assumption of KGC: entities with similar neighbors have
similar semantics. Therefore, we can distinguish entities with different
semantics. When randomly sampling neighbor entities from all the entities, we
assign different neighbors for different entities with a high possibility, and
thus we can distinguish different entities by the aggregated entity
representations.

To find out whether the above property is necessary for the performance gain,
we conduct experiments in which we do not use self-loop information and
meanwhile randomly sample neighbors in a given entity set. The number of
neighbor entities of each entity remains the same as their original values. If
the set size is small, different entities are more likely to have similar
neighborhoods and thus have similar representations, which makes them hard to
be distinguished. Hence, we expect the performance to decrease when the set
size becomes smaller. Figure 2 shows that, as the sample set sizes decrease,
the MRR results decrease rapidly and become worse than models without GCNs,
which meets our expectations. We also conduct experiments using self-loop
information and randomly sampled neighbors. Figure 3 shows that the
performance is relatively stable when the set sizes vary. It is expectable
since the self-loop information itself can uniquely determine an entity, no
matter what the neighbor information is.

Results on WN18RR. Compared with the results on FB15k-237, Table 5 shows that
only using neighbor information (WSI/WSI+RAT) leads to lower performance than
full GCN-based models on WN18RR. It is reasonable since the average numbers of
neighbor entities in WN18RR and FB15k-237 are 2.1 and 18.7, respectively. It
is more challenging to distinguish entities with different semantics based on
fewer neighbor entities. Therefore, the results are consistent with the
analyses for FB237.

In summary, GCNs improve the performance of KGE models if the aggregation
process can well distinguish entities with different semantics.

Table 6. Comparison between CompGCN with and without (w/o) linear transformations for relations (LTR). |  | TransE | DistMult | ConvE
---|---|---|---|---
FB237 | with LTR | 0.335 | 0.342 | 0.353
w/o LTR | 0.336 | 0.343 | 0.352
WN18RR | with LTR | 0.206 | 0.430 | 0.469
w/o LTR | 0.190 | 0.433 | 0.468

####  4.2.4. Linear Transformations for Relations.

Different from RGCN and WGCN, CompGCN applies linear transformations for
relation embeddings. We conduct ablation experiments to explore the effect of
the transformations. Table 6 shows that removing the linear transformations
for relations does not significantly affect the performance except for
CompGCN+TransE on WN18RR. Note that TransE is sensitive to hyper-parameters,
and we do not find the best hyper-parameters by grid search. The performance
of CompGCN+TransE may be underestimated. Thus, we can conclude that linear
transformations for relations are not critical for GCN-based KGC models.
Recall that the embedding update process of a GCN-based KGC model has three
main parts (Section 3.1). We have shown that two of them—the aggregation based
on graph structures and transformations for relations—are not critical for
GCN-based KGC models. Thus, the transformations for aggregated entity
representations are critical for the performance improvements.

Based on the above results, we conclude that: so long as a GCN can well
distinguish entities with different semantics by its generated entity
representations, the transformations for entity representations can
effectively improve the performance of KGE models.

##  5\. A simple yet effective framework

Based on the observations in the last section, we propose a simple yet
effective KGC framework, namely LTE-KGE, which uses linearly transformed
entity representations to achieve comparative performance to GCN-based KGC
models.  It is worth noting that we do not aim to propose a new state-of-the-
art KGC model. Instead, we aim to demonstrate that simpler models can achieve
similar performance to state-of-the-art GCN-based models, concluding that
existing complicated GCNs may be unnecessary for KGC.

###  5.1. Model Details for LTE-KGE

Suppose that $f(\textbf{h},\textbf{r},\textbf{t})$ is a scoring function for
the triplet $(h,r,t)$, which corresponds to an existing KGE model. Motivated
by the previous experimental results, we propose a framework named LTE-KGE,
which applies linear transformations to entity representations. Formally, the
proposed framework is

(2) $\displaystyle
f(g_{h}(W_{h}\textbf{h}),\textbf{r},g_{t}(W_{t}\textbf{t}))),$

where $W_{h}$ and $W_{t}$ are linear transformations with trainable weights.
We also introduce optional operations $g_{h}$ and $g_{t}$, which can be
compositions of functions from the function set {the identity function, non-
linear activation functions, batch normalization, dropout}. These operations
correspond to possible non-linear transformations in GCN-based models. Note
that: a) the linear transformations $W_{h}$ and $W_{t}$ can share the same
parameters depending on the experimental results; b) $g_{h}$ and $g_{t}$ can
be compositions of different functions depending on the experimental results;
c) as each entity has its own representations, LTE-KGE can distinguish
entities with different semantics; d) when $W_{h},W_{t}$ are identity matrices
and $g_{h},g_{t}$ are identity functions, LTE-KGE models recover KGE models.

Compared with GCNs only using self-loop information, LTE-KGE is more flexible
to incorporate different transformations for head and tail entities. Compared
with TransR (Lin et al., 2015) that applies relation-specific projections to
entity embeddings, LTE-KGE is more memory-efficient and flexible to
incorporate non-linear operations.

###  5.2. Experimental Results

We conduct experiments for DistMult, TransE, and ConvE. Specifically, $W_{h}$
and $W_{t}$ are the same, while $g_{h}$ and $g_{t}$ are a composition of batch
normalization and dropout for DistMult/ConvE, and an identity function for
TransE.

Table 7. Comparison between LTE-KGE models and CompGCN (Vashishth et al., 2020b). The symbol † indicates that the results are reproduced with DGL. The reproduced performance of CompGCN is similar to the reported performance in their original paper. | FB237 | WN18RR
---|---|---
| MRR | MR | H@1 | H@3 | H@10 | MRR | MR | H@1 | H@3 | H@10
RotatE | .338 | 177 | .241 | .375 | .533 | .476 | 3340 | .428 | .492 | .571
TuckER | .358 | - | .266 | .394 | .544 | .470 | - | .433 | .482 | .526
TransE† | .332 | 182 | .240 | .368 | .516 | .205 | 3431 | .022 | .347 | .519
DistMult† | .279 | 392 | .202 | .306 | .433 | .410 | 7970 | .389 | .420 | .450
ConvE† | .319 | 276 | .232 | .351 | .492 | .462 | 4888 | .431 | .476 | .525
CompGCN + TransE† | .335 | 205 | .247 | .369 | .511 | .206 | 3182 | .064 | .281 | .502
CompGCN + DistMult† | .342 | 200 | .252 | .372 | .520 | .430 | 4559 | .395 | .439 | .513
CompGCN + ConvE† | .353 | 221 | .261 | .388 | .536 | .469 | 3065 | .433 | .480 | .543
LTE-TransE | .334 | 182 | .241 | .370 | .519 | .211 | 3290 | .022 | .362 | .521
LTE-DistMult | .335 | 238 | .246 | .367 | .517 | .437 | 4485 | .403 | .447 | .517
LTE-ConvE | .355 | 249 | .264 | .389 | .535 | .472 | 3434 | .437 | .485 | .544

Table 7 shows the comparison results.  Note that the performance of our re-
implemented CompGCN is comparable to the reported performance in (Vashishth et
al., 2020b). Therefore, the comparison between LTE-KGE and GCNs is fair.
Overall, LTE-KGE significantly improves the performance of DistMult and ConvE.
Although LTE-KGE does not explicitly model local graph structures like GCNs,
it performs comparably to the GCN-based KGC models and sometimes even performs
better.  We also use RotatE (Sun et al., 2019) and TuckER (Balazevic et al.,
2019) as baselines. The results show that GCN-based models do not consistently
show great advantages over these KGE models. One may argue that we can also
build LTE-KGE over RotatE/TuckER to achieve better performance. However, as
noted before, we propose LTE-KGE to challenge the use of GCNs instead of
achieving state-of-the-art performance. As popular GCN-based models do not use
RotatE/TuckER as decoders, we do not build LTE-KGE on top of them either.

We also evaluate the efficiency of different models. We train and test the
models on the same machine. The batch size, the number of training epochs, and
the number of test samples are the same. The number of GCN layers is 1. Figure
4 shows the training and test time usage of different models. The results
demonstrate that adding GCN encoders, especially RGCN, suffers from high
training and test time usage. On the contrary, LTE-KGE models are as efficient
as models without GCNs. Therefore, LTE-KGE models have the benefit of GCN
models and avoid their heavy computational load.

(a) Training Time

(b) Test Time

Figure 4. Comparison of training/test time. The time usage of models without
GCNs is scaled to 1.

###  5.3. Relationship between LTE-KGE and GCNs

To understand why LTE-KGE models perform similarly to GCN-based KGC models, we
show that LTE-KGE behaves like a GCN-based model with a single GCN layer being
an encoder, while it does not aggregate information from neighborhoods
explicitly.

For simplicity, we only consider positive triplets and the loss function
without label smoothing. Given an entity $h$, we consider all its known
neighbors $(r_{i},t_{i})$ such that $(h,r_{i},t_{i})$ are known valid
triplets. Further, we assume that the formulation of LTE-KGE is
$f(W\textbf{h},\textbf{r},W\textbf{t})$. Then, for a given entity $h$, our aim
is to minimize the loss function

(3) $\displaystyle\sum_{r\in R_{h}}\sum_{t:(h,r,t)\in S}\log
f(W\textbf{h},\textbf{r},W\textbf{t}),$

where $R_{h}$ is the set consisting of all relations connected with the entity
$h$, and $f$ is the scoring function of a KGE model. Note that we omit the
constants involved in the formulation (3).

When optimizing the objective, we usually use the gradient descent method to
minimize the loss function (3). The gradient with respect to h is given as
follows

(4) $\displaystyle\sum_{r\in R_{h}}\sum_{t:(h,r,t)\in
S}\frac{1}{f(W\textbf{h},\textbf{r},W\textbf{t})}\frac{\partial
f}{\partial\textbf{h}}(W\textbf{h},\textbf{r},W\textbf{t}).$

In our experiments, the scoring function $f$ can be TransE, DistMult, or
ConvE, of which the definition are described in Section 2.2. In the following,
we calculate the gradients for these three models.

####  5.3.1. Gradients for LTE-TransE

The gradient for LTE-TransE is

$\displaystyle\sum_{r\in R_{h}}\sum_{t:(h,r,t)\in
S}\frac{1}{\|W\textbf{h}+\textbf{r}-W\textbf{t}\|_{1/2}}\frac{\partial}{\partial\textbf{h}}\|W\textbf{h}+\textbf{r}-W\textbf{t}\|_{1/2}.$

When the distance is $L_{1}$ norm, the above formulation is

(5) $\displaystyle\sum_{r\in R_{h}}\sum_{t:(h,r,t)\in
S}W^{\top}\frac{I(W\textbf{h},W\textbf{t}-\textbf{r})}{\|W\textbf{h}+\textbf{r}-W\textbf{t}\|_{1}},$

where
$I(\textbf{x},\textbf{y}):\mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$
is a function satisfying $[I(\textbf{x},\textbf{y})]_{i}$ is $-1$ if
$x_{i}<y_{i}$ or otherwise $1$. Note that the $L_{1}$ norm is non-
differentiable at $0$. For implementation and notation convenience, we choose
1 as the gradients at $0$, which belongs to the subderivative of the $L_{1}$
norm.

When the distance is $L_{2}$ norm, the gradient is

(6) $\displaystyle\sum_{r\in R_{h}}\sum_{t:(h,r,t)\in
S}-\frac{W^{\top}}{\|W\textbf{h}+\textbf{r}-W\textbf{t}\|_{2}^{2}}W\textbf{t}+\frac{W^{\top}(\textbf{r}+W\textbf{h})}{\|W\textbf{h}+\textbf{r}-W\textbf{t}\|_{2}^{2}}.$

####  5.3.2. Gradients for LTE-DistMult

The gradient is

$\displaystyle\sum_{r\in R_{h}}\sum_{t:(h,r,t)\in
S}\frac{1}{((W\textbf{h})^{\top}\textbf{R}(W\textbf{t}))}\frac{\partial}{\partial\textbf{h}}((W\textbf{h})^{\top}\textbf{R}(W\textbf{t}))$
(7) $\displaystyle=$ $\displaystyle\sum_{r\in R_{h}}\sum_{t:(h,r,t)\in
S}\frac{W^{\top}\textbf{R}}{((W\textbf{h})^{\top}\textbf{R}(W\textbf{t}))}W\textbf{t}$

####  5.3.3. Gradients for LTE-ConvE

The gradient for LTE-ConvE is

$\displaystyle\sum_{r\in R_{h}}\sum_{t:(h,r,t)\in
S}\frac{1}{g(\textbf{h},\textbf{r},\textbf{t})}\frac{\partial}{\partial\textbf{h}}g(\textbf{h},\textbf{r},\textbf{t}),$

where
$g(\textbf{h},\textbf{r},\textbf{t})=\sigma(\text{vec}(\sigma([\bar{\textbf{r}},\overline{W\textbf{h}}]*\omega))W^{\prime})^{\top}(W\textbf{t})$
and $W^{\prime}$ is the weight matrix in ConvE. Then we have that

$\displaystyle\frac{\partial}{\partial\textbf{h}}g(\textbf{h},\textbf{r},\textbf{t})=\frac{\partial}{\partial\textbf{h}}\sigma(\text{vec}(\sigma([\bar{\textbf{r}},\overline{W\textbf{h}}]*\omega))W^{\prime})^{\top}(W\textbf{t}),$

Let
$\lambda(\textbf{h},\textbf{r},\textbf{t})=\frac{1}{g(\textbf{h},\textbf{r},\textbf{t})}\frac{\partial}{\partial\textbf{h}}\sigma(\text{vec}(\sigma([\bar{\textbf{r}},\overline{W\textbf{h}}]*\omega))W^{\prime})^{\top}$.
Then the gradient is

(8) $\displaystyle\sum\nolimits_{r\in R_{h}}\sum\nolimits_{t:(h,r,t)\in
S}\lambda(\textbf{h},\textbf{r},\textbf{t})W\textbf{t}.$

In summary, the gradients of the $L_{2}$-version of LTE-TransE (6), LTE-
DistMult (5.3.2), and LTE-ConvE (8) can be unified as

(9) $\displaystyle\sum_{r\in R_{h}}\sum_{t:(h,r,t)\in
S}a(\textbf{h},\textbf{r},\textbf{t})W\textbf{t}+b(\textbf{h},\textbf{r},\textbf{t}),$

where $a(\textbf{h},\textbf{r},\textbf{t})$ and
$b(\textbf{h},\textbf{r},\textbf{t})$ are two scalar-valued functions. We can
regard the formulation (9) as an information aggregation from neighbor
entities and relations. If we use gradient descent to minimize the loss
function, then the optimization process is equivalent to a 1-layer GCN
iteration, where the linear transformation $W$ corresponds to the weight
matrices in GCN aggregation. Although the gradient of the $L_{1}$-version of
LTE-TransE (5) does not satisfy the unified formulation (9), the optimization
process also corresponds to an information aggregation based on graph
structures. In summary, the combination of a KGE model and gradient descent
already behaves like GCN aggregations. Thus, additional explicit aggregations
are unnecessary, and it is reasonable that LTE-KGE achieves similar
performance to GCN-based KGC models.

It is worth noting that Yu et al. (2021) also use gradient descent to discuss
the relationship between KGE and GCNs. However, their main aim is to unify the
GCNs by a gradient descent framework and design new aggregation schemes, while
our aim is to explain the equivalence between KGE and GCN-based KGC models.

##  6\. Related Work

Our work mainly focuses on GCN-based knowledge graph completion (KGC), which
is relevant to the Web research community in two aspects. First, knowledge
graphs (KGs) play an important role in many applications on the Web, such as
search and recommendations. Since the completeness of KGs significantly
influence their applicability and manually completing KGs is expensive, how to
complete KGs automatically is a fundamental research problem in the community.
Second, GCNs are popular algorithms to deal with many Web-related problems,
including knowledge graph completion. A better understanding of the GCNs’
effects in KGC can give us inspiration and guidance to build new KGC models.
Therefore, as a systematic analysis of recently proposed GCN-based KGC models,
our work is relevant to the community.

Moreover, our work is related to knowledge graph embeddings, GCNs in KGC, and
other work reviewing KGC models.

Knowledge Graph Embeddings. Knowledge graph embedding models usually use
simple architectures to measure the plausibility of triplets in knowledge
graphs. For example, TransE (Bordes et al., 2013), TransH (Wang et al., 2014),
TransR (Lin et al., 2015), and RotatE (Sun et al., 2019) define distance-based
scoring functions in either real or complex spaces. RESCAL (Nickel et al.,
2011), DistMult (Yang et al., 2015), ComplEx (Trouillon et al., 2016), ANALOGY
(Liu et al., 2017), TuckER (Balazevic et al., 2019), and LowFER (Amin et al.,
2020) use tensor factorization to model the knowledge graph completion
process. Their scoring functions usually consist of inner products between
real or complex vectors. Some works also turn to neural networks to generate
knowledge graph embeddings. For example, ConvKB (Nguyen et al., 2018), ConvE
(Dettmers et al., 2018), and InteractE (Vashishth et al., 2020a) use
convolutional neural networks to generate more expressive entity and relation
embeddings. CapsE (Nguyen et al., 2019) uses the capsule network to model the
interaction in knowledge graphs.

GCNs in Knowledge Graph Completion. Early GCNs are usually designed for
homogeneous graphs (Kipf and Welling, 2017; Hamilton et al., 2017), in which
nodes and edges have only one type. However, directly using these GCNs in KGC
usually leads to poor performance, since knowledge graphs have different types
of nodes (entities) and edges (relations). To address the problem, RGCN
(Schlichtkrull et al., 2018) extends the classical GCN and proposes to apply
relation-specific transformations in GCN’s aggregation. To alleviate the over-
parameterization problem caused by relation-specific weight matrices, they
also use basis and block-diagonal decomposition. Shang et al. (2019) propose a
weighted graph convolutional network, which uses learnable relation-specific
scalar weights during GCN aggregation. However, these models do not explicitly
learn relation embeddings, which are important for knowledge graph completion.
To tackle this problem, many works, such as VR-GCN (Ye et al., 2019), CompGCN
(Vashishth et al., 2020b), and KE-GCN (Yu et al., 2021), propose extensions of
GCNs to embed both entities and relations in knowledge graphs. Moreover,
CompGCN and KE-GCN combine the power of GCNs and the strength of knowledge
graph completion models to further exploit the interactions among entities and
relations.

Reviews for KGC models. Reviews for KGC models are constantly emerging in
recent years, which help us to understand KGC models better. For example, Wang
et al. (2017) and Ji et al. (2021) comprehensively review the architectures
and categories of existing KGC models. Ruffinelli et al. (2020) conduct
extensive experiments to demonstrate that early KGC models with advanced
training strategies can achieve good performance. Accordingly, they suggest
that many advanced architectures and techniques should be revisited to
reassess their individual beneﬁts. Sun et al. (2020) find that some works use
unfair evaluation protocols, which may lead to inflating performance. However,
to our best knowledge, there exists no work that provides a comprehensive
analysis for GCN-based KGC models, which is our main aim.

##  7\. Conclusion

In this paper, we conduct extensive experiments to find the real critical part
behind the complicated architectures of GCN-based KGC models. Surprisingly, we
observe from experiments that the graph structure modeling is unimportant for
GCN-based KGC models. Instead, the ability to distinguish different entities
and the transformations for entity embeddings account for the performance
improvements. Based on this observation, we propose LTE-KGE that enhances KGE
models with linearly transformed entity embeddings, achieving comparable
performance to GCN-based KGC models. Thus, we suggest that novel GCN-based KGC
models should count on more ablation studies to validate their effectiveness.

## Acknowledgments

We would like to thank all the anonymous reviewers for their insightful
comments. This work was supported in part by National Science Foundations of
China grants 61822604, U19B2026, 61836006, and 62021001, and the Fundamental
Research Funds for the Central Universities grant WK3490000004.

## References

  * (1)
  * Amin et al. (2020) Saadullah Amin, Stalin Varanasi, Katherine Ann Dunfield, and Günter Neumann. 2020.  LowFER: Low-rank Bilinear Pooling for Link Prediction. In _Proceedings of the 37th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 119)_. PMLR, 257–268.
  * Balazevic et al. (2019) Ivana Balazevic, Carl Allen, and Timothy Hospedales. 2019\.  TuckER: Tensor Factorization for Knowledge Graph Completion. 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)_. Association for Computational Linguistics, Hong Kong, China, 5185–5194.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013\.  Translating Embeddings for Modeling Multi-relational Data. In _Advances in Neural Information Processing Systems_ , Vol. 26.
  * Cheng et al. (2020) Dawei Cheng, Fangzhou Yang, Xiaoyang Wang, Ying Zhang, and Liqing Zhang. 2020.  Knowledge Graph-Based Event Embedding Framework for Financial Quantitative Investments. In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Virtual Event, China) _(SIGIR ’20)_. Association for Computing Machinery, New York, NY, USA, 2221–2230.
  * Dettmers et al. (2018) Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018.  Convolutional 2D Knowledge Graph Embeddings.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 32, 1 (Apr. 2018).
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive Representation Learning on Large Graphs. In _Advances in Neural Information Processing Systems_ , Vol. 30. Curran Associates, Inc.
  * Ji et al. (2021) Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and Philip S. Yu. 2021.  A Survey on Knowledge Graphs: Representation, Acquisition, and Applications.  _IEEE Transactions on Neural Networks and Learning Systems_ (2021), 1–21.
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling. 2017.  Semi-Supervised Classification with Graph Convolutional Networks. In _International Conference on Learning Representations_.
  * Lacroix et al. (2018) Timothee Lacroix, Nicolas Usunier, and Guillaume Obozinski. 2018\.  Canonical Tensor Decomposition for Knowledge Base Completion. In _Proceedings of the 35th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 80)_. PMLR, 2863–2872.  https://proceedings.mlr.press/v80/lacroix18a.html
  * 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 Twenty-Ninth AAAI Conference on Artificial Intelligence_ (Austin, Texas) _(AAAI’15)_. AAAI Press, 2181–2187.
  * Liu et al. (2017) Hanxiao Liu, Yuexin Wu, and Yiming Yang. 2017.  Analogical Inference for Multi-relational Embeddings. In _Proceedings of the 34th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 70)_ , Doina Precup and Yee Whye Teh (Eds.). PMLR, 2168–2178.
  * Liu et al. (2020a) Jiaying Liu, Jing Ren, Wenqing Zheng, Lianhua Chi, Ivan Lee, and Feng Xia. 2020a.  Web of Scholars: A Scholar Knowledge Graph. In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Virtual Event, China) _(SIGIR ’20)_. Association for Computing Machinery, New York, NY, USA, 2153–2156.  https://doi.org/10.1145/3397271.3401405
  * Liu et al. (2020b) Weijie Liu, Peng Zhou, Zhe Zhao, Zhiruo Wang, Qi Ju, Haotang Deng, and Ping Wang. 2020b.  K-BERT: Enabling Language Representation with Knowledge Graph.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 34, 03 (Apr. 2020), 2901–2908.  https://doi.org/10.1609/aaai.v34i03.5681
  * Liu et al. (2019) Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. 2019.  Rethinking the Value of Network Pruning. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=rJlnB3C5Ym
  * Luo et al. (2021) Xusheng Luo, Le Bo, Jinhang Wu, Lin Li, Zhiy Luo, Yonghua Yang, and Keping Yang. 2021\.  AliCoCo2: Commonsense Knowledge Extraction, Representation and Application in E-Commerce. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ (Virtual Event, Singapore) _(KDD ’21)_. Association for Computing Machinery, New York, NY, USA, 3385–3393.  https://doi.org/10.1145/3447548.3467203
  * Luo et al. (2020) Xusheng Luo, Luxin Liu, Yonghua Yang, Le Bo, Yuanpeng Cao, Jinghang Wu, Qiang Li, Keping Yang, and Kenny Q. Zhu. 2020.  AliCoCo: Alibaba E-Commerce Cognitive Concept Net. In _Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data_ (Portland, OR, USA) _(SIGMOD ’20)_. Association for Computing Machinery, New York, NY, USA, 313–327.  https://doi.org/10.1145/3318464.3386132
  * Mahdisoltani et al. (2015) Farzaneh Mahdisoltani, Joanna Biega, and Fabian M. Suchanek. 2015\.  YAGO3: A Knowledge Base from Multilingual Wikipedias. In _Seventh Biennial Conference on Innovative Data Systems Research_.
  * Mesquita et al. (2020) Diego Mesquita, Amauri Souza, and Samuel Kaski. 2020\.  Rethinking pooling in graph neural networks. In _Advances in Neural Information Processing Systems_ , Vol. 33. Curran Associates, Inc., 2220–2231.
  * 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_. 4710–4723.  https://doi.org/10.18653/v1/P19-1466
  * Nguyen et al. (2018) Dai Quoc Nguyen, Tu Dinh Nguyen, Dat Quoc Nguyen, and Dinh Phung. 2018.  A Novel Embedding Model for Knowledge Base Completion Based on Convolutional Neural Network. In _NAACL_.
  * Nguyen et al. (2019) Dai Quoc Nguyen, Thanh Vu, Tu Dinh Nguyen, Dat Quoc Nguyen, and Dinh Phung. 2019.  A Capsule Network-based Embedding Model for Knowledge Graph Completion and Search Personalization. In _NAACL_.
  * Nickel et al. (2011) Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. 2011\.  A Three-way Model for Collective Learning on Multi-relational Data. In _Proceedings of the 28th International Conference on Machine Learning_ , Vol. 11. PMLR, 809–816.
  * Ruffinelli et al. (2020) Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. 2020\.  You CAN Teach an Old Dog New Tricks! On Training Knowledge Graph Embeddings. In _International Conference on Learning Representations_.
  * Schlichtkrull et al. (2018) Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2018.  Modeling Relational Data with Graph Convolutional Networks. In _The Semantic Web_. Springer International Publishing, Cham, 593–607.
  * Shang et al. (2019) Chao Shang, Yun Tang, Jing Huang, Jinbo Bi, Xiaodong He, and Bowen Zhou. 2019\.  End-to-End Structure-Aware Convolutional Networks for Knowledge Base Completion. In _The Thirty-Third AAAI Conference on Artificial Intelligence_. AAAI Press, 3060–3067.
  * Sun et al. (2019) Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019\.  RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space. In _International Conference on Learning Representations_.
  * Sun et al. (2020) Zhiqing Sun, Shikhar Vashishth, Soumya Sanyal, Partha Talukdar, and Yiming Yang. 2020\.  A Re-evaluation of Knowledge Graph Completion Methods. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics, Online, 5516–5522.
  * Toutanova and Chen (2015) Kristina Toutanova and Danqi Chen. 2015.  Observed versus latent features for knowledge base and text inference. In _Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality_. Association for Computational Linguistics, Beijing, China, 57–66.
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Eric Gaussier, and Guillaume Bouchard. 2016.  Complex Embeddings for Simple Link Prediction. In _Proceedings of The 33rd International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 48)_. PMLR, New York, New York, USA, 2071–2080.
  * Vashishth et al. (2020a) Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, Nilesh Agrawal, and Partha Talukdar. 2020a.  InteractE: Improving Convolution-based Knowledge Graph Embeddings by Increasing Feature Interactions. In _Proceedings of the 34th AAAI Conference on Artificial Intelligence_. 3009–3016.
  * Vashishth et al. (2020b) Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. 2020b.  Composition-based Multi-Relational Graph Convolutional Networks. In _International Conference on Learning Representations_.
  * Wang et al. (2019b) Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. 2019b.  Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks.  (2019).
  * Wang et al. (2017) Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. 2017\.  Knowledge Graph Embedding: A Survey of Approaches and Applications.  _IEEE Transactions on Knowledge and Data Engineering_ 29, 12 (2017), 2724–2743.
  * Wang et al. (2019a) Xiang Wang, Xiangnan He, Yixin Cao, Meng Liu, and Tat-Seng Chua. 2019a.  KGAT: Knowledge Graph Attention Network for Recommendation. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD ’19)_. Association for Computing Machinery, 950–958.
  * Wang et al. (2014) Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014\.  Knowledge Graph Embedding by Translating on Hyperplanes.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 28, 1 (Jun. 2014).
  * Yang et al. (2015) Bishan Yang, Scott Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015.  Embedding Entities and Relations for Learning and Inference in Knowledge Bases. In _International Conference on Learning Representations_.
  * Yang and Xu (2020) Yuzhe Yang and Zhi Xu. 2020\.  Rethinking the Value of Labels for Improving Class-Imbalanced Learning. In _Advances in Neural Information Processing Systems_ , Vol. 33. Curran Associates, Inc., 19290–19301.
  * Ye et al. (2019) Rui Ye, Xin Li, Yujie Fang, Hongyu Zang, and Mingzhong Wang. 2019.  A Vectorized Relational Graph Convolutional Network for Multi-Relational Network Alignment. In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_. International Joint Conferences on Artificial Intelligence Organization, 4135–4141.
  * Yu et al. (2021) Donghan Yu, Yiming Yang, Ruohong Zhang, and Yuexin Wu. 2021\.  Knowledge Embedding Based Graph Convolutional Network. In _Proceedings of the Web Conference 2021_ (Ljubljana, Slovenia) _(WWW ’21)_. Association for Computing Machinery, New York, NY, USA, 1619–1628.
  * Zhang et al. (2020) Zhanqiu Zhang, Jianyu Cai, and Jie Wang. 2020.  Duality-Induced Regularizer for Tensor Factorization Based Knowledge Graph Completion. In _Advances in Neural Information Processing Systems_ , Vol. 33. Curran Associates, Inc., 21604–21615.
  * Zhang et al. (2021) Zhanqiu Zhang, Jie Wang, Chen Jiajun, Ji Shuiwang, and Wu Feng. 2021.  ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs. In _Advances in Neural Information Processing Systems_.

##  Appendix A Dataset Statistics

Besides FB15K-237 (FB237) and WN18RR used in the main text, we also include
the results on a larger dataset YAGO3-10 (Mahdisoltani et al., 2015) in the
Appendix D. The statistics of these three datasets are summarized in Table 8.

Table 8. Statistics of the benchmark datasets. | FB237 | WN18RR | YAGO3-10
---|---|---|---
#Entity | 14,541 | 40,943 | 123,182
#Relation | 237 | 11 | 37
#Train | 272,115 | 86,835 | 1,079,040
#Valid | 17,535 | 3,034 | 5,000
#Test | 20,466 | 3,134 | 5,000

##  Appendix B Evaluation Metrics

We use the mean reciprocal rank and Hits@N as metrics in the experiments.
Their definitions are as follows.

The mean reciprocal rank is the average of the reciprocal ranks of results for
a set of queries Q:

$\displaystyle\text{MRR}=\frac{1}{|Q|}\sum_{i=1}^{|Q|}\frac{1}{\text{rank}_{i}}.$

The Hits@N is the ratio of ranks that no more than $N$:

$\displaystyle\text{Hits@N}=\frac{1}{|Q|}\sum_{i=1}^{|Q|}\mathds{1}_{x\leq
N}(\text{rank}_{i}),$

where $\mathds{1}_{x\leq N}(\text{rank}_{i})=1$ if $\text{rank}_{i}\leq N$ or
otherwise $0$.

(a) WGCN+X

(b) CompGCN+X

Figure 5. MRR for different numbers of GCN layers on FB237 We use the models
WGCN and CompGCN.

##  Appendix C Number of GCN Layers

Many existing GCN-based knowledge graph completion models use either 1 or 2
GCN layers to achieve their best performance. To explore the effect of
different numbers of GCN layers, we train WGCN and CompGCN with 1, 2, and 3
GCN layers on FB237. Figure 5 shows that in many cases, more GCN layers do not
consistently improve the performance. Sometimes the performance even decreases
as the number of GCN layers increases. Since adding more GCN layers captures
more global graph structures, the results that only using a single GCN layer
is enough to achieve satisfying performance also suggest that graph structure
modeling may be unimportant for GCN-based KGC models.

Table 9. MRR results on the YAGO3-10 dataset. | ConvE
---|---
CompGCN | .348
CompGCN+RAT | .337
CompGCN+WNI | .358
CompGCN+WSI | .262
CompGCN+WSI+RAT | .186
LTE-ConvE | .362

##  Appendix D Results on YAGO3-10

To validate our conclusions on larger datasets, we conduct experiments for the
state-of-the-art CompGCN on YAGO3-10, which consists of 123k entities, 37
relations, and 1079k training triplets. The MRR results are shown in Table 9.
Note that: a) we cannot find the best hyper-parameters in the paper or
official implementation of CompGCN for YAGO3-10; b) tuning models on such a
large dataset is expensive; c) our aim is not to provide a benchmark for
existing models. Thus, we did not spend time tuning hyper-parameters, and
CompGCN may not achieve its best performance. Nonetheless, we can make helpful
conclusions based on the relative performance of different model variants.
Table 9 demonstrates that randomly breaking adjacency matrices (RAT) and only
using self-loop information (WNI) do not significantly affect the performance
of GCN-based models. Compared with FB15k-237, only using neighbor information
(WSI/WSI+RAT) leads to lower performance than full CompGCN on YAGO3-10. It is
because the average numbers of neighbor entities in YAGO3-10 and FB15k-237 are
8.8 and 18.7, respectively. It is more challenging to distinguish entities
with different semantics based on fewer neighbor entities. The results are
consistent with the analyses in Section 4.