本文將分圖神經(jīng)網(wǎng)絡(luò)歷史、圖神經(jīng)網(wǎng)絡(luò)的最新研究進(jìn)展和圖神經(jīng)網(wǎng)絡(luò)的應(yīng)用進(jìn)展三大部分歸納總結(jié)該課程 Theme II: Advances and Applications 部分的核心內(nèi)容。作者包括騰訊榮鈺、徐挺洋、黃俊洲，清華大學(xué)黃文炳，香港中文大學(xué)程鴻。

　　人工智能領(lǐng)域近幾年歷經(jīng)了突飛猛進(jìn)的發(fā)展。圖像、視頻、游戲博弈、自然語言處理、金融等大數(shù)據(jù)分析領(lǐng)域都實(shí)現(xiàn)了跨越式的進(jìn)步并催生了很多改變了我們?nèi)粘Ｉ畹膽?yīng)用。近段時(shí)間，圖神經(jīng)網(wǎng)絡(luò)成為了人工智能領(lǐng)域的一大研究熱點(diǎn)，尤其是在社交網(wǎng)絡(luò)、知識圖譜、化學(xué)研究、文本分析、組合優(yōu)化等領(lǐng)域，圖神經(jīng)網(wǎng)絡(luò)在發(fā)掘數(shù)據(jù)中隱含關(guān)系方面的強(qiáng)大能力能幫助我們獲得更好的數(shù)據(jù)表達(dá)，進(jìn)而能讓我們做出更好的決策。比如通過圖神經(jīng)網(wǎng)絡(luò)梳理人類社會關(guān)系網(wǎng)絡(luò)的演變，可有望幫助我們理解人類社會的底層運(yùn)作模式，進(jìn)而讓我們離理想社會更近一步。

　　在今年的計(jì)算機(jī)協(xié)會國際數(shù)據(jù)挖掘與知識發(fā)現(xiàn)大會（ACM SIGKDD，簡稱 KDD）上，圖神經(jīng)網(wǎng)絡(luò)備受研究關(guān)注的現(xiàn)狀得到了充分體現(xiàn)：粗略統(tǒng)計(jì)，今年 KDD 接收的 216 篇論文（research track）中有近 40 篇與圖神經(jīng)網(wǎng)絡(luò)相關(guān)。也因此，一場為期一天的圖神經(jīng)網(wǎng)絡(luò)相關(guān)課程得到了參會人員的重點(diǎn)關(guān)注。該聯(lián)合課程的主題為「圖深度學(xué)習(xí)：基礎(chǔ)、進(jìn)展和應(yīng)用（Deep Graph Learning: Foundations, Advances and Applications）」，由騰訊 AI Lab、清華大學(xué)、香港中文大學(xué)等機(jī)構(gòu)聯(lián)合組織，從基礎(chǔ)的圖概念一直談到了當(dāng)今最前沿的圖神經(jīng)網(wǎng)絡(luò)研究進(jìn)展。

　　本次課程分為兩個(gè)主題。本文將分圖神經(jīng)網(wǎng)絡(luò)歷史、圖神經(jīng)網(wǎng)絡(luò)的最新研究進(jìn)展和圖神經(jīng)網(wǎng)絡(luò)的應(yīng)用進(jìn)展三大部分歸納總結(jié)該課程 Theme II: Advances and Applications 部分的核心內(nèi)容，Theme I 以及更多詳細(xì)的內(nèi)容可參看課程幻燈片及相關(guān)論文：https://ai.tencent.com/ailab/ml/KDD-Deep-Graph-Learning.html

　　為了解決圖學(xué)習(xí)中的一系列具有挑戰(zhàn)性的問題， 探索圖學(xué)習(xí)應(yīng)用的邊界并在于助力公司各類與圖數(shù)據(jù)相關(guān)的業(yè)務(wù)。騰訊 AI Lab 于 2017 年下半年開始布局圖深度學(xué)習(xí)的研究，積極探索圖深度學(xué)習(xí)的應(yīng)用邊界。并且在各大機(jī)器學(xué)習(xí)數(shù)據(jù)挖掘頂級會議上發(fā)表多篇文章，涉及大圖計(jì)算，超深圖神經(jīng)網(wǎng)絡(luò)，無監(jiān)督圖學(xué)習(xí)，圖的對抗攻擊，圖的樣本學(xué)習(xí)等。在未來我們將探索圖深度學(xué)習(xí)在廣泛場景的應(yīng)用，如社交推薦，藥物研發(fā)等。使其能夠真正造福人類。

　　一 圖與圖神經(jīng)網(wǎng)絡(luò)

　　1 什么是圖？

　　漢語中的「圖」可以對應(yīng)成英語中多個(gè)不同的詞：image、picture、map 以及本文關(guān)注的 graph。圖（graph）也可稱為「關(guān)系圖」或「圖譜」，是一種可用于描述事物之間的關(guān)系的結(jié)構(gòu)。圖的基本構(gòu)成元素為頂點(diǎn)和連接頂點(diǎn)的邊。根據(jù)邊是否存在方向的性質(zhì)，還可分為有向圖和無向圖。一般而言，我們通?？蓪D表示成點(diǎn)和連接點(diǎn)的線的形式，這有助于我們更直觀地理解，如下圖所示：

　　但為便于計(jì)算機(jī)處理，我們也可用矩陣來表示圖。比如如果定義當(dāng) v_i 與 v_j 相連時(shí)，A[i,j]=1，否則 A[i,j]=0，則可將以上矩陣表示為鄰接矩陣 A：

　　圖具有很強(qiáng)的表征能力。物理學(xué)系統(tǒng)建模、蛋白質(zhì)預(yù)測、疾病分類以及許多文本和圖像處理任務(wù)都可以表示成圖結(jié)構(gòu)的數(shù)據(jù)，比如圖可用于表示文本中句子的依賴關(guān)系和圖像中事物的相對位置，也可以用于分析社交網(wǎng)絡(luò)中的信息傳播和用戶關(guān)系，還能通過分析分子之間的關(guān)聯(lián)來發(fā)現(xiàn)新藥。

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

　　近些年在大數(shù)據(jù)和硬件發(fā)展雙重助力下迎來跨越式發(fā)展的深度神經(jīng)網(wǎng)絡(luò)技術(shù)讓我們具備了分析和理解大規(guī)模圖數(shù)據(jù)的能力?？傮w而言，圖分析任務(wù)可分為節(jié)點(diǎn)分類、連接預(yù)測、聚類三類。

　　圖神經(jīng)網(wǎng)絡(luò)（GNN）就是處理圖數(shù)據(jù)的神經(jīng)網(wǎng)絡(luò)，其中有兩種值得一提的運(yùn)算操作：圖過濾 （Graph Filter, 分為基于空間的過濾和基于譜的過濾）和圖池化。其中圖過濾可細(xì)化節(jié)點(diǎn)特征，而圖池化可以從節(jié)點(diǎn)表示生成圖本身的表示。

　　一般來說，GNN 的框架在節(jié)點(diǎn)層面上由過濾層和激活構(gòu)成，而對于圖層面的任務(wù)，則由過濾層、激活和池化層組成不同的模塊后再連接而成。

　　在 GNN 的實(shí)現(xiàn)方面，目前最常用的方法是消息傳遞框架（Message Passing Framework）。簡單總結(jié)起來，該框架分為兩個(gè)步驟。

　　第一步是消息生成步驟。首先，從近鄰節(jié)點(diǎn)收集狀態(tài)數(shù)據(jù)，然后使用對應(yīng)函數(shù)生成當(dāng)前節(jié)點(diǎn)的消息。在第二步中，我們更新目標(biāo)節(jié)點(diǎn)的狀態(tài)。

　　目前大多數(shù)空間式 GNN 都可以構(gòu)建為某種消息傳遞過程，而且事實(shí)上目前大多數(shù)用于圖的深度學(xué)習(xí)工具包大都采用了這一框架，比如 Deep Graph Library 和 PyTorch Geometric。

　　3 圖神經(jīng)網(wǎng)絡(luò)的發(fā)展歷史

