Deep Generative Models for Graphs

Until now the course has learned from graphs: we assumed the graph was given. Slide 4 shows three examples, a social network, an economic network and a communication network, and asks the new question: how are these graphs generated?

Slide 5 states the problem. We want to generate realistic graphs with a graph generative model: the model outputs a synthetic graph that should be similar (\(\approx\)) to a real graph. Applications: drug discovery and material design (a molecule is a graph), and social network modeling.

Slide 6 gives four reasons to study graph generation:

• Insights: if a model can produce the graph, we understand how the graph forms.
• Predictions: we can predict how the graph will evolve.
• Simulations: we can run the same process to produce new graph instances.
• Anomaly detection: we can decide whether a graph is normal or abnormal (a graph that the model finds very unlikely is suspicious).

Slide 7 places the lecture in history. Step 1: measure properties of real-world graphs (degree distribution, clustering, path lengths); a good generator must reproduce them. Step 2: traditional generative models (for example Erdős–Rényi, small-world, preferential attachment, Kronecker), each with its own assumption about how graphs form. Step 3: deep generative models, which learn the formation process from data. This lecture is step 3.

Slides 8–9 make the contrast with earlier lectures visual. The same GNN picture (graph convolutions, activation, regularization such as dropout, more graph convolutions) is drawn twice. On slide 8 the arrow goes left to right and the output is node embeddings: a deep graph encoder. On slide 9 the arrow is reversed and the output is the graph structure itself: a deep graph decoder. Today we build decoders.

Slide 11 separates two tasks:

• Task 1, realistic graph generation: produce graphs similar to a given set of graphs. This is the main focus of the lecture (GraphRNN).
• Task 2, goal-directed graph generation: produce graphs that optimize given objectives or satisfy constraints, for example drug-molecule generation or optimization (GCPN, at the end).

Slide 12 formalizes Task 1. We are given graphs sampled from an unknown \(p_{\text{data}}(G)\). We want to (a) learn a distribution \(p_{\text{model}}(G)\) and (b) sample new graphs from it. The picture shows a box of training graphs labelled \(p_{\text{data}}(G)\), an arrow "Learn & Sample", and a box of similar-looking generated graphs labelled \(p_{\text{model}}(G)\).

Slide 13, the general setup. We have data points \(\{x_i\}\) (here, graphs) with \(x_i \sim p_{\text{data}}(x)\); the distribution itself is never known. The model \(p_{\text{model}}(x;\theta)\) has parameters \(\theta\). Two goals: (1) density estimation, make \(p_{\text{model}}(x;\theta)\) close to \(p_{\text{data}}(x)\); (2) sampling, be able to draw new \(x\) from \(p_{\text{model}}\). New graphs are exactly such samples.

Slide 14, goal (1): the key principle is maximum likelihood:

In practice we maximize \(\sum_i \log p_{\text{model}}(x_i;\theta)\) over the observed points: find the model most likely to have generated the observed data.

Slide 15, goal (2): to sample from a complex distribution, the common approach is (1) sample simple noise \(z_i \sim N(0,1)\), then (2) transform it with a complex function, \(x_i = f(z_i;\theta)\). Then \(x_i\) follows a complex distribution. How do we design \(f\)? Use a deep neural network and train it on our data.

Slide 16 introduces the family used today: autoregressive models. Here the same \(p_{\text{model}}(x;\theta)\) does both density estimation and sampling (VAEs and GANs use two or more networks, each playing one role). The idea is the chain rule of probability:

If \(x\) is a vector, \(x_t\) is its \(t\)-th dimension; if \(x\) is a sentence, \(x_t\) is the \(t\)-th word. For graphs, \(x_t\) is the \(t\)-th action: "add a node" or "add an edge". Computing the likelihood is easy (multiply the conditionals), and sampling is easy (draw \(x_1\), then \(x_2\) given \(x_1\), and so on).

