八、SDNE

1. 网络 representation 学习有以下几个主要挑战：

   • 高度非线性 non-linear：网络的底层结构是高度非线性的，如何设计模型来捕获这种高度非线性相当困难。
   • 保留结构 structure-preserving：如何在低维空间种保留原始网络的全局结构和局部结构也是一个难点。
   • 网络稀疏性 sparsity ：大多数现实世界的网络非常稀疏，仅利用已观察到的有限链接不足以获得效果较好的 representation 。

2. 高度非线性：过去的几十年提出了很多基于浅层模型的网络embedding 方法，如 IsoMap, Laplacian Eigenmaps(LE), LINE 。由于浅层模型的表达能力有限，所以这些方法很难捕获高度非线性的网络结构，因此得到的是次优（非最优）的网络representation 。

   尽管可以采用核技巧来捕获非线性，但是核技巧本身也是浅层的。

3. 保留结构：有一些方法，如 LINE, GraRep,WALKLETS 尝试分别使用一阶邻近度和高阶邻近度来保留局部结构和全局结构。其做法是分别学习一阶representation 和高阶 representation，然后简单的将二者拼接在一起。

   与在一个统一模型中同时建模局部网络结构和全局网络结构相比，这种方法不是最优的。

4. 论文 《Structural Deep Network Embedding》 提出了 SDNE 模型。

   • 模型利用多个非线性层来捕获非线性的网络结构。这些非线性层的组合将原始数据映射到高度非线性的潜在低维空间中，从而能够捕获到网络结构的高度非线性。

   • 一阶邻近度是直接相连的两个顶点之间的局部的、成对的相似性，它刻画了网络的局部结构。但是由于网络的稀疏性，很多真实存在的链接由于未被观察到所以缺失，这导致仅依赖一阶邻近度不足以描述整个网络。二阶邻近度表示顶点邻域结构的相似性，它刻画了网络的全局结构。

     通过一阶邻近度和二阶邻近度，我们可以很好的刻画网络本地结构和网络全局结构。而 SDNE 模型就利用一阶邻近度和二阶邻近度来保留网络结构。其中使用无监督学习来利用二阶邻近度从而捕获全局网络结构，使用监督学习来利用一阶邻近度从而捕获局部网络结构。

     通过在一个优化目标中同时优化这两者，SDNE 既可以保留局部网络结构，又可以保留全局网络结构。

     同时，由于网络二阶邻近度非零的顶点对比一阶邻近度数量多得多，因此采用二阶邻近度可以提供更多的网络结构信息，这有助于解决网络稀疏性问题。

     如下图所示，二阶邻近度顶点对的数量与一阶邻近度顶点对数量对比：

     

8.1 模型

1. 定义图 ，其中 为顶点集合； 为边的集合， 表示顶点 之间的边，它带有一个权重 。

   • 如果 之间不存在边，则 。
   • 对于无权图有 ，对于带权图有 ，其中 表示所有的正实数，这里不考虑负权重。

2. 一阶邻近度 First-Order Proximity 刻画了成对顶点之间的相似性。

   对于顶点对 ，其一阶邻近度就是 ：

   

   网络嵌入必须保持一阶邻近度，这意味着如果两个顶点是直接相连的则它们总是相似的。如：如果一篇论文引用了另一篇论文，则它们应该包含一些共同主题。

   但是现实世界的网络通常非常稀疏，观察到的链接仅占很小的比例，许多彼此相似的顶点之间没有任何直接链接，因此仅仅捕获一些邻近度是不够的。

3. 二阶邻近度 Second-Order Proximity 刻画了一对顶点的邻居之间的相似度。

   令顶点 与所有其它顶点的一阶邻近度为 ，因此顶点 和 的二阶邻近度由 的相似度来定义：

   

   其中 ， 为向量长度。

   二阶邻近度假设：若两个顶点的共同邻居越多，则它们越相似。该假设在很多领域是合理的。如：在 NLP 中，如果两个单词的上下文越相似，则这两个单词越相似；在社交网络中，如果两个用户的共同好友越多，则他们是好友的可能性越大。

   已经证明二阶邻近度是刻画顶点相似性的一个良好指标，即使这两个顶点之间不存在直接相连的边。因此通过引入二阶邻近度可以更好的描述网络全局结构，并且缓解网络稀疏性问题。

