【論文翻譯 arXiv 2020】異質網表示學習綜述-韓家炜組

論文題目：Heterogeneous Network Representation Learning: Survey, Benchmark, Evaluation, and Beyond

論文來源：arXiv 2020.04.01

論文連結：https://arxiv.org/abs/2004.00216

代碼連結：https://github.com/yangji9181/HNE

關鍵詞：異質網嵌入，綜述，benchmark

異質網的嵌入學習方法(HNE)已經被廣泛應用，但還沒有一篇詳細的綜述。

本文的貢獻如下：

（1）本文提出了一個統一的範式，對各種現有的HNE算法的優點進行系統的分類和分析。

（2）本文還從不同來源建立了4個具有不同屬性的基線資料集，包括規模、結構、屬性/标簽可用性等，以更全面地評估HNE算法。

（3）重構并修正了10個HNE流行算法接口的實作。并在多個任務和不同的實驗設定下對其進行了全方位的比較。

文章目錄

• 1 Generic Paradigm
• • 1.1 問題定義
  • 1.2 提出的範式
• 2 算法分類
• • 2.1 Proximity-Preserving 方法
  • • 2.1.1 基于随機遊走的方法
    • 2.1.2 基于一階/二階相似度的方法
  • 2.2 Message-Passing 方法
  • 2.3 Relation-Learning 方法
• 3 Benchmark
• • 3.1 資料集的準備
  • 3.2 結構分析
  • 3.3 設定，任務和度量
• 4 實驗評估
• • 4.1 Algorithms and Modifications
  • 4.2 Performance Benchmarks
• 5 Future

1 Generic Paradigm

1.1 問題定義

（1）網絡嵌入(Network embedding)

給定圖 G = { V , E } G={\{V, E}\} G={V,E}， V V V是節點集合， E E E是邊集合。網絡嵌入就是一個将節點映射成低維向量表示的函數： Φ : V → R ∣ V ∣ × d \Phi : V\rightarrow \mathbb{R}^{|V|\times d} Φ:V→R∣V∣×d， d d d遠小于 ∣ V ∣ |V| ∣V∣。映射函數 Φ \Phi Φ定義了每個節點的隐層表示，表示中含有從邊集 E E E中捕獲到的圖的結構資訊。

在多數情況下，網絡相似性(network proximity)是需要捕獲的主要拓撲資訊。例如，DeepWalk就捕獲到了基于随機遊走的節點相似性。随後有各種工作對DeepWalk進行了改進和擴充，這不屬于本文的範圍，DeepWalk是應用于同質圖的，本文關注的是異質圖的表示學習。

（2）異質網(Heterogeneous network)

異質網 H = { V , E , ϕ , ψ } H={\{V, E, \phi, \psi}\} H={V,E,ϕ,ψ}有多種類型的節點和邊。 H H H中，每個節點 v i v_i vi​都對應一種節點類型 ϕ ( v i ) \phi(v_i) ϕ(vi​)，每個邊 e i j e_{ij} eij​都對應一種邊類型 ψ ( e i j ) \psi(e_{ij}) ψ(eij​)。邊的類型自動定義了其兩端節點的類型。

（3）元路徑(Meta-path)

元路徑是定義在network schema上的由不同類型的節點和邊組成的序列。

每個元路徑都從特定的語義角度捕獲到了其兩端節點的相似性。使用不同的元路徑就可以使得模型計算到多模多類型的節點相似性和關系，有助于學習到更豐富的節點表示。

（4）異質網嵌入(Heterogeneous network embedding)

給定一個異質圖 H H H，異質網嵌入就是一組映射函數： { Φ k : V k → R ∣ V k ∣ × d } k = 1 K {\{\Phi_k: V_k\rightarrow \mathbb{R}^{|V_k|\times d}\}}^K_{k=1} {Φk​:Vk​→R∣Vk​∣×d}k=1K​。其中 K K K是節點類型的數量， ∀ v i ∈ V k , ϕ ( v i ) = k \forall v_i \in V_k, \phi(v_i)=k ∀vi​∈Vk​,ϕ(vi​)=k。映射函數 Φ k \Phi_k Φk​定義了類型為 k k k的所有節點的隐層表示，捕獲到了 E E E中關于異質邊的網絡拓撲資訊。

1.2 提出的範式

HNE一個最重要的原則就是趨同性。在網絡嵌入中，趨同性可以解釋成“在網絡中相近的節點應該有相似的嵌入表示”。

事實上，我們進一步發現了同質性原理和在網絡上廣泛使用的平滑實施技術之間的内在聯系，提出了一個通用的數學範式，涵蓋了大多數現有的和可能的許多未來的HNE算法。

作者引入如下的目标函數：

其中， e u = Φ ( u ) , e v = Φ ( v ) e_u=\Phi(u), e_v=\Phi(v) eu​=Φ(u),ev​=Φ(v)是需要學習得到的節點嵌入向量。 w u v w_{uv} wuv​是權重， d ( ⋅ , ⋅ ) d(\cdot, \cdot) d(⋅,⋅)是計算嵌入向量間距離的函數， J R \mathcal{J}_R JR​是附加的目标函數（例如正則化），在不同的HNE算法中，對這三項的定義不同。

2 算法分類

