1. 论文介绍

首先介绍了复杂网络面对的几种任务：

网络节点的分类，通俗点说就是将网络中的节点进行聚类，我们关心的是哪些节点具有类似的属性，就将其分到同一个类别中。
链接预测，就是预测网络中哪些顶点有潜在的关联。

但是要完成这些任务首先要解决的问题就是网络嵌入

此论文设计出一种既能保持节点邻居信息和体现网络信息而且又容易训练的模型。作者发现很多节点在网络中往往有一些类似的结构特征。一种结构特征是很多节点会聚集在一起，内部的连接远比外部的连接多，作者称之为社区。另一种结构特征是网络中两个可能相聚很远的点，在边的连接上有着类似的特征。比如下图， u,s1,s2,s3,s4 ,就属于一个社区，而 u, s6在结构上有着相似的特征。

在这里插入图片描述

作者结合前面的研究提出提出了一个有效的、可扩展的表示学习算法，可以体现网络特征和节点邻居特征。可以将网络中的结点变成一个向量。

2. 相关工作

2.1 前人方法

对于以前的网络嵌入做法有

手工提取特征的方式。但是特征需要依赖人手工定义，不是某个领域内专业人士无法从事工作
解优化函数的方式学习网络的表示特征。但是这样的方法面临一个计算效率和准确度的平衡问题，无法兼顾两者。
传统的降维方法。如PCA【】应用到网络表示中也确实有一定的效果，缺点是会涉及矩阵分解，运算量大，同时准确率也不高，而且有些方法只是针对特定的任务才有效果。

我们将网络的一个个结点看成一个结点序列，类似于文档看成一个个单车的序列集合，而在NLP方面对于文档的处理有很多模型，例如BERT， word2vec，从名字也可以看出来，作者是借鉴了word2vec的思想。而word2vec的其中一个重要结构就是skip-gram，作者从skip-gram和 deepwalk得到启发， node2vec创新之处就是在此之上提出了新的生成顶点序列的随机游走策略。下面我们就会介绍 skip-gram 和 deep-walk

2.2 skip-gram

例如 cat 和 kitten 应该在语义上是相近的，而dog和kitten 在语义空间上是远离的， skip-gram是给定input word来预测上下文。

在这里插入图片描述

我们给出一个单词的热编码输入到网络中，通过一个隐藏层，经过solfmax 得到窗口内单词的概率，概率代表着同时出现的概率。经过训练后，我们提取出隐藏层的权重作为词语的特征表。

2.3 deep walk

deep walk收到NLP方面的word2vec启发，把网络看成多个结点序列， 每个结点序列就类比成一个句子里的单词，所以deep walk 的关键点在于**，如何把生成结点序列**，deep walk使用随机游走(random walk)，就是在网络上不断重复地随机选择游走路径，最终形成一条贯穿网络的路径。从某个特定的端点开始，游走的每一步都从与当前节点相连的边中随机选择一条，沿着选定的边移动到下一个顶点，不断重复这个过程。然后使用skip-gram机制得到每个结点的特征表示。

3. 主要内容

node2vec 从前人工作中进行改进，其主要流程如下

3.1 优化目标

设f(u)是将顶点u 映射为Embedding向量的映射函数，Ns (u) 为通过采样策略S的近邻顶点集合。将现有的Skip-gram模型扩展到网络中来，优化以下目标函数

在这里插入图片描述

优化目标函数：给定一个顶点，令其近邻顶点出现的概率最大

为了使公式1能够得到很好的优化求解，提出了两个假设：

条件独立给定一个顶点，其近邻顶点出现的概率与近邻集合中的其他顶点无关，得到公式2：

在这里插入图片描述

特征空间中的对称性

源顶点和近邻顶点在特征空间中具有对称性，不管顶点是源顶点还是近邻点Embedding表达是一样的。

在这里插入图片描述

根据以上两个假设条件，最终的目标函数公式1简化为公式4

在这里插入图片描述

