論文研讀1

[1] B. Perozzi, R. Al-Rfou, and S. Skiena. DeepWalk: Online learning of social representations. In KDD, 2014.

[2] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. LINE: Large-scale Information Network Embedding. In WWW, 2015.

[3] Grover, Aditya, and Jure Leskovec. “node2vec: Scalable feature learning for networks.” Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016.

[1]

1.問題的引入

文章的初衷，普通 的機器學習方法适合于小規模樣本的訓練，對于規模巨大的樣本集來說，并不意味着性能一定同步上升。考慮到在機率圖模型中，我們可以根據網絡圖中蘊含的結構獨立性質，化簡聯合機率。這給了我們靈感：對于規模巨大的樣本，我們也可以把這些樣本映射到相應的網絡中，根據網絡中的結構性質，來化簡訓練過程，提高算法性能。這就要求，我們需要找到一種合适的節點到向量的映射政策，使得這種映射可以盡可能的捕捉到拓撲結構資訊。

2. 問題的定義

令 GL=(V,E,X,Y) 是一個帶有标簽的社會網絡。 X∈ℝ|V|×S , S 是特征空間的次元大小。Y∈ℝ|V|×||，其中  是标簽集合。

在傳統的機器學習分類場景中，哦我們的目标是學習一個分類政策。它可以将 X 映射到标簽集合中，而在本文中，我們在此基礎上，還可以充分利用 (V,E) 所确定的網絡中，樣本之間的獨立性特征，來取得更好的效果。在一般文獻中，我們把類似的分類過程叫做collective classification problem(或者叫做relational classification),處理這種問題的傳統方法是把分類問題看作是無向馬爾科夫網絡中的推理問題，使用疊代近似推理算法（如iterative classification algorithm， Gibbs Sampling , or label relaxation ）來計算給定網絡結構下的标簽後驗機率分布。

本文提出了不同的方法，來捕獲網絡中的拓撲資訊。采用無監督的方法，學習從圖結構中捕獲到的特征，這些特征與标簽的分布式獨立的。

這樣做的好處是，結構特征與标簽互相獨立，避免了錯誤的傳導，同時這種表達也可以用于該網絡下的多分類問題。

3. 核心思想

DeepWalk将NLP中的模型移植到了圖中.具體來說，如果把單詞看作是節點，那麼一個單詞的上下文相當于網絡中的neighborhoods，單詞與單詞之間的相關性相當于網絡中節點與節點的邊和邊的權重。基于單詞造成一句話，相當于在網絡中随機遊走的一條路線上的節點序列 Wvi .這種移植是合理的，原因在于在文本中，單詞出現的頻率服從幂律分布，同樣的，對于網絡中的節點而言，其出現在随機遊走序列中的頻率也是服從幂律分布的。

我們定義 Wvi 表示從節點 vi 出發的一條随機遊走路線上的節點序列。用 Wkvi 表示這個序列上的第k個點，顯然， Wk+1vi 表示的是這個随機遊走過程走到節點 vk 時候，從 vk 的neighbors中選擇的下一個節點。為了捕獲網絡的社群等拓撲性質，我們的随機遊走應當是短路徑下的遊走，即 short random walk。

語言模型中的N-gram算法：

minΦ−logPr(vi−m,⋯,vi+m∖vi|vi)

這個公式的意義是，給定一個單詞，預測它的鄰域的機率。我們希望讓這個機率最大化。通過最優化這個問題，得到合适的語言模型。

由于我們希望得到的是将節點 vi 映射為features的方法（也就是映射表格） Φ 。是以，我們對這個模型做如下修改:

minΦ−logPr(vi−m,⋯,vi+m∖vi|Φ(vi))

顯然的，在網絡中，具有相同結構的節點，會有相近的随機遊走政策，是以也會得到相近的機率。是以，上面這個最優化問題，将可以得到有效的 Φ ，它可以讓我們捕獲到節點中局部圖結構中的相似性特征。

幾點說明：算法2中的第3行隐含了公式2中條件獨立性的假設。此外，第三行的這個機率表達式，本文采用了層次softmax模型。即：

