Question

1. 图是许多现实世界问题中用于信息管理的常见表达。例如，在 protein-protein interaction 网络中挖掘蛋白质复合物在同源蛋白质功能多样性的描述中起着重要作用，并提供有价值的演化洞察，这本质上是一个聚类问题。因此，开发自动化算法以从图中提取有用的深层信息至关重要。组织这类信息（它与潜在的大且复杂的图相关）的有效方法之一是学习 graph representation，它为图的每个顶点分配一个低维的稠密的向量 representation，从而对图传达的有意义的信息进行编码。

   最近，人们对学习 word embedding 的工作产生了浓厚的兴趣。他们的目标是从大量自然语言文本中，根据上下文为每个自然语言单词学习一个低维的向量 representation。这些工作可以被视为线性序列的 learning representation ，因为语料库由自然语言序列构成的线性结构组成。由此产生的紧凑的、低维的向量 representation 被认为能够捕获丰富的语义信息，并被证明可用于各种自然语言处理任务。虽然已经确定了学习线性结构的良好 representation 的有效方法，但是处理具有丰富拓扑的、通用的图结构更为复杂。为此，一种自然的方法是确定一种有效的转化方法：将学习通用图结构的 vertex representation 的任务转化为学习线性结构的 representation 的任务。

   DeepWalk 提出了一种思想，它通过称作截断的随机游走 truncated random walk 的均匀采样方法将无权图转换为线性序列的集合。在他们的方法中，采样的顶点序列刻画了图中顶点之间的连接。这一步可以理解为将通用的图结构转化为线性结构集合的过程。接下来，他们利用了 SkipGram 模型从这种线性结构中学习顶点的低维 representation。学到的顶点 representation 在一些任务中是有效的，并且优于先前的几种方法，如谱聚类spectral clustering 、以及 modularity 方法。

   虽然这种学习无权图的顶点 representation 的方法是有效的，但是仍然有两个重要问题有待回答：

   • 首先，对于加权图，如何更准确、更直接地捕获到图结构信息？
   • 其次，是否有更好的方法来表达线性结构的顶点？

   为了回答第一个问题，论文 《Deep Neural Networks for Learning Graph Representations》设计了一个适合加权图的随机冲浪模型 random surfing model ，它可以直接产生一个概率共现矩阵 probabilistic co-occurrence matrix 。这样的矩阵类似于通过从图中采样线性序列获得的共现矩阵，但是我们的方法不需要采样过程。

   使用带重启的 PageRank 来计算转移概率，并不具备创新性。

   为了回答第二个问题，论文 《Deep Neural Networks for Learning Graph Representations》 首先回顾了一种用于学习线性结构的顶点 representation 的现有方法。最近的一项研究 《Neural word embedding as implicit matrix factorization》 表明：使用负采样的 SkipGram 的目标函数，与分解由单词和它们上下文组成的一个 shifted positive pointwise mutual information: PPMI 矩阵有内在关系。具体而言，他们表明可以使用标准的奇异值分解 SVD 方法对 PPMI 矩阵进行因式分解，从而从分解的矩阵中导出 vertex/word representation。最近的方法 GraRep 已被证明在学习 graph representation 的任务上取得了良好的实验结果。然而，该方法采用 SVD 来执行线性降维，而没有探索更好的非线性降维技术。

   在论文 《Deep Neural Networks for Learning Graph Representations》 中，作者对 《Neural word embedding as implicit matrix factorization》 的工作给出了一个新的视角。作者认为：原始 PPMI 矩阵本身是图的显式 representation 矩阵，而 SVD 步骤本质上起到了降维 toolbox 的作用。虽然用于产生最终 word representation 的 SVD 步骤被证明是有效的，但是 《Improving distributional similarity with lessons learned from word embeddings》 也证明了使用 PPMI 矩阵本身作为 word representation 的有效性。有趣的是，正如《Improving...》 的作者所展示的，从 SVD 方法学到的 representation 不能完全胜过 PPMI 矩阵本身的 representation 。由于我们的最终目标是学习能够有效捕获图信息的良好顶点 representation，因此必须研究从 PPMI 矩阵中得到顶点 representation 的更好方法，其中可以捕获不同顶点之间潜在的、复杂的非线性关系。

   深度学习揭示了非线性的复杂现象建模的路径，它在不同领域有许多成功的应用，例如语音识别和计算机视觉。深度神经网络 DNN ，例如堆叠自编码器 stacked autoencoder，可以被视为从低级特征学习高级抽象的有效方法。该过程本质上执行降维，将数据从高维空间映射到低维空间。与基于 SVD 的降维方法不同（它通过线性投影从原始 representation 空间映射到具有较低秩的新空间），堆叠自编码器等深度神经网络可以学习高度非线性的投影。

   事实上，《Learning deep representations for graph clustering》 在聚类任务中使用稀疏自编码器 sparse autoencoder 来代替谱聚类 spectral clustering 的特征值分解eigenvalue decomposition 步骤，并取得了显著的改进。受他们工作的启发，论文 《Deep Neural Networks for Learning Graph Representations》 还研究了使用基于深度学习的替代方法从原始数据 representation 中学习低维 representation 的有效性。与他们的工作不同，这里的目标是学习通用图的顶点 representation ，而不是专门关注聚类任务。作者将深度学习方法应用于 PPMI 矩阵，而不是他们模型中使用的拉普拉斯矩阵。DeepWalk 已经证明前者有可能比后者产生更好的表现。为了增强模型的鲁棒性，作者还使用了堆叠降噪自编码器来学习多层 representation 。

   仅仅用非线性投影代替线性投影，并不具有创新性。

   作者称提出的模型为 deep neural networks for graph representation: DNGR。学到的 representation 可以视为能够输入到其它任务中的输入特征，例如无监督聚类任务和有监督分类任务。为了验证模型的有效性，作者进行了将学到的 representation 用于一系列不同任务的实验，其中考虑了不同类型和拓扑的现实世界网络。为了在考虑更简单、但是更大规模的实际图结构时证明 DNGR 模型的有效性，作者将 DNGR 模型应用于一个非常大的语言数据集，并在 word similarity 任务上进行了实验。在所有这些任务中， DNGR 模型优于其它 learning graph representation 方法，而且 DNGR 模型也可以简单地并行化。

   论文的主要贡献在两个方面：

   • 从理论上讲，作者认为深度神经网络的优势在于能够捕获图传递的非线性信息，而许多广泛使用的、传统的线性降维方法无法轻易地捕获此类信息。此外，作者认为论文的随机冲浪模型可用于取代广泛使用的传统采样方法来直接捕获图结构信息。
   • 根据实验，作者证明 DNGR 模型能够更好地学习加权图的低维顶点 representation，其中可以捕获图的有意义的语义信息semantic information 、关系信息relational information 、以及结构信息structural information 。作者表明，得到的 representation 可以有效地用作不同下游任务的特征。

