圖神經網絡

圖神經網絡（Graph Neural Networks，簡稱GNNs）是一類專門設計用於輸入為圖的人工神經網絡。

圖神經網絡的典型應用如分子藥物設計，每個輸入樣本都是一個分子的圖表示，其中原子形成節點，原子之間的化學鍵形成邊。除了圖表示之外，輸入還包括每個原子的已知化學性質。因此，數據集樣本的長度可能不同，這反映了分子中原子數量的變化以及它們之間鍵的數量的變化。該網路的最終任務是預測給定分子在特定醫療應用中的功效，例如消除大腸桿菌（E. coli）。

GNN的關鍵設計元素是使用「成對消息傳遞（pairwise message passing）」機制，通過這種方式，圖節點通過與它們的鄰居交換資訊來迭代地更新其表示。目前已經提出了幾種GNN架構，實現了不同形式的消息傳遞，這些架構的最初形式包括遞歸或卷積構造。是否有可能定義「超越」消息傳遞的GNN架構，或者是否每個GNN都可以建立在適當定義的圖上的消息傳遞之上，仍是一個未解的開放問題。

<image>

在更廣泛的「幾何深度學習」主題中，某些現有的神經網路架構可以被解釋為在適當定義的圖上運行的GNN。在電腦視覺的背景下，一個卷積神經網絡層可以被認為是一個應用於圖的GNN，該圖的節點是像素，並且在圖中只有相鄰的像素由邊連接。在自然語言處理中，一個Transformer層可以被認為是一個應用於完全圖的GNN，該完全圖的節點是一段自然語言文本中的單詞或詞元。

GNN的相關應用領域包括自然語言處理、社交網路、引文網路、分子生物學、化學、物理學和NP-hard組合優化問題。

實現GNN的開源庫包括PyTorch Geometric（PyTorch）、TensorFlow GNN（TensorFlow）、Deep Graph Library（框架無關）、jraph（Google JAX），以及GraphNeuralNetworks.jl/GeometricFlux.jl（Julia，Flux）等。

## 架構

通用GNN的架構實現了以下基本的層：

- 排列等變（Permutation equivariant）：排列等變層將圖的表示映射為同一圖的更新表示。在文獻中，排列等變層是通過圖節點之間的成對消息傳遞來實現的。直觀地說，在消息傳遞層中，節點通過「聚合（aggregating）」從其直接鄰居接收到的「消息（messages）」來「更新（update）」其表示。因此，每個消息傳遞層都會使GNN的感受野增加一跳。
- 局部池化（Local pooling）：局部池化層通過降採樣使圖粗粒化。局部池化用於增加GNN的感受野，其方式類似於卷積神經網絡中的池化層。示例包括k-最近鄰池化、top-k池化和自注意力池化。
- 全局池化（Global pooling）：全局池化層，也稱為「讀出（readout）」層，提供整個圖的固定大小表示。全局池化層必須是排列不變的，以使圖節點和邊的排序排列不會改變最終輸出，例如逐元素求和、平均值或最大值。

事實證明，GNN的表達能力無法超越Weisfeiler-Lehman圖同構測試。在實踐中，這意味著存在GNN無法區分的不同圖結構（例如，具有相同原子但不同鍵的分子）。可以設計在更高維幾何結構（如單純復形）上運行的更強大的GNN。未來的架構是否能克服消息傳遞基元仍是一個開放的研究問題。

<image>

## 消息傳遞層

<image>

消息傳遞層是排列等變層，將圖映射為同一圖的更新表示。形式上，它們可以表示為消息傳遞神經網路（MPNN）。

令$G = (V,E)$為圖，其中$V$是節點集，$E$是邊集。令$N_u$為某個節點$u \in V$的鄰域。此外，令$\mathbf{x}_u$為節點$u \in V$的特徵，$\mathbf{e}_{uv}$為邊$(u, v) \in E$的特徵。一個MPNN層可以表示如下：