3.2 路径采样策略

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

在这里插入图片描述

Node2vec引入两个超参数p和 q来控制随机游走的策略。如上图所示，假设当前随机游走顶点t 经过边 ( t , v ) 到达顶点v ，顶点v的下一个访问顶点x 的概率根据下面公式计算得到，公式6中dtx 为下一个访问顶点x 和当前顶点v 的上一个顶点t 之间的距离

在这里插入图片描述

这里注意：

如果q 较大，则顶点v 下一步游走倾向于访问顶点v 上一步顶点近邻顶点，构成了宽度游走策略
如果q 较小，则顶点v 下一步游走倾向于访问顶点v 上一步顶点距离远的顶点，构成了深度游走策略

3.3 顶点采样策略

顶点采样策略区别于Deepwalk，不是随机采样顶点，使用Alias Sample方法进行采样。Alias方法按照均值1/N进行归一化，其总面积为N，并且分为1*N个长方形，每一列面积为1。通过将概率大于1的事件的面积补到概率小于1的事件中，来保证每列的概率和为1，并且每一列最多两个事件。

4. 主要创新点

提出一种新的Network Embedding 算法，其拓展性更好。
有偏的随机游走算法，通过p， q 等超参调节不同的游走情况，使其更加探索同质性或者结构性的信息
BFS 和 DFS 采样方法带来的结构性和同质性的探索，其中DFS擅长学习网络的同质性，BFS擅长学习网络的结构性
一种边预测的判定条件

在这里插入图片描述

边的特征由结点得出分别代表着

两头端点取平均
两头端点取乘积
取绝对值
取平方差

5. 改进方案思考

对于node2vec框架

在embedding 的过程中没有考虑边的权重，可以尝试通过将权重放到网络训练中
还有一点，无法控制walk序列的规模，可以尝试进行一些机制的改进使得模型可控性更加好
在word2vec中单词到句子没有用到Attention机制，但是后来的研究用到了，所以似乎可以使用Attention 机制来判断序列结点的权重，生成更好的特征向量？
node2vec 是模仿单词和词语的关系，但是句子之间的关系在最近的NLP 方面也进行了研究，所以能否将生成的序列集合看成一个文档，然后句子之间的关系和图上的关系能否进行对应，例如一个区域内的结点组成的序列集合就是一片文章等类比

6. 参考文献

G. Tsoumakas and I. Katakis. Multi-label classification: An overview. Dept. of Informatics, Aristotle University of Thessaloniki, Greece, 2006.
B. Gallagher and T. Eliassi-Rad. Leveraging label-independent features for classification in sparsely labeled networks: An empirical study. In Lecture Notes in Computer Science: Advances in Social Network Mining and Analysis. Springer, 2009.
B. Gallagher and T. Eliassi-Rad. Leveraging label-independent features for classification in sparsely labeled networks: An empirical study. In Lecture Notes in Computer Science: Advances in Social Network Mining and Analysis. Springer, 2009.
K. Henderson, B. Gallagher, L. Li, L. Akoglu, T. Eliassi-Rad, H. Tong, and C. Faloutsos. It’s who you know: graph mining using recursive structural features. In KDD, 2011.
Y. Bengio, A. Courville, and P. Vincent. Representation learning: A review and new perspectives. IEEE TPAMI, 35(8):1798–1828, 2013.
M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In NIPS, 2001.
T. Mikolov, K. Chen, G. Corrado, and J. Dean. Efficient estimation of word representations in vector space. In ICLR, 2013.
B Perozzi，R Al-Rfou，S Skiena. DeepWalk: Online Learning of Social Representations. In ACM, 2014
A Vaswani，N Shazeer，N Parmar，J Uszkoreit. Attention Is All You Need.In arxiv 2017
Jwa H , Oh D , Park K , et al. exBAKE: Automatic Fake News Detection Model Based on Bidirectional Encoder Representations from Transformers (BERT)[J]. Applied Sciences, 2019, 9(19):4062.