4. 网络表示任务的目标是对每个顶点 ，学习一个低维映射函数 ，其中 ，最终得到顶点 的低维表达 。

   在映射的过程中还需要保持网络结构，即：同时保留网络的一阶邻近度和二阶邻近度。

5. 给定图 另其邻接矩阵为 ，其第 行 刻画了顶点 的邻域结构，因此矩阵 刻画了所有顶点的邻域结构。

   SDNE 基于 和深度自编码器来保留二阶邻近度。深度自编码器首先通过编码器将输入数据映射到 representation 空间，然后通过解码器将 representation 数据映射回原始空间，在这个过程中保持重构误差最小化。

   对于顶点 ，假设原始输入数据为 。由于我们将邻接矩阵 作为自编码器的输入，因此有 。

   • 假设编码器为 层，则编码过程为：

     

     其中 为非线性激活函数， 为编码器参数。

   • 假设解码器为 层，则解码过程为：

     

     其中 ：

     • 为解码器参数。
     • 解码器多出来的一层是 。
     • 解码器层数也可以是任意层，不一定和编码器层数相关。

   • 最终自编码器的损失函数为重构误差：

     

     尽管最小化 的重构误差并未明确保留样本之间的邻域结构，但是基于重构误差最小化准则可以捕捉到数据流形从而保留顶点的二阶邻近度。最终重构过程使得具有相似邻域结构的顶点具有相似的潜在 representation 。

6. 在网络中我们虽然能够观察到部分链接，但是很多实际中存在的链接由于无法观察而缺失。这意味着：虽然顶点之间存在链接确实表明它们之间的相似，但是顶点之间不存在链接不一定表明它们不相似。

   此外，由于网络的稀疏性 中非零元素远远少于零元素的数量，如果直接使用 作为自编码器的输入，则自编码器更倾向于重建零元素。而这不是我们期望的行为。

   为解决该问题，我们在重构中对非零元素赋予比零元素更大的误差，因此调整目标函数为：

   

   其中 表示 Hadamard 积， 是 的误差权重向量：

   

   即：

   • 若顶点 存在链接（即 ），则误差权重为 ，其中 为超参数。
   • 若顶点 不存在链接（即 ），则误差权重为 1 。

7. 我们利用无监督部分重构顶点之间的二阶邻近度从而保留网络的全局网络结构。

   但是我们不仅要保留网络的全局结构，还需要保留网络的局部结构。

   一阶邻近度可以表示网络的局部结构，因此可以作为监督信息从而约束顶点的 representation 。因此 SDNE 设计了监督部分来保留局部网络结构，监督部分的损失函数为：

   

   其中：

   • 为顶点 的低维 representation， 为顶点 的低维 representation。
   • 为顶点 之间的一阶邻近度。

   该损失函数参考了 Laplacian Eigenmaps 的思想：相似顶点在嵌入空间中映射越远则损失越大。

   越大则顶点 越相似，此时它们距离 应该越小。

8. 为同时保留一阶邻近度和二阶邻近度，SDNE 提出了一个半监督学习模型，其目标函数为：

   

   其中：

   • 为网络的邻接矩阵，它作为网络的输入。

   • 为深度自编码器对网络输入的重构结构

   • 为误差权重，当 时 ；当 时 。

   • 为 正则化项，用于防止过拟合：

     

   • 为系数，用于平衡无监督损失、监督损失、正则化项。

   SDNE 的整体架构如下所示，模型采用多层神经网络将输入数据映射到高度非线性的潜在空间来捕获高度非线性的网络结构。

   

9. 由于模型的高度非线性，目标函数的最优化过程在参数空间中很容易陷入局部最优解。为了找到一个更好的参数空间，SDNE 首先使用深度信念网络对参数进行预训练。

