注：本篇博客公式格式?jīng)]有經(jīng)過認(rèn)真編輯珍促，歡迎去我的博客：http://www.pinkman.tech/index.php/tech/2021/gnn-basic/或者知乎：https://zhuanlan.zhihu.com/p/356872702獲得更好的閱讀體驗澄步。
本篇文章旨在通過最直白的語言解釋一些GNN中的基礎(chǔ)知識，涉及到的內(nèi)容包括：
- GNN在現(xiàn)實中的應(yīng)用
- 研究圖問題的兩個重要原則
- GNN是如何學(xué)習(xí)的
- GNN中信息如何傳遞绪颖？什么是卷積GNN，注意力GNN和信息傳遞GNN旦部？
- 關(guān)于GNN的一些觀點
本篇文章參考于Petar Veli?kovi?的教程霉晕，講義位于：petar-v.com/talks/GNN-W。由于我剛接觸這個領(lǐng)域雷客，所以在書寫過程中難免出錯芒珠，歡迎在評論中指出。
一搅裙、現(xiàn)實世界中GNN的應(yīng)用
判斷分子特性
生物分子就是一個圖結(jié)構(gòu)皱卓，其中每一個原子是一個節(jié)點裹芝，連接原子的化學(xué)鍵就是一個邊。關(guān)于分子有一些比較有趣的研究任務(wù)娜汁，比如判斷一個分子是不是一種強烈的藥物嫂易。此時，可以將該分子通過GNN來進(jìn)行二分類掐禁。
<figcaption>GNN應(yīng)用于化學(xué)領(lǐng)域</figcaption>
這樣訓(xùn)練以后怜械，有一個好處是可以通過圖神經(jīng)網(wǎng)絡(luò)發(fā)現(xiàn)各種各樣的分子特性：將一個很大的候選分子庫送入網(wǎng)絡(luò)進(jìn)行預(yù)測，可以選擇GNN模型輸出的候選100個分子集合傅事，再進(jìn)行化學(xué)測試宫盔。在這個領(lǐng)域還是非常有用的。
交通地圖也是圖結(jié)構(gòu)
其中享完，每個十字路口可以是一個節(jié)點，每個道路就是一個邊有额。
<figcaption>GNN應(yīng)用在交通地圖</figcaption>
通過在交通地圖上構(gòu)建的GNN般又，可以用來回歸預(yù)計抵達(dá)的時間（time to arrival, ETA）。
二巍佑、從CNN中觀察
CNN的思想
第一個思想：只要圖中出現(xiàn)某個信息茴迁，無論這個信息出現(xiàn)在哪里，都是有用的萤衰。比如檢測某個物體堕义，無論在圖像中的哪里被檢測到，只要被檢測到就是成功的脆栋。所以才可以對整張圖像進(jìn)行掃描倦卖。這個思想叫做translational invariance。
第二個思想：離得近的圖像像素之間的影響椿争，遠(yuǎn)比離得遠(yuǎn)的像素的影響要大怕膛，因此才能夠使用一個提取局部信息的卷積核。
我們接下來同樣會利用這些思想秦踪，應(yīng)用在圖上褐捻。
圖的特性
由于在圖中不會指定任何的節(jié)點順序，所以下面其實是一模一樣的兩幅圖椅邓。我們需要圖神經(jīng)網(wǎng)絡(luò)對這個輸入柠逞，能夠輸出同樣的信息。
<figcaption>兩個相同的圖</figcaption>
三景馁、排列不變性和排列相等性
我們暫時先假設(shè)圖中沒有邊板壮，此時圖是一個節(jié)點的集合。令(\boldsymbol{x}_i \in R^k) 表示節(jié)點 i 的 k 維特征合住「鍪可以將所有的節(jié)點特征堆疊到一起慕购，形成一個(n\times k)的特征矩陣。需要注意的是茬底，在這里為節(jié)點指定了順序沪悲，但是想要圖的輸出不會依賴于這個順序。
為了研究組合方式的操作阱表，定義如下的 (n\times n) 矩陣叫做排列矩陣殿如。其中，每一行和每一列都只有一個1最爬，其余都為0涉馁。這個矩陣的作用就是當(dāng)左乘上述特征矩陣時，就將上述特征矩陣換了一個排列組合的方式爱致。這個排列矩陣對于研究排列組合來說非常有用烤送。
排列不變性 Permutation Invariance
我們的目標(biāo)是：定義一個不依賴于輸入節(jié)點順序的函數(shù)(f(\boldsymbol{X})) 。
數(shù)學(xué)定義：如果 (f(\boldsymbol{X})) 是排列不變的糠悯，那么對于所有的排列矩陣P 帮坚，都有：(f(\boldsymbol{PX}) = f(\boldsymbol{X}) ) 。
排列相等性 Permutation Equivariance
但是互艾，如果想要獲得某一個節(jié)點的特征呢试和？此時就需要排列相等性了。它研究的是一個節(jié)點層面的排列性質(zhì)纫普。目標(biāo)是找到不會改變節(jié)點順序的函數(shù)阅悍。也就是說，如果我們改變節(jié)點的順序昨稼，無論我們經(jīng)過函數(shù)前改變节视，還是經(jīng)過函數(shù)后改變，結(jié)果應(yīng)該是一致的假栓。
數(shù)學(xué)定義：如果 (f(\boldsymbol{X})) 是排列相等的肴茄，那么對于所有的排列矩陣P，都有：(f(\boldsymbol{PX}) = \boldsymbol{P}f(\boldsymbol{X}) ) 但指。
集合研究的基礎(chǔ)
說到這里寡痰，大家也可以發(fā)現(xiàn)，排列相等性要求我們不能進(jìn)行每個節(jié)點的特征交互棋凳，即特征矩陣的行與行之間的交互拦坠，所以我們只能夠?qū)γ恳粋€節(jié)點進(jìn)行一個特征的映射。
其中的(\psi)是一個映射函數(shù)剩岳，獨立地作用于對每個節(jié)點贞滨。將所有的 (\boldsymbol{h}_i) 堆疊起來，就得到了(\boldsymbol{H} = f(\boldsymbol{X}))。
另一方面晓铆，為了保證排列不變性勺良，我們需要在最后添加一個聚集函數(shù)，例如求和骄噪，平均值尚困，最大值等。這樣我們就得到了最終的輸出链蕊。
說了這么多事甜，思想其實很簡單，就是先單獨對每個節(jié)點提取特征滔韵，然后將所有的特征整合起來逻谦，整合的過程要保證順序不會影響到最終結(jié)果。
四陪蜻、圖中的學(xué)習(xí)
好了邦马，現(xiàn)在可以研究圖中有邊的情況了。我們定義鄰接矩陣 A宴卖，其中
這里為了便于表示滋将，先忽略邊的特征，比如距離嘱腥，花費成本等。
將圖中的節(jié)點進(jìn)行排列時拘悦，由于節(jié)點的順序變化會同時影響到連接它的所有邊齿兔，在鄰接矩陣中表示，就是鄰接矩陣的行和列都要受到影響础米。具體來說分苇，假如節(jié)點經(jīng)過了 (\boldsymbol{P}) 的排列組合轉(zhuǎn)換，那么鄰接矩陣就會變?yōu)?(\boldsymbol{PAP}^T) 屁桑。
此時医寿，排列不變性和排列相等性就變成了這樣的表示：
圖中的局部性：鄰居節(jié)點
在前文提到的節(jié)點集合部分中，我們通過每個節(jié)點獨立地提取特征保證了排列相等性蘑斧。然而在圖中靖秩，我們有一個非常有用的信息：一個節(jié)點的鄰居節(jié)點。對于一個節(jié)點 i 來說竖瘾，和它距離為1的節(jié)點集合可以表示為：
此時沟突，我們可以在這個鄰居節(jié)點的集合上提取特征，表示為
將這個提取特征的過程表示為函數(shù) (g(\boldsymbol{x}i, \boldsymbol{X}{N_i})) 捕传。
圖神經(jīng)網(wǎng)絡(luò)
此時惠拭，我們終于可以了解到圖神經(jīng)網(wǎng)絡(luò)是什么樣的了。將上述的函數(shù)g作用于每一個節(jié)點及其鄰居節(jié)點庸论，得到最終的特征职辅，這就是一個圖神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)形式棒呛。
為了確保排列相等性，我們需要保證這里的函數(shù)g不依賴于鄰居節(jié)點的順序信息域携，因此簇秒，g應(yīng)該是排列不變的。
下圖中是一個圖神經(jīng)網(wǎng)絡(luò)提取特征的圖示涵亏，通過輸入一個節(jié)點b宰睡，及其周圍的鄰居節(jié)點給函數(shù)g，提取得到的隱向量气筋，標(biāo)記為 (\boldsymbol{h}_b)拆内。
<figcaption>圖神經(jīng)網(wǎng)絡(luò)提取特征圖示</figcaption>
得到了隱含向量以后，如何利用它們呢宠默？這里給出幾種常見的使用方式：
- 節(jié)點分類麸恍。得到某一個節(jié)點的的隱向量以后，利用該向量去對一個節(jié)點進(jìn)行分類搀矫。
- 圖分類抹沪。將所有節(jié)點的隱向量整合到一起，得到整個圖的特征瓤球，然后利用這個特征去分類融欧。比如上文提到的分子特性分類。
- 鏈接預(yù)測卦羡。輸入兩個節(jié)點的隱向量以及他們之間的邊的信息噪馏，能夠輸出這兩個節(jié)點之間相互作用的結(jié)果。這一點也非常有用绿饵，比如預(yù)測從一個節(jié)點到另一個節(jié)點的抵達(dá)時間欠肾。
以下圖示表示了這一過程：
<figcaption>如何使用隱向量</figcaption>
五、圖中的信息傳遞
在GNN領(lǐng)域中拟赊，通常把前文中描述的 (f) 叫做GNN的一層刺桃， 叫做“擴(kuò)散”、“傳播”或者“信息傳遞”吸祟。如何定義函數(shù) (g)瑟慈，是圖神經(jīng)網(wǎng)絡(luò)中的重點，也是非常熱門的研究領(lǐng)域屋匕。幾乎所有提出的定義方式封豪，可以按照空間偏好分為三類，分別是卷積（Convolutional）炒瘟，注意力（Attentional）和信息傳遞（Message-passing）吹埠。
卷積圖神經(jīng)網(wǎng)絡(luò)
通過一個固定的權(quán)重 (c_{ij}) 來整合鄰居節(jié)點的特征。通常來說，這里的權(quán)重通常直接依賴于節(jié)點之間邊的信息（邊的信息代表的是節(jié)點的相似度缘琅，比如兩個節(jié)點距離越近粘都，那么它們可能就越相似）。
<figcaption>卷積GNN示意圖</figcaption>
這種結(jié)構(gòu)對于同質(zhì)圖來說很有用（同質(zhì)圖：圖中的節(jié)點類型和關(guān)系類型都僅有一種）刷袍，并且網(wǎng)絡(luò)可以輕易擴(kuò)展到很大的規(guī)模翩隧。
使用這類方法的經(jīng)典模型包括：
- ChebyNet (Defferrard , NeurIPS’16) et al.
- GCN (Kipf & Welling, ICLR’17)
- SGC (Wu , ICML’19） et al.
注意力圖卷積神經(jīng)網(wǎng)絡(luò)
注意力機(jī)制是近幾年非常火的一個研究方向呻纹。應(yīng)用在GNN中堆生，就是將前文中固定的權(quán)重改為可學(xué)習(xí)的權(quán)重，以此來描述兩個相鄰節(jié)點之間的關(guān)系雷酪。用公式表示為：
<figcaption>注意力GNN示意圖</figcaption>
這種結(jié)構(gòu)對于一些邊中沒有蘊含節(jié)點關(guān)系的圖來說非常有效淑仆，適用于規(guī)模不是特別大的圖，因為注意力機(jī)制會增加比較大的顯存和計算量哥力。
使用這類方法的經(jīng)典模型包括：
- MoNet (Monti , CVPR’17) et al.
- GAT (Veli?kovi? , ICLR’18) et al.
- GaAN (Zhang , UAI’18) et al.
信息傳遞圖神經(jīng)網(wǎng)絡(luò)
計算出一個向量（“信息”）蔗怠，通過邊傳遞給其余節(jié)點。
用公式表示為：
<figcaption>信息傳遞GNN示意圖</figcaption>
其中 吩跋，(m_{ij} = \psi)就是傳遞的信息寞射。
因為有了信息的傳遞，這類模型可以擬合一些非常復(fù)雜的任務(wù)锌钮，但是可能會面臨一些規(guī)那盼拢或者學(xué)習(xí)上的問題，因為需要計算和存儲整個圖中所有邊計算出來的信息梁丘，而圖中的邊一般都比節(jié)點要多得多侵浸。
使用這類方法的經(jīng)典模型包括：
- Interaction Networks (Battaglia ., NeurIPS’16) et al
- MPNN (Gilmer ., ICML’17) et al
- GraphNets (Battaglia ., 2018) et al
六、關(guān)于GNN的觀點
節(jié)點嵌入技術(shù)
這項技術(shù)的目的是兰吟，將圖中的節(jié)點嵌入到隱空間中通惫。
<figcaption>節(jié)點嵌入</figcaption>
那么什么是一個好的嵌入表示呢茂翔？對于圖來說混蔼，一個自然的想法就是，保留住圖中的有用信息珊燎，而節(jié)點之間的有用信息惭嚣，那就是邊。所以就有了一個非常直接的目標(biāo)：如果兩個節(jié)點之間右邊悔政，那么他們在隱空間中應(yīng)該是相近的晚吞，可以使用標(biāo)準(zhǔn)的二分類交叉熵?fù)p失函數(shù)來實現(xiàn)這個目標(biāo)：
這個其實是一個更加廣泛的方法簇——隨機(jī)行走的一個特例。將上述損失函數(shù)中的 谋国，重新定義為 和 共同出現(xiàn)在一個隨機(jī)行走的過程中槽地。
這類方法在GNN面世前，是最主流的無監(jiān)督圖表示學(xué)習(xí)方法。有以下著名的算法：
- DeepWalk (Perozzi , KDD’14) et al.
- node2vec (Grover & Leskovec, KDD’16)
- LINE (Tang , WWW’15) et al.
值得注意的一點是捌蚊，通過這種方法集畅，能夠?qū)W習(xí)到節(jié)點局部的相似性。因為在隱空間中距離比較近的節(jié)點缅糟，可能在原先的圖結(jié)構(gòu)中是存在邊相連的挺智，就是他們互相是鄰居節(jié)點。這是隨機(jī)行走方法的一個內(nèi)在的特點窗宦。但是赦颇，這恰恰就是卷積GNN的設(shè)計思想：強迫鄰居學(xué)習(xí)到相似的特征，這是因為兩個圖中相鄰的節(jié)點赴涵，可能會有很多個共同的鄰居節(jié)點媒怯，所以能夠?qū)W習(xí)到相似的特征。關(guān)于此句占，有兩個有用的推論：
- 隨機(jī)行走的目標(biāo)可能不能給GNN提供有用的信號
- 有時沪摄，DeepWalk能得到與未訓(xùn)練的卷積GNN相同的效果！（Veli?kovi? et al., ICLR’19）
與NLP的關(guān)系
節(jié)點嵌入技術(shù)纱烘，其實和NLP中的詞向量技術(shù)如出一轍：
- 節(jié)點可以和詞對應(yīng)
- 隨機(jī)行走和一個句子對應(yīng)
- node2vec技術(shù)對應(yīng)于word2vec技術(shù)
- 優(yōu)化目標(biāo)基本是一模一樣的
并不單純只有NLP可以嵌入到GNN的設(shè)計思想中杨拐，GNN其實也可以嵌入到NLP的設(shè)計思想中，兩門技術(shù)是非常相通的擂啥。
在NLP領(lǐng)域中哄陶，一個句子中的不同單詞，是會互相交互的哺壶，比如出現(xiàn)一個詞屋吨，另外一個詞的含義可能完全變了。我們可以使用圖來表示這種交互山宾，但是這個交互信息并不是直接提供的至扰，此時，一個常見的假設(shè)就是去初始化一個完全圖（完全圖是一個簡單的無向圖资锰，其中每對不同的頂點之間都恰連有一條邊相連）敢课，然后讓網(wǎng)絡(luò)去學(xué)習(xí)相互之間的關(guān)系。而這绷杜，就是Transformers的思想直秆！
可以將Transformer視作GNN的一種，它是一個完全圖鞭盟，屬于注意力圖神經(jīng)網(wǎng)絡(luò)分類下圾结。attention可以看做圖中的一種軟相鄰。（Joshi (The Gradient; 2020).）
<figcaption>多頭注意力機(jī)制</figcaption>
感謝您的閱讀齿诉，如果覺得這篇文章對您有幫助筝野，歡迎分享收藏晌姚！最后附上教程的原始視頻鏈接。
