# Weak log majorization and determinantal inequalities

Tin-Yau Tam1 1 Department of Mathematics and Statistics, Auburn University,
Auburn, AL 36849, USA<EMAIL_ADDRESS>and  Pingping Zhang2∗ 2 School of
Science
Chongqing University of Posts and Telecommunications
Chongqing, 400065
China<EMAIL_ADDRESS>
###### Abstract.

Denote by $\mathbb{P}_{n}$ the set of $n\times n$ positive definite matrices.
Let $D=D_{1}\oplus\dots\oplus D_{k}$, where
$D_{1}\in\mathbb{P}_{n_{1}},\dots,D_{k}\in\mathbb{P}_{n_{k}}$ with
$n_{1}+\cdots+n_{k}=n$. Partition $C\in\mathbb{P}_{n}$ according to
$(n_{1},\dots,n_{k})$ so that ${\mbox{Diag}\,}C=C_{1}\oplus\dots\oplus C_{k}$.
We prove the following weak log majorization result:

$\lambda(C^{-1}_{1}D_{1}\oplus\cdots\oplus
C^{-1}_{k}D_{k})\prec_{w\,\log}\lambda(C^{-1}D),$

where $\lambda(A)$ denotes the vector of eigenvalues of
$A\in\mathbb{C}_{n\times n}$. The inequality does not hold if one replaces the
vectors of eigenvalues by the vectors of singular values, i.e.,

$s(C^{-1}_{1}D_{1}\oplus\cdots\oplus
C^{-1}_{k}D_{k})\prec_{w\,\log}s(C^{-1}D)$

is not true. As an application, we provide a generalization of a determinantal
inequality of Matic [5, Theorem 1.1]. In addition, we obtain a weak
majorization result which is complementary to a determinantal inequality of
Choi [2, Theorem 2] and give a weak log majorization open question.

###### Key words and phrases:

Positive definite matrices, determinant, weak log majorization, weak
majorization

###### 2010 Mathematics Subject Classification:

15A45

∗Corresponding author.

##  1\. Introduction

Denote by $\mathbb{C}_{n\times n}$ the set of $n\times n$ complex matrices and
$\mathbb{P}_{n}\subset\mathbb{C}_{n\times n}$ the set of $n\times n$ positive
definite matrices. For $A\in\mathbb{C}_{n\times n}$, we denote by $A^{*}$ and
$|A|=(A^{*}A)^{\frac{1}{2}}$ the conjugate transpose and the positive
semidefinite part of $A$, respectively. Given $n\times n$ Hermitian matrices
$A$ and $B$, $A\leq B$ means that $B-A$ is positive semidefinite.

For $x=(x_{1},x_{2},\dots,x_{n})$,
$y=(y_{1},y_{2},\dots,y_{n})\in\mathbb{R}^{n}$, let
$x^{\downarrow}=(x_{[1]},x_{[2]},\dots,x_{[n]})$ denote a rearrangement of the
components of $x$ such that $x_{[1]}\geq x_{[2]}\geq\cdots\geq x_{[n]}$. The
notation $x\leq y$ means that $x_{[i]}\leq y_{[i]},\,\,i=1,\ldots,n.$ We say
that $x$ is weakly majorized by $y$, denoted by $x\prec_{w}y$, if
$\sum_{j=1}^{k}x_{[j]}\leq\sum_{j=1}^{k}y_{[j]}$ for all $1\leq k\leq n$. We
say that $x$ is majorized by $y$, denoted by $x\prec y$, if $x\prec_{w}y$ and
$\sum_{j=1}^{n}x_{j}=\sum_{j=1}^{n}y_{j}$.

Let $\mathbb{R}_{+}$ denote the set of all positive real numbers and
$\mathbb{R}^{n}_{+}=(\mathbb{R}_{+})^{n}$. Given $x,y\in(\mathbb{R}_{+})^{n}$,
we say that $x$ is weakly log-majorized by $y$, written as
$x\prec_{w\,\log}y$, if $\prod_{i=1}^{k}x_{[i]}\leq\prod_{i=1}^{k}y_{[i]}$,
for $k=1,\ldots,n$; $x$ is log-majorized by $y$, denoted by $x\prec_{\log}y$,
if $x\prec_{w\,\log}y$ and $\prod_{j=1}^{n}x_{j}=\prod_{j=1}^{n}y_{j}$.

Let $A\in\mathbb{P}_{n}$. Denote by
$\lambda(A)=(\lambda_{1}(A),\dots,\lambda_{n}(A))\in\mathbb{R}_{+}^{n}$ the
vector of eigenvalues of $A$ and we may arrange the eigenvalues in non-
increasing order $\lambda_{1}(A)\geq\cdots\geq\lambda_{n}(A)$.

Matic [5, Theorem 1.1] proved the following determinantal inequality. Zhang
[8] and Choi [2] gave two different proofs, respectively. We state the theorem
using Choi’s version.

######  Theorem 1.1.

(Matic [5]) Let $C\in\mathbb{P}_{n}$ and $D=D_{1}\oplus\dots\oplus D_{k}$,
where $D_{1}\in\mathbb{P}_{n_{1}},\dots,D_{k}\in\mathbb{P}_{n_{k}}$ with
$n_{1}+\cdots+n_{k}=n$. Partition $C$ according to $(n_{1},\dots,n_{k})$ so
that ${\mbox{Diag}\,}C=C_{1}\oplus\dots\oplus C_{k}$ in which
${\mbox{Diag}\,}C$ is the main block diagonal of $C$. Then

$\det(I_{n_{1}}+C_{1}^{-1}D_{1})\cdots\det(I_{n_{k}}+C_{k}^{-1}D_{k})\leq\det(I_{n}+C^{-1}D).$
(1.1)

In this paper we obtain the following weak log majorization result where $C$
and $D$ are given as in Theorem 1.1:

$\lambda(C^{-1}_{1}D_{1}\oplus\cdots\oplus
C^{-1}_{k}D_{k})\prec_{w\,\log}\lambda(C^{-1}D).$ (1.2)

We note that (1.2) does not hold if one replaces the vectors of eigenvalues by
the vectors of singular values.

We would like to point out that (1.2) is more fundamental than (1.1). In order
to see that we will first derive the following determinantal inequality as an
application of (1.2):

$\det(I_{n_{1}}+(C_{1}^{-1}D_{1})^{p})\cdots\det(I_{n_{k}}+(C_{k}^{-1}D_{k})^{p})\leq\det(I_{n}+(C^{-1}D)^{p}),\quad
p\geq 0,$ (1.3)

which is evidently a generalization of (1.1). We will show by example that
(1.3) is not true when $p<0$.

By looking at (1.3) as a generalization of (1.1), one might ask whether the
following two possible generalizations of (1.1) are true or not:

$\det(I_{n_{1}}+|C_{1}^{-1}D_{1}|^{p})\cdots\det(I_{n_{k}}+|C_{k}^{-1}D_{k}|^{p})\leq\det(I_{n}+|C^{-1}D|^{p}),\quad
p\geq 0,$ (1.4)

and

$\det(I_{n_{1}}+C_{1}^{-p}D_{1}^{p})\cdots\det(I_{n_{k}}+C_{k}^{-p}D_{k}^{p})\leq\det(I_{n}+C^{-p}D^{p}),\quad
p\geq 0.$ (1.5)

Both answers are negative and we will provide a counterexample for both
inequalities.

Choi [2, Theorem 2] obtained the following determinantal inequality:

######  Theorem 1.2.

(Choi [2]) Let $A_{i}\in\mathbb{P}_{n},\,i=1,\dots,m$, and
${\mbox{Diag}\,}A_{i}=A_{i}^{(1)}\oplus\cdots\oplus A_{i}^{(k)}$, where
$A_{i}^{(j)}\in\mathbb{P}_{n_{j}}$ for $i=1,\dots,m$, $j=1,\ldots,k$.

$\det\left(\sum_{i=1}^{m}(A_{i}^{(1)})^{-1}\right)\cdots\det\left(\sum_{i=1}^{m}(A_{i}^{(k)})^{-1}\right)\leq\det\left(\sum_{i=1}^{m}A_{i}^{-1}\right).$
(1.6)

We present a weak majorization inequality which is complementary to (1.6) and
pose a weak log majorization open problem.

##  2\. Weak log majorization and generalization of Matic’s determinantal
inequality

Regarding (1.3), one may ask whether $(C^{-1}D)^{p}$ is well defined or not
when $p\in\mathbb{R}$. The question makes sense as we know that $X^{p}$ is not
necessarily defined for a general matrix $X\in\mathbb{C}_{n\times n}$.
However, we can define $X^{p}$ when $X$ is hyperbolic, i.e., $X$ is
diagonalizable with positive eigenvalues. Let $\mathbb{H}_{n}$ be the set of
all hyperbolic matrices in $\mathbb{C}_{n\times n}$ and $\mathbb{D}_{n}$ be
the set of all diagonalizable matrices in $\mathbb{C}_{n\times n}$ with real
eigenvalues. We claim that the exponential map
$\exp:\mathbb{D}_{n}\to\mathbb{H}_{n}$ is bijective. It is surjective since
each $X\in\mathbb{H}_{n}$ can be written as $X=SDS^{-1}$ for some nonsingular
$S$, where $D={\mbox{diag}\,}(e^{\lambda_{1}},\dots,e^{\lambda_{n}})$ and
$\lambda_{1},\dots,\lambda_{n}\in\mathbb{R}$. Set $Y:=S(\log D)S^{-1}$, where
$\log D:={\mbox{diag}\,}(\lambda_{1},\dots,\lambda_{n})$. Note that

$e^{Y}=e^{S(\log D)S^{-1}}=S(e^{\log D})S^{-1}=SDS^{-1}=X.$

