Question

1. 近年来 network embedding 为图和网络建模提供了革命性的范式。network embedding 的目标是自动学习网络中对象（例如顶点、边）的潜在 representation 。重要的研究表明：潜在representation 能够捕获网络的结构特性，促进各种下游网络应用，例如顶点分类任务、链接预测任务。

   在 network embedding 发展过程中，DeepWalk, LINE, node2vec 模型通常被认为是评估 network embedding 研究的强大基准方案。LINE 的优势在于它对大规模网络的可扩展性，因为它仅对一阶邻近性和二阶邻近性建模。也就是说，LINE 的 embedding 没有对网络中的 multi-hop 依赖。另一方面，DeepWalk 和 node2vec 利用图上的随机游走和具有较大 context size 的 SkipGram 来对更远的节点（即全局结构）进行建模。因此，DeepWalk 和 node2vec 处理大规模网络的计算成本更高。例如，使用默认参数设置的 DeepWalk 需要几个月的时间来嵌入一个由 6700 万顶点、8.95 亿条边组成的学术协作网络 academic collaboration network 。而执行高阶随机游走的 node2vec 模型比 DeepWalk 需要更多时间来学习 embedding 。

   最近的一项研究表明，DeepWalk 和 LINE 方法都可以看作是一个闭式closed-form 矩阵的隐式分解。在这个理论的基础上，该研究提出了 NetMF 方法来显式分解这个矩阵，从而实现比 DeepWalk 和 LINE 更有效的 embedding 。不幸的是，待分解的矩阵是一个 $ n\times n $ 的稠密矩阵，其中 $ n $ 为网络中的顶点数量，这使得直接构造和分解大规模网络的成本过高。

   鉴于现有方法的这些局限性（如下表中的总结），论文 《NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization》建议研究大规模网络的 representation learning ，目标是达到高效率、捕获全局结构上下文global structural context 、并具有理论上的保证。论文的思想是找到一个稀疏矩阵，该矩阵在谱上逼近由 DeepWalk 隐式分解的、稠密的 NetMF 矩阵。稀疏矩阵需要较低的构造成本和分解成本。同时，使其在谱上逼近原始 NetMF 矩阵可以保证网络的谱信息 spectral information 保持不变，并且从稀疏矩阵中学到的 embedding 与从稠密 NetMF 矩阵中学到的 embedding 一样强大。

   

   在这项工作中，论文提出了作为稀疏矩阵分解的 network embedding learning 方法 NetSMF 。NetSMF 包含三个步骤：首先，它利用谱图稀疏化技术 pectral graph sparsification technique 为网络的随机游走矩阵多项式random-walk matrix-polynomial 找到稀疏化器 sparsifier 。然后，它使用这个稀疏化器来构造一个非零元素数量明显少于原始 NetMF 矩阵、但是在谱上逼近原始 NetMF 矩阵的矩阵。最后，它执行随机奇异值分解randomized singular value decomposition 以有效地分解稀疏的 NetSMF 矩阵，从而产生网络的 embedding 。

   通过这种设计，NetSMF 保证了效率和效果，因为稀疏矩阵的逼近误差approximation error 在理论上是有界的。论文在代表不同规模和类型的五个网络中进行实验。实验结果表明：对于百万级或更大的网络，NetSMF 比 NetMF 实现了数量级上的加速，同时保持了顶点分类任务的有竞争力的性能competitive performance 。换句话讲，NetSMF 和 NetMF 都优于公认的 network embedding 基准方法（即 DeepWalk, LINE, node2vec），但是 NetSMF 解决了 NetMF 面临的计算挑战。

   总而言之，论文引入了通过稀疏矩阵分解来产生 network embedding 的思想，并提出了 NetSMF 算法。NetSMF 算法对 network embedding 的贡献如下：

   • 效率：NetSMF 的时间复杂度和空间复杂度显著低于 NetMF。值得注意的是，NetSMF 能够在 24 小时内在单台服务器上为包含 6700 万个顶点、8.95 亿条边的大型学术网络 academic network 生成 embedding，而 DeepWalk 和 node2vec 将花费数月时间。另外在相同的硬件上，NetMF 在计算上是不可行的。
   • 效果：NetSMF 学到的 embedding 能够保持与稠密矩阵分解的解决方案相同的表达能力。在网络中的多标签顶点分类任务中，NetSMF 始终优于 DeepWalk 和 node2vec 高达 34%、始终优于 LINE 高达 100% 。
   • 理论保证：NetSMF 的效率和效果在理论上得到了保证。稀疏的 NetSMF 矩阵在谱上逼近于精确的 NetMF 矩阵，并且逼近误差是有界的，从而保持了 NetSMF 学到的 embedding 的表达能力。