10. 对于网络加入的新顶点 ，如果它和其它旧顶点相连，则我们可以得到邻接向量 ，其中 表示顶点 和旧顶点 的链接权重。

    然后我们固定其它参数，将 加入模型来训练从而得到其 representation。

    如果 不与所有的旧顶点相连，则目前所有的已知方法都无法处理。此时我们需要求助其它辅助信息，如新顶点的内容特征。

11. SDNE 模型的训练复杂度为 ，其中： 为顶点数量， 为网络所有顶点的平均 degree， 为神经网络所有层的最大维度， 为迭代数量。 这里 主要和 相关。

    参数 通常和 representation 的维度相关，与顶点数量无关；迭代数量 也独立于顶点数量；网络顶点的平均 degree 通常被视为一个常量，如：社交网络中平均每个人的好友数量是有限的。因此 都与顶点数量无关，模型训练的整体复杂度和顶点数量成线性关系。

8.2 实验

1. 数据集：

   • ARXIV GR-QC 数据集：该数据集包括 arXiv 上广义相对论General Relativity 和量子力学 Quantum Cosmology 领域的论文的作者关联信息。每个顶点代表一个作者，边代表两个作者共同撰写了论文。

     因为我们没有顶点类别信息，因此该数据集用于链接预测任务。

   • 20-NEWSGROUP ：该数据集包含两万个新闻组文档，每篇文档都标记为20个类别之一。我们用单词的 tf-idf 向量表示文档，用余弦相似度表示文档之间的相似性。网络中每个顶点代表一篇文档，边代表文档之间的相似性。

     我们选择以下三类标签的文档来执行可视化任务：comp.graphics,rec.sport.baseball,talk.politics.gums。

   • BLOGCATALOG,FLICKR,YOUTUBE 数据集：这些数据集用于多标签分类任务。

     • BlogCatalog：该数据集包含 BlogCatalog 网站上博客作者之间的社交关系，标签代表通过元数据推断出来的博客兴趣。网络包含 39 种不同标签。
     • Flickr 数据集：Flickr网站用户之间的关系网络。标签代表用户的兴趣组，如“黑白照片”。网络包含195 种不同标签。
     • YouTube 数据集：YouTube 网站用户之间的社交网络。标签代表用户的视频兴趣组，如“动漫、摔跤”。网络包含 47 种不同标签。

   这些数据集分别代表了加权图/无权图、稀疏图/稠密图、小型图/大型图。总体统计如下表：

   

2. 基准模型：

   • DeepWalk：使用截断的随机游走和 SkipGram 模型来生成网络表达。
   • LINE：分别定义损失函数来保留一阶邻近度和二阶邻近度来求解一阶邻近度representation 和二阶邻近度 representation，然后将二者拼接一起作为 representation 。
   • GraRep：扩展到高阶邻近度并基于 SVD 分解来求解模型。它也是拼接了一阶邻近度 representation 和高阶邻近度 representation 作为最终的表达。
   • Laplacian Eigenmaps：通过分解邻接矩阵的拉普拉斯矩阵来生成网络表达，它仅仅保留了网络的一阶邻近度。
   • Common Neighbor：它仅使用共同邻居的数量来衡量顶点之间的相似性。该方法仅在链接预测任务中作为基准方法。

3. 我们分别执行了顶点重建、链接预测、多标签分类和顶点可视化任务。

   • 对于顶点重建和链接预测任务，我们采用 precision@k 和 Mean Average Precision:MAP 指标。

     • precision@k 指标：

       

       其中： 为顶点集合； 为预测结果中顶点 在所有顶点预测结果中排名，得分越高排名越靠前； 表示顶点 和 中确实存在边。

       该指标的物理意义为：预测结果的 top k 顶点中，和顶点 真实存在边的顶点比例。

       该指标仅仅考察单个顶点，无法评估所有顶点的效果。

     • MAP 指标：

       

       其中 刻画了单个顶点在top1,... top K 的 precision，而 进一步评估了所有顶点在所有 top1,... top K 上的precision 。

   • 对于多标签分类任务，我们使用 Micro-F1 和 Macro-F1 指标。

