Question

1. graph representation learning（也被称作 network embedding）旨在将图（或者network）中的每个顶点表达为一个低维向量。graph representation learning 可以促进对顶点和边的网络分析和预测任务。学到的 embedding 能够使广泛的实际application 受益，例如链接预测、节点分类、推荐、可视化、知识图谱 representation、聚类、text embedding、社交网络分析。最近，研究人员研究了将 representation learning 方法应用于各种类型的图，例如加权图weighted graph 、有向图directed graph 、有符号图signed graph、异质图 heterogeneous graph、属性图attributed graph。此外，先前的一些工作也试图在学习过程中保留特定的属性，例如全局结构global structure 、社区结构 community structure、分组信息 group information、非对称传递性 asymmetric transitivity。

   总的来讲，大多数现有的 graph representation learning 方法可以分为两类。

   • 第一类是生成式 graph representation learning 模型。类似于经典的生成模型generative model （例如高斯混合模型Gaussian Mixture Model: GMM或潜在狄利克雷分配 Latent Dirichlet Allocation: LDA），生成式 graph representation learning 模型假设：对于每个顶点 $ v_c $ ，存在一个底层的真实的连通性分布underlying true connectivity distribution $ p_\text{true}(v\mid v_c) $ ，它给出了 $ v_c $ 对图中所有其它顶点的连通性偏好 connectivity preference（或者相关性分布relevance distribution ）。因此，图中的边可以被视为由这些条件分布生成的观察样本 observed sample ，并且这些生成模型通过最大化图中边的可能性来学习顶点 embedding 。例如，DeepWalk 使用随机游走对每个顶点的上下文顶点进行采样，并尝试最大化观察给定顶点的上下文顶点的对数似然。node2vec 通过提出有偏随机游走过程进一步扩展了这个想法，这个有偏随机游走过程在为给定顶点生成上下文时提供了更大的灵活性。
   • 第二类是判别式 graph representation learning 模型。与生成模型不同的是，判别式 graph representation learning 模型不会将边视为从底层条件分布生成的，而是旨在学习一个分类器来直接预测边的存在。通常，判别模型discriminative model 将两个顶点 $ v_i $ 和 $ v_j $ 共同视为特征，并根据图中的训练数据预测两个顶点之间存在边的概率，即 $ p(\text{edge}\mid (v_i,v_j)) $ 。例如，SDNE 使用顶点的稀疏邻接向量 sparse adjacency vector 作为每个顶点的原始特征，并应用自编码器在边存在edge existence 的监督下提取顶点的低维稠密特征。PPNE 直接通过对正样本（连接的顶点 pair 对）和负样本（未连接的顶点 pair 对）的监督学习来学习顶点 embedding，同时在学习过程中也保留了顶点的固有属性。

   尽管生成模型和判别模型通常是 graph representation learning 方法的两个不相交的类别，但是它们可以被视为同一枚硬币的两个方面。事实上，LINE 已经对于隐式地结合这两个目标（一阶邻近性和二阶邻近性）进行了初步的尝试。最近，生成对抗网络 Generative Adversarial Net: GAN 受到了极大的关注。通过设计一个博弈论 game-theoretical 的 minimax 游戏来结合生成模型和判别模型，GAN 及其变体在各种应用中取得了成功，例如图像生成image generation 、序列生成sequence generation 、对话生成dialogue generation 、信息检索information retrieval 、领域适应 domain adaption 。

   受 GAN 的启发，论文 《GraphGAN: Graph Representation Learning with Generative Adversarial Nets》提出了一种新颖的框架 GraphGAN，它统一了 graph representation learning 的生成式思维和判别式思维。具体而言，框架的目标是在 GraphGAN 的学习过程中训练两个模型：

   • 生成器 generator $ G(v\mid v_c) $ ，它试图拟合底层的真实的连通性分布 $ p_\text{true}(v\mid v_c) $ ，生成最有可能与 $ v_c $ 连接的顶点。
   • 判别器 discriminator $ D(v,v_c) $ ，它试图区分 well-connected 的顶点 pair 对和 ill-connected 的顶点 pair 对，并计算顶点 $ v $ 和 $ v_c $ 之间存在边的概率。

   在提出的 GraphGAN 中，生成器 $ G $ 和判别器 $ D $ 在 minimax 游戏中充当两个参与者：生成器试图在判别器提供的指导下产生最难以区分的 “假” 顶点，而判别器试图在 ground truth 和 “假” 顶点之间划清界限从而避免被生成器愚弄。这场博弈中的竞争促使它们双方都提高自己的能力，直到生成器（代表模型学到的条件分布）与真实的连通性分布 true connectivity distribution 无法区分。

   在 GraphGAN 框架下，论文研究了生成器和判别器的选择。不幸的是，作者发现传统的softmax 函数（及其变体）不适用于生成器，有两个原因：

   • 对于给定的顶点，softmax 会同等对待图中的所有其它顶点，缺乏对图结构和邻近性信息 proximity information 的考虑。
   • softmax 的计算涉及图中的所有顶点，耗时且计算效率低。

   为了克服这些缺陷，论文在 GraphGAN 中提出了一种新的、针对生成器的 softmax 实现，称作 Graph Softmax。Graph Softmax 为图中的连通性分布提供了新的定义。论文证明了 Graph Softmax 满足规范化normalization 、图结构感知graph structure awareness 、以及计算效率 computational efficiency 的理想特性。据此，论文为生成器提出了一种基于随机游走的在线生成策略 online generating strategy ，该策略与 Graph Softmax 的定义一致，可以大大降低计算复杂度。

   论文在五个真实世界的图结构数据集上将 GraphGAN 应用于三个真实世界场景，即链接预测、节点分类、推荐。实验结果表明：与 graph representation learning 领域的 state-of-the-art 的 baseline 相比，GraphGAN 取得了可观的收益。具体而言，在准确率指标上，GraphGAN 在链接预测中的性能优于 baseline 0.59% ~ 11.13%，在节点分类中的性能优于 baseline 0.95% ~ 21.71%。此外，GraphGAN 在推荐任务上将 Precision@20 至少提高了 38.56%、Recall@20 至少提高了 52.33%。作者将 GraphGAN 的优越性归因于其统一的对抗性学习框架以及邻近性感知 proximity-aware 的 Graph Softmax 设计。其中，Graph Softmax 可以自然地从图中捕获结构信息。

