硬核！一文梳理經(jīng)典圖網(wǎng)絡(luò)模型

本文共2700字，建議閱讀5分鐘
今天我們就來整體梳理一些經(jīng)典常用的圖網(wǎng)絡(luò)模型：DeepWalk、GCN、Graphsage、GAT！

圖神經(jīng)網(wǎng)絡(luò)已經(jīng)在NLP、CV、搜索推薦廣告等領(lǐng)域廣泛應(yīng)用。

1. DeepWalk [2014]

DeepWalk是來解決圖里面節(jié)點(diǎn)embedding問題的。Graph Embedding技術(shù)將圖中的節(jié)點(diǎn)以低維稠密向量的形式進(jìn)行表達(dá)，要求在原始圖中相似(不同的方法對相似的定義不同)的節(jié)點(diǎn)其在低維表達(dá)空間也接近。得到的表達(dá)向量可以用來進(jìn)行下游任務(wù)，如節(jié)點(diǎn)分類(node classification)，鏈接預(yù)測(link prediction)等。

1.1 DeepWalk 算法原理

雖然DeepWalk是KDD 2014的工作，但卻是我們了解Graph Embedding無法繞過的一個(gè)方法。

我們都知道在NLP任務(wù)中，word2vec是一種常用的word embedding方法，word2vec通過語料庫中的句子序列來描述詞與詞的共現(xiàn)關(guān)系，進(jìn)而學(xué)習(xí)到詞語的向量表示。

DeepWalk的思想類似word2vec，使用圖中節(jié)點(diǎn)與節(jié)點(diǎn)的共現(xiàn)關(guān)系來學(xué)習(xí)節(jié)點(diǎn)的向量表示。那么關(guān)鍵的問題就是如何來描述節(jié)點(diǎn)與節(jié)點(diǎn)的共現(xiàn)關(guān)系，DeepWalk給出的方法是使用**隨機(jī)游走(RandomWalk)**的方式在圖中進(jìn)行節(jié)點(diǎn)采樣。

RandomWalk是一種可重復(fù)訪問visited節(jié)點(diǎn)的深度優(yōu)先遍歷算法。給定當(dāng)前訪問起始節(jié)點(diǎn)，從其鄰居中隨機(jī)采樣節(jié)點(diǎn)作為下一個(gè)訪問節(jié)點(diǎn)，重復(fù)此過程，直到訪問序列長度 = K。獲取足夠數(shù)量的節(jié)點(diǎn)訪問序列后，使用skip-gram進(jìn)行向量學(xué)習(xí)，這樣能夠把握節(jié)點(diǎn)的共現(xiàn)信息。這樣就得到了每個(gè)節(jié)點(diǎn)的embedding。

2. GCN [2016]

GCN的概念首次提出于ICLR 2017：SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS。

為什么要用GCN呢？這是因?yàn)閷τ趫D結(jié)構(gòu)的數(shù)據(jù)，CNN、RNN都無法解決。

對于圖片來說，我們用卷積核來提取特征，這是因?yàn)閳D片有平移不變性：一個(gè)小窗口無論移動(dòng)到圖片的哪一個(gè)位置，其內(nèi)部的結(jié)構(gòu)都是一模一樣的，因此CNN可以實(shí)現(xiàn)參數(shù)共享。RNN主要用在NLP這種序列信息上。圖片，或者語言，都屬于歐式空間的數(shù)據(jù)，因此才有維度的概念，歐式空間的數(shù)據(jù)的特點(diǎn)就是結(jié)構(gòu)很規(guī)則。

但是圖結(jié)構(gòu)（拓?fù)浣Y(jié)構(gòu)）如社交網(wǎng)絡(luò)、知識(shí)圖譜、分子結(jié)構(gòu)等等是十分不規(guī)則的，可以認(rèn)為是無限維的一種數(shù)據(jù)，所以它沒有平移不變性。每一個(gè)節(jié)點(diǎn)的周圍結(jié)構(gòu)可能都是獨(dú)一無二的，這種結(jié)構(gòu)的數(shù)據(jù)，就讓傳統(tǒng)的CNN、RNN瞬間失效。

GCN，圖卷積神經(jīng)網(wǎng)絡(luò)，實(shí)際上跟CNN的作用一樣，就是一個(gè)特征提取器，只不過它的對象是圖。GCN精妙地設(shè)計(jì)了一種從圖數(shù)據(jù)中提取特征的方法，從而讓我們可以使用這些特征去對圖數(shù)據(jù)進(jìn)行：

