十六、NetSMF

1. 现有的流行的 Graph Embedding 方法在可扩展性方面存在不足。

   • LINE 具有很好的可扩展性，这是因为它仅对一阶邻近度和二阶邻近度建模。但这也是它的缺点：学到的 embedding 缺失了网络中的高阶邻近关系。
   • DeepWalk/node2vec 基于图上的随机游走和较大上下文尺寸的 SkipGram 对较远的顶点（即全局网络结构）进行建模，但是它们处理大型网络的计算代价太高。
   • NetMF 证明了 DeepWalk/LINE 等价于一个显式的矩阵分解，但是这个矩阵是一个 的稠密矩阵，这使得直接构建和分解这个超大型稠密矩阵的代价非常高。

   鉴于这些方法的局限性（如下表所示），论文 NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization 提出了 NetSMF 模型，该模型具有计算效率高、能捕获全局上下文、能从理论上证明正确性的优点。

   

   NetSMF 的基本思想是：通过一个稀疏矩阵来拟合NetMF 中的稠密矩阵，从而降低矩阵构建成本和矩阵分解成本。

   NetSMF 主要包含三个步骤：

   • 利用谱图稀疏化 spectral graph sparsification 技术对网络的随机游走矩阵多项式 random-walk matrix-polynomial 找到稀疏化器 sparsifier
   • 基于这个稀疏化器构建一个稀疏矩阵，该稀疏矩阵是原始 NetMF 稠密矩阵在谱域上的近似，并且具有更少的非零值。
   • 执行 Randomized SVD 分解算法从而高效地分解该稀疏矩阵，从而得到网络顶点的 embedding 。

   我们设计的 NetSMF 稀疏矩阵在谱域上接近原始的 NetMF 稠密矩阵，从而保留了足够的网络信息。这使得我们从稀疏矩阵中学到的 embedding 几乎和原始NetMF 稠密矩阵中学到的 embedding 一样强大。

   另外论文证明了通过稀疏矩阵来逼近原始 NetMF 稠密矩阵误差的理论上界，从而理论上证明了 NetSMF 的有效性。

   通过各种实验表明：和流行的 Graph Embeding 方法相比，NetSMF 是唯一同时具有效果好、效率高优点的方法。如 NetSMF 在保持和 NetMF 效果相差无几的条件下，训练速度快了几个量级。

2. 给定无向带权图 ，记 。NetSMF 证明了当随机游走序列的长度 时，DeepWalk 隐式的分解矩阵：

   

   其中 也称作图的 volume ， 为矩阵的逐元素 log 。考虑到目标矩阵非零元素太多，以及 是未定义行为，因此NetMF 的目标矩阵调整为：

   

   其中： 。

   NetMF 通过显式分解该矩阵从而得到顶点的 embedding ，但是实践中存在两个挑战：

   • 首先，几乎每一对距离 内的顶点都对应于 NetMF 目标矩阵中的非零项。考虑到很多社交网络和信息网络都具有 small-world 属性：在每一个顶点开始，仅需要几步就可以达到绝大多数顶点。如，截至 2012 年，Facebook 中 92% 的可达到的顶点对之间的距离小于等于 5 。因此，即使设置了一个较小的上下文窗口（如DeepWalk 中默认的 ），NetMF 中目标矩阵也具有 个非零元素。而在大型网络中，这种规模矩阵的构建和分解是不现实的。

   • 其次，计算矩阵的幂 涉及到矩阵乘法，其算法复杂度为 。另外分解 的稠密矩阵的计算代价也较高。

     为降低构建目标矩阵的成本，NetMF 使用top 特征值和特征向量来逼近 。但是这个近似矩阵仍然是稠密的，使得该策略无法处理大型网络。

16.1 模型

1. 谱域相似性Spectral Similarity ：假设有两个带权无向图 和 ，令 和 分别为它们的拉普拉斯矩阵。如果下面的关系成立，我们就说 和 是 谱相似的spectrally similar ：

   

2. 定理九（继续章节15.1.5 的定理编号）：对于随机游走多项式 random-walk molynomial ，其中 ，则可以在 时间复杂度内构造一个 spectral sparsifier ，其中 具有 个非零项。

   对于无权图，时间复杂度可以进一步降低到 。

   证明参考：Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng. 2015. Efficient sampling for Gaussian graphical models via spectral sparsification. In COLT ’15. 364–390. 、Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng. 2015. Spectral sparsification of random-walk matrix polynomials. arXiv preprint arXiv:1502.03496 (2015).

3. 为构建一个包含 个非零项的 sparsifier ，该稀疏化算法包含两步：

   • 第一步获得一个针对 的初始化 sparsifier，它包含 个非零项。
   • 第二步使用标准的谱稀疏化算法spectral sparsification algorithm 来进一步降低非零项到 。

   本文我们仅仅应用第一步，因为一个包含 个非零项的稀疏矩阵已经足够可用，所以我们并没有采用第二步，这能够避免额外的计算。下面讲到的所有随机游走多项式稀疏化算法random-walk molynomial sparsification algorithm 都仅包含第一步。

