Deep Graph Generators - A Survey

 

前置知识

RNN

LSTM

GRU

Attention

Transformer

AE

VAE

GNN

GCN

MPNN

Graph Attention

多元正态分布

随机变量 $x_i$ 的 期望 定义为 $\mathbb{E}(x_i)={\Sigma}p(x_i)x_i$;方差 定义为 $var(x_i)=\mathbb{E}_{p(x_i)}[\xi_i-\mathbb{E}(x_i)]$,其中,$\xi_i$ 是从 $x_i$ 中采样得到的样本,就是说,方差 不仅与分布有关,还与参与计算的样本有关。

函数 $f(x)$ 在分布 $p(x_i)$ 下的 期望 定义为 $\mathbb{E}_{x~p(x_i)}[f(x)]={\Sigma}p(x)f(x)$。

随机变量 $x_i$ 和 $x_j$ 的 协方差 定义为 $cov(x_i,x_j)=\mathbb{E}_{p(x_i,x_j)}[(\xi_i-\mathbb{E}(x_i))(\xi_j-\mathbb{E}(x_j))]$ 。

如果向量的每个元素都是 1 个随机变量,则这个向量称为 随机向量

设每个 样本 有 n 个 特征 ,每个 特征 都是 1 个 随机变量 ,则可用 随机向量 $\vec{X}=[x_1,x_2,…,x_n]$ 表示样本所在的分布。

从此分布中采样出 m 个 iid样本 构成 数据集,则可以表示为 1 个矩阵 $\mathtt{X}^{m{\times}n}$ 。

$\vec{X}$ 的 协方差矩阵 定义为 $C(\vec{X})=(c_{ij})^{n{\times}n}$ ,其中,$c_{ij}=cov(x_i,x_j)$ 。协方差矩阵 一定是对称的。如果是 对角的,则各个特征相互独立。

设每个 特征 服从 正态分布 $x_i~N(\mu_i,\sigma_i^2)$ ,则 随机向量 服从 多元正态分布 $\vec{X}~N(\vec{\mu},\Sigma)$ ,其中,$\vec{\mu}=[\mu_1,\mu_2,…,\mu_n]$ 是 $\vec{X}$ 的 均值向量 ,$\Sigma$ 是 $\vec{X}$ 的协方差矩阵。

设每个 特征 是独立的且服从 标准正态分布 $x_i~N(0,1)$ ,则 随机向量 服从 多元标准正态分布 $\vec{X}~N(\vec{0},\mathtt{I})$ ,其中,$\vec{X}$ 的 均值向量零向量, $\vec{X}$ 的 协方差矩阵单位矩阵

矩阵正态分布

如果矩阵的每个元素都是 1 个随机变量,则这个矩阵称为 随机矩阵

马尔可夫链 中,$x_t$ 表示 t 时刻的 随机变量,所有的 $x_t$ 的可能取值称为状态 $\vec{s}=[s_i]^n$。从 t 时刻到 t+1 时刻,$p(x_t=s_i,x_{t+1}=s_j)$ 表示某种 状态转移 的概率,定义 状态转移矩阵 $P=(p_{ij})^{n{\times}n}$ ,其中,$p_{ij}=p(x_t=s_i,x_{t+1}=s_j)$。可见, 状态转移矩阵 就是 1 个 随机矩阵

随机矩阵 服从 矩阵正态分布 $\mathtt{X}~MN_{m{\times}n}(\mathtt{M},\mathtt{U},\mathtt{V})$ ,当且仅当 $vec(\mathtt{X}^T)~N_{mn}(vec(\mathtt{M}^T,\mathtt{U}{\cdot}\mathtt{V}))$。其中,

$vec()$ 表示把矩阵按列拆开,然后把第 1 列后面接第 2 列,再接第 3 列,以此类推,最终得到 1 个 $mn$ 维的列向量。

$\cdot$ 表示 张量积(Kronecker product),$\mathtt{A}^{m{\times}n}{\cdot}\mathtt{B}^{p{\times}q}=(a_{ij}\mathtt{B})^{mp{\times}nq}$。

$\mathtt{M}$ 是 均值矩阵 $\mathtt{M}=(\mu_{ij})^{m{\times}n}$。

$\mathtt{X}$ 的每 1 列都是 1 个 随机向量,这些 随机向量协方差矩阵 是相同的,都是 $\mathtt{U}$,称为 列协方差矩阵

$\mathtt{X}$ 的每 1 行都是 1 个 随机向量,这些 随机向量协方差矩阵 是相同的,都是 $\mathtt{V}$,称为 行协方差矩阵

自相关方法

