Question

1. 在许多实际问题中，信息通常是使用图来组织的。例如，在社交网络研究中，基于社交图 social graph 将用户分类为有意义的社交群组 social group 在很多实际 application 中有用，例如用户搜索 user search、定向广告 targeted advertising、以及推荐 recommendation 。因此，从图中准确地学习有用的信息至关重要。一种策略是学习图的 graph representation：图中的每个顶点都用一个低维向量来表达，这个低维向量可以准确地捕获图所传达的语义信息semantic information 、关系信息 relational information 、以及结构信息 structural information 。

   最近，人们对从数据中学习 graph representation 的兴趣激增。例如，最近的一个模型 DeepWalk 使用均匀采样（也称作截断的随机游走truncated random walk ）将图结构转换为由顶点组成的线性序列的样本集合。SkipGram 模型最初设计用于从线性序列中学习 word representation，也可用于从此类样本（即顶点组成的线性序列的样本）中学习顶点的 representation 。尽管这种方法在经验上是有效的，但是人们并不清楚在学习过程中所涉及的、图上定义的、确切exact 的损失函数是什么。

   在论文 《GraRep: Learning Graph Representations with Global Structural Information》 中，作者首先提出了在图上定义的 SkipGram 模型的显式损失函数。论文表明：本质上，我们可以使用 SkipGram 模型以不同的 $ k $ 值来捕获图中每个顶点与其 k-step 邻居之间的 k-step 关系（ $ k=1,2,\cdots $ ）。 SkipGram 模型的一个缺陷是：它将所有这些 k-step 关系信息投影到一个公共子空间中。论文认为，这种简单的处理可能会导致潜在的问题。通过在不同的子空间中保存不同的 k-step 关系信息，论文提出的模型 GraRep 克服了上述限制。

   最近人们提出的另一个工作是 LINE，它有一个损失函数来同时捕获 1-step 局部关系信息 local relational information 和 2-step 局部关系信息。为了捕获此类局部信息中的某些复杂关系，他们还从此类数据中学习非线性变换（LINE 用到了 sigmoid 函数，但是本质上 LINE 是广义线性函数）。虽然他们的模型不能很容易地扩展到捕获 k-step （ $ k\gt 2 $ ）关系信息来学习他们的 graph representation，但是他们提出了一个重要策略来提高模型的效果：对于 degree 较小的顶点，考虑高阶邻域。这一策略在某种程度上隐式地将某些 k-step 信息捕获到他们的模型中。GraRep 的作者相信：对于不同的 k 值，不同顶点之间的 k-step 关系型信息揭示了与图相关的、有用的全局结构信息，并且在学习良好的 graph representation 时显式地充分利用这一点至关重要。

   在论文 《GraRep: Learning Graph Representations with Global Structural Information》 中，作者提出了 GraRep，这是一种为知识管理 knowledge management 学习 graph representation 的新模型。该模型通过操作在图中定义的、不同的全局转移矩阵global transition matrix，直接从图中的顶点中捕获具有不同 $ k $ 值的、不同 k-step 关系信息，而不涉及缓慢 slow 的、复杂 complex 的采样过程。与现有工作不同， GraRep 模型定义了不同的损失函数来捕获不同的 k-step 局部关系信息（即不同的 $ k $ ）。论文使用矩阵分解 matrix factorization 技术优化每个模型，并通过组合从不同模型中学到的不同 representation 来构建每个顶点的全局 representation 。这种学到的全局 represetnation 可以用作下游任务的特征。

   论文对 GraRep 模型进行了正式的处理 formal treatment ，并展示了 GraRep 模型与之前几个模型之间的联系。论文还通过实验证明了学到的 representation 在解决几个现实世界问题中的有效性。具体而言，论文对语言网络聚类任务、社交网络多标签分类任务、以及引文网络可视化任务进行了实验。在所有这些任务中，GraRep 优于其它 graph representation 方法，从而证明了 GraRep 学到的全局 representation 可以有效地用作聚类、分类、可视化等任务的特征。并且， GraRep 可以简单地并行化。

   论文贡献如下：

   • 论文引入了一种新模型来学习图上顶点的潜在 representation，该模型可以捕获与图相关的全局结构信息。

   • 论文从概率的角度提供了对 DeepWalk 中用于学习 graph representation 的均匀采样方法的理解，该均匀采样方法将图结构转换为线性序列。

     此外，论文在图上显式定义了 DeepWalk 的损失函数，并将其扩展为支持加权图。

   • 论文正式分析了带有负采样 SkipGram 模型（skip-gram model with negative sampling: SGNS）相关的缺陷。论文的模型定义了一个更准确 accurate 的损失函数，该损失函数允许集成不同局部关系信息的非线性组合。

