論文鏈接：https://www.ijcai.org/proceedings/2021/0203.pdf

摘要：異質(zhì)信息網(wǎng)絡(luò)嵌入，學(xué)習(xí)多類型節(jié)點(diǎn)的低維表示，已經(jīng)被廣泛應(yīng)用并取得了優(yōu)異的性能表現(xiàn)。然而，大多數(shù)已有工作關(guān)注于靜態(tài)異質(zhì)信息網(wǎng)絡(luò)或?qū)W習(xí)特定快照網(wǎng)絡(luò)中的節(jié)點(diǎn)嵌入，很少關(guān)注整個(gè)網(wǎng)絡(luò)的演化過程以及捕捉相關(guān)的演化動(dòng)態(tài)特性。為了通過考慮演化過程中的所有時(shí)序動(dòng)態(tài)來填補(bǔ)獲得多類型節(jié)點(diǎn)低維嵌入的空白，我們提出了一種新的時(shí)序HIN嵌入方法（THINE）。該方法不僅使用注意力機(jī)制和元路徑來保留HIN中的結(jié)構(gòu)和語義信息，而且還結(jié)合Hawkes過程來模擬時(shí)序網(wǎng)絡(luò)演化。我們對各種真實(shí)時(shí)間中的時(shí)序HIN進(jìn)行了廣泛評(píng)估，實(shí)驗(yàn)結(jié)果表明THINE在靜態(tài)和動(dòng)態(tài)任務(wù)（包括節(jié)點(diǎn)分類、鏈路預(yù)測和時(shí)序鏈路推薦）中都實(shí)現(xiàn)了SOTA的性能表現(xiàn)。

1、Introduction

近年來，網(wǎng)絡(luò)嵌入因其優(yōu)異的性能表現(xiàn)已經(jīng)受到了越來越多的人的關(guān)注。它將網(wǎng)絡(luò)節(jié)點(diǎn)映射到一個(gè)低維向量空間，并同時(shí)保留了網(wǎng)絡(luò)的屬性特征和結(jié)構(gòu)特征。許多優(yōu)秀的算法，如Deepwalk、LINE等被提出，并被成功應(yīng)用到各種網(wǎng)絡(luò)相關(guān)的任務(wù)中，如節(jié)點(diǎn)分類、節(jié)點(diǎn)聚類以及鏈路預(yù)測等。

然而，這些方法都關(guān)注于同質(zhì)網(wǎng)絡(luò)，而現(xiàn)實(shí)世界中的絕大多數(shù)網(wǎng)絡(luò)數(shù)據(jù)是異質(zhì)的，其中包含了多種類型的節(jié)點(diǎn)和連邊關(guān)系。例如一個(gè)學(xué)術(shù)網(wǎng)絡(luò)通常由三類節(jié)點(diǎn)：作者（A）、論文（P）以及會(huì)議（C）；與多種類型的連邊關(guān)系構(gòu)成：作者與論文之間有合著、引用及撰寫等關(guān)系；論文與會(huì)議之間有出版關(guān)系等。在HIN中，不同類型的節(jié)點(diǎn)與連邊關(guān)系可以生成各種類型的嵌入表示，包含更為復(fù)雜的結(jié)構(gòu)及相互關(guān)系。也就是說，越來越多的研究人員開始關(guān)注于HIN的表示學(xué)習(xí)領(lǐng)域，如PTE、Metapath2Vec以及MAGNN等。

盡管如此，目前大多數(shù)工作都是針對靜態(tài)HIN提出的，而現(xiàn)實(shí)中的HIN是隨時(shí)間演化的。如學(xué)術(shù)網(wǎng)絡(luò)中作者可能在不同年份發(fā)表不同的論文，業(yè)務(wù)等級(jí)根據(jù)用戶在Yelp中的評(píng)論隨時(shí)間變化而變化。因此簡單地將時(shí)序HIN視為靜態(tài)不變的，將會(huì)無法準(zhǔn)確捕捉HIN變化時(shí)的結(jié)構(gòu)和語義特征。

