?作者 |?薄德瑜、王嘯

單位 |?北郵GAMMA Lab

研究方向 |?圖神經(jīng)網(wǎng)絡(luò)

前言

圖神經(jīng)網(wǎng)絡(luò)（Graph Neural Networks, GNN）在諸多圖任務(wù)上的巨大潛力已經(jīng)有目共睹。眾多學(xué)者也從不同的視角開始對(duì)GNN背后的機(jī)制開展探索，諸如 [1] 指出了GNN的低通濾波特性，[2] 證明了GNN等價(jià)于1-WL test，[3] 揭示了統(tǒng)一優(yōu)化目標(biāo)下的GNN傳播機(jī)制。其中GNN的低通濾波特性引起了業(yè)界廣泛關(guān)注，因?yàn)檫@意味著GNN可以有效過濾數(shù)據(jù)中的噪聲，平滑鄰居節(jié)點(diǎn)的表示，達(dá)到鄰近節(jié)點(diǎn)具有相似表征的目的。故而，這使得GNN非常適用于同配圖（Assortative Graph / Homophily Graph），即網(wǎng)絡(luò)中有相同標(biāo)簽的節(jié)點(diǎn)傾向于互相連接。

以廣泛使用的三個(gè)數(shù)據(jù)集，Cora, citeseer和pubmed為例，這三個(gè)數(shù)據(jù)集都屬于學(xué)術(shù)網(wǎng)絡(luò)，其特點(diǎn)是網(wǎng)絡(luò)有極強(qiáng)的同配性。由于GCN的消息傳遞方式是利用均值聚合所有鄰居的信息，所以可以很好地學(xué)習(xí)到學(xué)術(shù)網(wǎng)絡(luò)的歸納偏置（Inductive bias）。

但是，我們不禁要問，現(xiàn)實(shí)世界中的網(wǎng)絡(luò)是否都具有同配性這一特點(diǎn)呢？其實(shí)早在2003年，密歇根大學(xué)的物理學(xué)教授Mark Newman就已經(jīng)在論文《Mixing patterns in networks》[4] 中對(duì)現(xiàn)實(shí)世界里的各種網(wǎng)絡(luò)的同配性做了分析，如下圖所示：

對(duì)于指標(biāo)Assortativity (r)，其值越大，代表同配性越強(qiáng)，反之則異配性（Disassortativity / Heterophily）越強(qiáng)。從圖中我們可以看到一個(gè)不爭(zhēng)的事實(shí)，學(xué)術(shù)網(wǎng)絡(luò)的同配性是各種網(wǎng)絡(luò)中最強(qiáng)的，但是很多網(wǎng)絡(luò)并不具有同配性，反而有很強(qiáng)的異配性。所以GNN在學(xué)術(shù)網(wǎng)絡(luò)上的優(yōu)越性能難以佐證其在真實(shí)世界應(yīng)用的良好泛化性。論文 [5] 的實(shí)驗(yàn)中顯示，在異配性強(qiáng)的網(wǎng)絡(luò)中，GCN、GAT等在學(xué)術(shù)網(wǎng)絡(luò)中表現(xiàn)好的方法的性能，還不如不利用圖結(jié)構(gòu)信息的多層感知機(jī)。我們需要認(rèn)真審視這一現(xiàn)象，怎樣才能解決圖神經(jīng)網(wǎng)絡(luò)在異配圖上效果不佳的問題？

如何解決異配圖節(jié)點(diǎn)分類問題

目前，已經(jīng)有很多工作嘗試將圖神經(jīng)網(wǎng)絡(luò)泛化到異配圖上，我們以較早開始對(duì)這一問題開展探索的三篇代表性論文出發(fā)，從三個(gè)不同的角度，來說明如何讓圖神經(jīng)網(wǎng)絡(luò)在異配圖上也能取得很好的效果。

2.1?圖結(jié)構(gòu)學(xué)習(xí)

解決異配圖問題最直接的一個(gè)方法就是，通過改變圖結(jié)構(gòu)，使得原本的異配圖變?yōu)橥鋱D，這樣在同配圖上表現(xiàn)好的方法就可以繼續(xù)用在異配圖中。論文[6]中提出了一種利用利用結(jié)構(gòu)信息為節(jié)點(diǎn)選擇鄰居的模型：Geom-GCN。其基本思想是，具有相似結(jié)構(gòu)信息的節(jié)點(diǎn)（例如橋節(jié)點(diǎn)、中心節(jié)點(diǎn)等）可能屬于同一個(gè)類別，因此可以利用結(jié)構(gòu)信息來為節(jié)點(diǎn)選擇新的鄰居，增加圖的同配性。其模型流程如下圖所示：