2. 相关工作：这里我们回顾了 network embedding、大规模 embedding 算法、谱图稀疏化spectral graph sparsification 等相关的工作。

   • network embedding：network embedding 在过去几年中得到了广泛的研究。network embedding 的成功推动了许多下游网络应用network application，例如推荐系统。简而言之，最近关于 network embedding 的工作可以分为三类：

     • 受 word2vec 启发的、基于 SkipGram 的方法，如 LINE, DeepWalk, node2vec, metapath2vec, VERSE。
     • 基于深度学习的方法，如 《Semi-Supervised Classification with Graph Convolutional Networks》、《Graph Convolutional Neural Networks for Web-Scale Recommender Systems》 。
     • 基于矩阵分解的方法，如 GraRep, NetMF。其中，NetMF 通过将一系列基于 SkipGram 的 network embedding 方法统一到一个矩阵分解框架中来连接第一类工作和第三类工作。

     在这项工作中，我们利用了 NetMF 的优点并解决了它在效率方面的局限性。

     在文献中，PinSage 是一个用于十亿规模网络的 network embedding 框架。NetSMF 和 PinSage 的主要区别在于：NetSMF 的目标是以无监督的方式预训练通用的 network embedding；而 PinSage 是一种有监督的图卷积方法，既结合了推荐系统的目标，也结合了现有的节点特征。话虽如此，NetSMF 学到的 embedding 也可以被 PinSage 用于下游的网络应用。

   • large-scale embedding learning：一些研究试图优化 embedding 算法从而用于大型数据集。其中的一部分专注于改进 SkipGram 模型，另一部分则聚焦于改进矩阵分解模型。

     • 分布式 SkipGram 模型：受 word2vec 的启发，大多数现代的 embedding learning 算法都基于 SkipGram 模型。有一系列工作试图在分布式系统中加速 SkipGram 模型。例如，《Parallelizing word2vec in shared and distributed memory》 在多个 worker 上复制 embedding 矩阵并定期同步synchronize 它们。《Network-efficient distributed word2vec training system for large vocabularies》 将 embedding 矩阵的列（维度）分配给多个 executor ，并将它们与一个 parameter server 进行同步。

       负采样negative sampling 是 SkipGram 的关键步骤，它需要从噪声分布noisy distribution 中采样负样本。《Distributed Negative Sampling for Word Embeddings》 专注于通过使用别名方法 alias method 的分层采样算法hierarchical sampling algorithm 代替了 roulette wheel selection 从而优化负采样。

       最近，《Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba》 提出了一个十亿规模的network embedding 框架。该框架通过启发式地将输入图划分为小的子图，然后并行地、单独地处理这些子图。然而，该框架的性能高度依赖于图划分graph partition 的质量。另外，基于分区partition-based 的 embedding learning 的缺点是：在不同子图中学到的 embedding 不共享相同的潜在空间，因此无法跨子图比较节点。

     • 高效的矩阵分解：隐式分解 NetMF 矩阵（例如 LINE, DeepWalk）或显式分解 NetMF 矩阵（例如 NetMF 算法）会遇到两个问题：首先，即使对于中等的上下文窗口大小（例如 T=10），该矩阵的稠密程度也会使得计算变得昂贵。其次，非线性变换（即，逐元素的矩阵对数）很难近似approximate 。LINE 通过设置 T=1 解决了这个问题。通过这种简化，LINE 以预测性能为代价实现了良好的可扩展性。NetSMF 通过有效地稀疏化稠密的 NetMF 矩阵来解决这个问题，其中这个稀疏化过程具有理论上有界的近似误差。

   • spectral graph sparsification：谱图稀疏化在图论中已经研究了几十年。谱图稀疏化的任务是通过一个稀疏图来近似并代替一个稠密图。我们的 NetSMF 模型是第一个将谱图稀疏化算法纳入 network embedding 的工作。NetSMF 提供了一种强大而有效的方法来近似和分析 NetMF 矩阵中的随机游走矩阵多项式random-walk matrix-polynomial 。

16.1 模型

16.1.1 基本概念

1. 通常，network embedding 问题形式化如下：给定一个带权无向图 $ G=(V,E,\mathbf A) $ ，其中 $ V $ 为 $ n $ 个顶点组成的顶点集合， $ E $ 为 $ m $ 条边组成的边集合， $ \mathbf A $ 为邻接矩阵。network embedding 学习任务的目标是学习函数 $ V\rightarrow \mathbb R^d $ ，从而将每个顶点 $ v\in V $ 映射到一个 $ d $ 维的 embedding 向量 $ \mathbf{\vec x}_v\in \mathbb R^d $ ，其中 $ d\ll n $ 。这个 embedding 向量捕获了网络的结构属性 structural property，例如社区结构。顶点的 embedding 向量可以提供给下游应用程序使用，例如链接预测任务、顶点分类任务等等。

2. DeepWalk 模型是 network embedding 的开创性工作之一，并且在过去几年中一直被认为是一个强大的基准。简而言之，DeepWalk 模型分为两个步骤：首先，DeepWalk通过网络中的随机游走过程生成一些顶点序列；然后，DeepWalk 在生成的顶点序列上应用 SkipGram 模型来学习每个顶点的潜在 representation 。通常，SkipGram 使用上下文窗口大小 $ T $ 和负采样比例 $ b $ 进行参数化。最近，《Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE,and node2vec》 的理论分析研究表明：DeepWalk 本质上分解了从随机游走过程中派生出 derived 的矩阵。更正式地讲，该论文证明了当随机游走序列的长度达到无穷大时，DeepWalk 隐式且渐进地分解以下矩阵：

   $ \mathbf X \mathbf Y^\top = \log^\circ \left(\frac{\text{vol}_G}{b}\mathbf M\right)\\\text{vol}_G = \sum_i\sum_j A_{i,j},\quad d_i=\sum_{j}A_{i,j},\quad \mathbf D = \text{diag}(d_1,d_2,\cdots,d_n)\\ \mathbf M = \frac 1T\sum_{r=1}^T \left(\mathbf D^{-1}\mathbf A\right)^r\mathbf D^{-1} $

   其中：

   • $ \mathbf X\in \mathbb R^{n\times d} $ 为每个顶点的 embedding 向量组成的 embedding 矩阵， $ \mathbf Y\in \mathbb R^{n\times d} $ 为每个顶点作为 context 时的 embedding 矩阵。
   • $ \log^\circ(\cdot) $ 为矩阵的逐元素 log 。
   • $ d_i $ 为顶点 $ i $ 的 degree， $ \mathbf D $ 为所有顶点的 degree 组成的对角矩阵， $ \text{vol}_G $ 为所有顶点 degree 的和。 $ \text{vol}_G $ 也称作图的 volume ，

   这种矩阵形式提供了基于 SkipGram 的 network embedding 方法的另一种观点（即，矩阵分解的观点）。此外，该论文还提出了一种叫做 NetMF 的显式矩阵分解方法来学习 embedding 。该论文表明：基于 NetMF 的 embedding 在顶点分类任务上的准确率要优于基于 DeepWalk 或 LINE 的 embedding 。

   注意，如果在 T hop 中存在一对无法到达的顶点，那么上述等式中的矩阵将是未定义 ill-defined 的，因为 $ \log (0) = -\infty $ 。因此，遵循 《NeuralWord Embedding as Implicit Matrix Factorization》，NetMF 使用截断的对数，即 $ \text{trunc_log}(x) = \log \max(1,x) $ 。因此，NetMF 的目标是分解矩阵：

   $ \text{trunc_log}^\circ \left(\frac{\text{vol}_G}{b}\mathbf M\right) $

   在这项工作的其余部分，我们将这个矩阵称作 NetMF 矩阵。

