圖分割 | LA Tea

在譜分群中我們探討了如何用拉普拉斯矩陣中，排在最前面幾位的特徵向量（依對應特徵值由小到大排序），來將圖分成許多塊。這邊我們討論 圖分割（graph partitioning），著重在利用第 \(2\) 位的特徵向量，來將圖分成兩塊。

要將圖分割成兩塊時，通常有兩個訴求：

兩塊之間的邊要盡可能地少。
兩塊的大小要盡可能地一樣。

舉例來說，如果一個圖有一個葉子，那麼把圖分成葉子和葉子以外的部份並不是太好的分割。雖然兩塊之間的邊很少，但兩塊的大小差異太大。

以符號來說，一個圖 \(G = (V,E)\) 的分割指的是兩個點集合 \(\{A,B\}\) 使得 \(V = A\cup B\) 且 \(A\cap B = \emptyset\)。當圖 \(G\) 已經固定時，\(E(A,B) = \{\{a,b\}: a\in A,\ b\in B\}\) 指的是 \(A\) 和 \(B\) 之間的邊。所以一個好的分割希望的是 \(\vert{}E(A,B)\vert{}\) 盡可能小，而 \(\vert{}A\vert{}\) 和 \(\vert{}B\vert{}\) 盡可能接近。

我們考慮一個理想化的平均分割問題：如果一個圖 \(G = (V,E)\) 有偶數個點，如何找到一個分割，使得 \(\vert{}A\vert{} = \vert{}B\vert{}\) 且 \(\vert{}E(A,B)\vert{}\) 最小。也就是考慮圖 \(G\) 分割 \(\{A,B\}\) 的最佳化問題

\[ \begin{aligned} & \min_{\{A,B\}} \vert{}E(A,B)\vert{}, \\ & \text{subject to } \vert{}A\vert{} = \vert{}B\vert{}. \end{aligned} \]

這樣的問題沒有很好的解法，如果窮舉的話則有 \(\frac{1}{2}\binom{\vert{}V\vert{}}{\vert{}V\vert{}/2}\) 種可能性要考慮。

有趣的是，前述的兩個訴求都可以用拉普拉斯矩陣來表示。令 \(n\) 為 \(G\) 的點數，而 \(L\) 為 \(G\) 的拉斯拉斯矩陣。首先，一個圖的分割也可以想成是把每個點標上 \(1\) 或 \(-1\) 兩種標號，而這樣的標號可以視為是一個向量 \(\by\in\mathbb{R}^n\)。實際上，\(\by\) 的元素只能是 \(\pm 1\)，所以我們用 \(\{\pm 1\}^n\) 來表示所有元素為 \(\pm 1\) 且長度為 \(n\) 的向量。給定一個向量 \(\by\in\{\pm 1\}^n\)，則我們可以推出以下關係：

\(\vert{}E(A,B)\vert{} = \frac{1}{4}\sum_{e\in E(A,B)}(1 - (-1))^2 = \frac{1}{4}\by\trans L\by\)。
\(\vert{}A\vert{} = \vert{}B\vert{}\) 等價於 \(\inp{\by}{\bone} = 0\)。

因此，原來的最佳化問題可以改寫為

\[ \begin{aligned} & \min_{\by\in\{\pm 1\}^n} \frac{1}{4}\by\trans L\by, \\ & \text{subject to } \inp{\by}{\bone} = 0. \end{aligned} \]

這樣的問題是所謂的整數規劃（integer programming），通常是很難解的問題。而在整數規劃裡一個常見的手法叫做 鬆弛（relaxation），意思是我們不再堅持變數 \(\by\) 一定要是整數向量，給它多一點自由，反而會讓問題更好解；得到的最小值雖然不是真正的答案，但依定義鬆弛過後的最小值還是為原式最小值提供了一個下界。因此我們把原式中的 \(\{\pm 1\}^n\) 改為 \(\mathbb{R}^n\) 得到

\[ \begin{aligned} & \min_{\by\in\mathbb{R}^n} \frac{1}{4}\by\trans L\by, \\ & \text{subject to } \inp{\by}{\bone} = 0. \end{aligned} \]

而這樣的問題完全變成瑞利商的樣態，由於 \(\bone\) 是 \(L\) 第 \(1\) 位的特徵向量，鬆弛後的最小值發生在 \(\by\) 是 \(L\) 第 \(2\) 位的特徵向量。因此，給定一個圖，我們可以計算它的第 \(2\) 位拉普拉斯向量 \(\by\)，並得到一個合理的圖分割 \(\{N_{\geq 0}, N_{<0}\}\)，這裡

\[ \begin{aligned} N_{\geq 0} &= \{i: (\by)_i \geq 0\}, \\ N_{< 0} &= \{i: (\by)_i < 0\}. \end{aligned} \]

這樣的圖分割除了給出一個合理的近似解以外，它還有一個附帶的好處。捷克數學家費德勒（Miroslav Fiedler，1926–2015）¹ 證明了這樣的分割會讓區塊連通。

定理（費德勒 1975）

令 \(G\) 為一連通圖、\(\by\) 為其第 \(2\) 位的拉普拉斯向量、且 \(N_{\geq 0} = \{i: (\by)_i \geq 0\}\)。則 \(G[N_{\geq 0}]\) 為連通圖。

費德勒的定理告訴我們 \(\{N_{\geq 0}, N_{< 0}\}\) 這樣的圖分割，除了是合理的分割，同時也尊重圖的結構。儘管定理不保證 \(G[N_{< 0}]\) 會連通，若將定理可以套用在 \(-\by\) 上，則可得到 \(G[N_{\leq 0}]\) 是連通的。（這裡 \(N_{\leq 0}\) 遵循類似的定義。）在多數狀況裡，\(\by\) 常常每項都非零，因此往往 \(N_{\leq 0} = N_{< 0}\) 會讓 \(G[N_{< 0}]\) 也是連通的。

費德勒的定理可以視為峰谷定理（nodal domain theorem）的雛形，後續會介紹。實際上，費德勒證明的不只是這個版本，一方面它證明了 \(G[N_{\geq c}]\) 對於所有 \(c \leq 0\) 時都是連通的，另一方面也推廣成：如果 \(\by\) 是第 \(k\) 位的特徵向量，則 \(G[N_{\geq 0}]\) 最多只有 \(k - 1\) 個連通區塊。

想想以下問題：

驗證 \(\vert{}E(A,B)\vert{}\) 的公式。
將 \(10\) 個點的路徑圖 \(P_{10}\) 利用第 \(2\) 位拉普拉斯特徵向量做圖分割，並比較此分割與圖嵌入的結果。
將 \(10\) 個點的圈圖 \(C_{10}\) 利用第 \(2\) 位拉普拉斯特徵向量做圖分割，並比較此分割與圖嵌入的結果。
找一個例子讓 \(G[N_{< 0}]\) 是不連通的。
若 \(G\) 是賦權圖，說明 \(\frac{1}{4}\by\trans L\by\) 代表的是什麼，以及我們該如何定義 \(\vert{}E(A,B)\vert{}\)。