點擊上方“小白學(xué)視覺”，選擇加"星標(biāo)"或“置頂”

重磅干貨，第一時間送達

圖神經(jīng)網(wǎng)絡(luò)（GNN）是一類近年來逐漸興起的機器學(xué)習(xí)模型，它被用于學(xué)習(xí)圖結(jié)構(gòu)的數(shù)據(jù)。GNN 已經(jīng)被成功地應(yīng)用于對各種不同領(lǐng)域（包括社會科學(xué)、計算機視覺和圖形學(xué)、粒子物理學(xué)、化學(xué)、醫(yī)學(xué)等）的關(guān)系和交互的系統(tǒng)進行建模。

直到最近，該領(lǐng)域內(nèi)大多數(shù)的研究仍重點關(guān)注于研發(fā)新型 GNN 模型，并且在小型圖（例如，僅僅包含大約 5K 節(jié)點的引用網(wǎng)絡(luò) Cora 仍然被廣泛使用）上測試這些模型；相對來說，處理大規(guī)模應(yīng)用的研究工作鮮有人涉足。

另一方面，工業(yè)界的實際問題往往需要處理超大規(guī)模的圖（例如，包含數(shù)百萬節(jié)點、數(shù)十億條邊的 Twitter 或 Facebook 的社交網(wǎng)絡(luò)）。

大多數(shù)現(xiàn)有的文獻中描述的方法在這樣的大規(guī)模應(yīng)用場景下并不適用。

簡而言之，GNN 通過聚合局部鄰居節(jié)點的特征來進行操作。當(dāng)下流行的圖卷積網(wǎng)絡(luò)（GCN）模型通過將 d 維節(jié)點特征組織在一個 n×d 的矩陣 X 中（其中，n 代表節(jié)點的個數(shù)），在圖上實現(xiàn)了一種最簡單的類似于卷積的操作，它將節(jié)點層面上的變換與相鄰節(jié)點之間的特征傳遞融合了起來。

Y = ReLU(AXW).

在這里，W 是各節(jié)點之間共享的可學(xué)習(xí)的矩陣，A 是一個線性傳播算子，相當(dāng)于鄰居節(jié)點特征的加權(quán)平均。正如在傳統(tǒng)的卷積神經(jīng)網(wǎng)絡(luò)（CNN）中一樣，我們可以將多層堆疊的這種形式應(yīng)用在序列中。

GNN 可以被設(shè)計用于在節(jié)點層面上（例如，檢測社交網(wǎng)絡(luò)中的惡意用戶）、邊的層面上（例如，推薦系統(tǒng)中典型的場景——鏈接預(yù)測）、或整個圖的層面上（例如，預(yù)測分子圖的化學(xué)性質(zhì)）進行預(yù)測。例如，我們可以使用如下所示的雙層 GCN 執(zhí)行節(jié)點級別的分類任務(wù)：

Y = softmax(A ReLU(AXW)W’).

為什么擴展圖神經(jīng)網(wǎng)絡(luò)十分具有挑戰(zhàn)性呢？

在上述節(jié)點級別的預(yù)測問題中，GNN 會在樣本節(jié)點上進行訓(xùn)練。

在傳統(tǒng)的機器學(xué)習(xí)環(huán)境下，通常假設(shè)樣本是以統(tǒng)計上相獨立的方式從某個分布中采樣得到的。反過來，這樣就可以將損失函數(shù)分解為獨立樣本的貢獻，并采用隨機優(yōu)化技術(shù)。

然而，圖中的節(jié)點是通過邊相互關(guān)聯(lián)的，這使得訓(xùn)練集中的樣本在統(tǒng)計意義上相互依賴。此外，由于節(jié)點之間的統(tǒng)計依賴性，采樣過程可能會引入偏置。

例如，這可能使得一些節(jié)點或邊在訓(xùn)練集中比其它節(jié)點或邊出現(xiàn)得更頻繁，而我們需要恰當(dāng)?shù)貞?yīng)對這種「副作用」。

最后，同樣重要的是，我們需要保證采樣得到的子圖能夠保留 GNN 可以利用的有意義的結(jié)構(gòu)。

在許多早期的圖神經(jīng)網(wǎng)絡(luò)工作中，并未考慮上述問題：諸如 GCN（圖卷積網(wǎng)絡(luò)）、ChebNet、MoNet 和 GAT 等網(wǎng)絡(luò)架構(gòu)都是使用全批量梯度下降（full-batch gradient descent）算法訓(xùn)練的。

這使我們必須在內(nèi)存中維持全部圖的鄰接矩陣以及節(jié)點特征。因此，一個 L 層的 GCN 模型就具有了 O(Lnd2) 的時間復(fù)雜度和 O(Lnd +Ld2) 的空間復(fù)雜度，即使對于大小適度的圖來說，這也是無法接受的。

