基于元路徑的關系選擇圖神經網絡

吳世康

（1.北京交通大學計算機信息與技術學院，北京100044；2.交通數據分析與挖掘北京市重點實驗室，北京100044）

0 引言

現實世界中的許多數據都可以表示成異質圖［1］的形式，如學術網絡、推薦系統，等等。由于異質圖中節點類型與邊類型不唯一，其相較同質圖具有更豐富的語義信息和異質結構信息，近年來受到學者們的關注。異質圖嵌入借鑒了同質圖嵌入［2］的思想，將圖上節點表示為低維稠密的向量的同時保留圖中的異質結構信息和語義信息，以更好地服務于如節點分類［3］、節點聚類［4］等下游任務中。

主流的異質圖嵌入模型多依賴元路徑［1］，一種定義在異質圖上的高階關系，來捕獲圖中的異質結構信息和語義信息。早期的異質圖嵌入模型通過元路徑來指導圖上的隨機游走過程［5－6］，并與Deepwalk［7］結合生成節點嵌入。然而這些模型只能利用一種元路徑下的結構信息，為了更有效地挖掘圖中信息，Shang等人［8］通過人為的將多個元路徑下生成的節點嵌入融合，Zhang等人［9］提出將多種元路徑組合為元圖來指導隨機游走序列的生成。隨后，Wang等人［10］為了使模型能同時考慮節點屬性和結構信息，將圖神經網絡［11］與異質圖相結合，利用圖注意力網絡［12］在各元路徑子圖上生成節點表示后再融合。Yun等人［13］通過圖卷積［14］對模型生成的多個元路徑子圖聚合節點嵌入。

這些模型雖能對多元路徑下的信息加以利用，但它們假設各元路徑之間相互獨立，并分別為每種元路徑生成節點嵌入再融合。這種聚合信息的方式只關注了各元路徑內部的局部結構，忽略了元路徑之間的全局相關性。假設A、B、C三個作者節點，以及“共同作者”、“同會議下作者”兩種元路徑關系，A與B互為共同作者，B與C互為同會議下作者，顯然A與C之間存在一定的相關性，其研究方向大概率類似。但是僅通過“共同作者”或“同會議下作者”均不能使A與C產生聯系。若將三個節點構成多關系圖，使不同高階關系同時建模在一張圖中，就能使A與C構成全局上的相關。

基于這樣的思路，本文提出可以將異質圖轉化為基于元路徑的多關系圖，使節點間多種高階關系能同時建模。針對生成的多關系圖，一種直接的做法是利用關系圖卷積［15］來聚合圖中各關系下的鄰居信息以生成節點嵌入。但是這樣的方式忽略了不同關系對于后續任務的重要性。因此本文提出的一種基于元路徑的關系選擇圖神經網絡（Metapath-based Relational Selection Graph Neural Network，MRSGNN）。該網絡由多個關系選擇圖卷積層構成，每個關系選擇圖卷積層在關系圖卷積操作的基礎上，通過引入關系選擇模塊，從各關系內部和多關系間對鄰居信息進一步篩選，充分考慮元路徑間的全局相關性的同時對不同元路徑的重要性加以區分。在三個真實異質圖數據集上的節點分類任務上，MRSGNN分別取得了94%、92%、61%的預測準確度，均優于現有基準模型。同時在節點聚類任務上，也取得了不錯的實驗結果。

1 問題定義

定義一（異質圖）ɡ表示為異質圖或異質信息網絡（下文簡稱“圖”），ɡ＝｛V，E，A｝，其中V和E分別表示節點集和邊集，A∈R｜V｜×｜V｜為圖ɡ對應的鄰接矩陣，｜V｜為圖中節點數目。圖中任意節點v∈V或邊e∈E分別能通過映射函數?：V→T與ψ：E→R獲得節點與邊對應的類型，其中T和R分別為節點類型集與邊類型集，且滿足｜T｜＋｜R｜＞2。

定義二（異質圖嵌入［16］）旨在通過學習一個映射函數F：V→Rd，使圖中的節點v能表示為隱空間Rd中的向量并保留節點間鄰居關系與節點自身信息，其中d?｜V｜。

定義三（元路徑）m∈M是定義在異質圖ɡ上的由多種節點類型T1，T2，…，TL構成的一種高階關系，M為給定的元路徑集合。通常元路徑m可以表示為m：T1T2T3…TL＋1。每種元路徑分別代表圖上的一種高階關系，如圖1（a）這樣的學術網絡中，元路徑APA代表共同作者關系。

圖1 異質圖與元路徑子圖