12.1 模型

1. 这里我们首先介绍 GraphGAN 的框架，并讨论了生成器和判别器的实现和优化细节。然后，我们展示了作为生成器实现的 Graph Softmax，并证明了它优于传统 softmax 函数的性能。

12.1.1 GraphGAN 框架

1. 令图 $ \mathcal G=(\mathcal V,\mathcal E) $ ，其中 $ \mathcal V=\{v_1,\cdots,v_{|\mathcal V|}\} $ 为顶点集合， $ \mathcal E=\{e_{i,j}\} $ 为边集合。对于给定顶点 $ v_c $ ，定义 $ \mathcal N(v_c) $ 为 $ v_c $ 直接相连的顶点集合（即，直接邻域），通常该集合的规模远远小于全量顶点集合 $ \mathcal V $ 。

   我们定义顶点 $ v_c $ 的底层真实连通性分布 underlying true connectivity distribution 为条件概率 $ p_\text{true}(v\mid v_c) $ ，它反映了 $ v_c $ 对 $ \mathcal V $ 中所有其它顶点的连通性偏好 connectivity preference 。从这个角度来看， $ \mathcal N(v_c) $ 可以视为从 $ p_\text{true}(v\mid v_c) $ 中抽取的一组观测样本 observed sample 。

2. 给定图 $ \mathcal G $ ，我们的目标是学习以下两个模型：

   • 生成器 generator $ G(v\mid v_c;\theta_G) $ ：它的目标是逼近 $ p_\text{true}(v\mid v_c) $ ，然后针对 $ v_c $ 生成最有可能和它连接的顶点。更准确的说，是从 $ \mathcal V $ 中选择和 $ v_c $ 最有可能连接的顶点。
   • 判别器 discriminator $ D(v,v_c;\theta_D) $ ：它的目标是判断顶点 pair 对 $ (v,v_c) $ 之间的连通性 connectivity。它输出一个标量，代表顶点 $ v $ 和 $ v_c $ 之间存在边的概率。

   生成器 $ G $ 和判别器 $ D $ 充当两个对手：

   • 生成器 $ G $ 试图完美拟合 $ p_\text{true}(v\mid v_c) $ ，然后生成 “假” 顶点。这些生成的顶点和 $ v_c $ 真实连接的邻居顶点相似，从而欺骗判别器 $ D $ 。
   • 判别器 $ D $ 试图检测这些顶点是否是 $ v_c $ 的真实邻居，还是由生成器 $ G $ 生成的 ”假“ 顶点。

   形式化地，生成器 $ G $ 和判别器 $ D $ 正在参与具有以下值函数value function $ V(G,D) $ 的双人 minimax 游戏：

   $ \min_{\theta_G}\max_{\theta_D}V(G,D) = \sum_{c=1}^{|\mathcal V|}\left(\mathbb E_{v\in p_\text{true}(\cdot\mid v_c)}[\log D(v,v_c;\theta_D)]+\mathbb E_{v\sim G(\cdot\mid v_c;\theta_G)}[\log(1-D(v,v_c;\theta_D))]\right) $

   其中生成器和判别器的参数可以通过交替最大化和最小化值函数 $ V(G,D) $ 来学习。

   第一项要求判别器 $ D $ 尽可能给 ”真邻居” 以较高的预估概率，第二项要求判别器 $ D $ 尽可能给 “假邻居” 以较低的预估概率。

