圖神經網絡

圖神經網絡（英文：graph neural network，GNN）係一種人工神經網絡，攞來處理啲數據啲可以表示成圖嘅。

基本構建塊畀圖神經網絡（GNN）。$(1)$ 執位等變𤗲。$(2)$ 局部pooling𤗲。$(3)$ 全局pooling（或者readout）𤗲。顏色表示特徵。

喺普遍嘅「幾何深度學習」主題裏頭，噻尐現有嘅神經網絡架構都可以着解釋成GNN運行喺啲圖得到適當定義過嘅。卷積神經網絡，喺背景係計算機視覺前提下可以睇作係一種 GNN，應用喺啲圖啲組成像素網格結構嘅。喺自然語言處理語境裏頭，Transformers可以睇作係作用喺完全圖上高嘅 GNN，啲綟係句子裏頭嘅單詞。

關鍵設計元素畀 GNN 係使用到成孖嘅訊息傳遞，等啲圖綟得透過交換訊息戥佢啲鄰舍來疊代更新啲嘢表示。自引入隻概念以來，已經提出有幾種嘸同嘅架構畀 GNN，實現到嘸同風格嘅訊息傳遞。截至2022年 (2022-唔見咗必要嘅參數 1=月份！)，有可能定義啲 GNN 架構「超越」訊息傳遞嘅與否，或者每隻 GNN 都建立得喺基於傳遞訊息喺適當定義嘅圖上與否，都仲係一個開放嘅研究問題。

GNN 嘅相關應用領域包括社交網絡、引文網絡、分子生物學、物理學同埋NP-hard組合優化問題。

存在有幾隻用得嘅開源庫畀實現啲圖神經網絡，例如 PyTorch Geometric （PyTorch ）、TensorFlow GNN（TensorFlow ）同埋jraph（Google JAX ）。

架構

通用嘅架構畀 GNN 裏頭有以下啲基本𤗲得到實現：

1. 執位等變：執位等變𤗲轉換隻嘢表示畀一張圖嘅轉成一隻更新過嘅表示。喺文獻裏頭，實現執位等變𤗲係透過成孖訊息傳遞喺圖綟之間嘅來。直觀來講，一𤗲訊息傳遞𤗲裏頭，綟更新隻嘢表示係透過聚合啲訊息，啲接受跟佢啲直接鄰舍來嘅。因此，每𤗲訊息傳遞𤗲都會幫 GNN 感受野增加一𨂾。
2. 局部pooling：局部pooling𤗲透過下採樣來整粗粒啲圖。局部pooling係攞來增加 GNN 嘅感受野，透過一種類似卷積神經網絡裏頭pooling𤗲嘅方式。例子包括KNN pooling、top-k pooling、與及自關注pooling。
3. 全局pooling：全局pooling𤗲，都喊做讀出𤗲，提供固定大細嘅嘢表示畀成隻圖。全局pooling𤗲必須係執位嘸變嘅，等執位畀順序畀圖綟同檠嘸會再改變隻最終輸出。例子包括元素𤗲面嘅加和、平均或者最大值。

已經有證明講 GNN 並嘸係有表現力強過 Weisfeiler-Lehman 圖同構測試。實踐裏頭，代表講存在有嘸同嘅圖結構係 GNN 嘸區分得到嘅（例如，由相同原子組成但啲鍵嘸同嘅分子）。設計出啲愈發強大嘅 GNN，啲運行喺譬如高維幾何嘢似單體複形之類嘅，又得。截至2022年 (2022-唔見咗必要嘅參數 1=月份！)，未來嘅架構克服得到訊息傳遞隻基本原理抑或冇，仲係一隻開放嘅研究問題。

GNN 嘸區分得到嘅非同構圖，出於Weisfeiler -Lehman 圖同構測試嘅限制。顏色表示啲綟特徵。

訊息傳遞層

