《人工智能技術(shù)基礎(chǔ)》課件 第8章 圖神經(jīng)網(wǎng)絡(luò)

人工智能技術(shù)基礎(chǔ)圖神經(jīng)網(wǎng)絡(luò)第8章圖結(jié)構(gòu)普遍存在于人類社會生活中，如人與人之間的社交網(wǎng)絡(luò)、地鐵線路及高鐵線路、互聯(lián)網(wǎng)中網(wǎng)頁間的互相鏈接、論文的引用等等，都可以用圖結(jié)構(gòu)來描述。圖神經(jīng)網(wǎng)絡(luò)（GraphNeuralNetwork，GNN）自提出以來，除了在計算機(jī)視覺、自然語言處理等領(lǐng)域應(yīng)用之外，還在物理、生物、化學(xué)、社會科學(xué)等跨學(xué)科的網(wǎng)絡(luò)分析、推薦系統(tǒng)、生物化學(xué)、交通預(yù)測等諸多領(lǐng)域應(yīng)用。8圖神經(jīng)網(wǎng)絡(luò)簡介社交網(wǎng)絡(luò)化學(xué)分子網(wǎng)絡(luò)本章在介紹圖論基礎(chǔ)與圖譜理論的基礎(chǔ)上，給出圖神經(jīng)網(wǎng)絡(luò)的基本原理和圖神經(jīng)網(wǎng)絡(luò)的分類。進(jìn)而給出幾種典型的圖卷積神經(jīng)網(wǎng)絡(luò)、圖循環(huán)神經(jīng)網(wǎng)絡(luò)、圖注意力網(wǎng)絡(luò)、圖生成網(wǎng)絡(luò)以及圖時空網(wǎng)絡(luò)等模型。8圖神經(jīng)網(wǎng)絡(luò)簡介論文引用網(wǎng)絡(luò)1.學(xué)習(xí)圖論基礎(chǔ)與圖譜理論的基本原理，理解掌握分析、構(gòu)建圖神經(jīng)網(wǎng)絡(luò)得到基本工具；2.學(xué)習(xí)圖神經(jīng)網(wǎng)絡(luò)的基本原理，掌握圖神經(jīng)網(wǎng)絡(luò)的消息傳遞、更新與聚合等基本操作，了解圖神經(jīng)網(wǎng)絡(luò)的應(yīng)用場景，包括圖分類、節(jié)點(diǎn)分類、關(guān)系預(yù)測以及去噪重建；3.學(xué)習(xí)圖神經(jīng)網(wǎng)絡(luò)的分類，了解圖卷積神經(jīng)網(wǎng)絡(luò)、圖注意力網(wǎng)絡(luò)、圖生成網(wǎng)絡(luò)以及時空圖神經(jīng)網(wǎng)絡(luò)的基本概念；4.深入學(xué)習(xí)圖卷積神經(jīng)網(wǎng)絡(luò)、圖注意力網(wǎng)絡(luò)、圖生成網(wǎng)絡(luò)以及時空圖神經(jīng)網(wǎng)絡(luò)，掌握相關(guān)圖神經(jīng)網(wǎng)絡(luò)的原理以及應(yīng)用。8圖神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)目標(biāo)目錄Contents8.1圖論基礎(chǔ)與圖譜理論圖神經(jīng)網(wǎng)絡(luò)基本原理圖神經(jīng)網(wǎng)絡(luò)分類卷積圖神經(jīng)網(wǎng)絡(luò)8.28.38.48.5圖注意力網(wǎng)絡(luò)圖生成網(wǎng)絡(luò)圖時空網(wǎng)絡(luò)本章小結(jié)8.68.78.801圖論與圖譜理論8.1圖論基礎(chǔ)與圖譜理論8.1.1圖論基礎(chǔ)——圖的定義與表示