定義四（元路徑鄰居集和元路徑子圖［10］）異質圖ɡ中的任意節點v可以通過元路徑m獲取其在該元路徑下的鄰居集Nm（v）。如圖1（a）中所示，將圖中所有目標節點和節點在元路徑下的鄰居構成連邊，最終能獲得如圖1（c）所示的元路徑子圖ɡm。

2 基于元路徑的關系選擇圖神經網絡

本文提出了一種基于元路徑的關系選擇圖神經網絡（MRSGNN）來同時捕獲元路徑自身的局部信息與多元路徑間的全局相關性。如圖2所示，模型首先將原始異質圖轉化為基于元路徑的多關系圖ɡM，隨后將多關系圖gM與節點特征X＝｛xv，?v∈V｝共同輸入到關系選擇圖卷積層中，從而直接聚合多關系下的鄰居信息。受到Wang等人［17］的啟發，第k層關系選擇圖卷積層中包含nk個相互獨立的關系選擇圖卷積模塊以增加模型的擬合能力。MRSGNN通過疊加多層關系選擇圖卷積層以擴大節點所感知的鄰域范圍，并利用知識跳躍層自適應的從所有中間層的輸出結果中的選擇最佳的隱層輸出作為最終的節點嵌入。以下將對MRSGNN中的各個組件進行詳細介紹。

圖2 MRSGNN模型框架

2.1 基于元路徑的多關系圖轉化

給定元路徑集合M，模型首先將異質圖ɡ＝｛V，E，A｝轉化為基于元路徑的多關系圖ɡM＝｛V，｛ɡm，Am，?m∈M｝｝（以下簡稱圖ɡM），其中Em和Am分別表示元路徑子圖ɡm對應的邊集合和鄰接矩陣，且：

后續關系選擇圖卷積層將直接在圖ɡM上聚合鄰居信息從而考慮不同關系間的相關性。

2.2 關系選擇圖卷積模塊

多關系圖ɡM（以下簡稱圖ɡM）中的節點v∈V的鄰居集可以表示為｛Nm（v），?m∈M｝，其中Nm（v）表示節點v在高階關系（元路徑）m下的鄰居集。圖3展示了關系選擇圖卷積模塊生成節點表示的過程。模塊首先通過特征轉化層將輸入的節點表示Hk－1投射到每個關系選擇圖卷積模塊i的特征子空間：

圖3 關系選擇圖卷積模塊框架

其中Wk，i∈Ra×d為可學習的參數矩陣，Hk－1∈R｜V｜×d表示上一層輸出的節點嵌入，初始值H0＝X，d為模型隱層維度

2.2.1 關系圖卷積操作

2.2.2 關系內選擇操作

其中〈，〉表示向量內積，tanh（x）＝（ex－e－x）／（ex＋e－x）。

2.2.3 關系間選擇操作

其中qk，i∈Rd為注意力向量，da為注意力向量的維度，relu（x）＝max（x，0）。

2.3 關系選擇圖卷積層

如圖4所示，每個關系選擇圖卷積層將該層對應的nk個關系選擇圖卷積模塊中生成的節點表示?hk，i按行拼接作為本層的輸出Hk∈R｜V｜×d：

圖4 關系選擇圖卷積層框架

其中Hk∈R｜V｜×d為該層第i個關系選擇圖卷積模塊的輸出，［·，·］表示向量按行拼接。令用Fk來表示第k個關系選擇圖卷積層，則每個關系選擇圖卷積層可以表示為：

2.4 知識跳躍層

為了避免模型性能隨圖神經網絡層數增加而下降，Xu等人［19］提出了知識跳躍層網絡，該網絡能從所有隱層中自適應找出最佳隱層作為輸出。基于這樣的思想，知識跳躍層將所有關系選擇圖卷積層的輸出｛Hk，1≤k≤K｝進行聚合，并通過元素級最大池化自適應的選擇最佳的隱層輸出以作為節點最終表示Z∈R｜V｜×d：

其中K為關系選擇圖卷積層的最大層數，Fmax表示元素級最大池化。

2.5 預測層

通過知識跳躍層后的節點v的嵌入可以用Zv來表示，在預測層中模型直接使用單層神經網絡根據節點表示Zv預測節點的標簽類別：

其中W0∈Rd0×d為預測層參數矩陣，d0為節點類別數，S為Softmax激活函數，其計算公式如下：

2.6 模型訓練

訓練過程中，通過計算節點v的真實標簽的獨熱向量yv與模型預測的節點類別概率分布之間的交叉損失函數，然后利用結合反向傳播（Back Propagation）和梯度下降（Gradient Descent）算法來優化模型參數。交叉熵公式如下所示：

其中C為節點類別數，VL表示帶有標簽的節點集合。最后利用訓練好的模型再次輸入圖結構以及節點特征，并將生成的測試集對應的節點嵌入作為后續節點分類、節點聚類任務的輸入。