5.1 背景和相关工作

1. 这里我们首先展示 DeepWalk 中提出的无权图的随机采样，从而说明将顶点 representation 转换为线性 representation 的可行性。然后我们考虑两种 word represenation 方法：带负采样的 SkigGram、基于 PPMI 矩阵的矩阵分解。这些方法可以视为从线性结构数据中学习 word representation 的线性方法。

2. 背景：给定加权图 $ G=(V,E) $ ，其中 $ V=\{v_1,v_2,\cdots,v_n\} $ 为顶点集合， $ E=\{e_{i,j}\} $ 为边集合，边 $ e_{i,j} = (v_i,v_j) $ 由两个顶点组成。在无权图中，二元的边权重表示两个顶点之间是否存在关系。相比之下，加权图中的边权重是个实数，表示两个顶点之间的相关程度。尽管加权图中的边权重可能为负，但是我们在本文中仅考虑非负权重。

   为了符号方便，我们在全文中也使用 $ w $ 和 $ c $ 来表示顶点。我们试图通过捕获图 $ G $ 的深层结构信息来获得顶点的 representation 矩阵 $ \mathbf R $ 。

3. DeepWalk：DeepWalk 提供了一种有效的方法，称作截断的随机游走 truncated random walk，从而将无权的图结构信息转换为表示顶点之间关系的线性序列。所提出的随机游走是一种适用于无权图的均匀采样方法：

   • 首先从图中随机选择一个顶点 $ v_1 $ ，并将其标记为当前顶点。
   • 然后从当前顶点 $ v_1 $ 的所有邻居中随机选择下一个顶点 $ v_2 $ 。现在，将这个新选择的顶点 $ v_2 $ 标记为当前顶点并重复这样的顶点采样过程。

   当一条序列中的顶点数量达到 $ \eta $ （称作游走长度 walk length ）的预设数时，算法终止。重复上述过程 $ \gamma $ 次（称作游走次数 total walk）后，我们得到线性序列的集合。

   虽然截断的随机游走是一种使用线性序列表达无权图结构信息的有效方法，但是该过程涉及缓慢的采样过程，并且超参数 $ \eta $ 和 $ \gamma $ 不易确定。我们注意到：DeepWalk 基于采样的线性序列产生了一个共现矩阵 co-occurrence matrix 。在下文中，我们描述了我们的随机冲浪模型random surfing model ，该模型直接从加权图中构建概率共现矩阵，从而避免了昂贵的采样过程。

