本文作者：

騰訊：榮鈺、徐挺洋、黃俊洲；清華大學：黃文炳；香港中文大學：程鴻

前言

人工智能領域近幾年歷經了突飛猛進的發展。圖像、視頻、游戲博弈、自然語言處理、金融等大數據分析領域都實現了跨越式的進步并催生了很多改變了我們日常生活的應用。近段時間，圖神經網絡成為了人工智能領域的一大研究熱點，尤其是在社交網絡、知識圖譜、化學研究、文本分析、組合優化等領域，圖神經網絡在發掘數據中隱含關系方面的強大能力能幫助我們獲得更好的數據表達，進而能讓我們做出更好的決策。比如通過圖神經網絡梳理人類社會關系網絡的演變，可有望幫助我們理解人類社會的底層運作模式，進而讓我們離理想社會更近一步。

在今年的計算機協會國際數據挖掘與知識發現大會（ACM SIGKDD，簡稱 KDD）上，圖神經網絡備受研究關注的現狀得到了充分體現：粗略統計，今年 KDD 接收的 216 篇論文（research track）中有近 40 篇與圖神經網絡相關。也因此，一場為期一天的圖神經網絡相關課程課程得到了參會人員的重點關注。該聯合課程課程的主題為「圖深度學習：基礎、進展和應用（Deep Graph Learning: Foundations, Advances and Applications）」，由騰訊AI Lab、清華大學、香港中文大學等機構聯合組織，從基礎的圖概念一直談到了當今最前沿的圖神經網絡研究進展。

本次Tutorial課程（講解）分為兩個主題部分。本文將分圖與圖神經網絡歷史、圖神經網絡的最新研究進展和圖神經網絡的應用進展三大部分歸納總結該課程Theme II: Advances and Applications部分的核心內容，Theme I以及更多詳細的內容可參看課程幻燈片及相關論文：https://ai.tencent.com/ailab/ml/KDD-Deep-Graph-Learning.html

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

一、圖與圖神經網絡

1、什么是圖？

漢語中的「圖」可以對應成英語中多個不同的詞：image、picture、map 以及本文關注的 graph。圖（graph）也可稱為「關系圖」或「圖譜」，是一種可用于描述事物之間的關系的結構。圖的基本構成元素為頂點和連接頂點的邊。根據邊是否存在方向的性質，還可分為有向圖和無向圖。一般而言，我們通常可將圖表示成點和連接點的線的形式，這有助于我們更直觀地理解，如下圖所示：

? ? ? ? ? ? ? ? ? ? ? ?

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

? ? ? ? ? ? ? ? ? ? ? ?

圖具有很強的表征能力。物理學系統建模、蛋白質預測、疾病分類以及許多文本和圖像處理任務都可以表示成圖結構的數據，比如圖可用于表示文本中句子的依賴關系和圖像中事物的相對位置，也可以用于分析社交網絡中的信息傳播和用戶關系，還能通過分析分子之間的關聯來發現新藥。

2、圖神經網絡

近些年在大數據和硬件發展雙重助力下迎來跨越式發展的深度神經網絡技術讓我們具備了分析和理解大規模圖數據的能力。總體而言，圖分析任務可分為節點分類、連接預測、聚類三類。

