導讀

論文:

Representation Learning for Attributed Multiplex Heterogeneous Network

任務:

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

本文:

提出GATNE模型

機構:

清華大學、阿里達摩院

發表:

KDD 2019

一、動機

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

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

因此,

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

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

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

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

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

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

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

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

本表格展現了六種不同類型的網絡(第一列),

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

分為:

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

可以看出,

對節點多類型、邊多類型且帶屬性的異質網絡 (AMHEN)(最后一行)的研究目前是最少的。

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

Attributed:考慮節點性質,如用戶性別、年齡、購買力等

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

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

下圖為 阿里巴巴公司數據集的網絡及效果示意圖

三、本文貢獻

本論文提出了兩個模型

Transductive Model: GATNE-T

Inductive Model: GATNE-I

那么二者的區別又是什么呢?

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

那么Transductive Model和Inductive Model的區別是什么呢?

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

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

區別:

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

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

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

三、GATNE-T

GATNE模型

全稱:General Attributed Multiplex Heterogeneous Network Embedding

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

比如說,

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

具體的說,

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

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

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

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

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

如下圖所示,

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

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

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

模型結構如下圖所示:

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

但現實中的真實情況是:整張圖的網絡我們往往只能觀察到部分而非全部。

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

四、GATNE-I

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

不能處理觀察不到的數據然而在現實生活大量的應用中,被網絡化的數據常常只有部分能被觀測到

于是提出了模型GATNE-I

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

GATNE-I

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

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

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

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

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

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

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

五、訓練算法

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

具體過程包括:

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

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

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

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

3. 然后對節點序列執行skip gram以學習embedding表示;

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

   
   

2. 

3. 對每一對節點構建目標函數:

   
   

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

4. 

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

   六、數據集與實驗效果

   數據集規模:

實驗效果:

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