十二、GraphGAN

1. 目前的Graph Rresentation Learning 图表示学习方法可以分为两类：

   • 用于学习图的 underlying connectivity distribution 底层连接分布的生成模型。

     类似于经典的生成模型（如混合高斯模型、LDA 模型），生成式图表示学习学习模型假设对每个顶点 ，都存在一个潜在的真实连接分布 。这个真实的连接分布表明了 和图中其它顶点之间的连接性偏好。因此可以将图中存在的边视为从这些条件分布中生成的观测样本，并且生成模型可以通过最大化图中边的概率来学习顶点的 embedding 。

     如 DeepWalk 使用随机游走来为每个顶点采样上下文顶点，然后最大化给定顶点观测到的上下文顶点的对数似然。Node2vec 通过提出一个有偏的随机游走过程进一步拓展了这个思想，当为给定顶点选择上下文顶点时，这会提供更大的灵活性。

   • 用于预测一对顶点pair 对之间存在边的可能性的判别模型。

     与生成模型不同，判别模型不再将边视为从潜在的条件分布中产生，而是学习用于直接预测边的存在性的分类器。

     通常判别模型联合一对顶点 pair 对 作为特征，然后预测这对顶点之间存在边的概率 。

     如 SDNE 使用高维稀疏的顶点邻接向量作为每个顶点的原始特征，并通过应用自编码器，基于边是否存在的监督信息来提取顶点的 embedding 。PPNE 通过在正样本（连接的顶点pair 对）、负样本（断开的顶点 pair 对）上进行监督学习，直接学习顶点 embedding ，并在学习过程中保留顶点的固有属性。

   受 GAN 启发，论文 《GraphGAN: Graph Representation Learning with Generative Adversarial Nets》 提出了 GraphGAN 模型，一种结合了上述两种方法的新的图表示学习框架。

   具体而言，GraphGAN 在学习过程中训练两个模型：

   • 生成器 ：它试图尽可能地拟合底层的真实连接分布 ，并生成与顶点 最可能连接的顶点，即 fake 顶点。
   • 判别器 ：它试图区分well-connected 顶点对与 ill-connected 顶点对，并计算顶点 和 之间存在边的概率。

   生成器 和判别器 在 min-max game 中分别扮演两个角色：

   • 生成器 在判别器 提供的指导下生成最难区分的 fake 顶点。
   • 判别器 试图区分真实顶点和 fake 顶点，从而避免被生成器欺骗。

   通过在game 中相互竞争，最终它们都提高了自己的能力，直到生成器 和 无法区分为止。

2. 传统 softmax 及其变体不适于生成器，原因有两个：

   • 对给定的顶点 ， softmax 对所有其它顶点一视同仁，完全没有考虑到图的结构信息。
   • softmax 的计算涉及到图中的所有顶点，这既低效又耗时。

   为克服这些限制， GraphGAN 提出了一种新的图 softmax ，称作 Graph Softmax。论文证明了 Graph Softmax 满足归一性normalization、结构感知graph structure awareness、计算高效computational efficiency 等优点。

   另外，GraphGAN 对生成器提出了一种基于随机游走的生成策略，该策略与 Graph Softmax 的定义一致，从而大大降低了计算复杂度。

3. 论文在五个真实世界的图数据集上执行三个任务（链接预测、顶点分类、推荐），实验结果表明 GraphGAN 在 SOA 基准方法上取得相当大的提升。这归功于统一的对抗学习框架，以及捕获了图结构信息的 Graph Softmax 。

12.1 模型

1. 设图 ，其中 为顶点集合， 为边集合。

   给定顶点 ，定义 为 直接相连的顶点集合，定义 的底层真实连接分别为 。

   • 反映了 和所有其它顶点的连接分布。
   • 可以视为从 中采样到的观测样本。

2. 给定图 ，GraphGAN 的目标是学习两个方法：

   • 生成器 generator ：它的目标是逼近 ，然后针对 生成最有可能和它连接的顶点。更准确的说，是从 中选择和 最有可能连接的顶点。
   • 判别器 discriminator ：它的目标是判断顶点 pair 对 之间的连接性。它输出一个标量，代表顶点 和 之间存在边的概率。

   生成器 和判别器 扮演两种角色：

   • 生成器 试图完美拟合 ，然后生成fake 顶点。这些生成的顶点和 真实连接的邻居顶点相似，从而欺骗判别器。
   • 判别器 试图检测这些顶点是否是 的真实相连的顶点，还是由生成器 生成的 fake 顶点。

   形式化的，生成器 和判别器 正在参与具有以下值函数 的双人 min-max 游戏：

   

   其中生成器和判别器的参数可以通过交替最大化和最小化值函数 来学习。

