谱图论：Laplacian二次型和Markov转移算子

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

1 问题定义

1.1 无向图(G)

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

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

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

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

1.2 顶点标签(f)

定义 设函数

[f: Vrightarrow mathbb{R} ]

将图的每个顶点用一个实数值来进行标记，我们称其为顶点标签（vertex labelling）。在实际应用场景中，(f)可能是温度、电压、嵌入的坐标（推广到(mathbb{R}^d)时）或者(Ssubseteq 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: Vrightarrow mathbb{R}})上带有加法和标量乘法：

• 加法：(f+g)（逐点）；
• 标量乘法：(ccdot f)（(cinmathbb{R})）；

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

2 Laplacian二次型

2.1 定义

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

[mathcal{E}left[fright] = frac{1}{2}cdotmathbb{E}_{usim v}left[ left(fleft(uright) - fleft(vright)right)^2right] ]

（符号约定：(usim v)表示服从均匀分布的随机无向边((u, v)in E)）

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

2.2 性质

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

• (mathcal{E}left[fright]geqslant 0)；

• (mathcal{E}left[c cdot fright] = c^2 cdot mathcal{E}left[fright])；

• (mathcal{E}left[f + c right] = mathcal{E}left[fright])（(cinmathbb{R})）；

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

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

[f(u) = left{begin{matrix} 1quadtext{if}quad uin S\ 0quadtext{if}quad unotin S end{matrix}right. ]

则我们有：

[begin{aligned} mathcal{E}left[fright] &= frac{1}{2}cdotmathbb{E}_{usim v}left[left(mathbb{I}_S(u) - mathbb{I}_S(v)right)^2right] \ &= frac{1}{2} cdot mathbb{E}_{usim 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}_{usim v}left[urightarrow v text{ is stepping out of } Sright] end{aligned} ]

注意上述式子中要乘以(1/2)是因为我们考虑的是无向图，要避免有向边的重复计数（即“伸出”与“伸入”(S)），最后只需计算“伸出”(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)上的均匀分布。

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

事实 下列步骤：

• 随机采 (usim pi)；
• 再均匀随机地采(u)的一个邻居(v)（记为(vsim u)）

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

推论 设(tin mathbb{N})，随机采(usim 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_0in V)是非随机的，并从(u_0 overset{t}{rightsquigarrow}v)。随着(trightarrow infin)，(v)的分布是否还会(rightarrow pi)？

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

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

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

2.4 (f)的均值和方差

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

均值（mean） (f)的均值定义为：

[mathbb{E}left[fright] = mathbb{E}_{usim pi}left[f(u)right] ]

例 若(Ssubseteq V)，(f=mathbb{I}_S)，则

[mathbb{E}left[ f right] = text{Pr}_{usim pi}left[uin Sright] ]

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

方差（variance） (f)的方差定义为：

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

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

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

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

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

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

3 Laplacian二次型的极值

3.1 (mathcal{F})上的的内积与范数

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

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

[langle f, g rangle_{pi} := mathbb{E}_{usim 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, grangle_{pi}=langle g, frangle_{pi})；
• (langle ccdot f + g, hrangle_{pi} = clangle f, hrangle_{pi} + langle g, h rangle_{pi})（(cinmathbb{R})）；
• (langle f, frangle_{pi}=mathbb{E}_{usimpi}left[f(u)^2right]geqslant 0quad text{with equality iff } fequiv 0)；

定义 对于(finmathcal{F})，我们可以由内积诱导出(f)的(2)-范数：

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

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

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

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

例 设(Ssubseteq V)，(f=mathbb{I}_S)，则

[begin{aligned} lVert frVert_1 &:= mathbb{E}_{usimpi}left[|f(u)|right] =mathbb{E}_{usimpi}left[f(u)right] \ &= text{Pr}_{usimpi}left[uin Sright] = text{Volume}(S) end{aligned} ]

且我们有

[begin{aligned} lVert frVert_2^2 := mathbb{E}_{usimpi}left[f(u)^2right] = mathbb{E}_{usimpi}left[f(u)right] = lVert frVert_1 & end{aligned} ]

3.2 最小化/最大化(mathcal{E}left[fright])

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

最小化 现在我们来考虑最小化(mathcal{E}left[fright])，即求解：

[min mathcal{E}[f] ]

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

首先对于(fequiv 0)（即将图的每个顶点都映射到(0)）这一trival的情况，(mathcal{E}left[fright]=0)；

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

[mathcal{E}[ f ]=frac{1}{2} mathbb{E}_{usim v}left[left(f(u) - f(v)right)^2right] = 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[fright]=0)约束）。所谓线性无关，直观上即如下所示的关系：

[begin{aligned} S_1bigg{ \ \ \ \ end{aligned} left(begin{aligned}1\1\1\0\vdots\0end{aligned}right) begin{aligned} \ \ \ \ S_2 bigg{\ \ end{aligned}left(begin{aligned}0\0\0\1\vdots\1end{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_imathbb{I}_{S_i}: c_1,cdots, c_lin mathbb{R}})。

最大化 接下来我们来考虑最大化(mathcal{E}left[fright])，即求解

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

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

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

[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\ Rightarrowmathbb{E}[f^2] &= text{Var}[f] + underbrace{mathbb{E}[f]^2}_0 end{aligned} ]

直觉上，该优化问题是在寻找一个好的嵌入(Vrightarrow 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[1right]=1)，且(mathcal{E}[f]=2)（由于(frac{1}{2}mathbb{E}_{usim v}[(f(u) - f(v))^2])中(f(u))和(f(v))都为(pm1)）

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

证明如下：

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

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

4 Markov转移算子

4.1 定义

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

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

这里

[mathbb{E}_{usim v}[f(u)cdot f(v)]=mathbb{E}_{usimpi}mathbb{E}_{vsim u}[f(u)f(v)] = mathbb{E}_{usimpi}left[f(u)cdot underbrace{mathbb{E}_{vsim u}left[f(v)right]}_*right] ]

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

定义 我们定义函数(Kf: Vrightarrowmathbb{R})满足

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

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

这里(K)为定义在函数空间(mathcal{F}={f: Vrightarrow mathbb{R}})上的线性算子，它将函数(finmathcal{F})映射到(Kfinmathcal{F})，并满足：

[begin{aligned} &K(f + g) = Kf + Kg \ &K(ccdot f) = ccdotleft( Kfright)quad (cin mathbb{R}) end{aligned} ]

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

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

[begin{aligned} urightarrow\ \ 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.}}[vrightarrow umid v] ]

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

4.2 自伴性质

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

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

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

[langle f, Kgrangle=mathbb{E}_{usim v}left[f(u)cdot g(v)right]=mathbb{E}_{vsim u}left[f(v)cdot g(u)right] ]

证明

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

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

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

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

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

例 设(S, Tsubseteq V)（(Scap T=emptyset)），(f=mathbb{I}_S)，(g=mathbb{I}_T)，则：

[begin{aligned} langle f, Kgrangle &=mathbb{E}_{usim v}left[mathbb{I}_S(u) cdot mathbb{I}_T(v)right] \ &= text{Pr}_{usim v}left[uin S, vin Tright] 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} ]

我们进行如下步骤：

• 随机采一个顶点(usim p)。
• 进行一步从(urightarrow v)的随机游走，并设(p^{prime})为(v)的概率分布。

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

[ 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} urightarrow w\ 2 text{ step} end{aligned}}left[f(w)right] ]

证明 给定(f)，设(g=Kf)，则

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

故

[（K^2f)(u) = (Kg)(u) = mathbb{E}_{vsim u}left[g(v)right] = mathbb{E}_{vsim u}left[(Kf)(v)right] = mathbb{E}_{vsim u}left[mathbb{E}_{wsim v}left[f(w)right]right] quadblacksquare ]

推论 (forall t in mathbb{N})，((K^tf)(u)=mathbb{E}_{u overset{ttext{-step S.R.W}}{ rightsquigarrow} w}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.