This approach is based on the theory of permutation invariant neural networks. For example, an aggregation function with the following form is a universal set function approximator:

$$m_{N(u)}=MLP_{\theta}(\sum_{v\in N(u)}MLP_{\phi}(h_{v}))$$
Any permutation-invariant function that maps a set of embeddings to a single embedding can be approximated to an arbitrary accuracy by a model following this equation.

Set pooling approaches based on the above equation often lead to small increases in performance, though they also introduce an increased risk of overfitting, depending on the depth of the MLPs used. 

If set pooling is used, it is common to use MLPs that have only a single hidden layer, since these models are sufficient to satisfy the theory, but are not so over parameterized so as to risk catastrophic overfitting.

Set Aggregators: Set pooling

This approach is more powerful than simply taking a sum or mean of the neighbor embeddings. Instead of using a permutation-invariant reduction (e.g., a sum or mean), Janossy pooling applies a permutation-sensitive function and average the result over many possible permutations.

Let $\pi _{i} \in \Pi$ denote a permutation function that maps the set $\{ h_{v}, \forall v \in N(u) \}$ to a specific sequence $(h_{v1}, h_{v2}, ..., h_{v|N(u)|})_{\pi _{i}}$. The Janossy pooling approach then performs neighborhood aggregation by
$$m_{N(u)}=MLP_{\theta}(\frac{1}{|\Pi|} \sum_{\pi \in \Pi}\rho_{\phi}) (h_{v1}, h_{v2}, ..., h_{v||N(u)})_{\pi _{i}}$$, 

where $\Pi$ denotes a set of permutations and ρφ is a permutation-sensitive function.

Set Aggregators: Janossy pooling

In addition to more general forms of set aggregation, a popular strategy for improving the aggregation layer in GNNs is to apply attention. 

The basic idea is to assign an attention weight or importance to each neighbor, which is used to weigh this neighbor’s influence during the aggregation step. The first GNN model to apply this style of attention was Graph Attention Network (GAT), which uses attention weights to define a weighted sum of the neighbors:
$$m_{N(u)}=\sum _{v \in N(u)} \alpha _{u,v} h_{v}$$,
where $\alpha _{u,v}$ denotes the attention on neighbor $v \in N(u)$ when we are aggregating information at node u.

Neighborhood Attention

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.

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

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

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