$$\mathbf{h}_u = \phi \left( \mathbf{x}_u, \bigoplus_{v \in N_u} \psi(\mathbf{x}_u, \mathbf{x}_v, \mathbf{e}_{uv}) \right)$$

其中$\phi$和$\psi$是可微函數（例如，人工神經網絡），而$\bigoplus$是一個排列不變的聚合算子，可以接受任意數量的輸入（例如，逐元素求和、平均值或最大值）。特別地，$\phi$和$\psi$分別被稱為「更新（update）」和「消息（message）」函數。直觀地說，在一個MPNN計算塊中，圖節點通過「聚合」從其鄰居接收到的「消息」來「更新」其表示。

一個或多個MPNN層的輸出是圖中每個節點$u \in V$的節點表示$\mathbf{h}_u$。節點表示可以用於任何下游任務，例如節點/圖的分類或邊預測。

MPNN中的圖節點通過聚合其直接鄰居的資訊來更新其表示。因此，堆疊$n$個MPNN層意味著一個節點將能夠與最多相距$n$「跳（hops）」的節點進行通信。原則上，為了確保每個節點都能接收到來自所有其他節點的資訊，需要堆疊數量等於圖直徑的MPNN層。然而，堆疊許多MPNN層可能會導致過度平滑（oversmoothing）和過度擠壓（oversquashing）等問題。過度平滑是指節點表示變得不可區分的問題。過度擠壓是指將長程依賴關係壓縮到固定大小的表示中而產生的瓶頸。跳躍連接（如在殘差神經網絡中）、門控更新規則和跳躍知識等對策可以緩解過度平滑。將最終層修改為全相鄰層（即通過將圖視為完全圖），可以在需要長程依賴關係的問題中緩解過度擠壓。

文獻中已經開發了其他形式的MPNN，例如圖卷積網路和圖注意力網路，它們的定義可以用MPNN形式地來表達。

### 圖卷積網路

圖卷積網路（GCN）由Thomas Kipf和馬克斯·威靈於2017年首次提出。

GCN層定義了圖上局部譜過濾的一階近似。GCN可以理解為卷積神經網絡對圖結構數據的推廣。

GCN層的形式化表達式如下：

$$\mathbf{H} = \sigma\left(\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}} \mathbf{X} \mathbf{\Theta}\right)$$

其中$\mathbf{H}$是節點表示$\mathbf{h}_u$的矩陣，$\mathbf{X}$是節點特徵$\mathbf{x}_u$的矩陣，$\sigma(\cdot)$是一個激活函數（例如ReLU），$\tilde{\mathbf{A}}$是添加了自環的圖鄰接矩陣，$\tilde{\mathbf{D}}$是添加了自環的圖度矩陣，$\mathbf{\Theta}$是可訓練參數矩陣。

特別地，令$\mathbf{A}$為圖的鄰接矩陣：那麼，可以定義$\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I}$且$\tilde{\mathbf{D}}_{ii} = \sum_{j \in V} \tilde{A}_{ij}$，其中$\mathbf{I}$表示單位矩陣。這種歸一化確保了$\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}}$的特徵值限制在$[0, 1]$範圍內，從而避免了數值不穩定性和梯度爆炸/消失問題。

GCN的一個局限性是它們不允許存在多維邊特徵$\mathbf{e}_{uv}$。然而，可以通過施加$A_{uv} = w_{uv}$來將標量權重$w_{uv}$關聯到每條邊，即通過將鄰接矩陣中的每個非零項設置為等於相應邊的權重。

### 圖注意力網路

圖注意力網路（GAT）由Petar Veličković等人於2018年提出。

圖注意力網路是GNN和注意力層的結合。在圖神經網絡中實現注意力層有助於將注意力或焦點提供給數據中的重要資訊，而不是關注整個數據。

多頭（multi-head）GAT層可以表示如下：

$$\mathbf{h}_u = \overset{K}{\underset{k=1}{\Big\Vert}} \sigma \left(\sum_{v \in N_u} \alpha_{uv}^k \mathbf{W}^k \mathbf{x}_v\right)$$