Slide 18 introduces GraphRNN (You, Ying, Ren, Hamilton, Leskovec, ICML 2018): generate a graph by sequentially adding nodes and edges. The figure shows a 5-node graph \(G\) (a square 1–2–4–3 with node 5 attached to 3 and 4) and its generation process \(S^\pi\): add node 1, add node 2 and connect it to 1, add node 3 and connect it to 1, add node 4 and connect it to 2 and 3, add node 5 and connect it to 3 and 4.

Slide 19: a graph \(G\) with a node ordering \(\pi\) maps uniquely to a sequence of node and edge additions \(S^\pi = (S^\pi_1,\dots,S^\pi_5)\), and back (the two arrows). Each \(S^\pi_i\) is the step that adds node \(i\) together with its edges to earlier nodes.

Slides 20–21: \(S^\pi\) has two levels (it is a sequence of sequences).

• Node level: at each step a new node is added ("add node 1", …, "add node 5").
• Edge level: each node-level step is itself a sequence; at each edge step we decide on one new edge. Example from slide 21: \(S^\pi_4 = (S^\pi_{4,1}, S^\pi_{4,2}, S^\pi_{4,3})\) = ("not connect 4,1", "connect 4,2", "connect 4,3") = \((0,1,1)\).

Slide 22 summarizes: a graph + a node ordering = a sequence of sequences. The node ordering is chosen at random (the lecture returns to this with BFS). The figure shows the graph next to its adjacency matrix. Reading the upper triangle column by column (left to right = node-level sequence) and, inside each column, top to bottom (edge-level sequence) gives exactly \(S^\pi\). Column 4 is highlighted: entries \(0,1,1\), i.e. node 4 connects to 2 and 3 but not to 1. Column 5 is \(0,0,1,1\).

Slide 23: we have turned graph generation into sequence generation. We must model two processes: (1) generate a state for a new node (node-level sequence), and (2) generate edges for the new node based on that state (edge-level sequence). Approach: use Recurrent Neural Networks (RNNs) for both. The same principles apply to Transformers.

Slide 24 recalls RNNs. They are built for sequential data. An RNN reads an input sequence \(x_1, x_2, \dots\) and updates hidden states \(s_0, s_1, s_2,\dots\); each hidden state summarizes all input seen so far. The update is done by an RNN cell, which also emits an output \(y_t\) at each step.

Slide 25 defines the cell. \(s_t\) is the state after step \(t\), \(x_t\) the input, \(y_t\) the output; \(W, U, V\) are trainable. In GraphRNN's edge-level model, \(s_t\), \(x_t\) and \(y_t\) are scalars (edge probabilities).

More expressive cells exist: GRU, LSTM, and so on.

Slides 26–28: GraphRNN has a node-level RNN and an edge-level RNN. The node-level RNN produces the initial state for the edge-level RNN; the edge-level RNN then predicts, one by one, whether the new node connects to each previous node. The figure on slide 27 shows node-level states \(h_1,\dots,h_6\) (green arrows, "node-level update") starting from SOS, with the growing graph drawn above them. Under each \(h_i\) hangs a column: \(S^\pi_2=(1)\), \(S^\pi_3=(1,0)\), \(S^\pi_4=(0,1,1)\), \(S^\pi_5=(0,0,1,1)\) (blue arrows, "sample + edge-level update"). Slide 28 adds that after the edge-level RNN finishes its column, its result is used to update the node-level RNN state for the next node.

Slide 29 answers three questions about generating sequences with an RNN:

• How to generate? Feed the previous output as the next input: \(x_{t+1} = y_t\).
• How to start? Use a start-of-sequence token (SOS) as the first input, usually a vector of all zeros or all ones.
• When to stop? Add an end-of-sequence (EOS) output. If EOS = 0 the RNN continues; if EOS = 1 it stops.

Slide 30 draws this: \(x_1 = \text{SOS}\), \(x_2 = y_1\), …, \(x_T = y_{T-1}\), and the last cell outputs EOS = 1. The slide ends with a problem: this model is deterministic. With the same start it always produces the same sequence, so it can only generate one graph. We need randomness.

Slide 31 makes the model stochastic (consider the edge-level RNN for now). Our goal is to model \(\prod_{t=1}^n p_{\text{model}}(x_t\mid x_1,\dots,x_{t-1};\theta)\). Let the output be a probability:

