# Reachable Set Characterization of Open Quantum System by Quantum Speed Limit

Kohei Kobayashi  Quantum Computing Center, Keio University, Hiyoshi 3-14-1,
Kohoku, Yokohama, 223-8522, Japan

###### Abstract

In recent years, Arenz et al. proposed the idea of reachable set
characterization based on the quantum speed limit (QSL); that is, the
reachable set of the target unitary gate in a closed qubit system can be
characterized by considering the QSL as the necessary condition that the
control setup must satisfy in order to achieve the goal. Inspired by this
idea, in this paper we characterize a general Markovian open quantum system
based on the QSL derived in Kohei2 . Note that this bound is not only
explicitly computable with respect to system parameters, but also tighter than
the other bounds. Some examples for demonstrating this analysis will be given.

##  I Introduction

Quantum information technologies, e.g., quantum computing, communication,
teleportation, and metrology, is receiving a lot of attention in recent years,
due to its possibility to outperform classical information processing. These
technologies are described by a sequence of qubits for an information
resource. Therefore a technique of quantum control which efficiently and
accurately prepare the desired quantum states plays an important role.
However, in the practical situation, there is an undesirable environment
effect such as decoherence which destroys the coherence properties of quantum
systems, resulting that the actual control performance severely degrades.
Thus, it is important to quantitatively evaluate and characterize a reachable
set of the controlled state, i.e, the set of all the final states reachable
starting from the initial state, from the perspective of quantum engineering.
In general, the reachable set is described as a time-dependent function, e.g.,
Lie-semigroup structures Dirr , C-numerical range Dirr2 , spectrum of the
density matrix Yuan , and so on. In order to study this problem, the quantum
speed limit (QSL) can be used as a useful tool.
The QSL is defined as a fundamental lower bound on the evolution time of a
quantum state from an initial state to a final state. The study of the QSL
started from closed systems; Mandelstam and Tamm presented a first QSL between
orthogonal states MT , which is bounded by the variance of the system energy.
Later decades, Margolus and Levitin provided another QSL depending on mean
energy ML , and extensions to mixed states mixed , nonorthogonal states
nonorthogonal1 ; nonorthogonal2 , time-dependent driven system timedependent1
; timedependent2 , and open quantum systems Taddei ; Campo ; Deffner ; Sun ;
Meng ; Zhang  have been investigated. The QSL gives a trade-off relation
between the control time and energy resource, and thus it has several
applications in quantum control scenarios Caneva ; Poggi1 ; Andersson ; Poggi2
; Poggi3 . Actually, the connection between the reachable set and the QSL has
been studied in recent years. Arenz et al., characterized the sets of the all
target unitary gates by considering the QSL for the control time as the
necessary condition that control parameters, e.g., the drift and control
Hamiltonians and driving time, must satisfy in order to implement the target
gate Arenz .
Inspired by the above facts, in this paper we extend the work by Arenz et al.
to general Markovian open quantum systems. More precisely, we characterize the
reachable set of an open quantum system under a certain situation, e.g.,
initial state, Hamiltonian, decoherence, and evolution time, using the QSL. In
order to make this analysis tractable and rigorous, we employ the bound
derived in Kohei2 , because it is not only explicitly computable with respect
to control parameters, but also tighter than the other explicit bounds. Sec.
III provides some examples for demonstrating this analysis with insightful
notions.

##  II Setup and QSL

In this section, we introduce the QSL presented in Kohei2 . We first begin
with considering the Markovian master equation

$\displaystyle\frac{d\rho_{t}}{dt}=-i[H,\rho_{t}]+{\mathcal{D}}[M]\rho_{t},$
(1)

where $H$ is the time-independent Hamiltonian. $M$ is the Lindblad operator
representing the decoherence, and thus ${\mathcal{D}}[M]\rho=M\rho
M^{\dagger}-M^{\dagger}M\rho/2-\rho M^{\dagger}M/2$. Throughout this paper, we
assume that $\hbar=1$ and the initial state is pure, i.e.,
$\rho_{0}=|{\psi_{0}}\rangle\langle{\psi_{0}}|$. Next we focus on the relative
purity $\Theta_{t}$ between initial state and final state

$\displaystyle\Theta_{t}:={\rm
arccos}\left(\langle\psi_{0}|\rho_{t}|\psi_{0}\rangle\right),$ (2)

where $0\leq\Theta_{t}\leq\pi/2$. The relative purity has been often employed
for deriving the QSL Campo ; Meng . The upper bound is achieved when
$\rho_{0}$ and $\rho_{t}$ are orthogonal, and the lower one is achieved only
when $\rho_{t}=\rho_{0}$. In this setting, we find that the dynamics of
$\Theta_{t}$ is upper bounded as follows:

$\displaystyle\frac{d\Theta_{t}}{dt}\leq\frac{1}{\sin\Theta_{t}}(\mathcal{A}\sqrt{1-\cos\Theta_{t}}+\mathcal{E}),$
(3)

with

$\displaystyle\mathcal{A}=\sqrt{2}\left(\|i[H,\rho_{0}]+\mathcal{D}^{\dagger}[M]\rho_{0}\|_{\rm
F}\right),$
$\displaystyle\mathcal{E}=\|M|{\psi_{0}}\rangle\|^{2}-|\langle{\psi_{0}}|M|{\psi_{0}}\rangle|^{2},$

where $\|X\|_{\rm F}=\sqrt{{\rm Tr}(X^{\dagger}X)}$,
$\||{\psi}\rangle\|=\sqrt{\langle\psi|\psi\rangle}$, and
$\mathcal{D}^{\dagger}[M]\rho=M^{\dagger}\rho M-M^{\dagger}M\rho/2-\rho
M^{\dagger}M/2$. Integrating the above inequality (3) from $0$ to $T$, we
obtain the following lower bound Kohei2 :

$\displaystyle T\geq
T_{*}:=\frac{2\lambda}{\mathcal{A}}+\frac{2\mathcal{E}}{\mathcal{A}^{2}}\ln\left(\frac{\mathcal{E}}{\mathcal{E}+\mathcal{A}\lambda}\right),$
(4)

with $\lambda=\sqrt{1-\cos\Theta_{T}}$ $(0\leq\lambda\leq 1)$. The derivation
of the above results are given in Appendix A. This upper bound is achieved
when $\Theta_{T}=\pi/2$ and the lower one is achieved when $\Theta_{0}=0$,
Hence $\lambda$ can be interpreted as the radius of the ball around
$\rho_{0}$. The QSL $T_{*}$ gives a lower bound on the time $T$ for the state
$\rho_{t}$ to evolve from $\rho_{0}$ to $\rho_{T}$ (i.e., $\Theta_{t}$ evolves
from $0$ to $\Theta_{T}$). As shown in Ref Kohei2 , $T_{*}$ has the following
notable features: (i) $T_{*}$ is applicable to a general Markovian open
quantum system driven by arbitrary $H$ and $M$. (ii) $T_{*}$ is explicitly
computable once the parameters $(\rho_{0},H,M,\Theta_{T})$ are specified.
Thanks to this, it is not necessary for solving any equations to calculate
$T_{*}$. (iii) When $M=M^{\dagger}$, $H=0$, and $|{\psi_{0}}\rangle$ is an
eigenstate of $M$, or $M=0$ and $[H,\rho_{0}]=0$, we have $T_{*}\to\infty$ due
to $\mathcal{A}=\mathcal{E}=0$. In this case, the state cannot reach any
$\rho_{T}\neq\rho_{0}$, resulting that $\lambda$ remains zero. (iv) $T_{*}$ is
tighter than the other explicit bound; for the same setup mentioned above, del
Campo provided the QSL: $T\geq T_{\rm DC}:=\sqrt{2}\lambda/\mathcal{A}$ Campo
. Note that $T_{*}\geq T_{\rm DC}$ holds when the decoherence is small or the
radius $\lambda$ is small. (v) If $H$ is time-dependent, we cannot generally
solve the integral (3). Then, defining $H_{t}=u_{t}H^{\prime}$ where $u_{t}$
is the time-dependent control input with a energy constraint $u_{\rm
max}:={\rm max}\\{|u_{t}|\\}$ and using the triangle inequality,
${\mathcal{A}}$ is redefined as follows:

$\displaystyle\mathcal{A}^{\prime}=\sqrt{2}\left(u_{\rm
max}\|i[H^{\prime},\rho_{0}]\|_{\rm
F}+\|\mathcal{D}^{\dagger}[M]\rho_{0}\|_{\rm F}\right).$ (5)

Therefore, in this case the QSL is given by (4) replacing $\mathcal{A}$ with
$\mathcal{A}^{\prime}$.
In addition to the above points, here we explain the idea of charcterization
of the reachable set of targets based on the QSL; the parameters determining
the state evolution $(\rho_{0},H,M,T)$ and the fidelity-based distance
$\lambda$ are correlated via the inequality $T\geq T_{*}$. In other words,
this relation can be considered as a necessary condition that
$(\rho_{0},H,M,T)$ must satisfy in order to achieve a certain $\lambda$.
Therefore, once these parameters are specified, we can characterize the set of
all $\lambda$ (i.e., the set of all final states $|{\psi_{T}}\rangle$) by
examining $T\geq T_{*}$. Now as a simple example, let us consider the closed
system driven by $H$. In this case, we have $\mathcal{E}=0$ and

$\displaystyle\mathcal{A}$ $\displaystyle=\sqrt{2}\|i[H,\rho_{0}]\|_{\rm
F}=2\sqrt{\langle\psi_{0}|H^{2}|\psi_{0}\rangle-\langle\psi_{0}|H|\psi_{0}\rangle^{2}},$

which corresponds to the variance of the system energy in the initial state.
Hence for the state evolution from $|{\psi_{0}}\rangle$ to any final state
$|{\psi_{T}}\rangle$, $\lambda=\sqrt{1-\cos\Theta_{T}}$ has an upper bound

$\displaystyle\lambda\leq\sqrt{\langle\psi_{0}|H^{2}|\psi_{0}\rangle-\langle\psi_{0}|H|\psi_{0}\rangle^{2}}T.$
(6)

In particular, when $T$ is small such that the rightmost side of (6) is less
than one, it gives a meaningful bound with respect to $\lambda$. In what
follows, some typical examples demonstrating this idea will be given.

##  III Example

###  III.1 Qubit

First we study a qubit system consisting of the excited state
$|{0}\rangle=[1,0]^{\top}$ and the ground state $|{1}\rangle=[0,1]^{\top}$.
Its initial pure state can be fully parametrized by the Bloch representation:

$\displaystyle|{\psi_{0}}\rangle=[\cos\theta,\
e^{i\varphi}\sin\theta]^{\top},$ (7)

where $0\leq\theta,\varphi\leq\pi$. Also the system observables along the $i$
axis ($i=x,y,z$) are given by the Pauli matrices
$\sigma_{x}=|{0}\rangle\langle{1}|+|{1}\rangle\langle{0}|$,
$\sigma_{y}=-i|{0}\rangle\langle{1}|+i|{1}\rangle\langle{0}|$, and
$\sigma_{z}=|{0}\rangle\langle{0}|-|{1}\rangle\langle{1}|$. Here we consider
the following setup:

$\displaystyle H=\Omega\sigma_{z},\ M=\sqrt{\gamma}\sigma_{-}.$ (8)

$H$ represents the rotation the state along the $z$ axis with the frequency
$\Omega>0$ and $M$ represents the energy decay $|{0}\rangle\to|{1}\rangle$
with decay rate $\gamma>0$. In this case, the lower bound is given by (4) with

$\displaystyle\mathcal{A}$
$\displaystyle=\sqrt{2\gamma^{2}\cos^{2}2\theta+(4\Omega^{2}+\frac{\gamma^{2}}{4})\sin^{2}2\theta},$
$\displaystyle\mathcal{E}$ $\displaystyle=\gamma\cos^{4}\theta.$

First we focus on the case of $\gamma=0$, where $\lambda$ has an upper bound
$\lambda\leq\Omega|\sin 2\theta|T$. Figure 1 (a) shows the reachable set of
$\lambda$ for each initial states and driving times. The colored area is the
all sets satisfying this inequality and the white area is the one that does
not satisfy it. We find that the three curves takes zero at $\theta=0$ and
$\pi/2$, meaning that $|{0}\rangle$ and $|{1}\rangle$ does not change under
the rotation. This is consistent with the fact that $|{0}\rangle$ and
$|{1}\rangle$ are the steady state of the equation
$d\rho_{t}/dt=-i\Omega[\sigma_{z},\rho_{t}]$. Further, the reachable sets take
maximum at the superposition
$|{+}\rangle:=(|{0}\rangle+|{1}\rangle)/\sqrt{2}$, which lies on the equator
of the Bloch sphere. This implies that the rate of the state change from
$|{+}\rangle$ is biggest, and thus is the most fragile state against the
rotation induced by $H$. On the other hand, when $\gamma=1$, the curves take
the maximum at $\theta=0$ [Fig. 1 (b)]. This is because $|{0}\rangle$ is
largely affected by the decoherence $M$, while it is unchanged against $H$ due
to the fact that $|{0}\rangle$ is the eigenstate of $H$. In particular, it is
noted that the state cannot reach its orthogonal state within $T=0.1$, $0.3$,
while $|{\psi_{0}}\rangle$ with $\theta\leq 0.9$ may do so within $T=0.8$.
Next we consider an unitary gate implementation; that is, we aim to implement
the target gate by appropriately designing the time-dependent Hamiltonian
$H_{t}$ under the assumption that $M=0$. Now let the target gate be the
rotation operator
$G(\alpha,\beta,\delta)=R_{z}(\alpha)R_{y}(\beta)R_{z}(\delta)$ with

