<DepthLGP : Learning Embeddings of Out-of-Sample Nodes in Dynamic Networks>筆記

05-07

AAAI 2018

博主的話：

第一次看有關network embedding（NE）和高斯過程的paper，很多東西都沒怎麼弄懂，若有疏漏錯誤望見諒，如果能提醒一下的話那就太好了。
目前的NE的演算法大部分都是針對靜態網路（static network），即在訓練之前所有的結點都已經在圖裡了，但如何有效得到訓練之後加入網路結點的embedding還是一個問題，尤其是如何讓新的embedding也能保存與in-sample結點相同的屬性（比如說高階鄰近）。
這篇paper主要研究的是在動態網路中，用一個帶有設計好的kernel的高階拉普拉斯高斯過程hLGP作用於out-of-sample 結點，後面再接上一個DNN，可以生成與原圖中結點有相似特徵（即在同一個特徵空間中）的embedding。
DepthLGP是Deeply Transformed High-order Laplacian Gaussian Process的簡寫。

The DepthLGP Model

Problem Definition

這篇paper關注的是無向圖， $G=(V,E)$ 是給定的圖，其中 $V={v_1,v_2,...,v_n}$ 是圖中的結點，E是邊，NE的作用就是學習一個函數 $f:V ightarrow R^d$ 得到V中結點的embedding。

而隨著網路的增大，m個新結點 $V^*={v_{n+1},...,v_{n+m}}$ 加入網路，將G擴展為 $G^{}=(V^{},E^{})$ ，其中 $V^{}=Vcup V^{*}$ ，則 $V^{*}$ 就是out-of-sample 結點，本文研究的問題就是，給定 $G^{}=(V^{},E^{})$ 和 $f(v) : vin V$ ，來infer $f(v) : vin V^{*}$

Model Description

模型共有兩個function，一個是hLGP的latent function $h:v ightarrow R^s$ ，以及基於這個latent function的DNN的embedding function $f:v ightarrow R^d$ ，更詳細一點就是 $f(v)=g(h(v))$ 其中 $g:R^s ightarrow R^d$ 就是DNN所學習的函數。

DepthLGP認為 $h(cdot)$ 的s個維度是相互獨立的（這裡我一直沒懂為啥要這樣設計，難道是為了計算簡便？有沒有大佬能解答一下），所以後文都是以h的某個維度 $h_k(cdot)$ 為對象。

每個 $h_k(cdot)$ 對應一個kernel $K_kin R^{(n+m) imes (n+m)}$ （以 $G^{}$ 為例）

$A^{}$ 是 $G^{}$ 的鄰接矩陣， $diag(cdot)$ 得到的是輸入向量的對角矩陣， $L(cdot)$ 得到的是輸入矩陣的拉普拉斯矩陣，而 $eta_kin[0,infty),zeta_kin[0,infty),a_v^{(k)}in[0,1] for v in V$ 是kernel的參數（在train的過程中learn），其中 $eta_k$ 衡量的是一階鄰近（兩個相連的結點可能相似）， $zeta_k$ 衡量的是二階鄰近（兩個有相同鄰居的結點可能相似），而 $a_v^{(k)}$ 則代表的是結點權重，換句話說就是在prediction時在結點v上設置多少attention，當v是out-of-sample時均設為1，這個設計可以幫助DepthLGP識別無效結點（比如社交網路中隨機follow用戶的機器人）。