自回归模型Autoregressive model,简称AR模型),是统计上一种处理时间序列的方法,用同一变量例如x的之前各期,亦即x1至xt-1来预测本期xt的表现,并假设它们为一线性关系。因为这是从回归分析中的线性回归发展而来,只是不用x预测y,而是用x预测 x(自己);所以叫做自回归

Recurrent DGGs

MolMP

初始时图中仅有 1 个节点。然后迭代地决定:添加 1 个新节点;在新节点和另一个节点间添加一条边;结束。MolMP 仅根据图的当前状态计算 3 种动作的概率(马尔可夫决定过程)。每次迭代:

  1. 图卷积 计算新节点的 embedding ,再用 聚合操作 得到未添加新点的图的 embedding
  2. 把点的 embedding 和图的 embedding 输入 MLP 计算 3 种动作概率。
MolRNN

初始时图中仅有 1 个节点。然后迭代地决定:添加 1 个新节点;在新节点和另一个节点间添加一条边;结束。MolRNN 用 GRU 把 历史 纳入考虑。每次迭代:

  1. 图卷积 计算新节点的 embedding ,再用 聚合操作 得到未添加新点的图的 embedding
  2. 更新 隐状态 :$h_i=f_{trans}(h_{i-1},h_{v^},h_{G_{i-1}})$ 。其中, $h_i$ 是第 $i$ 次迭代的 隐状态 ;$f_{trans}$ 是 GRU ;$h_{v^}$ 是新节点的 embedding ;$h_{G_{i-1}}$ 是未添加新点的图的 embedding
  3. 把点的 embedding隐状态 输入 MLP 计算 3 种动作概率。
GraphRNN

指定某种节点排序规则 $\pi$ ,则图可以表示为序列 $S^{\pi}=(S^{\pi}1,S^{\pi}_2,…,S^{\pi}_n)$ ,其中,$S^{\pi}_i$ 是 ${0,1}^{i-1}$ 的序列,第 j 个元素表示节点 i 与节点 j 是否有边。于是问题变成采样 $p(S^{\pi})$ 。 $p(S^{\pi})$ 可按 条件概率分解 : \(p(S^{\pi})={\prod_{i=1}^{n+1}}p(S^{\pi}_i|S^{\pi}_1,...,S^{\pi}_{i-1})\) 自然想到先用 GRU 计算 隐状态 ,再用 隐状态 计算 $p(S^{\pi}_i)$ 。更新 隐状态 : \(h^{node}_i=f^{node}_{trans}(h^{node}_{i-1},S^{\pi}_{i-1})\) $S^{\pi}_i$ 也是序列,自然想到用 GRU 根据 $h^{node}_i$ 从 $S^{\pi}{i,0}$ 开始迭代计算 $p(S^{\pi}_{i,j})$ : \(\theta(S^{\pi}_{i,j}),h^{edge}_{i,j}=f^{edge}_{trans}(h^{edge}_{i,j-1},S^{\pi}_{i,j-1})\)

\[p(S^{\pi}_{i,j})=softmax(\theta(S^{\pi}_{i,j}))\]

其中,$h^{edge}_{i,0}=h^{node}_i$ 。

RNN-Transf
GraphRNN+Attn
MolecularRNN

把 GraphRNN 扩展:指定某种节点排序规则 $\pi$ ,则分子图可以表示为序列 $S^{\pi}=(S^{\pi}_1,S^{\pi}_2,…,S^{\pi}_n)$ 和 $C^{\pi}=(C^{\pi}_1,C^{\pi}_2,…,C^{\pi}_n)$ ,其中,$S^{\pi}_i$ 是 ${0,1,2,3}^{i-1}$ 的序列,第 j 个元素表示原子 i 与原子 j 的化学键类型;$C^{\pi}_i$ 是 ${1,2,…,K}$ ,表示原子 i 的类型。于是问题变成采样 $p(S^{\pi},C^{\pi})$ 。$p(S^{\pi},C^{\pi})$ 可按 条件概率分解联合概率分解 : \(p(S^{\pi},C^{\pi})=\Pi^{n+1}_{i=1}p(C^{\pi}_i|S^{\pi}_1,...,S^{\pi}_{i-1},C^{\pi}_1,...,C^{\pi}_{i-1})p(S^{\pi}_i|S^{\pi}_1,...,S^{\pi}_{i-1},C^{\pi}_1,...,C^{\pi}_{i})\) 自然想到先用 GRU 计算 隐状态 ,再用 隐状态 计算 $p(S^{\pi},C^{\pi})$ ;同时,用 embedding 计算原子的类型。 \([emb(S^{\pi}_{i}),emb(C^{\pi}_{i})],h^{node}_i=f^{node}_{trans}(h^{node}_{i-1},[emb(S^{\pi}_{i-1}),emb(C^{\pi}_{i-1})])\)