• 節(jié)點(diǎn)分類（node classification）
• 圖分類（graph classification）
• 鏈接預(yù)測（link prediction）

2.1 GCN的核心公式

假設(shè)我們手頭有一個(gè)圖，其中有N個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有自己的特征embedding，我們設(shè)這些節(jié)點(diǎn)的特征組成一個(gè)N×D維的矩陣X?，然后各個(gè)節(jié)點(diǎn)之間的關(guān)系也會(huì)形成一個(gè)N×N維的矩陣A（就是鄰接矩陣）。

GCN也是一個(gè)神經(jīng)網(wǎng)絡(luò)層，它的層與層之間的傳播方式是：

這個(gè)公式中：?

用這個(gè)公式就可以很好地提取圖的特征。假設(shè)我們構(gòu)造一個(gè)兩層的GCN，激活函數(shù)分別采用ReLU和Softmax，則整體的正向傳播的公式為：

其中，.

那么, 為什么這個(gè)公式能提取圖的特征呢？

• A+I 其實(shí)是保證對于每個(gè)節(jié)點(diǎn)，都能夠關(guān)注到其所有鄰居節(jié)點(diǎn)和自己的embedding。
• 左右乘上度矩陣D是為了對A做一個(gè)標(biāo)準(zhǔn)化處理，讓A的每一行加起來都是1。

當(dāng)然，原論文中用非常復(fù)雜的數(shù)學(xué)公式做了很多證明，由于筆者數(shù)學(xué)不好，只能如此不求甚解的來粗略理解，感興趣的同學(xué)可以自行閱讀原論文。

3. GraphSAGE

3.1. GCN的局限

GCN本身有一個(gè)局限，即沒法快速表示新節(jié)點(diǎn)。GCN需要把所有節(jié)點(diǎn)都參與訓(xùn)練（整個(gè)圖都丟進(jìn)去訓(xùn)練）才能得到node embedding，如果新node來了，沒法得到新node的embedding。所以說，GCN是transductive的。（Transductive任務(wù)是指：訓(xùn)練階段與測試階段都基于同樣的圖結(jié)構(gòu)）。

而GraphSAGE是inductive的。inductive任務(wù)是指：訓(xùn)練階段與測試階段需要處理的graph不同。通常是訓(xùn)練階段只是在子圖（subgraph）上進(jìn)行，測試階段需要處理未知的頂點(diǎn)。

要想得到新節(jié)點(diǎn)的表示，需要讓新的node或者subgraph去和已經(jīng)優(yōu)化好的node embedding去“對齊”。然而每個(gè)節(jié)點(diǎn)的表示都是受到其他節(jié)點(diǎn)的影響（牽一發(fā)而動(dòng)全身），因此添加一個(gè)節(jié)點(diǎn)，意味著許許多多與之相關(guān)的節(jié)點(diǎn)的表示都應(yīng)該調(diào)整。

3.2 GraphSAGE

針對這種問題，GraphSAGE模型提出了一種算法框架，可以很方便地得到新node的表示。

3.2.1 Embedding generation（前向傳播算法）

文中描述如下：

隨著層數(shù)K的增加，可以聚合越來越遠(yuǎn)距離的信息。這是因?yàn)椋m然每次選擇鄰居的時(shí)候就是從周圍的一階鄰居中均勻地采樣固定個(gè)數(shù)個(gè)鄰居，但是由于節(jié)點(diǎn)的鄰居也聚合了其鄰居的信息，這樣，在下一次聚合時(shí)，該節(jié)點(diǎn)就會(huì)接收到其鄰居的鄰居的信息，也就是聚合到了二階鄰居的信息了。這就像社交圖譜中“朋友的朋友”的概念。

3.2.2 聚合函數(shù)選擇

• Mean Pooling

這個(gè)比較好理解，就是當(dāng)前節(jié)點(diǎn)v本身和它所有的鄰居在k-1層的embedding的mean，然后經(jīng)過MLP+sigmoid。

• LSTM Aggregator：把當(dāng)前節(jié)點(diǎn)v的鄰居隨機(jī)打亂，輸入到LSTM中。作者的想法是說LSTM的模型capacity更強(qiáng)。但是節(jié)點(diǎn)周圍的鄰居明明是沒有順序的，這樣做似乎有不妥。
• Pooling Aggregator：

把節(jié)點(diǎn)v的所有鄰居節(jié)點(diǎn)都單獨(dú)經(jīng)過一個(gè)MLP+sigmoid得到一個(gè)向量，最后把所有鄰居的向量做一個(gè)element-wise的max-pooling。

