Latent graph inference is the task of infering graph or relational relations from unstructured or semi-structured data. It’s potentially very useful because it allows us to use GNN type of methods on data even without graph structure input. There has been initial work in this area, and current findings suggest that it can improve model performance even on data with graph relation input.

Latent Graph Inference

Message passing is a fundamental paradigm in current GNN and graph representation learning. However, it has several drawbacks. Theoretically, the power of message passing is bounded by Weisfeiler-Lehman (WL) isomorphism test, is limited to simple convolution filters, and is restricted to tree-structured computation graphs. Empirically, researchers find that message passing suffer from over-smoothing, which is a result of neighbor aggregation. The author believe that there is deeper connections between these problems, and a new paradigm is needed to overcome the theoretical bottle neck.

Breaking The Bottleneck Of Message Passing

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


University of Notre Dame

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

The neighborhood aggregation operation is fundamentally a set function. Given a set of neighbor embeddings $\{h_{v}, \forall v \in N(u)\}$, there is no natural ordering of a nodes’ neighbors, and any aggregation function we define must thus be permutation invariant.

Generalized neighborhood aggregation: Set aggregators

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)

One prominent example of alternative theoretical motivations for the GNN framework is the motivation of GNNs based on connections to variational inference in probabilistic graphical models (PGMs).

In this probabilistic perspective, we view the embeddings $z_{u}, \forall u \in V$ for
each node as latent variables that we attempt to infer. Assume that we observe the graph structure and the input node features X, and the goal is to infer the underlying latent variables hat can explain this observed data. Then the message passing operation that underlies GNNs can be viewed as a neural network analogue of certain message passing algorithms that are commonly used for variational inference to infer distributions over latent variables.

Probabilistic Graphical Models (PGM)

Many recent generative models leverage alternative generative frameworks, and among them generative adversarial networks (GANs) are one of the most popular. 

The basic idea behind a general GAN-based generative models is: first define a trainable network $g_{\theta}: R^{d}\rightarrow \chi$. This generator network is trained to generate realistic data samples $\tilde{x} \in \chi$ by taking a random seed $z \in R^{d}$ as input. 

At the same time, define a discriminator network $d_{\phi}: \chi \rightarrow [0,1]$. The
goal of it is to distinguish between real data samples $x \in \chi$ and samples generated by the generator $\tilde{x} \in \chi$.

Adversarial Approaches: Generative adversarial networks (GANs)

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

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

Learn Before

Related

Learn After