導讀：我們都知道在數據結構中，圖是一種基礎且常用的結構。現實世界中許多場景可以抽象為一種圖結構，如社交網絡，交通網絡，電商網站中用戶與物品的關系等。

目前提到圖算法一般指：

• 經典數據結構與算法層面的：最小生成樹 (Prim,Kruskal,...) ，最短路 (Dijkstra,Floyed,...) ，拓撲排序，關鍵路徑等

• 概率圖模型，涉及圖的表示，推斷和學習，詳細可以參考 Koller 的書或者公開課

• 圖神經網絡，主要包括 Graph Embedding (基于隨機游走)和 Graph CNN (基于鄰居匯聚)兩部分。

這里先看下 Graph Embedding 的相關內容。

Graph Embedding 技術將圖中的節點以低維稠密向量的形式進行表達，要求在原始圖中相似 ( 不同的方法對相似的定義不同 ) 的節點其在低維表達空間也接近。得到的表達向量可以用來進行下游任務，如節點分類，鏈接預測，可視化或重構原始圖等。

01

DeepWalk

雖然 DeepWalk 是 KDD 2014的工作，但卻是我們了解 Graph Embedding 無法繞過的一個方法。

我們都知道在 NLP 任務中，word2vec 是一種常用的 word embedding 方法， word2vec 通過語料庫中的句子序列來描述詞與詞的共現關系，進而學習到詞語的向量表示。

DeepWalk 的思想類似 word2vec，使用圖中節點與節點的共現關系來學習節點的向量表示。那么關鍵的問題就是如何來描述節點與節點的共現關系，DeepWalk 給出的方法是使用隨機游走 (RandomWalk) 的方式在圖中進行節點采樣。

RandomWalk 是一種可重復訪問已訪問節點的深度優先遍歷算法。給定當前訪問起始節點，從其鄰居中隨機采樣節點作為下一個訪問節點，重復此過程，直到訪問序列長度滿足預設條件。

獲取足夠數量的節點訪問序列后，使用 skip-gram model 進行向量學習。

DeepWalk 核心代碼

DeepWalk 算法主要包括兩個步驟，第一步為隨機游走采樣節點序列，第二步為使用 skip-gram modelword2vec 學習表達向量。

• 構建同構網絡，從網絡中的每個節點開始分別進行 Random Walk 采樣，得到局部相關聯的訓練數據

• 對采樣數據進行 SkipGram 訓練，將離散的網絡節點表示成向量化，最大化節點共現，使用 Hierarchical Softmax 來做超大規模分類的分類器

Random Walk

我們可以通過并行的方式加速路徑采樣，在采用多進程進行加速時，相比于開一個進程池讓每次外層循環啟動一個進程，我們采用固定為每個進程分配指定數量的num_walks的方式，這樣可以最大限度減少進程頻繁創建與銷毀的時間開銷。

deepwalk_walk方法對應上一節偽代碼中第6行，_simulate_walks對應偽代碼中第3行開始的外層循環。最后的Parallel為多進程并行時的任務分配操作。

def deepwalk_walk(self, walk_length, start_node):walk = [start_node]while len(walk) < walk_length:cur = walk[-1]cur_nbrs = list(self.G.neighbors(cur))if len(cur_nbrs) > 0:walk.append(random.choice(cur_nbrs))else:breakreturn walkdef _simulate_walks(self, nodes, num_walks, walk_length,):walks = []for _ in range(num_walks):random.shuffle(nodes)for v in nodes: walks.append(self.deepwalk_walk(alk_length=walk_length, start_node=v))return walksresults = Parallel(n_jobs=workers, verbose=verbose, )(delayed(self._simulate_walks)(nodes, num, walk_length) for num inpartition_num(num_walks, workers))walks = list(itertools.chain(*results))

Word2vec

這里就偷個懶直接用gensim里的 Word2Vec 了。

from gensim.models import Word2Vec w2v_model = Word2Vec(walks,sg=1,hs=1)

DeepWalk 應用

這里簡單的用 DeepWalk 算法在 wiki 數據集上進行節點分類任務和可視化任務。? wiki 數據集包含 2,405 個網頁和17,981條網頁之間的鏈接關系，以及每個網頁的所屬類別。

本例中的訓練，評測和可視化的完整代碼在下面的 git 倉庫中：

https://github.com/shenweichen/GraphEmbedding

G = nx.read_edgelist('../data/wiki/Wiki_edgelist.txt',create_using=nx.DiGraph(),nodetype=None,data=[('weight',int)])model = DeepWalk(G,walk_length=10,num_walks=80,workers=1) model.train(window_size=5,iter=3) embeddings = model.get_embeddings()evaluate_embeddings(embeddings) plot_embeddings(embeddings)

分類任務結果

micro-F1 : 0.6674

macro-F1 : 0.5768

可視化結果

02

LINE

之前介紹過DeepWalk，DeepWalk使用DFS隨機游走在圖中進行節點采樣，使用word2vec在采樣的序列學習圖中節點的向量表示。

LINE也是一種基于鄰域相似假設的方法，只不過與DeepWalk使用DFS構造鄰域不同的是，LINE可以看作是一種使用BFS構造鄰域的算法。此外，LINE還可以應用在帶權圖中(DeepWalk僅能用于無權圖)。

