TPAMI 2024 | 針對(duì)節(jié)點(diǎn)的融合全局-局部信息的圖譜濾波方法
論文題目：
Node-oriented Spectral Filtering for Graph Neural Networks
論文作者：
Shuai Zheng, Zhenfeng Zhu, Zhizhe Liu, Youru Li, Yao Zhao
作者單位：
北京交通大學(xué)
源碼鏈接：
??https://github.com/SsGood/NFGNN/??
論文鏈接：
??https://ieeexplore.ieee.org/abstract/document/10286416/??
01 研究背景
在圖機(jī)器學(xué)習(xí)領(lǐng)域中，同配性（homophily）一直是一個(gè)普遍的假設(shè)，即屬于同一類的節(jié)點(diǎn)傾向于互相連接。然而，這一假設(shè)在很多真實(shí)的圖相關(guān)場(chǎng)景中其實(shí)并不成立，蛋白質(zhì)結(jié)構(gòu)網(wǎng)絡(luò)就是一個(gè)很典型的例子。
因此，研究面向異配圖數(shù)據(jù)的圖神經(jīng)網(wǎng)絡(luò)在近幾年成為了領(lǐng)域內(nèi)的一大主題。考慮到同配性的定義，我們提出一個(gè)觀點(diǎn)：下游任務(wù)與構(gòu)建圖時(shí)所采用的先驗(yàn)的相關(guān)性決定了一個(gè)圖的同配性程度。
具體來說，對(duì)于一個(gè)給定的拓?fù)浣Y(jié)構(gòu)，當(dāng)其與不同下游任務(wù)的標(biāo)簽分布相結(jié)合時(shí)，其同配性程度可能會(huì)非常不同。例如，學(xué)術(shù)引用網(wǎng)絡(luò)中，因?yàn)橐黄撐母锌赡芤醚芯肯嗤蝾愃浦黝}的論文，所以引文網(wǎng)絡(luò)鏈接的形成與主題分類任務(wù)是強(qiáng)正相關(guān)的。因此，如果我們使用論文的主題作為標(biāo)簽，則則該網(wǎng)絡(luò)可能是同配性的；而如果我們以論文的發(fā)布年份作為標(biāo)簽，引用圖可能是異配性或隨機(jī)的。
以上述假設(shè)看待圖的同配性問題，我們會(huì)發(fā)現(xiàn)，在標(biāo)簽有限的情況下，下游任務(wù)與圖結(jié)構(gòu)之間的相關(guān)性是較難預(yù)測(cè)的。因此，一個(gè)自然而然的問題是：整個(gè)圖中不同局部子圖的同配程度是否一致？
?
直觀上，假設(shè)不同區(qū)域之間總是存在多樣的子圖模式可能更為現(xiàn)實(shí)。因此，相比于特定于同配圖或異配圖的聚合設(shè)計(jì)，一種可以自適配圖中不同局部同配模式的 GNN，可能是更貼近實(shí)際應(yīng)用需求的。
與基于空域聚合的方法相比，基于頻譜的圖神經(jīng)網(wǎng)絡(luò)具有出色的理論解釋性和計(jì)算效率。然而，當(dāng)前基于譜濾波的方法均采用了全局共享單一濾波器的學(xué)習(xí)方式。本文中，我們基于圖信號(hào)處理理論，首次嘗試探索局部自適應(yīng)的譜濾波學(xué)習(xí)，以解決圖中的混合局部模式。
本文的主要貢獻(xiàn)如下：
- 為了深入了解實(shí)際圖的高階混合模式以及 GNN 對(duì)它們的適應(yīng)性，我們從子圖同配隨機(jī)性和近鄰可聚合性兩個(gè)方面進(jìn)行了實(shí)證和理論分析。
- 受廣義平移算子的啟發(fā)，我們提出了一種面向節(jié)點(diǎn)的譜濾波 GNN，即 NFGNN。它充分考慮了過濾器定位節(jié)點(diǎn)的局部子圖模式來估計(jì)濾波系數(shù)。
- 為了減輕學(xué)習(xí)面向節(jié)點(diǎn)的局部濾波系數(shù)的繁重負(fù)擔(dān)，我們提出了一種基于低秩近似的重參數(shù)化方法來分解濾波系數(shù)矩陣，不僅簡(jiǎn)化了參數(shù)復(fù)雜度，而且在全局濾波和局部濾波之間進(jìn)行了權(quán)衡。
02 局部同配模式分析
2.1 子圖同配隨機(jī)性
由于目標(biāo)是通過節(jié)點(diǎn)鄰域的標(biāo)簽一致性來分析圖的局部同配模式，因此我們采用了節(jié)點(diǎn)同配率來分析局部同配模式。首先，我們給出一階鄰域同配率和二階鄰域同配率的節(jié)點(diǎn)級(jí)統(tǒng)計(jì)直方圖的可視化。
如圖 1 所示，即使在通常被認(rèn)為是同配性圖的 Cora 和 Citeseer 網(wǎng)絡(luò)中，也仍然存在少量的 1 跳完全異配子圖。同樣，在 Cornell 和 Actor 網(wǎng)絡(luò)中也有一些高同配率的子圖。此外，對(duì)于 Cornell 和 Actor 網(wǎng)絡(luò)，我們發(fā)現(xiàn)二階鄰域同配率統(tǒng)計(jì)直方圖與一階統(tǒng)計(jì)結(jié)果的顯示出一定的偏移，表明每個(gè)節(jié)點(diǎn)關(guān)聯(lián)的局部子圖模式通常隨著鄰域范圍的變化而變化。
▲ 圖1：一階鄰域同配率和二階鄰域同配率的節(jié)點(diǎn)級(jí)統(tǒng)計(jì)直方圖的可視化。
值得注意的是，節(jié)點(diǎn)同配率的計(jì)算僅能簡(jiǎn)單傳達(dá)鄰域節(jié)點(diǎn)和中心節(jié)點(diǎn)的標(biāo)簽一致性，但忽略了鄰域標(biāo)簽是呈現(xiàn)什么樣的分布，這對(duì)局部模式分析同樣重要。受信息論中香農(nóng)熵的啟發(fā)，我們提出使用標(biāo)簽熵 來衡量鄰域標(biāo)簽分布：
其中，，1e-10 是一個(gè)常數(shù)，用以避免溢出。標(biāo)簽熵作為節(jié)點(diǎn)級(jí)指標(biāo)，量化了給定節(jié)點(diǎn)的鄰域標(biāo)簽分布，并指示了以該節(jié)點(diǎn)為中心的子圖的隨機(jī)性。顯然，當(dāng)鄰居節(jié)點(diǎn)的標(biāo)簽分布均勻時(shí)，標(biāo)簽熵趨于最大。相反，如果給定節(jié)點(diǎn)的鄰域標(biāo)簽全部屬于同一類，則標(biāo)簽熵將是最小的。
▲ 圖2：一階鄰域標(biāo)簽熵和二階鄰域標(biāo)簽熵的節(jié)點(diǎn)級(jí)統(tǒng)計(jì)直方圖的可視化。
如圖 2 所示，同配性圖中的大多數(shù)節(jié)點(diǎn)的 較低，而異配性圖中的大多數(shù)節(jié)點(diǎn)的 較高。此外，對(duì)于所有四個(gè)圖，與 相比， 的統(tǒng)計(jì)直方圖總體上向右移動(dòng)。這些觀察表明，隨著鄰域范圍的增加，每個(gè)節(jié)點(diǎn)的鄰居標(biāo)簽分布趨于均勻。更重要的是，從圖 2（c）和（d）中，可以容易地發(fā)現(xiàn)一些明顯的聚類現(xiàn)象，表明圖中可能存在幾種類型的重要局部模式。
2.2 近鄰可聚合性
?
為了便于討論近鄰的可聚集性，我們首先給出鄰域同配傾向性的定義：
我們首先理論證明了鄰域同配傾向性和鄰域標(biāo)簽分布的關(guān)系：
隨即，我們還給出了隨鄰域范圍變化,鄰域同配傾向性的變化趨勢(shì)：
具體證明過程可見論文。
03 方法介紹
當(dāng)前基于譜濾波的圖神經(jīng)網(wǎng)絡(luò)多采用多項(xiàng)式參數(shù)化濾波器學(xué)習(xí)的形式。這種形式避免了特征分解，計(jì)算效率較高。另一個(gè)優(yōu)點(diǎn)就是具有局部性，多項(xiàng)式的階數(shù) K 決定了濾波器的局部化范圍，即 K 階多項(xiàng)式譜濾波器完全局限于節(jié)點(diǎn) 的 鄰域內(nèi)。
但是呢，當(dāng)前基于譜濾波的方法有一個(gè)顯著的特點(diǎn)：濾波器是全局節(jié)點(diǎn)通用的且頻率系數(shù)固定的單一濾波器。這個(gè)特點(diǎn)和多項(xiàng)式濾波的局部性結(jié)合在一起，就產(chǎn)生了新的問題：全局共享的單一濾波器相當(dāng)于是在不同子圖上訓(xùn)練的濾波器的trade-off。對(duì)于每個(gè)以節(jié)點(diǎn)為中心的子圖而言，這個(gè)全局濾波器肯定不是最差的，但應(yīng)該也不是最優(yōu)的。
直觀上，與學(xué)習(xí)整個(gè)圖中不同局部模式的全局共享濾波器 相比，學(xué)習(xí)特定于節(jié)點(diǎn)的節(jié)點(diǎn)濾波器 以適應(yīng)其所在的局部模式似乎是更好的選擇。為此，本文重新思考這種全局一致的譜圖濾波形式，并嘗試提出一種局部化的譜濾波器學(xué)習(xí)方法來打破這一限制。
NFGNN 首先引入圖信號(hào)處理中的廣義平移算子 ：
其中 表示 的第 個(gè)元素。通過對(duì)濾波信號(hào) 施加核化算子，可以使其定位在特定節(jié)點(diǎn)上。因此，為了自適應(yīng)局部濾波的目的，首先可以通過 將濾波器信號(hào) 定位到在目標(biāo)節(jié)點(diǎn) 上，將其定義為 ，然后與 執(zhí)行譜濾波：
其中 ，那我們?yōu)榱擞?jì)算的效率問題，進(jìn)一步地用多項(xiàng)式來參數(shù)化 ，從而得到節(jié)點(diǎn)導(dǎo)向的局部化濾波形式：
進(jìn)一步地，考慮到濾波系數(shù)矩陣 的參數(shù)復(fù)雜度和優(yōu)化問題，我們對(duì)其進(jìn)行低秩逼近重參數(shù)化。 由兩個(gè)可訓(xùn)練參數(shù)矩陣 近似，其中 和 。
可以很容易地觀察到，。這意味著 的每一列都可以視為 。因此， 相當(dāng)于一組基礎(chǔ)濾波器，而 對(duì)應(yīng)于節(jié)點(diǎn) 的濾波器權(quán)重。
根據(jù) ，通過對(duì) 中的基礎(chǔ)濾波器進(jìn)行加權(quán)組合，可以獲得專用于 的濾波器。所以，對(duì)于 ，由于其可以視為與節(jié)點(diǎn)相關(guān)的參數(shù)，我們應(yīng)用了一個(gè)簡(jiǎn)單但有效的非線性變換 來學(xué)習(xí)：。
04 實(shí)驗(yàn)
我們?cè)诙鄠€(gè)基準(zhǔn)數(shù)據(jù)集上進(jìn)行了全面的實(shí)驗(yàn)，以評(píng)估所提出的方法的有效性。
4.1 性能對(duì)比
在采用稀疏劃分的半監(jiān)督學(xué)習(xí)中，NFGNN 在 6 個(gè)數(shù)據(jù)集上表現(xiàn)出色，并在剩余的 4 個(gè)數(shù)據(jù)集上與基準(zhǔn)模型相比顯示出可比結(jié)果。此外，在全監(jiān)督學(xué)習(xí)設(shè)置下，NFGNN 在 7 個(gè)數(shù)據(jù)集上優(yōu)于所有基準(zhǔn)模型，在其他 3 個(gè)數(shù)據(jù)集上取得了可比結(jié)果。
4.2 節(jié)點(diǎn)級(jí)分析
▲ 圖3 不同同配比例區(qū)間內(nèi)的節(jié)點(diǎn)分類準(zhǔn)確率。
本文提出的 NFGNN 旨在解決混合局部模式問題。因此，我們根據(jù)鄰近節(jié)點(diǎn)的同配性比例 將測(cè)試節(jié)點(diǎn)劃分為 5 個(gè)不同區(qū)間，并報(bào)告每個(gè)區(qū)間的平均準(zhǔn)確率。GCN、僅有 的 NFGNN（標(biāo)記為 NFGNN w/o NF）和完整的 NFGNN 的結(jié)果如圖 3 所示。
值得注意的是，NFGNN w/o NF 相當(dāng)于使用切比雪夫多項(xiàng)式學(xué)習(xí)一個(gè)全局一致的濾波器。
與 GCN 不同，如圖 3（c）和（d）所示，NFGNN 在所有五個(gè)區(qū)間上均表現(xiàn)出了良好且相似的性能。這表明，只要可訓(xùn)練數(shù)據(jù)量足夠，NFGNN 可以有效捕獲各種局部模式。
此外，如圖 3（a）和（b）所示，無論是 NFGNN 還是 NFGNN w/o NF 都比 GCN 在半監(jiān)督節(jié)點(diǎn)分類任務(wù)上表現(xiàn)更好。這表明，即使在半監(jiān)督情況下，自適應(yīng)學(xué)習(xí)的濾波器也不比預(yù)設(shè)計(jì)的濾波器表現(xiàn)差。
▲ 圖4 節(jié)點(diǎn)對(duì) 之間的濾波系數(shù)平均距離 。
正如之前討論的，局部模式也可以根據(jù)節(jié)點(diǎn)的鄰域子圖來分析。一般來說，如果節(jié)點(diǎn)的局部模式相似，那么為這些節(jié)點(diǎn)學(xué)習(xí)的濾波器的系數(shù)也應(yīng)該相似。因此，本文中還計(jì)算了所有節(jié)點(diǎn)對(duì) 的 1 階鄰居的 Jaccard 相似系數(shù) ，以衡量節(jié)點(diǎn)之間 1 階局部模式的相似性，然后，對(duì)于每對(duì)節(jié)點(diǎn) ，根據(jù) 的區(qū)間計(jì)算平均系數(shù)距離 。
如圖 4 所示，總的來說，可以看到， 越大，相應(yīng)的 越大。并且，具有相同標(biāo)簽的節(jié)點(diǎn)對(duì)的 小于具有不同標(biāo)簽的節(jié)點(diǎn)對(duì)?？梢暬Y(jié)果表明，NFGNN 至少能夠?qū)W習(xí)到多種1跳局部模式的特性，符合預(yù)期。
4.3 濾波器可視化
首先根據(jù) 2 跳鄰域內(nèi)的同配比率將節(jié)點(diǎn)劃分為三個(gè)子集：
▲ 圖5 節(jié)點(diǎn)級(jí)濾波器可視化
05 總結(jié)
本文深入分析了圖數(shù)據(jù)中局部模式的特性及其近鄰的可聚合性?；谶@些觀察，本章重新審視了基于譜的圖神經(jīng)網(wǎng)絡(luò)（GNN）模型，并提出了 NFGNN ——一種針對(duì)節(jié)點(diǎn)的融合全局-局部信息的圖譜濾波方法。NFGNN 的核心優(yōu)勢(shì)在于，它不同于傳統(tǒng)使用全局濾波器的策略，而是通過轉(zhuǎn)移至特定節(jié)點(diǎn)的濾波器來實(shí)現(xiàn)局部譜濾波，從而有效地應(yīng)對(duì)局部模式的挑戰(zhàn)。
此外，通過引入重參數(shù)化策略，NFGNN 以一種簡(jiǎn)單且有效的方式實(shí)現(xiàn)了節(jié)點(diǎn)導(dǎo)向的濾波。在多個(gè)真實(shí)世界的圖數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)結(jié)果驗(yàn)證了 NFGNN 在當(dāng)前現(xiàn)有方法中的卓越性能，展示了其在處理局部圖模式方面的顯著優(yōu)勢(shì)。