3. 然而，在实践中利用 NetMF 矩阵时存在一些挑战。首先，距离 $ r\le T $ 内的每一对顶点几乎都对应于 NetMF 矩阵中的一个非零项。回想一下，许多社交网络social network 和信息网络information network 都表现出小世界smallworld 的属性，即大多数顶点之间可以通过少量 step 而相互抵达。例如，截至 2012 年，Facebook 的可达顶点对reachable pair ，92% 的距离小于等于 5 。因此，即使设置一个中等的上下文窗口大小（例如，DeepWalk 中的默认设置 T=10 ），NetMF 矩阵也将是具有 $ O(n^2) $ 个非零元素的稠密矩阵。这种矩阵的精确构造和精确分解对于大型网络而言是不切实际的。更具体而言，计算矩阵 $ \mathbf M $ 时涉及到 $ O(n^3) $ 复杂度的矩阵幂次运算，另外对稠密的 NetMF 矩阵进行矩阵分解也很耗时。

   为了降低构造成本，NetMF 使用 top 特征值和特征向量来近似 $ \mathbf M $ 。然而这个近似矩阵approximated matrix 仍然是稠密的，使得这种策略无法处理大型网络。在这项工作中，我们旨在解决 NetMF 的效率和可扩展性的缺陷，同时保持其效果优势。

   计算 NetMF 的 top 特征值和特征向量也是耗时的。

16.1.2 NetSMF

1. 在本节中，我们将 network embedding 开发为稀疏矩阵分解 sparse matrix factorization（即 NetSMF）。我们提出了 NetSMF 方法来构造和分解一个稀疏矩阵，这个稀疏矩阵逼近了稠密 的 NetMF 矩阵。我们利用的主要技术是随机游走矩阵多项式稀疏化 random-walk matrix-polynomial sparsification。

   我们首先介绍谱相似度spectral similarity 的定义和随机游走多项式稀疏化定理。

2. 谱相似度 Spectral Similarity ：假设有两个带权无向图 $ G=(V,E,\mathbf A) $ 和 $ \tilde G=(\tilde V,\tilde E,\tilde{\mathbf A}) $ ，令 $ \mathbf L = \mathbf D_G - \mathbf A $ 和 $ \tilde{\mathbf L} = \mathbf D_{\tilde G} - \tilde{\mathbf A} $ 分别为它们的拉普拉斯矩阵。如果下面的关系成立，我们就说 $ G $ 和 $ \tilde G $ 是 $ (1+\epsilon) $ 谱相似的spectrally similar ：

   $ \forall \mathbf{\vec x}\in \mathbb R^n,\quad (1-\epsilon) \mathbf{\vec x}^\top \tilde{\mathbf L}\mathbf{\vec x} \le \mathbf{\vec x}^\top \mathbf L\mathbf{\vec x} \le (1+\epsilon) \mathbf{\vec x}^\top\tilde{\mathbf L}\mathbf{\vec x} $

3. 定理（随机游走多项式的谱稀疏化器Spectral Sparsifier）：对于随机游走多项式 random-walk molynomial

   $ \mathbf H = \mathbf D - \sum_{r=1}^T \alpha_r\mathbf D\left(\mathbf D^{-1} \mathbf A\right)^r $

   其中 $ \alpha_r\ge 0, \sum_{r=1}^T\alpha_r = 1 $ ，则可以在 $ O(T^2m\epsilon^{-2}\log^2n) $ 时间复杂度内构造一个 $ (1+\epsilon) $ spectral sparsifier $ \tilde{\mathbf H} $ ，其中 $ \tilde{\mathbf H} $ 具有 $ O((n\log n )\epsilon^{-2}) $ 个非零项。对于无权图，时间复杂度可以进一步降低到 $ O(T^2m\epsilon^{-2}\log n) $ 。

   证明参考：《Efficient sampling for Gaussian graphical models via spectral sparsification》 、《Spectral sparsification of random-walk matrix polynomials》 。

4. 为构建一个包含 $ O((n\log n )\epsilon^{-2}) $ 个非零项的 sparsifier $ \tilde{\mathbf H} $ ，该稀疏化算法包含两步：

   • 第一步获得一个针对 $ \mathbf H $ 的初始化 sparsifier，它包含 $ O(Tm\epsilon^{-2}\log n) $ 个非零项。
   • 第二步使用标准的谱稀疏化算法spectral sparsification algorithm 来进一步降低非零项到 $ O(\epsilon^{-2}n\log n) $ 。

   本文我们仅仅应用第一步，因为一个包含 $ O(Tm\epsilon^{-2}\log n) $ 个非零项的稀疏矩阵已经足够可用，所以我们并没有采用第二步，这能够避免额外的计算。下面讲到的所有随机游走多项式稀疏化算法都仅包含第一步

5. 我们取 $ \alpha_r = \frac 1T $ ，因此有：

   $ \mathbf H = \mathbf D - \frac 1T\sum_{r=1}^T \mathbf D\left(\mathbf D^{-1} \mathbf A\right)^r $

   我们定义：

   $ \mathbf M = \frac{1}{T} \left(\sum_{r=1}^T\mathbf (\mathbf D^{-1}\mathbf A )^r \right) \mathbf D^{-1} $

   因此有： $ \mathbf M = \mathbf D^{-1}(\mathbf D - \mathbf H)\mathbf D^{-1} $ 。

   采用 $ \mathbf H $ 的稀疏化版本 $ \tilde{\mathbf H} $ ，我们定义 $ \tilde{\mathbf M} = \mathbf D^{-1}(\mathbf D - \tilde{\mathbf H}) \mathbf D^{-1} $ 。可以发现 $ \tilde{\mathbf M} $ 也是一个稀疏矩阵，其非零元素的规模和 $ \tilde{\mathbf H} $ 非零元素规模相当。最终我们可以分解这个稀疏矩阵从而获得每个顶点的 embedding ：

   $ \mathbf X \mathbf Y^\top = \text{trunc_log}^\circ \left(\frac{\text{vol}_G}{b}\tilde{\mathbf M}\right) $