之前還提到不同的graph embedding方法的一個主要區別是對圖中頂點之間的相似度的定義不同，所以先看一下LINE對于相似度的定義。

LINE 算法原理

1. 一種新的相似度定義

first-order proximity

1階相似度用于描述圖中成對頂點之間的局部相似度，形式化描述為若之間存在直連邊，則邊權即為兩個頂點的相似度，若不存在直連邊，則1階相似度為0。如上圖，6和7之間存在直連邊，且邊權較大，則認為兩者相似且1階相似度較高，而5和6之間不存在直連邊，則兩者間1階相似度為0。

second-order proximity

僅有1階相似度就夠了嗎？顯然不夠，如上圖，雖然5和6之間不存在直連邊，但是他們有很多相同的鄰居頂點(1,2,3,4)，這其實也可以表明5和6是相似的，而2階相似度就是用來描述這種關系的。形式化定義為，令表示頂點與所有其他頂點間的1階相似度，則與的2階相似度可以通過和的相似度表示。若與之間不存在相同的鄰居頂點，則2階相似度為0。

2. 優化目標

1st-order

對于每一條無向邊，定義頂點和之間的聯合概率為：

，為頂點的低維向量表示。（可以看作一個內積模型，計算兩個item之間的匹配程度）

同時定義經驗分布：

,?

優化目標為最小化：

是兩個分布的距離，常用的衡量兩個概率分布差異的指標為KL散度，使用KL散度并忽略常數項后有：

1st order 相似度只能用于無向圖當中。

2nd-order

這里對于每個頂點維護兩個embedding向量，一個是該頂點本身的表示向量，一個是該點作為其他頂點的上下文頂點時的表示向量。

對于有向邊，定義給定頂點條件下，產生上下文(鄰居)頂點的概率為：

，其中為上下文頂點的個數。

優化目標為：

，其中為控制節點重要性的因子，可以通過頂點的度數或者PageRank等方法估計得到。

經驗分布定義為：

，是邊的邊權，是頂點的出度，對于帶權圖，使用KL散度并設，忽略常數項，有

3. 優化技巧

Negative sampling

由于計算2階相似度時，softmax函數的分母計算需要遍歷所有頂點，這是非常低效的，論文采用了負采樣優化的技巧，目標函數變為：

，是負邊的個數。

論文使用，是頂點的出度。

Edge Sampling

注意到我們的目標函數在log之前還有一個權重系數，在使用梯度下降方法優化參數時，會直接乘在梯度上。如果圖中的邊權方差很大，則很難選擇一個合適的學習率。若使用較大的學習率那么對于較大的邊權可能會引起梯度爆炸，較小的學習率對于較小的邊權則會導致梯度過小。

對于上述問題，如果所有邊權相同，那么選擇一個合適的學習率會變得容易。這里采用了將帶權邊拆分為等權邊的一種方法，假如一個權重為的邊，則拆分后為個權重為1的邊。這樣可以解決學習率選擇的問題，但是由于邊數的增長，存儲的需求也會增加。

另一種方法則是從原始的帶權邊中進行采樣，每條邊被采樣的概率正比于原始圖中邊的權重，這樣既解決了學習率的問題，又沒有帶來過多的存儲開銷。

這里的采樣算法使用的是Alias算法，Alias是一種時間復雜度的離散事件抽樣算法。具體內容可以參考

Alias Method:時間復雜度O(1)的離散采樣方法

https://zhuanlan.zhihu.com/p/54867139

4. 其他問題

低度數頂點

對于一些頂點由于其鄰接點非常少會導致embedding向量的學習不充分，論文提到可以利用鄰居的鄰居構造樣本進行學習，這里也暴露出LINE方法僅考慮一階和二階相似性，對高階信息的利用不足。

新加入頂點

對于新加入圖的頂點，若該頂點與圖中頂點存在邊相連，我們只需要固定模型的其他參數，優化如下兩個目標之一即可：

若不存在邊相連，則需要利用一些side info，留到后續工作研究。

LINE核心代碼

1. 模型和損失函數定義

LINE使用梯度下降的方法進行優化，直接使用tensorflow進行實現，就可以不用人工寫參數更新的邏輯了~

這里的 實現中把1階和2階的方法融合到一起了，可以通過超參數order控制是分開優化還是聯合優化，論文推薦分開優化。

首先輸入就是兩個頂點的編號，然后分別拿到各自對應的embedding向量，最后輸出內積的結果。真實label定義為1或者-1，通過模型輸出的內積和line_loss就可以優化使用了負采樣技巧的目標函數了~

def line_loss(y_true, y_pred):return -K.mean(K.log(K.sigmoid(y_true*y_pred)))def create_model(numNodes, embedding_size, order='second'):v_i = Input(shape=(1,))v_j = Input(shape=(1,))first_emb = Embedding(numNodes, embedding_size, name='first_emb')second_emb = Embedding(numNodes, embedding_size, name='second_emb')context_emb = Embedding(numNodes, embedding_size, name='context_emb')v_i_emb = first_emb(v_i)v_j_emb = first_emb(v_j)v_i_emb_second = second_emb(v_i)v_j_context_emb = context_emb(v_j)first = Lambda(lambda x: tf.reduce_sum(x[0]*x[1], axis=-1, keep_dims=False), name='first_order')([v_i_emb, v_j_emb])second = Lambda(lambda x: tf.reduce_sum(x[0]*x[1], axis=-1, keep_dims=False), name='second_order')([v_i_emb_second, v_j_context_emb])if order == 'first':output_list = [first]elif order == 'second':output_list = [second]else:output_list = [first, second]model = Model(inputs=[v_i, v_j], outputs=output_list)