文獻[2]

1. introduction

1.文獻24的一些問題：

1，儲存的是網絡的局部資訊，全局資訊沒有儲存

2，目标函數是從NLP中移植過來的，不是對網絡量身定制，其合理性有待商榷

2. LINE模型

一階近似和二階近似：本文把直接連邊作為近似判據稱之為“一階近似”，而把共享相同鄰居作為近似判據稱之為”二階近似“。

3.邊采樣

即便有了一個優化目标，對大規模網絡做優化也是一個很有挑戰性的問題。目前比較好的方法是随機梯度下降。但是直接使用這個方法，在實際網路中是有問題的。這是因為在很多網絡中，邊的權重通常方差很大，例如對一個詞對網絡，詞對兒出現的頻率可能會從1到幾千萬。這些邊的權重将會乘進梯度公式中，導緻梯度爆炸，影響性能。為了解決這個問題，本文提出了一個精巧的邊采樣方法。我們根據邊的權重，構造與其成比例的機率，依照這個機率對邊進行采樣。将采樣的邊當做二值邊，用于模型更新。使用這種方法，優化目标仍然不變，但是邊的權重不再對梯度造成影響。

3. problem definition

Definition 2. (First-order Proximity)

The first-order proximity in a network is the local pairwise proximity between two vertices. For each pair of vertices linked by an edge (u; v), the weight on that edge, wuv, indicates the firstorder proximity between u and v. If no edge is observed between u and v, their first-order proximity is 0.

Definition 3. (Second-order Proximity)

The secondorder proximity between a pair of vertices (u; v) in a network is the similarity between their neighborhood network structures. Mathematically, let pu=(wu,1,⋯,wu,|V|) denote the first-order proximity of u with all the other vertices, then the second-order proximity between u and v is determined by the similarity between pu and pv . If no vertex is linked from/to both u and v, the second-order proximity between u and v is 0.

We investigate both first-order and second-order proximity for network embedding, which is defined as follows.

Definition 4. (Large-scale Information Network Embedding)

Given a large network G = (V; E), the problem of Large-scale Information Network Embedding aims to represent each vertex v∈V into a low-dimensional space Rd , i.e., learning a function fG:V→Rd,whered≪|V| . In the space Rd , both the first-order proximity and the second-order proximity between the vertices are preserved

4. LINE模型

4.1 LINE with First-order Proximity

for each undirected edge (i,j), we define the joint probability between vertex vi,vj as follows

p1(vi,vj)=11+exp(−uTi→.uj→)

vi→∈Rd 是結點的低次元向量表示。上面的公式定義了結點對的機率分布。另一方面，他們的經驗分布可以定義為：

p̂ 1(i,j)=ωijW

這樣，我們就可以得到一個最優化函數：

O1=distance(p̂ 1(.,.),p1(.,.))

這個距離衡量的是兩個分布的距離，是以我們可以采用KL-散度來完成：

O1=−∑(i,j)∈Eωijlogp1(vi,vj)

通過找到所有的 ui→ ，我們就找到了結點的低次元表達。

4.2 LINE with Second-order Proximity

二節相似性适用于有向圖和無向圖。它表達的是，擁有相同連接配接點的結點彼此更為相近。這些連接配接點稱之為“上下文”，擁有相近上下文的結點彼此更相近。

對于結點i，當它作為某些結點的上下文時，我們用 u′i→ ,表示,當i結點作為待研究結點時，用 ui→ 表示。這樣我們可以有如下機率分布：

p2(vj|vi)=exp(u′j→.ui→)∑|V|k=1exp(u′k→.ui→)

另一方面，他們的經驗分布可以定義為： p̂ 2(vj|vi)=ωijdi

這樣，我們就可以得到一個最優化函數：

O2=−∑(i,j)∈Eωijlogp2(vi|vj)

對于4.1節和4.2節，我們可以采取分别優化的方法，得到最終的U矩陣。也可以采用聯合優化的方法，這是本文以後的工作。

[3]