　　圖神經(jīng)網(wǎng)絡(luò)（GNN）并不是一個(gè)新事物，最早的 GNN 的歷史可以追溯到 1997 年，粗略總結(jié)起來，GNN 的發(fā)展過程大致可分為三個(gè)階段。

　　在第一個(gè)階段，GNN 所使用的主要方法是基于循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN）的擴(kuò)展。眾所周知，RNN 擅長處理序列數(shù)據(jù)，而反過來，序列數(shù)據(jù)則可被視為一種特殊模式的圖。因此，早期的一些工作（TNN97 / TNN08）將處理序列數(shù)據(jù)的 RNN 泛化用于樹和有向無環(huán)圖（DAG）等特殊的圖結(jié)構(gòu)。但那之后這一領(lǐng)域的發(fā)展幾乎陷入了停滯狀態(tài)。然而，在當(dāng)前這輪深度學(xué)習(xí)熱潮的帶動下，對非結(jié)構(gòu)化數(shù)據(jù)的建模和處理的研究開始廣泛涌現(xiàn)，GNN 也迎來了自己的發(fā)展契機(jī)，頂級會議上的相關(guān)論文數(shù)量也迅猛增長。

　　在第二個(gè)階段，卷積被引入到了 GNN 的工作流程中。當(dāng)用矩陣進(jìn)行表示時(shí)，圖與卷積擅長處理的圖像具有很多相似性，也因此開啟了在 GNN 中使用卷積的時(shí)代。一系列的工作將在譜空間上的圖卷積轉(zhuǎn)換為了拓?fù)淇臻g上的近似，并在此基礎(chǔ)上于 2017 年誕生了圖卷積網(wǎng)絡(luò)（GCN），其首次使用了逐層卷積來擴(kuò)展感受野，圖神經(jīng)網(wǎng)絡(luò)也由此開始了實(shí)際應(yīng)用。

　　我們現(xiàn)在正處于 GNN 發(fā)展的第三個(gè)階段。圖卷積已經(jīng)出現(xiàn)了多種變體，注意力機(jī)制已被引入 GNN 中，此外還出現(xiàn)了圖池化（Graph Pooling）技術(shù)和高階 GNN。這一階段出現(xiàn)的重要技術(shù)包括：

　　變體卷積：Lanczos 網(wǎng)絡(luò)（使用 Lanczos 算法來獲取圖拉普拉斯的低秩近似）、圖小波神經(jīng)網(wǎng)絡(luò)（使用小波變換替代傅里葉變換）、雙曲 GCN（將 GCN 構(gòu)建到雙曲空間中）。

　　注意力機(jī)制：圖注意力網(wǎng)絡(luò)（使用可學(xué)習(xí)的自注意力替換固定的聚合權(quán)重）、門控注意力網(wǎng)絡(luò)（加入了可學(xué)習(xí)的門來建模每個(gè)頭的重要度）、譜式圖注意力網(wǎng)絡(luò)（將注意力應(yīng)用于譜域中的高 / 低頻組件）。

　　圖池化：SAGE（自注意圖嵌入，在池化時(shí)使用自注意力來建模節(jié)點(diǎn)重要度）、通過圖剪切實(shí)現(xiàn)圖池化（通過圖剪切算法得到的預(yù)訓(xùn)練子圖實(shí)現(xiàn)圖池化）、可微分圖池化（DIFFPOOL，通過學(xué)習(xí)聚類分配矩陣以分層方式來聚合節(jié)點(diǎn)表征）、特征池化（EigenPooling，通過整合節(jié)點(diǎn)特征和局部結(jié)構(gòu)來獲得更好的分配矩陣）。

　　高階 GNN：高階 GNN 是指通過擴(kuò)展感受野來將高階相近度（high-order proximities）編碼到圖中。高階相近度描述的是距離更多樣的節(jié)點(diǎn)之間的關(guān)系，而不僅是近鄰節(jié)點(diǎn)之間的關(guān)系。這方面的研究工作包括 DCNN（通過把轉(zhuǎn)移矩陣的冪級數(shù)堆疊起來而將鄰接矩陣擴(kuò)展為張量，然后相互獨(dú)立地輸出節(jié)點(diǎn)嵌入和圖嵌入）、MixHop（使用了歸一化的多階鄰接矩陣，然后匯集各階的輸出，從而同時(shí)得到高階和低階的相近度）、APPNP（使用了個(gè)性化 PageRank 來為目標(biāo)節(jié)點(diǎn)構(gòu)建更好的近鄰關(guān)系）。

　　下圖簡單總結(jié)了各種 GNN 變體之間的關(guān)系：

　　二 圖神經(jīng)網(wǎng)絡(luò)的研究進(jìn)展

　　了解了 GNN 的基本知識和發(fā)展脈絡(luò)，接下來我們將踏入當(dāng)前的前沿研究領(lǐng)域，解讀近期的一些理論研究成果和設(shè)計(jì)創(chuàng)新。

　　1 圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力

　　我們知道圖在表達(dá)事物的關(guān)系方面能力非凡，但圖神經(jīng)網(wǎng)絡(luò)表達(dá)能力的極限在哪里？清華大學(xué)計(jì)算機(jī)系助理研究員、清華大學(xué)「水木學(xué)者」、騰訊「犀牛鳥訪問學(xué)者」黃文炳在課程中介紹了相關(guān)的研究進(jìn)展。

　　為了有效地評估 GNN 的表達(dá)能力，首先需要定義評估標(biāo)準(zhǔn)。目前來說，可通過三種典型任務(wù)來進(jìn)行評估：圖同構(gòu)、函數(shù)近似和圖檢測 / 優(yōu)化 / 評估。

　　對于圖同構(gòu)任務(wù)，GNN 的目標(biāo)是確定任意給定的兩個(gè)圖是否同構(gòu)。這是一個(gè)很重要的任務(wù)。對于圖分類任務(wù)而言，如果兩個(gè)圖是同構(gòu)的，則 GNN 需要為這兩個(gè)圖輸出同樣的標(biāo)簽。

　　但是，判定圖是否同構(gòu)的問題是一個(gè) NP-hard 問題，傳統(tǒng)的 Weisfeiler-Lehman（WL）測試方法除了少數(shù)圖結(jié)構(gòu)外，基本能否識別大多數(shù)圖結(jié)構(gòu)是否同構(gòu)。而 GNN 能更好地解決這一問題嗎？

　　并不一定。2019 年，Xu et al. 和 Morris et al. 已經(jīng)證明 GNN 至多做到與 WL 測試一樣強(qiáng)大。之后，Xu et al. 還進(jìn)一步證明，如果 GNN 中的聚合和讀出函數(shù)（readout function）是單射函數(shù)，則 GNN 就與 WL 測試等效。

　　對于函數(shù)近似任務(wù)，該任務(wù)的目標(biāo)是判斷 GNN 能否以任意準(zhǔn)確度近似任何基于圖的函數(shù)。因?yàn)?GNN 本身也是基于圖的某種函數(shù)，因此 GNN 在這一任務(wù)上的表現(xiàn)將能體現(xiàn)其能力。實(shí)際上，DNN 也有類似的評估任務(wù)。我們知道，只要隱藏單元足夠多，DNN 可以收斂到任何向量函數(shù)，這就是所謂的「通用近似定理」。所以我們很自然也會為 GNN 提出類似的問題。

　　Maron et al. 提出了一種架構(gòu)，對于擁有圖不變映射層（graph invariant layer）和圖等變映射層（graph equivariant layer）的 GNN，如果在一個(gè)非線性層（比如 ReLU）之后堆疊等變映射層，層層疊加，然后在最后添加圖不變映射層?？梢钥闯鲞@樣的模型能在輸入的排列方式變化時(shí)保持映射不變性。這樣的模型被稱為圖不變網(wǎng)絡(luò)（INN）。

　　INN 有多強(qiáng)大？Maron et al. 證明對于任意連續(xù)的不變式圖函數(shù)，如果某些條件成立，我們可以找到特定的 INN 參數(shù)，使其能以任意精度估計(jì)該函數(shù)。這是圖學(xué)習(xí)領(lǐng)域一大強(qiáng)有力的理論結(jié)果。對 GNN 而言，這就相當(dāng)于對 DNN 而言的通用近似定理。