We are going to show that $\exp$ is injective. Let
$Y_{1},Y_{2}\in\mathbb{D}_{n}$ such that $e^{Y_{1}}=e^{Y_{2}}$. Let
$P_{1}D_{1}P_{1}^{-1}=Y_{1}$ and $P_{2}D_{2}P_{2}^{-1}=Y_{2}$, where $D_{1}$
and $D_{2}$ are diagonal with diagonal entries arranged in non-increasing
order. Taking exponentials of both sides yields
$P_{1}e^{D_{1}}P_{1}^{-1}=P_{2}e^{D_{2}}P_{2}^{-1}$ and thus $D_{1}=D_{2}=D$,
say, by spectrum consideration. Write $D:=d_{1}I_{n_{1}}\oplus\cdots\oplus
d_{k}I_{n_{k}}$, where $d_{1}>\cdots>d_{k}$. Set $Q=P_{1}^{-1}P_{2}$. So
$e^{D}Q=Qe^{D}$ and hence $Q=Q_{1}\oplus\cdots\oplus Q_{k}$, where
$Q_{i}\in\mathbb{C}_{n_{i}\times n_{i}}$. Thus $DQ=QD$, i.e.,
$DP_{1}^{-1}P_{2}=P_{1}^{-1}P_{2}D$, which implies that $Y_{1}=Y_{2}$. So we
conclude that the map $\exp:\mathbb{D}_{n}\to\mathbb{H}_{n}$ is bijective. Now
given $X\in\mathbb{H}_{n}$, define $X^{p}:=e^{pY}$, $p\in\mathbb{R}$, where
$Y$ is the unique matrix in $\mathbb{D}_{n}$ such that $X=e^{Y}$. Explicitly,
if we write $X=S{\mbox{diag}\,}(\xi_{1},\dots,\xi_{n})S^{-1}$ for some
nonsingular $S\in\mathbb{C}_{n\times n}$, where
$\xi_{1},\dots,\xi_{n}\in\mathbb{R}_{+}$ are the eigenvalues of $X$ in any
order, then $X^{p}:=S{\mbox{diag}\,}(\xi_{1}^{p},\dots,\xi_{n}^{p})S^{-1}$
since $Y=S{\mbox{diag}\,}(\log\xi_{1},\dots,\log\xi_{n})S^{-1}$.

Let us get back to the well-definedness of $(C^{-1}D)^{p}$, $p\in\mathbb{R}$,
regarding (1.3). Note that $C^{-1},D\in\mathbb{P}_{n}$. Given
$A,B\in\mathbb{P}_{n}$, the product $AB$ is hyperbolic though it may not be in
$\mathbb{P}_{n}$. It is because that $AB$ is similar to
$B^{1/2}ABB^{-1/2}=B^{1/2}AB^{1/2}\in\mathbb{P}_{n}$, which is unitarily
similar to a positive diagonal matrix. Hence
$AB=P{\mbox{diag}\,}(\gamma_{1},\dots,\gamma_{n})P^{-1}$, for some nonsingular
$P\in\mathbb{C}_{n\times n}$, where
$\gamma_{1},\dots,\gamma_{n}\in\mathbb{R}_{+}$ so that
$(AB)^{p}=P{\mbox{diag}\,}(\gamma_{1}^{p},\dots,\gamma_{n}^{p})P^{-1}$,
$p\in\mathbb{R}$.

Now we give our main result as follows.

######  Theorem 2.1.

Under the conditions as in Theorem 1.1, we have

$\lambda(C^{-1}_{1}D_{1}\oplus\cdots\oplus
C^{-1}_{k}D_{k})\prec_{w\,\log}\lambda(C^{-1}D).$ (2.1)

###### Proof.

It suffices to prove the case when $D=I_{n}$:

$\displaystyle\lambda(C_{1}^{-1}\oplus\cdots\oplus
C_{k}^{-1})\prec_{w\,\log}\lambda(C^{-1}).$ (2.2)

The reason is that

$\lambda(C^{-1}D)=\lambda((D^{-1/2}CD^{-1/2})^{-1})$

and

${\mbox{Diag}\,}(D^{-1/2}CD^{-1/2})=(D_{1}^{-1/2}C_{1}D_{1}^{-1/2})\oplus\cdots\oplus(D_{k}^{-1/2}C_{k}D_{k}^{-1/2}).$

Thus (2.1) is equivalent to

$\lambda(({\mbox{Diag}\,}(D^{-1/2}CD^{-1/2}))^{-1})\prec_{w\,\log}\lambda((D^{-1/2}CD^{-1/2})^{-1})$

so it is sufficient to show (2.2). By a result of Ky Fan [4, p.308] we have

$\displaystyle\lambda(C_{1}\oplus\dots\oplus C_{k})\prec\lambda(C).$ (2.3)

It is known that [4, p.165] for any convex function
$f:\mathbb{R}\to\mathbb{R}$, if $x\prec y$, where
$x=(x_{1},x_{2},\ldots,x_{n}),y=(y_{1},y_{2},\ldots,y_{n})\in\mathbb{R}^{n}$,
then

$(f(x_{1}),f(x_{2}),\ldots,f(x_{n}))\prec_{w}(f(y_{1}),f(y_{2}),\ldots,f(y_{n})).$

Since $f(x)=x^{-p}$, where $p>0$, is convex on $(0,+\infty)$, by (2.3), we
have

$\displaystyle\lambda(C_{1}^{-p}\oplus\cdots\oplus
C_{k}^{-p})\prec_{w}\lambda(C^{-p}),\quad p>0.$ (2.4)

For $m$ positive numbers $a_{1},\dots,a_{m}$, their power mean of order $r$ is
defined by

$M_{r}(a):=\left(\frac{1}{m}\sum_{i=1}^{m}a_{i}^{r}\right)^{\frac{1}{r}}$

and it is known that $\lim_{r\to
0^{+}}M_{r}(a)=(\prod_{i=1}^{m}a_{i})^{\frac{1}{m}}$ (see [3, p.15]). Applying
this to (2.4) leads to

$\lambda(C^{-1}_{1}\oplus\cdots\oplus
C^{-1}_{k})\prec_{w\,\log}\lambda(C^{-1}),$

i.e., (2.2). Thus, we complete the proof. ∎

We now give an example to show that (2.1) may not be true if
$D\in\mathbb{P}_{n}$ is not in diagonal block form, where
${\mbox{Diag}\,}D=D_{1}\oplus\dots\oplus D_{k}$, and
$D_{1}\in\mathbb{P}_{n_{1}},\dots,D_{k}\in\mathbb{P}_{n_{k}}$ with
$n_{1}+\cdots+n_{k}=n$.

######  Example 2.2.

Let

$C=\begin{pmatrix}14&8&9&8\\\ 8&12&7&7\\\ 9&7&10&8\\\
8&7&8&8\end{pmatrix},\quad C_{1}=\begin{pmatrix}14&8\\\
8&12\end{pmatrix},\quad C_{2}=\begin{pmatrix}10&8\\\ 8&8\end{pmatrix},$
$D=\begin{pmatrix}11&12&6&11\\\ 12&16&7&12\\\ 6&7&5&6\\\
11&12&6&14\end{pmatrix},\quad D_{1}=\begin{pmatrix}11&12\\\
12&16\end{pmatrix},\quad D_{2}=\begin{pmatrix}5&6\\\ 6&14\end{pmatrix}.$

By Matlab,

$\displaystyle\lambda(C^{-1}D)$ $\displaystyle=$
$\displaystyle(4.8921,1.0664,0.3433,0.1772),$
$\displaystyle\lambda(C_{1}^{-1}D_{1})$ $\displaystyle=$
$\displaystyle(1.3488,0.2281),$ $\displaystyle\lambda(C_{2}^{-1}D_{2})$
$\displaystyle=$ $\displaystyle(4.8080,0.4420).$

So $\lambda(C_{1}^{-1}D_{1}\oplus
C_{2}^{-1}D_{2})\not\prec_{w\,\log}\lambda(C^{-1}D)$ by considering the
products of the first two largest entries of both sides.

######  Remark 2.3.

One cannot replace the weak log majorization by the log majorization in (2.1).
For example let $C,D_{1},D_{2}$ be given in Example 2.2, and $D:=D_{1}\oplus
D_{2}$. Note that

$\lambda(C_{1}^{-1}D_{1}\oplus
C_{2}^{-1}D_{2})\not\prec_{\log}\lambda(C^{-1}D)$

as
$\det(C_{1}^{-1}D_{1})\det(C_{2}^{-1}D_{2})=0.6538\not=2.1717=\det(C^{-1}D)$
by Matlab.

######  Remark 2.4.

Taking $D=I_{n}$ in Theorem 2.1, we easily obtain

$\prod_{i=m}^{n}\lambda_{i}(C)\leq\prod_{i=m}^{n}\lambda_{i}(C_{1}\oplus\cdots\oplus
C_{k}),\,\,\,m=1,\ldots,n.$ (2.5)

(2.5) implies Fischer inequality.

######  Remark 2.5.

Let $C\in\mathbb{P}_{n}$ be given as in Theorem 1.1 and
$D\in\mathbb{C}_{n\times n}$ be positive semidefinite with
${\mbox{Diag}\,}D=D_{1}\oplus\cdots\oplus D_{k}$. Wang, Xi, and Zhang [6,
Theorem 4] proved

$\lambda(C_{1}^{-1}D_{1}\oplus 0)\leq\lambda(C^{-1}D).$

In Example 2.2, one can see that
$(\lambda(C_{i}^{-1}D_{i}),0,0)\leq\lambda(C^{-1}D)$, $i=1,2$. Theorem 2.1
complements this result when $D\in\mathbb{P}_{n}$ is in diagonal block form.

Next we give an application of Theorem 2.1 as follows.

