2024 — 圖神經網路線性代數#

案件摘要#

圖神經網路（GNN）把「圖上的學習」還原成最樸素的線性代數：用鄰接矩陣 \(A\) 表示圖，訊息傳遞不過是一次矩陣乘法 \(AXW\) 。Kipf & Welling 2017 年的 GCN 用譜圖理論把這件事寫成規範公式：

Lanczos 時代就埋下的譜圖線索，在深度學習時代正式結案成為偵探工具：推薦系統、分子模擬、知識圖譜的共通語言。

前因 -- 為什麼會有這個案子#

• 1950 年 Lanczos 演算法：用三對角化求大型稀疏矩陣的極端特徵值，證明「圖 = 矩陣、圖的性質 = 矩陣的譜」這條路可行。
• 譜圖理論（Chung 1997 整理成書）：圖的 Laplacian \(\mathcal{L} = I - D^{-1/2}AD^{-1/2}\) 的特徵值刻畫連通性、社群結構、擴散行為。
• 1998 年 PageRank：Google 用隨機遊走的平穩分布（轉移矩陣的主特徵向量）給網頁排序——線性代數第一次在圖上大規模辦案，網際網路就是案發現場。
• 2012 年深度學習爆發（AlexNet），但 CNN 只會吃規則的網格（影像）；圖是不規則的：節點度不同、沒有平移不變性。如何把「卷積」推廣到圖上？
• 2013–2016 年 Scarselli（GNN 概念）、Bruna（譜卷積）、Defferrard（切比雪夫多項式）逐步逼近；2017 年 Kipf & Welling 用一階近似把譜卷積簡化成三行公式——GCN 問世。

線索與推理 -- 數學式、程式、理論#

線索一：圖 = 矩陣#

無向圖 \(G = (V, E)\) ， \(n = |V|\) ，用鄰接矩陣 \(A \in \mathbb{R}^{n\times n}\) （ \(A_{ij}=1\) 若有邊）、度矩陣 \(D = \mathrm{diag}(d_1,\dots,d_n)\) 表示。節點特徵堆成矩陣 \(X \in \mathbb{R}^{n \times f}\) 。最直覺的「圖上卷積」：

\(AH\) 的第 \(i\) 行 = 第 \(i\) 個節點所有鄰居特徵之和——訊息傳遞就是矩陣乘法。但裸的 \(A\) 有兩個毛病：沒有自環（節點看不到自己）、未歸一化（高度數節點的特徵會爆炸）。

線索二：歸一化與自環#

Kipf & Welling 的修正：加自環 \(\tilde{A} = A + I\) ，對稱歸一化用 \(\tilde{D} = \mathrm{diag}(\sum_j \tilde{A}_{ij})\) ：

對稱歸一化 \(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\) 使每條邊的權重 \(\propto 1/\sqrt{d_i d_j}\) ——類比隨機遊走的對稱化，保證譜半徑不超過 1，訓練穩定。

線索三：譜圖理論——為什麼叫「卷積」#

圖 Laplacian：

\(\mathcal{L}\) 半正定，特徵向量 \(U\) 是「圖上的 Fourier 基」。譜卷積（Bruna 2014）定義為：

但 \(U\) 是稠密矩陣，成本 \(O(n^3)\) 。Defferrard 用切比雪夫多項式 \(K\) 階截斷，Kipf & Welling 再取一階近似（ \(K=1\) 、 \(\lambda_{\max}\approx 2\) ），化簡後正是線索二的公式——GCN 是譜卷積的線性化身，深度堆疊換取感受野。

線索四：與 PageRank 的對決#

PageRank 求轉移矩陣 \(P = A^\top D^{-1}\) （近似）的主特徵向量，冪迭代 \(x_{t+1} = P^\top x_t\) 收斂到排名。GCN 的訊息傳遞其實是同款冪迭代 + 可學習權重 \(W\) + 非線性 \(\sigma\) ——PageRank 是「無參數、線性、單層」的特例，GCN 把它推廣成多層可學習的架構。隨機遊走的線索一脈相承。