3. GraphGAN 整体框架如下图所示。每次迭代过程中，我们使用来自 的正样本（绿色顶点）和来自生成器 的负样本（带蓝色条纹的顶点）来训练判别器 ，并在 的指导下使用策略梯度更新生成器 。

   和 之间的竞争趋势它们都改进自己的参数，直到 与 无法区分。

   

12.1.1 判别器

1. 给定从真实连接而来的正样本，以及从生成器而来的负样本，判别器 的目标是最大对数似然。

   如果判别器 是可微的，则可以通过针对 的梯度上升来解决。

2. 在 GraphGAN 中，我们简单的定义判别器 为两个输入顶点的 embedding 内积的 sigmoid 函数：

   

   其中 分别是判别器 中顶点 和 的 维 representation 向量， 。

   注意到这里仅包含 和 ，这意味着给定一对样本 ，我们仅仅需要通过对应的梯度上升来更新 和 ：

   

   既：没必要更新全网顶点的 embedding 。

3. 理论上 SDNE 等任何判别式模型都可以用作判别器 ，论文将如何选择合适的判别器作为未来的研究。

12.1.2 生成器

1. 和判别器相比，生成器 的目标是：使得判别器 区分 生成的fake 顶点的概率最小化。

   即：生成器通过调整参数 ，从而增加其生成的 fake 顶点在判别器 中的得分。

2. 由于生成器采样的顶点 是离散的，因此遵循 Schulman 等人的做法，论文建议通过策略梯度policy gradient计算 对 的梯度：

   

   为生成器采样的顶点数量。

   其中倒数第二行是因为 。

   梯度 的物理意义为 的加权和，权重为 。

   • 当 更容易被判别器 识别时， 得分较小，则加权的权重较大。
   • 当 更不容易被判别器 识别时， 得分较大，则加权的权重较小。

   这表明：当我们对 应用梯度下降时，更容易被判别器 区分的fake顶点将“拉扯”生成器，使其得到一个较大的更新。

3. 生成器 最简单直接的实现方式是通过 softmax 函数来实现：

   

   其中 为分别是生成器 中顶点 和 的 维 representation 向量， 。

4. 为了在每轮迭代中更新 ，我们首先基于 计算近似的连接分布，然后根据该分布随机采样一组 ，然后通过随机梯度下降法来更新 。

12.1.3 Graph Softmax

1. 在生成器中应用 softmax 有两个限制：

   • 计算 的 softmax 函数时，包含图中的所有顶点的embedding 。这意味着对于每个生成的样本 ，我们需要计算梯度 ，然后更新所有顶点。

     这种方式计算效率太低，尤其是对于具有数百万个顶点的真实世界的大型Graph 。

   • 图的结构信息编码了顶点之间丰富的邻近信息，但是 softmax 函数完全未考虑图的结构信息，因为它不加区分的对待所有顶点。

   最近 hierarchical softmax 和负采样技术是 softmax 的流行替代方案。尽管这些方法可以在一定程度上减少计算量，但是它们也没有考虑图的结构信息，因此应用于图的表示学习时也无法获得令人满意的性能。

2. 未解决softmax 的问题，GraphGAN 提出了 Graph Softmax，其关键思想是：重新对生成器 定义一个满足下面三个属性的理想的softmax 方法：

   • normalized 归一化：生成器 应该是一个有效的概率分布。即： 。
   • graph-structure-aware 结构感知：生成器 应该利用图的结构信息。即：顶点之间的最短距离越小，则它们连接的概率越大；顶点之间的最短距离越大，则它们连接的概率越小。
   • 计算高效 computationally efficient：和计算全量 softmax 不同，计算 应该仅仅包含图中的一小部分顶点。

3. 为计算 ，我们首先从顶点 开始对原始图 进行广度优先搜索 BFS ，这得到一棵以 为根的 BFS 树 。

   给定 我们将 表示为 中 的邻居的集合，即：和 直连的顶点，包括 的父顶点和所有子顶点。注意： 既依赖于顶点 ，又依赖于顶点 。如果根顶点 不同，则BFS 树 也不同，则 的邻居集合也不同。

   对于给定的顶点 及其邻居顶点 ，我们定义给定 的条件下 的概率为：

   

   这其实是定义在 上的一个 softmax 函数。

   注意到 中的每个顶点 可以从根节点 通过唯一的一条路径达到，定义该路径为 ，其中 。则 Graph Softmax 定义为：

   

   其中 由上式定义。