4. SkipGram with negative sampling: SGNS：自然语言语料库由线性序列的 streams of words 组成。最近，神经嵌入方法 neural embedding method 和基于矩阵分解的方法已广泛应用于学习 word representation 。《Distributed representations of words and phrases and their compositionality》 提出的 SkipGram 模型已被证明是一种有效且高效的学习 word representation 的方法。改进 SkipGram 模型的两种值得注意的方法是负采样 skip-gram with negative sampling: SGNS 、以及 hierarchical softmax。在本文中，我们选择使用前一种方法。

   在 SGNS 中，采用噪声对比估计 noise contrastive estimation: NCE 方法（《A Fast and Simple Algorithm for Training Neural Probabilistic Language Models》）的简化变体来增强 SkipGram 模型的鲁棒性。SGNS 根据经验的 unigram word distribution 随机创建 negative pairs $ (w,c_N) $ ，并尝试使用低维向量表示每个单词 $ w\in V $ 和每个上下文单词 $ c\in V $ 。SGNS 的目标函数旨在最大化 positive pairs $ (w,c) $ 和最小化 negative pairs $ (w,c_N) $ ：

   $ \arg\max_{\mathbf{\vec w},\mathbf{\vec c}} \log \sigma\left(\mathbf{\vec w}\cdot \mathbf{\vec c}\right) + \lambda\times \mathbb E_{c_N\sim P_\mathcal D} \left[\log \sigma\left(-\mathbf{\vec w}\cdot \mathbf{\vec c}\right)\right] $

   其中：

   • $ \sigma(\cdot) $ 为 sigmoid 函数 $ \sigma(x) = 1/(1+ e^{-x}) $ 。
   • $ \lambda $ 为负样本数量。
   • $ \mathbb E_{c_N\sim p_\mathcal D}[\cdot] $ 为当负样本 $ c_N $ 从分布 $ p_\mathcal D $ 中采样时的期望。分布 $ p_\mathcal D(c) = \#(c)/|\mathcal D| $ 为均匀分布，#(c) 为上下文顶点 $ c $ 在数据集 $ \mathcal D $ 中出现的次数， $ |\mathcal D| $ 为数据集规模。
   • $ \mathbf{\vec w} $ 为顶点 $ w $ 的 representation 向量， $ \mathbf{\vec c} $ 为上下文顶点 $ c $ 的 context representation 向量。