因此對于時(shí)序HIN的了解與日俱增。然而它卻面臨兩個(gè)嚴(yán)峻的挑戰(zhàn)：首先，如何有效的保留時(shí)序HIN中的結(jié)構(gòu)和語義動(dòng)態(tài)特征？動(dòng)力學(xué)描述了HIN在其演化過程中節(jié)點(diǎn)和邊的所有變化情況，包括節(jié)點(diǎn)的添加、邊的刪除等。因此準(zhǔn)確捕捉動(dòng)態(tài)特性對于研究時(shí)序HIN至關(guān)重要。而像DHNE等之前的大多數(shù)工作，通過簡單的將時(shí)間劃分為幾個(gè)時(shí)期來使用快照對時(shí)序HIN進(jìn)行建模，這會(huì)失去快照內(nèi)的動(dòng)態(tài)特性。

另一個(gè)挑戰(zhàn)是如何捕捉異質(zhì)節(jié)點(diǎn)之間的時(shí)序影響？不同于同質(zhì)網(wǎng)絡(luò)，HIN包含了多種類型的節(jié)點(diǎn)和邊，因此它包含了更復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)和更豐富的語義信息。例如在學(xué)術(shù)網(wǎng)絡(luò)中，我們通常會(huì)考慮來自相同類型節(jié)點(diǎn)的時(shí)序影響（如作者-作者，或論文-論文）。此外，在HIN中，我們還應(yīng)考慮來自不同類型節(jié)點(diǎn)的時(shí)序效應(yīng)（如作者-論文）。但由于難以模擬異質(zhì)節(jié)點(diǎn)之間的影響，以前的大多數(shù)工作如HDGAN、DyHNE僅考慮來自相同類型節(jié)點(diǎn)的時(shí)序影響。

為此我們提出了THINE，一種新穎的時(shí)序異質(zhì)網(wǎng)絡(luò)嵌入模型，用于捕捉所有類型節(jié)點(diǎn)之間的動(dòng)態(tài)特征。我們首先定義各種元路徑來捕捉HIN的語義和結(jié)構(gòu)，再對于特定的下游任務(wù)，生成與任務(wù)相關(guān)的候選元路徑集。通過使用Hawkes過程對節(jié)點(diǎn)之間的時(shí)序影響進(jìn)行建模，我們獲得了每個(gè)節(jié)點(diǎn)的低維嵌入。此外，還應(yīng)用了兩個(gè)級(jí)別的注意力機(jī)制來區(qū)分各個(gè)方面的權(quán)重。一種針對不同類型的元路徑，一種針對鄰居節(jié)點(diǎn)的距離。在各種真實(shí)世界數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，與幾種SOTA方法相比，我們的THINE在靜態(tài)和動(dòng)態(tài)任務(wù)中表現(xiàn)更好。

本文中我們的主要工作總結(jié)如下：

1、我們在時(shí)序異質(zhì)信息網(wǎng)絡(luò)嵌入問題中考慮了網(wǎng)絡(luò)的演化動(dòng)態(tài)特性；

2、我們提出了新的時(shí)序異質(zhì)信息網(wǎng)絡(luò)嵌入模型，該模型使用元路徑來捕捉HIN中的結(jié)構(gòu)信息和語義信息，并通過Hawkes過程來建模了網(wǎng)絡(luò)的演化動(dòng)態(tài)特性，同時(shí)應(yīng)用了兩個(gè)注意力層來分別捕捉不同的結(jié)構(gòu)特征和語義特征。

3、進(jìn)行了實(shí)驗(yàn)，結(jié)果表明在三個(gè)真實(shí)數(shù)據(jù)集上，THINE表現(xiàn)更好。

2、Preliminaries

一個(gè)HIN的演化可以視為在不同時(shí)間步上，節(jié)點(diǎn)或邊的添加或刪除。我們通常對時(shí)序HIN的定義如下：

定義1（時(shí)序HIN）：一個(gè)時(shí)序HIN被定義為 $G=（V，E，T，\phi ，\varphi ）$ ，其中V為節(jié)點(diǎn)集，E為邊集，T表示時(shí)間戳。此外有兩個(gè)映射函數(shù)， $\phi ：V\rightarrow A，\varphi ：E\rightarrow R$ ，其中A和R分別表示節(jié)點(diǎn)類型集合和邊類型集合。對于任意HIN，滿足 $|A|+|R|>2$ 。

