Let us take again the game of Example 2.3: let us give (in red) the values of
$\lambda_{1}=\mathsf{nego}(\lambda_{0})$, which correspond to the antagonistic
values.

$a$$c$$b$$d$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$(\lambda_{1})$$1$$2$$1$$2$

At the second step, let us execute the abstract game on the state $a$, with
the requirement $\lambda_{1}$: whatever Prover proposes at first, Challenger
has the possibility to deviate and to reach the state $b$. Then, Prover has to
propose a $\lambda_{1}$-consistent play from the state $b$, i.e. a play in
which player $\Circle$ gets at least the payoff $2$: such a play necessarily
ends in the state $d$, and gives player $\Box$ the payoff $2$.

The other states keep the same values.

$a$$c$$b$$d$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$(\lambda_{2})$$2$$2$$1$$2$

But then, at the third step, from the state $b$: whatever Prover proposes at
first, Challenger can deviate to reach the state $a$. Then, Prover has to
propose a $\lambda_{2}$-consistent play from $a$, i.e. a play in which player
$\Circle$ gets at least the payoff $2$: such a play necessarily end in the
state $d$, i.e. after possibly some prefix, Prover proposes the play
$abd^{\omega}$. But then, Challenger can always deviate to go back to the
state $a$; and the play which is thus created is $(ab)^{\omega}$ which gives
player $\Box$ the payoff $3$.

$a$$c$$b$$d$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$(\lambda_{3})$$2$$3$$1$$2$

Finally, from the states $a$ and $b$, there exists no $\lambda_{3}$-consistent
play, and therefore no $\lambda$-rational strategy profile.

$a$$c$$b$$d$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$(\lambda_{4})$$+\infty$$+\infty$$1$$2$

and for all $n\geq 4$, $\lambda_{n}=\lambda_{4}$.

In all the previous examples, all the games whose underlying graphs were
strongly connected contained SPEs. Here is an example of game with a strongly
connected underlying graph that does not contain SPEs. This game is similar to
the game of Example 2.3, hence we do not give the details of the computation
of the negotiation sequence.

$b$$c$$a$$d$$e$$f$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{4}}$$(\lambda_{1})$$1$$1$$3$$2$$2$$4$

$b$$c$$a$$d$$e$$f$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{4}}$$(\lambda_{2})$$2$$1$$3$$2$$2$$4$

$b$$c$$a$$d$$e$$f$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{4}}$$(\lambda_{3})$$2$$1$$3$$3$$2$$4$

$b$$c$$a$$d$$e$$f$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{1}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{4}}$$(\lambda_{4})$$+\infty$$+\infty$$+\infty$$+\infty$$+\infty$$+\infty$

This example shows how a new requirement can emerge from the combination of
several cycles.

Let $G$ be the following game:

$a$$b$$c$$d$$e$$f$$g$$(\lambda_{1})$$1$$1$$0$$0$$0$$0$$3$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$

At the first step, the requirement $\lambda_{1}$ captures the antagonistic
values.

Then, from the state $c$, if player $\Box$ forces the access to the state $b$,
then player $\Circle$ must get at least $1$: the worst play that can be
proposed to player $\Box$ is then $(babc)^{\omega}$, which gives player $\Box$
the payoff $\frac{3}{2}$.

From the state $f$, if player $\Box$ forces the access to the state $g$, then
the worst play that can be proposed to them is $g^{\omega}$.

$a$$b$$c$$d$$e$$f$$g$$(\lambda_{2})$$1$$1$$\frac{3}{2}$$0$$0$$2$$3$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$

Then, from the state $d$, if player $\Circle$ forces the access to the state
$c$, then player $\Box$ must get at least $\frac{3}{2}$: the worst play that
can be proposed to player $\Circle$ is then $(cccd)^{\omega}$, which gives
player $\Circle$ the payoff $\frac{1}{2}$.

At the same time, from the state $e$, player $\Circle$ can now force the acces
to the state $f$: then, the worst play that can be proposed to them is
$fg^{\omega}$.

$a$$b$$c$$d$$e$$f$$g$$(\lambda_{3})$$1$$1$$\frac{3}{2}$$\frac{1}{2}$$3$$2$$3$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$

But then, from the state $c$, player $\Box$ can now force the access to the
state $e$: then, the worst play that can be proposed to them is
$efg^{\omega}$.

$a$$b$$c$$d$$e$$f$$g$$(\lambda_{4})$$1$$1$$2$$\frac{1}{2}$$3$$2$$3$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$

And finally, from that point, if from the state $d$ player $\Circle$ forces
the access to the state $c$, then player $\Box$ must have at least the payof
$2$; and therefore, the worst play that can be proposed to player $\Circle$ is
now $(ccd)^{\omega}$, which gives her the payoff $\frac{2}{3}$.

