詳解Graph Embedding經典方法：算法原理、代碼實作與應用樣例

作者|沈偉臣（閱謙）

編輯|橙子君

出品|阿裡巴巴新零售淘系技術

導讀

我們都知道在資料結構中，圖是一種基礎且常用的結構。現實世界中許多場景可以抽象為一種圖結構，如社交網絡，交通網絡，電商網站中使用者與物品的關系等。以躺平APP社群為例，它是“躺平”這個大生态中生活方式分享社群，分享生活分享家，努力打造社群交流、好物推薦與居家指南。使用者在社群的所有行為：釋出、點選、點贊、評論收藏等都可以抽象為網絡關系圖。是以Graph Embedding技術非常自然地成為學習社群中使用者與内容的embedding的一項關鍵技術。

目前落地的模型大緻兩類：直接優化節點的淺層網絡模型和基于GNN的深層網絡模型。前者包括基于使用者行為了解内容，學習内容向量表征的item2vec,用于擴充i2i召回；同時學習使用者與内容向量表征的異構網絡表示學習模型metapath2vec，用于提高内容召回的多樣性；以群體行為代替個體行為的userCluster2vec，緩解新使用者冷啟動問題。後者包括采用鄰域聚合的思想，同時融入節點屬性資訊，通過多層節點聚合使得網絡中的拓撲結構能夠有效捕捕獲的graphSage，以及将attention機制運用鄰域資訊聚合階段的GAT，對使用者與内容向量表征進行更加細緻化學習。

這裡先看下 Graph Embedding 的相關内容。

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

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:
            break
    return walk

def _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 walks