3.2.3 GraphSAGE的參數(shù)學(xué)習(xí)

GraphSAGE的參數(shù)就是聚合函數(shù)的參數(shù)。為了學(xué)習(xí)這些參數(shù)，需要設(shè)計(jì)合適的損失函數(shù)。

對于無監(jiān)督學(xué)習(xí)，設(shè)計(jì)的損失函數(shù)應(yīng)該讓臨近的節(jié)點(diǎn)的擁有相似的表示，反之應(yīng)該表示大不相同。所以損失函數(shù)是這樣的：

其中，節(jié)點(diǎn)v是和節(jié)點(diǎn)u在一定長度的random walk上共現(xiàn)的節(jié)點(diǎn)，所以它們的點(diǎn)積要盡可能大；后面這項(xiàng)是采了Q個(gè)負(fù)樣本，它們的點(diǎn)積要盡可能小。這個(gè)loss和skip-gram中的negative sampling如出一轍。

對于有監(jiān)督學(xué)習(xí)，可以直接使用cross-entropy loss等常規(guī)損失函數(shù)。當(dāng)然，上面的這個(gè)loss也可以作為一個(gè)輔助loss。

3.3 和GCN的關(guān)系

原始GCN的方法，其實(shí)和GraphSAGE的Mean Pooling聚合方法是類似的，即每一層都聚合自己和自己鄰居的歸一化embedding表示。而GraphSAGE使用了其他capacity更大的聚合函數(shù)而已。

此外，GCN是一口氣把整個(gè)圖都丟進(jìn)去訓(xùn)練，但是來了一個(gè)新的節(jié)點(diǎn)就不免又要把整個(gè)圖重新訓(xùn)一次。而GraphSAGE則是在增加了新的節(jié)點(diǎn)之后，來增量更新舊的節(jié)點(diǎn)，調(diào)整整張圖的embedding表示。只是生成新節(jié)點(diǎn)embedding的過程，實(shí)施起來相比于GCN更加靈活方便了。

4. GAT (Graph Attention Network)

4.1 GAT的具體做法

對于每個(gè)節(jié)點(diǎn)，注意力其在鄰居頂點(diǎn)上的注意力。對于頂點(diǎn) ,逐個(gè)計(jì)算它的鄰居們和它自己之間的相似系數(shù)：

首先一個(gè)共享參數(shù)?的線性映射對于頂點(diǎn)的特征進(jìn)行了增維，當(dāng)然這是一種常見的特征增強(qiáng)（feature augment）方法；之后，對變換后的特征進(jìn)行了拼接（concatenate）；最后 a(·)把拼接后的高維特征映射到一個(gè)實(shí)數(shù)上，作者是通過單層的MLP來實(shí)現(xiàn)的。

然后，再對此相關(guān)系數(shù)用softmax做歸一化：

最后，根據(jù)計(jì)算好的注意力系數(shù)，把特征加權(quán)求和一下。這也是一種aggregation，只是和GCN不同，這個(gè)aggregation是帶注意力權(quán)重的。

就是輸出的節(jié)點(diǎn)的embedding，融合了其鄰居和自身帶注意力的權(quán)重（這里的注意力是self-attention）。

為了增強(qiáng)特征提取能力，用multi-head attention來進(jìn)化增強(qiáng)一下：

4.2 與GCN的聯(lián)系

GCN與GAT都是將鄰居頂點(diǎn)的特征聚合到中心頂點(diǎn)上（一種aggregate運(yùn)算）。不同的是GCN利用了拉普拉斯矩陣，GAT利用attention系數(shù)。一定程度上而言，GAT會(huì)更強(qiáng)，因?yàn)?頂點(diǎn)特征之間的相關(guān)性被更好地融入到模型中。

GAT適用于有向圖。這是因?yàn)镚AT的運(yùn)算方式是逐頂點(diǎn)的運(yùn)算（node-wise），每一次運(yùn)算都需要循環(huán)遍歷圖上的所有頂點(diǎn)來完成。逐頂點(diǎn)運(yùn)算意味著，擺脫了拉普利矩陣的束縛，使得有向圖問題迎刃而解。也正因如此，GAT適用于inductive任務(wù)。與此相反的是，GCN是一種全圖的計(jì)算方式，一次計(jì)算就更新全圖的節(jié)點(diǎn)特征。

編輯：于騰凱

校對：林亦霖