$\displaystyle
R_{z}(\alpha)=e^{-i\frac{\alpha}{2}\sigma_{z}}=\left[\begin{array}[]{cc}e^{-i\frac{\alpha}{2}}&0\\\
0&e^{i\frac{\alpha}{2}}\end{array}\right],$ $\displaystyle
R_{y}(\beta)=e^{-i\frac{\beta}{2}\sigma_{y}}=\left[\begin{array}[]{cc}\cos\frac{\beta}{2}&-\sin\frac{\beta}{2}\\\
\sin\frac{\beta}{2}&\cos\frac{\beta}{2}\end{array}\right],$ $\displaystyle
R_{z}(\delta)=e^{-i\frac{\delta}{2}\sigma_{z}}=\left[\begin{array}[]{cc}e^{-i\frac{\delta}{2}}&0\\\
0&e^{i\frac{\delta}{2}}\end{array}\right],$

where $0\leq\alpha<2\pi$, $0\leq\beta<\pi$, and $0\leq\delta<4\pi$. $R_{y}$
and $R_{z}$ represent the rotation around $y$ and $z$ axis, respectively, and
the transformation from $|{\psi_{0}}\rangle$ to $|{\psi_{T}}\rangle$ is
described by $|{\psi_{T}}\rangle=G(\alpha,\beta,\delta)|{\psi_{0}}\rangle$.
Also we take the Hamiltonian as

$\displaystyle H_{t}=\Omega\sigma_{x}+u_{t}\sigma_{z}.$ (9)

Note that the state is fully controllable, hence every
$G(\alpha,\beta)\subset{\rm SU}(2)$ can be implemented by suitably choosing
$u_{t}$ for sufficient time Arenz . In this case the lower bound is calculated
as follows:

$\displaystyle
T_{\ast}=\frac{\sqrt{1-\cos^{2}\frac{\alpha}{2}\cos^{2}\frac{\beta}{2}-\sin^{2}\frac{\alpha}{2}\cos^{2}(2\theta+\frac{\beta}{2})}}{\Omega|\cos
2\theta|+u_{\rm max}|\sin 2\theta|}.$ (10)

If $\theta=0$, $T_{*}=|\sin(\beta/2)|/\Omega$. Figure 1 (c) shows the sets
that satisfies $T\geq T_{*}$ for $T=0.3$, $0.5$, and $0.8$ under the fixed
values $\Omega=u_{\rm max}=1$. Note that for instance, when $T=0.5$, this
inequality is saturated at $\beta=\pi/3$, where the target is given by

$\displaystyle
G(\alpha)=\frac{1}{2}\left[\begin{array}[]{cc}\sqrt{3}e^{-i\frac{\alpha}{2}}&-e^{-i\frac{\alpha}{2}}\\\
e^{i\frac{\alpha}{2}}&\sqrt{3}e^{i\frac{\alpha}{2}}\end{array}\right].$

This $G$ gives the final fidelity $\cos\Theta_{T}=0.75$. Then we can only
steer the state to the one with fidelity about $0.75$ at most in $T=0.5$. Next
for the case of $\theta=\pi/4$, the lower bound is
$T_{*}=|\sin(\alpha/2-\beta/2)|/u_{\rm max}$. Clearly, the reachable sets
depicted in Fig. 1 (d) are remarkably changed from Fig. 1 (c). The lower bound
$T_{*}(\alpha,\beta)$ takes zero at $G(0,0)=G(2\pi,0)=I$ and
$G(\pi,\pi)=i\sigma_{x}$, because $|{\psi_{0}}\rangle=|{+}\rangle$ is the
eigenstate of $\sigma_{x}$. This means that there is no difference between
$|{\psi_{0}}\rangle$ and $|{\psi_{T}}\rangle$ in terms of the fidelity. On the
other hand, $T_{*}(\alpha,\beta)$ is maximized at

$\displaystyle G(0,\pi)=G(2\pi,\pi)=-i\sigma_{y},\ G(\pi,0)=i\sigma_{z}.$ (11)

Actually, they cannot be implemented even if $T=0.8$. Indeed, this result is
reasonable because the target states generated by $-i\sigma_{y}$ and
$i\sigma_{z}$ are given as $[1,-1]/\sqrt{2}$ and $[i,-i]/\sqrt{2}$, which are
orthogonal to $|{\psi_{0}}\rangle$. Therefore, we can conclude that it takes
longer time to prepare the state that is far from $|{\psi_{0}}\rangle$. As
shown above, by using $T_{*}$, we can characterize the set of the target
states or target gates under a given control setting.

Figure 1: Reachable set of $\lambda$ as a function of $\theta$ for each
evolution times $T=0.3$ (green area), $T=0.5$ (red area), and $T=0.8$ (blue
area) when (a) $\gamma=0$ and (b) $\gamma=1$, in unit of $\Omega=1$. Reachable
set of the target gate $G(\alpha,\beta)$ for $T=0.3$ (green area), $T=0.5$
(red area), and $T=0.8$ (blue area) when (a) $\theta=0$ and (b)
$\theta=\pi/4$, in unit of $\Omega=u_{\rm max}=1$.

###  III.2 Two qubits

Here we study a two-qubit system driven by decoherence. We first consider the
Bell states, which is the maximally entangled states defined as

$\displaystyle|{\Phi^{\pm}}\rangle=\frac{1}{\sqrt{2}}(|{0}\rangle\otimes|{0}\rangle+|{1}\rangle\otimes|{1}\rangle),$
$\displaystyle|{\Psi^{\pm}}\rangle=\frac{1}{\sqrt{2}}(|{1}\rangle\otimes|{0}\rangle+|{0}\rangle\otimes|{1}\rangle).$

The Bell states are used as a main resource for the quantum information
processing such as quantum teleportation. Thereby, it is of particular
interest in comparing the sets of the state from each Bell states under
undesirable noises. Now we take the collective (global) noise modeled by
$M=\sqrt{\gamma}(\sigma_{-}\otimes I+I\otimes\sigma_{-})$. Further, for
simplicity, we assume $H=0$. Then, the lower bound for each states are
calculated as follows:

$\displaystyle
T_{*}(|{\Phi^{\pm}}\rangle)=\frac{2\lambda}{\sqrt{5}\gamma}-\frac{2}{5\gamma}\ln(1+\lambda),$
$\displaystyle
T_{*}(|{\Psi^{+}}\rangle)=\frac{\lambda}{2\gamma}-\frac{1}{4\gamma}\ln(1+2\lambda),$

and $T_{*}(|{\Psi^{-}}\rangle)\to\infty$ due to $\mathcal{A}=0$. This
corresponds to the fact that the initial state $|{\Psi^{-}}\rangle$ does not
change because it is identical to the zero eigenstate of $M$. Hence, as an
information resource, $|{\Psi^{-}}\rangle$ is the best initial state against
$M$. Also, as shown in Fig. 2 (a), the set of the state from
$|{\Psi^{+}}\rangle$ spreads faster than that of $|{\Phi^{\pm}}\rangle$ as
$\gamma$ increases, implying that $|{\Phi^{\pm}}\rangle$ can preserve its
coherence longer than $|{\Psi^{+}}\rangle$.
Next we consider a qutrit, which is a symmetric two-qubit system described by
a three-level system consisting of the distinguishable states
$|{E}\rangle=[1,0,0]^{\top}$, $|{S}\rangle=[0,1,0]^{\top}$, and
$|{G}\rangle=[0,0,1]^{\top}$. Note that $|{S}\rangle$ corresponds to the
entangled state between two states. As seen in the qubit example, we
investigate a reachable set of the target $3\times 3$ gate. Let us consider a
rotation operator of the three-dimensional system
$G(\alpha,\beta,\delta)=R_{z}(\delta)R_{y}(\beta)R_{x}(\alpha)$ where matrix
representations of $R_{i}$ ($i=x,y,z$) are given as

$\displaystyle
R_{x}(\alpha)=\left[\begin{array}[]{ccc}\cos\alpha&-\sin\alpha&0\\\
\sin\alpha&\cos\alpha&0\\\ 0&0&1\end{array}\right],$ $\displaystyle
R_{y}(\beta)=\left[\begin{array}[]{ccc}\cos\beta&0&\sin\beta\\\ 0&1&0\\\
-\sin\beta&0&\cos\beta\end{array}\right],$ $\displaystyle
R_{z}(\delta)=\left[\begin{array}[]{ccc}1&0&0\\\ 0&\cos\delta&-\sin\delta\\\
0&\sin\delta&\cos\delta\end{array}\right],$

where $\alpha$, $\beta$, and $\delta$ are the rotation angles about $x$, $y$,
and $z$-axis. We limit the initial pure state to the real vector

$\displaystyle|{\psi_{0}}\rangle=[\sin(\theta/2)\cos(\varphi/2),\
\cos(\theta/2),\ \sin(\theta/2)\sin(\varphi/2)]^{\top},$

where $0\leq\theta$, $\varphi\leq\pi$. Also we assign the following
Hamiltonian:

$\displaystyle H_{t}=\Omega S_{x}+u_{t}S_{z},$ (12)

where $S_{x}=(|{S}\rangle\langle{E}|+|{G}\rangle\langle{S}|)/\sqrt{2}$+H.c.,
$S_{y}=i(|{S}\rangle\langle{E}|+|{G}\rangle\langle{S}|)/\sqrt{2}$+H.c., and
$S_{z}=|{E}\rangle\langle{E}|-|{G}\rangle\langle{G}|$ are the spin angular
momentum operators. This Hamiltonian is a straightforward extension of the
expression (9). Now as an example, we choose $\delta=0$ and
$|{\psi_{0}}\rangle=[1,0,1]^{\top}/\sqrt{2}$ at
$(\theta,\varphi)=(\pi,\pi/2)$. In this setting, we obtain the lower bound as

$\displaystyle T\geq T_{*}=\frac{\sqrt{1-\cos\Theta_{T}}}{\Omega+u_{\rm
max}},$ (13)

with

$\displaystyle\cos\Theta_{T}=\frac{1}{4}\left(\cos\alpha\cos\beta+\cos\alpha\sin\beta+\cos\beta-\sin\beta\right)^{2}.$
(14)

Thus, from Eq. (14), $T_{*}$ is maximized when $(\alpha,\beta)$ satisfies
$\cos\alpha=(\sin\beta-\cos\beta)/(\sin\beta+\cos\beta)$ [Fig. 2 (b)]; here we
typically take the following target gates

$\displaystyle G(\pi,0)=\left[\begin{array}[]{ccc}-1&0&0\\\ 0&-1&0\\\
0&0&1\end{array}\right],\ G(0,\pi/2)=\left[\begin{array}[]{ccc}0&0&1\\\
0&1&0\\\ -1&0&0\end{array}\right],$ $\displaystyle
G(\pi,\pi)=\left[\begin{array}[]{ccc}1&0&0\\\ 0&-1&0\\\
0&0&-1\end{array}\right].$

As noted in the previous subsection, the final states generated by the above
gates are orthogonal to $|{\psi_{0}}\rangle$, and thus implementing such goal
gates takes longest time. Moreover, let us particularly consider the spin-up
transformation $|{\psi_{0}}\rangle\to|{E}\rangle$, which is realized by
$G(0,\pi/4)$ or $G(\pi,3\pi/4)$. From Fig. 2 (b), it is immediately found that
this transformation takes $T=0.5$ at least. In this way, we can roughly
estimate the time to implement the target gate without solving any equations.

Figure 2: (a) Reachable sets of $\lambda$ as a function of $\gamma$ in $T=0.5$
when the initial state is $|{\Psi^{+}}\rangle$ (blue area),
$|{\Phi^{\pm}}\rangle$ (red area), and $|{\Phi^{-}}\rangle$ (green dot at the
origin). (b) Reachable set of the target gate $G(\alpha,\beta)$ when
$\theta=\pi/4$ in unit of $\Omega=u_{\rm max}=1$ for $T=0.3$ (green area),
$T=0.5$ (red area), and $T=0.8$ (blue area).

##  IV Conclusion

Motivated by the work by Arenz et al., in this paper we have characterized the
reachable set of Markovian open quantum systems under a given control setting
based on the QSL. In order to make this analysis tractable and rigorous, it is
important that the QSL is explicitly computable and tighter than other bounds;
the QSL used in this paper indeed satisfies these conditions. Thanks to this
features, as shown in Sec. III, we can clarify the set of all final states in
a given control time and roughly estimate the time for the controlled state
existng in a certain region from the initial state without solving any
equations. An important remaining work is to extend this approach to more
strategic control cases, e.g., the measurement-based feedback control.
This work was supported by MEXT Quantum Leap Flagship Program Grant Number
JPMXS0118067285 and JPMXS0120319794.

##  Appendix A Proof of QSL

We begin with taking the time derivative of $\Theta_{t}$:

$\displaystyle\frac{d\Theta_{t}}{dt}$ $\displaystyle=\frac{-1}{\sqrt{1-{\rm
Tr}(\rho_{0}\rho_{t})^{2}}}\cdot{\rm
Tr}\left(\rho_{0}\frac{d\rho_{t}}{dt}\right)$
$\displaystyle=\frac{1}{\sin\Theta_{t}}{\rm
Tr}\left\\{\left(i[\rho_{0},H]-\mathcal{D}^{\dagger}[M]\rho_{0}\right)\rho_{t}\right\\},$
(15)

To have an upper bound of the rightmost side of (A), we often use the Schwarz
inequality for matrices $X$ and $Y$:

$\left|{\rm Tr}(X^{\dagger}Y)\right|\leq\|X\|_{\rm F}\|Y\|_{\rm F}.$ (16)

Also the following inequality is often used:

$\displaystyle\|\rho_{t}-\rho_{0}\|_{\rm F}$ $\displaystyle=\sqrt{{\rm
Tr}\big{[}\left(\rho_{t}-\rho_{0}\right)^{2}\big{]}}=\sqrt{{\rm
Tr}\left(\rho_{t}^{2}-2\rho_{t}\rho_{0}+\rho_{0}^{2}\right)}$
$\displaystyle\leq\sqrt{2-2{\rm
Tr}(\rho_{t}\rho_{0})}=\sqrt{2-2\cos\Theta_{t}},$

where ${\rm Tr}(\rho_{t}^{2})\leq 1$ and ${\rm Tr}(\rho_{0}^{2})=1$ are used.
Using these inequalities, the rightmost side of (A) is upper bounded by

