前言

人工智能領(lǐng)域近幾年歷經(jīng)了突飛猛進(jìn)的發(fā)展。圖像、視頻、游戲博弈、自然語言處理、金融等大數(shù)據(jù)分析領(lǐng)域都實現(xiàn)了跨越式的進(jìn)步并催生了很多改變了我們?nèi)粘Ｉ畹膽?yīng)用。近段時間，圖神經(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ī)協(xié)會國際數(shù)據(jù)挖掘與知識發(fā)現(xiàn)大會（ACM SIGKDD，簡稱 KDD）上，圖神經(jīng)網(wǎng)絡(luò)備受研究關(guān)注的現(xiàn)狀得到了充分體現(xiàn)：粗略統(tǒng)計，今年 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)展。

本次課程分為兩個主題。本文將分圖神經(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īng)網(wǎng)絡(luò)，無監(jiān)督圖學(xué)習(xí)，圖的對抗攻擊，圖的樣本學(xué)習(xí)等。在未來我們將探索圖深度學(xué)習(xí)在廣泛場景的應(yīng)用，如社交推薦，****物研發(fā)等。使其能夠真正造福人類。

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

1.什么是圖？

漢語中的「圖」可以對應(yīng)成英語中多個不同的詞：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ī)處理，我們也可用矩陣來表示圖。比如如果定義當(dāng) v_i 與 v_j 相連時，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 的實現(xiàn)方面，目前最常用的方法是消息傳遞框架（Message Passing Framework）。簡單總結(jié)起來，該框架分為兩個步驟。

第一步是消息生成步驟。首先，從近鄰節(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ù)用于圖的深度學(xué)習(xí)工具包大都采用了這一框架，比如 Deep Graph Library 和 PyTorch Geometric。

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

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

在第一個階段，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ù)量也迅猛增長。

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

我們現(xiàn)在正處于 GNN 發(fā)展的第三個階段。圖卷積已經(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í)的門來建模每個頭的重要度）、譜式圖注意力網(wǎng)絡(luò)（將注意力應(yīng)用于譜域中的高/低頻組件）。

●  圖池化：SAGE（自注意圖嵌入，在池化時使用自注意力來建模節(jié)點(diǎn)重要度）、通過圖剪切實現(xiàn)圖池化（通過圖剪切算法得到的預(yù)訓(xùn)練子圖實現(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（使用了歸一化的多階鄰接矩陣，然后匯集各階的輸出，從而同時得到高階和低階的相近度）、APPNP（使用了個性化 PageRank 來為目標(biāo)節(jié)點(diǎn)構(gòu)建更好的近鄰關(guān)系）。

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