8.1圖論基礎(chǔ)與圖譜理論8.1.1圖論基礎(chǔ)——無向圖與有向圖圖最基本的性質(zhì)之一是它是有向的還是無向的，如圖8-1所示。在一個有向圖中，每條邊都有一個方向或兩個方向。這意味著該邊沿著一個特定的方向連接兩個節(jié)點(diǎn)，其中一個節(jié)點(diǎn)是源節(jié)點(diǎn)，另一個節(jié)點(diǎn)是目的地節(jié)點(diǎn)。相比之下，無向圖有無向邊，其中的邊沒有方向。圖8-1無向圖與有向圖(a)無向圖(b)有向圖8.1圖論基礎(chǔ)與圖譜理論8.1.1圖論基礎(chǔ)——權(quán)值圖圖的另一個重要性質(zhì)是這些邊是有權(quán)重還是無權(quán)重的。在一個權(quán)值圖中，如圖8-2所示，每條邊都有一個與之相關(guān)聯(lián)的權(quán)重或代價。這些權(quán)重可以代表各種因素，如距離、旅行時間或成本。例如，在一個交通網(wǎng)絡(luò)中，邊的權(quán)重可能代表不同城市之間的距離或在它們之間旅行所花費(fèi)的時間。相比之下，無權(quán)圖沒有與其邊相關(guān)聯(lián)的權(quán)重。這些類型的圖通常用于節(jié)點(diǎn)之間的關(guān)系是二進(jìn)制的情況，而邊只是表示它們之間是否存在連接。圖8-2權(quán)值圖8.1圖論基礎(chǔ)與圖譜理論8.1.1圖論基礎(chǔ)——鄰接矩陣與關(guān)聯(lián)矩陣鄰接矩陣在n個頂點(diǎn)的圖需要有一個n×n大小的矩陣A。在一個無權(quán)圖中，矩陣坐標(biāo)中每個位置的值為1，代表兩個點(diǎn)是相連的，0表示兩點(diǎn)是不相連的；在一個有權(quán)圖中，矩陣坐標(biāo)中每個位置值代表該兩點(diǎn)之間的權(quán)重，0表示該兩點(diǎn)不相連。對于無向圖，鄰接矩陣是對稱的，而對于有向圖，矩陣不一定是對稱的。圖8-3顯示了與該無向圖關(guān)聯(lián)的鄰接矩陣。圖8-3鄰接矩陣8.1圖論基礎(chǔ)與圖譜理論8.1.1圖論基礎(chǔ)——鄰域與度矩陣

8.1圖論基礎(chǔ)與圖譜理論8.1.2譜圖理論——拉普拉斯矩陣及性質(zhì)

8.1圖論基礎(chǔ)與圖譜理論8.1.2譜圖理論——拉普拉斯矩陣及性質(zhì)

8.1圖論基礎(chǔ)與圖譜理論8.1.2譜圖理論——譜分解

8.1圖論基礎(chǔ)與圖譜理論8.1.2譜圖理論——譜分解

8.1圖論基礎(chǔ)與圖譜理論8.1.2譜圖理論——譜分解

8.1圖論基礎(chǔ)與圖譜理論8.1.2譜圖理論——譜分解

02圖神經(jīng)網(wǎng)絡(luò)基本原理8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.1圖神經(jīng)網(wǎng)絡(luò)基本操作——消息傳遞

圖8-4各個節(jié)點(diǎn)的鄰域(a)(b)(c)(d)(e)8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.1圖神經(jīng)網(wǎng)絡(luò)基本操作——消息傳遞

圖8-4各個節(jié)點(diǎn)的鄰域(a)(b)(c)(d)(e)8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.1圖神經(jīng)網(wǎng)絡(luò)基本操作——聚合

圖8-5節(jié)點(diǎn)2的聚合操作8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.1圖神經(jīng)網(wǎng)絡(luò)基本操作——更新

8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.1圖神經(jīng)網(wǎng)絡(luò)基本操作——更新

8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.1圖神經(jīng)網(wǎng)絡(luò)基本操作——更新

8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.1圖神經(jīng)網(wǎng)絡(luò)基本操作——更新

