圖神經(jīng)網(wǎng)絡(luò)作為深度學(xué)習(xí)的一大活躍領(lǐng)域，受到人工智能學(xué)家廣泛關(guān)注。由于可以將圖論和深度學(xué)習(xí)緊密融合在一起，充分利用圖上拓?fù)湫畔?，圖神經(jīng)網(wǎng)絡(luò)為解決傳統(tǒng)深度學(xué)習(xí)單純歐氏空間中分析非歐氏空間的對稱性和傳遞性提供了思路。圖神經(jīng)網(wǎng)絡(luò)的發(fā)展中，主要面臨兩大階段性挑戰(zhàn)。一方面，由于工業(yè)應(yīng)用中圖多具有大規(guī)模特點(diǎn)，圖上傳統(tǒng)k-hop消息傳遞面臨指數(shù)增長的挑戰(zhàn)，對圖神經(jīng)網(wǎng)絡(luò)獲取圖上深層拓?fù)湫畔a(chǎn)生障礙。另一方面，傳統(tǒng)圖神經(jīng)網(wǎng)絡(luò)在圖同構(gòu)測試和Weisfeiler-Lehman test仍有較大提升空間。

基于對子圖網(wǎng)絡(luò)應(yīng)用的深入研究，Meta AI Research Scientist曾涵清博士對上述兩個(gè)問題分別提出新的思考；一方面，如何在不同任務(wù)中開發(fā)子圖的不同含義，從而降低大圖上的計(jì)算瓶頸并突破原始GNN的表達(dá)能力上限。當(dāng)通過“等比例縮小”原圖得到子圖時(shí)，在子圖上訓(xùn)練的GNN可以近似大規(guī)模全圖上訓(xùn)練的GNN（基于模型的泛化能力）。由此引申出的一系列基于子圖采樣的工作大大降低了訓(xùn)練的計(jì)算/存儲成本。另一方面，當(dāng)把子圖視為原圖拓?fù)湫畔⒌脑鰪?qiáng)時(shí)，我們可以從多種角度設(shè)計(jì)全新的GNN模塊（如子圖內(nèi)以及跨子圖的消息傳遞）從而增強(qiáng)模型表達(dá)力。在經(jīng)典的圖同構(gòu)測試問題上，子圖GNN超越了理論上最強(qiáng)的全圖GNN。

展望未來，如何同時(shí)取得高效以及高表達(dá)能力仍是子圖GNN需要解決的重要問題。曾博士提供了一種思路，通過結(jié)合節(jié)點(diǎn)分類和圖分類兩個(gè)任務(wù)中的子圖GNN的核心模塊，以達(dá)到計(jì)算開銷和表達(dá)力的平衡。

一、圖神經(jīng)網(wǎng)絡(luò)基礎(chǔ)知識

首先來介紹一下傳統(tǒng)圖神經(jīng)網(wǎng)絡(luò)的概念、基本任務(wù)及面臨的挑戰(zhàn)，將子圖神經(jīng)網(wǎng)絡(luò)應(yīng)用于上述問題的基本思路，以及子圖神經(jīng)網(wǎng)絡(luò)與全圖神經(jīng)網(wǎng)絡(luò)的對比。

1、圖神經(jīng)網(wǎng)絡(luò)與圖表示學(xué)習(xí)

圖表示學(xué)習(xí)任務(wù)可分為節(jié)點(diǎn)維度的信息嵌入、邊層面的信息嵌入及圖層面的信息嵌入。在節(jié)點(diǎn)層面，根據(jù)圖的輸入，產(chǎn)生針對每個(gè)點(diǎn)嵌入。在圖層面，對節(jié)點(diǎn)嵌入信息的池化可以得到圖層面的嵌入信息。

2、子圖圖神經(jīng)網(wǎng)絡(luò)與圖神經(jīng)網(wǎng)絡(luò)

①差異：子圖差異表現(xiàn)在拓?fù)湫畔⒌墨@取、節(jié)點(diǎn)特征信息的提取、消息傳遞、池化層等方面。

②聯(lián)系：子圖作為全圖的一部分，對子圖進(jìn)行計(jì)算產(chǎn)生的信息可以應(yīng)用于全圖神經(jīng)網(wǎng)絡(luò)的計(jì)算。

3、圖神經(jīng)網(wǎng)絡(luò)現(xiàn)存問題