So each RNN step outputs the probability of one edge; we sample from it and feed the sample (not the probability) into the next step.

Slide 32 shows this for an already-trained edge-level RNN. \(y_t\) is a scalar that defines a Bernoulli distribution: value 1 with probability \(p\), value 0 with probability \(1-p\). Start with \(s_0 = \text{SOS}\), \(x_1 = \text{SOS}\). The first cell outputs \(y_1 = 0.9\); we sample \(x_2 \sim 0.9\) and get \(x_2 = 1\). The next cell outputs \(y_2 = 0.4\); we sample \(x_3\sim 0.4\) and get \(x_3 = 0\). The third outputs \(y_3 = 0.7\), and so on. The question at the bottom: how do we use training data \(x_1,\dots,x_n\)?

Slide 33, training. We observe a true edge sequence \(y^*\), for example \([0,0,1,\dots]\). The principle is teacher forcing: replace the inputs and the targets by the real sequence. In the figure, the model outputs \(y_1 = 0.9, y_2 = 0.4, y_3 = 0.7\), the targets are \(y_1^* = 0, y_2^* = 0, y_3^* = 1\), and the inputs are the true values \(x_2 = 0, x_3 = 0\), not the model's own samples. A loss is computed at every step.

Slide 34: the loss is binary cross-entropy:

If \(y_1^* = 1\), we minimize \(-\log y_1\), which pushes \(y_1\) up. If \(y_1^* = 0\), we minimize \(-\log(1-y_1)\), which pushes \(y_1\) down. In the example \(y_1^* = 0\) and \(y_1 = 0.9\), so the loss is large and training lowers \(y_1\). Since \(y_1\) is computed by the RNN, backpropagation adjusts the RNN parameters.

Why teacher forcing? Early in training, the model's own samples are mostly wrong; feeding them back would train later steps on nonsense prefixes. With true prefixes, every step gets a clean signal and the summed loss is exactly \(-\log p_{\text{model}}\) of the true sequence, i.e. maximum likelihood.

Slide 35 gives the full plan:

1. Add a new node: run the node RNN for one step; its output initializes the edge RNN.
2. Add edges for the new node: run the edge RNN to predict whether the new node connects to each previous node.
3. Add another node: use the last hidden state of the edge RNN to run the node RNN one more step.
4. Stop: if the edge RNN outputs EOS at its first step, the new node connects to nothing, and graph generation stops.

Slides 36–43 walk through training on an observed graph with edges 1–2 and 1–3 (adjacency matrix rows \(0\,1\,1\); \(1\,0\,0\); \(1\,0\,0\)):

• Slide 36: node 1 is in the graph; to add node 2, start the node RNN with SOS.
• Slide 37: the edge RNN (started with SOS) predicts "will node 2 connect to node 1?" and outputs 0.5.
• Slide 38: update the node RNN with the edge RNN's hidden state.
• Slide 39: for node 3, the edge RNN outputs 0.6 for "connect to node 1?". By teacher forcing, the next input is the true answer, 1 (node 3 does connect to node 1). It then outputs 0.4 for "connect to node 2?".
• Slide 40: update the node RNN again.
• Slide 41: for node 4 the edge RNN's first output is EOS (here 0.4); since node 4 connects to nothing in the data, generation stops.
• Slide 42: every prediction gets supervision from the ground truth (targets 1 for 2–1; 1 and 0 for node 3; EOS for node 4).
• Slide 43: backprop through time: the red arrows show gradients accumulated across all time steps of both RNNs.

Slides 44–45 show test time: (1) sample each edge from its predicted distribution; (2) replace every input by GraphRNN's own previous prediction. In the example the edge RNN outputs 0.9 for 2–1 and samples 1; for node 3 it outputs 0.2 and 0.2 and samples 0 and 0; for the next node the EOS output 0.5 is sampled as EOS, so generation stops. Slide 45 shows the generated graph: edge 1–2, with node 3 isolated. This differs from the observed graph, which is fine: we sample from a distribution, we do not copy.