8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.1圖神經(jīng)網(wǎng)絡(luò)基本操作——更新

8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.1圖神經(jīng)網(wǎng)絡(luò)基本操作——更新(a)(b)8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.2多層GNN

圖8-7多層GNN(a)(b)(c)8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.3GNN應(yīng)用場景

圖8-8GNN分類8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.3GNN應(yīng)用場景

圖8-9GNN自編碼器8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.3GNN應(yīng)用場景

圖8-10GNN節(jié)點(diǎn)分類8.2圖神經(jīng)網(wǎng)絡(luò)基本原理8.2.3GNN應(yīng)用場景

8-11GNN鏈接預(yù)測03圖神經(jīng)網(wǎng)絡(luò)分類8.3圖神經(jīng)網(wǎng)絡(luò)分類卷積圖神經(jīng)網(wǎng)絡(luò)

8.3圖神經(jīng)網(wǎng)絡(luò)分類圖注意力網(wǎng)絡(luò)圖注意力網(wǎng)絡(luò)可以簡單理解為借助注意力模塊取代一般卷積圖神經(jīng)網(wǎng)絡(luò)中的卷積激活器。在不同的方法中，可以結(jié)合門控信息來提升注意力機(jī)制感受域的權(quán)重參數(shù)，達(dá)到更好的推理和應(yīng)用性能。圖卷積神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)了對圖結(jié)構(gòu)數(shù)據(jù)的節(jié)點(diǎn)分類，而注意力機(jī)制目前在NLP領(lǐng)域有非常好的效果和表現(xiàn)。對于圖注意力機(jī)制（GraphAttention，GAT）而言，鄰域節(jié)點(diǎn)的特征做累加求和的過程與卷積圖神經(jīng)網(wǎng)絡(luò)完全不同，通過全局注意力機(jī)制替代卷積分層傳遞的固化操作，可以有效地選擇在圖結(jié)構(gòu)中更為重要的節(jié)點(diǎn)或子圖、模型、路徑分配更大的注意力權(quán)重。8.3圖神經(jīng)網(wǎng)絡(luò)分類圖生成網(wǎng)絡(luò)圖生成網(wǎng)絡(luò)的目標(biāo)是基于一組可觀察圖來生成圖。其中的很多方法都是特定領(lǐng)域的。例如，在分子圖生成方面，一些研究將分子圖的表征建模為字符串。在NLP中，生成語義圖或知識圖通常需要一個給定的句子。近年來，研究人員又提出了一些通用方法，主要有兩個方向：一是將生成過程看成節(jié)點(diǎn)或邊的形成，另一些則使用生成對抗訓(xùn)練。該領(lǐng)域的方法主要使用卷積圖神經(jīng)網(wǎng)絡(luò)作為構(gòu)造塊。8.3圖神經(jīng)網(wǎng)絡(luò)分類時空圖神經(jīng)網(wǎng)絡(luò)

04卷積圖神經(jīng)網(wǎng)絡(luò)8.4卷積圖神經(jīng)網(wǎng)絡(luò)8.4.1基于圖譜理論的ConvGNN

8.4卷積圖神經(jīng)網(wǎng)絡(luò)8.4.1基于圖譜理論的ConvGNN

8.4卷積圖神經(jīng)網(wǎng)絡(luò)8.4.1基于圖譜理論的ConvGNN

8.4卷積圖神經(jīng)網(wǎng)絡(luò)8.4.1基于圖譜理論的ConvGNN8.4卷積圖神經(jīng)網(wǎng)絡(luò)8.4.2基于空間的ConvGNN圖像可以被認(rèn)為是一種特殊形式的圖，每個像素代表一個節(jié)點(diǎn)。每個像素都直接連接到其附近的像素，如圖8-14(a)圖所示。類似地，基于空間的圖卷積將中心節(jié)點(diǎn)的表示與其鄰域的表示進(jìn)行卷積，得到中心節(jié)點(diǎn)的更新表示，如圖8-14(b)圖所示。圖8-142D卷積與圖卷積(a)(b)8.4卷積圖神經(jīng)網(wǎng)絡(luò)8.4.2基于空間的ConvGNN