由于現(xiàn)實(shí)數(shù)據(jù)圖的固有特點(diǎn)，傳統(tǒng)圖神經(jīng)網(wǎng)絡(luò)在工業(yè)應(yīng)用中往往面臨多種問題，具體表現(xiàn)為可擴(kuò)展性問題和表達(dá)力問題。一方面，工業(yè)應(yīng)用中圖的節(jié)點(diǎn)數(shù)往往遠(yuǎn)大于實(shí)驗(yàn)用圖數(shù)據(jù)，由此產(chǎn)生的計(jì)算復(fù)雜度往往使得全圖神經(jīng)網(wǎng)絡(luò)難以真正被用于圖數(shù)據(jù)的計(jì)算。設(shè)計(jì)出可以用于大規(guī)模圖數(shù)據(jù)的圖神經(jīng)網(wǎng)絡(luò)，是圖神經(jīng)網(wǎng)絡(luò)亟待解決的問題。另一方面，為了區(qū)分圖數(shù)據(jù)中不同節(jié)點(diǎn)的信息，圖神經(jīng)網(wǎng)絡(luò)應(yīng)可以對不同相似節(jié)點(diǎn)產(chǎn)生不同節(jié)點(diǎn)嵌入信息。在對節(jié)點(diǎn)的分析中，傳統(tǒng)以消息傳遞為基礎(chǔ)的圖神經(jīng)網(wǎng)絡(luò)的理論上限被證明為1-WL，如何設(shè)計(jì)出高區(qū)分度的圖神經(jīng)網(wǎng)絡(luò)，也是圖神經(jīng)網(wǎng)絡(luò)面臨的挑戰(zhàn)。

4、最近的工作

下圖中列出了最近的一些工作，并標(biāo)出了每篇文章關(guān)注的重點(diǎn)。

二、子圖神經(jīng)網(wǎng)絡(luò)與可擴(kuò)展性

針對上述圖神經(jīng)網(wǎng)絡(luò)的挑戰(zhàn)，曾博士從子圖神經(jīng)網(wǎng)絡(luò)角度提出了思考。通過對經(jīng)典子圖神經(jīng)網(wǎng)絡(luò)算法GraphSIANT的分析，剖析子圖神經(jīng)網(wǎng)絡(luò)的可擴(kuò)展性方法。

1、圖訓(xùn)練：小批量訓(xùn)練

對數(shù)據(jù)容量小于原圖但保留原圖特征的子圖進(jìn)行圖神經(jīng)網(wǎng)絡(luò)計(jì)算，可以使得圖神經(jīng)網(wǎng)絡(luò)訓(xùn)練在近似原圖訓(xùn)練的同時(shí)減少計(jì)算復(fù)雜度。另外，由于子圖中消息傳遞的節(jié)點(diǎn)數(shù)小于總節(jié)點(diǎn)數(shù)，通過設(shè)定子圖節(jié)點(diǎn)數(shù)，子圖神經(jīng)網(wǎng)絡(luò)鄰居點(diǎn)數(shù)可以被限制在一定有效范圍內(nèi)，從防止鄰居節(jié)點(diǎn)指數(shù)級增長帶來計(jì)算復(fù)雜度。

2、GraphSAINT基于子圖采樣的普適圖訓(xùn)練架構(gòu)

小批量訓(xùn)練在訓(xùn)練中體現(xiàn)出的性能建立在采樣方法可以以小樣本采集到原圖結(jié)構(gòu)信息基礎(chǔ)上。如何能夠設(shè)計(jì)出可表征原圖信息的子圖采樣方法，成為小批量訓(xùn)練的關(guān)鍵問題。

曾博士提出的GraphSAINT框架，第一步，基于importance node/edge sampling、Random-walk及其變種等采樣算法，采樣子圖。第二步，利用神經(jīng)網(wǎng)絡(luò)對子圖進(jìn)行計(jì)算。GraphSAINT還加入了normalization以減小不同采樣算法之間差異帶來的影響，同時(shí)利用variance reduction增強(qiáng)對重要子圖的提取能力，以增強(qiáng)子圖采樣的整體可信度并利用隨機(jī)性采樣增加泛化能力。另外，Cluster-GNN也可視為子圖神經(jīng)網(wǎng)絡(luò)采樣的一種方案。

