# Indicated domination game

Boštjan Brešara,b Email<EMAIL_ADDRESS>Csilla Bujtásb,c,d Email:
<EMAIL_ADDRESS>Vesna Iršičb,c Email<EMAIL_ADDRESS>Douglas F.
Ralle Email<EMAIL_ADDRESS>Zsolt Tuzad,f Email<EMAIL_ADDRESS>pannon.hu

###### Abstract

Motivated by the success of domination games and by a variation of the
coloring game called the indicated coloring game, we introduce a version of
domination games called the indicated domination game. It is played on an
arbitrary graph $G$ by two players, Dominator and Staller, where Dominator
wants to finish the game in as few rounds as possible while Staller wants just
the opposite. In each round, Dominator indicates a vertex $u$ of $G$ that has
not been dominated by previous selections of Staller, which, by the rules of
the game, forces Staller to select a vertex in the closed neighborhood of $u$.
The game is finished when all vertices of $G$ become dominated by the vertices
selected by Staller. Assuming that both players are playing optimally
according to their goals, the number of selected vertices during the game is
the indicated domination number, $\gamma_{i}(G)$, of $G$.

We prove several bounds on the indicated domination number expressed in terms
of other graph invariants. In particular, we find a place of the new graph
invariant in the well-known domination chain, by showing that
$\gamma_{i}(G)\geq\Gamma(G)$ for all graphs $G$, and by showing that the
indicated domination number is incomparable with the game domination number
and also with the upper irredundance number. In connection with the trivial
upper bound $\gamma_{i}(G)\leq n(G)-\delta(G)$, we characterize the class of
graphs $G$ attaining the bound provided that $n(G)\geq 2\delta(G)+2$. We prove
that in trees, split graphs and grids the indicated domination number equals
the independence number. We also find a formula for the indicated domination
number of powers of paths, from which we derive that there exist graphs in
which the indicated domination number is arbitrarily larger than the upper
irredundance number. We provide some partial results supporting the statement
that $\gamma_{i}(G)=n(G)/2$ if $G$ is a cubic bipartite graph, and leave this
as an open question.

a Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

b Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

c Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

d University of Pannonia, Veszprém, Hungary

e Furman University, USA

f Alfréd Rényi Institute of Mathematics, Budapest, Hungary

Keywords: domination game; indicated coloring; independence number; upper
domination number;

AMS Subj. Class. (2020): 05C57

##  1 Introduction

The coloring game was introduced independently in [12] and [3]. Unlike
combinatorial games in which a winner is decided, the result of the coloring
game gives a graph invariant, which is based on the assumption that both
players are playing optimally according to their goals. A number of variants
of the original game have been introduced, see e.g. [2, 5, 19, 20]. The
following version was proposed by Grytczuk and defined by Grzesik [14].

The _indicated coloring game_ is played on a simple graph $G$ by two players,
and a fixed set $C$ of colors. In each round of the game Ann indicates an
uncolored vertex, and Ben colors it using a color from $C$, obeying just the
proper coloring rule. The goal of Ann is to achieve a proper coloring of the
whole graph, while Ben is trying to prevent this. The minimum cardinality of
the set of colors $C$ for which Ann has a winning strategy is called the
_indicated chromatic number_ , $\chi_{i}(G)$, of a graph $G$.

The _domination game_ , as introduced in [8], is played on a graph $G$ by two
players: Dominator and Staller. They alternate taking moves in which they
select a vertex of $G$. A move is legal if the selected vertex dominates at
least one vertex which is not already dominated by previously played vertices.
The game ends when there are no legal moves, so when the set of played
vertices is a dominating set of $G$. The goal of Dominator is to finish the
game with minimum number of moves, while the aim of Staller is to maximize the
number of moves. If both players play optimally, then the number of moves
played on $G$ is an invariant (see [7, 9]). Therefore, as defined in [8], the
_game domination number_ $\gamma_{\rm g}(G)$ is the number of moves on $G$ if
Dominator starts the game. Many variants of the domination game have been
introduced; see a recent monograph [7] and a few papers [4, 9, 11, 13, 16].
Having in mind the indicated coloring game, we propose the following variant
of the domination game.

The _indicated domination game_ is played on a graph $G$ by two players,
Dominator and Staller, who take turns making a move. In each of his moves,
Dominator indicates a vertex $v$ of the graph that has not been dominated in
the previous moves, and Staller chooses (or selects) any vertex from the
closed neighborhood of $v$, and adds it to a set $D$ that is being built
during the game. The game ends when there is no undominated vertex left, that
is, when $D$ is a dominating set. The goal of Dominator is to minimize the
size of $D$, while Staller wants just the opposite. Providing that both
players are playing optimally with respect to their goals, the size of the
resulting set $D$ is the _indicated domination number_ of $G$, and is denoted
by $\gamma_{\rm i}(G)$.

In the following section, we establish the notation and present basic
definitions, while in Section 3 we give some preliminary results. In
particular, we prove that $\Gamma(G)\leq\gamma_{i}(G)\leq\gamma_{\rm gr}(G)$,
where $\Gamma(G)$ is the upper domination number and $\gamma_{\rm gr}(G)$ is
the Grundy domination number of a graph $G$. In Section 4, we prove that for a
graph $G$ with minimum degree $\delta$ and order $n$, where $n\geq 2\delta+2$,
we have $\gamma_{\rm i}(G)=n-\delta$ if and only if $G$ contains a spanning
subgraph $K_{\delta,n-\delta}$ with an additional property that the part of
the bipartition of size $n-\delta$ is an independent set in $G$. In Section 5,
we prove that in several families of graphs (namely trees, split graphs,
grids, and connected bipartite cubic graphs with at most 12 vertices) the
indicated domination number equals the independence number. On the other hand,
the indicated domination number can be arbitrarily larger than the upper
irredundance number (and thus also the independence number), which is
established in Section 6. This is derived from the formula for the indicated
domination number of the $k$-th power of the path $P_{n}$, which is roughly
$\gamma_{\rm i}(P_{n}^{k})=\Theta\Big{(}\frac{\log k}{k}\,n\Big{)}$ as
$n\to\infty$. In Section 7, we propose several open questions.

##  2 Notation

Let $G$ be a graph. We denote the number of vertices of $G$ by $n(G)$. If
$S\subseteq V(G)$, then the subgraph induced by $S$ is denoted by $G[S]$. For
a vertex $v\in V(G)$, the _(open) neighborhood_ $N(v)$ is the set of neighbors
of $v$, and the _closed neighborhood_ is $N[v]=N(v)\cup\\{v\\}$. If
$S\subseteq V(G)$, then $N[S]=\bigcup_{v\in S}N[v]$.

For a vertex $x\in S$, every vertex in $N[S]-N[S-\\{x\\}]$ is called a
_private neighbor of $x$ with respect to $S$_.111Observe that every vertex
isolated in $G[S]$ is viewed as a private neighbor of itself by definition. A
set $S\subseteq V(G)$ is an _irredundant set_ if every vertex in $S$ has a
private neighbor with respect to $S$. The smallest and largest cardinalities
of a maximal irredundant set of $G$ are denoted by ${\rm ir}(G)$ and ${\rm
IR}(G)$, respectively.

A set $S\subseteq V(G)$ is an _independent set_ in a graph $G$ if the vertices
in $S$ are pairwise nonadjacent. The maximum size of an independent set of $G$
is denoted by $\alpha(G)$. An _edge cover_ of $G$ is a set $F\subseteq E(G)$
such that every vertex of $G$ is incident to some edge in $F$. We denote the
minimum size of an edge cover of $G$ by $\rho(G)$. Note that notation
$\beta^{\prime}(G)$ is also used in the literature. Recall that combining
König’s and Gallai’s Theorems gives $\alpha(G)=\rho(G)$ for a bipartite graph
$G$ without isolated vertices.

A vertex $v\in V(G)$ _dominates_ itself and its neighbors. A subset of
vertices $D\subseteq V(G)$ is a _dominating set_ of $G$ if it dominates all
vertices of $G$, i.e. $N[D]=V(G)$. This means that every vertex from $V(G)-D$
has a neighbor in $D$. The minimum cardinality of a dominating set of $G$ is
the _domination number_ , $\gamma(G)$, of $G$.

A dominating set $D$ in $G$ is a _minimal dominating set_ if no proper subset
of $D$ is a dominating set. That is, $D$ is a minimal dominating set if and
only if every $x\in D$ has a private neighbor with respect to $D$. The maximum
cardinality of a minimal dominating set is the _upper domination number_ ,
$\Gamma(G)$, of $G$. We recall the following results.

######  Theorem 2.1 ([10, Theorem 5]).

If $G$ is a bipartite graph, then $\alpha(G)=\Gamma(G)={\rm IR}(G)$.

######  Theorem 2.2 ([17, Theorem 9]).

If $G$ is a chordal graph, then $\alpha(G)=\Gamma(G)={\rm IR}(G)$.

Given a graph $G$, a sequence $S=(v_{1},\ldots,v_{k})$ of vertices of $G$ is a
dominating sequence if for each $i$

$N[v_{i}]-\cup_{j=1}^{i-1}N[v_{j}]\not=\emptyset$ (1)

and the set of vertices from $S$ dominates $G$. We call the length $k$ of the
longest such sequence $S$ the Grundy domination number, $\gamma_{\rm gr}(G)$,
of $G$. Clearly, $\gamma(G)\leq\gamma_{\rm gr}(G)$.

##  3 Preliminary results

A well known domination chain [15] was extended with the Grundy domination
number in [6]:

${\rm ir}(G)\leq\gamma(G)\leq i(G)\leq\alpha(G)\leq\Gamma(G)\leq{\rm
IR}(G)\leq\gamma_{\rm gr}(G)\,.$

The following proposition explains where indicated domination number fits in
this chain.

######  Proposition 3.1.

If $G$ is a graph, then

$\Gamma(G)\leq\gamma_{\rm i}(G)\leq\gamma_{\rm gr}(G)\,.$

In addition, $\gamma_{\rm i}$ is incomparable with both $\gamma_{\rm g}$ and
${\rm IR}$.

###### Proof.

Note that the definition of the indicated domination game implies that the
sequence of vertices selected by Staller is a dominating sequence, so
$\gamma_{\rm i}(G)\leq\gamma_{\rm gr}(G)$.

Let $D$ be a minimal dominating set of cardinality $\Gamma(G)$. We provide a
strategy for Staller that will prove that $\Gamma(G)\leq\gamma_{\rm i}(G)$.
The basic ingredient of this strategy is for her to always select a vertex
from $D$. She can do so regardless of which vertex Dominator indicates. Unless
all vertices from $D$ have been selected, there exists an undominated vertex
(a private neighbor of an unselected vertex from $D$). This shows that
$\Gamma(G)\leq\gamma_{\rm i}(G)$.

In the rest of the proof we present infinite families of graphs showing that
$\gamma_{\rm i}$ is incomparable with both $\gamma_{\rm g}$ and ${\rm IR}$.
Stars $K_{1,n}$ show that $\gamma_{\rm i}$ can be arbitrarily larger than
$\gamma_{\rm g}$, since $\gamma_{\rm i}(K_{1,n})=n$ and $\gamma_{\rm
g}(K_{1,n})=1$. Second powers of paths (see Corollary 6.3) show that
$\gamma_{\rm i}$ can be arbitrarily larger than ${\rm IR}$.

To see that ${\rm IR}$ can be arbitrarily larger than $\gamma_{\rm i}$, we
consider the following family of graphs. Let $H_{n}$ be the graph obtained
from two disjoint copies of $K_{n}$ with vertices $u_{1},\ldots,u_{n}$ and
$v_{1},\ldots,v_{n}$ by adding edges $u_{i}v_{i}$ for all
$i\in\\{2,\ldots,n\\}$. Notice that $H_{n}$ is isomorphic to the graph
$K_{n}\,\square\,K_{2}$ with one edge removed. It is easy to see that ${\rm
IR}(H_{n})=n-1$ (it is attained for example by the maximal irredundant set
$\\{u_{2},\ldots,u_{n}\\}$). On the other hand, we have $\gamma_{\rm
i}(H_{n})\geq\gamma(H_{n})=2$, and if Dominator first indicates $u_{1}$ and
then $v_{1}$, we get $\gamma_{\rm i}(H_{n})=2$. Note that this also shows that
in general $\gamma_{\rm i}(G)$ and $\gamma_{\rm i}(G-e)$ can be arbitrarily
far apart since $\gamma_{\rm
i}(K_{n}\,\square\,K_{2})\geq\Gamma(K_{n}\,\square\,K_{2})=n$.