######  Theorem 2.6.

Under the conditions as in Theorem 1.1, we have

$\det(I_{n_{1}}+(C_{1}^{-1}D_{1})^{p})\cdots\det(I_{n_{k}}+(C_{k}^{-1}D_{k})^{p})\leq\det(I_{n}+(C^{-1}D)^{p}),\quad
p\geq 0.$ (2.6)

###### Proof.

When $p=0$, it is trivial so we may assume $p>0$. By Theorem 2.1, we have

$\log\lambda(C^{-1}_{1}D_{1}\oplus\cdots\oplus
C^{-1}_{k}D_{k})\prec_{w}\log\lambda(C^{-1}D).$ (2.7)

Let us recall a known result [4, p.167] for any increasing convex function
$f:\mathbb{R}\to\mathbb{R}$. If $x\prec_{w}y$, where
$x=(x_{1},x_{2},\ldots,x_{n}),y=(y_{1},y_{2},\ldots,y_{n})\in\mathbb{R}^{n}$,
then

$(f(x_{1}),f(x_{2}),\ldots,f(x_{n}))\prec_{w}(f(y_{1}),f(y_{2}),\ldots,f(y_{n})).$

Since the function $f(x)=\log(1+e^{px})$, where $p>0$, is an increasing convex
function, applying the function to (2.7) gives

$\sum_{i=1}^{n}\log(1+(\lambda_{i}(C^{-1}_{1}D_{1}\oplus\cdots\oplus
C^{-1}_{k}D_{k}))^{p})\leq\sum_{i=1}^{n}\log(1+(\lambda_{i}(C^{-1}D))^{p}),$

i.e.,

$\sum_{i=1}^{n}\log(1+\lambda_{i}((C^{-1}_{1}D_{1})^{p}\oplus\cdots\oplus(C^{-1}_{k}D_{k})^{p}))\leq\sum_{i=1}^{n}\log(1+\lambda_{i}((C^{-1}D)^{p})).$

The desired result follows by taking exponential on both sides. ∎

######  Remark 2.7.

When $p=1$, Theorem 2.6 reduces to Theorem 1.1.

In the next example we show that (2.6) is not true when $p<0$.

######  Example 2.8.

Let $n=2$, $n_{1}=n_{2}=1$, $D=I_{2}$,

$C=\begin{pmatrix}3&2\\\ 2&3\end{pmatrix}\in\mathbb{P}_{2\times 2},\quad
C_{1}=C_{2}=3.$

Direct computation gives $\lambda(C)=\\{5,1\\}$. Let $p<0$ and set $q:=-p$ so
$q>0$. Then

$\lambda(C^{q})=\\{5^{q},1\\},\quad C_{1}^{q}=C_{2}^{q}=3^{q}.$

Let

$f(q):=\det(I_{2}+C^{q})=(1+5^{q})(1+1)=2+2\cdot 5^{q}$

and

$g(q):=\det(1+C_{1}^{q})\det(1+C_{2}^{q})=(1+3^{q})^{2}=1+2\cdot
3^{q}+3^{2q}.$

We are going to show that $g(q)>f(q)$ for all $q>0$. Let $f(x)=2\cdot
3^{x}+3^{2x}-2\cdot 5^{x}-1$. Since

$f^{\prime}(x)=(3^{x}+9^{x})\ln 9-2\cdot 5^{x}\ln 5\geq 2\sqrt{3^{x}\cdot
9^{x}}\ln 9-2\cdot 5^{x}\ln 5>0,\quad\mbox{for }x>0,$

we have $f(x)>f(0)=0$ when $x>0$. Thus (2.6) is not true when $p<0$.

We would like to point out that (2.6) is no longer true if
$D\in\mathbb{P}_{n}$ is not in diagonal block form. We give an example to show
this as follows.

######  Example 2.9.

Let $p=1$, $n=2$, $n_{1}=n_{2}=1$,

$C=\begin{pmatrix}12&7\\\ 7&10\end{pmatrix},\quad C_{1}=12,\quad C_{2}=10,$
$D=\begin{pmatrix}16&7\\\ 7&5\end{pmatrix},\quad D_{1}=16,\quad D_{2}=5.$

Direct computation gives

$\det(I_{2}+C^{-1}D)\approx
3.1549<3.5=\det(1+C_{1}^{-1}D_{1})\det(1+C_{2}^{-1}D_{2}).$

Next we will show that inequalities (1.4) and (1.5) are not true and we first
give a counterexample to the following inequality.

$\displaystyle\det(D_{1}^{-2}+C_{1}^{-2})\cdots\det(D_{k}^{-2}+C_{k}^{-2})\leq\det(D^{-2}+C^{-2}),$
(2.8)

where $C,D,C_{i},D_{i},i=1,\ldots,k$, are given as in Theorem 1.1.

######  Example 2.10.

Let

$C=\begin{pmatrix}16.25&21&10&12.5\\\ 21&39.75&20.75&28.5\\\
10&20.75&22.5&27.75\\\ 12.5&28.5&27.75&39.25\end{pmatrix},\quad
C_{1}=\begin{pmatrix}16.25&21\\\ 21&39.75\end{pmatrix},$
$C_{2}=\begin{pmatrix}22.5&27.75\\\ 27.75&39.25\end{pmatrix},\quad
D=\begin{pmatrix}14.7&15&0&0\\\ 15&15.8&0&0\\\ 0&0&0.25&0.4\\\
0&0&0.4&0.8\end{pmatrix},$

and

$D_{1}=\begin{pmatrix}14.7&15\\\ 15&15.8\end{pmatrix},\quad
D_{2}=\begin{pmatrix}0.25&0.4\\\ 0.4&0.8\end{pmatrix}.$

By Matlab

$\det(D^{-2}+C^{-2})=51.0669<54.6523=\det(D_{1}^{-2}+C_{1}^{-2})\det(D_{2}^{-2}+C_{2}^{-2}).$

Therefore, (2.8) is false.

Note that

$\displaystyle\det(I_{n}+|C^{-1}D|^{2})$ $\displaystyle=$
$\displaystyle\det(I_{n}+DC^{-2}D)=\det(D(D^{-2}+C^{-2})D)$ $\displaystyle=$
$\displaystyle\det(D^{-2}+C^{-2})\cdot(\det D)^{2},$

and

$\det(I_{n_{1}}+|C_{1}^{-1}D_{1}|^{2})\cdots\det(I_{n_{k}}+|C_{k}^{-1}D_{k}|^{2})$
$\displaystyle=$
$\displaystyle\det(D_{1}(D_{1}^{-2}+C^{-2})D_{1})\cdots\det(D_{k}(D_{k}^{-2}+C_{k}^{-2})D_{k})$
$\displaystyle=$
$\displaystyle\det(D_{1}^{-2}+C_{1}^{-2})\cdot\det(D_{1})^{2}\cdots\det(D_{k}^{-2}+C_{k}^{-2})\cdot(\det
D_{k})^{2}$ $\displaystyle=$
$\displaystyle\det(D_{1}^{-2}+C_{1}^{-2})\cdots\det(D_{k}^{-2}+C_{k}^{-2})\cdot(\det
D)^{2}.$

Since (2.8) is false, (1.4) is invalid.

Note that

$\det(I_{n}+C^{-2}D^{2})=\det((D^{-2}+C^{-2})D^{2})=\det(D^{-2}+C^{-2})\cdot(\det
D)^{2}$

and

$\det(I_{n_{1}}+C_{1}^{-2}D_{1}^{2})\cdots\det(I_{n_{k}}+C_{k}^{-2}D_{k}^{2})$
$\displaystyle=$
$\displaystyle\det(D_{1}^{-2}+C_{1}^{-2})\cdot\det(D_{1})^{2}\cdots\det(D_{k}^{-2}+C_{k}^{-2})\cdot(\det
D_{k})^{2}$ $\displaystyle=$
$\displaystyle\det(D_{1}^{-2}+C_{1}^{-2})\cdots\det(D_{k}^{-2}+C_{k}^{-2})\cdot(\det
D)^{2}.$

Since (2.8) is false, (1.5) is also invalid.

######  Remark 2.11.

Since (1.4) is not true, the vectors of eigenvalues cannot be replaced by the
vectors of singular values in (2.1) from the proof in Theorem 2.6. In other
words,

$s(C^{-1}_{1}D_{1}\oplus\cdots\oplus
C^{-1}_{k}D_{k})\not\prec_{w\,\log}s(C^{-1}D),$

where $C,D,C_{i},D_{i},i=1,\ldots,k$, are given as in Theorem 1.1.

##  3\. Weak majorization complementary to Choi’s determinantal inequality

Let us first recall a result from [7, Theorem 7.13].

######  Lemma 3.1.

Let $A\in\mathbb{C}_{n\times n}$ be positive semidefinite and let $[A]$ be the
principal submatrix of $A$ corresponding to some fixed rows and columns.
Assuming that the inverses involved exist, we have

$[A]^{-1}\leq[A^{-1}].$

######  Theorem 3.2.

Under the conditions as in Theorem 1.2, we have

$\displaystyle\lambda\left(\sum_{i=1}^{m}(A_{i}^{(1)})^{-1}\oplus\cdots\oplus\sum_{i=1}^{m}(A_{i}^{(k)})^{-1}\right)^{p}$
$\displaystyle\prec_{w}$
$\displaystyle\lambda\left(\sum_{i=1}^{m}A_{i}^{-1}\right)^{p},\quad p\geq 1.$
(3.1)

###### Proof.

By (2.3), we have

$\displaystyle\lambda\left(\sum_{i=1}^{m}(A_{i}^{-1})^{(1)}\oplus\cdots\oplus\sum_{i=1}^{m}(A_{i}^{-1})^{(k)}\right)\prec\lambda\left(\sum_{i=1}^{m}A_{i}^{-1}\right).$
(3.2)