5. PPMI 矩阵和 SVD：学习 graph representation （尤其是 word representation）的另一种方法是基于矩阵分解技术。这种方法基于全局共现计数 global co-occurrence counts 的统计数据来学习 representation，并且在某些预测任务中可以优于基于单独的局部上下文窗口 local context windows 的神经网络方法。

   矩阵分解方法的一个例子是超空间模拟分析 hyperspace analogue analysis，它分解 word-word 共现矩阵从而产生 word representation。这种方法和相关方法的一个主要缺点是：语义信息相对较小的高频词（例如停用词 stop words）对生成的 word representation 产生不成比例的影响 disproportionate effect 。《Word association norms, mutual information, and lexicography》 提出了 pointwise mutual information: PMI 矩阵来解决这个问题，并且已经被证明可以提供更好的 word representation：

   $ \text{PMI}_{w,c} = \log \left(\frac{\#(w,c)\times |\mathcal D|}{\#(w)\times \#(c)}\right) $

   其中： $ \#(\cdot) $ 表示数据集 $ \mathcal D $ 中出现的次数， $ |\mathcal D|=\sum_w\sum_c \#(w,c) $ 为所有 pair 的总样本量。

   进一步提高性能的方法是将每个负值调整为 0（详细信息参考论文 《Neural word embedding as implicit matrix factorization》），从而形成 PPMI 矩阵：

   $ \mathbf X_{w,c} = \max(\text{PMI}_{w,c},0) $

   其中 $ \mathbf X $ 为 PPMI 矩阵。

   尽管 PPMI 矩阵是一个高维矩阵，但是使用截断的 SVD 方法truncated SVD method 执行降维会产生关于 L2 损失的最佳秩 $ d $ 的分解。我们假设矩阵 $ \mathbf X $ 可以分解为三个矩阵： $ \mathbf X = \mathbf U\mathbf\Sigma\mathbf V^\top $ ，其中 $ \mathbf U\in \mathbb R^{n\times n},\mathbf V\in \mathbb R^{n\times n} $ 为正交矩阵， $ \mathbf \Sigma\in \mathbb R^{n\times n} $ 为对角矩阵（奇异值从大到小排列）。换言之：

   $ \mathbf X\sim \mathbf X_d = \mathbf U_d\mathbf \Sigma_d\mathbf V_d^\top $

   其中： $ \mathbf U_d\in \mathbb R^{n\times d} $ 为 $ \mathbf U $ 的最左侧的 $ d $ 列， $ \mathbf V_d \in \mathbb R^{n\times d} $ 为 $ \mathbf V $ 的最左侧的 $ d $ 列， $ \mathbf \Sigma_d\in \mathbb R^{d\times d} $ 为 $ \mathbf \Sigma $ 最左侧的 $ d $ 个奇异值（也是最大的 $ d $ 个奇异值）。根据 《Improving distributional similarity with lessons learned from word embeddings》，word representation 矩阵 $ \mathbf R\in \mathbb R^{n\times d} $ 可以为：

   $ \mathbf R = \mathbf U_d\left(\mathbf\Sigma_d\right)^{1/2},\quad\text{ or } \mathbf R=\mathbf U_d $

   PPMI 矩阵 $ \mathbf X $ 是 word representation 矩阵和 context 矩阵的乘积。SVD 过程为我们提供了一种从矩阵 $ \mathbf X $ 中找到矩阵 $ \mathbf R $ 的方法，其中 $ \mathbf R $ 的行向量是 word/vertex 的低维 representation，并且 $ \mathbf R $ 的行向量可以通过 $ \mathbf X $ 给出的高维 representation 的线性投影获得。我们认为这种投影不一定是线性投影。在这项工作中，我们研究了使用非线性投影方法通过使用深度神经网络来代替线性 SVD 的方法。

6. 深度神经网络：可用于学习 multiple level 的 feature representation 的深度神经网络在不同领域取得了成功。训练这样的网络被证明是困难的。一种有效的解决方案是使用贪心的逐层无监督预训练greedy layer-wise unsupervised pre-training 。该策略旨在一次学习一层的有用的 representation。然后将学到的low-level representation 作为下一层的输入，用于后续的 representation learning 。神经网络通常采用非线性激活函数（例如 sigmoid 或 tanh）来捕获从输入到输出的复杂非线性投影。

   为了训练涉及多层 feature representation 的深层架构，自编码器 autoencoder 已经成为常用的 building block 之一。自编码器执行两个操作：编码 encoding 、解码 decoding 。

   • 在编码步骤中，函数 $ f_{\theta_1}(\cdot) $ 应用于输入空间中的向量，并将其转换到新的特征空间。在这个过程中通常会涉及一个激活函数来对两个向量空间之间的非线性进行建模：输入向量空间，以及潜在向量 representation 的空间。
   • 在解码步骤中，重构函数 $ g_{\theta_2}(\cdot) $ 用于从潜在 representation 空间重构原始输入向量。

   让我们假设 $ f_{\theta_1}\left(\mathbf{\vec x}\right) = \sigma\left(\mathbf W_1\mathbf{\vec x} + \mathbf{\vec b}_1 \right) $ ，以及 $ g_{\theta_2}\left(\mathbf{\vec x}\right) = \sigma\left(\mathbf W_2\mathbf{\vec x} + \mathbf{\vec b}_2\right) $ ，其中： $ \sigma(\cdot) $ 为非线性激活函数， $ \theta_1=\left\{\mathbf W_1,\mathbf{\vec b}_1\right\} $ 为编码器的参数， $ \theta_2=\left\{\mathbf W_2,\mathbf{\vec b}_2\right\} $ 为解码器的参数。这里 $ \mathbf W_1,\mathbf W_2 $ 是转换输入空间的线性映射的权重， $ \mathbf{\vec b}_1,\mathbf{\vec b}_2 $ 为线性映射的 bias 向量。我们的目标是通过找到 $ \theta_1 $ 和 $ \theta_2 $ 来最小化以下重构损失函数：

   $ \mathcal L = \sum_{\mathbf{\vec x} \in \mathbb D} l\left(\mathbf{\vec x} , g_{\theta_2}\left(f_{\theta_1}\left(\mathbf{\vec x} \right)\right)\right) $

   其中 $ \mathbb D $ 为数据集， $ l(\cdot) $ 为单个样本的损失函数。

   堆叠自编码器 stacked autoencoder 是由多层的此类自编码器组成的多层深度神经网络。堆叠自编码器使用逐层训练方法来提取基本规律，从数据中逐层捕获不同 level 的抽象，其中更高层传递来自数据的更高 level 的抽象。

5.2 模型

2. 现在我们详细介绍我们的 DNGR 模型。如下图所示，该模型由三个主要步骤组成：

   • 首先，我们引入随机场冲浪模型 random surfing model 来捕获图结构信息并生成概率共现矩阵 probabilistic co-occurrence matrix。
   • 接下来，遵从 《Extracting semantic representations from word co-occurrence statistics: A computational study》，我们根据概率共现矩阵计算 PPMI 矩阵。
   • 最后，我们使用堆叠降噪自编码器 stacked denoising autoencoder 来学习低维的 vertex representation。

   下图的 SDAE 结构中， $ X_i $ 对应于输入数据、 $ Y_i $ 对应于第一层学到的 representation， $ Z_i $ 对应于第二层学到的 representation。临时破坏的节点（例如 $ X_2,X_5,Y_2 $ ） 以红色突出显示。

   

5.2.1 随机冲浪和上下文加权

1. 虽然有效，但是将图结构转换为线性序列的采样方法有一些弱点：

   • 首先，采样序列的长度是有限的。这使得很难为出现在采样序列边界处的顶点捕获正确的上下文信息。
   • 其次，确定某些超参数（例如游走长度 $ \eta $ 、游走次数 $ \gamma $ ）难以简单地确定，尤其对于大图。

   为了解决这些问题，我们考虑使用由 PangeRank 模型启发的随机冲浪模型 andom surfing model ，其中 PageRank 模型原本用于 ranking 任务。我们首先对图中的顶点进行随机排序。我们假设当前的顶点是第 $ i $ 个顶点，并且有一个转移矩阵 $ \mathbf A $ 来捕获不同顶点之间的转移概率 transition probability 。

   我们引入一个行向量 $ \mathbf{\vec p}_k $ ，它的第 $ j $ 项表示经过 $ k $ 步转移之后达到第 $ j $ 个顶点的概率。 $ \mathbf{\vec p}_0 $ 为初始的 1-hot 向量，它的第 $ i $ 项为 1 而其它所有项为 0 。我们考虑一个带重启的随机冲浪模型random surfing model with restart ：在每次，继续随机冲浪过程的概率为 $ \alpha $ ，返回原始顶点并重新开始的概率为 $ 1-\alpha $ ，其中 $ 0\le \alpha\le 1 $ 。这将导致以下递推关系：

   $ \mathbf{\vec p}_k = \alpha\times \mathbf{\vec p}_{k-1} \mathbf A + (1-\alpha)\times \mathbf{\vec p}_0 $

   如果我们假设过程中没有随机重启，则在恰好 $ k $ 步转移之后到达不同顶点的概率由以下公式指定：

   $ \mathbf{\vec p}_k^* = \mathbf{\vec p}_{k-1}^* \mathbf A = \mathbf{\vec p}_0 \mathbf A^k $

   如果我们考虑所有顶点开始的随机冲浪（而不仅仅是顶点 $ v_i $ 开始的），则有：

   $ \mathbf P_k^* = \mathbf I \mathbf A^k = \mathbf A^k\\ \mathbf P_k = \alpha \mathbf P_{k-1} \mathbf A + (1-\alpha ) \mathbf I $

   设最大的转移步数为 $ K $ ，则通过这种方式我们得到 PMI 矩阵：

   $ \text{PMI} = \sum_{k=1}^K \mathbf P_k $

2. 直觉上，两个顶点之间的距离越近，它们的关系就应该越紧密。因此，根据上下文节点和当前节点的相对距离来衡量上下文节点的重要性是合理的。在 word2vec 和 GloVe 中都实施了此类加权策略，并且发现对于获得良好的实验结果很重要（《Improving distributional similarity with lessons learned from word embeddings》）。基于这一事实，我们可以看到，理想情况下，第 $ i $ 个顶点的 representation 应该以如下方式构建：

   $ \mathbf{\vec r} = \sum_{k=1}^K w(k) \times \mathbf{\vec p}_k^* $

   其中 $ w(\cdot) $ 是一个单调递减函数（称作权重函数 weighting function），满足 $ w(t+1)\lt w(t) $ 。

   注意：PMI 的转移概率向量也可以视为顶点的某种 representation 。

   我们认为，基于上述随机冲浪过程构建顶点 representation 的以下方式（即 $ \mathbf{\vec r} = \sum_{k=1}^K \mathbf{\vec p}_k $ ）实际上满足了上述条件。事实上，可以证明：

   $ \mathbf{\vec p}_k = \alpha^k\mathbf{\vec p}_k^* + \sum_{t=1}^k \alpha ^{k-t}(1-\alpha) \mathbf{\vec p}_{k-t}^* $

   其中 $ \mathbf{\vec p}_0^* = \mathbf{\vec p}_0 $ 。则 $ \mathbf{\vec r} $ 中 $ \mathbf{\vec p}_t^* $ 的系数为：

   $ w(t) = \alpha^t + \alpha^t(1-\alpha)(K-t) $

   当满足 $ 0\lt \alpha\lt 1 $ 时， $ w(t) $ 是一个单调递减函数。

   另外，SkipGram 中的 $ w(t) $ 函数为：

   $ w^\prime(t) = -\frac{t}{K} + \left(1+\frac{1}{K}\right) $

   而 GloVe 中的 $ w(t) $ 函数为：

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

   如下图所示，所有权重函数 $ w(t) $ 都是单调递减的。图中纵轴是分配给上下文节点的权重，横轴是上下文顶点和当前顶点之间的距离。

   因此，与 word2vec 和 GloVe 类似，我们的模型还允许根据上下文到 target 的距离从而对上下文信息进行不同的加权。这在之前被证明对于构建良好的 word representation 很重要。我们将通过实验评估这方面的重要性。

   

5.2.2 堆叠降噪自编码器

1. 我们的研究旨在钻研从 PPMI 矩阵构建顶点的高质量低维向量 representation，其中 PPMI 矩阵传递了图的基本结构信息。SVD 过程虽然有效，但是它本质上只产生从 PPMI 矩阵所包含的高维向量 representation 到最终低维向量 representation 的线性变换。我们相信可以在两个向量空间之间构建潜在的非线性映射。因此，我们使用堆叠降噪自编码器 stacked denosing autoencoder （一种用于深度学习的流行模型）从原始高维顶点向量 representation 生成压缩的低维顶点向量 representation 。

   我们首先初始化神经网络的参数，然后我们使用贪心的逐层训练 greedy layer-wise training 策略来学习每一层的high-level 抽象。为了增强 DNN 的鲁棒性，我们使用了堆叠降噪自编码器 stacked denoising autoencoder: SDAE 。与传统的自编码器不同，降噪自编码器会在进行训练之前部分破坏输入数据。具体而言，我们通过将输入向量中的一些位置以一定概率设置为 0 来随机破坏每个输入样本 $ \mathbf{\vec x} $ （它是一个向量）。这个想法类似于在矩阵补全 matrix completion 任务中对缺失项进行建模，其目标是利用数据矩阵中的规律性在某些假设下有效地恢复完整矩阵。与标准的自编码器类似，我们从潜在 representation 中重建数据。换句话讲，我们对以下目标感兴趣：

   $ \min_{\theta_1,\theta_2} \sum_{\mathbf{\vec x} \in \mathbb D} l\left(\mathbf{\vec x} , g_{\theta_2}\left(f_{\theta_1}\left(\tilde{\mathbf{\vec x} }\right)\right)\right) $

   其中 $ \tilde{\mathbf{\vec x} } $ 是 $ \mathbf{\vec x} $ 的破坏的版本， $ l(\cdot,\cdot) $ 为标准的平方误差。

2. SDAE 算法：

   • 输入：

     • PPMI 矩阵 $ \mathbf X $
     • SDAE 层数 $ \Gamma $

   • 输出：顶点的 representation 矩阵 $ \mathbf R $

   • 算法步骤：

     • 初始化第一层的 input $ \mathbf X^{(1)} = \mathbf X $

     • 贪心逐层训练，步骤为： $ \text{ for } j=2,\cdots,\Gamma $ ：

       • 基于 input $ \mathbf X^{(j)} $ 来构建单隐层的 SDAE
       • 学习隐层 representation $ \mathbf H^{(j)} $
       • 隐层的输出作为 $ \mathbf X^{(j+1)} $

     最后一层隐层的 representation $ \mathbf H^{(\Gamma)} $ 作为顶点的 representation 矩阵 $ \mathbf R $ 。

5.2.3 DNGR 模型的讨论

1. 这里我们分析以下 DNGR 的优势，其实验有效性将在实验部分介绍。

   • 随机冲浪策略：如前所述，随机冲浪过程克服了以前工作中的采样程序相关的限制，并且为我们提供了某些所需的属性。这些属性是以前的 embedding 模型 （例如 word2vec 和 GloVe ）所具备的。

     随机冲浪策略涉及计算 PMI 矩阵，其计算复杂度太高（ $ O(|V|^2 ) $ ）。

   • 堆叠策略：堆叠结构提供了一种平滑的降维方式。我们相信在深度架构的不同层上学习的 representation 可以为输入数据提供不同 level 的有意义的抽象。

   • 降噪策略：高维输入数据通常包含冗余信息和噪声。我们相信降噪策略可以有效地降低噪声并增强鲁棒性。

   • 效率：根据之前的分析，DNGR 中使用自编码器来推断，在顶点数量方面，比基于 SVD 的矩阵分解方法具有更低的时间复杂度。SVD 的时间复杂度至少是顶点数量的二次方。然而，DNGR 的推断时间复杂度与图中的顶点数量呈线性关系。

     但是在训练效率方面，DNGR 和 SVD 都需要计算 PPMI 矩阵，二者都是 $ O(|V|^2) $ 计算复杂度。

5.3 实验

1. 为了评估 DNGR 模型的性能，我们在真实数据集上进行了实验。除了展示 graph representation 的结果以外，我们还评估了从自然语言语料库（它由线性序列组成）中学习的 word embedding 的有效性。

2. 数据集：

   • 语言网络数据集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 这九个新闻组的文档构成。

     这些小网络分别对每个主题随机抽取200 篇文档。

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

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

   • 维基百科语料库：包含 2010 年 4 月的快照作为训练集，包含 2000 万条文章和 9.9 亿个 token 。由于 SVD 算法复杂性，我们选择 1 万个最常见的单词构建词典。

     为了评估每个算法生成的 word representation 的性能，我们在四个数据集上进行了 word similarity 实验，包括流行的 WordSim353、WordSim Similarity、WordSim Relatedness 、MC 四个数据集。所有这四个数据集都有 word pairs 以及人工分配的相似性。

   注意，这里得到的 graph 都是根据节点相似性来构建的，因此并不是天然的图结构。这种数据集作为 benchmark 可能不太科学，因为稍微不同的图构建方式可能导致完全不同的评测结果。

3. baseline 方法：我们考虑以下四个 baseline 方法：

   • DeepWalk：使用截断的随机游走truncated random walk 将图结构转化为线性结构，然后使用 hierarchical softmax 的 SkipGram 模型处理序列。
   • SGNS：使用带负采样的 SkipGram模型。它已被证明是从理论上和经验上学习 word representation 的有效模型。
   • PPMI：是信息论中经常使用的度量。该方法直接基于单词的共现来构建 PPMI 矩阵，并用顶点的 PPMI 信息构建顶点的稀疏、高维 representation 。
   • SVD：是一种常用的矩阵分解方法，用于降维或提取特征。我们使用 SVD 来压缩 PPMI 矩阵从而获取顶点的低维 representation 。

4. 参数配置：

   • 随机游走序列长度 $ \eta = 40 $ ，每个顶点开始的序列数量为 $ \gamma = 80 $ 。

   • 对于 DeepWalk, SGNS ，负采样个数 $ \lambda = 5 $ ，上下文窗口大小为 $ K=10 $ 。

   • 对于 DNGR：

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

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

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

       

5. 20-NewsGroup 数据集上的聚类任务：该任务通过 K-means 对每个算法生成的顶点 representation 向量进行聚类，并以归一化互信息 normalized mutual information: NMI 作为衡量指标。每种算法随机执行10 次并报告平均结果。为了验证不同维度的影响，下面还给出了 DeepWalk,SGNS 在维度为 128、512 时的结果。

   结论：

   • 我们的 DNGR 模型明显优于其它 baseline 方法，尤其是当 $ \alpha = 0.98 $ 时。

     当 $ \alpha=1 $ 时，上下文信息不会根据它们的距离进行加权，我们得到较差的结果。这证明了前面讨论的上下文加权策略的重要性。

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

   • 比较 DNGR 和 PPMI ，效果的提升证明了对于高维稀疏矩阵降维并提取有效信息的好处。

   • 在相同的 $ \alpha $ 设置下，DNGR 始终比 SVD 效果更好。这为我们之前的讨论提供了实验证据：DNGR 是一种比 SVD 更有效的降维方法。

   

6. Wine 数据集上的可视化任务：该任务采用 t-SNE 将 DNGR,SVD,DeepWalk,SGNS 输出的顶点representation 映射到二维空间来可视化。在二维空间中，相同类型的葡萄酒以相同颜色来展示。在相同设置下，不同类型葡萄酒之间具有更清晰边界的聚类意味着更好的 representation 。

   结论：

   • DeepWalk 和 SGNS 的可视化显示不清晰的边界和分散的簇。
   • DNGR （ $ \alpha = 1 $ ）要好得多。虽然 SVD 优于 DNGR （ $ \alpha = 1 $ ），但是在结果中我们可以看到绿色的点仍然与一些红色的点混合在一起。
   • DNGR （ $ \alpha = 0.98 $ ）效果最好。我们可以看到不同颜色的点出现在 3 个独立的区域，并且大多数相同颜色的点聚集在一起。

   

7. Word Similarity任务：我们在维基百科语料库上执行单词相似度任务，该任务直接从训练语料库中计算 word-context 组合因此不需要随机冲浪模型来生产 PPMI 矩阵。我们采用 Spearman’s rank correlation coefficient 来评估算法的结果。为了获得最佳结果，我们将 SGNS,DNGR,SVD 负采样的样本数分别设置为 5,1,1 。

   结论：

   • DNGR 的性能优于其它 baseline 方法。
   • SVD,DNGR 都比 PPMI 效果更好，这表明降维在该任务中的重要性。
   • DNGR 超越了 SVD 和 SGNS ，这表明学习representation 时捕获非线性关系的重要性，并说明了使用我们的深度学习方法学习更好抽象的能力。

   

8. 深度结构的重要性：为了理解深层结构的必要性，我们进一步度量了 20-NewsGroup 数据集的 layerwise NMI 值。对于 3NG 和 6NG，我们使用 3 层神经网络，对于 9NG 我们使用 4 层神经网络。

   从结果中我们可以看到：从浅层到深层，这三个网络的性能总体而言都在提升。这证明了深层结构的重要性。