1. 問題的引入

前面的兩篇文獻中，我們可以看見這樣的結論：

結點到結點：一階相似性；這是第一篇文獻主要解決的問題

結點的鄰居：二階相似性：這是第二篇文獻主要解決的問題

除此之外，我們注意到，在上面的示意圖中，結點u和結點 s6 雖然沒有直接連邊（不符合一階相似性），他們的鄰接結點集合也不相似（不符合二節相似性），但是這兩個結點分别處在兩個社群之中，且他們都充當了hub結點（中心結點）。屬于同一個社群，這叫做homophily(同質性)，屬于同樣的結構角色，這是結構等價性的一種。現實網絡中往往是這兩種性質的混合。是以，本文希望找到更好的方法，能夠捕捉到結點的結構等價性。即，“三階相似性”

2. 核心思想

本文的核心思想，與第一篇相似，也是基于NLP中Skip-gram算法的移植。不同的是，本文對随機遊走政策做了修改。

2.1 算法核心

可以看到，算法的架構與前面的論文是相近的。需要注意的是這個 NS(u) ，是 u 的neighbors,但是對這個詞的一般了解中，我們往往認為neighbors是結點的直接鄰居。事實上，本文中的neighbors更像是context上下文。它指的是，根據采樣政策S得到的結點。是以，這裡的NS(u)與采樣政策是密切相關的。接下來，我們就來探讨兩種最基本的采樣政策：深度優先搜尋和廣度優先搜尋。本文采用的是對這兩種政策的相容方法：2階随機遊走算法。

2.2 搜尋政策研究

本小節的目的，是希望說明，BFS和DFS對同質性（homophily ）和結構等價性（structural equivalence ）的影響。由于本文的目标是希望捕獲這兩種性質。是以有必要研究兩種基本搜尋政策對這兩種性質的挖掘能力。

首先簡要說明什麼是同質性和結構等價性：

同質性：

Under the homophily hypothesis nodes that are highly interconnected and belong to similar network clusters or communities should be embedded closely together.

結構等價性：

under the structural equivalence hypothesis nodes that have similar structural roles in networks should be embedded closely together. Importantly, unlike homophily, structural equivalence does not emphasize connectivity;

BFS對結構等價性的挖掘

通過BFS得到的nerghborhoods采樣更容易感覺結構等價性。直覺上來說，為了确定結構等價，我們必須充分的刻畫待研究結點的local neighbohoods。（請注意，我們之前說過，本文的neighborhoods與我們常見的含義不同，更像是context.是以這裡用local neighborhoods來表達我們一般意義上了解的“鄰居”）

例如，基于網絡角色（橋還是中心結點等等）的結構等價可以通過觀測直接鄰居來推斷。是以，通過限制搜尋的範圍到結點附近，BFS可以實作對每一個結點鄰居的微觀視角上的刻畫。

BFS的另一個好處是，如果我們對每個結點都用一遍BFS，那麼這意味着會有很多結點重複考察多次，這有助于提高結點分布的穩定性。當然，與之對應的缺點是，給定門檻值K，我們可能隻會周遊到一小部分結點。

DFS對同質性的挖掘

DFS可以所搜到距離源節點更遠的地方。是以采樣的結點更容易反應宏觀視角，這有助于推斷基于同質性的社群結構。

2.3 node2vec

随機遊走：

有偏搜尋

之前我們令 πvx=ωvx ，現在我們在權重上增加一個控制系數，用于控制随機遊走的快慢： πvx=αpq(t,x).ωvx ,其中:

Intuitively, parameters p and q control how fast the walk explores and leaves the neighborhood of starting node u. In particular, the parameters allow our search procedure to (approximately) interpolate between BFS and DFS and thereby reflect an affinity for different notions of node equivalences.

結合示意圖，我們可以看到參數p控制了立即折返的可能性，是以我們稱它為折返系數（return parameter）。當p取值很大時，這意味着随機遊走不太可能出現折返現象。反之，若p取值很小，那麼折返現象會比較明顯。這意味着随機遊走會局限在起點周圍。

