圖神經網絡

出自維基百科,自由嘅百科全書

圖神經網絡英文graph neural network,GNN)係一種人工神經網絡,攞來處理啲數據啲可以表示成嘅。[1][2][3]

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

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

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

GNN 嘅相關應用領域包括社交網絡[9]引文網絡[10]分子生物學[11]物理學[12]同埋NP-hard組合優化問題[13]

存在有幾隻用得嘅開源畀實現啲圖神經網絡,例如 PyTorch Geometric [14]PyTorch )、TensorFlow GNN[15]TensorFlow )同埋jraph[16]Google JAX )。

架構[編輯]

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

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

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

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

訊息傳遞𤗲[編輯]

更新綟表示喺訊息傳遞神經網絡(MPNN)𤗲當中。綟接收訊息跟佢所有啲直系鄰舍 來。訊息得透過隻訊息函數來計算,隻函數講明到啲特徵畀嘸單止係發送者仲有接收者嘅。

訊息傳遞𤗲係一尐執位等變𤗲,識捉幅圖轉換成更新過嘅表示畀隻同一幅圖嘅。形式上,啲𤗲可以表示成訊息傳遞神經網絡(MPNN)[4]

係一幅,其中係隻綟集並且係隻檠集。設係隻鄰舍畀某隻綟。另外,設係特徵畀綟 ,而係特徵畀檠。係噉一𤗲 MPNN𤗲得表示如下[4]

其中係微分得嘅函數(例如,人工神經網絡),並且係一個執位嘸變嘅聚合算子,可以接受隨便乜數量嘅輸入(例如,逐隻元素嘅總和、平均或者最大值)。特別嘅係,分別着喊做更新同埋訊息函數。直觀來講,一䊆 MPNN 計算塊裏頭,圖綟更新佢隻表示係透過聚合訊息跟佢啲鄰舍來嘅。

一𤗲或者多𤗲 MPNN 𤗲嘅輸出係綟嘅嘢表示 畀每粒圖裏頭嘅綟。綟嘅嘢表示可以用於任何下游任務,例如綟/圖分類或者檠預測。

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

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

圖卷積網絡[編輯]

圖卷積網絡(英文graph convolutional network, GCN)由Thomas Kipf同Max Welling首次引入喺 2017 年[5]

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

GCN𤗲嘅正式表達式如下:

其中係矩陣畀綟嘅嘢表示係矩陣畀綟特徵係一隻激活函數(例如ReLU),係圖鄰接矩陣帶有自迴環(self-loops)嘅,係圖次數矩陣帶有自迴環嘅,而係矩陣畀啲可供訓練嘅參數。

特別嘅係,設係隻圖鄰接矩陣:然之後,可以定義,其中表示單位矩陣。種歸一化確保到特徵值係有界嘅喺範圍內,避免到數值嘸穩定同埋梯度爆炸/消失

GCN 嘅一個限制係佢哋嘸允許多維檠特徵[5]。之不過,可以關聯啲標量權重戥每個檠,透過令,即透過設置每個非零項喺隻鄰接矩陣裏頭嘅設置成等於隻權重畀每條對應嘅檠。

圖關注網絡[編輯]

圖關注網絡(英文graph attention network, GAT)由Petar Veličković等人得引入喺2018 年[7]

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

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

其中關注頭嘅數量,表示向量錔接(vector concatenation),係一個激活函數(例如ReLU ),係關注係數,而係矩陣畀可供訓練嘅參數畀第 隻關注頭嘅。

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

機械學習中嘅關注係一種模仿認知注意力嘅技術。喺圖學習嘅背景下,關注係數衡量綟到綟 有幾一重要。

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

其中係向量畀可供學習嘅權重,表示轉置,而修改後嘅 ReLU激活函數。關注係數得到歸一化,等容易比較佢哋喺嘸同綟之間[7]

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

閘控圖序迾神經網絡[編輯]

Yujia Li等人引入了閘控圖序迾神經網絡(英文gated graph sequence neural network, GGS-NN)喺2015 年[26]。GGS-NN 擴展了 Scarselli 等人嘅 GNN 組成來做輸出序迾[1]。訊息傳遞框架着實現為一種更新規則畀閘控遞迴單位(GRU)胞。

一個 GGS-NN 可以表示如下:

其中表示向量錔接,係一個零向量,係矩陣畀可供學習嘅參數,係一個 GRU 單元,而表示序迾索引。喺 GGS-NN 裏頭,綟嘅嘢表示着當成隱狀態畀 GRU 胞。初始綟特徵着零填充(zero-padded)做到啱 GRU 胞嘅隱狀態維度。相同嘅 GRU 胞用於更新每粒綟嘅嘢表示。

局部pooling𤗲[編輯]

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

Top-k pooling[編輯]