Slide 46, quick summary: generate a graph by generating a two-level sequence, and use RNNs to generate the sequences (node-level RNN across columns, edge-level RNN down each column of the adjacency matrix). Next: make GraphRNN tractable and evaluate it properly.

Slide 48 states the problem. With a random ordering, any node can connect to any prior node. So there are too many edge-generation steps: we must generate the full adjacency matrix, and the edge dependencies are complex and very long. The figure shows a random ordering of the 5-node graph, where node 5 may connect to any or all previous nodes, with the "recipe": add node 1, add node 2, add node 3, connect 3 with 2 and 1, add node 4, … How do we limit this complexity?

Slide 49: use a Breadth-First Search (BFS) node ordering. The recipe becomes: add node 1; add node 2; connect 2 with 1; add node 3; connect 3 with 1; add node 4; connect 4 with 3 and 2. The argument:

• Node 4 does not connect to node 1.
• In BFS, all of node 1's neighbors are visited right after node 1 is processed, so they have all appeared already.
• Therefore node 5 and every later node will never connect to node 1.
• So we only need memory of 2 "steps" (the recent frontier), not \(n-1\) steps.

Slide 50 lists the benefits: (1) fewer possible node orderings, from \(O(n!)\) to the number of distinct BFS orderings; (2) fewer edge-generation steps, because each new node looks at fewer previous nodes.

Slide 51 shows the effect on the adjacency matrix for \(N = 10\). Without BFS, the blue (possible-edge) region is the whole upper triangle: column \(i\) needs \(i-1\) entries, up to \(M = 9\) ("connectivity with all previous nodes"). With BFS, the blue region is a band along the diagonal of width \(M = 3\) ("connectivity only with nodes in the BFS frontier"). The edge RNN only needs to output \(M\) entries per column, so the work drops from \(O(n^2)\) to \(O(nM)\).

Slide 52 poses the task: compare two sets of graphs, a training set and a generated set, and ask how similar they are. We need similarity metrics for graphs. Two solutions: (1) visual similarity and (2) graph statistics similarity.

Slide 53, visual similarity on grid graphs. Top row: three training grids. Middle row (red box): three GraphRNN samples, which are clearly grid-like (one is slightly distorted). Bottom row: baselines Kronecker, MMSB (mixed-membership stochastic block model) and B-A (Barabási–Albert). They look like random hairballs and miss the grid structure completely.

Slide 54, the same comparison on community graphs (graphs made of two dense clusters). GraphRNN samples show two clear communities joined by a few edges, like the training graphs. Among the baselines, MMSB (a block model, so built for communities) also shows two clusters, but Kronecker and B-A produce a single blob with no community split.

Intuition: traditional models hard-code one formation mechanism (preferential attachment, block structure, recursive self-similarity), so they can only produce graphs of that kind. GraphRNN learns the mechanism from examples, so it adapts to grids, communities or anything else in the training set.

Graph statistics similarity (option 2) is only named on slide 52. In the GraphRNN paper, one compares distributions of degree, clustering coefficient and orbit counts between the two sets with Maximum Mean Discrepancy (MMD). Visual inspection alone is not a metric: it does not scale and is subjective.

Slide 56 moves to drug discovery (You, Liu, Ying, Pande, Leskovec, NeurIPS 2018). Question: can we learn a model that generates valid and realistic molecules with optimized property scores? Picture: Model → output molecule → that optimizes → Property, for example drug_likeness = 0.95.

Slide 57: we want graphs that

• optimize a given objective (high scores), e.g. drug-likeness;
• obey underlying rules (valid), e.g. chemical validity rules (an atom can only form a limited number of bonds);
• are learned from examples (realistic), i.e. imitate a molecule dataset. GraphRNN already covered this part.

Slide 58 marks the hard part: the objective is a black box. Properties like drug-likeness are governed by physical laws that we assume are unknown to us. We can evaluate a molecule, but we cannot differentiate the score with respect to the model.

Slide 59: the tool for this is reinforcement learning (RL). An ML agent observes the environment, takes an action, and receives a positive or negative reward; it learns from this loop. The key idea: the agent learns directly from the environment, which is a black box to it. The diagram: ML Agent → Action → Environment → Observation, Reward → ML Agent.

