图因式分解GraphFactorization

Distributed Large-scale Natural Graph Factorization
Graph Embedding Techniques, Applications, and Performance: A Survey

综述里的描述
图因式分解GraphFactorization

博客上LLE、拉普拉斯特征图的资料不少，但是Graph Factorization的很少，也可能是名字太普通了。。。只能自己看论文了。。。

主要是实现了分布式计算，以及较低的时间复杂度，做图的降维

这里不关注分布式实现，只看最基本的思路和解法

符号定义

基本假设，认为通过降维后的结点向量的内积 $< Z_{i}, Z_{j} >$ 可以表达出边权重 $Y_{i j}$ ，再加上正则项得到如下目标函数

f (Y, Z, λ) = \frac{1}{2} \sum_{(i, j) \in E} (Y_{i j} - < Z_{i}, Z_{j} >)^{2} + \frac{λ}{2} \sum_{i} ‖ Z_{i} ‖^{2}

对

Z_{i}

求偏导得到

\frac{\partial f}{\partial Z_{i}} = - \sum_{j \in N (i)} (Y_{i j} - < Z_{i}, Z_{j} >) Z_{j} + λ Z_{i}

对于每条边有

- (Y_{i j} - < Z_{i}, Z_{j} >) Z_{j} - λ Z_{i}

最后，用SGD更新参数，整体的算法流程为
图因式分解GraphFactorization