Graph Embedding：LINE算法

背景

 如上图所示，结点6和7是相邻结点，他们应该是相似结点，结点5和6虽然不是相邻结点，但是它们有共同的相邻的结点，因此它们也应该是相似结点。

基于词观察，LINE算法提出了一阶相似性算法和二阶相似性算法

First-order

我们首先如如下公式来计算结点i和j的联合概率分布：

其中u_i，u_j​分别为节点i和节点j的embedding向量表示，同时我们依据边的权值，也可得经验分布：

其中W为图中边的权值之和，这样我们可以用交叉熵来计算loss：

上面的公式可以看出，两个向量的内积越大，p1越大。且由于内积没有方向，所以First-order只适合无向图

Second-order

我们首先如如下公式来计算结点i和j的转移概率分布：

参考资料

https://zhuanlan.zhihu.com/p/56478167

https://blog.csdn.net/weixin_38877987/article/details/118422847