\[p(C^{\pi}_i)=softmax(f_{MLP}([emb(S^{\pi}_{i}),emb(C^{\pi}_{i})]))\]

$S^{\pi}i$ 也是序列,自然想到用 GRU 根据 $h^{node}_i$ 从 $S^{\pi}{i,0}$ 开始迭代计算 $p(S^{\pi}_{i,j})$ : \(emb(S^{\pi}_{i,j}),h^{edge}_{i,j}=f^{edge}_{trans}(h^{edge}_{i,j-1},emb(S^{\pi}_{i,j-1}))\)

\[p(S^{\pi}_{i,j})=softmax(f_{MLP}(emb(S^{\pi}_{i,j})))\]

其中,$h^{edge}_{i,0}=h^{node}_i$ 。

先用 所有分子数据集 预训练,再用得到的 MolecularRNN 进行 强化学习 ,使生成的分子图具有某种特性。MolecularRNN 作为 策略网络 ,生成的分子图作为 状态 ,下次迭代生成的所有可能的分子图作为 动作 ,损失函数为: \(L(\theta)=-\sum^{n}_{i=1}{r(s_i)\cdot{\gamma}^i{\cdot}{\log}p(s_i|s_{i-1};\theta)}\) 其中,$s_i$ 是第 i 次迭代得到的分子图;$r(s_i)$ 是此分子图的特性评分;$p(s_i|s_{i-1};\theta)$ 是 状态转移概率 ,也就是上面的 $p(S^{\pi},C^{\pi})$ 。

对违反 化学价约束 的情况增加 1 个 惩罚项 ;推断时采用 基于化学价的拒绝采样方法 ;以此保证生成分子的有效性。

Sun et al.
  1. 把图转化为 DAG,并得到节点排序。
  2. 分别用 Energy-FlowTopology-Flowencoder 计算每个节点的 embedding
  3. decoder 采用类似 GraphRNN 的方法生成新图。
Bacciu et al.

指定某种节点排序规则 $\pi$ ,并指定边排序规则为 $当u^{\pi}i<u^{\pi}{i+1} 或 u^{\pi}i=u^{\pi}{i+1},v^{\pi}i<v^{\pi}{i+1}时,S^{edge,\pi}i{\leq}S^{edge,\pi}{i+1}$ ,则分子图可以表示为序列 $S^{edge,\pi}=(S^{edge,\pi}_1,S^{edge,\pi}_2,…,S^{edge,\pi}_n)$ ,其中,$S^{edge,\pi}_i=(u^{\pi}_i,v^{\pi}_i)$ 是第 i 条边,用起点 $u^{\pi}_i$ 和终点 $v^{\pi}_i$ 的节点对表示。定义 $U^{\pi}=(u^{\pi}_1,…,u^{\pi}_m)$ 和 $V^{\pi}=(v^{\pi}_1,…,v^{\pi}_m)$ ,则: \(S^{edge,\pi}=p(U^{\pi})p(V^{\pi}|U^{\pi})\) 计算 $p(U^{\pi})$ : \(h^{U}_i=f_{trans}(h^{U}_{i-1},emb(u^{\pi}_{i-1}))\)

\[p(u^{\pi}_i)=softmax(f_{MLP}(h^{U}_i))\]

得到 $U^{\pi}$ 后计算 $p(V^{\pi}|U^{\pi})$ : \(h^{V}_i=f_{trans}(h^{V}_{i-1},u^{\pi}_{i})\)

\[p(v^{\pi}_i)=softmax(f_{MLP}(h^{V}_i))\]

其中,$h^V_0=h^U_n$ 。

GraphGen

根据 min DFS code ,把图转化为序列 $S^{edge}=(S^{edge}_i,…,S^{edge}_m)$ ,其中, $S^{edge}_i=(t_u,t_v,L_u,L_v,L_e)$ 是 5 元组,$t_u,t_v$ 是 DFS 访问到节点的时间戳, $L_u,L_v,L_e$ 是节点或边的标签。这种转化方法不用解决 节点顺序敏感问题 。于是问题变成采样 $p(S^{edge})$ 。 $p(S^{edge})$ 可按 条件概率分解 : \(p(S^{edge})={\prod_{i=1}^{n+1}}p(S^{edge}_i|S^{edge}_1,...,S^{edge}_{i-1})\) 因为 5 元组的各成分是独立的,所以可以继续分解: \(p(S^{edge}_i|S^{edge}_{<i})=p(t_u|S^{edge}_{<i}){\cdot}p(t_v|S^{edge}_{<i}){\cdot}p(L_u|S^{edge}_{<i}){\cdot}p(L_v|S^{edge}_{<i}){\cdot}p(L_e|S^{edge}_{<i})\) 用 LSTM 模拟 ,然后分别计算各成分的概率并采样: \(h_i=f_{trans}(h_{i-1},emb(S^{edge}_{i-1}))\)