　　看過了圖同構(gòu)和函數(shù)近似的近期進(jìn)展，更進(jìn)一步，這兩者之間又有何關(guān)系呢？Chen et al. 2019 證明在滿足一些條件的情況下，這兩者其實(shí)是等效的。

　　接下來，我們看看 GNN 是否有足夠的表達(dá)能力來解決更困難的任務(wù)，比如尋找圖中的最短路徑或確定圖中是否存在環(huán)。這些任務(wù)的難度很高，因?yàn)樗鼈冃枰诠?jié)點(diǎn)層面執(zhí)行很細(xì)粒度的推理。

　　Loukas 證明 GNN 能解決這些任務(wù)，他得出結(jié)論：只要 GNN 的深度和寬度足夠，而且節(jié)點(diǎn)之間具有可互相判別的屬性，則 GNN 就能完成這些任務(wù)。這里深度是指 GNN 的層數(shù)，寬度則是指隱藏單元的維度。

　　因此，總結(jié)起來，只要架構(gòu)合適，GNN 其實(shí)具有非常強(qiáng)大的表達(dá)能力；也因此，要充分發(fā)掘 GNN 的真正實(shí)力，我們還需要更多架構(gòu)方面的研究探索。

　　2 訓(xùn)練深度圖神經(jīng)網(wǎng)絡(luò)

　　前面已經(jīng)簡單提到，深度對 GNN 的能力而言是非常重要的。這一點(diǎn)在深度神經(jīng)網(wǎng)絡(luò)（DNN）上也有體現(xiàn)——更深的網(wǎng)絡(luò)往往具有強(qiáng)大的表達(dá)能力，可以說深度網(wǎng)絡(luò)就是當(dāng)前的人工智能發(fā)展熱潮的最主要驅(qū)動力之一。

　　那么，具體來說，更深度的 GNN 是否也有如此的優(yōu)勢呢？更深度的 GNN 能否像 CNN 一樣獲得更大的感受野？

　　答案當(dāng)然是肯定的。舉個(gè)例子，尋找最短路徑問題需要非常深的感受野來尋找所有可能的路徑，環(huán)檢測和子圖查找問題也都需要較大的感受野。

　　那么，我們可以怎樣增大 GNN 的感受野，使其具備更強(qiáng)大的能力呢？為此，我們需要更深或更寬的 GNN。

　　首先來看通過簡單增加深度來擴(kuò)展 GNN 的方法?？梢钥吹剑瑢τ谙聢D中的六種 GNN：GCN、GraphSAGE（進(jìn)一步改進(jìn)了池化方法）、ResGCN（使用了殘差網(wǎng)絡(luò)的思路）、JKNet（使用了 DenseNet 的思路）、IncepGCN（使用了 Inception-v3 的思路）、APPNP（借用了 PageRank 的思路），簡單增加深度并不一定能提升準(zhǔn)確度，甚至還可能出現(xiàn)相反的狀況，比如 GCN、GraphSAGE 和 ResGCN 在深度增大時(shí)準(zhǔn)確度反而顯著下降。

　　這不禁讓人疑問：增加深度能提升表達(dá)能力的根本原因是什么？又是什么原因阻礙了 GNN 的深度擴(kuò)展？

　　近期的研究找到了有礙 GNN 變得更深的三大根本原因：過平滑（over-smoothing）、過擬合（overfitting）和訓(xùn)練動態(tài)變化（training dynamics）。其中后兩者也是常見的深度學(xué)習(xí)問題，而過平滑則是圖深度學(xué)習(xí)方面特有的問題。

　　過平滑

　　首先來看過平滑。GNN 本質(zhì)上是逐層推送彼此相鄰節(jié)點(diǎn)混合的表征，因此極端地看，如果層數(shù)無限多，那么所有節(jié)點(diǎn)的表征都將收斂到一個(gè)駐點(diǎn)，這也就與輸入特征完全無關(guān)了，并會導(dǎo)致梯度消失問題。因此，過平滑的一個(gè)現(xiàn)象是模型的訓(xùn)練損失和驗(yàn)證損失都難以下降。那么，為什么會出現(xiàn)過平滑呢？

　　我們以線性 GCN 來進(jìn)行說明。首先，GCN 與平滑有何關(guān)聯(lián)？一般來說，GCN 可被視為拉普拉斯平滑（Laplacian smoothing）的一種特殊形式，如下所示：

　　這個(gè)過程意味著一個(gè)節(jié)點(diǎn)的新特征是根據(jù)其本身和相鄰節(jié)點(diǎn)的加權(quán)平均而構(gòu)建的。

　　要知道這個(gè)過平滑過程發(fā)生的位置，我們先討論一下 GCN 何時(shí)會因過平滑而失效？我們將討論三種過平滑的情況。第一種是使用線性激活時(shí)，隱變量 H_L 會收斂到一個(gè)特定的點(diǎn)。第二種是使用 ReLU 激活時(shí)，H_L 會收斂到一個(gè)特定的平面 M。第三種是使用 ReLU 加偏差時(shí)，H_L 會收斂到一個(gè)特定的子立方體 O（M, r） 的表面。

　　在使用線性激活的情況下，H_L 為什么會收斂到一個(gè)特定的點(diǎn)呢？實(shí)際上，這與 L 步隨機(jī)游走有關(guān)。一個(gè)游走器從一個(gè)節(jié)點(diǎn)游走到其一個(gè)相鄰節(jié)點(diǎn)的概率為「1 / 該節(jié)點(diǎn)的度」。經(jīng)過 L 步游走后，游走的路徑會形成一個(gè)已訪問節(jié)點(diǎn)的序列。用數(shù)學(xué)公式表示，隨機(jī)游走的過程實(shí)際上就是一個(gè)歸一化的矩陣的 L 次冪乘以初始概率。

　　然后，如果我們用一組在節(jié)點(diǎn)特征上的可學(xué)習(xí)參數(shù)替換這個(gè)初始概率，它就能轉(zhuǎn)換成一個(gè)線性的 L 層 GCN。

　　可以看出，基于隨機(jī)游走的一些結(jié)論也適用于線性 GCN，其中一項(xiàng)便是隨機(jī)游走在經(jīng)過無限多步之后會收斂到一個(gè)駐點(diǎn)。

　　詳細(xì)地說，我們首先需要進(jìn)行特征值分解，即將歸一化的鄰接矩陣分解為 n 個(gè)特征值 λ 及其對應(yīng)的特征向量 u。

　　將這個(gè)求和展開，可得到下式：

　　這個(gè)圖譜中的特征值有一個(gè)性質(zhì)。即，假設(shè)一個(gè)圖 g 包含 m 個(gè)互相連接的分量，則歸一化鄰接矩陣的特征值便由 m 個(gè)為 1 的最大特征值構(gòu)成，其余的 λ 則在 （-1,1） 的開區(qū)間中。

　　因此，當(dāng) lL 趨近無窮大時(shí)，最大的 m 項(xiàng)依然存在，因?yàn)槠?λ 等于 1。但是，其余的項(xiàng)都將被忽略，因?yàn)檫@些 λ 的 l 次冪將趨近于零。這會使得隱變量 H_L 隨網(wǎng)絡(luò)深度增長而趨近于一個(gè)特定的點(diǎn)。

　　另一方面，對于非線性的情況，H_L 將收斂到一個(gè)具有非線性激活 ReLU 的特定子空間 M。首先我們給出 M 子空間的定義：

　　則隨著層的深度增加，隱變量將越來越接近子空間 M。H_L+1 離該子空間的距離至少為：

　　要注意，λ_m+1 是鄰接矩陣中最大的非 1 特征值，s_l 則是模型參數(shù) W_l 中最大的奇異值。

　　接下來我們開始解析這個(gè)收斂公式。這個(gè)歸一化鄰接矩陣的收斂滿足這一不等式。

　　如果我們假設(shè)這個(gè)子空間的維度為 m，則 m 個(gè)最大的 λ 將位于該子空間，其余的則在 λ_m+1 的范圍內(nèi)。

　　然后，模型參數(shù) W_l 和 ReLU 的收斂分別滿足下列兩個(gè)不等式：