4. 可以证明这种定义的 Graph Softmax 满足归一性、结构感知、计算高效等性质。

   • 定理一：Graph Softmax 满足 。证明见原始论文。

   • 定理二：在原始图中如果 和 的最短路径增加，则 下降。

     证明：由于 是通过广度优先 BFS 得到的，因此路径 同时也定义了一条从 到 的最短路径，该路径长度为 。随着最短路径增加，则 中的概率乘积越多，因此 越小。

   • 定理三：计算 依赖于 个顶点，其中 是所有顶点的平均 degree， 为所有顶点的大小。

     证明：计算 依赖于两种类型的顶点：

     • 在路径 上的顶点。路径的最长长度为 ，它是 BFS 树的深度。
     • 路径上顶点直接相连的顶点。路径上每个顶点平均有 个邻居顶点相连。

5. 生成器 生成 fake 顶点的一个简单方法是：为所有的 顶点计算 ，然后根据这个概率按比例执行随机采样。

   这里我们提出一种在线的顶点生成方法，该方法计算效率更高并且与 Graph Softmax 的定义一致：根据转移概率 在 中执行一个从根节点 开始的随机游走。在随机游走过程中，如果 首次需要访问 的父顶点，则选择 作为生成的顶点。

   下图给出了 fake 顶点的在线生成过程，以及 Graph Softmax 计算过程。蓝色数字表示概率 ，蓝色实线箭头表示随机游走的方向，蓝色条纹顶点是被采样的顶点。最后一幅图的带颜色顶点（绿色、橙色、蓝色、蓝色带条纹）是需要更新参数的顶点。

   • 在每个随机游走步通过概率 随机选择当前顶点 的一个邻居顶点（标记为蓝色）。
   • 一旦 ，则将 作为采样顶点并返回（标记为蓝色带条纹）。
   • 然后根据 对路径 上的所有路径顶点、以及它们直接相连的顶点的参数进行更新。

   

6. 生成器 在线生成算法：

   • 输入：

     • 图
     • BFS 树
     • 顶点的embedding

   • 输出：生成的顶点

   • 算法步骤：

     • 初始化：

     • 

       • 根据概率 随机选择一个顶点
       • 如果 ，则 ，直接返回
       • 否则
7. 生成器 在线生成算法最多执行 个迭代步，因为随机游走路径最迟会在到达叶结点时终止。类似于 Graph Softmax，在线生成方法的计算复杂度为 ，这大大低于离线生成方法的 。

12.1.4 GraphGan

1. GraphGAN 算法：

   • 输入：

     • embedding 维度
     • 生成样本数
     • 判别样本数

   • 输出：

     • 生成器
     • 判别器

   • 算法步骤：

     • 初始化和预训练 以及

     • 对每个顶点 ，构建 BFS 树 。

     • 迭代直到 GraphGAN 收敛，迭代步骤为：

       • 

         • 根据生成器在线生成算法，生成器 对每个顶点 采样 个顶点
         • 根据 更新

       • 

         • 对每个顶点 ，从真实邻居顶点中采样 个正样本，从 中采样 个负样本。
         • 根据 来更新
     • 返回

2. 由于构建每棵BFS 树的算法复杂度为 ，则构建所有 BFS 树的计算复杂度 。其中 为顶点的平均degree 。

   在G-steps ，每一行的算法复杂度都是 ；在 D-steps，第一行的算法复杂度为 ，第二行的算法复杂度为 。由于 都是常数，因此 GraphGAN 每次迭代的算法复杂度为 。

   因此总的算法复杂度为 ，由构建 BFS 树的部分决定。

12.2 实验

1. 我们评估 GraphGAN 在一系列真实数据集上的性能，覆盖链接预测、顶点分类、推荐等三个任务。

2. 数据集：

   • arXiv-AstroPh 数据集：来自 arXiv 上天文物理领域的论文，包含了作者之间的合作关系。顶点表示作者，边表示co-author 关系。该图包含 18772 个顶点、198110 条边。
   • arXiv-GrQc 数据集：来自 arXiv 上广义相对论与量子宇宙学领域的论文，包含了作者之间的合作关系。顶点表示作者，边表示co-author 关系。该图包含 5242 个顶点、14496 条边。
   • BlogCatalog 数据集：来自 BlogCatelog 网站上给出的博客作者的社交关系网络。顶点标签表示通过博客作者提供的元数据推断出来的作者兴趣。该图包含 10312 个顶点、333982 条边、39 个不同的标签。
   • Wikipedia 数据集：来自维基百科，包含了英文维基百科 dump 文件的前 个字节中的单词共现网络。顶点的标签表示推断出来的单词词性Part-of-Speech:POS 。该图包含 4777 个顶点、184812 条边、40 个不同的标签。
   • MovieLens-1M 数据集：是一个二部图，来自 MovieLens 网站上的大约 100万 个评分（边），包含 6040 位用户和 3706 部电影。