By Lemma 3.1 and Weyl’s monotonicity theorem [1, p.63], we have

$\displaystyle\lambda\left(\sum_{i=1}^{m}(A_{i}^{(1)})^{-1}\oplus\cdots\oplus\sum_{i=1}^{m}(A_{i}^{(k)})^{-1}\right)\leq\lambda\left(\sum_{i=1}^{m}(A_{i}^{-1})^{(1)}\oplus\cdots\oplus\sum_{i=1}^{m}(A_{i}^{-1})^{(k)}\right).$
(3.3)

Now (3.2) and (3.3) lead to

$\displaystyle\lambda\left(\sum_{i=1}^{m}(A_{i}^{(1)})^{-1}\oplus\cdots\oplus\sum_{i=1}^{m}(A_{i}^{(k)})^{-1}\right)\prec_{w}\lambda\left(\sum_{i=1}^{m}A_{i}^{-1}\right).$

The desired result follows by the fact that $f(x)=x^{p},\,p>1,$ is increasing
and convex on $(0,+\infty)$. ∎

######  Remark 3.3.

Choi’s determinantal inequality (1.6) is equivalent to the following:

$\det\left(\sum_{i=1}^{m}(A_{i}^{(1)})^{-1}\oplus\cdots\oplus\sum_{i=1}^{m}(A_{i}^{(k)})^{-1}\right)^{p}\leq\det\left(\sum_{i=1}^{m}A_{i}^{-1}\right)^{p},\quad
p>0.$

Thus, Theorem 3.2 is a complement to Theorem 1.2.

It is natural to ask whether (3.1) holds for $0<p<1$? By Theorem 3.2 and the
proof of Theorem 2.1, this question is equivalent to the following weak log
majorization question:

######  Question 3.4.

Under the conditions as in Theorem 1.2,

$\lambda\left(\sum_{i=1}^{m}(A_{i}^{(1)})^{-1}\oplus\cdots\oplus\sum_{i=1}^{m}(A_{i}^{(k)})^{-1}\right)\prec_{w\log}\lambda\left(\sum_{i=1}^{m}A_{i}^{-1}\right)?$
(3.4)

When $n=2,k=2,n_{1}=n_{2}=1$, (3.4) holds by (1.6) and (3.1). The other cases
are open. We would like to point out that we performed computer experiments
and the outcomes are consistent with the weak log majorization given in (3.4).

## Disclosure statement

No potential conflict of interest was reported by the authors.

## Acknowlegements

The second author is supported by the National Natural Science Foundation of
China (Grant numbers: 11601054, 11671060), the Basic and Advanced Research
Project of CQ CSTC (Grant number: cstc2016jcyjA0466), the Science and
Technology Research Project of Chongqing Municipal Education Commission (Grant
number: KJ201600644621) and the Youth Science Research Project of Chongqing
University of Posts and Telecommunications (Grant number: A2014-104).

## References

  * [1] R. Bhatia, Matrix Analysis, Springer, New York, 1997.
  * [2] D. Choi, Determinantal inequalities of positive definite matrices, Math. Inequal. Appl. 19 (2016), 167-172.
  * [3] G. Hardy, J.E. Littlewood, and G. Pólya, Inequalities, Cambridge University Press, 1991.
  * [4] A.W. Marshall, I. Olkin, B.C. Arnold, Inequalities: Theory of Majorization and Its Applications, Second Edition, Springer, 2011.
  * [5] I. Matic, Inequalities with determinants of perturbed positive matrices, Linear Algebra Appl. 449 (2014), 166-174.
  * [6] B.Y. Wang, B.Y. Xi and F. Zhang, Some inequalities for sum and product of positive semidefinite matrices, Linear Algebra Appl. 293 (1999), 39-49.
  * [7] F. Zhang, Matrix Theory: Basic Results and Techniques, Second Edition, Springer, 2011.
  * [8] P. Zhang, Extension of Matic’s results, Linear Algebra Appl. 486 (2015), 328-334.


11institutetext: Technical University of Munich
11email<EMAIL_ADDRESS>
# SRTK: A Toolkit for Semantic-relevant Subgraph Retrieval

Yuanchun Shen  0009-0003-1513-5362

###### Abstract

Information retrieval based knowledge base question answering (KBQA) first
retrieves a subgraph to reduce search space, then reasons on the subgraph to
select answer entities. Existing approaches have three issues that impede the
retrieval of such subgraphs. Firstly, there is no off-the-shelf toolkit for
semantic-relevant subgraph retrieval. Secondly, existing methods are
knowledge-graph-dependent, resulting in outdated knowledge graphs used even in
recent studies. Thirdly, previous solutions fail to incorporate the best
available techniques for entity linking or path expansion. In this paper, we
present SRTK, a user-friendly toolkit for semantic-relevant subgraph retrieval
from large-scale knowledge graphs. SRTK is the first toolkit that streamlines
the entire lifecycle of subgraph retrieval across multiple knowledge graphs.
Additionally, it comes with state-of-the-art subgraph retrieval algorithms,
guaranteeing an up-to-date solution set out of the box.

Resource Type: Software
License: MIT
DOI: https://doi.org/10.5281/zenodo.7895612
Repository: https://github.com/happen2me/subgraph-retrieval-toolkit

###### Keywords:

Subgraph Retrieval Knowledge Graph KBQA

##  1 Introduction

Knowledge base question answering (KBQA) aims to answer natural language
questions over large scale knowledge graphs such as Wikidata [34], Freebase
[2], and DBPedia [1]. One crucial step in KBQA is subgraph retrieval, which
involves narrowing down the search space by retrieving a subset of entities
and relations from the knowledge graph that are relevant to the question. By
obtaining a smaller subgraph with more pertinent information, noise can be
reduced, and the reasoning process can be facilitated.

Subgraph retrieval can be divided into two main steps: entity linking and path
expansion. Entity linking identifies named entities in questions and anchors
them to corresponding entities in knowledge graphs, while path expansion
selectively includes neighbor entities and relations to form the subgraph. The
scale and complexity of knowledge graphs pose challenges for both steps.
Firstly, accurate entity linking requires detecting potential entity mentions
and disambiguating them to the correct entities in the knowledge graph. This
task becomes challenging due to the large number of entities within the
knowledge graph, where multiple entities may have similar names to those
mentioned in the question. Once the entities are identified, selecting the
most relevant paths for subgraph expansion is also non-trivial. Although
numerous paths can be expanded from an entity, only a small subset of them are
truly relevant. For instance, as of the time of writing, Wikidata has 3,278
entities connected to the United States as the subject of certain relations,
exemplifying the vast number of potential paths to consider.

Existing KBQA works that involve subgraph retrieval have certain limitations.
For entity linking, some recent works still rely on pure pattern matching,
resulting in a significant number of irrelevant linked entities [38, 19, 7].
In terms of path expansion, many existing approaches either blindly expand
entities within one or two hops [4], which quickly becomes infeasible for
large knowledge graphs, or filter expansion paths using non-trainable
embedding similarity [39], which may not capture the most relevant paths.
Zhang et al. proposed a path expansion method called SR [44], which achieved
state-of-the-art results on specific KBQA datasets, but it assumes pre-linked
entities and only works with the outdated knowledge graph Freebase.

To address these gaps, we propose SRTK, a toolkit designed to simplify the
retrieval of semantic-relevant subgraphs from large-scale knowledge graphs.
SRTK integrates multiple off-the-shelf entity linking tools with unified
interfaces and implements the SR path expansion algorithm [44] for both
Freebase and up-to-date knowledge graphs such as Wikidata and DBpedia.
Furthermore, we extend the SR algorithm to support contrastive losses and
different base models during training, as well as varying beam width and
search depth during inference. To our knowledge, SRTK is the first readily
available toolkit for subgraph retrieval across multiple knowledge graphs. Its
main features include:

  * •

Out-of-the-box Functionality: SRTK provides command-line tool and Python
library for subgraph retrieval. It comes with documentation and tutorials for
a quick and effortless start.

  * •

Full Lifecycle Support for Subgraph Retrieval: SRTK streamlines the complete
lifecycle of subgraph retrieval. This includes not only retrieval itself
(entity linking, path expansion), but also retrieval model training (data
processing, scorer training, and retrieval evaluation).

  * •

Multi-Knowledge Graph Support: SRTK provides support for Freebase, Wikidata,
and DBpedia, employing unified access patterns. Furthermore, the toolkit can
be extended to accommodate other knowledge graphs that have a SPARQL
interface, thereby increasing its versatility.

  * •

User-friendly Design: SRTK offers a user-friendly interface that is both
intuitive and extensible. For instance, each step of the retrieval process can
be executed with a single command; various steps are seamlessly connected
using standardized JSONL files, ensuring a smooth workflow; extension to new
knowledge graphs and entity linking tools can be accomplished by implementing
standardized protocols, etc;.

  * •

Inclusion of SOTA Algorithms: REL and DBpedia are among the best available
off-the-shelf entity linking tools; For path expansion, we employed the SR
algorithm proposed by Zhang et al [44], which achieves the state-of-the-art
results on two Freebase KBQA datasets, ensuring path expansion is on par with
the state-of-the-art methods.

  * •

Huggingface Model Compatibility: SRTK supports training or evaluation with any
language encoding models available on the Huggingface model hub.

  * •

Interactive Visualization: Retrieved subgraphs can be visualized as
interactive web pages, allowing users to explore and analyze the retrieved
information in a user-friendly and intuitive manner.

The rest of the paper is structured as follows. We begin with a review of
related works in section 2. Then we introduce the main functions and
implementations of SRTK in section 3, exemplifying the usage of SRTK.
Subsequently, in section 4, we discuss the impact, positioning to the state of
the art, limitations, and future development plans. Finally, we conclude the
paper in section 5.