2. 頂點負采樣和邊采樣

下面的函數功能是創建頂點負采樣和邊采樣需要的采樣表。中規中矩，主要就是做一些預處理，然后創建alias算法需要的兩個表。

def _gen_sampling_table(self):# create sampling table for vertexpower = 0.75numNodes = self.node_sizenode_degree = np.zeros(numNodes) ?# out degreenode2idx = self.node2idxfor edge in self.graph.edges():node_degree[node2idx[edge[0]]] += self.graph[edge[0]][edge[1]].get('weight', 1.0)total_sum = sum([math.pow(node_degree[i], power)for i in range(numNodes)])norm_prob = [float(math.pow(node_degree[j], power)) /total_sum for j in range(numNodes)]self.node_accept, self.node_alias = create_alias_table(norm_prob)# create sampling table for edgenumEdges = self.graph.number_of_edges()total_sum = sum([self.graph[edge[0]][edge[1]].get('weight', 1.0)for edge in self.graph.edges()])norm_prob = [self.graph[edge[0]][edge[1]].get('weight', 1.0) *numEdges / total_sum for edge in self.graph.edges()]self.edge_accept, self.edge_alias = create_alias_table(norm_prob)

LINE 應用

和之前一樣，還是用LINE在wiki數據集上進行節點分類任務和可視化任務。wiki數據集包含 2,405 個網頁和17,981條網頁之間的鏈接關系，以及每個網頁的所屬類別。由于1階相似度僅能應用于無向圖中，所以本例中僅使用2階相似度。

本例中的訓練，評測和可視化的完整代碼在下面的git倉庫中，

https://github.com/shenweichen/GraphEmbedding

G = nx.read_edgelist('../data/wiki/Wiki_edgelist.txt',create_using=nx.DiGraph(),nodetype=None,data=[('weight',int)])model = LINE(G,embedding_size=128,order='second') model.train(batch_size=1024,epochs=50,verbose=2) embeddings = model.get_embeddings()evaluate_embeddings(embeddings) plot_embeddings(embeddings)

分類任務結果

micro-F1: 0.6403

macro-F1:0.5286

結果有一定隨機性，可以多運行幾次，或者稍微調整epoch個數。

可視化結果

03

nodo2vec

前面介紹過基于DFS鄰域的DeepWalk和基于BFS鄰域的LINE。

node2vec是一種綜合考慮DFS鄰域和BFS鄰域的graph embedding方法。簡單來說，可以看作是deepwalk的一種擴展，是結合了DFS和BFS隨機游走的deepwalk。

nodo2vec 算法原理

1. 優化目標

設?是將頂點?映射為embedding向量的映射函數,對于圖中每個頂點，定義?為通過采樣策略采樣出的頂點?的近鄰頂點集合。

node2vec優化的目標是給定每個頂點條件下，令其近鄰頂點（如何定義近鄰頂點很重要）出現的概率最大。

為了將上述最優化問題可解，文章提出兩個假設：

• 條件獨立性假設

假設給定源頂點下，其近鄰頂點出現的概率與近鄰集合中其余頂點無關。

• 特征空間對稱性假設

這里是說一個頂點作為源頂點和作為近鄰頂點的時候共享同一套embedding向量。(對比LINE中的2階相似度，一個頂點作為源點和近鄰點的時候是擁有不同的embedding向量的) 在這個假設下，上述條件概率公式可表示為：

根據以上兩個假設條件，最終的目標函數表示為：

由于歸一化因子：

的計算代價高，所以采用負采樣技術優化。

2. 頂點序列采樣策略

node2vec依然采用隨機游走的方式獲取頂點的近鄰序列，不同的是node2vec采用的是一種有偏的隨機游走。

給定當前頂點?，訪問下一個頂點的概率為：

是頂點?和頂點之間的未歸一化轉移概率，?是歸一化常數。

node2vec引入兩個超參數?和來控制隨機游走的策略，假設當前隨機游走經過邊?到達頂點?設，是頂點?和之間的邊權，

為頂點和頂點之間的最短路徑距離。

下面討論超參數p和 q對游走策略的影響

• Return parameter,p

參數p控制重復訪問剛剛訪問過的頂點的概率。注意到p僅作用于的情況，而?表示頂點x就是訪問當前頂點?之前剛剛訪問過的頂點。那么若 p較高，則訪問剛剛訪問過的頂點的概率會變低，反之變高。

• In-out papameter,q

q控制著游走是向外還是向內，若，隨機游走傾向于訪問和t接近的頂點(偏向BFS)。若，傾向于訪問遠離t的頂點(偏向DFS)。

下面的圖描述的是當從t訪問到時，決定下一個訪問頂點時每個頂點對應的。

3. 學習算法

采樣完頂點序列后，剩下的步驟就和deepwalk一樣了，用word2vec去學習頂點的embedding向量。值得注意的是node2vecWalk中不再是隨機抽取鄰接點，而是按概率抽取，node2vec采用了Alias算法進行頂點采樣。