6. 我们正式给出 NetSMF 算法，该算法包含三个步骤：

   • 随机游走多项式的稀疏化：我们首先构建一个网络 $ \tilde G $ ，它具有和 $ G(V,E,\mathbf A) $ 相同的顶点但是不包含任何边。然后我们重复 Path-Sampling 路径采样算法 $ M $ 次，从而得到 $ O(M) $ 条边，这些边构成了 $ \tilde{\mathbf H} $ 的非零项。在每一次迭代过程中：

     • 首先均匀随机选择一条边 $ e=(u,v)\in E $ ，均匀随机选择一个路径长度 $ r\in \{1,\cdots,T\} $ 。

     • 然后从顶点 $ u $ 开始进行 $ k-1 $ 步随机游走，得到顶点序列 $ (u,u_{k-2},\cdots,u_0) $ ；从顶点 $ v $ 开始进行 $ r-k $ 步随机游走，得到顶点序列 $ (v,u_{k+1},\cdots,u_r) $ 。这一过程产生了一个长度为 $ r $ 的路径 $ \mathbf p = (u_0,u_1,\cdots,u_r) $ 。同时我们计算：

       $ Z(\mathbf p) = \sum_{i=1}^r\frac{2}{A_{u_{i-1},u_i}} $

     • 然后我们向图 $ \tilde G $ 中添加一条新的边 $ (u_0,u_r) $ ，其权重为 $ \frac{2rm}{MZ(\mathbf p)} $ 。如果边已经存在，则相同的边进行合并（只需要将权重相加即可）。

       这条新的边代表了图 $ G $ 中一条长度为 $ r $ 的随机游走序列，权重就是转移概率。其中 $ M\gt m $ 。

     • 最终我们计算 $ \tilde G $ 的未归一化的拉普拉斯矩阵 $ \tilde {\mathbf H} $ ，它具有 $ O(M) $ 个非零项。

       这个被构造出的图的未归一化拉普拉斯矩阵与 $ \mathbf M $ 产生联系。

   • NetMF 稀疏器 sparsifier 的构造：即计算 $ \tilde{\mathbf M} = \mathbf D^{-1}(\mathbf D - \tilde{\mathbf H}) \mathbf D^{-1} $ 。这一步并未改变非零项的规模。

   • 截断的奇异值分解：对 $ \text{trunc_log}^\circ(\frac{\text{vol}_G}{b}\tilde{\mathbf M}) $ 执行 $ d $ 维的 RandomizedSVD 分解。

     即使稀疏矩阵仅有 $ O(M) $ 个非零元素，执行精确的 SVD 仍然非常耗时。这里我们使用 Randomized SVD 进行分解。由于篇幅有限我们无法包含更多细节，简而言之，该算法通过高斯随机矩阵将原始矩阵投影到低维空间，然后在 $ d\times d $ 维的小矩阵上执行经典的 SVD 分解即可。

     采用 SVD 的另一个优势是：我们可以通过使用诸如 Cattell’s Scree test 来确定 embedding 的维度。在测试中，我们绘制奇异值并选择一个 rank $ d $ ，使得奇异值幅度显著下降或者奇异值开始趋向于平衡的位置。

     实际上自动选择一个 rank d 需要对 $ \text{trunc_log}^\circ \left(\frac{\text{vol}_G}{b}\tilde{\mathbf M}\right) $ 进行奇异值分解，这对于大型网络而言是不可行的。

7. NetSFM 算法：

   • 输入：

     • 图 $ G= (V,E,\mathbf A) $
     • 非零项的数量 $ M $
     • embedding 维度 $ d $

   • 输出：顶点 embedding 矩阵 $ \mathbf X\in \mathbb R^{n\times d} $

   • 算法步骤：

     • 初始化 $ \tilde G = (V,\mathbf\Phi,\mathbf 0) $ ，即只有顶点没有边。

     • 迭代 $ i=1,\cdots,M $ ，迭代步骤为：

       • 均匀随机选择一条边 $ e=(u,v)\in E $ 。

       • 均匀随机选择一个长度 $ r\in \{1,\cdots,T\} $ 。

       • 随机采样一条路径： $ u^\prime,v^\prime,Z \leftarrow \text{PathSampling}(e,r) $

       • 添加边 $ (u^\prime,v^\prime) $ 到 $ \tilde G $ 中，边的权重为 $ \frac{2rm}{MZ} $ 。

         如果有多条边相同则合并成一个，将权重直接相加即可。

     • 计算 $ \tilde G $ 的未归一化的拉普拉斯矩阵 $ \tilde{\mathbf H} $ 。

     • 计算 $ \tilde{\mathbf M} = \mathbf D^{-1}(\mathbf D - \tilde{\mathbf H}) \mathbf D^{-1} $ 。

     • 对 $ \text{trunc_log}^\circ(\frac{\text{vol}_G}{b}\tilde{\mathbf M}) $ 执行 $ d $ 维的 RandomizedSVD 分解，得到 $ \mathbf U_d,\mathbf \Sigma_d,\mathbf{\vec V}_d $ 。

     • 返回 $ \mathbf U_d\sqrt{\mathbf\Sigma}_d $ 。

