GAN在网络特征学习中的一些应用

会员服务 ·

GAN在网络特征学习中的一些应用

2018 年 1 月 25 日 计算机视觉战队 WG.Edison

首先来看看 GAN 现在能做到哪些惊艳的事呢？

GAN 可以被用来学习生成各种各样的字体——也就是说，以后字迹辨认这种侦查手段很可能就不靠谱啦！这个工作还有很多动图，在 GitHub 上搜 zi2zi 这个 project 就可以。

有了GAN，以后就不怕灵魂画手了！左边这么简单的“简笔画”，居然也可以直接生成出对应的蕴含丰富含义的完整图画呢。这个工作同时还可以用来做一些修正，比如可以把春天的山变成被白雪覆盖尖端的山——而这一切只需要一点点白色的涂抹。

可参考：机器人也会画漫画

有了GAN，不仅仅可以在有辅助的情况下作画，还可以在无辅助的情况下完成很多修饰！比如从分割图变成真实照片，从黑白图变成彩色图，从线条画变成富含纹理、阴影和光泽的图……这些都是用 pix2pix里的方法生成的。

去年非常火爆的应用，脸萌当然也难不倒 GAN！想拥有自己的专属Q版定制头像吗？快去看看：

Yaniv Taigman, Adam Polyak, Lior Wolf. “Unsupervised Cross-Domain Image Generation”. ICLR 2017

基础知识：

严格来说，一个GAN 框架，最少（但不限于）拥有两个组成部分，一个是生成模型 G，一个是判别模型 D。在训练过程中，会把生成模型生成的样本和真实样本随机地传送一张（或者一个 batch）给判别模型 D。判别模型 D 的目标是尽可能正确地识别出真实样本（输出为“真”，或者1），和尽可能正确地揪出生成的样本，也就是假样本（输出为“假”，或者0）。这两个目标分别对应了下方的目标函数的第一和第二项。而生成模型的目标则和判别模型相反，就是尽可能最小化判别模型揪出它的概率。这样 G 和 D 就组成了一个 min-max game，在训练过程中双方都不断优化自己，直到达到平衡——双方都无法变得更好，也就是假样本与真样本完全不可区分。

通过这样的巧妙设计，GAN 就拥有了一个非常吸引人的性质。GAN 中的 G 作为生成模型，不需要像传统图模型一样，需要一个严格的生成数据的表达式。这就避免了当数据非常复杂的时候，复杂度过度增长导致的不可计算。同时，它也不需要 inference 模型中的一些庞大计算量的求和计算。它唯一的需要的就是，一个噪音输入，一堆无标准的真实数据，两个可以逼近函数的网络。

而今天要说的是特征学习的主要内容：

网络特征学习（network representation learning / network embedding）是近年来兴起的一个特征学习的研究分支。

作为一种降维方法，网络特征学习试图将一个网络中的节点映射到一个低维连续向量空间中，并在该低维空间中保持原有网络的结构信息，以辅助后续的连接预测、节点分类、推荐系统、聚类、可视化等任务。

Outline

本次主要分为2个部分：

首先，介绍 Graph Representation Learning 的定义、应用、分类方法和相关代表作；

第二部分，介绍GraphGAN: Graph Representation Learning with Generative Adversarial Nets。

关于GRL

首先，介绍图特征学习或者网络特征学习。其主要目的在于，将图中每一个节点都映射到一个低维向量空间，并且在此空间内保持原有图的结构信息或距离信息。Graph Representation Learning 目前没有任何官方定义或名字，它也可以被称作 Network Embedding、Graph Embedding 或 GRL。

如上图，左图有三个节点和三条边，其中的数字表示各边的权值 weight，我们通过 GRL 将其映射到一个二维空间中。可以发现，如果两个点之间的 weight 越大，那么它们之间的距离就越近。这就是 GRL 的精髓所在，即在低维空间中保持原有图的结构信息。

Application

Graph Representation Learning 的应用相当广泛，它可以被用于链路预测、节点分类、推荐系统、视觉、知识图谱表示、聚类、Text Embedding 以及社会网络分析。

GRL分类方法

将 GRL 的方法按照不同分类来进行介绍：

第一种叫同构图，即图中的节点和边都只有一种，比如引用网络，其中的节点表示每篇 paper，边表示引用关系。

第二种是异构图，即网络中的节点和边不止一种，一般分为2种情况：

