機器之心發布
機器之心編輯部
本文將分圖神經網絡歷史、圖神經網絡的最新研究進展和圖神經網絡的應用進展三大部分歸納總結該課程 Theme II: Advances and Applications 部分的核心內容。作者包括騰訊榮鈺、徐挺洋、黃俊洲，清華大學黃文炳，香港中文大學程鴻。
人工智慧領域近幾年曆經了突飛猛進的發展。圖像、視頻、遊戲博弈、自然語言處理、金融等大數據分析領域都實現了跨越式的進步並催生了很多改變了我們日常生活的應用。近段時間，圖神經網絡成為了人工智慧領域的一大研究熱點，尤其是在社交網絡、知識圖譜、化學研究、文本分析、組合優化等領域，圖神經網絡在發掘數據中隱含關係方面的強大能力能幫助我們獲得更好的數據表達，進而能讓我們做出更好的決策。比如通過圖神經網絡梳理人類社會關係網絡的演變，可有望幫助我們理解人類社會的底層運作模式，進而讓我們離理想社會更近一步。
在今年的計算機協會國際數據挖掘與知識發現大會（ACM SIGKDD，簡稱 KDD）上，圖神經網絡備受研究關注的現狀得到了充分體現：粗略統計，今年 KDD 接收的 216 篇論文（research track）中有近 40 篇與圖神經網絡相關。也因此，一場為期一天的圖神經網絡相關課程得到了參會人員的重點關注。該聯合課程的主題為「圖深度學習：基礎、進展和應用（Deep Graph Learning: Foundations, Advances and Applications）」，由騰訊 AI Lab、清華大學、香港中文大學等機構聯合組織，從基礎的圖概念一直談到了當今最前沿的圖神經網絡研究進展。
本次課程分為兩個主題。本文將分圖神經網絡歷史、圖神經網絡的最新研究進展和圖神經網絡的應用進展三大部分歸納總結該課程 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 取值，我們可以得到不同的具體情況：
過擬合和訓練動態變化
接下來我們看看過擬合問題。過擬合是深度學習的一個常見問題，當數據點數量少而參數數量很多時，就會出現這種情況。此時模型會與訓練數據完全擬合（本質上就是記住了數據），而在驗證數據上表現很差。
訓練動態變化也是深度學習領域的一大常見問題。根據鏈式法則，當模型變深時，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》（https://arxiv.org/pdf/2008.09864.pdf）。總結一下，在這些新的理論進展的幫助下，訓練更深度 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），即我們在圖分類問題中，是否可以根據圖的標籤來推斷每個節點的標籤？子圖識別，即如何在圖中找到關鍵的子圖同時還有圖與多示例學習問題的結合形成多圖示例學習問題，以及在圖上進行攻擊與防禦相關的圖深度學習魯棒性的研究。最後，層次圖也是一個熱門的研究方向。圖神經網絡必將在人工智慧領域未來的研究和應用中扮演更重要的角色。