##  2 Related Works

KBQA answers natural language questions with entities or relations from a
knowledge graph [17]. Knowledge graph is a structured representation of
knowledge. It usually represents real-world facts as (subject, predicate,
object) triples. Researchers have approached the problem of KBQA in different
ways, which can be broadly categorized into two types. The first type is based
on semantic parsing, where a graph query is constructed by filling patterns or
end-to-end constructions to directly retrieve the targets [40, 7]. However,
this method has limitations due to the difficulty in precisely interpreting
human intentions and the fact that it excludes potentially helpful reasoning
paths and connected nodes. The second type is based on information retrieval.
It regards selecting targets as either binary classification or ranking over
candidate entities [11]. They usually start with entity linking that matches
mentions in question to entities in knowledge graphs, then expands the
subgraphs by including neighbors. A reasoner is then applied to select correct
answers from the retrieved subgraphs [44, 4, 39]. Our work mainly applies to
this branch of KBQA solutions.

Semantic-relevant Subgraph Retrieval reduces the search space and noisy
information for downstream reasoners by retrieving a pertinent subgraph that
is likely to contain the target entities or relations, leveraging the semantic
information conveyed in a natural language question. This retrieval process is
typically divided into entity linking and path expansion. In entity linking,
it first performs named entity recognition (NER) to detect entity mentions in
the questions, then employs entity disambiguation to link entities to
corresponding knowledge graphs. While in path expansion, neighbor entities and
relations to existing entities are retrieved to form the subgraphs. The
assumption behind this approach is that the target entities are within
proximity of mentioned entities in the questions. There are also works that do
not follow this approach. For example, CLOCQ [6] use a combination of
features, such as lexical matching, question-relevance, coherency, and
connectivity, to directly retrieve top-$k$ relevant entities or relations as
the reduced search space.

Earlier methods to subgraph retrieval, which are still adopted by recent works
[39, 19, 7], usually starts with keywords matching to link entities to
knowledge graphs, then include all entities within a certain hop. Such methods
are suitable for small-scale knowledge graphs, but for large knowledge graphs,
lexically matching mentions may include many unrelated entities. Including all
$k$-hop entities may further lead to a size explosion of the retrieved graph.
Based on this approach, some optimizations were proposed to shrink the
subgraph size. QA-GNN [39] uses GLOVE embedding distance as similarity metrics
to filter out less similar entities and relations, but it is not trainable,
thus incapable for situations where the expansion path is semantically
dissimilar to the question itself.

Recent advancements in subgraph retrieval have demonstrated improvements in
both entity linking and path expansion. Several entity linking tools, such as
WAT [25], REL [14], DBpedia Spotlight [20], have been developed for different
knowledge graphs, incorporating lexical, contextual, and semantic information.
In terms of path expansion, recent works take semantic information of the
retrieval paths into consideration. PullNet[30] assumes that entities are
already linked. It iteratively pulls neighboring entities or entities from a
related corpus based on their probabilities predicted by a neural network,
forming the subgraph. However, PullNet lacks the separation between path
expansion and subgraph reasoning. Building upon this, Zhang et al. proposed SR
[44], which decouples path expansion from reasoning to enable a plug-and-play
framework that generalizes to different reasoners. SR performs iterative path
expansion by comparing the trained semantic similarity of the next expansion
path with the question concatenated with the previously expanded paths. By
leveraging subgraphs retrieved through SR, Zhang et al. achieved state-of-the-
art results on WebQSP [41] and CWQ [32] KBQA datasets. However, it is
important to note that SR assumes the entities are already linked and is
specifically designed for the Freebase knowledge graph, which ceased to be
updated in 2015111https://en.wikipedia.org/wiki/Freebase_(database).

##  3 SRTK: Subgraph Retrieval Toolkit

The SRTK project is publicly available on
PyPI222https://pypi.org/project/srtk, and it serves as both a command line
toolkit and a Python library. We focus on demonstrating its usage as a command
line toolkit. For information on using it as a Python library, please consult
the Python API section of the documentation333https://srtk.readthedocs.io. In
this section, we first define the problem of subgraph retrieval, then we
introduce each API and the underlying implementation. The SRTK CLI is divided
into five subcommands: preprocess, train, link, retrieve, and visualize. We
categorize them based on two workflows: the first being retrieving subgraphs
with trained models, and the second being training models for subgraph
retrieval.

###  3.1 Problem Definition

The objective of Semantic-relevant Subgraph Retrieval for KBQA is to retrieve
a subgraph $\mathcal{G}=(E_{\mathcal{G}},R_{\mathcal{G}})$ from a given
knowledge graph $G=(E,R)$ based on a natural language question $q$, such that
$\mathcal{G}\subseteq G$ contains the answer entities or relations $A\subseteq
G$ that the question expects. Here, $E$ and $R$ represent all entities and
relations in the knowledge graph. The retrieved subgraph $\mathcal{G}$ is
passed to a reasoner to predict answers. As reasoning is decoupled and not
within the scope of this paper, we assume that the reasoner
$p_{\phi}(A|q,\mathcal{G})$ will select $m$ items from $\mathcal{G}$ as
answers if it is known that there are $m$ answers. In the best case,
$\mathcal{G}$ will contain all the desired answers ($\mathcal{G}=A$), while in
the worst case, none of the answers will be present in $\mathcal{G}$. If the
answers included in $\mathcal{G}$ are fixed, a smaller subgraph $\mathcal{G}$
makes it easier for the reasoner $p_{\phi}(A|q,\mathcal{G})$ to select the
correct answers. On the other hand, when the size of $\mathcal{G}$ is fixed,
including more answers in the subgraph increases the likelihood of the
reasoner selecting the correct answers. Therefore, the goal of subgraph
retrieval is to obtain a subset of the knowledge graph that is as close as
possible to answers. The quality of the retrieval result is measured by both
the size of the subgraph and the recall of the answers. One retrieved subgraph
is considered strictly better than another if it has a smaller subgraph size
while achieving a higher recall of the answers.

###  3.2 Retrieval Workflow

Figure 1: The retrieval workflow of SRTK consists of three main steps: entity
linking, subgraph retrieval, and visualization. Entity linking identifies
knowledge graph entities mentioned in questions; subgraph retrieval retrieves
semantic relevant subgraphs with trained models by iteratively including
neighbors of the linked entities within certain proximity on a knowledge
graph; visualization visualizes the retrieved subgraphs in the form of
interactive webpages.

####  3.2.1 Entity Linking

Identifying named entities and aligning them with knowledge graph entities is
typically the initial step in subgraph retrieval. If a dataset is already
linked to a knowledge graph, this step may not be necessary.

SRTK link subcommand builds upon existing entity linking services, enabling
researchers to perform entity linking on various knowledge graphs through the
same interface. Consider the example Where is Hakata?, once storing it in a
jsonl file called question.jsonl like {"question": "Where is Hakata Ward?"},
users can link it to Wikidata with the following command:

⬇

srtk link \--input question.jsonl \

\--output linked.jsonl \

\--knowledge-graph wikidata \

\--el-endpoint https://rel-entity-linker.d4science.org

The link shown above is the public endpoint of REL [14] service 444In practice
you also have to pass an authorization in the command line.. Each line of the
output linked.jsonl has the following format:

⬇

{"question_entities": ["Q1330839"], "spans": [[9,20]],

"entity_names": ["Hakata-ku,_Fukuoka"]}

Where the question entities are the linked entities from Wikidata, the spans
store the corresponding character index of the linked entity in the original
text, and the entity names show the name of the linked entities in the
knowledge graph. Under the hood, it first invokes REL [14] to link entity
mentions to Wikipedia articles, and then utilize
wikimapper555https://github.com/jcklie/wikimapper to map the corresponding
Wikipedia IDs to their corresponding entities in Wikidata. The extra step is
needed because most existing services only link entities to Wikipedia [14, 9,
25].

For DBpedia, we integrate DBpedia Spotlight [20] to directly identify entity
mentions and link them to DBpedia resources. By implementing annotation
interfaces defined in SRTK, the entity linking can be extended to other
knowledge graphs.

####  3.2.2 Retrieval

The retrieval interface is at the core of the library. It retrieves a
semantic-relevant subgraph with trained models and a given question.

The retrieval process can be divided into path search and fact retrieval. Path
search identifies the most probable expansion paths from linked entities. An
expansion path comprises a sequence of relations from the knowledge graph,
based on the idea that a question typically implies a reasoning chain [44].
For the example Where is Hakata Ward?, the corresponding expansion path would
be <locate in> from the triple (Hakata, locate in, ? ) implied by the
question, where <locate in> forms a path of length one. Path search starts
with loading a trained path scoring model that measures the likelihood to
expand a relation upon a current path, then it iteratively compares, selects,
and includes neighboring relations into expansion paths. Path search initially
regards linked entities and tracked entities. Subsequently, at each step of
expansion, it first queries knowledge graphs to retrieve a set of relations
connected to the tracked entities, then expand the paths by one hop by
selecting the most probable relations with the trained scoring model, taking
the question and the previously expanded paths into consideration. A path may
also stop expansion when a special end relation is selected as the next
relation. Afterward, path search updates the tracked entities with entities
that the chosen relations connect to. During expansion, beam search is applied
to keep track of top-$k$ most probable expansion paths; otherwise, the search
space will grow explosively as hop increases. Finally, until a certain hop is
reached, or until all paths have ended with the end relation, path search
stops expansion. After getting a set of probable expansion paths, fact
retrieval creates the subgraph by retrieving the entities and relations
present along the paths.

