导读：我们都知道在数据结构中，图是一种基础且常用的结构。现实世界中许多场景可以抽象为一种图结构，如社交网络，交通网络，电商网站中用户与物品的关系等。

目前提到图算法一般指：

• 经典数据结构与算法层面的：最小生成树 (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为多进程并行时的任务分配操作。

Word2vec

这里就偷个懒直接用gensim里的 Word2Vec 了。

DeepWalk 应用

这里简单的用 DeepWalk 算法在 wiki 数据集上进行节点分类任务和可视化任务。  wiki 数据集包含 2,405 个网页和17,981条网页之间的链接关系，以及每个网页的所属类别。

本例中的训练，评测和可视化的完整代码在下面的 git 仓库中：

https://github.com/shenweichen/GraphEmbedding

分类任务结果

micro-F1 : 0.6674

macro-F1 : 0.5768

可视化结果

之前介绍过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散度并忽略常数项后有：

2nd-order

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

，其中为上下文顶点的个数。

，其中为控制节点重要性的因子，可以通过顶点的度数或者PageRank等方法估计得到。

，是边的边权，是顶点的出度，对于带权图，使用KL散度并设，忽略常数项，有

3. 优化技巧

Negative sampling

，是负边的个数。

论文使用，是顶点的出度。

Edge Sampling

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

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

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

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

新加入顶点

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

LINE核心代码

1. 模型和损失函数定义

2. 顶点负采样和边采样

下面的函数功能是创建顶点负采样和边采样需要的采样表。中规中矩，主要就是做一些预处理，然后创建alias算法需要的两个表。

LINE 应用

和之前一样，还是用LINE在wiki数据集上进行节点分类任务和可视化任务。wiki数据集包含 2,405 个网页和17,981条网页之间的链接关系，以及每个网页的所属类别。由于1阶相似度仅能应用于无向图中，所以本例中仅使用2阶相似度。

本例中的训练，评测和可视化的完整代码在下面的git仓库中，

https://github.com/shenweichen/GraphEmbedding

分类任务结果

micro-F1: 0.6403

macro-F1:0.5286

结果有一定随机性，可以多运行几次，或者稍微调整epoch个数。

可视化结果

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个顶点时，使用文章提到的有偏采样。

2. 构造采样表

preprocess_transition_probs分别生成alias_nodes和alias_edges，alias_nodes存储着在每个顶点时决定下一次访问其邻接点时需要的alias表（不考虑当前顶点之前访问的顶点）。alias_edges存储着在前一个访问顶点为t，当前顶点为 时决定下一次访问哪个邻接点时需要的alias表。

get_alias_edge方法返回的是在上一次访问顶点 t，当前访问顶点为时到下一个顶点的未归一化转移概率:

node2vec 应用

使用node2vec在wiki数据集上进行节点分类任务和可视化任务。wiki数据集包含 2,405 个网页和17,981条网页之间的链接关系，以及每个网页的所属类别。通过简单的超参搜索，这里使用p=0.25,q=4的设置。

本例中的训练，评测和可视化的完整代码在下面的git仓库中：

https://github.com/shenweichen/GraphEmbedding

分类任务

可视化

当机器学习遇上复杂网络：解析微信朋友圈 Lookalike 算法

SDNE 算法原理

相似度定义

2阶相似度优化目标

这里我们使用图的邻接矩阵进行输入，对于第个顶点，有，每一个都包含了顶点i的邻居结构信息，所以这样的重构过程能够使得结构相似的顶点具有相似的embedding表示向量。

其中为逐元素积，，若，则，否则

1阶相似度优化目标

还可以表示为

其中L是图对应的拉普拉斯矩阵，，D是图中顶点的度矩阵，S是邻接矩阵， 。

整体优化目标

是正则化项，为控制1阶损失的参数，为控制正则化项的参数。

模型结构

    

再看中间一排，就是我们需要的embedding向量，模型通过1阶损失函数使得邻接的顶点对应的embedding向量接近，从而保留顶点的局部结构特性(中间应该是 Local structure preserved cost)

实现

损失函数定义

模型定义

应用

可视化

     

阿里凑单算法首次公开！基于Graph Embedding的打包购商品挖掘系统解析

05

Struc2Vec

Struc2Vec算法原理

相似度定义

顶点对距离定义

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

令 表示顶点集合S的有序度序列。

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

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

下面就是如何定义有序度序列之间的比较函数了，由于和的长度不同，并且可能含有重复元素。所以文章采用了Dynamic Time Warping(DTW)来衡量两个有序度序列。

基于DTW，定义元素之间的距离函数

至于为什么使用这样的距离函数，这个距离函数实际上惩罚了当两个顶点的度数都比较小的时候两者的差异。举例来说，情况下的距离为1，情况下的距离差异为0.0099。这个特性正是我们想要的。

构建层次带权图

根据上一节的距离定义，对于每一个我们都可以计算出两个顶点之间的一个距离，现在要做的是通过上一节得到的顶点之间的有序度序列距离来构建一个层次化的带权图（用于后续的随机游走）。

我们定义在某一层k中两个顶点的边权为

其中是第k层与u相连的边的边权大于平均边权的边的数量。

，就是第k层所有边权的平均值。

采样获取顶点序列

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

其中是第k层中关于顶点u的归一化因子。

若决定切换不同的层，则以如下的概率选择 层或层，

三个时空复杂度优化技巧：

• OPT1 有序度序列长度优化

为度数， 为度的出现次数。

• OPT2 相似度计算优化

在原始的方法中，我们需要计算每一层k中，任意两个顶点之间的相似度。事实上，这是不必要的。因为两个度数相差很大的顶点，即使在的时候他们的距离也已经非常大了，那么在随机游走时这样的边就几乎不可能被采样到，所以我们也没必要计算这两个顶点之间的距离。

文章给出的方法是在计算顶点u和其他顶点之间的距离时，只计算那些与顶点u的度数接近的顶点的距离。具体来说，在顶点u对应的有序度序列中进行二分查找，查找的过程就是不断逼近顶点u的度数的过程，只计算查找路径上的顶点与u的距离。这样每一次需要计算的边的数量从数量级缩减到。

• OPT3 限制层次带权图层数

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

当k接近 时，环上的度序列长度也会变得很短，  和会变得接近。

因此将图中的层数限制为，使用最重要的一些层来评估结构相似度。

Struc2Vec 核心代码

顶点对距离计算

首先看第一个函数_get_order_degreelist_node，这个函数的作用是计算顶点root对应的有序度序列，也就是前面提到的。

这里我们采用层序遍历的方式从root开始进行遍历，遍历的过程计算当前访问的层次level，就是对应文章中的。每次进行节点访问时只做一件事情，就是记录该顶点的度数。当level增加时，将当前level中的度序列(如果使用优化技巧就是压缩度序列)排序，得到有序度序列。函数的返回值是一个字典，该字典存储着root在每一层对应的有序度序列。

有了所有顶点对应的后，我们要做的就是计算顶点对之间的距离 ， 然后再利用公式 

得到顶点对之间的结构距离 

这里先看第3个函数compute_dtw_dist,该函数实现的功能是计算顶点对之间的距离 ，参数degreeList就是前面一步我们得到的存储每个顶点在每一层的有序度序列的字典。

第4个函数convert_dtw_struc_dist的功能是根据compute_dtw_dist得到的顶点对距离完成关于 的迭代计算。

<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"  />

构建带权层次图

layers_adj存储着每一层中每个顶点的邻接点，layers_distances存储着每一层每个顶点对的结构化距离。_get_transition_probs只做了一件事情，就是逐层的计算顶点之间的边权，并生成后续采样需要的alias表。

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

下面的prepare_biased_walk就是计算当随机游走需要跨层时，决定向上还是向下所用到的。

随机游走采样

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

<pre style="letter-spacing: 0.544px;max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><p style="max-width: 100%;letter-spacing: 0.544px;white-space: normal;color: rgb(0, 0, 0);font-family: -apple-system-font, system-ui, "Helvetica Neue", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;widows: 1;line-height: 1.75em;box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;font-size: 14px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;box-sizing: border-box !important;overflow-wrap: break-word !important;">—</span></strong>完<strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;font-size: 14px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;box-sizing: border-box !important;overflow-wrap: break-word !important;">—</span></strong></span></strong></span></strong></p><section style="max-width: 100%;letter-spacing: 0.544px;white-space: normal;font-family: -apple-system-font, system-ui, "Helvetica Neue", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;widows: 1;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section powered-by="xiumi.us" style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 15px;margin-bottom: 25px;max-width: 100%;opacity: 0.8;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section powered-by="xiumi.us" style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 15px;margin-bottom: 25px;max-width: 100%;opacity: 0.8;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section><p style="margin-bottom: 15px;padding-right: 0em;padding-left: 0em;max-width: 100%;color: rgb(127, 127, 127);font-size: 12px;font-family: sans-serif;line-height: 25.5938px;letter-spacing: 3px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;color: rgb(0, 0, 0);box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;font-size: 16px;font-family: 微软雅黑;caret-color: red;box-sizing: border-box !important;overflow-wrap: break-word !important;">为您推荐</span></strong></span></p><section style="margin: 5px 8px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;box-sizing: border-box !important;overflow-wrap: break-word !important;">知乎高赞：985计算机视觉毕业后找不到工作怎么办？怒刷leetcode，还是另寻他路？</section><p style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;box-sizing: border-box !important;overflow-wrap: break-word !important;">GitHub重大更新：在线开发上线，是时候卸载IDE了</p><p style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;box-sizing: border-box !important;overflow-wrap: break-word !important;">李沐团队半年离开六人，MxNet是否英雄落幕？</p><p style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;box-sizing: border-box !important;overflow-wrap: break-word !important;">程序猿惯用口头禅，你中了几条？</p></section></section></section></section></section></section></section></section>

本篇文章来源于: 深度学习这件小事