本文發(fā)表于NeurIPS 2022

本文關(guān)注的問題是什么

當(dāng)前GNN的關(guān)系歸納偏差（同質(zhì)性假設(shè)）并不完全成立，在異質(zhì)圖上尤其嚴(yán)重。本文研究了如何提高現(xiàn)有GNN在異質(zhì)圖上的性能

本文提出了何種方法來解決問題

• 證明了現(xiàn)有的圖同質(zhì)性度量指標(biāo)存在缺陷，并提出了一個(gè)新的同質(zhì)性度量指標(biāo)

• 提出了自適應(yīng)通道融合策略（Adaptive Channel Mixing, ACM），這個(gè)策略根據(jù)每個(gè)節(jié)點(diǎn)不同的異質(zhì)性，自適應(yīng)地為節(jié)點(diǎn)提取豐富的局部信息（?richer localized information?）

Abstract

圖神經(jīng)網(wǎng)絡(luò)（GNN）通過使用基于關(guān)系歸納偏差（同質(zhì)性假設(shè)）的圖結(jié)構(gòu)來擴(kuò)展神經(jīng)網(wǎng)絡(luò)（Neural Network，NN）。雖然人們普遍認(rèn)為GNN在實(shí)際任務(wù)中優(yōu)于NN，但最近的工作發(fā)現(xiàn)了一組非平凡的數(shù)據(jù)集（異質(zhì)圖數(shù)據(jù)集），與NN相比，GNN的性能并不令人滿意。異質(zhì)性被認(rèn)為是GNN性能不好的主要原因，并提出了許多工作來解決這一問題。在本文中，我們首先回顧了廣泛使用的同質(zhì)性度量指標(biāo)，并指出它們只考慮圖和標(biāo)簽的一致性是一個(gè)缺點(diǎn)。然后，我們從聚合后節(jié)點(diǎn)相似性的角度研究異質(zhì)性，并定義了新的同質(zhì)性度量指標(biāo)，這些度量指標(biāo)與現(xiàn)有度量指標(biāo)相比具有潛在的優(yōu)勢(shì)?；谶@一調(diào)查，我們證明了一些有害的圖異質(zhì)性情況可以通過局部多樣化操作（local diversification operation）得到有效解決。然后，我們提出了自適應(yīng)信道混合（Adaptive Channel Mixing,?ACM），這是一個(gè)框架，可以靈活地針對(duì)每個(gè)節(jié)點(diǎn)（node-wisely）利用聚合、多樣化和恒等通道，為不同節(jié)點(diǎn)的異質(zhì)性情況提取更豐富的局部化信息。ACM比通常使用的單通道框架在異質(zhì)圖的節(jié)點(diǎn)分類任務(wù)上更強(qiáng)大，并且易于在現(xiàn)有GNN中實(shí)現(xiàn)。當(dāng)在10個(gè)基準(zhǔn)節(jié)點(diǎn)分類任務(wù)上進(jìn)行評(píng)估時(shí)，ACM增強(qiáng)的基線一致地實(shí)現(xiàn)了顯著的性能增益，在大多數(shù)任務(wù)上超過了最先進(jìn)的GNN，而不會(huì)產(chǎn)生顯著的計(jì)算負(fù)擔(dān)。

Introduction