GraphSAGE 是研究圖神經(jīng)網(wǎng)路的可擴展性問題的第一項工作，它是 Will Hamilton 等人撰寫的奠基性論文。GraphSAGE 將鄰居節(jié)點采樣與 mini-batch 訓(xùn)練結(jié)合了起來，從而在大規(guī)模圖上訓(xùn)練 GNN（「SAGE」指的是「采樣與聚合」）。

該論文的核心思想是，為了用一個 L 層的 GCN  計算某個節(jié)點上的訓(xùn)練損失，只需要聚合該節(jié)點 L 跳之內(nèi)鄰居節(jié)點的信息，而在計算中不考慮圖中更遠(yuǎn)一些的節(jié)點。

但問題在于，對于這種符合「小世界」模型的圖（例如社交網(wǎng)絡(luò)），由某些節(jié)點 2 跳內(nèi)的鄰居組成的子圖可能就已經(jīng)包含數(shù)百萬的節(jié)點了，這使得我們很難將其存儲在內(nèi)存中。

GraphSAGE 通過至多對 L 跳的鄰居進行采樣來解決該問題：從正在訓(xùn)練的節(jié)點開始，該算法多次有放回地均勻采樣 k 個 1 跳鄰居；接著，對于每一個該節(jié)點的鄰居節(jié)點，算法以相同的方式再采樣 k 個鄰居節(jié)點，以此迭代式地采樣 L 次。通過這種方式，我們保證對于每個節(jié)點而言，可以聚合有界的 L 跳規(guī)模為 O(k?) 的采樣鄰居節(jié)點。

如果我們使用 b 個訓(xùn)練節(jié)點構(gòu)建一個 batch，且每個節(jié)點的 L 跳鄰居節(jié)點相互獨立，那么我們就會得到與圖的規(guī)模 n 無關(guān)的空間復(fù)雜度 O(bk?)。使用 GraphSAGE 算法時，一個 batch 的計算復(fù)雜度為 O(bLd2k?)。

圖 1：GraphSAGE 的鄰居節(jié)點采樣過程。我們從完整的圖中下采樣得到包含 b 個節(jié)點的 batch （在本例中，b=2，我們將紅色和淡黃色的節(jié)點用于訓(xùn)練）。在右側(cè)的圖中，我們采樣得到 2 跳鄰居節(jié)點圖，將其用于獨立地計算紅色和淡黃色節(jié)點的圖嵌入和損失。

GraphSAGE 有一個顯著的缺點，即采樣得到的節(jié)點可能會出現(xiàn)很多次（由于有放回的抽樣），因此可能會引入大量冗余的計算。例如，在上圖中，深綠色的節(jié)點在兩個訓(xùn)練節(jié)點的 L 跳鄰居中都出現(xiàn)了。因此，在一個 batch 中，該深綠色節(jié)點的嵌入會被計算兩次。

隨著 batch 大小 b 和采樣節(jié)點個數(shù) k 的增長，冗余計算的規(guī)模也會增大。此外，對于每個 batch 而言，盡管擁有 O(bk?) 的空間復(fù)雜度，但只會利用 b 個節(jié)點計算損失函數(shù)。因此，從某種程度上說，對于其它節(jié)點的計算也是一種浪費。 

在 GraphSAGE 之后，許多后續(xù)的工作重點關(guān)注改進 mini-batch 的采樣過程，從而減少 GraphSAGE 中的冗余計算，并使得每個 batch 更加高效。

ClusterGCN 和 GraphSAINT 是該研究方向最新的工作，它們采用了「圖采樣」（與 GraphSAGE 的鄰居節(jié)點采樣相對應(yīng)）技術(shù)。

在圖采樣方法中，我們在每一個 batch 中采樣得到原始圖的一個子圖，然后在整個子圖上運行類似于 GCN 的模型。在這里，我們面臨的挑戰(zhàn)是，需要保證這些子圖保留了大多數(shù)原始的邊，并且能展現(xiàn)出有意義的拓?fù)浣Y(jié)構(gòu)。

為了實現(xiàn)上述目標(biāo)，ClusterGCN 首先對圖進行了聚類；然后，在每一個 batch 中，該模型會在一個聚類上進行訓(xùn)練。這使得每個 batch 中的節(jié)點會聯(lián)系得盡可能的緊密。

GraphSAINT 則提出了一種通用的概率化的圖采樣器，它通過在原始的圖中采樣子圖來構(gòu)建用于訓(xùn)練的 batch。

我們可以根據(jù)不同的方案設(shè)計圖采樣器：例如，該采樣器可以執(zhí)行均勻節(jié)點采樣、均勻邊采樣，或者通過使用隨機游走計算節(jié)點的重要性、將其用于采樣的概率分布從而進行「重要性采樣」。