8. PathSampling 算法：

   • 输入：

     • 图 $ G= (V,E,\mathbf A) $
     • 边 $ e=(u,v) $
     • 采样的路径长度 $ r $

   • 输出：路径的初始顶点 $ u_0 $ 、结束顶点 $ u_r $ 、路径 $ Z $ 值

   • 算法步骤：

     • 均匀随机采样一个整数 $ k\in \{1,\cdots,r\} $ 。

     • 从顶点 $ u $ 开始执行 $ (k-1) $ 步随机游走，采样到的顶点记作 $ （u,u_{k-2},\cdots, u_0) $ 。

     • 从顶点 $ v $ 开始执行 $ (r-k) $ 步随机游走，采样到的顶点记作 $ (v,u_{k+1},\cdots,u_r) $ 。

     • 计算整条路径的路径 $ Z $ 值：

       $ Z= \sum_{i=1}^r\frac{2}{A_{u_{i-1},u_i}} $

     • 返回 $ (u_0,u_r,Z) $ 。

9. Randomized SVD 算法：

   • 输入：

     • 一个稀疏的对称矩阵 $ \mathbf K = \text{trunc_log}^\circ(\frac{\text{vol}_G}{b}\tilde{\mathbf M}) $ 。我们以行优先的方式存储矩阵，从而充分利用对称性来简化计算。
     • 目标维度 $ d $

   • 输出：SVD 矩阵分解的 $ \mathbf U_d,\mathbf\Sigma_d,\mathbf V_d $

   • 步骤：

     • 采样一个高斯随机矩阵 $ \mathbf O\in \mathbb R^{n\times d} $ 作为投影矩阵。
     • 计算映射后的矩阵 $ \mathbf Y = \mathbf K^\top\mathbf O = \mathbf K\mathbf O \in \mathbb R^{n\times d} $ 。
     • 对矩阵 $ \mathbf Y $ 进行正交归一化。
     • 计算矩阵 $ \mathbf B = \mathbf K\mathbf Y\in \mathbb R^{n\times d} $ 。
     • 采样另一个高斯随机矩阵 $ \mathbf P\in \mathbb R^{d\times d} $ 作为投影矩阵。
     • 计算映射后的矩阵 $ \mathbf Z = \mathbf B \mathbf P\in \mathbb R^{n\times d} $ 。
     • 对矩阵 $ \mathbf Z $ 进行正交归一化。
     • 计算矩阵 $ \mathbf C = \mathbf Z^\top \mathbf B\in \mathbb R^{d\times d} $ 。
     • 对 $ \mathbf C $ 执行 Jacobi SVD 分解： $ \mathbf C = \mathbf U\mathbf\Sigma \mathbf V^\top $ 。
     • 返回 $ \mathbf Z\mathbf U\in \mathbb R^{n\times d},\mathbf\Sigma\in \mathbb R^{d\times d},\mathbf Y \mathbf V\in \mathbb R^{n\times d} $ 。

10. PathSampling 算法的说明：

    • 引理：给定一个长度为 $ r $ 的路径 $ \mathbf p = (u_0,\cdots,u_r) $ ，则PathSampling 算法采样到该路径的概率为：

      $ \pi(\mathbf p) = \frac{w(\mathbf p)Z(\mathbf p)}{2rm} $

      其中：

      $ Z(\mathbf p) = \sum_{i=1}^r\frac{2}{A_{u_{i-1},u_i}},\quad w(\mathbf p) = \frac{\prod_{i=1}^rA_{u_{i-1},u_i}}{\prod_{i=1}^{r-1}D_{u_i}} $

    • 引理：假设采样到一个长度为 $ r $ 的路径 $ \mathbf p = (u_0,\cdots,u_r) $ ，则新的边 $ (u_0,u_r) $ 的权重应该为：

      $ \frac{w(\mathbf p)}{\pi(\mathbf p)M} $

    根据上述引理，则添加到 $ \tilde G $ 中的边的权重为：

    $ \frac{w(\mathbf p)}{\pi(\mathbf P)M} = \frac{w(\mathbf p)}{(w(\mathbf p)Z(\mathbf p))/(2rm) \times M} = \frac{2rm}{MZ(\mathbf p)} $

    对于无向图，则 $ Z(\mathbf P) = 2r $ ，则权重简化为 $ \frac{m}{M} $ 。

11. NetMF 和 NetSMF 之间的主要区别在于对目标矩阵的近似策略。NetMF 使用了一个稠密矩阵来近似，从而带来了时间和空间上的挑战；NetSFM 基于谱图稀疏化理论和技术，使用了一个稀疏矩阵来近似。

16.1.3 复杂度

1. 算法复杂度：

   • 第一步：我们需要调用 PathSampling 算法 $ M $ 次，每次 PathSampling 都需要在网络 $ G $ 上执行 $ O(T) $ 步随机游走。对于无权无向图，随机游走采样一个顶点的计算复杂度为 $ O(1) $ ；对于带权无向图，可以使用 roulette wheel selection 从而随机游走采样一个顶点的计算复杂度为 $ O(\log n) $ 。

     另外我们需要 $ O(M) $ 的空间存储 $ \tilde G $ ，以及额外的 $ O(n+m) $ 空间来存储算法的输入。

   • 第二步：我们需要 $ O(M) $ 的时间来计算 $ \tilde{\mathbf M} = \mathbf D^{-1}(\mathbf D - \tilde{\mathbf H}) \mathbf D^{-1} $ 以及 $ \text{trunc_log}^\circ \left(\frac{\text{vol}_G}{b}\tilde{\mathbf M}\right) $ 。

     另外我们需要 $ O(n) $ 空间来存储degree 矩阵 $ \mathbf D $ ， $ O(M) $ 的空间来存储 $ \hat{\mathbf M} $ 。

   • 第三步：我们需要 $ O(Md) $ 时间来计算一个稀疏矩阵和一个稠密矩阵的乘积，以及 $ O(d^3) $ 来执行 Jacobi SVD ，以及 $ O(nd^2) $ 来计算Gram-Schmidt 正交化 。

   