$\displaystyle{\rm
Tr}\\{\left(i[\rho_{0},H]-\mathcal{D}^{\dagger}[M]\rho_{0}\right)\rho_{t}\\}$
$\displaystyle={\rm
Tr}\\{\left(i[\rho_{0},H]-\mathcal{D}^{\dagger}[M]\rho_{0}\right)(\rho_{t}-\rho_{0})\\}-{\rm
Tr}(\rho_{0}\mathcal{D}^{\dagger}[M]\rho_{0})$ $\displaystyle={\rm
Tr}\\{\left(i[H,\rho_{0}]+\mathcal{D}^{\dagger}[M]\rho_{0}\right)(\rho_{0}-\rho_{t})\\}+{\rm
Tr}(M^{\dagger}M\rho_{0})$ $\displaystyle\ \ \ -{\rm
Tr}(M^{\dagger}\rho_{0}M\rho_{0})$
$\displaystyle\leq\|i[H,\rho_{0}]+\mathcal{D}^{\dagger}[M]\rho_{0}\|_{\rm
F}\cdot\|\rho_{t}-\rho_{0}\|_{\rm F}+\|M|{\psi_{0}}\rangle\|^{2}$
$\displaystyle\ \ \ -|\langle{\psi_{0}}|M|{\psi_{0}}\rangle|^{2}$
$\displaystyle\leq\sqrt{2}\|i[H,\rho_{0}]+\mathcal{D}^{\dagger}[M]\rho_{0}\|_{\rm
F}\sqrt{1-\cos\Theta_{t}}+\|M|{\psi_{0}}\rangle\|^{2}$ $\displaystyle\ \ \
-|\langle{\psi_{0}}|M|{\psi_{0}}\rangle|^{2}$
$\displaystyle\leq\sqrt{2}\left(\|i[H,\rho_{0}]+\mathcal{D}^{\dagger}[M]\rho_{0}\|_{\rm
F}\right)\sqrt{1-\cos\Theta_{t}}$ $\displaystyle\ \ \
+\|M|{\psi_{0}}\rangle\|^{2}-|\langle{\psi_{0}}|M|{\psi_{0}}\rangle|^{2}.$
(17)

From Eqs. (A) and (A), we have

$\displaystyle\frac{d\Theta_{t}}{dt}\leq\frac{1}{\sin\Theta_{t}}\left(\mathcal{A}\sqrt{1-\cos\Theta_{t}}+\mathcal{E}\right),$
(18)

where

$\displaystyle\mathcal{A}$ $\displaystyle=$
$\displaystyle\sqrt{2}\left(\|i[H,\rho_{0}]+\mathcal{D}^{\dagger}[M]\rho_{0}\|_{\rm
F}\right),$ $\displaystyle\mathcal{E}$ $\displaystyle=$
$\displaystyle\|M|{\psi_{0}}\rangle\|^{2}-|\langle{\psi_{0}}|M|{\psi_{0}}\rangle|^{2}.$

Finally, by integrating (18) from $t=0$ to $T$, we end up with the lower bound
(4).

## References

  * (1) G. Dirr, U. Helmke, I. Kurniawan, and T. Schlte-Herbruggen, Lie-semigroup structures for reachability and control of open quantum systems: kossakowski-lindblad generators form lie wedge to markovian channels, Rep. Math. Phys. 64, 93 (2009).
  * (2) G. Dirr, U. Helmke, M. Kleinsteuber, S. J. Glaser, and T. Schulte-Herbruggen, The local C-numerical range: Examples, conjectures, and numerical algorithms, Proc. MTNS, Kyoto (2006).
  * (3) H. Yuan, Reachable set of operators on controlled open quantum systems in a Markovian environment, Automatica 49, 955 (2013).
  * (4) L. Mandelstam and I. Tamm, The uncertainty relation between energy and time in nonrelativistic quantum mechanics, J. Phys. (USSR) 9, 249-254 (1945).
  * (5) N. Margolus and L. B. Levitin, The maximum speed of dynamical evolution, Physica D 120, 188 (1998).
  * (6) A. Uhlmann, An energy dispersion estimate, Phys. Lett. A 161, 329 (1992).
  * (7) V. Giovannetti, S. Lloyd, and L. Maccone, Quantum limits to dynamical evolution, Phys. Rev. A 67, 052109 (2003).
  * (8) S. Luo and Z. Zhang, On decaying rate of a quantum state, Lett. Math. Phys. 71, 7-11 (2005).
  * (9) P. Pfeifer, How fast can a quantum state change with time?, Phys. Rev. Lett. 70, 22, 3365 (1993).
  * (10) P. Pfeifer and J. Frohlich, Generalized time-energy uncertainty relations and bounds on lifetimes of resonance, Rev. Mod. Phys. 67, 759 (1995).
  * (11) M. M. Taddei, B. M. Escher, L. Davidovich, and R. L. de Matos Filho, Quantum speed limit for physical processes, Phys. Rev. Lett. 110, 050402 (2013).
  * (12) A. del Campo, I. L. Egusquiza, M. B. Plenio, and S. F. Huelga, Quantum speed limits in open system dynamics, Phys. Rev. Lett. 110, 050403 (2013).
  * (13) S. Deffner and E. Lutz, Quantum speed limit for non-Markovian dynamics, Phys. Rev. Lett. 111, 010402 (2013).
  * (14) Z. Sun, J. Liu, J. Ma, and X. Wang, Quantum speed limits in open systems: non-Markovian dynamics without rotating-wave approximation, Sci. Rep. 5, 8444 (2015).
  * (15) X. Meng, C. Wu, and H. Guo, Minimal evolution time and quantum speed limit of non-Markovian open systems, Sci. Rep. 5, 16357 (2015).
  * (16) Y.-J. Zhang, W. Han, Y.-J. Xia, J.-P Cao, and H. Fan, Quantum speed limit for arbitrary initial states, Sci. Rep. 4, 27349 (2016).
  * (17) T. Caneva, M. Murphy, T. Calarco, R. Fazio, S. Montangero, V. Giovannetti, and G. E. Santoro, Optimal Control at the Quantum Speed Limit, Phys. Rev. Lett. 103, 240501 (2009).
  * (18) P. M. Poggi, F. C. Lombardo, and D. A. Wisniacki, Quantum speed limit and optimal evolution time in a two-level system, EPL 104 (2013).
  * (19) O. Andersson and H. Heydari, Quantum speed limits and optimal Hamiltonians for driven systems in mixed states, J. Phys. A: Math. Theor. 47, 215301 (2014).
  * (20) P. M. Poggi, Geometric quantum speed limits and short-time accessibility to unitary operations, Phys. Rev. A 99, 042116 (2019).
  * (21) P. M. Poggi, Analysis of lower bounds for quantum control times and their relation to the quantum speed limit, Anales. AFA 31, 29-38 (2020).
  * (22) C. Arenz, B. Russell, D. Burgarth, and H. Rabitz, The roles of drift and control field constraints upon quantum control speed limits, New J. Phys. 19, 103015 (2017).
  * (23) K. Kobayashi and N. Yamamoto, Quantum speed limit for robust state characterization and engineering, Phys. Rev. A 102, 042606 (2020).


# Ultrahyperbolic Knowledge Graph Embeddings

Bo Xiong  0000-0002-5859-1961 University of StuttgartStuttgartGermany
<EMAIL_ADDRESS>,  Shichao Zhu  IIE, Chinese Academy of
SciencesSchool of Cyber Security, UCASBeijingChina<EMAIL_ADDRESS>,
Mojtaba Nayyeri  University of StuttgartStuttgartGermany ,  Chengjin Xu
University of BonnBonnGermany ,  Shirui Pan  Monash
UniversityMelbourneAustralia ,  Chuan Zhou  AMSS, Chinese Academy of
SciencesBeijingChina and  Steffen Staab  University of StuttgartUniversity of
SouthamptonStuttgartGermany

(2022)

###### Abstract.

Recent knowledge graph (KG) embeddings have been advanced by hyperbolic
geometry due to its superior capability for representing hierarchies. The
topological structures of real-world KGs, however, are rather heterogeneous,
i.e., a KG is composed of multiple distinct hierarchies and non-hierarchical
graph structures. Therefore, a homogeneous (either Euclidean or hyperbolic)
geometry is not sufficient for fairly representing such heterogeneous
structures. To capture the topological heterogeneity of KGs, we present an
ultrahyperbolic KG embedding (UltraE) in an ultrahyperbolic (or pseudo-
Riemannian) manifold that seamlessly interleaves hyperbolic and spherical
manifolds. In particular, we model each relation as a pseudo-orthogonal
transformation that preserves the pseudo-Riemannian bilinear form. The pseudo-
orthogonal transformation is decomposed into various operators (i.e., circular
rotations, reflections and hyperbolic rotations), allowing for simultaneously
modeling heterogeneous structures as well as complex relational patterns.
Experimental results on three standard KGs show that UltraE outperforms
previous Euclidean- and hyperbolic-based approaches.

knowledge graph embeddings, knowledge graph completion, ultrahyperbolic
manifold

††journalyear: 2022††copyright: acmcopyright††conference: Proceedings of the
28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining; August
14–18, 2022; Washington, DC, USA††booktitle: Proceedings of the 28th ACM
SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’22), August
14–18, 2022, Washington, DC, USA††price: 15.00††doi:
10.1145/3534678.3539333††isbn: 978-1-4503-9385-0/22/08††ccs: Computing
methodologies Knowledge representation and reasoning††ccs: Computing
methodologies Semantic networks

##  1\. Introduction

Knowledge graph (KG) embeddings, which map entities and relations into a low-
dimensional space, have emerged as an effective way for a wide range of KG-
based applications (Celebi et al., 2019; Cao et al., 2019; Huang et al.,
2019). In the last decade, various KG embedding methods have been proposed.
Prominent examples include the _additive_ (or _translational_) family (Bordes
et al., 2013b; Wang et al., 2014; Lin et al., 2015) and the _multiplicative_
(or _bilinear_) family (Nickel et al., 2011; Yang et al., 2015; Liu et al.,
2017). Most of these approaches, however, are built on the Euclidean geometry
that suffers from inherent limitations when dealing with hierarchical KGs such
as WordNet (Miller, 1995). Recent studies (Chami et al., 2019; Nickel and
Kiela, 2017) show that hyperbolic geometries (e.g., the Poincaré ball or
Lorentz model) are more suitable for embedding hierarchical data because of
their exponentially growing volumes. Such _tree-like_ geometric space has been
exploited in developing various hyperbolic KG embedding models such as MuRP
(Balazevic et al., 2019), RotH (Chami et al., 2020) and HyboNet (Chen et al.,
2021), boosting the performance of link prediction on KGs with rich
hierarchical structures and remarkably reducing the dimensionality.

Although hierarchies are the most dominant structures, the real-world KGs
usually exhibit heterogeneous topological structures, e.g., a KG consists of
multiple hierarchical and non-hierarchical relations. Typically, different
hierarchical relations (e.g., subClassOf and partOf) form distinct
hierarchies, while various non-hierarchical relations (e.g., similarTo and
sisterTerm) capture the corresponding interactions between the entities at the
same hierarchy level (Bai et al., 2021). Fig.1(a) shows an example of KG
consisting of a heterogeneous graph structure. However, current hyperbolic KG
embedding methods such as MuRP (Balazevic et al., 2019) and HyboNet (Chen et
al., 2021) can only model a globally homogeneous hierarchy. RotH (Chami et
al., 2020) implicitly considers the topological ”heterogeneity” of KGs and
alleviates this issue by learning relation-specific curvatures that
distinguish the topological characteristics of different relations. However,
this does not entirely solve the problem, because hyperbolic geometry
inherently _mismatches_ non-hierarchical data (e.g., data with cyclic
structure) (Gu et al., 2019).

To deal with data with heterogeneous topologies, a recent work (Wang et al.,
2021b) learns KG embeddings in a product manifold and shows some improvements
on KG completion. However, such product manifold is still a homogeneous space
in which all data points have the same degree of heterogeneity (i.e.,
hierarchy and cyclicity), while KGs require relation-specific geometric
mappings, e.g., relation partOf should be more ”hierarchical” than relation
similarTo. Different from previous works, we consider an ultrahyperbolic
manifold that seamlessly interleaves the hyperbolic and spherical manifolds.
Fig.1 (b) shows an example of ultrahyperbolic manifold that contains multiple
distinct geometries. Ultrahyperbolic manifold has demonstrated impressive
capability on embedding graphs with heterogeneous topologies such as
hierarchical graphs with cycles (Law and Stam, 2020; Sim et al., 2021; Xiong
et al., 2021). However, such powerful representation space has not yet been
exploited for embedding KGs with heterogeneous topologies.

(a)

(b)

Figure 1. (a) A KG contains multiple distinct hierarchies (e.g., subClassOf
and partOf) and non-hierarchical relations (e.g., similarTo and sisterTerm).
(b) An ultrahyperbolic manifold generalizing hyperbolic and spherical
manifolds (figure from (Law and Stam, 2020)).

In this paper, we propose ultrahyperbolic KG embeddings (UltraE), the first KG
embedding method that simultaneously embeds multiple distinct hierarchical
relations and non-hierarchical relations in a single but heterogeneous
geometric space. The intuition behind the idea is that there exist multiple
kinds of local geometries that could describe their corresponding relations.
For example, as shown in Fig. 2(a), two points in the same _circular conic
section_ are described by spherical geometry, while two points in the same
half of a _hyperbolic conic section_ can be described by hyperbolic geometry.
In particular, we model entities as points in the ultrahyperbolic manifold and
model relations as pseudo-orthogonal transformations, i.e., isometries in the
ultrahyperbolic manifold. We exploit the theorem of hyperbolic Cosine-Sine
decomposition (Stewart and Dooren, 2005) to decompose the pseudo-orthogonal
matrices into various geometric operations including circular
rotations/reflections and hyperbolic rotations. Circular rotations/reflections
allow for modeling relational patterns (e.g., composition), while hyperbolic
rotations allow for modeling hierarchical graph structures. As Fig. 2(b)
shows, a combination of circular rotations/reflections and hyperbolic
rotations induces various geometries including circular, elliptic, parabolic
and hyperbolic geometries. These geometric operations are parameterized by
Givens rotation/reflection (Chami et al., 2020) and trigonometric functions,
such that the number of relation parameters grows linearly w.r.t embedding
dimensionality. The entity embeddings are parametrized in Euclidean space and
projected to the ultrahyperbolic manifold with differentiable and bijective
mappings, allowing for stable optimization via standard Euclidean based
gradient descent algorithms.

