论文笔记：Adversarially Regularized Graph Autoencoder for Graph Embedding

前言

大多数现有的嵌入算法通常集中于保留拓扑结构或最小化图数据的重构错误，但它们大多忽略了图中潜在代码的数据分布，这通常导致在现实世界中的图数据嵌入效果较差。由此作者提出了两种基于对抗正则化的图自动编码方法：**即对抗正则化图自动编码器（ARGA）和对抗正则化变图自动编码器（ARVGA）。**实验证明了算法在链接预测，图聚类和图可视化任务方面大大优于baseline。
论文链接：https://arxiv.org/pdf/1802.04407v2.pdf

1. Introduction

首先介绍了一些图类型数据的任务包括节点/图分类、点聚类，由于高计算复杂度，低并行性以及机器学习方法无法用于图形数据，使得这些图形分析任务极具挑战性。最近图嵌入方法已经成为解决此类问题的一个切入点

图嵌入：将图数据转换为低维，紧凑且连续的特征空间，关键在于保留拓扑结构，顶点内容以及其他信息

这种新的学习范式已将寻找用于分类，聚类和链接预测的复杂模型的任务转移到学习图数据的可靠表示形式，因此可以通过采用简单的传统模型轻松地执行任何图分析任务

目前主流的图嵌入方法分为三类：

概率模型：DeepWalk，node2vec，LINE
基于矩阵分解的算法：GraRep，HOPE，M-NMF
基于深度学习的算法：SDNE，DNGR

**上面的方法通常是非正规化的方法，主要侧重于保持结构关系（概率方法）或最小化重构误差（矩阵分解或深度学习方法）。他们大多忽略了潜在代码的数据分布。**可能会导致难以处理现实世界中稀疏并且存在噪音误差的图形数据。解决办法是引入正则化方法，使降维的数据可以学习到与处理数据中的特征而不是机械的记忆

对抗正则化图自动编码器（ARGA）和对抗正则化变图自动编码器（ARVGA），**不仅使图形结构的重构误差最小，而且使潜码与先验分布匹配。**算法将图数据encoder在code中。借助旨在重构拓扑图信息的decoder，并且进一步采用了对抗训练方案来规范化潜在代码以学习鲁棒的图表示。对抗训练模块旨在区分潜在代码是来自实际的先验分布还是来自图形编码器。图编码器学习和对抗性正则化在一个统一的框架中进行了联合优化，从而使彼此受益，并最终实现了更好的图嵌入。

此篇文章主要分析了三个无监督的图分析问题：即链接预测，节点聚类和图可视化

2. Related Work

图嵌入模型可以分为两大类：

拓扑图嵌入方法：认为只有拓扑结构可以保留信息，因此主要的学习目的是保存拓扑信息。代表性的方法有：DeepWalk，node2vec，GraRep等
内容增强的图嵌入方法：认为节点信息包含了拓扑结构的相关信息和节点自身feature，可以加以利用。代表性方法：TADW，TriDNR，SNE

3. Problem Definition and Framework

论文笔记：Adversarially Regularized Graph Autoencoder for Graph Embedding
输入：代表图拓扑结构的邻接矩阵 $A$ 和代表节点内容信息的节点特征向量 $X$
encoder：由图卷积构成的自动编码器最终嵌入 $Z$ 中
decoder：简单地通过矩阵转置的相乘进行解码
ARVGA：考虑变分的额外输入
discriminator：对抗生成的思想，区分原数据和自动编码器降维嵌入的输出
低维嵌入的输出 $Z$ 应该尽可能的保留，原始图拓扑结构信息和节点特征信息

3.1 Overall Framework

整个架构看起来还是挺清晰的，大致上来看由两部分组成：

Graph Convolutional Autoencoder：
自动编码器采用图 $A$ 的结构和节点内容 $X$ 作为输入来学习潜在表示 $Z$ ，然后从 $Z$ 重构图结构 $A$ 。
Adversarial Regularization：
对抗网络通过对抗训练模块强制潜在代码匹配先前的分布，该模块训练当前潜在代码是来自编码器还是来自先前的分布

4. Algorithm

4.1 Graph Convolutional Autoencoder

在encoder部分与大部分图卷积的选择一致，都是Kipf在2016年提出的以切比雪夫多项式的一阶近似来拟合卷积核进行特征的提取方法
论文笔记：Adversarially Regularized Graph Autoencoder for Graph Embedding
应用到该架构上就是两层图卷积

需要注意的是，对于ARVGA还要考虑变分的两个参数，计算公式如下

说明一下，与之前提到过的GAE和VGAE策略相同，第一层共享权重，第二层存在差异

到了decoder部分，与GAE/VGAE高度相似
论文笔记：Adversarially Regularized Graph Autoencoder for Graph Embedding

损失函数部分分为ARGA和ARVGA，一脉通体
论文笔记：Adversarially Regularized Graph Autoencoder for Graph Embedding

4.2 Adversarial Model

这里应该是这篇paper最重要的部分了，其余部分与前人的工作没什么差异。文章中作者提出了一个概念就是强化图嵌入结果对原始信息的包含，也就是说让输出 $Z$ 尽可能地匹配原始数据，作者希望通过对抗训练模型达到这一目的

对抗模型建立在标准多层感知器（MLP）上，其中输出层只有一个维度。对抗模型充当区分encoder生成的嵌入表示code是来自原始数据 $P_z$ （正）还是来自图编码器 $G（X; A）$ （负）的判别器。通过最小化训练二元分类器的交叉熵代价，最终将在训练过程中对嵌入进行规则化和改进。成本可以计算如下：
论文笔记：Adversarially Regularized Graph Autoencoder for Graph Embedding
整体流程如下

很重要的部分