Machine-translated from Chinese.
Large scale Ricci curvature on graphs - Mark Kempton · Gabor Lippner ·
Florentin Münch
图上许多曲率仅局限在点与其邻居附近, 局部范围过小,
可能导致无法导出有意思的结果. 本文引入邻域半径$R,$
定义尺度为$R$的各类概念, 导出曲率.
记号
对带权图$G(V,w,m),$
$$\Delta f(x):=\frac{1}{m(x)}\sum_yw(x,y)(f(y)-f(x)),$$
由其导出用于能量方法的Dirichlet形式:
$$Q(f,f):=\left<{}-\Delta f,f\right>,$$
进而导出Bakry-Emery(carré du
champ)算子:
$$\Gamma(f,g):=\frac{1}{2}(\Delta(fg)-f\Delta g-g\Delta f),$$
计算得到即有:
$$\Gamma(f,g)(x)=\frac{1}{2m(x)}\sum_y w(x,y)[f(y)-f(x)][g(y)-g(x)].$$
记$\Gamma f:=\Gamma(f,f),$
那么$\Gamma f=\frac{1}{2}\parallel\nabla f\parallel^2.$
由$\Delta$生成的热半群记为$\{P_t=e^{t\Delta}\},$ 使得$P_tf$满足热方程
$$\partial_t P_tf=\Delta P_tf.$$
曲率导出
对Riemannian流形$M,$ Ricci曲率以$K$为下界等价于
$$|\nabla P_tf|\le e^{-Kt}P_t|\nabla f|,\quad \,\forall\,C_c^\infty(M).$$
我们定义$R$-梯度来将这个概念大范围推广到图上.
令$B_R(x)=\{y:d(x,y)\le R\}.$ 对$f:V\rightarrow \mathbb{R},$ $x\in V,$
定义:
$$|\nabla_R f|(x):=\max_{y\in B_R(x)}|f(y)-f(x)|.$$
接下来我们考虑令
$$|\nabla_R P_tf|\le e^{-Kt}P_t|\nabla_R f|$$
成立的必要条件是什么.
由于$t=0$时两侧相等, $t=0$时右侧导数应比左侧导数大.
注意到对两侧求导就能将曲率条件$K$提出, 我们进行求导推导.
由于$P_tf$连续变动, $\,\exists\,y_0\in B_R(x)$使得
$$|\nabla_RP_tf|(x)=|P_tf(y_0)-P_tf(x)|,\quad \,\forall\,t\in[0,\varepsilon].$$
那么对满足$|\nabla_R f|(x)=|f(y)-f(x)|$的$y\in B_R(x),$
$$|\nabla_RP_tf|(x)=|P_tf(y_0)-P_tf(x)|\ge |P_tf(y)-P_tf(x)|,\quad \,\forall\,t\in[0,\varepsilon],$$
且$t=0$时两侧相等, 因此$t=0$时左侧导数也比右侧导数大.
计算$t=0$时右侧导数为
$$\partial_t (P_tf(y)-P_tf(x))\operatorname{sgn}(P_tf(y)-P_tf(x))=(\Delta f(y)-\Delta f(x))\operatorname{sgn}(f(y)-f(x)),$$
因此对任意满足$|\nabla_R f|(x)=|f(y)-f(x)|$的$y\in B_R(x),$
$$\begin{aligned}
(\Delta f(y)-\Delta f(x))\operatorname{sgn}(f(y)-f(x))&\le \partial_t |\nabla_RP_tf|(x)\le \partial_t (e^{-Kt}P_t|\nabla_Rf|)\\
&\le -K|\nabla_R f|(x)+\Delta |\nabla_R f|(x).
\end{aligned}$$
这样我们有关于曲率的不等式:
$$K|\nabla_R f|(x)\le\Delta |\nabla_R f|(x)-(\Delta f(y)-\Delta f(x))\operatorname{sgn}(f(y)-f(x)).$$
左右关于$f$的量纲为$1,$ 不妨设$|\nabla_R f|=1,$
由此导出如下的曲率定义方法:
定义 1.1. 任意指定$R\in \mathbb{N},$ $x,y\in V,$ 定义梯度-Ollivier曲率:
$$K_R(x,y):=\inf_{\begin{subarray}{c}
f:V\rightarrow \mathbb{R}\\
|\nabla_Rf|(x)=1\\
|f(y)-f(x)|=|\nabla_R f|(x)
\end{subarray} }\Delta|\nabla_R f|(x)-(\Delta f(y)-\Delta f(x))\operatorname{sgn}(f(y)-f(x)).$$
与Ollivier曲率联系
定理 1.2. $\,\forall\,x\sim y,$ 我们有:
$$K_1^{Ol}(x,y)\ge K_1(x,y).$$
证: 由定义,
$$K_1^{Ol}(x,y)=\min_{\begin{subarray}{c}
\parallel\nabla f\parallel_{\infty}=1\\
f(y)-f(x)=1
\end{subarray} }\Delta f(x)-\Delta f(y).$$
令$f$为实现最小值的函数, 则$|\nabla_1 f|(x)=1,$ 且$\,\forall\,z\sim x,$
$|\nabla_1 f|(z)\le 1.$ 这说明$\Delta |\nabla_1 f|(x)\le 0.$ 因此:
$$K_1(x,y)\le \Delta |\nabla_1f|(x)+K_1^{Ol}(x,y)\le K_1^{Ol}(x,y).$$
梯度估计
接下来说明这种曲率定义方式事实上也是充分的. 首先需要如下引理:
引理 1.3. 若$K_R(x,y)\ge K,$ $\,\forall\,d(x,y)\le R.$ 给定$t>0,$ 取函数
$$G_s:=e^{-Ks}P_s|\nabla_R P_{t-s}f|,\quad s\in[0,t]$$
那么$G_s$是递增函数.
证:
只需证$G_s$下导数$\underline{\partial}_sG_s:=\varliminf\limits_{h\rightarrow 0}\frac{G_{s+h}-G_s}{h}\ge0.$
计算得到:
$$\underline{\partial}_sG_s=-KG_s+e^{-Ks}(P_s(\underline\partial_s|\nabla_RP_{t-s}f|)+\Delta P_s|\nabla_R P_{t-s}f|).$$
与导出曲率时的方法相同,
$\,\forall\,y\in B_R(x)$满足$|\nabla_R P_{t-s}f|(x)=|P_{t-s}f(y)-P_{t-s}f(x)|,$
有:
$$\begin{aligned}
\underline\partial_s|\nabla_RP_{t-s}f|(x)&\ge \partial_s|P_{t-s}f(y)-P_{t-s}f(x)|\\
&=(\partial_s P_{t-s}f(y)-\partial_s P_{t-s}f(x))\operatorname{sgn}(P_{t-s}f(y)-P_{t-s}f(x))\\
&=-(\Delta P_{t-s}f(y)-\Delta P_{t-s}f(x))\operatorname{sgn}(P_{t-s}f(y)-P_{t-s}f(x))\\
&\ge |\nabla_R P_{t-s}f|(x)K_R(x,y)-\Delta |\nabla_RP_{t-s}f|(x)\\
&\ge K|\nabla_R P_{t-s}f|(x)-\Delta |\nabla_R P_{t-s} f|(x)
\end{aligned}$$
由于$P_s\Delta=\Delta P_s$且对于非负函数$f\ge 0,$ $P_sf\ge 0,$ 我们有
$\underline{\partial}_s G_s\ge 0,$ 引理得证.
比较$G_0$与$G_t,$ 立即得到如下定理成立:
定理 1.4. 若$K_R(x,y)\ge K,$ $\,\forall\,d(x,y)\le R,$ 则
$$|\nabla_R P_tf|\le e^{-Kt}P_t|\nabla_R f|.$$
衰减性
当$K=0$时, 上述梯度估计不再能给出好的衰减性. 我们希望证明如下的估计:
定理 1.5. 若$\,\forall\,x,y\in V,$ $d(x,y)\le R,$ 有$K_R(x,y)\ge 0.$ 那么
$$|\nabla_R P_tf|^2\le \frac{C}{t}\parallel f\parallel^2_{\infty},$$
我们希望利用$\Gamma f$来估计$|\nabla_R f|^2,$ 给出其上界.
然而对$R\ge 2,$ $\Gamma$仅涉及一步邻域,
于是基本的想法是将$\Gamma f$在足够大的邻域上求和来控制$|\nabla_R f|.$
我们需要如下工具.
定义 1.6. 对图$G=(G,w,m),$ 记$Q(x,y):=\frac{w(x,y)}{m(x)},$ 那么 $\Delta f(x)=\sum_y Q(x,y)(f(y)-f(x)).$ 记$\deg(x):=\sum_y Q(x,y),$ $Q_{\min} :=\inf_{x\sim y}Q(x,y).$ 定义$A:=\Delta+\deg_{\max},$ 称为平均算子.
易见它满足一些简单的性质:
$f\ge 0\Rightarrow Af\ge 0;$
$\parallel Af\parallel_{\infty}\le \deg_{\max}\parallel f\parallel_{\infty};$
$P_t A=AP_t.$
引理 1.7. $\,\forall\,f:V\rightarrow \mathbb{R},$ 我们有
$$|\nabla_R f|^2\le \frac{2R}{Q_{\min}^R}A^{R-1}\Gamma f.$$
证: 首先估计$A^{R-1}\Gamma f.$ 注意到$\,\forall\,g\ge 0,$
$$Ag(x)\ge \sum_y Q(x,y) g(y)\ge Q_{\min}\sum_{y\sim x}g(y).$$
因此,
$$A^{R-1}\Gamma f\ge Q_{\min}^{R-1}\sum_{x\sim x_1\sim\cdots\sim x_{R-1} } \Gamma f(x_{R-1}).$$
类似地, $\Gamma f$本身满足
$$\Gamma f(x)\ge \frac{1}{2}Q_{\min}\sum_{y\sim x}(f(z)-f(x))^2.$$
因此,
$$A^{R-1}\Gamma f(x)\ge \frac{1}{2}Q_{\min}^{R}\sum_{x\sim x_1\sim\cdots\sim x_{R} } (f(x_{R})-f(x_{R-1}))^2.$$
那么设$|\nabla_R f|(x)=|f(x)-f(y)|,$ $y\in B_R(x).$
取$x=y_0\sim \cdots\sim y_r=y,$ $r\le R.$
那么由基本不等式$\frac{a_1+\cdots+a_n}{n}\le \sqrt{\frac{a_1^2+\cdots+a_n^2}{n} },$
有:
$$\begin{aligned}
A^{R-1}\Gamma f(x)&\ge \frac{1}{2}Q_{\min}^{R}\sum_{k=1}^r(f(y_k)-f(y_{k-1}))^2\\
&\ge \frac{1}{2}Q_{\min}^R\frac{1}{r}(f(y_r)-f(y_0))^2\\
&\ge \frac{1}{2}Q_{\min}^R\frac{1}{R}|\nabla_R f|^2.
\end{aligned}$$
引理得证.
现在就能证明前面的定理了. 事实上我们可以证明如下更强的版本:
定理 1.8. 设$K_R(x,y)\ge K,$ $\,\forall\,x,y\in V,$ $d(x,y)\le R.$ 那么
$$\frac{e^{2Kt}-1}{2K}|\nabla_R P_tf|^2\le R\frac{\deg_{\max}^{R-1} }{Q_{\min}^{R} }\parallel f\parallel_{\infty}^2.$$
$K=0$时, $\frac{e^{2Kt}-1}{2K}:=t,$ 即为前面的定理.
证: 令$H_s:=A^{R-1}P_s[(P_{t-s}f)^2],$
$G_s:=e^{-Ks}P_s|\nabla_R P_{t-s} f|.$ 那么对$H$求导, 应用前一引理即有:
$$\begin{aligned}
\partial_s H_s&= P_s A^{R-1}\Delta(P_{t-s}f)^2-2P_s A^{R-1}P_{t-s}f \cdot \Delta P_{t-s} f\\
&=2P_sA^{R-1} \Gamma (P_{t-s}f)\\
&\ge \frac{Q_{\min}^R}{R}P_s|\nabla_R P_{t-s}f|^2\\
&\ge \frac{Q_{\min}^R}{R}(P_s|\nabla_R P_{t-s}f|)^2\\
&=\frac{Q_{\min}^R}{R}e^{2Ks}G_s^2.
\end{aligned}$$
积分并利用$G_s$是单增的, 得到:
$$H_t-H_0\ge \frac{Q_{\min}^R}{R}G_0^2\int_0^te^{2Ks}ds=\frac{Q_{\min}^R}{R}G_0^2\frac{e^{2Ks}-1}{2K}.$$
那么由于$\parallel Ag\parallel_{\infty}\le \deg_{\max}\parallel g\parallel_{\infty},$
$H_0\ge 0,$
$$\begin{aligned}
\deg_{\max}^{R-1}\parallel f\parallel_\infty^2&\ge A^{R-1}(P_tf)^2=H_t\\
&\ge \frac{Q_{\min}^R}{R}G_0^2\frac{e^{2Kt}-1}{2K}\\
&=\frac{Q_{\min}^R}{R}|\nabla_R P_tf|^2\frac{e^{2Kt}-1}{2K}.
\end{aligned}$$
整理即有定理成立.
需要注意的是, 该定理只在$\deg_{\max}<\infty,$ $Q_{\min}>0,$
即图$G$度数有一致上界, $Q$有非零一致下界时有意义.
指数曲率
Ollivier曲率以$K$为下界由下面的梯度估计刻画:
$$\parallel\nabla_R P_tf\parallel_{\infty}\le e^{-Kt}\parallel\nabla_R f\parallel_{\infty}.$$
指数Ollivier曲率的想法是对$f>0,$ 加强梯度估计为如下形式:
$$\parallel\nabla_R \log P_tf\parallel_{\infty}\le e^{-Kt}\parallel\nabla_R
\log f\parallel_{\infty}.$$
这的确是更强的形式,
因为$\frac{1}{\varepsilon}\log(1+\varepsilon f)\rightarrow f,$
$\varepsilon\rightarrow 0.$
因此下面的不等式成立可以通过取极限推出上面的梯度估计.
那么$\,\forall\,x,y\in V$满足$d(x,y)\le R,$
且$\log f(y)-\log f(x)=\parallel\nabla_R \log f\parallel_{\infty},$
类似先前的导出方法, 我们对两侧求导, 在$t=0$时, 有
$$\partial_t (\log P_t f(y)-\log P_t f(x))=\frac{\Delta f(y)}{f(y)}-\frac{\Delta f(x)}{f(x)}\le -K\parallel\nabla_R \log f\parallel_{\infty}.$$
令$f=\exp(g),$ 即有如下定义:
定义 1.9. 任意指定$R\in \mathbb{N},$ $x,y\in V,$ 定义指数梯度-Ollivier曲率:
$$K_R^e(x,y)=\inf_{\begin{subarray}{c}
r>0\\
\parallel\nabla_R g\parallel_{\infty}=r\\
g(y)-g(x)=r \end{subarray} }\frac{1}{r} \left(\frac{\Delta \exp(g)}{\exp(g)}(x)-\frac{\Delta \exp(g)}{\exp(g)}(y)\right)$$
类似地, 它的定义方式也是充分的.
定理 1.10. 若$K_R^e(x,y)\ge K,$ $\,\forall\,d(x,y)\le R,$ 且$G$为有限图. 那么$\,\forall\,0<f\in \ell^\infty(V),$
$$\parallel\nabla_R\log P_tf\parallel_{\infty}\le e^{-Kt}\parallel\nabla_R \log f\parallel_{\infty}.$$
证: 由于假设$G$是有限的, 最大模均能在某点取到. 记$g_0=\log P_tf,$
$r_0=\parallel\nabla_R g_0\parallel_{\infty},$ 则
$$\begin{aligned}
\partial_t\parallel\nabla_R\log P_t f\parallel_{\infty}
&=\sup_{\begin{subarray}{c}
d(x,y)\le R\\
\log P_tf(y)-\log P_tf(x)=\parallel\nabla_R \log P_t f\parallel_{\infty}
\end{subarray} }\partial_t(\log P_tf(y)-\log P_tf(x))\\
&=-r_0\inf_{\begin{subarray}{c}
d(x,y)\le R\\
g_0(y)-g_0(x)=\parallel\nabla_R g_0\parallel_{\infty}=r_0
\end{subarray} }\frac{1}{r_0}\left(\frac{\Delta \exp(g_0)}{\exp(g_0)}(x)-\frac{\Delta \exp(g_0)}{\exp(g_0)}(y)\right)\\
&\le -r_0\inf_{\begin{subarray}{c}
d(x,y)\le R\\
g(y)-g(x)=\parallel\nabla_R g\parallel_{\infty}=r
\end{subarray} }\frac{1}{r}\left(\frac{\Delta \exp(g)}{\exp(g)}(x)-\frac{\Delta \exp(g)}{\exp(g)}(y)\right)\\
&=-r_0 \inf_{d(x,y)\le R} K_R^e(x,y)\le -r_0 K=-K\parallel\nabla_R\log P_t f\parallel_{\infty}.
\end{aligned}$$
从而$\partial_t \log \parallel\nabla_R\log P_t f\parallel_{\infty}\le -K,$
积分得到定理成立.
文章最后更新于 2021-11-16 15:29:10
Large scale Ricci curvature on graphs - Mark Kempton · Gabor Lippner ·
Florentin Münch
Many curvatures on the graph are only limited to the vicinity of points and their neighbors, and the local range is too small.
This may result in the inability to derive interesting results. This article introduces neighborhood radius $R,$
Define various concepts with a scale of $R$ and derive curvature.
mark
Weighted graph $G(V,w,m),$
$$\Delta f(x):=\frac{1}{m(x)}\sum_yw(x,y)(f(y)-f(x)),$$
From this derives the Dirichlet form for energy methods:
$$Q(f,f):=\left<{}-\Delta f,f\right>,$$
Then derive Bakry-Emery(carré du
champ) operator:
$$\Gamma(f,g):=\frac{1}{2}(\Delta(fg)-f\Delta g-g\Delta f),$$
Calculated:
$$\Gamma(f,g)(x)=\frac{1}{2m(x)}\sum_y w(x,y)[f(y)-f(x)][g(y)-g(x)].$$
Remember$\Gamma f:=\Gamma(f,f),$
Then $\Gamma f=\frac{1}{2}\parallel\nabla f\parallel^2.$
The thermal semigroup generated by $\Delta$ is denoted as $\{P_t=e^{t\Delta}\},$ such that $P_tf$ satisfies the thermal equation
$$\partial_t P_tf=\Delta P_tf.$$
Curvature export
For the Riemannian manifold $M,$, the Ricci curvature with $K$ as the lower bound is equivalent to
$$|\nabla P_tf|\le e^{-Kt}P_t|\nabla f|,\quad \,\forall\,C_c^\infty(M).$$
We define $R$-gradient to generalize this concept to graphs on a large scale.
Let $B_R(x)=\{y:d(x,y)\le R\}.$ pair $f:V\rightarrow \mathbb{R},$ $x\in V,$
Definition:
$$|\nabla_R f|(x):=\max_{y\in B_R(x)}|f(y)-f(x)|.$$
Next we consider the order
$$|\nabla_R P_tf|\le e^{-Kt}P_t|\nabla_R f|$$
What are the necessary conditions for its establishment.
Since both sides are equal when $t=0$, the derivative on the right side should be larger than the derivative on the left when $t=0$.
Note that the curvature condition $K$ can be proposed by deriving the derivation on both sides, and we perform the derivation.
Since $P_tf$ changes continuously, $\,\exists\,y_0\in B_R(x)$ makes
$$|\nabla_RP_tf|(x)=|P_tf(y_0)-P_tf(x)|,\quad \,\forall\,t\in[0,\varepsilon].$$
Then for $y\in B_R(x),$ that satisfies $|\nabla_R f|(x)=|f(y)-f(x)|$
$$|\nabla_RP_tf|(x)=|P_tf(y_0)-P_tf(x)|\ge |P_tf(y)-P_tf(x)|,\quad \,\forall\,t\in[0,\varepsilon],$$
And when $t=0$, both sides are equal, so when $t=0$, the derivative on the left side is also larger than the derivative on the right side.
When calculating $t=0$, the derivative on the right side is
$$\partial_t (P_tf(y)-P_tf(x))\operatorname{sgn}(P_tf(y)-P_tf(x))=(\Delta f(y)-\Delta f(x))\operatorname{sgn}(f(y)-f(x)),$$
Therefore, for any $y\in B_R(x),$ satisfying $|\nabla_R f|(x)=|f(y)-f(x)|$
$$\begin{aligned}
(\Delta f(y)-\Delta f(x))\operatorname{sgn}(f(y)-f(x))&\le \partial_t |\nabla_RP_tf|(x)\le \partial_t (e^{-Kt}P_t|\nabla_Rf|)\\
&\le -K|\nabla_R f|(x)+\Delta |\nabla_R f|(x).
\end{aligned}$$
So we have the inequality for curvature:
$$K|\nabla_R f|(x)\le\Delta |\nabla_R f|(x)-(\Delta f(y)-\Delta f(x))\operatorname{sgn}(f(y)-f(x)).$$
The left and right dimensions of $f$ are $1,$. Let’s assume $|\nabla_R f|=1,$
The following curvature definition method is derived from this:
Definition 1.1. Arbitrarily specify $R\in \mathbb{N},$ $x,y\in V,$ definition Gradient - Ollivier Curvature:
$$K_R(x,y):=\inf_{\begin{subarray}{c}
f:V\rightarrow \mathbb{R}\\
|\nabla_Rf|(x)=1\\
|f(y)-f(x)|=|\nabla_R f|(x)
\end{subarray} }\Delta|\nabla_R f|(x)-(\Delta f(y)-\Delta f(x))\operatorname{sgn}(f(y)-f(x)).$$
Contact Ollivier Curvature
Theorem 1.2. $\,\forall\,x\sim y,$ We have:
$$K_1^{Ol}(x,y)\ge K_1(x,y).$$
Certificate: By definition,
$$K_1^{Ol}(x,y)=\min_{\begin{subarray}{c}
\parallel\nabla f\parallel_{\infty}=1\\
f(y)-f(x)=1
\end{subarray} }\Delta f(x)-\Delta f(y).$$
Let $f$ be the function that achieves the minimum value, then $|\nabla_1 f|(x)=1,$ and $\,\forall\,z\sim x,$
$|\nabla_1 f|(z)\le 1.$ This means $\Delta |\nabla_1 f|(x)\le 0.$ Therefore:
$$K_1(x,y)\le \Delta |\nabla_1f|(x)+K_1^{Ol}(x,y)\le K_1^{Ol}(x,y).$$
Gradient estimation
Next, it will be shown that this way of defining curvature is actually sufficient. First, the following lemma is required:
Lemma 1.3. If $K_R(x,y)\ge K,$ $\,\forall\,d(x,y)\le R.$ given $t>0,$, get the function
$$G_s:=e^{-Ks}P_s|\nabla_R P_{t-s}f|,\quad s\in[0,t]$$
Then $G_s$ is an increasing function.
Certificate:
It is only necessary to prove that the lower derivative $\underline{\partial}_sG_s:=\varliminf\limits_{h\rightarrow 0}\frac{G_{s+h}-G_s}{h}\ge0.$ of $G_s$
Calculated:
$$\underline{\partial}_sG_s=-KG_s+e^{-Ks}(P_s(\underline\partial_s|\nabla_RP_{t-s}f|)+\Delta P_s|\nabla_R P_{t-s}f|).$$
In the same way as when exporting curvature,
$\,\forall\,y\in B_R(x)$ satisfies $|\nabla_R P_{t-s}f|(x)=|P_{t-s}f(y)-P_{t-s}f(x)|,$
There are:
$$\begin{aligned}
\underline\partial_s|\nabla_RP_{t-s}f|(x)&\ge \partial_s|P_{t-s}f(y)-P_{t-s}f(x)|\\
&=(\partial_s P_{t-s}f(y)-\partial_s P_{t-s}f(x))\operatorname{sgn}(P_{t-s}f(y)-P_{t-s}f(x))\\
&=-(\Delta P_{t-s}f(y)-\Delta P_{t-s}f(x))\operatorname{sgn}(P_{t-s}f(y)-P_{t-s}f(x))\\
&\ge |\nabla_R P_{t-s}f|(x)K_R(x,y)-\Delta |\nabla_RP_{t-s}f|(x)\\
&\ge K|\nabla_R P_{t-s}f|(x)-\Delta |\nabla_R P_{t-s} f|(x)
\end{aligned}$$
Since $P_s\Delta=\Delta P_s$ and for nonnegative functions $f\ge 0,$ $P_sf\ge 0,$ we have
$\underline{\partial}_s G_s\ge 0,$ The lemma is proved.
Comparing $G_0$ and $G_t,$, we immediately get the following theorem:
Theorem 1.4. If $K_R(x,y)\ge K,$ $\,\forall\,d(x,y)\le R,$ then
$$|\nabla_R P_tf|\le e^{-Kt}P_t|\nabla_R f|.$$
attenuation
When $K=0$, the above gradient estimate no longer gives good decay properties. We wish to prove the following estimate:
Theorem 1.5. If $\,\forall\,x,y\in V,$ $d(x,y)\le R,$ has $K_R(x,y)\ge 0.$ then
$$|\nabla_R P_tf|^2\le \frac{C}{t}\parallel f\parallel^2_{\infty},$$
We hope to use $\Gamma f$ to estimate $|\nabla_R f|^2,$ to give its upper bound.
However, $R\ge 2,$ $\Gamma$ only involves one step neighborhood,
So the basic idea is to sum $\Gamma f$ over a large enough neighborhood to control $|\nabla_R f|.$
We need the following tools.
Definition 1.6. For graph $G=(G,w,m),$, write $Q(x,y):=\frac{w(x,y)}{m(x)},$ then $\Delta f(x)=\sum_y Q(x,y)(f(y)-f(x)).$ Note $\deg(x):=\sum_y Q(x,y),$ $Q_{\min} :=\inf_{x\sim y}Q(x,y).$ and define $A:=\Delta+\deg_{\max},$ as average operator.
It is easy to see that it satisfies some simple properties:
$f\ge 0\Rightarrow Af\ge 0;$
$\parallel Af\parallel_{\infty}\le \deg_{\max}\parallel f\parallel_{\infty};$
$P_t A=AP_t.$
Lemma 1.7. $\,\forall\,f:V\rightarrow \mathbb{R},$ We have
$$|\nabla_R f|^2\le \frac{2R}{Q_{\min}^R}A^{R-1}\Gamma f.$$
Certificate: First estimate $A^{R-1}\Gamma f.$ and note $\,\forall\,g\ge 0,$
$$Ag(x)\ge \sum_y Q(x,y) g(y)\ge Q_{\min}\sum_{y\sim x}g(y).$$
Therefore,
$$A^{R-1}\Gamma f\ge Q_{\min}^{R-1}\sum_{x\sim x_1\sim\cdots\sim x_{R-1} } \Gamma f(x_{R-1}).$$
Similarly, $\Gamma f$ itself satisfies
$$\Gamma f(x)\ge \frac{1}{2}Q_{\min}\sum_{y\sim x}(f(z)-f(x))^2.$$
Therefore,
$$A^{R-1}\Gamma f(x)\ge \frac{1}{2}Q_{\min}^{R}\sum_{x\sim x_1\sim\cdots\sim x_{R} } (f(x_{R})-f(x_{R-1}))^2.$$
Then let $|\nabla_R f|(x)=|f(x)-f(y)|,$ $y\in B_R(x).$
Take $x=y_0\sim \cdots\sim y_r=y,$ $r\le R.$
Then from the basic inequality $\frac{a_1+\cdots+a_n}{n}\le \sqrt{\frac{a_1^2+\cdots+a_n^2}{n} },$
There are:
$$\begin{aligned}
A^{R-1}\Gamma f(x)&\ge \frac{1}{2}Q_{\min}^{R}\sum_{k=1}^r(f(y_k)-f(y_{k-1}))^2\\
&\ge \frac{1}{2}Q_{\min}^R\frac{1}{r}(f(y_r)-f(y_0))^2\\
&\ge \frac{1}{2}Q_{\min}^R\frac{1}{R}|\nabla_R f|^2.
\end{aligned}$$
The lemma is proved.
Now we can prove the previous theorem. In fact we can prove the following stronger version:
Theorem 1.8. Let $K_R(x,y)\ge K,$ $\,\forall\,x,y\in V,$ $d(x,y)\le R.$ then
$$\frac{e^{2Kt}-1}{2K}|\nabla_R P_tf|^2\le R\frac{\deg_{\max}^{R-1} }{Q_{\min}^{R} }\parallel f\parallel_{\infty}^2.$$
When $K=0$, $\frac{e^{2Kt}-1}{2K}:=t,$ is the previous theorem.
Certificate: Let$H_s:=A^{R-1}P_s[(P_{t-s}f)^2],$
$G_s:=e^{-Ks}P_s|\nabla_R P_{t-s} f|.$ Then take the derivative of $H$ and apply the previous lemma:
$$\begin{aligned}
\partial_s H_s&= P_s A^{R-1}\Delta(P_{t-s}f)^2-2P_s A^{R-1}P_{t-s}f \cdot \Delta P_{t-s} f\\
&=2P_sA^{R-1} \Gamma (P_{t-s}f)\\
&\ge \frac{Q_{\min}^R}{R}P_s|\nabla_R P_{t-s}f|^2\\
&\ge \frac{Q_{\min}^R}{R}(P_s|\nabla_R P_{t-s}f|)^2\\
&=\frac{Q_{\min}^R}{R}e^{2Ks}G_s^2.
\end{aligned}$$
Integrate and use $G_s$ to be monoincreasing, we get:
$$H_t-H_0\ge \frac{Q_{\min}^R}{R}G_0^2\int_0^te^{2Ks}ds=\frac{Q_{\min}^R}{R}G_0^2\frac{e^{2Ks}-1}{2K}.$$
Then because $\parallel Ag\parallel_{\infty}\le \deg_{\max}\parallel g\parallel_{\infty},$
$H_0\ge 0,$
$$\begin{aligned}
\deg_{\max}^{R-1}\parallel f\parallel_\infty^2&\ge A^{R-1}(P_tf)^2=H_t\\
&\ge \frac{Q_{\min}^R}{R}G_0^2\frac{e^{2Kt}-1}{2K}\\
&=\frac{Q_{\min}^R}{R}|\nabla_R P_tf|^2\frac{e^{2Kt}-1}{2K}.
\end{aligned}$$
The theorem is established by sorting it out.
It should be noted that this theorem only applies to $\deg_{\max}<\infty,$ $Q_{\min}>0,$
That is, it makes sense when the degree of graph $G$ has a consistent upper bound and $Q$ has a non-zero consistent lower bound.
exponential curvature
Ollivier curvature is characterized by the following gradient estimate with $K$ as the lower bound:
$$\parallel\nabla_R P_tf\parallel_{\infty}\le e^{-Kt}\parallel\nabla_R f\parallel_{\infty}.$$
The idea of exponential Ollivier curvature is to enhance the gradient estimate of $f>0,$ as follows:
$$\parallel\nabla_R \log P_tf\parallel_{\infty}\le e^{-Kt}\parallel\nabla_R
\log f\parallel_{\infty}.$$
This is indeed a stronger form,
Because$\frac{1}{\varepsilon}\log(1+\varepsilon f)\rightarrow f,$
$\varepsilon\rightarrow 0.$
Therefore, the following inequality holds and the above gradient estimate can be deduced by taking the limit.
Then $\,\forall\,x,y\in V$ satisfies $d(x,y)\le R,$
And $\log f(y)-\log f(x)=\parallel\nabla_R \log f\parallel_{\infty},$
Similar to the previous derivation method, we derive the derivative on both sides. At $t=0$, we have
$$\partial_t (\log P_t f(y)-\log P_t f(x))=\frac{\Delta f(y)}{f(y)}-\frac{\Delta f(x)}{f(x)}\le -K\parallel\nabla_R \log f\parallel_{\infty}.$$
Let $f=\exp(g),$ have the following definition:
Definition 1.9. Arbitrarily specify $R\in \mathbb{N},$ $x,y\in V,$ definition Exponential Gradient - Ollivier Curvature:
$$K_R^e(x,y)=\inf_{\begin{subarray}{c}
r>0\\
\parallel\nabla_R g\parallel_{\infty}=r\\
g(y)-g(x)=r \end{subarray} }\frac{1}{r} \left(\frac{\Delta \exp(g)}{\exp(g)}(x)-\frac{\Delta \exp(g)}{\exp(g)}(y)\right)$$
Similarly, the way it is defined is adequate.
Theorem 1.10. If $K_R^e(x,y)\ge K,$ $\,\forall\,d(x,y)\le R,$ and $G$ are finite graphs. Then $\,\forall\,0<f\in \ell^\infty(V),$
$$\parallel\nabla_R\log P_tf\parallel_{\infty}\le e^{-Kt}\parallel\nabla_R \log f\parallel_{\infty}.$$
Certificate: Since $G$ is assumed to be finite, the maximum module can be obtained at a certain point. Denote $g_0=\log P_tf,$
$r_0=\parallel\nabla_R g_0\parallel_{\infty},$ then
$$\begin{aligned}
\partial_t\parallel\nabla_R\log P_t f\parallel_{\infty}
&=\sup_{\begin{subarray}{c}
d(x,y)\le R\\
\log P_tf(y)-\log P_tf(x)=\parallel\nabla_R \log P_t f\parallel_{\infty}
\end{subarray} }\partial_t(\log P_tf(y)-\log P_tf(x))\\
&=-r_0\inf_{\begin{subarray}{c}
d(x,y)\le R\\
g_0(y)-g_0(x)=\parallel\nabla_R g_0\parallel_{\infty}=r_0
\end{subarray} }\frac{1}{r_0}\left(\frac{\Delta \exp(g_0)}{\exp(g_0)}(x)-\frac{\Delta \exp(g_0)}{\exp(g_0)}(y)\right)\\
&\le -r_0\inf_{\begin{subarray}{c}
d(x,y)\le R\\
g(y)-g(x)=\parallel\nabla_R g\parallel_{\infty}=r
\end{subarray} }\frac{1}{r}\left(\frac{\Delta \exp(g)}{\exp(g)}(x)-\frac{\Delta \exp(g)}{\exp(g)}(y)\right)\\
&=-r_0 \inf_{d(x,y)\le R} K_R^e(x,y)\le -r_0 K=-K\parallel\nabla_R\log P_t f\parallel_{\infty}.
\end{aligned}$$
Thus $\partial_t \log \parallel\nabla_R\log P_t f\parallel_{\infty}\le -K,$
The integral leads to the theorem being established.
The article was last updated on 2021-11-16 15:29:10