　　有關(guān)這些不等式的更詳細(xì)證明，請參閱 ICLR 2020 論文《Graph Neural Networks Exponentially Loss Expressive Power for Node Classification》。

　　綜合這些不等式，可得到隱變量的子空間距離沿層數(shù)變化的收斂性?？梢钥吹?，隨著層數(shù)趨近于無窮大，子空間距離將趨近于 0，因此隱變量將會收斂到子空間 M。

　　接下來是更一般的情況，使用 ReLU 加偏差的 GCN 又如何呢？H_L 將收斂到一個(gè)特定子立方體 O（M,r） 的表面上。首先，我們寫出帶偏差的 GCN 的公式：

　　很顯然，由于 b_l 到子空間的距離是一個(gè)常量，因此其收斂性就滿足：

　　可以看到，當(dāng) l 趨近無窮大時(shí)，不等式右側(cè)部分就是一個(gè)無窮等比序列的和：

　　因此，可以看到 H_L 將趨近于一個(gè)子立方體的表面，其與子空間 M 的距離為 r，而 r 就等于上式。

　　總結(jié)一下，通過分析上面三種來自不同場景的情況，可以發(fā)現(xiàn)這三種情況之下存在一種普適的公式。我們可用以下不等式統(tǒng)一過平滑的情況：

　　然后通過不同的 v 和 r 取值，我們可以得到不同的具體情況：

　　過擬合和訓(xùn)練動態(tài)變化

　　接下來我們看看過擬合問題。過擬合是深度學(xué)習(xí)的一個(gè)常見問題，當(dāng)數(shù)據(jù)點(diǎn)數(shù)量少而參數(shù)數(shù)量很多時(shí)，就會出現(xiàn)這種情況。此時(shí)模型會與訓(xùn)練數(shù)據(jù)完全擬合（本質(zhì)上就是記住了數(shù)據(jù)），而在驗(yàn)證數(shù)據(jù)上表現(xiàn)很差。

　　訓(xùn)練動態(tài)變化也是深度學(xué)習(xí)領(lǐng)域的一大常見問題。根據(jù)鏈?zhǔn)椒▌t，當(dāng)模型變深時(shí)，s_l-1 乘以 λ_m+1 的結(jié)果小于 1，會出現(xiàn)梯度消失問題。如果我們將 RGB 色彩作為以下的圖的節(jié)點(diǎn)特征，可以看到當(dāng)層數(shù)達(dá)到 500 時(shí)，這些特征的梯度降為了 0，節(jié)點(diǎn)都變成了黑色，即 RGB=[0, 0, 0]。

　　過擬合和訓(xùn)練動態(tài)變化是深度學(xué)習(xí)的常見問題，這里便不過多贅述了。下面我們看看在解決過平滑問題方面有什么研究進(jìn)展。

　　如何解決過平滑問題？

　　首先，如何量化平滑？以 GCN 為例，我們先定義一個(gè) ε- 平滑，使得對于任意大于特定層 L 的 l，隱變量 H_l 的子空間距離將小于 ε：

　　然后，將 ε- 平滑層定義為能讓 H_l 的子空間距離小于 ε 的最小層。但是，ε- 平滑層是很難推導(dǎo)的。因此，我們?nèi)∫粋€(gè)松弛化的 ε- 平滑層作為上界。這個(gè)松弛化的 ε- 平滑層的公式如下：

　　用層量化了平滑之后，我們就可以想辦法來緩解過平滑問題了。

　　注意這里的 λ_m+1 與鄰接矩陣相關(guān)，s_max 與模型權(quán)重相關(guān)，這也暗示了存在兩個(gè)緩解過平滑問題的方向。

　　第一，我們可以通過處理鄰接矩陣來緩解過平滑，即增大 λ_m+1，進(jìn)而使得松弛化的 ε- 平滑層增大：

　　那么我們?nèi)绾巫龅竭@一點(diǎn)呢？很簡單，在每 epoch 都丟棄一些邊即可。研究證明，當(dāng)丟棄一些邊時(shí)，圖上信息的傳播速度會下降，子空間的維度會隨連接的分量的增多而增加。丟棄邊后的這兩個(gè)現(xiàn)象都有助于緩解過平滑問題。

　　更多詳情和實(shí)驗(yàn)論證可見騰訊 AI Lab 的 ICLR 2020 論文《DropEdge: Towards Deep Graph Convolutional Networks on Node Classification》。

　　第二，我們可以通過調(diào)整模型權(quán)重來緩解過平滑。為了增大 s_max，我們可以增大初始 W_ls 的值。下圖展示了這種方法的效果。詳見 ICLR 2020 論文《Graph Neural Networks Exponentially Lose Expressive Power for Node Classification》。

　　其它問題的解決方案

　　ICLR 2020 上還有一篇論文《PairNorm: Tackling Oversmoothing in GNNs》提出了一種用于解決訓(xùn)練動態(tài)變化問題的方法。

　　PairNorm 的思路對 GCN 輸出進(jìn)行居中和重新縮放或歸一化，使得總的兩兩平方距離保持不變。如圖所示，GCN 的輸出點(diǎn)在圖卷積之后通常會更接近彼此。但通過使用 PairNorm，新輸出的兩兩距離能與輸入的距離保持相似。

　　另一種克服訓(xùn)練動態(tài)變化的方法是在結(jié)構(gòu)中添加捷徑。JKNet、IncepGCN 和 APPNP 等 GNN 能在深度結(jié)構(gòu)中保持性能的方法就是如此。

　　因?yàn)檫@三個(gè)模型全都包含通過聚合層到終點(diǎn)的捷徑，因此淺的信息可以傳播到最后的層，也因此這些模型實(shí)際上仍舊是「淺模型」。

　　順便一提，這些不同的 GNN 結(jié)構(gòu)仍然滿足過平滑的一般情況：

　　詳細(xì)的分析請參考論文：《Tackling Over-Smoothing for General Graph Convolutional Networks》（https://arxiv.org/pdf/2008.09864.pdf）?？偨Y(jié)一下，在這些新的理論進(jìn)展的幫助下，訓(xùn)練更深度 GNN 的問題已經(jīng)得到了初步解答。

　　3 大規(guī)模圖神經(jīng)網(wǎng)絡(luò)

　　真實(shí)世界的圖可能具有非常大的規(guī)模，因此讓 GNN 有能力處理大規(guī)模圖是非常重要的研究課題。

　　基本的 GNN 通常無法處理大規(guī)模圖，因?yàn)槠渫ǔo法滿足巨大的內(nèi)存需求，而且梯度更新的效率也很低。

　　為了讓 GNN 有能力處理大規(guī)模圖，研究者已經(jīng)提出了三種不同的采樣范式：基于節(jié)點(diǎn)的采樣、基于層的采樣和基于子圖的采樣。

　　其中，逐節(jié)點(diǎn)采樣是根據(jù)目標(biāo)節(jié)點(diǎn)執(zhí)行采樣，而逐層采樣是基于卷積層來執(zhí)行采樣，逐圖采樣則是從原圖采樣子圖，然后使用子圖進(jìn)行模型推理。

　　根據(jù)這三種范式，可以知道為了實(shí)現(xiàn)大規(guī)模 GNN，我們需要解決兩個(gè)問題：如何設(shè)計(jì)高效的采樣算法？如何保證采樣質(zhì)量？

　　近些年在構(gòu)建大規(guī)模 GNN 方面已經(jīng)出現(xiàn)了一些成果，下圖給出了這些成果的時(shí)間線：

　　接下來我們將按這一時(shí)間線簡要介紹這些研究成果。

　　首先來看 GraphSAGE，其可被視為原始 GCN 的一種擴(kuò)展：在 GCN 的平均聚合器的基礎(chǔ)上增加了許多廣義上的聚合器，包括池化聚合器和 LSTM 聚合器。不同的聚合器也會對模型產(chǎn)生不同的影響。此外，在聚合之后，不同于 GCN 使用的求和函數(shù)，GraphSAGE 使用了連接函數(shù)來結(jié)合目標(biāo)節(jié)點(diǎn)機(jī)器鄰近節(jié)點(diǎn)的信息。這兩大改進(jìn)是基于對 GCN 的空間理解得到的。

