HARP: Hierarchical Representation Learning for Networks 閱讀筆記

01-27

轉載請註明出處：

每周一篇機器學習論文筆記zhuanlan.zhihu.com

論文來源：AAAI 2018

論文下載：HARP: Hierarchical Representation Learning for Networks

論文作者：Haochen Chen、Bryan Perozzi、Yifan Hu、Steven Skiena

Abstract

在這篇文章中，作者提出了一種新的方法，能夠在做network embedding的時候保持網路高階的結構特徵，具體的做法是通過將原網路圖進行合併，合併為多個層次的網路圖。這個演算法應該可以說是一個通用處理框架，可以用於改進現有演算法的效果，這個在實驗中也有所展示。

Introduction

Network embedding領域在近幾年發展迅猛，出現了許多效果公認不錯的演算法，比如：DeepWalk、Node2Vec和LINE這三個演算法。不過，對於這些演算法，它們有兩個共同的問題：

1、基本都把考慮的重點放在了網路的局部結構關係（如：一階相似性和二階相似性），而忽略了距離較長的全局關係。

2、它們都是通過隨機梯度下降法對一個非凸的目標函數進行優化，這樣如果初始化不好就很容易陷入局部最優。

所以，作者提出的HARP演算法希望通過遞歸地粗粒化方式，將原網路圖的節點和邊通過合併劃分成一系列分層的結構更小的網路圖，然後再利用現有的演算法進行不斷的特徵提取，從而實現最終的network embedding特徵提取。所以，在這篇文章中，作者的contributions可以總結為以下幾點：

1. 提出新的表示學習範式

2. 改進優化過程的效果

3. 更好的embedding效果，有利於接下來的任務

Algorithm

對於給定的圖 $G=(V,E)$ ，圖表示學習的任務是找到一個映射函數 $Phi:V rightarrow R^{|V| times d}, d ll |V|$ ，在這篇文章中，作者希望找到比原圖 $G$ 更小的圖 $G_s=(V_s,E_s)$ ，其中 $|V_s| ll |V|$ 且 $|E_s| ll |E|$ ，我們得到的圖 $G_s$ 會更加有利於做embedding，原因有以下兩個：

1. 相比於原圖 $G$ , $G_s$ 的節點對之間關係更少，即 $|V_s|^2$ 表示的空間要比 $|V|^2$ 更小。

2. 圖 $G_s$ 的直徑要比圖 $G$ 小，當小到一定程度時，基於局部結構的演算法也能利用到圖的全局結構。

對於整個演算法來說，大致可以看成是以下流程：

1. 給定一個大的網路圖 $G$ 和一個映射函數 $f$ ，並使用 $theta$ 進行初始化，得到 $f:G times theta rightarrow Phi_G$

2. 化簡 $G$ 為一系列更小的圖 $G_0...G_L$

3. 學習粗粒度embedding $Phi_{G_L}=f(G_L,phi)$

4. 通過迭代地應用 $Phi_{G_i}=f(G_i,Phi_{G_{i+1}}),0le i lt L$ ,改善粗粒度embedding為 $Phi_G$

總的演算法流程如下圖：

上述演算法中，第1行是將原圖劃分為多層次的小圖，具體演算法後面會介紹；第2-3行是初始化參數 $theta$ ， $G_L$ 是劃分到最後最小的圖，直接利用現有演算法對其求embedding，第4-7行是迭代地對比較高層次的（較大的）圖和對較低層次的（較小的）圖的embedding結果進行結合延伸，作為較大圖的embedding參數輸入進行embedding，最後第8行返回原圖的embedding結果。

圖粗粒度化

作者使用一種混合圖粗粒度化的方法來維護不同規模的圖結構信息，包括邊合併和中心點合併，分別維護的是一階相似度和二階相似度。示意圖如下：

邊合併

邊合併是為了保持圖結構中的一階相似度，先選擇 $E subseteq E$ ，使得 $E$ 中的兩條邊不會連接於相同的點，然後對於 $E$ 中的每個節點對 $(u_i,v_i)$ ,合併為單一節點 $w_i$ ，並把之間的邊去掉，這樣，圖的規模就能夠大大的減小了。效果如上圖2(a)

中心點合併

在真實世界中的網路，經常符合無標度特性，也就是說，某一個中心節點往往同時連接著非常多的節點，如果按照邊合併的策略，則這種情況對圖的粗粒度化作用非常不明顯，如上圖2(b)，所以，作者同時又採用了中心點合併的方法來進行粗粒度化操作，而它也能保持圖結構中的二階相似度。中心點合併的方法也很簡單，就是把共同以中心點為鄰居的節點兩兩進行合併，如上圖2(c)

混合粗粒度化

因為演算法中用到了兩種粗粒度化操作，所以，作者使用了一個簡單的方法將它們結合起來，就是先進行中心點合併，再將合併結果進行邊合併，這樣得到一張圖 $G_i$ ，然後再用 $G_i$ 進行下一步合併，直到圖的節點小於某一個閾值為止。演算法如下圖：

Embedding Prolongation

當圖 $G_{i+1}$ 的表示被學習之後，我們可以利用學習的結果結合到上一層的圖 $G_{i}$ 的初始化中。對於圖 $G_{i+1}$ 中的任意節點 $v$ 來說， $v$ 在圖 $G_i$ 中要不就是對應節點 $v$ ，要不就是 $v$ 和另外節點合併的節點。所以，直接使用 $v$ 在 $G_{i+1}$ 中的embedding結果來初始化 $v$ 都是合理的。

Experiment

實驗部分，作者用了自己的框架來改進幾個經典演算法:DeepWalk、Node2Vec、Line，並與自身之前的演算法進行比較，分類結果都有提高，說明演算法可行。效果如圖：

尾巴

個人認為，這篇文章單從演算法的複雜度來講是比較簡單的，不過作者能夠很機智地發現現有演算法忽略了網路全局結構的問題並很有新意地提出了利用將圖迭代分層合併的idea，而且效果很好，渣渣膜拜一波。

最後，大家新年快樂，沒點關注的點波關注~