【論文解讀 AAAI 2019 | HHNE】Hyperbolic Heterogeneous Information Network Embedding

論文連結：https://www.aaai.org/ojs/index.php/AAAI/article/view/4471/4349

代碼連結：https://github.com/ydzhang-stormstout/HHNE

會議：AAAI 2019

文章目錄

• 1 摘要
• 2 介紹
• • 2.1 現有的方法
  • 2.2 動機
  • 2.3 雙曲空間
  • 2.4 作者提出
  • 2.5 貢獻
• 3 Embedding HIN in Hyperbolic Spaces
• • 3.1 問題定義
  • 3.2 Hyperbolic Geometry and Embedding
  • 3.3 HHNE模型
  • 3.4 優化
• 4 實驗
• 5 總結

1 摘要

複雜網絡的結構可能有着雙曲的幾何特征，因為雙曲結構可以天然地反映出複雜網絡的一些屬性，比如hierarchical（層級）結構和power-law（幂律）結構。本文是第一個在雙曲空間中研究HIN嵌入問題的。

文章分析了兩個真實的HIN，并發現了其存在power-law distribution等屬性，是以提出了雙曲的異質資訊網絡嵌入模型。

文章使用了meta-path指導的随機遊走采樣得到訓練資料，利用了節點在雙曲空間中的距離作為相似度度量。雙曲距離符合三角不等式，且可以很好地保留HIN中的傳遞資訊。作者還進一步推導出疊代更新雙曲嵌入的有效優化政策。

在網絡重構（network reconstruction）和連結預測（link prediction）任務中表現出了優于state-of-the-art的效果。通過可視化，也表現出了捕獲HIN層級結構的能力。

2 介紹

關注的根本問題為HIN的嵌入學習問題。

2.1 現有的方法

現有的方法大緻可以分為：基于随機遊走的方法；基于網絡分割的方法；基于深度神經網絡的方法。

這些方法都聚焦于如何有效地捕獲HIN的結構和語義資訊，然而還有一個基本的問題：HIN的适合的或内在的等軸空間（isometric spaces）是什麼？

也有一些研究将網絡嵌入到低維的雙曲空間中，但是它們都隻是對同質網絡的節點進行表示學習，沒有考慮異質的複雜資訊網絡。

HIN嵌入方法有Metapath2vec（Dong, Chawla, and Swami 2017）、HIN2vec（Fu, Lee, and Lei 2017）、PTE（Tang, Qu, and Mei 2015）、EOE（Xu et al. 2017）、HNE（Chang et al. 2015）、SHINE（Wang et al. 2018）。這些方法都是将HIN模組化在了低維的歐式空間中，然而歐式空間是否是最合适的選擇還有待研究。

2.2 動機

歐式空間已成為目前HIN嵌入方法的主流選擇，但是越來越多的研究表明，許多複雜的資料（如：社交網絡），有着高度非歐幾裡得的潛在資訊。

這引發了作者的思考：1）現有的HIN嵌入模型常用的低維空間（歐式空間）是否是合适的？2）是否有其他可行的非歐空間？

2.3 雙曲空間

雙曲空間是常負曲率空間，它比歐式空間擴張速度快（文章中有舉例），是以更易于對有着低維嵌入表示的複雜資料模組化。

Krioukov（2010）等人将雙曲空間作為複雜網絡的基礎，并且發現了有幂律（power-law）結構的資料适合于在雙曲空間中模組化。Dhingra（2018）等人将文本表示在了雙曲空間中，(Nickel and Kiela 2017)和 (Ganea, Becigneul, and Hofmann 2018) 在雙曲空間中學習到了同質網絡的嵌入表示。

2.4 作者提出

作者提出HHNE模型（hyperbolic heterogeneous information network embedding ），在雙曲空間中獲得網絡的結構和語義資訊。

使用元路徑指導的随機遊走，擷取HIN中的結構資訊和語義關聯資訊。

