作者|沈偉臣（閱謙）
編輯|橙子君
出品|阿里巴巴新零售淘系技術

導讀

我們都知道在數據結構中，圖是一種基礎且常用的結構。現實世界中許多場景可以抽象為一種圖結構，如社交網絡，交通網絡，電商網站中用戶與物品的關係等。以躺平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倉庫中

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

▐ 可視化結果

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算法進行頂點採樣。

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_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倉庫中：

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

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條網頁之間的鏈接關係，以及每個網頁的所屬類別。

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

https://github.com/shenweichen/GraphEmbedding

▐ 分類任務

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做一個對比實驗。

本例中的訓練，評測和可視化的完整代碼在下面的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結果

關注淘系技術微信公眾號，後臺回覆：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]，期待您的加入！

關注「淘系技術」微信公眾號，一個有溫度有內容的技術社區~