Contributions. Our key contributions are summarized as follows:

  * •

We propose a novel KG embedding method, dubbed UltraE, that models entities in
an ultrahyperbolic manifold seamlessly covering various geometries including
hyperbolic, spherical and their combinations. UltraE enables modeling multiple
hierarchical and non-hierarchical structures in a single but heterogeneous
space.

  * •

We propose to decompose the relational transformation into various operators
and parameterize them via Givens rotations/reflections such that the number of
parameters is linear to the dimensionality. The decomposed operators allow for
modeling multiple relational patterns including inversion, composition,
symmetry, and anti-symmetry.

  * •

We propose a novel Manhattan-like distance in the ultrahyperbolic manifold, to
retain the identity of indiscernibles while without suffering from the broken
geodesic issues.

  * •

We show the theoretical connection of UltraE with some existing approaches.
Particularly, by exploiting the theorem of Lorentz transformation, we identify
the connections between multiple hyperbolic KG embedding methods, including
MuRP, RotH/RefH and HyboNet.

  * •

We conduct extensive experiments on three standard benchmarks, and the
experimental results show that UltraE outperforms previous Euclidean,
hyperbolic and mixed-curvature (product manifold) baselines on KG completion
tasks.

##  2\. Preliminaries

In this paper, the points on a manifold are denoted by boldface lower letters
$\mathbf{x,y}$. The matrices are denoted by boldface capital letters
$\mathbf{U},\mathbf{V},\mathbf{I}$. The embedding spaces are denoted by
blackboard bold capital letters like
$\mathbb{R},\mathbb{H},\mathbb{S},\mathbb{U}$ denoting Euclidean, hyperbolic,
spherical and ultrahyperbolic manifolds, respectively.

###  2.1. Pseudo-Riemannian Geometry

A pseudo-Riemannian manifold $(\mathcal{M},g)$ is a differentiable manifold
$\mathcal{M}$ equipped with a metric tensor $g:T_{\mathbf{x}}\mathcal{M}\times
T_{\mathbf{x}}\mathcal{M}\rightarrow\mathbb{R}$ defined in the entire tangent
space $T_{\mathbf{x}}\mathcal{M}$, where $g$ is non-degenerate (i.e.,
$g(\mathbf{x},\mathbf{y})=0$ for all $\mathbf{y}\in
T_{\mathbf{x}}\mathcal{M}\backslash\\{\mathbf{0}\\}$ implies that
$\mathbf{x}=\mathbf{0}$) and indefinite (i.e., $g$ could be positive, negative
and zero). Such a metric is called a pseudo-Riemannian metric, defined as

(1)
$\displaystyle\forall\mathbf{x},\mathbf{y}\in\mathbb{R}^{p,q},\langle\mathbf{x},\mathbf{y}\rangle_{q}=\sum_{i=1}^{p}\mathbf{x}_{i}\mathbf{y}_{i}-\sum_{j=p+1}^{p+q}\mathbf{x}_{j}\mathbf{y}_{j},$

where $\mathbb{R}^{p,q}$ is a pseudo-Euclidean space (or space-time) with the
dimensionality of $d=p+q$ where $p\geq 0,q\geq 0$. The space
$\mathbb{R}^{p,q}$ has a rich background in physic (O’neill, 1983). A point in
$\mathbb{R}^{p,q}$ is interpreted as an _event_ , where the first $p$
dimensions and last $q$ dimensions are _space-like_ and _time-like_
dimensions, respectively. The pair $(p,q)$ is called the signature of space-
time. Two important special cases are Riemannian ($q=0$) and Lorentz ($q=1$)
geometrics that have positive definite metrics. The more general cases of
pseudo-Riemannian geometry ($q\geq 2,p\geq 1$), however, do not need to
possess positive definiteness, i.e., the scalar product induced by the metric
could be positive (space-like), negative (time-like) or zero (light-like).

(a)  (b)

Figure 2. (a) An illustration of a spherical (green) geometry in the circular
conic section and a hyperbolic (blue) geometry in the hyperbolic conic
section. The Manhattan-like distance of two points is defined by summing up
the _energy_ moving from one point to another point with a circular rotation
and a hyperbolic rotation. $\rho_{\mathbf{x}}(\mathbf{y})$ is a projection of
$\mathbf{y}$ on an circular conic section crossing $\mathbf{x}$, such that
$\rho_{\mathbf{x}}(\mathbf{y})$ and $\mathbf{x}$ are connected by a circular
rotation while $\rho_{\mathbf{x}}(\mathbf{y})$ and $\mathbf{y}$ are connected
by a hyperbolic rotation. (b) An illustration of the various geometries
covered by the circular rotation and hyperbolic rotation, including circular,
elliptic, parabolic and hyperbolic geometries.

###  2.2. Ultrahyperbolic Manifold

By exploiting the scalar product induced by Eq. (1), an ultrahyperbolic
manifold (or pseudo-hyperboloid) is defined as a submanifold in the ambient
space $\mathbb{R}^{p,q}$, given by

(2)
$\mathbb{U}_{\alpha}^{p,q}=\left\\{\mathbf{x}=\left(x_{1},x_{2},\cdots,x_{p+q}\right)^{\top}\in\mathbb{R}^{p,q}:\|\mathbf{x}\|_{q}^{2}=-\alpha^{2}\right\\},$

where $\alpha$ is a non-negative real number denoting the radius of curvature.
$\|\mathbf{x}\|_{q}^{2}=\langle\mathbf{x},\mathbf{x}\rangle_{q}$ is a norm of
the induced scalar product.

The ultrahyperbolic manifold $\mathbb{U}_{\alpha}^{p,q}$ can be seen as a
generalization of hyperbolic and spherical manifolds, i.e., hyperbolic and
spherical manifolds can be defined as special cases of ultrahyperbolic
manifold by setting all time dimensions except one to be zero and setting all
space dimensions to be zero, respectively, i.e.,
$\mathbb{H}_{\alpha}=\mathbb{U}_{\alpha}^{p,1},\mathbb{S}_{\alpha}=\mathbb{U}_{\alpha}^{0,q}$.
It is commonly known that hyperbolic and spherical manifolds are optimal
geometric spaces for hierarchical and cyclic structures, respectively. Hence,
ultrahyperbolic manifold is able to embed both hierarchical and cyclic
structures.

##  3\. Ultrahyperbolic Knowledge Graph Embeddings

Let $\mathcal{E}$ and $\mathcal{R}$ denote the set of entities and relations.
A KG $\mathcal{K}$ consists of a set of triples $(h,r,t)\in\mathcal{K}$ where
$h,t\in\mathcal{E},r\in\mathcal{R}$ denote the head, the tail and their
relation, respectively. The objective is to associate each entity with an
embedding $\mathbf{e}\in\mathbb{U}^{p,q}$ in the ultrahyperbolic manifold, as
well as a relation-specific transformation
$f_{r}:\mathbb{U}^{p,q}\rightarrow\mathbb{U}^{p,q}$ that transforms one entity
to another one in the ultrahyperbolic manifold.

###  3.1. Relation as Pseudo-Orthogonal Matrix

We propose to model relations as pseudo-orthogonal (or $J$-orthogonal)
transformations (Higham, 2003), a generalization of _orthogonal
transformation_ in pseudo-Riemannian geometry. Formally, a real, square matrix
$\mathbf{Q}\in\mathbb{R}^{d\times d}$ is called $J$-orthogonal if

(3) $\mathbf{Q}^{T}\mathbf{J}\mathbf{Q}=\mathbf{J},$

where $\mathbf{J}=\left[\begin{array}[]{cc}\mathbf{I}_{p}&\mathbf{0}\\\
\mathbf{0}&-\mathbf{I}_{q}\end{array}\right],p+q=d$ and $\mathbf{I}_{p}$,
$\mathbf{I}_{q}$ are identity matrices. $\mathbf{J}$ is called a signature
matrix of signature $(p,q)$. Such $J$-orthogonal matrices form a
multiplicative group called pseudo-orthogonal group $O(p,q)$. Conceptually, a
matrix $\mathbf{Q}\in O(p,q)$ is an _isometry_ (distance-preserving
transformation) in the ultrahyperbolic manifold that preserves the bilinear
form (i.e.,
$\forall\mathbf{x}\in\mathbb{U}^{p,q},\mathbf{Q}\mathbf{x}\in\mathbb{U}^{p,q}$).
Therefore, the matrix acts as a linear transformation in the ultrahyperbolic
manifold.

There are two challenges to model relations as $J$-orthogonal transformations:
1) $J$-orthogonal matrix requires $\mathcal{O}(d^{2})$ parameters. 2) Directly
optimizing the $J$-orthogonal matrices results in constrained optimization,
which is practically challenging within the standard gradient based framework.

####  3.1.1. Hyperbolic Cosine-Sine Decomposition

To solve these issues, we seek to decompose the $J$-orthogonal matrix by
exploiting the Hyperbolic Cosine-Sine (CS) Decomposition.

###### Proposition 0 (Hyperbolic CS Decomposition (Stewart and Dooren, 2005)).

Let $\mathbf{Q}$ be $J$-orthogonal and assume that $q\leq p.$ Then there are
orthogonal matrices $\mathbf{U}_{1},\mathbf{V}_{1}\in\mathbb{R}^{p\times p}$
and $\mathbf{U}_{2},\mathbf{V}_{2}\in\mathbb{R}^{q\times q}$ s.t.

(4) $\mathbf{Q}=\left[\begin{array}[]{cc}\mathbf{U}_{1}&\mathbf{0}\\\
\mathbf{0}&\mathbf{U}_{2}\end{array}\right]\left[\begin{array}[]{ccc}\mathbf{C}&\mathbf{0}&\mathbf{S}\\\
\mathbf{0}&I_{p-q}&\mathbf{0}\\\
\mathbf{S}&\mathbf{0}&\mathbf{C}\end{array}\right]\left[\begin{array}[]{cc}\mathbf{V}_{1}^{T}&\mathbf{0}\\\
\mathbf{0}&\mathbf{V}_{2}^{T}\end{array}\right],$

where
$\mathbf{C}=\operatorname{diag}\left(c_{1},\ldots,c_{q}\right),\mathbf{S}=\operatorname{diag}\left(s_{1},\ldots,s_{q}\right)$
and $\mathbf{C}^{2}-\mathbf{S}^{2}=\mathbf{I}_{q}$. For cases where $q>p$, the
decomposition can be defined analogously. For simplicity, we only consider
$q\leq p$.

Geometrically, the $J$-orthogonal matrix is decomposed into various geometric
operators. The orthogonal matrices $\mathbf{U}_{1},\mathbf{V}_{1}$ represent
circular rotation or reflection (depending on their determinant) 111Depending
on the determinant, a orthogonal matrix $\mathbf{U}$ denotes a rotation iff
$\operatorname{det}(\mathbf{U})=1$ or a reflection iff
$\operatorname{det}(\mathbf{U})=-1$ in the space dimension, while
$\mathbf{U}_{2},\mathbf{V}_{2}$ represent circular rotation or reflection in
the time dimension. The intermediate matrix that is uniquely determined by
$\mathbf{C},\mathbf{S}$, denotes a hyperbolic rotation (analogous to the
”circular rotation”) across the space and time dimensions. Fig. 3 shows a
$2$-dimensional example of circular rotation and hyperbolic rotation.

It is worth noting that both circular rotation/reflection and hyperbolic
rotation are important operations for KG embeddings. On the one hand, circular
rotations/reflections are able to model complex relational patterns including
inversion, composition, symmetry, or anti-symmetry. Besides, these relational
patterns usually form some non-hierarchies (e.g., cycles). Hence, circular
rotations/reflections inherently encode non-hierarchical graph structures.
Hyperbolic rotation, on the other hand, is able to model hierarchies, i.e., by
connecting entities at different levels of hierarchies. Therefore, the
decomposition in proposition 1 shows that $J$-orthogonal transformation is
powerful for representing both relational patterns and graph structures.

Figure 3. A two-dimensional example of circular rotation (left) and hyperbolic
rotation (right), where $\theta$ is the angle of rotations.

###  3.2. Relation Parameterization

In light of this, we now parameterize circular rotation/reflection and
hyperbolic rotation, respectively.

####  3.2.1. Circular Rotation/Reflection.

Parameterizing circular rotation or reflection via orthogonal matrices is non-
trivial and there are some _trivialization_ approaches such as using Cayley
Transform (Shepard et al., 2015). However, such parameterization requires
$\mathcal{O}(d^{2})$ parameter complexity. To simplify the complexity, we
consider Given transformations denoted by $2\times 2$ matrices. Suppose the
number of dimension $p,q$ are even, circular rotation and reflection can be
denoted by block-diagonal matrices of the form, given as

(5)
$\begin{array}[]{c}\operatorname{\mathbf{Rot}}\left(\Theta_{r}\right)=\operatorname{diag}\left(\mathbf{G}^{+}\left(\theta_{r,1}\right),\ldots,\mathbf{G}^{+}\left(\theta_{r,\frac{p+q}{2}}\right)\right)\\\
\operatorname{\mathbf{Ref}}\left(\Phi_{r}\right)=\operatorname{diag}\left(\mathbf{G}^{-}\left(\phi_{r,1}\right),\ldots,\mathbf{G}^{-}\left(\phi_{r,\frac{p+q}{2}}\right)\right)\\\
\text{where}\quad\mathbf{G}^{\pm}(\theta):=\left[\begin{array}[]{cc}\cos(\theta)&\mp\sin(\theta)\\\
\sin(\theta)&\pm\cos(\theta)\end{array}\right]\end{array},$