節點在雙曲空間中的距離，作為節點間相似度的衡量标準，距離符合三角不等式，且可以很好地保留HIN中的傳遞資訊。

模型實作了最大化鄰域節點間的相似度，最小化負采樣節點間的相似度。作者還進一步推導出疊代更新雙曲嵌入的有效優化政策。

2.5 貢獻

（1）第一個在雙曲空間進行HIN的嵌入學習；

（2）提出HHNE模型，解決上述問題；

（3）進行實驗驗證了HHNE的表示能力，效果優于state-of-the-art。

3 Embedding HIN in Hyperbolic Spaces

3.1 問題定義

（1）HIN（異質資訊網絡）

定義圖為 G = ( V , E , T , ϕ , ψ ) G=(V,E,T,\phi,\psi) G=(V,E,T,ϕ,ψ)， V V V和 E E E分别是節點集合和邊集合。 ϕ ( v ) : V → T V , ψ ( e ) : E → T E \phi(v):V\rightarrow T_V, \psi(e):E\rightarrow T_E ϕ(v):V→TV​,ψ(e):E→TE​且 ∣ T V ∣ + ∣ T E ∣ > 2 |T_V|+|T_E|>2 ∣TV​∣+∣TE​∣>2。

（2）元路徑

元路徑 P P P是不同類型的邊連接配接起來的不同節點類型的序列。

（3）HIN embedding

輸入 G = ( V , E , T , ϕ , ψ ) G=(V,E,T,\phi,\psi) G=(V,E,T,ϕ,ψ)，将節點映射到潛在的低維表示空間，同時保留原始的網絡結構資訊以及語義關聯。

作者使用兩個真實的HIN檢測節點的power-law分布是否也存在不同的元路徑。

節點分布計算過程如下：給定元路徑 P P P和節點 v v v，首先計算從節點 v v v出發，按照元路徑 P P P的模式，能生成多少條元路徑。然後計算有多少節點有相同的結果。上述兩步操作的結果分别作為橫縱坐标值，分布在空間中。例如，對于DBLP和MovieLens 資料集，有如下分布：

從圖中可以看出，這些分布是幂律分布。表明了雙曲空間可能是HIN嵌入的合适的空間。

HIN中有許多元路徑，有些元路徑也許不具有幂律分布，但是在本文後續的實驗中可以看出，實驗結果仍然是有競争力的。今後的研究還需要對元路徑有更細粒度的分析。

幂律分布通俗解釋：資料波動非常地大，少數點的數值特别高，大多數的點數值都很低，最大和最小的點之間，可能相差好幾個數量級。

這和網絡的生長方式有關：網絡生長的方式不是随機發生的，而是優先連接配接。當新的節點加入網絡，或者網絡中有新的連接配接産生時，連接配接度高的節點會比連接配接度低的節點更有可能得到新連接配接，這就是所謂的優先連接配接。

3.2 Hyperbolic Geometry and Embedding

雙曲幾何是非歐幾裡德幾何，它是通過取代歐幾裡德第五幾何公設(平行公設)而得到的。

雙曲空間H的一個關鍵性質是它們比歐幾裡得空間擴張得更快，因為歐幾裡得空間R多項式地擴張，而雙曲空間H指數地擴張。

在圖4(a)中，每個瓦片在雙曲空間中的面積是相等的，但是在歐式空間中随着向邊界處擴充，面積逐漸減小為0。

由于這個性質，雙曲空間可以考慮為連續樹。如圖4(b)所示，對于分支系數為b的樹，第 l l l層的節點數為 ( b + 1 ) b l − 1 (b+1)b^{l-1} (b+1)bl−1；從根節點出發跳數不超過 l l l的節點數為 [ ( b + 1 ) b l − 2 ] / ( b − 1 ) [(b+1)b^l-2]/(b-1) [(b+1)bl−2]/(b−1)。

節點的數量，随着節點到根節點距離的增加而指數增長，這和雙曲空間是很相似的，都是指數型增長。在雙曲空間中，樹結構類型的資料可以被天然地嵌入到2維雙曲空間中。

