GraphRNN

Definition

Graph recurrent neural network (GraphRNN) is a graph generation model. It generates graph in a autoregressive manner. GraphRNN treats graph generation as a sequential process. It generates nodes one at a time and for each new node, it decides its connections to previously generated nodes. The model consists of two main components: node-level RNN and edge-level RNN.

Architecture

Graph $G$ with node ordering $\pi$ can be uniquely mapped into a sequence of node and edge additions $S^{\pi }$. The sequence $S^{\pi }$ has two levels: node-level and edge-level. Node-level sequence adds nodes one at the time, and each node-level step is an edge-level sequence. Edge-level sequence adds edges between existing nodes. $S^{\pi }=(S_1^{\pi },S_2^{\pi },\dots ,S_n^{\pi })$ where $S^{\pi }$ is the entire graph sequence, and $S_i^{\pi }$ is $i$-th node-level step or edge-level sequence. $S_i^{\pi }=(S_{i,1}^{\pi },S_{i,2}^{\pi },\dots ,S_{i,m}^{\pi })$ where $S_{i,j}^{\pi }$ is $j$-th edge-level step in $i$-th node-level step.

The sequence is created from the Adjacency Matrix of a Graph.

Node-Level RNN

At each step, node-level RNN outputs a hidden state that summarizes the graph generated so far. The hidden state is used to initialize the edge-level RNN.

Edge-Level RNN

Edge-level RNN sequentially predict if the new node will connect to each of the previously generated nodes.