請注意，進行采樣的好處之一是：在訓(xùn)練時，采樣可以作為一種邊級別上的「dropout」技術(shù)，它可以對模型進行正則化，從而提升模型的性能。然而，在推理時，邊 dropout 仍然需要看到所有的邊，而在上述方法中，我們這些無法獲得這些邊的信息。

圖采樣技術(shù)的另一個影響是，它可以減少在鄰居節(jié)點指數(shù)級增長的情況下，存在的「信息瓶頸」及其造成的「過度擠壓」現(xiàn)象。

在我們與 Ben Chamberlian、Davide Eynard 以及 Federico Monti 等人聯(lián)合發(fā)表的論文 “SIGN: Scalable Inception Graph Neural Networks” 中，我們研究了為節(jié)點級分類問題設(shè)計簡單、與采樣無關(guān)的架構(gòu)的可能性。

考慮到上文介紹的采樣技術(shù)的間接好處，讀者可能會問：為什么我們要摒棄采樣策略呢？

原因如下：節(jié)點分類問題的實例之間可能存在顯著的差異，據(jù)我們所知，至今還沒有工作系統(tǒng)地研究了「何時采樣」能真正起到積極的作用，而不是僅僅減輕了計算復(fù)雜度。

對采樣方案的實現(xiàn)引入了額外的復(fù)雜性，而我們相信，我們需要的是一種簡單、強大、與采樣無關(guān)、可擴展的基線架構(gòu)

方法探究 

  

我們的方法受到了一些近期發(fā)布的實驗結(jié)果的啟發(fā)。首先，在很多情況下，簡單的固定的信息聚合器（例如 GCN）比一些更加復(fù)雜的信息聚合器（例如，GAT 和 MPNN）性能更好。

此外，盡管深度學(xué)習(xí)的成功是建立在擁有多層的模型之上的，但是在圖深度學(xué)習(xí)領(lǐng)域中，「模型是否需要很深」仍然是一個有待解決的開放性問題。

具體而言，Wu 等人在論文「Simplifying Graph Convolutional Networks」中指出，只擁有一個多跳信息傳播層的 GCN 模型可以擁有與具有多個信息傳播層的模型相當(dāng)?shù)男阅堋?/span>

通過在單個卷積層中組合不同的、固定的鄰居節(jié)點聚合器，我們可以在不使用圖采樣技術(shù)的前提下，得到具有非常大的可擴展性的模型。換句話說，我們在該架構(gòu)的第一層進行所有與圖相關(guān)的（固定的）操作，因此這些操作可以被預(yù)計算。

接下來，這些預(yù)先聚合的信息可以作為模型其它部分的輸入，而由于缺少鄰居節(jié)點的信息聚合，這些部分可以被歸納為一個多層感知機（MLP）。

需要指出的是，即使我們使用了這么淺的卷積方案，通過采用一些（可能專用的、更復(fù)雜的）信息傳播算子，我們?nèi)匀荒鼙Ａ魣D卷積操作的表達能力。例如，我們可以設(shè)計一些算子來考慮「局部子圖計數(shù)」或圖中的模體（motif）。

圖 2：SIGN 架構(gòu)包含一個類似于 GCN 的層，它帶有多個線性傳播算子，這些算子可能作用于多跳鄰居節(jié)點。在這個層后面，會連接著一個面向節(jié)點級別應(yīng)用的多層感知機。該架構(gòu)之所以具有較高的計算效率，是由于對被傳播的特征的預(yù)計算（如圖中紅色部分所示）。

我們提出的可擴展架構(gòu)被稱為 SIGN，它面向的是如下所示的節(jié)點級分類任務(wù)：

Y = softmax(ReLU(XW? | A?XW? | A?XW? | … | A?XW?) W’)

其中，A? 是線性傳播矩陣（例如一個正則化的鄰接矩陣，它的冪，或者一個模體矩陣）。W? 和 W’ 是可學(xué)習(xí)的參數(shù)。如圖 2 所示，該網(wǎng)絡(luò)可以通過加入面向節(jié)點的層變得更深：

Y = softmax(ReLU(…ReLU(XW? | A?XW? | … | A?XW?) W’)… W’’)

最后，當(dāng)我們對相同的傳播算子應(yīng)用不同的冪（例如，A?=B1, A?=B2，等等）時，圖操作有效地在越來越遠(yuǎn)的跳中聚合了來自鄰居節(jié)點的信息，這類似于在相同的網(wǎng)絡(luò)層中感受野不同的卷積核。

在這里，與經(jīng)典的卷積神經(jīng)網(wǎng)絡(luò)中「Inception」模塊的類比，解釋了我們提出的論文的名字 SIGN 的由來。 