給定第 l l l層的一個節點，它可以被表示在雙曲空間距離源點 d H ∝ l d^H\propto l dH∝l的球面上，分支系數 b b b可用雙曲空間中的常曲率 K = − l n 2 b K=-ln^2b K=−ln2b表示。

如上所述，節點的數量随着節點到根節點距離的增加而指數增長，樹中節點的分布也就服從幂律分布。呈幂律分布的資料，适合于模組化在雙曲空間中(Krioukov et al. 2010)。

雙曲空間不能等距同構到歐式空間，很難做。有學者提出了一些雙曲空間的等價模型，例如Poincar´ e disk (ball) model，Poincar´ e half-plane model, Beltrami-Klein model, hyperboloid model 。作者使用了Poincar´ e ball model，因為該模型可适用于基于梯度更新的優化。

設 D d = { x ∈ R d : ∣ ∣ x ∣ ∣ < 1 } D^d={\{x \in R_d:||x||<1\}} Dd={x∈Rd​:∣∣x∣∣<1}為開放的 d d d維機關球。Poincar´ e ball模型用多個 D d D^d Dd和如下所示的黎曼度量張量（Riemannian metric tensor） g x D g^D_x gxD​表示：

其中 x ∈ D d , g E = I x\in D^d, g^E=\bold I x∈Dd,gE=I表示歐幾裡得度量張量。Poincar´ e模型是保角的，也就是說，模型中兩個雙曲線之間的歐幾裡得夾角和它們之間的雙曲夾角相等，是以可用于基于梯度的優化方法。

3.3 HHNE模型

給定異質圖 G = ( V , E , T , ϕ , ψ ) , ∣ T V ∣ > 1 G=(V,E,T,\phi,\psi), |T_V|>1 G=(V,E,T,ϕ,ψ),∣TV​∣>1，目的是學習到節點表示 Θ = { θ i } i = 1 ∣ V ∣ , θ i ∈ D d \Theta={\{\theta_i\}^{|V|}_{i=1}}, \theta_i\in D^d Θ={θi​}i=1∣V∣​,θi​∈Dd。通過促進節點 v v v和其鄰居 c t ∈ C t ( v ) c_t\in C_t(v) ct​∈Ct​(v)的相似性（t為類型），實作對網絡結構的保留。

使用元路徑指導的随機遊走，為每個節點獲得異質鄰域。給定元路徑模式 P P P，在第 i i i步的轉移機率計算如下：

其中 v t v i i v^i_{t_{v_i}} vtvi​​i​是類型為 t v i t_{v_i} tvi​​的節點， N t v i + 1 ( v t v i i ) N_{t_{v_{i+1}}}(v^i_{t_{v_i}}) Ntvi+1​​​(vtvi​​i​)是節點 v t v i i v^i_{t_{v_i}} vtvi​​i​的類型為 t v i + 1 t_{v_{i+1}} tvi+1​​的鄰居節點。

使用節點在Poincar´ e ball 模型中的距離，來衡量節點間的相似度。給定節點嵌入表示 θ i , θ j ∈ D d \theta_i, \theta_j\in D^d θi​,θj​∈Dd，距離計算如下：

使用機率模型，衡量節點 c t c_t ct​是節點 v v v的鄰居的機率：

其中 σ ( x ) = 1 1 + e x p ( − x ) \sigma(x)=\frac{1}{1+exp(-x)} σ(x)=1+exp(−x)1​。模型的目标函數就是最大化下面的機率：

作者還利用負采樣技術，以實作更有效的優化。在HHNE模型中，對于給定的節點 v v v，我們希望最大化 v v v和鄰居節點 c t c_t ct​的相似度，同時最小化 v v v和負采樣節點 n n n的相似度。是以，（4）式被重寫為下式：

3.4 優化

