導讀

論文:

Representation Learning for Attributed Multiplex Heterogeneous Network

任務:

針對考慮屬性的復雜異構圖的圖表示學習

本文:

提出GATNE模型

機構:

清華大學、阿里達摩院

發(fā)表:

KDD 2019

一、動機

「圖的embedding表示」在真實世界中已經(jīng)有了非常大規(guī)模的應用,然而現(xiàn)存的一些圖嵌入相關的方法主要還是集中在同質(zhì)網(wǎng)絡的應用場景下,即節(jié)點和邊的類型都是單一類型的情況下。

但是,真實世界網(wǎng)絡中每個節(jié)點的類型都多種,每條邊的類型也有多種,而且每一個節(jié)點都具有不同且繁多的屬性(異構網(wǎng)絡)。

因此,

本論文提出了一種在Attributed Multiplex Heterogeneous Network(考慮屬性的復雜異構圖)中進行embedding學習的統(tǒng)一框架,還在Amazon, YouTube, Twitter, and Alibaba數(shù)據(jù)集上進行了大量的實驗。

實驗結(jié)果表明利用此框架學習到的embedding有驚人的性能提升F1 scores可提高5．99-28．23%

而且該框架還成功地部署在全球領先的電子商務公司阿里巴巴集團的推薦系統(tǒng)上。

二、什么是考慮屬性的復雜異構圖 圖有哪些分類方式呢?

節(jié)點類型(Node Type)表格第三列):單一類型 / 多類型

邊類型(Edge Type)第四列):單一類型 / 多類型 & 有向邊 / 無向邊

特征屬性(Attribute)最右側(cè)列):帶屬性 / 不帶屬性

根據(jù)以上幾種分類方式的不同組合,

本表格展現(xiàn)了六種不同類型的網(wǎng)絡(第一列),

并分別列出了學術界的發(fā)展進度(第二列)。

分為:

不帶屬性的同構網(wǎng)絡(HON)(第一行)、帶屬性的同構網(wǎng)絡(AHON)(第二行)、不帶屬性的異構網(wǎng)絡(HEN)、帶屬性的異構網(wǎng)絡(AHEN)、多重異構網(wǎng)絡(MHEN)和帶屬性的異構網(wǎng)絡(AMHEN)。

可以看出,

對節(jié)點多類型、邊多類型且?guī)�屬性的異質(zhì)網(wǎng)絡 (AMHEN)(最后一行)的研究目前是最少的。

本文則重點關注 Attributed Multiplex Heterogeneous (AMHEN) 網(wǎng)絡:

Attributed:考慮節(jié)點性質(zhì),如用戶性別、年齡、購買力等

Multiplex:多重邊,節(jié)點之間可能有多種關系,比如說兩個用戶之間可能為好友、同學、交易關系等;用戶和item之間可以瀏覽、點擊、添加到購物車、購買等

Heterogeneous:異構,節(jié)點和邊有多種類型,節(jié)點類型+邊類型>2

下圖為 阿里巴巴公司數(shù)據(jù)集的網(wǎng)絡及效果示意圖

三、本文貢獻

本論文提出了兩個模型

Transductive Model: GATNE-T

Inductive Model: GATNE-I

那么二者的區(qū)別又是什么呢?

想要知道二者的區(qū)別,首先要明白Transductive Model和Inductive Model的區(qū)別

那么Transductive Model和Inductive Model的區(qū)別是什么呢?

Transductive learning:直推式學習,后面我們簡稱T

Inductive Leaning:歸納式學習,簡稱I

區(qū)別:

模型訓練:T在訓練過程中已經(jīng)用到測試集數(shù)據(jù)(不帶標簽)中的信息,而I僅僅只用到訓練集中數(shù)據(jù)的信息,也就是說訓練時的T是見到過測試數(shù)據(jù)的;

模型預測:T只能預測在其訓練過程中所用到的樣本,而I只要樣本特征屬于同樣的歐拉空間,即可進行預測;

當有新樣本時,T需要重新進行訓練;I則不需要;

三、GATNE-T

GATNE模型

全稱:General Attributed Multiplex Heterogeneous Network Embedding

本文提出的GATNE模型,希望每個節(jié)點在不同類型邊中有不同的表示。

比如說,

用戶A在點擊查看商品的場景下學習一種向量表示,在購買商品的場景下學習另一種向量表示,而不同場景之間并不完全獨立。

具體的說,

本文將每個邊類型r上特定節(jié)點vi的整體embedding(Vi,r)分為兩部分:

