鑽石舞台

點擊上方 藍字關注我們

題目：Powerful Graph Convolutioal Networks with Adaptive Propagation Mechanism for Homophily and Heterophily

作者：王濤（天津大學）, 王銳（天津大學）, 金弟 (天津大學）, 何東曉（天津大學）, 黃禹霄(喬治華盛頓大學）

會議：The 36th AAAI Conference on Artificial Intelligence (AAAI-2022)

文章鏈接：https://github.com/hedongxiao-tju/HOG-GCN

代碼鏈接：https://github.com/hedongxiao-tju/HOG-GCN

1. 內容簡介

圖卷積神經網絡 (Graph Convolutional Network) 因其在處理圖結構數據方面的強大能力而被廣泛應用於各個領域。經典的 GCN 及其變體主要基於同質性假（Homophily Assumption）設計，即圖中相同類型的節點傾向於相互連接。而該假設忽略了存在於現實世界網絡中的異質性（Heterophily），即網絡中不同類型的節點傾向於相互連接的性質。現有方法主要通過聚合高階鄰居或聚合中間表徵來處理異質性，這會導致結果中產生噪聲和不相關的信息。最重要的是，這些方法並沒有改變基於同質假設而設計的傳播機制（這是 GCN 的基本部分），這使得不同類型節點的表示之間難以區分。為了解決該問題，本文設計了一種新的傳播機制，可以根據節點對之間的同質性或異質性自適應的改變傳播和聚合過程。為了自適應地學習傳播過程，我們引入了節點對之間的同質性度量（Homophily Degree），該度量融合了拓撲和屬性信息。我們將可學習的同質性程度矩陣納入到圖卷積框架中，通過端到端的訓練，使該模型能夠超越同質性假設。我們從理論上證明了我們的模型可以根據節點之間的同質性來約束節點之間表徵的相似性。在七個真實世界數據集上的實驗表明，這種新方法在異質性或低同質性的數據集上的表現優於現有的代表性方法，並在同質數據集上也獲得了有競爭力的性能。

2.方法

為了讓 GCN 的傳播機制能夠同時適用於同質性和異質性，我們提出了一種新的同質性指導的圖卷積框架HOG-GCN。該框架可以根據節點對之間的同質性程度來自動的學習傳播過程。從直覺來說，類內標籤之間的影響應該大於類間標籤之間的影響。因此我們在傳播過程中引入同質性程度矩陣，將其合併到圖卷積框架中，進行在同質性指導下的傳播，從而使框架能夠根據鄰域間的同質性程度自適應地改變特徵傳播權值。下圖是模型的框架圖。模型主要包含兩個模塊：同質性程度矩陣估計以及同質性引導的特徵傳播。

2.1 同質性程度矩陣估計（Homophily Degree Matrix Estimation）

在半監督任務下，只有部分標籤信息可用，很難直接從節點標籤中計算出同質性程度。為此，我們考慮分別從屬性空間和拓撲空間估計節點對之間的同質性，然後將其結合。

估計過程利用不使用拓撲信息的多層感知機（Multi-Layer Perceptron）：

標籤初步預估使用如下損失得到：

theta_m是最小化該損失的MLP全部參數。

根據標籤B，我們可以計算出兩個節點屬於同一類的可能性，稱為同質性程度矩陣：

經典的標籤傳播方法對第l次迭代的標籤傳播的定義如下（基於同質性假設）：

為了超越同質性假設，我們使用廣義標籤傳播來估計拓撲空間中的同質性程度矩陣。先在網絡的k階結構上進行標籤傳播，以捕獲更多同質性節點：

其中T*是使上方廣義標籤傳播來預測標籤的損失最小化的最優邊權值。

將屬性空間和拓撲空間估計的同質性程度矩陣與可調節超參數結合得到：

H即為同質性程度矩陣。

2.2 同質性指導下的傳播（Homophily-guided Propagation）

得到了同質性程度矩陣後，我們將其作為指導，來自適應地學習同質性和異質性的傳播過程。同質性程度矩陣表示兩個節點屬於同一類的程度，其可以反映網絡的同質性或異質性的潛在分布。因此，我們將可學習的同性度矩陣合併到圖卷積框架中，根據同性度自動改變鄰域之間的傳播權值。下式給出了HOG-GCN在第l次迭代中的特徵傳播過程：

2.3 優化目標（Optimization Objective）

整個框架由同質性程度矩陣估計和同質性指導下的傳播兩個部分組成。第一部分包含MLP和廣義標籤傳播。前文已經給出了MLP和廣義標籤傳播的目標函數：

在第二部分中，我們將同質性程度矩陣整合到圖卷積框架當中。將圖卷積運算的所有參數表示為Theta_g，然後根據HOG-GCN的最終輸出Z得到最優的Theta_g*：

在傳播過程中，同質性程度矩陣從屬性和拓撲信息中學習得到，並進一步用於特徵傳播。傳播過程反過來可以幫助學習更好的同質性程度矩陣。這兩個部分相互增強，將3個目標損失函數結合起來，可以以端到端的方式訓練整個過程：

其中λ和γ為超參數，用來調節3個損失的比重。

2.4 理論分析（Theoretical Analysis）

我們證明了HOG-GCN可以根據k階鄰域內節點之間的同質性來約束節點之間表示的相似性。也就是說，同質性程度較高的節點具有更相似的表示，即HOG-GCN的傳播過程可以視為最小化下面的目標函數：

可以用下式來迭代近似：

若忽略非線性，即為HOG-GCN的聚合函數。

3.實驗

本文在七個真實圖數據集上進行了結點分類實驗。數據集的統計信息如下：

本文在七個數據集上進行了節點分類實驗，結果如下：

本文在Citeseer數據集上進行了節點可視化實驗，結果如下：

5.總結

本文提出了一種新的同質性指導傳播的圖卷積網絡，該網絡可以同時適用於同質性和異質性的網絡。我們將一個可學習的同質性程度矩陣納入圖卷積框架，以建模網絡的同質性和異質性，並根據節點對之間的同質性程度進一步自適應地改變傳播過程。通過下游的半監督任務，傳播過程反過來可以進一步幫助學習同相度矩陣。這兩個過程可以相互增強並且共同訓練。在七個真實世界數據集上的實驗表明，該方法在異質性下優於現有方法，在同質性下獲得了有競爭力的性能。