由于Poincar´ e ball 模型有着Riemannian manifold structure，是以反向傳播的梯度是黎曼梯度。也就是說，基于歐幾裡得的梯度優化，例如： θ i ← θ i + η ∇ θ i E L ( Θ ) \theta_i \leftarrow \theta_i+\eta\nabla^E_{\theta_i}L(\Theta) θi​←θi​+η∇θi​E​L(Θ)，是無效的優化。

是以，（5）式需要通過黎曼随機梯度下降(RSGD)來優化。 T θ i D d \Tau_{\theta_i}D^d Tθi​​Dd為節點嵌入 θ i ∈ D d \theta_i\in D^d θi​∈Dd的切面空間。然後就可以計算 L ( Θ ) L(\Theta) L(Θ)的黎曼梯度 ∇ θ i R L ( Θ ) ∈ T θ i D d \nabla^R_{\theta_i}L(\Theta) \in \Tau_{\theta_i}D^d ∇θi​R​L(Θ)∈Tθi​​Dd。使用RSGD，（5）式中的參數按照如下的方式更新：

給定 θ i ∈ D d , s = η ∇ θ i R L ( Θ ) \theta_i\in D^d, s=\eta\nabla^R_{\theta_i}L(\Theta) θi​∈Dd,s=η∇θi​R​L(Θ)，指數映射函數 e x p θ i ( ⋅ ) exp_{\theta_i}(\cdot) expθi​​(⋅)表示如下

因為Poincar´ e ball模型是雙曲空間中的保角模型，是以黎曼梯度 ∇ R \nabla^R ∇R可以通過，對歐幾裡得梯度 ∇ E \nabla^E ∇E進行尺度變換得到：

對（5）式求導的結果如下，疊代地使用(9)(10)式更新模型參數：

其中 α = 1 − ∣ ∣ θ c t ∣ ∣ 2 , β = 1 − ∣ ∣ θ u m ∣ ∣ 2 , γ = 1 + 2 α β ∣ ∣ θ c t − θ u m ∣ ∣ 2 \alpha=1-||\theta_{c_t}||^2, \beta=1-||\theta_{u^m}||^2, \gamma=1+\frac{2}{\alpha\beta}||\theta_{c_t}-\theta_{u^m}||^2 α=1−∣∣θct​​∣∣2,β=1−∣∣θum​∣∣2,γ=1+αβ2​∣∣θct​​−θum​∣∣2；

m = 0 m=0 m=0時， u 0 = v u^0=v u0=v；

I v [ u ] I_v[u] Iv​[u]是訓示函數，表示 u u u是否為 v v v。

4 實驗

資料集：DBLP、MovieLens。

實驗任務：網絡重構；連結預測；可視化。

對比方法：

（1）同質網絡嵌入方法：DeepWalk、LINE、node2vec

（2）異質資訊網絡嵌入方法：metapath2vec

（3）雙曲同質網絡嵌入方法：Poincar´ eEmb

實驗結果：

（1）網絡重構實驗結果：

（2）連結預測實驗結果：

（3）DBLP資料集可視化結果如下：

5 總結

本文在雙曲空間中研究了HIN的嵌入學習問題，提出了HHNE模型，是第一個進行此項研究的文章。

文章使用了節點在雙曲空間中的距離，作為相似度度量。既滿足三角不等式，又保留了HIN中的傳遞資訊。并使用了黎曼随機梯度下降方法優化模型。

實驗表明了HHNE超越了state-of-the-art，并且證明了該模型能發現HIN中的隐含層級資訊。尤其是在MoiveLens上的網絡重構的實驗結果，居然有的高達99%多。

而且當嵌入表示的次元很小的情況下，HHNE模型也能表現出很好的效果。這說明了當空間次元小時，雙曲空間有着很強的模組化能力。

這篇文章的研究前提是，定義的元路徑在HIN中是呈幂律分布的。少量的不滿足幂律分布的元路徑的存在，并不會對結果産生較大影響。今後的研究還需要對元路徑有更細粒度的分析。