程式碼範例：鄰接矩陣 \(AXW\) 訊息傳遞與兩層 GCN#

import numpy as np

np.random.seed(0)
n, f, h, c = 6, 4, 8, 3      # 6 節點, 特徵 4, 隱層 8, 類別 3

# 一個小圖：兩個三角社群 + 一座橋
A = np.zeros((n, n))
edges = [(0,1),(1,2),(0,2),(3,4),(4,5),(3,5),(2,3)]
for i, j in edges: A[i, j] = A[j, i] = 1.0

A_tilde = A + np.eye(n)                       # 加自環
D_t = np.diag(A_tilde.sum(1))
A_hat = np.linalg.inv(np.sqrt(D_t)) @ A_tilde @ np.linalg.inv(np.sqrt(D_t))  # 對稱歸一化

X = np.random.randn(n, f)                     # 節點特徵

def gcn_forward(X, W1, W2):
    H1 = np.tanh(A_hat @ X  @ W1)             # 第一層：AXW + 非線性
    H2 = A_hat @ H1 @ W2                      # 第二層
    return H2

def softmax(Z):
    e = np.exp(Z - Z.max(1, keepdims=True))
    return e / e.sum(1, keepdims=True)

W1 = np.random.randn(f, h); W2 = np.random.randn(h, c)
P = softmax(gcn_forward(X, W1, W2))

print("訊息傳遞驗證：A_hat @ X 的第 0 行 = 節點0鄰居(1,2)特徵之和的歸一化 ?")
raw = A_tilde @ X
manual = raw[0] / np.sqrt(A_tilde[0,0] * A_tilde[0,0])   # 自環對角 = 1 時簡化
print("  差異 = %.2e" % np.abs(A_hat @ X)[0].sum() , "(每行和 ≈ 0~1，對稱歸一化生效)")

print("\n節點分類機率（訓練前隨機權重）：")
for i in range(n):
    print("  node %d -> %s" % (i, np.round(P[i], 3)))

# 譜半徑檢查：對稱歸一化後譜半徑 ≤ 1，訓練不爆炸
eig = np.linalg.eigvalsh(A_hat)
print("\nA_hat 譜半徑 = %.3f  (≤ 1 ? %s)" % (np.max(np.abs(eig)), np.max(np.abs(eig)) <= 1 + 1e-12))

輸出顯示： \(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\) 的行和受控、譜半徑 \(\leq 1\) ——訊息傳遞是矩陣乘法，且歸一化保證深層堆疊不爆炸。

結案 -- 後果與影響#

• 推薦系統：Pinterest 的 PinSage（2018）、各大電商的圖協同過濾，GCN 式訊息傳遞成為工業標準。
• 分子模擬：MPNN（Gilmer 2017）、SchNet 把分子當圖，GNN 預測分子性質，2018 年後成為計算化學主力；2024 年 Nobel 化學獎的 AlphaFold 生態系中圖結構無所不在。
• 知識圖譜：實體連結、知識補全（R-GCN 2018）直接用鄰接矩陣訊息傳遞。
• 理論面：GNN 的表達能力與 WL 測試（Weisfeiler–Lehman）等價（Xu et al. 2019, GIN）；過平滑（oversmoothing）問題催生殘差連接、注意力圖網路（GAT 2018）。
• 圖基礎模型（graph foundation models）成為 2023–2024 年新戰場，訊息傳遞的線性代數内核不變。

關鍵人物與文獻#

• T. N. Kipf, M. Welling, "Semi-Supervised Classification with Graph Convolutional Networks", ICLR (2017), arXiv:1609.02907。
• J. Bruna, W. Zaremba, A. Szlam, Y. LeCun, "Spectral Networks and Locally Connected Networks on Graphs", ICLR (2014)。
• M. Defferrard, X. Bresson, P. Vandergheynst, "Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering", NeurIPS (2016)。
• L. Page, S. Brin, R. Motwani, T. Winograd, "The PageRank Citation Ranking", Stanford InfoLab (1999)。
• F. R. K. Chung, Spectral Graph Theory, AMS (1997)。