The retrieve subcommand is used to retrieve subgraphs with linked questions
and a trained scoring model. Users can additionally specify the max hop to
search with \--max-depth, and beam width with \--beam-width. A larger beam
width and a greater hop may increase the probability to arrive at target
entities, but will also increase the running time. Using the linked.jsonl from
the last sub-section with questions and linked entities, one can retrieve
subgraphs with the following command:

⬇

srtk retrieve \--input linked.jsonl \

\--output subgraph.jsonl \

\--beam-width 2 \--max-depth 1 \

\--scorer-model-path drt/srtk-scorer \

\--sparql-endpoint https://query.wikidata.org/sparql

The \--scorer-model-path specifies the location of a trained path scoring
model. It can be either the folder of a saved local model or any language
encoder model identifier from the Huggingface model
hub666https://huggingface.co/models. Besides, if an encoder-decoder model like
T5 [27] is fed in as the path scoring model, only the encoder part of the
model will be used. The output has the following format, where the subgraph is
saved as a list of (subject, predicate, object) triples in the form of their
identifiers on respective knowledge graphs.

⬇

# Output subgraph.jsonl

{"triples": [["Q1330839","P31","Q26600"],

["Q1330839","P17","Q17"]]}

####  3.2.3 Visualization

SRTK’s visualization module generates interactive web pages that display the
retrieved subgraphs. The labels of the unique identifiers are fetched from the
knowledge graphs through their SPARQL endpoints, and the linked entities are
highlighted for better visualization.

By feeding the output subgraph subgraph.jsonl from the last sub-section, one
can visualize it with the following command. The resulting graph is depicted
in Fig. 2.

⬇

srtk visualize \--input subgraph.jsonl \

\--knowledge-graph wikidata \

\--sparql-endpoint https://query.wikidata.org/sparql

Figure 2: The visualized subgraph with srtk visualize. The subgraph
corresponds to the question Where is Hakata Ward?. It is visualized from a
subgraph comprised of two triples: (Hakata-ku, located in, Fukuoka) and
(Hakata-ku, country, Japan).

###  3.3 Training Workflow

SRTK trains scorer models to align questions with their corresponding
reasoning paths in the embedding space, enabling semantic-relevant subgraph
retrieval.

The training process can be achieved through either full supervision or weak
supervision. In full supervision, the correct subgraph or the gold expansion
paths are known. While in weak supervision, only the source and target
entities are known, which is more common in KBQA. SRTK supports both
supervised and weakly supervised learning. For the latter, SRTK searches for
the shortest paths from source to target entities in the knowledge graphs
during the preprocessing stage, which are then used as weak supervision
signals.

Figure 3: The training workflow of SRTK involves three steps. Firstly, it
preprocesses the raw data by identifying positive expansion paths and sampling
negative ones. Next, it trains a scorer model that can selectively expand the
subgraph according to a question by learning to pull together the question and
the correct expansion path in the embedding space. Finally, if the answer
entities are known, the scorer can be evaluated by calculating the answer
coverage rate. The answer coverage rate in SRTK is calculated as the
percentage of test samples where at least one answer entity is successfully
retrieved.

####  3.3.1 Preprocessing

The preprocess subcommand simplifies the preprocessing of training data. In
the fully supervised scenario, where the expansion paths from source entities
to target entities are known, the preprocessing create training samples from
each expansion step within an expansion path. For weak supervision scenarios,
where only the source and target entities are known, it additionally retrieves
likely paths between source and target entities within two hops. Then it
creates training samples as that in full supervision. Here, we discuss the
case of weak supervision for completeness.

To extract the most likely paths, we first query the SPARQL endpoints to
search for the shortest paths from each source entity to the target entities.
Since there may be multiple paths between the source and target entities, we
then filter the paths by examining how close the entity sets derived from the
paths to the answers. This involves retrieving a set of terminal entities of
each path and scoring the paths based on the Jaccard index between the
retrieved entities and the answer entities. Paths with scores below a certain
threshold are discarded.

Once the expansion paths are known, we convert the retrieved paths into
training samples by sampling negative relations for each relation in an
expansion path. The intuition of this conversion is to mimic the decision-
making process during retrieval, where the goal is to select the most suitable
relation from the set of connected relations so that the probability of
reaching the target entities will be maximized. This is a form of weak
supervision, as the retrieved expansion path may not be the real reasoning
chain. A $K$-hop path is decomposed into $K+1$ positive samples. The first $K$
samples are $([q;r_{1},r_{2},\ldots,\allowbreak r_{k-1}],r_{k})$, with $q$
being a given query, , $r_{k}$ being the $k$-th relation, and $k$ in range
$1,2,\ldots,K$. The last sample is
$([q;r_{1},\ldots,r_{K}];\textnormal{END})$, where END is a special relation
signifying stopping expansion. For a positive sample
$([q;r_{1},r_{2},\ldots,r_{k-1}],r_{k})$, $N$ negative samples are retrieved
from the knowledge graph by sampling from the relations connected to relation
$r_{k-1}$ via one-hop intermediate entities, excluding $r_{k}$. Each positive
sample is then converted to a training sample along with its negative samples
and the query.

For instance, if we know from the previous example that the source entity is
Q1330839 (Hakata-ku), while the target entity is Q26600 (Fukuoka City), we can
first arrange the information into a JSONL file with one line as follows:

⬇

# Input kbqa_dataset.jsonl

{"question": "Where␣is␣Hakata␣Ward?",

"question_entities": ["Q1330839"],

"answer_entities": ["Q26600"]}

By executing the srtk preprocess command as follows, we first identify the
probable expansion paths between the question and answer entities within two
hops, then create training samples from the paths:

⬇

srtk preprocess \--input kbqa_dataset.jsonl \

\--search-path \--output train.jsonl \

\--knowledge-graph wikidata \

\--sparql-endpoint https://query.wikidata.org/sparql \

\--metric jaccard \--num-negative 2

In the command above, \--search-path instructs SRTK to look for connections
between question and answer entities. This argument can be omitted when the
gold expansion paths are known. \--num-negative specifies how many negative
relations to sample for each relation. The first sample in train.jsonl is as
follows:

⬇

{"query": "Where␣is␣Hakata␣Ward?␣[SEP]",

"positive": "located␣in␣the␣administrative␣entity",

"negatives": ["located␣in␣time␣zone","different␣from"]}

In the output, the query is the question and previous expansion relations
concatenated by a [SEP] token. The positive field saves the relation between
Hakata-ku and Fukuoka as natural language, while the negative field saves a
list of possible negative relations that connects to Hakata-ku but are not in
the correct expansion path. Since the question and answers are only one hop
away in this case, there will be only two generated training samples, where
the first is as shown above, having the one-hop relation as a positive
relation, while the second has END as the positive relation.

####  3.3.2 Training and Evaluation

The training process aims to train an encoder that encodes questions close to
their correct expansion paths in the embedding space. To be more specific, an
encoder is trained to encode each relation on a correct expansion path close
to the question concatenated with all relations before that relation. For
example, if a question $q$ has the reasoning path $r1\rightarrow r2$, then an
encoder is trained to encode $r1$, $r2$, and the special relation END similar
with $q$, $q+r1$, and $q+r1+r2$, respectively. Here, $+$ denotes
concatenation. We call a trained encoder a scorer, as it scorers candidate
relations at inference time. Therefore, for the question Where is Hakata? and
the expansion path <locate in>, Where is Hakata? [SEP] and locate in should be
similar if measured by a scorer; the same is for Where is Hakata? [SEP] locate
in and END. The similarity is computed as the cosine distance of the sentence-
level embeddings. For BERT-like models [8], which use a $[\textnormal{CLS}]$
token for classification, we use the embedding of [CLS] as the sentence-level
embedding. For other encoder models, we average over all token embeddings in
the last hidden layer of a sentence to obtain its sentence-level embedding.

We finetune a pretrained language encoder from huggingface as a scorer. Two
loss functions for model optimization are supported: cross-entropy loss and
contrastive loss. In the cross-entropy loss, the positive relation is regarded
as the correct class, while the other $N$ negative relations are regarded as
false ones. For contrastive learning, we use NTXentLoss [5], where the
question and the positive relation form a positive pair, and the query and
each of the negative relation form negative pairs.

Consider the output train.jsonl from the previous sub-section, if there are
many training samples generated as before, we can train a scorer with srtk
train as follows:

⬇

srtk train \--train-dataset data/train.jsonl \

\--output-dir artifacts/scorer \

\--model-name-or-path roberta-base \

\--accelerator gpu

If the answer entities are known in a dataset, we can proceed to evaluate a
scorer using SRTK. It works by retrieving subgraphs for a test dataset, then
calculating how many answer entities are retrieved with answer coverage rate.
We define answer coverage rate as the number of samples where any of the
correct answer entities is retrieved, divided by the total number of test
samples. We can perform an evaluation using the srtk retrieve subcommand with
the \--evaluate option. The expected input fields include question, question
entities, and answer entities. If the test dataset is stored at test.jsonl,
one can evaluate a trained scorer with the following command:

⬇

srtk retrieve \--input test.jsonl \

\--scorer-model-path artifacts/scorer \

\--evaluate

>>> Answer coverage rate: 0.9749 (4188 / 4296)

>>> Average subgraph size: 7.5345 triples

In the provided example, the command line output reveals that out of the 4296
samples, a total of 4188 samples successfully retrieve at least one of the
target entities. Additionally, the size of the subgraphs is measured by
calculating the average number of triples within the subgraphs across all the
samples. The numbers provided in this example are used purely for explanatory
purposes.

##  4 Discussions

###  4.1 Impact