2. 相关工作：

   • 线性的序列representation方法 Linear Sequence Representation Method：由单词的 stream 组成的自然语言语料库可以视为一种特殊的图结构，即线性链linear chain 。目前，学习 word representation 有两种主流方法：神经嵌入neural embedding 的方法、基于矩阵分解matrix factorization based 的方法。

     • 神经嵌入方法采用固定长度的滑动窗口捕获当前单词的 context words。人们提出了像 SkipGram 这样的模型，这些模型提供了一种学习 word representation 的有效方法。虽然这些方法可能会在某些任务上产生良好的性能，但是它们不能很好地捕获有用的信息，因为它们使用独立的、局部的上下文窗口，而不是全局共现计数 global co-occurrence count 。

     • 另一方面，矩阵分解方法可以利用全局统计。先前的工作包括潜在语义分析 Latent Semantic Analysis: LSA，该方法分解 term-document 矩阵从而产生潜在语义representation。

       《Producing high-dimensional semantic spaces from lexical co-occurrence》 提出了 Hyperspace Analogue to Language: HAL，它分解一个 word-word 共现计数矩阵来生成 word representation。

       《Extracting semantic representations from word co-occurrence statistics: A computational study》 提出了用于学习 word representation 的、shifted positive Pointwise Mutual Information: PMI 矩阵的矩阵分解，并表明带负采样的 SkipGram 模型（Skip-Gram model with Negative Sampling: SGNS）可以视为隐式的这样的一个矩阵。

   • 图表示Graph Representation 方法：存在几种学习低维 graph representation 的经典方法，如多维缩放 multidimensional scaling: MDS、IsoMap、LLE、Laplacian Eigenmaps。

     最近，《Relational learning via latent social dimensions》 提出了学习图的潜在 representation 向量的方法，然后可以用于社交网络分类。

     《Distributed large-scale natural graph factorization》 提出了一种图分解方法，该方法使用随机梯度下降来优化大型图中的矩阵。

     《Deepwalk:Online learning of social Representations》 提出了DeepWalk 方法，该方法通过使用截断的随机游走算法将图结构转换为多个线性的顶点序列，并使用 SkipGram 模型生成顶点的 representation。

     《Line: Large-scale information network embedding》 提出了一种大规模信息网络的 embedding ，它优化了一个损失函数从而可以在学习过程中同时捕获 1-step 关系信息和 2-step 关系信息。

3.1 模型

3.1.1 图及其 Representation

1. 给定一个图 $ G=(V,E) $ ，其中 $ V=\{v_1,v_2,\cdots,v_{|V|}\} $ 为顶点集合， $ |V| $ 为顶点数量， $ E=\{e_{i,j}\} $ 为边集合。路径 path 定义为连接一个顶点序列的边序列。

   • 邻接矩阵：定义邻接矩阵为 $ \mathbf S $ 。

     • 对于无权图，如果顶点 $ v_i $ 到 $ v_j $ 之间存在边，那么 $ S_{i,j} = 1 $ ，否则 $ S_{i,j} = 0 $ 。
     • 对于带权图， $ S_{i,j} $ 为顶点 $ v_i $ 到 $ v_j $ 之间边的权重。

     尽管边的权重可以为负值，但是这里我们仅考虑正的权重。

   • 度矩阵degree matrix：定义度矩阵 degree matrix 为 $ \mathbf D $ ，其中：

     $ D_{i,j} =\begin{cases} \sum_{p} S_{i,p},& i = j\\ 0,&i\ne j \end{cases} $

   • 转移概率矩阵 probability transition matrix：假设我们想要捕获从一个顶点到另一个顶点的转移，并假设顶点 $ v_i $ 转移到顶点 $ v_j $ 的概率正比于 $ S_{i,j} $ ，则定义转移概率矩阵 probability transition matrix： $ \mathbf A = \mathbf D^{-1}\mathbf S $ 。其中 $ A_{i,j} $ 定义了从顶点 $ v_i $ 经过一步转移到顶点 $ v_j $ 的概率，因此也称为一阶转移概率矩阵。显然 $ \mathbf A $ 可以认为是对 $ \mathbf S $ 按 ”行“ 进行的归一化。

2. 带全局结构信息的 graph representation：给定一个图 $ G $ ，学习带全局结构信息的 graph representation的任务旨在学习图的全局 represetation 矩阵 $ \mathbf W\in \mathbb R^{|V|\times d} $ ，其中第 $ i $ 行 $ \mathbf{\vec w}_i\in \mathbb R^d $ 为图 $ G $ 中顶点 $ v_i $ 的 $ d $ 维向量，并且这些 representation 向量可以捕获图的全局结构信息global structural information 。

   在本文中，全局结构信息有两个功能：捕获两个不同顶点之间的长距离关系、根据不同的转移 steps 考虑不同的链接。我们将在后面进一步地说明。

3. 正如我们之前讨论过的，我们认为在构建这样的全局 graph representation 时需要从图中捕获 k-step （具有不同的 $ k $ ）的关系信息。为了验证这一点，下图给出了一些说明性的示例，展示了需要在两个顶点 A1 和 A2 之间捕获的、 k-step （其中 $ k=1,2,3,4 $ ） 的关系信息的重要性。图中，粗线表示两个顶点之间的关系较强、细线表示两个顶点之间的关系较弱。

   • 在 (a) 和 (e) 中显示了捕获彼此直接连接的、顶点之间简单的 1-step 信息的重要性，其中 (a) 具有较强的关系，(e) 具有较弱的关系。

   • 在 (b) 和 (f) 中显示了 2-step 信息，其中 (b) 中两个顶点A1 和 A2 共享许多共同的邻居，而 (f) 中两个顶点A1 和 A2 仅共享一个邻居。

     显然，2-step 信息对于捕获两个顶点之间的连接强度很重要：顶点之间共享的共同邻居越多，则它们之间的关系就越强。

   • 在 (c) 和 (g) 中显示了 3-step 信息。具体而言：

     • 在 (g) 中，尽管 A1 和 B 之间的关系很强，但是由于连接 B 和 C、以及 C 和 A2 的两条较弱的边，A1 和 A2 之间的关系可能会减弱。
     • 相比之下，在 (c) 中，A1 和 A2 之间的关系仍然很强，因为 B 和 A2 之间有大量的共同邻居，这加强了它们的关系。

     显然，在学习具有全局结构信息的良好 graph representation 时，必须捕获此类 3-step 信息。

   • 类似地，如 (d) 和 (h) 所示，4-step 信息对于揭示图的全局结构特性也至关重要。在 (d) 中，A1 和 A2 之间的关系明显很强。而在 (h) 中，A1 和 A2 明显不相关，因为从一个顶点到另一个顶点之间不存在路径。在缺乏 4-step 关系信息的情况下，无法捕获这种重要的区别important distinction 。

   