特別的，邊 $e_{ij}^t\in E$ 表示節(jié)點(diǎn) $v_i$ 與節(jié)點(diǎn) $v_j$ 在時(shí)間步 t 建立連邊關(guān)系。值得注意的是，兩個(gè)節(jié)點(diǎn)可能在不同時(shí)間建立多個(gè)關(guān)系。例如會(huì)議（C）可能會(huì)發(fā)表同一作者（A）的多篇論文，因此學(xué)術(shù)網(wǎng)絡(luò)中A和C之間可能存在大量關(guān)系。

定義2（節(jié)點(diǎn)對的影響）：節(jié)點(diǎn)對的影響表示兩個(gè)節(jié)點(diǎn)對建立它們之間連邊關(guān)系的貢獻(xiàn)。給定一個(gè)節(jié)點(diǎn)對 $（v_i,v_j）$ ，其中 $v_i，v_j\in V$ ，V為節(jié)點(diǎn)集，兩節(jié)點(diǎn)的影響為 $\eta _{x,y}$ ，則：

$\eta _{x,y}=-||u_x - u_y||^2$ ? ? ? ? (1)

其中 $u_x，u_y$ 分別表示節(jié)點(diǎn) $v_x，v_y$ 的嵌入表示。

定義3（元路徑）：給定一個(gè)時(shí)序HIN， $G=（V，E，T，\phi ，\varphi ）$ ，元路徑M是一個(gè)定義如下的路徑：

其中 $r_i\in R，a_i \in A$ ，A和R分別表示節(jié)點(diǎn)的類型和邊的類型。顯然，一個(gè)元路徑被描述為一個(gè)類型為 $a_1到a_l$ 的復(fù)雜關(guān)系。特別的，滿足元路徑M的節(jié)點(diǎn)序列 $（v_1，v_2，…，v_l）$ 是元路徑M的一個(gè)路徑實(shí)例m。

定義4（候選元路徑集）：一個(gè)時(shí)序邊 $e_{ij}^t\in E$ 的候選元路徑集S(t)是一個(gè)包含了所有涉及源節(jié)點(diǎn) $v_i$ ，并且在時(shí)間 t 之前生成的元路徑實(shí)例的集合。請注意，在時(shí)間 t 之前形成的路徑實(shí)例，意味著它包含的所有時(shí)序邊都在時(shí)間 t 之前生成。

在本文中，我們的目標(biāo)是在考慮時(shí)間動(dòng)態(tài)的情況下獲得多類型節(jié)點(diǎn)嵌入。形式上，我們將問題定義如下：

問題：時(shí)序HIN嵌入：給定一個(gè)時(shí)序HIN $G=（V，E，T，\phi ，\varphi ）$ ，目標(biāo)是學(xué)習(xí)一個(gè)映射函數(shù) $f:V\rightarrow R^d$ ，其中 d<<|V|，且 d 表示嵌入維度。函數(shù) f 不僅要捕捉到網(wǎng)絡(luò)的演化時(shí)序動(dòng)態(tài)特征，還需要考慮所有類型的節(jié)點(diǎn)間的相互影響。

3、The Propsed Model

3.1 Model Overview

在本節(jié)中，我們將解釋我們提出的模型 THINE 的細(xì)節(jié)，它可以結(jié)合時(shí)間動(dòng)態(tài)的影響來捕捉 HIN 的結(jié)構(gòu)和語義。如圖 1 所示，THINE 通過基于元路徑的隨機(jī)游走獲得不同類型節(jié)點(diǎn)之間的結(jié)構(gòu)交互。然后，我們獲得每個(gè)邊的候選元路徑集，以使用 Hawkes 過程對時(shí)序 HIN 的動(dòng)態(tài)結(jié)構(gòu)和語義進(jìn)行建模。此外，通過區(qū)分不同關(guān)系影響的結(jié)構(gòu)級(jí)和語義級(jí)注意機(jī)制進(jìn)行優(yōu)化，我們聚合每個(gè)節(jié)點(diǎn)的效果以獲得多類型節(jié)點(diǎn)嵌入。

3.2 THINE Model