In this paper, we have primarily focused on discussing the use case of SRTK in
the domain of KBQA. Within KBQA, our toolkit helps researchers more easily
retrieve subgraphs, which reduces search space and may improve the downstream
tasks by providing less noisy information. Moreover, SRTK promotes the
migration from outdated knowledge graphs to up-to-date ones by providing
unified interfaces. For example, research works that use to depend on Freebase
can seamlessly migrate to Wikidata777We additionally provide migration scripts
from Freebase to Wikidata, including entities and relations:
https://github.com/happen2me/freebase-wikidata-convert by updating the
knowledge graph endpoint URL, while the interfaces to access underlying
knowledge graphs remain the same. More importantly, SRTK may promote the
development of transferable and shareable888The trained models can be easily
shared on HuggingFace hub, e.g. we share our trained checkpoint as drt/srtk-
scorer retrieval algorithms, such that newly developed datasets or algorithms
work across knowledge graphs and can be easier compared and benchmarked.

SRTK has numerous potential use cases that extend beyond KBQA. In knowledge
graph augmented language model pretraining, subgraphs retrieved with SRTK can
be used to enhance language representations with either entity knowledge [45,
37, 36, 24, 10] or triple knowledge [31, 35, 26]. One possible approach is
using SRTK to identify entities, search relations within the linked entities
or with semantic-relevant neighbors, and use the retrieved triples for
language pretraining. In knowledge-enhanced language generation, SRTK may be
used to retrieve relevant and accurate facts with the given prompts [16, 15,
18, 47]. In conversation reasoning and generation, SRTK can be used to
identify mentioned entities and provides semantic-relevant subgraphs as extra
information for responses[43, 21, 33]. In fact verification, SRTK may be used
to retrieve subgraph as reliable facts to verify the statements [3]. One way
to accomplish this is to examine whether certain links exist in the retrieved
subgraph. Furthermore, the subgraphs retrieved by SRTK can be leveraged for
improvement on a variety of downstream tasks [42, 46], like translation [22],
summarization [13] etc.

###  4.2 Positioning to the State of the Art

SRTK stands on the shoulder of giants. It builds upon existing entity linking
services and extends an existing state-of-the-art path expansion algorithm to
offer an off-the-shelf toolkit for subgraph retrieval across various knowledge
graphs. Regarding entity linking on Wikidata, REL [14] is integrated, which
currently achieves the highest micro-F1-strong score on the AIDA CoNLL-YAGO
dataset [12]. Although REL and most other entity linking tools primarily link
entities to Wikipedia, the presence of a maintained mapping between Wikipedia
articles and Wikidata enables their utilization. For entity linking on
DBpedia, DBpedia Spotlight [20] is supported. It relies on pattern match and
thus does not perform as well as neural models [28]. However, due to the
absence of alternative off-the-shelf entity linking services for DBpedia, we
include DBpedia Spotlight as part of the toolkit. For path expansion, we
integrate SR proposed by Zhang et al [44]. They reported state-of-the-art
results on CWQ [32] and WebQSP [41], two datasets for KBQA on Freebase, with
the subgraph retrieved by SR. The retrieved subgraphs are significantly
smaller in size but still have high coverage of answer entities. We further
extend SR to support other knowledge graphs. Although we did not compare the
results of KBQA using subgraphs retrieved by SRTK on datasets of other
knowledge graphs, this is due to the complexities involved in setting up such
comparisons. Besides, evaluating the performance of a specific implementation
of the path expansion algorithm in various settings exceeds the scope of this
paper.

###  4.3 Limitations

SRTK relies on knowledge graph endpoints for up-to-date information, but
network latency and iterative queries slow down retrieval. To address this, we
propose two solutions. Firstly, setting up local endpoints can alleviate the
problem, as demonstrated in our experiments (tutorial available in our
documentation). Secondly, caching known entities’ $k$-hop facts in advance can
build a smaller local graph, an approach currently under development.

Another limitation of SRTK is its dependency on preceding steps, where issues
can accumulate and magnify. For instance, failure to link entities to
knowledge graphs renders subgraph retrieval impossible. One possible solution
is to combine the results from multiple entity linking services or to fallback
to n-gram based methods when neural methods fail so that the mentioned are
more likely to be recognized. We plan to integrate more existing entity
linking services into SRTK.

On the path expansion side, there are two notable limitations. One limitation
is the restricted expansion direction. SRTK currently only expands outward
along directed relations. This means for a triple like (Hakata, locate in,
Fukuoka), Fukuoka can be discovered by following the directed relation locate
in if Hakata is known, but the inversed discovery of Hakata is not possible if
only Fukuoka is known. This limitation arises in knowledge bases lacking
paired inverse relations like Wikidata. Another limitation lies in the
proximity assumption. The current link-then-expand approach assumes that the
target entities lie in a certain proximity to the linked entities. This holds
for most KBQA scenarios but does not generally hold for all subgraph retrieval
situations. The first limitation can be alleviated by allowing inverse
expansion, e.g. constructing SPARQL queries with unknown variables in the
subject position. But this significantly increases complexity, including
challenges of circle avoidance and expansion direction determination. The
second limitation may be solved by replacing entity linking with problem-
specific entity discovery methods to locate entities near the target.

Besides, SRTK currently retrieves subgraphs as sets of triples, excluding
additional affiliated information available in knowledge graphs like Wikidata.
For example, the triple (Merkel, Position Held, Chancellor of Germany)
includes start and end dates. Current methods retrieve this information as
extra triples (position held, start time, 22.11.2005). Future improved
algorithms seek to retrieve all related information simultaneously.

###  4.4 Future Development and Maintenance

The SRTK project has several directions for future development. In addition to
the current capabilities, we plan to add support for additional knowledge
graphs such as YAGO [23]. This would involve integrating an entity linking
service and implementing graph access interfaces for each supported knowledge
graph. Besides, since the abstract access interfaces are implementation-
agnostic, SRTK has the potential to support knowledge graphs queried with
interfaces other than SPARQL. Our ultimate goal is to encourage comparable
methods across different knowledge graphs and to help researchers migrate from
outdated knowledge graphs.

Moving forward, we aim to expand the range of algorithms supported by SRTK.
The current retrieval algorithm is path-centric: it retrieves subgraphs by
selecting the most probable outgoing expansion paths. However, we see room for
improvement in several areas. For example, we could take entities along the
paths into account when expanding subgraphs, and consider both incoming and
outgoing links when expanding from a known entity. This would undoubtedly make
expansion more complex, but it holds promise for future research.

In the medium term, our plans for SRTK include incorporating support for YAGO,
integrating more online entity linking services, and exploring the
compatibility of SRTK with existing information retrieval-based KBQA methods
across various datasets. Looking ahead to the long term, we aspire to
incorporate support for additional retrieval algorithms and integrate SRTK
with popular KBQA models, enabling direct comparisons and benchmarking of
existing KBQA and retrieval methods. Additionally, we are also committed to
continuously maintaining SRTK, addressing any bugs or security
vulnerabilities. To achieve these visions, we also greatly value and encourage
contributions from the open-source community.

##  5 Conclusion

SRTK is an extensible and user-friendly toolkit that focuses on retrieving
semantic-relevant subgraphs. It is built on a state-of-the-art algorithm and
comes with a command line interface and Python API. SRTK streamlines the full
life cycle of subgraph retrieval development and application, providing
customizable pipeline steps. It supports multiple knowledge graphs, including
Freebase, DBpedia, and Wikidata. Future developments include support for
entity linking services, more knowledge graphs, and other retrieval
algorithms.

Resource Availability Statement: Source code for SRTK is available from
Github999https://github.com/happen2me/subgraph-retrieval-toolkit. Its
canonical citation is [29].

