【網絡表示學習】metapath2vec

題目：metapath2vec: Scalable Representation Learning for Heterogeneous Networks

作者：Yuxiao Dong, Nitesh V. Chawla and Ananthram Swami

來源：KDD 2017

源碼：https://ericdongyx.github.io/metapath2vec/m2v.html

目前的許多網絡表示學習方法主要是針對同質網絡的。本文提出一種的專門針對異質圖的網絡表示學習方法，能夠同時捕捉不同類型節點之間的語義和結構聯系。metapath2vec使用meta-path-based随機遊走建構節點的異質鄰居，然後使用一個異質skip-gram訓練模型，模組化結構上和語義上相近的節點。metapath2vec++進一步提出一種異質負采樣方法，準确高效地預測一個節點的異質鄰居。

核心問題

1. 在異質圖中如何有效地在不同類型的節點中保留上下文
2. 随機遊走是否可以用于異質圖
3. skip-gram是否可以用于異質圖

模型

定義一個異質網絡 G = ( V , E , T ) G=(V, E, T) G=(V,E,T)，其中每個節點和邊的類型由映射函數定義 ϕ ( v ) : V → T V \phi(v) : V \rightarrow T_{V} ϕ(v):V→TV​ ， φ ( e ) : E → T E \varphi(e) : E \rightarrow T_{E} φ(e):E→TE​ 。 T V T_{V} TV​和 T E T_{E} TE​分别代表相應類型的集合。 ∣ T V ∣ + ∣ T E ∣ > 2 \left|T_{V}\right|+\left|T_{E}\right|>2 ∣TV​∣+∣TE​∣>2 （不隻一種類型）。

Heterogeneous Skip-Gram

對于異質圖 G = ( V , E , T ) G=(V, E, T) G=(V,E,T)， ∣ T V ∣ > 1 |T_V|>1 ∣TV​∣>1 ，metapath2vec通過skip-gram模型學習網絡表示。給定一節點 v v v，最大化其異質上下文 N t ( v ) N_t(v) Nt​(v)， t ∈ T V t\in T_V t∈TV​（節點 v v v的 t t h t^{th} tth類型鄰居節點）的機率：

(2) arg ⁡ max ⁡ θ ∑ v ∈ V ∑ t ∈ T V ∑ c t ∈ N t ( v ) log ⁡ p ( c t ∣ v ; θ ) \arg \max _{\theta} \sum_{v \in V} \sum_{t \in T_{V}} \sum_{c_{t} \in N_{t}(v)} \log p\left(c_{t} | v ; \theta\right){\tag 2} argθmax​v∈V∑​t∈TV​∑​ct​∈Nt​(v)∑​logp(ct​∣v;θ)(2)

條件機率定義為softmax函數

p ( c t ∣ v ; θ ) = e X c l ⋅ X v ∑ u ∈ V e X u ⋅ X v p\left(c_{t} | v ; \theta\right)=\frac{e^{X_{c_{l}} \cdot X_{v}}}{\sum_{u \in V} e^{X_{u} \cdot X_{v}}} p(ct​∣v;θ)=∑u∈V​eXu​⋅Xv​eXcl​​⋅Xv​​

X v X_v Xv​是節點 v v v的embedding向量。

softmax分母的計算需要周遊所有節點，根據word2vec的負采樣優化，上式改寫為

log ⁡ ( X c i ⋅ X v ) + ∑ m = 1 M E u m ∼ P ( u ) log ⁡ σ ( − X u m ⋅ X v ) \log \left(X_{c_{i}} \cdot X_{v}\right)+\sum_{m=1}^{M} \mathbb{E}_{u^{m} \sim P(u)} \log \sigma\left(-X_{u^{m}} \cdot X_{v}\right) log(Xci​​⋅Xv​)+m=1∑M​Eum∼P(u)​logσ(−Xum​⋅Xv​)

模型在建構 P ( u ) P(u) P(u) 分布時，忽略節點的類别資訊，采樣負樣本。

Meta-Path-Based Random Walks