綜上，子圖神經(jīng)網(wǎng)絡(luò)的第一種應(yīng)用方法可概括為設(shè)計(jì)采樣方式在原圖中采樣能夠反映原圖信息的子圖，以此降低計(jì)算復(fù)雜度并對產(chǎn)生與全圖神經(jīng)網(wǎng)絡(luò)相近的計(jì)算結(jié)果。

三、子圖神經(jīng)網(wǎng)絡(luò)與表達(dá)力

傳統(tǒng)圖神經(jīng)網(wǎng)絡(luò)被證明以1-WL為表達(dá)力上限，如何設(shè)計(jì)出能夠依據(jù)圖產(chǎn)生更多信息，并以此增加圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力，也是圖神經(jīng)網(wǎng)絡(luò)亟待解決的問題。

1、圖表達(dá)力的子圖應(yīng)用

圖神經(jīng)網(wǎng)絡(luò)表達(dá)能力的評判，關(guān)鍵在于算法能否區(qū)分相似但不同的“regular graph”。在曾博士看來，當(dāng)引入子圖時(shí)，一個(gè)重要的直覺就是“regular graph的子圖不一定是regular的” –- 全局（全圖）的對成型被局部（子圖）的不對稱所打破。所以在這樣的子圖上運(yùn)行1WL（及相對應(yīng)的GNN），我們就可以區(qū)分出這兩個(gè)圖不同構(gòu)。

2、Shadow-GNN：子圖與節(jié)點(diǎn)分類

不同于GraphSAINT，在shaDow-GNN看來，每個(gè)子圖不再代表全圖的性質(zhì)，而是作為每個(gè)目標(biāo)節(jié)點(diǎn)的一個(gè)“指紋”。整體architecture如下：對每個(gè)目標(biāo)節(jié)點(diǎn)，我們在其周圍提取一個(gè)小的臨域子圖（這里“小”可以是幾億節(jié)點(diǎn)的全圖中的200個(gè)節(jié)點(diǎn)構(gòu)成的子圖，這200個(gè)節(jié)點(diǎn)可以通過Personalized PageRank score或其他方法進(jìn)行filter）；這個(gè)小的子圖可能只包含目標(biāo)節(jié)點(diǎn)的一（?。┎糠?-hop與2-hop neighbor，但是我們在這個(gè)淺層的子圖里運(yùn)用一個(gè)深層的GNN（比如5層），以保證子圖的信息能夠被模型徹底吸收提取。注意這里GNN的層數(shù)（比如5）不再直接與子圖的深度（比如2）掛鉤，所以我們說這個(gè)模型是decoupled。進(jìn)一步拓展，每個(gè)目標(biāo)節(jié)點(diǎn)可以由多個(gè)臨域子圖來描述，這樣我們就有多個(gè)GNN并行地提取subgraph embedding，最后通過ensemble得到目標(biāo)節(jié)點(diǎn)的embedding。

3、子圖神經(jīng)網(wǎng)絡(luò)與圖分類

（1）思路：傳統(tǒng)GNN的kernel是對所有直接鄰居的信息聚合，而subgraph-GNN的kernel是對整個(gè)subgraph的多層的信息聚合。

（2）Nested GNN：內(nèi)層（inner）GNN類似于shaDow-GNN的操作：對每個(gè)節(jié)點(diǎn)取一個(gè)鄰居子圖，然后對此子圖跑多層的GNN生成subgraph embedding。外層（outer）GNN對所有內(nèi)層GNN的subgraph embedding再做了一次全局的pooling，從而得到整個(gè)全圖的embedding，以此對全圖生成預(yù)測的標(biāo)簽。由于shaDow-GNN超越了1WL的表達(dá)力，Nested GNN也超越了1WL。

（3）GNN-AK：GNN-AK進(jìn)一步拓展了kernel的用法，它是Nested GNN的一種衍生模型。Nested GNN在全圖層面對所有subgraph embedding做了一次信息聚合，而GNN-AK則進(jìn)行了多次subgraph embedding的聚合。直觀來看，GNN-AK是把多個(gè)Nested GNN疊加，相當(dāng)于一個(gè)多層的Nested GNN。這樣的模型層面的拓展也帶來表達(dá)能力的提升。理論上GNN-AK也超越了1WL；GNN-AK可以區(qū)分某一些3WL不能區(qū)分的圖。如果我們對每個(gè)節(jié)點(diǎn)取一種特殊的鄰居subgraph，即k-hop subgraph，那么當(dāng)k增大時(shí)，GNN-AK的表達(dá)能力也得到提升。這說明更大的subgraph包含更多信息，進(jìn)而更能提升表達(dá)力。

