LINE

文章背景

题目：《LINE:Large-scale Information Network Embedding》
来源：World Wide Web2015
作者：Jian Tang等

Abstract

1. 动机：处理更大规模的图。
2. 优势：可适用于有向/无向、有权重／无权重 的图。+ 以下两点创新。
3. 两点创新：
   • 新的评价函数：既关注了局部信息，也关注了全局信息。(first-order和second-order)
   • 边采样方法：突破了SGD的限制，既快又好，还使得可处理规模更大。
4. 适用场景：语言网络、社交网络、引用网络
5. 处理规模：百万点+十亿边 单机几个小时就处理完

Introduction

1. first-order:边直接相连，真实场景中很稀疏。
2. second-order:共享邻居的节点。有相同邻居社区的两个节点，它俩也应该是相似的。
3. 关系：second-order可以补充first-order的稀疏性，并且保留了网络的全局结构。
4. SGD缺陷：边的权重有很高的方差，梯度乘上这些大权重的话容易引起梯度爆炸。
   本文提出的edge-smapling将权重作为被选中的概率，然后将所有的边转化为binary边，消除了梯度爆炸问题。

Related work

deepwalk缺陷：

1. 没有说明具体保留了图的什么性质。（我觉得说清楚了，就是二阶性质啊）
2. 做出了假设：second-order更高的两个点有更相似的embedding。
3. 使用了DFS，而本文使用了BFS，更接近second-order。(我还是觉得DFS好一些，更符合word2vec)
4. 只能处理无权边。

4.LINE:

4.1Model Description

4.1.1 first-order

只能处理无向边

4.1.2 second-order

1. 有向\无向 均可。
2. 每个点都有两个角色：自己本身和作为其他点的邻居。
3. second-order在LINE中是单向定义，即最大化v_j是v_i邻居的概率。

4.1.3 Combineing first-order and second-order proximities

1. 目前的策略是分别训练，然后拼接
2. 后续方案可能是联合训练

4.2Model Optimization

1. 负采样，由于公式4需要遍历整个节点集合-计算量大，因此采用negative sampling。
2. second-order具体更新时，只更新了中心节点i的embedding。

4.2.1Optimization via Egde Sampling

1. 动机：避免梯度爆炸
2. 采样过程：从原始边集中进行采样，选中的概率和边的权重正相关。
3. 原理：通过概率采样，既将有权边转化成无权边，又考虑到了权重的作用。
4. 预处理过程中采用了alias table来简化采样过程，好像比较有用，具体不清楚。

4.3Discuss

1. 本文认为second-order严重依赖邻居，对于出度小的节点不友好，因此还采样了邻居的邻居作为邻居。
2. 对于新添加的点，使用老点对新点进行更新，并且维持老点的embedding不变。我对公式10有疑问。

5实验

设置：

1. 数据集：一个语言网络、两个社交网络、两个引用网路。
2. Baseline: Graph factorization、DeepWalk、使用SGD的LINE、使用edge-sampling的LINE、结合了first-order和dsecond-order的LINE。
3. 最终都对embedding进行了归一化。
4. 单机多线程。

结论：

1. second-order比first-order更能抓住单词之间的语义关系。
2. Deepwalk在语言模型中表现不好，是因为忽视了边的权重，这很重要。
3. 使用SGD的LINE在语言模型中发生了梯度爆炸。
4. second-order和first-order可以互补。
5. 社交网络中first-order比second-order重要。
6. 社交网络比语言网络更稀疏。
7. second-order对稀疏场景的处理不如first-order。
8. second-order对degree低的点效果也不好。
9. embedding的维度太大时，效果会变差。
10. 扩展性方面，差不多可以达到线性加速，但是模型效果还是很稳定的。

6.Conclusion

1. second-order和first-order可以互补;
2. edge-sampling可以解决SGD的限制；
3. LINE又快又好；
4. 未来准备探索更高的order,还探索异构图(点的类型不同)

我自己的想法

1. Introduction中为什么说second-order可以保留了网络的全局结构？
2. (已解决)Introduction中：SGD中，为什么边的权重要乘以梯度？答案请看4.2。
3. Related work中：DFS vs. BFS 到底谁好？
4. second-order具体更新时，可以既更新中心节点i的embedding，又更新邻居节点j的embedding吗？我觉得是可以的啊，每次固定一个即可！
5. 公式1和公式4的区别在哪里？ p1和p2的经验概率公式的区别又在哪里？我觉得没有对应起来！！公式4根本看不出来与方向有关啊,而且并不能描述出neighborhood的属性，要是我做的话，我会选取节点v的两个相邻节点m和n,然后看U_m和U_n的关系。
6. 不理解公式10。
7. 采样方法中，BFS是取代DFS，还是作为DFS的补充？