node2vec

文章背景

题目：《node2vec》:Scalable Feature Learning for Networks
来源：ACM SIGKDD 2016
作者：Aditya Grover、Jure Leskovec(都是stanford cs)

Abstract

1. 动机：前人工作没有捕获连接模式的多样性，本文将维护节点的邻域。

2. 贡献：

   • 拓展了邻域的概念
   • 设计了有偏差的随机游走，这对不同邻域都有效
   • 是前人”严格定义邻域”的泛化，证明了“拓展邻域的概念”可以更丰富表达

3. 适用场景：多标签分类任务、链接预测任务

4. 适用于有向\无向，有权重\无权重的图。

1.Introduction

1. 节点两种属性：
   • 同质性(属于同一个社区;homophily)
   • 结构角色(比如是中心节点;structural role)
   • 在真实场景中，这两种属性是混合的

Present work

1. node2vec属于半监督
2. 使用了word2vec中的skip-gram,SGD
3. 最大化节点邻域的可能性(likelihood)
4. 使用了2阶随机游走
5. 关键贡献是对节点的邻域做了更为灵活的定义
6. 扩张方面：也对边做了embedding，即对边进行向量表示。(其实就是对边的两个点的embedding做二元运算)
7. 对标算法：DeepWalk LINE
8. 模型性能：多标签提升了26.7%,连接预测提升了12.6%。甚至只用了10%的数据时，效果也很好。
9. 可并行化计算，可扩展到大规模网络(几百万节点)

Contribution

没什么干货

2.Related work

1. skim-gram是基于分布式假设的：在相似上下文中出现的单词有相似的含义，即相似的单词出现在相似的上下文中。（感觉这两句话是一个意思）
2. node2vec优势：前人工作的模型效果强依赖于对节点的采样策略，node2vec设计了一个灵活的评价函数，可以不强依赖于特定的采样策略，并且增加了超参数可以用于调节采样空间。
3. 最后一段好像是在说DNN的思想和缺陷。

3.Feature learning framework

1. 基于两点假设：
   • 独立性假设
   • 对称性假设

3.1Classic search strategies

1. BFS探索的是结构性，DFS探索的是同质性。
2. BFS优点：减小方差，但是探索的范围太小
   DFS优点：没有捕获连接中的依赖关系的实质，高方差，路径太深就没有代表性了、依赖关系也会变得复杂。

3.2node2vec

1. 参数q控制了DFS和BFS之间的平衡。
2. 本文的随机游走是2阶的Markovian。(没有证明，我也不太清楚)
3. 随机游走的好处：
   • 内存开销小
   • 时间复杂性低

4.Experiments

实验章节还是非常严谨的，只是现在和我的实现无关，因此粗看，后续要细看一下这个实验部分。

我自己的一些想法

1. 在3.Feature learning framework中做出了对称性的假设，但我觉得后文其实没有用上。
   要是让我做，可能需要设计一个考虑方向的评价函数。
2. 在3.1Classic search strategies中，我不认为“BFS探索的是结构性”。