　　為了實(shí)現(xiàn)大規(guī)模 GNN，GraphSAGE 首先采用了 mini-batch 的訓(xùn)練方法，這樣可以降低訓(xùn)練期間的通信成本。在每次迭代中，僅會考慮用于計(jì)算表征的節(jié)點(diǎn)。但是，mini-batch 訓(xùn)練可能出現(xiàn)鄰近節(jié)點(diǎn)擴(kuò)張的問題，使得 mini-batch 在層數(shù)較多時(shí)需要采用圖的大部分乃至全部節(jié)點(diǎn)！

　　為了解決這一問題并進(jìn)一步提升性能，GraphSAGE 采用了固定采樣個(gè)數(shù)的的鄰近采樣方法，即每層都采樣固定大小的鄰近節(jié)點(diǎn)集合。

　　從上右圖可以看到，采用固定采樣個(gè)數(shù)的采樣方法后，采樣節(jié)點(diǎn)的數(shù)量降低了。當(dāng)圖的規(guī)模很大時(shí)，這一差距會更加顯著。不過，GraphSAGE 在網(wǎng)絡(luò)層數(shù)較大時(shí)依然無法避免鄰近節(jié)點(diǎn)擴(kuò)張問題，采樣質(zhì)量上也無法得到保證。

　　為了進(jìn)一步降低采樣規(guī)模和得到一些理論上的質(zhì)量保證，VR-GCN 整合了基于控制變量的估計(jì)器（CV 采樣器）。其可以維持歷史隱藏嵌入（historical hidden embedding）來獲得更好的估計(jì)，這個(gè)歷史隱藏嵌入可用于降低方差，進(jìn)而消除方差，實(shí)現(xiàn)更小的采樣規(guī)模。VR-GCN 的數(shù)學(xué)形式如下：

　　不過，VR-GCN 也有一個(gè)缺點(diǎn)：需要額外的內(nèi)存來存儲所有的歷史隱藏嵌入，這使得我們難以實(shí)現(xiàn)大規(guī)模擴(kuò)展。

　　上面我們可以看到，基于節(jié)點(diǎn)的采樣方法并不能徹底解決鄰近節(jié)點(diǎn)擴(kuò)張問題。接下來看基于層的采樣方法。

　　FastGCN 提出從 Functional generalization 的角度來理解 GCN，并為 GCN 給出了基于層的估計(jì)形式：

　　基于此，我們可以在每層都采樣固定數(shù)量的節(jié)點(diǎn)。更進(jìn)一步，F(xiàn)astGCN 還提出了基于重要度的采樣模式，從而降低方差。在采樣過程中，每一層的采樣都是相互獨(dú)立的，而且每一層的節(jié)點(diǎn)采樣概率也保持一致。下圖是 GCN 與 FastGCN 的對比：

　　可以看出，F(xiàn)astGCN 的計(jì)算成本顯著更低，而且研究表明，這種采樣模式從期望上并不會丟失太多信息，因?yàn)槠湓趫?zhí)行重要度采樣時(shí)會進(jìn)行隨機(jī)化處理，通過足夠多 epoch 的訓(xùn)練，每個(gè)節(jié)點(diǎn)和鏈接都有期望被采樣。

　　可以看出，基于層采樣的 FastGCN 徹底解決了鄰近節(jié)點(diǎn)擴(kuò)張問題，而且采樣方法有質(zhì)量保證。但是該方法的缺點(diǎn)是無法獲得層之間的相關(guān)性，模型的表現(xiàn)也可能受到負(fù)面影響。

　　為了更好地獲得層之間的相關(guān)性，ASGCN 提出了自適應(yīng)層式采樣方法，即根據(jù)高層采樣結(jié)果動態(tài)調(diào)整更低層的采樣概率。如下左圖所示，在對底層采樣的時(shí)候 ASGCN 會考慮采樣高層采樣的鄰居節(jié)點(diǎn)，使得層之間的相關(guān)性得到很好的保留。如下右圖所示，整個(gè)采樣過程是自上而下的。我們首先采樣輸出層的目標(biāo)節(jié)點(diǎn)，然后根據(jù)其采樣結(jié)果采樣中間層的節(jié)點(diǎn)，然后重復(fù)這個(gè)過程直到輸入層。在采樣過程中，每層采樣節(jié)點(diǎn)的數(shù)目也會保持一個(gè)固定值。

　　另外，為了降低采樣方差，ASGCN 還引入了顯式方差下降法（explicit variance reduction），以優(yōu)化損失函數(shù)中的采樣方差。

　　總體來說，ASGCN 能獲得更好的性能，方差控制也更好，但由于采樣過程有額外的層間依賴關(guān)系需要考慮，采樣效率會受到一些影響。

　　接下來出現(xiàn)了基于子圖的采樣方法。ClusterGCN 首先使用圖分割算法將圖分解為更小的聚子圖，然后在子圖層面上組成隨機(jī)的分批，再將其輸入 GNN 模型，從而降單次計(jì)算需求。

　　通過限制子圖的大小，這種方法也可以有效避免鄰近節(jié)點(diǎn)擴(kuò)張問題，因?yàn)樵诿恳粚又校蓸拥姆秶疾粫^聚類子圖。

　　不過，ClusterGCN 的論文并沒有對這種方法的采樣質(zhì)量進(jìn)行實(shí)證研究。

　　GraphSAINT 則并未在采樣過程中使用聚類算法（這會引入額外的偏差和噪聲），而是直接通過子圖采樣器來采樣用于 mini-batch 訓(xùn)練的子圖。其給出了三種采樣器的構(gòu)建方式，分別為基于節(jié)點(diǎn)的采樣、基于邊的采樣和隨機(jī)游走采樣，如下所示：

　　GraphSAINT 還從理論上分析了控制采樣器的偏差和方差的方法，其中包括用于消除采樣偏差的損失歸一化和聚合歸一化方法：

　　另外，該論文還提出通過調(diào)整邊采樣概率來降低采樣方差。作為當(dāng)前最佳的方法，GraphSAINT 的表現(xiàn)也在實(shí)驗(yàn)中得到了證明。具體詳情請瀏覽 ICLR 2020 論文《GraphSAINT: Graph Sampling Based Inductive Learning Method》。

　　很顯然，大規(guī)模圖神經(jīng)網(wǎng)絡(luò)方面還有很大的進(jìn)一步研究空間，比如更高效的采樣技術(shù)、適用于異構(gòu)圖或動態(tài)圖的架構(gòu)等等。

　　4 圖神經(jīng)網(wǎng)絡(luò)的自監(jiān)督 / 無監(jiān)督學(xué)習(xí)

　　前面討論的 GNN 的表達(dá)能力、深度和規(guī)模都是基于監(jiān)督式方法，也就是說我們有輸入圖的標(biāo)簽。但在現(xiàn)實(shí)生活中，獲取這些標(biāo)簽卻并非易事。比如在分子屬性預(yù)測任務(wù)中，為了獲取基本真值標(biāo)簽，我們必需專業(yè)人士的協(xié)助。此外，訓(xùn)練任務(wù)與測試任務(wù)并不總是一致的，比如對于社交網(wǎng)絡(luò)推薦任務(wù)，我們可能在訓(xùn)練中使用的是節(jié)點(diǎn)用戶購買商品的數(shù)據(jù)，但我們卻想知道節(jié)點(diǎn)用戶是否想看某部電影，此時(shí)訓(xùn)練標(biāo)簽可能對測試就毫無作用了。因此，我們需要研究如何在沒有標(biāo)簽的情況下訓(xùn)練 GNN。

　　目前在自監(jiān)督圖學(xué)習(xí)方面已經(jīng)有一些研究成果了。我們可以根據(jù)它們的機(jī)制將其分為兩大類別：預(yù)測方法和基于信息論的方法。而根據(jù)所要解決的任務(wù)的差異，又可以分為兩種情況：節(jié)點(diǎn)分類和圖分類。

　　預(yù)測方法

