網路表示學習論文引介

05-21

網路表示學習論文引介

來自專欄 RUC智能情報站

前言：我們生活在一個信息網路無處不在的互聯世界。信息網路的一些例子包括社交網路，出版網路，萬維網和電子商務網路。網路可以用鄰接矩陣表示，然而這類表示過於稀疏和高維。網路表示學習旨在學習節點低維表示，學習到的節點表示已被證明可以用於各種網路分析任務，如鏈接預測和節點分類。本文將介紹WSDM2018中一項嵌入複雜網路的工作，以及在網路表示學習的研究中常常作為baseline的兩個演算法LINE和DeepWalk。

本文作者：谷琪，2014級本科生，來自中國人民大學信息學院社會大數據分析與智能實驗室。

備註：本文首發於知乎[RUC智能情報站]，如需轉載請告知作者並註明本專欄文章地址。

論文一 《Multi-Dimensional Network Embedding with Hierarchical Structure》WSDM2018

1.想法

受word2vec的啟發，近年提出了DeepWalk和LINE，這類可以應用於超大規模網路的嵌入演算法。而現有的大多數方法不能直接應用於結構更加複雜的網路。文章定義了一種如圖1所示的具有層次結構的多維網路，並提出了一個嵌入這類複雜網路的框架MINES。

圖1 具有層次結構的多維網路示例

2.問題定義

假設網路中總共有 $K$ 種類型的節點，並且令 $V_{i} = {{v_{1}}^{(i)}, {v_{2}}^{(i)},...,{v_{N_i}}^{(i)}}$ 為第 $i$ 種類型的節點集合，集合大小為 $N_i$ 。令 $V$ 表示所有類型節點的集合 $V=igcup_{K}^{i=1}V_i$ 。

網路中某些類別的可能呈現層次結構。換句話說，這些節點與類別相關聯。我們令 $C_{i} = {{c_{1}}^{(i)}, {c_{2}}^{(i)},...,{c_{M_i}}^{(i)}}$ 為第 $i$ 種類型節點的類別集合，集合大小為 $M_i$ 。並令 $T^{(i)}inRe^{N_i imes{M_i}}$ 為描述第 $i$ 種節點類別信息的矩陣。

兩個節點間可以通過多個關係連接，我們將每種關係視為一個維度。因此，同一類型或不同類型的節點可以連接在同一維度上。這些連接可以通過鄰接矩陣（對於相同類型的節點）和交互矩陣（對於不同類型的節點）來描述。令 $A_d^{(i)}inRe^{N_i imes{N_i}}$ 表示第 $i$ 種節點在第 $d$ 維的的鄰接矩陣，令 $H_d^{(i)}inRe^{N_i imes{N_j}}$ 表示第 $i$ 種節點和第 $j$ 種節點在第 $d$ 維的交互矩陣。

我們旨在學習網路結構中每個維度中節點的表示。令 $U_d^{(i)} = {u_{d_1}^{(i)}, u_{d_2}^{(i)},...,u_{d_{N_i}}^{(i)}}$ 表示第 $i$ 種節點在第 $d$ （ $d=(1,...,D)$ ）維度的表示，其中 $D$ 是該多維網路的維數。

基於前述的符號和定義，我們的問題可以如下的定義：

給定

K個不同的節點集合， $V_{i} = {{v_{1}}^{(i)}, {v_{2}}^{(i)},...,{v_{N_i}}^{(i)}} (i=1,...,K)$
節點間多維的關係， $A_d^{(i)}inRe^{N_i imes{N_i}} (i=1,...,K)$ 和 $H_d^{(i)}inRe^{N_i imes{N_j}} (i,j=1,...,K;i e j;d=1,...,D)$
層次信息， $T^{(i)}inRe^{N_i imes{M_i}} (i=1,...,K)$