Slide 60: the solution is the Graph Convolutional Policy Network (GCPN), which combines graph representation and RL. Its key components:

• a graph neural network captures the structure of the partial graph;
• reinforcement learning guides the generation toward the desired objectives;
• supervised training imitates examples in the given dataset.

Slide 61 compares GCPN with GraphRNN. Common: both generate graphs sequentially and imitate a given dataset. Differences: (1) GCPN uses a GNN to predict the generation action. Pro: a GNN is more expressive than an RNN. Con: a GNN takes longer to compute. (2) GCPN also uses RL to direct generation toward our goals, which enables goal-directed generation.

Slide 62 shows the difference in pictures. GraphRNN predicts actions from RNN hidden states: from the partial graph 1–2, 1–3, the node RNN and three edge-RNN steps output 0, 1, 1, so node 4 connects to 2 and 3. The hidden state "captures the generated graph so far", but only implicitly. GCPN predicts actions from GNN node embeddings: run a GNN on the current graph (with the new node 4), get an embedding for every node, and score each possible link with the link prediction head from earlier lectures:

Slide 63, overview of one GCPN step. (a) State \(G_t\) (a partial molecule of carbon atoms) plus a scaffold \(C\) of candidate atoms (here C, N, O) that can be inserted. (b) The GCPN policy \(\pi_\theta(a_t\mid G_t\cup C)\) runs message passing and computes node embeddings. (c) Sample an action \(a_t\sim\pi_\theta\): two node IDs to connect (one may be a new scaffold atom), an edge (bond) type, and a stop flag. (d) The environment updates the graph, \(p(G_{t+1}\mid G_t,a_t)\), and checks chemical validity. (e) New state \(G_{t+1}\). (f) Reward \(r_t\), shown as a step reward 0.1 and a final reward 0.

Slide 64, the reward:

• Step reward: learn to take valid actions. At each step, give a small positive reward for a valid action.
• Final reward: optimize the desired property. At the end, give a positive reward for a high property score.

Slide 65, training has two parts: (1) supervised training, which trains the policy to imitate actions taken in real observed graphs, using gradients (the same idea as GraphRNN); (2) RL training, which trains the policy to maximize rewards with a standard policy gradient algorithm (see any RL course, e.g. Stanford CS234).

Slide 66 draws both loops from a current graph \(G_t\). Top (supervised): GCPN runs one step to get a generated \(G_{t+1}\); the query dataset gives the real next graph \(G^*_{t+1}\); a cross-entropy loss (0.6 in the figure) gives the gradient. Bottom (RL): GCPN runs until stop to get a complete molecule \(G^*_T\); the environment returns step reward 0.1 and final reward 1; the policy gradient flows back into GCPN.

Slide 67, property optimization: generate molecules with a high score for a chosen property. (a) Penalized logP optimization: four generated molecules with scores 7.98, 7.48, 7.12 and 23.88*. The first three are long carbon chains with branches; the starred one (drawn in purple) is an unrealistic, heavily branched structure that exploits the score. (b) QED (drug-likeness) optimization: four ring-containing, drug-like molecules with scores 0.948, 0.945, 0.944 and 0.941.

Slide 68, constrained optimization: start from a given molecule and edit it for a few steps to raise the property score, here penalized logP, i.e. increase the solubility in octanol. One starting structure scores −8.32 and the finished one −0.71 (long alkyl chains were added). Another goes from −5.55 to −1.78.

Slide 69, summary of graph generation:

• Complex graphs can be generated successfully by sequential generation with deep learning.
• Each step makes a decision based on a hidden state, which can be implicit (a vector representation, decoded with an RNN, as in GraphRNN) or explicit (the intermediate generated graph, decoded with a GCN, as in GCPN).
• Possible tasks: imitating a set of given graphs, and optimizing graphs toward given goals.

The 23.88* molecule is a useful warning: when a black-box reward is the only goal, RL finds strange solutions that score well but are not realistic. That is why GCPN keeps the supervised imitation term and the validity rewards.