详解 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 Word2Vecw2v_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 阶相似度用于描述图中成对顶点之间的局部相似度，形式化描述为若 $u,v$ 之间存在直连边，则边权 $w_{uv}$ 即为两个顶点的相似度，若不存在直连边，则 1 阶相似度为 0。如上图，6 和 7 之间存在直连边，且边权较大，则认为两者相似且 1 阶相似度较高，而 5 和 6 之间不存在直连边，则两者间 1 阶相似度为 0。

✎ second-order proximity

仅有 1 阶相似度就够了吗？显然不够，如上图，虽然 5 和 6 之间不存在直连边，但是他们有很多相同的邻居顶点(1,2,3,4)，这其实也可以表明 5 和 6 是相似的，而 2 阶相似度就是用来描述这种关系的。形式化定义为，令 $p_u=(w_{u,1},\dots ,w_{u,|V|})$ 表示顶点 $u$ 与所有其他顶点间的 1 阶相似度，则 $u$ 与 $v$ 的 2 阶相似度可以通过 $p_u$ 和 $p_v$ 的相似度表示。若 $u$ 与 $v$ 之间不存在相同的邻居顶点，则 2 阶相似度为 0。

2. 优化目标

✎ 1st-order

对于每一条无向边 $(i,j)$，定义顶点 $v_i$ 和 $v_j$ 之间的联合概率为：

$p_1(v_i,v_j)=\frac{1}{1+\exp (-{\vec{u}}_u^T,{\vec{u}}_j)}$，${\vec{u}}_i$ 为顶点 $v_i$ 的低维向量表示。（可以看作一个内积模型，计算两个 item 之间的匹配程度）

同时定义经验分布：

优化目标为最小化：

$d(\cdot ,\cdot )$ 是两个分布的距离，常用的衡量两个概率分布差异的指标为 KL 散度，使用 KL 散度并忽略常数项后有：

1st order 相似度只能用于无向图当中。

✎ 2nd-order

这里对于每个顶点维护两个 embedding 向量，一个是该顶点本身的表示向量，一个是该点作为其他顶点的上下文顶点时的表示向量。

对于有向边 $(i,j)$，定义给定顶点 $v_i$ 条件下，产生上下文(邻居)顶点 $v_j$ 的概率为：

$p_2(v_j|v_i)=\frac{\exp ({\vec{c}}_j^T\cdot {\vec{u}}_i)}{{\sum }_{k=1}^{|V|}\exp ({\vec{c}}_k^T\cdot {\vec{u}}_i)}$，其中 $|V|$ 为上下文顶点的个数。

优化目标为：$O_2={\sum }_{i\in V}{\lambda }_{i}d({\hat{p}}_2(\cdot |v_i),p_2(\cdot |v_i))$，其中 ${\lambda }_i$ 为控制节点重要性的因子，可以通过顶点的度数或者 PageRank 等方法估计得到。

经验分布定义为：${\hat{p}}_2(v_j|v_i)=\frac{w_{ij}}{d_i}$，$w_{ij}$ 是边 $(i,j)$ 的边权，$d_i$ 是顶点 $v_i$ 的出度，对于带权图，$d_i={\sum }_{k\in N(I)}{W}_{ik}$ 使用 KL 散度并设 ${\lambda }_i=d_i$，忽略常数项，有 $O_2=-{\sum }_{(i,j)\in E}{w}_{ij}\log p_2(v_j|v_i)$

3. 优化技巧

✎ Negative sampling

由于计算 2 阶相似度时，softmax 函数的分母计算需要遍历所有顶点，这是非常低效的，论文采用了负采样优化的技巧，目标函数变为：

$\log \text{sigam}({\vec{c}}_j^T\cdot {\vec{u}}_i)+{\sum }_{i=1}^K{E}_{v_n\sim P_n(v)}[-\log \sigma ({\vec{c}}_n^T\cdot {\vec{u}}_i)]$，$K$ 是负边的个数。

论文使用 $P_n(v)\propto d_v^{3/4}$，$d_v$ 是顶点 $v$ 的出度。

✎ Edge Sampling

注意到我们的目标函数在 log 之前还有一个权重系数 $w_{ij}$，在使用梯度下降方法优化参数时，$w_{ij}$ 会直接乘在梯度上。如果图中的边权方差很大，则很难选择一个合适的学习率。若使用较大的学习率那么对于较大的边权可能会引起梯度爆炸，较小的学习率对于较小的边权则会导致梯度过小。

对于上述问题，如果所有边权相同，那么选择一个合适的学习率会变得容易。这里采用了将带权边拆分为等权边的一种方法，假如一个权重为 $w$ 的边，则拆分后为 $w$ 个权重为 1 的边。这样可以解决学习率选择的问题，但是由于边数的增长，存储的需求也会增加。