　　首先來看預(yù)測方法。Yann LeCun 說過：「自監(jiān)督學(xué)習(xí)的系統(tǒng)是根據(jù)其輸入的某些部分來預(yù)測輸入的其它部分?！惯@就意味著在自監(jiān)督學(xué)習(xí)中，輸入的結(jié)構(gòu)是很重要的。而圖就是高度結(jié)構(gòu)化的，因此天生就很適合自監(jiān)督學(xué)習(xí)。

　　對于節(jié)點(diǎn)分類任務(wù)，實(shí)現(xiàn)自監(jiān)督學(xué)習(xí)的方法通常有兩種。一是強(qiáng)制使用相鄰節(jié)點(diǎn)之間的相似性，二是基于鄰近節(jié)點(diǎn)執(zhí)行每個(gè)節(jié)點(diǎn)的重建。

　　首先，我們來看第一種方法，這種方法由 GraphSAGE 引入，其基本思想是強(qiáng)制每個(gè)節(jié)點(diǎn)與其鄰近節(jié)點(diǎn)有相似的表征。在這種情況下，設(shè) h_u 為 h_v 的鄰近節(jié)點(diǎn)，則我們的目標(biāo)是最大化它們的內(nèi)積。我們稱這些鄰近節(jié)點(diǎn)為正例樣本。然后，我們最小化 h_v 與通過負(fù)采樣得到的其它節(jié)點(diǎn)之間的相似性，這些節(jié)點(diǎn)通常是從整個(gè)圖均勻采樣的。這樣，我們就可以使用反向傳播來訓(xùn)練 GNN 的參數(shù)了。

　　至于第二種方法，來自 Durán & Niepert 提出的 EP-B，其首先會計(jì)算鄰近節(jié)點(diǎn)的表征的聚合。目標(biāo)是最小化重建的結(jié)果與真實(shí)表征之間的距離。與此同時(shí)，又最大化這個(gè)聚合表征與其它節(jié)點(diǎn)的表征之間的距離。

　　EP-B 和 GraphSAGE 的主要區(qū)別是 EP-B 強(qiáng)制使用了鄰近節(jié)點(diǎn)和每個(gè)其它節(jié)點(diǎn)的聚合之間的相似性，而 GraphSAGE 則直接強(qiáng)制使用了鄰近節(jié)點(diǎn)與每個(gè)節(jié)點(diǎn)的相似性。

　　在圖分類方面又有哪些方法呢？

　　我們要介紹的第一種方法是 N-Gram Graph。該方法分為兩個(gè)階段：節(jié)點(diǎn)表征階段和圖表征階段。節(jié)點(diǎn)表征階段使用了一種傳統(tǒng)的自監(jiān)督式節(jié)點(diǎn)嵌入方法 CBoW 來學(xué)習(xí)節(jié)點(diǎn)表征。在第二個(gè)階段，由于已有節(jié)點(diǎn)表征，則首先會為每條長度為 n 的路徑計(jì)算表征，稱為 n-gram 路徑。這個(gè)路徑表征是以該路徑中每個(gè)節(jié)點(diǎn)的表征的積形式得到的。因此，它們將歷經(jīng)圖中所有的 n-gram 路徑并歸總所有路徑的表征。最終的圖表征是通過將 1-gram 到 T-gram 的路徑連接起來而得到的。

　　事實(shí)上，這樣的計(jì)算就等于沒有訓(xùn)練的 GNN。N-Gram Graph 的訓(xùn)練無需任何監(jiān)督。

　　另一種用于圖分類的方法是 PreGNN，它同樣分為兩個(gè)階段：第一個(gè)階段是執(zhí)行節(jié)點(diǎn)表征（但使用了兩種全新方法），第二階段是使用簡單的讀出基于所有節(jié)點(diǎn)獲取圖層面的表征。但它是通過一種監(jiān)督式策略交叉熵來訓(xùn)練圖層面的表征。該研究指出，節(jié)點(diǎn)層面和圖層面的訓(xùn)練對最終性能而言都很重要。

　　因?yàn)槠涞诙€(gè)階段很普通，所以我們只解讀一下第一個(gè)階段。

　　在這一階段，PreGNN 提出了兩種損失函數(shù)。周圍結(jié)構(gòu)預(yù)測（context prediction）是強(qiáng)制節(jié)點(diǎn)表征與其周圍結(jié)構(gòu)相似。另外我們還執(zhí)行負(fù)采樣來最小化 h_v 與其它節(jié)點(diǎn)的周圍結(jié)構(gòu)之間的相似性。這個(gè)方法的思路很簡單：每個(gè)節(jié)點(diǎn)周圍的結(jié)構(gòu)定義了該節(jié)點(diǎn)的局部拓?fù)浣Y(jié)構(gòu)。

　　另一個(gè)損失則是屬性掩碼（attribute masking）。這個(gè)損失的設(shè)計(jì)靈感來自強(qiáng)大的 NLP 模型 BERT。簡單來說，就是隨機(jī)地使用掩碼替換節(jié)點(diǎn)，然后構(gòu)建訓(xùn)練損失函數(shù)來預(yù)測輸入。方法很簡單，但效果很好。

　　另一種值得一提的方法是 GCC。該方法使用了對比學(xué)習(xí)（contrastive learning）來執(zhí)行圖層面的無監(jiān)督學(xué)習(xí)。不過 GCC 的一大主要問題是沒有節(jié)點(diǎn)層面的訓(xùn)練。

　　總結(jié)一下，在圖分類任務(wù)上，N-Gram Graph 和 PreGNN 都使用了節(jié)點(diǎn)層面的自監(jiān)督，而 GCC 使用了圖層面的自監(jiān)督。那么，我們自然會問：能不能同時(shí)使用節(jié)點(diǎn)層面和圖層面的自監(jiān)督？

　　答案當(dāng)然是肯定的。這就要談到騰訊 AI Lab 研究團(tuán)隊(duì)提出的 GROVER 了。

　　GROVER 同樣分為兩個(gè)階段。在節(jié)點(diǎn)階段，我們還同時(shí)考慮了邊，但為了說明簡單，這里僅討論節(jié)點(diǎn)表征過程。在這一階段，首先為每個(gè)節(jié)點(diǎn)提取一個(gè)詞典池。我們稱之為 key。然后我們像 BERT 一樣為每個(gè)節(jié)點(diǎn)加掩碼，然后預(yù)測每個(gè)節(jié)點(diǎn)周圍的局部結(jié)構(gòu)。如果局部結(jié)構(gòu)與詞典中的一個(gè) key 匹配，則在該維度上輸出 1，否則便輸出 0。注意這是一個(gè)多標(biāo)簽分類問題，因?yàn)槊總€(gè)節(jié)點(diǎn)的局部結(jié)構(gòu)通常有多個(gè)。這樣，我們僅需要一類掩碼就能做到 PreGNN 的兩件事。

　　然后在圖階段，預(yù)測是相似的。我們也首先提取 graph motif，其由典型的官能團(tuán)（比如苯環(huán)）構(gòu)成。然后我們使用 GNN 獲取每個(gè)圖的輸出。使用該輸出，我們將預(yù)測這個(gè)圖是否包含這些 graph motif。注意這也是一個(gè)多標(biāo)簽分類問題。

　　除此之外，騰訊 AI Lab 還在該研究中提出了一種類似 Transformer 的強(qiáng)大 GNN 模型：GTransformer。其首先會使用一種新提出的名為 dyMPN 的 動態(tài)擴(kuò)展范圍 MPNN 來獲取每個(gè)輸入圖的 key、查詢和值，然后會像 Transformer 一樣獲取最終輸出結(jié)果。實(shí)驗(yàn)結(jié)果證明了這一模式的強(qiáng)大能力。

　　以上這些就是 GROVER 的關(guān)鍵組件。更進(jìn)一步的，我們還實(shí)現(xiàn)了一個(gè)分布式的圖訓(xùn)練框架，最終成功在 1000 萬個(gè)無標(biāo)注分子數(shù)據(jù)上預(yù)訓(xùn)練帶有 1 億個(gè)參數(shù)的大模型。

　　使用這個(gè)預(yù)訓(xùn)練的模型，我們可以針對下游任務(wù)進(jìn)行微調(diào)。在此基礎(chǔ)上，GROVER 可以取得顯著優(yōu)于 MPNN 和 DMPNN 等傳統(tǒng)方法的表現(xiàn)，同時(shí)也優(yōu)于 N-Gram 和 PreGNN 等自監(jiān)督方法。