Alias Method:時間復雜度O(1)的離散采樣方法

https://zhuanlan.zhihu.com/p/54867139

node2vec 核心代碼

1. node2vecWalk

通過上面的偽代碼可以看到，node2vec和deepwalk非常類似，主要區別在于頂點序列的采樣策略不同，所以這里我們主要關注node2vecWalk的實現。

由于采樣時需要考慮前面2步訪問過的頂點，所以當訪問序列中只有1個頂點時，直接使用當前頂點和鄰居頂點之間的邊權作為采樣依據。當序列多余2個頂點時，使用文章提到的有偏采樣。

def node2vec_walk(self, walk_length, start_node):G = self.G ? ?alias_nodes = self.alias_nodes ? ?alias_edges = self.alias_edgeswalk = [start_node]while len(walk) < walk_length: ? ? ? ?cur = walk[-1] ? ? ? ?cur_nbrs = list(G.neighbors(cur)) ? ? ? ?if len(cur_nbrs) > 0: ? ? ? ? ? ?if len(walk) == 1: ? ? ? ? ? ? ? ?walk.append(cur_nbrs[alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])]) ? ? ? ? ? ?else: ? ? ? ? ? ? ? ?prev = walk[-2] ? ? ? ? ? ? ? ?edge = (prev, cur) ? ? ? ? ? ? ? ?next_node = cur_nbrs[alias_sample(alias_edges[edge][0],alias_edges[edge][1])] ? ? ? ? ? ? ? ?walk.append(next_node) ? ? ? ?else: ? ? ? ? ? ?breakreturn walk

2. 構造采樣表

preprocess_transition_probs分別生成alias_nodes和alias_edges，alias_nodes存儲著在每個頂點時決定下一次訪問其鄰接點時需要的alias表（不考慮當前頂點之前訪問的頂點）。alias_edges存儲著在前一個訪問頂點為t，當前頂點為?時決定下一次訪問哪個鄰接點時需要的alias表。

get_alias_edge方法返回的是在上一次訪問頂點 t，當前訪問頂點為時到下一個頂點的未歸一化轉移概率:

def get_alias_edge(self, t, v):G = self.G ? ?p = self.p ? ?q = self.qunnormalized_probs = [] ? ?for x in G.neighbors(v): ? ? ? ?weight = G[v][x].get('weight', 1.0)# w_vx ? ? ? ?if x == t:# d_tx == 0 ? ? ? ? ? ?unnormalized_probs.append(weight/p) ? ? ? ?elif G.has_edge(x, t):# d_tx == 1 ? ? ? ? ? ?unnormalized_probs.append(weight) ? ? ? ?else:# d_tx == 2 ? ? ? ? ? ?unnormalized_probs.append(weight/q) ? ?norm_const = sum(unnormalized_probs) ? ?normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs]return create_alias_table(normalized_probs)def preprocess_transition_probs(self):G = self.Galias_nodes = {} ? ?for node in G.nodes(): ? ? ? ?unnormalized_probs = [G[node][nbr].get('weight', 1.0) for nbr in G.neighbors(node)] ? ? ? ?norm_const = sum(unnormalized_probs) ? ? ? ?normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs] ? ? ? ? ? ? ? ?alias_nodes[node] = create_alias_table(normalized_probs)alias_edges = {}for edge in G.edges(): ? ? ? ?alias_edges[edge] = self.get_alias_edge(edge[0], edge[1])self.alias_nodes = alias_nodes ? ?self.alias_edges = alias_edgesreturn

node2vec 應用

使用node2vec在wiki數據集上進行節點分類任務和可視化任務。wiki數據集包含 2,405 個網頁和17,981條網頁之間的鏈接關系，以及每個網頁的所屬類別。通過簡單的超參搜索，這里使用p=0.25,q=4的設置。

本例中的訓練，評測和可視化的完整代碼在下面的git倉庫中：

https://github.com/shenweichen/GraphEmbedding

G = nx.read_edgelist('../data/wiki/Wiki_edgelist.txt',create_using=nx.DiGraph(),nodetype=None,data=[('weight',int)])model = Node2Vec(G,walk_length=10,num_walks=80,p=0.25,q=4,workers=1) model.train(window_size=5,iter=3) ? ? embeddings = model.get_embeddings()evaluate_embeddings(embeddings) plot_embeddings(embeddings)

分類任務

micro-F1: 0.6757 macro-F1: 0.5917

這個結果相比于DeepWalk和LINE是有提升的。

可視化

這個結果相比于DeepWalk和LINE可以看到不同類別的分布更加分散了。

最后補充一個node2vec在業界的應用介紹

當機器學習遇上復雜網絡：解析微信朋友圈 Lookalike 算法

04

SDNE

SDNE（Structural Deep Network Embedding ）是和node2vec并列的工作，均發表在2016年的KDD會議中。可以看作是基于LINE的擴展，同時也是第一個將深度學習應用于網絡表示學習中的方法。

SDNE使用一個自動編碼器結構來同時優化1階和2階相似度(LINE是分別優化的)，學習得到的向量表示能夠保留局部和全局結構，并且對稀疏網絡具有魯棒性。

SDNE 算法原理

相似度定義