## References

  * [1] Auer, S., Bizer, C., Kobilarov, G., Lehmann, J., Cyganiak, R., Ives, Z.: Dbpedia: A nucleus for a web of open data. In: The Semantic Web: 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007+ ASWC 2007, Busan, Korea, November 11-15, 2007. Proceedings. pp. 722–735. Springer (2007)
  * [2] Bollacker, K., Evans, C., Paritosh, P., Sturge, T., Taylor, J.: Freebase: a collaboratively created graph database for structuring human knowledge. In: Proceedings of the 2008 ACM SIGMOD international conference on Management of data. pp. 1247–1250 (2008)
  * [3] Cao, Z., Wei, F., Li, W., Li, S.: Faithful to the original: Fact aware neural abstractive summarization. In: McIlraith, S.A., Weinberger, K.Q. (eds.) Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018. pp. 4784–4791. AAAI Press (2018)
  * [4] Chaudhuri, D., Rony, M.R.A.H., Lehmann, J.: Grounding dialogue systems via knowledge graph aware decoding with pre-trained transformers. In: The Semantic Web: 18th International Conference, ESWC 2021, Virtual Event, June 6–10, 2021, Proceedings 18. pp. 323–339. Springer (2021)
  * [5] Chen, T., Kornblith, S., Norouzi, M., Hinton, G.E.: A simple framework for contrastive learning of visual representations. In: Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event. Proceedings of Machine Learning Research, vol. 119, pp. 1597–1607. PMLR (2020)
  * [6] Christmann, P., Saha Roy, R., Weikum, G.: Beyond NED: Fast and Effective Search Space Reduction for Complex Question Answering over Knowledge Bases. In: Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining. pp. 172–180. ACM, Virtual Event AZ USA (2022)
  * [7] Das, R., Godbole, A., Naik, A., Tower, E., Zaheer, M., Hajishirzi, H., Jia, R., McCallum, A.: Knowledge base question answering by case-based reasoning over subgraphs. In: Chaudhuri, K., Jegelka, S., Song, L., Szepesvári, C., Niu, G., Sabato, S. (eds.) International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA. Proceedings of Machine Learning Research, vol. 162, pp. 4777–4793. PMLR (2022)
  * [8] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: BERT: Pre-training of deep bidirectional transformers for language understanding. In: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). pp. 4171–4186. Association for Computational Linguistics, Minneapolis, Minnesota (2019)
  * [9] Ferragina, P., Scaiella, U.: Fast and accurate annotation of short texts with wikipedia pages. IEEE software 29(1), 70–75 (2011)
  * [10] Févry, T., Baldini Soares, L., FitzGerald, N., Choi, E., Kwiatkowski, T.: Entities as experts: Sparse memory access with entity supervision. In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 4937–4951. Association for Computational Linguistics, Online (2020)
  * [11] Fu, B., Qiu, Y., Tang, C., Li, Y., Yu, H., Sun, J.: A survey on complex question answering over knowledge base: Recent advances and challenges. ArXiv preprint abs/2007.13069 (2020)
  * [12] Hoffart, J., Yosef, M.A., Bordino, I., Fürstenau, H., Pinkal, M., Spaniol, M., Taneva, B., Thater, S., Weikum, G.: Robust disambiguation of named entities in text. In: Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing. pp. 782–792. Association for Computational Linguistics, Edinburgh, Scotland, UK. (2011)
  * [13] Huang, L., Wu, L., Wang, L.: Knowledge graph-augmented abstractive summarization with semantic-driven cloze reward. In: Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. pp. 5094–5107. Association for Computational Linguistics, Online (2020)
  * [14] van Hulst, J.M., Hasibi, F., Dercksen, K., Balog, K., de Vries, A.P.: REL: an entity linker standing on the shoulders of giants. In: Huang, J., Chang, Y., Cheng, X., Kamps, J., Murdock, V., Wen, J., Liu, Y. (eds.) Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020. pp. 2197–2200. ACM (2020)
  * [15] Ji, H., Ke, P., Huang, S., Wei, F., Zhu, X., Huang, M.: Language generation with multi-hop reasoning on commonsense knowledge graph. In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 725–736. Association for Computational Linguistics, Online (2020)
  * [16] Koncel-Kedziorski, R., Bekal, D., Luan, Y., Lapata, M., Hajishirzi, H.: Text Generation from Knowledge Graphs with Graph Transformers. In: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). pp. 2284–2293. Association for Computational Linguistics, Minneapolis, Minnesota (2019)
  * [17] Lan, Y., He, G., Jiang, J., Jiang, J., Zhao, W.X., Wen, J.R.: Complex knowledge base question answering: A survey. IEEE Transactions on Knowledge and Data Engineering (2022)
  * [18] Liu, W., Zhou, P., Zhao, Z., Wang, Z., Ju, Q., Deng, H., Wang, P.: K-BERT: enabling language representation with knowledge graph. In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020. pp. 2901–2908. AAAI Press (2020)
  * [19] Liu, Y., Wan, Y., He, L., Peng, H., Yu, P.S.: KG-BART: knowledge graph-augmented BART for generative commonsense reasoning. In: Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021. pp. 6418–6425. AAAI Press (2021)
  * [20] Mendes, P.N., Jakob, M., García-Silva, A., Bizer, C.: Dbpedia spotlight: shedding light on the web of documents. In: Proceedings of the 7th international conference on semantic systems. pp. 1–8 (2011)
  * [21] Moon, S., Shah, P., Kumar, A., Subba, R.: OpenDialKG: Explainable conversational reasoning with attention-based walks over knowledge graphs. In: Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. pp. 845–854. Association for Computational Linguistics, Florence, Italy (2019)
  * [22] Moussallem, D., Soru, T., Ngonga Ngomo, A.C.: Thoth: neural translation and enrichment of knowledge graphs. In: The Semantic Web–ISWC 2019: 18th International Semantic Web Conference, Auckland, New Zealand, October 26–30, 2019, Proceedings, Part I. pp. 505–522. Springer (2019)
  * [23] Pellissier Tanon, T., Weikum, G., Suchanek, F.: Yago 4: A reason-able knowledge base. In: The Semantic Web: 17th International Conference, ESWC 2020, Heraklion, Crete, Greece, May 31–June 4, 2020, Proceedings 17. pp. 583–596. Springer (2020)
  * [24] Peters, M.E., Neumann, M., Logan, R., Schwartz, R., Joshi, V., Singh, S., Smith, N.A.: Knowledge enhanced contextual word representations. In: Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). pp. 43–54. Association for Computational Linguistics, Hong Kong, China (2019)
  * [25] Piccinno, F., Ferragina, P.: From tagme to wat: a new entity annotator. In: Proceedings of the first international workshop on Entity recognition & disambiguation. pp. 55–62 (2014)
  * [26] Qin, Y., Lin, Y., Takanobu, R., Liu, Z., Li, P., Ji, H., Huang, M., Sun, M., Zhou, J.: ERICA: Improving entity and relation understanding for pre-trained language models via contrastive learning. In: Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). pp. 3350–3363. Association for Computational Linguistics, Online (2021)
  * [27] Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., Liu, P.J.: Exploring the limits of transfer learning with a unified text-to-text transformer. J. Mach. Learn. Res. 21, 140:1–140:67 (2020)
  * [28] Sevgili, Ö., Shelmanov, A., Arkhipov, M., Panchenko, A., Biemann, C.: Neural entity linking:: A survey of models based on deep learning. Semantic Web 13(3), 527–570 (2022)
  * [29] Shen, Y.: happen2me/subgraph-retrieval-toolkit. Zenodo (2023). https://doi.org/10.5281/zenodo.7895612, https://doi.org/10.5281/zenodo.7895612
  * [30] Sun, H., Bedrax-Weiss, T., Cohen, W.: PullNet: Open domain question answering with iterative retrieval on knowledge bases and text. In: Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). pp. 2380–2390. Association for Computational Linguistics, Hong Kong, China (2019)
  * [31] Sun, T., Shao, Y., Qiu, X., Guo, Q., Hu, Y., Huang, X., Zhang, Z.: CoLAKE: Contextualized language and knowledge embedding. In: Proceedings of the 28th International Conference on Computational Linguistics. pp. 3660–3670. International Committee on Computational Linguistics, Barcelona, Spain (Online) (2020)
  * [32] Talmor, A., Berant, J.: The web as a knowledge-base for answering complex questions. In: Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers). pp. 641–651. Association for Computational Linguistics, New Orleans, Louisiana (2018)
  * [33] Tuan, Y.L., Chen, Y.N., Lee, H.y.: DyKgChat: Benchmarking dialogue generation grounding on dynamic knowledge graphs. In: Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). pp. 1855–1865. Association for Computational Linguistics, Hong Kong, China (2019)
  * [34] Vrandečić, D., Krötzsch, M.: Wikidata: a free collaborative knowledgebase. Communications of the ACM 57(10), 78–85 (2014)
  * [35] Wang, X., Gao, T., Zhu, Z., Zhang, Z., Liu, Z., Li, J., Tang, J.: KEPLER: A unified model for knowledge embedding and pre-trained language representation. Transactions of the Association for Computational Linguistics 9, 176–194 (2021)
  * [36] Xiong, W., Du, J., Wang, W.Y., Stoyanov, V.: Pretrained encyclopedia: Weakly supervised knowledge-pretrained language model. In: 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net (2020)
  * [37] Yamada, I., Asai, A., Shindo, H., Takeda, H., Matsumoto, Y.: LUKE: Deep contextualized entity representations with entity-aware self-attention. In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 6442–6454. Association for Computational Linguistics, Online (2020)
  * [38] Yasunaga, M., Bosselut, A., Ren, H., Zhang, X., Manning, C.D., Liang, P.S., Leskovec, J.: Deep bidirectional language-knowledge graph pretraining. Advances in Neural Information Processing Systems 35, 37309–37323 (2022)
  * [39] Yasunaga, M., Ren, H., Bosselut, A., Liang, P., Leskovec, J.: QA-GNN: Reasoning with language models and knowledge graphs for question answering. In: Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 535–546. Association for Computational Linguistics, Online (2021)
  * [40] Yih, W.t., Chang, M.W., He, X., Gao, J.: Semantic parsing via staged query graph generation: Question answering with knowledge base. In: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). pp. 1321–1331. Association for Computational Linguistics, Beijing, China (2015)
  * [41] Yih, W.t., Richardson, M., Meek, C., Chang, M.W., Suh, J.: The value of semantic parse labeling for knowledge base question answering. In: Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers). pp. 201–206. Association for Computational Linguistics, Berlin, Germany (2016)
  * [42] Yu, W., Zhu, C., Li, Z., Hu, Z., Wang, Q., Ji, H., Jiang, M.: A survey of knowledge-enhanced text generation. ACM Computing Surveys 54(11s), 1–38 (2022)
  * [43] Zhang, H., Liu, Z., Xiong, C., Liu, Z.: Grounded conversation generation as guided traverses in commonsense knowledge graphs. In: Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. pp. 2031–2043. Association for Computational Linguistics, Online (2020)
  * [44] Zhang, J., Zhang, X., Yu, J., Tang, J., Tang, J., Li, C., Chen, H.: Subgraph retrieval enhanced model for multi-hop knowledge base question answering. In: Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 5773–5784. Association for Computational Linguistics, Dublin, Ireland (2022)
  * [45] Zhang, Z., Han, X., Liu, Z., Jiang, X., Sun, M., Liu, Q.: ERNIE: Enhanced language representation with informative entities. In: Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. pp. 1441–1451. Association for Computational Linguistics, Florence, Italy (2019)
  * [46] Zhen, C., Shang, Y., Liu, X., Li, Y., Chen, Y., Zhang, D.: A survey on knowledge-enhanced pre-trained language models. ArXiv preprint abs/2212.13428 (2022)
  * [47] Zhou, Y., Sun, Y., Honavar, V.: Improving image captioning by leveraging knowledge graphs. In: 2019 IEEE Winter Conference on Applications of Computer Vision (WACV). pp. 283–293. IEEE Computer Society (2019)