Last, we present a family of graphs for which $\gamma_{\rm g}$ is arbitrarily
larger than $\gamma_{\rm i}$. Let $D_{1}$ be a graph obtained from a cycle
$C_{9}$ with vertices $x_{1},\ldots,x_{9}$ by adding edges $x_{1}x_{3}$,
$x_{4}x_{6}$ and $x_{7}x_{9}$. Since Dominator can in turn indicate vertices
$x_{2}$, $x_{5}$ and $x_{8}$, he has a strategy that ensures $\gamma_{\rm
i}(D_{1})\leq 3$. Since $\gamma_{\rm i}(D_{1})\geq\gamma(D_{1})=3$, we have
$\gamma_{\rm i}(D_{1})=3$. On the other hand, it is easy to see that
$\gamma_{\rm g}(D_{1})=4$. Let $D_{n}$ be a disjoint union of $n$ copies of
the graph $D_{1}$. Since $\gamma_{\rm i}(D_{n})\geq\gamma(D_{n})=3n$ and
Dominator can in turn indicate vertices of degree two, we have $\gamma_{\rm
i}(D_{n})=3n$. But since Staller’s strategy in the domination game on $D_{n}$
can be to reply in the same copy of $D_{1}$ as Dominator played, we get
$\gamma_{\rm g}(D_{n})\geq 4n$ (because under that strategy, in each copy the
game ends after an even number, four, of moves). Thus $\gamma_{\rm
g}(D_{n})-\gamma_{\rm i}(D_{n})\geq n$. Alternatively, we can consider a
connected graph $E_{n}$ obtained from $C_{3n}$ by adding edges
$x_{1}x_{3},x_{4}x_{6},\ldots,x_{3n-2}x_{3n}$. In this case, $\gamma_{\rm
i}(E_{n})=n$, while $\gamma_{\rm g}(E_{n})\geq n+\frac{n}{10}$ (the last
follows by an argument similar as in [18, Theorem 4.1]). ∎

The diagram in Figure 1 shows the relations between the parameters from
Proposition 3.1.

${\rm ir}$$\gamma$$i$$\alpha$$\Gamma$$\mathbf{\gamma_{\rm i}}$${\rm
IR}$$\gamma_{\rm g}$$\gamma_{\rm gr}$ Figure 1: Relations between the
domination and independence invariants.

There are several classes of graphs with a transparent structure where the
parameters discussed in Proposition 3.1 coincide. For example, the graphs $G$
below all have the property $\Gamma(G)=\gamma_{\rm gr}(G)$ as listed in [1]:
hypercubes; complete multipartite graphs, $G=K_{n_{1},\ldots,n_{k}}$, such
that $n_{1}\geq\cdots\geq n_{k}$, $k\geq 2$, and $n_{k-1}\geq 2$; prisms over
complete graphs, $G=K_{n}\,\square\,K_{2}$, for $n\geq 2$; large families of
Kneser graphs; the class of (twin-free, connected) cographs. It is also proved
in [1] that the join operation preserves that property. By Proposition 3.1 all
the graphs from the above families have the indicated domination number equal
to their upper domination number. By Theorem 2.1 this in turn implies that the
bipartite graphs among the above families have their indicated domination
number equal to their independence number.

However, the difference between the indicated domination number and the
independence number can be arbitrarily large. For example,
$\alpha(K_{n}\,\square\,K_{2})=2$ and $\gamma_{\rm
i}(K_{n}\,\square\,K_{2})=n$. Similarly, the difference between the Grundy
domination number and the indicated domination number can be arbitrarily
large. For example, $\gamma_{\rm gr}(P_{n})=n-1$ and $\gamma_{\rm
i}(P_{n})=\left\lceil\frac{n}{2}\right\rceil$ as will be proven in Corollary
5.3.

##  4 Upper bound on $\gamma_{\rm i}$ and extremal graphs

Using a bound from Proposition 3.1 combined with [6, Proposition 2.1] we
obtain:

$\gamma_{\rm i}(G)\leq\gamma_{\rm gr}(G)\leq n(G)-\delta(G).$ (2)

In the following theorem we characterize the graphs $G$ that attain the bound
$\gamma_{\rm i}(G)=n(G)-\delta(G)$ under the assumption that $n(G)\geq
2\delta(G)+2$.

######  Theorem 4.1.

A graph $G$ with minimum degree $\delta$ and order $n$, where $n\geq
2\delta+2$, has $\gamma_{\rm i}(G)=n-\delta$ if and only if it contains a
spanning subgraph $K_{\delta,n-\delta}$ with an additional property that the
part of the bipartition of size $n-\delta$ is an independent set in $G$.

###### Proof.

Let $G$ be a graph, which has a spanning subgraph $K_{\delta,n-\delta}$ and
the only edges of $G$ that are not in $K_{\delta,n-\delta}$, if any, are
between two vertices in the part of size $\delta$. Let the indicated
domination game be played on $G$. Regardless of which vertex is indicated by
Dominator in his first move, Staller selects a vertex from the part of size
$n-\delta$. In this way, all vertices in the part of size $\delta$ become
dominated after the first selection of Staller. Therefore, Dominator will in
his subsequent moves need to indicate only vertices in the part of size
$n-\delta$, and Staller’s strategy is simply to select the vertex that
Dominator indicated in his move. In this way, Staller ensures that at least
$n-\delta$ vertices will be chosen. Thus, $\gamma_{\rm i}(G)\geq n-\delta$,
and combining this with (2) we get $\gamma_{\rm i}(G)=n-\delta$.

For the converse, let $G$ be a graph on $n$ vertices, where $n\geq 2\delta+2$,
such that $\gamma_{\rm i}(G)=n-\delta$. Let the indicated domination game be
played on $G$. If after the first selection of Staller more than $\delta+1$
vertices were dominated, then at most $n-\delta-1$ vertices will be chosen by
Staller when the indicated domination game ends on $G$, a contradiction.
Therefore, Staller needs to select a vertex of degree $\delta$ in her first
move. For the same reason, since $\gamma_{\rm i}(G)=n-\delta$, in all of her
subsequent moves Staller needs to select a vertex that dominates only one
vertex that was not dominated earlier. Let $x$ be the vertex selected in the
first move of Staller, and let $N_{G}(x)=\\{u_{1},\ldots,u_{\delta}\\}$. Let
$R=V(G)-N_{G}[x]$. If there existed a vertex $v\in R$ such that $v$ had no
neighbors in $N_{G}(x)$, then Dominator’s next move would be to indicate $v$,
and after Staller selected a vertex that dominates $v$, at least two new
vertices would become dominated, a contradiction. Therefore, every vertex in
$R$ has at least one neighbor in $N_{G}(x)$.

Now, suppose that there exists a vertex in $R$, say $w_{0}$, that has a
neighbor in $R$, and let $w_{1},\ldots,w_{k}$ be the neighbors of $w_{0}$ from
$R$. For every vertex $w_{i}$, where $i\in\\{0,\ldots,k\\}$, there exists a
vertex $u_{j_{i}}\in N_{G}(x)$ such that $w_{i}$ is the only neighbor of
$u_{j_{i}}$ in $R$. Indeed, if for some $w_{i}$ such a vertex $u_{j_{i}}$
would not exist, then Dominator could indicate $w_{i}$ in his second move, and
regardless of which vertex Staller would select in her second move to dominate
$w_{i}$ at least two new vertices would become dominated in that move, which
is a contradiction. Since $\deg(w_{0})\geq\delta$, we infer that $w_{0}$ has
(at least) $\delta-k$ neighbors in $N_{G}(x)$. Clearly, all of the neighbors
of $w_{0}$ in $N_{G}(x)$ are distinct from vertices $u_{j_{i}}$, where
$i\in[k]$, which implies that $w_{0}$ has exactly $\delta-k$ neighbors in
$N_{G}(x)$. In addition, $k\leq\delta-1$, since all vertices $u_{j_{i}}$,
where $i\in\\{0,1,\ldots,k\\}$, are pairwise distinct. Therefore, since
$n>2\delta+1\geq|N_{G}[x]|+k+1$, we infer that there exists a vertex $z\in
R-\\{w_{0},\ldots,w_{k}\\}$. If $z$ has a neighbor in $R$, then, by the same
reason as earlier, there exists a vertex $u^{\prime}$ in $N_{G}(x)$ such that
$z$ is the only neighbor of $u^{\prime}$ from $R$. However, every vertex in
$N_{G}(x)$ has a neighbor in $\\{w_{0},\ldots,w_{k}\\}$, therefore $z$ cannot
be adjacent to any vertex in $R$. Since $\deg(z)\geq\delta$, we infer
$N_{G}(z)=N_{G}(x)$, which is again a contradiction, since each $u_{j_{i}}\in
N_{G}(x)$ has only one neighbor in $R$. The assumption that there exists an
edge between two vertices in $R$ led us to a contradiction, therefore
$R\cup\\{x\\}$ is independent, and $K_{\delta,n-\delta}$ is a spanning
subgraph of $G$ with the part of the bipartition of size $n-\delta$ being
independent. ∎

##  5 Graphs with $\gamma_{\rm i}=\alpha$

In this section, we present several classes of graphs whose indicated
domination number equals their independence number. Naturally, due to
Proposition 3.1, the independence number of any of these graphs is equal to
the upper domination number.

Recall that a graph is split if its vertex set can be partitioned into a
clique and an independent set. A split partition of a split graph $G$ is a
pair $(K,I)$ such that $K$ is a clique, $I$ is an independent set, $K\cup
I=V(G)$ and $K\cap I=\emptyset$. It was proven in [6] that if $G$ is a split
graph with split partition $(K,I)$, then