參數q控制了搜尋政策，直覺上看，當q取值很大時，随機遊走更傾向于選擇距t結點較近的結點。這一過程與BFS的行為類似。反之，若q取值很小時，随機遊走更傾向于選擇距離t結點更遠的結點，這相當于DFS。從這個角度來看，參數q表達了我們搜尋的政策，是遠離(outward)源節點還是接近（inward）源節點，是以我們稱參數q為進出參數（in-out parameter）

通過剛才的分析，我們發現，本文通過設定不同的參數p,q,可以成功模拟BFS和DFS過程，進而捕獲到網絡的同質性特征和結構等價性特征。接下來我們對node2vec算法做一般性描述：

幾點說明：

什麼是alias sample?

問題：比如一個随機事件包含四種情況，每種情況發生的機率分别為： 1/2,1/3,1/12,1/12 ，問怎麼用産生符合這個機率的采樣方法。

最容易想到的方法：

産生0-1之間的一個随機數，如若落在0~ 1/2之間就是事件A，落在1/2-5/6之間就是事件B，落在5/6-11/12之間就是事件C，落在11/12-1之間就是事件D。

但是這樣的複雜度，如果用BST樹來構造上面這個的話，時間複雜度為 O(logN) ，有沒有時間複雜度更低的方法?

Alias Method

将四個事件排成4列：

按照均值1/4進行歸一化：

總面積為N，将其分割為 1×N 的長方形，原則是，每一列最多隻能出現兩個事件。

設定兩個數組:Prob和Alias.其中Prob數組存放着第i列中，事件i占的面積比例。即Prob=[2/3,1,1/3,1/3].Alias中存放着第i列中非事件i的事件标号，即Alias=[2,NULL,1,1]

産生兩個随機數，第一個為1-N之間的整數，用于選擇第i列。第二個随機數為0-1之間，判斷其與Prob[i]的大小，如果比Prob[i]小，則采樣i，否則采樣Alias[i]

3. 實驗

3.1 同質性和結構等價性的檢驗

當我們設定參數p=1,q=0.5時候，圖如top。可以看到相同顔色的結點聚在一起，此時相同顔色表達的是同一個社群的概念homophily 。

當我們設定參數p=1,q=2時候，圖如button。可以看到此時相同顔色表達的是同一個結構功能即結構等價性的概念 。

3.2 多标簽分類

對比算法：

1. Spectral clustering

   This is a matrix factorization approach in which we take the top d eigenvectors of the normalized Laplacian matrix of graph G as the feature vector representations for nodes.

2. DeepWalk

   This approach learns d-dimensional feature representations by simulating uniform random walks. The sampling strategy in DeepWalk can be seen as a special case of node2vec with p = 1 and q = 1.

3. LINE

   This approach learns d-dimensional feature representations in two separate phases. In the first phase, it learns d=2 dimensions by BFS-style simulations over immediate neighbors of nodes. In the second phase, it learns the next d=2 dimensions by sampling nodes strictly at a 2-hop distance from the source nodes。

資料集：BlogCatalog, Protein-Protein Interactions, Wikipedia

分類政策：邏輯斯蒂回歸

分類效果：

說明：

什麼是Macro/Micro-F1 score?

TP：正例判為正例

FP: 負例判為正例

FN: 正例判為負例

TN: 負例判為負例

準确率： P=TPTP+FP ，”你猜的正例中有幾個是對的？”

召回率： R=TPTP+FN ，“正例中，你猜對幾個？”

F1=2PRP+R

我們現在将資料集分成N組:

Micro-準确率:

Micro−P=∑TPi∑(TPi+FPi)

Micro-召回率：

Micro−R=∑TPi∑(TPi+FNi)

Micro-F1 score:

Micro−F1=2Micro−P.Micro−RMicro−P+Micro−R

Macro-準确率：

Macro−P=∑PiN

Macro-召回率：

Macro−R=∑RiN

Macro-F1 score:

Macro−F1=2Macro−P.Micro−RMacro−P+Micro−R

3.3 鍊路預測