4. 我们取 ，因此有：

   

   我们定义：

   

   因此有： 。

   采用 的稀疏化版本 ，我们定义 。可以发现 也是一个稀疏矩阵，其非零元素的规模和 非零元素规模相当。

   最终我们可以分解这个稀疏矩阵从而获得每个顶点的 embedding ：

   

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

   • 随机游走多项式的稀疏化Random-Walk Molynomial Sparsification ：我们首先构建一个网络 ，它具有和 相同的顶点但是不包含任何边。然后我们重复 Path-Sampling 路径采样算法 次，从而得到 条边，这些边构成了 的非零项。在每一次迭代过程中：

     • 首先均匀随机选择一条边 ，均匀随机选择一个路径长度 。

     • 然后从顶点 开始进行 步随机游走，得到顶点序列 ；从顶点 开始进行 步随机游走，得到顶点序列 。这一过程产生了一个长度为 的路径 。同时我们计算：

       

     • 最后我们向图 中添加一条新的边 ，其权重为 。如果边已经存在，则相同的边进行合并（只需要将权重相加即可）。

       这条新的边代表了图 中一条长度为 的随机游走序列，权重就是转移概率。

     最终我们计算 的未归一化的拉普拉斯矩阵 ，它具有 个非零项。

   • 构建 NetMF 稀疏器 sparsifier ：即计算 。这一步并未改变非零项的规模。

   • 截断的奇异值分解 truncated singular value decomposition ：对 执行 维的 RandomizedSVD 分解。

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

6. NetSFM 算法：

   • 输入：

     • 图
     • 非零项的数量
     • embedding 维度

   • 输出：顶点 embedding 矩阵

   • 算法步骤：

     • 初始化 ，即只有顶点没有边。

     • 迭代 ，迭代步骤为：

       • 均匀随机选择一条边

       • 均匀随机选择一个长度

       • 随机采样一条路径：

       • 添加边 到 中，边的权重为 。

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

     • 计算 的未归一化的拉普拉斯矩阵

     • 计算

     • 对 执行 维的 RandomizedSVD 分解，得到 。

     • 返回 。

7. PathSampling 算法：

   • 输入：

     • 图
     • 边
     • 采样的路径长度

   • 输出：路径的初始顶点 、结束顶点 、路径 值

   • 算法步骤：

     • 均匀随机采样一个整数

     • 从顶点 开始执行 步随机游走，采样到的顶点记作 。

     • 从顶点 开始执行 步随机游走，采样到的顶点记作 。

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

       

     • 返回

8. Randomized SVD 算法：

   • 输入：

     • 一个稀疏的对称矩阵 。我们以行优先的方式存储矩阵，从而充分利用对称性来简化计算。
     • 目标维度

   • 输出：SVD 矩阵分解的

   • 步骤：

     • 采样一个高斯随机矩阵 作为投影矩阵。
     • 计算映射后的矩阵
     • 对矩阵 进行正交归一化
     • 计算矩阵
     • 采样另一个高斯随机矩阵 作为投影矩阵。
     • 计算映射后的矩阵 。
     • 对矩阵 进行正交归一化。
     • 计算矩阵 。
     • 对 执行 Jacobi SVD 分解：
     • 返回

9. 基于 SVD 分解的一个优点是：我们可以通过 Cattell’s Scree 测试来选择合适的 embedding 维度 ：通过从大到小来绘制奇异值，然后选择奇异值明显下降、或者奇异值开始趋向于均匀的 。

10. PathSampling 算法的说明：

    • 引理：给定一个长度为 的路径 ，则PathSampling 算法采样到该路径的概率为：

      

      其中：

      

    • 引理：假设采样到一个长度为 的路径 ，则新的边 的权重应该为：

      

    • 根据上述引理，则添加到 中的边的权重为：

      

      对于无向图，则 ，则权重简化为 。

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

16.2 复杂度

1. 算法复杂度：

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

     另外我们需要 的空间存储 ，以及额外的 空间来存储算法的输入。

   • 第二步：我们需要 的时间来计算 以及 。

     另外我们需要 空间来存储degree 矩阵 ， 的空间来存储 。

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

   

2. 示例：假设网络 的顶点数量 ，边的数量为 ，上下文窗口大小 ，逼近因子approximation factor 。

   • NetSMF 调用 PathSampling 算法次数为 次，得到一个稀疏矩阵大约 个非零值，稠密度大约为 。

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

   • NetMF 必须构建一个稠密矩阵，它包含 个非零元素，这比 NetSMF 大一个量级。

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