3. GraphGAN 整体框架如下图所示。每次迭代过程中，我们使用来自 $ p_\text{true}(\cdot\mid v_c) $ 的正样本（绿色顶点）和来自生成器 $ G(\cdot\mid v_c;\theta_G) $ 的负样本（带蓝色条纹的顶点）来训练判别器 $ D $ ，并在 $ D $ 的指导下使用策略梯度更新生成器 $ G $ 。

   $ G $ 和 $ D $ 之间的竞争促使它们都改进自己的参数，直到 $ G $ 与 $ p_\text{true} (\cdot\mid v_c) $ 无法区分。

   

4. 判别器Discriminator：给定从底层真实连通性分布而来的正样本，以及从生成器而来的负样本，判别器 $ D $ 的目标是最大化将正确 label 分配给正样本和负样本的概率的对数。如果判别器 $ D $ 是可微的，则可以通过针对 $ \theta_D $ 的梯度上升来解决。

   在 GraphGAN 中，我们简单地定义判别器 $ D $ 为两个输入顶点的 embedding 内积的 sigmoid 函数。理论上 SDNE 等任何判别式模型都可以用作判别器 $ D $ ，我们将如何选择合适的判别器作为未来的研究。因此，这里的判别器为：

   $ D(v,v_c) = \sigma\left(\mathbf{\vec d}_v^\top \mathbf{\vec d}_{v_c}\right) = \frac{1}{1+\exp\left(-\mathbf{\vec d}_v^\top \mathbf{\vec d}_{v_c}\right)} $

   其中 $ \mathbf{\vec d}_v,\mathbf{\vec d}_{v_c}\in \mathbb R^k $ 分别是判别器 $ D $ 中顶点 $ v $ 和 $ v_c $ 的 $ k $ 维 representation 向量， $ \theta_D=\left\{\mathbf{\vec d}_1,\cdots,\mathbf{\vec d}_{|\mathcal V|}\right\} $ 。

   注意到这里仅包含 $ v $ 和 $ v_c $ ，这意味着给定一对样本 $ (v,v_c) $ ，我们仅仅需要通过对应的梯度上升来更新 $ \mathbf{\vec d}_v $ 和 $ \mathbf{\vec d}_{v_c} $ ：

   $ \nabla_{\theta_D}V(G,D) = \begin{cases} \nabla_{\theta_D}\log D(v,v_c),&\text{if}\; v\sim p_\text{true}\\ \nabla_{\theta_D}\left(1-\log D(v,v_c)\right),&\text{if}\; v\sim G \end{cases} $

   即，没必要更新全量顶点的 embedding 。