與deepwalk類似，metapath2vec也是通過随機遊走的方式保留網絡結構。但是在異質網絡中，決定遊走下一步的條件機率 p ( v i + 1 ∣ v i ) p\left(v^{i+1} | v^{i}\right) p(vi+1∣vi)不能像deepwalk那樣，直接在節點 v i v_i vi​ 的所有鄰居上做标準化（Normalized Probability）。如果這樣做忽略了節點的類型資訊。

PathSim論文[1] 指出

heterogeneous random walks are biased to highly visible types of nodes—those with a dominant number of paths—and concentrated nodes—those with a governing percentage of paths pointing to a small set of nodes .

給定一個異質網絡 G ( V , E , T ) G(V,E,T) G(V,E,T)和meta-path P = V 1 ⟶ R 1 V 2 ⟶ R 2 ⋯ V t ⟶ R t V t + 1 ⋯ ⟶ R l − 1 V l \mathcal{P} = V_{1} \stackrel{R_{1}}{\longrightarrow} V_{2} \stackrel{R_{2}}{\longrightarrow} \cdots V_{t} \stackrel{R_{t}}{\longrightarrow} V_{t+1} \cdots \stackrel{R_{l-1}}{\longrightarrow} V_{l} P=V1​⟶R1​​V2​⟶R2​​⋯Vt​⟶Rt​​Vt+1​⋯⟶Rl−1​​Vl​

其中節點類型 V 1 V_1 V1​ 和 V l V_l Vl​之間的關系表示為 R = R 1 ∘ R 2 ∘ ⋯ ∘ R l − 1 R=R_{1} \circ R_{2} \circ \cdots \circ R_{l-1} R=R1​∘R2​∘⋯∘Rl−1​。那麼第i步的轉移機率為