首先，Geom-GCN利用傳統(tǒng)的網(wǎng)絡(luò)嵌入方法學(xué)習(xí)到每個(gè)節(jié)點(diǎn)的低維向量表示；然后選擇向量相似的節(jié)點(diǎn)作為新的鄰居，顯示地捕獲了節(jié)點(diǎn)之間的結(jié)構(gòu)相似性，增加了圖結(jié)構(gòu)的同配性；然后再將原始鄰居和新鄰居的信息進(jìn)行聚合，更新節(jié)點(diǎn)的表示。

類似的思想其實(shí) [7] 也做了初步嘗試，除了原始的圖結(jié)構(gòu)以外，他們基于節(jié)點(diǎn)特征顯式地構(gòu)造了一個(gè)新的特征圖，這樣假如原始圖結(jié)構(gòu)不具備同配性特點(diǎn)的時(shí)候，新的基于節(jié)點(diǎn)特征的特征圖或可以起到效果。進(jìn)一步地，也可以直接拋棄掉顯式構(gòu)造特征圖的步驟，直接學(xué)習(xí)出一個(gè)新的圖結(jié)構(gòu) [8]。

2.2 圖表征分離

除了圖結(jié)構(gòu)學(xué)習(xí)外，還有一些方法嘗試通過改進(jìn)圖神經(jīng)網(wǎng)絡(luò)的消息傳遞機(jī)制來提升其表達(dá)能力。H2GNN [9] 從理論上證明了分離節(jié)點(diǎn)自身的表征和鄰居聚合的表征可以將圖神經(jīng)網(wǎng)絡(luò)泛化到異配圖上。然后它設(shè)計(jì)了三個(gè)關(guān)鍵的消息傳遞機(jī)制，通過適當(dāng)集成，可以幫助圖神經(jīng)網(wǎng)絡(luò)提升在異配圖上的性能。

1. 自身表征和鄰居表征分離。H2GNN認(rèn)為圖神經(jīng)網(wǎng)絡(luò)通過層層堆疊的方式聚合鄰居信息，會(huì)使得節(jié)點(diǎn)的表示變得相似，導(dǎo)致模型不能很好地區(qū)分不同類別的節(jié)點(diǎn)，因此它的第一個(gè)設(shè)計(jì)是分離自身表征和鄰居表征：，其中 代表拼接操作， 是層數(shù)，AGG是聚合函數(shù)， 是節(jié)點(diǎn) 的鄰居集合。

2. 引入高階鄰居信息。除了分離表征以外，H2GNN還證明了高階鄰居對(duì)于異配圖的節(jié)點(diǎn)分類是有幫助的，通過引入高階鄰居，模型可以學(xué)習(xí)到異配性主導(dǎo)（heterophily-dominant）的信息，其消息傳遞機(jī)制為：

其中 代表了距離中心節(jié)點(diǎn)距離為的鄰居。

3. 中間層表征融合。在做完每一層的信息聚合后，H2GNN將所有中間層的表征拼接在一起，來捕獲圖中的局部和全局信息，這種設(shè)計(jì)更準(zhǔn)確地模擬了異配圖中鄰居表示的分布：，其中K是消息傳遞的總層數(shù)。

H2GNN通過以上三個(gè)設(shè)計(jì)的集成，緩解了圖神經(jīng)網(wǎng)絡(luò)隨著層數(shù)的增加難以區(qū)分不同類型的節(jié)點(diǎn)的問題，提升了圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力。

2.3 圖信號(hào)處理

在自然界中，信息以不同的頻率進(jìn)行傳輸，其中較高的頻率通常用來編碼細(xì)節(jié)信息，而較低的頻率則代表了全局結(jié)構(gòu)。那么同配圖和異配圖是否具有不同頻率的信息呢？論文 [5] 設(shè)計(jì)了一個(gè)從圖信號(hào)處理角度來分析同配圖和異配圖的實(shí)驗(yàn)，如下圖所示：