5. 生成器Generator：和判别器相比，生成器 $ G $ 的目标是，使得判别器 $ D $ 区分由 $ G $ 生成的 “假” 顶点的概率最小化。即，生成器通过调整参数 $ \theta_G $ 来移动其近似的连通性分布 approximated connectivity distribution，从而增加其生成的 “假” 顶点在判别器 $ D $ 中的得分。

   由于生成器采样的顶点 $ v $ 是离散的，因此遵循 《Gradient estimation using stochastic computation graphs》 和 《Irgan: A minimax game for unifying generative and discriminative information retrieval models》的做法，我们建议通过策略梯度policy gradient计算 $ V(G,D) $ 对 $ \theta_G $ 的梯度：

   $ \nabla_{\theta_G}V(G,D) = \nabla_{\theta_G}\sum_{c=1}^{|\mathcal V|}\mathbb E_{v\sim G(\cdot\mid v_c)}[\log(1-D(v,v_c))]\\ = \sum_{c=1}^{|\mathcal V|}\sum_{i=1}^N\nabla_{\theta_G}G(v_i\mid v_c)\log(1-D(v_i,v_c)) $

   其中 $ N $ 为生成器采样的顶点数量。

   考虑到 $ \log(1-D(v_i,v_c)) $ 与 $ \theta_G $ 无关，以及 $ G \nabla_{\theta_G} \log G = G\times \frac 1G\nabla_{\theta_G} G = \nabla_{\theta_G} G $ ，因此有：

   $ \nabla_{\theta_G}G(v_i\mid v_c)\log(1-D(v_i,v_c)) = G(v_i\mid v_c)\nabla_{\theta_G}\log G(v_i\mid v_c)\log(1-D(v_i,v_c)) $

   则有：

   $ \nabla_{\theta_G}V(G,D) = \sum_{c=1}^{|\mathcal V|}\sum_{i=1}^NG(v_i\mid v_c)\nabla_{\theta_G}\log G(v_i\mid v_c)\log(1-D(v_i,v_c))\\ = \sum_{c=1}^{|\mathcal V|} \mathbb E_{v\sim G(\cdot\mid v_c)}[\nabla_{\theta_G}\log G(v\mid v_c)\log(1-D(v,v_c))] $

   梯度 $ \nabla_{\theta_G}V(G,D) $ 的物理意义为： $ \nabla_{\theta_G}\log G(v\mid v_c;\theta_G) $ 的加权和，权重为 $ \log(1-D(v,v_c;\theta_D)) $ 。

   • 当 $ v $ 更容易被判别器 $ D $ 识别时， $ D(v,v_c;\theta_D) $ 得分较小，则加权的权重较大。
   • 当 $ v $ 更不容易被判别器 $ D $ 识别时， $ D(v,v_c;\theta_D) $ 得分较大，则加权的权重较小。

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

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

   $ G(v\mid v_c) = \frac{\exp\left(\mathbf{\vec g}_v^\top \mathbf{\vec g}_{v_c}\right)}{\sum_{v^\prime\ne v_c}\exp\left(\mathbf{\vec g}_{v^\prime}^\top \mathbf{\vec g}_{v_c}\right)} $

   其中 $ \mathbf{\vec g}_v,\mathbf{\vec g}_{v_c} \in \mathbb R^k $ 为分别是生成器 $ G $ 中顶点 $ v $ 和 $ v_c $ 的 $ k $ 维 representation 向量， $ \theta_G=\{\mathbf{\vec g}_1,\cdots,\mathbf{\vec g}_{|\mathcal V|}\} $ 。

   为了在每轮迭代中更新 $ \theta_G $ ，我们首先基于 $ G(v\mid v_c;\theta_G) $ 计算近似的连通性分布 approximated connectivity distribution ，然后根据该分布随机采样一组样本 $ (v,v_c) $ ，然后通过随机梯度下降法来更新 $ \theta_G $ 。

   注意，采样“假”顶点时采用更新前的生成器，然后通过随机梯度下降得到更新后的生成器。