2. 示例：假设网络 $ G $ 的顶点数量 $ n=10^{6} $ ，边的数量为 $ m=10^7 $ ，上下文窗口大小 $ T=10 $ ，逼近因子approximation factor $ \epsilon = 0.1 $ 。

   • NetSMF 调用 PathSampling 算法次数为 $ M=Tm\epsilon^{-2}\log n\simeq 1.4\times 10^{11} $ 次，得到一个稀疏矩阵大约 $ 1.4\times 10^{11} $ 个非零值，稠密度大约为 $ \frac{M}{n^2}\simeq 14\% $ 。

     然后我们在 randomized SVD 中计算 sparse-dense 矩阵乘积，近似矩阵的稀疏性可以大大加快计算速度。

   • NetMF 必须构建一个稠密矩阵，它包含 $ n^2=10^{12} $ 个非零元素，这比 NetSMF 大一个量级。

   通过一个更大的 $ \epsilon $ 我们可以进一步降低 NetSMF 中近似矩阵的稀疏性，而 NetMF 缺乏这种灵活性。

3. 并行化：NetSMF 的每个步骤都可以并行化，从而scale 到非常大的网络。NetSMF 的并行化设计如下图所示。

   • 第一步：我们可以同时启动多个 PathSampling worker 来独立的、并行的采样多个路径，每个 worker 负责采样一批路径。这里，我们要求每个 worker 能够有效访问网络数据集 $ G=(V,E,\mathbf A) $ 。有很多选择可以满足这一要求，最简单的方法是将网络数据的副本拷贝到每个 worker 的内存中。但是如果网络非常大（例如万亿规模），或者 worker 内存受限时，应该采用图引擎来支持随机游走等图操作。

     在这一步结束时，我们设计了一个 reducer 来合并平行边并汇总它们的权重。

   • 第二步：我们可以简单直接地并行计算 $ \tilde{\mathbf M} = \mathbf D^{-1}(\mathbf D - \tilde{\mathbf H}) \mathbf D^{-1} $ 和 $ \mathbf K = \text{trunc_log}^\circ(\frac{\text{vol}_G}{b}\tilde{\mathbf M}) $ 。

   • 第三步：我们可以将稀疏矩阵组织为行优先的格式，这种格式可以在稀疏矩阵和稠密矩阵之间进行高效的乘法运算。其它稠密矩阵的算子（如高斯随机矩阵生成、Gram-Schmidt 正交归一化、Jacobi SVD）可以通过使用多线程或者常见的线性代数库来轻松加速。

   

16.1.4 近似误差分析

1. 我们假设逼近因子 $ \epsilon \lt 0.5 $ 。我们假设顶点的 degree 是降序排列： $ d_\min = d_1\le d_2\le \cdots\le d_n = d_{\max} $ 。 我们令 $ \sigma_i(\mathbf \cdot) $ 为矩阵从大到小排列的奇异值中的第 $ i $ 个奇异值。

   我们首先证明一个结论：令 $ \mathbf F = \mathbf D^{-1/2}\mathbf H \mathbf D^{-1/2} $ ，以及 $ \tilde{\mathbf F} = \mathbf D^{-1/2}\tilde {\mathbf H} \mathbf D^{-1/2} $ ，则有：

   $ \forall i\in \{1,\cdots,n\},\quad \sigma_i(\tilde{\mathbf F} - \mathbf F) \lt 4\epsilon $

   证明：

   $ \mathbf F = \mathbf D^{-1/2}\left( \mathbf D - \frac 1T\sum_{r=1}^T \mathbf D\left(\mathbf D^{-1} \mathbf A\right)^r\right)\mathbf D^{-1/2} = \mathbf I - \sum_{r=1}^T\frac{1}{T}\left(\mathbf D^{-1/2} \mathbf A\mathbf D^{-1/2}\right)^r $

   它是某个图的归一化的拉普拉斯矩阵，因此有特征值 $ \lambda_i(\mathbf F)\in [0,2) $ 。

   由于 $ \tilde {\mathbf F} $ 是矩阵 $ \mathbf F $ 的 $ \epsilon $ spectral sparsifier，因此有：

   $ \forall \mathbf{\vec x}\in \mathbb R^n,\quad \frac{1}{1+\epsilon}\mathbf{\vec x}^\top \mathbf F\mathbf{\vec x} \le \mathbf{\vec x}^\top\tilde {\mathbf F}\mathbf{\vec x} \le \frac{1}{1-\epsilon}\mathbf{\vec x}^\top \mathbf F\mathbf{\vec x} $

   令 $ \mathbf{\vec x} = \mathbf D^{-1/2}\mathbf{\vec y} $ ，则有：

   $ \frac{1}{1+\epsilon}\mathbf{\vec y}^\top \mathbf F\mathbf{\vec y} \le \mathbf{\vec y}^\top\tilde {\mathbf F}\mathbf{\vec y} \le \frac{1}{1-\epsilon}\mathbf{\vec y}^\top \mathbf F\mathbf{\vec y}\\ \rightarrow \left|\mathbf{\vec y}^\top(\tilde{\mathbf F} - \mathbf F)\mathbf{\vec y}\right|\le \frac{\epsilon}{1-\epsilon}\mathbf{\vec y}^\top \mathbf F \mathbf{\vec y}\lt 2\epsilon \mathbf{\vec y}^\top \mathbf F \mathbf{\vec y} $

   其中最后一个不等式是因为 $ \epsilon \lt 0.5 $ 。

   根据瑞利商的性质有： $ |\lambda_i(\tilde{\mathbf F} - \mathbf F)|\le 2\epsilon \lambda_i(\mathbf L) \lt 4\epsilon $ 。

   根据奇异值和特征值的关系，我们有： $ \sigma_i(\tilde{\mathbf F} - \mathbf F) \lt 4\epsilon $ 。