另一种方法则是从原始的带权边中进行采样，每条边被采样的概率正比于原始图中边的权重，这样既解决了学习率的问题，又没有带来过多的存储开销。

这里的采样算法使用的是 Alias 算法，Alias 是一种 $O(1)$ 时间复杂度的离散事件抽样算法。具体内容可以参考：

Alias Method:时间复杂度 O(1)的离散采样方法

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

4. 其他问题

✎ 低度数顶点

对于一些顶点由于其邻接点非常少会导致 embedding 向量的学习不充分，论文提到可以利用邻居的邻居构造样本进行学习，这里也暴露出 LINE 方法仅考虑一阶和二阶相似性，对高阶信息的利用不足。

✎ 新加入顶点

对于新加入图的顶点 $v_i$，若该顶点与图中顶点存在边相连，我们只需要固定模型的其他参数，优化如下两个目标之一即可：

若不存在边相连，则需要利用一些 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. 优化目标

设 $f(u)$ 是将顶点 $u$ 映射为 embedding 向量的映射函数,对于图中每个顶点 $u$，定义 $N_S(u)$ 为通过采样策略 $S$ 采样出的顶点 $u$ 的近邻顶点集合。

node2vec 优化的目标是给定每个顶点条件下，令其近邻顶点（如何定义近邻顶点很重要）出现的概率最大。

为了将上述最优化问题可解，文章提出两个假设：

• 条件独立性假设

假设给定源顶点下，其近邻顶点出现的概率与近邻集合中其余顶点无关。

• 特征空间对称性假设

这里是说一个顶点作为源顶点和作为近邻顶点的时候共享同一套 embedding 向量。(对比 LINE 中的 2 阶相似度，一个顶点作为源点和近邻点的时候是拥有不同的 embedding 向量的) 在这个假设下，上述条件概率公式可表示为：

根据以上两个假设条件，最终的目标函数表示为：

由于归一化因子：

$Z_u={\sum }_{n_i\in N_S(u)}\exp (f(n_i)\cdot f(u))$ 的计算代价高，所以采用负采样技术优化。

2. 顶点序列采样策略

node2vec 依然采用随机游走的方式获取顶点的近邻序列，不同的是 node2vec 采用的是一种有偏的随机游走。

给定当前顶点 $v$，访问下一个顶点 $x$ 的概率为：

${\pi }_{vx}$ 是顶点 $v$ 和顶点 $x$ 之间的未归一化转移概率，$Z$ 是归一化常数。

node2vec 引入两个超参数 $p$ 和 $q$ 来控制随机游走的策略，假设当前随机游走经过边 $(t,v)$ 到达顶点 $v$ 设 ${\pi }_{vx}={\alpha }_{pq}(t,x)\cdot w_{vx}$，$w_{vx}$ 是顶点 $v$ 和 $x$ 之间的边权。

$d_{tx}$ 为顶点 $t$ 和顶点 $x$ 之间的最短路径距离。

下面讨论超参数 p 和 q 对游走策略的影响：

• Return parameter,p

参数 p 控制重复访问刚刚访问过的顶点的概率。注意到 p 仅作用于 $d_{tx}=0$ 的情况，而 $d_{tx}=0$ 表示顶点 x 就是访问当前顶点 $v$ 之前刚刚访问过的顶点。那么若 p 较高，则访问刚刚访问过的顶点的概率会变低，反之变高。

• In-out papameter,q

q 控制着游走是向外还是向内，若 $q>1$，随机游走倾向于访问和 t 接近的顶点(偏向 BFS)。若 $q<1$，倾向于访问远离 t 的顶点(偏向 DFS)。

下面的图描述的是当从 t 访问到 $v$ 时，决定下一个访问顶点时每个顶点对应的 $\alpha$。

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，当前顶点为 $v$ 时决定下一次访问哪个邻接点时需要的 alias 表。

get_alias_edge 方法返回的是在上一次访问顶点 t，当前访问顶点为 $v$ 时到下一个顶点 $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$ 个顶点，有 $x_i=s_i$ ，每一个 $s_i$ 都包含了顶点 i 的邻居结构信息，所以这样的重构过程能够使得结构相似的顶点具有相似的 embedding 表示向量。

这里存在的一个问题是由于图的稀疏性，邻接矩阵 S 中的非零元素是远远少于零元素的，那么对于神经网络来说只要全部输出 0 也能取得一个不错的效果，这不是我们想要的。

文章给出的一个方法是使用带权损失函数，对于非零元素具有更高的惩罚系数。修正后的损失函数为