SDNE中的相似度定義和LINE是一樣的。簡單來說，1階相似度衡量的是相鄰的兩個頂點對之間相似性。2階相似度衡量的是，兩個頂點他們的鄰居集合的相似程度。

2階相似度優化目標

這里我們使用圖的鄰接矩陣進行輸入，對于第個頂點，有，每一個都包含了頂點i的鄰居結構信息，所以這樣的重構過程能夠使得結構相似的頂點具有相似的embedding表示向量。

這里存在的一個問題是由于圖的稀疏性，鄰接矩陣S中的非零元素是遠遠少于零元素的，那么對于神經網絡來說只要全部輸出0也能取得一個不錯的效果，這不是我們想要的。

文章給出的一個方法是使用帶權損失函數，對于非零元素具有更高的懲罰系數。修正后的損失函數為

其中為逐元素積，，若，則，否則

1階相似度優化目標

對于1階相似度，損失函數定義如下

該損失函數可以讓圖中的相鄰的兩個頂點對應的embedding vector在隱藏空間接近。

還可以表示為

其中L是圖對應的拉普拉斯矩陣，，D是圖中頂點的度矩陣，S是鄰接矩陣，?。

整體優化目標

聯合優化的損失函數為

是正則化項，為控制1階損失的參數，為控制正則化項的參數。

模型結構

? ??

先看左邊，是一個自動編碼器的結構，輸入輸出分別是鄰接矩陣和重構后的鄰接矩陣。通過優化重構損失可以保留頂點的全局結構特性(論文的圖畫錯了，上面應該是Global structure preserved cost)。

再看中間一排，就是我們需要的embedding向量，模型通過1階損失函數使得鄰接的頂點對應的embedding向量接近，從而保留頂點的局部結構特性(中間應該是 Local structure preserved cost)

實現

文章提出使用深度信念網絡進行預訓練來獲得較好的參數初始化，這里我就偷個懶省略這個步驟了~

損失函數定義

l_2nd是2階相似度對應的損失函數，參數beta控制著非零元素的懲罰項系數。y_true和y_pred分別是輸入的鄰接矩陣和網絡重構出的鄰接矩陣。

l_1st是1階相似度對應的損失函數，參數alpha控制著其在整體損失函數中的占比。

def l_2nd(beta):
def loss_2nd(y_true, y_pred):
b_ = np.ones_like(y_true)
b_[y_true != 0] = beta
x = K.square((y_true - y_pred) * b_)
t = K.sum(x, axis=-1, )
return K.mean(t)
return loss_2nd

def l_1st(alpha):
def loss_1st(y_true, y_pred):
L = y_true
Y = y_pred
batch_size = tf.to_float(K.shape(L)[0])
return alpha * 2 * tf.linalg.trace(tf.matmul(tf.matmul(Y, L, transpose_a=True), Y)) / batch_size
return loss_1st

模型定義

create_model函數創建SDNE模型，l1和l2分別為模型的正則化項系數，模型的輸入A為鄰接矩陣，L為拉普拉斯矩陣。輸出A_為重構后的鄰接矩陣，Y為頂點的embedding向量。

函數中兩個for循環分別對應encoder和decoder結構。

def create_model(node_size, hidden_size=[256, 128], l1=1e-5, l2=1e-4):
A = Input(shape=(node_size,))
L = Input(shape=(None,))
fc = A
for i in range(len(hidden_size)):
if i == len(hidden_size) - 1:
fc = Dense(hidden_size[i], activation='relu',kernel_regularizer=l1_l2(l1, l2),name='1st')(fc)
else:
fc = Dense(hidden_size[i], activation='relu',kernel_regularizer=l1_l2(l1, l2))(fc)
Y = fc
for i in reversed(range(len(hidden_size) - 1)):
fc = Dense(hidden_size[i], activation='relu',kernel_regularizer=l1_l2(l1, l2))(fc)
A_ = Dense(node_size, 'relu', name='2nd')(fc)
model = Model(inputs=[A, L], outputs=[A_, Y])
return model

應用

使用SDNE在wiki數據集上進行節點分類任務和可視化任務(感興趣的同學可以試試別的數據集，我比較懶就選了個很小的數據集)。wiki數據集包含 2,405 個網頁和17,981條網頁之間的鏈接關系，以及每個網頁的所屬類別。

本例中的訓練，評測和可視化的完整代碼在下面的git倉庫中：

https://github.com/shenweichen/GraphEmbedding

分類任務

micro-F1: 0.6341 macro-F1: 0.4962

可視化

這個貌似某些類別的點的向量都聚集在一起了，可能和超參的設置還有網絡權重的初始化有關，我懶得調了~

? ? ?

這里還有一個SDNE在業界的應用的介紹：

阿里湊單算法首次公開！基于Graph Embedding的打包購商品挖掘系統解析

05

Struc2Vec

前面介紹過DeepWalk,LINE,Node2Vec,SDNE幾個graph embedding方法。這些方法都是基于近鄰相似的假設的。其中DeepWalk,Node2Vec通過隨機游走在圖中采樣頂點序列來構造頂點的近鄰集合。LINE顯式的構造鄰接點對和頂點的距離為1的近鄰集合。SDNE使用鄰接矩陣描述頂點的近鄰結構。

事實上，在一些場景中，兩個不是近鄰的頂點也可能擁有很高的相似性，對于這類相似性，上述方法是無法捕捉到的。Struc2Vec就是針對這類場景提出的。Struc2Vec的論文發表在2017年的KDD會議中。