3 實驗結果與分析

3.1 數據集介紹

為了評估MRSGNN模型的有效性，本文在三個真實的異質圖數據集進行節點分類與節點聚類實驗，其中包括兩個引文網絡數據集DBLP1https：／／dblp.uni－trier.de／、ACM2http：／／dl.acm.org／和一個電影數據集IMDB3https：／／www.imdb.com／。表1中展示了實驗使用的異質數據集的基本統計信息，各數據集的劃分遵循文獻［10］的設置。DBLP數據集包含論文（P）、作者（A）、會議（C）三種類型節點，本文將作者節點設為目標節點，作者的研究領域作為標簽，其關鍵字的詞帶表示作為節點特征。ACM數據集包含論文（P）、作者（A）、主題（S）三種類型節點，本文將論文節點為目標節點，論文的研究類型為標簽，其關鍵字的詞帶表示為節點特征。IMDB包含電影（M）、演員（A）和導演（D）三種類型的節點，本文將電影節點為目標節點，電影的類型作為標簽，其情節的詞帶表示作為節點特征。

表1 數據集統計信息

3.2 對比方法及參數設置

本文將MRSGNN模型與其他基準模型的實驗結果進行比較，各模型介紹如下：

Deepwalk［7］是定義在同質圖上的嵌入模型，該模型通過隨機游走生成節點序列從而學習節點嵌入。

Metapath2vec［5］是定義在異質圖上的嵌入模型，該模型通過元路徑隨機游走生成節點序列從而學習節點嵌入。

HERec［6］是定義在異質圖上的嵌入模型，模型通過元路徑獲得基于元路徑的高階關系圖，隨后在所獲得的圖上直接使用Deepwalk模型獲得節點嵌入。

GCN［14］是定義在同質圖上的圖神經網絡，通過在譜域上定義了圖上的卷積操作，來捕獲圖中結構信息與節點信息，從而生成節點嵌入。

GAT［12］是定義在同質圖上的圖神經網絡，該模型通過注意力機制對鄰居間信息帶權聚合的方式來生成節點嵌入。

HAN［10］是定義在異質圖上的圖神經網絡，它通過將多個元路徑子圖視為互相獨立，分別使用GAT來捕獲子圖內信息，最后利用語義級別注意力機制對多個元路徑下獲得的節點表示進行融合，是最新的基準模型。

GTN［13］是定義在異質圖上的圖神經網絡，它通過學習不同元路徑組合考慮所有潛在基于元路徑的高階關系圖，并在所得的圖上使用GCN聚合節點信息，是最新的基準模型。

在實驗中，對于Deepwalk模型，本文直接將原始異質圖作為輸入，并忽略節點和邊的異質性。對于基于單元路徑的異質圖嵌入模型（Metapath2vec、HERec）以及同質圖圖神經網絡（GCN、GAT），本文分別對每個候選元路徑對應的元路徑序列或元路徑子圖作為模型輸入進行測試，最終選出最好的結果進行展示。對于半監督學習模型（如GCN、GAT、HAN、GTN以及本文提出的模型MRSGNN），本文將各個數據集的目標節點按表1中所設大小隨機劃分為訓練集、驗證集和測試集。對于基于隨機游走的算法，游走序列的窗口大小為5，長度為100，每個節點作為初始節點游走40次，負采樣的個數設置為5。GAT、HAN的多頭注意力統一設置為8，HAN和MRSGNN中所使用的注意力向量維度為128。本文用“｛n0，…，nK｝”的形式來表示MRSGNN中所使用關系選擇圖卷積層的層數和每層所包含的關系選擇圖卷積模塊的數目，例如DBLP和ACM數據集中該超參值為｛8，1｝，IMDB為｛2，1｝。為了保證公平性，所有模型生成的節點嵌入的維度均設置為64。模型學習器為Adam，學習率設為0.005，L2正則項的權重為0.001。所有的模型統一訓練200輪，并設置早停（early stopping）的容忍系數為40。

節點分類任務的評價指標為micro-F1，其常用來衡量多分類任務下模型精準度，并兼顧了模型的精準率和召回率。節點聚類任務的評價指標為標準化互信息（Normalized Mutual Information，NMI）和調整蘭德里系數（Adjusted Rand Index，ARI）。

3.3 節點分類任務

本文在三個數據集上進行了節點分類實驗來對比模型的效果，具體實驗步驟參照了文獻［10］的做法，并使用K－近鄰（K-Nearest Neighbor，KNN）作為節點分類實驗的分類器。由于基于半監督學習的模型（GCN、GAT、HAN、GTN和MRSGNN）在訓練階段已使用訓練集和驗證集對模型參數進行更新，因此我們僅使用測試集中的節點作為KNN模型的輸入以保持公平性，并測試不同訓練率下的節點分類結果。