　　基于信息的方法

　　介紹了預(yù)測方法，我們再來看基于信息的方法。

　　優(yōu)良的表征應(yīng)該能將輸入中的大量信息保存下來。受此啟發(fā)，Vincent et al. 在 2010 年提出使用自動編碼器來進(jìn)行表征學(xué)習(xí)，這意味著隱藏表征應(yīng)該可以解碼到與其輸入一樣。

　　但自動編碼器資源消耗高，既需要編碼，也需要解碼，而在圖領(lǐng)域，如何解碼圖仍還是一個(gè)有待解決的問題。那么還有其它可以直接衡量表征與輸入之間的信息的方法嗎？有的，那就是互信息（mutual information）。

　　給定兩個(gè)隨機(jī)變量，互信息的定義是它們的邊界屬性和關(guān)節(jié)屬性的積之間的 KL 散度，這又可以進(jìn)一步推導(dǎo)為熵減去條件熵。

　　互信息為什么可以計(jì)算信息關(guān)系？我們可以這樣看，如果 X 和 Y 互相獨(dú)立，且 p（X）p（Y）=p（X,Y），則互信息等于 0，這表明 X 和 Y 不相關(guān)。這是合理的，因?yàn)?X 和 Y 互相獨(dú)立。如果條件熵為 0，則 X 和 Y 確定是相關(guān)的，則互信息輸出為最大值。

　　Hjelm et al. 2019 證明執(zhí)行自動編碼是計(jì)算互信息的重建誤差的一個(gè)下限。

　　計(jì)算互信息是很困難的，近些年方才出現(xiàn)一些可行的方法。這里有三種典型的方法（MINE、JSD MI 和 infoNCE MI），其基本思想是學(xué)習(xí)一個(gè)神經(jīng)網(wǎng)絡(luò)來最大化互信息的一個(gè)替代函數(shù)。詳情請參閱各論文。

　　回到圖，我們能否使用互信息來實(shí)現(xiàn)圖的自監(jiān)督學(xué)習(xí)？DGI 是這方面首個(gè)研究成果，其目標(biāo)設(shè)定為最大化輸入的節(jié)點(diǎn)特征 X 和鄰接矩陣 A 與輸出表征 h_i 之間的互信息。DGI 使用了 JSD 估計(jì)器，其中包含正例項(xiàng)和負(fù)例項(xiàng)。

　　但直接計(jì)算互信息的難度不小，我們可能需要另一個(gè) GNN 作為互信息的替代。DGI 使用了表征的讀出 s 來替代輸入。如下圖所示，原圖有兩個(gè)輸入，其中錯(cuò)誤的圖是負(fù)例，然后我們用同樣的 GNN 得到它們的輸出，之后再執(zhí)行讀出函數(shù)得到 s。s 可以替代原目標(biāo)中的 X,A，得到替代目標(biāo)函數(shù)。

　　DGI 證明這種操作不會導(dǎo)致信息損失，其還證明這種替換方式實(shí)際上就等同于真正的互信息。

　　不過 DGI 仍還有一些問題。第一是它需要讀出函數(shù)來計(jì)算互信息，而且這個(gè)讀出函數(shù)需要是單射式的，這并不容易保證。另外它還需要構(gòu)建錯(cuò)誤的圖來得到負(fù)例，因此效率不高。而在實(shí)驗(yàn)中，DGI 需要為不同的任務(wù)使用不同的編碼器，這并不實(shí)用。

　　針對這些問題，清華大學(xué)、西安交通大學(xué)與騰訊 AI Lab 合作提出了 GMI，其基本思想是不使用讀出函數(shù)和錯(cuò)誤樣本，而是直接計(jì)算互信息。

　　在 GMI 中，首先分兩部分定義互信息。一是特征互信息，僅度量節(jié)點(diǎn)特征和表征之間的信息關(guān)系。二是拓?fù)浠バ畔?，這是預(yù)測的邊和原始鄰接矩陣之間的互信息。

　　很顯然，這一方法能同時(shí)考慮到邊和特征，而無需讀出函數(shù)或錯(cuò)誤樣本。更重要的是，特征互信息還能進(jìn)一步分解。

　　我們證明：特征互信息可以分解為局部互信息的加權(quán)和。而每個(gè)局部互信息計(jì)算的是每個(gè)節(jié)點(diǎn)及其表征之間的互信息。權(quán)重取決于不同的情況，將它們設(shè)置為與預(yù)測的邊一樣也不錯(cuò)。然后我們可以使用 JSD 互信息估計(jì)器來計(jì)算特征互信息和邊互信息。

　　在節(jié)點(diǎn)分類任務(wù)上的實(shí)驗(yàn)結(jié)果證明 GMI 有更優(yōu)的表現(xiàn)，相關(guān)的代碼也已經(jīng)發(fā)布：https://github.com/zpeng27/GMI

　　至于用于圖分類的基于信息的方法，可參看 ICLR 2020 論文《InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization》，這里不再過多贅述。

　　三 圖神經(jīng)網(wǎng)絡(luò)的應(yīng)用進(jìn)展

　　圖神經(jīng)網(wǎng)絡(luò)作為一種有效的深度學(xué)習(xí)工具，已經(jīng)在分子屬性預(yù)測、生物學(xué)分析、金融等許多領(lǐng)域得到了應(yīng)用。這里以騰訊 AI Lab 實(shí)現(xiàn)的在社交網(wǎng)絡(luò)和醫(yī)療影像領(lǐng)域的應(yīng)用為例，介紹圖神經(jīng)網(wǎng)絡(luò)的應(yīng)用進(jìn)展。

　　1 用于社交網(wǎng)絡(luò)的 GNN

　　首先來看一篇 WWW 2019 論文《Semi-supervised graph classification: A hierarchical graph perspective》，其中騰訊 AI Lab 提出了使用分層圖實(shí)現(xiàn)半監(jiān)督圖分類的方法。

　　分層圖是指一組通過邊互相連接在一起的圖實(shí)例，如圖所示：

　　在許多現(xiàn)實(shí)應(yīng)用中，很多數(shù)據(jù)都可以建模成分層圖的形式，比如具有分組結(jié)構(gòu)的社交網(wǎng)絡(luò)和文檔集合（比如具有引用關(guān)系的 graph-of-words）。如上所示，假設(shè)我們有一個(gè)「用戶 - 分組」分層圖，我們知道其中部分標(biāo)簽，我們可以怎樣預(yù)測其它組的標(biāo)簽？

　　如果僅考慮組之間的聯(lián)系，那么這個(gè)問題就又回到了節(jié)點(diǎn)分類。但是，可以看到每一組都有自己的用戶圖，忽略這樣的信息并不合適。為了在用戶和分組層面上利用圖信息，我們面臨著這樣的難題：如何將任意大小的圖表征為固定長度的向量？如何整合實(shí)例層面和分層層面的信息？

　　首先來看第一個(gè)問題。圖表征與節(jié)點(diǎn)表征在不同的層面上；在節(jié)點(diǎn)層面上圖 G 會被投射到大小為 n×v 的隱藏空間中；而在圖層面上圖 G 會被投射成大小為 v 的隱藏向量。因此，為了將節(jié)點(diǎn)層面的空間轉(zhuǎn)換成圖層面的向量，這里引入了自注意力圖嵌入（SGAE）。

　　首先，將單個(gè)圖通過一個(gè)兩層 GCN，得到節(jié)點(diǎn)層面的表征 H，其大小為 n×v，然后根據(jù)上圖中的 S 計(jì)算自注意力。在經(jīng)過一個(gè) softmax 函數(shù)之后，會得到一個(gè)具有 r 個(gè)頭的多頭自注意分?jǐn)?shù)，其大小為 r×n。然后，如果我們將這些分?jǐn)?shù)應(yīng)用到節(jié)點(diǎn)層面的表征，我們就會得到大小固定為 r×v 的矩陣。SAGE 有三大優(yōu)勢：1）其大小因自注意力而保持不變，2）因?yàn)?GCN 平滑而具有排列不變性，3）因?yàn)樽宰⒁饬Χ苁褂霉?jié)點(diǎn)重要度。