$a$$b$$c$$d$$e$$f$$g$$(\lambda_{5})$$1$$1$$2$$\frac{2}{3}$$3$$2$$3$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{3}}\stackrel{{\scriptstyle\Box}}{{2}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{2}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{1}}\stackrel{{\scriptstyle\Box}}{{3}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$$\stackrel{{\scriptstyle{\scriptsize{\Circle}}}}{{0}}\stackrel{{\scriptstyle\Box}}{{0}}$

The requirement $\lambda_{5}$ is a fixed point of the negotiation function.


# A gradient estimate for positive functions on graphs

Yong Lin<EMAIL_ADDRESS>Shuang Liu<EMAIL_ADDRESS>Yunyan Yang
<EMAIL_ADDRESS>Department of Mathematics, Renmin University of China,
Beijing 100872, P. R. China

###### Abstract

We derive a gradient estimate for positive functions, in particular for
positive solutions to the heat equation, on finite or locally finite graphs.
Unlike the well known Li-Yau estimate, which is based on the maximum
principle, our estimate follows from the graph structure of the gradient form
and the Laplacian operator. Though our assumption on graphs is slightly
stronger than that of Bauer, Horn, Lin, Lippner, Mangoubi, and Yau (J.
Differential Geom. 99 (2015) 359-405), our estimate can be easily applied to
nonlinear differential equations, as well as differential inequalities. As
applications, we estimate the greatest lower bound of Cheng’s eigenvalue and
an upper bound of the minimal heat kernel, which is recently studied by Bauer,
Hua and Yau (Preprint, 2015) by the Li-Yau estimate. Moreover, generalizing an
earlier result of Lin and Yau (Math. Res. Lett. 17 (2010) 343-356), we derive
a lower bound of nonzero eigenvalues by our gradient estimate.

###### keywords:

gradient estimate, locally finite graph, Harnack inequality, spectral graph

###### MSC:

[2010] 58J35

††journal: ***

section[0mm] [] subsection[3mm] []

##  1 Introduction

Let $G=(V,E)$ be a finite or locally finite graph, where $V$ denotes the
vertex set and $E$ denotes the edge set. For any edge $xy\in E$, we assume its
weight $w_{xy}>0$. The degree of $x\in V$ is defined as ${\rm
deg}(x)=\sum_{y\sim x}w_{xy}$, here and throughout this paper we write $y\sim
x$ if $xy\in E$. Let $\mu:V\rightarrow\mathbb{R}$ be a finite measure. Then
the $\mu$-Laplacian (or Laplacian for short) on $G$ is defined as

$\Delta f(x)=\frac{1}{\mu(x)}\sum_{y\sim x}w_{xy}(f(y)-f(x)).$

The associated gradient form reads

$2\Gamma(f,g)(x)=\frac{1}{\mu(x)}\sum_{y\sim x}w_{xy}(f(y)-f(x))(g(y)-g(x)).$

Write $\Gamma(f)=\Gamma(f,f)$. Denote

$D_{\mu}=\sup_{x\in V}\frac{{\deg}(x)}{\mu(x)},\quad d=\sup_{x\in V,\,xy\in
E}\frac{\mu(x)}{w_{xy}}.$ (1)

The main result in this paper is the following gradient estimate.

######  Theorem 1.

Let $G=(V,E)$ be a finite or locally finite graph. Suppose that

$D_{\mu}<+\infty,\quad d<+\infty,$ (2)

where $D_{\mu}$ and $d$ are defined as in (1). Then for any positive function
$u:V\rightarrow\mathbb{R}$, there holds

$\frac{\sqrt{2\Gamma(u)}}{u}\leq\sqrt{d}\frac{\Delta
u}{u}+\sqrt{d}D_{\mu}+\sqrt{D_{\mu}}.$ (3)

Several special cases are listed below:

$(i)$ If $u$ is a positive solution to the differential inequality $\Delta
u-qu\leq 0$ on $V$, where $q:V\rightarrow\mathbb{R}$ is a function, then there
holds

$\frac{\sqrt{2\Gamma(u)}}{u}-\sqrt{d}q\leq\sqrt{d}D_{\mu}+\sqrt{D_{\mu}}.$

$(ii)$ If $u$ is a positive solution to the differential inequality $\Delta
u-hu^{\alpha}\leq 0$, where $\alpha\in\mathbb{R}$, and
$h:V\rightarrow\mathbb{R}$ is a function, then there holds

$\frac{\sqrt{2\Gamma(u)}}{u}-\sqrt{d}hu^{\alpha-1}\leq\sqrt{d}D_{\mu}+\sqrt{D_{\mu}}.$

$(iii)$ If $u$ is a positive solution to the differential inequality $\Delta
u-\partial_{t}u\leq qu$, where $q:V\times\mathbb{R}\rightarrow\mathbb{R}$ is a
function, then there holds

$\frac{\sqrt{2\Gamma(u)}}{u}-\sqrt{d}\frac{\partial_{t}u}{u}-\sqrt{d}q\leq\sqrt{d}D_{\mu}+\sqrt{D_{\mu}}.$

$(iv)$ If $u$ is a positive solution to the differential inequality $\Delta
u-\partial_{t}u+au\log u\leq 0$, where $a\in\mathbb{R}$ is a constant, then
there holds

$\frac{\sqrt{2\Gamma(u)}}{u}-\sqrt{d}\frac{\partial_{t}u}{u}-\sqrt{d}a\log
u\leq\sqrt{d}D_{\mu}+\sqrt{D_{\mu}}.$

######  Remark 2.

For the corresponding partial differential equations on complete Riemannian
manifolds, $(i)-(iv)$ were extensively studied, see for examples [11, 12, 10,
15, 14, 16, 17] and the references there in.

At least two points can be seen from Theorem 1: One is that (3) is a global
estimate; The other is that (3) can be easily applied to nonlinear elliptic or
parabolic equations, as well as differential inequalities. We now analyze the
assumption (2), whch is equivalent to

$\sup_{x\in V}\sharp\left\\{y|y\sim x\right\\}<+\infty,\quad 0<\inf_{x\in
V,\,y\sim x}\frac{\mu(x)}{w_{xy}}\leq\sup_{x\in V,\,y\sim
x}\frac{\mu(x)}{w_{xy}}<+\infty,$ (4)

where $\sharp\left\\{y|y\sim x\right\\}$ stands for the number of $y\in V$
which is adjacent to $x$. In fact, suppose (2) holds. Then
$\sharp\left\\{y|y\sim x\right\\}\leq D_{\mu}d$ and
$\frac{1}{D_{\mu}}\leq\frac{\mu(x)}{w_{xy}}\leq d$ for any $y\sim x$. Hence
(4) holds. Conversely, if (4) holds, we have

$\frac{{\rm deg}(x)}{\mu(x)}=\frac{\sum_{y\sim
x}w_{xy}}{\mu(x)}\leq\frac{\sharp\\{y|y\sim x\\}}{\inf_{x\in V,\,y\sim
x}\frac{\mu(x)}{w_{xy}}}.$

Then (2) follows immediately. If we replace (2) by (4) in Theorem 1, then the
gradient estimate (3) would be

$\frac{\sqrt{2\Gamma(u)}}{u}\leq\sqrt{b}\frac{\Delta
u}{u}+\sqrt{b}\left(\frac{N}{a}+\sqrt{\frac{N}{ab}}\right),$ (5)

where $N=\sup_{x\in V}\sharp\left\\{y|y\sim x\right\\}$, $a=\inf_{x\in
V,\,y\sim x}\frac{\mu(x)}{w_{xy}}$ and $b=\sup_{x\in V,\,y\sim
x}\frac{\mu(x)}{w_{xy}}$. Note that the essential assumption of [3] is

$D_{\mu}<+\infty,\quad D_{w}=\sup_{x\in V,\,y\sim x}\frac{{\rm
deg}(x)}{w_{xy}}<+\infty.$ (6)

It is easy to see that (6) is slightly weaker than (2). All gradient estimates
in [3] are about $\sqrt{u}$, where $u$ is a positive solution to a parabolic
equation on $V$. Note that for any positive function $u$

$\displaystyle 2\Gamma(\sqrt{u})(x)$ $\displaystyle=$
$\displaystyle\frac{1}{\mu(x)}\sum_{y\sim
x}w_{xy}\left(\sqrt{u}(y)-\sqrt{u}(x)\right)^{2}$ (7) $\displaystyle\leq$
$\displaystyle\left(\sum_{y\sim
x}\frac{w_{xy}}{\mu(x)}\right)^{1/2}\left(\frac{1}{\mu(x)}\sum_{y\sim
x}w_{xy}\left(\sqrt{u}(y)-\sqrt{u}(x)\right)^{4}\right)^{1/2}$
$\displaystyle\leq$ $\displaystyle\left(\frac{{\rm
deg}(x)}{\mu(x)}\right)^{1/2}\left(\frac{1}{\mu(x)}\sum_{y\sim
x}w_{xy}\left({u}(y)-{u}(x)\right)^{2}\right)^{1/2}$ $\displaystyle\leq$
$\displaystyle\sqrt{D_{\mu}}\sqrt{2\Gamma(u)(x)}.$

If $u:V\times[0,+\infty)\rightarrow\mathbb{R}$ is a positive solution to the
parabolic equation $\Delta u-\partial_{t}u-qu=0$ on $V\times[0,+\infty)$, we
conclude an analog of ([3], Theorem 4.10) by combining (7) with Theorem 1,

$\frac{\Gamma(\sqrt{u})}{u}-\sqrt{D_{\mu}d}\frac{\partial_{t}\sqrt{u}}{\sqrt{u}}-\sqrt{D_{\mu}d}\frac{q}{2}\leq\frac{D_{\mu}(\sqrt{D_{\mu}d}+1)}{2}.$

As an application of Case $(iii)$ of Theorem 1, we state the following Harnack
inequality.

######  Theorem 3.

Let $G=(V,E)$ be a finite or locally finite graph satisfying (2). Moreover
$\mu_{\max}=\sup_{x\in V}\mu(x)<+\infty$ and $w_{\min}=\inf_{x\in V,\,y\sim
x}w_{xy}>0$. Assume $u:V\times(-\infty,+\infty)\rightarrow\mathbb{R}$ is a
positive solution to the heat inequality $\Delta u-\partial_{t}u\leq qu$,
where $q:V\times(-\infty,+\infty)\rightarrow\mathbb{R}$ is a function. Then
for any $(x,T_{1})$ and $(y,T_{2})$, $T_{1}<T_{2}$, we have

$\displaystyle u(x,T_{1})$ $\displaystyle\leq$ $\displaystyle
u(y,T_{2})\exp\left\\{\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)(T_{2}-T_{1})+\frac{\left({\rm
dist}(x,y)\right)^{2}}{T_{2}-T_{1}}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}\right.$
$\displaystyle\left.+\min\sum_{k=0}^{\ell-1}\left(\int_{t_{k}}^{t_{k+1}}q(x_{k},t)dt+\frac{\ell^{2}}{(T_{2}-T_{1})^{2}}\int_{t_{k}}^{t_{k+1}}(t-t_{k})^{2}(q(x_{k+1},t)-q(x_{k},t))dt\right)\right\\},$

where the minimum takes over all shortest paths
$x=x_{0},x_{1},\cdots,x_{\ell}=y$ connecting $x$ and $y$, and
$t_{k}=T_{1}+k(T_{2}-T_{1})/\ell$, $k=0,1,\cdots,\ell$. In particular, if
there exists some constant $C_{0}$ such that $|q(x,t)|\leq C_{0}$ for all
$(x,t)$, then for any $x,y\in V$ and $T_{1}<T_{2}$, there holds

$u(x,T_{1})\leq
u(y,T_{2})\exp\left\\{\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}+\frac{5}{3}C_{0}\right)(T_{2}-T_{1})+\frac{\left({\rm
dist}(x,y)\right)^{2}}{T_{2}-T_{1}}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}\right\\}.$
(8)

In a recent work of F. Bauer, B. Hua and S. T. Yau [2], the Li-Yau inequality
on graphs, which is due to F. Bauer, P. Horn, Y. Lin, G. Lipper, D. Mangoubi
and S. T. Yau [3], is applied to Liouville type theorems and eigenvalue
estimates. Moreover a DGG lemma [7, 6, 8] concerning the minimal heat kernel
is established on graphs, and it is used together with the Li-Yau inequality
to estimate the upper bound of the minimal heat kernel. Our gradient estimate
can be used instead of the Li-Yau estimate in [2]. Using Theorem 1, we can
estimate the greatest lower bound of the $\ell^{2}$-spectrum known as Cheng’s
eigenvalue [4].

######  Theorem 4.

Let $G=(V,E)$ be a locally finite graph satisfying (2) and $\lambda^{\ast}$ be
the greatest lower bound of the $\ell^{2}$-spectrum of the graph Laplacian
$\Delta$. Then we have $\lambda^{\ast}\leq D_{\mu}+\sqrt{D_{\mu}}/\sqrt{d}$.

While Theorem 3 can be used to get an analog of ([2], Theorem 1.2).

######  Theorem 5.

Let $G=(V,E)$ be a finite or locally finite graph satisfying (2). Moreover
$\mu_{\max}<+\infty$ and $w_{\min}>0$. Let $\lambda^{\ast}$ be the greatest
lower bound of the $\ell^{2}$-spectrum of the graph Laplacian $\Delta$. Given
any $\epsilon>0$, $0<\gamma\leq 1$, $\beta>0$. Let $P_{t}(x,y)$ be the minimum
heat kernel of $G$. Then there exist positive constants
$C_{1}(\beta,\gamma,D_{\mu})$ and
$C_{2}(\epsilon,\beta,\gamma,D_{\mu},d,\mu_{\max},w_{\min})$ such that for any
$x,y\in V$ and $t\geq\max\\{\beta d(x,y),1\\}$,

$P_{t}(x,y)\leq\frac{\exp\left(-(1-\gamma)\lambda^{\ast}t\right)}{\sqrt{{\rm
Vol}(B_{x}(\sqrt{t})){\rm
Vol}(B_{y}(\sqrt{t}))}}\exp\left\\{C_{2}\sqrt{t}-C_{1}\frac{({\rm
dist}(x,y))^{2}}{4(1+2\epsilon)t}\right\\}.$

Finally we remark that Theorem 1 can also be used to estimate a lower bound of
nonzero eigenvalues of the Laplacian on finite connected graphs. Precisely we
have an analog of ([13], Theorem 1.8), namely

