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. 两个顶点的长距离关系，
2. 不同的 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 转移概率为：

2.3 Optimization with Matrix Factorization

可能为0 ，这里作非零处理；

2.4 ALGORITHM

3.源码

4.参考文献