where
$\Theta_{r}:=\left(\theta_{r,i}\right)_{i\in\left\\{1,\ldots\frac{p+q}{2}\right\\}}$
and
$\Phi_{r}:=\left(\phi_{r,i}\right)_{i\in\left\\{1,\ldots\frac{p+q}{2}\right\\}}$
are relation-specific parameters.

Although circular rotation is theoretically able to infer symmetric patterns
(Wang et al., 2021a) (i.e., by setting rotation angle $\theta=\pi$ or
$\theta=0$), circular reflection can more effectively represent symmetric
relations since their second power is the identity. AttH (Wang et al., 2021a)
combines circular rotations and circular reflections by using an attention
mechanism learned in the tangent space, which requires additional parameters.
We also combine circular rotation and circular reflection operators but in a
different way. Since the $J$-orthogonal matrix is decomposed into two
rotation/reflection matrices, we set the first matrix in Eq. (4) to be
circular rotation while the third part to be circular reflection matrices,
given by

(6)
$\small\begin{split}\mathbf{U_{\Theta_{r}}}=\left[\begin{array}[]{cc}\operatorname{\operatorname{\mathbf{Rot}}}\left(\Theta_{r_{p}}\right)&\mathbf{0}\\\
\mathbf{0}&\operatorname{\operatorname{\mathbf{Rot}}}\left(\Theta_{r_{q}}\right)\end{array}\right],\end{split}\quad\begin{split}\mathbf{V_{\Phi_{r}}}=\left[\begin{array}[]{cc}\operatorname{\operatorname{\mathbf{Ref}}}\left(\Phi_{r_{p}}\right)&\mathbf{0}\\\
\mathbf{0}&\operatorname{\operatorname{\mathbf{Ref}}}\left(\Phi_{r_{q}}\right)\end{array}\right]\end{split},$

Clearly, the parameterization of circular rotation and reflection in Eq. (5),
as well as the combination of them in Eq.(6), lose a certain degree of freedom
of $J$-orthogonal transformation. However, it 1) results in a linear
($\mathcal{O}(d)$) memory complexity of relational embeddings; 2)
significantly reduces the risk of overfitting; and 3) is sufficiently
expressive to model complex relational patterns as well as graph structures.
This is similar to many other Euclidean models, such as SimplE (Kazemi and
Poole, 2018), that sacrifice some degree of freedoms of the multiplicative
model (i.e., RESCAL (Nickel et al., 2011)) parameterized by quadratic matrices
while pursuing a linearly complex, less overfitting and highly expressive
relational model. Our ablation studies will show that such combination of
rotation and reflection results in performance gains.

####  3.2.2. Hyperbolic Rotation.

The hyperbolic rotation matrix is parameterized by two diagonal matrices
$\mathbf{C},\mathbf{S}$ that satisfy the condition
$\mathbf{C}^{2}-\mathbf{S}^{2}=\mathbf{I}$. The hyperbolic rotation matrix can
be seen as a generalization of the $2\times 2$ hyperbolic rotation given by
$\left[\begin{array}[]{ll}\cosh(\mu)&\sinh(\mu)\\\
\sinh(\mu)&\cosh(\mu)\end{array}\right]$, where the trigonometric functions
$\sinh$ and $\cosh$ are hyperbolic versions of the $\sin$ and $\cos$
functions. Clearly, it satisfies the condition
$\cosh(\mu)^{2}-\sinh(\mu)^{2}=1$. Analogously, to satisfy the condition
$\mathbf{C}^{2}-\mathbf{S}^{2}=\mathbf{I}$, we parameterize
$\mathbf{C},\mathbf{S}$ by diagonal matrices

(7)
$\displaystyle\mathbf{C}(\mu)=\operatorname{diag}\left(\cosh(\mu_{1}),\ldots,\cosh(\mu_{q})\right),$
(8)
$\displaystyle\mathbf{S}(\mu)=\operatorname{diag}\left(\sinh(\mu_{1}),\ldots,\sinh(\mu_{q})\right),$

where $\mu=(\mu_{1},\cdots,\mu_{q})$ is the parameter of hyperbolic rotation
to learn. Therefore, the hyperbolic rotation matrix can be denoted by

(9)
$\scriptsize\mathbf{H}_{\mu_{r}}=\left[\begin{array}[]{ccc}\operatorname{diag}\left(\cosh(\mu_{r,1}),\ldots,\cosh(\mu_{r,q})\right)&\mathbf{0}&\operatorname{diag}\left(\sinh(\mu_{r,1}),\ldots,\sinh(\mu_{r,q})\right)\\\
\mathbf{0}&I_{p-q}&\mathbf{0},\\\
\operatorname{diag}\left(\sinh(\mu_{r,1}),\ldots,\sinh(\mu_{r,q})\right)&\mathbf{0}&\operatorname{diag}\left(\cosh(\mu_{r,1}),\ldots,\cosh(\mu_{r,q})\right)\end{array}\right],$

Given the parameterization of each component, the final transformation
function of relation $r$ is given by

(10) $f_{r}=\mathbf{U}_{\theta_{r}}\mathbf{H}_{\mu_{r}}\mathbf{V}_{\Phi_{r}}.$

Notably, the combination of circular rotation/reflection and hyperbolic
rotation covers various kinds of geometric transformations in the
ultrahyperbolic manifold, including circular, elliptic, parabolic, and
hyperbolic transformations (See Fig. 2(a)). Hence, our relational embedding is
able to work with all corresponding geometrical spaces.

###  3.3. Objective and Manhattan-like Distance

####  3.3.1. Objective Function.

Given $f_{r}$ and entity embeddings $e$, we design a score function for each
triplet $(h,r,t)$ as

(11)
$s(h,r,t)=-d_{\mathbf{U}}^{2}\left(f_{r}\left(\mathbf{e}_{h}\right),\mathbf{e}_{t}\right)+b_{h}+b_{t}+\delta,$

where
$f_{r}\left(\mathbf{e}_{h}\right)=\mathbf{U}_{\theta_{r}}\mathbf{H}_{\mathbf{\mu}_{r}}\mathbf{V}_{\Phi_{r}}\mathbf{e_{h}}$,
and $\mathbf{e}_{h},\mathbf{e}_{t}\in\mathbb{U}^{p,q}$ are the embeddings of
head entity $h$ and tail entity $t$, $b_{h},b_{t}\in\mathbf{R}^{d}$ are
entity-specific biases, and each bias defines an entity-specific _sphere of
influence_ (Balazevic et al., 2019) surrounding the center point. $\delta$ is
a global margin hyper-parameter. $d_{\mathbb{U}}(\cdot)$ is a function that
quantifies the nearness/distance between two points in the ultrahyperbolic
manifold.

####  3.3.2. Manhattan-like Distance.

Defining a proper distance $d_{\mathbb{U}}(\cdot)$ in the ultrahyperbolic
manifold is non-trivial. Different from Riemannian manifolds that are
geodesically connected, ultrahyperbolic manifolds are not geodesically
connected, and there exist _broken cases_ in which the geodesic distance is
not defined (Law and Stam, 2020). Some approximation approaches (Law and Stam,
2020; Xiong et al., 2021) are proposed and satisfy some of the axioms of a
classic metric (e.g., symmetric premetric). However, these distances suffer
from the lack of the identity of indiscernibles, that is, one may have
$\mathbf{d}_{\mathbb{U}}(\mathbf{x},\mathbf{y})=0$ for some distinct points
$\mathbf{x}\neq\mathbf{y}$. This is not a problem for metric learning that
learns to preserve the pair-wise distances (Law and Stam, 2020; Xiong et al.,
2021). However, our preliminary experiments find that the geodesic distance
lacks the identity of indiscernibles results in unstable and non-convergent
training. We conjecture this is due to the fact that the target of KG
embedding is different from the graph embedding aiming at preserving pair-wise
distance. KG embedding aims at satisfying
$f_{r}(\mathbf{e}_{h})\approx\mathbf{e}_{t}$ for each positive triple
$(h,r,t)$ while not for negative triples. Hence, we need to retain the
_identity of indiscernibles_ , that is,
$\mathbf{d}_{\mathbb{U}}(\mathbf{x},\mathbf{y})=0\Leftrightarrow\mathbf{x}=\mathbf{y}$.

To address this issue, we propose a novel Manhattan-like distance function,
which is defined by a composition of a spherical distance and a hyperbolic
distance. Fig. 2 shows the Manhattan-like distance. Formally, given two points
$\mathbf{x},\mathbf{y}\in\mathbb{U}^{p,q}$, we first define a projection
$\rho_{\mathbf{x}}(\mathbf{y})$ of $\mathbf{y}$ on the _circular conic
section_ crossing $\mathbf{x}$, such that $\rho_{\mathbf{x}}(\mathbf{y})$ and
$\mathbf{x}$ share the same space dimension while
$\rho_{\mathbf{x}}(\mathbf{y})$ and $y$ lie on a hyperbolic subspace.

(12)
$\rho_{\mathbf{x}}(\mathbf{y})=\left(\begin{array}[]{c}\mathbf{\mathbf{x}_{p}}\\\
\alpha\mathbf{y}_{q}\frac{\|x_{p}\|}{\|y_{p}\|}\end{array}\right),$

This projection makes that $\mathbf{x}$ and $\rho_{\mathbf{x}}(\mathbf{y})$
are connected by a purely space-like geodesic while
$\rho_{\mathbf{x}}(\mathbf{y}),\mathbf{y}$ are connected by a purely time-like
geodesic. The distance function of $\mathbb{U}$ hence can be defined as a
Manhattan-like distance, i.e., the sum of the two distances, given as

(13) $\displaystyle d_{\mathbb{U}}(\mathbf{x},\mathbf{y})=\min\\{$
$\displaystyle
d_{\mathbb{S}}(\mathbf{y},\rho_{\mathbf{y}}(\mathbf{x}))+d_{\mathbb{H}}(\rho_{\mathbf{y}}(\mathbf{x}),\mathbf{x}),$
(14) $\displaystyle
d_{\mathbb{S}}(\mathbf{x},\rho_{\mathbf{x}}(\mathbf{y}))+d_{\mathbb{H}}(\rho_{\mathbf{x}}(\mathbf{y}),\mathbf{y})\\},$

where $d_{\mathbb{S}}$ and $d_{\mathbb{H}}$ are spherical and hyperbolic
distances, respectively, which are well-defined and maintain the identity of
indiscernibles.

###  3.4. Optimization

For each triplet $(h,r,t)$, we create $k$ negative samples by randomly
corrupting its head or tail entity. The probability of a triple is calculated
as $p=\sigma(s(h,r,t))$ where $\sigma(.)$ is a sigmoid function. We minimize
the binary cross entropy loss, given as

(15) $\mathcal{L}=-\frac{1}{N}\sum_{i=1}^{N}\left(\log
p^{(i)}+\sum_{j=1}^{k}\log\left(1-\tilde{p}^{(i,j)}\right)\right),$

where $p^{(i)}$ and $\tilde{p}^{(i,j)}$ are the probabilities for positive and
negative triplets respectively, and $N$ is the number of samples.

Notably, directly optimizing the embeddings in ultrahyperbolic manifold is
challenging. The issue is caused by the fact that there exist some points that
cannot be connected by a geodesic in the manifold (hence no tangent direction
for gradient descent). One way to sidestep the problem is to define entity
embeddings in the Euclidean space and use a _diffeomorphism_ to map the points
into the manifold. In particular, we consider the following diffeomorphism.

###### Theorem 2.

[Diffeomorphism (Xiong et al., 2021)] For any point
$\mathbf{x}\in\mathbb{U}_{\alpha}^{p,q}$, there exists a diffeomorphism
$\psi:\mathbb{U}_{\alpha}^{p,q}\rightarrow\mathbb{R}^{p}\times\mathbb{S}_{\alpha}^{q}$
that maps $\mathbf{x}$ into the product manifolds of a sphere and the
Euclidean space. The mapping and its inverse are given by

(16) $\psi(\mathbf{x})=\left(\begin{array}[]{c}\mathbf{s}\\\
\alpha\frac{\mathbf{t}}{\|\mathbf{t}\|}\end{array}\right),\quad\psi^{-1}(\mathbf{z})=\left(\begin{array}[]{c}\mathbf{v}\\\
\frac{\sqrt{\alpha^{2}+\|\mathbf{v}\|^{2}}}{\alpha}\mathbf{u}\end{array}\right)\text{,
}$

where $\mathbf{x}=\left(\begin{array}[]{c}\mathbf{s}\\\
\mathbf{t}\end{array}\right)\in\mathbb{U}_{\alpha}^{p,q}$ with
$\mathbf{s}\in\mathbb{R}^{p}$ and $\mathbf{t}\in\mathbb{R}_{*}^{q}$.
$\mathbf{z}=\left(\begin{array}[]{c}\mathbf{v}\\\
\mathbf{u}\end{array}\right)\in\mathbb{R}^{p}\times\mathbb{S}_{\alpha}^{q}$
with $\mathbf{v}\in\mathbb{R}^{p}$ and $\mathbf{u}\in\mathbb{S}_{\alpha}^{q}$.

With these mappings, any vector
$\mathbf{x}\in\mathbb{R}^{p}\times\mathbb{R}_{*}^{q}$ can be mapped to
$\mathbb{U}_{\alpha}^{p,q}$ by a double projection
$\varphi=\psi^{-1}\circ\psi$. Note that since the diffeomorphism is
differential and bijective, the canonical chain rule can be exploited to
perform standard gradient descent optimization.

##  4\. Theoretical Analysis

In this section, we provide some theoretical analyses of UltraE and some
related approaches.

###  4.1. Complexity Analysis