Struc2Vec算法原理

相似度定義

Struc2Vec是從空間結構相似性的角度定義頂點相似度的。

用下面的圖簡單解釋下，如果在基于近鄰相似的模型中，頂點u和頂點v是不相似的，第一他們不直接相連，第二他們不共享任何鄰居頂點。

而在struc2vec的假設中，頂點u和頂點v是具有空間結構相似的。他們的度數分別為5和4，分別連接3個和2個三角形結構，通過2個頂點(d,e;x,w)和網絡的其他部分相連。

直觀來看，具有相同度數的頂點是結構相似的，若各自鄰接頂點仍然具有相同度數，那么他們的相似度就更高。

頂點對距離定義

令?表示到頂點u距離為k的頂點集合，則?表示是u的直接相連近鄰集合。

令?表示頂點集合S的有序度序列。

通過比較兩個頂點之間距離為k的環路上的有序度序列可以推出一種層次化衡量結構相似度的方法。

令表示頂點u和v之間距離為k（這里的距離k實際上是指距離小于等于k的節點集合）的環路上的結構距離(注意是距離，不是相似度)。

其中是衡量有序度序列和的距離的函數，并且.

下面就是如何定義有序度序列之間的比較函數了，由于和的長度不同，并且可能含有重復元素。所以文章采用了Dynamic Time Warping(DTW)來衡量兩個有序度序列。

一句話，DTW可以用來衡量兩個不同長度且含有重復元素的的序列的距離（距離的定義可以自己設置）。

基于DTW，定義元素之間的距離函數

至于為什么使用這樣的距離函數，這個距離函數實際上懲罰了當兩個頂點的度數都比較小的時候兩者的差異。舉例來說，情況下的距離為1，情況下的距離差異為0.0099。這個特性正是我們想要的。

構建層次帶權圖

根據上一節的距離定義，對于每一個我們都可以計算出兩個頂點之間的一個距離，現在要做的是通過上一節得到的頂點之間的有序度序列距離來構建一個層次化的帶權圖（用于后續的隨機游走）。

我們定義在某一層k中兩個頂點的邊權為

這樣定義的邊權都是小于1的，當且僅當距離為0的是時候，邊權為1。

通過有向邊將屬于不同層次的同一頂點連接起來，具體來說，對每個頂點，都會和其對應的上層頂點還有下層頂點相連。邊權定義為

其中是第k層與u相連的邊的邊權大于平均邊權的邊的數量。

，就是第k層所有邊權的平均值。

采樣獲取頂點序列

使用有偏隨機游走在構造出的圖中進行頂點序列采樣。每次采樣時，首先決定是在當前層游走，還是切換到上下層的層游走。

若決定在當前層游走，設當前處于第k層，則從頂點u到頂點v的概率為：

其中是第k層中關于頂點u的歸一化因子。

通過在圖M中進行隨機游走，每次采樣的頂點更傾向于選擇與當前頂點結構相似的頂點。因此，采樣生成的上下文頂點很可能是結構相似的頂點，這與頂點在圖中的位置無關。

若決定切換不同的層，則以如下的概率選擇?層或層，

三個時空復雜度優化技巧：

• OPT1 有序度序列長度優化

前面提到過對于每個頂點在每一層都有一個有序度序列，而每一個度序列的空間復雜度為O(n)。

文章提出一種壓縮表示方法，對于序列中出現的每一個度，計算該度在序列里出現的次數。壓縮后的有序度序列存儲的是(度數，出現次數)這樣的二元組。

同時修改距離函數為：

為度數，?為度的出現次數。

• OPT2 相似度計算優化

在原始的方法中，我們需要計算每一層k中，任意兩個頂點之間的相似度。事實上，這是不必要的。因為兩個度數相差很大的頂點，即使在的時候他們的距離也已經非常大了，那么在隨機游走時這樣的邊就幾乎不可能被采樣到，所以我們也沒必要計算這兩個頂點之間的距離。

文章給出的方法是在計算頂點u和其他頂點之間的距離時，只計算那些與頂點u的度數接近的頂點的距離。具體來說，在頂點u對應的有序度序列中進行二分查找，查找的過程就是不斷逼近頂點u的度數的過程，只計算查找路徑上的頂點與u的距離。這樣每一次需要計算的邊的數量從數量級縮減到。

• OPT3 限制層次帶權圖層數

層次帶權圖M中的層數是由圖的直徑決定的。但是對很多圖來說，圖的直徑會遠遠大于頂點之間的平均距離。

當k接近?時，環上的度序列長度也會變得很短，??和會變得接近。

因此將圖中的層數限制為，使用最重要的一些層來評估結構相似度。

這樣的限制顯著降低構造M時的計算和存儲開銷。

Struc2Vec 核心代碼

Struc2Vec的實現相比于前面的幾個算法稍微復雜一些，這里我主要說下大體思路，對一些細節有疑問的同學可以郵件或者私信我~

根據前面的算法原理介紹，首先確定一下我們要做哪些事情 1. 獲取每一層的頂點對距離 2. 根據頂點對距離構建帶權層次圖 3. 在帶權層次圖中隨機游走采樣頂點序列

頂點對距離計算

