GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, Jure Leskovec
Stanford
Intro
有几个难点需要解决
- Large and variable output spaces：输出的n个点和m条边，这个会依据不同的graph而产生不同的结果。
- Non-unique representations：general graph generation问题中，我们想要假设graph structure上的某种分布，而不去假设固定的节点数。在这种情况下，有可能会尝试$$n!$$种图。这么高的representation complexity会带来比较大的挑战性。GraphVAE的解决方案是用了一个approximate graph matching，复杂度为$$\mathcal{O}(n^4)$$
- Complex dependencies：图中的edge information会有比较复杂的相互作用的关系。两个阶段如果有相同的neighborhood，那么更有可能会相互连接。因此edge不太会单独产生，而回jointly产生。Li et al 2018解决了这个方案，使用的是message passing的个数；但是这个方法的复杂度也比较高。
GraphRNN用autoregressive/recurrent的方法来生成图，抓住了所有edge和node的joint distribution。 GraphRNN可以被当作是一个hierarchical结构，graph-level RNN保留graph的状态和生产新的node，一个edge-level RNN负责对新生成的节点进行连边。使用BFS的遍历方法来缓解这么一个问题：graph的表示可以不唯一。
Proposed Approach
Notations and Problem Definition
一个node ordering $$\pi$$
每一个ordering对应于一个adjacency matrix $$A^\pi$$
目标是学习graph上的一个distribution $$p_{model}(G)$$，基于从set of observed graphs (sampled from data distribution $$p(G)$$)。并且我们也假设每一张图会对应不同的node ordering，这与前面的设定有所区别。
A Brief Survey of Possible Approaches
一些不同modeling $$p(G)$$的方法
Vector-representation based models. 将$$A^\pi$$ flatten 成为vector in $$\mathbb{R}^{n^2}$$，然后就可以送到VAE或者GAN中。但是有一个问题是无法产生不同size的graph，并且需要确定一个canonical ordering/permutation。
Node-embedding based models. 通过node embedding来embed graph，还有的方法是用generative model来decode edge probability基于pairwise node relation。但这个仅限于知道明确的node才行，且仅仅能生成一张图。
GraphRNN: Deep Generative Models for Graphs
Modeling Graph Sequences
graph distribution $$p(G)$$ 很难描述它的sample space，因此我们随机取样一个auxiliary ordering $$\pi$$来得到observation $$S^\pi$$，然后学习$$p(S^\pi)$$。因为是序列的数据结构，可以很自然地用autoregressive方法学习。在inference的时候，就可以不用学习graph distribution $$p(G)$$，而直接通过sequence $$S^\pi$$进行sample得到$$G$$。
因此我们将graph distribution转换成了sequence distribution。且：
$$ p(S^\pi) = \prod{i=1}^{n+1} p(S_i^\pi | S_1^\pi, ..., S{i-1}^\pi) = \prod{i=1}^{n+1} p(S_i^\pi | S{< i}^\pi)
$$
The GraphRNN Framework
我们将$$p(Si^\pi | S{< i}^\pi)$$用neural network来表示，且每一个time step都会share weights。这里用RNN，RNN包含了state-transition function和output function。
$$ fi = f{trans} (h{i-1}, S{i-1}^\pi)\ \thetai = f{out}(h_i)
$$
这里$$hi$$表示到第i时生成的graph state，$$S{i-1}^\pi$$是最近生成的node (i-1)的adjacency vector，而$$\theta_i$$是i的adjacency vector distribution $$S_i^\pi \sim P(\theta_i)$$。这只是一个非常general的framework。下面就来讨论一下具体的变形。
GraphRNN Variants
这里讨论两种variants，都使用GRU当作$$f{trans}$$，但是edge-level model $$f{out}$$不一样。
Multivariate Bernoulli GraphRNN-S。$$p(Si^\pi | S{< i}^\pi)$$是被当作multivariate Bernoulli distribution，parameterized by $$\thetai$$,而$$\theta$$是$$f{out}$$的output。详细的说，我们将$$f_{out}$$当作一层layer的MLP，sigmoid activation，且share weights across all time steps。sample edges according to $$\theta_i$$。
Dependent Bernoulli sequence 为了能够充分利用complex edge dependencies，我们这么进行decompose
$$ p(Si^\pi | S{< i}^\pi) = \prod{j=1}^{i-1} p( S{i,j}^\pi | S{i,< j}^\pi, S{< j}^\pi )
$$
这里每一个分布都是由另外RNN来估计的，也就是edge-level RNN。