圖同構網路（Graph Isomorphism Network）是什麼？

一種 GNN 模型，基於圖同構測試的 Weisfeiler-Lehman 算法設計，具有較強的圖判別能力。

核心概念

圖同構問題問：給定兩個圖，判斷它們的結構是否相同（無論節點標籤）。這是圖論中的經典難題。WL 算法是啟發式的檢驗方法，透過迭代哈希更新節點標籤，若在某一步兩個圖的標籤分佈不同，則判定非同構。WL 算法雖不能完全解決同構問題，但在實踐中效果很好。

GIN 將 WL 算法轉化為可微的神經網路形式。核心洞察是，WL 中的節點標籤更新相當於聚合鄰域的標籤信息。GIN 使用神經網路參數化這個聚合過程，使得訓練來區分圖結構。

運作原理

WL 算法回顧

1. 初始化：每個節點 v 的標籤 l_v^(0) 為其度數
2. 迭代更新：l_v^(k) = hash({l_v^(k-1)} ∪ {l_u^(k-1) : u ∈ N(v)})
3. 判別：若兩圖在某一步的標籤分佈不同，判定非同構

GIN 的神經網路版本

GIN 使用完全單射函數（injective function）替代哈希，使得聚合後的表示能區分不同的鄰域多重集（multiset）。具體的更新規則為：

h_v^(k+1) = MLP((1 + ε) h_v^(k) + Σ_{u∈N(v)} h_u^(k))

其中 ε 是可學習或固定的標量參數，MLP 是多層感知器（非線性變換）。

關鍵設計

1. 求和聚合：而非平均或最大值。求和能保留鄰域的「計數」信息，更適合判別複雜結構。
2. (1 + ε) 係數：保留節點自身的影響，避免過度平滑。
3. MLP：提供足夠的非線性，使得不同的多重集映射到不同的嵌入。

• 圖級別的判別：對於圖分類任務，GIN 在每層後進行層級讀出（layer-wise readout），將所有層的節點表示聚合成圖表示：

y = Concat(Readout(H^(1)), Readout(H^(2)), ..., Readout(H^(K)))

其中每層的 Readout 是求和池化。

實際應用

• 分子分類：GIN 在分子圖數據集（如 NCI1、PROTEINS）上相比其他 GNN 性能更優。利用其強大的判別能力預測分子的毒性、活性等性質。

• 蛋白質功能預測：在蛋白質結構圖上預測功能。蛋白質圖由氨基酸構成，邊代表空間相鄰性。GIN 的強判別能力適合捕捉複雜的拓撲特徵。

• 社交網路分析：在社交網路中檢測社區結構、異常行為等。GIN 能識別不同的網路拓撲模式。

• 化學反應預測：預測化學反應產物或反應類型。反應物和產物可視為圖，GIN 判別結構特徵推測反應類型。

• 知識圖譜補全：在知識圖譜上進行圖級別的推理，如預測子圖的屬性或關係。

常見誤區

• 誤區一：GIN 能完全解決圖同構問題。GIN 和 WL 演算法一樣，不能完全區分所有非同構圖（存在 WL 無法區分但直觀不同的圖），但在實踐中足夠有效。

• 誤區二：GIN 總是優於 GCN 和 GAT。GIN 在圖分類、判別任務上表現好，但在節點分類或圖數據較小的情況下，可能不如 GCN。選型應根據具體任務而定。

• 誤區三：求和聚合會導致梯度爆炸。相比平均，求和確實可能導致更大的梯度，但透過適當的正則化、層正規化（layer normalization）等可以控制。梯度爆炸不是求和聚合的必然結果。

• 誤區四：GIN 對圖大小特別敏感。雖然求和聚合理論上依賴於鄰域大小，但在實踐中，使用 MLP 的非線性變換和層級讀出能夠自動調整，GIN 對大小變化的魯棒性與其他 GNN 相近。

與相關技術的比較

• GCN：GCN 使用度歸一化的平均聚合，表現力有限（理論上等價於較弱的圖核）。GIN 使用無歸一化的求和聚合，理論上達到 WL 算法的表現力。在圖判別任務上，GIN 通常優於 GCN。

• GAT：GAT 使用注意力加權聚合，動態調整鄰域權重。GIN 的求和聚合對所有鄰域平等對待（無權重）。GAT 更靈活但表現力受限，GIN 的強判別能力在某些圖分類任務上更優。

• 圖核方法：圖核（如 WL 核、子圖核）基於圖統計特徵定義相似度。GIN 是可學習的神經網路版本，根據任務優化，泛化能力更強。

• GraphSAGE：GraphSAGE 使用採樣和聚合策略，適合大規模圖。GIN 無採樣機制，適合規模較小但結構複雜的圖。