Given an input graph $G = (V,E)$ and a set of node features **X** $\in \mathbb{R}^{d*|V|}$, our goal is to produce a node embedding $z_u$, for all nodes in the graph.

Formal Definition of GNN

One of the defining features of a GNN is that it uses a form of *neural message passing* in which vector messages are exchanged between nodes and updated using neural networks

Neural Message Passing

In the context of GNNs, many of the standard regularization approaches are known to work well, including L2 regularization, dropout, and layer normalization. However, there are also regularization strategies that are somewhat specific to the GNN setting.

Regularization in GNN

GNNs had been independently developed from several distinct theoretical motivations and perspectives:
- Graph convolutions: the theory of graph signal processing, as a generalization of Euclidean convolutions to the non-Euclidean graph domain.
- Probabilistic graphical models: neural message passing approaches proposed by analogy to message passing algorithms for probabilistic inference in graphical models.
- Graph isomorphism: connection to the Weisfeiler-Lehman graph isomorphism
test.

Theoretical Motivations of GNNs

Original node-level message passing mechanism can be time-consuming.

Efficiency Concerns of GNNs

 $\mathcal{L} = \sum_{ \mathcal{G}_i \in \mathcal{T} } \| MLP( z_{\mathcal{G}_{i}} ) - y_{\mathcal{G}_{i}}  \|_{2}^{2}$

$z_{\mathcal{G}_{i}}$ is graph level embeddings

$\mathcal{T}  =  {\mathcal{G}_{1}, ..., \mathcal{G}_{n} }$ set of labeled training graphs

MLP ,densely connected feed forward neural network

$y_{\mathcal{G}_{i}  \in  {\rm I\!R} }$ is the target value for training graph $\mathcal{G}_{i}$


Definition of Loss in GNNs for Graph Classification

Pair wise node embedding loss function are deployed for applications utilizing graph relation prediction.

Loss function in GNNs for Relation Prediction

 - GNN pre-training approaches is an open and active area of research. 

 - Pretraining is an effective way   of injecting domain knowledge into a model before the actual training take place

 -  Pre-training a GNN using  neighborhood reconstruction loss  to reconstruct missing edges before a classification task does not improve the classification loss.

 -  A pre-training method called Deep Graph Infomax maximizes the mutual information between node embeddings $z_u$  and graph embeddings $ z_{\mathcal G}$.


Pretraining a GNN

The basic GNN can be derived as a neural network variation of the existing Weisfieler-Lehman (WL) isomorphism algorithm

GNNs and Graph Isomorphism

1. Given two graphs, we assign each node an initial label in each graph. 
2. We iteratively assign a new label to each node in each graph by hashing the multi-set of the current labels within the node’s neighborhood, as well as the node’s current label.
3. We repeat Step 2 until the labels for all nodes in both graphs converge.
4. Finally, we construct  multi-sets summarizing all the node labels in each graph, and we declare G1 and G2 to be isomorphic if and only if the multi-sets for both graphs are identical.

The Weisfieler-Lehman(WL) Algorithm

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.

Carleton College

Hamilton College

Neural relation extraction (NRE) models introduce neural networks to automatically extract semantic features from text. Compared with SRE models,
NRE methods can effectively capture textual information and generalize to wider range of data.

Neural Relation Extraction Models

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

Han, X. (n.d.). More Data, More Relations, More Context and More Openness:
A Review and Outlook for Relation Extraction *, Retrieved June 4, 2022, from https://arxiv.org/pdf/2004.03186.pdf

More Relations, More Context and More Openness:
A Review and Outlook for Relation Extraction

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

It learns compositional representations for sentences recursively.

Recursive Neural Networks

It can better handle long sequential data.

Recurrent Neural Networks (RNNs)

Graph Neural Networks (GNNs)

It utilizes attention mechanism to aggregate global relational information.

Attention-based Neural Networks

Different from SRE models, NRE mainly utilizes word embeddings and position embeddings instead of hand-craft features as inputs. Word embeddings are the most used input representations in NLP, which encode the semantic meaning of
words into vectors.

Word Embeddings

In order to capture the entity information in text, position embeddings are introduced to specify the relative distances between words and entities.

Position Embeddings

Convolutional networks, also known as convolutional neural networks, or CNNs, are a specialized kind of neural network for processing data that has a known grid-like topology. Examples include time-series data, which can be thought of as a 1-D grid taking samples at regular time intervals, and image data, which can be thought of as a 2-D grid of pixels. 

The network employs a mathematical operation called convolution. Convolution is a specialized kind of linear operation. Convolutional networks are simply neural networks that use convolution in place of general matrix multiplication in at least one of their layers.

The CNN gets its power from the following concepts:
- Sparse connectivity
- Parameter sharing

Convolutional Neural Network (CNN)

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

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