文章背景
题目：《node2vec》:Scalable Feature Learning for Networks
来源：ACM SIGKDD 2016
作者：Aditya Grover、Jure Leskovec(都是stanford cs)
Abstract
动机：前人工作没有捕获连接模式的多样性，本文将维护节点的邻域。
贡献：
- 拓展了邻域的概念
- 设计了有偏差的随机游走，这对不同邻域都有效
- 是前人”严格定义邻域”的泛化，证明了“拓展邻域的概念”可以更丰富表达
适用场景：多标签分类任务、链接预测任务
适用于有向\无向，有权重\无权重的图。
1.Introduction
- 节点两种属性：
- 同质性(属于同一个社区;homophily)
- 结构角色(比如是中心节点;structural role)
- 在真实场景中，这两种属性是混合的
Present work
- node2vec属于半监督
使用了word2vec中的skip-gram,SGD- 最大化节点邻域的可能性(likelihood)
- 使用了2阶随机游走
- 关键贡献是对节点的邻域做了更为灵活的定义
- 扩张方面：也对边做了embedding，即对边进行向量表示。(其实就是对边的两个点的embedding做二元运算)
- 对标算法：DeepWalk LINE
- 模型性能：多标签提升了26.7%,连接预测提升了12.6%。甚至只用了10%的数据时，效果也很好。
- 可并行化计算，可扩展到大规模网络(几百万节点)
Contribution
没什么干货
2.Related work
- skim-gram是基于分布式假设的：在相似上下文中出现的单词有相似的含义，即相似的单词出现在相似的上下文中。（感觉这两句话是一个意思）
- node2vec优势：前人工作的模型效果强依赖于对节点的采样策略，node2vec设计了一个灵活的评价函数，可以不强依赖于特定的采样策略，并且增加了超参数可以用于调节采样空间。
- 最后一段好像是在说DNN的思想和缺陷。
3.Feature learning framework
- 基于两点假设：
- 独立性假设
- 对称性假设
3.1Classic search strategies
- BFS探索的是结构性，DFS探索的是同质性。
- BFS优点：减小方差，但是探索的范围太小
DFS优点：没有捕获连接中的依赖关系的实质，高方差，路径太深就没有代表性了、依赖关系也会变得复杂。
3.2node2vec
- 参数q控制了DFS和BFS之间的平衡。
- 本文的随机游走是2阶的Markovian。(没有证明，我也不太清楚)
- 随机游走的好处：
- 内存开销小
- 时间复杂性低
4.Experiments
实验章节还是非常严谨的，只是现在和我的实现无关，因此粗看，后续要细看一下这个实验部分。
我自己的一些想法
- 在3.Feature learning framework中做出了对称性的假设，但我觉得后文其实没有用上。
要是让我做，可能需要设计一个考虑方向的评价函数。 在3.1Classic search strategies中，我不认为“BFS探索的是结构性”。