4. 模型参数：

   • 对于 LINE 模型，随机梯度下降的 batch-size=1，初始化学习率为 0.025，负采样比例为 5 ，总采样的样本数为 100 亿。

     最终将一阶邻近度表达和二阶邻近度表达拼接形成拼接向量，并使用 归一化。

   • 对于 DeepWalk 模型，共现窗口大小设置为 10，每个顶点开始的游走序列数量为 40，每个游走序列长度为 40 。

   • 对于 GraRep，最高转移矩阵阶数为 5 。

   • 对于 SDNE，深度自编码器的层数随着不同数据集而不同，层数和各层维度见下表。如果使用更深的模型，则由于优化困难导致性能几乎不变甚至更差。

     另外 SDNE 通过验证集上执行网格搜索来选择最佳超参数 。

     

8.2.1 网络重建任务

1. 进行网络重建任务是为了验证：良好的网络embedding 模型应该确保学到的 embedding 能够保留原始的网络结构。

   验证方式：给定一个网络，通过模型来学习网络的representation，然后基于 representation 来重建网络并评估误差。

   注意：这里的误差是训练误差，而不是测试误差。因为网络的链接用于生成矩阵 作为模型输入，所以所有的链接是已知的。

   由于所有链接是已知的，因此可以作为 label；而得到 representation 之后可以得到每个顶点的 top k 相似顶点。基于二者我们可以计算 precision@k 和 MAP 指标作为训练误差。

   我们使用 ARXIV GR-QC 和 BLOGCATALOG 数据集来验证，结果如下。可以看到：

   • SDNE 在两个数据集上 MAP 指标始终超越其它模型。

   • 当 增加时，SDNE 在两个数据集上 precision@k 始终最高。

   • SDNE 和 LINE 均优于 LE，这表明引入二阶邻近度可以更好的保留网络结构。

   • 尽管 SDNE 和 LINE 都利用了一阶邻近度和二阶邻近度来保留网络结构，但是 SDNE 效果超越了 LINE，原因可能有两个：

     • LINE 采用浅层结构，因此难以捕获底层网络的高度非线性结构。
     • LINE 直接将一阶邻近度的表达和二阶邻近度的表达拼接在一起，这比 SDNE 直接联合优化一阶邻近度和二阶邻近度要差。

   

   

8.2.2 多标签分类任务

1. 对于 BLOGCATALOG 我们随机抽取 10% 到 90% 的顶点作为训练集，剩余顶点作为测试集；对于 FLICKR,YOUTUBE 我们随机抽取 1% 到 10% 的顶点作为训练集，剩余顶点作为测试集。另外我们删除 YOUTUBE 中没有任何标签的顶点。

   我们随即重复此过程五次并报告平均的 Micro-F1 和 Macro-F1 指标。

   BLOGCATALOG 结果如下：

   

   FLICKR 结果如下：

   

   YOUTUBE 结果如下：

   

   可以看到：

   • SDNE 的效果始终超越其它模型，证明SDNE 可以推广到多标签分类任务中。

   • 在 BLOGCATALOG 数据集中，当只有 10% 的训练数据集时 SDNE 比其它模型有显著提升。这表明 SDNE 相比于基准模型，它对于数据稀疏性鲁棒性更好。

   • 大多数情况下 DeepWalk 效果最差。这有两个原因：

     • DeepWalk 没有明确的目标来捕获网络结构。
     • DeepWalk 使用随机游走来产生顶点的邻居。由于随机性这会引入很多噪音，尤其对于 degree 很高的顶点。

8.2.3 链接预测

1. 在链接预测任务中，我们随机隐藏了一部分已有链接，然后用剩下的网络来训练模型。训练完成之后我们获得每个顶点的表达，然后基于顶点表达预测未观察到的链接。

   和网络重建任务不同，链接预测任务预测的是未观察到的链接，而不是重建观察到的链接。因此链接预测任务可以评估不同模型的预测能力。

