文章主要是提出了一阶相似性和二阶相似性
文章链接： Large-scale Information Network Embedding
参考链接： 知乎笔记LINE
代码见： Colab
LINE可以适用于任何类型的graph，如无向图、有向图、加权图等，同时作者基于边采样进行了目标函数的优化，使算法既能捕获到局部的网络结构，也能捕获到全局的网络结构。
优化目标
一阶相似度：如果两个顶点之间有直接相连的边，则一阶相似度由权重决定，若无则为0；
经验概率：
（wij表示的是ij两点之间的权重，W表示的是所有边的权重和）
因此目标函数变为：
使用KL散度公式计算两个概率的差异（即
），带入到公式，上式化简为：
优化
更小也就是让联合概率
更好地拟合经验概率，得到的各顶点向量能存储一阶相似度信息。
二阶相似度：
二阶相似度经验概率：
（wij表示的是ij两点之间的权重，di表示的是所有顶点i的出边的权重和）
如何理解该经验概率可以表示二阶相似度？原文中对二阶相似度如此定义：The secondorder proximity between a pair of vertices (u, v) in a network is the similarity between their neighborhood network structures.
也就是说若将两点的临边经验概率向量表示：如 下图示：
v1=(w14，w15，w16，w13)=(3/11,2/11,4/11,2/11)
v2=(w24，w25，w26，w27)=(3/9,1/9,4/9,1/9)
两向量的相似度即可表示此二阶相似度。
那么如何使得我们得到的顶点向量表示能够“蕴含”该二阶相似度的信息呢，关键在于两点向量表示在某一表达式处理后，能够得到近似于上述真实概率分布（经验概率）。
换言之，就是要更好地拟合下面的预测概率表达式和经验概率（
和
）
（|V|为所有顶点个数）
为保证二阶相似度能够被保证保留在向量信息中，如原文说，we should make the conditional distribution of the contexts 
specified by the low-dimensional representation be close to the empirical distribut
也即目标函数如下：
其中，
表示的是顶点i的重要度，在下面的化简中，以
（顶点i的出度）近似之，在实际上也可用PageRank等方法估计得到。
使用KL散度公式计算两个概率的差异（即
），带入到公式，上式化简为
模型优化
接下来的目标就是优化向量
，也即两个嵌入矩阵（embeddings和context_embeddings）的内容（用两个矩阵的原因和w2v中的一样），使得上述式子（
和
）最小化。
在接下来，一阶二阶分别优化，最后得到的向量拼接即可。
负采样
由于O2式具体化之后为
在计算分母
时，需要遍历所有顶点，效率极为低下，因此需要采用负采样的方法提高效率。
别名采样
在优化两个目标函数时，有以下问题：若为带权图，使用梯度下降法优化参数时，要将边权重
乘上（直观上感受，这样的原因在于：）为了解决这个问题，可将权重为w的边拆分为w条无权边，但是会因此耗费很多内存，所以要考虑另外一种方法：对于权重较大的边以更高的概率采样，权重小的则以更低的概率采样，采样后的边都视为无权边，这样既能解决学习率低的问题，也能避免内存耗费的问题。
采样的方法参照Alias method，带入到此来说就是对于N条边，边权重之和为sum，每条边被采样的概率为
，先从1-N取一个整数n，再随即从0-1取一值p，若p>Prob(n)，则采样别名Alias(n)，否则采样本名n。这样就可以采样得到真正需要训练的边。在生成batch时可用。
复现代码
这一部分花了较多的时间，主要是在复现的部分，网络上没有什么可供参考的复现的资料，且因为学习复现node2vev和deepwalk时并没有用到pytorch或者是tensorflow框架（直接用的gensim里面的word2vec），所以在这里我希望自己至少能动手改写一个pytorch的代码，以加深对整个框架使用的了解，找到了openne的开源代码（tf框架写成），在认真阅读代码并结合博客后，对代码有了更深入的理解，动手改写了pytorch版的，也就是在这里我意识到这些框架代码的共性和核心：一些基本的参数（iter，batch_size，epoch等的选择以及调整的意义），loss函数的确定和batch的选择是最为核心的部分。
在最初没有意识到一个小的细节问题前，改写后的pytorch代码loss下降效果远远不如tf版，于是尝试修改batchsize并看这个问题下的回答，（最后是在同学帮忙看找到的，问题在于误使两个矩阵相同了）虽然最后问题并不是batch_size，但也算有所收获。（batch_size会影响什么）
基于一个tf版本的代码（openne中的line.py）改写了一个pytorch版本，并以blogcatalog作为数据集，代码可见：Colab
MICRO-F1
使用数据集BlogCatalog得到的Micro-F1=0.3757828810020877
可视化
使用数据量较小的wiki进行可视化，可以看到有一定的聚集效果（代码见：Colab）
