BLOG

个人博客,记录学习与生活

[AAAI2016]DNGR

Published Aug. 11, 2020, 6:07 p.m. by kkk

DNGR模型于2016年在1中提出,在AAAI会议中被收录。利用自编码器来进行网络图节点的低维映射。

流程

  • 采样
  • 矩阵变换
  • 自编码器

1. 采样

提到了Deepwalk中用到的Random Walk,并解释其局限性:

  1. 采样序列长度固定,难以捕捉采样边界点的上下文信息
  2. 对于大型图,难以直接确定超参数,如步长、总步数

采用了采样方式为Random Surfing model,说是受到PageRank启发。

以word2vec2和GloVe3为例,说明一个直觉上的概念:距离越近的点,彼此间的关系越密切

于是提出所认为的理想节点表示(对于第$i$个节点,未降维的表示): $$ r = \sum_{k=1}^{K} w(k) \cdot p_k^\ast \tag 1 $$ 公式、符号定义:

$A$为图节点的转移矩阵,$p_k$表示经过$k$次转移之后,到达各节点的概率,$p_0$是某节点对应的one-hot向量,另外每次转移的时候,有$\alpha$概率向外转移,$(1-\alpha)$的概率回到自身,于是有: $$ p_k = \alpha \cdot p_{k-1}A+(1-\alpha)p_0 $$ 如果不会转回自身,即$\alpha = 0$,设这种情况下为$p_k^\ast$,那么: $$ p_k^\ast = p_{k-1}^\ast A = p_0A^k $$ 那么对于$p_k^\ast$,$k$越大则转移次数越大,就是会更多的转移到更远的节点,表示距离越远的点,对于前面理想节点表示的公式,按照直觉概念,越远的点关系越松散,那么$w(k)$是一个减函数(具体形式未定义)。为了简化运行,找到了一个符合公式$(1)$的特殊情况: $$ r = \sum_{k=1}^K p_k \tag 2 $$ 此时,$w()$定义如下: $$ w(t) = \alpha^t + \alpha^t (1-\alpha)(K-t) $$ 另外将word2vec2和GloVe3也统一为公式$(1)$的形式,将其$w()$分别表示为$w^\prime()$和$w^{\prime \prime}$,那么有: $$ w^\prime(t) = - \frac{t}{K} + (1 + \frac{1}{K}) $$

$$ w^{\prime \prime}(t) = \frac{1}{t} $$

通过公式$(2)$,确定下超参数$k$后,可以得到各节点转移$k$次之后的表示,将所有节点的转移$k$次表示构成一个矩阵,命名为$PCO$矩阵

2. 矩阵变换

利用$PMI$矩阵,因为在矩阵分解的图表示方法中,用到了该技术构建节点的共现信息,后[^4]将其改进为$PPMI$矩阵,矩阵中的负值都替换为$0$,两者定义如下: $$ PMI_{w,c} = log(\frac{\sharp(w,c) \cdot \vert D \vert}{\sharp(w)\cdot \sharp(c)}) $$

$$ PPMI_{w,c} = \max(PMI_{w,c}, 0) $$

其中$\sharp()$表示出现次数,如$\sharp(w,c)$表示$w,c$在采用所得到的$PCO$矩阵中共同出现(在同一节点的$k$次转移所得向量中)的次数,$\vert D \vert = \sum_w \sum_c \sharp(w,c)$,表示$(w,c)$共同出现的总次数,于是可以将$PCO$矩阵转化为表示节点共现信息的$PPMI$矩阵

3. 自编码器

对于得到的$PPMI$矩阵,将其每一列作为输入数据,采用自编码器为处理结构,文中采取的不是普通版本自编码器,而是采用堆叠式降噪自编码器(SDAE),降噪指训练前,将数据按照概率将部分元素置为0,类似于正则化作用,自编码器结构比较简单,目标函数为: $$ \min_{\theta_1, \theta_2}\sum^n_{i=1} L(x^{(i)}, g_{\theta_2}(f_{\theta1} (\widetilde x^{(i)}))) $$ 其中$g,f$分别指解码、编码结构,$\widetilde x$指经过降噪处理过的输入数据。通过自编码器处理,学到到了中间层数据即为网络中节点的低维embedding表示,即最后结果。

总结

以上就是DNGR模型的PIPELINE,下图分别是算法描述、PIPELINE图解流程、分类实验可视化结果:



  1. Cao S, Lu W, Xu Q. Deep neural networks for learning graph representations[C]//Thirtieth AAAI conference on artificial intelligence. 2016. 

  2. Mikolov T, Sutskever I, Chen K, et al. Distributed representations of words and phrases and their compositionality[C]//Advances in neural information processing systems. 2013: 3111-3119. 

  3. Pennington J, Socher R, Manning C D. Glove: Global vectors for word representation[C]//Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). 2014: 1532-1543. 


Share this post
< Pre: [KDD2015]PTE Pos: 服务器机器学习、深度学习配置 >
418 comments
Similar posts
Add a new comment