表2展示的是在相同數據切分規則下的所有模型10次實驗結果的平均值。從表2中可以看出，基于圖神經網絡的模型效果普遍優于傳統圖嵌入模型，而利用多種元路徑的異質圖神經網絡模型（HAN和GTN）效果普遍優于其他僅使用單一元路徑的基準模型，這反映出通過多種元路徑能更有效地捕捉圖中異質結構信息。GTN在ACM和IMDB數據集上節點分類效果均好于HAN，其潛在原因是該模型將生成的不同元路徑子圖直接相加的方式能一定程度上考慮不同元路徑間的全局相關度。本文所提出的模型MRSGNN在所有數據集上一致取得了最好的實驗結果，即便對比最新的基線模型HAN和GTN仍有不少的提升，這說明了MRSGNN通過考慮多種元路徑間的全局相關性并對不同關系下鄰居信息進行篩選能更有效地捕捉圖中的異質結構信息與語義信息。

表2 各數據集上的節點分類任務結果

3.4 節點聚類任務

本文同樣參照文獻［10］的做法在三個數據集上進行了節點聚類實驗，并僅使用測試集中的節點嵌入作為K－均值（K-means）算法的輸入，K-means算法的預設集簇數設置為每個數據集對應的節點標簽類別數。

由于K-means算法的聚類結果會受到聚類中心初始位置的影響，因此為了增加實驗結果的可靠性，我們取10次聚類實驗的平均值作為最終結果并展示在表3中。從表3中觀察可見，基于元路徑的異質圖神經網絡HAN、GTN效果要優于傳統圖嵌入模型與同質圖神經網絡模型，這也進一步證明了結合元路徑和圖神經網絡能更有效捕捉圖中的異質結構。MRSGNN在DBLP和ACM數據集上均取得了最好的結果，也側面反映出模型考慮多種元路徑間全局相關性是有必要的。特別指出，IMDB數據集上所有模型的聚類結果表現均不佳，其潛在原因可能是因為該數據集中標簽不一定準確：通常一部電影對應多種類別，而實驗中僅使用其中一個類別作為節點標簽。

表3 各數據集上的節點聚類任務結果

3.5 消融實驗

為了驗證模型中提出的關系內選擇操作和關系間選擇操作的有效性，本節分別對模型做了如下變種，2個模型變體分別為：①Intra：將每個關系選擇圖卷積模塊中去掉關系內選擇操作；②Inter：將每個關系選擇圖卷積模塊中去掉關系間選擇操作，直接將不同關系下的鄰居信息相加。我們在DBLP數據集上進行了如3.3與3.4小節的節點分類與節點聚類實驗，并使用相同的指標進行評估兩種模型變體的效果。消融實驗的結果如表4所示。

表4 DBLP數據集上消融實驗結果

通過對比可以發現，去掉關系內選擇或關系間選擇都會使模型性能下降。特別指出，若將關系間選擇中注意力模塊去掉，直接相加不同關系下的鄰居信息，模型的性能明顯下降。通過后續觀察發現DBLP數據集中對后續任務幫助最大的元路徑是APCPA，因此若直接相加兩種元路徑下的鄰居信息則會削弱APCPA元路徑在后續任務中的主導地位。這也進一步表明了不同元路徑對后續任務的重要性不同，通過關系間選擇操作能更有效地考慮不同元路徑的重要性，從而更好地融合多關系下的鄰居信息。

3.6 超參實驗

本小節將對MRSGNN中部分超參進行了敏感性實驗，并將實驗結果（Micro-F1和NMI）展示在表5中。

表5 DBLP數據集上超參實驗結果

首先對模型層數和各層模塊數進行測試，結果表明增加模型層數和模塊數均使模型效果有一定的提升，其原因在于前者能擴大感知的鄰域范圍，后者則增加了模型的擬合能力。隨后對最終生成嵌入的維度進行測試，隨著維度的增加，模型效果先提升后略有下降，其原因是MRSGNN需要合適的維度來建模圖中語義信息與結構信息，而過大的維度反而引入額外的冗余。

4 結語

本文針對異質圖場景提出了一種基于元路徑的關系選擇圖神經網絡（MRSGNN）模型來學習節點嵌入。通過將原始異質圖轉化為基于元路徑的多關系圖，模型能在引入多元路徑下局部結構信息的同時考慮不同元路徑間的全局相關性，并利用所提出關系選擇圖卷積層在聚合多關系下的鄰居信息的同時對其進一步篩選。模型在3個真實數據集的進行實驗，實驗表明MRSGNN相較其他基線模型一致取得最好的預測效果。