Graph Neural Networks/zh
| Article | |
|---|---|
| Topic area | deep-learning |
| Prerequisites | Neural Network, Graph Theory |
概述
圖神經網絡（GNN）是一類專為圖結構數據設計的神經網絡，其輸入由通過邊連接的節點構成，而不是規則的網格或序列。與利用圖像或文本規則拓撲結構的卷積或循環架構不同，GNN 學習的表示尊重任意的連接模式，並且對節點順序的置換保持不變。它們已成為關係結構具有信息量的問題的標準工具，包括分子性質預測、社交網絡分析、推薦系統、交通預測和知識圖譜推理。幾乎所有現代 GNN 變體背後的統一思想是消息傳遞：每個節點通過聚合來自其鄰居的信息來迭代更新其表示，從而使局部特徵能夠在圖中傳播，並產生同時捕獲節點屬性和結構上下文的嵌入。[1]
直覺與動機
圖 $ G = (V, E) $ 由節點集 $ V $、邊 $ E \subseteq V \times V $ 以及可選的附加在每個節點和邊上的特徵組成。許多現實世界的系統天然具有關係性：分子中的原子、社交網絡中的用戶、道路地圖中的交叉口，或知識圖譜中的實體。將標準的多層感知機應用於此類數據需要將圖展平為固定大小的向量，這會丟棄連接性信息。應用卷積神經網絡則需要規則網格，而圖缺乏這種結構。GNN 通過將節點嵌入計算為每個節點局部鄰域的函數來迴避這兩個問題，然後堆疊層，使每增加一層就將感受野擴展一跳。
有兩個屬性使其在實踐中可行。第一，置換等變性：重新排序節點索引會以相同的方式重新排序輸出，但不會改變其值，這是無序鄰居集合的正確對稱性。第二，局部性：節點的更新僅依賴於其直接鄰居，因此相同的參數可以在整個圖上重複使用，與圖的大小無關。這兩個屬性共同賦予 GNN 對關係數據的強歸納偏置，正如平移等變性賦予 CNN 對圖像的強偏置。
消息傳遞的形式化
占主導地位的抽象是消息傳遞神經網絡（MPNN）框架。[2] 設 $ h_v^{(l)} $ 表示節點 $ v $ 在第 $ l $ 層的嵌入，$ \mathcal{N}(v) $ 表示其鄰居。單層應用三個步驟：
$ {\displaystyle m_v^{(l+1)} = \mathrm{AGG}^{(l)}\big(\{h_u^{(l)} : u \in \mathcal{N}(v)\}\big)} $
$ {\displaystyle h_v^{(l+1)} = \mathrm{UPD}^{(l)}\big(h_v^{(l)}, m_v^{(l+1)}\big)} $
聚合函數 $ \mathrm{AGG} $ 必須是置換不變的——典型選擇包括求和、平均、最大值或注意力加權求和。更新函數 $ \mathrm{UPD} $ 通常是一個小型 MLP 或門控單元。經過 $ L $ 層之後，每個節點嵌入都包含來自其 $ L $ 跳鄰域的信息。對於圖級任務，最終的讀出會將所有節點嵌入匯集為單個向量，通常通過求和、平均或學習得到的注意力池化來完成。
常見架構
圖卷積網絡（GCN）將一層定義為鄰接矩陣的對稱歸一化，然後是線性變換和非線性：[3]
$ {\displaystyle H^{(l+1)} = \sigma\!\left(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} H^{(l)} W^{(l)}\right)} $
其中 $ \tilde{A} = A + I $ 包含自環，$ \tilde{D} $ 是其度矩陣，$ \sigma $ 是諸如 ReLU 之類的非線性函數。GCN 本質上是帶有基於度的加權的均值聚合器，可作為譜圖卷積的一階近似導出。
GraphSAGE 將全鄰域聚合替換為固定大小的採樣，從而允許在內存放不下的大圖上進行歸納學習，並能處理之前未見過的節點。[4]
圖注意力網絡（GAT）通過注意力機制為每個鄰居分配可學習的權重，使得信息量大的鄰居比信息量小的鄰居貢獻更多：[5]
$ {\displaystyle \alpha_{vu} = \mathrm{softmax}_u\!\left(\mathrm{LeakyReLU}\big(a^\top [W h_v \,\|\, W h_u]\big)\right)} $
圖同構網絡（GIN）使用求和聚合配合單射的 MLP 更新，可證明地匹配Weisfeiler-Leman 圖同構測試的判別能力，這是標準消息傳遞 GNN 所能達到的最強表達能力。[6]
訓練與推理
GNN 使用標準的基於梯度的優化器（如 Adam）配合任務特定的損失函數進行訓練：節點分類使用交叉熵，回歸使用均方誤差，鏈接預測使用對比損失或間隔損失。常見的任務範式有三類：
- 節點級：為每個節點預測標籤（例如，引文網絡中的類別）。半監督設置（僅有少量標註節點）較為典型。
- 邊級：預測兩個節點是否應該連接，用於推薦和知識圖譜補全。
- 圖級：預測整個圖的某種屬性，例如分子毒性或溶解度。
擴展到大型圖時需要謹慎。全批次訓練會將所有節點嵌入存儲在內存中，這在超過幾百萬個節點時是不可行的。常見替代方案包括鄰居採樣（GraphSAGE 風格）、子圖採樣（Cluster-GCN、GraphSAINT），以及以陳舊度換內存的歷史嵌入緩存。在推理時，當架構參數化的是局部特徵的函數而非節點身份時，GNN 是歸納的，這允許將其應用於未見過的圖。
表達能力與局限性
標準的消息傳遞GNN在區分圖方面的能力至多與 1-Weisfeiler-Leman 測試相當，這意味着存在沒有任何 MPNN 能夠區分的非同構圖。這促使了更高階的變體，例如 $ k $-WL GNN、用結構標識符增強節點特徵的子圖 GNN，以及在圖上的等變Transformer。
兩種眾所周知的病態現象影響深層 GNN：
- 過平滑：隨着深度增加，重複聚合會驅使節點嵌入趨向無法區分的值，從而損害準確率。殘差連接、歸一化和 PairNorm 風格的正則化器可以緩解這一現象，但無法完全解決。
- 過擠壓：來自遠處節點的信息會通過狹窄的瓶頸被壓縮，因此在瓶頸集較小的圖中難以捕獲長程依賴。圖重連和圖 Transformer 通過添加捷徑邊或用全局注意力取代局部消息傳遞來嘗試解決這一問題。
GNN 同樣繼承了深度學習的常見缺陷：對分布偏移敏感、依賴高質量的節點特徵，以及對圖結構的對抗擾動的魯棒性有限。
與其他模型的比較
與卷積神經網絡相比，GNN 將卷積操作推廣到了不規則域；CNN 可以視為帶有平移不變濾波器的、作用在規則網格圖上的 GNN。與循環神經網絡相比，GNN 作用於鄰居集合而非有序序列，但迭代的消息傳遞可以展開為循環計算。Transformer 與之密切相關：自注意力等價於在完全連接圖上運行的 GNN，而最新的圖 Transformer架構將局部消息傳遞與全局注意力以及結構化位置編碼相結合，以同時捕獲歸納偏置和長程依賴。
應用
GNN 在結構比絕對特徵更重要的領域取得了最先進的成果。在化學和材料科學中，它們預測分子性質、加速密度泛函理論計算，並提出合成路徑。在藥物發現中，它們對結合親和力進行評分並篩選候選分子。在推薦中，它們以生產規模建模用戶-物品交互圖。在物理學中，它們已經學會了粒子和流體動力學的模擬器。在代碼分析中，它們對抽象語法樹和數據流圖進行推理。消息傳遞抽象的多功能性，加上關係數據的普遍存在，已經使 GNN 成為現代機器學習的核心工具。