（4）OSAN and ESAN:信息增強(qiáng)：OSAN的子圖集合定義為所有k個(gè)節(jié)點(diǎn)可能組成的子圖。該子圖用來生成1-WL的初始顏色（由于GNN和1WL的等價(jià)性，拓展1WL的初始顏色相當(dāng)于增強(qiáng)每個(gè)GNN節(jié)點(diǎn)的初始特征）。每個(gè)節(jié)點(diǎn)和每個(gè)k指定大小子圖匹配起來都可以生成一組初始顏色。這樣相比于原始的1-WL（每個(gè)節(jié)點(diǎn)只有一種初始顏色），OSAN的消息傳遞的信息更加豐富。并且由于k-sized subgraph包含了原圖的結(jié)構(gòu)信息，由子圖生成的新的信息也使得GNN可以提取更豐富的結(jié)構(gòu)信息。公式展示了每次WL迭代中更新顏色的過程。一式對應(yīng)原始的WL，二式對應(yīng)基于子圖的WL。下面的C（v，g）表示此處v的顏色也取決于子圖g。

表達(dá)能力方面，OSAN在增大k值時(shí)表達(dá)能力逐漸增強(qiáng)。

另一經(jīng)典應(yīng)用為ESAN：利用子圖，增加信息傳遞的種類。

與在構(gòu)建的子圖上進(jìn)行獨(dú)立的信息傳遞不同的是，ESAN增加了新的信息傳遞操作：子圖間的信息傳遞。即在不同圖同時(shí)進(jìn)行神經(jīng)網(wǎng)絡(luò)計(jì)算，并對不同子圖的同一層輸出進(jìn)行信息整合，形成“子圖間”的信息傳遞，達(dá)到豐富信息傳遞的目的。

（右圖：基于edge-deletion的子圖構(gòu)建方法：在原圖中的所有邊中刪除一條邊后得到的子圖就是ESAN的一個(gè)子圖。并展示了對原圖的多種刪除邊方法。）

四、未來展望

1、問題與解決

同一計(jì)算方法，對于可擴(kuò)展性和表達(dá)力的提升往往處于矛盾狀態(tài)：表達(dá)能力強(qiáng)的subgraph-GNN計(jì)算起來不高效。主要原因?yàn)椋孩?nbsp;GNN需要處理非常多的子圖，每個(gè)子圖大小差異巨大。②K步子圖包含的子圖數(shù)目及節(jié)點(diǎn)數(shù)隨著k的增加呈指數(shù)級增加。③node-deleted subgraph個(gè)數(shù)等于全圖的節(jié)點(diǎn)個(gè)數(shù)。曾博士給出的解決方式為進(jìn)一步采樣，即在子圖集合中采樣部分?jǐn)?shù)據(jù)用于訓(xùn)練。但是如何在進(jìn)一步采樣時(shí)減少表達(dá)能力的損失，仍需要更多的研究。

針對不同下游任務(wù)，圖神經(jīng)網(wǎng)絡(luò)面臨的挑戰(zhàn)也有所不同：圖嵌入任務(wù)多用于分子圖等小型圖數(shù)據(jù)，而節(jié)點(diǎn)分類更多用于社交網(wǎng)絡(luò)等大規(guī)模圖計(jì)算，因此需要更多精力解決圖神經(jīng)網(wǎng)絡(luò)的可擴(kuò)展性問題。

2、未來展望

展望未來，我們可以以shaDow-GNN為基本框架，結(jié)合為節(jié)點(diǎn)分類和圖分類兩種任務(wù)設(shè)計(jì)的不同的subgraphGNN，從而取得節(jié)點(diǎn)分類任務(wù)中對超巨圖的expressivity與scalability的更好的平衡。我們可以在巨大的社交網(wǎng)絡(luò)里抽取小的子圖，然后在小的子圖上運(yùn)行那些為圖分類問題設(shè)計(jì)，表達(dá)能力更高但計(jì)算成本也更高的subgraph-GNN。這樣我們既提升了shaDow-GNN的表達(dá)能力，又仍然服從模型整體復(fù)雜度的要求（相對全圖的線性復(fù)雜度；相對小的子圖的多項(xiàng)式復(fù)雜度）