它利用隨機(jī)塊（Stochastic Blockmodel，SBM）模型生成了一系列圖數(shù)據(jù)集，其中類內(nèi)連接概率固定為0.05，而類間連接概率從0.01逐漸增大到0.1，隨著類間連接概率的增大，圖結(jié)構(gòu)逐漸顯現(xiàn)出異配性。同時(shí)它將輸入特征分為低頻特征和高頻特征，然后在生成數(shù)據(jù)集上進(jìn)行性能測(cè)試。從圖中我們可以發(fā)現(xiàn)，低頻特征在同配圖上表現(xiàn)較好，而高頻特征在異配圖上表現(xiàn)較好。結(jié)合論文[1]中提到的GCN是一個(gè)低通濾波器，我們不難明白為什么大多數(shù)圖神經(jīng)網(wǎng)絡(luò)都不能再異配圖上取得很好的效果，因?yàn)閷?duì)于異配圖分類重要的高頻特征已經(jīng)被過濾掉了！

所以，如果想讓圖神經(jīng)網(wǎng)絡(luò)能夠在同配圖和異配圖上都有很好的表現(xiàn)，我們就需要模型能夠同時(shí)具有低通濾波和高通濾波的能力。為了達(dá)到這一目的，論文[5]提出了頻率自適應(yīng)圖神經(jīng)網(wǎng)絡(luò)（Frequency Adaptation Graph Convolutional Networks，FAGCN）。它首先設(shè)計(jì)了一個(gè)低通濾波器和一個(gè)高通濾波器，其頻率響應(yīng)濾波函數(shù)如下：

通過這兩個(gè)濾波器，模型可以分別提取到模型的低頻和高頻特征，然后通過注意力機(jī)制進(jìn)行信號(hào)融合：，其中為特征矩陣，為節(jié)點(diǎn)的特征。

為了更好地解釋信號(hào)融合背后的原理，我們可以對(duì)公式進(jìn)行進(jìn)一步的展開：。我們可以看到，其本質(zhì)仍然是圖神經(jīng)網(wǎng)絡(luò)的消息傳遞機(jī)制，對(duì)自身信息和鄰居信息進(jìn)行融合。

在注意力機(jī)制中，注意力系數(shù)的和為1，即，所以的范圍就限制在之間。這與傳統(tǒng)的基于注意力的圖神經(jīng)網(wǎng)絡(luò)（比如GAT）略有不同，FAGCN并不限制注意力系數(shù)一定為非負(fù)數(shù)，這一點(diǎn)是解決異配圖的核心關(guān)鍵。

但是該消息傳遞函數(shù)仍然存在很多不足，最大的問題是，在節(jié)點(diǎn)聚合鄰居消息時(shí)，其注意力系數(shù)對(duì)于每個(gè)鄰居是相同的（在很多論文中被稱為各向同性），這樣會(huì)極大程度地限制FAGCN的表達(dá)能力。所以，我們對(duì)該消息傳遞機(jī)制進(jìn)行一些細(xì)微的修改，其消息傳遞函數(shù)變?yōu)?#xff0c;即每一個(gè)鄰居都有其獨(dú)有的系數(shù)，達(dá)到了各向異性的目的，增強(qiáng)了模型的表達(dá)能力。

對(duì)于系數(shù)的學(xué)習(xí)，FAGCN采用和GAT一樣設(shè)計(jì)，所不同的是，為了保證系數(shù)的范圍限制在之間，FAGCN利用tanh激活函數(shù)代替了GAT中的softmax，即。可以看到，FAGCN中關(guān)鍵步驟即學(xué)到一個(gè)可以區(qū)分正負(fù)的權(quán)重系數(shù)，這一步驟具有譜域?yàn)V波的理論基礎(chǔ)，自適應(yīng)能力強(qiáng)，同時(shí)操作非常簡(jiǎn)潔，因?yàn)槠毡橐饬x上看，tanh的激活函數(shù)可以即插即用到任何其他的圖神經(jīng)網(wǎng)絡(luò)之中，使得其他圖神經(jīng)網(wǎng)絡(luò)也具備這種區(qū)分能力。

最后FAGCN還提供了理論證明：低通濾波可以讓節(jié)點(diǎn)表征變得相似，而高通濾波會(huì)讓節(jié)點(diǎn)表征變得不同。通過正系數(shù)聚合鄰居可以模擬低通濾波，通過負(fù)系數(shù)聚合鄰居可以模擬高通濾波。所以FAGCN可以在同配圖和異配圖上都取得很好的效果。

思考與總結(jié)

以上三個(gè)思路從不同角度都對(duì)GNN如何泛化到異配圖上開展研究，但可以看到，本質(zhì)上還是會(huì)落腳到圖結(jié)構(gòu)本身來。他們或者是探索圖結(jié)構(gòu)本身不同階數(shù)節(jié)點(diǎn)的不同影響，或者是直接修改圖結(jié)構(gòu)，比如學(xué)習(xí)圖結(jié)構(gòu)或者使得圖結(jié)構(gòu)上具有正負(fù)判別性。

