五、DNGR

1. 虽然 DeepWalk 可以有效的学习无权图的顶点representation ，但是它存在两个缺点：

   • 获得vertex-context 的采样过程效率太低，且无法对带权图进行采样。

   • SGNS 等价于对 PPMI 矩阵进行矩阵分解，目前广泛使用的 SVD 本质是一种降维工具。

     事实上 SVD 是一种线性降维，无法捕获原始高维空间和representation 低维空间之间的非线性关系。Levy 也证明了：从 SVD 方法中学到的representation 不一定优于 PPMI 矩阵本身作为 representation（参考 word representation 章节）。

   针对这两个问题，论文 《Deep Neural Networks for Learning Graph Representations》 提出了 DNGR 模型，该模型主要做了两点改进：

   • 采用基于随机游走模型 random surfing model 来直接构建Graph 的结构信息，抛弃了基于随机游走random walk策略生成线性序列的方式。
   • 引入stacked denoising autoencoder:SDAE 堆叠式降噪自编码器来分解 PPMI 矩阵，从而进行非线性降维，从而捕获顶点之间的潜在复杂的非线性关系。

5.1 模型

1. 给定带权图 ，其中 为所有顶点集合， 为所有边的集合。 表示顶点 和 之间边的权重，如果顶点 和 之间不存在边则 。

2. 如GraRep 章节所示，可以证明 SGNS 等价于 PPMI 矩阵分解。

   

   其中：

   • 为所有观测到的 vertext-context 组合， 为它的数量
   • 为 中vertex 的数量， 为 中contex 的数量， 为 中vertex-contex 的数量
   • 为负采样过程中负样本数量

   如word representation 章节SGNS vs 矩阵分解 部分所示，可以对 PPMI 矩阵分解来获得每个顶点的 representation 。

   因此这里的关键是：

   • 如何生成 PPMI 矩阵
   • 如何分解 PPMI 矩阵

3. DNGR 模型主要包含三个部分：

   • 随机游走模型：该部分主要用于捕获图结构信息，并生成概率共现矩阵。
   • PPMI 矩阵：根据概率共现矩阵计算 PPMI 矩阵。
   • 堆叠式降噪自编码器：该部分主要用于执行非线性降维来获得顶点的低维 representation 。

   

4. 随机游走模型基于 PangeRank 模型。

   假设顶点 经过一步到达顶点 的概率为 ，定义转移矩阵为：

   

   考虑random surfing model：每个顶点以 的概率随机游走，但以 的概率返回源点并重启随机游走。

   考虑顶点 为源点：定义行向量 ，其中第 项表示顶点 经过 步转移之后到达顶点 的概率。则有递归公式：

   • 是一个one-hot 向量，其第 项为1、其它项为 0。
   • 

5. 堆叠式降噪自编码器用于对 PPMI 矩阵进行非线性降维。

   • 降噪自编码器：与常规自编码器不同，降噪自编码器在训练之前通过随机重置部分输入为零从而破坏输入数据，目标是最小化重建误差：

     

     其中 为平方误差； 为 的破坏形式； 为编码函数， 为对应参数； 为解码函数， 为对应参数； 为 sigmoid 函数，用于建模非线性关系。

     降噪自编码器能够有效降低噪音并提高鲁棒性。

     如上图中： 被破坏从而以红色突出显示。

   • 堆叠式：采用逐层训练的多层降噪自编码器来学习不同 level 上的 representation。作者认为：不同层学到的representation 代表了不同level 的抽象，网络层越高抽象层次越高。

     如上图中： 对应于原始输入， 对应于第一层 representation， 对应于第二层 representation

5.2 实验

