題目：Block Modeling-Guided Graph Convolutional Neural Networks
作者：何東曉（天津大學），梁春棟（天津大學），劉蕙心（天津大學），文明祥（天津大學），焦鵬飛（杭州電子科技大學），馮志勇（天津大學）
網絡表徵（Network Embedding）旨在學習網絡中節點的低維表示，可以用於許多下游網絡分析任務。圖卷積網絡（Graph Convolutional Networks, GCN）已經成為學習網絡表徵的一種經典範式。然而，GCN的方法是建立在同質性假設（homophily assumption）基礎上的，即相似的節點往往更傾向於在網絡中建立連接。因此GCN聚合機制不能適應於現實生活中普遍存在的異質性（heterophily）網絡。為了使GCN的傳播和聚合機制能夠高效處理不同程度的同質性和異質性(甚至二者混合)的網絡，本文將塊建模理論引入到GCN框架中，使圖卷積操作能夠實現「分類聚合」，自動學習不同類鄰居間對應的聚合規則。本文將所提算法與當前針對網絡異質性問題的先進方法進行了比較，實驗結果表明，本方法在同質性和異質性的網絡上均優於現有的方法，且對模型關鍵組件的可視化進一步對本方法作了解釋。
2. 方法本文模型主要由兩部分構成，分別為塊相似度矩陣的計算模塊和塊相似度矩陣引導下的圖卷積模塊（如下圖所示）。
在塊相似度矩陣的計算模塊部分，本文利用MLP預學習節點的軟標籤矩陣B，並用學習到的軟標籤矩陣來近似計算塊矩陣H。塊矩陣H描述了不同類節點間存在邊的概率，在異質性強網絡中不足以指導圖卷積操作實現分類聚合。基於塊矩陣H，本文進一步引入塊相似度矩陣Q來刻畫類間相似度，以實現塊相似度矩陣Q引導的分類聚合，即同類或相似類間存在更多的消息聚合。
在塊相似度矩陣引導下的圖卷積模塊部分，本文依據軟標籤矩陣B中各節點的標籤概率分布，以及塊相似度矩陣Q中的類間相似度，來計算任意兩節點在聚合過程中的消息傳遞規則。依據學習到的聚合規則，本文對網絡的原始拓撲結構進行修正，使得圖卷積過程能夠自適應地處理同質性和異質性的網絡。
2.1 基於MLP的預訓練計算塊矩陣H需要預先知道每個節點的真實標籤，然而在本文的半監督場景中，只有訓練集的真實標籤是已知的。因此，本文設計基於MLP的預訓練方式來通過節點屬性X對節點的標籤進行預測。預測節點軟標籤B的預訓練過程為
其中T_v是訓練集， Y是真實標籤， f代表多分類交叉熵損失函數。
2.2 塊相似度矩陣的計算塊建模理論揭示了網絡拓撲結構的規律，塊矩陣的概念可以表示網絡中類與類之間節點的連接模式。在已知部分真實標籤和學習到節點的軟標籤後，本文塊矩陣的計算過程如下
其中 Y_s是真實標籤與軟標籤的組合，A 是鄰接矩陣，E 是全1矩陣， %代表矩陣對應元素做除法運算。塊矩陣H 中每一元素刻畫了對應兩類節點間存在邊的概率，描述了網絡拓撲的固有規律。然而，在異質性強的網絡中，塊矩陣H 所描繪的網絡異質性規律並不能用作GCN的指導，因為GCN取得高性能的前提是網絡滿足同質性假設。
同質性假設下的GCN模型之所以性能優異，是因為同類或相似類間節點存在更多的消息聚合，使得相似節點間的表徵更平滑，最終保證模型對相似節點的預測結果更相近。為了使GCN在各種情況下保持這種能力，本文基於塊矩陣 設計了塊相似度矩陣 ，用來衡量類與類之間的相似性，其計算過程如下
Q 中坐標(i，j) 對應的元素值代表第i 類和第j 類的相似度。考慮到同類節點間應該傳遞更多的信息，本文引入增強因子alpha ，對Q 中的主對角線元素進行增強。
2.3 塊相似度矩陣指導的圖卷積基於計算得到的塊相似度矩陣Q ，本文為不同節點對分配不同的消息傳遞策略。考慮節點v_i 和節點v_j 及其對應的軟標籤向量 和 ，其中c代表類別數，軟標籤向量的第t 個分量代表了該節點屬於第t 類的概率，因此節點對(v_i,v_j) 有 c^2種類型候選組合，計算不同類型組合概率的形式化表達如下
其中 是將節點類別映射函數。由於Q 刻畫了類與類之間的相似性，因此可以將其建模為不同類間傳遞信息的概率，即越相似的兩類間傳遞消息的概率越大。因此，節點v_i 和節點v_j 間的消息傳遞概率期望的形式化公式如下
根據上述公式可以看出，兩個節點間傳遞消息的概率由節點的軟標籤向量及塊相似度矩陣Q 共同決定。對於網絡中的所有節點，上述過程的矩陣運算表示為
受益於塊相似度矩陣的性質，提供了一個在同質性和異質性網絡上均適用的消息傳遞策略，可以真正地幫助GCN實現分類聚合的目的，即同類或相似類間節點存在更多的消息聚合。本文用對原始網絡拓撲進行修正，新型的圖卷積過程如下
在模型優化階段，本文採用交叉熵損失對模型進行半監督訓練優化，同時為了保證MLP所學軟標籤的可靠性，對預訓練的MLP模塊進行了微調，整體的目標函數如下
3. 實驗
本文在六個真實網絡數據集上進行了實驗，數據集的統計信息如下
節點分類實驗 本文在六個數據集上進行了節點分類實驗，結果如下
節點可視化實驗 本文在chameleon數據集上進行了節點可視化實驗，結果如下
塊矩陣的可視化 本文分別在Cora（同質）和Chameleon（異質）上可視化了用真實標籤計算的塊矩陣 H^bar（圖a），基於軟標籤的塊矩陣H（圖b）及塊相似度矩陣 Q（圖c），結果如下圖，其中左列為Cora網絡，右列為Chameleon網絡。可以看出，在同質Cora網絡上，塊矩陣已經足以實現「分類聚合」的指導，且本文方法的塊相似度矩陣與塊矩陣有相同的作用；在異質Chameleon網絡，塊矩陣中沒有展示適於「分類聚合」的類間連接模式，而本文方法的塊相似度矩陣中同類(主對角線)間連接概率更大，更有助於圖卷積模式實現「分類聚合」。
4. 總結本文提出了一種不受網絡同質性假設約束的新型圖卷積網絡BM-GCN，將塊建模理論引入到GCN框架中，使圖卷積操作能夠實現「分類聚合」，自動學習不同類鄰居間對應的聚合規則。實驗結果表明，本方法在同質性和異質性的網絡上均優於現有的方法。
留言列表