前言

人工智能領(lǐng)域近幾年歷經(jīng)了突飛猛進(jìn)的發(fā)展。圖像、視頻、游戲博弈、自然語(yǔ)言處理、金融等大數(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ò)、知識(shí)圖譜、化學(xué)研究、文本分析、組合優(yōu)化等領(lǐng)域，圖神經(jīng)網(wǎng)絡(luò)在發(fā)掘數(shù)據(jù)中隱含關(guān)系方面的強(qiáng)大能力能幫助我們獲得更好的數(shù)據(jù)表達(dá)，進(jìn)而能讓我們做出更好的決策。比如通過(guò)圖神經(jīng)網(wǎng)絡(luò)梳理人類社會(huì)關(guān)系網(wǎng)絡(luò)的演變，可有望幫助我們理解人類社會(huì)的底層運(yùn)作模式，進(jìn)而讓我們離理想社會(huì)更近一步。

在今年的計(jì)算機(jī)協(xié)會(huì)國(guó)際數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)大會(huì)（ACM SIGKDD，簡(jiǎn)稱 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)。也因此，一場(chǎng)為期一天的圖神經(jīng)網(wǎng)絡(luò)相關(guān)課程得到了參會(huì)人員的重點(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)性的問(wè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ù)挖掘頂級(jí)會(huì)議上發(fā)表多篇文章，涉及大圖計(jì)算，超深圖神經(jīng)網(wǎng)絡(luò)，無(wú)監(jiān)督圖學(xué)習(xí)，圖的對(duì)抗攻擊，圖的樣本學(xué)習(xí)等。在未來(lái)我們將探索圖深度學(xué)習(xí)在廣泛場(chǎng)景的應(yīng)用，如社交推薦，****物研發(fā)等。使其能夠真正造福人類。

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

1.什么是圖？

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

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

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

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

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

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

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

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

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

目前大多數(shù)空間式 GNN 都可以構(gòu)建為某種消息傳遞過(guò)程，而且事實(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é)起來(lái)，GNN 的發(fā)展過(guò)程大致可分為三個(gè)階段。

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

在第二個(gè)階段，卷積被引入到了 GNN 的工作流程中。當(dāng)用矩陣進(jìn)行表示時(shí)，圖與卷積擅長(zhǎng)處理的圖像具有很多相似性，也因此開啟了在 GNN 中使用卷積的時(shí)代。一系列的工作將在譜空間上的圖卷積轉(zhuǎn)換為了拓?fù)淇臻g上的近似，并在此基礎(chǔ)上于 2017 年誕生了圖卷積網(wǎng)絡(luò)（GCN），其首次使用了逐層卷積來(lái)擴(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 算法來(lái)獲取圖拉普拉斯的低秩近似）、圖小波神經(jīng)網(wǎng)絡(luò)（使用小波變換替代傅里葉變換）、雙曲 GCN（將 GCN 構(gòu)建到雙曲空間中）。

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

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

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

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