To make the model scalable to the size of the current KGs and keep up with
their growth, a KG embedding model should have linear time and parameter
(space) complexity (Bordes et al., 2013a; Kazemi and Poole, 2018). In our
case, the number of relation parameters of circular rotation, circular
reflection, and hyperbolic rotation grows linearly with the dimensionality
given by $p+q$. The total number of parameters is then
$\mathcal{O}((N_{e}+N_{r})\times d)$, where $N_{e}$ and $N_{r}$ are the
numbers of entities and relations and $d=p+q$ is the embedding dimensionality.
Similar to TransE (Bordes et al., 2013b) and RotH (Chami et al., 2020), UltraE
has time complexity $\mathcal{O}(d)$.

###  4.2. Connections with Hyperbolic Methods

UltraE has close connections with some existing hyperbolic KG embedding
methods, including HyboNet (Chen et al., 2021), RotH/RefH (Chami et al.,
2020), and MuRP (Balazevic et al., 2019). To show this, we first introduce
Lorentz transformation.

###### Definition 0.

Lorentz transformation is a pseudo-orthogonal transformation with signature
$(p,1)$.

HyboNet (Chen et al., 2021) embeds entities as points in a Lorentz space and
models relations as Lorentz transformations. According to Definition 1, we
have the following proposition.

###### Proposition 0.

UltraE, if parameterized by a full $J$-orthogonal matrix, generalizes HyboNet.

That is, HyboNet is the case of UltraE (with full $J$-orthogonal matrix
parameterization) where $q=1$.

By exploiting the polar decomposition (Ratcliffe et al., 1994), a Lorentz
transformation matrix $\mathbf{T}$ can be decomposed into
$\mathbf{T}=\mathbf{R}_{\mathbf{U}}\mathbf{R}_{\mathbf{b}}$, where

(17) $\mathbf{R_{U}}=\left[\begin{array}[]{cc}\mathbf{U}&\mathbf{0}\\\
\mathbf{0}&1\end{array}\right],\mathbf{R_{b}}=\left[\begin{array}[]{cc}\left(\mathbf{I}+\mathbf{b}\mathbf{b}^{\top}\right)^{\frac{1}{2}}&\mathbf{b}^{\top}\\\
\mathbf{b}&\sqrt{1+\|\mathbf{b}\|_{2}^{2}}\end{array}\right],$

where $\mathbf{R_{U}}$ is an orthogonal matrix. In Lorentz geometry,
$\mathbf{R_{U}}$ and $\mathbf{R_{b}}$ are called Lorentz rotation and Lorentz
boost, respectively. $\mathbf{R_{U}}$ represents rotation or reflection in
space dimension (without changing the time dimension), while $\mathbf{R_{b}}$
denotes a hyperbolic rotation across the time dimension and each space
dimension. (Tabaghi and Dokmanic, 2021) established an equivalence between
Lorentz boost and Möbius addition (or hyperbolic translation). Hence, HyboNet
inherently models each relation as a combination of a rotation/reflection and
a hyperbolic translation.

RotH/RefH (Chami et al., 2020), interestingly, also models each relation as a
combination of a rotation/reflection and a hyperbolic translation that is
implemented by Möbius addition. Hence, HyboNet subsumes RotH/RefH,222Note that
RotH/RefH consider Poincaré Ball while HyboNet considers Lorentz model. The
subsumption still holds since Poincaré Ball is isometric to the Lorentz model.
where the equivalence cannot hold because the rotation/reflection of RotH/RefH
is parameterized by the Givens rotation/reflection (Chami et al., 2020).

MuRP (Balazevic et al., 2019) models relations as a combination of Möbius
multiplication (with diagonal matrix) and Möbius addition. Note that (Chen et
al., 2021) established a fact that a Lorentz rotation is equivalent to Möbius
multiplication, and (Tabaghi and Dokmanic, 2021) proved that Lorentz boost is
equivalent to Möbius addition. Hence, HyboNet subsumes MuRP, where the
equivalence cannot hold because the Möbius multiplication in MuRP is
parameterized by a diagonal matrix.

To sum up, UltraE generalizes HyboNet to allow for arbitrary signature
$(p,q)$, while HyboNet subsumes RotH/RefH and MuRP.

Table 1. The statistics of KGs, where $\xi_{G}$ measures the tree-likeness (the lower the $\xi_{G}$ is, the more tree-like the KG is). Dataset | #entities | #relations | #triples | $\xi_{G}$
---|---|---|---|---
WN18RR | $41\mathbf{k}$ | 11 | $93\mathbf{k}$ | $-2.54$
FB15k-237 | $15\mathbf{k}$ | 237 | $310\mathbf{k}$ | $-0.65$
YAGO3-10 | $123\mathbf{k}$ | 37 | $1\mathbf{M}$ | $-0.54$

###  4.3. Inference Patterns

UltraE can naturally infer relation patterns including symmetry, anti-
symmetry, inversion and composition. As discussed above, the defined relation
transformation $f_{r}=U_{\theta_{r}}B_{\mu_{r}}V_{\Phi_{r}}$ consists of three
operations, including a circular rotation, a hyperbolic rotation, and a
circular reflection. The three operation matrices can all be identified as
identity matrices. Therefore, there are several different combinations of
parameter settings to meet the above inferred requirements, demonstrating the
comprehensive capability of the proposed UltraE on encoding relational
patterns. For the sake of proof, we assume $B_{\mu_{r}}$ is an identity matrix
$\mathbf{I}$, and $\Theta_{r},\Phi_{r}\in[-\pi,\pi)$.

###### Proposition 0.

Let $r$ be a symmetric relation such that for each triple $(e_{h},r,e_{t})$,
its symmetric triple $(e_{t},r,e_{h})$ also holds. This symmetric property of
$r$ can be encoded into UltraE.

###### Proof.

If $r$ is a symmetric relation, by taking the $B_{\mathbf{b}_{r}}=\mathbf{I}$
and $U_{\Theta_{r}}=\mathbf{I}$, we have

$\displaystyle\mathbf{e}_{h}=f_{r}\left(\mathbf{e}_{t}\right)=V_{\Phi_{r}}\mathbf{e}_{t},\
\mathbf{e}_{t}=f_{r}\left(\mathbf{e}_{h}\right)=V_{\Phi_{r}}\mathbf{e}_{h}\Rightarrow
V_{\Phi_{r}}^{2}=\mathbf{I}$

which holds true when $\Phi_{r}=0$ or $\Phi_{r}=-\pi$. ∎

###### Proposition 0.

Let $r$ be an anti-symmetric relation such that for each triple
$(e_{h},r,e_{t})$, its symmetric triple $(e_{t},r,e_{h})$ is not true. This
anti-symmetric property of $r$ can be encoded into UltraE.

###### Proof.

If $r$ is an anti-symmetric relation, by taking the
$B_{\mathbf{b}_{r}}=\mathbf{I}$ and $U_{\Theta_{r}}=\mathbf{I}$, we have

$\displaystyle\mathbf{e}_{h}=f_{r}\left(\mathbf{e}_{t}\right)=V_{\Phi_{r}}\mathbf{e}_{t},\
\mathbf{e}_{t}=f_{r}\left(\mathbf{e}_{h}\right)=V_{\Phi_{r}}\mathbf{e}_{h}\Rightarrow\mathbf{e}_{h}=\mathbf{e}_{t}$

which holds true when $\Phi_{r}\neq 0$ and $\Phi_{r}\neq-\pi$. ∎

###### Proposition 0.

Let $r_{1}$ and $r_{2}$ be inverse relations such that for each triple
$(e_{h},r_{1},e_{t})$, its inverse triple $(e_{t},r_{2},e_{h})$ is also true.
This inverse property of $r_{1}$ and $r_{2}$ can be encoded into UltraE.

###### Proof.

If $r_{1}$ and $r_{2}$ are inverse relations, by taking the
$B_{\mathbf{b}_{r_{1}}}=B_{\mathbf{b}_{r_{2}}}=\mathbf{I}$ and
$V_{\Phi_{r_{1}}}=V_{\Phi_{r_{2}}}=\mathbf{I}$, we have

$\displaystyle\mathbf{e}_{h}=f_{r_{1}}\left(\mathbf{e}_{t}\right)=U_{\Theta_{r_{1}}}\mathbf{e}_{t},\
\mathbf{e}_{t}=f_{r_{2}}\left(\mathbf{e}_{h}\right)=U_{\Theta_{r_{2}}}\mathbf{e}_{h}\Rightarrow
U_{\Theta_{r_{1}}}U_{\Theta_{r_{2}}}=\mathbf{I}$

which holds true when $\Theta_{r_{1}}+\Theta_{r_{2}}=0$. ∎

###### Proposition 0.

Let relation $r_{1}$ be composed of $r_{2}$ and $r_{3}$ such that triple
$(e_{h},r_{1},e_{t})$ exists when $(e_{h},r_{2},e_{t})$ and
$(e_{h},r_{3},e_{t})$ exist. This composition property can be encoded into
UltraE.

###### Proof.

If $r_{1}$ is composed of $r_{2}$ and $r_{3}$, by taking the
$B_{\mathbf{b}_{r_{1}}}=B_{\mathbf{b}_{r_{2}}}=\mathbf{I}$ and
$V_{\Phi_{r_{1}}}=V_{\Phi_{r_{2}}}=\mathbf{I}$, we have

(18)
$\displaystyle\mathbf{e}_{h}=f_{r_{1}}\left(\mathbf{e}_{t}\right)=U_{\Theta_{r_{1}}}\mathbf{e}_{t},\
\mathbf{e}_{h}=f_{r_{2}}\left(\mathbf{e}_{t}\right)=U_{\Theta_{r_{2}}}\mathbf{e}_{t},$
$\displaystyle\mathbf{e}_{h}=f_{r_{3}}\left(\mathbf{e}_{t}\right)=U_{\Theta_{r_{3}}}\mathbf{e}_{t}\
\Rightarrow U_{\Theta_{r_{1}}}=U_{\Theta_{r_{2}}}U_{\Theta_{r_{3}}}$

which holds true when $\Theta_{r_{1}}=\Theta_{r_{2}}+\Theta_{r_{3}}$ or
$\Theta_{r_{1}}=\Theta_{r_{2}}+\Theta_{r_{3}}+2\pi$ or
$\Theta_{r_{1}}=\Theta_{r_{2}}+\Theta_{r_{3}}-2\pi$. ∎

Table 2. Link prediction results (%) on WN18RR, FB15k-237 and YAGO3-10 for low-dimensional embeddings ($d=32$) in the filtered setting. The first group of models are Euclidean models, the second groups are non-Euclidean models and MuRMP is a mixed-curvature baseline. RotatE, MuRE, MuRP, RotH, RefH and AttH results are taken from (Chami et al., 2020). RotatE results are reported without self-adversarial negative sampling for fair comparison. The best score and best baseline are in bold and underlined, respectively.  | WN18RR | FB15k-237 | YAGO3-10
---|---|---|---
Model | MRR | H@ 1 | H@3 | H@10 | MRR | H@1 | H@3 | H@10 | MRR | H@1 | H@3 | H@10
TransE | 36.6 | 27.4 | 43.3 | 51.5 | 29.5 | 21.0 | 32.2 | 46.6 | - | - | - | -
RotatE | 38.7 | 33.0 | 41.7 | 49.1 | 29.0 | 20.8 | 31.6 | 45.8 | - | - | - | -
ComplEx | 42.1 | 39.1 | 43.4 | 47.6 | 28.7 | 20.3 | 31.6 | 45.6 | 33.6 | 25.9 | 36.7 | 48.4
QuatE | 42.1 | 39.6 | 43.0 | 46.7 | 29.3 | 21.2 | 32.0 | 46.0 | - | - | - | -
5$\star$E | 44.9 | 41.8 | 46.2 | 51.0 | 32.3 | 24.0 | 35.5 | 50.1 | - | - | - | -
MuRE | 45.8 | 42.1 | 47.1 | 52.5 | 31.3 | 22.6 | 34.0 | 48.9 | 28.3 | 18.7 | 31.7 | 47.8
MuRP | 46.5 | 42.0 | 48.4 | 54.4 | 32.3 | 23.5 | 35.3 | 50.1 | 23.0 | 15.0 | 24.7 | 39.2
RotH | 47.2 | 42.8 | 49.0 | 55.3 | 31.4 | 22.3 | 34.6 | 49.7 | 39.3 | 30.7 | 43.5 | 55.9
RefH | 44.7 | 40.8 | 46.4 | 51.8 | 31.2 | 22.4 | 34.2 | 48.9 | 38.1 | 30.2 | 41.5 | 53.0
AttH | 46.6 | 41.9 | 48.4 | 55.1 | 32.4 | 23.6 | 35.4 | 50.1 | 39.7 | 31.0 | 43.7 | 56.6
MuRMP | 47.0 | 42.6 | 48.3 | 54.7 | 31.9 | 23.2 | 35.1 | 50.2 | 39.5 | 30.8 | 42.9 | 56.6
UltraE (q=2) | 48.1 | 43.4 | 50.0 | 55.4 | 33.1 | 24.1 | 35.5 | 50.3 | 39.5 | 31.2 | 43.9 | 56.8
UltraE (q=4) | 48.8 | 44.0 | 50.3 | 55.8 | 33.4 | 24.3 | 36.0 | 51.0 | 40.0 | 31.5 | 44.3 | 57.0
UltraE (q=6) | 48.3 | 42.5 | 49.1 | 55.5 | 33.8 | 24.7 | 36.3 | 51.4 | 40.5 | 31.8 | 44.7 | 57.2
UltraE (q=8) | 47.5 | 42.3 | 49.0 | 55.1 | 32.6 | 24.6 | 36.2 | 51.0 | 39.4 | 31.3 | 43.4 | 56.5

##  5\. Empirical Evaluation

In this section, we evaluate the performance of UltraE on link prediction in
three KGs that contain both hierarchical and non-hierarchical relations. We
systematically study the major components of our framework and show that (1)
UltraE outperforms Euclidean and non-Euclidean baselines on embedding KGs with
heterogeneous topologies, especially in low-dimensional cases (Sec. 5.2); (2)
the signature of embedding space works as a knob for controlling the geometry,
and hence influences the performance of UltraE (Sec. 5.3.2); (3) UltraE is
able to improve the embeddings of relations with heterogeneous topologies
(Sec. 5.3.3); and (4) the combination of rotation and reflection outperforms a
single operator (Sec. 5.3.4).

