LINE

2019-08-14 本文已影响0人 GXLiu_28

LINE用first-order和second-order来保持Graph的结构

first-order：描述局部点对的邻近度(互相连接的网页page的话题是相似的)如顶点6、7
second-order：共享相同邻居的节点也会有相似的性质（在社交网络中分享相似朋友的人也会有相似的兴趣从而可能成为朋友），如顶点5、6

以下分别为first-order和second-order的优化目标函数，作者自己定义了一个近似分布(左边是sigmoid函数右边是softmax函数)，然后用KL-Divergence衡量两个分布的距离，并最小化两者距离

优化p2比较耗时，作者采用Negative Sampling来训练(在做softmax的时候，分母的计算要遍历所有节点，这部分其实很费时，所以在分母较大的时候，经常会使用负采样技术)根据噪声分布采样一些负例的边，此目标函数的第一项是正例，第二项是采样得到的负例，第一项中的 $u'_j$ 和 $u_i$ 越相似越好, 第二项中的 $u'_n$ 与 $u_i$ 越不相似越好，这个可以说是 $O_2$ 的一个替代目标函数，K是采集的negative edges边数。
Negative Sampling
因为 $O_1$ 和 $O_2$ 都是会乘上权重 $w_{ij}$ ，所以用backpropagation的时候，如果 $w_{ij}$ 比较大的话，那么会出现梯度问题，这样就不能够得到合适的学习率，针对这个问题，文中提出了一种edge sample的方法，对于带权值的边最好转化成为不带权值的边(binary edge 也就是连接就为1，不连接就为0)，根据权重sample一条边，并把这条边视为binary edge，采样方法用alias table method，这个方法的采样时间复杂度是O(1)