4. 我们还认为：在学习 graph representation 时，必须区别对待不同的 k-step 信息。我们在下图的 (a) 中展示了一个简单的例子。让我们专注于学习图中顶点 A 的 representation。可以看到，A 在学习其 representation 时接收到两种类型的信息：来自顶点 B 的 1-step 信息、以及来自顶点 C 的 2-step 信息。

   我们注意到，如果我们不区分这两种不同类型的信息，我们可以构建如图 (b) 所示的替代品，其中顶点 A 接受与 (a) 完全相同的信息。但是，图 (b) 具有完全不同的结构。

   这意味着如何使用 k-step 信息很重要，它们位于不同的子空间，应该区别对待。

   

5. 在本文中，我们提出了一种用于学习准确 graph representation 的新的框架，它集成了各种 k-step 信息，这些信息共同捕获了与图相关的全局结构信息。

3.1.2 图上的损失函数

1. 我们将在这里讨论用于学习具有全局结构信息的graph representation 的损失函数。对于图 $ G $ ，考虑两个顶点 $ w $ 和 $ c $ 。为了学习全局 representation 来捕获它们之间的关系，我们需要了解这两个顶点之间的连接强度。

   让我们从几个问题开始。是否存在从顶点 $ w $ 到顶点 $ c $ 的路径？如果存在，那么假设我们随机采样一条从顶点 $ w $ 开始的路径，我们到达顶点 $ c $ 的可能性有多大？

   为了回答这些问题，我们首先令 $ p_k(c\mid w) $ 表示从顶点 $ w $ 刚好通过 $ k $ 步到达顶点 $ c $ 的转移概率。我们已经知道了 1-step 转移概率（即矩阵 $ \mathbf A $ ），为了计算 k-step 转移概率，我们引入 k-step 转移概率矩阵 probability transition matrix ：

   $ \mathbf A^k =\underbrace{ \mathbf A\cdots\mathbf A}_{k} $

   可以看到 $ A_{i,j}^k $ 表示从顶点 $ i $ 刚好通过 $ k $ 步到达顶点 $ j $ 的转移概率。这直接得到 $ p_k(c\mid w) = A_{w,c}^k $ ，其中 $ A_{w,c}^k $ 为矩阵 $ \mathbf A^k $ 的第 $ w $ 行、第 $ c $ 列的元素。

2. 现在考虑一个给定的 $ k $ 。给定一个图 $ G $ ，考虑从顶点 $ w $ 开始到顶点 $ c $ 结束、并且长度为 k-step 的所有路径的集合。这里我们称 $ w $ 为 current vertex、 $ c $ 为 context vertex。我们的目标旨在最大化：这些 pair 来自图中的概率、以及其它 pair 不来自图中的概率。

   受到 SkipGram 模型的启发，我们采用了 《Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics》 提出的噪声对比估计 noise contrastive estimation: NCE 来定义我们的目标函数。遵循 《Neural word embedding as implicit matrix factorization》 中提出的类似讨论，我们首先介绍我们在图上定义的 k-step 损失函数为：

   $ \mathcal L_k = \sum_{w\in V} L_k(w)\\ L_k(w) = \left(\sum_{c\in V}p_k(c\mid w)\log\sigma\left(\mathbf{\vec w}\cdot \mathbf{\vec c}\right)\right) + \lambda \mathbb E_{c^\prime \sim p_k(V)}\left[\log\sigma\left(-\mathbf{\vec w}\cdot \mathbf{\vec c}^\prime \right)\right] $

   其中：

   • $ p_k(c\mid w) $ 描述了顶点 $ w $ 和顶点 $ c $ 之间的 k-step 关系，即从顶点 $ w $ 到顶点 $ c $ 的 k-step 转移概率。
   • $ \sigma(\cdot) $ 为 sigmoid 函数，定义为 $ \sigma(x) = 1/(1+\exp(x)) $ 。
   • $ \mathbf{\vec w} $ 表示顶点 $ w $ 作为 current vertex 时的 representation， $ \mathbf{\vec c} $ 表示顶点 $ c $ 作为 context vertex 时的 representation 。二者采用了不同的 representation 矩阵。
   • $ \lambda $ 为超参数，表示负样本的数量。
   • $ p_k(V) $ 为 k-step 负采样分布， $ \mathbb E_{c^\prime\sim p_k(V)}[\cdot] $ 表示当 $ c^\prime $ 服从分布 $ p_k(V) $ 时的期望值， $ c^\prime $ 是从负采样中获得的负样本。

   上式物理意义：

   • 第一项为 “正样本” 的加权对数似然，权重为 k-step 转移概率，“正样本”为从顶点 $ w $ 所有经过 k-step 能够到达的顶点集合。
   • 第二项为 “负样本”的对数似然。这里负样本没有加权。

   和 DeepWalk 相比，GraRep 的重要区别在于它对正样本进行了加权。

   期望部分可以重写为：

   $ \mathbb E_{c^\prime \sim p_k(V)}\left[\log\sigma\left(-\mathbf{\vec w}\cdot \mathbf{\vec c}^\prime \right)\right] = \sum_{c^\prime \in V} p_k(c^\prime ) \times \log\sigma(-\mathbf{\vec w}\cdot \mathbf{\vec c}^\prime ) $

   因此对于特定的顶点 pair 对 $ (w,c) $ ，定义其局部损失函数local loss为：

   $ l_k(w,c) = p_k(c\mid w)\times \log\sigma\left( \mathbf{\vec w}\cdot \mathbf{\vec c} \right) +\lambda \times p_k(c)\times \log\sigma\left(-\mathbf{\vec w}\cdot \mathbf{\vec c} \right)\\ L_k(w) = \sum_{c\in V}l_k(w,c) $

   其物理意义为：

   • 对于从 $ w $ 经过 k-step 到达的顶点 $ c $ ，其损失为作为正样本的加权对数似然（权重为 k-step 转移概率），加上作为负样本的加权对数似然（权重为 k-step 采样概率）。
   • 对于从 $ w $ 无法经过 k-step 到达的顶点 $ c $ ，其损失为作为负样本的加权对数似然（权重为 k-step 采样概率）。

   k-step 负采样分布 $ p_k(c) $ 可以计算为：

   $ p_k(c) = \sum_{w^\prime}q(w^\prime) p_k(c\mid w^\prime) = \frac {1} {|V|} \sum_{w^\prime} A_{w^\prime,c}^k $

   其物理意义为：以概率 $ q(\cdot) $ 随机选择一个顶点，然后经过 k-step 转移到顶点 $ c $ 的概率。这里 $ q(w^\prime) $ 是选择 $ w^\prime $ 作为路径中第一个顶点的概率，我们假设它服从均匀分布，即 $ q(w^\prime) = 1/|V| $ 。因此得到：

   $ l_k(w,c)=A_{w,c}^k\times \log\sigma\left( \mathbf{\vec w}\cdot \mathbf{\vec c}\right )+ \frac{\lambda}{|V|}\times \left(\sum_{w^\prime}A^k_{w^\prime,c}\right)\times \log\sigma\left(-\mathbf{\vec w}\cdot \mathbf{\vec c} \right) $

   则 k-step 损失函数为：

   $ \mathcal L_k = \sum_{w\in V}\sum_{c\in V} l_k(w,c) $

   为最小化 $ \mathcal L_k $ 则只需要最小化每个成分，即求解： $ \min l_k(w,c) $ 。令 $ e= \mathbf{\vec w}\cdot \mathbf{\vec c} $ ，求解：

   $ \frac{\partial }{\partial e} l_k(w,c) = 0 $

   得到最优解：

   $ e= \mathbf{\vec w}\cdot \mathbf{\vec c} = \log\left(\frac{A^k_{w,c}}{\sum_{w^\prime}A^k_{w^\prime,c}}\right) -\log(\beta) $

   其中 $ \beta = \frac{\lambda }{|V|} $ 。

   可以得到结论：我们本质上需要将矩阵 $ \mathbf Y $ 分解为两个矩阵 $ \mathbf W\in \mathbb R^{|V|\times d} $ 和 $ \mathbf C $ ，其中 $ \mathbf W $ 的每一行和 $ \mathbf C\in \mathbb R^{|V|\times d} $ 的每一行分别由顶点 $ w $ 和顶点 $ c $ 的向量 representation 组成。其中矩阵 $ Y $ 的元素定义为：

   $ Y_{i,j}^k = \log\left(\frac{A^k_{w,c}}{\sum_{w^\prime}A^k_{w^\prime,c}}\right) -\log(\beta) $

   现在我们已经定义了我们的损失函数，并表明优化该损失函数本质上涉及到矩阵分解问题。

