GraRep: Learning Graph Representations with Global Structural Information

一种基于全局信息的图结点特征向量学习算法

1.背景

DW相关方法，在经验上是有效的，但没有给出损失函数的具体定义。在本论文中，提出了一个明确的损失函数。

GraRep考虑两个信息：

1. 两个顶点的长距离关系，
2. 不同的 k-step

2.原理

2.1 Graphs and Their Representations

：一个信息网络被定义为，其中是顶点集合，每个代表一个数据对象，是顶点之间的边集，代表两个数据对象之间的关系。
无权重的图中，邻接矩阵中的元素值为0 或者 1 ，0 表示两个顶点无连接、1表示两个顶点有链接；对于有权重的图，表示从节点 到节点 的权重；在本文中只考虑非负权重情况；
表示节点表的个数，由于使用矩阵表示，可该矩阵是一个对角矩阵，可以使用邻接矩阵 定义

假设： 节点
这里给出来定义节点
1-step：两个节点直接相连；
a vs e： a 中两个节点是强链接， e 中两个节点是弱连接；
2-step：两个节点通过另外一个节点链接；
b vs f： b 中 A1与A2 共享了很多邻居节点，共享链接越多，节点之间链接越强；
3-step：两个节点通过另外两个节点链接；
c vs g
4-step：两个节点通过另外三个节点链接；
d vs h

上图a，节点 与 、 的表示可以压缩成图b的形式，由于在计算中都转化为矩阵了，这种说明感觉是多余的。。。

2.2 Loss Function On Graph

k -step 转移概率为：

k-step loss function：


求导分解后看出，最后的结果是两个向量的乘机，而这两个向量对应图中的两个节点，也就是这个向量表示的节点信息。上面就出现了矩阵分解的过程：
下面就是SVD分解的过程，直接截图了。

2.4 ALGORITHM

3.源码

4.参考文献