node2vec: Scalable Feature Learning for Networks
本文贡献
- 提出了 node2vec 模型
- 展示了 node2vec 模型，符合以往的网络科学（network science）中建立起来的原则
- 拓展了 node2vec 算法，以及其他基于邻居的算法，来做基于边的预测任务
- 在真实数据上，建立 标签分类 （multi-label classification） 和 连接预测 ( link prediction) 这两种任务，目的是经验性地评估 node2vec （为啥是经验性地评估呢？个人觉得是因为这用两个任务评估算法有一定的说服力，但并不充分，但也没有更好的评估方法了）
前人成果
我们想要寻找一种无须任何人工工程（hand-engineered）的方法
无监督特征抽取，往往需要各种矩阵，例如拉普拉斯矩阵和近邻矩阵（Laplacian and the adjacency matrice），一代数视角看来，这些方法是一些降维技术，例如PCA和IsoMap，他们的缺点来自两个：计算量、统计表现。
- 特征分解就很耗费计算量。所以这些方法很难用到大规模网络上
- 对于各种网络特征，并不鲁棒。例如谱聚类（spectral clustering）的前提假设就很强（也就是很严，不过好多中文也喜欢用强这个词）。
然后论文介绍了NLP中的 word2vec 方法，然后说可以把节点序列类比为文字序列。这一块不多说。
但是，有很多种采样策略，论文的研究展示，没有哪个采样策略显著胜出。
node2vec 就克服了这一缺陷，靠的是设计了一个灵活的、不依赖特定采样策略的目标，以及提供了可以调整的参数。
node2vec框架
摘录一个原文上的公式：
$\max\limits_f \sum\limits_{u\in V} Pr(N_S(u)\mid f(u))$
其中，
- V是节点，图 $G=(V,E)$ 的节点。
- $N_S$ 是一种采样方法，$N_S(u)$ 是用这种采样方法得到的邻居。（后面好几段都在强调这个采样方法是创新点）
NLP 中的 skip-gram，因为语言是线性的，所以直接去截取就行了。但图上的不能这样做。
传统的采样方法
有两个极端：
- Breadth-first Sampling (BFS)
- Depth-first Sampling (DFS)
这个不多说，看下面这个图
通常说，图上的点的预测问题，往往是两种相似性的折中：同质性和结构等价性。
（原文：prediction tasks on nodes in networks often shuttle between two kinds of similarities: homophily and structural equivalence）
- homophily:如果两个节点连接紧密，那么就应当归为一类。例如图中的s1和u就在homophily概念上算同一社区。
- structural equivalence：有相似的结构上的角色（e similar structural roles in networks），例如u和s6在结构上就很相似。现实中，两个节点可以相距很远，但有相同的结构。
一般来说，
- BFS取样更多的提取 structural equivalence 特征。直观理解：structural equivalence 更加依赖相邻的邻居，BFS会更多提取相邻邻居的信息。再者，BFS采样会把相邻邻居采样后的数量增多。
- DFS采样更多地提取邻居的更宏观的视角，更接近 homophily
node2vec
random walk
以概率随机游走，deep walk 那篇论文笔记里也写了，不多说。
$P(v\to x)=\dfrac{\pi_{v\to x}}{\sum ?}$
其中
- $\pi$用来控制转移概率，最简单的模型可以取权重
- $\sum ?$是为了让概率总和归一化
search bias
这是本论文的一个特点，
看上面的图，假设已经从t游走到v，那么：
- v到t是回退
- v到x1是BFS
- v到x2，v到x3是DFS
与v相连的节点，都按照下面的原则赋值
- 对于回退，赋值为1/p
- 对于BFS，赋值1
- 对于DFS，赋值1/q
所以这就使用超参数p, q控制了BFS和DFS
实验
case study
结果与预期一致：
- 上面那个是 p=1, q=0.5 的结果，更多地提取了 homophily 特征
- 下面那个是 p=1, q=2 的结果，更多地提取了 structural equivalence 特征
experiment
模型应用于 multi-label classification
- BlogCatalog：label是blogger 的兴趣
- Protein-Protein Interactions (PPI)，蛋白质之间的相互作用，也是一个 graph：label 是特征基因集（我也不懂）
- Wikipedia：网络是 cooccurrence network of words，label是词性
然后，实验就是用 one-vs-rest logistic regreesion ，计算其 F1-score，实验效果当然是挺好。
模型稳定性
然后，文章又做了稳定性实验。
- 随机去除某些边。
- 随机增加一些边
发现模型表现下降，但不很剧烈（下面的右边两个图）
数据规模
实验并记录了数据规模和计算耗时，线性关系。
而且采样时间花费占比很大。
Link prediction
为了做这件事：
- 随机去除50%的边，并且保证剩下的图是联通的
- 负例：随机选取不相邻的节点对