首先設

其中係一個學習得嘅投影向量。投影向量計算標量投影值畀每粒圖綟。

跟尾可以捉 top-k pooling𤗲[17]形式化如下:

其中係子集畀啲綟,啲有前 k 隻最高投影分數嘅,表示逐隻元素嘅矩陣乘法,而sigmoid 函數。即係話,啲綟有排前k位最高投影分數嘅,得到保留喺新嘅鄰接矩陣裏頭。隻操作令到投影向量可以透過反向傳播訓練,否則佢會產生啲離散輸出[17]

自關注pooling[編輯]

首先設

其中係一個通用嘅執位等變 GNN 𤗲(例如,GCN、GAT、MPNN)。

跟尾可以捉自關注pooling𤗲[18]形式化如下:

其中係子集畀啲綟,啲有前 k 隻最高投影分數嘅,表示逐元素嘅矩陣乘法

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

應用[編輯]

蛋白質折疊[編輯]

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

社交網絡[編輯]

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

組合優化[編輯]

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

[編輯]

  1. 1.0 1.1 1.2 Scarselli, Franco; Gori, Marco; Tsoi, Ah Chung; Hagenbuchner, Markus; Monfardini, Gabriele (2009). "The Graph Neural Network Model". IEEE Transactions on Neural Networks. 20 (1): 61–80. doi:10.1109/TNN.2008.2005605. ISSN 1941-0093. PMID 19068426. S2CID 206756462.
  2. Sanchez-Lengeling, Benjamin; Reif, Emily; Pearce, Adam; Wiltschko, Alex (2021-09-02). "A Gentle Introduction to Graph Neural Networks". Distill. 6 (9): e33. doi:10.23915/distill.00033. ISSN 2476-0757.
  3. Daigavane, Ameya; Ravindran, Balaraman; Aggarwal, Gaurav (2021-09-02). "Understanding Convolutions on Graphs". Distill. 6 (9): e32. doi:10.23915/distill.00032. ISSN 2476-0757. S2CID 239678898.
  4. 4.0 4.1 4.2 4.3 4.4 4.5 4.6 Bronstein, Michael M.; Bruna, Joan; Cohen, Taco; Veličković, Petar (May 4, 2021). "Geometric Deep Learning: Grids, Groups, Graphs Geodesics and Gauges". arXiv:2104.13478 [cs.LG].
  5. 5.0 5.1 5.2 5.3 Kipf, Thomas N; Welling, Max (2016). "Semi-supervised classification with graph convolutional networks". IEEE Transactions on Neural Networks. 5 (1): 61–80. arXiv:1609.02907. doi:10.1109/TNN.2008.2005605. PMID 19068426. S2CID 206756462.
  6. 6.0 6.1 Hamilton, William; Ying, Rex; Leskovec, Jure (2017). "Inductive Representation Learning on Large Graphs" (PDF). Neural Information Processing Systems. 31. arXiv:1706.02216 –透過Stanford.
  7. 7.0 7.1 7.2 7.3 Veličković, Petar; Cucurull, Guillem; Casanova, Arantxa; Romero, Adriana; Liò, Pietro; Bengio, Yoshua (2018-02-04). "Graph Attention Networks". arXiv:1710.10903 [stat.ML].
  8. 8.0 8.1 8.2 Veličković, Petar (2022). "Message passing all the way up". arXiv:2202.11097 [cs.LG].
  9. 9.0 9.1 Ying, Rex; He, Ruining; Chen, Kaifeng; Eksombatchai, Pong; Hamilton, William L.; Leskovec, Jure (2018). Graph Convolutional Neural Networks for Web-Scale Recommender Systems. pp. 974–983. arXiv:1806.01973. doi:10.1145/3219819.3219890. ISBN 9781450355520. S2CID 46949657.
  10. "Stanford Large Network Dataset Collection". snap.stanford.edu. 喺2021-07-05搵到.
  11. Gilmer, Justin; Schoenholz, Samuel S.; Riley, Patrick F.; Vinyals, Oriol; Dahl, George E. (2017-07-17). "Neural Message Passing for Quantum Chemistry". Proceedings of Machine Learning Research (英文): 1263–1272. arXiv:1704.01212.
  12. Qasim, Shah Rukh; Kieseler, Jan; Iiyama, Yutaro; Pierini, Maurizio Pierini (2019). "Learning representations of irregular particle-detector geometry with distance-weighted graph networks". The European Physical Journal C. 79 (7). doi:10.1140/epjc/s10052-019-7113-9. S2CID 88518244.
  13. Li, Zhuwen; Chen, Qifeng; Koltun, Vladlen (2018). "Combinatorial optimization with graph convolutional networks and guided tree search". Neural Information Processing Systems. 31: 537–546. arXiv:1810.10659.
  14. Matthias, Fey; Lenssen, Jan E. (2019). "Fast Graph Representation Learning with PyTorch Geometric". arXiv:1903.02428 [cs.LG].
  15. "Tensorflow GNN". GitHub. 喺30 June 2022搵到.
  16. "jraph". GitHub. 喺30 June 2022搵到.
  17. 17.0 17.1 17.2 Gao, Hongyang; Ji, Shuiwang Ji (2019). "Graph U-Nets". arXiv:1905.05178 [cs.LG].
  18. 18.0 18.1 Lee, Junhyun; Lee, Inyeop; Kang, Jaewoo (2019). "Self-Attention Graph Pooling". arXiv:1904.08082 [cs.LG].
  19. 19.0 19.1 Liu, Chuang; Zhan, Yibing; Li, Chang; Du, Bo; Wu, Jia; Hu, Wenbin; Liu, Tongliang; Tao, Dacheng (2022). "Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities". arXiv:2204.07321 [cs.LG].
  20. Douglas, B. L. (2011-01-27). "The Weisfeiler–Lehman Method and Graph Isomorphism Testing". arXiv:1101.5211 [math.CO].
  21. Xu, Keyulu; Hu, Weihua; Leskovec, Jure; Jegelka, Stefanie (2019-02-22). "How Powerful are Graph Neural Networks?". arXiv:1810.00826 [cs.LG].
  22. Bodnar, Christian; Frasca, Fabrizio; Guang Wang, Yu; Otter, Nina; Montúfar, Guido; Liò, Pietro; Bronstein, Michael (2021). "Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks". arXiv:2103.03212 [cs.LG].
  23. Chen, Deli; Lin, Yankai; Li, Wei; Li, Peng; Zhou, Jie; Sun, Xu (2020). "Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (4): 3438–3445. arXiv:1909.03211. doi:10.1609/aaai.v34i04.5747. S2CID 202539008.
  24. 24.0 24.1 Alon, Uri; Yahav, Eran (2021). "On the Bottleneck of Graph Neural Networks and its Practical Implications". arXiv:2006.05205 [cs.LG].
  25. Xu, Keyulu; Zhang, Mozhi; Jegelka, Stephanie; Kawaguchi, Kenji (2021). "Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth". arXiv:2105.04550 [cs.LG].
  26. 26.0 26.1 26.2 Li, Yujia; Tarlow, Daniel; Brockschmidt, Mark; Zemel, Richard (2016). "Gated Graph Sequence Neural Networks". arXiv:1511.05493 [cs.LG].
  27. 27.0 27.1 Xu, Keyulu; Li, Chengtao; Tian, Yonglong; Sonobe, Tomohiro; Kawarabayashi, Ken-ichi; Jegelka, Stefanie (2018). "Representation Learning on Graphs with Jumping Knowledge Networks". arXiv:1806.03536 [cs.LG].
  28. Sample, Ian (2 December 2018). "Google's DeepMind predicts 3D shapes of proteins". The Guardian. 喺30 November 2020搵到.
  29. "DeepMind's protein-folding AI has solved a 50-year-old grand challenge of biology". MIT Technology Review (英文). 喺30 November 2020搵到.
  30. Fan, Wenqi; Ma, Yao; Li, Qing; He, Yuan; Zhao, Eric; Tang, Jiliang; Yin, Dawei (2019). Graph Neural Networks for Social Recommendation. pp. 417–426. arXiv:1902.07243. doi:10.1145/3308558.3313488. hdl:10397/81232. ISBN 9781450366748. S2CID 67769538.
  31. Cappart, Quentin; Chételat, Didier; Khalil, Elias; Lodi, Andrea; Morris, Christopher; Veličković, Petar (2021). "Combinatorial optimization and reasoning with graph neural networks". arXiv:2102.09544 [cs.LG].
  32. Mirhoseini, Azalia; Goldie, Anna; Yazgan, Mustafa; Jiang, Joe Wenjie; Songhori, Ebrahim; Wang, Shen; Lee, Young-Joon; Johnson, Eric; Pathak, Omkar; Nazi, Azade; Pak, Jiwoo; Tong, Andy; Srinivasa, Kavya; Hang, William; Tuncer, Emre; Le, Quoc V.; Laudon, James; Ho, Richard; Carpenter, Roger; Dean, Jeff (2021). "A graph placement methodology for fast chip design". Nature. 594 (7862): 207–212. doi:10.1038/s41586-021-03544-w. PMID 34108699. S2CID 235395490.
  33. Gasse, Maxime; Chételat, Didier; Ferroni, Nicola; Charlin, Laurent; Lodi, Andrea (2019). "Exact Combinatorial Optimization with Graph Convolutional Neural Networks". arXiv:1906.01629 [cs.LG].