更新綟表示喺訊息傳遞神經網絡（MPNN）層當中。綟$\mathbf {x} _{0}$接收訊息跟佢所有啲直系鄰舍$\mathbf {x} _{1}$至$\mathbf {x} _{4}$ 來。訊息得透過隻訊息函數$\phi$來計算，隻函數講明到啲特徵畀嘸單止係發送者仲有接收者嘅。

訊息傳遞層係一尐執位等變層，識捉幅圖轉換成更新過嘅表示畀隻同一幅圖嘅。形式上，啲層可以表示成訊息傳遞神經網絡（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$分別着喊做更新同埋訊息函數。直觀來講，一䊆 MPNN 計算塊裏頭，圖綟更新佢隻表示係透過聚合啲訊息跟佢啲鄰舍來嘅。

一𤗲或者多𤗲 MPNN 𤗲嘅輸出係綟嘅嘢表示 $\mathbf {h} _{u}$ 畀每粒圖裏頭嘅綟$u\in V$。綟嘅嘢表示可以用於任何下游任務，例如綟/圖分類或者檠預測。

MPNN 裏頭嘅圖綟更新佢啲嘅嘢表示係透過聚合訊息跟佢啲直接鄰舍來。因此，堆疊$n$𤗲MPNN 𤗲代表到一粒綟可以戥最多$n$「𨂾」外嘅綟通訊。原則上，為確保每粒綟都接收得到訊息跟其他綟來，需要堆疊多𤗲MPNN 𤗲等戥圖直徑相等。之但係，堆疊好多 MPNN 𤗲可能會導致諸如過度平滑（oversmoothing）同過度擠壓（oversquashing）等問題。過度平滑係指冇辦法區分得各綟嘅嘢表示。過度擠壓係指種樽頸問題，產生跟壓縮啲遠距離嘅互相依賴變成固定大細嘅嘢表示嘅。對策似skip連接（似喺殘差神經網絡裏頭嘅）、閘控嘅更新規則與及跳躍知識（jumping knowledge）等，緩解得到過度平滑。改最後一𤗲成完全相接嘅𤗲，即捉圖當成完整圖，可以減輕過度擠壓問題喺啲需要遠距離互相依賴嘅情況。

其他「風格」畀 MPNN 經已得到開發喺文獻當中，譬如圖卷積網絡、圖關注網絡，佢哋啲定義攞 MPNN 嘅形式都表示得到。

圖卷積網絡

圖卷積網絡（英文：graph convolutional network, GCN）由Thomas Kipf同Max Welling首次引入喺 2017 年。

GCN 𤗲定義了一階近似畀圖上嘅局部化嘅譜濾波器。GCNs 可以理解成卷積神經網絡得到普適化喺圖結構數據。

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} }}$係圖鄰接矩陣帶有自迴環（self-loops）嘅，${\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}$。之不過，可以關聯啲標量權重$w_{uv}$戥每個檠，透過令$A_{uv}=w_{uv}$，即透過設置每個非零項喺隻鄰接矩陣裏頭嘅設置成等於隻權重畀每條對應嘅檠。

圖關注網絡

圖關注網絡（英文：graph attention network, GAT）由Petar Veličković等人喺2018 年引入。

圖關注網絡係圖神經網絡同關注𤗲嘅組合。喺圖形神經網絡中，關注𤗲嘅實現有助於提供關注能力或者焦點畀數據裏頭嘅重要訊息，而嘸係集中喺成隻數據上。

一個多頭 GAT 𤗲可以表示成如下：

$\mathbf {h} _{u}={\overset {K}{\underset {k=1}{\Big \Vert }}}\sigma \left(\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)$

其中$K$係關注頭嘅數量，${\Big \Vert }$表示向量錔接（vector concatenation），$\sigma (\cdot )$係一個激活函數（例如ReLU ），$\alpha _{ij}$係關注係數，而$W^{k}$係矩陣畀可供訓練嘅參數畀第$k$ 隻關注頭嘅。

對於最孻嘅 GAT 𤗲，每隻關注頭嘅輸出得到做平均喺應用激活函數之前。形式上，最孻嘅 GAT 𤗲可以寫成：