深度神經(jīng)網(wǎng)絡(luò)（NN）[22]已經(jīng)徹底改變了許多機(jī)器學(xué)習(xí)領(lǐng)域，包括圖像識(shí)別[21]、語音識(shí)別[13]和自然語言處理[2]，因?yàn)樗鼈冊(cè)趶臍W幾里德數(shù)據(jù)學(xué)習(xí)潛在表示方面的有效性。最近的研究將重點(diǎn)轉(zhuǎn)移到了非歐幾里德數(shù)據(jù)[6]上，例如關(guān)系數(shù)據(jù)或圖表。結(jié)合圖信號(hào)處理和卷積神經(jīng)網(wǎng)絡(luò)[23]，已經(jīng)提出了許多圖神經(jīng)網(wǎng)絡(luò)（GNN）架構(gòu)[38、10、15、40、19、29]，這些架構(gòu)在基于圖的機(jī)器學(xué)習(xí)任務(wù)（如節(jié)點(diǎn)分類、圖分類、鏈路預(yù)測(cè)和圖生成）方面的經(jīng)驗(yàn)優(yōu)于傳統(tǒng)的NN，GNN建立在同質(zhì)性假設(shè)的基礎(chǔ)上[34]：連接的節(jié)點(diǎn)傾向于彼此共享相似的屬性[14]，這提供了節(jié)點(diǎn)特征之外的額外信息。這種關(guān)系歸納偏差[3]被認(rèn)為是導(dǎo)致GNN在許多任務(wù)中優(yōu)于NN的關(guān)鍵因素。

然而，越來越多的經(jīng)驗(yàn)證據(jù)表明，GNN與傳統(tǒng)NN相比并不總是有利的。在某些情況下，即使是簡單的多層感知器（MLP），在關(guān)系數(shù)據(jù)上也能比GNN表現(xiàn)出色[45,28,31,8]。一個(gè)重要的原因被認(rèn)為是異質(zhì)性問題： 同質(zhì)性假設(shè)并不總是成立的，因此連接的節(jié)點(diǎn)實(shí)際上可能具有不同的屬性。近來，異質(zhì)性受到了很多關(guān)注，越來越多的模型被提出來解決這個(gè)問題[45、28、31、8、44、43、32、16、24]。在本文中，我們首先表明，僅考慮圖和標(biāo)簽的一致性，現(xiàn)有的同態(tài)度量指標(biāo)不能描述某些異質(zhì)性對(duì)基于聚合的GNN的影響。我們提出了一個(gè)聚合后節(jié)點(diǎn)相似性矩陣，并在此基礎(chǔ)上導(dǎo)出了新的同態(tài)度量，其優(yōu)點(diǎn)在合成圖上得到了說明（第3節(jié)）。然后，我們證明多元化經(jīng)營有助于解決一些有害的異質(zhì)性案例（第4節(jié)）?；诖?，我們提出了自適應(yīng)信道混合（ACM）GNN框架，該框架增強(qiáng)了單信道基線GNN，允許它們?cè)诿總€(gè)層中自適應(yīng)地、node-wisely和locally利用聚合、多樣化和恒等通道。ACM顯著提高了3個(gè)單通道基線GNN的性能2.04%～ 在7個(gè)廣泛使用的基準(zhǔn)異親圖上，節(jié)點(diǎn)分類任務(wù)占27.5%，超過了SOTA模型（第6節(jié)）。對(duì)于3個(gè)同質(zhì)圖，ACM增強(qiáng)GNN的性能至少與單通道基線一樣好，并且與SOTA相比具有競(jìng)爭(zhēng)力。

貢獻(xiàn)

1. 據(jù)我們所知，我們是第一個(gè)從聚合后節(jié)點(diǎn)相似性角度分析異質(zhì)性的人。

2. 所提出的ACM框架與具有多個(gè)信道的自適應(yīng)濾波器組和現(xiàn)有的用于異構(gòu)的GNN有很大不同：1）傳統(tǒng)自適應(yīng)濾波器組信道[39]為每個(gè)濾波器使用標(biāo)量權(quán)重，并且該權(quán)重由所有節(jié)點(diǎn)共享。相反，ACM提供了一種機(jī)制，使得不同的節(jié)點(diǎn)可以學(xué)習(xí)不同的權(quán)重，以利用來自不同信道的信息來解釋不同的本地異質(zhì)性；2） 與利用高階濾波器和高頻信號(hào)的全局特性的現(xiàn)有方法不同[45,28,8,16]，這些方法需要更多的計(jì)算資源，ACM通過自適應(yīng)地僅考慮整個(gè)節(jié)點(diǎn)的局部信息成功地解決了異質(zhì)性問題。

