圖嵌入

在 譜分群 裡已經有提到圖嵌入的概念，在這文章中我們將正式介紹它的演算法，以及相關的理論背景。在了解圖嵌入以後，我們也可以再回頭看譜分群，會更發現這樣的分群法是有它的道理的。

圖論中的圖本身只描述點和點之間的連接關係，並不預設點應該要被放在哪一個位置。圖嵌入的演算法提供了一個方式，計算每個點「適合」的位置，所以可以看成是把圖嵌入到歐氏空間中，從這個觀點來看，它常被稱為 spectral embedding，屬於 畫圖理論（graph drawing） 中的一類。而在機器學習中，它也可以被看成從圖資料（如社群網路）中萃取出各點的特徵，而從這個觀點出發的話，一般稱之為 Laplacian eigenmap。

綜觀而言，圖嵌入演算法希望將圖的點放到歐氏空間中，在某些基本的限制條件下希望有連邊的點盡可能地靠近，以下是它的基本做法。

圖嵌入演算法

輸入：賦權圖 \((G,w)\)、目標維度 \(r\)
輸出：\(n\times r\) 矩陣，其中 \(n\) 是圖的點數，而矩陣的每一列為各點要嵌入的座標
步驟：

  1. 將 \(L = L(G, w)\) 進行譜分解求得特微向量 \(\lambda_1 \leq \cdots \leq \lambda_n\) 以及其對應的特徵向量 \(\bu_1, \ldots, \bu_n\)。我們可以要求 \(\lambda_1 = 0\)、\(\bu_1 = \frac{1}{\sqrt{n}}\bone\)、各特徵向量長度均為 \(1\) 且彼此垂直。
  2. 令 \(U\) 為依序由 \(\bu_2, \ldots, \bu_{r+1}\) 組成其行向量的矩陣，並回傳 \(U\)。

如果考慮 譜分群 中提到 \(15\) 個點的例子，前五個點的座標大約會在 \((0.32, -0.18)\) 的位置、中間五個點大約在 \((0, 0.37)\)、後五個點則大約在 \((-0.32, -0.18)\)。我們會發覺各點的 \(x\)-座標相加會是 \(0\)，這是因為 \(\bu_2\) 和 \(\bu_1 = \frac{1}{\sqrt{n}}\bone\) 垂直的綠故，同樣地各點的 \(y\)-座標相加也會是 \(0\)。整體而言，圖嵌入演算法畫出來的重心會被置在原點上。

另外一個重點是，有連邊的兩個點會盡量被放在附近。我們先考慮 \(r = 1\) 且權重都是 \(1\) 的狀況。如果我們希望把圖嵌在 \(\mathbb{R}^1\) 上，每點的座標為 \(x_1, \ldots, x_n\)，並且讓相鄰的點愈接近愈好，則我們可以考慮最小值問題

\[ \min_{x_1, \ldots, x_n} \sum_{\{i,j\}\in E(G)} (x_i - x_j)^2. \]

然而這樣的最小值問題有一個顯而易見的答案，那就是 \(x_1 = \cdots = x_n\)，也就是把所有點嵌在同一點就好。另一方面，如果 \(x_1, \ldots, x_n\) 是最佳解，則任何平移過的 \(x_1 + s, \ldots, x_n + s\) 也都是最佳解。為避免後者，我們可以要求嵌入的中心要在原點，也就是 \(x_1 + \cdots + x_n = 0\)；為避免前者的退化狀況，我們可以再要求 \(x_1^2 + \cdots + x_n^2 = 1\)。如果寫成向量 \(\bx = (x_1, \ldots, x_n)\) 的樣子，上述的問題就可以寫成

\[ \begin{aligned} & \min_{\bx} \sum_{\{i,j\}\in E(G)} (x_i - x_j)^2, \\ & \text{subject to }\bx\trans\bx = 1,\ \bone\trans\bx = 0. \end{aligned} \]

由於 \(\bx\trans L\bx = \sum_{\{i,j\}\in E(G)} (x_i - x_j)^2\)，根據瑞利商定理，這個最小值問題發生在 \(\bx = \bu_2\) 的時候。

對於一般維度 \(r\) 且考慮任何權重的狀況下，圖嵌入演算法想找的是 \(\mathbb{R}^r\) 中的座標 \(\bx_1, \ldots, \bx_n\) 來解最小值問題

\[ \min_{\bx} \sum_{\{i,j\}\in E(G)} w_{i,j}\|\bx_i - \bx_j\|^2. \]

留意到這裡每點被嵌入成一個 \(r\) 維向量，所以原本的差值 \(x_i - x_j\) 被取代成兩向量的距離 \(\|\bx_i - \bx_j\|\)，而權重愈大的邊在目標函數中的權重也愈大，表示權重大的邊的兩端點，應該要更盡可能地放近一些。如果我們把 \(\bx_1\trans, \ldots, \bx_n\trans\) 當成列向量擺成一個矩陣 \(X\)，則目標函數就可以寫成 \(\tr(X\trans LX)\)。

另一方面，我們仍然要考慮置中及退化的問題，所以可以加上 \(X\trans X = I\) 及 \(\bone\trans X = \bzero\trans\) 等條件。總結來說，我們要考慮的最小值問題是

\[ \begin{aligned} & \min_{X} \tr(X\trans LX), \\ & \text{subject to }X\trans X = I,\ \bone\trans X = \bzero. \end{aligned} \]

同樣的最小值問題改用 \(X\) 的行向量的觀點來看，我們要找的是一些長度是 \(1\) 且互相垂直的行向量（因為 \(X\trans X = I\)），同時每個行向量已經置中在原點 \(\bone\trans X\)。換以資料科學的角度來看，把這些行向量看成新的特徵，則我們要求的是這些特徵已經標準化成長度 \(1\)、置中、而且彼此獨立（置中向量的內積就是兩特徵的共變異數）。而在行向量的觀點來看，它的解剛好就是演算法算出來的 \(X = U\)。

想想以下問題：

  1. 說明為什麼
    \[ X\trans LX = \sum_{\{i,j\}\in E(G)} w_{i,j}(\bx_i - \bx_j)(\bx_i - \bx_j)\trans \]

    並藉此說明 \(\tr(X\trans LX) = \sum_{\{i,j\}\in E(G)} w_{i,j}\|\bx_i - \bx_j\|^2\)。

  2. 把 \(10\) 個點的路徑圖 \(P_{10}\) 用圖嵌入演算法畫在 \(\mathbb{R}^2\) 上。
  3. 把 \(10\) 個點的圈圖 \(C_{10}\) 用圖嵌入演算法畫在 \(\mathbb{R}^2\) 上。