results = Parallel(n_jobs=workers, verbose=verbose, )(
    delayed(self._simulate_walks)(nodes, num, walk_length) for num in
    partition_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

▐ 可視化結果

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

對于每一條無向邊（i，j），定義頂點

和

之間的聯合機率為：

，

為頂點

的低維向量表示。（可以看作一個内積模型，計算兩個item之間的比對程度）

同時定義經驗分布：

優化目标為最小化：

是兩個分布的距離，常用的衡量兩個機率分布差異的名額為KL散度，使用KL散度并忽略常數項後有：

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

✎ 2nd-order

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

對于有向邊（i，j），

定義給定頂點條件下，産生上下文(鄰居)頂點

的機率為：

，其中

為上下文頂點的個數。

優化目标為：

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

經驗分布定義為：

是邊（i，j）的邊權，

是頂點

的出度，對于帶權圖，

使用KL散度并設

，忽略常數項，有

**3. 優化技巧

**

✎ Negative sampling

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

，k是負邊的個數。

論文使用

是頂點的v出度。

✎ Edge Sampling

注意到我們的目标函數在log之前還有一個權重系數

，在使用梯度下降方法優化參數時，

會直接乘在梯度上。如果圖中的邊權方差很大，則很難選擇一個合适的學習率。若使用較大的學習率那麼對于較大的邊權可能會引起梯度爆炸，較小的學習率對于較小的邊權則會導緻梯度過小。

對于上述問題，如果所有邊權相同，那麼選擇一個合适的學習率會變得容易。這裡采用了将帶權邊拆分為等權邊的一種方法，假如一個權重為w的邊，則拆分後為w個權重為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 vertex
    power = 0.75
    numNodes = self.node_size
    node_degree = np.zeros(numNodes)  # out degree
    node2idx = self.node2idx

    for 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 edge
    numEdges = 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倉庫中

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個數。

node2vec

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

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

▐ node2vec 算法原理

1. 優化目标

設

是将頂點u映射為embedding向量的映射函數,對于圖中每個頂點u，定義

為通過采樣政策s采樣出的頂點u的近鄰頂點集合。

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

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

• 條件獨立性假設

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

• 特征空間對稱性假設

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

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

由于歸一化因子：

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

1. 頂點序列采樣政策

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

給定目前頂點 v，通路下一個頂點x的機率為：

是頂點 v和頂點x之間的未歸一化轉移機率， z是歸一化常數。

node2vec引入兩個超參數 和來控制随機遊走的政策，假設目前随機遊走經過邊（t，v）到達頂點v設

是頂點v和x之間的邊權。

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

下面讨論超參數p和 q對遊走政策的影響：

• Return parameter,p

參數p控制重複通路剛剛通路過的頂點的機率。注意到p僅作用于的情況，而 表示頂點x就是通路目前頂點 之前剛剛通路過的頂點。那麼若 p較高，則通路剛剛通路過的頂點的機率會變低，反之變高。

• In-out papameter,q

q控制着遊走是向外還是向内，若

，随機遊走傾向于通路和t接近的頂點(偏向BFS)。若

，傾向于通路遠離t的頂點(偏向DFS)。

下面的圖描述的是當從t通路到v時，決定下一個通路頂點時每個頂點對應的

。

3. 學習算法

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

▐ 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_edges
    walk = [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:            
            break
    return walk           

2. 構造采樣表

preprocess_transition_probs分别生成alias_nodes和alias_edges，alias_nodes存儲着在每個頂點時決定下一次通路其鄰接點時需要的alias表（不考慮目前頂點之前通路的頂點）。alias_edges存儲着在前一個通路頂點為t，目前頂點為 時決定下一次通路哪個鄰接點時需要的alias表。

get_alias_edge方法傳回的是在上一次通路頂點 t，目前通路頂點x為時到下一個頂點的未歸一化轉移機率:

def get_alias_edge(self, t, v):
    G = self.G    
    p = self.p    
    q = self.q
    unnormalized_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.G
    alias_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_edges
    return           

▐ node2vec 應用

使用node2vec在wiki資料集上進行節點分類任務和可視化任務。wiki資料集包含 2,405 個網頁和17,981條網頁之間的連結關系，以及每個網頁的所屬類别。通過簡單的超參搜尋，這裡使用p=0.25,q=4的設定。

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

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 算法當機器

SDNE

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

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

▐ SDNE 算法原理

相似度定義

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

2階相似度優化目标

這裡我們使用圖的鄰接矩陣進行輸入，對于第i個頂點，有

，每一個

都包含了頂點i的鄰居結構資訊，是以這樣的重構過程能夠使得結構相似的頂點具有相似的embedding表示向量。

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

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

其中為逐元素積，

，若

，則

，否則

1階相似度優化目标

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

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

還可以表示為

其中L是圖對應的拉普拉斯矩陣，

，D是圖中頂點的度矩陣，S是鄰接矩陣，

整體優化目标

聯合優化的損失函數為

是正則化項，

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

模型結構

先看左邊，是一個自動編碼器的結構，輸入輸出分别是鄰接矩陣和重構後的鄰接矩陣。通過優化重構損失可以保留頂點的全局結構特性(論文的圖畫錯了，上面應該是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條網頁之間的連結關系，以及每個網頁的所屬類别。

micro-F1: 0.6341 macro-F1: 0.4962

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

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

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

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的節點集合）的環路上的結構距離(注意是距離，不是相似度)。

其中

是衡量有序度序列D1和D2的距離的函數，并且

.

下面就是如何定義有序度序列之間的比較函數了，由于

的長度不同，并且可能含有重複元素。是以文章采用了Dynamic Time Warping(DTW)來衡量兩個有序度序列。

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

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

至于為什麼使用這樣的距離函數，這個距離函數實際上懲罰了當兩個頂點的度數都比較小的時候兩者的差異。舉例來說，

情況下的距離為1，

情況下的距離差異為0.0099。這個特性正是我們想要的。

建構層次帶權圖

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

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

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

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

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

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

采樣擷取頂點序列

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

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

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

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

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

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

• OPT1 有序度序列長度優化

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

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

同時修改距離函數為：

為度數， a1，b1為度的出現次數。

• 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 = 0
 queue.append(root)
 visited[root] = True

 while (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) + 1
 else:
 degree_list.append(degree)

 for nei in self.graph[node]:
 nei_idx = self.node2idx[nei]
 if not visited[nei_idx]:
 visited[nei_idx] = True
 queue.append(nei_idx)
 count -= 1
 if 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_list
 level += 1

 return ordered_degree_sequence_dict

def _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 v1
 for v2 in nbs:
 lists_v2 = degreeList[v2] # lists_v1 :orderd degree list of v2
 max_layer = min(len(lists_v1), len(lists_v2)) # valid layer
 dtw_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] = dist
 return dtw_dist

def _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_max
 else:
 dist_func = cost

 if 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 vertex
 nbs = get_vertices(
 v, len(self.graph[self.idx2node[v]]), degrees, n_nodes)
 vertices[v] = nbs # store nbs
 degreeListsSelected[v] = degreeList[v] # store dist
 for n in nbs:
 # store dist of nbs
 degreeListsSelected[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.0

 for 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 += w

 e_list = [x / sum_w for x in e_list]
 norm_weights[v] = e_list
 accept, alias = create_alias_table(e_list)
 node_alias_dict[v] = alias
 node_accept_dict[v] = accept

 pd.to_pickle(
 norm_weights, self.temp_path + 'norm_weights_distance-layer-' + str(layer)+'.pkl')

 layers_alias[layer] = node_alias_dict
 layers_accept[layer] = node_accept_dict

 return layers_accept, layers_alias           

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

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

def prepare_biased_walk(self,):

 sum_weights = {}
 sum_edges = {}
 average_weight = {}
 gamma = {}
 layer = 0
 while (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 = 0
 for w in list_weights:
 if (w > average_weight[layer]):
 num_neighbours += 1
 gamma[layer][v] = num_neighbours

 layer += 1

 pd.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 = 0
 layer = initialLayer

 path = []
 path.append(self.idx2node[v])

 while len(path) < walk_length:
 r = random.random()
 if(r < stay_prob): # same layer
 v = chooseNeighbor(v, graphs, layers_alias,
 layers_accept, layer)
 path.append(self.idx2node[v])
 else: # different layer
 r = 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 - 1
 else:
 if((layer + 1) in graphs and v in graphs[layer + 1]):
 layer = layer + 1

 return path           

▐ Struc2Vec 應用

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

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

▐ 分類

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

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

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

Struc2Vec結果

Node2Vec結果

關注淘系技術微信公衆号，背景回複：ge 即可擷取本文涉及的所有論文和代碼彙總～

參考資料：

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
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

阿裡巴巴淘系技術部-商業機器智能團隊

商業機器智能部是一支資料和算法一體的團隊，服務于淘寶、天貓、聚劃算、閑魚和躺平等業務線的二十餘個業務場景，提供線上零售、内容社群、3D智能設計和端上智能等資料和算法服務。我們通過機器學習、強化學習、資料挖掘、機器視覺、NLP、運籌學、3D算法、搜尋和推薦算法，為千萬商家尋找商機，為平台營運提供智能化方案，為使用者提高使用體驗，為設計師提供自動搭配和布局，進而促進平台和生态的供給繁榮和使用者增長，不斷拓展商業邊界。

這是一支快速成長中的學習型團隊。在創造業務價值的同時，我們不斷輸出學術成果，在KDD、ICCV、Management Science等國際會議和雜志上發表數篇學術論文。團隊學習氛圍濃厚，每年組織上百場技術分享交流，互相學習和啟發。真誠邀請海内外相關方向的優秀人才加入我們，在這裡成長并貢獻才智。

如果您有興趣可将履歷發至[email protected]，期待您的加入！

關注「淘系技術」微信公衆号，一個有溫度有内容的技術社群~