3. 與現(xiàn)有方法不同，現(xiàn)有方法試圖促進(jìn)具有高表達(dá)能力的濾波器的學(xué)習(xí)[45，44，8，16]，ACM的目標(biāo)是，當(dāng)給定具有一定表達(dá)能力的濾波器時(shí)，我們可以以某種方式從額外的信道中提取更豐富的信息，以解決異質(zhì)性問題。這使得ACM更靈活，更易于實(shí)現(xiàn)。

同質(zhì)性度量指標(biāo)

文章的2.2節(jié)的公式3給出了現(xiàn)有的3種圖同質(zhì)性度量指標(biāo)：edge homophily [1, 45], node homophily [35] and class homophily

3.1節(jié)中的圖1給出了一個(gè)例子，這個(gè)例子證明了現(xiàn)有的同質(zhì)性度量指標(biāo)失效了。

作者提出的同質(zhì)性度量指標(biāo)

首先，定義聚合后節(jié)點(diǎn)相似矩陣（post-aggregation node similarity matrix）

然后，定義聚合相似性得分（aggregation similarity score）

然后再歸一化到[0,1]

the graph (G) aggregation ( ? A) homophily and its modified version

Adaptive Channel Mixing (ACM)

這部分是論文的核心內(nèi)容

在先前的工作[31,8,4]中，已經(jīng)表明，可以通過高通濾波器（HP）提取的高頻圖信號(hào)在解決異質(zhì)性方面是經(jīng)驗(yàn)上有用的。在本節(jié)中，基于等式6中的相似度矩陣，我們從理論上證明了多樣化操作，即高通濾波器，可以局部解決一些有害的異質(zhì)性情況。此外，逐節(jié)點(diǎn)分析表明，不同的節(jié)點(diǎn)可能需要不同的過濾器來處理其鄰居信息。基于上述分析，在第4.2節(jié)中，我們提出了自適應(yīng)信道混合（ACM），這是一種3通道架構(gòu)，可以自適應(yīng)地利用聚合、多樣化和恒等通道中的本地和節(jié)點(diǎn)信息?local and node-wise。

ACM中一共有3個(gè)通道，分別是?aggregation（低通濾波器，這個(gè)是現(xiàn)有GNN中廣泛采用的，相當(dāng)于Message Passing中的聚合操作，我認(rèn)為也是GNN過平滑的原因）, diversification（多樣化操作，其實(shí)就是高通濾波器，之前的論文發(fā)現(xiàn)高頻成分對(duì)圖的異質(zhì)性是有幫助的，本文作者進(jìn)行了理論證明） and identity （這個(gè)就是恒等，相當(dāng)于全通濾波器，不進(jìn)行任何變化）

本文ACM的思想和數(shù)字信號(hào)處理中的自適應(yīng)濾波器非常像，目的都是自適應(yīng)地對(duì)當(dāng)前的輸入配置不同參數(shù)的濾波器。在這里，每個(gè)不同的輸入是節(jié)點(diǎn)，而因?yàn)槊總€(gè)節(jié)點(diǎn)具有不同的異質(zhì)性，所以需要自適應(yīng)。ACM自適應(yīng)的方法是讓模型學(xué)習(xí)到3個(gè)通道的權(quán)重系數(shù)，然后進(jìn)行相加。

Diversification Helps with Harmful Heterophily

4.1節(jié)用圖3展示了為什么高通濾波器有效果

可以看到，圖3中右邊的圖的矩陣，有正有負(fù)，比較有區(qū)分度。而圖3中間的矩陣，數(shù)值都比較均衡，看不出區(qū)分度，效果不好。因此，高通濾波器對(duì)異質(zhì)性是有幫助的。

Filterbank and Adaptive Channel Mixing (ACM) Framework

4.2節(jié)介紹了圖中的高通濾波器和低通濾波器的概念

2.1節(jié)的最后，作者說明了ACM中的高通和低通濾波器到底是哪個(gè)

可以看到，ACM的算法步驟并不是非常復(fù)雜，而且可以方便地插入到其他的GNN中。