GraRep: Learning Graph Representations with Global Structural Information
一种基于全局信息的图结点特征向量学习算法
1.背景
DW相关方法，在经验上是有效的，但没有给出损失函数的具体定义。在本论文中，提出了一个明确的损失函数。
GraRep考虑两个信息：
- 两个顶点的长距离关系，
- 不同的 k-step
2.原理
2.1 Graphs and Their Representations
：一个信息网络被定义为
，其中
是顶点集合，每个代表一个数据对象，
是顶点之间的边集，代表两个数据对象之间的关系。
无权重的图中，邻接矩阵中的元素值为0 或者 1 ，0 表示两个顶点无连接、1表示两个顶点有链接；对于有权重的图，
表示从节点
到节点
的权重；在本文中只考虑非负权重情况；
表示节点
表的个数，由于使用矩阵表示，可该矩阵是一个对角矩阵，可以使用邻接矩阵
定义
假设： 节点
这里给出来定义节点
GraRep考虑两个信息：
- 两个顶点的长距离关系，
- 不同的 k-step
k-step 可以获取图的全局结果信息，举例：
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：
求导分解后看出，最后的结果是两个向量的乘机，而这两个向量对应图中的两个节点，也就是这个向量表示的节点信息。上面就出现了矩阵分解的过程：
2.3 Optimization with Matrix Factorization
可能为0 ，这里作非零处理；
下面就是SVD分解的过程，直接截图了。
2.4 ALGORITHM
