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

DeepWalk：演算法原理，實現和應用?

zhuanlan.zhihu.com圖標LINE：演算法原理，實現和應用?

zhuanlan.zhihu.com圖標Node2Vec：演算法原理，實現和應用?

zhuanlan.zhihu.com圖標SDNE：演算法原理，實現和應用?

zhuanlan.zhihu.com圖標

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

Struc2Vec演算法原理

相似度定義

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

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

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

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

頂點對距離定義

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

令 s(S) 表示頂點集合S的有序度序列。

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

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

f_k(u,v)=f_{k-1}(u,v)+g(s(R_k(u)),s(R_k(v))),kge 0 ext{ and } |R_k(u)|,|R_k(v)|>0

其中 g(D_1,D_2)ge 0 是衡量有序度序列 D_1 和 D_2 的距離的函數，並且 f_{-1}=0 .

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

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

基於DTW，定義元素之間的距離函數 d(a,b)=frac{max(a,b)}{min(a,b)}-1

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

構建層次帶權圖

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

我們定義在某一層k中兩個頂點的邊權為 w_k(u,v)=e^{-f_k(u,v)},k=0,...,k^*

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

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

w(u_k,u_{k+1})=log{(Gamma_{k}(u)+e)},k=0,...,k^*-1

w(u_k,u_{k-1})=1

其中 Gamma_k(u) 是第k層與u相連的邊的邊權大於平均邊權的邊的數量。 Gamma_k(u) = sum_{v in V} 1(w_k(u,v)>ar{w_k}) ， ar{w_k} 就是第k層所有邊權的平均值。

採樣獲取頂點序列

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

若決定在當前層遊走，設當前處於第k層，則從頂點u到頂點v的概率為： p_k(u,v)=frac{e^{-f_k(u,v)}}{Z_k(u)} 其中 Z_k(u)=sum_{vin V,v e u}e^{-f_k(u,v)} 是第k層中關於頂點u的歸一化因子。

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

若決定切換不同的層，則以如下的概率選擇 k+1 層或 k-1 層，

p_k(u_k,u_{k+1})=frac{w(u_k,u_{k+1})}{w(u_k,u_{k+1})+w(u_k,u_{k-1})}

p_k(u_k,u_{k-1})=1-p_k(u_k,u_k+1)

三個時空複雜度優化技巧

OPT1 有序度序列長度優化

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

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

同時修改距離函數為： dist(a,b)=(frac{max(a_0,b_0)}{min(a_0,b_0)}-1)max(a_1,b_1) a_0,b_0 為度數， a_1,b_1 為度的出現次數。

OPT2 相似度計算優化

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

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

OPT3 限制層次帶權圖層數

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

當k接近 k^* 時，環上的度序列 s(R_k(u)) 長度也會變得很短， f_k(u,v) 和 f_{k-1}(u,v) 會變得接近。

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

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

Struc2Vec核心代碼

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

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

頂點對距離計算

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

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

這裡我們採用層序遍歷的方式從root開始進行遍歷，遍歷的過程計算當前訪問的層次level，就是對應文章中的 k 。每次進行節點訪問時只做一件事情，就是記錄該頂點的度數。 當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

有了所有頂點對應的 s(R_k(u)) 後，我們要做的就是計算頂點對之間的距離 g(s(R_k(u)), s(R_k(v))) ， 然後再利用公式 f_k(u,v)=f_{k-1}(u,v)+g(s(R_k(u)),s(R_k(v))) 得到頂點對之間的結構距離 f_k(u,v)

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

第4個函數convert_dtw_struc_dist的功能是根據compute_dtw_dist得到的頂點對距離完成關於 f_k(u,v) 的迭代計算。

最後說明一下根據我們是否使用優化技巧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只做了一件事情，就是逐層的計算頂點之間的邊權 w_k(u,v)=e^{-f_k(u,v)} ，並生成後續採樣需要的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就是計算當隨機遊走需要跨層時，決定向上還是向下所用到的 Gamma_{k}(u) 。

w(u_k,u_{k+1})=log{(Gamma_{k}(u)+e)},k=0,...,k^*-1

w(u_k,u_{k-1})=1,

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是在一個多層圖中進行採樣，遊走可能發生在同一層中，也可能發生跨層，所以要添加一些跨層處理的邏輯。

p_k(u_k,u_{k+1})=frac{w(u_k,u_{k+1})}{w(u_k,u_{k+1})+w(u_k,u_{k-1})}

p_k(u_k,u_{k-1})=1-p_k(u_k,u_k+1)

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倉庫中，

shenweichen/GraphEmbedding?

github.com圖標

分類

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

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

可視化

  • Struc2Vec結果
  • Node2Vec結果

參考資料

  • struc2vec: Learning Node Representations from Structural Identity

快開學了，要回學校搬磚了，大家可以先關注一下這個專欄，以後有空我再來更新~

推薦閱讀：

相關文章