12.1.2 Graph Softmax

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

   • 计算 $ G(v\mid v_c;\theta_G ) $ 的 softmax 函数时涉及到图中的所有顶点，这意味着对于每个生成的样本 $ v $ ，我们需要计算梯度 $ \nabla_{\theta_G}\log G(v\mid v_c;\theta_G) $ ，并更新所有顶点。这在计算上是低效的，尤其是对于具有数百万个顶点的真实世界的大型Graph 。
   • 图结构信息编码了顶点之间丰富的邻近性信息，但是 softmax 函数完全忽略了来自图的结构信息，因为它不加区分地对待所有顶点。

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

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

   • 归一化normalized ：生成器 $ G $ 应该是一个有效的概率分布。即： $ \sum_{v\ne v_c} G(v\mid v_c;\theta_G) = 1 $ 。
   • 图结构感知graph structure aware ：生成器 $ G $ 应该利用图的结构信息。直观而言，对于图中的两个顶点，它们的连通性概率应该随着它们之间最短路径距离shortest distance 的增加而下降。
   • 计算高效 computationally efficient：和计算全量 softmax 不同，计算 $ G(v\mid v_c;\theta_G) $ 应该仅仅包含图中的一小部分顶点。

3. Graph Softmax：为计算 $ G(\cdot\mid v_c;\theta_G) $ ，我们首先从顶点 $ v_c $ 开始对原始图 $ G $ 进行广度优先搜索 Breadth First Search: BFS ，这得到一棵以 $ v_c $ 为根的 BFS 树 $ T_c $ 。给定 $ T_c $ ，我们将 $ \mathcal N_c(v) $ 表示为 $ T_c $ 中 $ v $ 的邻居的集合，即和 $ v $ 直连的顶点，包括 $ v $ 的直系父顶点和直系子顶点。

   注意： $ \mathcal N_c(v) $ 既依赖于顶点 $ v $ ，又依赖于顶点 $ v_c $ 。如果根顶点 $ v_c $ 不同，则BFS 树 $ T_c $ 也不同，则 $ v $ 的邻居集合也不同。另外，这里仅包含直接相连的顶点（直系父顶点、直系子顶点）。

   对于给定的顶点 $ v $ 及其邻居顶点 $ v_i\in \mathcal N_c(v) $ ，我们定义给定 $ v $ 的条件下 $ v_i $ 的概率为：

   $ p_c(v_i\mid v) = \frac{\exp\left(\mathbf{\vec g}_{v_i}^\top\mathbf{\vec g}_v\right)}{\sum_{v_j\in \mathcal N_c(v)}\exp\left(\mathbf{\vec g}_{v_j}^\top \mathbf{\vec g}_v\right)} $

   这其实是定义在 $ \mathcal N_c(v) $ 上的一个 softmax 函数。

   $ p_c(v_i\mid v) $ 定义的是路径概率：给定树 $ T_c $ 和顶点 $ v $ ，下一步选择其父顶点或子顶点的路径概率。这个概率并不是 “假” 顶点的生成概率。

   注意到 $ T_c $ 中的每个顶点 $ v $ 可以从根节点 $ v_c $ 通过唯一的一条路径达到，定义该路径为 $ P_{v_c\rightarrow v} = (v_{r_0},v_{r_1},\cdots,v_{r_m}) $ ，其中 $ v_{r_0} = v_c, v_{r_m} = v $ 。则 Graph Softmax 定义为：

   $ G(v\mid v_c;\theta_G) = \left(\prod_{j=1}^m p_c(v_{r_j}\mid v_{r_{j-1}})\right)\times p_c(v_{r_{m-1}}\mid v_{r_m}) $

   其中 $ p_c(\cdot\mid \cdot) $ 由上式定义。最后一项因子 $ p_c(v_{r_{m-1}}\mid v_{r_m}) $ 是为了归一化从而得到概率分布。

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

   • 定理一：Graph Softmax 满足 $ \sum_{v\ne v_c} G(v\mid v_c;\theta_G) = 1 $ 。证明见原始论文。

   • 定理二：在原始图中如果 $ v $ 和 $ v_c $ 的最短路径增加，则 $ G(v\mid v_c;\theta_G) $ 下降。

     证明：由于 $ T_c $ 是通过广度优先 BFS 得到的，因此路径 $ P_{v_c\rightarrow v} $ 同时也定义了一条从 $ v_c $ 到 $ v $ 的最短路径，该路径长度为 $ m $ 。随着最短路径增加，则 $ G(v\mid v_c;\theta_G) $ 中的概率乘积越多，因此 $ G $ 越小。

   • 定理三：计算 $ G(v\mid v_c;\theta_G) $ 依赖于 $ O(d\times\log |\mathcal V|) $ 个顶点，其中 $ d $ 是所有顶点的平均 degree， $ |\mathcal V| $ 为所有顶点的大小。

     证明：计算 $ G(v\mid v_c;\theta_G) $ 依赖于两种类型的顶点：

     • 在路径 $ P_{v_c\rightarrow v} $ 上的顶点。路径的最长长度为 $ \log |\mathcal V| $ ，它是 BFS 树的深度。
     • 路径上顶点直接相连的顶点。路径上每个顶点平均有 $ d $ 个邻居顶点相连。

