Deep Neural Networks for Learning Graph Representations论文笔记

Deep Neural Networks for Learning Graph Representations

stack anto-encoder 的相关介绍

网络性质	属性、标签	权重	方向	方法	任务
同质	有	有权	有向	matrix factorization	node classification
异质	无	无权	无向	random walk	link prediction
/	/	/	有向&无向	deep learning	clustering (community detection)
/	/	/	/	transition matrix	visualization

输入：对角矩阵与转移矩阵的相乘，且$\alpha$α概率相乘，$1-\alpha$1−α 概率回到起点

文章是2016年的，深度学习大火，所以，这篇文章的重点在于应用深度学习，用非线性模型来抓取其中的结构、语义信息。

主体是auto-encoder，auto-encoder的输入是经过随机减少特征的PPMI矩阵，这个PPMI矩阵，是特殊的转移矩阵的经过k步衰减之后的求和。

Random Surfing and Context Weighting

We introduce a row vector $p_k$pk​, whose j-th entry indicates the probability of reaching the j-th vertex after k steps of transitions, and $p_0$p0​ is the initial 1-hot vector with the value of the i-th entry being 1 and all other entries being 0.

那么其实这里的$p_0$p0​只是第$i$i个节点的起始状态，$p_k$pk​是以第 $i$i个节点起始, 转移 $k$k步之后的各个节点的分布。因此，$p_k$pk​的第$j$j列表示从$i$i 个开始，经过 $k$k步，到达第$j$j个节点的概率。因此，实际上，这儿还是以应该和 watch your step一样，是个$P$P矩阵才对。

出发点是认为，¹⁾Deepwalk长度有限，处于边缘的节点信息没有用全，²⁾ Deepwalk参数难调，感觉和watch your step的出发点很像。因此用了一个 random surfing，主要思想还是用 转移矩阵 $A$A ， $p_k$pk​有$\alpha$α 的概率继续转移，还有另外一部分$(1-\alpha)$(1−α)概率回到原点。$p_0$p0​是是一个one-hot向量。
$p_k = \alpha (p_{k-1}A) + (1-\alpha)p_0$pk​=α(pk−1​A)+(1−α)p0​

$p^*_k = p_0 A^k$pk∗​=p0​Ak

两者综合一下：
$p_k = \alpha ^k p^*_k + \sum^k_{t=1} \alpha^{k-t} (1-\alpha)p^*_{k-t}$pk​=αkpk∗​+t=1∑k​αk−t(1−α)pk−t∗​

但是这这是说，我分别走几步的概率，要把所有的东西加起来才行：
$r = \sum^K_{k=1} w(k)p^*_k = \sum^K_{k=1}p_k$r=k=1∑K​w(k)pk∗​=k=1∑K​pk​
所以 eq(4) 主要是为了把式子总合成 只关于$p_k^*$pk∗​的式子，$w(t)$w(t)是一个随距离衰减的函数，那么综合 eq(3),(4)，可以得出，$w(k )=\alpha^k +\alpha^k(1-\alpha)(K-k) $，求导是个减函数就是了。

上式说明，一个点有$\alpha$α 的概率继续转移，还有另外一部分$(1-\alpha)$(1−α)概率回到原点，这样的设想确实能够满足，当$k$k越大，之后的向量在整体 representation 中的占比越低。这也就是 Context Weighting

stacked denoising auto-encoder

以上得到的$r$r作为 auto-encoder 的输入，这个 auto-encoder 的输入也很特别，是stacked denoising auto-encoder，也就是输入的一部分会被随机替换为0。为增强鲁棒性。

本文强调深度学习的重要性，特别的还对比了不同深度的结果。

论文结构：

• P_1-3 相关工作介绍
• P_4-5 模型介绍
• P_6-7 对于模型的讨论、数据集、baseline、实验、结论