論文題目：MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding
論文來源：WWW 2020
論文連結：https://arxiv.org/pdf/2002.01680.pdf
代碼連結：https://github.com/cynricfu/MAGNN
關鍵詞：神經網絡，表示學習，社交網絡，異質圖，attention
本文提出MAGNN模型，正如标題所言，圍繞元路徑聚合的問題展開，需要人為定義元路徑。聚合是指元路徑内部的聚合、元路徑間的聚合。在模組化過程中還融入了節點内容特征的資訊（節點屬性資訊）。
文章目錄
- 1 引言
- 2 相關定義和符号
- 3 方法
-
- 3.1 Node Content Transformation
- 3.2 Intra-metapath Aggregation
- 3.3 Inter-metapath Aggregation
- 3.4 Metapath Instance Encoders
- 3.5 訓練
- 4 實驗
- 5 總結
- 參考文獻
1 引言
本文解決的是異質圖的嵌入學習問題。
現有的基于元路徑的嵌入學習方法有以下局限性：
（1）忽略節點的内容特征（屬性資訊），不能很好地處理節點屬性特征豐富的異質圖。例如 metapath2vec, ESim, HIN2vec, HERec。
（2）舍棄了元路徑内部的節點資訊，隻考慮元路徑的起始節點和末尾節點，造成資訊損失。例如 HERec, HAN。
（3）隻依賴于單個元路徑，是以需要人工選擇元路徑，丢失了來自其他元路徑的部分資訊，導緻性能不佳。例如 metapath2vec。
為了解決上述問題，本文提出MAGNN（Metapath Aggregated Graph Neural Network ）。
MAGNN由三個部分組成：
（1）節點内容轉換(node content transformation )，将異質的節點屬性資訊映射到同一個隐層的向量空間；
（2）元路徑内部聚合(intra-metapath aggregation )，使用注意力機制将元路徑内部的語義資訊納入考慮；
（3）元路徑間的聚合(inter-metapath aggregation )，使用注意力機制從多個元路徑聚合資訊。
貢獻：
（1）提出新的元路徑聚合的GNN方法用于異質圖的嵌入學習；
（2）設計了幾個候選編碼器函數，用于從集合執行個體中提取資訊，其中一個基于複雜空間中的關系旋轉思想。
（3）在IMDB和DBLP資料集上進行了節點分類和節點聚類任務，在Last.fm資料集上進行了連結預測任務。實驗證明使用MAGNN學習得到的節點嵌入表示超越了state-of-the-art baselines的表現。
2 相關定義和符号
異質圖、元路徑、元路徑執行個體的定義不再贅述。
相關定義的圖示如下圖所示：
Metapath-based Neighbor：
給定異質圖中的一個元路徑 P P P，節點 v v v的metapath-based鄰居 N v P \mathcal{N}^P_v NvP為和 v v v相連的遵循元路徑 P P P的模式的節點集合。由兩個不同的元路徑執行個體與 v v v相連的同一個鄰居節點，被視為 N v P \mathcal{N}^P_v NvP中的兩個節點。另外，如果元路徑 P P P是對稱的， N v P \mathcal{N}^P_v NvP中也包含節點 v v v自身。
Metapath-based Graph：
給定異質圖 G \mathcal{G} G中的元路徑 P P P，基于元路徑的圖 G P \mathcal{G}^P GP由原始圖 G \mathcal{G} G中所有的基于元路徑 P P P的鄰居點對組成（去掉了元路徑執行個體的中間節點，隻保留了元路徑執行個體兩端的節點，并在兩點間建立起連邊）。如果元路徑 P P P是對稱的，則 G P \mathcal{G}^P GP是同質圖。如上圖(d)所示。
異質圖嵌入：
給定 G = ( V , E ) \mathcal{G}=(\mathcal{V}, \mathcal{E}) G=(V,E)和節點屬性矩陣 X A i ∈ R ∣ V A i ∣ × d A i \mathbf{X}_{A_i}\in \mathbb{R}^{|\mathcal{V}_{A_i}|\times d_{A_i}} XAi∈R∣VAi∣×dAi，其中 A i A_i Ai表示節點類型，異質圖嵌入學習的目的是從圖中捕獲到豐富的結構資訊和語義資訊，進而為每個節點學習到 d d d維的表示 h v ∈ R d \mathbf{h}_v\in \mathbb{R}^d hv∈Rd。
3 方法
MAGNN由節點内容轉換、元路徑内部聚合、元路徑間的聚合三部分組成，圖2展示了一個節點的嵌入生成過程。
3.1 Node Content Transformation
異質圖中的不同類型的節點有着不同的屬性，是以不同類型的節點的特征向量可能有着不同的次元，即使碰巧次元相同，特征向量也應該屬于不同的特征空間。
為了友善統一處理，需要将這些不同類型的節點的特征映射到同一個隐層的向量空間中。具體方法就是對每種類型的節點都使用一個特定的線性轉換，來将節點的特征向量轉換到同一個隐層的特征空間中。對于類别為 A ∈ A A\in \mathcal{A} A∈A節點 v ∈ V A v\in \mathcal{V}_A v∈VA，進行如下的轉換：
其中 x v ∈ R d A x_v\in \mathbb{R}^{d_A} xv∈RdA是原始的特征向量， h v ′ ∈ R d ′ \mathbf{h}^{'}_v\in \mathbb{R}^{d^{'}} hv′∈Rd′是映射後的節點 v v v的特征向量。 W A ∈ R d ′ × d A W_A\in \mathbb{R}^{d^{'}\times d_A} WA∈Rd′×dA是對于類型為 A A A的節點的參數化權重矩陣。
3.2 Intra-metapath Aggregation
給定元路徑 P P P，元路徑内部聚合層通過對 P P P的元路徑執行個體編碼，可以學習到 目标節點、基于元路徑的鄰居節點、節點之間的上下文 中嵌入的結構資訊和語義資訊。
定義連接配接目标節點 v v v和它的metapath-based鄰居節點 u ∈ N v P u\in \mathcal{N}^P_v u∈NvP為 P ( v , u ) P(v, u) P(v,u)。
定義 P ( v , u ) P(v, u) P(v,u)的内部節點為 { m P ( v , u ) } = P ( v , u ) ∖ { u , v } {\{m^{P(v, u)}\}}=P(v, u)\setminus{\{u, v\}} {mP(v,u)}=P(v,u)∖{u,v}。
（1）元路徑内部聚合采用了特殊的元路徑執行個體編碼器（metapath instance encoder）将元路徑執行個體中的所有節點的特征轉換成向量 h P ( v , u ) ∈ R d ′ \mathbf{h}_{P(v,u)}\in \mathbb{R}^{d^{'}} hP(v,u)∈Rd′：
節點 v , u v, u v,u之間可能存在多個元路徑執行個體，3.4節介紹了限定的metapath instance encoder的幾種選擇。
（2）接着使用圖注意力層（graph attention layer）權重聚合針對目标節點 v v v的且元路徑為 P P P的多個元路徑執行個體：
其中 a P ∈ R 2 d ′ a_P\in \mathbb{R}^{2d^{'}} aP∈R2d′是元路徑 P P P的參數化的注意力向量。 e v u P e^P_{vu} evuP表示元路徑執行個體 P ( v , u ) P(v, u) P(v,u)對節點 v v v的重要性，然後使用softmax進行了歸一化，然後使用歸一化後的注意力系數對和節點 v v v相關的元路徑執行個體的表示進行權重求和。最後再經過一個激活函數。
（3）上述的注意力機制可以擴充成多頭的（multi-heads），這有助于學習過程的穩定，并且可以減小圖的異質性帶來的高方差：
總結：
給出映射後的特征向量 h u ′ ∈ R d ′ , ∀ u ∈ V h^{'}_u\in \mathbb{R}^{d^{'}}, \forall u\in \mathcal{V} hu′∈Rd′,∀u∈V，以及一組元路徑 P A = { P 1 , P 2 , . . . , P M } \mathcal{P}_A={\{P_1, P_2, ..., P_M\}} PA={P1,P2,...,PM}。内部元路徑聚合為目标節點 v v v生成 M M M個針對特定元路徑的向量表示，記為 { h v P 1 , h v P 2 , . . . , h v P M } {\{h^{P_1}_v,h^{P_2}_v, ..., h^{P_M}_v \}} {hvP1,hvP2,...,hvPM}，每個$ h^{P_i}_v\in \mathbb{R}{d{’}} （ 假 定 （假定 （假定K=1 ） 都 表 示 了 節 點 ）都表示了節點 ）都表示了節點v$中隐含的一種語義資訊。
3.3 Inter-metapath Aggregation
使用元路徑間的聚合層結合所有元路徑的語義資訊。
從上一步可知，對于類型為 A A A的節點，生成了 ∣ V A ∣ |\mathcal{V}_A| ∣VA∣組隐層向量： { h v P 1 , h v P 2 , . . . , h v P M } {\{h^{P_1}_v, h^{P_2}_v, ..., h^{P_M}_v\}} {hvP1,hvP2,...,hvPM}， v ∈ V A v\in \mathcal{V}_A v∈VA， M M M是 A A A類型節點的元路徑數目。使用注意力機制為不同的元路徑配置設定不同的權重。
（1）首先，針對每條元路徑 P i ∈ P A P_i\in \mathcal{P}_A Pi∈PA，對所有類型為 A A A的節點在特定元路徑下的節點向量進行轉換，然後取平均：
其中 M A ∈ R d m × d ′ , b A ∈ R d m M_A\in \mathbb{R}^{d_m\times d^{'}}, b_A\in \mathbb{R}^{d_m} MA∈Rdm×d′,bA∈Rdm為可學習到的參數。
（2）然後使用注意力機制混合特定元路徑下的節點 v v v的特征向量：
其中 q A ∈ R d m q_A\in \mathbb{R}^{d_m} qA∈Rdm為參數化的針對 A A A類型節點的注意力向量。 β P i \beta_{P_i} βPi可解釋為元路徑 P i P_i Pi對于 A A A類型節點的重要性。使用這個注意力系數對節點 v v v的所有針對特定元路徑的向量進行權重求和。
（3）最後，MAGNN使用線性轉換和一層非線性函數，将節點嵌入映射到輸出所需次元的向量空間：
其中 W o ∈ R d o × d ′ W_o\in \mathbb{R}^{d_o\times d^{'}} Wo∈Rdo×d′是權重矩陣， σ ( ⋅ ) \sigma(\cdot) σ(⋅)是激活函數。
這個映射針對具體任務有所不同，可以看成是用于節點分類的線性分類器，也可看成是帶有節點間相似度度量的空間投影，可用于連結預測。
3.4 Metapath Instance Encoders
本節對應3.2（2）式中的元路徑執行個體編碼函數 f θ f_{\theta} fθ，作者給出了三個候選的編碼函數：
（1）Mean encoder：
（2）Linear encoder
是mean encoder的擴充，差別在于添加了一個線性轉換。
（3）Relational rotation encoder
基于在複雜空間的關系旋轉（relation rotation）的元路徑執行個體編碼器。這一操作是RotatE[1]提出的，原文做的是知識圖譜的嵌入學習。
mean encoder 和 linear encoder将元路徑執行個體看作了一個集合，忽視了元路徑序列結構中嵌入的資訊。關系旋轉的方法提供了模組化這一類知識的方法。
給定 P ( v , u ) = ( t 0 , t 1 , . . . , t n ) , t 0 = u , t n = v P(v, u)=(t_0, t_1, ..., t_n), t_0=u, t_n=v P(v,u)=(t0,t1,...,tn),t0=u,tn=v， R i R_i Ri為節點 t i − 1 , t i t_{i-1}, t_i ti−1,ti之間的關系。令 r i \mathbf{r}_i ri為 R i R_i Ri的向量表示。Relational rotation encoder可形式化為：
其中， h t i ′ , r i \mathbf{h}^{'}_{t_i}, \mathbf{r}_i hti′,ri是複雜的向量， ⊙ \odot ⊙表示元素間乘積。可将 d ′ d^{'} d′維的真實向量（ h P ( v , u ) \mathbf{h}_{P(v,u)} hP(v,u)）看成是一個複雜的向量，它的前 d ′ / 2 d^{'}/2 d′/2維是真實的部分，後 d ′ / 2 d^{'}/2 d′/2為虛構的部分。
MAGNN前向傳播算法如下：
3.5 訓練
經過上述的三個部分，得到了最終的節點表示，可用于下遊任務。
由于不同任務的特點不同，而且不一定能得到節點标簽。是以為MAGNN設計了兩種學習範式：半監督學習、無監督學習。
（1）半監督學習
最小化交叉熵損失：
其中， V L \mathcal{V}_L VL是有标簽的節點集合， C C C是類别數目， y v \mathbf{y}_v yv是節點 v v v的one-hot向量， h v \mathbf{h}_v hv是模型輸出的節點 v v v的向量表示。
（2）無監督學習
使用負采樣技術，最小化如下的損失函數：
其中， Ω \Omega Ω是正樣本集合， Ω − \Omega^{-} Ω−是負樣本集合。
4 實驗
實驗回答了以下幾個問題：
- MAGNN在節點分類任務上表現如何？
- MAGNN在節點聚類任務上表現如何？
- MAGNN在連結預測任務上表現如何？
- MAGNN的三個主要組成部分對其有什麼樣的影響？
- 如何了解不同圖嵌入方法的表示學習能力？
資料集：
IMDb、DBLP、Last.fm
**實驗任務：**節點分類、節點聚類、連結預測
對比方法：
- LINE：同質圖模型，使用了節點間的一階和二階相似度；
- node2vec：同質圖模型；
- ESim：異質圖模型，從采樣到的元路徑執行個體中學習節點嵌入；
- metapath2vec：異質圖模型，元路徑指導下得到的随機遊走路徑輸入到skip-gram模型中，得到節點嵌入；
- HERec：異質圖模型，使用元路徑将異質圖轉化為同質圖，再在其上面進行随機遊走；
- GCN：同質圖GNN；
- GAT：同質圖GNN；
- GATNE：異質圖GNN，使用基類嵌入和邊嵌入學習到節點表示，聚焦于連結預測任務；
- HAN：異質圖GNN，從基于元路徑的同質圖學習到特定元路徑下的節點嵌入，使用注意力機制進行聚合。
實驗結果：
（1）節點分類實驗結果(RQ1)
（2）節點聚類實驗結果(RQ2)
（3）連結預測實驗結果(RQ3)
（4）消融實驗(RQ4)
- M A G N N r o t MAGNN_{rot} MAGNNrot使用了relation rotation encoder，作為參考模型；
- M A G N N f e a t MAGNN_{feat} MAGNNfeat沒有使用節點内容特征；
- M A G N N n b MAGNN_{nb} MAGNNnb隻考慮了基于元路徑的鄰居；
- M A G N N s m MAGNN_{sm} MAGNNsm考慮了單個最好的元路徑；
- M A G N N a v g MAGNN_{avg} MAGNNavg使用了mean對元路徑執行個體進行編碼；
- M A G N N l i n e a r MAGNN_{linear} MAGNNlinear使用了linear對元路徑執行個體進行編碼。
M A G N N n b MAGNN_{nb} MAGNNnb和 M A G N N a v g , M A G N N l i n e a r , M A G N N r o t MAGNN_{avg}, MAGNN_{linear}, MAGNN_{rot} MAGNNavg,MAGNNlinear,MAGNNrot相比，可以看出聚合元路徑執行個體比metapath-based鄰居帶來的提升更多，驗證了元路徑内部聚合（intra-metapath aggregation）的有效性。
比較 M A G N N s m MAGNN_{sm} MAGNNsm和 M A G N N r o t MAGNN_{rot} MAGNNrot可以看出元路徑間聚合（intre-metapath aggregation）的有效性。
比較 M A G N N a v g , M A G N N l i n e a r , M A G N N r o t MAGNN_{avg}, MAGNN_{linear}, MAGNN_{rot} MAGNNavg,MAGNNlinear,MAGNNrot可以看出，使用relational rotation encoder可帶來提升。這三個變形都比目前最好的baseline HAN要表現好。
（5）可視化(RQ5)
5 總結
本文提出元路徑聚合的GNN模型——MAGNN，解決現有異質圖嵌入方法的三個缺點：
（1）忽略節點的内容特征；
（2）不考慮元路徑内部的節點；
（3）隻考慮單個元路徑。
MAGNN由三個部分組成，分别解決了上述的三個問題：
（1）節點内容轉換(node content transformation)
（2）元路徑内部聚合(intra-metapath aggregation)
（3）元路徑間的聚合(inter-metapath aggregation)
另外，本文還定義了元路徑執行個體編碼器，以抽取出元路徑執行個體中的結構資訊和語義資訊。提出3個候選的編碼函數，其中relation rotation encoder是受RotatE啟發的。
在真實資料集上進行了節點分類、節點聚類、連結預測三個任務，達到state-of-the-art。
未來方向：将MAGNN應用到rating prediction任務中（例如 推薦任務）。
本文正如标題所示，一目了然，方法圍繞元路徑的聚合展開。聚合具體分為元路徑内部的聚合、元路徑間的聚合。
聚合當然少不了注意力機制，這兩個聚合都使用到了注意力機制，還引入了多頭注意力（multi-head attention）。
MAGNN在模組化的過程中還使用了節點的屬性資訊，GATNE[2]模型也考慮到了這一點，實驗中也和此方法進行了對比。
比較創新的地方是考慮到了元路徑的内部結構，使用元路徑執行個體編碼器（metapath instance encoder）進行了元路徑的内部聚合。
一共對比了3種元路徑執行個體編碼器：mean, linear, relation rotation
實驗效果顯示relation rotation的效果最好，因為它考慮了元路徑中每兩個相鄰節點間的關系。但是實驗結果顯示relation rotation和mean差别不是很大。
需要注意的是，MAGNN還是需要人為定義元路徑。GTNs[3]是自動生成元路徑，并且在節點分類任務上也超越了HAN，本文的MAGNN沒有和GTNs進行對比。
另外同樣被WWW 2020接收的HGT[4]，也是不需要預先定義元路徑，且在節點分類、連結預測任務上也表現出了很好的效果，超越了HAN。不知道HGT和MAGNN相比的話會怎麼樣呢。
參考文獻
[1] Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019. RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space. In ICLR.
[2] Yukuo Cen, Xu Zou, Jianwei Zhang, Hongxia Yang, Jingren Zhou, and Jie Tang. 2019. Representation Learning for Attributed Multiplex Heterogeneous Network. In SIGKDD. 1358–1368.
[3] Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, Hyunwoo J.Kim. 2019. Graph Transformer Networks. In NeurIPS.
[4] Ziniu Hu, Yuxiao Dong, Kuansan Wang, Yizhou Sun. 2020. Heterogeneous Graph Transformer. 2020. In WWW.