近段時(shí)間來，對(duì)于異配圖上的GNN的探索吸引了眾多的注意力。與此同時(shí)，也有學(xué)者關(guān)注到GNN并非在所有異配圖上都不適用。這一點(diǎn)，筆者也表示同意，可以試想這樣一張異配圖，具有A標(biāo)簽節(jié)點(diǎn)的鄰居都是B，而具有B標(biāo)簽節(jié)點(diǎn)的鄰居都是A，以GNN的信息傳播機(jī)制來講，A和B只是互換了一下信息而已，而A標(biāo)簽節(jié)點(diǎn)，他們之間的表征還依然是相似的，也就是說對(duì)于A的分類，應(yīng)該也依然會(huì)奏效。B節(jié)點(diǎn)同理。因此，如何更準(zhǔn)確界定GNN的適用范圍，或者真正實(shí)現(xiàn)普適性，還需要進(jìn)一步思考。

參考文獻(xiàn)

[1] Simplifying Graph Convolutional Networks. ICML 2019.

[2] How Powerful are Graph Neural Networks? ICLR 2019.

[3] Interpreting and Unifying Graph Neural Networks with An Optimization Framework. WWW 2021.

[4] Mixing patterns in networks. Physical review E, 2003

[5] Beyond Low-frequency Information in Graph Convolutional Networks. AAAI 2021.

[6] Geom-gcn: Geometric graph convolutional networks. ICLR 2020.

[7] AM-GCN: Adaptive Multi-channel Graph Convolutional Networks. KDD 2020.

[8] Graph Structure Estimation Neural Networks. WWW 2021.

[9] Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. NeurIPS 2020.

特別鳴謝

感謝 TCCI 天橋腦科學(xué)研究院對(duì)于 PaperWeekly 的支持。TCCI 關(guān)注大腦探知、大腦功能和大腦健康。

更多閱讀

#投 稿?通 道#

?讓你的文字被更多人看到?

如何才能讓更多的優(yōu)質(zhì)內(nèi)容以更短路徑到達(dá)讀者群體，縮短讀者尋找優(yōu)質(zhì)內(nèi)容的成本呢？答案就是：你不認(rèn)識(shí)的人。

總有一些你不認(rèn)識(shí)的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學(xué)者和學(xué)術(shù)靈感相互碰撞，迸發(fā)出更多的可能性。?

PaperWeekly 鼓勵(lì)高校實(shí)驗(yàn)室或個(gè)人，在我們的平臺(tái)上分享各類優(yōu)質(zhì)內(nèi)容，可以是最新論文解讀，也可以是學(xué)術(shù)熱點(diǎn)剖析、科研心得或競(jìng)賽經(jīng)驗(yàn)講解等。我們的目的只有一個(gè)，讓知識(shí)真正流動(dòng)起來。

📝?稿件基本要求：

? 文章確系個(gè)人原創(chuàng)作品，未曾在公開渠道發(fā)表，如為其他平臺(tái)已發(fā)表或待發(fā)表的文章，請(qǐng)明確標(biāo)注?

? 稿件建議以?markdown?格式撰寫，文中配圖以附件形式發(fā)送，要求圖片清晰，無版權(quán)問題

? PaperWeekly 尊重原作者署名權(quán)，并將為每篇被采納的原創(chuàng)首發(fā)稿件，提供業(yè)內(nèi)具有競(jìng)爭(zhēng)力稿酬，具體依據(jù)文章閱讀量和文章質(zhì)量階梯制結(jié)算

📬?投稿通道：

? 投稿郵箱：hr@paperweekly.site?

? 來稿請(qǐng)備注即時(shí)聯(lián)系方式（微信），以便我們?cè)诟寮x用的第一時(shí)間聯(lián)系作者

? 您也可以直接添加小編微信（pwbot02）快速投稿，備注：姓名-投稿

△長(zhǎng)按添加PaperWeekly小編

🔍

現(xiàn)在，在「知乎」也能找到我們了

進(jìn)入知乎首頁搜索「PaperWeekly」

點(diǎn)擊「關(guān)注」訂閱我們的專欄吧

·

總結(jié)

以上是生活随笔為你收集整理的异配图神经网络小结：突破同配性，拥抱异配性的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。