###  5.1. Experiment Setup

####  5.1.1. Dataset.

We use three standard benchmarks: WN18RR (Bordes et al., 2013b), a subset of
WordNet containing $11$ lexical relationships, FB15k-237 (Bordes et al.,
2013b), a subset of Freebase containing general world knowledge, and YAGO3-10
(Mahdisoltani et al., 2015), a subset of YAGO3 containing information of
relationships between people. All three datasets contain hierarchical (e.g.,
partOf) and non-hierarchical (e.g., similarTo) relations, and some of which
contain relational patterns like symmetry (e.g., isMarriedTo). For each KG, we
follow the standard data augmentation protocol (Lacroix et al., 2018) and the
same train/valid/test splitting as used in (Lacroix et al., 2018) for fair
comparision. Following the previous work (Chami et al., 2020), we use the
global graph curvature (Gu et al., 2019) to measure the geometric properties
of the datasets. The statistics of datasets are summarized in Table 1. As we
can see, all datasets are globally hierarchical (i.e., the curvature is
negative) but none of which is a pure tree structure. Comparatively, WN18RR is
more hierarchical than FB15k-237 and YAGO3-10 since it has a smaller global
graph curvature.

Table 3. Link prediction results (%) on WN18RR, FB15k-237 and YAGO3-10 for high-dimensional embeddings (best for $d\in\\{200,400,500\\}$) in the filtered setting. RotatE, MuRE, MuRP, RotH, RefH and AttH results are taken from (Chami et al., 2020). RotatE results are reported without self-adversarial negative sampling. The best score and best baseline are in bold and underlined, respectively. | WN18RR | FB15k-237 | YAGO3-10
---|---|---|---
Model | MRR | H@ 1 | H@3 | H@10 | MRR | H@1 | H@3 | H@10 | MRR | H@1 | H@3 | H@10
TransE | 48.1 | 43.3 | 48.9 | 57.0 | 34.2 | 24.0 | 37.8 | 52.7 | - | - | - | -
DistMult | 43.0 | 39.0 | 44.0 | 49.0 | 24.1 | 15.5 | 26.3 | 41.9 | 34.0 | 24.0 | 38.0 | 54.0
RotatE | 47.6 | 42.8 | 49.2 | 57.1 | 33.8 | 24.1 | 37.5 | 53.3 | 49.5 | 40.2 | 55.0 | 67.0
ComplEx | 48.0 | 43.5 | 49.5 | 57.2 | 35.7 | 26.4 | 39.2 | 54.7 | 56.9 | 49.8 | 60.9 | 70.1
QuatE | 48.8 | 43.8 | 50.8 | 58.2 | 34.8 | 24.8 | 38.2 | 55.0 | - | - | - | -
5$\star$E | 50.0 | 45.0 | 51.0 | 59.0 | 37.0 | 28.0 | 40.0 | 56.0 | - | - | - | -
MuRE | 47.5 | 43.6 | 48.7 | 55.4 | 33.6 | 24.5 | 37.0 | 52.1 | 53.2 | 44.4 | 58.4 | 69.4
MuRP | 48.1 | 44.0 | 49.5 | 56.6 | 33.5 | 24.3 | 36.7 | 51.8 | 35.4 | 24.9 | 40.0 | 56.7
RotH | 49.6 | 44.9 | 51.4 | 58.6 | 34.4 | 24.6 | 38.0 | 53.5 | 57.0 | 49.5 | 61.2 | 70.6
RefH | 46.1 | 40.4 | 48.5 | 56.8 | 34.6 | 25.2 | 38.3 | 53.6 | 57.6 | 50.2 | 61.9 | 71.1
AttH | 48.6 | 44.3 | 49.9 | 57.3 | 34.8 | 25.2 | 38.4 | 54.0 | 56.8 | 49.3 | 61.2 | 70.2
MuRMP | 48.1 | 44.1 | 49.6 | 56.9 | 35.8 | 27.3 | 39.4 | 56.1 | 49.5 | 44.8 | 59.1 | 69.8
UltraE (q=20) | 48.5 | 44.2 | 50.0 | 57.3 | 34.9 | 25.1 | 38.5 | 54.1 | 56.9 | 49.5 | 61.0 | 70.3
UltraE (q=40) | 50.1 | 45.0 | 51.5 | 59.2 | 35.1 | 27.5 | 40.0 | 56.0 | 57.5 | 49.8 | 62.0 | 70.8
UltraE (q=80) | 49.7 | 44.8 | 51.2 | 58.5 | 36.8 | 27.6 | 40.0 | 56.3 | 58.0 | 50.6 | 62.3 | 71.1
UltraE (q=160) | 48.6 | 44.5 | 50.3 | 57.4 | 35.4 | 26.0 | 39.0 | 55.5 | 57.0 | 49.5 | 61.8 | 70.5

####  5.1.2. Evaluation protocol.

Two popular ranking-based metrics are reported: 1) mean reciprocal rank (MRR),
the mean of the inverse of the true entity ranking in the prediction; and 2)
hit rate $H@K$ ($K\in\\{1,3,10\\}$), the percentage of the correct entities
appearing in the top $K$ ranked entities. As a standard, we report the metrics
in the filtered setting (Bordes et al., 2013b), i.e., when calculating the
ranking during evaluation, we filter out all true triples in the training set,
since predicting a low rank for these triples should not be penalized.

####  5.1.3. Hyperparameters.

For each KG, we explore batch size $\in\\{500,1000\\}$, global margin
$\in\\{2,4,6,8\\}$ and learning rate $\in\\{3e-3,5e-3,7e-3\\}$ in the
validation set. The negative sampling size is fixed to $50$. The maximum
number of epochs is set to $1000$. The radius of curvature $\alpha$ is fixed
to $1$ since our model does not need relation-specific curvatures but is able
to learn relation-specific mappings in the ultrahyperbolic manifold. The
signature of the product manifold is set as the same as (Wang et al., 2021b).

####  5.1.4. Baselines.

Our baselines are divided into two groups:

  * •

Euclidean models. 1) TransE (Bordes et al., 2013b), the first translational
model; 2) RotatE (Sun et al., 2019), a rotation model in a complex space; 3)
DistMult (Yang et al., 2015), a multiplicative model with a diagonal
relational matrix; 4) ComplEx (Trouillon et al., 2016), an extension of
DisMult in a complex space; 5) QuatE (Cao et al., 2021), a generalization of
complex KG embedding in a hypercomplex space ; 6) 5$\star$E that models a
relation as five transformation functions; 7) MuRE (Balazevic et al., 2019), a
Euclidean model with a diagonal relational matrix.

  * •

Non-Euclidean models. 1) MuRP (Balazevic et al., 2019), a hyperbolic model
with a diagonal relational matrix; 2) MuRS, a spherical analogy of MuRP; 3)
RotH/RefH (Chami et al., 2020), a hyperbolic embedding with rotation or
reflection; 4) AttH (Chami et al., 2020), a combination of RotH and RefH by
attention mechanism; 5) MuRMP (Wang et al., 2021b), a generalization of MuRP
in the product manifold.

We compare UltraE with varied signatures (time dimensions). Since for all KGs,
the hierarchies are much more dominant than cyclicity and we assume that both
space and time dimension are even numbers, we set the time dimension to be a
relatively small value (i.e., $q=2,4,6,8$ and $q=20,40,80,160$ for low-
dimension settings and high-dimension settings, respectively) for comparison.
A full possible setting of time dimension with $q\leq p$ is studied in Sec.
5.3.2.

###  5.2. Overall Results

####  5.2.1. Low-dimensional Embeddings.

Following previous non-Euclidean approaches (Chami et al., 2020), we first
evaluate UltraE in the low dimensional setting ($d=32$). Table 2 shows the
performance of UltraE and the baselines. Overall, it is clear that UltraE with
varying time dimension ($q=2,4,6,8$) improves the performance of all methods.
UltraE, even with only $2$ time dimension, consistently outperforms all
baselines, suggesting that the heterogeneous structure imposed by the pseudo-
Riemannian geometry leads to better representations. In particular, the best
performance of WN18RR is achieved by UltraE ($q=4$) while the best
performances of FB15k-237 and YAGO3-10 are achieved by UltraE ($q=6$). We
believe that this is because WN18RR is more hierarchical than FB15k-237 and
YAGO3-10, validating our conjecture that the number of time dimensions
controls the geometry of the embedding space. Besides, we observed that the
mixed-curvature baseline MuRMP does not consistently improve the hyperbolic
methods. We conjecture that this is because MuRMP cannot properly model
relational patterns.

####  5.2.2. High-dimensional Embeddings

Table 3 shows the results of link prediction in high dimensions (best for
$d\in\\{200,400,500\\}$). Overall, UltraE achieves either better or
competitive results against a variety of other models. In particular, we
observed that there is no significant performance gain among hyperbolic
methods and mixed-curvature methods against Euclidean-based methods. We
conjecture that this is because when the dimension is sufficiently large, both
Euclidean and hyperbolic geometries have sufficient ability to represent
complex hierarchies in KGs. However, UltraE roughly outperforms all compared
approaches, with the only exception of 5$\star$E achieving competitive
results. Again, the performance gain is not as significant as in the low-
dimension cases, which further validates the hypothesis that KG embeddings are
not sensitive to the choice of embedding space with high dimensions. The
additional performance gain might be obtained from the flexibility of
inference of the relational patterns.

Figure 4. The performance (MRR) of various methods on WN18RR, with
$d\in\\{10,16,20,32,50,200,500\\}$. UltraE is implemented with only rotation
and $q=4$. The results of MuRE, MuRS and MuRMP are taken from (Wang et al.,
2021b) with $d\in\\{10,15,20,40,100,200,500\\}$. All results are averaged over
10 runs. Figure 5. The performance (H@10) of UltraE with varied signature
(time dimensions) under the condition of $d=p+q=32,q\leq p$ on WN18RR. The
dashed horizontal lines denote the results of RotH. As $q$ increases, the
performance first increases and starts to decrease after reaching a peak.
Table 4. Comparison of H@10 for WN18RR relations. Higher $\mathbf{Khs}_{G}$
and lower $\xi_{G}$ mean more hierarchical structure. UltraE is implemented by
rotation and with best signature $(4,28)$.

Relation | $\mathbf{Khs}_{G}$ | $\xi_{G}$ | RotE | RotH | UltraE (Rot)
---|---|---|---|---|---
member meronym | 1.00 | -2.90 | 32.0 | 39.9 | 41.3
hypernym | 1.00 | -2.46 | 23.7 | 27.6 | 28.6
has part | 1.00 | -1.43 | 29.1 | 34.6 | 36.0
instance hypernym | 1.00 | -0.82 | 48.8 | 52.0 | 53.2
member of domain region | 1.00 | -0.78 | 38.5 | 36.5 | 43.3
member of domain usage | 1.00 | -0.74 | 45.8 | 43.8 | 50.3
synset domain topic of | 0.99 | -0.69 | 42.5 | 44.7 | 46.3
also see | 0.36 | -2.09 | 63.4 | 70.5 | 73.5
derivationally related form | 0.07 | -3.84 | 96.0 | 96.8 | 97.1
similar to | 0.07 | -1.00 | 100.0 | 100.0 | 100.0
verb group | 0.07 | -0.50 | 97.4 | 97.4 | 98.0

Table 5. Comparison of H@10 on YAGO3-10 relations. UltraE (Rot) and UltraE
(Ref) are implemented by only rotation and reflection, respectively. We choose
the best signature $(6,26)$.

Relation | Anti-symmetric | Symmetric | UltraE (Rot) | UltraE (Ref) | UltraE
---|---|---|---|---|---
hasNeighbor | $\bm{x}$ | $\checkmark$ | 75.3 | 100.0 | 100.0
isMarriedTo | $\bm{x}$ | $\checkmark$ | 94.0 | 94.4 | 100.0
actedIn | $\checkmark$ | $\bm{x}$ | 14.7 | 12.7 | 15.3
hasMusicalRole | $\checkmark$ | $\bm{x}$ | 43.5 | 37.0 | 46.0
directed | $\checkmark$ | $\bm{x}$ | 51.5 | 45.3 | 56.8
graduatedFrom | $\checkmark$ | $\bm{x}$ | 26.8 | 16.3 | 27.5
playsFor | $\checkmark$ | $\bm{X}$ | 67.2 | 64.0 | 66.8
wroteMusicFor | $\bm{\checkmark}$ | $\bm{X}$ | 28.4 | 18.8 | 27.9
hasCapital | $\bm{\checkmark}$ | $\bm{X}$ | 73.2 | 68.3 | 73.2
dealsWith | $\bm{X}$ | $\bm{X}$ | 30.4 | 29.7 | 43.6
isLocatedIn | $\bm{X}$ | $\bm{X}$ | 41.5 | 39.8 | 42.8

###  5.3. Parameter Sensitivity

####  5.3.1. The effect of dimensionality.

To investigate the effect of dimensionality, we conduct experiments on WN18RR
and compare UltraE ($q=4$) against various state-of-the-art counterparts with
varying dimensionality. For a fair comparison with RotH that only considers
rotation, we only use rotation for the implementation of UltraE, denoted by
UltraE (Rot). Fig. 4 shows the results obtained by averaging over 10 runs. It
clearly shows that the mixed-curvature method MuRMP outperforms its
counterparts (MuRE, MuRP) with a single geometry, showcasing the limitation of
a single homogeneous geometry on capturing the intrinsic heterogeneous
structures. However, RotH performs slightly better than MuRMP, especially in
high dimensionality, we conjecture that this is due to the capability of RotH
on inferring relational patterns. UltraE achieves further improvements across
a broad range of dimensions, suggesting the benefits of ultrahyperbolic
manifold for modeling relation-specific geometries as well as inferring
relational patterns.

