1、Introduction

网络表示学习方法可以分成两个类别。

• Generative model假定对于每一个顶点$v_c$ ，在图中存在一个潜在的、真实的连续性分布 $P_{true}(v|v_c)$， 图中的每条边都可以看作是从$P_{true}$里采样的一些样本，暗示着节点 $v_c$ 在整个网络中的连接偏好，因此网络中的边，其实也可以被看作是这些条件分布概率的观测样本，因此这些生成式表示学习算法的目的就是最大化网络中边的似然生成式方法都试图将边的似然概率最大化，来学习vertex embedding。例如DeepWalk (KDD 2014) and node2vec (KDD 2016)。

• Discriminative Model 将两顶点联合作为$feature$，预测两点之间存在边的概率。判别式模型认为边不是条件分布得到的，而是直接通过训练学习一个判别器来直接预测两两节点之间，是否存在会存在边。典型的判别式模型，就是将网络中的训练集上的每两个节点 $v_i$ 和$v_j$ 都看作是特征，然后预测两点之间存在边的概率$p(edage|(v_i,v_j))$ 。例如SDNE (KDD 2016) and PPNE (DASFAA, 2017)。

本文创新点：
1、GraphGAN 结合非常popular的GAN设计了一个 game-theoretical minimax game 将两者结合。
2、graph softmax 克服了传统的softmax函数的局限性，证明该函数满足规范化、图结构感知和计算效率的要求。

• $softmax$对给定顶点的图中所有其他顶点都是平等的，没有考虑图的结构和邻近信息
• $softmax$的计算涉及到图中的所有顶点，这既耗时又效率低下
• 提出了一种基于随机游走的生成器在线生成策略，该策略符合图$softmax$的定义，可以大大降低计算复杂度。

2、GraphGAN Framework

在GraphGAN中，主要有两个模型：

对于$G$来说，它的目标是生成与 $v_c$ 真实连接的邻居节点相似的点，来骗过判别器$D$；而对于$D$，它的目标是判别这些节点哪些是$v_c$的真实邻居，哪些是它的对手$G$生成的节点。因此，两个对手的一个$minimax$游戏的目标函数$(1)$为：



理解了公式$（1）$就基本理解了$GraphGAN$的内在原理，上图给出$GraphGAN$工作的流程。${\theta }_D$和${\theta }_G$可以通过交替最小化和最大化$V(G,D)$函数来迭代更新得到。每次迭代，我们从 $P_{true}$ 中 抽样一些跟 $V_c$ 真实相邻的绿点，从 $G$ 中又生成了一些跟 $V_c$接近的蓝点。我们将绿点作为正样本，将蓝点作为负样本来训练 $D$，在得到 $D$ 之后，再用 $D$ 中的信号，通过$policygradient$去反过来训练 $G$。不断重复这个过程，直到生成器 $G$ 和 $P_{true}$极为接近。在刚开始的时候，$G$ 相对比较差，因此对于给定的 $V_c$ 而言，$Gsample$ 的点都是一些离 $V_c$ 很远的点。随着训练的不断进行，$Gsample$ 的点会逐渐向 $V_c$ 接近，到最后 $G$ 抽样的点几乎都变成了真正跟 $V_c$ 相邻的点，也就是 $G$ 和 $P_{true}$ 已经很难被区分了

生成器和判别器的参数是不断地交替训练进行更新的。每一次迭代，判别器$D$通过来自 $P_{true}(v|v_c)$的正样本（图例中所示的绿色节点）和来自$G$的负样本（图例中为蓝条纹节点）进行训练；生成器$G$则通过$D$的指导，按照梯度策略进行更新。

2.1 Optimization

Discriminator Optimization

Generator Optimization

Graph Softmax for Generator

证明:

• 对于每个叶子节点$v$,其只有一个父节点，故$p_c(v_{r_{m-1}}|v_{r_m})=p_c(v_{r_{m-1}}|v)=1$

• 对于每个非叶子节点$v$,我们定义$C_c(v)$为节点$v$的孩子节点的集合，每个孩子节点$v_k\in C_c(v)$

论文链接：GraphGAN
代码链接：https://github.com/hwwang55