2. 在连接预测任务中，我们增加了 Common Neighbor 基准方法，该方法已被证明是进行链接预测的有效方法。

3. 这里使用 ARXIV GR-QC 数据集。首先随机隐藏 15% 的链接（大约 4000 个链接），并使用 precision@k 作为评估指标。

   当 从 2 逐渐增加到 10000 时，实验结果如下。

   结论：

   • 当 增加时，SDNE 方法始终由于其它方法。这证明了 SDNE 学到的representation 对于未观察到的链接具有很好的预测能力。

   • 当 时，SDNE 的precision 仍然高于 0.9，而其它方法的 precision 掉到 0.8 以下。

     这表明 SDNE 对于排名靠前的链接预测的比较准。对于某些实际应用，如推荐和信息检索，这种优势非常重要。因为这些应用更关心排名靠前的结果。

   

4. 我们随机删除原始网络的一部分链接从而产生更稀疏的网络，然后重复上述步骤来执行链接预测，从而评估稀疏网络的链接预测能力。

   结论：

   • 当网络更稀疏时，LE 和 SDNE/LINE 模型之间的差距增大。这表明：二阶邻近度的引入使得学到的表达对于稀疏网络鲁棒性更好。
   • 当删除 80% 链接时，SDNE 仍然比所有其它方法好。这表明：SDNE 在处理稀疏网络时能力更强。

   

8.2.4 可视化任务

1. 我们将 20-NEWSGROUP 学到的网络表达通过 t-SNE 进行可视化。每篇文档都被映射到二维空间的一个点，不同类别的文档采用不同颜色：rec.sport.baseball 为蓝色、comp.graphics 为红色、talk.politics.guns 为绿色。可视化结果如下图所示。

   结论：

   • LE 和 DeepWalk 的效果较差，因为不同类别的顶点彼此混合。
   • LINE 虽然不同类别形成了簇，但是中间部分不同类别的文档依然彼此混合。
   • GraRep 效果更好，但是簇的边界不是很清晰。
   • SND 在簇的分组以及簇的边界上表现最佳。

   

   另外我们也评估了可视化的LK 散度指标，该指标越低越好。从下表可见，SDNE 效果最好。

   

8.2.5 参数探索

1. 我们在 ARXIV-GRQC 数据集上研究不同超参数的影响。

2. 维度 探索：

   • 当维度增加时效果先提升。这是因为更大的维度可以容纳更多的有效信息。
   • 继续增加维度将导致效果下降。这是因为太大的维度会引入更多的噪音。
   • 总体而言维度大小很重要，但 SDNE 对此参数不是特别敏感。

   

3. 参数 探索 ：参数 用于平衡一阶邻近度和二阶邻近度的损失权重。

   • 当 时，模型性能完全取决于二阶邻近度；当 越大，模型性能越趋近于一阶邻近度。
   • 当 或者 时模型性能最佳。这表明：一阶邻近度和二阶邻近度对于刻画网络结构都是必不可少的。

   

4. 参数 探索：参数 控制了 中非零元素的重建， 越大则模型越倾向于重建非零元素。

   • 当 时效果不佳。因为 表示模型重构 时认为零元素和非零元素都是同样重要的。

     如前所述，虽然两个结点之间没有链接不一定表示两个结点不相似，但是两个结点之间存在链接一定表明两个结点的相似性。因此非零元素应该比零元素更加重要。所以 在零元素的重构中引入大量噪声，从而降低模型性能。

   • 当 太大时性能也较差。因为 很大表示模型在重构中几乎忽略了 的零元素，模型倾向于认为每一对顶点之间都存在相似性。事实上 之间的很多零元素都表明顶点之间的不相似。所以 太大将忽略这些不相似，从而减低性能。

   • 这些实验表明：我们应该更多的关注 中非零元素的重构误差，但是也不能完全忽略 中零元素的重构误差。