其中$K$是注意力頭的數量，$\Big\Vert$表示向量拼接，$\sigma(\cdot)$是一個激活函數（例如，ReLU），$N_{u}$是節點$u$的直接相鄰節點的集合（包括節點$u$本身），$\alpha_{uv}^k$是第$k$個注意力頭的注意力係數，$W^k$是第$k$個注意力頭的可訓練參數矩陣。

對於最終的GAT層，在應用激活函數之前，將每個注意力頭的輸出取平均值。形式上，最終的GAT層可以寫成：

$$\mathbf{h}_u = \sigma \left(\frac{1}{K}\sum_{k=1}^K \sum_{v \in N_u} \alpha_{uv}^k \mathbf{W}^k \mathbf{x}_v\right)$$

機器學習中的注意力是一種模仿認知注意力的技術。在圖學習的背景下，注意力係數$\alpha_{uv}$衡量了節點$v$對節點$u$的「重要程度」。

歸一化的注意力係數計算如下：

$$\alpha_{uv} = \frac{\exp(\text{LeakyReLU}\left(\mathbf{a}^T [\mathbf{W} \mathbf{x}_u \Vert \mathbf{W} \mathbf{x}_v \Vert \mathbf{e}_{uv}]\right))}{\sum_{z \in N_u}\exp(\text{LeakyReLU}\left(\mathbf{a}^T [\mathbf{W} \mathbf{x}_u \Vert \mathbf{W} \mathbf{x}_z \Vert \mathbf{e}_{uz}]\right))}$$

其中$\mathbf{a}$是可學習權重的向量，$\cdot^T$表示轉置，$\mathbf{e}_{uv}$是邊特徵（如果存在），$\text{LeakyReLU}$是一種修改的ReLU激活函數。然後通過softmax對注意力係數進行歸一化，使其易於在不同節點之間進行比較。

GCN可以被看作是GAT的一個特例，其中注意力係數是不可學習的，而是固定且等於邊權重$w_{uv}$。

### 門控圖序列神經網路

門控圖序列神經網路（GGS-NN）由Yujia Li等人於2015年提出。GGS-NN將Scarselli等人的GNN公式擴展為輸出序列。消息傳遞框架被實現為對門控循環單元（GRU）單元的更新規則。

GGS-NN可以表示如下：

$$\mathbf{h}_u^{(0)} = \mathbf{x}_u \, \Vert \, \mathbf{0}$$

$$\mathbf{m}_u^{(l+1)} = \sum_{v \in N_u} \mathbf{\Theta} \mathbf{h}_v$$

$$\mathbf{h}_u^{(l+1)} = \text{GRU}(\mathbf{m}_u^{(l+1)}, \mathbf{h}_u^{(l)})$$

其中$\Vert$表示向量拼接，$\mathbf{0}$是零向量，$\mathbf{\Theta}$是可學習參數矩陣，$\text{GRU}$是GRU單元，$l$表示序列索引。在GGS-NN中，節點表示被視為GRU單元的隱藏狀態。初始節點特徵$\mathbf{x}_u^{(0)}$被零填充（zero-padded）到GRU單元的隱藏狀態維度。同一個GRU單元用於更新每個節點的表示。

## 局部池化層

局部池化層通過降採樣使圖粗粒化。這裡介紹了幾種已提出的可學習局部池化策略。在這些策略中，輸入是由節點特徵矩陣$\mathbf{X}$表示的初始圖，以及圖的鄰接矩陣$\mathbf{A}$。輸出是新的節點特徵矩陣$\mathbf{X}'$，以及新的圖鄰接矩陣$\mathbf{A}'$。

### Top-k池化

首先令

$$\mathbf{y} = \frac{\mathbf{X}\mathbf{p}}{\Vert\mathbf{p}\Vert}$$

其中$\mathbf{p}$是一個可學習的投影向量。投影向量$\mathbf{p}$為每個圖節點計算一個標量投影值。