3. 基准模型：

   • DeepWalk：通过随机游走和 skip-gram 来学习顶点 embedding。
   • LINE：保留了顶点的一阶邻近关系和二阶邻近关系。
   • Node2Vec：是 DeepWalk 的一个变种，通过一个biased 有偏的随机游走来学习顶点 embedding 。
   • Struct2Vec：捕获了图中顶点的结构信息。

4. 参数配置：

   • 所有方法的embedding 的维度 。

   • 所有基准模型的超参数都是默认值。

   • 在所有任务上，GraphGAN 的学习率都是 0.001， ， 为测试集的正样本数，然后分别执行 G-steps 和 D-steps 30 次。这些超参数都是通过交叉验证来选取的。

     最终学到的顶点 embedding 为 。

5. 我们首先实验了图中连接分布的模式，即：边的存在概率如何随着图中最短路径的变化而变化。

   我们首先分别从 arXiv-AstroPh 和 arXiv-GrQc 数据集中随机抽取 100 万 个顶点 pair 对。对于每个选定的顶点 pair 对，我们删除它们之间的连接（如果存在），然后计算它们之间的最短距离。我们计算所有可能的最短距离上边存在的可能性，如下图所示。

   • 显然，顶点 pair 对之间最短距离的增加会极大降低它们之间存在边的可能性。

   • 从对数概率曲线几乎为线性可以看出，顶点 pair 对之间的边存在概率和它们最短距离的倒数成指数关系。

     这进一步证明了 Graph Softmax 捕获了真实世界 Graph 的结构信息。

   

6. 在链接预测任务中，我们的目标是预测两个给定顶点之间是否存在边。因此该任务显式了不同的图表示学习方法预测链接的能力。

   我们随机将原始图中 10% 的边作为测试集，并在图上删掉这些边，然后用所有的顶点和剩下的边来训练模型。训练后，我们根据所有顶点训练得到的 embedding 向量，然后用逻辑回归来预测给定顶点 pair 对之间存在边的概率。

   测试集包含原始图中删掉的 10% 条边作为正样本，并随机选择未连接的相等数量的pair 对作为负样本。

   我们使用 arXiv-AstroPh 和 arXiv-GrQc 作为数据集，并在下表报告准确率和 Macro-F1 的结果。

   结论：

   • LINE 和 struct2vec 的性能在链接预测方面相对较差，因为它们不能完全捕获图中链接存在的模式。
   • DeepWalk 和 node2vec 的性能优于 LINE 和 struct2vec，这可能优于 DeepWalk 和 node2vec 都利用了基于随机游走的 skip-gram 模型，该模型在提取顶点之间邻近度方面表现更好。
   • GraphGAN 优于所有基准方法。与基准方法的单个模型训练相比，对抗训练为 GraphGAN 提供了更高的学习灵活性。

   

7. 为直观了解 GraphGAN 学习的稳定性，我们进一步给出了生成器和判别器在 arXiv-GrQc 上的学习曲线。可以看到：

   • GraphGAN 中的 mini-max game 达到了平衡，其中生成器表现出色。
   • 判别器的性能首先增强，然后但逐渐降到 0.8以下。 注意，判别器不会降级到随机盲猜的水平，因为在实践中生成器仍然提供很多真实的负样本。

   

8. 我们在 BlogCatalog 和 Wikipedia 数据集上执行顶点分类任务。我们在整个图上训练模型，然后将顶点 embedding 作为逻辑回归分类器的输入。其中训练集、测试集按照 9:1 的比例进行拆分。

   我们报告了测试集的准确率和 Macro-F1 结果。

   可以看到：GraphGAN 性能在这两个数据集上都优于所有基准模型。这表明：尽管GraphGAN 设计用于建模顶点之间的连接性分布，但是它仍然可以有效的将顶点信息编码到顶点 embedding 中。

   

9. 我们使用 Movielens-1M 作为推荐数据集，我们的目标是对每个用户向他/她推荐一组尚未观看、但是可能被用户喜欢的电影。

   我们首先将所有的4星 和 5星 评级视为边，从而得到一个二部图。然后将原始图的 10% 边随机隐藏作为测试集，并为每个用户构建 BFS 树。

   注意：和之前的两个任务不同，在之前任务中，对于给定的顶点我们定义了它与所有其它顶点的连接性分布。但是推荐任务中，我们仅在一小部分顶点上定义连接性分布，如电影顶点（而不包括用户顶点）。因此我们在用户的 BFS 树中，对于除根顶点之外的所有用户顶点，我们将它们和位于当前 BFS 树中的电影顶点添加直连边来 shortcut 。

   在训练并获得用户和电影的embedding 之后，对于每个用户，我们基于user embeding 和电影 embedding 的相似度来挑选 个用户未观看的电影来作为推荐结果。我们给出测试集上的 Precision@K 和 Recall@K 指标。可以看到：GraphGAN 始终优于所有基准方法，并在两个指标上均有显著改进。