\[t_u~softmax(f^{t_u}_{MLP}(h_i))\]

None-Recurrent DGGs

GRAN
AGE
DeepGMG
DeepGG
BiGG

自动编码器方法

先用 GNNGCN输入图 转化为 latent space embedding (encoder),然后再把 embedding 转化为 输出图 (decoder)。

One-Shot DGGs

一次性生成整张图。

VGAE

用 1 个 邻接矩阵 $A^{N{\times}N}$ 和 1 个 点特征矩阵 $X^{N{\times}L}$ 描述一张有 N 个节点 M 条边的图。

图的 隐矩阵 $Z$ 建模为 \(q(Z|X,A)={\prod_{i=1}^n}q(\vec{z}_i|X,A)\) 其中, \(q(\vec{z}_i|X,A)=N(\vec{z}_i|\vec{\mu}_i,diag({\sigma}^2_i))\) $\vec{\mu}i$ 用 1 个 GCN 学习:$\mu=GCN{\mu}(X,A)$ ;$\sigma_i$ 用另 1 个 GCN 学习:$\log{\sigma}=GCN_{\sigma}(X,A)$ 。

生成图建模为 \(p(A|Z)={\prod_{i=1}^n}{\prod_{j=1}^n}p(A_{ij}|\vec{z}_i,\vec{z}_j)\) 其中, \(p(A_{ij}=1|\vec{z}_i,\vec{z}_j)=\sigma(\vec{z}_i^T{\cdot}\vec{z}_j)\) VGAE 的缺点是只能学习 1 张图。

GraphVAE

用图集作为训练集。encoder 用 GCN 学习输入图的表示向量 $\vec{z}$ ,encoder 的分布是 $q_{\phi}(\vec{z}|G)$ ;decoder 输出 概率的全联接图(probabilistic fully-connected graph)$\tilde{G}$,decoder 的分布是 $p_{\theta}(G|\vec{z})$ ;损失函数是: \(L_{\theta,\phi}=\mathbb{E}_{q_{\phi}(\vec{z}|G)}[-\log{p_{\theta}(G|\vec{z})}]+KL[q_{\phi}(\vec{z}|G)||p(\vec{z})]\) 第 1 项的意义是生成图与原图尽量相似,第 2 项的意义是学到的表示向量的分布与真实的表示向量的分布尽量相似。

计算 $p_{\theta}(G \vec{z})$ 需要用图匹配算法。因为参数量大,算法复杂, GraphVAE 只能用于小规模图。
MPGVAE
RGVAE

用于生成“语义有效”的图。设第 $i$ 个有效性约束为 $g_i(\theta,\vec{z}){\leq}0$ ,根据拉格朗日,损失函数转化为: \(L=L_{\theta,\phi}(G)+{\mu}\sum_imax(g_i(\theta,\vec{z}),0)\)

Graphite

学习 1 张图,对图的结构建模,点特征矩阵 当作条件。encoder 用 GNN 学习 点特征 的隐向量 $\vec{z}_i$。decoder 部分,给定 $X,Z$ ,以下 2 个步骤交替进行:

  1. 由隐矩阵 $Z$ 构造矩阵 $\hat{A}=\frac{ZZ^T}{   Z   ^2}+\vec{1}\vec{1}^T$ ,其中,$\vec{1}\vec{1}^T$ 得到 1 个元素全为 1 的矩阵,以保证 $\hat{A}$ 中元素非负;
  2. 用 GNN 更新隐矩阵 $Z^*=GNN_{\theta}(\hat{A},[Z,X])$ 。

损失函数是似然函数的下界,$\log{p_{\theta}(A|X)}{\geq}L$ 。目标是最大化 $L$ ,$L$ 表示为: \(L=\mathbb{E}_{q_{\phi}(Z|A,X)}[\log{\frac{p_{\theta}(A,Z|X)}{q_{\phi}(Z|A,X)}}]\)

DGVAE

狄利克雷分布 代替 高斯分布 作为隐变量的先验分布。

证明了最大化重构项等价于最小化 均衡图割(balanced graph cut)

Substructure-Based Generators

Node-By-Node Generators

基于强化学习的深度生成模型

对抗生成模型

基于随机游走的方法

基于图的方法

基于 Flow 的方法