谱图论：Laplacian二次型和Markov转移算子-Toy模板网

这篇具有很好参考价值的文章主要介绍了谱图论：Laplacian二次型和Markov转移算子。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

以下部分是我学习CMU 15-751: TCS Toolkit的课堂笔记。由于只是个人笔记，因此许多地方在推导上可能不那么严谨，还望理论大佬多多包涵。

1 问题定义

1.1 无向图$G$

在本文中，我们将研究对象限定在无向图（undirected graph）$G=(V, E)$，且满足：

有限（finite）；
允许重边和自环；
不允许度为0的顶点（即孤立，isolated顶点），但允许有多个连通分量；

此外，我们在某些情况下可能会假设$G$是正则的。

正则图：指各顶点的度均相同的无向简单图。

1.2 顶点标签$f$

定义设函数

\[f: V\rightarrow \mathbb{R} \]

将图的每个顶点用一个实数值来进行标记，我们称其为顶点标签（vertex labelling）。在实际应用场景中，$f$可能是温度、电压、嵌入的坐标（推广到$\mathbb{R}^d$时）或者$S\subseteq V$的0-1示性函数。

在本文中，我们会将函数$f$想成是一个如下所示的（列）向量：

\[\left(\begin{aligned} \bigg|\\ f\\ \bigg| \end{aligned}\right)\begin{aligned} \leftarrow &v_1\\ \leftarrow &v_2\\ &\vdots \\ \leftarrow &v_n \end{aligned} \]

回顾函数集合$\mathcal{F}=\{f: V\rightarrow \mathbb{R}\}$上带有加法和标量乘法：

加法：$f+g$（逐点）；
标量乘法：$c\cdot f$（$c\in\mathbb{R}$）；

可以证明，$\mathcal{F}$是一个向量空间，且维度$n=|V|$。后面我们还会在$\mathcal{F}$上定义内积和范数。

2 Laplacian二次型

2.1 定义

接下来我们将要介绍的是谱图论（spectral graph theory）的关键，也就是Laplacian二次型（Laplacian quadratic form），其定义如下：

\[\mathcal{E}\left[f\right] = \frac{1}{2}\cdot\mathbb{E}_{u\sim v}\left[ \left(f\left(u\right) - f\left(v\right)\right)^2\right] \]

（符号约定：$u\sim v$表示服从均匀分布的随机无向边$(u, v)\in E$，有时把它想成两条“有向边”（$u$到$v$和$v$到$u$）是很有用的，前面的$\frac{1}{2}$系数有其妙处，我们后面会介绍）

直观地理解，Laplacian二次型刻画了图的“能量”（energy），这也是我们为什么用$\mathcal{E}(f)$来表示它的原因。它在其它语境下，又被称为Dirichlet形式（Dirichlet form），局部方差（local variance），解析边界大小（analytic boundary size）。

2.2 性质

关于Laplacian二次型，我们有以下事实：

$\mathcal{E}\left[f\right]\geqslant 0$；
$\mathcal{E}\left[c \cdot f\right] = c^2 \cdot \mathcal{E}\left[f\right]$；
$\mathcal{E}\left[f + c \right] = \mathcal{E}\left[f\right]$（$c\in\mathbb{R}$）；

直觉上，$\mathcal{E}\left[f\right]$的值越小，也就意味着$f$更加“光滑”（smooth），即其值不会沿着边变化得太剧烈。

例设图顶点的子集$S\subseteq V$, 0-1示性函数$f=\mathbb{I}_{S}$用于指示顶点是否在集合$S$中，即：

