【論文筆記】HetGNN

Heterogeneous Graph Neural Network

2019 KDD

論文連結：https://dl.acm.org/doi/pdf/10.1145/3292500.3330961

官方代碼：https://github.com/chuxuzhang/KDD2019_HetGNN

個人實作：https://github.com/ZZy979/pytorch-tutorial/tree/master/gnn/hetgnn

1.引言

（本文研究的）異構圖不僅包含多個類型的頂點之間的結構化關聯（邊），還包含與每個頂點關聯的非結構化内容

例如：

• 學術圖包含學者、論文和期刊三種頂點，“作者-寫-論文”、“論文-引用-論文”和“論文-發表于-期刊”三種邊，另外，學者頂點還包含id（屬性），論文頂點包含摘要（文本），這裡的屬性和文本就是非結構化内容
• 評論圖包含使用者和物品兩種頂點，“使用者-評論-物品”一種邊，另外，使用者頂點還包含id（屬性），物品頂點還包含簡介（文本）和圖檔（圖像），這裡的屬性、文本和圖像就是非結構化内容

盡管在同構或異構圖嵌入、屬性圖嵌入以及圖神經網絡等方面已經有了大量的研究，但很少有研究能同時考慮異構結構資訊（頂點和邊）和異構内容資訊（屬性、文本、圖像等）

論文中總結了異構圖嵌入面臨的挑戰

• (C1) 如何為每個頂點采樣與它們的嵌入生成強相關的異構鄰居？
• (C2) 如何編碼頂點内容，解決異構圖中不同頂點的内容異構？
• (C3) 考慮不同的頂點類型對頂點嵌入的影響，如何聚集異構鄰居的特征資訊？

為了解決以上挑戰，論文提出了HetGNN——用于異構圖表示學習的異構圖神經網絡模型

2.問題定義

（1）内容相關的異構圖

内容相關的異構圖是指具有多種頂點類型和邊類型的圖 G = ( V , E , O V , R E ) G=(V, E, O_V, R_E) G=(V,E,OV​,RE​) ，其中 O V O_V OV​ 和 R E R_E RE​ 分别表示頂點和邊的類型集合，另外，每個頂點還關聯了異構内容（例如屬性、文本、圖像等）

前面提到的學術圖和評論圖都是内容相關的異構圖的例子

（2）異構圖表示學習

給定一個内容相關的異構圖 G = ( V , E , O V , R E ) G=(V, E, O_V, R_E) G=(V,E,OV​,RE​) ，頂點内容集合為C，目标是設計一個模型 F : V → R d F: V→R^d F:V→Rd 來學習一個d維嵌入，該嵌入能夠同時對異構結構資訊（頂點和邊）和異構非結構資訊（内容）進行編碼

學習到的頂點嵌入可用于多種圖挖掘任務，例如連接配接預測、推薦、頂點分類等

3.HetGNN模型

模型包括4部分：

• 采樣異構鄰居(C1)
• 頂點的異構内容嵌入(C2)
• 聚集異構鄰居(C3)
• 目标函數和模型訓練

每一部分的功能如下：

• 設計了一個基于重新開機政策的随機遊走方法，來為異構圖中的每一個頂點采樣固定數量的強相關的異構鄰居
• 設計了一個異構圖神經網絡來根據頂點類型對采樣的鄰居進行分組，包含兩個子產品：
  • 第一個子產品使用RNN來編碼異構内容的“深度”特征互動，進而得到每個頂點的内容嵌入
  • 第二個子產品使用另一個RNN來聚集不同的鄰居組（類型）的内容嵌入，進而得到這個類型的特征表示；之後通過注意力機制來衡量不同異構頂點類型的影響，将它們組合起來，獲得最終的頂點嵌入
• 最後，利用一個圖上下文損失函數和小批量梯度下降方法來訓練模型

模型的整體結構如下圖所示

3.1 采樣異構鄰居(C1)

用于同構圖的GNN通過頂點的直接鄰居來聚集特征資訊，這種做法在異構圖中會産生幾個問題：

• 異構圖中的直接鄰居可能隻有部分類型的頂點（例如學術圖中學者頂點的直接鄰居隻有論文頂點），學習出來的頂點嵌入缺乏表示能力
• 每個頂點的鄰居數量可能差别很大
• 異構鄰居不同的内容特征需要使用不同的特征變換來處理

