GraphGAN: Graph Representation Learning with GAN
GraphGAN: Graph Representation Learning with GAN
- 1、Introduction
- 2、GraphGAN Framework
-
- 2.1 Optimization
-
- Discriminator Optimization
- Generator Optimization
- Graph Softmax for Generator
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工作的流程。θ_D和θ_G可以通过交替最小化和最大化V(G,D)函数来迭代更新得到。每次迭代，我们从 P_{true} 中 抽样一些跟 V_c 真实相邻的绿点，从 G 中又生成了一些跟 V_c接近的蓝点。我们将绿点作为正样本，将蓝点作为负样本来训练 D，在得到 D 之后，再用 D 中的信号，通过policy\ gradient去反过来训练 G。不断重复这个过程，直到生成器 G 和 P_{true}极为接近。在刚开始的时候，G 相对比较差，因此对于给定的 V_c 而言，G\ sample 的点都是一些离 V_c 很远的点。随着训练的不断进行，G\ sample 的点会逐渐向 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