$\mathbf {h} _{u}=\sigma \left({\frac {1}{K}}\sum _{k=1}^{K}\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)$

機械學習中嘅關注係一種模仿認知注意力嘅技術。喺圖學習嘅背景下，關注係數$\alpha _{uv}$衡量綟$u\in V$到綟$v\in V$ 有幾一重要。

歸一化嘅關注係數計算如下：

$\alpha _{uv}={\frac {\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {h} _{u}\Vert \mathbf {W} \mathbf {h} _{v}\Vert \mathbf {e} _{uv}]\right))}{\sum _{z\in N_{u}}\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {h} _{u}\Vert \mathbf {W} \mathbf {h} _{z}\Vert \mathbf {e} _{uz}]\right))}}$

其中$\mathbf {a}$係向量畀可供學習嘅權重，$\cdot ^{T}$表示轉置，而${\text{LeakyReLU}}$係修改後嘅 ReLU激活函數。關注係數得到歸一化，等容易比較佢哋喺嘸同綟之間。

GCN 可以睇作係 GAT 嘅一種特殊情況，其中關注係數係嘸學習得嘅，而係固定、等於檠權重$w_{uv}$嘅。

閘控圖序迾神經網絡

Yujia Li等人引入了閘控圖序迾神經網絡（英文：gated graph sequence neural network, GGS-NN）喺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 胞用於更新每粒綟嘅嘢表示。

局部pooling𤗲

局部pooling𤗲透過下採樣來整粗粒啲圖。以下呈現幾種學習得嘅局部pooling策略。對於每種情況，輸入係幅初始圖，由一隻矩陣$\mathbf {X}$畀綟特徵嘅與及隻圖鄰接矩陣$\mathbf {A}$兩者來表示。輸出係隻新矩陣$\mathbf {X} '$畀綟特徵嘅與及隻新嘅圖鄰接矩陣$\mathbf {A} '$。

Top-k pooling

首先設

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

其中$\mathbf {p}$係一個學習得嘅投影向量。投影向量$\mathbf {p}$計算標量投影值畀每粒圖綟。

跟尾可以捉 top-k pooling𤗲形式化如下：

$\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 隻最高投影分數嘅，$\odot$表示逐隻元素嘅矩陣乘法，而${\text{sigmoid}}(\cdot )$係sigmoid 函數。即係話，啲綟有排前k位最高投影分數嘅，得到保留喺新嘅鄰接矩陣$\mathbf {A} '$裏頭。隻${\text{sigmoid}}(\cdot )$操作令到投影向量$\mathbf {p}$可以透過反向傳播訓練，否則佢會產生啲離散輸出。

自關注pooling

首先設

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

其中${\text{GNN}}$係一個通用嘅執位等變 GNN 𤗲（例如，GCN、GAT、MPNN）。

跟尾可以捉自關注pooling𤗲形式化如下：

$\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$表示逐元素嘅矩陣乘法。

自關注pooling𤗲可以睇作係擴展top-k pooling 𤗲。嘸同於 top-k pooling，自關注pooling裏頭計算嘅自關注分數同時考慮埋圖特徵與及圖拓撲。

應用

蛋白質折疊

圖神經網絡係 AlphaFold 嘅主要組成部分之一，隻係由Google嘅DeepMind開發嘅人工智能程序，着攞來解決生物學中嘅蛋白質折疊問題。AlphaFold 獲得第一名喺好幾項CASP比賽當中。

社交網絡

社交網絡係 GNN 嘅主要應用領域，因為佢哋可以自然噉表示成社交圖。GNN 用於開發啲推薦系統，啲基於社會關係同埋item關係嘅。

組合優化

GNN 得用作基本嘅構建塊畀噻幾種組合優化算法。例子包括計算最短路徑或者歐拉迴路畀一幅畀定嘅圖，推導出芯片佈局係優於人工或者相當於人工解決方案嘅，以及改進Branch and Bound裏頭嘅專家設計嘅分支規則。