為了解決以上問題以及挑戰C1，論文提出了基于重新開機随機遊走(RWR)的異構鄰居采樣政策

• 第1步：采樣固定長度的RWR。從任意頂點v開始随機遊走，遊走的過程會重複地經過v的鄰居或者以一個機率p傳回初始頂點。RWR在收集到固定數量的鄰居頂點後會停止，記為RWR(v)。采樣序列中不同類型的頂點數量是受限的，進而確定采樣到的鄰居包含了所有類型的頂點。
• 第2步：将不同類型的鄰居分組。對于每個頂點類型t，根據頻率選出top k個頂點作為v的t類型鄰居集合 N t ( v ) N_t(v) Nt​(v)

該政策避免了上面提到的問題：

• RWR為每個頂點收集了所有類型的鄰居
• 采樣的鄰居數量是固定的，選擇的是最頻繁通路的鄰居頂點
• 相同類型（有相同的内容特征）的頂點被分組，進而可以使用基于類型的聚集

3.2 頂點的異構内容嵌入(C2)

為了解決挑戰C2，論文中設計了一個子產品用于将頂點v的異構内容 C v C_v Cv​ 通過一個神經網絡 f 1 f_1 f1​ 編碼為固定長度的嵌入，如下圖所示

首先根據不同内容的類型使用不同的方法進行預訓練（例如屬性内容使用one-hot編碼，文本内容使用Par2Vec，圖像内容使用CNN），将頂點v的第i個内容的特征表示記為 x i ∈ R d f × 1 , 1 ≤ i ≤ ∣ C v ∣ x_i∈R^{d_f×1},1≤i≤|C_v| xi​∈Rdf​×1,1≤i≤∣Cv​∣

之後使用雙向LSTM來聚集頂點v的異構内容特征，最後将LSTM層輸出的隐含狀态輸入到一個mean-pooling層（即取平均），進而得到頂點v的總體異構内容嵌入 f 1 ( v ) f_1(v) f1​(v)

其中FC是一個特征轉換層，可以是恒等變換、全連接配接層等

簡單來說就是：内容編碼→ x i x_i xi​ →雙向LSTM→取平均→ f 1 ( v ) f_1(v) f1​(v)

這個内容編碼架構有如下優點：

• 複雜度相對較低（參數少），是以實作模型和調參都相對容易
• 之前的模型直接将不同類型的内容特征拼接為一個向量，而該模型使用了雙向LSTM來捕獲“深度”特征互動，能夠融合異構内容資訊，進而獲得更強的表示能力
• 添加額外的内容特征很靈活，模型友善拓展

3.3 聚集異構鄰居(C3)

為了解決挑戰C3，論文中設計了另一個子產品——基于類型的神經網絡來聚集異構鄰居的内容嵌入

該子產品包括兩步：

• 同類型鄰居聚集
• 類型組合

3.3.1 同類型鄰居聚集

在3.1節中通過RWR每個頂點的所有類型的鄰居，這一步使用一個神經網絡 f 2 t f_2^t f2t​ （注意和類型t相關）來聚集每個頂點v的t類型鄰居 N t ( v ) N_t(v) Nt​(v) 的内容嵌入