3. 在这项工作中，我们为每条路径设置最大长度。换句话讲，我们假设 $ 1\le k\le K $ 。实际上，当 $ k $ 足够大时，转移概率会转移到某些固定值。

3.1.3 矩阵分解的最优化

1. 遵从 《Neural word embedding as implicit matrix factorization》 的工作，为了降低噪音，我们将 $ \mathbf Y^k $ 中的所有负数都替换为 0 。因为若存在负数，则图中存在的 $ k $ 阶顶点pair 对的概率 $ \sigma(\mathbf{\vec w}\cdot \mathbf{\vec c}) \lt \frac 12 $ 。这使得我们得到一个正的 k-step 概率矩阵 $ \mathbf X^k $ ，其中：

   $ X_{i,j}^k = \max\left(Y_{i,j}^k,0\right) $

   虽然存在各种矩阵分解技术，但是在这项工作中，由于其简单性，我们将重点放在流行的奇异值分解 singular value decomposition: SVD 方法上。SVD 已经在多个矩阵分解任务中取得成功，被认为是可用于降维的重要方法之一。

   对于矩阵 $ \mathbf X^k\in \mathbb R^{|V|\times |V|} $ ，SVD 分解为：

   $ \mathbf X^k = \mathbf U^k\mathbf \Sigma^k(\mathbf V^k)^\top $

   其中：

   • $ \mathbf U^k\in \mathbb R^{|V|\times |V|},\mathbf V^k\in \mathbb R^{|V|\times |V|} $ 均为正交矩阵。
   • $ \mathbf \Sigma^k\in \mathbb R^{|V|\times |V|} $ 为对角矩阵，对角线元素为按降序排列的矩阵奇异值。

   我们可以用 $ \mathbf X_d^k\in \mathbb R^{|V|\times |V|} $ 来近似原始的矩阵 $ \mathbf X^k $ ，即：

   $ \mathbf X^k\simeq \mathbf X_d^k = \mathbf U_d^k\mathbf\Sigma_d^k\left(\mathbf V_d^k\right)^\top $

   其中： $ \mathbf\Sigma_d^k\in \mathbb R^{d\times d} $ 为最大的 $ d $ 个奇异值， $ \mathbf U_d^k\in \mathbb R^{|V|\times d} $ 为 $ \mathbf U^k $ 的前 $ d $ 列， $ \mathbf V_d^k\in \mathbb R^{|V|\times d} $ 为 $ \mathbf V^k $ 的前 $ d $ 列。它们的物理意义为： $ \mathbf X^k (\mathbf X^k )^\top $ 、 $ (\mathbf X^k )^\top\mathbf X^k $ 最大的 d 个特征值对应的特征向量。

   通过这种方式，我们可以分解我们的矩阵 $ \mathbf X^k $ 为：

   $ \mathbf X^k\simeq \mathbf X_d^k = \mathbf W^k\left(\mathbf C^k\right)^\top $

   其中 $ \mathbf W^k = \mathbf U_d^k\left(\mathbf \Sigma_d^k\right)^{1/2}\in \mathbb R^{|V|\times d},\mathbf C^k=\mathbf V_d^k\left(\mathbf \Sigma_d^k\right)^{1/2}\in \mathbb R^{|V|\times d} $ 。 $ \mathbf W^k $ 的每一行给出了各顶点作为当前顶点的 representation 向量， $ \mathbf C^k $ 的每一行给出了各顶点作为上下文顶点的 representation 向量。最终我们返回矩阵 $ \mathbf W^k $ 作为顶点的 $ d $ 维 representation，它在图中捕获了 k-step 全局结构信息。