1. 数据集：

   • 语言网络数据集20-Newsgroup ：包含2万篇新闻组文档，并按照20个不同的组分类。每篇文档由文档内单词的 tf-idf 组成的向量表示，并根据余弦相似度计算得到文档的相似度。根据文档的这些相似度构建语言网络，该网络是一个全连接的带权图，用于聚类效果的评估。

     为验证模型的鲁棒性，论文分别从3/6/9 个不同的新闻组构建了三个更小规模的语言网络(NG 代表 Newsgroups ）：

     • 3-NG：由comp.graphics, comp.graphics and talk.politics.guns 这三个新闻组的文档构成。
     • 6-NG：由 alt.atheism, comp.sys.mac.hardware, rec.motorcycles, rec.sport.hockey, soc.religion.christian and talk.religion.misc 这六个新闻组的文档构成。
     • 9-NG：由 talk.politics.mideast, talk.politics.misc, comp.os.ms- windows.misc, sci.crypt, sci.med, sci.space, sci.electronics, misc.forsale, and comp.sys.ibm.pc.hardware 这九个新闻组的文档构成。

     这些小网络分别使用所有文档 all data，以及每个主题随机抽取200 篇文档两种配置。

   • Wine 数据集：包含意大利同一地区种植的三种不同品种的葡萄酒化学分析的13种成分的数量（对应13各特征及其对应取值），数据包含 178个样本。

     论文将样本作为顶点、采用不同样本之间的余弦相似度作为边来构建Graph 。

   • 维基百科数据集：包含 2010 年 4 月的快照作为训练集，包含 2000 万条文章和 9.9 亿个 token 。

     由于 SVD 算法复杂性论文选择 1 万个最常见的单词构建词典。

2. 基准模型：

   • DeepWalk：使用截断的随机游走将图结构转化为线性结构，然后使用层次 softmax 的 SkipGram 模型处理序列。
   • SGNS：使用带负采样的 SkipGram模型。
   • PPMI：直接基于单词的共现来构建 PPMI 矩阵，并用顶点的 PPMI 信息构建顶点的稀疏、高维 representation 。
   • SVD：构建 PPMI矩阵，并通过 SVD 降维来获取顶点的低维 representation 。

3. 模型参数：

   • 随机游走序列长度 ，每个顶点开始的序列数量为 。

   • 对于 DeepWalk,SGNS ，负采样个数 ，上下文窗口大小为 。

   • 对于 DNGR：

     • 使用 dropout 缓解过拟合，dropout 比例通过调参来择优。

     • 所有神经元采用 sigmoid 激活函数。

     • 堆叠式降噪自编码器的层数针对不同数据集不同。

       

4. 论文在 20-NewsGroup 上执行聚类任务，该任务通过 K-means 对每个算法生成的顶点 representation 向量进行聚类，并以归一化互信息 normalized mutual information: NMI 作为衡量指标。

   每种算法随机执行10 次并报告平均结果。为了验证不同维度的影响，下面还给出了 DeepWalk,SGNS 在维度为 128、512 时的结果。

   结论：

   • 在 DeepWalk 和 SGNS 中，增加维度使得效果先提升后下降。

   • DNGR 明显优于其它基准算法。

     • 对比 DNGR 和 PPMI 可知，对于高维稀疏矩阵降维并提取有效信息可以提升效果。
     • 对比 SVD、PPMI可知，SVD 并不一定总是优于 PPMI。
     • 对比 DNGR、SVD 可知，DNGR 是一种更有效的降维方法。

   

5. 论文在 Wine 数据集上执行可视化任务，该任务采用 t-SNE 将 DNGR,SVD,DeepWalk,SGNS 输出的顶点representation 映射到二维空间来可视化。在二维空间中，相同类型的葡萄酒以相同颜色来展示。

   结论：在所有可视化结果中，DNGR 效果最好。

   

6. 论文在维基百科数据集上执行单词相似度任务，该任务直接从训练语料库中计算 word-context 组合因此不需要随机游走模型来生产 PPMI 矩阵。

   论文采用 Spearman’s rank correlation coefficient 来评估算法的结果。

   为了获得最佳结果，论文将 SGNS,DNGR,SVD 负采样的样本数分别设置为 5,1,1 。

   结论：

   • SVD,SGNS,DNGR 都比 PPMI 效果更好，这表明降维在该任务中的重要性。
   • DNGR 效果最好，超越了 SVD 和 SGNS ，这表明学习representation 时捕获非线性关系的重要性。

   

7. 论文在通过评估 20-NewsGroup 的逐层 NMI 值，验证了堆叠式降噪自编码器深层架构的重要性。