Learning Graph Representations with Embedding Propagation 閱讀筆記

05-02

轉載請註明出處：

每周一篇機器學習論文筆記?

zhuanlan.zhihu.com

論文來源：NIPS 2017

論文鏈接：Learning Graph Representations with Embedding Propagation

論文原作者：Alberto García-Durán, Mathias Niepert

（侵刪）

Abstract

這篇論文提出了一種基於節點屬性傳播的網路學習方法框架（EP）。EP通過在節點與節點的鄰居之間傳播兩種信息來學習出網路節點的向量表達，兩種信息分別是：(1).前向信息：由節點的屬性的向量表達組成；(2).反向信息：由誤差的梯度組成。最後，節點的向量表達由它們的屬性向量表達拼接而成。

Introduction

網路表示學習演算法最早的是對矩陣進行操作，比如說譜分解[1]和LLE演算法[2]等等，它們都是需要首先構建一個圖的連接矩陣（可以是鄰接矩陣，也可以是相似度矩陣），之後再對矩陣進行操作從而將網路映射到一個低維度的空間上。這些方法的優化通常都需要通過閉式解形式解出，因此顯然，當應用到大規模圖中，這些方法就不再適用了。

而最近比較火的網路表示學習演算法主要有DeepWalk，node2vec,以及Line等等，這些演算法更多的也是從網路結構上去考慮，比如一階相似性，二階相似性等等，然後來得到節點的向量表達。然而，真實世界中，圖更多是一個「多模態」的數據，即節點是具有很多屬性的，可以是id；可以是關鍵性的單詞描述類的文本型數據；可以是離散型的流派所屬；也可以是連續型的特徵值。很多時候，學習網路時，會更加關注於網路本身的結構特徵，節點的屬性信息就會被忽略，所以這篇文章提出的一個無監督框架-EP，更多的是針對節點的屬性信息來得到節點的向量表達。

它的核心思想很簡單，個人認為是由標籤傳播演算法[3]以及LLE演算法得到的啟發：首先將節點 $v$ 的鄰居節點的屬性向量表達結合起來，重建出節點 $v$ 的屬性向量表達；接著，將節點 $v$ 本身的屬性向量與重建出來的屬性向量的差值的梯度，反向傳播給它的鄰居，來更新鄰居的屬性向量，不斷迭代，直至收斂（或迭代一定次數）。

由於這篇論文提出的是一種框架思想，所以論文寫作上，公式的推導並不多。

Model

簡單的符號定義：

$G=(V,E)$ , 其中 $V$ 是節點集合， $E$ 是邊的集合；
$N(v)$ ：如果 $G$ 是無向圖，則它表示節點 $v$ 的鄰居；如果 $G$ 是有向圖，則它表示節點 $v$ 的「入鄰居」；
$L={L_1,...,L_k}$ 指的是屬性種類的集合，每個節點可能有多種屬性，比如說單詞，電影流派，連續值特徵等等。論文中給出了一個引用網路的例子：引用網路中的節點屬性有兩種，一種是唯一的文章id，另一種是和文章相關的關鍵詞的文本屬性；
$l_i(v)$ 指的是節點 $v$ 的第 $i$ 類屬性的集合， $l_i(N(v))$ 則是節點 $v$ 的鄰居節點第 $i$ 類屬性的集合；
$Psi={f_i(psi)}$ 是指將節點的第i種屬性的每一個值 $psi$ 都轉成向量形式表示的集合，對於不同種類的屬性， $f_i$ 是不同的，比如可以用word2vec模型來處理文本單詞類型的屬性，可以用複雜的卷積網路來處理圖像類型的屬性；
$d_i$ ：表示節點第i類屬性的向量維度；

整個EP的學習框架可以分為兩步：

1.學習出每一個節點的每一種屬性向量。

令 $h_i(v)=g_i({Psi | psiin l_i(v) })$ 表示節點 $v$ 關於 $i$ 屬性類型的向量表示， $ilde{h}_i(v)= ilde{g}_i({Psi | psiin l_i(N(v)) })$ 表示節點 $v$ 關於 $i$ 屬性類型的重建出來的向量表示（由鄰居的 $i$ 屬性向量計算得到），其中 $g_i$ 和 $ilde{g}_i$ 是能夠將多個 $d_i$ 維度向量映射成一個 $d_i$ 維度向量的可維函數。 $g_i$ 和 $ilde{g}_i$ 這兩個函數，可以被參數化（比如用神經網路），也可以用簡單的函數（比如求平均值或者求最大值）。

