The primary insight in the common traditional models is that we specify a generation process or probability model, which allows us to capture some useful property of real-world graphs while still being tractable and easy to analyze. Historically, these traditional generation models have been used in two key applications:
- Generating synthetic data
- Creating null models

Traditional Applications

Molecule generation is the task of generating diverse and novel molecules that has certain desirable chemical properties.

Molecule Generation

The Erdös-Rényi (ER) model is a traditional graph generation approach where the likelihood of an edge existing between any two distinct nodes is an independent, constant probability. This generation process is mathematically expressed as $$P(A[u,v]=1)=r, \forall u,v \in \mathcal{V}, u \neq v$$, where the parameter $$r \in [0,1]$$ represents the expected density of the graph.

Erdös-Rényi Model

The goal of graph generation is to build models that can generate realistic graph structures. In some ways, we can view this graph generation problem as the mirror image of the graph embedding problem. There are three common traditional graph generation approaches:
- Erdös-Rényi (ER) model
- Stochastic Block Model (SBM)
- Preferential Attachment (PA) model

University of Michigan - Ann Arbor

Graph Representation Learning is the application of machine learning techniques on graph-structured data. A few examples of growing topics in Graph Representation Learning include techniques for deep graph embeddings, Graph Neural Networks (GNNs), and applications to knowledge graphs.

Graph Representation Learning

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

Node embeddings is a way of graph representation. The goal of node embeddings is to map the nodes in the graph into a low-dimensional vector space, where the relations of the nodes in graph can be reflected by the geometric relations in the embedding space. Compared with hand-engineered features, node embeddings are more flexible and they are learned through learning processes.

Node Embeddings

Neighborhood overlap metrics between pairs of nodes are useful in helping us quantify the extent to which a pair of nodes are related, which is import in tasks such as predicting the existence of an edge between two nodes.

Neighborhood Overlap Detection

By examining the eigenvectors of graph Laplacian, the nodes can be clustered into K groups. The steps are as follows:
1. Find the smallest K eigenvectors of the graph Laplacian (excluding the smallest one).
2. Let U be the matrix whose columns are the K eigenvectors, then represent each node $v$ as its corresponding row $z_v$ in U.
3. Run K-means clustering on the embeddings $z_v, \forall v\in V$

K-Clustering of Graph Nodes

Graph is a general data structure  to represent complex data in complex systems. 
It is used to describe and analyze objects/entities with relations/interactions.
A graph is a collection of nodes( objects ) and edges (interactions)


Graph Data structure

Machine learning is inherently a problem-driven discipline, where we seek to build models that can learn from data in order to solve particular tasks. Machine learning on graphs is no different, except the usual categories of supervised and unsupervised are not necessarily the most informative or useful when it comes to graphs.

Machine Learning on Graphs

Traditional approaches to classification using graph data follow the standard machine learning paradigm, where we begin by extracting some statistics or features — based on heuristic functions or domain knowledge — and then use these features as input to a standard machine learning classifier.

Graph Statistics and Kernel Methods

GNNs are a general framework for defining deep neural networks on graph data. The goal of GNNs is to generate representations of nodes that actually depend on the structure of the graph, as well as any feature information available.

Graph Neural Networks (GNNs)

Deep generative models aim to design models that can observe a set of graphs {G1, ..., Gn} and learn to generate graphs with similar characteristics as this training set. These approaches avoid hand-coding particular properties—such as community structure or degree distributions.

Deep Generative Models

There are two concrete instantiations of the autoregressive generation
idea: in the first model called GraphRNN, we model autoregressive dependencies using a recurrent neural network (RNN); In the second approach called graph recurrent attention network (GRAN), we generate graphs by using a GNN to condition on the adjacency matrix that has been generated so far.

Recurrent Models for Graph Generation

Traditional Graph Generation

There are many important sub-area in graph representation learning. However, the author believe that there’re two key areas that have the potential of pushing fundamentals of graph representation learning forward:

1)	Latent graph inference

2)	Breaking the bottleneck of message passing


Learn Before

Related

Learn After