####  5.3.2. The effect of signature.

We study the influence of the signature on WN18RR by setting a varying number
of time dimensions under the condition of $d=p+q=32,p\geq q$. Fig. 5 shows
that in all three benchmarks, by increasing $q$, the performance grows first
and starts to decline after reaching a peak, which is consistent with our
hypothesis that the signature acts as a knob for controlling the geometric
properties. One might also note that compared with hyperbolic baselines (the
dashed horizontal lines), the performance gain for WN18RR is relatively
smaller than those of FB15k-237 and YAGO3-10. We conjecture that this is
because WN18RR is more hierarchical than FB15k-237 and YAGO3-10, and the
hyperbolic embedding performs already well. This assumption is further
validated by the fact that the best time dimension of WN18RR ($q=4$) is
smaller than that of FB15k-237 and YAGO3-10 ($q=6$).

####  5.3.3. The effect of relation types.

In this part, we investigate the per-relationship performance of UltraE on
WN18RR. Similar to RotE and RotH that only consider rotation, we consider
UltraE (Rot) as before. Two metrics that describe the geometric properties of
each relation are reported, including global graph curvature and Krackhardt
hierarchy score (Chami et al., 2020), for which higher $\mathbf{Khs}_{G}$ and
lower $\xi_{G}$ means more hierarchical. As shown in Table 4, although RotH
outperforms RotE on most of the relation types, the performance is not on par
with RotE on relations ”member of domain region” and ”member of domain usage”.
UltraE (Rot), however, consistently outperforms both RotE and RotH on all
relations, with significant performance gains on relations ”member of domain
region ” and ”member of domain usage ” that RotH fails on. The overall
observation also verifies the flexibility and effectiveness of the proposed
method in dealing with heterogeneous topologies of KGs.

####  5.3.4. The effect of rotation and reflection.

To investigate the role of rotation and reflection, we compare UltraE against
its two variants: UltraE with only rotation (UltraE (Rot)) and UltraE with
only reflection (UltraE (Ref)). Table 5 shows the per-relationship results on
YAGO3-10. We observe that UltraE with rotation performs better on anti-
symmetric relations while UltraE with reflection performs better on symmetric
relations, suggesting that reflection is more suitable for representing
symmetric patterns. On almost all relations including relations that are
neither symmetric nor anti-symmetric, except for ”wroteMusicFor”, UltraE
outperforms both rotation or reflection variants, showcasing that combining
multiple operators can learn more expressive representations.

##  6\. Related Work

###  6.1. Knowledge Graph Embeddings

Recent progress of KG embeddings has been achieved from many perspectives. One
line of works aims at improving the expressivity of relational operations,
from _additive_ operations (Bordes et al., 2013b; Wang et al., 2014; Lin et
al., 2015) to _multiplicative_ operations (Nickel et al., 2011; Yang et al.,
2015; Liu et al., 2017). Among which rotation model (Sun et al., 2019) allows
for better representation of relational patterns such as symmetry, anti-
symmetry, inversion and composition. Another line of work tries to exploit
more expressive embedding space, from Euclidean space to hyperbolic space.
Various hyperbolic KG embeddings are proposed, including MuRP (Balazevic et
al., 2019) that models relation as a combination of Möbius multiplication and
Möbius addition, as well as RotH/RefH (Chami et al., 2020) that models
relations as hyperbolic isometries (rotation/reflection and translation) to
infer relational patterns. RotH/RefH learn relation-specific curvature to
distinguish the geometric characteristics of different relations, but still
cannot tackle the non-hierarchical relations since hyperbolic space is not the
optimal geometry of non-hierarchies. HyboNet (Chen et al., 2021) is a
multiplicative hyperbolic model in Lorentz geometry but requires a quadratic
number of parameters. 5$\star$E (Nayyeri et al., 2021) proposes $5$
transformations (inversion, reflection, translation, rotation, and homothety)
to support multiple graph structures but the embeddings are still learned in
the Euclidean space. Unlike all previous methods that focus on homogeneous
geometric space, our method is learned in the ultrahyperbolic manifold, a
heterogeneous geometric space with multiple kinds of local geometries.

###  6.2. Ultrahyperbolic Embeddings

Some recent works explored the application of ultrahyperbolic or pseudo-
Riemannian geometry in representation learning. Pseudo-Riemannian geometry (or
pseudo-Euclidean space) was first applied to embed non-metric data that
preserves local information (Sun et al., 2015). (Clough and Evans, 2017)
exploited Lorentzian space-time on embedding directed acyclic graphs. More
recently, (Law and Stam, 2020) proposed learning graph embeddings on pseudo-
hyperboloid and provided some necessary geodesic tools, (Sim et al., 2021)
further extended it into directed graph embedding, and (Xiong et al., 2021;
Law, 2021) extended the pseudo-Riemannian embedding to support neural network
operators. However, pseudo-Riemannian geometry has not yet been exploited in
the setting of KG embeddings.

##  7\. Conclusion

This paper proposes UltraE, an ultrahyperbolic KG embedding method in a
pseudo-Riemannian manifold that interleaves hyperbolic and spherical
geometries, allowing for simultaneously modeling multiple hierarchical and
non-hierarchical structures in KGs. We derive a relational embedding by
exploiting the pseudo-orthogonal transformation, which is decomposed into
various geometric operators including circular rotations/reflections and
hyperbolic rotations, allowing for inferring complex relational patterns in
KGs. We propose a Manhattan-like distance that measures the nearness of points
in the ultrahyperbolic manifold. The embeddings are optimized by standard
gradient descent thanks to the differentiable and bijective mapping. We
discuss theoretical connections of UltraE with other hyperbolic methods. On
three standard KG datasets, UltraE outperforms many previous Euclidean and
non-Euclidean counterparts, especially in low-dimensional settings.

## Acknowledgments

The authors thank the International Max Planck Research School for Intelligent
Systems (IMPRS-IS) for supporting Bo Xiong. This project has received funding
from the European Union’s Horizon 2020 research and innovation programme under
the Marie Skłodowska-Curie grant agreement No: 860801.

## References

  * Bai et al. [2021] Yushi Bai, Zhitao Ying, Hongyu Ren, and Jure Leskovec.  Modeling heterogeneous hierarchies with relation-specific hyperbolic cones.  In Advances in Neural Information Processing Systems, volume 34, 2021.
  * Balazevic et al. [2019] Ivana Balazevic, Carl Allen, and Timothy M. Hospedales.  Multi-relational poincaré graph embeddings.  In NeurIPS, pages 4465–4475, 2019.
  * Bordes et al. [2013a] Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko.  Irreflexive and hierarchical relations as translations.  CoRR, abs/1304.7158, 2013.
  * Bordes et al. [2013b] Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko.  Translating embeddings for modeling multi-relational data.  In NIPS, pages 2787–2795, 2013.
  * Cao et al. [2019] Yixin Cao, Xiang Wang, Xiangnan He, Zikun Hu, and Tat-Seng Chua.  Unifying knowledge graph learning and recommendation: Towards a better understanding of user preferences.  In WWW, pages 151–161. ACM, 2019.
  * Cao et al. [2021] Zongsheng Cao, Qianqian Xu, Zhiyong Yang, Xiaochun Cao, and Qingming Huang.  Dual quaternion knowledge graph embeddings.  In AAAI, pages 6894–6902. AAAI Press, 2021.
  * Celebi et al. [2019] Remzi Celebi, Hüseyin Uyar, Erkan Yasar, Özgür Gümüs, Oguz Dikenelli, and Michel Dumontier.  Evaluation of knowledge graph embedding approaches for drug-drug interaction prediction in realistic settings.  BMC Bioinform., 20(1):726, 2019.
  * Chami et al. [2019] Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec.  Hyperbolic graph convolutional neural networks.  In NeurIPS, pages 4869–4880, 2019.
  * Chami et al. [2020] Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré.  Low-dimensional hyperbolic knowledge graph embeddings.  In ACL, pages 6901–6914. Association for Computational Linguistics, 2020.
  * Chen et al. [2021] Weize Chen, Xu Han, Yankai Lin, Hexu Zhao, Zhiyuan Liu, Peng Li, Maosong Sun, and Jie Zhou.  Fully hyperbolic neural networks.  CoRR, abs/2105.14686, 2021.
  * Clough and Evans [2017] James R Clough and Tim S Evans.  Embedding graphs in lorentzian spacetime.  PloS one, 12(11):e0187301, 2017.
  * Gu et al. [2019] Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré.  Learning mixed-curvature representations in product spaces.  In ICLR (Poster). OpenReview.net, 2019.
  * Higham [2003] Nicholas J. Higham.  _J_ -orthogonal matrices: Properties and generation.  SIAM Rev., 45(3):504–519, 2003.
  * Huang et al. [2019] Xiao Huang, Jingyuan Zhang, Dingcheng Li, and Ping Li.  Knowledge graph embedding based question answering.  In WSDM, pages 105–113. ACM, 2019.
  * Kazemi and Poole [2018] Seyed Mehran Kazemi and David Poole.  Simple embedding for link prediction in knowledge graphs.  In NeurIPS, pages 4289–4300, 2018.
  * Lacroix et al. [2018] Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski.  Canonical tensor decomposition for knowledge base completion.  In ICML, volume 80 of Proceedings of Machine Learning Research, pages 2869–2878. PMLR, 2018.
  * Law and Stam [2020] Marc T. Law and Jos Stam.  Ultrahyperbolic representation learning.  In Advances in neural information processing systems, 2020.
  * Law [2021] Marc Law.  Ultrahyperbolic neural networks.  Advances in Neural Information Processing Systems, 34, 2021.
  * Lin et al. [2015] Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu.  Learning entity and relation embeddings for knowledge graph completion.  In AAAI, pages 2181–2187. AAAI Press, 2015.
  * Liu et al. [2017] Hanxiao Liu, Yuexin Wu, and Yiming Yang.  Analogical inference for multi-relational embeddings.  In ICML, volume 70 of Proceedings of Machine Learning Research, pages 2168–2178. PMLR, 2017.
  * Mahdisoltani et al. [2015] Farzaneh Mahdisoltani, Joanna Biega, and Fabian M. Suchanek.  YAGO3: A knowledge base from multilingual wikipedias.  In CIDR. www.cidrdb.org, 2015.
  * Miller [1995] George A. Miller.  Wordnet: A lexical database for english.  Commun. ACM, 38(11):39–41, 1995.
  * Nayyeri et al. [2021] Mojtaba Nayyeri, Sahar Vahdati, Can Aykul, and Jens Lehmann.  5* knowledge graph embeddings with projective transformations.  In AAAI, pages 9064–9072. AAAI Press, 2021.
  * Nickel and Kiela [2017] Maximilian Nickel and Douwe Kiela.  Poincaré embeddings for learning hierarchical representations.  In NIPS, pages 6338–6347, 2017.
  * Nickel et al. [2011] Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel.  A three-way model for collective learning on multi-relational data.  In ICML, pages 809–816. Omnipress, 2011.
  * O’neill [1983] Barrett O’neill.  Semi-Riemannian geometry with applications to relativity.  Academic press, 1983.
  * Ratcliffe et al. [1994] John G Ratcliffe, S Axler, and KA Ribet.  Foundations of hyperbolic manifolds, volume 149.  Springer, 1994.
  * Shepard et al. [2015] Ron Shepard, Scott R Brozell, and Gergely Gidofalvi.  The representation and parametrization of orthogonal matrices.  The Journal of Physical Chemistry A, 119(28):7924–7939, 2015.
  * Sim et al. [2021] Aaron Sim, Maciej Wiatrak, Angus Brayne, Páidí Creed, and Saee Paliwal.  Directed graph embeddings in pseudo-riemannian manifolds.  Thirty-eighth International Conference on Machine Learning, 2021\.
  * Stewart and Dooren [2005] Michael Stewart and Paul Van Dooren.  On the factorization of hyperbolic and unitary transformations into rotations.  SIAM J. Matrix Anal. Appl., 27(3):876–890, 2005.
  * Sun et al. [2015] Ke Sun, Jun Wang, Alexandros Kalousis, and Stéphane Marchand-Maillet.  Space-time local embeddings.  In Advances in Neural Information Processing Systems, pages 100–108, 2015.
  * Sun et al. [2019] Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang.  Rotate: Knowledge graph embedding by relational rotation in complex space.  In ICLR (Poster). OpenReview.net, 2019.
  * Tabaghi and Dokmanic [2021] Puoya Tabaghi and Ivan Dokmanic.  On procrustes analysis in hyperbolic space.  IEEE Signal Process. Lett., 28:1120–1124, 2021.
  * Trouillon et al. [2016] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard.  Complex embeddings for simple link prediction.  In ICML, volume 48 of JMLR Workshop and Conference Proceedings, pages 2071–2080. JMLR.org, 2016.
  * Wang et al. [2014] Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen.  Knowledge graph embedding by translating on hyperplanes.  In AAAI, pages 1112–1119. AAAI Press, 2014.
  * Wang et al. [2021a] Kai Wang, Yu Liu, Dan Lin, and Michael Sheng.  Hyperbolic geometry is not necessary: Lightweight euclidean-based models for low-dimensional knowledge graph embeddings.  In EMNLP (Findings), pages 464–474. Association for Computational Linguistics, 2021.
  * Wang et al. [2021b] Shen Wang, Xiaokai Wei, Cícero Nogueira dos Santos, Zhiguo Wang, Ramesh Nallapati, Andrew O. Arnold, Bing Xiang, Philip S. Yu, and Isabel F. Cruz.  Mixed-curvature multi-relational graph neural network for knowledge graph completion.  In WWW, pages 1761–1771. ACM / IW3C2, 2021.
  * Xiong et al. [2021] Bo Xiong, Shichao Zhu, Nico Potyka, Shirui Pan, Chuan Zhou, and Steffen Staab.  Semi-riemannian graph convolutional networks.  CoRR, abs/2106.03134, 2021.
  * Yang et al. [2015] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng.  Embedding entities and relations for learning and inference in knowledge bases.  In ICLR (Poster), 2015.