我們使用一個統一的分類方法，将現有的HNE算法基于它們的目标分為3類，并且解釋它們都符合式（1）的範式。

2.1 Proximity-Preserving 方法

網絡嵌入的一個基本目标就是捕獲到網絡的拓撲資訊，保留不同類型節點間的相似度可以實作這一目标。HNE中相似度保留(proximity preserving)方法可分成兩類：（1）受DeepWalk啟發的基于随機遊走的方法；（2）受LINE啟發的基于一階/二階相似度的方法。

2.1.1 基于随機遊走的方法

（1）metapath2vec

metapath2vec使用了由元路徑指導的随機遊走得到的節點組成的路徑，考慮到異質的語義資訊，來模組化節點的上下文。給定元路徑 M \mathcal{M} M，在第 i i i步的轉移機率定義為：

其中， N l ( v ) = { u ∣ ψ ( u , v ) = l } \mathcal{N}_l(v)={\{u|\psi(u, v)=l}\} Nl​(v)={u∣ψ(u,v)=l}為通過類型為 l l l的邊和節點 v v v相連接配接的鄰居節點。假定 P = { P 1 , . . . , P M } \mathcal{P}={\{\mathcal{P}_1,..., \mathcal{P}_M}\} P={P1​,...,PM​}是随機遊走生成的一組序列。則metapath2vec的目标函數為：

其中， C ( v ) \mathcal{C}(v) C(v)是 v v v在 P \mathcal{P} P中的上下文。例如，若 P 1 = v 1 v 2 v 3 v 4 v 5 . . . \mathcal{P}_1=v_1v_2v_3v_4v_5... P1​=v1​v2​v3​v4​v5​...，上下文視窗大小為2，則 { v 1 , v 2 , v 4 , v 5 } ⊆ C ( v 3 ) {\{v_1, v_2, v_4, v_5}\}\subseteq \mathcal{C}(v_3) {v1​,v2​,v4​,v5​}⊆C(v3​)。令 w u v w_{uv} wuv​記為在 P \mathcal{P} P中 u ∈ C ( v ) u\in \mathcal{C}(v) u∈C(v)出現的次數，将式（3）重寫為如下的形式：

分母需要對所有節點進行計算求和，計算量很大。在實際的計算中，通常使用負采樣進行近似。

（2）HIN2Vec

HIN2Vec是考慮節點 u , v u,v u,v間存在元路徑 M \mathcal{M} M的可能性：

其中， 1 \mathbf{1} 1是全1的向量， ⊙ \odot ⊙是Hadamard乘積， f 01 f_{01} f01​是正則化函數。 e u = W X T u , e v = W X T v , e M = f 01 ( W R T m ) e_u=W^T_Xu, e_v=W^T_Xv, e_{\mathcal{M}}=f_{01}(W^T_Rm) eu​=WXT​u,ev​=WXT​v,eM​=f01​(WRT​m)可視為 u , v , M u, v, \mathcal{M} u,v,M的嵌入表示。令 A M = d i a g ( e M 1 , . . . , e M d ) \mathbf{A}_{\mathcal{M}}=diag(e_{\mathcal{M}1},..., e_{\mathcal{M}d}) AM​=diag(eM1​,...,eMd​)，有：

其中， σ \sigma σ是sigmoid函數，于是有：

