Heterogeneous Graph Attention Network
2019 WWW
論文連結：https://arxiv.org/pdf/1903.07293
代碼：
- 官方代碼：https://github.com/Jhy1993/HAN
- DGL實作：https://github.com/dmlc/dgl/tree/master/examples/pytorch/han
- 個人實作：https://github.com/ZZy979/pytorch-tutorial/tree/master/gnn/han
1.引言
真實世界的資料通常是圖結構，例如社交網絡、引用網絡、網際網路等，GNN是一種強大的用于圖資料深度表示學習的方法
注意力機制能夠處理變長資料，使模型能夠聚焦于資料最突出的部分，GAT是一種将注意力機制用于同構圖的GNN模型
下圖是一個IMDB異構圖的例子：
該論文中的一個重要概念是元路徑，元路徑表示兩個頂點之間經過特定類型頂點的連接配接關系，表達了異構圖中的語義資訊
例如在上圖中，“電影-演員-電影”(MAM)是一種元路徑，含義是“同一個演員出演的兩部電影”，表達的語義資訊是“識别電影類型”；“電影-導演-電影”(MDM)是另一種元路徑，含義是“同一個導演執導的兩部電影”（表達的語義資訊是“電影風格”，猜的）
該論文提出了異構圖注意力網絡模型HAN，該模型考慮了頂點層次的注意力和語義層次的注意力
頂點層次的注意力旨在學習基于元路徑的鄰居的重要性，并給它們賦予不同的注意力權重
例如，《終結者》、《終結者2》和《泰坦尼克号》都是導演詹姆斯·卡梅隆的電影，即《終結者2》和《泰坦尼克号》都是《終結者》基于元路徑MDM的鄰居；如果要識别《終結者2》的類型為科幻電影，注意力應該更集中于《終結者》而不是《泰坦尼克号》
語義層次的注意力旨在學習每種元路徑的重要性，并給它們賦予适當的注意力權重
例如，《終結者2》是《終結者》基于元路徑MAM的鄰居（都由施瓦辛格主演），而《鳥人》是《終結者》基于元路徑MYM的鄰居（都拍攝于1984年）；如果要識别《終結者》的類型，MAM比MYM起更重要的作用
也就是說，将不同的元路徑同等對待會削弱異構圖中的語義資訊
該論文的主要貢獻如下：
- 首次将注意力機制應用于異構圖神經網絡
- 提出了HAN模型，同時考慮了頂點層次的注意力和語義層次的注意力
- 通過實驗證明提出的模型優于SOTA模型，另外對于異構圖分析有較好的可解釋性
2.相關工作
- GNN
- 網絡嵌入
3.預備知識
-
異構圖：G=(V, E)，頂點和邊有多種類型
例如圖1是一個包含演員、電影、導演三種頂點以及“演員-出演-電影”和“導演-執導-電影”兩種邊的異構圖
-
元路徑：兩個頂點之間的綜合關系(composite relation)，即兩個頂點之間經過特定類型頂點的連接配接關系
A 1 → R 1 A 2 → R 2 ⋯ → R l A l + 1 A_1 \xrightarrow{R_1} A_2 \xrightarrow{R_2} \cdots \xrightarrow{R_l} A_{l+1} A1R1
A2R2
⋯Rl
Al+1
（上面提到的元路徑MAM和MDM都是l=2）
例如在圖1中，“電影-演員-電影”(MAM)是一種元路徑，表示“同一個演員出演的兩部電影”，執行個體有m1-a1-m2, m1-a3-m3, m2-a2-m3, m1-a1-m1等；電影-導演-電影”(MDM)是另一種元路徑，含義是“同一個導演執導的兩部電影”
-
基于元路徑的鄰居：給定一個頂點i和元路徑Φ，頂點i的基于元路徑Φ的鄰居 N i Φ N_i^\Phi NiΦ 定義為通過元路徑Φ與頂點i相連的頂點集合，包括頂點i本身
在圖1的例子中，m1基于元路徑MAM的鄰居集合為 N m 1 M A M = { m 1 , m 2 , m 3 } N_{m_1}^{MAM}=\{m_1,m_2,m_3\} Nm1MAM={m1,m2,m3}，基于元路徑MDM的鄰居集合為 N m 1 M D M = { m 1 , m 2 } N_{m_1}^{MDM}=\{m_1,m_2\} Nm1MDM={m1,m2}
基于元路徑的鄰居異構圖中多種結構資訊和豐富的語義資訊
可以通過鄰接矩陣序列相乘的方式得到基于元路徑的鄰居
4.HAN模型
HAN是用于異構圖的半監督GNN模型
層級注意力結構：頂點層次的注意力→語義層次的注意力
模型結構如下：
- 首先使用頂點層次的注意力來學習基于元路徑的鄰居的注意力權重，并将它們聚集起來得到語義相關的頂點嵌入（元路徑=語義）
- 之後通過語義層次的注意力來學習不同元路徑的注意力權重，并将上一步得到的語義相關的頂點嵌入組合起來得到最終的頂點嵌入，用于特定的任務
4.1 頂點層次的注意力
基于不同元路徑的鄰居對學習頂點嵌入有不同的影響，即重要性不同，是以引入頂點層次的注意力來學習基于元路徑的鄰居的重要性，并将它們聚集起來得到一個頂點嵌入
首先，由于不同的類型的頂點有不同的特征空間，是以通過一個類型相關的轉換矩陣将不同類型的頂點特征映射到相同的特征空間
其中 h i h_i hi 是頂點i的原始特征， h i ′ h_i' hi′ 是映射後的特征， ϕ i \phi_i ϕi 是頂點i的類型
之後，使用自注意力來學習不同鄰居的重要性
給定通過元路徑Φ連接配接的頂點對(i, j)（即j是i的基于元路徑Φ的鄰居），令 e i j Φ e_{ij}^\Phi eijΦ 表示頂點j對頂點i的重要性，定義為
其中attnode表示計算頂點層次注意力的深度神經網絡（具體結構見公式(3)）
給定元路徑Φ， a t t n o d e {att}_{node} attnode 對所有基于元路徑Φ的頂點對是共享的
注意 e i j Φ e_{ij}^\Phi eijΦ 是不對稱的，即j對i的重要性和i對j的重要性可以不同，是以頂點層次的注意力保留了異構圖的不對稱性
對 e i j Φ e_{ij}^\Phi eijΦ 歸一化即可得到基于元路徑的鄰居的權重參數 α i j Φ \alpha_{ij}^\Phi αijΦ
（和HetGNN的注意力公式一樣！都來自GAT）
（由此推斷， a t t n o d e {att}_{node} attnode 的具體形式就是 σ ( a Φ T [ h i ′ ∣ ∣ h j ′ ] ) \sigma(a_\Phi^T [h_i^′ || h_j^′]) σ(aΦT[hi′∣∣hj′]) ）
其中σ是激活函數，||表示向量拼接， a Φ a_\Phi aΦ 是元路徑Φ的頂點層次的注意力向量（可學習參數）
使用 α i j Φ \alpha_{ij}^\Phi αijΦ 對鄰居的映射後的特征權重即可頂點i的基于元路徑Φ的嵌入：
這一步就是聚集操作
由于 α i j Φ \alpha_{ij}^\Phi αijΦ 是和元路徑Φ相關的，是以可以捕獲元路徑Φ所表示的語義資訊，基于元路徑的嵌入也叫語義相關的嵌入
論文中還将頂點層次的注意力擴充到多頭注意力，即将(4)式重複K次并将向量拼接起來：
根據以上過程，可以計算出每個頂點基于每個元路徑的嵌入表示
論文中給出了一張圖來解釋計算過程
虛線以上對應頂點層次的注意力，每個大圈表示針對一種元路徑，通過聚集鄰居的特征得到頂點i基于元路徑的嵌入的過程
虛線以下對應語義層次的注意力，即對頂點i基于每種元路徑的嵌入權重得到最終嵌入
4.2 語義層次的注意力
在異構圖中，每個頂點有多種元路徑（例如“電影”頂點有MAM和MDM兩種元路徑），是以包含多種語義資訊，而4.1節中基于元路徑的嵌入隻能反映一種語義資訊
是以論文中提出了語義層次的注意力來學習不同元路徑的重要性，進而将每個頂點基于不同元路徑的嵌入融合為一個嵌入
設 Z Φ p Z_{\Phi_p} ZΦp 為基于元路徑 Φ p \Phi_p Φp 的頂點嵌入， β Φ p \beta_{\Phi_p} βΦp 為元路徑 Φ p \Phi_p Φp 的注意力權重
其中 a t t s e m {att}_{sem} attsem 表示計算語義層次注意力的深度神經網絡，具體計算方法如下
首先通過一個全連接配接層将上一步得到的基于元路徑的嵌入（語義相關的嵌入）進行轉換，使用轉換後的嵌入與語義層次的注意力向量q（可學習參數）的相似度來表示每個元路徑的重要性 w Φ p w_{\Phi_p} wΦp
（公式右邊的i表示頂點，左邊的i應該是元路徑的編号p，z的上标應該是 Φ p \Phi_p Φp ，和w的下标對應）
其中的參數對所有的元路徑是共享的
對 w Φ p w_{\Phi_p} wΦp 歸一化即可得到元路徑的權重參數 β Φ p \beta_{\Phi_p} βΦp
β Φ p \beta_{\Phi_p} βΦp 表達了一個元路徑在特定任務中的重要性，一個元路徑對于不同任務的權重可能不同
使用 β Φ p \beta_{\Phi_p} βΦp 對基于元路徑的嵌入權重即可得到最終的頂點嵌入
這一步對應圖3(b)
4.3 模型分析
- 可以處理不同類型的頂點和邊并融合異構圖豐富的語義資訊
- 計算高效，可并行化
- 注意力參數共享，是以參數數量不随圖的規模變化
- 學習到的頂點嵌入可解釋性好
5.實驗
5.1 資料集
- DBLP：包含論文§、學者(A)、會議©、關鍵詞(T)四種頂點，學者分為資料庫、資料挖掘、機器學習、資訊檢索四個領域，根據學者發表過論文的會議标注學者的研究領域，學者頂點的輸入特征是其關鍵詞的詞袋表示，元路徑包括APA, APCPA, APTPA
- ACM：包含論文§、學者(A)、主題(S)三種頂點，論文分為資料庫、無線通信、資料挖掘三類，根據論文所屬的會議标注論文标簽，論文頂點的輸入特征是其關鍵詞的詞袋表示，元路徑包括PAP和PSP
- IMDB：包含電影(M)、演員(A)、導演(D)三種頂點，電影分為動作、喜劇、話劇三類，電影頂點的輸入特征是其劇情的詞袋表示，元路徑包括MAM, MDM
閱讀代碼後注：
- 注意到每個資料集選擇的所有元路徑的起點和終點都是相同的類型，是以在代碼中分别構造該類型的頂點基于每種元路徑的鄰居的同構圖（可使用
dgl.metapath_reachable_graph()
- 所謂頂點分類和聚類兩個任務其實隻有評價名額不同，模型輸出的頂點嵌入和損失函數都一樣，差別隻在于如何由頂點嵌入及标簽計算評價名額
5.2 Baseline
用于比較的SOTA baseline包括（異構）網絡嵌入方法和基于GNN的方法
- DeepWalk：基于随機遊走的網絡嵌入方法（用于同構圖）
- ESim：異構圖嵌入方法，從多個元路徑捕獲語義資訊
- metapath2vec：異構圖嵌入方法，使用基于元路徑的随機遊走，使用skip-gram做嵌入
- HERec：異構圖嵌入方法，設計了一個類型限制政策來過濾頂點序列，使用skip-gram做嵌入
- GCN：半監督的圖卷積網絡，用于同構圖
- GAT：半監督的神經網絡，在同構圖上使用注意力機制
- HAN_nd：HAN的變體，移除了頂點層次的注意力，給每個鄰居賦予相同的權重
-
HAN_sem：HAN的變體，移除了語義層次的注意力，給每個元路徑賦予相同的權重
（與最後兩個變體的比較實際上是消融實驗）
5.3 實作細節
優化器Adam，學習率0.005，正則項參數0.001
語義層次的注意力向量q的維數128
注意力頭數K=8，dropout=0.6
嵌入維數為64（即每個注意力頭的嵌入維數為8）
代碼：https://github.com/Jhy1993/HAN
5.4 分類
使用k=5的KNN分類器進行頂點分類，運作10次取平均的Macro-F1和Micro-F1
（實際上代碼中用的根本不是KNN，就是一個全連接配接層？）
5.5 聚類
使用KMeans方法進行頂點聚類，K設定為類别個數，ground truth與頂點分類任務相同，使用NMI和ARI來評價聚類結果（和HetGNN一樣），運作10次取平均結果
5.6 層級注意力機制分析
圖4顯示（論文）P831注意力權重最高的鄰居是P699和P133，這兩篇論文所屬的類别和P831相同，證明頂點層次的注意力有效
圖5顯示在DBLP資料集上，HAN賦予元路徑APCPA最高的權重，因為元路徑APCPA比APA在區分學者的研究領域上更有意義
5.7 可視化
5.8 參數實驗
論文中分析了三個超參數對模型性能的影響
- 最終嵌入Z的維數
- 語義層次注意力向量q的維數
- 注意力頭數K
【論文筆記】HANHeterogeneous Graph Attention Network1.引言2.相關工作3.預備知識4.HAN模型5.實驗6.結論
6.結論
該論文提出了基于注意力機制的半監督異構圖神經網絡模型HAN
HAN可以捕獲異構圖複雜的結構資訊和豐富的語義資訊
HAN分别利用頂點層次的注意力和語義層次的注意力來學習頂點和元路徑的重要性
分類和聚類的實驗結果證明了HAN的有效性和可解釋性