我們旨在在每個維度 $d$ ( $d=(1,...,D)$ 學習所有節點的一組表示 $U_d^{(i)} = {u_{d_1}^{(i)}, u_{d_2}^{(i)},...,u_{d_{N_i}}^{(i)}} (i=1,...,K)$

3.模型

首先，為了獲取網路結構的多維關係，給定維度 $d$ ，一個節點的表示 $u_d$ 應包括兩個組件(1)一個組件 $u$ 用於保留跨緯度的依賴信息；以及(2)一個組件 $e_d$ 用於保留 $d$ 維度的獨立信息。因此將 $u_d$ 重寫為： $u_d=f(u,e_d)$ 。其中 $f$ 是組合依賴組件 $u$ 和獨立組件 $e_d$ 的函數。在實驗中，作者選擇了線性函數。

其次，為了獲取網路結構的層次結構，對於這些具有層次結構的節點，還需要對其類別信息（或父母節點）進行建模。類別信息實際上是由所有維度共享的，因此作者認為它應在表示的依賴組件中。進一步的，節點表示的依賴組件 $u$ 應該包含(1)一個組件 $c_u$ 表示類別信息，以及(2)一個組件 $s_u$ 表示該節點的特定信息，即 $u=g(c_u,s_u)$ 。其中 $g$ 是組合類別信息 $c_u$ 和節點特定信息 $s_u$ 的函數。在實驗中，作者選擇了線性函數。

最後，使用skip-gram模型對網路進行建模。給定維度 $d$ ，以及一個中心節點 $v$ ，我們需要預測其「上下文」。對「上下文」由 $v$ 生成的概率建模：

$p_d(N_d(v)|v)=prod_{i=1}^{K}p_d(N_d^{(i)}(v)|v)=prod_{i=1}^{K}prod_{v_j^{(i)}in N_d^{(i)}(v)}^{}p_d(v_j^{(i)}|v)$

其中 $N_d(v)=igcup_{i=1}^{K}N_d^{(i)}(v)$ 表示 $d$ 維中，與節點 $v$ 相連的第 $i$ 類節點節點集合。同時 $p(v_j^{(i)}|v)$ 使用softmax函數建模。

對於 $D$ 個維度的所有的節點 $vin V$ ，最大化 $N_d(v)$ 由 $v$ 生成的概率：

$P=prod_{d=1}^{D}P_d=prod_{d=1}^{D}prod_{vin V}^{}p_d(N_d(v)|v)$

論文二 《DeepWalk: Online Learning of Social Representations》KDD2014

1. 想法

相似的節點具有相似的表示。在DeepWalk中作者認為，在通過隨機遊走生成的遊走序列中，目標點與在一個窗口長度內的其餘點，是相似的。

2. 模型

對於每一組節點對 $(v_i,v_j)$ ， $v_j$ 由 $v_i$ 生成的條件概率使用層次softmax建模。最大化所有目標點和與之相似的點共同出現的概率。

論文三 《LINE:Large-scale Information Network Embedding》WWW2015

1. 想法

相似的節點具有相似的表示。在LINE中作者認為(1)直接相連的兩點是相似的；(2)具有類似鄰節點的兩點是相似的。

一個示例圖如圖2所示，其中節點6和節點7屬於第一種相似，節點5和節點6屬於第二種相似。

圖2 網路結構示例

2.模型

第一種相似作者稱之為一階相似，對於每一條邊 $(v_i,v_j)$ ， $v_i,v_j$ 一階相似的概率 $p_1(v_i,v_j)$ 使用sigmoid函數建模。並定義出對應的經驗概率 $ilde{p_1}(v_i,v_j)=frac{w_{ij}}{W}$ ，其中 $W$ 是所有邊的權重之和。最小化模型概率和經驗概率的距離。

第二種相似作者稱之為二階相似，對於每一條邊 $(v_i,v_j)$ ， $v_j$ 由 $v_i$ 生成的條件概率 $p_2(v_j|v_i)$ 使用softmax函數建模。並定義出對應的經驗概率 $ilde{p_2}(v_j|v_i)=frac{w_{ij}}{d_i}$ ，其中 $d_i$ 是節點 $i$ 的出度。同樣是最小化模型概率和經驗概率的距離。