2. 定理： $ \tilde{\mathbf M} - \mathbf M $ 的奇异值满足：

   $ \forall i \in \{1,\cdots,n\},\quad \sigma_i(\tilde{\mathbf M} - \mathbf M) \le \frac{4\epsilon}{\sqrt{d_id_\min}} $

   证明：

   $ \tilde{\mathbf M} - \mathbf M = \mathbf D^{-1}(\tilde{\mathbf H} - \mathbf H)\mathbf D^{-1} = \mathbf D^{-1/2}(\tilde{\mathbf H} - \mathbf H)\mathbf D^{-1/2} $

   根据奇异值的性质，我们有：

   $ \sigma_i(\tilde{\mathbf M} - \mathbf M) \le \sigma_i(\mathbf D^{-1/2})\times \sigma_1(\tilde{\mathbf F} - \mathbf F)\times \sigma_1(\mathbf D^{-1/2})\\ \le \frac{1}{\sqrt d_i}\times 4\epsilon \times \frac{1}{\sqrt {d_\min}} = \frac{4\epsilon}{\sqrt{d_id_\min}} $

3. 定理：令 $ ||\cdot||_F $ 为矩阵的 Frobenius 范数，则有：

   $ \left\|\text{trunc_log}^\circ\left(\frac{\text{vol}_G}{b}\tilde{\mathbf M}\right)-\text{trunc_log}^\circ\left(\frac{\text{vol}_G}{b} {\mathbf M}\right)\right\|_F \le \frac{4\epsilon\text{vol}_G}{b\sqrt{d_\min}}\sqrt{\sum_{i=1}^n \frac{1}{d_i}} $

   证明：很明显 $ \text{trunc_log}^\circ() $ 函数满足是 1- Lipchitz 的。因此我们有：

   $ \left\|\text{trunc_log}^\circ\left(\frac{\text{vol}_G}{b}\tilde{\mathbf M}\right)-\text{trunc_log}^\circ\left(\frac{\text{vol}_G}{b} {\mathbf M}\right)\right\|_F \\ \le \left\|\frac{\text{vol}_G}{b}\tilde{\mathbf M} - \frac{\text{vol}_G}{b} {\mathbf M}\right\|_F = \frac{\text{vol}_G}{b}\left\|\tilde{\mathbf M}- {\mathbf M}\right\|\\ = \frac{\text{vol}_G}{b}\sqrt{\sum_{i=1}^n \sigma_i^2(\tilde{\mathbf M} - \mathbf M)}\le \frac{4\epsilon\text{vol}_G}{b\sqrt {d_\min}}\sqrt{\sum_{i=1}^n\frac{1}{d_i}} $

4. 上述界限是在未对输入网络进行假设的情况下实现的。如果我们引入一些假设，比如有界的 $ d_\min $ 、或者特定的随机图模型（如 Planted Partition Model 或者 Extended Planted Partition Model ），则有望通过利用文献中的定理来探索更严格的边界。

16.2 实验

1. 数据集：我们使用五个数据集，其中四个规模（BlogCatalog, PPI, Flickr, YouTube）相对较小但是已被广泛用于 network embedding 的论文，剩下一个是大规模的 academic co-authorship network 。

   • BlogCatalog 数据集：在线博主的社交关系网络。标签代表博主的兴趣。
   • Flickr 数据集：Flickr网站用户之间的关系网络。标签代表用户的兴趣组，如“黑白照片”。
   • Protein-Protein Interactions:PPI：智人 PPI 网络的子图。顶点标签是从标志基因组hallmark gene set 中获取的，代表生物状态。
   • Youtube 数据集：YouTube 网站用户之间的社交网络。标签代表用户的视频兴趣组，如“动漫、摔跤”。
   • Open Academic Graph:OAG 数据集：一个学术网络，顶点标签位每个作者的研究领域，共有 19 种不同的标签。每位作者可以研究多个领域，所以有多个标签。

   这些数据集的统计信息如下表所示。

   

2. baseline 和配置：我们将 NetSMF 与 NetMF, LINE, DeepWalk, node2vec 等方法进行比较。

   • 所有模型的 embedding 维度设置为 $ d=128 $ 。
   • 对于 NetSMF/NetMF/DeepWalk/node2vec ，我们将上下文窗口大小设为 $ T=10 $ ，这也是 DeepWalk, node2vec 中使用的默认设置。
   • 对于 LINE我们仅使用二阶邻近度，即 LINE(2nd)，负样本系数为 5，边采样的数量为 100亿。
   • 对于 DeepWalk，随机游走序列的长度为40，每个顶点开始的随机游走序列数量为 80，负采样系数为 5 。
   • 对于node2vec，随机游走序列的长度为40，每个顶点开始的随机游走序列数量为 80，负采样系数为 5 。参数 $ p,q $ 从 $ \{0.25,0.5,1,2,4\} $ 中进行 grid search 得到。
   • 对于 NetMF，我们在 BlogCatalog,PPI,Flickr 数据集中设置 $ h=256 $ 。
   • 对于 NetSMF，我们在 PPI,Flickr,YouTube 数据集中设置采样数量 $ M=10^3\times T\times m $ ；我们在 BlogCatalog 数据集中设置采样数量 $ M=10^4\times T\times m $ ；我们在 OAG 数据集中设置采样数量 $ M=10\times T\times m $ 。
   • 对于 NetMF 和 NetSMF，我们设置负采样系数 $ b=1 $ 。