然後，top-k池化層可以如下表示：

$$\mathbf{X}' = (\mathbf{X} \odot \text{sigmoid}(\mathbf{y}))_{\mathbf{i}}$$

$$\mathbf{A}' = \mathbf{A}_{\mathbf{i}, \mathbf{i}}$$

其中$\mathbf{i} = \text{top}_k(\mathbf{y})$是具有前k個（top-k）最高投影分數的節點子集，$\odot$表示逐元素的矩陣乘法，$\text{sigmoid}(\cdot)$是S型函數。換句話說，具有前k個最高投影分數的節點保留在新的鄰接矩陣$\mathbf{A}'$中。$\text{sigmoid}(\cdot)$操作使得投影向量$\mathbf{p}$可以通過反向傳播進行訓練，否則將產生離散的輸出。

### 自注意力池化

首先令

$$\mathbf{y} = \text{GNN}(\mathbf{X}, \mathbf{A})$$

其中$\text{GNN}$是通用的排列等變GNN層（例如，GCN、GAT、MPNN）。

然後自注意力池化層可以如下表示：

$$\mathbf{X}' = (\mathbf{X} \odot \mathbf{y})_{\mathbf{i}}$$

$$\mathbf{A}' = \mathbf{A}_{\mathbf{i}, \mathbf{i}}$$

其中$\mathbf{i} = \text{top}_k(\mathbf{y})$是具有前k個最高投影分數的節點子集，$\odot$表示逐元素矩陣乘法。

自注意力池化層可以被視為top-k池化層的擴展。與top-k池化不同，在自注意力池化中計算的自注意力分數同時考慮了圖特徵和圖拓撲。

## 異配圖學習

同配性（Homophily）原則，即具有相同標籤或相似屬性的節點更有可能連接在一起，通常被認為是圖神經網絡（GNN）在圖結構數據（尤其是節點級任務）上優於傳統神經網路（NN）的主要原因。然而，最近的研究發現了一組並非微不足道的數據集，在這些數據集上，與NN相比，GNN的表現並不令人滿意。異配性（Heterophily），即低同配性，被認為是這一經驗觀察結果的主要原因。人們已經開始在各種類型的圖（例如，異構圖、時序圖和超圖）的異配性場景中重新審視和重新評估現有的大多數圖模型。此外，許多與圖相關的應用被發現與異配性問題密切相關，例如圖欺詐/異常檢測、圖對抗攻擊與魯棒性、隱私、聯邦學習和點雲分割、圖聚類、推薦系統、生成模型、鏈路預測、圖分類和著色等。在過去幾年中，人們投入了大量精力來研究和解決圖學習中的異配性問題。

## 可擴展性與分布式訓練

在大型圖上訓練GNN所面臨的計算挑戰與其他神經網路架構有很大不同。出現了兩大類問題設定：在單個超大圖（例如具有數十億節點的社交網路）上進行訓練，以及在大型個體圖的集合（例如需要高階交互建模的分子系統）上進行訓練。

對於單個大圖的設定，基於採樣的方法通過在子圖而不是全圖上進行操作來降低記憶體要求。Cluster-GCN使用圖劃分演算法將圖劃分為子圖，按順序在每個劃分上訓練模型。相比之下，GraphSAINT在訓練期間隨機採樣圖，為全圖損失構建無偏估計量。DistDGL等分布式框架將訓練擴展到多機環境，管理當圖的節點分布在多台機器上時，鄰域聚合所需的機器間通信。

對於諸如原子模擬等任務，出現了不同的瓶頸：對原子三元組或四元組之間的高階相互作用進行建模的GNN架構在單個圖級別上占用大量記憶體，使得標準的數據並行（即每個GPU處理一個單獨的樣本）在單個圖超出單設備記憶體時顯得力不從心。圖並行（Graph Parallelism）通過將單個輸入圖分布在多個GPU上，在設備之間劃分節點和邊而不是在設備之間分配樣本來解決這個問題。這種方法使得具有數億甚至數十億參數的GNN能夠在原本會超出單設備記憶體的原子系統上進行訓練，並已被應用於大規模通用原子間勢的開發中。