每一層的頂點對距離計算涉及到4個函數，我們一個一個看。。。

首先看第一個函數_get_order_degreelist_node，這個函數的作用是計算頂點root對應的有序度序列，也就是前面提到的。

這里我們采用層序遍歷的方式從root開始進行遍歷，遍歷的過程計算當前訪問的層次level，就是對應文章中的。每次進行節點訪問時只做一件事情，就是記錄該頂點的度數。當level增加時，將當前level中的度序列(如果使用優化技巧就是壓縮度序列)排序，得到有序度序列。函數的返回值是一個字典，該字典存儲著root在每一層對應的有序度序列。

第2個函數_compute_ordered_degreelist函數就很簡單了，用一個循環去計算每個頂點對應的有序度序列。

def _get_order_degreelist_node(self, root, max_num_layers=None):if max_num_layers is None:max_num_layers = float('inf')ordered_degree_sequence_dict = {}visited = [False] * len(self.graph.nodes())queue = deque()level = 0queue.append(root)visited[root] = Truewhile (len(queue) > 0 and level <= max_num_layers):count = len(queue)if self.opt1_reduce_len:degree_list = {}else:degree_list = []while (count > 0):top = queue.popleft()node = self.idx2node[top]degree = len(self.graph[node])if self.opt1_reduce_len:degree_list[degree] = degree_list.get(degree, 0) + 1else:degree_list.append(degree)for nei in self.graph[node]:nei_idx = self.node2idx[nei]if not visited[nei_idx]:visited[nei_idx] = Truequeue.append(nei_idx)count -= 1if self.opt1_reduce_len:orderd_degree_list = [(degree, freq)for degree, freq in degree_list.items()]orderd_degree_list.sort(key=lambda x: x[0])else:orderd_degree_list = sorted(degree_list)ordered_degree_sequence_dict[level] = orderd_degree_listlevel += 1return ordered_degree_sequence_dictdef _compute_ordered_degreelist(self, max_num_layers):degreeList = {}vertices = self.idx # self.g.nodes()for v in vertices:degreeList[v] = self._get_order_degreelist_node(v, max_num_layers)return degreeList

有了所有頂點對應的后，我們要做的就是計算頂點對之間的距離?， 然后再利用公式?

得到頂點對之間的結構距離?

這里先看第3個函數compute_dtw_dist,該函數實現的功能是計算頂點對之間的距離?，參數degreeList就是前面一步我們得到的存儲每個頂點在每一層的有序度序列的字典。

第4個函數convert_dtw_struc_dist的功能是根據compute_dtw_dist得到的頂點對距離完成關于?的迭代計算。

最后說明一下根據我們是否使用優化技巧self.opt2_reduce_sim_calc函數會選擇計算所有頂點對間的距離，還是只計算度數接近的頂點對之間的距離。

def compute_dtw_dist(part_list, degreeList, dist_func):dtw_dist = {}for v1, nbs in part_list:lists_v1 = degreeList[v1] # lists_v1 :orderd degree list of v1for v2 in nbs:lists_v2 = degreeList[v2] # lists_v1 :orderd degree list of v2max_layer = min(len(lists_v1), len(lists_v2)) # valid layerdtw_dist[v1, v2] = {}for layer in range(0, max_layer):dist, path = fastdtw(lists_v1[layer], lists_v2[layer], radius=1, dist=dist_func)dtw_dist[v1, v2][layer] = distreturn dtw_distdef _compute_structural_distance(self, max_num_layers, workers=1, verbose=0,):if os.path.exists(self.temp_path+'structural_dist.pkl'):structural_dist = pd.read_pickle(self.temp_path+'structural_dist.pkl')else:if self.opt1_reduce_len:dist_func = cost_maxelse:dist_func = costif os.path.exists(self.temp_path + 'degreelist.pkl'):degreeList = pd.read_pickle(self.temp_path + 'degreelist.pkl')else:degreeList = self._compute_ordered_degreelist(max_num_layers)pd.to_pickle(degreeList, self.temp_path + 'degreelist.pkl')if self.opt2_reduce_sim_calc:degrees = self._create_vectors()degreeListsSelected = {}vertices = {}n_nodes = len(self.idx)for v in self.idx: # c:list of vertexnbs = get_vertices(v, len(self.graph[self.idx2node[v]]), degrees, n_nodes)vertices[v] = nbs # store nbsdegreeListsSelected[v] = degreeList[v] # store distfor n in nbs:# store dist of nbsdegreeListsSelected[n] = degreeList[n]else:vertices = {}for v in degreeList:vertices[v] = [vd for vd in degreeList.keys() if vd > v]results = Parallel(n_jobs=workers, verbose=verbose,)(delayed(compute_dtw_dist)(part_list, degreeList, dist_func) for part_list in partition_dict(vertices, workers))dtw_dist = dict(ChainMap(*results))structural_dist = convert_dtw_struc_dist(dtw_dist)pd.to_pickle(structural_dist, self.temp_path +'structural_dist.pkl')return structural_dist

構建帶權層次圖

構建帶權層次圖的一個主要操作就是根據前面計算得到的每一層中頂點之間的結構化距離來計算同一層中頂點之間和同一頂點在不同層之間的轉移概率，通過函數_get_transition_probs實現。