該神經網絡的結構與3.2節中的類似，使用雙向LSTM來聚集每個鄰居v’的内容嵌入 f 1 ( v ′ ) f_1(v') f1​(v′) ，最後将LSTM層輸出的隐含狀态輸入到一個mean-pooling層（即取平均），進而得到頂點v的t類型鄰居的聚集嵌入 f 2 t ( v ) f_2^t (v) f2t​(v)

對于不同頂點類型的鄰居使用不同的雙向LSTM來聚集

3.3.2 類型組合

前一步對每個頂點v生成了 ∣ O V ∣ |O_V| ∣OV​∣ 個聚集嵌入 f 2 t ( v ) , t ∈ O V f_2^t (v),t∈O_V f2t​(v),t∈OV​ ，這一步使用注意力機制來組合基于類型的鄰居嵌入，如下圖所示

使用注意力機制的動機是不同類型的鄰居會對頂點v的最終嵌入表示有不同的貢獻，用 α v , t \alpha ^{v, t} αv,t 表示t類型的鄰居對頂點v的注意力權重，則頂點v的最終嵌入表示為

（這裡的 E v \mathcal{E}_v Ev​ 就是第2節提到的F）

α v , t \alpha ^{v, t} αv,t 的計算公式如下：

其中 F ( v ) = { f 1 ( v ) } ∪ { f 2 t ( v ) ∣ t ∈ O V } F(v)=\{ f_1 (v) \} \cup \{ f_2^t (v) | t \in O_V \} F(v)={f1​(v)}∪{f2t​(v)∣t∈OV​}

（就是對基于類型的鄰居嵌入使用GAT）

3.4 目标函數和模型訓練

目标函數定義如下：

C N v t {CN}_v^t CNvt​ 表示頂點v的t類型上下文頂點

注意 o 1 o_1 o1​ 不是誤差函數而是似然函數，是以是最大化， v c v_c vc​ 來自頂點v的随機遊走結果，是以該目标函數的含義是使得随機遊走結果出現的機率最大

論文中使用負采樣技術來優化目标函數 o 1 o_1 o1​ ，具體做法是對于頂點v的每一個t類型的鄰居 v c v_c vc​ ，從噪聲分布 P t ( v c ) P_t(v_c) Pt​(vc​) 中采樣一個負樣本 v c ′ v_{c'} vc′​ ，則 log ⁡ p ( v c ∣ v ; Θ ) \log p(v_c|v;\Theta) logp(vc​∣v;Θ) 的估計退化為交叉熵損失

是以目标函數(7)轉化為

4.實驗

實驗目的是回答4個問題：

• (RQ1) HetGNN和SOTA基準模型相比在圖挖掘任務上的表現如何，包括
  • (RQ1-1) 連接配接預測
  • (RQ1-2) 個性化推薦
  • (RQ1-3) 頂點分類/聚類
• (RQ2) HetGNN和SOTA基準模型相比在歸納性(inductive)圖挖掘任務上的表現如何
• (RQ3) HetGNN的不同組成部分（例如3.2異構内容編碼器、3.3異構鄰居聚集器）對模型性能有什麼影響
• (RQ4) 各超參數（例如嵌入次元、異構鄰居采樣數量）對模型的性能有什麼影響

4.1 實驗設計

4.1.1 資料集

論文使用了4個異構圖資料集，包括兩個學術圖和兩個評論圖

學術圖資料集來自AMiner，評論圖資料來自Amazon

4.1.2 Baseline

• metapath2vec：異構圖嵌入模型，使用基于metapath的遊走和異構skipgram模型來學習頂點的嵌入表示
• ASNE：屬性圖的嵌入模型，利用頂點的隐含特征和屬性特征來學習頂點的嵌入表示
• SHNE：帶文本屬性的異構圖的嵌入模型，通過聯合優化圖的結構相近度和文本語義相關度來學習頂點的嵌入表示
• GraphSAGE：圖神經網絡模型，使用神經網絡來聚集頂點鄰居的特征資訊
• GAT：圖神經網絡模型，使用自注意力神經網絡來聚集頂點鄰居的特征資訊

4.1.3 複現

嵌入次元為128，學術圖的鄰居采樣數量為23（學者、論文、期刊分别為10, 10, 3），評論圖的鄰居采樣數量為20（使用者、物品各10）

使用Par2Vec預訓練文本内容特征，使用CNN預訓練圖像内容特征，使用DeepWalk預訓練頂點嵌入

學術圖的輸入頂點特征為文本（論文摘要）特征和預訓練的頂點嵌入；評論圖的輸入頂點特征為文本（物品描述）特征、圖檔（物品照片）特征和預訓練的頂點嵌入

使用PyTorch實作，代碼：https://github.com/chuxuzhang/KDD2019_HetGNN

4.2 應用

4.2.1 連接配接預測(RQ1-1)

哪個連接配接關系會在将來出現？

将兩個頂點的嵌入按元素相乘作為連接配接嵌入，訓練一個二分類器來預測兩個頂點之間是否存在一條邊，結果如下

對于學術圖，按年份劃分訓練集和測試集（例如對于A-I_2003，2003年之前的資料作為訓練集，2003年及之後的資料作為測試集），預測的連接配接關系分為兩種：type-1是學者之間的合作關系（學者1→論文←學者2），type-2是學者和論文之間的引用關系（學者→論文1→論文2）

對于評論圖，按順序劃分訓練集和測試集，預測的連接配接關系為使用者和物品之間的評論關系

結果表明在連接配接預測任務上，HetGNN能學到比baseline更好的頂點嵌入

4.2.2 推薦(RQ1-2)

哪個頂點應該被推薦給目标頂點？

該任務實際上和連接配接預測很相似，偏好得分定義為兩個頂點嵌入的内積

隻使用學術圖，目标是給學者推薦期刊（即預測“學者-期刊”連接配接關系），使用訓練集學習頂點嵌入，使用測試集中學者發表過論文的期刊作為groud truth，仍然按年份劃分，評價名額為top k推薦清單的準确率、召回率和F1得分，結果如下

結果表明在頂點推薦任務上，HetGNN能學到比baseline更好的頂點嵌入

4.2.3 頂點分類和聚類(RQ1-3)

給定的頂點屬于哪一個類别/類簇？

這部分包括多标簽分類(MC)和頂點聚類(NC)兩個任務

隻使用A-II學術圖，目标是将學者與4個人工選擇的研究領域比對：資料挖掘(DM)、計算機視覺(CV)、自然語言處理(NLP)和資料庫(DB)；另外，還為每個研究領域人工選擇了top 3期刊（資料集中的頂點，相當于給這些期刊頂點人工指定領域）

每個學者的标簽是發表論文最多的研究領域（通過論文所屬的期刊），使用整個資料集來學習頂點嵌入

對于多标簽分類任務，學習到的頂點嵌入用于訓練邏輯回歸分類器，評價名額為Micro-F1和Macro-F1；對于頂點聚類任務，學習到的頂點嵌入用于k-means算法的輸入，評價名額為歸一化的互資訊(NMI)和adjusted rand index (ARI)，結果如下

聚類結果的可視化如下

可以看到相同研究領域的學者嵌入距離較近，說明學習到的頂點嵌入有效

4.2.4 歸納式頂點分類和聚類(RQ2)

新頂點屬于哪一個類别/類簇？

“歸納式”展現在沒有預先學習到測試集中的頂點嵌入，需要使用訓練好的模型來推斷這些頂點的嵌入，之後進行頂點分類和聚類任務的測試

4.3 分析

4.3.1 消融實驗(RQ3)

為了研究各組成部分對模型性能的影響，論文中将HetGNN模型和3個變體進行了比較：

• No-Neigh：不考慮鄰居的影響，直接用異構内容嵌入f1(v)作為頂點嵌入
• Content-FC：把異構内容嵌入子產品的Bi-LSTM換成了全連接配接神經網絡
• Type-FC：把類型組合子產品的注意力機制換成全連接配接層（把原本要權重的各個向量先連接配接起來，然後輸入全連接配接層，得到頂點的嵌入）

HetGNN和這3個變體在A-II資料集的連接配接預測和頂點推薦任務上的表現如下

從圖中可以得出以下結論：

• HetGNN比No-Neigh的性能好，證明聚集鄰居資訊有助于學習更好的頂點嵌入
• HetGNN比Content-FC的性能好，證明Bi-LSTM比“淺層”的全連接配接結構能更好地捕獲“深度”特征互動
• HetGNN比Type-FC的性能好，證明自注意力機制比全連接配接層能更好地捕獲頂點類型的影響

4.3.2 超參數敏感性(RQ4)

論文中分析了兩個關鍵的超參數的影響：嵌入次元和異構鄰居采樣數量

不同超參數對HetGNN在A-II資料集的連接配接預測和頂點推薦任務上的性能影響如下

結果顯示：

• 性能随嵌入次元的增大而提高，但過高會導緻過拟合
• 性能随鄰居采樣數量的增大先提高後緩慢下降，原因是加入了弱相關鄰居（噪聲鄰居）的負面影響，最優範圍為20~30

5.相關工作

• 異構圖挖掘
• 圖表示學習
• 圖神經網絡

6.結論

• 本文正式定義了同時考慮同時考慮異構結構資訊和異構内容資訊的異構圖表示學習問題
• 本文提出了一個異構圖表示學習模型HetGNN，能夠捕獲結構和内容的異構，對于直推式(transductive)和歸納式(inductive)任務都很有用
• 本文在多個公共資料集上做了大量的實驗，證明了HetGNN再連接配接預測、推薦、頂點分類和聚類、歸納性頂點分類和聚類等圖挖掘任務上的性能優于SOTA方法