騰訊AI Lab聯合清華、港中文，萬字解讀圖深度學習歷史、最新進展與應用（1）

前言

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

在今年的計算機協會國際數據挖掘與知識發現大會（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）也可稱為「關系圖」或「圖譜」，是一種可用于描述事物之間的關系的結構。圖的基本構成元素為頂點和連接頂點的邊。根據邊是否存在方向的性質，還可分為有向圖和無向圖。一般而言，我們通?？蓪D表示成點和連接點的線的形式，這有助于我們更直觀地理解，如下圖所示：

但為便于計算機處理，我們也可用矩陣來表示圖。比如如果定義當 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 變體之間的關系：