base embedding(bi)和edge embedding(Uir),由二者組合而成。

公式中的ai,r為self-attention,計算當前節(jié)點下的不同類型的邊的權重:

其中,Uir表示i節(jié)點r邊的特征,Ui表示i節(jié)點concat聚合了所有邊類型的特征,m為聚合后的邊embedding的維度。

以上公式中,W、w 均為可訓練的參數(shù)矩陣。

如下圖所示,

base embedding不區(qū)分邊的類型,在不同類型的邊之間共享

edge embedding會區(qū)分不同類型的邊,利用類似于Graphsage對鄰居聚合的思想,節(jié)點i邊類型r下的特征表示Ui,r由周圍的K層鄰居聚合得到

對于節(jié)點i,他的base embedding(bi)與對于邊類型r節(jié)點i的初始的edge embedding(Uir)均為:根據(jù)網(wǎng)絡結(jié)構,針對每一個節(jié)點,通過訓練獲得。

模型結(jié)構如下圖所示:

圖上我們也可以看出,GATNE-T僅僅利用了網(wǎng)絡結(jié)構信息,而GATNE-I同時考慮了網(wǎng)絡結(jié)構信息和節(jié)點屬性。

但現(xiàn)實中的真實情況是:整張圖的網(wǎng)絡我們往往只能觀察到部分而非全部。

因此,為了解決部分觀察的問題,本論文在GATNE-T的模型上做了一個延伸,生成了一個新模型,叫作:GATNE-I

四、GATNE-I

本文基于GATNE-T模型的局限性:

不能處理觀察不到的數(shù)據(jù)然而在現(xiàn)實生活大量的應用中,被網(wǎng)絡化的數(shù)據(jù)常常只有部分能被觀測到

于是提出了模型GATNE-I

此模型能夠更好地處理那些不能被觀測到的數(shù)據(jù)部分,即,從考慮節(jié)點初始的特征入手。

GATNE-I

它不再為每一個節(jié)點直接訓練特征,而是通過訓練兩個函數(shù),將節(jié)點屬性分別通過兩個函數(shù)生成。

這樣有助于在訓練過程中哪怕看不到這個節(jié)點,但是只要這個節(jié)點有原屬性就可以通過函數(shù)生成相應特征。

對比GATNE-T模型,GATNE-I模型主要從以下三個角度進行調(diào)整:

1. base embedding:GATNE-T中base embedding由訓練得到,而GATNE-I考慮利用節(jié)點屬性(Xi)生成base embedding,其中加入了函數(shù)h,完成節(jié)點屬性Xi到base embedding=h(Xi)的轉(zhuǎn)化。

2. 初始edge embedding:GATNE-T中edge embedding值由隨機初始化得到,而GATNE-I中的初始edge embedding同樣利用節(jié)點屬性生成,其中使用了節(jié)點類型&邊類型的轉(zhuǎn)化函數(shù)。

3. 最終的 節(jié)點在邊類型為r下的 embedding 由 base embedding + edge embedding + 類型為z的節(jié)點的 轉(zhuǎn)化特征 DzXi 得到。

其中,Dz是vi對應節(jié)點類型z上的特征變換矩陣。

五、訓練算法

本文利用基于元路徑meta-path-based的隨機游走方法和skip-gram來學習模型參數(shù)。

具體過程包括:

1. 在圖上,對于每一種類型的邊,通過隨機游走生成節(jié)點序列,其中包含點Vi、Vj與邊r;

1. 由于是異構的,我們使用基于元路徑的隨機游走,然后設置路徑中各節(jié)點的轉(zhuǎn)移概率,0或1;

2. 基于元路徑的隨機游走策略確保了不同類型節(jié)點之間的語義關系能夠正確地融入到skip-gram模型中。

2. 通過公式(6)或(13)計算得到點Vir、Vjr的表示;

3. 然后對節(jié)點序列執(zhí)行skip gram以學習embedding表示;

1. 對于節(jié)點vi與其路徑中的“上下文”C,我們的目標為最小化負對數(shù)似然:

   
   

2. 

3. 對每一對節(jié)點構建目標函數(shù):

   
   

   其中,L是與正訓練樣本相對應的負樣本數(shù)。

4. 

4. 通過構建的目標函數(shù)不斷更新模型參數(shù)

   六、數(shù)據(jù)集與實驗效果

   數(shù)據(jù)集規(guī)模:

實驗效果:

紅色框框??出了本文模型在阿里數(shù)據(jù)集上的效果,可以看出,利用此框架學習到的embedding有著驚人的性能提升。