8.4卷積圖神經(jīng)網(wǎng)絡(luò)8.4.2基于空間的ConvGNNHamilton等人于2017年引入了GraphSAGE，作為用于在大型圖（具有超過100000個節(jié)點(diǎn)）上進(jìn)行歸納表示學(xué)習(xí)的框架。其目標(biāo)是為下游任務(wù)生成節(jié)點(diǎn)編碼，例如節(jié)點(diǎn)分類。此外，它還解決了GCN和GAT面臨的兩個問題——在大型圖上進(jìn)行擴(kuò)展和高效地推廣到未見數(shù)據(jù)。在GraphSAGE方法中，每個GNN層都根據(jù)它們的鄰居計算節(jié)點(diǎn)編碼。這意味著計算一個只需要這個節(jié)點(diǎn)的直接鄰居（1跳）。如果GNN有兩個GNN層，需要這些鄰居和它們自己的鄰居（2個跳），以此類推（如圖8-15所示）。網(wǎng)絡(luò)的其余部分與計算這些單個節(jié)點(diǎn)編碼無關(guān)。圖8-15以節(jié)點(diǎn)0為目標(biāo)節(jié)點(diǎn)和1跳和2跳鄰居的圖8.4卷積圖神經(jīng)網(wǎng)絡(luò)8.4.2基于空間的ConvGNN從圖8-16可以看出，需要聚合2跳鄰居，以計算1跳鄰居的。然后對這些編碼進(jìn)行聚合，以獲得節(jié)點(diǎn)0的編碼。上述方法存在兩個問題，一是計算圖相對跳數(shù)呈指數(shù)級增長，二是具有高度連接性的節(jié)點(diǎn)會創(chuàng)建出巨大的計算圖。因此在GraphSAGE中，作者提出了一種稱為鄰居采樣的技術(shù)。鄰居采樣沒有在計算圖中添加每個鄰居，而是采樣一個預(yù)定義的數(shù)量。圖8-16節(jié)點(diǎn)0的計算圖圖8-17一個具有鄰居采樣的計算圖來保持兩個1跳鄰居和兩個2跳鄰居8.4卷積圖神經(jīng)網(wǎng)絡(luò)8.4.2基于空間的ConvGNN

05圖注意力網(wǎng)絡(luò)8.5圖注意力網(wǎng)絡(luò)與GCN平等對待節(jié)點(diǎn)的所有鄰居相比，注意力機(jī)制可以為每個鄰居分配不同的注意力得分，從而識別出更重要的鄰居。將注意力機(jī)制納入圖譜神經(jīng)網(wǎng)絡(luò)的傳播步驟是很直觀的。圖注意力網(wǎng)絡(luò)也可以看作是圖卷積網(wǎng)絡(luò)家族中的一種方法。GAT背后的主要思想是，一些節(jié)點(diǎn)比其它節(jié)點(diǎn)更重要。但是圖卷積層已經(jīng)做過歸一化操作，鄰居很少的節(jié)點(diǎn)比其他節(jié)點(diǎn)更重要。這種方法是有局限的，因?yàn)樗豢紤]了節(jié)點(diǎn)的度。另一方面，圖注意力層的目標(biāo)是產(chǎn)生考慮節(jié)點(diǎn)特征重要性的加權(quán)因子，如圖8-18所示。圖8-18注意力系數(shù)計算8.5圖注意力網(wǎng)絡(luò)

8.5圖注意力網(wǎng)絡(luò)

8.5圖注意力網(wǎng)絡(luò)

8.5圖注意力網(wǎng)絡(luò)