layers_adj存儲著每一層中每個頂點的鄰接點，layers_distances存儲著每一層每個頂點對的結構化距離。_get_transition_probs只做了一件事情，就是逐層的計算頂點之間的邊權，并生成后續采樣需要的alias表。

def _get_transition_probs(self, layers_adj, layers_distances):layers_alias = {}layers_accept = {}for layer in layers_adj:neighbors = layers_adj[layer]layer_distances = layers_distances[layer]node_alias_dict = {}node_accept_dict = {}norm_weights = {}for v, neighbors in neighbors.items():e_list = []sum_w = 0.0for n in neighbors:if (v, n) in layer_distances:wd = layer_distances[v, n]else:wd = layer_distances[n, v]w = np.exp(-float(wd))e_list.append(w)sum_w += we_list = [x / sum_w for x in e_list]norm_weights[v] = e_listaccept, alias = create_alias_table(e_list)node_alias_dict[v] = aliasnode_accept_dict[v] = acceptpd.to_pickle(norm_weights, self.temp_path + 'norm_weights_distance-layer-' + str(layer)+'.pkl')layers_alias[layer] = node_alias_dictlayers_accept[layer] = node_accept_dictreturn layers_accept, layers_alias

前面的部分僅僅得到了在同一層內，頂點之間的轉移概率，那么同一個頂點在不同層之間的轉移概率如何得到呢？

下面的prepare_biased_walk就是計算當隨機游走需要跨層時，決定向上還是向下所用到的。

def prepare_biased_walk(self,):sum_weights = {}sum_edges = {}average_weight = {}gamma = {}layer = 0while (os.path.exists(self.temp_path+'norm_weights_distance-layer-' + str(layer))):probs = pd.read_pickle(self.temp_path+'norm_weights_distance-layer-' + str(layer))for v, list_weights in probs.items():sum_weights.setdefault(layer, 0)sum_edges.setdefault(layer, 0)sum_weights[layer] += sum(list_weights)sum_edges[layer] += len(list_weights)average_weight[layer] = sum_weights[layer] / sum_edges[layer]gamma.setdefault(layer, {})for v, list_weights in probs.items():num_neighbours = 0for w in list_weights:if (w > average_weight[layer]):num_neighbours += 1gamma[layer][v] = num_neighbourslayer += 1pd.to_pickle(average_weight, self.temp_path + 'average_weight')pd.to_pickle(gamma, self.temp_path + 'gamma.pkl')

隨機游走采樣

采樣的主體框架和前面的DeepWalk,Node2Vec差不多，這里就說下不同的地方。由于Struc2Vec是在一個多層圖中進行采樣，游走可能發生在同一層中，也可能發生跨層，所以要添加一些跨層處理的邏輯。

def _exec_random_walk(self, graphs, layers_accept,layers_alias, v, walk_length, gamma, stay_prob=0.3):initialLayer = 0layer = initialLayerpath = []path.append(self.idx2node[v])while len(path) < walk_length:r = random.random()if(r < stay_prob): # same layerv = chooseNeighbor(v, graphs, layers_alias,layers_accept, layer)path.append(self.idx2node[v])else: # different layerr = random.random()try:x = math.log(gamma[layer][v] + math.e)p_moveup = (x / (x + 1))except:print(layer, v)raise ValueError()if(r > p_moveup):if(layer > initialLayer):layer = layer - 1else:if((layer + 1) in graphs and v in graphs[layer + 1]):layer = layer + 1return path

Struc2Vec 應用

Struc2Vec應用于無權無向圖(帶權圖的權重不會用到，有向圖會當成無向圖處理)，主要關注的是圖中頂點的空間結構相似性，這里我們采用論文中使用的一個數據集。該數據集是一個機場流量的數據集，頂點表示機場，邊表示兩個機場之間存在航班。機場會被打上活躍等級的標簽。

這里我們用基于空間結構相似的Struc2Vec和基于近鄰相似的Node2Vec做一個對比實驗。

本例中的訓練，評測和可視化的完整代碼在下面的git倉庫中，

https://github.com/shenweichen/GraphEmbedding

分類

• Struc2Vec結果 micro-F1: 0.7143, macro-F1: 0.7357

• Node2Vec結果 micro-F1: 0.3571, macro-F1: 0.3445

差距還是蠻大的，說明Struc2Vec確實能夠更好的捕獲空間結構性。

可視化

• Struc2Vec結果

• Node2Vec結果

參考資料：

1. Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014: 701-710.

http://www.perozzi.net/publications/14_kdd_deepwalk.pdf

2. Graph Neural Network Review

https://zhuanlan.zhihu.com/p/43972372

3. Tang J, Qu M, Wang M, et al. Line: Large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 2015: 1067-1077.

4. Grover A, Leskovec J. node2vec: Scalable Feature Learning for Networks[C]// Acm Sigkdd International Conference on Knowledge Discovery & Data Mining. 2016.

https://www.kdd.org/kdd2016/papers/files/rfp0218-groverA.pdf

5. Wang D, Cui P, Zhu W. Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016: 1225-1234.

https://www.kdd.org/kdd2016/papers/files/rfp0191-wangAemb.pdf

6. struc2vec: Learning Node Representations from Structural Identity

https://arxiv.org/pdf/1704.03165.pdf

總結

以上是生活随笔為你收集整理的一文直击Graph Embedding图表示学习的原理及应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。