图神经网络三剑客：GCN、GAT与GraphSAGE
?PaperWeekly 原創(chuàng) ·?作者｜桑運(yùn)鑫
學(xué)校｜上海交通大學(xué)
研究方向｜圖神經(jīng)網(wǎng)絡(luò)在金融領(lǐng)域的應(yīng)用
2019 年號稱圖神經(jīng)網(wǎng)絡(luò)元年，在各個領(lǐng)域關(guān)于圖神經(jīng)網(wǎng)絡(luò)的研究爆發(fā)式增長。本文主要介紹一下三種常見圖神經(jīng)網(wǎng)絡(luò)：GCN、GAT 以及 GraphSAGE。前兩者是目前應(yīng)用比較廣泛的圖神經(jīng)網(wǎng)絡(luò)，后者則為圖神經(jīng)網(wǎng)絡(luò)的工程應(yīng)用提供了基礎(chǔ)。
GCN
圖神經(jīng)網(wǎng)絡(luò)基于巴拿赫不動點定理提出，但圖神經(jīng)網(wǎng)絡(luò)領(lǐng)域的大發(fā)展是在 2013 年 Bruna 提出圖上的基于頻域和基于空域的卷積神經(jīng)網(wǎng)絡(luò)后。
關(guān)于圖卷積神經(jīng)網(wǎng)絡(luò)的理解與介紹，知乎上的回答已經(jīng)講的非常透徹了。
如何理解 Graph Convolutional Network (GCN)？
https://www.zhihu.com/question/54504471/answer/332657604
這里主要介紹一下 PyG 和 DGL 兩個主要的圖神經(jīng)網(wǎng)絡(luò)庫實現(xiàn)所基于的文章?Semi-supervised Classification with Graph Convolutional Networks。它基于對圖上頻域卷積的一階近似提出了一種高效的逐層傳播規(guī)則。?
論文標(biāo)題：Semi-supervised Classification with Graph Convolutional Networks
論文鏈接：https://arxiv.org/abs/1609.02907
在將定義在歐式空間上的拉普拉斯算子和傅里葉變換對應(yīng)到圖上之后，圖上的頻域卷積操作可以基于卷積定理自然導(dǎo)出：
其中圖上的拉普拉斯矩陣（歸一化后）L 是一個半正定對稱矩陣，它具有一些良好的性質(zhì)，可以進(jìn)行譜分解：，其中 U 是 L 的特征向向量組成的矩陣，Λ 是 L 的特征值組成的對角矩陣，?則是定義在圖上的對信號??的傅里葉變換。
而對角矩陣??則是卷積核，也是不同的卷積操作關(guān)注的焦點，對??不同的設(shè)計會影響卷積操作的效率，其編碼的信息也會影響最終任務(wù)的精度。
一開始的圖卷積神經(jīng)網(wǎng)絡(luò)將 ?視作 L 的特征值的一個函數(shù)?。但這種定義存在兩個問題：?
1. 對特征向量矩陣 U 的乘法操作時間復(fù)雜度是 ；??
2. 對大規(guī)模圖的拉普拉斯矩陣 L 的特征分解是困難的。
之后的研究發(fā)現(xiàn)可以使用切比雪夫多項式來對 進(jìn)行近似：
其中?。?是 L 的最大特征值，?是切比雪夫多項式的系數(shù)向量。切比雪夫多項式通過如下的遞推公式定義：，起始值：。將其代入之前定義的卷積操作：
其中?，此時的時間復(fù)雜度為?。文章在此基礎(chǔ)上對卷積操作進(jìn)行了進(jìn)一步的簡化，首先固定 K=1，并且讓 ?近似等于 2（注意之前對 L 的定義），則上式可以簡化為一個包含兩個自由參數(shù)??和??的公式：
我們進(jìn)一步假定?，則可進(jìn)一步對公式進(jìn)行變形：
但是此時的??的特征值取值在 [0, 2]，對這一操作的堆疊會導(dǎo)致數(shù)值不穩(wěn)定以及梯度爆炸（或消失）等問題。為了解決這一問題，引入一種稱為重歸一化（renormalization）的技術(shù)：
最后將計算進(jìn)行向量化，得到最終的卷積計算公式為：
這一計算的時間復(fù)雜度為?。基于上式實現(xiàn)的 GCN 在三個數(shù)據(jù)集上取得了當(dāng)時最好的結(jié)果。
GAT
PyG 與 DGL 的 GAT 模塊都是基于 Graph Attention Networks 實現(xiàn)的，它的思想非常簡單，就是將 transform 中大放異彩的注意力機(jī)制遷移到了圖神經(jīng)網(wǎng)絡(luò)上。
論文標(biāo)題：Graph Attention Networks
論文鏈接：https://arxiv.org/abs/1710.10903
整篇文章的內(nèi)容可以用下面一張圖來概況。
首先回顧下注意力機(jī)制的定義，注意力機(jī)制實質(zhì)上可以理解成一個加權(quán)求和的過程：對于一個給定的 query，有一系列的 value 和與之一一對應(yīng)的 key，怎樣計算 query 的結(jié)果呢？
很簡單，對 query 和所有的 key 求相似度，然后根據(jù)相似度對所有的 value 加權(quán)求和就行了。這個相似度就是 attention coefficients，在文章中計算如下：
其中??是前饋神經(jīng)網(wǎng)絡(luò)的權(quán)重系數(shù)，|| 代表拼接操作。
利用注意力機(jī)制對圖中結(jié)點特征進(jìn)行更新：
既然得到了上式，那么多頭注意力的更新就不言而明了，用 k 個權(quán)重系數(shù)分別得到新的結(jié)點特征之后再拼接就可以了：
最后就是大家喜聞樂見的暴打 benchmarks 的環(huán)節(jié)，GAT 在三個數(shù)據(jù)集上達(dá)到了當(dāng)時的 SOTA。
GraphSAGE
GraphSAGE 由 Inductive Representation Learning on Large Graphs 提出，該方法提供了一種通用的歸納式框架，使用結(jié)點信息特征為未出現(xiàn)過的（unseen）結(jié)點生成結(jié)點向量，這一方法為后來的 PinSage（GCN 在商業(yè)推薦系統(tǒng)首次成功應(yīng)用）提供了基礎(chǔ)。
論文標(biāo)題：Inductive Representation Learning on Large Graphs
論文鏈接：https://arxiv.org/abs/1706.02216
但 GraphSAGE 的思想?yún)s非常簡單，也可以用一張圖表示。?
算法的詳細(xì)過程如下：
1. 對圖上的每個結(jié)點 v，設(shè)置它的初始 embedding??為它的輸入特征?；
2. 之后進(jìn)行 K次迭代，在每次迭代中，對每個結(jié)點 v，聚合它的鄰居結(jié)點（采樣后）的在上一輪迭代中生成的結(jié)點表示??生成當(dāng)前結(jié)點的鄰居結(jié)點表示?，之后連接??輸入一個前饋神經(jīng)網(wǎng)絡(luò)得到結(jié)點的當(dāng)前表示??；? ? ? ? ? ?
3. 最后得到每個結(jié)點的表示?。
這個算法有兩個關(guān)鍵點：一是鄰居結(jié)點采樣，二是聚合鄰居結(jié)點信息的聚合函數(shù)。?
鄰居結(jié)點采樣方面，論文中在 K 輪迭代中，每輪采樣不同的樣本，采樣數(shù)量為?。在聚合函數(shù)方面，論文提出了三種聚合函數(shù)：
Mean aggregator：
LSTM aggregator：使用 LSTM 對鄰居結(jié)點信息進(jìn)行聚合。值得注意地是，因為 LSTM 的序列性，這個聚合函數(shù)不具備對稱性。文章中使用對鄰居結(jié)點隨機(jī)排列的方法來將其應(yīng)用于無序集合。?
Pooling aggregator：
論文在三個數(shù)據(jù)集上取得了對于 baseline 的 SOTA。
既然為工程應(yīng)用提出的方法，對于實驗部分就不能一筆帶過了，這里給出論文中兩個有意思的結(jié)論：
對于鄰居結(jié)點的采樣，設(shè)置 K=2 和??得到比較好的表現(xiàn)；
對于聚合函數(shù)的比較上，LSTM aggregator 和 Pooling aggregator 表現(xiàn)最好，但是前者比后者慢大約兩倍。
總結(jié)
本文對圖神經(jīng)網(wǎng)絡(luò)中常用的三種方法進(jìn)行了介紹。隨著圖神經(jīng)網(wǎng)絡(luò)研究的熱度不斷上升，我們也看到圖神經(jīng)網(wǎng)絡(luò)的不同變種不斷涌現(xiàn)，此外，因為對于非歐空間數(shù)據(jù)良好的表達(dá)能力，圖神經(jīng)網(wǎng)絡(luò)在交通、金融、社會科學(xué)等有大量相應(yīng)數(shù)據(jù)積淀的交叉領(lǐng)域也面臨著廣闊的應(yīng)用前景。
點擊以下標(biāo)題查看更多往期內(nèi)容：?
針對圖嵌入模型的受限黑盒對抗攻擊框架
深度學(xué)習(xí)模型不確定性方法對比
ICLR 2020?| 隱空間的圖神經(jīng)網(wǎng)絡(luò)：Geom-GCN
深度學(xué)習(xí)預(yù)訓(xùn)練模型可解釋性概覽
如何快速理解馬爾科夫鏈蒙特卡洛法？
神經(jīng)網(wǎng)絡(luò)中的常用激活函數(shù)總結(jié)
#投 稿 通 道#
?讓你的論文被更多人看到?
如何才能讓更多的優(yōu)質(zhì)內(nèi)容以更短路徑到達(dá)讀者群體，縮短讀者尋找優(yōu)質(zhì)內(nèi)容的成本呢？答案就是：你不認(rèn)識的人。
總有一些你不認(rèn)識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學(xué)者和學(xué)術(shù)靈感相互碰撞，迸發(fā)出更多的可能性。?
PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優(yōu)質(zhì)內(nèi)容，可以是最新論文解讀，也可以是學(xué)習(xí)心得或技術(shù)干貨。我們的目的只有一個，讓知識真正流動起來。
?????來稿標(biāo)準(zhǔn)：
? 稿件確系個人原創(chuàng)作品，來稿需注明作者個人信息（姓名+學(xué)校/工作單位+學(xué)歷/職位+研究方向）?
? 如果文章并非首發(fā)，請在投稿時提醒并附上所有已發(fā)布鏈接?
? PaperWeekly 默認(rèn)每篇文章都是首發(fā)，均會添加“原創(chuàng)”標(biāo)志
???? 投稿郵箱：
? 投稿郵箱：hr@paperweekly.site?
? 所有文章配圖，請單獨(dú)在附件中發(fā)送?
? 請留下即時聯(lián)系方式（微信或手機(jī)），以便我們在編輯發(fā)布時和作者溝通
????
現(xiàn)在，在「知乎」也能找到我們了
進(jìn)入知乎首頁搜索「PaperWeekly」
點擊「關(guān)注」訂閱我們的專欄吧
關(guān)于PaperWeekly
PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學(xué)術(shù)平臺。如果你研究或從事 AI 領(lǐng)域，歡迎在公眾號后臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群里。
總結(jié)
以上是生活随笔為你收集整理的图神经网络三剑客：GCN、GAT与GraphSAGE的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 特斯拉首席信息官 Nagesh Sald
- 下一篇： 小鹏 MONA M03 热销后，比亚迪王