12.1.3 算法和讨论

1. 在线生成策略 online generating strategy ：生成器 $ G $ 生成 “假” 顶点的一个简单方法是：为所有的 $ v\ne v_c $ 顶点计算 $ G(v\mid v_c;\theta_G) $ ，然后根据这个近似的连通性概率执行随机采样。

   这里我们提出一种在线的顶点生成方法，该方法计算效率更高并且与 Graph Softmax 的定义一致。为了生成一个顶点，我们从 $ T_c $ 中的根节点 $ v_c $ 开始，根据转移概率 $ p_c(v_i\mid v) $ 执行随机游走。在随机游走过程中，如果 $ G $ 首次需要访问 $ v $ 的父节点（即在路径上反向），则选择 $ v $ 作为生成的顶点。

   因为 Graph Softmax 的定义中包含 $ v_c $ 到 $ v $ 的一条路径，并且还包含 $ v $ 到 $ v $ 的父节点的反向。

   下图给出了 “假” 顶点的在线生成过程，以及 Graph Softmax 计算过程。蓝色数字表示概率 $ p_c(v_i\mid v) $ ，蓝色实线箭头表示随机游走的方向，蓝色条纹顶点是被采样的顶点。最后一幅图的带颜色顶点（绿色、橙色、蓝色、蓝色带条纹）是需要更新参数的顶点。我们将当前访问的顶点记作 $ v_\text{cur} $ ，前一个访问的顶点记作 $ v_\text{pre} $ （即父节点）。

   • 在每个随机游走步通过概率 $ p_c(v_i\mid v_\text{curr}) $ 随机选择当前顶点 $ v_\text{curr} $ 的一个邻居顶点（标记为蓝色）。
   • 一旦 $ v_i = v_\text{pre} $ ，则将 $ v_\text{cur} $ 作为采样顶点并返回（标记为蓝色带条纹）。
   • 然后根据 $ \nabla_{\theta_G}V(G,D) $ 对路径 $ P_{v_c\rightarrow v_\text{curr}} $ 上的所有路径顶点、以及它们直接相连的顶点的参数进行更新。

   生成器 $ G $ 在线生成算法最多执行 $ O(\log |\mathcal V|) $ 个迭代步，因为随机游走路径最迟会在到达叶结点时终止。类似于 Graph Softmax，在线生成方法的计算复杂度为 $ O(d\times\log|\mathcal V|) $ ，这大大低于离线生成方法的 $ O(|\mathcal V|\times d\log |\mathcal V|) $ 。

   