如前文所述，上述等式中矩陣的積 A?X,…, A?X 并不依賴可學(xué)習(xí)的模型參數(shù)，因此可以被預(yù)計算。具體而言，對于規(guī)模超大的圖來說，我們可以使用 Apache Spark 等分布式計算架構(gòu)高效地擴展這種預(yù)計算過程。

這種做法有效地將整體模型的計算復(fù)雜度降低到了與多層感知機相同的水平上。此外，通過將信息傳播過程轉(zhuǎn)移到預(yù)計算步驟中，我們可以聚合來自所有鄰居節(jié)點的信息，從而避免采樣過程及其可能帶來的信息損失與偏置。

SIGN 主要的優(yōu)點在于其可擴展性與效率，我們可以使用標(biāo)準(zhǔn)的 mini-batch 梯度下降方法訓(xùn)練它。

我們發(fā)現(xiàn)，在保持與目前最先進的 GraphSAINT 模型準(zhǔn)確率非常接近的條件下，在推理階段，SIGN 的運算速度比 ClusterGCN 和 GraphSAINT 要快兩個數(shù)量級；而在訓(xùn)練階段，SIGN 也要比它們快得多。

圖 3：在 OGBN-Product 數(shù)據(jù)集上，不同方法的收斂情況。SIGN 的各種變體都要比GraphSAINT 和 ClusterGCN 收斂地更快，并且能夠在驗證中得到更高的 F1 分?jǐn)?shù)。     

圖 4：在 OGBN-Product 數(shù)據(jù)集上，不同方法的預(yù)處理、訓(xùn)練、推理時間（單位：秒）。盡管 SIGN 的預(yù)處理過程較為緩慢，但是 SIGN 在訓(xùn)練階段要比對比基線快得多，并且在推理階段要比其它方法快上近兩個數(shù)量級。

此外，我們的模型也支持任意的傳播算子。對于不同類型的圖而言，也許我們必須處理不同的傳播算子。

我們發(fā)現(xiàn)，有一些任務(wù)可以獲益于基于模體的算子（如三角形計數(shù)）。

圖 5：在一些流行的數(shù)據(jù)集上，SIGN 模型以及其它可擴展方法在節(jié)點分類任務(wù)中的性能?；谌悄ｓw的傳播算子在 Flickr 數(shù)據(jù)集上取得了較大的性能提升，在 PPI 和 Yelp 數(shù)據(jù)集上也有一定的性能提升。

盡管受限于只擁有單個圖卷積層，以及只使用了線性傳播算子，SIGN 實際上可以良好運行，取得了與更加復(fù)雜的模型相當(dāng)、甚至更好的性能。由于 SIGN 具有很快的運算速度并且易于實現(xiàn)，我們期待 SIGN 成為一種大規(guī)模應(yīng)用的圖學(xué)習(xí)方法的簡單對比基線。

也許，更重要的是，由于這種簡單的模型取得了成功，我們不禁要提出一個更本質(zhì)的問題：「我們真的需要深度的圖神經(jīng)網(wǎng)絡(luò)嗎」？

我們推測，在許多面向社交網(wǎng)絡(luò)以及「小世界」圖的學(xué)習(xí)問題中，我們需要使用更為豐富的局部結(jié)構(gòu)信息，而不是使用暴力的深度架構(gòu)。

有趣的是，由于算力的進步以及將較為簡單的特征組合為復(fù)雜特征的能力，傳統(tǒng)的卷積神經(jīng)網(wǎng)絡(luò)架構(gòu)朝著相反的方向發(fā)展（使用更小卷積核的更深的網(wǎng)絡(luò)）。

我們尚不明確同樣的方法是否適用于圖學(xué)習(xí)問題，因為圖的組合性要復(fù)雜得多（例如，無論網(wǎng)絡(luò)有多深，某些結(jié)構(gòu)都不能通過消息傳遞來計算）。

當(dāng)然，我們還需要通過更多詳細(xì)的實驗來驗證這一猜想。

好消息，小白學(xué)視覺團隊的知識星球開通啦，為了感謝大家的支持與厚愛，團隊決定將價值149元的知識星球現(xiàn)時免費加入。各位小伙伴們要抓住機會哦！

交流群

歡迎加入公眾號讀者群一起和同行交流，目前有SLAM、三維視覺、傳感器、自動駕駛、計算攝影、檢測、分割、識別、醫(yī)學(xué)影像、GAN、算法競賽等微信群（以后會逐漸細(xì)分），請掃描下面微信號加群，備注：”昵稱+學(xué)校/公司+研究方向“，例如：”張三 + 上海交大 + 視覺SLAM“。請按照格式備注，否則不予通過。添加成功后會根據(jù)研究方向邀請進入相關(guān)微信群。請勿在群內(nèi)發(fā)送廣告，否則會請出群，謝謝理解~