　　對于第二個(gè)問題：如何整合實(shí)例層面和分層層面的信息？這里實(shí)例層面是基于 SAGE 的圖層面學(xué)習(xí)，分層層面模型是節(jié)點(diǎn)層面的學(xué)習(xí)。我們使用了特征共享來連接 SAGE 的輸出和 GCN 的輸入。然后又引入一種新的分歧損失（disagreement loss）來最小化實(shí)例分類器和分層分類器之間的不一致情況。

　　另外，我們還使用了主動學(xué)習(xí)來解決樣本數(shù)量少的問題。我們使用了分歧損失來為外部標(biāo)注選擇實(shí)例。有關(guān)這兩種算法 SEAL-AI 和 SEAL-CI 的詳情以及相關(guān)實(shí)驗(yàn)結(jié)果請查閱論文。

　　接下來看騰訊 AI Lab 另一項(xiàng)被 AAAI 2020 接收的研究《Rumor Detection on Social Media with Bi-Directional Graph Convolutional Networks》，提出了一種通過雙向圖卷積網(wǎng)絡(luò)實(shí)現(xiàn)社交網(wǎng)絡(luò)謠言檢測的新思路。

　　謠言可算是當(dāng)今社會面臨的一大頑疾。這篇論文提出通過關(guān)注和轉(zhuǎn)發(fā)關(guān)系來檢測社交媒體上的謠言。不管是謠言還是新聞，它們的傳播模式都是樹結(jié)構(gòu)的。但通常來說，謠言的傳播有兩個(gè)屬性。第一如下圖 b 所示，其會沿一條關(guān)系鏈進(jìn)行很深的傳播。第二如圖 c，謠言在社交媒體上傳播時(shí)散布很寬。舉個(gè)例子，一個(gè) Twitter 用戶可能有大量關(guān)注者。

　　為了同時(shí)獲取謠言傳播的這兩種屬性，我們設(shè)計(jì)了一種基于 GCN 的新模型。這個(gè)用于謠言檢測的雙向 GCN 包含 4 個(gè)組件：1）兩個(gè)不同的有向圖，用于描述謠言的傳播和擴(kuò)散度；2）使用二層 GCN 來計(jì)算高層面的節(jié)點(diǎn)表征；GCN 不僅能學(xué)習(xí)特征信息，還能學(xué)習(xí)謠言的傳播拓?fù)浣Y(jié)構(gòu)；3）經(jīng)過觀察，根節(jié)點(diǎn)通常就已經(jīng)包含了謠言或新聞的主要內(nèi)容，而關(guān)注者通常只是不帶任何內(nèi)容進(jìn)行轉(zhuǎn)發(fā)，因此通過將根特征連接到樹中的每個(gè)節(jié)點(diǎn)，可以增強(qiáng)每層的隱藏特征；4）分別根據(jù)節(jié)點(diǎn)表征對傳播和擴(kuò)散度的兩個(gè)表征進(jìn)行池化處理。這兩個(gè)表征再被聚合到一起得到最終結(jié)果。

　　我們在 Twitter15、Twitter16、Weibo 三個(gè)常用基準(zhǔn)上的實(shí)驗(yàn)研究對這一方法的效果進(jìn)行驗(yàn)證，結(jié)果表明新方法具有顯著更優(yōu)的表現(xiàn)。

　　此外，我們還評估了謠言的早期偵測，此時(shí)僅給出謠言樹上非常有限的節(jié)點(diǎn)并且還設(shè)置了一個(gè)偵測截止時(shí)間，結(jié)果表明基于圖的方法非常適用于早期發(fā)現(xiàn)謠言。

　　2 用于醫(yī)療影像的 GNN

　　醫(yī)療影像也是 GNN 的一個(gè)重要應(yīng)用場景，騰訊 AI Lab 近兩年在這一領(lǐng)域取得了一些重要的研究成果。首先來看騰訊 AI Lab 的 MICCAI 2018 論文《Graph CNN for Survival Analysis on Whole Slide Pathological Images》，其中提出使用圖卷積網(wǎng)絡(luò)基于全切片病理圖像進(jìn)行生存分析。

　　生存分析的目標(biāo)是預(yù)測特定事件發(fā)生的風(fēng)險(xiǎn)，這類事件包括器官衰竭、藥物不良反應(yīng)和死亡。有效的分析結(jié)果具有重要的臨床應(yīng)用價(jià)值。但實(shí)際操作時(shí)卻面臨著許多困難。

　　首先，全切片病理圖像（WSI）分析是一個(gè)需要大量計(jì)算的過程，因?yàn)閱螐?WSI 的數(shù)據(jù)量就超過 0.5 GB，而且其中包含數(shù)百萬個(gè)細(xì)胞，還涉及局部特征和全局特征，因此非常復(fù)雜。另外，如何將 WSI 的拓?fù)涮卣饔糜谏娣治鲆策€是一個(gè)有待解決的問題。

　　為此，我們提出將 WSI 建模成圖，然后開發(fā)了一種圖卷積神經(jīng)網(wǎng)絡(luò)（Graph CNN），其使用了注意力機(jī)制，可通過提供 WSI 的最優(yōu)圖表征來實(shí)現(xiàn)更好的生存分析。

　　實(shí)驗(yàn)結(jié)果表明，這種新方法優(yōu)于之前的其它方法。

　　這一部分同時(shí)也介紹了近年來 GNN 在醫(yī)療圖像上的其他工作：在 IPMI2019 發(fā)表的《Graph Convolutional Nets for Tool Presence Detection in Surgical Videos》中，作者提出使用 GCN 來檢測手術(shù)視頻中的工具，這是自動手術(shù)視頻內(nèi)容分析的核心問題之一，可用于手術(shù)器材使用評估和手術(shù)報(bào)告自動生成等應(yīng)用。這個(gè)模型使用了 GCN 沿時(shí)間維度通過考慮連續(xù)視頻幀之間的關(guān)系來學(xué)習(xí)更好的特征。

　　而在 MICCAI 2020 發(fā)表的論文《Graph Attention Multi-instance Learning for Accurate Colorectal Cancer Staging》中，作者提出使用圖注意力多實(shí)例學(xué)習(xí)來準(zhǔn)確判斷結(jié)直腸癌是處于早期、中期還是晚期。

　　總結(jié)和展望

　　在這次課程中，我們介紹了圖神經(jīng)網(wǎng)絡(luò)的發(fā)展歷史、包括圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力、深度、大規(guī)模擴(kuò)展、自監(jiān)督 / 無監(jiān)督學(xué)習(xí)等方面的研究進(jìn)展，也簡要介紹了騰訊 AI Lab 在圖神經(jīng)網(wǎng)絡(luò)的社交網(wǎng)絡(luò)和醫(yī)療影像應(yīng)用方面的一些初步成果。

　　圖深度學(xué)習(xí)領(lǐng)域仍處于發(fā)展之中，有很多有趣的問題等待解決，例如逆向圖識別（IGI），即我們在圖分類問題中，是否可以根據(jù)圖的標(biāo)簽來推斷每個(gè)節(jié)點(diǎn)的標(biāo)簽？子圖識別，即如何在圖中找到關(guān)鍵的子圖同時(shí)還有圖與多示例學(xué)習(xí)問題的結(jié)合形成多圖示例學(xué)習(xí)問題，以及在圖上進(jìn)行攻擊與防御相關(guān)的圖深度學(xué)習(xí)魯棒性的研究。最后，層次圖也是一個(gè)熱門的研究方向。圖神經(jīng)網(wǎng)絡(luò)必將在人工智能領(lǐng)域未來的研究和應(yīng)用中扮演更重要的角色。

　　如何快速構(gòu)建圖片搜索引擎？

　　亞馬遜AWS解決方案架構(gòu)師邱越俊將于9月24日帶來一場live coding，利用Amazon Elasticsearch Service，從零開始構(gòu)建一個(gè)以圖搜圖的應(yīng)用程序，包括用Amazon SageMaker對圖片做特征向量提取，用Amazon Elasticsearch做特征向量搜索，用AWS Amplify快速搭建應(yīng)用程序。