2. 在我们的算法中，我们考虑所有 $ k=1,2,\cdots,K $ 阶转移，其中 $ K $ 是预定义的常数。我们在学习 graph representation 时整合了所有这些 k-step 信息，这将在接下来讨论。

3. 注意，这里我们实际上是在寻找从 $ \mathbf X^k $ 的行空间到具有低秩的 $ \mathbf W^k $ 的行空间的投影。因此，也可以利用流行的 SVD 以外的替代方法，包括 incremental SVD、独立成分分析 independent component analysis: ICA、神经网络 DNN 。 我们这项工作的重点是学习 graph representation 的新模型，因此矩阵分解技术不是我们的重点。

   事实上，如果在这一步使用诸如稀疏自编码器之类的替代方法，则相对难以证明我们 representation 的实验效果是由于我们的新模型、还是由于降维步骤引入的任何非线性。为了保持与 《Neural word embedding as implicit matrix factorization》 工作的一致性，这里我们只使用了 SVD 。

3.1.4 GraRep 算法

1. 这里我们详细介绍我们的学习算法。通常，graph representation 被提取为其它任务的特征，例如分类、聚类。在实践中，编码 k-step representation 的一种有效方法是将 k-step representation 拼接起来作为每个顶点的全局特征，因为每个不同的 step representation 反映了不同的局部信息。

2. GraRep 算法：

   • 算法输入：

     • 图的邻接矩阵 $ \mathbf S $
     • 最大转移阶数 $ K $
     • 对数偏移系数 $ \beta $
     • 维度 $ d $

   • 算法输出：顶点的representation 矩阵 $ \mathbf W $

   • 算法步骤：

     • 计算 $ k=1,2,\cdots,K $ 阶转移概率矩阵 $ A^k $ 。计算流程：

       首先计算 $ \mathbf A = \mathbf D^{-1} \mathbf S $ ，然后依次计算 $ \mathbf A^1,\mathbf A^2,\cdots,\mathbf A^k $ 。

       对于带权图， $ \mathbf S $ 是一个实数矩阵；对于无权图， $ \mathbf S $ 是一个0-1 矩阵。算法都能够处理。

     • 对 $ k=1,2,\cdots,K $ 迭代计算每个顶点的 k-step representation，计算流程：

       • 获取正的对数概率矩阵 $ \mathbf X^k $ ：

         首先计算 $ \Gamma_1^k,\Gamma_2^k,\cdots,\Gamma_{|V|}^k $ ，其中 $ \Gamma_j^k=\sum_p A_{p,j}^k $ ；然后计算：

         $ X_{i,j}^k = \max\left\{\log\left(\frac{A_{i,j}^k}{\Gamma_j^k}\right)-\log\beta,0\right\} $

       • 计算representation 矩阵 $ \mathbf W^k $ ：

         $ \left[\mathbf U^k,\mathbf \Sigma^k,(\mathbf V^k)^\top\right] = \text{SVD}\left(\mathbf X^k\right)\\ \mathbf W^k = \mathbf U_d^k\left(\mathbf \Sigma_d^k\right)^{1/2} $

     • 拼接所有的 $ k $ 阶表达： $ \mathbf W = \left[\mathbf W^1,\mathbf W^2,\cdots,\mathbf W^K\right]\in \mathbb R^{|V|\times (Kd)} $

3. 未来工作：

   • 研究矩阵操作有关的近似计算和在线计算。
   • 研究通过深度架构代替 SVD 矩阵分解来学习低维 representation。

3.1.5 SkipGram 作为 GraRep 特例

1. GraRep 旨在学习 grap representation，并且我们基于矩阵分解来优化损失函数。另一方面，SGNS 已被证明在处理线性结构（如自然语言的句子）方面是成功的。GraRep 和 SGNS 之间有内在的联系吗？这里我们将 SGNS 视为 GraRep 模型的一个特例。

a. 图 SkipGram 模型的损失函数

1. SGNS 旨在以线性序列的方式来表达单词，因此我们需要将图结构转换为线性结构。DeepWalk 揭示了一种均匀采样（截断的随机游走）的有效方法。该方法首先从图中随机均匀采样一个顶点，然后随机游走到它的一个邻居并重复这个随机游走过程。如果顶点序列长度达到某个预定值，则停止随机游走并开始生成新的序列。该过程可用于从图中生成大量序列。

   本质上，对于无权图，这种均匀采样的策略是有效的。但是对于加权图，需要一种基于边权重的概率性采样方法，而 DeepWalk 中没有采用这种方法。在本文中，我们提出了一种适用于加权图的增强型 SGNS 方法 Enhanced SGNS: E-SGNS 。我们还注意到，DeepWalk 优化了一个不同于负采样的、替代的损失函数 alternative loss function（即 hierarchical softmax）。