使用元路徑捕獲語義。THINE 首先使用基于元路徑的隨機(jī)游走來提取 HIN 的信息。元路徑的構(gòu)建決定了我們可以捕捉到哪些語義和結(jié)構(gòu)。因此，元路徑的選擇對于研究 HIN 至關(guān)重要。定義元路徑的關(guān)鍵是包含盡可能多的語義。例如，對于學(xué)術(shù)網(wǎng)絡(luò)，除了之前模型考慮的作者-論文關(guān)系的配對路徑外，我們還考慮了論文-論文關(guān)系的元路徑，寫為APPA?？偟膩碚f，我們定義的元路徑列在表 1 中。使用這些元路徑，我們可以很好地保留 HIN 中的語義。此外，網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊受節(jié)點(diǎn)本身和相關(guān)候選元路徑集的影響。因此，基于節(jié)點(diǎn)對的影響，我們對候選集的影響進(jìn)行建模以理解時(shí)序 HIN。

候選元路徑集的建模動(dòng)力學(xué)。此外，我們模擬候選元路徑集的影響，以使用Hawkes過程捕獲時(shí)序 HIN 的語義和結(jié)構(gòu)。通常，Hawkes過程用于模擬過去事件對現(xiàn)在的影響。顯然，事件越久，它們對當(dāng)前的影響就越小。具體來說，對于THINE，我們對每一個(gè)影響都應(yīng)用了Hawkes過程的關(guān)注。因此，候選元路徑集的影響，以及所有相關(guān)元路徑實(shí)例的影響，正式定義為：

其中 m 是一個(gè)元路徑實(shí)例， $t_m < t$ 表示在時(shí)間 t 之前生成的元路徑實(shí)例 m。為方便起見，我們使用 $\eta _i，i \in (s，m，e)$ 來表示候選元路徑集、一個(gè)元路徑和一個(gè)時(shí)序邊的影響。因此， $\eta _s(t)，\eta _m(t)和\eta _e(t)$ 表示時(shí)間 t 之前的相應(yīng)影響。因此我們需要對一個(gè)元路徑實(shí)例 $\eta _m(t)$ 的影響進(jìn)行初步建模，這可以被認(rèn)為是它包含的所有邊的影響。因此，它被定義為:

其中 $e_{ij}$ 表示節(jié)點(diǎn) $v_i$ 和 $v_j$ 之間的一條邊。一條邊可以由它連接的兩個(gè)節(jié)點(diǎn)表示。因此，我們通過使用節(jié)點(diǎn)對和霍克斯過程的影響來模擬一個(gè)時(shí)間邊緣的影響，這意味著

其中 $t_{i,j}$ 表示邊緣 $e_{ij}^t$ 的時(shí)間戳， $k(t-t_{i,j})$ 描述了時(shí)間衰減效應(yīng)，我們定義 $k(t-t_{i,j})=e^{(-\sigma _i(t-t_{i,j}))}$ 。 δ 是與節(jié)點(diǎn)相關(guān)的可訓(xùn)練參數(shù)，用于調(diào)整時(shí)間衰減效果的比例。

請注意，由于計(jì)算復(fù)雜性，我們選擇候選元路徑集的子集進(jìn)行訓(xùn)練。具體來說，我們選擇從時(shí)間 t 最近生成的 n 個(gè)元路徑實(shí)例，n 是一個(gè)超參數(shù)。很可能，對于一個(gè)元路徑實(shí)例，我們選擇最接近源節(jié)點(diǎn)的 z 個(gè)候選邊進(jìn)行訓(xùn)練，z 也是一個(gè)超參數(shù)。

使用注意力機(jī)制優(yōu)化。我們展示了THINE如何計(jì)算候選元路徑集的詳細(xì)過程。如圖1（c）所示，邊 $e_{a_3p_4}^t$ 的候選元路徑集包含 $m_1:(a_1,p_2,c_1,p_3,a_3)，m_2:(a_2,p_3,a_3)$ 等。因此 $\eta _s(t)=\eta _{m_1}(t)+\eta _{m_2}(t)$ 。顯然 $m_1$ 和 $m_2$ 是由不同元路徑APCPA和APA生成，它們將影響不同的任務(wù)。為了捕捉這種微妙的區(qū)別，我們應(yīng)用了語義級(jí)注意機(jī)制。形式上，我們定義不同類型元路徑的權(quán)重如下：