######  Theorem 6.

Let $G=(V,E)$ be a finite connected graph, $D_{\mu}$ and $d$ be defined as in
(1), and $D$ be its diameter. Moreover we assume $w_{x,y}=w_{yx}$ for all
$y\sim x$ and all $x\in V$. Suppose that $\lambda$ is a nonzero eigenvalue of
$-\Delta$. Then there holds

$\lambda\geq\frac{1}{Dd\left(\exp\left\\{1+Dd\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)\right\\}-1\right)}.$
(9)

######  Remark 7.

If $\mu(x)=\deg(x)=\sum_{y\sim x}w_{xy}$, we have $D_{\mu}=1$, and whence (9)
becomes

$\lambda\geq\frac{1}{Dd\left(\exp\left\\{1+Dd\left(1+\sqrt{\frac{1}{d}}\right)\right\\}-1\right)}.$

We refer the reader to [1, 5] for earlier estimates in terms of the volume of
the graph $G$.

Let us describe the method. The proof of Theorem 1 is based on the positivity
of the average of $u$, i.e. $\frac{1}{\mu(x)}\sum_{y\sim x}w_{xy}u(y)$, and
its relation with $\Delta u$. To prove Theorem 3, we follow [3] and thereby
closely follow [12]. While the proof of Theorems 4, 5 and 6 is adapted from
[2] and [13] respectively.

The remaining part of this paper is organized as follows. In Section 2, we
prove the gradient estimate, Theorem 1. In Section 3, we prove the
corresponding Harnack inequality, Theorem 3. Finally Theorems 4, 5 and 6 are
proved in Section 4.

##  2 Gradient estimate

In this section, we prove Theorem 1 by using a very simple method.

Proof of Theorem 1. Special cases $(i)-(iv)$ are immediate consequences of
(3). Hence it suffices to prove (3). Since $u>0$, we have by definition of
$\Gamma(u)$,

$\displaystyle 2\Gamma(u)(x)$ $\displaystyle=$
$\displaystyle\frac{1}{\mu(x)}\sum_{y\sim x}w_{xy}(u(y)-u(x))^{2}$
$\displaystyle\leq$ $\displaystyle\frac{1}{\mu(x)}\sum_{y\sim
x}w_{xy}u^{2}(y)+\frac{1}{\mu(x)}\sum_{y\sim x}w_{xy}u^{2}(x)$
$\displaystyle=$ $\displaystyle\sum_{y\sim
x}\frac{\mu(x)}{w_{xy}}\left(\frac{w_{xy}}{\mu(x)}u(y)\right)^{2}+u^{2}(x)\frac{{\deg}(x)}{\mu(x)}$
$\displaystyle\leq$ $\displaystyle d\left(\sum_{y\sim
x}\frac{w_{xy}}{\mu(x)}u(y)\right)^{2}+D_{\mu}u^{2}(x).$

Noting that

$\sum_{y\sim x}\frac{w_{xy}}{\mu(x)}u(y)=\Delta
u(x)+u(x)\frac{{\deg}(x)}{\mu(x)}$

and using an elementary inequality $\sqrt{a^{2}+b^{2}}\leq a+b$, $\forall
a,b\geq 0$, we get

$\displaystyle\sqrt{2\Gamma(u)(x)}$ $\displaystyle\leq$
$\displaystyle\sqrt{d}\sum_{y\sim
x}\frac{w_{xy}}{\mu(x)}u(y)+\sqrt{D_{\mu}}u(x)$ $\displaystyle=$
$\displaystyle\sqrt{d}\left(\Delta
u(x)+u(x)\frac{{\deg}(x)}{\mu(x)}\right)+\sqrt{D_{\mu}}u(x)$
$\displaystyle\leq$ $\displaystyle\sqrt{d}\Delta
u(x)+(\sqrt{D_{\mu}}+\sqrt{d}D_{\mu})u(x).$

This leads to (3) and thus ends the proof of the theorem. $\hfill\Box$

##  3 Harnack inequality

In this section, following the lines of [3, 12], we prove a Harnack inequality
for positive solution to the parabolic inequality $\Delta u-\partial_{t}u\leq
qu$ by using $(iii)$ of Theorem 1.

Proof of Theorem 3. Let $u$ be a positive solution to the inequality $\Delta
u-\partial_{t}u\leq qu$. By $(iii)$ of Theorem 1, we have

$-\partial_{t}\log u\leq
D_{\mu}+\frac{\sqrt{D_{\mu}}}{\sqrt{d}}+q-\frac{1}{\sqrt{d}}\frac{\sqrt{2\Gamma(u)}}{u}.$
(10)

We distinguish two cases to proceed.

Case 1. $x\sim y$.

For any $s\in[T_{1},T_{2}]$, we have by (10) that

$\displaystyle\log u(x,T_{1})-\log u(y,T_{2})$ $\displaystyle=$
$\displaystyle\log\frac{u(x,T_{1})}{u(x,s)}+\log\frac{u(x,s)}{u(y,s)}+\log\frac{u(y,s)}{u(y,T_{2})}$
(11) $\displaystyle=$ $\displaystyle-\int_{T_{1}}^{s}\partial_{t}\log
u(x,t)dt+\log\frac{u(x,s)}{u(y,s)}-\int_{s}^{T_{2}}\partial_{t}\log u(y,t)dt$
$\displaystyle\leq$
$\displaystyle\left(D_{\mu}+\frac{\sqrt{D_{\mu}}}{\sqrt{d}}\right)(T_{2}-T_{1})+\int_{T_{1}}^{s}q(x,t)dt+\int_{s}^{T_{2}}q(y,t)dt$
$\displaystyle-\frac{1}{\sqrt{d}}\left(\int_{T_{1}}^{s}\frac{\sqrt{2\Gamma(u)(x,t)}}{u(x,t)}dt+\int_{s}^{T_{2}}\frac{\sqrt{2\Gamma(u)(y,t)}}{u(y,t)}dt\right)$
$\displaystyle+\log\frac{u(x,s)}{u(y,s)}.$

We estimate the above terms respectively. Obviously

$\int_{T_{1}}^{s}\frac{\sqrt{2\Gamma(u)(x,t)}}{u(x,t)}dt\geq 0.$ (12)

Since

$\displaystyle 2\Gamma(u)(y,t)$ $\displaystyle=$
$\displaystyle\frac{1}{\mu(y)}\sum_{z\thicksim y}w_{yz}(u(z,t)-u(y,t))^{2}$
$\displaystyle\geq$
$\displaystyle\frac{w_{\min}}{\mu_{\max}}(u(x,t)-u(y,t))^{2},$

we get

$-\frac{1}{\sqrt{d}}\int_{s}^{T_{2}}\frac{\sqrt{2\Gamma(u)(y,t)}}{u(y,t)}dt\leq-\sqrt{\frac{w_{\min}}{d\mu_{\max}}}\int_{s}^{T_{2}}\left|\frac{u(x,t)}{u(y,t)}-1\right|dt.$
(13)

Using an elementary inequality $\log r\leq\sqrt{|r-1|},\forall r>0$, we have

$\log\frac{u(x,s)}{u(y,s)}\leq\psi(x,y,s),$ (14)

where

$\psi(x,y,s)=\sqrt{\left|\frac{u(x,s)}{u(y,s)}-1\right|}.$

Inserting (12), (13), (14) into (11), and using ([3], Lemma 5.3), we obtain

$\displaystyle\log u(x,T_{1})-\log u(y,T_{2})$ $\displaystyle\leq$
$\displaystyle\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)(T_{2}-T_{1})+\psi(x,y,s)$
$\displaystyle-\sqrt{\frac{w_{\min}}{d\mu_{\max}}}\int_{s}^{T_{2}}\psi^{2}(x,y,t)dt+\int_{T_{1}}^{s}q(x,t)dt+\int_{s}^{T_{2}}q(y,t)dt$
$\displaystyle\leq$
$\displaystyle\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)(T_{2}-T_{1})+\frac{1}{T_{2}-T_{1}}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}$
$\displaystyle+\int_{T_{1}}^{T_{2}}q(x,t)dt+\frac{1}{(T_{2}-T_{1})^{2}}\int_{T_{1}}^{T_{2}}(t-T_{1})^{2}(q(y,t)-q(x,t))dt.$

Case 2. $x$ is not adjacent to $y$.

Assume ${\rm dist}(x,y)=\ell$. Take a shortest path
$x=x_{0},x_{1},\cdots,x_{\ell}=y$. Let
$T_{1}=t_{0}<t_{1}<\cdots<t_{\ell}=T_{2}$, $t_{k}=t_{k-1}+(T_{2}-T_{1})/\ell$,
$k=1,\cdots,\ell$. By the result of Case 1, we have

$\displaystyle\log u(x,T_{1})-\log u(y,T_{2})=\sum_{k=0}^{\ell-1}\left(\log
u(x_{k},t_{k})-\log u(x_{k+1},t_{k+1})\right)$
$\displaystyle\leq\sum_{k=0}^{\ell-1}\left(\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)(t_{k+1}-t_{k})+\frac{1}{t_{k+1}-t_{k}}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}\right)$
$\displaystyle\quad+\sum_{k=0}^{\ell-1}\left(\int_{t_{k}}^{t_{k+1}}q(x_{k},t)dt+\frac{1}{(t_{k+1}-t_{k})^{2}}\int_{t_{k}}^{t_{k+1}}(t-t_{k})^{2}(q(x_{k+1},t)-q(x_{k},t))dt\right)$
$\displaystyle\leq\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)(T_{2}-T_{1})+\frac{\ell^{2}}{T_{2}-T_{1}}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}$
$\displaystyle\quad+\sum_{k=0}^{\ell-1}\left(\int_{t_{k}}^{t_{k+1}}q(x_{k},t)dt+\frac{\ell^{2}}{(T_{2}-T_{1})^{2}}\int_{t_{k}}^{t_{k+1}}(t-t_{k})^{2}(q(x_{k+1},t)-q(x_{k},t))dt\right).$