圖神經網絡（GNN）就是處理圖數據的神經網絡，其中有兩種值得一提的運算操作：圖過濾(Graph Filter, 分為基于空間的過濾和基于譜的過濾）和圖池化。其中圖過濾可細化節點特征，而圖池化可以從節點表示生成圖本身的表示。

一般來說，GNN 的框架在節點層面上由過濾層和激活構成，而對于圖層面的任務，則由過濾層、激活和池化層組成不同的模塊后再連接而成。

?

在 GNN 的實現方面，目前最常用的方法是消息傳遞框架（Message Passing Framework）。簡單總結起來，該框架分為兩個步驟。

第一步是消息生成步驟。首先，從近鄰節點收集狀態數據，然后使用對應函數生成當前節點的消息。在第二步中，我們更新目標節點的狀態。

?

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

3、圖神經網絡的發展歷史

圖神經網絡（GNN）并不是一個新事物，最早的GNN 的歷史可以追溯到 1997 年，粗略總結起來，GNN 的發展過程大致可分為三個階段。

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

在第二個階段，卷積被引入到了 GNN 的工作流程中。當用矩陣進行表示時，圖與卷積擅長處理的圖像具有很多相似性，也因此開啟了在 GNN 中使用卷積的時代。一系列的工作將在譜空間上的圖卷積轉換為了拓撲空間上的近似，并在此基礎上于 2017 年誕生了圖卷積網絡（GCN），其首次使用了逐層卷積來擴展感受野，圖神經網絡也由此開始了實際應用。

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

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

• 注意力機制：圖注意力網絡（使用可學習的自注意力替換固定的聚合權重）、門控注意力網絡（加入了可學習的門來建模每個頭的重要度）、譜式圖注意力網絡（將注意力應用于譜域中的高/低頻組件）。

• 圖池化：SAGE（自注意圖嵌入，在池化時使用自注意力來建模節點重要度）、通過圖剪切實現圖池化（通過圖剪切算法得到的預訓練子圖實現圖池化）、可微分圖池化（DIFFPOOL，通過學習聚類分配矩陣以分層方式來聚合節點表征）、特征池化（EigenPooling，通過整合節點特征和局部結構來獲得更好的分配矩陣）。

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

下圖簡單總結了各種 GNN 變體之間的關系：

二、圖神經網絡的表達能力

了解了 GNN 的基本知識和發展脈絡，接下來我們將踏入當前的前沿研究領域，解讀近期的一些理論研究成果和設計創新。

1、圖神經網絡的表達能力

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

為了有效地評估 GNN 的表達能力，首先需要定義評估標準。目前來說，可通過三種典型任務來進行評估：圖同構、函數近似和圖檢測/優化/評估。

對于圖同構任務，GNN 的目標是確定任意給定的兩個圖是否同構。這是一個很重要的任務。對于圖分類任務而言，如果兩個圖是同構的，則 GNN 需要為這兩個圖輸出同樣的標簽。

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

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

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

Maron et al. 提出了一種架構，對于擁有圖不變映射層（graph invariant layer）和圖等變映射層（graph equivariant layer）的 GNN，如果在一個非線性層（比如 ReLU）之后堆疊等變映射層，層層疊加，然后在最后添加圖不變映射層。可以看出這樣的模型能在輸入的排列方式變化時保持映射不變性。這樣的模型被稱為圖不變網絡（INN）。

? ? ? ? ??

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

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

? ? ? ? ? ?

接下來，我們看看 GNN 是否有足夠的表達能力來解決更困難的任務，比如尋找圖中的最短路徑或確定圖中是否存在環。這些任務的難度很高，因為它們需要在節點層面執行很細粒度的推理。

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

因此，總結起來，只要架構合適，GNN 其實具有非常強大的表達能力；也因此，要充分發掘 GNN 的真正實力，我們還需要更多架構方面的研究探索。

2、訓練深度圖神經網絡

前面已經簡單提到，深度對 GNN 的能力而言是非常重要的。這一點在深度神經網絡（DNN）上也有體現——更深的網絡往往具有強大的表達能力，可以說深度網絡就是當前的人工智能發展熱潮的最主要驅動力之一。

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

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

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

首先來看通過簡單增加深度來擴展 GNN 的方法。可以看到，對于下圖中的六種 GNN：GCN、GraphSAGE（進一步改進了池化方法）、ResGCN（使用了殘差網絡的思路）、JKNet（使用了 DenseNet 的思路）、IncepGCN（使用了 Inception-v3 的思路）、APPNP（借用了 PageRank 的思路），簡單增加深度并不一定能提升準確度，甚至還可能出現相反的狀況，比如 GCN、GraphSAGE 和 ResGCN 在深度增大時準確度反而顯著下降。

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

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

• 過平滑

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

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

?

這個過程意味著一個節點的新特征是根據其本身和相鄰節點的加權平均而構建的。

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

?

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

然后，如果我們用一組在節點特征上的可學習參數替換這個初始概率，它就能轉換成一個線性的 L層 GCN。

可以看出，基于隨機游走的一些結論也適用于線性 GCN，其中一項便是隨機游走在經過無限多步之后會收斂到一個駐點。

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

將這個求和展開，可得到下式：

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

因此，當 lL趨近無窮大時，最大的 m 項依然存在，因為其 λ 等于 1。但是，其余的項都將被忽略，因為這些 λ 的 l 次冪將趨近于零。這會使得隱變量 H_L 隨網絡深度增長而趨近于一個特定的點。

?

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

?

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

? ? ? ? ? ?? ? ??

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

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

?

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

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

?

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

綜合這些不等式，可得到隱變量的子空間距離沿層數變化的收斂性。可以看到，隨著層數趨近于無窮大，子空間距離將趨近于 0，因此隱變量將會收斂到子空間 M。

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

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

可以看到，當 l 趨近無窮大時，不等式右側部分就是一個無窮等比序列的和：

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

總結一下，通過分析上面三種來自不同場景的情況，可以發現這三種情況之下存在一種普適的公式。我們可用以下不等式統一過平滑的情況：

?

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

詳見論文《Tackling Over-Smoothing for General Graph Convolutional Networks》。

• 過擬合和訓練動態變化

接下來我們看看過擬合問題。過擬合是深度學習的一個常見問題，當數據點數量少而參數數量很多時，就會出現這種情況。此時模型會與訓練數據完全擬合（本質上就是記住了數據），而在驗證數據上表現很差。

??? ?

訓練動態變化也是深度學習領域的一大常見問題。根據鏈式法則，當模型變深時，s_l-1 乘以 λ_m+1 的結果小于 1，會出現梯度消失問題。如果我們將 RGB 色彩作為以下的圖的節點特征，可以看到當層數達到 500 時，這些特征的梯度降為了 0，節點都變成了黑色，即RGB=[0, 0, 0]。

過擬合和訓練動態變化是深度學習的常見問題，這里便不過多贅述了。下面我們看看在解決過平滑問題方面有什么研究進展。

• 如何解決過平滑問題？

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

?

然后，將 ε-平滑層定義為能讓 H_l 的子空間距離小于 ε 的最小層。但是，ε-平滑層是很難推導的。因此，我們取一個松弛化的 ε-平滑層作為上界。這個松弛化的 ε-平滑層的公式如下：

? ? ? ? ? ?? ? ? ? ? ?

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

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

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

? ? ? ? ? ? ? ? ? ? ? ?

那么我們如何做到這一點呢？很簡單，在每 epoch 都丟棄一些邊即可。研究證明，當丟棄一些邊時，圖上信息的傳播速度會下降，子空間的維度會隨連接的分量的增多而增加。丟棄邊后的這兩個現象都有助于緩解過平滑問題。

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

?

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

? ? ? ? ? ? ? ? ? ? ? ?

• 其它問題的解決方案

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

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

另一種克服訓練動態變化的方法是在結構中添加捷徑。JKNet、IncepGCN 和 APPNP 等 GNN 能在深度結構中保持性能的方法就是如此。

因為這三個模型全都包含通過聚合層到終點的捷徑，因此淺的信息可以傳播到最后的層，也因此這些模型實際上仍舊是「淺模型」。

順便一提，這些不同的 GNN 結構仍然滿足過平滑的一般情況：

詳細的分析請參考論文：《Tackling Over-Smoothing for General Graph Convolutional Networks》。總結一下，在這些新的理論進展的幫助下，訓練更深度 GNN 的問題已經得到了初步解答。

3、大規模圖神經網絡

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

基本的 GNN 通常無法處理大規模圖，因為其通常無法滿足巨大的內存需求，而且梯度更新的效率也很低。

為了讓 GNN 有能力處理大規模圖，研究者已經提出了三種不同的采樣范式：基于節點的采樣、基于層的采樣和基于子圖的采樣。

?

其中，逐節點采樣是根據目標節點執行采樣，而逐層采樣是基于卷積層來執行采樣，逐圖采樣則是從原圖采樣子圖，然后使用子圖進行模型推理。

根據這三種范式，可以知道為了實現大規模 GNN，我們需要解決兩個問題：如何設計高效的采樣算法？如何保證采樣質量？

近些年在構建大規模 GNN 方面已經出現了一些成果，下圖給出了這些成果的時間線：

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

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

? ? ? ? ? ??

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

為了解決這一問題并進一步提升性能，GraphSAGE 采用了固定采樣個數的的鄰近采樣方法，即每層都采樣固定大小的鄰近節點集合。

?

從上右圖可以看到，采用固定采樣個數的采樣方法后，采樣節點的數量降低了。當圖的規模很大時，這一差距會更加顯著。不過，GraphSAGE 在網絡層數較大時依然無法避免鄰近節點擴張問題，采樣質量上也無法得到保證。

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

? ? ? ? ? ? ? ? ? ? ? ?

不過，VR-GCN 也有一個缺點：需要額外的內存來存儲所有的歷史隱藏嵌入，這使得我們難以實現大規模擴展。

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

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

?

基于此，我們可以在每層都采樣固定數量的節點。更進一步，FastGCN 還提出了基于重要度的采樣模式，從而降低方差。在采樣過程中，每一層的采樣都是相互獨立的，而且每一層的節點采樣概率也保持一致。下圖是 GCN 與 FastGCN 的對比：

?

可以看出，FastGCN 的計算成本顯著更低，而且研究表明，這種采樣模式從期望上并不會丟失太多信息，因為其在執行重要度采樣時會進行隨機化處理，通過足夠多epoch的訓練，每個節點和鏈接都有期望被采樣。

可以看出，基于層采樣的FastGCN 徹底解決了鄰近節點擴張問題，而且采樣方法有質量保證。但是該方法的缺點是無法獲得層之間的相關性，模型的表現也可能受到負面影響。

為了更好地獲得層之間的相關性，ASGCN 提出了自適應層式采樣方法，即根據高層采樣結果動態調整更低層的采樣概率。如下左圖所示，在對底層采樣的時候ASGCN會考慮采樣高層采樣的鄰居節點，使得層之間的相關性得到很好的保留。如下右圖所示，整個采樣過程是自上而下的。我們首先采樣輸出層的目標節點，然后根據其采樣結果采樣中間層的節點，然后重復這個過程直到輸入層。在采樣過程中，每層采樣節點的數目也會保持一個固定值。

?

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

?

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

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

? ? ? ? ? ? ? ? ? ? ? ?

通過限制子圖的大小，這種方法也可以有效避免鄰近節點擴張問題，因為在每一層中，采樣的范圍都不會超過聚類子圖。

?

不過，ClusterGCN 的論文并沒有對這種方法的采樣質量進行實證研究。

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

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

? ? ? ? ? ? ? ? ? ? ? ?

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

很顯然，大規模圖神經網絡方面還有很大的進一步研究空間，比如更高效的采樣技術、適用于異構圖或動態圖的架構等等。

4、圖神經網絡的自監督/無監督學習

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

目前在自監督圖學習方面已經有一些研究成果了。我們可以根據它們的機制將其分為兩大類別：預測方法和基于信息論的方法。而根據所要解決的任務的差異，又可以分為兩種情況：節點分類和圖分類。

• 預測方法

首先來看預測方法。Yann LeCun 說過：「自監督學習的系統是根據其輸入的某些部分來預測輸入的其它部分。」這就意味著在自監督學習中，輸入的結構是很重要的。而圖就是高度結構化的，因此天生就很適合自監督學習。

對于節點分類任務，實現自監督學習的方法通常有兩種。一是強制使用相鄰節點之間的相似性，二是基于鄰近節點執行每個節點的重建。

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

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

EP-B 和 GraphSAGE 的主要區別是 EP-B 強制使用了鄰近節點和每個其它節點的聚合之間的相似性，而 GraphSAGE 則直接強制使用了鄰近節點與每個節點的相似性。

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

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

?

事實上，這樣的計算就等于沒有訓練的 GNN。N-Gram Graph 的訓練無需任何監督。

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

因為其第二個階段很普通，所以我們只解讀一下第一個階段。

在這一階段，PreGNN 提出了兩種損失函數。周圍結構預測（context prediction）是強制節點表征與其周圍結構相似。另外我們還執行負采樣來最小化 h_v 與其它節點的周圍結構之間的相似性。這個方法的思路很簡單：每個節點周圍的結構定義了該節點的局部拓撲結構。

另一個損失則是屬性掩碼（attribute masking）。這個損失的設計靈感來自強大的 NLP 模型 BERT。簡單來說，就是隨機地使用掩碼替換節點，然后構建訓練損失函數來預測輸入。方法很簡單，但效果很好。

另一種值得一提的方法是 GCC。該方法使用了對比學習（contrastive learning）來執行圖層面的無監督學習。不過 GCC 的一大主要問題是沒有節點層面的訓練。

總結一下，在圖分類任務上，N-Gram Graph 和 PreGNN 都使用了節點層面的自監督，而 GCC 使用了圖層面的自監督。那么，我們自然會問：能不能同時使用節點層面和圖層面的自監督？

答案當然是肯定的。這就要談到騰訊 AI Lab 研究團隊提出的 GROVER 了。

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

?

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

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

以上這些就是 GROVER 的關鍵組件。更進一步的，我們還實現了一個分布式的圖訓練框架，最終成功在1000 萬個無標注分子數據上預訓練帶有 1 億個參數的大模型。

使用這個預訓練的模型，我們可以針對下游任務進行微調。在此基礎上，GROVER 可以取得顯著優于 MPNN 和 DMPNN 等傳統方法的表現，同時也優于 N-Gram 和 PreGNN 等自監督方法。

• 基于信息的方法

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

優良的表征應該能將輸入中的大量信息保存下來。受此啟發，Vincent et al. 在 2010 年提出使用自動編碼器來進行表征學習，這意味著隱藏表征應該可以解碼到與其輸入一樣。

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

給定兩個隨機變量，互信息的定義是它們的邊界屬性和關節屬性的積之間的 KL 散度，這又可以進一步推導為熵減去條件熵。

? ? ? ? ? ? ? ? ? ? ? ?

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

Hjelm et al. 2019 證明執行自動編碼是計算互信息的重建誤差的一個下限。

? ? ? ? ? ? ? ? ? ? ? ?

計算互信息是很困難的，近些年方才出現一些可行的方法。這里有三種典型的方法（MINE、JSD MI 和 infoNCE MI），其基本思想是學習一個神經網絡來最大化互信息的一個替代函數。詳情請參閱各論文。

回到圖，我們能否使用互信息來實現圖的自監督學習？DGI 是這方面首個研究成果，其目標設定為最大化輸入的節點特征 X 和鄰接矩陣 A 與輸出表征 h_i 之間的互信息。DGI 使用了 JSD 估計器，其中包含正例項和負例項。

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

?

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

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

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

在 GMI 中，首先分兩部分定義互信息。一是特征互信息，僅度量節點特征和表征之間的信息關系。二是拓撲互信息，這是預測的邊和原始鄰接矩陣之間的互信息。

? ? ? ? ? ? ? ? ? ? ? ?

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

我們證明：特征互信息可以分解為局部互信息的加權和。而每個局部互信息計算的是每個節點及其表征之間的互信息。權重取決于不同的情況，將它們設置為與預測的邊一樣也不錯。然后我們可以使用 JSD 互信息估計器來計算特征互信息和邊互信息。

?

在節點分類任務上的實驗結果證明 GMI 有更優的表現，相關的代碼也已經發布：https://github.com/zpeng27/GMI

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

三、圖神經網絡的應用進展

圖神經網絡作為一種有效的深度學習工具，已經在分子屬性預測、生物學分析、金融等許多領域得到了應用。這里以騰訊 AI Lab 實現的在社交網絡和醫療影像領域的應用為例，介紹圖神經網絡的應用進展。

1、用于社交網絡的 GNN

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

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

? ? ? ? ? ???

在許多現實應用中，很多數據都可以建模成分層圖的形式，比如具有分組結構的社交網絡和文檔集合（比如具有引用關系的graph-of-words）。如上所示，假設我們有一個「用戶-分組」分層圖，我們知道其中部分標簽，我們可以怎樣預測其它組的標簽？

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

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

??

首先，將單個圖通過一個兩層 GCN，得到節點層面的表征 H，其大小為 n×v，然后根據上圖中的 S 計算自注意力。在經過一個 softmax 函數之后，會得到一個具有 r 個頭的多頭自注意分數，其大小為 r×n。然后，如果我們將這些分數應用到節點層面的表征，我們就會得到大小固定為 r×v 的矩陣。SAGE 有三大優勢：1）其大小因自注意力而保持不變，2）因為 GCN 平滑而具有排列不變性，3）因為自注意力而能使用節點重要度。

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

??

另外，我們還使用了主動學習來解決樣本數量少的問題。我們使用了分歧損失來為外部標注選擇實例。有關這兩種算法 SEAL-AI 和 SEAL-CI 的詳情以及相關實驗結果請查閱論文。

?

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

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

? ? ? ? ? ? ? ? ? ? ? ?

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

??

我們在 Twitter15、Twitter16、Weibo 三個常用基準上的實驗研究對這一方法的效果進行驗證，結果表明新方法具有顯著更優的表現。

此外，我們還評估了謠言的早期偵測，此時僅給出謠言樹上非常有限的節點并且還設置了一個偵測截止時間，結果表明基于圖的方法非常適用于早期發現謠言。

2、用于醫療影像的 GNN

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

生存分析的目標是預測特定事件發生的風險，這類事件包括器官衰竭、藥物不良反應和死亡。有效的分析結果具有重要的臨床應用價值。但實際操作時卻面臨著許多困難。

首先，全切片病理圖像（WSI）分析是一個需要大量計算的過程，因為單張 WSI 的數據量就超過 0.5 GB，而且其中包含數百萬個細胞，還涉及局部特征和全局特征，因此非常復雜。另外，如何將 WSI 的拓撲特征用于生存分析也還是一個有待解決的問題。

為此，我們提出將 WSI 建模成圖，然后開發了一種圖卷積神經網絡（Graph CNN），其使用了注意力機制，可通過提供 WSI 的最優圖表征來實現更好的生存分析。

?

實驗結果表明，這種新方法優于之前的其它方法。

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

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

總結和展望

在這次課程個「圖深度學習：基礎、進展和應用」中，我們介紹了圖神經網絡的發展歷史、包括圖神經網絡的表達能力、深度、大規模擴展、自監督/無監督學習等方面的研究進展，也簡要介紹了騰訊 AI Lab 在圖神經網絡的社交網絡和醫療影像應用方面的一些初步成果。

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

總結

以上是生活随笔為你收集整理的腾讯AI Lab联合清华，港中文长文解析图深度学习的历史、最新进展到应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。