引言

本文為GNN教程的第三篇文章 【GraghSAGE算法】，在GCN的博文中我們重點(diǎn)討論了圖神經(jīng)網(wǎng)絡(luò)的逐層傳播公式是如何推導(dǎo)的，然而，GCN的訓(xùn)練方式需要將鄰接矩陣和特征矩陣一起放到內(nèi)存或者顯存里，在大規(guī)模圖數(shù)據(jù)上是不可取的。 其次，GCN在訓(xùn)練時(shí)需要知道整個(gè)圖的結(jié)構(gòu)信息(包括待預(yù)測(cè)的節(jié)點(diǎn)), 這在現(xiàn)實(shí)某些任務(wù)中也不能實(shí)現(xiàn)(比如用今天訓(xùn)練的圖模型預(yù)測(cè)明天的數(shù)據(jù)，那么明天的節(jié)點(diǎn)是拿不到的)。GraphSAGE的出現(xiàn)就是為了解決這樣的問(wèn)題，這篇博文中我們將會(huì)詳細(xì)得討論它。

一、Inductive learning v.s. Transductive learning

首先我們介紹一下什么是inductive learning。與其他類型的數(shù)據(jù)不同，圖數(shù)據(jù)中的每一個(gè)節(jié)點(diǎn)可以通過(guò)邊的關(guān)系利用其他節(jié)點(diǎn)的信息，這樣就產(chǎn)生了一個(gè)問(wèn)題，如果訓(xùn)練集上的節(jié)點(diǎn)通過(guò)邊關(guān)聯(lián)到了預(yù)測(cè)集或者驗(yàn)證集的節(jié)點(diǎn)，那么在訓(xùn)練的時(shí)候能否用它們的信息呢? 如果訓(xùn)練時(shí)用到了測(cè)試集或驗(yàn)證集樣本的信息(或者說(shuō)，測(cè)試集和驗(yàn)證集在訓(xùn)練的時(shí)候是可見(jiàn)的), 我們把這種學(xué)習(xí)方式叫做transductive learning, 反之，稱為inductive learning。

顯然，我們所處理的大多數(shù)機(jī)器學(xué)習(xí)問(wèn)題都是inductive learning, 因?yàn)槲覀兛桃獾膶颖炯譃橛?xùn)練/驗(yàn)證/測(cè)試，并且訓(xùn)練的時(shí)候只用訓(xùn)練樣本。然而，在GCN中，訓(xùn)練節(jié)點(diǎn)收集鄰居信息的時(shí)候，用到了測(cè)試或者驗(yàn)證樣本，所以它是transductive的。

二、概述

GraphSAGE是一個(gè)inductive框架，在具體實(shí)現(xiàn)中，訓(xùn)練時(shí)它僅僅保留訓(xùn)練樣本到訓(xùn)練樣本的邊。inductive learning 的優(yōu)點(diǎn)是可以利用已知節(jié)點(diǎn)的信息為未知節(jié)點(diǎn)生成Embedding. GraphSAGE 取自 Graph SAmple and aggreGatE, SAmple指如何對(duì)鄰居個(gè)數(shù)進(jìn)行采樣。aggreGatE指拿到鄰居的embedding之后如何匯聚這些embedding以更新自己的embedding信息。下圖展示了GraphSAGE學(xué)習(xí)的一個(gè)過(guò)程：

對(duì)鄰居采樣

采樣后的鄰居embedding傳到節(jié)點(diǎn)上來(lái)，并使用一個(gè)聚合函數(shù)聚合這些鄰居信息以更新節(jié)點(diǎn)的embedding

根據(jù)更新后的embedding預(yù)測(cè)節(jié)點(diǎn)的標(biāo)簽

三、算法細(xì)節(jié)

3.1 節(jié)點(diǎn) Embedding 生成(即：前向傳播)算法

這一節(jié)討論的是如何給圖中的節(jié)點(diǎn)生成(或者說(shuō)更新)embedding, 假設(shè)我們已經(jīng)完成了GraphSAGE的訓(xùn)練，因此模型所有的參數(shù)(parameters)都已知了。具體來(lái)說(shuō)，這些參數(shù)包括個(gè)聚合器(見(jiàn)下圖算法第4行)中的參數(shù), 這些聚合器被用來(lái)將鄰居embedding信息聚合到節(jié)點(diǎn)上，以及一系列的權(quán)重矩陣(下圖算法第5行), 這些權(quán)值矩陣被用作在模型層與層之間傳播embedding的時(shí)候做非線性變換。

下面的算法描述了我們是怎么做前向傳播的：

算法的主要部分為：

(line 1)初始化每個(gè)節(jié)點(diǎn)embedding為節(jié)點(diǎn)的特征向量

(line 3)對(duì)于每一個(gè)節(jié)點(diǎn)

(line 4)拿到它采樣后的鄰居的embedding并將其聚合，這里表示對(duì)鄰居采樣