3. 和 DeepWalk 相同的实验步骤执行多标签顶点分类任务：我们首先训练整个网络的 embedding，然后随机采样一部分标记样本来训练一个one-vs-rest 逻辑回归分类模型（通过 LIBLINEAR 实现），剩余的顶点作为测试集。在测试阶段，one-vs-rest 模型产生标签的排序，而不是精确的标签分配。为了避免阈值效应，我们采用在 DeepWalk, LINE, node2vec 中所作的假设，即给定测试数据集中顶点的 label 数量。我们评估测试集的 Micro-F1 指标和 Macro-F1 指标。为了确保实验结果可靠，每个配置我们都重复实验 10 次，并报告测试集指标的均值。所有实验均在配备 Intel Xeon E7-8890 CPU （64 核）、1.7TB 内存、2TB SSD 硬盘的服务器上进行。

   对于 BlogCatalog,PPI 数据集，我们考察分类训练集占比 10%~90% 的情况下，各模型的性能；对于 Flickr,YouTube,OAG 数据集，我们考察分类训练集占比 1%~10% 的情况下，各模型的性能。

   完成的实验结果如下图所示。对于训练时间超过1周的模型，我们判定为训练失败，此时并未在图中给出结果。第二张图给出了模型训练时间，- 表示模型无法在周内完成训练（时间复杂度太高)；x 表示模型因内存不足无法训练（空间复杂度太高）。

   我们首先重点对比 NetSMF 和 NetMF，因为 NetSMF 的目标是解决 NetMF 的效率和可扩展性问题，同时保持 NetMF 的效果优势。从结果可以看到：

   • 在训练速度上：对于大型网络 （YouTube,OAG），NetMF 因为空间复杂度和时间复杂度太高而无法训练，但是 NetSMF 可以分别在4h 内、 24h 内完成训练；对于中型网络（Flickr），二者都可以完成训练，但是 NetSMF 的速度要快2.5倍；对于小型网络，NetMF 的训练速度反而更快，这是因为 NetSMF 的稀疏矩阵构造和分解的优势被 pipeline 中其它因素抵消了。
   • 在模型效果上：NetSMF 和 NetMF 都能产生最佳的效果（和其它方法相比）。在 BlogCatlog 中，NetSMF 的效果比 NetMF 稍差；在 PPI 中，两种方法性能难以区分、在 Flicker 中，NetSMF 的效果比 NetMF 更好。这些结果表明：NetSMF 使用的稀疏谱近似sparse spectral approximation，其性能不一定比稠密的 NetMF 效果更差。

   总之，NetSMF 不仅提高了可扩展性，还能保持足够好的性能。这证明了我们谱稀疏化近似算法的有效性。

   我们还将 NetSMF 与常见的 graph embedding 基准（即 DeepWalk, LINE, node2vec）进行了比较。

   • 对于 OAG 数据集，DeepWalk 和 node2vec 无法在一周内完成计算，而 NetSMF 仅需要 24 小时。根据公开报道的 SkipGram 运行时间，我们预计 DeepWalk 和 node2vec 可能需要几个月的时间来为 OAG 数据集生成 embedding。

     在 BlogCatalog 中，DeepWalk 和 NetSMF 需要差不多的计算时间。而在 Flickr, YouTube, PPI 中，NetSMF 分别比DeepWalk 快 2.75 倍、5.9 倍、24 倍。

     在所有数据集中，NetSMF 比 node2vec 实现了 4 ~ 24 倍的加速。

   • 此外，NetSMF 的性能在 BlogCatalog, PPI, Flickr 中显著优于 DeepWalk。在 YouTube 中，NetSMF 取得了与 DeepWalk 相当的结果。与 node2vec 相比，NetSMF 在 BlogCatalog, YouTube 上的性能相当，在 PPI, Flickr 上的性能显著更好。总之，NetSMF 在效率和效果上始终优于 DeepWalk 和 node2vec 。

   • LINE 在所有五种方法中是效率最高的，然而它的预测效果也最差，并且在所有数据集上始终以很大的差距输给其它方法。总之，LINE 以忽略网络中的 multi-hop 依赖性作为代价从而实现了效率，而所有其它四种方法都支持这些依赖，这证明了 multi-hop 依赖性对于学习 network representation 的重要性。

   • 更重要的是，在除了 LINE 以外的四种方法之间，DeepWalk 既没有达到效率上的优势，也没有达到效果上的优势。node2vec 以效率为代价实现了相对较好的性能。NetMF 以显著增加的时间和空间成本为代价实现了更好的效果。NetSMF 是唯一同时实现了高效率和高效果的方法，使得它能够在一天内在单台服务器上为数十亿规模的网络（例如 9 亿条边的 OAG 网络）学习有效的 embedding 。

   

   

4. 这里我们讨论超参数如何影响 NetSMF 的效率和效果。我们用 Flickr 数据集的 10% 标记顶点作为训练集，来评估NetSMF 超参数的影响。

   • 维度 $ d $ ：我们使用 Cattell Scree 测试。首先从大到小绘制奇异值，然后再图上找出奇异值突变或者趋于均匀的点。从 Flickr 数据的奇异值观察到：当 $ d $ 增加到 100 时，奇异值趋近于零（图b 所示）。因此我们在实验中选择 $ d=2^8=128 $ 。

     我们观察 $ d=2^4\sim2^8 $ 时测试集的指标，可以看到确实当 $ d=128 $ 时模型效果最好。这表明了 NetSMF 可以自动选择最佳的 embedding 维度。

     NetSMF 能够自动选择选择最佳 embedding 维度的前提是计算矩阵 $ \mathbf X \mathbf Y^\top = \text{trunc_log}^\circ \left(\frac{\text{vol}_G}{b}\tilde{\mathbf M}\right) $ 的奇异值。对于大型网络，计算奇异值是不可行的。

   • 非零元素数量：理论上 $ M=O(T\times m\epsilon^{-2}\log n) $ ，当 $ M $ 越大则近似误差越小。不失一般性我们将 $ M $ 设置为 $ k\times T\times m $ ，其中 $ k=\{1,10,,100,200,500,1000,2000\} $ ，我们研究随着 $ M $ 的增大模型性能的影响。

     如图 c 所示，当增加非零元素数量时，NetSMF 效果更好，因为更大的 $ M $ 带来更小的误差。但是随着 $ M $ 的增加，预测性能提升的边际收益在递减。可以看到当 $ M=1000\times T\times m $ 时，NetSMF 的效率和效果得到平衡。

   • 并行性：我们将线程数量分别设置为 1、10、20、30、60，然后考察NetSMF 的训练时间。

     如图d 所示，在单线程时NetSMF 运行了 12 个小时，在30 个线程时NetSMF 运行了 48 分钟，这实现了 15 倍的加速比（理想情况 30 倍）。这种相对较好的亚线性加速比使得 NetSMF 能够扩展到非常大规模的网络。