多媒体网络。比如有的 paper 就考虑过一张图具备图像和文本两种节点，以及图像文本、图像图像和文本文本这三种边。
知识图谱。图中节点表示的是实体，边表示的关系。每一个三元，HRT 都表示头节点 H 和尾节点 T 有关系 R。由于关系 R 可以有很多种，因此 KG 也属于一种异构图。

第三种是 Graph with side information，side information 即为辅助信息。这种图是指除了边和点之外，节点和边都会带有辅助信息，比如边和点都有 label，边和点都有 attribute，或者 note 有 feature。它们的区别在于 label 是类别型的，attribute 可以是离散的，也可以是连续的，而 feature 就可能是文本或图像等更复杂的一些特征。

第四种是 Graph Transformed from non-relational data，即从非关系型数据中转换成的图，一般是指在高维空间中的一些数据。

上图是我整理的 GRL 方法代表作。按照时间顺序可将它们分为三类，第一类是传统方法，包含 PCA、LDA、MDS 等降维方法。

GraphGAN

Motivation 1

前文将 Network Embedding 的方法归为三类，而我们在 GraphGAN 里将其分为两类，第一类叫生成式模型，第二类叫判别式模型。生成式模型是指，假定在图中存在一个潜在的、真实的连续性分布 Ptrue(V|Vc)。对于给定的 Vc 而言，我们可以看到 Vc 跟四个节点相连接，图中除了 Vc 之外还有五个节点。Ptrue(V|Vc) 就是指在除了 Vc 之外其他节点上的分布。假设图中对于每个 Vc 都有这么一个分布，那么图中的每条边都可以看作是从 Ptrue 里采样的一些样本。这些方法都试图将边的似然概率最大化，来学习 vertex embedding。我们之前提到的 DeepWalk 和 Node2vec 都属于生成式模型。

Motivation 2

判别式模型是指，模型试图直接去学习两个节点之间有边的概率。这种方法会将 Vi 和 Vj 联合作为 feature，然后输出的是 edge 的概率 P(edge|Vi, Vj)。这种方法的代表作是 SDNE，以及 DASFAA 上的一篇 PPNE。

这样分类之后，一个很自然的想法是，判别式模型和生成式模型能否进行联合。这两者其实可以看作是一个硬币的两面，他们是相互对立又相互联系的。

Motivation 3

受以上工作启发，我们提出了 GraphGAN，它是一个在网络生成学习中将生成模型和判别模型加以结合的框架。

GraphGAN Framework

通过上图可以看出，我们在每一步的迭代中，从 Ptrue 中 sample 出来了一些跟 Vc 真实相邻的绿点，然后从 G 中又生成了一些跟 Vc 相连的蓝点。我们将绿点作为正样本，将蓝点作为负样本来训练 D，在得到 D 之后，再用 D 中的信号去反过来训练 G。这就是之前所说的 policy gradient 过程。我们不断重复这个过程，直到生成器 G 和 Ptrue 极为接近。

在刚开始的时候，G 相对比较差，因此对于给定的 Vc 而言，G sample 的点都是一些离 Vc 很远的点。随着训练的不断进行，G sample 的点会逐渐向 Vc 接近，到最后 G sample 的点几乎都变成了真正跟 Vc 相邻的点，也就是 G 和 Ptrue 已经很难被区分了。

接下来，我们来讨论一下 G 的实现过程。一种最直观的想法是用 softmax 来实现 G，也就是将 G(v|VC) 定义成一个 softmax 函数。这种定义有如下两个问题：首先是计算复杂度过高，计算会涉及到图中所有的节点，而且求导也需要更新图中所有节点。这样一来，大规模图将难以适用。另一个问题是没有考虑图的结构特征，即这些点和 Vc 的距离未被纳入考虑范围内。

第二种方法是使用层次 softmax，具体来说就是组织了一棵二叉树，然后将所有节点都放在叶节点的位置，再将当前的 Vc 从根开始计算。由于从根到每个叶结点都存在唯一路径，因此这个计算可以转换成在树的路径上的计算，即它的计算复杂度为 logN ，N 代表树的深度。这种做法虽然可以简化计算，但它仍然没有考虑到图结构特征。

第三种方法是 Negative Sampling。这种方法其实是一个优化方法，它并没有产生有效的概率分布，并且同样没有考虑图的结构特征信息。

Graph Softmax