其中 $\odot$ 为逐元素积，${\mathrm{b}}_{\mathrm{i}}={b_{i,j}}_{j=1}^n$，若 $s_{i,j}=0$，则 $b_{i,j}=1$，否则 $b_{i,j}=\beta >1$

1 阶相似度优化目标

对于 1 阶相似度，损失函数定义如下

该损失函数可以让图中的相邻的两个顶点对应的 embedding vector 在隐藏空间接近。

$L_{1st}$ 还可以表示为

其中 L 是图对应的拉普拉斯矩阵，$L=D-S$，D 是图中顶点的度矩阵，S 是邻接矩阵，$D_{i,i}={\sum }_j{s}_{ij}$。

整体优化目标

联合优化的损失函数为

$L_{reg}$ 是正则化项，$\alpha$ 为控制 1 阶损失的参数，$\nu$ 为控制正则化项的参数。

模型结构

先看左边，是一个自动编码器的结构，输入输出分别是邻接矩阵和重构后的邻接矩阵。通过优化重构损失可以保留顶点的全局结构特性(论文的图画错了，上面应该是 Global structure preserved cost)。

再看中间一排，$y_i^{(K)}$ 就是我们需要的 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)和网络的其他部分相连。

直观来看，具有相同度数的顶点是结构相似的，若各自邻接顶点仍然具有相同度数，那么他们的相似度就更高。

顶点对距离定义

令 $R_k(u)$ 表示到顶点 u 距离为 k 的顶点集合，则 $R_1(u)$ 表示是 u 的直接相连近邻集合。

令 $s(S)$ 表示顶点集合 S 的 有序度序列 。

通过比较两个顶点之间距离为 k 的环路上的有序度序列可以推出一种层次化衡量结构相似度的方法。

令 $f_k(u,v)$ 表示顶点 u 和 v 之间距离为 k（这里的距离 k 实际上是指距离小于等于 k 的节点集合）的环路上的结构距离(注意是距离，不是相似度)。

其中 $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,\dots ,k^{\ast }$

这样定义的边权都是小于 1 的，当且仅当距离为 0 的是时候，边权为 1。

通过有向边将属于不同层次的同一顶点连接起来，具体来说，对每个顶点，都会和其对应的上层顶点还有下层顶点相连。边权定义为

其中 ${\Gamma }_k(u)$ 是第 k 层与 u 相连的边的边权大于平均边权的边的数量。

${\Gamma }_k(u)={\sum }_{v\in V}1(w_k(u,v)>{\bar{w}}_k)$，${\bar{w}}_k$ 就是第 k 层所有边权的平均值。

采样获取顶点序列

使用有偏随机游走在构造出的图 $M$ 中进行顶点序列采样。每次采样时，首先决定是在当前层游走，还是切换到上下层的层游走。

若决定在当前层游走，设当前处于第 k 层，则从顶点 u 到顶点 v 的概率为：$p_k(u,v)=\frac{e^{-f_k(u,v)}}{Z_k(u)}$ 其中 $Z_k(u)={\sum }_{v\in V,v\ne u}{e}^{-f_k(u,v)}$ 是第 k 层中关于顶点 u 的归一化因子。

通过在图 M 中进行随机游走，每次采样的顶点更倾向于选择与当前顶点结构相似的顶点。因此，采样生成的上下文顶点很可能是结构相似的顶点，这与顶点在图中的位置无关。

若决定切换不同的层，则以如下的概率选择 $k+1$ 层或 $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$ 数量级缩减到 $n\log n$。

• OPT3 限制层次带权图层数

层次带权图 M 中的层数是由图的直径 $k^{\ast }$ 决定的。但是对很多图来说，图的直径会远远大于顶点之间的平均距离。

当 k 接近 $k^{\ast }$ 时，环上的度序列 $s(R_k(u))$ 长度也会变得很短，$f_k(u,v)$ 和 $f_{k-1}(u,v)$ 会变得接近。

因此将图中的层数限制为 $k’<k^{\ast }$，使用最重要的一些层来评估结构相似度。

这样的限制显著降低构造 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)$。

这里先看第 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

前面的部分仅仅得到了在同一层内，顶点之间的转移概率，那么同一个顶点在不同层之间的转移概率如何得到 k 呢？

下面的 prepare_biased_walk 就是计算当随机游走需要跨层时，决定向上还是向下所用到的 ${\Gamma }_k(u)$。

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.

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

3. Graph Neural Network Review

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

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

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

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

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

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

10. struc2vec: Learning Node Representations from Structural Identity

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

本文转载自公众号淘系技术（ID：AlibabaMTT）。

原文链接：

详解Graph Embedding经典方法：算法原理、代码实现与应用样例