(line 5)根據(jù)聚合后的鄰居embedding()和自身embedding()通過(guò)一個(gè)非線性變換()更新自身embedding.

算法里的這個(gè)比較難理解，下面單獨(dú)來(lái)說(shuō)他，之前提到過(guò)，它既是聚合器的數(shù)量，也是權(quán)重矩陣的數(shù)量，還是網(wǎng)絡(luò)的層數(shù)，這是因?yàn)槊恳粚泳W(wǎng)絡(luò)中聚合器和權(quán)重矩陣是共享的。

網(wǎng)絡(luò)的層數(shù)可以理解為需要最大訪問(wèn)到的鄰居的跳數(shù)(hops)，比如在figure 1中，紅色節(jié)點(diǎn)的更新拿到了它一、二跳鄰居的信息，那么網(wǎng)絡(luò)層數(shù)就是2。

為了更新紅色節(jié)點(diǎn)，首先在第一層()我們會(huì)將藍(lán)色節(jié)點(diǎn)的信息聚合到紅色節(jié)點(diǎn)上，將綠色節(jié)點(diǎn)的信息聚合到藍(lán)色節(jié)點(diǎn)上。在第二層()紅色節(jié)點(diǎn)的embedding被再次更新，不過(guò)這次用的是更新后的藍(lán)色節(jié)點(diǎn)embedding，這樣就保證了紅色節(jié)點(diǎn)更新后的embedding包括藍(lán)色和綠色節(jié)點(diǎn)的信息。

3.2 采樣 (SAmple) 算法

GraphSAGE采用了定長(zhǎng)抽樣的方法，具體來(lái)說(shuō)，定義需要的鄰居個(gè)數(shù), 然后采用有放回的重采樣/負(fù)采樣方法達(dá)到,。保證每個(gè)節(jié)點(diǎn)(采樣后的)鄰居個(gè)數(shù)一致是為了把多個(gè)節(jié)點(diǎn)以及他們的鄰居拼成Tensor送到GPU中進(jìn)行批訓(xùn)練。

3.3 聚合器 (Aggregator) 架構(gòu)

GraphSAGE 提供了多種聚合器，實(shí)驗(yàn)中效果最好的平均聚合器(mean aggregator)，平均聚合器的思慮很簡(jiǎn)單，每個(gè)維度取對(duì)鄰居embedding相應(yīng)維度的均值，這個(gè)和GCN的做法基本一致(GCN實(shí)際上用的是求和)：

舉個(gè)簡(jiǎn)單例子，比如一個(gè)節(jié)點(diǎn)的3個(gè)鄰居的embedding分別為 ，按照每一維分別求均值就得到了聚合后的鄰居embedding為.

論文中還闡述了另外兩種aggregator:LSTM aggregator和Pooling aggregator, 有興趣的可以去論文中看下。

3.4 參數(shù)學(xué)習(xí)

到此為止，整個(gè)模型的架構(gòu)就講完了，那么GraphSAGE是如何學(xué)習(xí)聚合器的參數(shù)以及權(quán)重變量的呢? 在有監(jiān)督的情況下，可以使用每個(gè)節(jié)點(diǎn)的預(yù)測(cè)label和真實(shí)label的交叉熵作為損失函數(shù)。在無(wú)監(jiān)督的情況下，可以假設(shè)相鄰的節(jié)點(diǎn)的輸出embeding應(yīng)當(dāng)盡可能相近，因此可以設(shè)計(jì)出如下的損失函數(shù)：

其中是節(jié)點(diǎn)的輸出embedding,是節(jié)點(diǎn)的鄰居(這里鄰居是廣義的，比如說(shuō)如果和在一個(gè)定長(zhǎng)的隨機(jī)游走中可達(dá)，那么我們也認(rèn)為他們相鄰)，是負(fù)采樣分布，是負(fù)采樣的樣本數(shù)量，所謂負(fù)采樣指我們還需要一批不是鄰居的節(jié)點(diǎn)作為負(fù)樣本，那么上面這個(gè)式子的意思是相鄰節(jié)點(diǎn)的embedding的相似度盡量大的情況下保證不相鄰節(jié)點(diǎn)的embedding的期望相似度盡可能小。

四、后話

GraphSAGE采用了采樣的機(jī)制，克服了GCN訓(xùn)練時(shí)內(nèi)存和顯存上的限制，使得圖模型可以應(yīng)用到大規(guī)模的圖結(jié)構(gòu)數(shù)據(jù)中，是目前幾乎所有工業(yè)上圖模型的雛形。然而，每個(gè)節(jié)點(diǎn)這么多鄰居，采樣能否考慮到鄰居的相對(duì)重要性呢，或者我們?cè)诰酆嫌?jì)算中能否考慮到鄰居的相對(duì)重要性? 這個(gè)問(wèn)題在我們的下一篇博文Graph Attentioin Networks中做了詳細(xì)的討論。

責(zé)任編輯：lq