## 應用

### 蛋白質摺疊

圖神經網絡是AlphaFold的主要組成部分之一，這是由Google的DeepMind開發的人工智慧程序，用於解決生物學中的蛋白質摺疊問題。AlphaFold在多項CASP競賽中拔得頭籌。

### 社交網路

社交網路是GNN的一個主要應用領域，因為它們天然地表示為社交圖譜。GNN被用於開發基於社會關係和物品關係的推薦系統。

### 組合優化

GNN被用作幾種組合優化演算法的基礎構建模塊。例如，計算給定圖的最短路徑或歐拉迴路，得出優於人工設計或與之競爭的晶片布局，以及改進分支定界中專家設計的分支規則。

### 網路安全

當將電腦網絡視為圖時，可以使用GNN對其進行分析以檢測異常。溯源圖（provenance graphs）中的異常通常與網路中的惡意活動相關。GNN已被用於識別各個節點上的這些異常以及路徑內的惡意進程，或者在邊級別上檢測網路橫向移動。

### 供水管網

供水系統可以被建模為圖，因此可以直接應用GNN。此類演算法已被應用於用水需求預測，互連獨立計量區（DMA）以提高預測能力。該演算法在配水建模中的另一個應用是開發元模型（metamodels）。

### 電腦視覺

為了將圖像表示為圖結構，首先將圖像劃分為多個補丁（patches），每個補丁被視為圖中的一個節點。然後根據空間或特徵相似性，通過將每個節點連接到其最近的鄰居來形成邊。這種基於圖的表示形式能夠將圖學習模型應用於視覺任務。關係結構有助於增強特徵提取並提高圖像理解的性能。

### 文本與自然語言處理

基於圖的文本表示有助於捕捉單詞之間更深層的語義關係。許多研究使用圖網路來提高各種文本處理任務的性能，如文本分類、問答、神經機器翻譯（NMT）、事件抽取、事實核查等。

### 原子模擬與材料科學

GNN已成為在計算化學和材料科學中對原子相互作用進行建模的主要工具，在這些領域中，分子和晶體結構自然地表示為圖，其中原子作為節點，化學鍵或空間接近度作為邊。與密度泛函理論（DFT）等傳統量子化學方法相比，其主要優勢在於計算成本從O(n³)降低到O(n)，從而使得在以前不切實際的規模上進行模擬成為可能。

該領域早期的GNN架構包括SchNet（2017），它引入了連續濾波器卷積層用於在3D分子結構上進行學習，以及DimeNet（2020），它結合了原子之間的角度資訊以提高几何表達能力。隨後的等變架構（如NequIP和MACE），尊重了物理系統的旋轉和平移對稱性，在包括QM9、MD17和Materials Project在內的標準基準上實現了顯著的精度提升。

大型開放數據集推動了該領域的快速進展。Open Catalyst 2020（OC20）數據集包含超過2.6億次吸附物-催化劑表面相互作用的DFT計算，為與催化劑發現相關的能量和力預測任務建立了一個廣泛使用的基準。Materials Project和Alexandria資料庫同樣為訓練通用原子間勢提供了大規模晶體結構數據。包括OMat24和OMol25在內的最新數據集已經將覆蓋範圍擴展到了更大計算規模的有機分子和複雜材料。

這些數據集促進了通用機器學習原子間勢（MLIPs）的開發——這些模型跨越不同的化學領域進行訓練，而不是基於特定系統的數據。例子包括CHGNet、 M3GNet、 MACE-MP，以及Meta FAIR的Universal Models for Atoms（UMA），後者在涵蓋分子、材料和催化劑的約5億個原子結構上進行了訓練。由Google DeepMind開發的GNoME應用GNN來預測晶體結構的穩定性，報告稱確定了數百萬種新的穩定候選材料。