Therefore we conclude

$\displaystyle\log u(x,T_{1})-\log u(y,T_{2})$ $\displaystyle\leq$
$\displaystyle\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)(T_{2}-T_{1})+\frac{\left({\rm
dist}(x,y)\right)^{2}}{(T_{2}-T_{1})}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}$
$\displaystyle\quad+\min\mathscr{F}(q)(x,y,T_{1},T_{2}),$

where

$\mathscr{F}(q)(x,y,T_{1},T_{2})=\sum_{k=0}^{\ell-1}\left(\int_{t_{k}}^{t_{k+1}}q(x_{k},t)dt+\frac{\ell^{2}}{(T_{2}-T_{1})^{2}}\int_{t_{k}}^{t_{k+1}}(t-t_{k})^{2}(q(x_{k+1},t)-q(x_{k},t))dt\right)$

and the minimum takes over all shortest paths connecting $x$ and $y$. Hence
the first assertion of the theorem follows immediately.

Moreover, if $|q(x,t)|\leq C_{0}$ for all $(x,t)$, then we have

$\sum_{k=0}^{\ell-1}\int_{t_{k}}^{t_{k+1}}q(x_{k},t)dt\leq C_{0}(T_{2}-T_{1})$

and

$\sum_{k=0}^{\ell-1}\frac{\ell^{2}}{(T_{2}-T_{1})^{2}}\int_{t_{k}}^{t_{k+1}}(t-t_{k})^{2}(q(x_{k+1},t)-q(x_{k},t))dt\leq\frac{2C_{0}}{3}(T_{2}-T_{1}).$

This gives the desired result and the proof of the theorem is completed.
$\hfill\Box$

##  4 Further applications of the gradient estimate

In this section, as applications of Theorem 1, we prove Theorems 4, 5 and 6.
For the proof of Theorems 4 and 5, we follow the lines of [2], the essential
difference is that we use Theorem 1 instead of the Li-Yau estimate [3]. While
the proof of Theorem 6 is an adaptation of [13]. For reader’s convenience, we
give the details here.

Proof of Theorem 4. Let $\lambda^{\ast}$ be the greatest lower bound of
Cheng’s eigenvalues. By a result of S. Haeseler and M. Keller ([9], Theorem
3.1), if $\lambda<\lambda^{\ast}$, then there would be a positive solution $u$
to $\Delta u=-\lambda u$. We conclude from Case $(i)$ of Theorem 1 that

$\frac{\sqrt{2\Gamma(u)}}{u}+\sqrt{d}\lambda\leq\sqrt{d}D_{\mu}+\sqrt{D_{\mu}}.$

Hence $\lambda\leq D_{\mu}+\sqrt{D_{\mu}/d}$. Since $\lambda$ is arbitrary, we
obtain $\lambda^{\ast}\leq D_{\mu}+\sqrt{D_{\mu}/d}$. $\hfill\Box$

To prove Theorem 5, we need the following DGG lemma on graphs ([2], Theorem
1.1).

######  Lemma 8.

Let $P_{t}(x,y)$ be the minimal heat kernel of the graph $G=(V,E)$. Then for
any $\beta>0$ and $0<\gamma\leq 1$, there exists a constant $C_{1}$ depending
only on $\beta,\gamma$ and $D_{\mu}$ such that for any subsets
$B_{1},B_{2}\subset G$, $t\geq\max\\{\beta{\rm dist}(B_{1},B_{2}),1\\}$,

$\sum_{x\in B_{1}}\sum_{y\in B_{2}}P_{t}(x,y)\mu(x)\mu(y)\leq
e^{-(1-\gamma)\lambda^{\ast}t}\sqrt{{\rm Vol}(B_{1}){\rm
Vol}(B_{2})}\exp\left(-C_{1}\frac{\left({\rm
dist}(B_{1},B_{2})\right)^{2}}{4t}\right).$

Proof of Theorem 5. Fix $x,y\in V$, $\delta>0$, $T_{1}=t$ and
$T_{2}=(1+\delta)t$. Applying the Harnack inequality, Theorem 3, to the
minimal heat kernel $P_{t}(x,y)$,

$\displaystyle P_{t}(x,y)$ $\displaystyle\leq$ $\displaystyle
P_{(1+\delta)t}(x^{\prime},y)\exp\left\\{\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)\delta
t+\frac{({\rm dist}(x,x^{\prime}))^{2}}{\delta
t}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}\right\\}$ $\displaystyle\leq$
$\displaystyle
P_{(1+\delta)t}(x^{\prime},y)\exp\left\\{\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)\delta
t+\frac{1}{\delta}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}\right\\},\quad\forall
x^{\prime}\in B_{x}(\sqrt{t}).$

Integrating the above inequality on $B_{x}(\sqrt{t})$ with respect to
$x^{\prime}$, we have

${\rm
Vol}(B_{x}(\sqrt{t}))P_{t}(x,y)\leq\exp\left\\{\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)\delta
t+\frac{1}{\delta}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}\right\\}\sum_{x^{\prime}\in
B_{x}(\sqrt{t})}\mu(x^{\prime})P_{(1+\delta)t}(x^{\prime},y).$ (15)

Note that $h(y,s)=\sum_{x^{\prime}\in
B_{x}(\sqrt{t})}\mu(x^{\prime})P_{s}(x^{\prime},y)$ is also a positive
solution to the heat equation. Applying again the Harnack inequality, Theorem
3, to $h(y,s)$ with $T_{1}=(1+\delta)t$ and $T_{2}=(1+2\delta)t$, we have

${\rm
Vol}(B_{y}(\sqrt{t}))h(y,(1+\delta)t)\leq\exp\left\\{\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)\delta
t+\frac{1}{\delta}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}\right\\}\sum_{y^{\prime}\in
B_{y}(\sqrt{t})}\mu(y^{\prime})h(y^{\prime},(1+2\delta)t).$

This together with (15) implies that

$\displaystyle P_{t}(x,y)$ $\displaystyle\leq$
$\displaystyle\exp\left\\{2\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)\delta
t+\frac{2}{\delta}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}\right\\}$
$\displaystyle\frac{1}{{\rm Vol}(B_{x}(\sqrt{t})){\rm
Vol}(B_{y}(\sqrt{t}))}\sum_{x^{\prime}\in B_{x}(\sqrt{t})}\sum_{y^{\prime}\in
B_{y}(\sqrt{t})}\mu(x^{\prime})\mu(y^{\prime})P_{(1+2\delta)t}(x^{\prime},y^{\prime}).$

Let $t\geq\max\\{\beta{\rm dist}(x,y),1\\}$. Obviously
$t\geq\frac{1}{1+2\delta}\max\\{\beta{\rm
dist}(B_{x}(\sqrt{t}),B_{y}(\sqrt{t})),1\\}$. Let $\gamma$, $0<\gamma\leq 1$,
be fixed. It follows from Lemma 8 that there exists a constant $C_{1}$
depending only on $\gamma$, $\beta$ and $D_{\mu}$ such that

$\displaystyle P_{t}(x,y)$ $\displaystyle\leq$
$\displaystyle\exp\left\\{2\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)\delta
t+\frac{2}{\delta}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}\right\\}\frac{1}{\sqrt{{\rm
Vol}(B_{x}(\sqrt{t})){\rm Vol}(B_{y}(\sqrt{t}))}}$ (16)
$\displaystyle\exp\left\\{-(1-\gamma)\lambda^{\ast}(1+2\delta)t-C_{1}\frac{\left({\rm
dist}(B_{x}(\sqrt{t}),B_{y}(\sqrt{t}))\right)^{2}}{4(1+2\delta)t}\right\\}.$

If ${\rm dist}(x,y)>2\sqrt{t}$, then ${\rm
dist}(B_{x}(\sqrt{t}),B_{y}(\sqrt{t}))\geq{\rm dist}(x,y)-2\sqrt{t}$ and thus

$\frac{\left({\rm
dist}(B_{x}(\sqrt{t}),B_{y}(\sqrt{t})\right)^{2}}{4(1+2\delta)t}\geq\frac{({\rm
dist}(x,y))^{2}}{4(1+4\delta)t}-\frac{1}{2\delta}.$ (17)

It is easy to see that (17) still holds if ${\rm dist}(x,y)\leq 2\sqrt{t}$.
Inserting (17) into (16), we have

$\displaystyle P_{t}(x,y)$ $\displaystyle\leq$
$\displaystyle\frac{1}{\sqrt{{\rm Vol}(B_{x}(\sqrt{t})){\rm
Vol}(B_{y}(\sqrt{t}))}}\exp\left\\{2\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)\delta
t+\frac{2}{\delta}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}+\frac{C_{1}}{2\delta}\right\\}$
$\displaystyle\exp\left\\{-(1-\gamma)\lambda^{\ast}(1+2\delta)t-C_{1}\frac{\left({\rm
dist}(x,y)\right)^{2}}{4(1+4\delta)t}\right\\}.$ (18)

Note that $t\geq 1$. Choosing $2\delta=\epsilon/\sqrt{t}$ in (18), we obtain
for $t\geq\max\\{\beta{\rm dist}(x,y),1\\}$,