2. 首先，我们考虑图上的、所有 K-step 的损失 $ \mathcal L $ ：

   $ \mathcal L = f(\mathcal L_1,\mathcal L_2,\cdots,\mathcal L_K) $

   其中 $ f(\cdot) $ 为一个线性函数： $ f(\varphi_1,\varphi_2,\cdots,\varphi_K) =\sum_{k=1}^K \varphi_k $ 。

   我们关注特定于 pair $ (w,c) $ 的损失，它们是图中第 $ w $ 个顶点和第 $ c $ 个顶点。

   定义 $ \mathbf M = \mathbf A^1 + \mathbf A^2 +\cdots + \mathbf A^K $ ，其中 $ M_{w,c} = \sum_{k=1}^K A_{w,c}^k $ 。这里 $ \mathbf M $ 为 $ K $ 步之内的概率转移矩阵， $ M_{w,c} $ 表示从顶点 $ w $ 不超过 $ K $ 步转移到顶点 $ c $ 的概率。

   则损失函数重写为：

   $ \mathcal L = \sum_{k=1}^K\mathcal L_k = \sum_{k=1}^K\sum_{w\in V}\sum_{c\in V} l_k(w,c)\\ = \sum_{w\in V}\sum_{c\in V}\left( \sum_{k=1}^KA_{w,c}^k\times \log\sigma( \mathbf{\vec w}\cdot \mathbf{\vec c} )+ \frac{\lambda}{|V|}\times \left(\sum_{w^\prime} \sum_{k=1}^KA^k_{w^\prime,c}\right)\times \log\sigma(-\mathbf{\vec w}\cdot \mathbf{\vec c} )\right)\\ = \sum_{w\in V}\sum_{c\in V}\left(M_{w,c} \times \log\sigma( \mathbf{\vec w}\cdot \mathbf{\vec c} )+ \frac{\lambda}{|V|}\times \left(\sum_{w^\prime} M _{w^\prime,c}\right)\times \log\sigma(-\mathbf{\vec w}\cdot \mathbf{\vec c}\right) $

   同样的推导过程可以解得最优解：

   $ e= \mathbf{\vec w}\cdot \mathbf{\vec c} = \log\left(\frac{M_{w,c}}{\sum_{w^\prime}M_{w^\prime,c}}\right) -\log(\beta) $

   其中其中 $ \beta = \frac{\lambda }{|V|} $ 。

   定义矩阵 $ \mathbf Y^{\text{E-SGNS}} $ ，其中：

   $ Y_{i,j}^\text{E-SGNS} = \log\left(\frac{M_{i,j}}{\sum_{t}M_{t,j}}\right) -\log(\beta) $

   则 $ Y^\text{E-SGNS} $ 为 E-SGNS 的被分解矩阵 factorized matrix 。

3. E-SGNS 和 GraRep 模型的区别在于 $ f(\cdot) $ 的定义：

   • E-SGNS 可以认为是 K-step loss 的线性组合，每个 loss 的权重相等。

     E-SGNS 和 SGNS 的主要区别在于对正样本的加权：E-SGNS 的正样本权重为 $ M_{w,c} $ ，即从顶点 $ w $ 不超过 $ K $ 步转移到顶点 $ c $ 的概率。

   • 我们的 GraRep 模型没有做出如此强的假设，但允许在实践中从数据中学习它们的关系（比如，潜在的非线性关系）。

     直觉上，不同的 k-step 转移概率应该有不同的权重。对于异质网络数据 heterogeneous network dat ，这些损失的线性组合可能无法达到理想的效果。

b. 采样与转移概率之间的内在联系

1. 在我们的方法中，我们使用转移概率来衡量顶点之间的关系。这合理吗？在这里，我们阐明了采样了转移概率之间的内在联系。

2. 在随机游走生成的序列中，我们假设顶点 $ w $ 一共出现的次数为：

   $ \#(w) = \gamma\times K $

   其中 $ \gamma $ 是与 $ \#(w) $ 相关的变量。

   我们将顶点 $ w $ 视为当前顶点，则顶点 $ c $ 为 $ w $ 直接邻居（1-step 距离）的次数的期望为：

   $ \#(w,c)_1 = \gamma\times K\times p_1(c\mid w) $

   这对于无权图的均匀采样、或者对于加权图的非均匀采样都成立。

   进一步地，顶点 $ c $ 为 $ w $ 二阶邻居（2-step 距离）的次数的期望为：

   $ \#(w,c)_2 = \gamma\times K\times\sum_{c^\prime}p_1(c_2\mid c^\prime)\times p_1(c^\prime\mid w) = \gamma\times K\times p_2(c\mid w) $

   其中 $ c^\prime $ 为连接顶点 $ w $ 和 $ c_2 $ 的任意其它顶点，即 $ c^\prime $ 为顶点 $ w $ 和 $ c_2 $ 的共享邻居。

   类似地，我们可以推导出 $ k=3,4,\cdots, $ 的方程：

   $ \#(w,c)_3 = \gamma\times K\times p_3(c\mid w)\\ \vdots\\ \#(w,c)_K = \gamma\times K\times p_K(c\mid w) $

   然后，我们将它们相加并除以 $ K $ ，得到：

   $ \#(w,c) = \gamma\times \sum_{k=1}^K p_k(c\mid w) $

   其中 $ \#(w,c) $ 为顶点 $ w $ 和顶点 $ c $ 在 $ K $ 步内共现的期望次数。

   根据 $ M_{w,c} $ 的定义，我们有： $ \#(w,c) = \gamma\times M_{w,c} $ 。

   现在，我们可以计算将顶点 $ c $ 作为上下文顶点的期望次数 $ \#(c) $ 为： $ \#(c) = \gamma\times \sum_{t} M_{t,c} $ ，其中我们考虑从所有可能顶点 $ t $ 到顶点 $ c $ 的转移。

   最后，我们将所有这些期望计数代入 $ Y_{w,c}^\text{E-SGNS} $ 的方程，得到：

   $ Y_{w,c}^\text{E-SGNS} = \log\left(\frac{M_{w,c}}{\sum_{t}M_{w,c}}\right) -\log(\beta) = \log\left(\frac{\#(w,c)\times |V|}{\#(c)}\right) - \log\lambda $

   定义数据集中所有观察到的 pair 的集合为 $ \mathcal D $ ，则 $ |\mathcal D| = \#(w)\times |V| $ ，因此有：

   $ Y_{w,c}^\text{E-SGNS} = \log\left(\frac{\#(w,c)\times |\mathcal D|}{\#(w)\times \#(c)}\right) - \log \lambda $

   矩阵 $ \mathbf Y^\text{E-SGNS} $ 变得与 《Neural word embedding as implicit matrix factorization》 中描述的 SGNS 完全相同。

   这表明 SGNS 本质上是我们 GraRep 模型的一个特殊版本，它可以处理从图中采样的线性序列。我们的方法相比缓慢的、昂贵的采样过程有若干优点，并且采样过程通常涉及几个要调整的超参数，例如线性序列的最大长度、每个顶点开始的序列数量等等。

3.2 实验

1. 这里我们通过实验评估 GraRep 模型的有效性。我们针对几个不同的任务在几个真实世界数据集上进行了实验，并与 baseline 算法进行了比较。

2. 数据集和任务：为了证明 GraRep 的性能，我们在三种不同类型的图上进行了实验，社交网络social network 、语言网络language network 、引文网络 citation network ，其中包括加权图和无权图。我们对三种不同类型的任务进行了实验，包括聚类clustering 、分类classification,、以及可视化 visualization 。正如我们前面提到的，我们工作的重点是提出一个新的框架，用于学习具有全局结构信息的、图的良好 representation ，旨在验证我们提出的模型的有效性。因此，除了 SVD 之外，我们不采用其它更有效的矩阵分解方法，并重点关注以下三个真实世界的数据集：

   • 语言网络数据集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 篇文档两种配置。每个文档上的 topic label 被认为是 ground truth 。

     这些 toplic label 被认为是聚类的真正 cluster id 。

   • 社交网络数据集 Blogcatalog：它是一个社交网络，每个顶点表示一个博客作者，每条边对应作者之间的关系。每个作者都带有多个标签信息，标签来自 39 种主题类别。

     该网络是一个无权图，用于多标签分类效果的评估。我们的模型以及 baseline 算法生成的 graph representation 被视为特征。

   • 引文网络数据集 DBLP Network：它是一个引文网络，每个顶点代表一个作者，边代表一个作者对另一位作者的引用次数。

     我们选择六个热门会议并分为三组：数据挖掘data mining 领域的 WWW,KDD 会议、机器学习 machine learning 领域 的 NIPS,IML 会议、计算机视觉 computer vision 领域的 CVPR,ICCV 会议。

     我们使用可视化工具 t-SNE 来可视化所有算法学到的 representation，从而提供学到的 representation 的定性结果和定量结果。

   总而言之，我们对加权图和无权图、稀疏图和稠密图进行了实验，其中执行了三种不同类型的学习任务。这些数据集的更多细节如下表所示。

   

3. baseline 方法：我们使用以下 graph representation 方法作为 baseline 。

   • LINE：LINE 是最近提出的一种在大规模信息网络上学习 graph representation 的方法。LINE 根据顶点之间的 1-step 和 2-step 关系信息定义了一个损失函数。一种提升 small degree 顶点的性能的策略是：扩展它们的邻域使得图更稠密。如果将 1-step 关系信息的 representation 和 2-step 关系信息的 representation 拼接起来，并调节邻域最大顶点的阈值，则 LINE 将获得最佳性能。

   • DeepWalk：DeepWalk 是一种学习社交网络 representation 的方法。原始模型仅适用于无权图。对于每个顶点，截断的随机游走用于将图结构转换为线性序列。带 hierarchical softmax 的 SkipGram 模型用作损失函数。

   • E-SGNS：SkipGram 是一种有效的模型，可以学习大型语料库中每个单词的 representation。对于这个增强版本，我们首先对无权图使用均匀采样、对加权图使用与边权重成正比的概率性采样（即随机游走），从而生成顶点序列。然后引入 SGNS 进行优化。

     这种方法可以视为我们模型的一个特例，其中每个 k-step 信息的不同 representation 向量进行均值池化。

   • Spectral Clustering：谱聚类是一种合理的 baseline 算法，旨在最小化归一化割 Normalized Cut:NCut 。与我们的方法一样，谱聚类也对矩阵进行分解，但是它侧重于图的不同矩阵：拉普拉斯矩阵Laplacian Matrix 。本质上，谱聚类和 E-SGNS 的区别在于它们的损失函数不同。

4. 参数配置：

   • 对于 LINE 模型：batch-size=1，学习率为 0.025，负采样系数为 5，迭代step 总数为百亿级。

     我们还还将 1-step 关系信息 representation 和 2-step 关系信息 representation 拼接起来 ，并针对degree 较小的顶点执行重构策略来达到最佳性能。

   • 对于 DeepWalk 和 E-SGNS 模型：窗口大小为 10，序列最长长度为 40，每个顶点开始的游走序列数量为 80 。

   • 正则化：LINE,GraRep 模型进行 $ L_2 $ 正则化可以达到最佳效果，DeepWalk,E-SGNS 模型没有正则化也能达到最佳效果。

   • embedding 维度 $ d $ ：为公平比较，Blogcatalog 和 DBLP 数据集的 $ d=128 $ ，而 20-NewsGroup 数据集的 $ d=64 $ 。

   • GraRep 模型： $ \beta = \frac 1{|V|} $ ；Blogcatalog 和 DBLP 数据集的 $ K=6 $ ， 20-NewsGroup 数据集的 $ K=3 $ 。

3.3.1 语言网络

1. 我们通过在 k-means 算法中使用学到的 representation，通过聚类任务在语言网络上进行实验。为了评估结果的质量，我们报告了每个算法在 10 次不同运行中的平均归一化互信息Normalized Mutual Information (NMI) 得分。

   为了理解不同维度 $ d $ 在最终结果中的影响，我们还展示了 DeepWalk、E-SGNS、Spectral Clustering 在 $ d=192 $ 的结果（除了 $ d=64 $ 之外）。对于 LINE 模型这里采用了重构策略，邻居数量阈值分别设定为 k-max = 0,200,500,1000 取最佳阈值（最佳阈值为 200）。

   最终结果如下表所示，每列的最佳结果用粗体突出显示。结论：

• GraRep 模型在所有实验中都优于其它 baseline 方法。

  • 对于 DeepWalk, E-SGNS 和 Spectral Clustering ，增加维度 $ d $ 似乎并不能有效提高性能。我们认为：较高的维度并不会为representation 提供额外的补充信息。

• 对于LINE 模型采用重建策略确实有效，因为它可以捕获图的额外结构信息，例如超出 1-step 、2-step 的局部信息。

  • 值得一提的是，GraRep 和 LINE 模型在很小的 Graph 上就可以得到良好的性能。我们认为：即使在图很小的条件下，这两个模型也可以捕获丰富的局部关系信息。
  • 此外，对于标签较多的任务，例如 9GN，GraRep 和 LINE 可以提供比其它方法更好的性能。
  • 一个有趣的发现是：当 $ d=16 $ 时 Spectral Clustering 达到最佳性能，但是对其它算法 $ d=64 $ 达到最佳性能。

  由于篇幅所限，我们没有报告所有 baseline 方法在 $ d=128, d=256 $ 时的详细结果，也没有报告 LINE 的 k-max=500, 1000 以及没有重建策略的结果。因为这些结果并不比下表的效果更好。后面的实验会进一步探究参数敏感性问题。

  

3.3.2 社交网络

1. 在这个实验中，我们专注于社交网络上的监督任务。我们将学到的 representation 视为特征，通过多标签分类任务评估不同算法得到的 graph representation 的有效性。

   我们使用 LibLinear package 来训练 one-vs-rest 逻辑回归分类器。我们将这个过程运行 10 轮并报告平均 Micro-F1 和 Macro-F1 指标。对于每一轮，我们随机采样 10%~90% 的顶点来训练，剩下的顶点作为测试集 。 这里LINE 模型采用了重构策略，邻居数量阈值分别设定为 k-max = 0,200,500,1000 取最佳阈值（最佳阈值为 500）。

   最终结果如下表所示，每列的最佳结果用粗体突出显示。结论：总体上 GraPep 性能远超过其它方法，尤其是仅使用 10% 样本训练。

   这表明GraRep 学到的不同类型的、丰富的局部结构信息可以相互补充从而捕获到全局结构信息。在与现有的 baseline 相比具有明显的优势，尤其是在数据稀疏时。

   

3.3.3 引文网络

1. 在这个实验中，我们专注于通过检查一个真实的引文网络 DBLP 来可视化学到的 representation。我们将学到的 graph representation 输入到 t-SNE 工具中来 lay out 图，其中来自同一个研究领域的作者使用相同的颜色，绿色表示数据挖掘、紫色表示计算机视觉、蓝色表示机器学习。

   结论：

   • 使用谱聚类的效果一般，因为不同颜色的顶点相互混合。

   • DeepWalk 和 E-SGNS 结果看起来好得多，因为大多数相同颜色的顶点似乎构成了分组，但是分组的边界似乎不是很明显。

   • LINE 和 GraRep结果中，每个分组的边界更加清晰，不同颜色的顶点出现在明显可区分的区域中。

     与 LINE 相比 GraRep 的结果似乎更好，每个区域的边界更清晰。

   

2. 引文网络可视化的 KL 散度如下表所示。其中 KL 散度捕获了 ”成对顶点的相似度” 和 “二维投影距离” 之间的误差。更低的 KL 散度代表更好的表达能力。可以看到：GraRep 模型的顶点 representation 效果最好。

   

3.3.4 参数敏感性

1. 这里我们讨论参数敏感性，具体而言我们评估了最大步长 $ K $ 、维度 $ d $ 对于模型效果的影响。

   • $ K $ 值：下图给出 Blogcatelog 数据集上不同 $ K $ 值对应得 Micro-F1 和 macro-F1 得分。为阅读方便，这里仅给出 $ K=1,2,5,6,7 $ 的结果。因为实验发现： $ K=4 $ 的结果略好于 $ K=3 $ ，而 $ K=5 $ 的效果与 $ K=4 $ 相当。

     可以看到：

     • $ K=2 $ 比 $ K=1 $ 有明显改善，而 $ K=3 $ 的性能进一步优于 $ K=2 $ 。

       这表明：不同的 $ k $ 阶信息可以学到互补的局部信息。

     • $ K=7 $ 的结果并不比 $ K=6 $ 好多少。

       这是因为当 $ k $ 足够大时，学到的 $ k $ 阶信息会减弱并趋于一个稳定的分布。

     

   • $ d $ 值：下图给出了 3NG 和 9NG 在不同 $ d $ 配置下不同模型的 NMI 得分。可以看到：

     • GraRep 模型结果始终优于其它模型。
     • 几乎所有算法都在 $ d=64 $ 时取得最佳性能，当 $ d $ 从 64 继续增加到更大值时所有算法效果都开始下降。

     

2. 运行时间：下图给出不同总维度和不同图大小时模型的运行时间。总维度等于 $ d\times K $ ，它代表最终 GraRep 拼接得到的representation 向量。

   • 图 a 给出了 $ d=128 $ 且 $ K=1,2,\cdots,7 $ 时，模型在 Blogcatalog 数据集上的模型训练时间。

     可以看到：模型训练时间随着总维度的增加而几乎线性增加。

   • 图 b 给出了在 20-NewsGroup 数据集不同规模的网络上训练的时间。

     可以看到：随着 Graph 规模的增长，模型训练时间显著增加。原因是随着 Graph 增长，矩阵幂运算 $ \mathbf A^k $ 和矩阵 SVD 分解涉及到时间复杂度较高的运算。

     后续可以考虑采用深度学习来替代 SVD 技术来做矩阵分解。