Research/Blog
Generative Models for Graphs
- August 13, 2020
- Posted by: vsinghal
- Category: Generative Modeling Graph Neural Networks Pharma
#CellStratAILab #disrupt4.0 #WeCreateAISuperstars
Recently, our AI Lab Researcher Gouthaman Asokan presented an amazing session on Generative Models for Graphs. This is part of our webinar series on Graphs and Graph Neural Networks.
Graph is a nonlinear data structure consisting of nodes and edges. Widely used in applications like Physical system interactions, Knowledge graphs, Molecular interactions, Transportation routes, Information extraction.
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Intro-to-Graphs.png)
Generative Models
- Automatically generating graphs from inputs will be useful for map building, relational extraction.
- Graph completion by the generative models will help in finding new links useful in knowledge graph completion, social networks.
- Generating new structures is vital for drug and material discovery
One can use pre trained generative models to create Graphs (along with the vertices and the edges) on the fly (Cycle generated during inference).
Deep Generative Models of Graphs (DGMG)
DGMG helps in structural generation that uses probability driven structure to sequentially add the nodes, edges and finally connect with the destination nodes.
![](https://www.cellstrat.com/wp-content/uploads/2020/08/DGMG.png)
Teacher Forcing :-
Teacher forcing is the technique where the target word is passed as the next input to the decoder.
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Teacher-Forcing.png)
Image credit : https://towardsdatascience.com/what-is-teacher-forcing-3da6217fed1c
DGMG: Optimization :-
For each graph, there exists a sequence of actions a1…aT that generates it. The Objective is to compute the joint probabilities of such action sequences and maximize them using teacher forcing
![](https://www.cellstrat.com/wp-content/uploads/2020/08/DGMG-Eq-1.png)
Maximum Likelihood Estimation (MLE) loss (also called -ve log likelihood) that acts as the optimization objective is as follows
![](https://www.cellstrat.com/wp-content/uploads/2020/08/DGMG-Eq-2.png)
DGMG Skeleton :-
![](https://www.cellstrat.com/wp-content/uploads/2020/08/DGMG-skeleton.png)
Initializations made in the DGMG class are as follows :-
![](https://www.cellstrat.com/wp-content/uploads/2020/08/DGMG-code.png)
Encoding a Dynamic Graph
All the actions generating a graph are sampled from probability distributions. In order to do that, you project the structured data, namely the graph, onto an Euclidean space. The challenge is that such process, called embedding, needs to be repeated as the graphs mutate.
Graph Embedding – An approach used to transform the nodes, edges and their features into vector space whilst maximally preserving properties like graph structure and information.
Graph Propagation – As new nodes and edges are added, the vector representation changes and this update is done with the help of graph propagation.
Graph Embedding :-
Let the Graph be represented as G=(V,E).
Each node v has an embedding vector hv. Similarly, the graph has an embedding vector hG.
Sigmoid(gm(hv)) computes a gating function and can be thought of as how much the overall graph embedding attends on each node.
fm maps the node embeddings to the space of graph embeddings.
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Graph-Embedding-eq.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Graph-Propagation-code.png)
Graph Propagation :-
For every node v in the graph, the neighboring nodes sends the message as follows
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Graph-Propagation-Eq-1.png)
where x(u,v) is the embedding of the edge between u and v.
V summarizes with a node activation vector after receiving message from its neighbors.
This information is used to update its own feature
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Graph-Propagation-Eq-2.png)
Graph Propagation and Prediction Process :-
Run T rounds of propagation to update node vectors, after which a graph representation vector is computed and output predicted.
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Graph-Propagation.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Graph-Propagation-code-1.png)
Sequential Graph Generation Process :-
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Sequential-Graph-Generation-Process.png)
Sampling from Probability Distribution :-
Distribution is the abstract base class for probability distributions, helpful in adding nodes and choosing destination for generative models by sampling.
Adding nodes: Bernoulli Distribution- Creates a Bernoulli distribution parameterized by probs or logits.
Choosing destination: Categorical Distribution- Creates a Categorical distribution parameterized by probs or logits similar to Bernoulli.
Here we see examples of how these distributions are invoked from Pytorch
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Bernoulli-Eq.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Categorial-Eq.png)
Adding Nodes :-
Given the graph embedding vector hG, the below equation is used to parametrize a bernoulli distribution for deciding whether to add a new node.
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Adding-Nodes-Eq-1-1.png)
If a new node is to be added, it is initialized as follows where hinit is a learnable embedding module for untyped nodes.
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Adding-Nodes-Eq-2.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Add-Node.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Add-Node-code.png)
Adding Edges :-
Given the graph embedding vector hG and node embedding vector hV, the below equation is used to parametrize a bernoulli distribution for deciding whether to add a new edge.
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Adding-Edges-Eq-1.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Adding-Edges.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Add-Edge.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Add-Edge-Code.png)
Choosing Destination :-
Newly added node with the edge finds the destination node to connect to
For each possible destination u∈{0,⋯,v−1}, the probability of choosing it is given by
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Choosing-Destination-Eq.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Choosing-Destination.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Choosing-Destination-2.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Choosing-Destination-code.png)
Synthetic Graphs
Synthetic graphs are graphs not collected from real life data but instead constructed using particular rules.
Barabasi Albert model is a Scale Free Model that incorporates growth and preferential attachment.
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Synthetic-Graphs-1.png)
Image credit : https://www.geeksforgeeks.org/barabasi-albert-graph-scale-free-models/
Generation of Synthetic Graphs :-
Model is being trained on three different set of graphs: cycles, trees and graphs generated by Barabasi-Albert model. Percentage of valid samples generated and the training curves for the dataset by the models DGMG and LSTM are shown below
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Synthetic-Graphs-table.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Synthetic-Graphs-2.png)
Grammar for Graphs
Graph Grammar associates vertices with a set of attributes and rewrites these attributes with help of functions.
Simplified Molecular-Input Line-Entry System (SMILES) is a specification in the form of a line notation for describing the structure of chemical species using short ASCII strings.
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Grammar-for-Graphs.png)
Molecular Generation :-
Model’s ability to generate molecules is also tested. It is trained on the Zinc dataset and the results are compared with another model GrammarVAE which uses SMILES grammar.
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Molecular-Generation.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Molecular-Generation-2.png)
Dataset for Generative Model :-
- Dataset is generated with input of the range of the vertices to be present and the number of samples to be created.
- Decision sequence is obtained for generating valid cycles with DGMG for teacher forcing optimization.
- CycleModelEvaluation helps to find whether vertices are in the range and whether it is a valid cycle.
- Adam optimizer is used. Loss is calculated with the log_prob and backpropagation is done.
Improving model and corresponding graphs generated :-
With more batches and epochs, models get better over time. It can be seen that the model creates better cycles as the training progresses
![](https://www.cellstrat.com/wp-content/uploads/2020/08/Improving-Model.gif)
Summary
- Deep Generative Model for Graphs (DGMG) is capable of generating arbitrary graphs through a sequential process.
- Sequential Process follows adding node, adding edge and choosing the destination iteratively.
- Graph Embedding and Propagation helps in encoding the graph dynamically when taking the actions.
- Applications like Synthetic Graphs and Molecular Generation benefit greatly from DGMG models as compared to the traditional RNN models.