$\displaystyle P_{t}(x,y)$ $\displaystyle\leq$
$\displaystyle\frac{1}{\sqrt{{\rm Vol}(B_{x}(\sqrt{t})){\rm
Vol}(B_{y}(\sqrt{t}))}}\exp\left\\{\sqrt{t}\left(D_{\mu}\epsilon+\sqrt{\frac{D_{\mu}}{d}}\epsilon+\frac{4}{\epsilon}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}+\frac{C_{1}}{\epsilon}\right)\right\\}$
$\displaystyle\exp\left\\{-(1-\gamma)\lambda^{\ast}t-C_{1}\frac{\left({\rm
dist}(x,y)\right)^{2}}{4(1+2\epsilon)t}\right\\}.$

Denoting
$C_{2}=D_{\mu}\epsilon+\sqrt{\frac{D_{\mu}}{d}}\epsilon+\frac{4}{\epsilon}\sqrt{\frac{d\mu_{\max}}{w_{\min}}}+\frac{C_{1}}{\epsilon}$,
we finish the proof of the theorem. $\hfill\Box$

Proof of Theorem 6. Note that $\int_{V}\Delta ud\mu=0$ and that if $-\Delta
u=\lambda u$, then $-\Delta(cu)=\lambda cu$ for any constant $c\in\mathbb{R}$.
We can assume $-\Delta u=\lambda u$ with $\sup u=1$ and $\inf u<0$. Take
$x_{1},x_{\ell}\in G$ such that $u(x_{1})=\sup u=1$, $u(x_{n})=\inf u<0$,
$x_{1}x_{2}\cdots x_{\ell}$ be the shortest path connecting $x_{1}$ and
$x_{\ell}$, where $(x_{i},x_{i+1})\in E$. Then $\ell\leq D$. For any
$\beta>1$, note that

$\displaystyle\frac{|u(x_{i})-u(x_{i+1})|}{\beta-u(x_{i})}$
$\displaystyle\leq$
$\displaystyle\frac{\sqrt{\frac{1}{\mu(x_{i})}\sum_{x_{i}y\in
E}\frac{\mu(x_{i})}{w_{x_{i}y}}w_{x_{i}y}(u(x_{i})-u(y))^{2}}}{\beta-u(x_{i})}$
$\displaystyle\leq$
$\displaystyle\sqrt{d}\frac{\sqrt{2\Gamma(u)(x_{i})}}{\beta-u(x_{i})}.$ (19)

Since $\beta-u>0$ and $u\leq 1$, we have by using Theorem 1,

$\displaystyle\frac{\sqrt{2\Gamma(u)}}{\beta-u}$ $\displaystyle=$
$\displaystyle\frac{\sqrt{2\Gamma(\beta-u)}}{\beta-u}$ $\displaystyle\leq$
$\displaystyle\sqrt{d}\left(\frac{\Delta(\beta-u)}{\beta-u}+D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)$
$\displaystyle=$ $\displaystyle\sqrt{d}\left(\frac{\lambda
u}{\beta-u}+D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)$ $\displaystyle\leq$
$\displaystyle\sqrt{d}\left(\frac{1}{\beta-1}\lambda+D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right).$

This together with (19) implies

$\sum_{i=1}^{\ell}\frac{|u(x_{i})-u(x_{i+1})|}{\beta-u(x_{i})}\leq
D{d}\left(\frac{1}{\beta-1}\lambda+D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right).$
(20)

On the other hand,

$\displaystyle\sum_{i=1}^{\ell}\frac{|u(x_{i})-u(x_{i+1})|}{\beta-u(x_{i})}$
$\displaystyle\geq$
$\displaystyle\sum_{i=1}^{\ell}\log\left(1+\frac{|u(x_{i})-u(x_{i+1})|}{\beta-u(x_{i})}\right)$
(21) $\displaystyle\geq$
$\displaystyle\sum_{i=1}^{\ell}\log\frac{\beta-u(x_{i+1})}{\beta-u(x_{i})}$
$\displaystyle=$ $\displaystyle\log\frac{\beta-u(x_{\ell})}{\beta-u(x_{1})}$
$\displaystyle\geq$ $\displaystyle\log\frac{\beta}{\beta-1}.$

Combining (20) and (21), we have

$\lambda\geq(\beta-1)\left(\frac{1}{Dd}\log\frac{\beta}{\beta-1}-D_{\mu}-\sqrt{\frac{D_{\mu}}{d}}\right).$

Choose $\beta$ such that
$\frac{1}{Dd}\log\frac{\beta}{\beta-1}-D_{\mu}-\sqrt{\frac{D_{\mu}}{d}}=\frac{1}{Dd}$.
We obtain

$\lambda\geq\frac{1}{Dd\left(\exp\left\\{1+Dd\left(D_{\mu}+\sqrt{\frac{D_{\mu}}{d}}\right)\right\\}-1\right)}.$

This completes the proof of the theorem. $\hfill\Box$

Acknowledgements. Y. Lin is supported by the National Science Foundation of
China (Grant No.11271011). Y. Yang is supported by the National Science
Foundation of China (Grant No.11171347 and Grant No. 11471014).

## References

  * [1] M. Barlow, T. Coulhon, A. Grigor’yan, Manifolds and graphs with slow heat kernel decay, Invent. Math. 144 (2001) 609-649.
  * [2] F. Bauer, B. Hua, S. T. Yau, Davies-Gaffney-Grior’yan lemma on graphs, Preprint.
  * [3] F. Bauer, P. Horn, Y. Lin, G. Lippner, D. Mangoubi, S. T. Yau, Li-Yau inequality on graphs, J. Differential Geom. 99 (2015) 359-405.
  * [4] S. Y. Cheng, Eigenvalue comparision theorems and its geometric applications, Math Z 143 (1975) 289-297.
  * [5] Fan R. K. Chung, Spectral graph theory, CBMS regional conference series in Math., No. 92, 1997, Amer. Math. Society.
  * [6] E. Davies, Heat kernel bounds, conservation of probability and the Feller property, J. d’Analyse Math. 58 (1992) 99-119.
  * [7] M. Gaffney, The conservation property of the heat equation on Riemannian manifolds, Comm. Pure Appl. Math. 12 (1959) 1-11.
  * [8] A. Grigor’yan, Integral maximum principle and its applications, Proc. R. Soc. A 124 (1994) 353-362.
  * [9] S. Haeseler, M. Keller, Generalized solutions and spectrum for Dirichlet forms on graphs, Random walks, Boundaries and spectra, Progress in probability 64 (2011) 181-201.
  * [10] J. Li, Gradient estimates and Harnack inequalities for nonlinear parabolic and nonlinear elliptic equations on Riemannian manifolds, J. Funct. Anal. 100 (1991) 233-256.
  * [11] P. Li, S. T. Yau, Estimates of eigenvalues of a compact Riemannian manifold, AMS symposium on the geometry of the Laplace operator, University of Hawaii at Manoa, 1979, 205-239.
  * [12] P. Li, S. T. Yau, On the parabolic kernel of the Schrödinger operator, Acta Math. 156 (1986) 153-201.
  * [13] Y. Lin, S. T. Yau, Ricci curvature and eigenvalue estimate on locally finite graphs, Math. Res. Lett. 17 (2010) 343-356.
  * [14] L. Ma, Gradient estimates for a simple elliptic equation on non-compact Riemannian manifolds, J. Funct. Anal. 241 (2006) 374-382.
  * [15] E. Negrin, Gradient estimates and a Liouville type theorem for the Schrödinger operator, J. Funct. Anal. 127 (1995) 198-203.
  * [16] Y. Yang, Gradient estimates for a nonlinear parabolic equation on Riemannian manifolds, Proc. Amer. Math. Soc. 136 (2008) 4095-4102.
  * [17] Y. Yang, Gradient estimates for the equation $\Delta u+cu^{-\alpha}=0$ on Riemannian manifolds, Acta Math. Sinica, English Series, 26 (2010) 1177-1182.


#  $k$NN-NER: Named Entity Recognition with Nearest Neighbor Search