(3) p ( v i + 1 ∣ v t i , P ) = { 1 ∣ N t + 1 ( v t i ) ∣ ( v i + 1 , v t i ) ∈ E , ϕ ( v i + 1 ) = t + 1 0 ( v i + 1 , v t i ) ∈ E , ϕ ( v i + 1 ) ≠ t + 1 0 ( v i + 1 , v t i ) ∉ E p\left(v^{i+1} | v_{t}^{i}, \mathcal{P}\right)=\left\{\begin{array}{cc}{\frac{1}{\left|N_{t+1}\left(v_{t}^{i}\right)\right|}} & {\left(v^{i+1}, v_{t}^{i}\right) \in E, \phi\left(v^{i+1}\right)=t+1} \\ {0} & {\left(v^{i+1}, v_{t}^{i}\right) \in E, \phi\left(v^{i+1}\right) \neq t+1} \\ {0} & {\left(v^{i+1}, v_{t}^{i}\right) \notin E}\end{array}\right.{\tag{3}} p(vi+1∣vti​,P)=⎩⎪⎨⎪⎧​∣Nt+1​(vti​)∣1​00​(vi+1,vti​)∈E,ϕ(vi+1)=t+1(vi+1,vti​)∈E,ϕ(vi+1)̸​=t+1(vi+1,vti​)∈/​E​(3)

其中 v t i ∈ V t v_{t}^{i} \in V_{t} vti​∈Vt​， N t + 1 ( v t i ) N_{t+1}\left(v_{t}^{i}\right) Nt+1​(vti​)表示節點 v t i v_t^i vti​的鄰居中屬于 V t + 1 V_{t+1} Vt+1​類型的節點集合。也就是說，遊走是在預先設定的meta-path P的條件上。通常meta-path一般用在對稱的路徑上，第一個節點類型與最後一個節點類型相同。例如 OAPVPAO

p ( v i + 1 ∣ v t i ) = p ( v i + 1 ∣ v 1 i ) ,  if  t = l p\left(v^{i+1} | v_{t}^{i}\right)=p\left(v^{i+1} | v_{1}^{i}\right), \text { if } t=l p(vi+1∣vti​)=p(vi+1∣v1i​), if t=l

下面是metapah的舉例：

metapath2vec++

metapath2vec在計算softmax時，忽略了節點類型資訊。換句話說，在采集負樣本時，沒有考慮樣本是否與正樣本屬于同一個節點類型。因而本文提出，異質的負采樣 (Heterogeneous negative sampling)。也就說條件機率 p ( c t ∣ v ; θ ) p\left(c_{t} | v ; \theta\right) p(ct​∣v;θ)在特定的節點類型 t t t 上做标準化。

(5) p ( c t ∣ v ; θ ) = e X c t ⋅ X v ∑ u t ∈ V t e X u t ⋅ X v p\left(c_{t} | v ; \theta\right)=\frac{e^{X_{c_{t}} \cdot X_{v}}}{\sum_{u_{t} \in V_{t}} e^{X_{u_{t}} \cdot X_{v}}}{\tag 5} p(ct​∣v;θ)=∑ut​∈Vt​​eXut​​⋅Xv​eXct​​⋅Xv​​(5)

這就為skip-gram最後一層輸出層中的 每個類型都指定了一個多項分布。deepwalk中輸出多項分布的次元等于網絡中節點的數目，而metapath2vec++中類型t的節點輸出的多項分布次元等于類型t節點的數量。

二者的比較見下圖：

采樣分布也是針對特定類型節點進行采樣 P t ( ⋅ ) P_t(\cdot) Pt​(⋅)，目标函數為：

(6) O ( X ) = log ⁡ σ ( X c t ⋅ X v ) + ∑ m = 1 M E u t m ∼ P t ( u t ) [ log ⁡ σ ( − X u t m ⋅ X v ) ] O(\mathrm{X})=\log \sigma\left(X_{c_{t}} \cdot X_{v}\right)+\sum_{m=1}^{M} \mathrm{E}_{u_{t}^{m} \sim P_{t}\left(u_{t}\right)}\left[\log \sigma\left(-X_{u_{t}^{m}} \cdot X_{v}\right){\tag {6}}\right] O(X)=logσ(Xct​​⋅Xv​)+m=1∑M​Eutm​∼Pt​(ut​)​[logσ(−Xutm​​⋅Xv​)](6)

參數更新式子

∂ O ( X ) ∂ X u t m = ( σ ( X u t m ⋅ X v − I c t [ u t m ] ) ) X v ∂ O ( X ) ∂ X v = ∑ m = 0 M ( σ ( X u t m ⋅ X v − I c t [ u t m ] ) ) X u t m \begin{array}{l}{\frac{\partial O(\mathrm{X})}{\partial X_{u_{t}^{m}}}=\left(\sigma\left(X_{u_{t}^{m}} \cdot X_{v}-\mathbb{I}_{c_{t}}\left[u_{t}^{m}\right]\right)\right) X_{v}} \\ {\frac{\partial O(\mathrm{X})}{\partial X_{v}}=\sum_{m=0}^{M}\left(\sigma\left(X_{u_{t}^{m}} \cdot X_{v}-\mathbb{I}_{c_{t}}\left[u_{t}^{m}\right]\right)\right) X_{u_{t}^{m}}}\end{array} ∂Xutm​​∂O(X)​=(σ(Xutm​​⋅Xv​−Ict​​[utm​]))Xv​∂Xv​∂O(X)​=∑m=0M​(σ(Xutm​​⋅Xv​−Ict​​[utm​]))Xutm​​​

I c t [ u t m ] \mathbb{I}_{c_{t}}\left[u_{t}^{m}\right] Ict​​[utm​]是一個訓示函數，表明 u t m u_t^m utm​ 是否是上下文節點 c t c_t ct​ 。當 m = 0 , u t 0 = c t m=0, u_{t}^{0}=c_{t} m=0,ut0​=ct​。

metapath++算法整體流程

總結

metapath2vec定義了随機遊走時必須符合預設的meta-path（eq3），并且提出了相應的skip-gram訓練模型（eq5）以及負采樣方法（eq6）。該模型能夠有效地得到不同類型節點之間結構和語義上的聯系。

參考資料

1. Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S. Yu, and Tianyi Wu, “PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks”, PVLDB 4(11): 992-1003, 2011. (Also, Proc. of 2011 Int. Conf. on Very Large Data Bases