2. 生成器 $ G $ 在线生成算法：

   • 输入：

     • 图 $ G $
     • BFS 树 $ T_c $
     • 顶点的embedding $ \left\{\mathbf{\vec g}_i\right\}_{i\in |\mathcal V|} $

   • 输出：生成的顶点 $ v_\text{gen} $

   • 算法步骤：

     • 初始化： $ v_\text{pre} \leftarrow v_c, v_\text{cur}\leftarrow v_c $

     • $ \text{while true do:} $

       • 根据概率 $ p_c(v_i\mid v_\text{cur}) $ 随机选择一个顶点 $ v_i $
       • 如果 $ v_i = v_\text {pre} $ ，则 $ v_\text{gen}\leftarrow v_\text{cur} $ ，直接返回 $ v_\text{gen} $
       • 否则 $ v_\text{pre}\leftarrow v_\text{cur},v_\text{cur}\leftarrow v_i $

3. GraphGAN 算法：

   • 输入：

     • embedding 维度 $ k $
     • 生成样本数 $ N $
     • 判别样本数 $ M $

   • 输出：

     • 生成器 $ G(v\mid v_c;\theta_G) $
     • 判别器 $ D(v,v_c;\theta_D) $

   • 算法步骤：

     • 初始化和预训练 $ G(v\mid v_c;\theta_G) $ 以及 $ D(v,v_c;\theta_D) $

     • 对每个顶点 $ v_c\in \mathcal V $ ，构建 BFS 树 $ T_c $ 。

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

       • $ \text{for G-steps} : $

         • 根据生成器在线生成算法，生成器 $ G $ 对每个顶点 $ v_c $ 采样 $ N $ 个顶点
         • 根据 $ \nabla_{\theta_G} V(G,D) $ 更新 $ \theta_G $

       • $ \text{for D-steps}: $

         • 对每个顶点 $ v_c $ ，从真实邻居顶点中采样 $ M $ 个正样本，从 $ G(v\mid v_c;\theta_G) $ 中采样 $ M $ 个负样本。
         • 根据 $ \nabla_{\theta_D} V(G,D) $ 来更新 $ \theta_D $

     • 返回 $ G(v\mid v_c;\theta_G),D(v,v_c;\theta_D) $

4. 由于构建每棵BFS 树的算法复杂度为 $ O(|\mathcal V| + |\mathcal E|) $ ，则构建所有 BFS 树的计算复杂度 $ O(|\mathcal V|\times (|\mathcal V| + |\mathcal E|)) = O(d\times |\mathcal V|^2) $ 。其中 $ d $ 为顶点的平均degree 。

   在G-steps ，每一行的算法复杂度都是 $ O(N|\mathcal V|\times d\log|\mathcal V|\times k) $ ；在 D-steps，第一行的算法复杂度为 $ O(M|\mathcal V|\times d\log |\mathcal V|\times k) $ ，第二行的算法复杂度为 $ O(M|\mathcal V|\times k) $ 。由于 $ k,M,N,d $ 都是常数，因此 GraphGAN 每次迭代的算法复杂度为 $ O(|\mathcal V|\times \log |\mathcal V|) $ 。

   因此总的算法复杂度为 $ O(|\mathcal V|^2) $ ，由构建 BFS 树的部分决定。

5. 读者注：论文将生成器的 embedding $ \left\{\mathbf{\vec g}_i\right\}_{i=1}^{|\mathcal V|} $ 作为顶点的最终 embedding，而并没有采用判别器的 embedding $ \left\{\mathbf{\vec d}_i\right\}_{i=1}^{|\mathcal V|} $ 。这是因为在链接预测任务的实验中表明：生成器 embedding 的效果要比判别器 embedding 的效果更好。

   理论上也可以尝试拼接生成器的 embedding 和判别器的 embedding 从而得到顶点的最终 embedding 。

12.2 实验

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

2. 数据集：

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

3. baseline 方法：

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

4. 参数配置：

   • 所有方法的embedding 的维度 $ k=20 $ 。

   • 所有baseline 模型的其它超参数都是默认值。

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

     最终学到的顶点 embedding 为生成器的 $ \mathbf{\vec g}_i $ （而不是判别器的 $ \mathbf{\vec d}_i $ ） 。