HIN2Vec忽略節點/邊的類型，使用同質的随機遊走生成了多個正的三元組樣本 ( u , v , M ) (u, v, \mathcal{M}) (u,v,M)。對于每個正樣本，将 u u u随機替換成 u ′ u^{'} u′，生成多個負樣本。目标函數為：

這其實就是對如下目标函數的負采樣近似值：

其中 w u v M w^{\mathcal{M}}_{uv} wuvM​是在元路徑為 M \mathcal{M} M的前提下，節點 u , v u, v u,v間的路徑執行個體數。

（3）SHINE

SHINE在metapath2vec的基礎上記性了改進，考慮到了附加的節點資訊。一些類型的節點可能有附加的文本資訊(定義為 x v x_v xv​)。它提出了基于GRU的深層編碼函數 f E N C f_{ENC} fENC​。若 v v v有文本資訊，則 e v = f E N C ( x v ) e_v=f_{ENC}(x_v) ev​=fENC​(xv​)；否則， e v e_v ev​就表示可訓練的節點嵌入。

SHINE的目标函數和metapath2vec一樣，它還可以通過利用特定領域的深層編碼器，直接擴充到其他類型的節點資訊，例如類别屬性值、圖像等。

其他的基于随機遊走的方法總結到了表1中。MRWNN将内容先驗整合到了DeepWalk嵌入中；HHNE将metapath2vec擴充到了雙曲空間；GHE提出了一種半監督的元路徑權重技術；MNE在多視圖網絡中對每個視圖分别進行随機遊走；JUST提出Jump/Stay随機遊走，不依賴于預先定義的元路徑。

2.1.2 基于一階/二階相似度的方法

（1）PTE

PTE提出将異質網分解為多個二部圖，每個都描述了一種類型的邊。它的目标函數是對所有二部圖的對數似然的和：

其中， T E \mathcal{T}_E TE​是邊類型的集合； w u v l w^l_{uv} wuvl​是節點對 ( u , v ) (u, v) (u,v)間類型為 l l l的邊所對應的權重(若 u , v u, v u,v間沒有類型為 l l l的連邊，則該值為0)； w u v = ∑ l w u v l w_{uv}=\sum_l w^l_{uv} wuv​=∑l​wuvl​是節點 u , v u, v u,v間邊的權重之和。

（2）AspEm

AspEm假定每個異質圖都有多個角度(aspects)，将每個角度定義成network schema的一個子圖。AspEm還提出了一個不相容的度量，以為嵌入學習選取合适的角度。給定一個角度 a a a，目标函數為：

其中， T E a \mathcal{T}_E^a TEa​是角度 a a a下的邊集合； Z l = ∑ u , v w u v l Z_l=\sum_{u, v}w^l_{uv} Zl​=∑u,v​wuvl​是為了規範化的參數； e u , a e_{u, a} eu,a​是節點 u u u在特定角度下的嵌入表示。

（3）HEER

HEER是PTE的擴充，它考慮到了typed closeness。類型為 l l l的邊有嵌入表示 μ l \mu_l μl​。目标函數為：

其中， g u v g_{uv} guv​是邊 ( u , v ) (u, v) (u,v)的嵌入表示； P l ( u , v ) = { ( u ′ , v ) ∣ ψ ( u ′ , v ) = l } ∪ { ( u , v ′ ) ∣ ψ ( u , v ′ ) = l } P_l(u, v)={\{(u^{'}, v)| \psi(u^{'}, v)=l}\} \cup { \{(u, v^{'})| \psi(u, v^{'})=l}\} Pl​(u,v)={(u′,v)∣ψ(u′,v)=l}∪{(u,v′)∣ψ(u,v′)=l}。HEER原文中的 g u v g_{uv} guv​基于Hadamard乘積針對有向邊和無向邊有不同的定義。本文為了總結的簡化，我們假定 g u v = e u ⋅ e v g_{uv}=e_u\cdot e_v guv​=eu​⋅ev​。令 A l = d i a g ( μ l 1 , . . . , μ l d ) A_l=diag(\mu_{l1},..., \mu_{ld}) Al​=diag(μl1​,...,μld​)，則有 μ l T g u v = e u T A l e v \mu^T_lg_{uv}=e^T_uA_le_v μlT​guv​=euT​Al​ev​和目标函數：

其他的基于一階/二階相似度的方法總結到了表1中。HNE模型中引入了一個節點的類型感覺的内容編碼器(node type-aware content encoder)；CMF在分解得到的二部圖中進行了聯合的矩陣分解；HEBE考慮到了每個元路徑，保留了相似性資訊；Phine面向半監督的訓練，結合了額外的正則化；MVE提出基于attention的架構，考慮到了同一節點的多個視角。

還有一些研究采取了其他形式的目标函數來描述一階/二階相似性。例如，SHINE受SDNE的啟發，使用自動編碼器的重構損失作為目标函數；DRL提出在每一步學習一種類型的邊，并使用深度強化學習的方法選擇下一步的邊類型；HINSE基于不同元路徑的鄰接矩陣，采用譜嵌入的方法；HeGAN使用關系類型感覺的判别器，提出對抗學習的架構。

基于上述讨論，大多數proximity-preserving方法可以定義為：

其中， w u v w_{uv} wuv​是針對特定元路徑 M \mathcal{M} M或者是針對類型為 l l l的邊的，可表示為 w u v M w^{\mathcal{M}}_{uv} wuvM​或 w u v l w^l_{uv} wuvl​； J R 0 \mathcal{J}_{R0} JR0​是針對特定算法的正則化函數(表1中有總結)； s ( u , v ) s(u, v) s(u,v)是節點 u , v u, v u,v間的相似度度量函數。

在大多數情況下，可以将 s ( u , v ) s(u, v) s(u,v)寫成 f ( e u ) T f ( e v ) f(e_u)^Tf(e_v) f(eu​)Tf(ev​)。例如metapath2vec、PTE中 f ( e u ) = e u f(e_u)=e_u f(eu​)=eu​；HIN2Vec中 f ( e u ) = A M e u f(e_u)=\sqrt{A_{\mathcal{M}}e_u} f(eu​)=AM​eu​

​；HEER中 f ( e u ) = A l e u f(e_u)=\sqrt{A_{\mathcal{l}}e_u} f(eu​)=Al​eu​

​。在這些方法中，目标函數可形式化為：

第二步得出是因為： ∣ ∣ x − y ∣ ∣ 2 = ( x − y ) T ( x − y ) = ∣ ∣ x ∣ ∣ 2 + ∣ ∣ y ∣ ∣ 2 − 2 x T y ||x-y||^2=(x-y)^T(x-y)=||x||^2+||y||^2-2x^Ty ∣∣x−y∣∣2=(x−y)T(x−y)=∣∣x∣∣2+∣∣y∣∣2−2xTy。是以，我們的目标等價于：

其中， J R 1 \mathcal{J}_{R1} JR1​和 J R 2 \mathcal{J}_{R2} JR2​是兩個正則化函數。沒有 J R 1 \mathcal{J}_{R1} JR1​時，讓 ∣ ∣ f ( e v ) ∣ ∣ → 0 ||f(e_v)||\rightarrow 0 ∣∣f(ev​)∣∣→0可以最小化 d ( e u , e v ) d(e_u, e_v) d(eu​,ev​)；沒有 J R 2 \mathcal{J}_{R2} JR2​時，讓 e v ≡ c , ( ∀ v ∈ V ) e_v\equiv c, (\forall v\in V) ev​≡c,(∀v∈V)可以最小化 d ( e u , e v ) d(e_u, e_v) d(eu​,ev​)。

式（1）中的 J R \mathcal{J}_R JR​是 − J R 0 , − J R 1 , J R 2 -\mathcal{J}_{R_0}, -\mathcal{J}_{R_1}, \mathcal{J}_{R_2} −JR0​​,−JR1​​,JR2​​的和。表1中總結了 w u v , d ( e u , e v ) , J R 0 w_{uv}, d(e_u, e_v), \mathcal{J}_{R0} wuv​,d(eu​,ev​),JR0​的不同選擇。

2.2 Message-Passing 方法

網絡中的每個節點都可能有屬性資訊，表示為 x u x_u xu​。消息傳遞(Message-passing)的方法目的就是通過聚合來自節點 u u u的鄰居的資訊以及節點 u u u自身的屬性資訊 x u x_u xu​，學習得到節點嵌入表示 e u e_u eu​。近些年的研究中，GNN被廣泛用于消息的聚合和傳遞過程。

（1）R-GCN

R-GCN有 K K K層卷積，初始的節點表示 h u ( 0 ) h^{(0)}_u hu(0)​是節點的特征 x u x_u xu​，在第 k k k層卷積，每個節點向量表示是通過聚合鄰居節點的資訊得到的：

和傳統的GCNs不同，R-GCN考慮到了邊的異質性，為每種類型的邊都學習到了一個矩陣 W W W。在消息傳遞時，同一類型的邊的鄰居先被聚合并歸一化。第 K K K層的輸出 e v = h v ( K ) e_v=h^{(K)}_v ev​=hv(K)​就是節點嵌入。

在無監督的實驗設定中，消息傳遞方法使用連結預測作為下遊任務，最大化異質網中出現邊的似然，來對GNNs進行訓練。R-GCN使用負采樣和交叉熵損失，對如下的目标函數進行近似：

其中 w u v l = 1 ( u , v ) ∈ E 1 w^l_{uv}=\mathbf{1}_{(u,v)\in E_1} wuvl​=1(u,v)∈E1​​。

（2）HAN

HAN沒有直接使用一階鄰居，而是使用元路徑來模組化更高階的相似性。給定一個元路徑 M \mathcal{M} M，節點 u u u的表示是從基于該元路徑的鄰居聚合的，鄰居節點為： N M ( u ) = { u } ∪ { v ∣ v 通 過 元 路 徑 M 和 u 相 連 } \mathcal{N}_{\mathcal{M}}(u)={\{u}\}\cup {\{v| v通過元路徑\mathcal{M}和u相連}\} NM​(u)={u}∪{v∣v通過元路徑M和u相連}。HAN提出注意力機制為不同的鄰居學習到不同的權重：

其中， a M a_{\mathcal{M}} aM​是元路徑 M \mathcal{M} M下節點級别的注意力向量； x u ′ = M ϕ ( u ) x u x^{'}_u=M_{\phi(u)}x_u xu′​=Mϕ(u)​xu​是節點 u u u映射後的特征向量； ∣ ∣ || ∣∣表示連接配接操作。

給定特定元路徑下的嵌入 h u M h^{\mathcal{M}}_u huM​，HAN使用語義級别的注意力為不同的元路徑配置設定不同的權重：

其中 q q q是語義級别的注意力向量。

最近，有學者提出HGDI來提升基于HAN的無監督訓練效果；HGT的提出實作了對動态圖進行時間編碼以及在大規模資料上進行mini-batch的采樣。

因為HAN是為半監督的節點分類問題設計的，當需要在無監督的情況下學習節點嵌入時(就像許多的proximity-preserving方法)，我們通常采用連結預測任務的損失函數，例如R-GCN和GraphSAGE。

（3）HetGNN

HetGNN假定每個節點都和不同的特征相關聯，例如類别、文本、圖像。它首先将每個節點的内容資訊編碼成向量 h u s h^s_u hus​，然後使用節點的類型感覺(node type-aware)的聚合函數從鄰居節點收集資訊：

其中 N R W R ( v ) \mathcal{N}_{RWR}(v) NRWR​(v)是使用帶重新開機的随機遊走得到的節點 v v v的鄰居。HetGNN對不同類型的鄰居節點使用注意力機制，以得到最終的嵌入，和HAN的思想一緻：

HetGNN的損失函數和PTE的一樣。

還有一些其他的message-passing方法。例如HEP從鄰居 N o ( u ) \mathcal{N}_o(u) No​(u)(例如 節點類型感覺的鄰居)進行聚合得到 u u u的表示，應用于電商平台的使用者對齊；GATNE從鄰居 N l ( u ) \mathcal{N}_l(u) Nl​(u)(例如 邊類型感覺的鄰居)進行聚合得到 u u u的表示，應用于transductive和inductive的網絡嵌入學習。

上述的message-passing方法也可以寫成式（4）的形式，其中 s ( u , v ) s(u, v) s(u,v)是關于 e u , e v e_u, e_v eu​,ev​的函數。唯一的不同之處在于，這裡的 e u e_u eu​是使用GNNs從 x v x_v xv​聚合得到的。若我們仍将 J R \mathcal{J}_R JR​寫成式（1）中 − J R 0 , − J R 1 , J R 2 -\mathcal{J}_{R_0}, -\mathcal{J}_{R_1}, \mathcal{J}_{R_2} −JR0​​,−JR1​​,JR2​​的和，則可以得到如式（5）所示的相同的 J R 1 , J R 2 \mathcal{J}_{R_1}, \mathcal{J}_{R_2} JR1​​,JR2​​。

在這組算法中，隻有HEP使用了額外的重構損失 J R 0 = ∑ v ∣ ∣ e v − h v ∣ ∣ 2 \mathcal{J}_{R_0}=\sum_v ||e_v-h_v||^2 JR0​​=∑v​∣∣ev​−hv​∣∣2，其他所有的算法中都有 J R 0 = 0 \mathcal{J}_{R_0}=0 JR0​​=0。我們将 w u v , d ( e u , e v ) w_{uv}, d(e_u, e_v) wuv​,d(eu​,ev​)和聚合函數的不同選擇，總結在了表2中。

2.3 Relation-Learning 方法

異質網中的每個邊都可以看成一個三元組 ( u , l , v ) (u, l, v) (u,l,v)，其中 u , v u, v u,v是節點， l ∈ T E l\in \mathcal{T}_E l∈TE​是邊的類型(例如 KG中的實體和關系)。

relation-learning方法的目标是學習到一個打分函數 s l ( u , v ) s_l(u, v) sl​(u,v)，對任意一個三元組進行評估，衡量這個三元組可接受性。這一思想廣泛用于KB的嵌入學習。已經有了KB嵌入學習算法的綜述，我們在這裡隻考慮最流行的方法并且突出它們和HNE的關聯。

（1）TransE

TransE假定若存在三元組 ( u , l , v ) (u, l , v) (u,l,v)，則有這樣的嵌入變換： e u + e l = e v e_u + e_l = e_v eu​+el​=ev​。是以TransE的打分函數就定義為： s l ( u , v ) = − ∣ ∣ e u + e l − e v ∣ ∣ p , p = 1 或 2 s_l(u, v)=-||e_u+e_l-e_v||_p, p=1或2 sl​(u,v)=−∣∣eu​+el​−ev​∣∣p​,p=1或2。目标函數就是最小化一個margin-based ranking loss：

其中， T T T是正的三元組樣本集合， T ( u , l , v ) ′ T^{'}_{(u, l, v)} T(u,l,v)′​是将 u u u或 v v v随機替換得到的負的三元組樣本集合：

TransE是使用"a translational distance"來定義打分函數的最具代表性的模型。它的擴充有TransH, TransR, RHINE等。

（2）DistMult

和translational distance的模型不同，DistMult使用了基于相似性的打分函數。每個關系都用一個對角矩陣 A l = d i a g ( e l 1 , . . . , e l d ) A_l=diag(e_{l1},...,e_{ld}) Al​=diag(el1​,...,eld​)表示， s l ( u , v ) s_l(u,v) sl​(u,v)使用雙線性函數定義：

注意，對于任意的 u , v u, v u,v，都有 s l ( u , v ) = s l ( v , u ) s_l(u,v)=s_l(v,u) sl​(u,v)=sl​(v,u)。是以DistMult主要用于對稱的關系資料。

除了DistMult，RESCAL也是用雙線性的打分函數，但是不将 A l A_l Al​限制為對角陣。

（3）ConvE

ConvE不使用簡單的距離或相似性函數，而是提出了深層的神經模型為三元組打分。分值由在2D的嵌入上的卷積決定：

其中， E u , E r E_u, E_r Eu​,Er​分别表示節點嵌入和關系嵌入的2D矩陣，" ∗ * ∗"是卷積操作。

其他使用深度神經網絡作為打分函數的模型包括：NTN，CACL，SACN，NKGE等。

所有上述提到的基于relation-learning的嵌入算法都采用了式（6）的margin-based ranking loss，再加上一些正則項，作為損失函數：

有學者提出基于margin的損失和如下的負采樣損失有着相似的形式：

使用負采樣損失重寫式（7），就可以近似成最大化如下的式子：

• 對于translational distance模型， s l ( u , v ) s_l(u, v) sl​(u,v)是通過距離描述的，等價于：

此例中，可将 J R \mathcal{J}_R JR​寫成 − J R 0 + J R 1 -\mathcal{J}_{R_0}+\mathcal{J}_{R_1} −JR0​​+JR1​​。

• 對于neural triplet scores， s l ( u , v ) s_l(u, v) sl​(u,v)的形式比内積或者距離更加複雜。在這些情況下，因為距離和相似度可以看成相反的度量，我們将 d ( e u , e v ) d(e_u, e_v) d(eu​,ev​)定義成 C − s l ( u , v ) C-s_l(u, v) C−sl​(u,v)，其中 C C C是 s l ( ⋅ , ⋅ ) s_{l}(\cdot, \cdot) sl​(⋅,⋅)的上界，是一個常數。則損失函數和式（8）就相似了，仍有 J R = − J R 0 + J R 1 \mathcal{J}_R=-\mathcal{J}_{R_0}+\mathcal{J}_{R_1} JR​=−JR0​​+JR1​​。

我們将 w u v l , d ( e u , e v ) , J R 0 w^l_{uv}, d(e_u, e_v), \mathcal{J}_{R_0} wuvl​,d(eu​,ev​),JR0​​的不同選擇總結到了表3中。注意，對于relation-learning方法， d ( ⋅ , ⋅ ) d(\cdot, \cdot) d(⋅,⋅)也許不是一個距離的度量。例如在許多translational distance模型中， d ( e u , e v ) ≠ d ( e v , e u ) d(e_u, e_v)\neq d(e_v, e_u) d(eu​,ev​)​=d(ev​,eu​)。這是因為 ( u , l , v ) (u, l, v) (u,l,v)和 ( v , l , u ) (v, l ,u) (v,l,u)通常表達了不同的語義。

3 Benchmark

3.1 資料集的準備

我們整理并公開了4個來源于不同領域的真實的異質網資料集，旨在為現有的和未來的HNE算法建立一個benchmark。

（1）DBLP

我們從DBLP建構了一個含有authors, paper, venues, phrases的網絡。Phrases是使用流行的AutoPhrase算法，從論文文本抽取的，并且專家對其進行了進一步的篩選過濾。

我們對所有的論文文本進行了word2vec的計算，生成了300維的paper和phrase的特征。author和venue的特征是通過聚合它們對應的的paper特征得到的。我們還采用爬蟲技術，将一小部分author手動标記成來自4個研究領域的12個研究小組。

（2）Yelp

我們從Yelp建構了由businesses，users，locations，reviews構成的網絡。節點沒有特征，但是大部分的businesses都有16類中的一類或多類的标簽。

（3）Freebase

從Freebase建構了由books，films，music，sports，people，locations，organizations，businesses組成的網絡。節點沒有特征，但大部分的books都屬于8類中的一類。

（4）PubMed

從PunMed建構了由genes，diseases，chemicals，species組成的網絡。所有的節點都是通過AutoPhrase抽取得到的，由AutoNER打标簽，然後由專家進行進一步的過濾。

我們在PubMed所有的papers上進行了word2vec的計算，為所有類型的節點生成了200維的單詞嵌入。還将一小部分的diseases分成了8類，每個disease隻有一個标簽。

3.2 結構分析

這4個資料集統計為表4和圖3所示。

作者還對這些異質網的屬性進行了分析，有度分布(圖4)、聚合系數(圖5)、頻繁元路徑的數量(圖6)。根據度分布進行節點采樣，度分布可以顯著影響HNE算法的性能。聚類系數對使用潛在的社群結構的HNE算法帶來影響。由于許多HNE算法依賴于元路徑，元路徑的skewer distribution可能偏向于使用較少元路徑的算法。

對于這4個資料集，我們關注到的屬性是不一樣的。例如，Yelp中有更多緊密的連結和更多的标簽；Freebase和PubMed中的節點有鮮明的長尾度分布；DBLP和Yelp中特定類型的節點連接配接地較好(例如 DBLP中的phrase，Yelp中的businesses)，形成了更多的星型結構(star-shaped)的子圖；type-wise的聚類系數和元路徑分布在DBLP中偏斜最嚴重，在PubMed中最均衡。

這4個資料集為各種HNE算法的魯棒性和通用性提供了一個全面的基準。(4.2節中有介紹)

3.3 設定，任務和度量

對所有資料集設定成無監督無屬性的HNE，主要對10種算法進行比較，目的是保留異質網中不同類型的邊。

（1）對于為屬性網和半監督的HNE特别設計的message-passing算法，在相應的設定下對它們進行了額外的實驗。在DBLP和PubMed資料集上進行了帶屬性的HNE的評估，在Yelp和Freebase上進行了半監督HNE的評估。在節點分類和連結預測兩個任務上測試學習得到的網絡嵌入表示。将所有算法得到的嵌入次元設為50，在所有資料集上使用标準的5折交叉驗證對超參數進行微調。

（2）對于标準的無屬性無監督的HNE算法，随機隐藏20%的邊，使用剩餘80%的邊訓練所有的HNE算法。

• 對于節點分類任務，基于使用80%有标注的節點訓練學習得到的嵌入，訓練一個分離的線性SVM(LinearSVC)，以預測剩餘的20%的節點标簽。重複5次這一過程對所有的得分取平均，得到macro-F1和micro-F1。
• 對于連結預測任務，使用Hadamard函數重構節點對的特征向量，在80%的連結資料集上訓練一個二分類的LinearSVC，在剩餘的20%的資料集上進行評估。同樣的，重複5次這一過程，得到AUC(ROC曲線下的面積)和MRR(mean reciprocal rank)兩個度量。AUC是分類問題的标準度量，我們将連結預測視為了二分類問題。MRR是排序問題的标準度量，我們将連結預測視為了連結檢索問題。對所有的節點對進行計算，這個計算量太大了，是以通常使用兩跳(two-hop)的鄰居作為所有節點的候選。

（3）對于帶屬性的HNE，節點特征用于HNE算法的訓練過程。對于半監督的HNE，隻使用特定數量的節點标簽(預設是80%)。

4 實驗評估

4.1 Algorithms and Modifications

我們修改了10個流行的HNE算法以在我們準備的資料集上進行有效的實驗評估。我們選擇的算法和進行的修改如下：

（1）metapath2vec

原始的實作版本包含大量的hard-coded的特定資料的設定，例如節點類型和元路徑。并且優化是不穩定的和受限的，因為它僅僅檢測了基于元路徑的一種類型的上下文。作者重新實作了該方法。

首先，進行随機遊走，基于采樣的執行個體數目學習到不同元路徑的權重。然後使用統一的損失函數訓練模型，損失函數是對所有元路徑的損失進行權重求和得到的。

随機遊走和基于元路徑的嵌入優化都是通過多線程并行實作的。

（2）PTE

原先的方法是将有标簽的文本作為輸入，隻能用于有三種特定類别節點(word, document, label)和三種特定類别邊(word-word, document-word, label-word)的文本網絡。作者将原始版本進行了修正，使得模型能直接用于有任意類型的節點和邊的異質網。

（3）HIN2Vec

作者去除掉了不必要的資料預處理代碼，對原始的版本進行了修改，使得程式先進行随機遊走，然後對模型進行訓練，最終隻輸出節點的嵌入表示。

（4）AspEm

作者去除了原始版本中hard-coded特定資料的設定，編寫了script将自動選擇aspects的不同組成部分相連接配接，并實作了不相容性的最小化。還同時連接配接了基于不同aspects的嵌入的學習、配對、拼接。

（5）HEER

作者去除了原始版本中hard-coded特定資料的設定，跳過了knockout步驟并理順了圖建立的過程，實作了資料預處理的簡化。

（6）R-GCN

現有的DGL的實作版本由于在圖卷積過程需要将整張圖輸入到記憶體中，隻能擴充到有上千個節點的異質網。為了使得R-GCN能擴充到大規模的資料，作者采用了固定大小的節點和邊的采樣，像GraphSage一樣，用于batch-wise訓練。

（7）HAN

HAN的原始實作版本包含了大量hard-coded特定資料的設定，例如節點類型和元路徑，并且和R-GCN一樣不能擴充到大規模的資料集。作者在R-GCN實作的基礎上重新實作了HAN算法。

具體來說，我們首先根據所選的節點類型，基于adjacency lists自動建構元路徑。然後在batch-wise的訓練過程中為seed nodes采樣鄰居。

（8）TransE

修改了OpenKE的實作，使得模型隻輸出節點的嵌入表示。

（9）DistMult

作者去除了原始版本中hard-coded特定資料的設定，和原始版本相比極大地簡化了資料預處理。

（10）ConvE

同DistMult。

作者公開了提出的4個資料集，以及上述所有方法的實作代碼，組成了開源的易使用的HNE benchmark。

https://github.com/yangji9181/HNE

4.2 Performance Benchmarks

在我們整理的4個資料集上，對上述的10個流行的state-of-the-art的HNE算法進行了實驗對比。實驗情景有：無監督無屬性的HNE，帶屬性的HNE和半監督的HNE。

表5展示了無監督無屬性的HNE在節點分類和連結預測任務上的對比結果。

從表5中可以看出：

（1）proximity-perserving算法在無監督無屬性的HNE設定下，通常在兩個任務中都有較好的表現。這也就解釋了為什麼proximity-perserving算法是應用最廣泛的HNE。

在proximity-perserving方法中，HIN2Vec和HEER在連結預測任務中表現出了很好的效果，但是在節點分類問題上表現欠佳(尤其是在DBLP和Freebase資料集上)。實際上這兩個方法的目标主要是對邊的表示進行模組化(HIN2Vec中的 A M A_{\mathcal{M}} AM​，HEER中的 A l A_l Al​)，是以更适用于連結預測任務。

（2）在無監督無屬性的HNE設定下，message-passing方法表現不好，尤其是在節點分類任務中。正如我們前面所讨論過的，message-passing方法內建了節點屬性、連結結構和訓練标簽。當節點屬性和标簽都沒有的時候，我們使用随機的向量表示作為節點特征，并且使用連結預測的損失，這極大地限制了R-GCN和HAN的表現能力。後面将關注着兩個算法在有屬性的和半監督的HNE設定下的表現。

HAN在Yelp資料集上的連結預測結果甚至不可得。這是因為HAN隻能預測同類型的兩節點間的連邊(例如 business-business)，但是Yelp中所有的連邊連接配接的都是不同類型的節點(例如 business-user)。

（3）Relation-learning方法在Freebase和PubMed資料集上，兩個任務的表現更好，尤其在連結預測任務中表現更好。在表4和圖3中我們可以觀察到這兩個資料集，尤其是Freebase資料集，有更多種類型的邊。Relation-learning方法主要是為KG的嵌入學習設計的(例如 Freebase)，可以更好地捕獲到不同種類的有向連接配接的語義資訊。

從資料集的角度：

（1）所有的方法在Yelp和Freebase的節點分類任務上都有較低的F1值，尤其是Yelp。這是因為這兩個資料集都有大量的節點标簽，Yelp中是16個，Freebase是8個。

而且，和其他的資料集不同的是，Yelp中的節點可以有多個标簽，這使得分類任務更具挑戰。

（2）圖4中可以看出Freebase的度分布更加偏斜。這就會導緻在Freebase上進行邊的采樣或者随機遊走時，度數較小的節點被采樣的頻率越低，它們的表示就不能準确地學習到。

這一發現就能解釋為什麼連結預測在Freebase上的度量結果普遍比DBLP和Yelp上的低。

（3）從圖3-6可以看出，網絡屬性在Freebase和PubMed上更加均衡(尤其是在PubMed上)。對于所有算法，這使得節點分類和連結預測任務更加困難，同樣使得不同算法間的效果差異變小。

為了提供不同HNE算法的深層次的性能比較，我們進一步對實驗參數進行了控制。

圖7中展示了在PubMed資料集上進行節點分類和連結預測的結果。可以看出，不同的嵌入次元和link removal率可以對大多數算法的結果産生顯著影響。這再次說明了建立包括資料集和評估協定在内的标準基準對系統HNE算法評估的重要性。

在PubMed資料集上，大于50次元的嵌入會損害大多數算法的表現性能，尤其是在節點分類任務上。這可能是由于在有限的資料次元和标簽情況下産生了過拟合。有意思的是，随機去除掉連邊并沒有對連結預測任務的效果産生有害的影響，并且沒有對節點分類的預測結果帶來必然的損害。

這意味着節點的類别和連接配接的結構可能并不總是強相關聯的，甚至連接配接的一部分已經為節點分類提供了最大程度的有用資訊。

針對目前将節點屬性和标簽整合到R-GCN、HAN等嵌入學習中的HNE算法評價，我們還通過在節點屬性中加入随機高斯噪聲、掩蔽(mask)不同數量的訓練标簽進行了控制實驗。

圖8展示了在PubMed資料集上的結果。從中可以看出，所有子圖中的得分都比表5中的高，這表示了R-GCN和HAN在整合節點屬性和标簽方面的有效性。

當将方差更大的随機噪聲添加到節點屬性時，節點分類的性能顯著下降，但是連結預測的性能受的影響很小。當可獲得的訓練标簽更多時，所有算法都在節點分類任務上得到了顯著的提升，但是連結預測任務幾乎不受影響。

這一發現有一次證明了這兩個任務有着不同的天然特性，節點類别可以從節點内容和連接配接結構等多個信号中推斷得出，而連結隻和其他連結有關聯性。

5 Future

文本對多個現有的HNE算法進行了分類，并提供了benchmark資料集和baseline方法，以易于這一方向後續工作的開展。接下來簡單讨論一下目前HNE的局限性和值得探索的幾個方向。

（1）Beyond homophily(趨同性)

正如式（1）所示，目前的HNE算法利用了網絡的趨同性。最近的針對同質圖的研究結合了位置(positional)和結構(structural)的嵌入，未來可以探索如何将這樣的設計和範式推廣到HNE中。

特别地，在異質圖中，相對位置和節點的結構角色可使用不同的meta-paths或meta-graphs進行度量，這就可以利用更豐富的資訊。但是，這樣的考慮同樣引入了有關計算難度的挑戰。

（2）Beyond accuracy

大多數現有的HNE方法隻是關注于算法在下遊任務的準确率。未來應該進一步研究HNE的高效性(efficiency)和可擴充性(scalability)，時間适應性(用于動态網絡)，魯棒性(面向對抗攻擊)，可解釋性，不确定性(uncertainty)，公平性(fairness)。

（3）Beyond node embedding

已經有同質圖上針對圖級别的和子圖級别的嵌入算法的相關研究，但是很難在異質圖上應用。盡管HIN2Vec研究了元路徑的嵌入，以提升節點的嵌入表示。但是直接應用異質網的上下文對圖級别和子圖級别的嵌入學習還有待進一步研究。

（4）Revisiting KB embedding

KB嵌入和HNE主要差別在于節點和連邊類型的數量。直接将KB的嵌入學習方法用于異質網的話，沒有考慮到有豐富語義資訊的元路徑，直接将HNE應用到KB也是不現實的，因為KB元路徑的數量是指數級别的。

未來可以研究這兩組方法和這兩種類型資料的互動。

例如，如何将異質圖中的元路徑思想與KB中的embedding transformation相結合，以為HNE提供更多的語義感覺的轉換操作(semantic-aware transformation)？

如何為KB的嵌入學習設計基于截斷的随機遊走方法(truncated random walk)，以學習到包含高階關系資訊的嵌入表示？

（5）Modeling heterogeneous contexts

異質網的嵌入學習主要是對不同類型的節點和邊進行模組化。然而，如今的網絡中可能包含豐富的内容資訊，這些資訊為節點、邊和子網絡提供了上下文資訊。

是以，如何通過多模态的内容和結構的內建來對多方面(multi-facet)環境下的異構資訊互動進行模組化，是一個具有挑戰性但值得研究的方向。

（6）Understanding the limitation

雖然HNE(以及其他的基于神經網絡的表示學習模型)在多個領域中都有着很好的表現，但是我們還需要了解它的一些潛在的局限性。

例如，在什麼情況下流行的HNE算法比傳統的網絡挖掘方法(例如 path counting, 子圖比對, 非神經的或線性的模型)表現更好？如何聯合這兩種類型的方法的優點？

此外，已經有一些針對同質網的神經網絡的背後數學機制的深入研究(例如 smoothingm, 低通濾波器, invariant and equivariant變換)。本工作對現有的HNE模型進行了統一整理，也有助于促進對HNE的能力和局限性的進一步理論研究。