node2vec的一些思考

柔情只为你懂 2022-09-30 09:48 163阅读 0赞

# 概述 #

## 论文主要观点 ##

本文将抽取网络中节点的特征转化成最优化一个“可能性”目标函数问题，这个“可能性”是该节点可以保存其邻居节点的信息。

## 成果 ##

*  node2vec，如上述，利用SGD优化，高效
 *  “随机选择邻居”算法，可让node2vec可适应不同的网络

## 方法模型 ##

定义可能性，并且给予两个条件，构成要优化的目标函数；  
![这里写图片描述][1.png]

条件独立性：  
![这里写图片描述][2.png]

节点之间对称性：  
![这里写图片描述][3.png]

最后目标函数：  
![这里写图片描述][4.png]  
既然目标函数描述的是此节点能保存相邻节点的可能性，那么最重要的就是对于相邻节点的选择[算法][Link 1]了，在这里本文利用了一种“Random Walks”的方式，其中含有几个参数，该算法可以在BFS和DFS中随意变换以达到最好的效果，这部分没具体看，不做详细记录。

# 创新点 #

本文的“保存相邻节点可能性”来自于一篇自然语言处理论文，在自然语言中，源文件是线性的，只要设置一个“滑动窗口”即可方便实现。那么本文将该线性方法使用到非线性的图中，创新点就在于引入“Random Walks”的邻居节点选择方式。

# 总结 #

本文的特征抽取方式类似于聚类分析的非监督方法，本质上都是利用相邻节点之间的联系。文中提到了网络中的节点一般有两种相似度量：1.内容相似性，2.结构相似性。其中内容相似性主要是相邻节点之间的相似性，而结构上相似的的点并不一定是相邻的，可能隔得很远，这也是文中为何要把BFS和DFS相结合来选择邻居节点的原因。

# 我的想法 #

这是一篇很有启发作用的好文章。总的来说，你可以以两个方式来看一个网络中的节点，第一，“看本身”，只看这个节点，用其本身的表象来抽取特征，对应于监督方式；第二，“看联系”，看其和其周围的节点，其周围节点一定具有一定的相似度，对应于无监督方式。  
那么对于任何问题，我们如果想去看联系，首先要根据某种规则让他们存在联系，这种存在联系的过程必须是自然的，才能很好的体现出“无人为干预”的自主聚类形式。

Entelecheia（简书作者）  
原文链接：[http://www.jianshu.com/p/a9a2ed8b98be][http_www.jianshu.com_p_a9a2ed8b98be]

# 2.node2vec: Scalable Feature Learning for Networks #

文章地址：[KDD 2016][]

这篇文章来自于Jure Leskovec的组。文章所提出的方法[软件实现][Link 2]。

文章的主要想法就是，利用SkipGram的方法，来为Networks抽取Representation。那么，自然，根据SkipGram的思路，最重要的就是定义这个Context，或者说是Neighborhood。从文本的角度来说，这个Neighborhood当然就是当前Word周围的字，这个定义非常自然。但是对于Graph或者Network来说就来得没那么容易了。

文章阐述了一般所采用Depth-First Search或者是Breadth-First Search来Sample一个Node的周边Node的问题。简单来说，BFS比较容易有一个Microscopic的View而DFS容易有一个Macro-view，两者都有Representative的问题。

文章的核心思想是采用Random Walk来代替DFS或者BFS。文章定义了一种二阶的Random Walk，拥有两个参数，来控制多大的概率反复经过一些Node和控制所谓的Inward和Outward。总之，整个Random Walk的目的就是在DFS和BFS之间采取某种平衡。

文章虽然提出的是关于Node Feature提取的算法，但是Edge Feature也可以很容易从Node Feature导出。

总体感觉是，硬要用SkipGram或者WordVec的想法在Networks上做，还显得比较牵强。因为有这个Neighborhood的概念，在Graph上，反而不是那么直观得定义，因此所有类似的工作都显得比较别扭。当然，这篇文章也不失为一种不错的Heuristic。

作者：洪亮劼  
原文链接：[http://weibo.com/ttarticle/p/show?id=2309404006947190904515][http_weibo.com_ttarticle_p_show_id_2309404006947190904515]

程序源代码：  
[http://snap.stanford.edu/node2vec/][http_snap.stanford.edu_node2vec]

[1.png]: /images/20220706/2a7783efb1744e268f8a8ca20cd4478a.png
[2.png]: /images/20220706/b36463e2322b45d692d75f6e4c88afd9.png
[3.png]: /images/20220706/fb761d72da91479193da936e989c8104.png
[4.png]: /images/20220706/dc33cbb0b055490c93953c43d50868b0.png
[Link 1]: http://lib.csdn.net/base/datastructure
[http_www.jianshu.com_p_a9a2ed8b98be]: http://www.jianshu.com/p/a9a2ed8b98be
[KDD 2016]: http://www.kdd.org/kdd2016/papers/files/rfp0218-groverA.pdf
[Link 2]: http://snap.stanford.edu/node2vec
[http_weibo.com_ttarticle_p_show_id_2309404006947190904515]: http://weibo.com/ttarticle/p/show?id=2309404006947190904515
[http_snap.stanford.edu_node2vec]: http://snap.stanford.edu/node2vec/