12.2.1 连通性分布

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

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

   • 显然，顶点 pair 对之间存在边的概率随着它们最短路径的增加而急剧下降。

   • 从对数概率曲线几乎为线性可以看出，顶点 pair 对之间的边存在概率和它们最短距离的倒数成指数关系。这进一步证明了 Graph Softmax 捕获了真实世界 Graph 的本质。

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

   

12.2.2 链接预测

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

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

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

   • LINE 和 struct2vec 的性能在链接预测方面相对较差，因为它们不能完全捕获图中链接存在的模式。
   • DeepWalk 和 node2vec 的性能优于 LINE 和 struct2vec，这可能优于 DeepWalk 和 node2vec 都利用了基于随机游走的 skip-gram 模型，该模型在提取顶点之间邻近性方面表现更好。
   • GraphGAN 优于所有 baseline 方法。具体而言，GraphGAN 将 arXiv-AstroPh 的预测准确率提升 1.18% ~ 4.27%、将 arXiv-GrQc的预测准确率提升 0.59% ~ 11.13%。我们认为，与 baseline 方法的单个模型训练相比，对抗训练为 GraphGAN 提供了更高的学习灵活性。

   

2. 为直观了解 GraphGAN 学习的稳定性，我们进一步给出了生成器和判别器在 arXiv-GrQc 上的学习曲线learning curve。可以看到：GraphGAN 中的 minimax game 达到了平衡，其中生成器在收敛后表现出色，而判别器的性能首先增强然后逐渐降到 0.8以下。注意，判别器不会降级到随机盲猜的水平，因为在实践中生成器仍然提供很多真正的负样本。

   结果表明，与 IRGAN 不同，Graph Softmax 的设计使得 GraphGAN 中的生成器能够更有效地采样顶点和学习顶点 embedding 。

   这个实验表明生成器 embedding 要比判别器 embedding 效果更好。

   

12.2.3 节点分类

1. 在节点分类中，每个顶点被分配一个或者多个标签。在我们观察到一小部分顶点及其标签之后，我们的目标是预测剩余顶点的标签。因此，顶点分类的性能可以揭示不同 graph representation learning 方法下顶点的可分性。我们在 BlogCatalog 和 Wikipedia 数据集上执行顶点分类任务。我们在整个图上训练模型，然后将顶点 embedding 作为逻辑回归分类器的输入。其中训练集、测试集按照 9:1 的比例进行拆分。我们报告了测试集的准确率和 Macro-F1 结果。

   可以看到：GraphGAN 性能在这两个数据集上都优于所有基准模型。例如，GraphGAN 在这两个数据集的准确率上分别实现了 1.75% ~ 13.17% 以及 0.95% ~ 21.71% 的增益。这表明：尽管GraphGAN 设计用于建模顶点之间的连通性分布，但是它仍然可以有效的将顶点信息编码到顶点 embedding 中。

   

12.2.4 推荐

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

   我们首先将所有的4星和 5星评级视为边，从而得到一个二部图。然后将原始图的 10% 边随机隐藏作为测试集，并为每个用户构建 BFS 树。注意：和之前的两个任务不同，在之前任务中，对于给定的顶点我们定义了它与所有其它顶点的连通性分布。但是推荐任务中，一个用户的连接概率仅定义在图中的一小部分电影顶点上（用户顶点之间不存在连接、电影顶点之间也不存在连接）。因此我们在用户的 BFS 树中，对于除根顶点之外的所有用户顶点，我们将它们和位于当前 BFS 树中的电影顶点添加直连边来 shortcut 。

   在训练并获得用户和电影的embedding 之后，对于每个用户，我们基于user embeding 和电影 embedding 的相似度来挑选 $ K $ 个用户未观看的电影来作为推荐结果。我们给出测试集上的 Precision@K 和 Recall@K 指标。可以看到：GraphGAN 始终优于所有基准方法，并在两个指标上均有显著改进。以 Precision@20 为例，GraphGAN 比 DeepWalk, LINE, node2vec, struct2vec 分别高出 38.56%、58.60%、124.95%、156.85% 。因此，我们可以得出结论：GraphGAN 在 ranking-based 任务中保持了更出色的性能。