譜圖論：Laplacian二次型和Markov轉移算子

以下部分是我學習CMU 15-751: TCS Toolkit的課堂筆記。接下來將要介紹的是譜圖論（spectral graph theory）的關鍵，也就是Laplacian二次型（Laplacian quadratic form）。直觀地理解，Laplacian二次型刻畫了圖的“能量”（energy）。它在其它語境下，又被稱為Dirichlet形式（Dirichlet form），局部方差（local variance），解析邊界大?。╝nalytic boundary size）。直覺上，其值越小，也就意味著f更加“光滑”（smooth），即其值不會沿著邊變化得太劇烈。

以下部分是我學習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}w0obha2h00 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.

posted @ 2023-09-27 00:32 orion-orion 閱讀(721) 評論(0) 收藏舉報

刷新頁面返回頂部

Orion's Blog

學習理論、在線優化、數據挖掘

譜圖論：Laplacian二次型和Markov轉移算子

1 問題定義

1.1 無向圖\(G\)

1.2 頂點標簽\(f\)

2 Laplacian二次型

2.1 定義

2.2 性質

2.3 標準隨機游走

2.4 \(f\)的均值和方差

3 Laplacian二次型的極值

3.1 \(\mathcal{F}\)上的的內積與范數

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

4 Markov轉移算子

4.1 定義

4.2 自伴性質

4.3 Markov鏈

參考

公告

Orion's Blog

學習理論、在線優化、數據挖掘

譜圖論：Laplacian二次型和Markov轉移算子

1 問題定義

1.1 無向圖\(G\)

1.2 頂點標簽\(f\)

2 Laplacian二次型

2.1 定義

2.2 性質

2.3 標準隨機游走

2.4 \(f\)的均值和方差

3 Laplacian二次型的極值

3.1 \(\mathcal{F}\)上的的內積與范數

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

4 Markov轉移算子

4.1 定義

4.2 自伴性質

4.3 Markov鏈

參考

公告

學習理論、在線優化、數據挖掘