圖8-19圖多頭注意力機(jī)制級聯(lián)/平均06圖生成網(wǎng)絡(luò)8.6圖生成網(wǎng)絡(luò)建模和生成圖是研究生物工程和社會科學(xué)網(wǎng)絡(luò)的基礎(chǔ)。圖生成網(wǎng)絡(luò)（GraphGenerativeNetwork,GGN）是一類用來生成圖數(shù)據(jù)的GNN，其使用一定的規(guī)則對節(jié)點(diǎn)和邊進(jìn)行重新組合，最終生成具有特定屬性和要求的目標(biāo)圖。因?yàn)橛行﹫D數(shù)據(jù)具有非唯一性、高維性質(zhì)，圖中邊緣之間存在復(fù)雜的非局部依賴性。因此不能假設(shè)所有的圖數(shù)據(jù)都來自同一個先驗(yàn)分布，尤其是對于異質(zhì)圖，模型在識別過程中必須具有平移不變性。GAN可以模擬圖形或生成優(yōu)化某些約束的網(wǎng)絡(luò)。后一種選擇在尋找具有特定性質(zhì)的新化合物等應(yīng)用中很方便。由于其離散性，這個問題非常龐大（超過1060種可能的組合）和復(fù)雜。8.6圖生成網(wǎng)絡(luò)由DeCao和Kipf2018年提出的MolGAN是解決這一問題的一個流行方案。它結(jié)合了WGAN和直接處理圖結(jié)構(gòu)數(shù)據(jù)的梯度懲罰和RL（強(qiáng)化學(xué)習(xí)，詳見10.4節(jié)）目標(biāo)，以生成具有所需化學(xué)性質(zhì)的分子。這個強(qiáng)化學(xué)習(xí)目標(biāo)基于深度確定性策略梯度（DDPG）算法，使用確定性策略梯度的非策略演員-評論家模型。MolGAN的體系結(jié)構(gòu)總結(jié)如圖（8-20）所示。圖8-20MolGAN結(jié)構(gòu)圖鑒別器獎勵網(wǎng)絡(luò)分子生成器8.6圖生成網(wǎng)絡(luò)

圖8-20MolGAN結(jié)構(gòu)圖鑒別器獎勵網(wǎng)絡(luò)分子生成器8.6圖生成網(wǎng)絡(luò)

圖8-20MolGAN結(jié)構(gòu)圖鑒別器獎勵網(wǎng)絡(luò)分子生成器07圖時空網(wǎng)絡(luò)8.7圖時空網(wǎng)絡(luò)空間‐時間圖神經(jīng)網(wǎng)絡(luò)（STGNNs）在捕捉圖表的動態(tài)性方面占據(jù)著重要位置。這類方法旨在對動態(tài)節(jié)點(diǎn)輸入進(jìn)行建模，同時假設(shè)相連節(jié)點(diǎn)之間存在相互依賴關(guān)系。作為解決方案，STGNN同時捕捉了圖的空間和時間依賴性。STGNN的任務(wù)可以是預(yù)測未來節(jié)點(diǎn)值或標(biāo)簽，或者預(yù)測空間-時間圖表的標(biāo)簽?，F(xiàn)有的融合神經(jīng)結(jié)構(gòu)可分為解耦和耦合神經(jīng)結(jié)構(gòu)兩類。8.7圖時空網(wǎng)絡(luò)

解耦空間-時間圖神經(jīng)網(wǎng)絡(luò)圖8-21STGCN結(jié)構(gòu)時間門卷積ST-Conv塊輸出層1維卷積時間門卷積,C=64時間門卷積,C=64空間圖卷積,C=16ST-Conv塊8.7圖時空網(wǎng)絡(luò)

解耦空間-時間圖神經(jīng)網(wǎng)絡(luò)圖8-22T-GCN結(jié)構(gòu)8.7圖時空網(wǎng)絡(luò)STGNNs中耦合神經(jīng)結(jié)構(gòu)的一個例子是DCRNN，它將GCN集成到GRU體系結(jié)構(gòu)中，如圖8-23所示。在該模型中，將LSTM中原始的線性單位替換為一個圖卷積算子，可以寫成：耦合空間-時間圖神經(jīng)網(wǎng)絡(luò)8.7圖時空網(wǎng)絡(luò)