Shuhe Wang1,2, Xiaoya Li1, Yuxian Meng1, Tianwei Zhang3
Rongbin Ouyang2, Jiwei Li1,4, Guoyin Wang5
1Shannon.AI, 2Peking University,3Nanyang Technological University
4Zhejiang University, 5Amazon Alexa AI
{shuhe_wang, xiaoya_li, yuxian_meng<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Inspired by recent advances in retrieval augmented methods in NLP (Khandelwal
et al., 2019, 2020; Meng et al., 2021b) , in this paper, we introduce a $k$
nearest neighbor NER ($k$NN-NER) framework, which augments the distribution of
entity labels by assigning $k$ nearest neighbors retrieved from the training
set. This strategy makes the model more capable of handling long-tail cases,
along with better few-shot learning abilities. $k$NN-NER requires no
additional operation during the training phase, and by interpolating $k$
nearest neighbors search into the vanilla NER model, $k$NN-NER consistently
outperforms its vanilla counterparts: we achieve a new state-of-the-art
F1-score of 72.03 (+1.25) on the Chinese Weibo dataset and improved results on
a variety of widely used NER benchmarks. Additionally, we show that $k$NN-NER
can achieve comparable results to the vanilla NER model with 40% less amount
of training data. 111Code available at https://github.com/ShannonAI/KNN-NER.

##  1 Introduction

Named Entity Recognition (NER) is an important problem in NLP, which refers to
identifying named entities (e.g., person names, organizations, or locations)
from a given chunk of text. The most widely employed strategy for the NER task
is to train a sequential labeling model based on a labeled dataset, and this
model learns to assign named entities to each token (Chiu and Nichols, 2016;
Ma and Hovy, 2016; Devlin et al., 2018). This process of training can be
viewed as memorization, in which the model iterates over the whole training
set to memorize and generalize the most confident named entity assigned to the
given word. This strategy of memorization has difficulty in handling long-tail
cases, and requires a large training set as sentence semantics get diverse and
complicated (Hammerton, 2003; Collobert et al., 2011; Lample et al., 2016;
Chiu and Nichols, 2016; Devlin et al., 2018; Liu et al., 2019a; Shao et al.,
2021).

Motivated by recent progress in retrieval augmented methods Khandelwal et al.
(2019, 2020), which have been successfully employed to handle similar issues
in language generation, i.e. Language Modeling (LM) and Neural Machine
Translation (NMT), we propose the $k$NN-NER framework for the NER task. $k$NN-
NER first retrieves $k$ nearest neighbors from the cached training set. Then,
it computes the distribution over labels by interpolating the distribution
over labels output from a vanilla NER model, and weights for labels from
similar examples in the training set, retrieved using token-level $k$NN
search. In this way, we are able to resolve the long-tail issue mentioned
above: by accessing the cached training examples through $k$NN search during
inference, similar cases (and their labels) will shed light on the test
examples, which makes memorizing the entire dataset unnecessary.

We conducted extensive experiments to evaluate the effectiveness of the
proposed $k$NN-NER framework. We show that $k$NN-NER consistently outperforms
its vanilla counterpart, which is based only on the distribution output from a
vanilla tagging model and does not rely on similar examples in the training
set. By applying $k$NN on the vanilla NER model with BERT (Devlin et al.,
2018) as the backbone, we are able to achieve a new state-of-the-art result
72.03 (+1.25) F1-score on the Chinese Weibo NER dataset and results comparable
to SOTA performances on a variety of widely applied NER benchmarks, including
CoNLL03, OntoNotes5.0, Chinese MSRA, and Chinese OntoNotes4.0. Additionally,
our experiments show that $k$NN-NER can achieve comparable results to the
vanilla NER model with 40% less amount of training data.

Figure 1: An example for the process of $k$NN-NER. The datastore contains a
set of representation-label pairs, which are extracted from the hidden states
of the vanilla NER model. By given an inference sentence: Obama lives in
Washington, suppose that at current test time $t$ we need to assign named
entity to the word Washington. The word representation of Washington is used
to query $k$ nearest neighbors from the datastore according to the similarity
distance, and through the softmax function, the similarity distances are
converted to $k$NN entity distribution. Interpolating the $k$NN distribution
with the vanilla NER model distribution, we get the final distribution for the
assigned named entities.

##  2 Related Work

#### Retrieval Augmented Model

Retrieval augmented models additionally use the input to retrieve a set of
relevant information to improve the model performance under the merit that an
open-book exam is easier than a close-book exam. Recent success on various NLP
tasks has shown the effectiveness of retrieval augmented models in improving
the quality of neural NLP models, such as language modeling (Khandelwal et
al., 2019; Meng et al., 2021b), question answering (Guu et al., 2020; Lewis et
al., 2020a, b; Xiong et al., 2020), text classification Lin et al. (2021b),
dialog generation (Fan et al., 2020; Thulke et al., 2021; Weston et al., 2018)
and neural machine translation (Khandelwal et al., 2019; Meng et al., 2021a;
Wang et al., 2021).

#### Named Entity Recognition

Research on NER has a long history. Hammerton (2003) first attempted to solve
this problem using unidirectional LSTMs. Collobert et al. (2011) presented a
CNN-CRF structure and Lample et al. (2016) combined the bidirectional LSTMs
with CRFs. Ma and Hovy (2016) and Chiu and Nichols (2016) further added
character feature via character CNN. Many works then focus on better improve
the decoding structure: leveraging the context information (Liu et al., 2018,
2019a; Lin et al., 2021a; Cui and Zhang, 2019); interpolating latent variables
(Lin et al., 2020; Shao et al., 2021); transferring to CRF model (Ye and Ling,
2018; Panchendrarajan and Amaresan, 2018); combining positive information (Dai
et al., 2019). Other researches like viewing the NER task as a machine reading
comprehension(MRC) task also have made great performance (Li et al., 2019a, b;
Gan et al., 2021).

##  3 Proposed Method: $k$NN-NER

###  3.1 Background: Vanilla NER

#### Sequence labeling for NER

Given an input sentence ${\bm{x}}=\\{x_{1},...,x_{n}\\}$ with length $n$,
$\forall~{}1\leq i\leq n$, $x_{i}$ denotes the $i$-th word token within this
sentence. We formalize the NER task as a sequence labeling task which assigns
a label $y_{i}$ to each given word $x_{i}$. A training set with $N$ samples is
then denoted by
$\\{\mathcal{X},\mathcal{Y}\\}=\\{({\bm{x}}^{1},{\bm{y}}^{1}),\cdots,({\bm{x}}^{N},{\bm{y}}^{N})\\}$,
where $({\bm{x}},{\bm{y}})$ is the text sequence and corresponding label
sequence.

For the vanilla NER model, we decompose the above sequence labeling task into
two steps: (_i_) using a text encoder to represent word tokens as high-
dimensional vectors, and (_ii_) classifying each high-dimensional vector into
a named entity category. For step (_i_), we use masked language models, e.g.,
BERT(Devlin et al., 2018) and RoBERTa(Liu et al., 2019b), as the feature
extractor. For a given word $x_{i}$, the output ${\bm{h}}_{i}$ from the last
layer of feature extractor is used as the contextualized word embedding
vector, where ${\bm{h}}_{i}\in\mathbb{R}^{m}$ with $m$ as the embedding
dimension. Then for the step (_ii_), we pass the word representation
${\bm{h}}_{i}$ through a multi-layer perceptron (MLP), and obtain the
distribution over the named entity vocabulary via a softmax operation:

$\displaystyle p_{\text{NER}}(y_{i}|{\bm{x}},x_{i})=\text{softmax}({\
\text{MLP}({\bm{h}}_{i}})).$ (1)

###  3.2 $k$ Nearest Neighbor NER

The key idea of the $k$NN-NER model is that it augments the process of
classification during inference stage with a $k$ nearest neighbor retrieval
mechanism. As shown in Figure 1, the $k$NN-NER process can be split into two
parts: (_i_) following the vanilla NER steps, i.e., extracting word
representation ${\bm{h}}$ and then assigning probability distribution
$p_{\text{NER}}$ for each word in a given input sentence; and (_ii_) finding
the most similar contexts in the datastore and adjust the final entity
distribution $p_{\text{final}}$ with a $k$NN-augmented entity distribution
$p_{\text{KNN}}$. In the following parts, we focus on two major components of
$k$NN-NER framework: datastore construction and $k$NN entity probability
interpolation.

#### Building datastore

The datastore $\mathcal{D}$ consists of a set of key-value pairs. Each key is
the contextualized word embedding of a word from a given sentence, and the
corresponding value is the name entity of that word in that sentence. Then the
datastore $\mathcal{D}$ is formulated as:

$\displaystyle\mathcal{D}\stackrel{{\scriptstyle\mathclap{\mbox{def}}}}{{=}}{}\\{\mathcal{K},\mathcal{V}\\}=$
$\displaystyle\\{({\bm{h}}_{i},y_{i})|~{}\forall x_{i}\in{\bm{x}},\forall
y_{i}\in{\bm{y}},$ (2)
$\displaystyle({\bm{x}},{\bm{y}})\in\\{\mathcal{X},\mathcal{Y}\\}\\}.$

where ${\bm{h}}_{i}$ is the contextualized representation of word $x_{i}$,
$\mathcal{K}$ represents the set of keys and $\mathcal{V}$ represents the
corresponding value set.

####  $k$NN-augmented Entity Probability

Suppose that we have constructed the datastore $\mathcal{D}$. During inference
time, for each word ${x_{i}}$ from a given input sentence ${\bm{x}}$, our
$k$NN-NER model first generates contextualized word embedding ${\bm{h}}_{i}$
and distribution over the entire entity labels
$p_{\text{NER}}(y_{i}|{\bm{x}},x_{i})$ for each word $x_{i}$. Then for each
word $x_{i}$, corresponding ${\bm{h}}_{i}$ is used to query $k$ nearest
neighbors set $\mathcal{N}$ from datastore $\mathcal{D}$ with $L^{2}$
Euclidean distance $d({\bm{h}}_{i},\cdot)$ as similarity measure.

The retrieved named entity set is then converted into a distribution over the
entire named entity vocabulary based on an RBF kernel output (Vert et al.,
2004) of the distance to the original word embedding ${\bm{h}}_{i}$. The
probability of predicting the label as an entity $e_{j}$ is proportional to
the summarization of kernel outputs from all values in $\mathcal{N}$ which
equal to $e_{j}$.

$\displaystyle p_{\text{kNN}}(y_{i}=$ $\displaystyle
e_{j}|{\bm{x}},x_{i})\varpropto$ (3)
$\displaystyle\sum_{({\bm{k}},v)\in\mathcal{N}}\mathbbm{1}_{v=e_{j}}\exp(\frac{-d({\bm{h}}_{i},{\bm{k}})}{T})$

where $e_{j}$ represents the $j$th entity within the entity vocabulary and $T$
is a temperature parameter to flatten the distribution. Note that, for the
labels that do not appear in the retrieved set, we always assign zero
probability to these entities. Finally, we augment the pure NER distribution
$p_{\text{NER}}(y_{i}|{\bm{x}},x_{i})$ with
$p_{\text{kNN}}(y_{i}|{\bm{x}},x_{i})$ as:

$\displaystyle p_{\text{final}}(y_{i}|{\bm{x}},x_{i})=$ $\displaystyle\lambda
p_{\text{NER}}(y_{i}|{\bm{x}},x_{i})\ +$ (4)
$\displaystyle(1-\lambda)p_{\text{kNN}}(y_{i}|{\bm{x}},x_{i})$

where $\lambda$ makes a balance between $k$NN distribution and pure NER
distribution.

##  4 Experiments

###  4.1 Datasets

We conduct experiments on commonly used English datasets and Chinese datasets.
For English datasets, we use the widely used CoNLL2003 and OntoNotes 5.0
benchmarks. For Chinese datasets, we use OntoNotes 4.0, MSRA and Weibo NER. We
adopt the general evaluation metric: span-level precision, recall and F1
score. Dataset details are described at Appendix A.

###  4.2 Experiment Results

English CoNLL 2003
---
Model | Precision | Recall | F1
Base Model
BERT-Base (Devlin et al., 2018) | 90.69 | 91.96 | 91.32
BERT-Base+$k$NN | 91.50 | 91.58 | 91.54 (+0.22)
Large Model
BERT-Large (Devlin et al., 2018) | 91.54 | 92.79 | 92.16
BERT-Large+$k$NN | 92.26 | 92.43 | 92.40 (+0.24)
RoBERTa-Large (Liu et al., 2019b) | 92.77 | 92.81 | 92.76
RoBERTa-Large+$k$NN | 92.82 | 92.99 | 92.93 (+0.17)
English OntoNotes 5.0
Model | Precision | Recall | F1
Base Model
BERT-Base (Devlin et al., 2018) | 85.09 | 85.99 | 85.54
BERT-Base+$k$NN | 85.27 | 86.13 | 85.70 (+0.16)
Large Model
BERT-Large (Devlin et al., 2018) | 85.84 | 87.61 | 86.72
BERT-Large+$k$NN | 85.92 | 87.84 | 86.87 (+0.15)
RoBERTa-Large (Liu et al., 2019b) | 86.59 | 88.17 | 87.37
RoBERTa-Large+$k$NN | 86.73 | 88.29 | 87.51 (+0.14)

Table 1: Results for two English datasets: CoNLL 2003 and OntoNotes 5.0.

Chinese OntoNotes 4.0
---
Model | Precision | Recall | F1
Base Model
BERT-Base (Devlin et al., 2018) | 78.01 | 80.35 | 79.16
BERT-Base+$k$NN | 80.23 | 81.60 | 80.91 (+1.75)
RoBERTa-Base (Liu et al., 2019b) | 80.43 | 80.30 | 80.37
RoBERTa-Base+$k$NN | 79.65 | 82.60 | 81.10 (+0.73)
ChineseBERT-Base (Sun et al., 2021) | 80.03 | 83.33 | 81.65
ChineseBERT-Base+$k$NN | 81.43 | 82.58 | 82.00 (+0.35)
Large Model
RoBERTa-Large (Liu et al., 2019b) | 80.72 | 82.07 | 81.39
RoBERTa-Large+$k$NN | 79.87 | 83.17 | 81.49 (+0.10)
ChineseBERT-Large (Sun et al., 2021) | 80.77 | 83.65 | 82.18
ChineseBERT-Large+$k$NN | 81.68 | 83.46 | 82.56 (+0.38)
Chinese MSRA
Model | Precision | Recall | F1
Base Model
BERT-Base (Devlin et al., 2018) | 94.97 | 94.62 | 94.80
BERT-Base+$k$NN | 95.34 | 94.64 | 94.99 (+0.19)
RoBERTa-Base (Liu et al., 2019b) | 95.27 | 94.66 | 94.97
RoBERTa-Base+$k$NN | 95.47 | 94.79 | 95.13 (+0.16)
ChineseBERT-Base (Sun et al., 2021) | 95.39 | 95.39 | 95.39
ChineseBERT-Base+$k$NN | 95.73 | 95.27 | 95.50 (+0.11)
Large Model
RoBERTa-Large (Liu et al., 2019b) | 95.87 | 94.89 | 95.38
RoBERTa-Large+$k$NN | 95.96 | 95.02 | 95.49 (+0.11)
ChineseBERT-Large (Sun et al., 2021) | 95.61 | 95.61 | 95.61
ChineseBERT-Large+$k$NN | 95.83 | 95.68 | 95.76 (+0.15)
Chinese Weibo NER
Model | Precision | Recall | F1
Base Model
BERT-Base (Devlin et al., 2018) | 67.12 | 66.88 | 67.33
BERT-Base+$k$NN | 70.07 | 67.87 | 68.96 (+1.63)
RoBERTa-Base (Liu et al., 2019b) | 68.49 | 67.81 | 68.15
RoBERTa-Base+$k$NN | 67.52 | 69.81 | 68.65 (+0.50)
ChineseBERT-Base (Sun et al., 2021) | 68.27 | 69.78 | 69.02
ChineseBERT-Base+$k$NN | 68.97 | 73.71 | 71.26 (+2.24)
Large Model
RoBERTa-Large (Liu et al., 2019b) | 66.74 | 70.02 | 68.35
RoBERTa-Large+$k$NN | 69.36 | 70.53 | 69.94 (+1.59)
ChineseBERT-Large (Sun et al., 2021) | 68.75 | 72.97 | 70.80
ChineseBERT-Large+$k$NN | 75.00 | 69.29 | 72.03 (+1.23)

Table 2: Results for three Chinese datasets: OntoNotes 4.0, MSRA and Weibo
NER.

#### The vanilla models

For the vanilla NER model, we choose BERT (Devlin et al., 2018) and RoBERTa
(Liu et al., 2019b) for both English datasets and Chinese datasets, and
ChineseBERT (Sun et al., 2021) only for Chinese datasets. Both base and large
version of the vanilla NER model are used in our experiments. The details of
implementation can be found in the original work, BERT (Devlin et al., 2018),
RoBERTa (Liu et al., 2019b) and ChineseBERT (Sun et al., 2021).

#### Results

Table 1 and Table 2 show the results on English datasets and Chinese datasets
respectively. 222For two English datasets, we only interpolated $k$NN into
pure BERT(Devlin et al., 2018) model, so the results are different from the
reported ones. More details can be found in https://github.com/google-
research/bert/issues/223 We observe a significant improvement by interpolating
$k$NN model across all tasks. Especially on Chinese OntoNotes 4.0 and Chinese
Weibo NER dataset, we observe an improvement of 1.75 and 1.63 respectively on
F1-score based on BERT model.

Figure 2: F1-score on Chinese OntoNotes 4.0 by varying the percentage of
training set.

#### Performance on low resource scenario

Empirically, we also observe that $k$NN-NER can achieve comparable results
with much fewer training samples benefitting from direct access to the cached
datastore. On dataset Chinese OntoNotes 4.0, we conducted experiments by
varying the percentage of training set while holding the full training set as
the datastore for $k$NN search. Figure 2 shows that without additional
training and annotation, $k$NN-NER can still generate comparable result to the
vanilla NER model with 40% less amount of training data.

#### Effectiveness and Sensitivity of $k$

To clearly observe the effectiveness of the hyperparameter $k$ during $k$NN
search, we varied $k$ on dataset Chinese OntoNotes 4.0 with BERT as the
vanilla NER model. From Table 3, we observe that with the increase of $k$, the
F1-score first increases and then keeps horizontal after $k$ reaches 256. A
larger $k$ can retrieve more informative neighbors from the cached datastore.
As $k$ continues increasing, the newly retrieved examples are less similar
with the current input example and hence add ignorable change to the final
performance. The steady performance with large enough $k$ values shows that
our $k$NN-NER model is robust and not sensitive to choice $k$.

F1-score on Chinese OntoNotes 4.0
---
Varying $k$ | F1-score
The Vanilla NER Model | 79.16
\+ by setting $k$=8 | 79.49(+0.33)
\+ by setting $k$=16 | 79.67(+0.51)
\+ by setting $k$=32 | 80.01(+0.85)
\+ by setting $k$=64 | 80.53(+1.37)
\+ by setting $k$=128 | 80.83(+1.67)
\+ by setting $k$=256 | 80.91(+1.75)
\+ by setting $k$=512 | 80.91(+1.75)

Table 3: F1-score on Chinese OntoNotes 4.0 by varying the $k$NN parameter $k$.

##  5 Conclusion

In this paper, we propose a new $k$NN-NER framework, which augments the
generated distribution through assigning $k$ nearest neighbors from the cached
training set. This strategy requires no additional operation on training
phase. By applying $k$NN search on the vanilla NER model, we achieve a new
state-of-the-art result 72.03 F1-score on Chinese Weibo NER dataset and
comparable results on a variety of datasets, e.g., Chinese MSRA and Chinese
OntoNotes 4.0. Additionally, our experiments show that $k$NN-NER can achieve
comparable results to the vanilla NER model with only 60% training data.

## References

  * Chiu and Nichols (2016) Jason PC Chiu and Eric Nichols. 2016.  Named entity recognition with bidirectional lstm-cnns.  _Transactions of the association for computational linguistics_ , 4:357–370.
  * Collobert et al. (2011) Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa. 2011.  Natural language processing (almost) from scratch.  _Journal of machine learning research_ , 12(ARTICLE):2493–2537.
  * Cui and Zhang (2019) Leyang Cui and Yue Zhang. 2019.  Hierarchically-refined label attention network for sequence labeling.  _arXiv preprint arXiv:1908.08676_.
  * Dai et al. (2019) Dai Dai, Xinyan Xiao, Yajuan Lyu, Shan Dou, Qiaoqiao She, and Haifeng Wang. 2019\.  Joint extraction of entities and overlapping relations using position-attentive sequence labeling.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, pages 6300–6308.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Fan et al. (2020) Angela Fan, Claire Gardent, Chloe Braud, and Antoine Bordes. 2020.  Augmenting transformers with knn-based composite memory for dialogue.  _arXiv preprint arXiv:2004.12744_.
  * Gan et al. (2021) Leilei Gan, Yuxian Meng, Kun Kuang, Xiaofei Sun, Chun Fan, Fei Wu, and Jiwei Li. 2021.  Dependency parsing as mrc-based span-span prediction.  _arXiv preprint arXiv:2105.07654_.
  * Guu et al. (2020) Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Ming-Wei Chang. 2020.  Realm: Retrieval-augmented language model pre-training.  _arXiv preprint arXiv:2002.08909_.
  * Hammerton (2003) James Hammerton. 2003.  Named entity recognition with long short-term memory.  In _Proceedings of the seventh conference on Natural language learning at HLT-NAACL 2003_ , pages 172–175.
  * Khandelwal et al. (2020) Urvashi Khandelwal, Angela Fan, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. 2020\.  Nearest neighbor machine translation.  _arXiv preprint arXiv:2010.00710_.
  * Khandelwal et al. (2019) Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. 2019\.  Generalization through memorization: Nearest neighbor language models.  _arXiv preprint arXiv:1911.00172_.
  * Lample et al. (2016) Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016.  Neural architectures for named entity recognition.  _arXiv preprint arXiv:1603.01360_.
  * Levow (2006) Gina-Anne Levow. 2006.  The third international Chinese language processing bakeoff: Word segmentation and named entity recognition.  In _Proceedings of the Fifth SIGHAN Workshop on Chinese Language Processing_ , pages 108–117, Sydney, Australia. Association for Computational Linguistics.
  * Lewis et al. (2020a) Mike Lewis, Marjan Ghazvininejad, Gargi Ghosh, Armen Aghajanyan, Sida Wang, and Luke Zettlemoyer. 2020a.  Pre-training via paraphrasing.  _arXiv preprint arXiv:2006.15020_.
  * Lewis et al. (2020b) Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020b.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  _arXiv preprint arXiv:2005.11401_.
  * Li et al. (2019a) Xiaoya Li, Jingrong Feng, Yuxian Meng, Qinghong Han, Fei Wu, and Jiwei Li. 2019a.  A unified mrc framework for named entity recognition.  _arXiv preprint arXiv:1910.11476_.
  * Li et al. (2019b) Xiaoya Li, Xiaofei Sun, Yuxian Meng, Junjun Liang, Fei Wu, and Jiwei Li. 2019b.  Dice loss for data-imbalanced nlp tasks.  _arXiv preprint arXiv:1911.02855_.
  * Lin et al. (2021a) Jerry Chun-Wei Lin, Yinan Shao, Youcef Djenouri, and Unil Yun. 2021a.  Asrnn: a recurrent neural network with an attention model for sequence labeling.  _Knowledge-Based Systems_ , 212:106548.
  * Lin et al. (2020) Jerry Chun-Wei Lin, Yinan Shao, Ji Zhang, and Unil Yun. 2020.  Enhanced sequence labeling based on latent variable conditional random fields.  _Neurocomputing_ , 403:431–440.
  * Lin et al. (2021b) Yuxiao Lin, Yuxian Meng, Xiaofei Sun, Qinghong Han, Kun Kuang, Jiwei Li, and Fei Wu. 2021b.  Bertgcn: Transductive text classification by combining gcn and bert.  _arXiv preprint arXiv:2105.05727_.
  * Liu et al. (2018) Liyuan Liu, Jingbo Shang, Xiang Ren, Frank Xu, Huan Gui, Jian Peng, and Jiawei Han. 2018.  Empower sequence labeling with task-aware neural language model.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32.
  * Liu et al. (2019a) Yijin Liu, Fandong Meng, Jinchao Zhang, Jinan Xu, Yufeng Chen, and Jie Zhou. 2019a.  Gcdt: A global context enhanced deep transition architecture for sequence labeling.  _arXiv preprint arXiv:1906.02437_.
  * Liu et al. (2019b) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019b.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Ma and Hovy (2016) Xuezhe Ma and Eduard Hovy. 2016.  End-to-end sequence labeling via bi-directional lstm-cnns-crf.  _arXiv preprint arXiv:1603.01354_.
  * Meng et al. (2021a) Yuxian Meng, Xiaoya Li, Xiayu Zheng, Fei Wu, Xiaofei Sun, Tianwei Zhang, and Jiwei Li. 2021a.  Fast nearest neighbor machine translation.  _arXiv preprint arXiv:2105.14528_.
  * Meng et al. (2021b) Yuxian Meng, Shi Zong, Xiaoya Li, Xiaofei Sun, Tianwei Zhang, Fei Wu, and Jiwei Li. 2021b.  Gnn-lm: Language modeling based on global contexts via gnn.  _arXiv preprint arXiv:2110.08743_.
  * Panchendrarajan and Amaresan (2018) Rrubaa Panchendrarajan and Aravindh Amaresan. 2018.  Bidirectional lstm-crf for named entity recognition.  In _Proceedings of the 32nd Pacific Asia Conference on Language, Information and Computation_.
  * Peng and Dredze (2015) Nanyun Peng and Mark Dredze. 2015.  Named entity recognition for chinese social media with jointly trained embeddings.  In _Proceedings of the 2015 conference on empirical methods in natural language processing_ , pages 548–554.
  * Pradhan (2011) Sameer Pradhan. 2011.  Proceedings of the fifteenth conference on computational natural language learning: Shared task.  In _Proceedings of the Fifteenth Conference on Computational Natural Language Learning: Shared Task_.
  * Pradhan et al. (2013) Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Hwee Tou Ng, Anders Björkelund, Olga Uryupina, Yuchen Zhang, and Zhi Zhong. 2013.  Towards robust linguistic analysis using ontonotes.  In _Proceedings of the Seventeenth Conference on Computational Natural Language Learning_ , pages 143–152.
  * Sang and De Meulder (2003) Erik F Sang and Fien De Meulder. 2003.  Introduction to the conll-2003 shared task: Language-independent named entity recognition.  _arXiv preprint cs/0306050_.
  * Shao et al. (2021) Yinan Shao, Jerry Chun-Wei Lin, Gautam Srivastava, Alireza Jolfaei, Dongdong Guo, and Yi Hu. 2021.  Self-attention-based conditional random fields latent variables model for sequence labeling.  _Pattern Recognition Letters_ , 145:157–164.
  * Sun et al. (2021) Zijun Sun, Xiaoya Li, Xiaofei Sun, Yuxian Meng, Xiang Ao, Qing He, Fei Wu, and Jiwei Li. 2021.  Chinesebert: Chinese pretraining enhanced by glyph and pinyin information.  _arXiv preprint arXiv:2106.16038_.
  * Thulke et al. (2021) David Thulke, Nico Daheim, Christian Dugast, and Hermann Ney. 2021.  Efficient retrieval augmented generation from unstructured knowledge for task-oriented dialog.  _arXiv preprint arXiv:2102.04643_.
  * Vert et al. (2004) Jean-Philippe Vert, Koji Tsuda, and Bernhard Schölkopf. 2004.  A primer on kernel methods.  _Kernel methods in computational biology_ , 47:35–70.
  * Wang et al. (2021) Shuhe Wang, Jiwei Li, Yuxian Meng, Rongbin Ouyang, Guoyin Wang, Xiaoya Li, Tianwei Zhang, and Shi Zong. 2021.  Faster nearest neighbor machine translation.  _arXiv preprint arXiv:2112.08152_.
  * Weston et al. (2018) Jason Weston, Emily Dinan, and Alexander H Miller. 2018.  Retrieve and refine: Improved sequence generation models for dialogue.  _arXiv preprint arXiv:1808.04776_.
  * Xiong et al. (2020) Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul Bennett, Junaid Ahmed, and Arnold Overwijk. 2020.  Approximate nearest neighbor negative contrastive learning for dense text retrieval.  _arXiv preprint arXiv:2007.00808_.
  * Ye and Ling (2018) Zhi-Xiu Ye and Zhen-Hua Ling. 2018.  Hybrid semi-markov crf for neural sequence labeling.  _arXiv preprint arXiv:1805.03838_.

##  Appendix A Experiments Datasets

#### English CoNLL2003.

CoNLL2003 (Sang and De Meulder, 2003) is an English dataset containing four
types of named entities: Location, Organization, Person and Miscellaneous, and
we followed (Li et al., 2019a) leveraging protocols in (Ma and Hovy, 2016) to
process it.

#### English OntoNotes 5.0.

OntoNotes 5.0 (Pradhan et al., 2013) is an English dataset including 18 types
of named entities: 11 types (e.g., Person, Organization) and 7 values (e.g.,
Date, Percent).

#### Chinese OntoNotes 4.0.

OntoNotes 4.0 (Pradhan, 2011) is a Chinese dataset with 18 types of named
entities and all of them are extracted from news domain texts. Same as the
CoNLL2003 (Sang and De Meulder, 2003), we followed (Li et al., 2019a) to
process it.

#### Chinese MSRA.

MSRA (Levow, 2006) is a Chinese dataset collected from news domain texts. It
contains three types of named entities and is used as shared task on SIGNAN
backoff 2006.

#### Chinese Weibo NER.

Weibo NER (Peng and Dredze, 2015) is a Chinese dataset drawn from the social
media website Sina Weibo and includes four types of named entities.