3. NetSMF 的每个步骤都可以并行化，从而scale 到非常大的网络。

   • 第一步：我们可以同时启动多个 PathSampling worker 来独立的、并行的采样多个路径，每个 worker 负责采样一批路径。
   • 第二步：我们可以简单直接地并行计算 和 。
   • 第三步：我们可以将稀疏矩阵组织为行优先的格式，这种格式可以在稀疏矩阵和稠密矩阵之间进行高效的乘法运算。

16.3 近似误差分析

1. 我们假设逼近因子 。我们假设顶点的 degree 是降序排列： 。 我们令 为矩阵从大到小排列的奇异值中的第 个奇异值。

   我们首先证明一个结论：令 ，以及 ，则有：

   

   证明：

   

   它是某个图的归一化的拉普拉斯矩阵，因此有特征值 。

   由于 是矩阵 的 spectral sparsifier，因此有：

   

   令 ，则有：

   

   其中最后一个不等式是因为 。

   根据瑞利商的性质（15.1 中的定理七）有： 。

   根据奇异值和特征值的关系（15.1 中的定理五），我们有： 。

2. 定理十： 的奇异值满足：

   

   证明：

   

   根据奇异值的性质（15.1 中的定理六），我们有：

   

3. 定理十一：令 为矩阵的 Frobenius 范数，则有：

   

   证明：很明显 函数满足是 1- Lipchitz 的。因此我们有：

   

16.3 实验

1. 数据集：

   • BlogCatalog 数据集：由博客作者提供的社交关系网络。标签代表作者提供的主题类别。
   • Flickr 数据集：Flickr网站用户之间的关系网络。标签代表用户的兴趣组，如“黑白照片”。
   • Protein-Protein Interactions:PPI：该数据集包含蛋白质和蛋白质之间的关联，标签代表基因组。
   • Youtube 数据集：YouTube 网站用户之间的社交网络。标签代表用户的视频兴趣组，如“动漫、摔跤”。网络包含 1138499 个顶点、2990443 条边、47 种不同标签。
   • Open Academic Graph:OAG 数据集：一个学术网络，它包含 67,768,244 位作者和 895,368,962 条无向边。顶点标签位每个作者的研究领域，共有 19 种不同的标签。每位作者可以研究多个领域，所以有多个标签。

   

2. 模型配置：

   • 所有模型的 embedding 维度设置为
   • 对于 NetSMF/NetMF/DeepWalk/node2vec ，我们将上下文窗口大小设为
   • 对于 LINE我们仅使用二阶邻近度，即 LINE(2nd)，负样本系数为 5，边采样的数量为 100亿。
   • 对于 DeepWalk，随机游走序列的长度为40，每个顶点开始的随机游走序列数量为 80，负采样系数为 5 。
   • 对于node2vec，随机游走序列的长度为40，每个顶点开始的随机游走序列数量为 80，负采样系数为 5 。参数 从 中进行 grid search 得到。
   • 对于 NetMF，我们在 BlogCatalog,PPI,Flickr 数据集中设置 。
   • 对于 NetSMF，我们在 PPI,Flickr,YouTube 数据集中设置采样数量 ；我们在 BlogCatalog 数据集中设置采样数量 ；我们在 OAG 数据集中设置采样数量 。
   • 对于 NetMF 和 NetSMF，我们设置负采样系数 。

3. 和 DeepWalk 相同的实验步骤，我们首先训练整个网络的 embedding，然后随机采样一部分标记样本来训练一个one-vs-rest 逻辑回归分类模型，剩余的顶点作为测试集。我们评估测试集的 Micro-F1 指标和 Macro-F1 指标。为了确保实验结果可靠，每个配置我们都重复实验 10 次，并报告测试集指标的均值。

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

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

   • 我们首先重点对比 NetSMF 和 NetMF：

     • 在训练速度上：对于大型网络 （YouTube,OAG），NetMF 因为空间复杂度和时间复杂度太高而无法训练，但是 NetSMF 可以在 24h 内完成训练；对于中型网络（Flickr），二者都可以完成训练，但是 NetSMF 的速度要快2倍；对于小型网络，NetMF 的训练速度反而更快，这是因为 NetSMF 的稀疏矩阵构造和分解的优势被 pipeline 中其它因素抵消了。
     • 在模型效果上：NetSMF 和 NetMF 都能产生最佳的效果（和其它方法相比），并且 NetSMF 性能相比 NetMF 略有下降。

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

   

   

4. 我们用 Flickr 数据集的 10% 标记顶点作为训练集，来评估NetSMF 超参数的影响。

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

     我们观察 时，测试集的指标。可以看到确实当 时模型效果最好。这表明了 NetSMF 可以自动选择最佳的 embedding 维度。

   • 非零元素数量：理论上 ，当 越大则近似误差越小。不失一般性我们将 设置为 ，其中 ，我们研究随着 的增大模型性能的影响。

     如图 c 所示，当增加非零元素数量时，NetSMF 效果更好，因为更大的 带来更小的误差。但是随着 的增加，预测性能提升的边际收益在递减。

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

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