目錄
教材版本：基於 MIT 6.7960 Fall 2024 OCW（對應 OCW Lec 05）。影片、投影片、作業全公開於 MIT OCW。本講由 Phillip Isola 授課。
圖上的資料長什麼樣
前面的架構都在處理「規則結構」：MLP 是扁平向量、CNN 是規則網格（影像）、RNN/Transformer 是序列。但很多真實資料是圖：分子（原子=節點、化學鍵=邊）、社交網路、知識圖譜、晶片佈局、交通路網。
圖的難點在於：沒有固定的輸入順序，拓撲任意。你不能像影像一樣直接 flattened 丟進 MLP——節點排列一換，特徵就亂了。
從 MLP / CNN 看 GNN
- MLP：每個樣本是獨立向量，不考慮樣本間關係。
- CNN：在固定網格上做「鄰居聚合」，權重共享 → 平移等變。
- GNN：把 CNN 的「網格鄰居」推廣成「圖鄰居」，在任意拓撲上做局部聚合。
所以 GNN 可以想成 「作用在圖上的、帶鄰居聚合的 MLP」。它保留了權重共享（每個節點用同一套更新函數），但聚合範圍由圖結構決定。
訊息傳遞（Message Passing）
主流 GNN 是**訊息傳遞神經網路（MPNN）**框架。每一層對每個節點 v：
- 收集（aggregate）：從鄰居
u ∈ N(v)收集訊息m_{uv} = MSG(h_u, h_v, e_{uv})。 - 更新（update）：
h_v' = UPD(h_v, AGG({m_{uv} : u ∈ N(v)}))。
重複 L 層，每個節點就聚合到 L 跳（hop）鄰居的資訊——這就是「感受野」隨深度擴大。下面是最小實作：
import torch
def message_pass(h, edge_index, W_msg, W_upd):
# h: [N, D] 節點特徵; edge_index: [2, E] (src, dst)
src, dst = edge_index
msg = h[src] @ W_msg.T # 鄰居訊息
agg = torch.zeros_like(h).index_add(0, dst, msg) # 按 dst 聚合
return torch.tanh((h @ W_upd.T) + agg) # 更新這段就是 GCN / GIN / GraphSAGE 的共同骨架，差別只在 MSG/AGG/UPD 的選擇。
置換等變與等變性（Permutation Equivariance / Invariance）
圖沒有自然順序，所以 GNN 必須滿足：
- 等變（equivariant）：重排節點順序後，每個節點的輸出也跟著重排 → 節點級任務（節點分類）需要這個。
- 等變（invariant）：重排後整圖輸出不變 → 圖級任務（分子是否有毒）需要這個。
這正是 GNN 的歸納偏置：它天生尊重圖的對稱性，這點和 CNN 的平移等變、Transformer 的排列等變一脈相承（見 L08）。
表達力的理論上限：Weisfeiler–Lehman
一個關鍵問題：GNN 能區分任意兩張圖嗎？
答案是不能。一階訊息傳遞 GNN 的表達力，上限就是 Weisfeiler–Lehman（WL）圖同構測試：它把節點鄰居的多重集合做雜湊迭代，若兩圖最後的雜湊多重集不同，WL 就判定「不同構」。
但 WL 自己就分不出某些非同構圖（經典的反例：兩個 1-WL 不可區分的強正則圖）。既然 GNN 的表達力 ≤ WL，它們也分不出這些圖。這是 GNN 的根本性天花板，不是訓練沒調好。
實作上的補洞方法
為了突破 WL 上限，常見做法：
- GIN（Xu et al.）：用 injective 的聚合（sum + MLP）把表達力拉到 WL 的極限。
- 位置/結構編碼：注入節點距離或游走資訊，打破對稱。
- 子圖 / 高階訊息：傳遞邊或三角形等更高階結構。
- 注意力（GAT）：用注意力權重代替固定聚合，捕捉異質鄰居。
這些都呼應一個主題：表達力不夠時，要麼加結構先驗，要麼改聚合方式——和 L13 談的歸納偏置、L12 的表示學習是同一條線。
什麼時候用 GNN
- ✅ 資料本質是關係/拓撲（分子、社交、推薦、知識圖譜）。
- ✅ 節點數可變、沒有固定柵格。
- ⚠️ 若圖很大、邊稀疏，注意鄰居爆炸與過平滑（over-smoothing，深層後所有節點特徵趨同）。
- ⚠️ 若你的「圖」其實很規則，CNN/Transformer 可能更簡單有效。
參考資料
- MIT 6.7960 OCW（Fall 2024）：課程首頁
- Kipf & Welling, Semi-Supervised Classification with Graph Convolutional Networks：arXiv:1609.02907
- Gilmer et al., Neural Message Passing for Quantum Chemistry：arXiv:1704.01212
- Xu et al., How Powerful are Graph Neural Networks (GIN)：arXiv:1810.00826
Loading...