$\gamma_{gr}(G)=\left\\{\begin{array}[]{ll}\alpha(G),&\hbox{if every two
vertices in $K$ have a common neighbor in $I$;}\\\
\alpha(G)+1,&\hbox{otherwise.}\end{array}\right.$

We next show that the second line in the above equation never appears if
$\gamma_{\rm gr}$ is replaced with $\gamma_{\rm i}$.

######  Proposition 5.1.

If $G$ is a split graph, then $\gamma_{\rm i}(G)=\alpha(G)$.

###### Proof.

Let $(K,I)$ be the split partition of $G$. We can assume that $I$ is a maximum
independent set, and thus every vertex in $K$ has a neighbor in $I$.
Dominator’s strategy in each of his moves is to indicate a vertex $x$ from $I$
that has not been dominated by the vertices previously chosen by Staller.
After all vertices from $I$ have been dominated by Staller’s selected
vertices, the vertices in $K$ have also been dominated since $K$ is a clique
and each vertex from $K$ has a neighbor in $I$. Hence at most $|I|=\alpha(G)$
vertices were chosen by Staller, and we infer that $\gamma_{\rm
i}(G)\leq\alpha(G)$. The reverse inequality follows from Proposition 3.1. ∎

To see that trees enjoy the equality considered in this section is a bit less
straightforward.

######  Theorem 5.2.

If $T$ is a tree, then $\gamma_{\rm i}(T)=\alpha(T)$.

###### Proof.

Let $F$ be a minimum edge cover of the tree $T$. Since $T$ is bipartite,
$|F|=\rho(G)=\alpha(T)$. Choose a leaf $r$ of $T$ and consider $T$ as a rooted
tree with $r$ as its root, by which the notions of parent and child can be
used in $T$. Let an indicated domination game be played in $T$. We will
present a strategy of Dominator, which ensures that at most $\alpha(T)$
vertices will be selected during the game.

In the first move, Dominator indicates vertex $r$, which forces Staller to
dominate both $r$ and its child $s$. Note that $rs\in F$, and that after the
first move of Staller both endvertices of this edge from $F$ become dominated.
We will say that an edge $f\in F$ is saturated if both of its endvertices are
dominated. We claim that Dominator can ensure that after every move of
Staller, a new edge from $F$ becomes saturated. In other words, after the
$i^{th}$ move of Staller, Dominator can ensure that at least $i$ edges from
$F$ are saturated. This is clearly true after the first move of Staller. In
the subsequent moves, as long as there are still some undominated vertices
left, Dominator considers the vertex of $T$ which is the closest to $r$ among
all undominated vertices. Let this vertex be denoted by $u$, and let $uv\in F$
for a neighbor $v$ of $u$. Now, we consider several possibilities that need to
be reflected in Dominator’s strategy. With this, Dominator will achieve that a
new edge of $F$ becomes saturated after every move of Staller, and, in
addition, that the set of dominated vertices induces a connected subgraph of
$T$ (there is one exception case to this property, in which case Dominator can
achieve that after the subsequent move of Staller the set of dominated
vertices again induces a connected subgraph of $T$).

If $v$ is the parent of $u$, then it is clear, by how $u$ is defined, that $v$
has been dominated in some of the previous moves. In this case, the strategy
of Dominator is to indicate $u$. In this way, $u$ will become dominated after
the following move of Staller, and so the edge $uv$ becomes saturated, by
which the number of saturated edges from $F$ increases by one. Additionally,
the set of dominated vertices still induces a connected subgraph. Next, assume
that $u$ is the parent of $v$. It may happen that $v$ is already dominated.
(This is the case when the set of dominated vertices does not induce a tree,
and how this happens will be explained in the next case.) If this is indeed
so, then Dominator indicates $u$, and in the following move of Staller, $u$
will become dominated and $uv\in F$ will thus become saturated. The remaining
possibility is that $v$ is not dominated. By the strategy of Dominator, we can
argue that all children of $v$ are undominated at this point. Dominator’s
strategy in this case is to indicate $v$. If $v$ or $u$ is selected by Staller
in the next move, then $uv\in F$ becomes saturated and the set of dominated
vertices is connected, as desired. Otherwise, a child $x$ of $v$ is selected
by Staller, and let $xy$ be the edge of $F$, which covers $x$. Note that
either $y=v$ or $y$ is a child of $x$. In either case, the edge $xy\in F$
becomes saturated. In this case (that is, when a child $x$ of $v$ is selected
by Staller), we are in the situation when the set of dominated vertices is not
connected, but, as explained earlier, Dominator’s next move is to indicate
$u$. In this way, $u$ becomes dominated, and since $v$ was dominated in the
preceding move, the edge $uv\in F$ becomes saturated. Thus, after these two
consecutive moves, the set of vertices in $D$ that are dominated induces a
connected subgraph again.

Since after each move of Staller, the number of saturated edges from $F$
increased, we infer that at most $|F|=\alpha(T)$ vertices are chosen by
Staller when the game ends. Since $\gamma_{\rm i}(T)\geq\alpha(T)$ by
Proposition 3.1, the stated equality is proved. ∎

######  Corollary 5.3.

If $n\geq 1$, then $\gamma_{\rm i}(P_{n})=\left\lceil\frac{n}{2}\right\rceil.$

In the next result, we prove for yet another family of graphs, namely the
grids, that their indicated domination number equals the independence number.

######  Theorem 5.4.

If $m,n\geq 1$, then $\gamma_{\rm
i}(P_{m}\,\square\,P_{n})=\alpha(P_{m}\,\square\,P_{n})=\left\lceil\frac{mn}{2}\right\rceil$.

###### Proof.

Let $V(P_{m})=\\{x_{1},\ldots,x_{m}\\}$ and
$V(P_{n})=\\{y_{1},\ldots,y_{n}\\}$. We divide the proof into two cases,
depending on whether both $m$ and $n$ are odd or not.

First, assume that at least one of $m$ and $n$ is an even integer, and, by
symmetry, we may assume with no loss of generality that $m$ is even. Consider
the partition of $V(P_{m}\,\square\,P_{n})$ into pairs of adjacent columns.
Namely, let $C_{i}=\\{x_{2i-1},x_{2i}\\}\times V(P_{n})$, for all $i\in[m/2]$.
The strategy of Dominator, to achieve his goal that at most $mn/2$ vertices
will be selected during the indicated domination game on
$P_{m}\,\square\,P_{n}$, is divided into two phases. In the first phase, he
deals with each of the sets $C_{i}$, proceeding in their natural order, while
in the process some of the vertices of $C_{i}$, for all $i\in[m/2]$, may be
left undominated. In the second phase, he indicates the vertices that were
left undominated in the first phase one by one.

Let us first present the strategy of Dominator in $C_{1}$. Whenever Dominator
indicates a vertex of $C_{1}$, that vertex is in the column $\\{x_{2}\\}\times
V(P_{n})$. Dominator can start by indicating an arbitrary vertex of that
column, say $(x_{2},y_{1})$, and then proceeds by indicating vertices of that
column by obeying only one rule, which we explain next. At a given point in
the game we say that the pair $\\{(x_{2i-1},y_{j}),(x_{2i},y_{j})\\}$, where
$i\in[m/2]$ and $j\in[n]$, is empty if neither vertex in the pair has been
dominated up to that point in the game. The strategy of Dominator while
dealing with the set $C_{1}$ in the first phase is to find an arbitrary empty
pair $\\{(x_{1},y_{j}),(x_{2},y_{j})\\}$, if it exists, and indicate
$(x_{2},y_{j})$, as long as there exists an empty pair in $C_{1}$. Thus, in
her next move, Staller has to dominate $(x_{2},y_{j})$. She can do this by
choosing either $(x_{2},y_{j})$ or one of its neighbors. In either case, the
pair $\\{(x_{1},y_{j}),(x_{2},y_{j})\\}$ is no longer empty after her move.
Clearly, if the move of Staller is to choose
$(x_{1},y_{j}),(x_{2},y_{j-1}),(x_{2},y_{j})$ or $(x_{2},y_{j+1})$, then it
may happen that additional pairs of $C_{1}$ become non-empty. In this case,
regardless of which of the vertices
$(x_{1},y_{j}),(x_{2},y_{j-1}),(x_{2},y_{j})$ or $(x_{2},y_{j+1})$ is chosen
by Staller, the chosen vertex is the first vertex of its corresponding pair
that was chosen during the game, and since its neighboring pairs have become
non-empty (if they were not already non-empty before that move), the other
vertex of the pair in which the chosen vertex lies will never be selected by
Staller during the first phase of the game. It is also possible, that Staller
choses $(x_{3},y_{j})$ to dominate $(x_{2},y_{j})$. In this case,
$(x_{2},y_{j})$ becomes dominated and the pair
$\\{(x_{1},y_{j}),(x_{2},y_{j})\\}$ becomes non-empty, yet the move of Staller
choosing $(x_{3},y_{j})$ will be considered when dealing with $C_{2}$. The
first step of the game in the first phase, dealing with $C_{1}$, ends when all
pairs of $C_{1}$ have become non-empty. Note that by the strategy of
Dominator, in each pair $\\{(x_{1},y_{j}),(x_{2},y_{j})\\}$ at most one of the
vertices has been chosen by Staller, and since all pairs in $C_{1}$ have
become non-empty, at most one of the vertices in each pair remains
undominated. Clearly, if a vertex from a pair was chosen, then in the
corresponding pair both vertices have been dominated. We summarize these
observations as follows: after dealing with $C_{1}$ in the first phase,
$\ell_{1}$ vertices of $C_{1}$ have been chosen, and at most $n-\ell_{1}$
vertices from $C_{1}$ have been left undominated.

Dominator proceeds by dealing with $C_{2}$, and the only difference from the
initial case when dealing with $C_{1}$ is that some vertices $(x_{3},y_{j})$
may have already been chosen by Staller. More generally, when Dominator starts
to deal with $C_{i}$, where $2\leq i\leq m/2$, some vertices
$(x_{2i-1},y_{j})$ may have already been chosen by Staller while dealing with
$C_{i-1}$. This also implies that the corresponding pairs
$\\{(x_{2i-1},y_{j}),(x_{2i},y_{j})\\}$, and their eventual neigboring pairs,
$\\{(x_{2i-1},y_{j-1}),(x_{2i},y_{j-1})\\}$ and
$\\{(x_{2i-1},y_{j+1}),(x_{2i},y_{j+1})\\}$, are already non-empty when
Dominator starts to deal with $C_{i}$. The strategy of Dominator is the same
as when dealing with $C_{1}$. Notably, Dominator finds an arbitrary empty pair
$\\{(x_{2i-1},y_{j}),(x_{2i},y_{j})\\}$, if it exists, and indicates
$(x_{2i},y_{j})$, as long as there exists an empty pair in $C_{i}$. By using
the same arguments as in the previous paragraph, Dominator can ensure that
after dealing with $C_{i}$ in the first phase, $\ell_{i}$ vertices of $C_{i}$
have been chosen, and at most $n-\ell_{i}$ vertices from $C_{i}$ have been
left undominated. The first phase is over after Dominator deals with
$C_{m/2}$. By that time, Staller has chosen $\sum_{i=1}^{m/2}{\ell_{i}}$
vertices, while at most

$\sum_{i=1}^{m/2}{(n-\ell_{i})}=\frac{mn}{2}-\sum_{i=1}^{m/2}{\ell_{i}}$

vertices of $P_{m}\,\square\,P_{n}$ have been left undominated. Now, the
second phase begins, in which Dominator indicates the remaining undominated
vertices one by one, in any order. Hence, Staller will additionally select at
most $\frac{mn}{2}-\sum_{i=1}^{m/2}{\ell_{i}}$ vertices, which together with
vertices selected in the first phase contributes to at most $\frac{mn}{2}$
chosen vertices during the entire game. Hence, $\gamma_{\rm
i}(P_{m}\,\square\,P_{n})\leq\frac{mn}{2}=\alpha(P_{m}\,\square\,P_{n})$,
which combined with Proposition 3.1 implies the stated result.

Second, consider the case when both $m$ and $n$ are odd. In this case,
partition $V(P_{m}\,\square\,P_{n})$ into $\frac{m+1}{2}$ sets, namely
$C_{0}=\\{x_{1}\\}\times V(P_{n})$ and $C_{i}=\\{x_{2i},x_{2i+1}\\}\times
V(P_{n})$, where $1\leq i\leq\frac{m-1}{2}$. The proof is similar to the proof
of the previous case in which $m$ was even, the only difference is in the
first step, where Dominator deals with the first column $C_{0}$, and which we
explain next.

Dominator uses the following strategy when dealing with $C_{0}$, which lasts
as long as there is an undominated vertex left in $C_{0}$. The strategy
consists of two phases. In the first phase, Dominator starts by indicating
$(x_{1},y_{1})$, and then, in every further step, he indicates the vertex
$(x_{1},y_{i+2})$ if $i$ is the largest index such that $(x_{1},y_{i})$ is
dominated and $i\leq n-2$. By the choices of Staller, a vertex of $C_{0}$
becomes dominated by itself or one of its neighbors (possibly it is dominated
by a neighbor from $C_{1}$, which will then be considered when dealing with
$C_{1}$). If Staller chose $(x_{1},y_{i+3})$ in one of her moves, then after
the first phase is over, vertex $(x_{1},y_{i+1})$ remains undominated. Now,
note that vertices chosen by Staller together with vertices that are not yet
dominated after the first phase form an independent set of the path induced by
the first column. In the second phase, Dominator selects vertices of $C_{0}$
that have not been dominated in the first phase (if any) one by one, and in
this way all vertices of $C_{0}$ become dominated. By the previous
observation, Staller has chosen at most $\alpha(P_{n})=\frac{n+1}{2}$ vertices
in $C_{0}$.

The rest of the strategy of Dominator is exactly the same as in the previous
case. Hence we conclude that Dominator can ensure that at most
$\frac{(m-1)n}{2}$ vertices will be selected to dominate the vertices in
$C_{1}\cup\cdots\cup C_{\frac{m-1}{2}}$. Together with the bound on the number
of vertices from $C_{0}$ selected in the first step of the game, we infer that
at most

$\frac{n+1}{2}+\frac{(m-1)n}{2}=\frac{mn+1}{2}=\left\lceil\frac{mn}{2}\right\rceil$

vertices will be selected during the game on $P_{m}\,\square\,P_{n}$. We
readily infer that $\gamma_{\rm
i}(P_{m}\,\square\,P_{n})=\left\lceil\frac{mn}{2}\right\rceil$. ∎

The next family of graphs $G$ for which we suspect that $\gamma_{\rm
i}(G)=\alpha(G)$ are cubic bipartite graphs. We checked by computer that the
equality holds for all (cubic) bipartite graphs $G$ with $n(G)\leq 10$. Next,
we extend this result to $n(G)\leq 12$.

######  Proposition 5.5.

If $G$ is a connected, cubic bipartite graph of order at most $12$, then
$\gamma_{\rm i}(G)=\frac{n(G)}{2}=\alpha(G)$.

###### Proof.

By the observations preceding the proposition, it remains to consider the case
when $n(G)=12$. Let $A=\\{a_{1},\ldots,a_{6}\\}$ and
$B=\\{b_{1},\ldots,b_{6}\\}$ be the partite sets of $G$. For $j\geq 1$, we let
$s_{j}$ denote the vertex chosen by Staller on her $j^{th}$ move and let
$S_{j}=\\{s_{1},\ldots,s_{j}\\}$. In addition, $d_{i}$ will denote the vertex
indicated by Dominator in his $i^{th}$ move, for $i\geq 2$. We provide a
strategy for Dominator that will ensure at most $6$ vertices are chosen by
Staller. Without loss of generality $s_{1}=a_{1}$ and
$N(a_{1})=\\{b_{1},b_{2},b_{3}\\}$. Dominator indicates $d_{2}=b_{4}$. If
$s_{2}=b_{4}$, then $|N[S_{2}]|=8$, which leaves four undominated vertices. At
most four more vertices will be chosen by Staller. Otherwise, $s_{2}\in
N(b_{4})\cap(A-\\{a_{1}\\})$. Reindexing if necessary we assume $s_{2}=a_{2}$.
If $\\{b_{5},b_{6}\\}\subseteq N(a_{2})$, then $S_{2}$ dominates eight
vertices and thus at most six vertices will be chosen by Staller. If $a_{2}$
is adjacent to only one, say $b_{5}$, of $b_{5}$ or $b_{6}$, then Dominator
points to $b_{6}$. Now, regardless of which vertex Staller chooses from
$\\{b_{6},a_{3},a_{4},a_{5},a_{6}\\}$ it is easy to see that $|N[S_{3}]|\geq
9$, which implies that Staller will choose at most $6$ vertices. Therefore, we
may assume that $N(s_{2})\cap\\{b_{4},b_{5},b_{6}\\}=\\{b_{4}\\}$, and this
implies that $|N(a_{2})\cap\\{b_{1},b_{2},b_{3}\\}|=2$. Note that we now have
$(N(b_{5})\cup N(b_{6}))\subseteq\\{a_{3},a_{4},a_{5},a_{6}\\}$. Dominator
then points to $d_{3}=b_{5}$. If $s_{3}=b_{5}$, then $|N[S_{3}]|=10$ which
implies that Staller can choose at most five vertices when the game has ended.
Thus, we may assume that Staller chooses $s_{3}\in
N(b_{5})\cap\\{a_{3},a_{4},a_{5},a_{6}\\}$. By reindexing if necessary we
assume that $s_{3}=a_{3}$. Similar to the above argument, if $a_{3}b_{6}\in
E(G)$, then Staller can choose at most six vertices when the game has ended.
Hence, we may assume that $b_{6}\notin N(a_{3})$. Dominator now indicates
$d_{4}=b_{6}$. Staller must choose $s_{4}\in\\{b_{6},a_{4},a_{5},a_{6}\\}$,
and it follows that $|V(G)-N[S_{4}]|\leq 2$. Therefore, $\gamma_{\rm i}(G)\leq
6$. The reverse inequality follows by Proposition 3.1. ∎

We could not extend the above reasoning to graphs of larger order. Thus it
remains open whether $\gamma_{\rm i}(G)=\frac{n(G)}{2}$ holds for all cubic
bipartite graph $G$.

##  6 Graphs with $\gamma_{\rm i}$ larger than $\Gamma$

In this section, we present a class of graphs whose indicated domination
numbers exceed their upper irredundance numbers (and therefore also the
independence number) by an arbitrarily large amount.

Recall that the $k^{\rm th}$ power $G^{k}$ of a graph $G$ has $V(G^{k})=V(G)$,
and $uv\in E(G^{k})$ if and only if $d_{G}(u,v)\leq k$, where $d_{G}$ is the
standard (shortest paths) distance in $G$.

######  Theorem 6.1.

For every $n\geq k\geq 2$, the $k^{\mathrm{th}}$ powers $P_{n}^{k}$ of paths
satisfy

$\gamma_{\rm i}(P_{n}^{k})=\Theta\Big{(}\frac{\log k}{k}\,n\Big{)}$

as $n\to\infty$. More explicitly,

$(\left\lceil\log(k+1)\right\rceil+1)\left\lfloor\frac{n}{4k}\right\rfloor\leq\gamma_{\rm
i}(P_{n}^{k})\leq\frac{\left\lceil\log(k+1)\right\rceil+2}{2k+2}\,n+\left\lceil\log(k+1)\right\rceil+2$

where $\log$ means logarithm of base $2$.

###### Proof.

For the lower bound we may assume without loss of generality that $n$ is a
multiple of $4k$. We divide $P_{n}^{k}$ into $\frac{n}{4k}$ sections of $4k$
consecutive vertices. Staller’s strategy is to consider each section
separately. Denote the vertices in one such section $S$ by
$v_{1},\ldots,v_{4k}$. Note that the “middle” subsection $S^{-}$ formed by the
vertices $v_{k+1},\ldots,v_{3k}$ can only be dominated by vertices within $S$.
Let us also use the notation $S^{\prime}$ for the “left” half
$v_{1},\ldots,v_{2k}$ of $S$, and write $S^{\prime\prime}$ for its “right”
half $v_{2k+1},\ldots,v_{4k}$.

The first time Dominator indicates a vertex in $S$, with no loss of generality
it is one of the vertices from $S^{\prime}$. Staller then selects $v_{k}$.
This selection dominates the entire $S^{-}\cap S^{\prime}$, but leaves the $k$
vertices of $S^{-}\cap S^{\prime\prime}$ undominated. More generally, no
matter what happened during the game before this move, the set $U$ of
undominated vertices inside $S$ is a set $\\{v_{i},v_{i+1},\dots,v_{j}\\}$ of
consecutive vertices (or just a singleton $\\{v_{i}\\}$), because only some
vertices at the right end of $S^{\prime\prime}$ may possibly be dominated by a
selection from the successor section of $S$. Here $j>3k$ may occur, but
Staller’s strategy will handle this situation as if $j\leq 3k$ held. So,
attention will be restricted to
$U^{\prime}=\\{v_{i},v_{i+1},\dots,v_{j^{\prime}}\\}$ where
$j^{\prime}=\min(j,3k)$; hence $2k+1\leq i\leq j^{\prime}\leq 3k$. The crucial
point is:

  * (*)

If $|U^{\prime}|\geq 2^{s}$, for an integer $s\geq 0$, then Staller can
achieve that at least $s+1$ steps are needed to make the entire $U^{\prime}$
dominated during the rest of the game.

We prove this by induction on $s$, the case of $s=0$ being trivial. Once (*)
is proved, it follows that the $S^{-}$ subsection inside each of the
$\frac{n}{4k}$ sections $S$ requires at least
$\left\lceil\log\,(k+1)\right\rceil+1$ moves under a properly chosen strategy
of Staller, hence implying the claimed lower bound.

In a general move of the game when at least one selection has already been
made in $S$, assume that the set of undominated vertices inside $S$ is
$U\subseteq S^{\prime\prime}$ (also allowing $U\not\subset S^{-}$, but
$U^{\prime}\subset S^{-}$ will hold by definition), and let Dominator indicate
vertex $v_{\ell}$ from $U$.

  * (a)

If $\ell>3k$ (i.e., $v_{\ell}\in U\setminus U^{\prime}$), then Staller
imagines as if Dominator has indicated $\ell=3k$ and proceeds as in case (c)
below.

  * (b)

If $\ell\leq 3k$ and $\ell-i<j-\ell$, then Staller selects $v_{\ell-k}$.

  * (c)

If $\ell\leq 3k$ and $\ell-i\geq j-\ell$, then Staller selects $v_{\ell+k}$.

In either case, Staller’s selection is inside $S$, hence it has no influence
on the middle subsection of any section other than $S$. Moreover, in case (a)
the selected vertex is $v_{4k}$, therefore it dominates $v_{\ell}$. Finally,
the number of vertices in $U^{\prime}$ that become dominated by Staller’s
selection is at most $\lceil\frac{1}{2}|U^{\prime}|\rceil$. Consequently, if
$|U^{\prime}|\geq 2^{s}$, then at least $2^{s-1}$ vertices remain undominated
inside $S^{-}$ after this move. This implies (*) by induction, and completes
the proof of the lower bound.

As a preparation to the proof of the upper bound, we observe the following.

  * (**)

If $U=\\{v_{i},v_{i+1},\dots,v_{j}\\}$ is a set of consecutive undominated
vertices, and $j-i+1\leq 2k+1$, then Dominator can achieve in at most
$\lceil\log\,(j-i+2)\rceil$ moves that the entire $U$ becomes dominated.

The strategy is simple:

  1. 1.

Indicate $v_{\ell}$, where $\ell=\lfloor\frac{1}{2}(i+j)\rfloor$.

  2. 2.

Depending on Staller’s selection, update $U$ to its part that remains
undominated.

  3. 3.

Return to step 1 as long as $U$ is non-empty.

To verify that this strategy proves (**), it suffices to observe that the
undominated vertices of $U$ remain consecutive after each move—this is because
$j-i+1\leq 2k+1$ has been assumed—and that their number gets halved in each
move.

Now we provide a strategy for Dominator, who will proceed from left to right
in $P_{n}^{k}$. The situation before each move can be described with an
alternating sequence of sections that we call “gaps” $U_{i}$, consisting of
consecutive undominated vertices, and “intervals” $D_{i}$, consisting of
consecutive dominated vertices. At the beginning we have no intervals, and
just one gap $U_{1}=\\{v_{1},\dots,v_{n}\\}$. Let Dominator play according to
the following rules.

  1. 1.

While $v_{n}$ is undominated and the last gap has at least $2k+2$ vertices:

    1. (a)

Identify the first vertex $v_{g}$ of the gap that contains $v_{n}$.

    2. (b)

Indicate the vertex $v_{\ell}$, where $\ell=g+2k+1$.

    3. (c)

Depending on Staller’s selection, update the alternating sequence $U_{1}$,
$D_{1}$, $U_{2}$, $D_{2}$, $\dots$ of gaps and intervals.

  2. 2.

In each of the gaps $U_{1},U_{2},\dots,$ apply the strategy described above
for (**).

After the first phase, for the sake of a more transparent computation, we
split the gap-interval vertex partition into blocks $B_{1}=(U_{1},D_{1})$,
$B_{2}=(U_{2},D_{2})$, $\dots,$ $B_{m}=(U_{m},D_{m})$. If $v_{n}$ remains
undominated before the second phase, i.e. $v_{n}\in U_{m}$, we artificially
define $D_{m}$ as the emptyset. Observe that except for the last block
$B_{m}$, each gap $U_{i}$ has at least 1 and at most $2k+1$ vertices, and each
interval $D_{i}$ has exactly $2k+1$ vertices. In particular, also the first
block begins with a gap, as $v_{1}$ is undominated.

Consider any $B_{i}$ with $i<m$. If $2^{s}\leq|U_{i}|<2^{s+1}$, (**)
guarantees that Dominator can achieve that $U_{i}$ becomes dominated within
$s+1\leq\lceil\log\,(2k+2)\rceil$ moves (and, according to (*), that is the
best he can do). Moreover, $D_{i}$ was dominated in just one step. Since
$|U_{i}\cup D_{i}|\geq 2k+1+2^{s}\geq 2k+2$ whenever $i<m$, the average number
of moves required to dominate one vertex in $B_{i}$ is

$\frac{s+2}{|U_{i}|+|D_{i}|}\leq\frac{\lceil\log\,(2k+2)\rceil+1}{2k+2}$

because $s$ is an integer and $2^{s}\leq|U_{i}|\leq 2k+1$. This upper bound is
valid for all vertices in the whole $B_{1}\cup\cdots\cup B_{m-1}$.

To complete the proof of the theorem, it suffices to note that $U_{m}$ becomes
dominated in at most
$\left\lceil\log\,(2k+2)\right\rceil=\left\lceil\log\,(k+1)\right\rceil+1$
moves and $D_{m}$ in just one move (or none if it is empty). ∎

Let us state the particular case $k=2$ of the general lower bound separately,
as it already has important consequences.

######  Corollary 6.2.

If $n\geq 2$, then $\gamma_{\rm i}(P_{n}^{2})\geq 3\lfloor\frac{n}{8}\rfloor$

Since all $P_{n}^{2}$ are chordal graphs, we have ${\rm
IR}(P_{n}^{2})=\Gamma(P_{n}^{2})=\alpha(P_{n}^{2})=\left\lceil\frac{n}{3}\right\rceil\leq\frac{n+2}{3}$
by Theorem 2.2. Together with Corollary 6.2, noting also that
$3\lfloor\frac{n}{8}\rfloor\geq\frac{3}{8}n-\frac{21}{8}$, we get $\gamma_{\rm
i}(P_{n}^{2})-{\rm IR}(P_{n}^{2})\geq\frac{n-79}{24}$, which can be
arbitrarily large when $n$ grows.

######  Corollary 6.3.

There exist graphs $G$ such that $\gamma_{\rm i}(G)-{\rm IR}(G)$ is
arbitrarily large.

The above corollary also implies that there exist graphs $G$ such that
$\gamma_{\rm i}(G)-\Gamma(G)$ is arbitrarily large.

##  7 Concluding remarks

In Section 4 we characterized the graphs $G$ with minimum degree $\delta$ and
order $n\geq 2\delta+2$, that satisfy the extremal value $\gamma_{\rm
i}(G)=n-\delta$. It would be interesting to extend the characterization to
graphs of smaller order relative to $\delta$.

######  Question 7.1.

For which graphs $G$ of order $n$ and minimum degree $\delta$ such that
$n<2\delta+2$ does $\gamma_{\rm i}(G)=n-\delta$ hold?

In Section 5, we proved for two important families of bipartite graphs (namely
trees and grids) that the indicated domination number equals their
independence number. In addition, computer check confirmed this to hold for
all (bipartite) graphs of order at most $10$. We could not find any bipartite
graph that would not have this property, so we pose this as an open problem:

######  Question 7.2.

Is it true that for every bipartite graph $G$ we have $\gamma_{\rm
i}(G)=\alpha(G)$?

In the same section we also proved that connected, cubic bipartite graph of
order at most $12$ satisfy $\gamma_{\rm i}(G)=\frac{n(G)}{2}=\alpha(G)$. We
think this result could be generalized to all connected, cubic bipartite
graphs, but we were unable to prove it. Therefore we pose the following
question.

######  Question 7.3.

Is it true that $\gamma_{\rm i}(G)=\frac{n(G)}{2}$ for any cubic bipartite
graph $G$?

It would also be interesting to find whether there is an upper bound on the
indicated domination number in the class of all connected cubic graphs. In
particular, is there a constant $C<1$ such that $\gamma_{\rm i}(G)\leq C\cdot
n$ holds for all connected cubic graphs $G$? Note that $C\geq\frac{1}{2}$ due
to the $3$-cube and the Petersen graph, as checked by computer.

### Acknowledgements.

This research was supported in part by the National Research, Development and
Innovation Office, NKFIH Grants SNN 129364 and FK 132060, by the Slovenian
Research and Innovation Agency (ARIS) under the grants P1-0297, J1-2452,
J1-3002, J1-4008 and Z1-50003, and by the European Union (ERC, KARST,
101071836). The authors thank the Faculty of Natural Sciences and Mathematics
of the University of Maribor for hosting the Workshop on Games on Graphs in
June 2023.

## References

  * [1] G. Bacsó, B. Brešar, K. Kuenzel, D.F. Rall, Graphs with equal Grundy domination and independence number, Discrete Optim. 48 (2023) Paper 100777, 15 pp.
  * [2] T. Bartnicki, J. Grytczuk, H. A. Kierstead, X. Zhu, The map coloring game, Amer. Math. Monthly 144 (2007) 793–803.
  * [3] H.L. Bodlaender, On the complexity of some coloring games, Internat. J. Found. Comput. Sci. 2 (1991) 133–147.
  * [4] M. Borowiecki, A. Fiedorowicz, E. Sidorowicz, Connected domination game, Appl. Anal. Discrete Math. 13 (2019) 261–289.
  * [5] M. Borowiecki, E. Sidorowicz, Zs. Tuza, Game list colouring of graphs, Electron. J. Combin. 14 (2007) Paper R26, 11 pp.
  * [6] B. Brešar, T. Gologranc, M. Milanič, D.F. Rall, R. Rizzi, Dominating sequences in graphs, Discrete Math. 336 (2014) 22–36.
  * [7] B. Brešar, M.A. Henning, S. Klavžar, D.F. Rall, Domination Games Played on Graphs, SpringerBriefs in Mathematics, 2021.
  * [8] B. Brešar, S. Klavžar, D.F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979–991.
  * [9] Cs. Bujtás, Zs. Tuza, Fractional domination game, Electron. J. Combin. 26 (2019) Paper 4.3, 17 pp.
  * [10] E.J. Cockayne, O. Favaron, C. Payan, and A. G. Thomason, Contributions to the theory of domination, independence and irredundance in graphs, Discrete Math. 33 (1981) 249–258.
  * [11] E. Duchêne, V. Gledel, A. Parreau, G. Renault, Maker-Breaker domination game, Discrete Math. 343 (2020) Paper 111955, 12 pp.
  * [12] M. Gardner, Mathematical games, Scientific American 244 (1981) 18–26.
  * [13] V. Gledel, M.A. Henning, S. Klavžar, V. Iršič, Maker-Breaker total domination game, Discrete Appl. Math. 282 (2020) 96–107.
  * [14] A. Grzesik, Indicated coloring of graphs, Discrete Math. 312 (2012) 3467–3472.
  * [15] T.W. Haynes, S.T. Hedetniemi, P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker Inc., New York, NY, 1998.
  * [16] M.A. Henning, S. Klavžar, D.F. Rall, Total version of the domination game, Graphs Combin. 31 (2015) 1453–1462.
  * [17] M.S. Jacobson, K. Peters, Chordal graphs and upper irredundance, upper domination and independence, Discrete Math. 86 (1990) 59–69.
  * [18] G. Košmrlj, Realizations of the game domination number, J. Comb. Optim. 28 (2014) 447–461.
  * [19] T. Mahoney, G.J. Puleo, D.B. West, Online sum-paintability: the slow-coloring game, Discrete Math. 341 (2018) 1084–1093.
  * [20] Zs. Tuza, X. Zhu, Colouring games, in Topics in Chromatic Graph Theory, Cambridge Univ. Press, Cambridge, 2016, 304–326.


# Knowledge Graph-Enhanced Large Language Models via Path Selection

Haochen Liu, Song Wang, Yaochen Zhu, Yushun Dong, Jundong Li
University of Virginia
<EMAIL_ADDRESS>
###### Abstract

Large Language Models (LLMs) have shown unprecedented performance in various
real-world applications. However, they are known to generate factually
inaccurate outputs, a.k.a. the hallucination problem. In recent years,
incorporating external knowledge extracted from Knowledge Graphs (KGs) has
become a promising strategy to improve the factual accuracy of LLM-generated
outputs. Nevertheless, most existing explorations rely on LLMs themselves to
perform KG knowledge extraction, which is highly inflexible as LLMs can only
provide binary judgment on whether a certain knowledge (e.g., a knowledge path
in KG) should be used. In addition, LLMs tend to pick only knowledge with
direct semantic relationship with the input text, while potentially useful
knowledge with indirect semantics can be ignored. In this work, we propose a
principled framework KELP with three stages to handle the above problems.
Specifically, KELP is able to achieve finer granularity of flexible knowledge
extraction by generating scores for knowledge paths with input texts via
latent semantic matching. Meanwhile, knowledge paths with indirect semantic
relationships with the input text can also be considered via trained encoding
between the selected paths in KG and the input text. Experiments on real-world
datasets validate the effectiveness of KELP.111Our code is available at
https://github.com/HaochenLiu2000/KELP.

Knowledge Graph-Enhanced Large Language Models via Path Selection

Haochen Liu, Song Wang, Yaochen Zhu, Yushun Dong, Jundong Li University of
Virginia<EMAIL_ADDRESS>

##  1 Introduction

Recently, Large Language Models (LLMs) such as ChatGPT Brown et al. (2020) and
LLaMa Touvron et al. (2023) have shown exceptional performance, such as
unprecedented reasoning capabilities Wei et al. (2022), across various NLP
tasks Su et al. (2019); Lewis et al. (2020); Zhu et al. (2024); Wang et al.
(2021b). However, in scenarios where certain new knowledge beyond the scope of
training corpus is required, current LLMs are usually criticized for
generating factually inaccurate outputs Petroni et al. (2019); Ji et al.
(2023); Bang et al. (2023); Wang et al. (2023a). As a consequence, it becomes
imperative to develop effective and efficient techniques for incorporating new
knowledge into pretrained LLMs.

To facilitate the incorporation of new knowledge in LLMs, extracting external
knowledge from Knowledge Graphs (KGs) (known as KG-Enhanced LLMs Pan et al.
(2024)) has become a promising way to improve the factual accuracy of LLM
outputs Wang et al. (2023); Pan et al. (2024); Wu et al. (2024). Here, the
structure of KGs plays a critical role, since the relationship between
entities can effectively contribute to novel knowledge required by various
tasks, such as multi-hop reasoning Jiang et al. (2023a). In general, there are
two mainstreams to achieve KG-Enhanced LLMs. The first mainstream incorporates
new knowledge for LLMs during their training phase, which is usually achieved
by designing new training objectives or tasks Zhang et al. (2019); Wang et al.
(2021a). Nevertheless, these techniques typically require significant
computational resources. On the contrary, the second mainstream incorporates
new knowledge for LLM during the inference phase, where this new knowledge is
incorporated by prompt engineering, that is, designing new prompts to include
the triplets (head, relation, tail) derived from KGs Kim et al. (2023a).
Usually, prompt engineering stands out as the most computationally efficient
approach to incorporate new knowledge for LLMs, as new information can be
directly introduced together with the text input without an additional
training process.

Figure 1: An example of the phenomenon that semantically unrelated contexts in
the input prompts can possibly contain important knowledge to correct/improve
the generation of large language models. In this example, there exist
potential relationships between "Japan" and "Akita Inu" that are challenging
to directly identify and capture.

Nevertheless, integrating new knowledge for LLMs with prompt engineering bears
two significant disadvantages despite its effectiveness and efficiency. First,
most existing methods solely rely on LLMs to identify relevant triplets Kim et
al. (2023a). However, LLMs can only provide binary outputs on whether a
certain instance of knowledge (e.g., a path in a KG) should be used or not
Jiang et al. (2023a). As a consequence, existing approaches bear low
flexibility due to their coarse granularity in determining to what extent a
certain knowledge is useful. Second, solely using LLMs to select and
incorporate instances of knowledge is usually overwhelmed by the knowledge
that has direct semantic relationships with the input text. However, the
knowledge with indirect semantic relationships could also help LLMs achieve
factually accurate outputs. More specifically, instances of knowledge with
indirect semantic relationship to the input text can also help LLMs generate
factually accurate outputs. We refer to these instances as potentially
impactful knowledge, and an example is presented in Figure 1. Such a
phenomenon can be attributed to certain potential relationships between
entities and relations contained in the training corpus of LLMs, while it can
be challenging for both humans and LLMs themselves to perceive directly.
Therefore, it is usually difficult for existing approaches to capture this
nuanced, potentially impactful knowledge that can effectively improve the LLM
outputs solely based on the selection of knowledge instances from LLM
themselves.

To properly handle the problems discussed above, we introduce a novel approach
for KG-Enhanced LLMs, i.e., KELP (Knowledge Graph-Enhanced Large Language
Models via Path Selection), aiming to flexibly capture potentially impactful
knowledge as in-context facts to improve the factual accuracy of the LLM
outputs given input texts. In particular, KELP consists of three key
components: (i) Knowledge path extraction, (ii) Sample encoding, and (iii)
Fine-grained path selection. Specifically, we first extract knowledge paths
from KG based on the entities identified in the input texts as the candidate
knowledge. Subsequently, we train a path-text encoder to encode the indirect
connections between input texts and the knowledge paths extracted from KG,
with similarity defined on the latent semantic space, such that whether an
instance of knowledge (represented by a path in the KG) is potentially useful
for a certain input text (i.e., is the potentially impactful knowledge) can be
quantitatively measured. Based on the latent similarity score, two _coverage
rules_ are introduced to further refine the selected paths with high
flexibility. Through these meticulously designed steps, KELP strives to
flexibly capture potentially impactful knowledge with fine granularity (based
on quantitative scores) to refine LLM outputs. The contribution of this paper
can be concretely summarized into three folds as follows:

  * •

We critically study the challenges associated with the lack of flexibility and
omission of potentially impactful knowledge in the realm of prompt engineering
for KG-Enhanced Large Language Models.

  * •

We introduce KELP, an innovative approach aiming to capture potentially
impactful knowledge and incorporate it into the prompts of LLMs via trained
path-text encoding, with two coverage rules ensuring the flexibility of
knowledge extraction.

  * •

Extensive experiments on Fact Verification and Question Answering (QA)
datasets that encompass diverse graph reasoning patterns demonstrate the
effectiveness of KELP.

##  2 Problem Formulation

In this section, we introduce the task of enhancing LLM performance with KGs.
The KG is defined as $\mathcal{G}=(\mathcal{E},\mathcal{R},\mathcal{T})$,
where $\mathcal{E}$ and $\mathcal{R}$ are sets of entities and relations,
respectively, and
$\mathcal{T}=\\{(h,r,t)|h,t\in\mathcal{E},r\in\mathcal{R}\\}$ represents the
set of knowledge triplets, each contains a head entity $h$, a tail entity $t$,
and a relation $r$. In addition, we have a pretrained large language model
(LLM) denoted as $LM$. Given a question $q$ as the given task, if we denote
all the entities contained in $q$ as a set $\mathcal{E}_{q}$, the goal is to
utilize the background KG $\mathcal{G}$ as input prompts to support the
generation of $LM$ based on question $q$.

Figure 2: The overall pipeline of the proposed KELP. During the inference
phase, we identify knowledge paths from the knowledge graph that are
associated with the entities present in the input question. An encoder is then
trained to select valuable paths as knowledge contexts. Finally, the selected
knowledge contexts, along with the input question, are input into the LLM to
generate the final answer.

##  3 Methodology

In this section, we introduce the details of our proposed framework KELP,
which is presented in Figure 2. KELP is structured into three phases: (i)
Knowledge path extraction, (ii) Sample encoding, and (iii) Fine-grained path
selection. During knowledge path extraction, we extract a set of knowledge
paths for each entity in the entity set $\mathcal{E}_{q}$ of $q$ from the
background KG $\mathcal{G}$. For sample encoding, we employ a sentence encoder
$M$ trained on the latent semantic space that can encode the input question
$q$ and paths in the extracted knowledge path sets to obtain their distance
(i.e., the possibility that the paths can influence the output of LLMs), thus
ensuring capturing the potentially impactful knowledge in the paths. In the
final fine-grained path selection phase, we propose two coverage rules to
guarantee that the selection of knowledge paths is sufficiently flexible,
thereby ensuring the acquisition of the most diverse and representative paths
for the inference of LLMs regarding the input question $q$. Additionally, we
also design an alternative strategy called _Relation-Only Ranking_ to
generalize KELP to cases where the sizes of the knowledge path sets become
substantially massive.

###  3.1 Knowledge Path Extraction

In this subsection, we introduce the knowledge path extraction in KELP. The
objective is to identify valuable paths in the background Knowledge Graph
$\mathcal{G}$, i.e., knowledge paths, that contain potentially impactful
knowledge for a given input question $q$, which could be used as additional
contexts in the prompt to improve the factual accuracy in the generation
process of the LLM. To achieve this, we propose the following path extraction
procedure: For each entity $e$ in the entity set $\mathcal{E}_{q}$, we first
extract a knowledge path set denoted as follows:

$\displaystyle\mathcal{P}_{e}=\\{(e\rightarrow r\rightarrow
o)|o\in\mathcal{E},r\in\mathcal{R}\\}\cup$ (1) $\displaystyle\\{(e\rightarrow
r_{1}\rightarrow o_{1}\rightarrow r_{2}\rightarrow
o_{2})|o_{1,2}\in\mathcal{E},r_{1,2}\in\mathcal{R}\\},$

which contains all 1-hop and 2-hop paths starting from the entity $e$. These
selected paths serve as the candidates for the sample encoding phase.

###  3.2 Sample Encoding

From the extracted path set $\mathcal{P}_{e}$, sample encoding aims to further
refine the candidate knowledge paths that could help LLMs generate factually
accurate answers for question $q$ via learned encoding. Specifically, we
encode both the question $q$ and candidate knowledge paths in
$\mathcal{P}_{e}$ via an encoder $M$ fine-tuned on latent semantic space. The
fine-tuning steps of $M$ are introduced in Sections 3.4 and 3.5. In this
manner, we could quantify the usefulness of each path based on the learned
representations obtained by $M$.

To utilize the pretrained knowledge of the encoder $M$, we construct a path
sentence for each knowledge path before encoding. The conversion depends on
the number of triplets in the knowledge path: For a path containing only one
triplet $(h,r,t)$, we formulate the path sentence $p^{\prime}$ as
$p^{\prime}=``h\ r\ t.$” For a path consisting of two triplets
$(h_{1},r_{1},t_{1})$ and $(h_{2},r_{2},t_{2})$, we construct the path
sentence $p$ as follows: $p^{\prime}=``h_{1}\ r_{1}\ t_{1},\ h_{2}\ r_{2}\
t_{2}.$” The embeddings $\mathbf{h}_{q}$ and $\mathbf{h}_{p}$ for the question
$q$ and the knowledge path $p$ is acquired by encoding $q$ and $p^{\prime}$
using the encoder $M$ as follows:

$\mathbf{h}_{q}=M(q),\ \ \ \ \mathbf{h}_{p}=M(p^{\prime}).$ (2)

With the encoded representations $\mathbf{h}_{q}$, $\mathbf{h}_{p}$, we are
ready to learn the beneficial paths that contain potentially impactful
knowledge, based on the learned latent semantic similarity between
$\mathbf{h}_{q}$ and $\mathbf{h}_{p}$.

###  3.3 Fine-Grained Path Selection

In this phase, we aim to select the most suitable paths as in-context facts
for the input question $q$ based on the cosine similarity between their
representations as scores with our proposed coverage rules. In this manner, we
can address the challenge of rigid path selection by flexibly adjusting the
hyperparameters within the coverage rules controlling the diversity and amount
of the selected paths. Specifically, we aggregate the path sets of all
entities in $\mathcal{E}_{q}$ as
$\mathcal{P}_{q}=\bigcup_{e\in\mathcal{E}_{q}}\mathcal{P}_{e}.$ Notably, the
paths in $\mathcal{P}_{q}$ inevitably involve redundant triplets that are
shared in a larger number of paths. Therefore, we need to remove paths with
overlapping triplets for selection. We first divide the entire path set
$\mathcal{P}_{q}$ into subsets, each of which contains paths that share a
specific triplet. By denoting the set of paths sharing a specific triplet
$(h,r,t)$ as $\mathcal{P}_{q}(h,r,t)=\\{p|(h\rightarrow r\rightarrow t)\subset
p,p\in\mathcal{P}_{q}\\}$, we select the $k_{1}$ paths with highest scores for
each triplet $(h,r,t)$ as follows:

$\displaystyle\mathcal{P}\textquoteright_{q}(h,r,t)=\operatorname*{argmax}_{\mathcal{P}\textquoteright_{q}(h,r,t)}\sum\limits_{p\in\mathcal{P}\textquoteright_{q}(h,r,t)}\cos(\mathbf{h}_{p},\mathbf{h}_{q}),$
(3) $\displaystyle\;\text{s.t.}\;\ \
|\mathcal{P}\textquoteright_{q}{(h,r,t)}|=k_{1},\ \
\mathcal{P}\textquoteright_{q}{(h,r,t)}\subset\mathcal{P}_{q}(h,r,t).$

$\mathcal{P}\textquoteright_{q}(h,r,t)$ represents the subset of
$\mathcal{P}_{q}(h,r,t)$ with $k_{1}$-top paths in scores. By restricting the
size of $\mathcal{P}\textquoteright_{q}(h,r,t)$ to $k_{1}$, we could prevent
including multiple high-scoring 2-hop triplets that share the same 1-hop
triplet, precluding overly long contexts in the prompt with redundant
information. We then select paths based on the scores from these subsets,
where another rule is introduced to further restrict the number of distinct
sharing triplets. Particularly, we denote the set of distinct sharing triplet
subsets $\mathcal{T}\textquoteright$ obtained as follows:

$\displaystyle\mathcal{T}\textquoteright$
$\displaystyle=\operatorname*{argmax}_{\mathcal{T}\textquoteright}\sum\limits_{(h,r,t)\in\mathcal{T}\textquoteright}\max_{p\in\mathcal{P}\textquoteright_{q}(h,r,t)}\
\cos(\mathbf{h}_{p},\mathbf{h}_{q}),$ (4)
$\displaystyle\;\text{s.t.}\;|\mathcal{T}\textquoteright|\leq k_{2}.$

Here, we introduce another parameter $k_{2}$ to control the size of
$\mathcal{T}\textquoteright$, which consists of the distinct sharing triplets
that can constitute the aggregated path set:

$\mathcal{P}\textquoteright_{r}=\bigcup_{(h,r,t)\in\mathcal{T}\textquoteright}\mathcal{P}\textquoteright_{q}(h,r,t),\\\
$ (5)

where $\mathcal{P}\textquoteright_{r}$ is the aggregated path set from
triplets in $\mathcal{T}\textquoteright$. By restricting the size of
$\mathcal{T}^{\prime}$, we can avoid the inclusion of excessive, irrelevant
information in the context. Nonetheless, there still exist specific paths with
low similarity to the input question $q$. Thus, we additionally consider a
threshold to reduce the impact of such low-similarity paths. Particularly, we
set the threshold as the lowest similarity score among the highest similarity
scores among all selected $\mathcal{P}\textquoteright_{q}(h,r,t)$, which is
formally described as:

$\gamma=\min_{(h,r,t)\in\mathcal{T}\textquoteright}\ \
\max_{p\in\mathcal{P}\textquoteright_{q}(h,r,t)}\cos(\mathbf{h}_{p},\mathbf{h}_{q}),$
(6)

where $(h,r,t)\in\mathcal{T}\textquoteright$. In this manner, we could filter
out the low-similarity paths in $\mathcal{P}\textquoteright_{r}$ to obtain a
high-similarity path set. The final selected reference path set is denoted as
follows:

$\mathcal{P}_{r}=\\{p|p\in\mathcal{P}\textquoteright_{r},\cos(\mathbf{h}_{p},\mathbf{h}_{q})\geq\gamma\\}.$
(7)

As all paths in $\mathcal{P}_{r}$ are highly close to $q$, they will be
selected as a context of the prompt fed to $LM$.

By adjusting the value of $k_{1}$ and $k_{2}$ in Eqs. (3) and (4), we can
flexibly control the path selection process in KELP and the amount of new
knowledge introduced as context in the prompt, which allows for a more dynamic
and tailored selection process, and ensures that the selected knowledge paths
are optimally aligned with the knowledge required by $q$ to generate the
desired outputs.

###  3.4 Training-Set Establishment

To facilitate the training of encoder $M$ to match the candidate knowledge
paths that can potentially improve the factual accuracy of the output of LLM,
we construct a specialized dataset for encoder training, which contains both
positive and negative instances that can or can not influence generation of
the LLM. This dataset is constructed based on an original dataset comprising
input questions and their corresponding ground-truth responses. Specifically,
for a given input question $q$ that the Language Model $LM$ fails to generate
the correct answer, we select the knowledge path set $\mathcal{P}_{q}$ as
described in Section 3.3. We select the knowledge paths in $\mathcal{P}_{q}$
and individually use each of them as the context for the LLM input. If the
inclusion of a specific path results in the LLM generating the correct answer
(i.e., the answer is consistent with ground truth), we consider this knowledge
path as a positive sample of the training set. Similarly, we recognize it as a
negative sample of the training set if it still leads to an incorrect answer.

This training set is constructed using samples in the background KG and
therefore encompasses a wide spectrum of reference paths that are both
semantically related and semantically non-related to the input question $q$.
This design ensures that our encoder $M$ is capable of learning the latent
semantics that match both directly semantic-connected knowledge paths to the
input question $q$, but also the potentially impactful knowledge paths that
may not be (directly) semantically-related to the input question $q$, which
substantially improves the generalization ability of the learned encoder in
KELP.

###  3.5 Pairwise Optimization

With the positive and negative samples selected to establish the dataset, we
proceed to train the sentence encoder $M$. During the training of the encoder
$M$, we encode the input question $q$ and the corresponding path sentences
converted from positive and negative samples (see subsection 3.2), denoted as
$p_{q}^{+}$ and $p_{q}^{-}$. The representations of $q$, $p_{q}^{+}$ and
$p_{q}^{-}$ are $\mathbf{h}_{q}$, $\mathbf{h}^{+}_{q}$ and
$\mathbf{h}^{-}_{q}$ respectively.

To train the encoder $M$, we design a pairwise loss with both the positive and
the negative knowledge path samples for a given input question $q$. The loss
function $\mathcal{L}$ is defined as follows:

$\mathcal{L}=\sum_{q}\max(\cos(\mathbf{h}_{q},\mathbf{h}^{-}_{q})-\cos(\mathbf{h}_{q},\mathbf{h}^{+}_{q})+\eta,0).$
(8)

Here, $\cos(\cdot,\cdot)$ represents the cosine similarity function, and
$\eta$ is a threshold to prevent the model from excessively focusing on
positive or negative samples. The loss function defined in Eq. (8) encourages
the embeddings of positive samples (where $q$ and the path $p$ are related) to
be closer in similarity compared to the embeddings of negative samples (where
they are not related), where the latent semantic learned by the encoder can be
well aligned with the matchfulness between a potentially impactful knowledge
path and an input question $q$. Through this optimization process, the model
acquires the capability to capture useful knowledge that can enhance the
output of LLMs, encompassing even potentially impactful knowledge that may not
be immediately apparent or directly related.

###  3.6 Relation-Only Ranking

The above training strategy can be well applied to the number of candidate
path of normal KGs. However, in situations where the number of paths becomes
substantially massive, we introduce an alternative path selection strategy
called _Relation-Only Ranking_ to efficiently select important paths from the
KG. This approach is particularly useful for large knowledge graphs where the
$k$-hop $(k=1,2)$ neighboring subgraph of entities mentioned in the question
tends to be excessively dense for path selection. In such cases, encoding
every path we extract can be time-consuming. Recognizing that it is primarily
the relations within the paths that provide the most valuable enhancements, we
pivot to the _Relation-Only Ranking_ strategy.

In this strategy, when dealing with a specific extracted path $p$, we first
construct the path sentence $p^{\prime}$ exclusively from the relations
present in $p$. This means that for a path comprising only one triplet
$(h,r,t)$, we formulate a path sentence $p^{\prime}$ as follows:
$p^{\prime}=``r.$” For a path containing two triplets $(h_{1},r_{1},t_{1})$
and $(h_{2},r_{2},t_{2})$, we construct a path sentence $p$ as follows:
$p^{\prime}=``r_{1},r_{2}.$” This path sentence serves as the input to another
encoder specifically designed for path sentences with only relations, denoted
as $M_{r}$.

The encoder $M_{r}$ is trained in a similar manner as $M$, but it utilizes the
new path sentences constructed solely from relations within the knowledge
paths. Subsequently, we employ $M_{r}$ to rank the cosine similarity between
the representations of input question $q$ and path sentence $p^{\prime}$
containing relations, similar to how we generally rank knowledge paths. From
the selected relations with high scores, we then use the original encoder $M$
to rank all the knowledge paths associated with these selected relations. The
paths with higher scores are chosen as our contexts. With the introduced
Relation-Only Ranking approach, we significantly reduce the number of
candidate path sentences that require encoding in case of huge KG, resulting
in a more efficient matching process that consumes less time while still being
able to select valuable contexts based on the Relation-Only information.

##  4 Experiments

In this section, we introduce the extensive experiments conducted on two
different tasks to demonstrate the effectiveness of the proposed method KELP.
Our experimental setup closely follows the experimental settings outlined in
KG-GPT Kim et al. (2023a), ensuring consistency and comparability with
existing research in the field.

###  4.1 Datasets

In this paper, we focus on two important tasks respectively on two different
types of datasets for KG-Enhanced LLM: (i) Strongly Semantic Knowledge, where
the majority of questions have directly relevant semantic knowledge available
in the KG, and (ii) Weakly Semantic Knowledge, where only a minority of
questions have directly relevant semantic knowledge accessible in the KG. For
the Strongly Semantic Knowledge task, we utilize MetaQA Zhang et al. (2018),
i.e., a crucial benchmark dataset containing subsets of questions with
1-hop/2-hop reasoning steps respectively, and featuring a wide variety of
questions. Each question in MetaQA comes with a set of supporting facts and a
corresponding query over a knowledge graph, challenging models to perform
intricate multi-hop inference to derive accurate answers. With its rich
contextual information, MetaQA presents significant challenges for models to
effectively reason over interconnected entities and relations within the
knowledge graph. For the Weakly Semantic Knowledge task, we utilize the FACTKG
dataset Kim et al. (2023b). The FACTKG dataset comprises 108,000 claims
categorized as either _True_ or _False_ , where claims are subject to
validation with DBpedia, i.e., a knowledge graph developed by Lehmann et al.
(2015) which is not directly connected to most questions. In our experiments,
we employ a subset of DBpedia provided by Kim et al. (2023b) in FACTKG.

###  4.2 Baselines

We include the same baselines as previous studies Kim et al. (2023a). We
conduct all tasks with the large language model “gpt-3.5-turbo-0613” Brown et
al. (2020).

For all datasets, we conduct a question-only setting without evidence (i.e.,
context) in all few-shot learning scenarios. Moreover, for LLM-based evidence
setting, where LLMs are utilized to capture the useful knowledge in KGs as
prompts, we employ KG-GPT Kim et al. (2023a) in the same settings to assess
its performance across varying levels of evidence support from the KG. These
experiments are designed to assess the model’s performance across a spectrum
of scenarios employing 4-shot, 8-shot, and 12-shot configurations.

Besides few-shot learning settings, we also compare these performances with
fully supervised models: For Strongly Semantic Knowledge setting, we implement
five widely recognized baselines for Knowledge Graph Question Answering
(KGQA), i.e., KV-Mem Xu et al. (2019), GraftNet Sun et al. (2018), EmbedKGQA
Saxena et al. (2020), NSM He et al. (2021), and UniKGQA Jiang et al. (2023b).
For Weakly Semantic Knowledge setting, we also compare these performances of
few-shot learning settings with two encoder-only transformer-based text
classifiers, BERT Devlin et al. (2019) and BlueBERT Peng et al. (2019), and an
evidence retrieval approach GEAR Zhou et al. (2019), which comprises an
evidence graph retriever and a claim verification model.

Table 1:  Comparison between the accuracy(%) and standard deviations over Few-shot settings of KELP and baselines on both tasks. Here LLME represents LLM-based evidence. $\Delta_{PE}$ is the improved value of KELP compared to LLME. _Stongly_ and _Weakly_ respectively represent Strong Semantic Knowledge and Weakly Semantic Knowledge. The best results in each learning strategy are shown in bold, respectively.  Task | Method | Accuracy (%) | $\sigma$
---|---|---|---
4-shot | 8-shot | 12-shot
| GPT | 54.4 | 61.5 | 63.0 | 4.59
Strongly | LLME | 94.7 | 95.8 | 96.3 | 0.82
1-hop | KELP | 97.5 | 97.0 | 97.1 | 0.26
| $\Delta_{PE}$ | +2.8 | +1.2 | +0.8 | -0.56
| GPT | 22.6 | 22.8 | 28.3 | 3.23
Strongly | LLME | 92.8 | 93.8 | 94.4 | 0.81
2-hop | KELP | 93.7 | 94.3 | 93.8 | 0.32
| $\Delta_{PE}$ | +0.9 | +0.5 | -0.6 | -0.49
Weakly | GPT | 54.6 | 55.2 | 64.0 | 5.26
LLME | 59.5 | 67.7 | 72.7 | 6.66
KELP | 68.5 | 68.6 | 69.2 | 0.38
$\Delta_{PE}$ | +9.0 | +0.9 | -3.5 | -6.28

###  4.3 Implementation Details

In this subsection, we provide the detailed settings for the implementation of
our framework. The baseline LLM used in our experiments is
“gpt-3.5-turbo-0613” Brown et al. (2020), which is an enhanced version within
the GPT-3 series. During the establishment of the training set, we use 20% of
the samples from the original training sets to identify certain positive and
negative triplets. Then, a pretrained DistilBert Model with 66 million
parameters is introduced as the encoder $M$ to judge whether a triplet can
potentially contain the important knowledge to correct/improve the generation
of the baseline LLM. For optimization, we use AdamW Loshchilov and Hutter
(2018) as the optimizer, with the learning rate set as $2\times 10^{-6}$. We
set $k_{1}=k_{2}=4$ in the coverage rules based on their performance.

Here, for the FACTKG dataset, due to the large size of the neighboring
subgraph associated with the entities, we employ the _Relation-Only Ranking_
strategy introduced in Section 3.6 to select diverse and concise triplet paths
from the KG. Furthermore, our preliminary analysis of the FACTKG dataset
reveals notable accuracy in scenarios where a claim is determined to be
_True_. Conversely, in instances from the FACTKG dataset where a claim is
predicted as _False_ , there exists a possibility that it could actually be a
_True_ example, but with context information that has been inadequately
captured. To mitigate this issue, for claims predicted to be _False_ within
this dataset, we employ the LLM for a secondary verification process devoid of
any contextual information.

Figure 3: Comparison between the baseline GPT no-context, KG-GPT (LLM-based
evidence), and our proposed method KELP on the FACTKG dataset and MetaQA
dataset w.r.t. different shots in the learning setting.

###  4.4 Results and Analysis

In this subsection, we compare and analyze the performance of KELP and various
baselines on the Strongly Semantic Knowledge and Weakly Semantic Knowledge
tasks. The results of few-shot learning settings are summarized in Tables 1.
From the table, we can find that adding LLM-identified useful knowledge in the
prompt, i.e., LLM-based evidence, demonstrates significant performance
improvement over the baseline GPT. This indicates that a lack of certain
knowledge can indeed result in serious performance degradation in the LLM
generation due to factual inaccuracy. However, since LLMs mainly encode direct
semantic information, potentially useful knowledge with indirect semantic
similarity with the input texts can be overlooked by LLM-based evidence. By
finetuning pretrained encoder to capture the latent similarity between the
collected sample pairs of impactful knowledge paths and input texts, in the
experiments conducted within both 4-shot and 8-shot frameworks, our
methodology obtains superior outcomes compared to those achieved through LLM-
based evidence. Notably, in the 12-shot scenario, our approach’s performance
in 1-hop Strong Semantic Knowledge task with a retrieval surpassed that of
LLM-based evidence. Furthermore, in other experimental settings within the
12-shot scenario, our method’s results approached the efficacy levels of LLM-
based evidence, demonstrating the potential of our approach to closely match
or exceed LLM capabilities under varying conditions of informational support,
especially in scenarios with a lower number of shots. The analysis of the
relationship between performance and shots will be discussed in Section 4.5.

In table 2 we provide the performances of fully supervised models. Our
research indicates that the method KELP we propose in few-shot learning
settings surpasses the performance of some fully supervised models, achieving
results that are close to the highest accuracy benchmarks among these models.
This finding underscores the effectiveness of our approach in leveraging
limited data to achieve high levels of accuracy.

Table 2:  Baselines of fully supervised models on both tasks. _Stongly_ and _Weakly_ respectively represent Strong Semantic Knowledge and Weakly Semantic Knowledge.  Semantic Knowledge | Methods | Accuracy (%)
---|---|---
1-hop | 2-hop
Strongly | KV-Mem | 96.2 | 82.7
GraftNet | 97.0 | 94.8
EmbedKGQA | 97.5 | 98.8
NSM | 97.1 | 99.9
UniKGQA | 97.5 | 99.0
| BERT | 65.20
| BlueBERT | 59.93
Weakly | GEAR | 77.65

###  4.5 Sensitivity w.r.t. Shots

Furthermore, we compare KELP with the method on LLM-based evidence, when
different shots of knowledge are included in the prompt. As the results
illustrated in Figure 3 and the standard deviations in Table 1, the number of
shots does not significantly affect the performance of KELP. This phenomenon
can be attributed to KELP’s emphasis on capturing potentially impactful
knowledge aiming at effectively refining the outputs of LLM. In contrast, in-
context examples serve merely to enhance the LLMs on a semantic level. Given
that these in-context examples are crafted manually, it becomes challenging to
determine the exact influence of increasing their number. Furthermore, the
addition of more in-context examples can potentially introduce learning noise,
detracting from the model’s performance. Consequently, KELP exhibits minimal
fluctuation in its performance across various numbers of shots, particularly
excelling in contexts where the shots are limited. This stability and superior
performance, even with scant examples, render KELP especially relevant in
practical scenarios where acquiring a large volume of examples is challenging.
The consistency of KELP under these conditions not only demonstrates its
robustness but also its practical applicability, offering a compelling
solution in environments where data limitations are a significant constraint.

###  4.6 Ablation Study

In this subsection, we design different variants of KELP to demonstrate the
effectiveness of various components in our framework. In particular, we
consider the following variants: (1) KELP w/o Ru1, which removes the $k_{1}$
in coverage rules and directly selects paths with the highest scores in each
set $\mathcal{P}_{q}(h,r,t)$. As a result, we did not incorporate measures for
fault tolerance regarding the selection of useful knowledge within the set.
(2) KELP w/o Ru2, which removes the $k_{2}$ in coverage rules and directly
selects the top-1 set with the highest scores. As a result, the diversity of
selected paths cannot be ensured. (3) KELP w/o Ra, which removes the ranking
performed by the encoder and randomly selects paths in the subgraphs. As a
result, the selected paths contain less beneficial information. The results of
the ablation study, presented in Table 3, validate the effectiveness of the
coverage rules and the ranking method. Removing each of them will lead to a
decrease in the accuracy of prediction, which demonstrates the effectiveness
of our design.

Table 3:  Experimental results of ablation studies. _Stongly_ and _Weakly_ respectively represent Strong Semantic Knowledge and Weakly Semantic Knowledge. Strongly 1-hop is not applicable to KELP w/o Ru1.  Tasks | Methods | Accuracy (%)
---|---|---
4-shot | 8-shot | 12-shot
Strongly 1-hop | KELP | 97.5 | 97.0 | 97.1
KELP w/o Ru1 | - | - | -
KELP w/o Ru2 | 90.0 | 89.4 | 89.6
KELP w/o Ra | 82.9 | 82.2 | 82.3
Strongly 2-hop | KELP | 93.7 | 94.3 | 93.8
KELP w/o Ru1 | 88.1 | 88.2 | 88.2
KELP w/o Ru2 | 81.0 | 80.9 | 81.2
KELP w/o Ra | 70.4 | 70.1 | 69.7
Weakly | KELP | 68.5 | 68.5 | 69.2
KELP w/o Ru1 | 67.0 | 67.4 | 68.3
KELP w/o Ru2 | 66.5 | 67.0 | 67.7
KELP w/o Ra | 66.1 | 64.6 | 66.3

##  5 Related Work

###  5.1 Large Language Model (LLM)

Large language model (LLM), such as GPT Brown et al. (2020), BERT Devlin et
al. (2019), and T5 Raffel et al. (2020), represents a pivotal development in
natural language processing (NLP). Based on transformers Vaswani et al. (2017)
trained extensively on diverse datasets that encompass a wide spectrum of
textual sources (including books, articles, and websites), LLMs acquire a
profound understanding of semantics and reasoning ability in multiple
languages. In the era of LLMs, prompt engineering is a specialized technique
to efficiently adapt pretrained LLMs to downstream tasks, aiming to elicit
desired responses from these models by careful design and optimization of the
input text presented to the LLM known as prompts for different tasks. Prompt
engineering leverages the extensive training of LLMs on diverse datasets to
guide and instruct them to generate specific outputs or perform particular
tasks without laborious fine-tuning for each downstream task.

###  5.2 Knowledge Graph-Enhanced LLM

Knowledge Graphs (KGs) Chen et al. (2020) are organized repositories for
knowledge structured as a collection of triplets
$KG=\\{(h,r,t)\subseteq\mathcal{E}\times\mathcal{R}\times\mathcal{E}\\}$.
$\mathcal{E}$ and $\mathcal{R}$ represent the set of entities and relations,
respectively. Each triplet in the KG consists of a head entity $h$, a relation
$r$, and a tail entity $t$. KG-Enhanced LLM aims to use KG as external
knowledge to support LLM generations Wang et al. (2023b). Two primary
strategies are prevalent for integrating KG knowledge into LLMs: training
phase enhancement and inference phase enhancement. The former involves
embedding KG knowledge into LLMs via novel training objectives or directly
incorporating KG data into input sequences Wang et al. (2022), exemplified by
models like ERNIE Zhang et al. (2019) and K-BERT Liu et al. (2020). However,
these methods require extensive computational resources and frequent updates.
Alternatively, the inference phase enhancement incorporates new knowledge
through graph models or innovative prompt engineering, as seen in QA-GNN
Yasunaga et al. (2021) and KG-GPT Kim et al. (2023a). It is noteworthy that
these methods offer a computationally efficient and flexible method for KG
integration, where LLMs’ reasoning capabilities can be enhanced without
constant retraining.

##  6 Conclusion

In this paper, we present KELP, an innovative method to enhance Large Language
Models (LLMs) with Knowledge Graphs (KG), aiming to flexibly capture
potentially impactful knowledge that may lack direct semantic relevancy to the
input texts. Specifically, we establish a training dataset with real examples
of path-text pairs that demonstrate the correction of LLM outputs by including
external knowledge as contexts. Subsequently, we train a path-text encoder to
measure whether an instance of knowledge (represented as a given path in KG)
contains potentially impactful knowledge for a specified input text. Based on
the similarity score, two coverage rules are introduced to further refine the
selected knowledge paths with high flexibility. Through experimental
validation on two datasets, KELP has proven its superiority over other state-
of-the-art baselines on KG-Enhanced LLMs.

##  7 Limitaions

Our work performs path selection via an encoder trained on the latent semantic
space. As introduced in Section 3.4, to train an encoder proficient in
capturing valuable knowledge contexts encompassing both direct and indirect
semantic relationships, it is essential to construct a training set that
covers a diverse spectrum of data types. Nevertheless, manually testing the
paths surrounding entities within a text input via Large Language Models to
discern and select positive and negative samples would be an exceedingly time-
consuming process.

##  8 Ethics Statement

In our work, the knowledge in the background knowledge graph (KG) and the
pretrained large language model (LLM) may involve information from raw data in
the real world with social bias. Nevertheless, our method only selects
knowledge path samples from KGs based on their relations to the input texts.
Thus, as long as the input texts and samples do not preserve harmful
information, we believe that our method does not present any negative social
impacts.

##  9 Acknowledgement

This work is supported in part by the National Science Foundation under grants
(IIS-2006844, IIS-2144209, IIS-2223769, CNS2154962, and BCS-2228534), the
Commonwealth Cyber Initiative Awards under grants (VV-1Q23-007, HV2Q23-003,
and VV-1Q24-011), the JP Morgan Chase Faculty Research Award, and the Cisco
Faculty Research Award.

## References

  * Bang et al. (2023) Yejin Bang, Samuel Cahyawijaya, Nayeon Lee, Wenliang Dai, Dan Su, Bryan Wilie, Holy Lovenia, Ziwei Ji, Tiezheng Yu, Willy Chung, et al. 2023.  A multitask, multilingual, multimodal evaluation of chatgpt on reasoning, hallucination, and interactivity.  _arXiv preprint arXiv:2302.04023_.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _NeurIPS_.
  * Chen et al. (2020) Xiaojun Chen, Shengbin Jia, and Yang Xiang. 2020.  A review: Knowledge reasoning over knowledge graph.  _Expert Systems with Applications_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: pre-training of deep bidirectional transformers for language understanding.  In _NAACL_.
  * He et al. (2021) Gaole He, Yunshi Lan, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen. 2021.  Improving multi-hop knowledge base question answering by learning intermediate supervision signals.  In _WSDM_.
  * Ji et al. (2023) Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Yejin Bang, Andrea Madotto, and Pascale Fung. 2023.  Survey of hallucination in natural language generation.  _ACM CSUR_.
  * Jiang et al. (2023a) Jinhao Jiang, Kun Zhou, Zican Dong, Keming Ye, Xin Zhao, and Ji-Rong Wen. 2023a.  StructGPT: A general framework for large language model to reason over structured data.  In _EMNLP_.
  * Jiang et al. (2023b) Jinhao Jiang, Kun Zhou, Xin Zhao, and Ji-Rong Wen. 2023b.  Unikgqa: Unified retrieval and reasoning for solving multi-hop question answering over knowledge graph.  In _ICLR_.
  * Kim et al. (2023a) Jiho Kim, Yeonsu Kwon, Yohan Jo, and Edward Choi. 2023a.  KG-GPT: A general framework for reasoning on knowledge graphs using large language models.  In _EMNLP_.
  * Kim et al. (2023b) Jiho Kim, Sungjin Park, Yeonsu Kwon, Yohan Jo, James Thorne, and Edward Choi. 2023b.  Factkg: Fact verification via reasoning on knowledge graphs.  In _ACL_.
  * Lehmann et al. (2015) Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N. Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick van Kleef, Sören Auer, and Christian Bizer. 2015.  Dbpedia - A large-scale, multilingual knowledge base extracted from wikipedia.  _Semantic Web_.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _ACL_.
  * Liu et al. (2020) Weijie Liu, Peng Zhou, Zhe Zhao, Zhiruo Wang, Qi Ju, Haotang Deng, and Ping Wang. 2020.  K-BERT: enabling language representation with knowledge graph.  In _AAAI_.
  * Loshchilov and Hutter (2018) Ilya Loshchilov and Frank Hutter. 2018.  Decoupled weight decay regularization.  In _ICLR_.
  * Pan et al. (2024) Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu. 2024.  Unifying large language models and knowledge graphs: A roadmap.  _IEEE TKDE_.
  * Peng et al. (2019) Yifan Peng, Shankai Yan, and Zhiyong Lu. 2019.  Transfer learning in biomedical natural language processing: An evaluation of BERT and elmo on ten benchmarking datasets.  In _BioNLP_.
  * Petroni et al. (2019) Fabio Petroni, Tim Rocktäschel, Sebastian Riedel, Patrick S. H. Lewis, Anton Bakhtin, Yuxiang Wu, and Alexander H. Miller. 2019.  Language models as knowledge bases? In _EMNLP-IJCNLP_.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _JMLR_.
  * Saxena et al. (2020) Apoorv Saxena, Aditay Tripathi, and Partha P. Talukdar. 2020.  Improving multi-hop question answering over knowledge graphs using knowledge base embeddings.  In _ACL_.
  * Su et al. (2019) Dan Su, Yan Xu, Genta Indra Winata, Peng Xu, Hyeondey Kim, Zihan Liu, and Pascale Fung. 2019.  Generalizing question answering system with pre-trained language model fine-tuning.  In _MRQA_.
  * Sun et al. (2018) Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, Kathryn Mazaitis, Ruslan Salakhutdinov, and William W. Cohen. 2018.  Open domain question answering using early fusion of knowledge bases and text.  In _EMNLP_.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 2023.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _NeurIPS_ , volume 30.
  * Wang et al. (2023) Siyuan Wang, Zhongyu Wei, Jiarong Xu, Taishan Li, and Zhihao Fan. 2023.  Unifying structure reasoning and language model pre-training for complex reasoning.  _arXiv preprint arXiv:2301.08913_.
  * Wang et al. (2023a) Song Wang, Zhen Tan, Ruocheng Guo, and Jundong Li. 2023a.  Noise-robust fine-tuning of pretrained language models via external guidance.  In _EMNLP_.
  * Wang et al. (2023b) Song Wang, Yaochen Zhu, Haochen Liu, Zaiyi Zheng, Chen Chen, et al. 2023b.  Knowledge editing for large language models: A survey.  _arXiv preprint arXiv:2310.16218_.
  * Wang et al. (2021a) Xiaozhi Wang, Tianyu Gao, Zhaocheng Zhu, Zhengyan Zhang, Zhiyuan Liu, Juanzi Li, and Jian Tang. 2021a.  KEPLER: A unified model for knowledge embedding and pre-trained language representation.  _TACL_.
  * Wang et al. (2022) Yaqing Wang, Song Wang, Yanyan Li, and Dejing Dou. 2022.  Recognizing medical search query intent by few-shot learning.  In _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 502–512.
  * Wang et al. (2021b) Yaqing Wang, Song Wang, Quanming Yao, and Dejing Dou. 2021b.  Hierarchical heterogeneous graph representation learning for short text classification.  _CoRR_ , abs/2111.00180.
  * Wei et al. (2022) Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. 2022.  Emergent abilities of large language models.  _TMLR_.
  * Wu et al. (2024) Xuansheng Wu, Haiyan Zhao, Yaochen Zhu, Yucheng Shi, Fan Yang, Tianming Liu, Xiaoming Zhai, Wenlin Yao, Jundong Li, Mengnan Du, et al. 2024.  Usable xai: 10 strategies towards exploiting explainability in the llm era.  _arXiv preprint arXiv:2403.08946_.
  * Xu et al. (2019) Kun Xu, Yuxuan Lai, Yansong Feng, and Zhiguo Wang. 2019.  Enhancing key-value memory neural networks for knowledge based question answering.  In _NAACL_.
  * Yasunaga et al. (2021) Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. 2021.  QA-GNN: Reasoning with language models and knowledge graphs for question answering.  In _NAACL_.
  * Zhang et al. (2018) Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander J. Smola, and Le Song. 2018.  Variational reasoning for question answering with knowledge graph.  In _AAAI_.
  * Zhang et al. (2019) Zhengyan Zhang, Xu Han, Zhiyuan Liu, Xin Jiang, Maosong Sun, and Qun Liu. 2019.  ERNIE: enhanced language representation with informative entities.  In _ACL_.
  * Zhou et al. (2019) Jie Zhou, Xu Han, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 2019.  GEAR: graph-based evidence aggregating and reasoning for fact verification.  In _ACL_.
  * Zhu et al. (2024) Yaochen Zhu, Liang Wu, Qi Guo, Liangjie Hong, and Jundong Li. 2024.  Collaborative large language model for recommender systems.  In _WWW_ , pages 3162–3172.