這樣一來，針對屬性 $i$ 的目標函數就是要使由鄰居節點傳播消息重構得到的屬性向量表示儘可能與原本的屬性向量接近：

$min sum_{vin V} d_i ( ilde{h}_i(v),{h}_i(v))$

對於每一個節點，它接收到的消息是由鄰居節點的屬性向量線性組合重構而成的屬性向量，而返回給鄰居節點的，則是自身屬性向量與接收到的屬性向量的誤差梯度。這個誤差梯度隨後會更新鄰居的屬性向量表達，從而進一步更新整個網路的每一個節點的屬性向量。（文中沒有詳細說明具體如何更新）

下圖是EP框架第一步的示意圖，能夠幫助理解：

2.學習出節點的向量表示。

第二步要考慮的就是如何從節點的各種屬性的向量表示中得到節點的向量表示，即要學習這樣一個函數 $r$ ，使得 $mathbf{v}=r({Psi | psiin l(v)})$ . 可以採用的方法有簡單地將節點的各個屬性向量拼接而成，或者線性加權組合等等。

示意圖如下圖所示：

Experiments

這篇論文提出的是一個具有啟發性的框架演算法，為了能夠進行實驗對比，所以論文中提出了一個應用了框架的比較簡單的演算法EP-B。這個演算法中，兩個關鍵函數分別為：

$h_i(v)=frac{1}{ |l_i(v)|} sum_{psiin l_i(v)} Psi$

$ilde{h}_i(v)=frac{1}{ |l_i(N(v))|}sum_{u in N(v)} sum_{psiin l_i(u)} Psi$

即節點 $v$ 關於屬性 $i$ 的向量表示為每一個值的向量表達的平均值，重構的向量則是由節點 $v$ 的鄰居節點關於屬性 $i$ 的每一個值的向量的平均值。

之後為了更好地求導，誤差使用的是margin-based ranking loss:

$L_i = sum_{v in V} sum_{u in V setminus {v}} [gamma + d_i( ilde{h}_i(v), {h}_i(v)) - d_i( ilde{h}_i(v), {h}_i(u))]_+$

最後，在收斂（或是迭代終止）得到每一個節點的每一種屬性向量後，將它們拼接，成為節點的向量表示。

實驗用的數據集有BlogCatalog，PPI，POS等多分類的社交網路數據集，以及Cora，Citeseer，Pubmed等引用網路數據集。對於社交網路，每一個節點的屬性僅僅是它們的id；而對於引用網路，由於節點表示的是文章，因此節點的屬性除了節點id，還有該篇文章摘要的關鍵詞。文中提到最後是用Word2Vec的CBOW模型來對文字類屬性進行嵌入學習。

該論文的實驗比較完善，針對不同情況，做了很多對比實驗，實驗最終的效果可以翻看原文。從結果上來看，EP-B演算法整體上比對比演算法有提高，但提高幅度不大。

Conclusion

這篇論文提出的EP框架，非常具有啟發性，而它的idea，我覺得是來自於LLE演算法。LLE演算法是認為每一個節點的向量表示是由它的鄰居節點的向量線性組合而成；而EP演算法框架考慮的則是節點的屬性向量，之後再讓屬性向量形成節點向量。目前，絕大多數論文都是從網路結構上去解析網路，從而得到節點向量；然而，對於大規模網路來說，從網路連接矩陣下手是不現實的，所以需要「另闢蹊徑」來儘可能近似得出結構信息，節點鄰居關係等等，比如deepwalk的隨機遊走刻畫。而這篇論文，用到的是傳播鄰居的屬性向量，這樣一來，即利用了網路結構的一階相似性，也多考慮了節點屬性這樣的side information，可能就能夠更好地學習出網路的向量表達，因此這樣的方向，未嘗不可多嘗試。最後，個人覺得，節點最後的向量表達是由其屬性向量表達拼接而成的做法，解釋性不太夠。但總得來說，這篇論文的想法還是值得一讀的。

[1].U. Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, 2007

[2].S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323–2326, 2000.

[3].X. Zhu and Z. Ghahramani. Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, 2002