導(dǎo)讀

論文:

Representation Learning for Attributed Multiplex Heterogeneous Network

任務(wù):

針對(duì)考慮屬性的復(fù)雜異構(gòu)圖的圖表示學(xué)習(xí)

本文:

提出GATNE模型

機(jī)構(gòu):

清華大學(xué)、阿里達(dá)摩院

發(fā)表:

KDD 2019

一、動(dòng)機(jī)

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

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

因此,

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

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

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

二、什么是考慮屬性的復(fù)雜異構(gòu)圖 圖有哪些分類方式呢?

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

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

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

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

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

并分別列出了學(xué)術(shù)界的發(fā)展進(jìn)度(第二列)。

分為:

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

可以看出,

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

本文則重點(diǎn)關(guān)注 Attributed Multiplex Heterogeneous (AMHEN) 網(wǎng)絡(luò):

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

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

Heterogeneous:異構(gòu),節(jié)點(diǎn)和邊有多種類型,節(jié)點(diǎn)類型+邊類型>2

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

三、本文貢獻(xiàn)

本論文提出了兩個(gè)模型

Transductive Model: GATNE-T

Inductive Model: GATNE-I

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

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

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

Transductive learning:直推式學(xué)習(xí),后面我們簡稱T

Inductive Leaning:歸納式學(xué)習(xí),簡稱I

區(qū)別:

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

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

當(dāng)有新樣本時(shí),T需要重新進(jìn)行訓(xùn)練;I則不需要;

三、GATNE-T

GATNE模型

全稱:General Attributed Multiplex Heterogeneous Network Embedding

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

比如說,

用戶A在點(diǎn)擊查看商品的場景下學(xué)習(xí)一種向量表示,在購買商品的場景下學(xué)習(xí)另一種向量表示,而不同場景之間并不完全獨(dú)立。

具體的說,

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

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

公式中的ai,r為self-attention,計(jì)算當(dāng)前節(jié)點(diǎn)下的不同類型的邊的權(quán)重:

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

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

如下圖所示,

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

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

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

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

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

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

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

四、GATNE-I

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

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

于是提出了模型GATNE-I

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

GATNE-I

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

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

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

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

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

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

其中,Dz是vi對(duì)應(yīng)節(jié)點(diǎn)類型z上的特征變換矩陣。

五、訓(xùn)練算法

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

具體過程包括:

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

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

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

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

3. 然后對(duì)節(jié)點(diǎn)序列執(zhí)行skip gram以學(xué)習(xí)embedding表示;

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

   
   

2. 

3. 對(duì)每一對(duì)節(jié)點(diǎn)構(gòu)建目標(biāo)函數(shù):

   
   

   其中,L是與正訓(xùn)練樣本相對(duì)應(yīng)的負(fù)樣本數(shù)。

4. 

4. 通過構(gòu)建的目標(biāo)函數(shù)不斷更新模型參數(shù)

   六、數(shù)據(jù)集與實(shí)驗(yàn)效果

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

實(shí)驗(yàn)效果:

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