其中 c 是任務(wù)中定義的所有元路徑的集合， $\omega _b$ 表示第 b 個(gè)元路徑的權(quán)重?？紤]到不同元路徑的語義，我們將候選元路徑集的影響重新表述為:

其中 $\omega _M$ 為元路徑M的權(quán)重，而元路徑實(shí)例m屬于M。根據(jù)上述定義， $\eta _{m_1}(t)=\eta _{e_{a_1p_2}}(t)+\eta _{e_{p_2c_1}}(t)+\eta _{e_{c_1p_3}}(t)+\eta _{e_{p_3a_3}}(t)$ 。顯然，由于訓(xùn)練邊 $e_{a_3p_4}^t$ 的跳數(shù)，每條邊的影響應(yīng)該是不同的。因此，使用結(jié)構(gòu)級(jí)別的注意力機(jī)制來捕捉這種差異，我們將與跳數(shù)相關(guān)的權(quán)重表示為：

其中 $h_{oq}$ 表示邊 $e_{oq}$ 到源節(jié)點(diǎn)的跳數(shù)，第 $h_{oq}$ 跳的權(quán)重表示為 $\theta _{h_{oq}}$ 。 $z^/$ 正相關(guān)于候選邊 z 的數(shù)量。即一個(gè)元路徑實(shí)例的影響可重新定義為：

通過元路徑、兩級(jí)注意力機(jī)制和霍克斯過程，我們對每個(gè)時(shí)序邊的演化進(jìn)行建模。通過這種方式，THINE 能夠在靜態(tài)和動(dòng)態(tài)網(wǎng)絡(luò)中獲得具有保留語義和結(jié)構(gòu)的多類型節(jié)點(diǎn)嵌入?；谝陨瞎?，我們定義條件強(qiáng)度函數(shù) $\tilde{\lambda } _{x,y}(t)$ 來表示在時(shí)間 t 處節(jié)點(diǎn) $v_x$ 和 $v_y$ 之間生成時(shí)序邊的強(qiáng)度：

$\tilde{\lambda } _{x,y}(t)=\eta _{x,y}+\eta _s(t)=\eta _{x,y}+\sum_{t_m<t} (\omega _M\times \sum_{e_{ij}\in m}\theta _{h_ij}\times \eta _{e_ij}(t))$ ? ? (9)

因?yàn)闂l件強(qiáng)度函數(shù)應(yīng)該返回一個(gè)正實(shí)數(shù)，因此使用指數(shù)函數(shù)來轉(zhuǎn)換 $\tilde{\lambda } _{x,y}(t)$ ，即有 ${\lambda } _{x,y}(t)=exp(\tilde{\lambda } _{x,y}(t))$ 。 ${\lambda } _{x,y}(t)$ 取值為0到1，表示節(jié)點(diǎn) $v_x$ 與 $v_y$ 之間建立連邊的概率。

損失函數(shù)：因此，我們可以表示在時(shí)間 t 節(jié)點(diǎn) $v_x$ 和 $v_y$ 之間建立連接的概率。特別是，考慮到時(shí)間 t 之前的條件強(qiáng)度函數(shù)和候選元路徑集 S(t)，我們將這個(gè)概率定義為

其中 $y^/$ 表示時(shí)序 HIN 中除 $v_x$ 之外的所有節(jié)點(diǎn)，所有節(jié)點(diǎn)對的對數(shù)似然可以表示為:

顯然， $p(v_x,v_y|S(t))$ 的計(jì)算需要匯總?cè)W(wǎng)節(jié)點(diǎn)的信息。我們應(yīng)用負(fù)采樣技術(shù)使我們的模型降低計(jì)算開銷。所以損失函數(shù)可以重新表述為：

其中K為根據(jù) $P_n(v)$ 采樣到負(fù)樣本個(gè)數(shù)， $P_n(v)$ 正相關(guān)于 $d_v^{3/4}$ ，且 $d_v$ 表示節(jié)點(diǎn) v 的度。 $\sigma$ 為sigmoid函數(shù)，表示為 $\sigma (x)=\frac{1}{1+e^{-x}}$ 。最后，我們通過Adam方法優(yōu)化模型。