\[f(u) = \left\{\begin{matrix} 1\quad\text{if}\quad u\in S\\ 0\quad\text{if}\quad u\notin S \end{matrix}\right. \]

则我们有：

\[\begin{aligned} \mathcal{E}\left[f\right] &= \frac{1}{2}\cdot\mathbb{E}_{u\sim v}\left[\left(\mathbb{I}_S(u) - \mathbb{I}_S(v)\right)^2\right] \\ &= \frac{1}{2} \cdot \mathbb{E}_{u\sim v}\left[\mathbb{I}_{(u, v) \text{ crosses the cut } (S, \bar{S})}\right]\\ &= \frac{1}{2}\left[\text{frac. of edges on the boundary of $S$}\right]\\ &= \text{Pr}_{u\sim v}\left[u\rightarrow v \text{ is stepping out of } S\right] \end{aligned} \]

这里可以看到乘以系数$\frac{1}{2}$的妙处了，如果我们把无向边$u \sim v$想成“伸出”与“伸入”$S$的两条有向边，那么乘以$\frac{1}{2}$可以使我们只计算“伸出”$S$的边。

2.3 标准随机游走

为了选择一个随机顶点，我们可以：

均匀随机地选择一条边 $(u, v)$；
输出 $u$（或$v$）；

我们依据此采样方式得到的顶点分布记为$\pi$，$\pi_i$表示顶点$i$被抽中的概率。我们有以下事实：

事实 $\pi(u)$正比于$\text{deg}(u)$，即

\[\pi [u] = \frac{\text{deg}(u)}{2|E| }， \]

（注意这里用到了握手定理，即$\sum_v \text{deg}(v)=2|E|$）

直观地看，$\pi$为每个顶点给出了权重/重要性。

注：如果$G$是正则的，那么$\pi$是在$V$上的均匀分布。

在此基础上，我们可以得到一些有用的结论。

事实下列步骤：

随机采 $u\sim \pi$；
再均匀随机地采$u$的一个邻居$v$（记为$v\sim u$）

实质上就等价于均匀随机地采样边$(u, v)$。如果我们接着输出$v$，则$v$也服从分布$\pi$。

推论设$t\in \mathbb{N}$，随机采$u\sim \pi$，进行$t$步的 “标准随机游走”（standard random walk，S.R.W.）：

\[\underbrace{u \rightarrow \cdot \rightarrow \cdot \rightarrow \cdots \rightarrow v}_{t} \]

则$v$的分布也是$\pi$。

定义 $\pi$是不变（invariant）/ 平稳（stationary）分布。

Q：现在假设$u_0\in V$是非随机的，并从$u_0 \overset{t}{\rightsquigarrow}v$。随着$t\rightarrow \infin$，$v$的分布是否还会$\rightarrow \pi$？

A：当$G$非连通图时不是；当$G$为二分图时也不是；而其它情况都是如此（我们后面会介绍原因）。

Q：那么需要多少步才能到达平稳分布呢（也即马尔可夫链的混合时间，mixing time）？

A：这需要考虑图$G$的谱（特征值），具体我们会在下一讲中介绍。直观的例子比如图拥有较小的割集，那么在随机游走时就需要较长的时间来跨越$S$和$\bar{S}$；更极端的例子比如非连通图直接永远不会达到平稳分布。在$2.2$中我们证明了若图的割集较小则其$\mathcal{E}\left[\mathbb{I}_S\right]$就较小，而我们后面会看到快速收敛等价于$\mathcal{E}\left[f\right]$永远不会小。

2.4 $f$的均值和方差

设$f:V\rightarrow \mathbb{R}$，若$u\sim \pi$，则$f(u)$是一个实随机变量（我们这里简记为$f$）。对于该随机变量，我们接下来讨论它的均值与方差。

均值（mean） $f$的均值定义为：

\[\mathbb{E}\left[f\right] = \mathbb{E}_{u\sim \pi}\left[f(u)\right] \]

例若$S\subseteq V$，$f=\mathbb{I}_S$，则

\[\mathbb{E}\left[ f \right] = \text{Pr}_{u\sim \pi}\left[u\in S\right] \]

直观上，这个概率表示$S$的“权重”或“体积”。

方差（variance） $f$的方差定义为：

\[\begin{aligned} \text{Var}\left[f\right]=\text{Var}_{u\sim \pi}\left[f(u)\right]&\overset{(1)}{=}\mathbb{E}_{u\sim \pi}\left[\left(f\left(u\right) - \mu\right)^2\right] \\ &\overset{(2)}{=}\mathbb{E}_{u\sim\pi}\left[f(u)^2\right] -\mathbb{E}_{u\sim\pi}\left[f(u)\right]^2 \\ &\overset{(3)}{=} \frac{1}{2}\mathbb{E}_{\underset{\text{indep.}}{u, v \sim \pi}}\left[\left(f\left(u\right) - f\left(v\right)\right)^2\right] \end{aligned} \]

注意，上述式$(3)$成立是由于：

\[\begin{aligned} &\mathbb{E}\left[\left(f\left(u\right) - f\left(v\right)\right)^2\right]\\ &=\mathbb{E}\left[f(u)^2 - 2f(u)f(v) + f(v)^2\right] \\ &=\underbrace{\mathbb{E}\left[f(u)^2\right] + \mathbb{E}\left[f(v)^2\right]} - \underbrace{2 \mathbb{E}\left[f(u)f(v)\right]}\\ &= 2\cdot \mathbb{E}\left[f(u)^2\right] - \underbrace{2\mathbb{E}\left[f(u)\right]\mathbb{E}\left[f(v)\right]}_{2\cdot\mathbb{E}\left[f(u)\right]^2} \end{aligned} \]

辨析这里要注意$f$的方差$\text{Var}(f)$和其能量$\mathcal{E}(f)$的差异，它们俩的对比如下：

\[\begin{aligned} \text{Var}\left[f\right]&=\frac{1}{2}\mathbb{E}_{\underset{\text{indep.}}{u, v \sim \pi}}\left[\left(f\left(u\right) - f\left(v\right)\right)^2\right] \\ \mathcal{E}\left[f\right]&=\frac{1}{2}\mathbb{E}_{u \sim v}\left[\left(f\left(u\right) - f\left(v\right)\right)^2\right] \end{aligned} \]

可见方差$\text{Var}[f]$是对图的顶点取期望（我们称其为关于$f$的全局方差，global variance），而$\mathcal{E}[f]$则是对图的边取期望（我们称其为关于$f$的局部方差，local variance）。

3 Laplacian二次型的极值

3.1 $\mathcal{F}$上的的内积与范数

接下来我们讨论Laplacian二次型的极值，而这就需要我们先定义$\mathcal{F}=\{f: V\rightarrow \mathbb{R}\}$空间上的内积和范数。

定义设$f, g: V\rightarrow\mathbb{R}$，则向量空间$\mathcal{F}$上的 加权内积（weighted inner product） 可以定义为：

\[\langle f, g \rangle_{\pi} := \mathbb{E}_{u\sim \pi}[f(u)\cdot g(u)] \]

直观地，我们可以将其写做：

\[\langle \left(\begin{aligned} \bigg| \\ f\\ \bigg| \end{aligned}\right), \left(\begin{aligned} \bigg| \\ g\\ \bigg| \end{aligned}\right) \rangle_{\pi} \]

注：当$G$是正则图时（此时$\pi$为均匀分布），上式是经由$\frac{1}{|V|}$缩放的“标准点积”（normal dot product）。

回顾实向量空间上的内积满足以下性质

$\langle f, g\rangle_{\pi}=\langle g, f\rangle_{\pi}$；
$\langle c\cdot f + g, h\rangle_{\pi} = c\langle f, h\rangle_{\pi} + \langle g, h \rangle_{\pi}$（$c\in\mathbb{R}$）；
$\langle f, f\rangle_{\pi}=\mathbb{E}_{u\sim\pi}\left[f(u)^2\right]\geqslant 0\quad \text{with equality iff } f\equiv 0$；

定义对于$f\in\mathcal{F}$，我们可以由内积诱导出$f$的$2$-范数：

\[\lVert f \rVert_2 := \sqrt{\langle f, f\rangle_{\pi}} = \sqrt{\mathbb{E}_{u\sim\pi}\left[f(u)^2\right]}。 \]

处理2-范数的平方通常比直接处理它更容易，故我们常常使用$ \lVert f \rVert^2_2:=\langle f, f\rangle_{\pi}=\mathbb{E}_{u\sim\pi}\left[f(u)^2\right] $。

此外，我们还可以定义$f$的$1$-范数：

\[\lVert f \rVert_1 := \mathbb{E}_{u\sim \pi}\left[|f(u)|\right] \]

例设$S\subseteq V$，$f=\mathbb{I}_S$，则

\[\begin{aligned} \lVert f\rVert_1 &:= \mathbb{E}_{u\sim\pi}\left[|f(u)|\right] =\mathbb{E}_{u\sim\pi}\left[f(u)\right] \\ &= \text{Pr}_{u\sim\pi}\left[u\in S\right] = \text{Volume}(S) \end{aligned} \]

且我们有

\[\begin{aligned} \lVert f\rVert_2^2 := \mathbb{E}_{u\sim\pi}\left[f(u)^2\right] = \mathbb{E}_{u\sim\pi}\left[f(u)\right] = \lVert f\rVert_1 & \end{aligned} \]

3.2 最小化/最大化$\mathcal{E}\left[f\right]$

我们在 2.3 中提到随机游走快速收敛等价于$\mathcal{E}\left[f\right]$永远不会小，那么$\mathcal{E}\left[f\right]$能够有多小呢？

最小化 现在我们来考虑最小化$\mathcal{E}\left[f\right]$，即求解：

\[\min \mathcal{E}[f] \]

我们已知$\mathcal{E}[f]\geqslant0$，故我们接下来讨论什么样的$f$可以使$\mathcal{E}[f]=0$。

首先对于$f\equiv 0$（即将图的每个顶点都映射到$0$）这一trival的情况，$\mathcal{E}\left[f\right]=0$；

接下来考虑non-trival的情况。我们注意到$f\equiv 1$（或任何其它常数）时，

\[\mathcal{E}[ f ]=\frac{1}{2} \mathbb{E}_{u\sim v}\left[\left(f(u) - f(v)\right)^2\right] = 0 \]

事实上，由于图的不同连通分量之间是不存在边的，因此只要保证$f$在图$G$的每个连通分量上是常数就行。

命题 $\mathcal{E}[f]=0$当且仅当$f$在$G$的每个连通分量上是常数。此时：

\[\#\text{ connected components of } G = \#\text{ lin. indep } f \text{ with } \mathcal{E}[f]=0 \]

即当图的连通分量为$S_1,\cdots, S_l$时, $\mathbb{I}_{S_1}, \mathbb{I}_{S_2}, \cdots, \mathbb{I}_{S_l}$是线性无关的（linearly independent）（并满足$\mathcal{E}\left[f\right]=0$约束）。所谓线性无关，直观上即如下所示的关系：

\[\begin{aligned} S_1\bigg\{ \\ \\ \\ \\ \end{aligned} \left(\begin{aligned}1\\1\\1\\0\\\vdots\\0\end{aligned}\right) \begin{aligned} \\ \\ \\ \\ S_2 \bigg\{\\ \\ \end{aligned}\left(\begin{aligned}0\\0\\0\\1\\\vdots\\1\end{aligned}\right) \]

更一般地说，集合$\{f: \mathcal{E}[f]=0\}$事实上就是$\mathbb{I}_{S_1}, \mathbb{I}_{S_2}\cdots, \mathbb{I}_{S_l}$的张成空间$\{\sum^l_{i=1}c_i\mathbb{I}_{S_i}: c_1,\cdots, c_l\in \mathbb{R}\}$。

最大化 接下来我们来考虑最大化$\mathcal{E}\left[f\right]$，即求解

\[\begin{aligned} &\text{max } \mathcal{E}[f]\quad \\ \text{s.t.}\quad &\text{Var}[f]=1(\leqslant 1) \end{aligned} \]

（这里需要注意由于$\mathcal{E}[c\cdot f]=c^2\mathcal{E}[f]$，故我们要添加关于$\text{Var}\left[f\right]$的约束项以控制常数缩放因子的影响）

事实上，上述优化问题即等价于：

\[\begin{aligned} &\text{max } \mathcal{E}[f]\quad \\ \text{s.t.}\quad &\lVert f \rVert^2_2=\mathbb{E}\left[ f^2 \right]=1 (\leqslant1) \end{aligned} \]

这是因为：

\[\begin{aligned} \text{Var}[f] &= \mathbb{E}[f^2] - \mathbb{E}[f]^2\\ \Rightarrow\mathbb{E}[f^2] &= \text{Var}[f] + \underbrace{\mathbb{E}[f]^2}_0 \end{aligned} \]

直觉上，该优化问题是在寻找一个好的嵌入$V\rightarrow \mathbb{R}$，使得边的两个端点在嵌入空间中能够尽可能“远”。那么，什么样的$G$才能最成功呢？答案是二分图。

如果$G$是二分图，$V=(V_1, V_2)$。设

\[f = \mathbb{I}_{V_1} - \mathbb{I}_{V_2} \]

也即

\[f(u) = \left\{\begin{aligned} +1, \quad \text{if } u \in V_1 \\ -1, \quad \text{if } u \in V_2 \end{aligned}\right.， \]

于是我们有$\lVert f \rVert^2_2=\mathbb{E}[f^2]=\mathbb{E}\left[1\right]=1$，且$\mathcal{E}[f]=2$（由于$\frac{1}{2}\mathbb{E}_{u\sim v}[(f(u) - f(v))^2]$中$f(u)$和$f(v)$都为$\pm1$）

命题 $\mathcal{E}[f] \leqslant 2 \lVert f \rVert^2_2$（即$2\mathbb{E}[f^2]$）

证明如下：

\[\begin{aligned} \mathcal{E}[f] &= \frac{1}{2}\mathbb{E}_{u\sim v}\left[(f(u)-f(v))^2\right]\\ &= \frac{1}{2} \mathbb{E}_{\underbrace{u\sim v}_{u\sim\pi}}[f(u)^2] + \frac{1}{2}\mathbb{E}_{\underbrace{u\sim v}_{v\sim\pi}}[f(v)^2] - \mathbb{E}_{u\sim v}[f(u)f(v)]\\ & \leqslant \mathbb{E}[f^2] + \underbrace{\sqrt{\mathbb{E}_{u\sim v}[f(u)^2]}}_{\mathbb{E}\left[f^2\right]}\underbrace{\sqrt{\mathbb{E}_{u\sim v}[f(v)^2]}}_{\mathbb{E}\left[f^2\right]} \quad (\text{Cauchy Schwarz})\\ &=2 \mathbb{E}[f^2] \end{aligned} \]

例等式$\mathcal{E}[f] = 2 \lVert f\rVert^2_2$当且仅当$G$为二分图的时候成立。

4 Markov转移算子

4.1 定义

根据我们前面在 3.2 中的的叙述，我们已经知道

$\mathcal{E}[f]=\text{arithm}= \lVert f\rVert^2_2 - \mathbb{E}_{u\sim v}[f(u)\cdot f(v)] $

这里

\[\mathbb{E}_{u\sim v}[f(u)\cdot f(v)]=\mathbb{E}_{u\sim\pi}\mathbb{E}_{v\sim u}[f(u)f(v)] = \mathbb{E}_{u\sim\pi}\left[f(u)\cdot \underbrace{\mathbb{E}_{v\sim u}\left[f(v)\right]}_*\right] \]

注意上图中的带$*$表达式$\mathbb{E}_{v\sim u}\left[f(v)\right]$刻画的是顶点$u$邻居集合$\{v\}$的$f$标签平均值。而这个表达式实际上描述了一个将顶点$u$映射到其邻居标签平均值的函数，接下来我们就来进一步研究这个函数。

定义我们定义函数$Kf: V\rightarrow\mathbb{R}$满足

\[ \quad (Kf)(u)= \mathbb{E}_{v\sim u}\left[f(v)\right] \]

由于我们是离散状态空间，故上式可以写为$(Kf)(u)=\sum_v f(v)\text{Pr}\left[v\rightarrow u\mid v\right]$，这里$\text{Pr}[v\rightarrow u\mid v]$表示邻居顶点$v$到当前顶点$u$的状态转移概率。直观地理解，函数$Kf$使得顶点$u$被赋予其邻居集合的$f$标签平均值。

这里$K$为定义在函数空间$\mathcal{F}=\{f: V\rightarrow \mathbb{R}\}$上的线性算子，它将函数$f\in\mathcal{F}$映射到$Kf\in\mathcal{F}$，并满足：

\[\begin{aligned} &K(f + g) = Kf + Kg \\ &K(c\cdot f) = c\cdot\left( Kf\right)\quad (c\in \mathbb{R}) \end{aligned} \]

定义我们将上述的算子$K$称为图$G$的Markov转移算子（Markov transition operator）/归一化邻接矩阵（normalized adjacency matrix）。

我们可以将算子$K$表示成一个矩阵，该矩阵以如下方式作用：

\[\begin{aligned} u\rightarrow\\ \\ \end{aligned}\left( \begin{matrix} & \cdots & \\ & K & \\ & & \end{matrix}\right)\left(\begin{matrix} \bigg| \\ f \\ \bigg| \end{matrix}\right)\begin{aligned} \leftarrow &v_1\\ &\vdots\\ \leftarrow &v_n \end{aligned} =\left(\begin{aligned} \bigg|\\ K&f \\ \bigg| \end{aligned}\right) \begin{aligned} \leftarrow u \\ \\ \\ \end{aligned} \]

且满足

\[K[u, v]=\left\{ \begin{aligned} & \frac{1}{\text{deg}(v)}, f(v, u)\in E \\ & 0 \end{aligned} \right\}=\text{Pr}_{\text{S.R.W.}}[v\rightarrow u\mid v] \]

所以$K$是归一化后的邻接矩阵$A$的转置（当然这里由于我们关注无向图，$A^T=A$），其每一列的和为$1$（代表一个概率分布）。这样的矩阵被称为随机矩阵（stochastic marix）。

4.2 自伴性质

如果图$G$是$d$-正则的（即所有顶点的度都为$d$），那么我们有：

\[K = \frac{1}{d} A \quad \& \quad K\text{ is symmtric, } K^T= K \]

那么对于非正则图呢？此时$K$的矩阵表示（在非规范正交基下）尽管可能不再是对称阵，但是算子$K$仍然满足自伴的性质。我们有以下事实：
事实对于$f, g: V\rightarrow \mathbb{R}$，

\[\langle f, Kg\rangle=\mathbb{E}_{u\sim v}\left[f(u)\cdot g(v)\right]=\mathbb{E}_{v\sim u}\left[f(v)\cdot g(u)\right] \]

证明

\[\begin{aligned} \langle f, Kg\rangle &=\mathbb{E}_{u\sim \pi}\left[f(u)\cdot (Kg)(u) \right]\\ &=\mathbb{E}_{u\sim\pi}\left[f(u)\cdot \mathbb{E}_{v\sim u}\left[g(v)\right]\right] \\ &= \underbrace{\mathbb{E}_{u\sim \pi}\mathbb{E}_{v\sim u}}_{(u, v)\text{ rand edge}}\left[f(u)\cdot g(v)\right]\\ &= \mathbb{E}_{u\sim v}\left[f(u)\cdot g(v)\right]\\ &= \mathbb{E}_{v\sim u}\left[f(v)\cdot g(u)\right]\\ \end{aligned} \]

基于此，我们有下列推论：
推论

\[\langle Kf, g \rangle = \langle f, Kg \rangle \]

也即$K$是自伴的（self-adjoint）。而这在图$G$是正则图的情况下就等价于$K$是对称的。

接下来再来看我们熟悉的那个示性函数例子。

例设$S, T\subseteq V$（$S\cap T=\emptyset$），$f=\mathbb{I}_S$，$g=\mathbb{I}_T$，则：

\[\begin{aligned} \langle f, Kg\rangle &=\mathbb{E}_{u\sim v}\left[\mathbb{I}_S(u) \cdot \mathbb{I}_T(v)\right] \\ &= \text{Pr}_{u\sim v}\left[u\in S, v\in T\right] \end{aligned} \]

4.3 Markov链

概率分布转移 设$p$为在顶点$V$上的概率分布，即

\[p = \left(\begin{aligned} p_1\\ p_2\\ \vdots\\ p_n \end{aligned}\right)\begin{aligned} \leftarrow v_1 \\ \\ \\ \leftarrow v_n \end{aligned} \]

我们进行如下步骤：

随机采一个顶点$v\sim p$。
进行一步从$v\rightarrow u$的随机游走，并设$p^{\prime}$为$u$的概率分布。

则我们有如下的概率分布转移关系：

\[ \left(\begin{aligned} \bigg|\\ p^{\prime}\\ \bigg| \end{aligned}\right)= \left( \begin{matrix} & & \\ & K & \\ & & \end{matrix}\right) \left(\begin{aligned} \bigg|\\ p\\ \bigg| \end{aligned}\right) \]

推论对于平稳概率分布$\pi$，满足

\[\pi = K \pi \]

接下来我们再展示一个例子说明概率转移具体是如何运作的。

引理对于算子$K^2 = K \circ K $，我们有：

\[(K^2 f)(u) = \mathbb{E}_{\begin{aligned} w\rightarrow u\\ 2 \text{ step} \end{aligned}}\left[f(w)\right] \]

证明给定$f$，设$g=Kf$，则

\[K^2f = K(Kf) = Kg, \]

故

\[（K^2f)(u) = (Kg)(u) = \mathbb{E}_{v\sim u}\left[g(v)\right] = \mathbb{E}_{v\sim u}\left[(Kf)(v)\right] = \mathbb{E}_{v\sim u}\left[\mathbb{E}_{w\sim v}\left[f(w)\right]\right] \quad\blacksquare \]

推论 $\forall t \in \mathbb{N}$，$(K^tf)(u)=\mathbb{E}_{w \overset{t\text{-step S.R.W}}{ \rightsquigarrow} u}\left[ f(w)\right]$（甚至$t=0$时，我们也有$I f(u) = f(u)$）。

参考

[1] CMU 15-751: TCS Toolkit
[2] Bilibili: CMU计算机科学理论(完结)—你值得拥有的数学和计算机课)
[3] Spielman D. Spectral graph theory[J]. Combinatorial scientific computing, 2012, 18: 18.
[4] Axler S. Linear algebra done right[M]. springer publication, 2015.文章来源地址https://www.toymoban.com/news/detail-711845.html

到了这里，关于谱图论：Laplacian二次型和Markov转移算子的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！