A graph neural network (GNN) belongs to a class of artificial neural networks for processing data that can be represented as graphs.
In the more general subject of "geometric deep learning", certain existing neural network architectures can be interpreted as GNNs operating on suitably defined graphs. A convolutional neural network layer, in the context of computer vision, can be considered a GNN applied to graphs whose nodes are pixels and only adjacent pixels are connected by edges in the graph. A transformer layer, in natural language processing, can be considered a GNN applied to complete graphs whose nodes are words or tokens in a passage of natural language text.
The key design element of GNNs is the use of pairwise message passing, such that graph nodes iteratively update their representations by exchanging information with their neighbors. Several GNN architectures have been proposed, which implement different flavors of message passing, started by recursive or convolutional constructive approaches., it is an open question whether it is possible to define GNN architectures "going beyond" message passing, or instead every GNN can be built on message passing over suitably defined graphs.
Relevant application domains for GNNs include natural language processing, social networks, citation networks, molecular biology,[1] chemistry,[2] physics and NP-hard combinatorial optimization problems.
Open source libraries implementing GNNs include PyTorch Geometric (PyTorch), TensorFlow GNN (TensorFlow), Deep Graph Library[3] (framework agnostic), jraph (Google JAX), and GraphNeuralNetworks.jl/GeometricFlux.jl (Julia, Flux).
The architecture of a generic GNN implements the following fundamental layers:
It has been demonstrated that GNNs cannot be more expressive than the Weisfeiler–Leman Graph Isomorphism Test. In practice, this means that there exist different graph structures (e.g., molecules with the same atoms but different bonds) that cannot be distinguished by GNNs. More powerful GNNs operating on higher-dimension geometries such as simplicial complexes can be designed., whether or not future architectures will overcome the message passing primitive is an open research question.
Message passing layers are permutation-equivariant layers mapping a graph into an updated representation of the same graph. Formally, they can be expressed as message passing neural networks (MPNNs).
Let
G=(V,E)
V
E
Nu
u\inV
xu
u\inV
euv
(u,v)\inE
hu=\phi\left(xu,
| oplus | |
| v\inNu |
\psi(xu,xv,euv)\right)
where
\phi
\psi
oplus
\phi
\psi
The outputs of one or more MPNN layers are node representations
hu
u\inV
Graph nodes in an MPNN update their representation aggregating information from their immediate neighbours. As such, stacking
n
n
Other "flavours" of MPNN have been developed in the literature, such as graph convolutional networks and graph attention networks, whose definitions can be expressed in terms of the MPNN formalism.
The graph convolutional network (GCN) was first introduced by Thomas Kipf and Max Welling in 2017.
A GCN layer defines a first-order approximation of a localized spectral filter on graphs. GCNs can be understood as a generalization of convolutional neural networks to graph-structured data.
The formal expression of a GCN layer reads as follows:
H=\sigma\left(\tilde{D
where
H
hu
X
xu
\sigma( ⋅ )
\tilde{A
\tilde{D
\Theta
In particular, let
A
\tilde{A
\tilde{D
I
\tilde{D
[0,1]
A limitation of GCNs is that they do not allow multidimensional edge features
euv
wuv
Auv=wuv
The graph attention network (GAT) was introduced by Petar Veličković et al. in 2018.
Graph attention network is a combination of a graph neural network and an attention layer.The implementation of attention layer in graphical neural networks helps provide attention or focus to the important information from the data instead of focusing on the whole data.
A multi-head GAT layer can be expressed as follows:
hu=\overset{K}{\underset{k=1}{\Vert}}\sigma
| \left(\sum | |
| v\inNu |
\alphauvWkxv\right)
where
K
\Vert
\sigma( ⋅ )
\alphaij
Wk
k
For the final GAT layer, the outputs from each attention head are averaged before the application of the activation function. Formally, the final GAT layer can be written as:
hu=\sigma\left(
| 1 | |
| K |
| K | |
| \sum | |
| k=1 |
| \sum | |
| v\inNu |
\alphauvWkxv\right)
Attention in Machine Learning is a technique that mimics cognitive attention. In the context of learning on graphs, the attention coefficient
\alphauv
u\inV
v\inV
Normalized attention coefficients are computed as follows:
\alphauv=
| \exp(LeakyReLU\left(aT[Wxu\VertWxv\Verteuv]\right)) | ||||||
|
where
a
⋅ T
euv
LeakyReLU
A GCN can be seen as a special case of a GAT where attention coefficients are not learnable, but fixed and equal to the edge weights
wuv
The gated graph sequence neural network (GGS-NN) was introduced by Yujia Li et al. in 2015. The GGS-NN extends the GNN formulation by Scarselli et al. to output sequences. The message passing framework is implemented as an update rule to a gated recurrent unit (GRU) cell.
A GGS-NN can be expressed as follows:
| (0) | |
| h | |
| u |
=xu\Vert0
| (l+1) | |
| m | |
| u |
=
| \sum | |
| v\inNu |
\Thetahv
| (l+1) | |
| h | |
| u |
=
| (l+1) | |
| GRU(m | |
| u |
,
| (l) | |
| h | |
| u |
)
where
\Vert
0
\Theta
GRU
l
| (0) | |
| x | |
| u |
Local pooling layers coarsen the graph via downsampling. We present here several learnable local pooling strategies that have been proposed. For each case, the input is the initial graph is represented by a matrix
X
A
X'
A'
We first set
y=
| Xp | |
| \Vertp\Vert |
where
p
p
The top-k pooling layer can then be formalised as follows:
X'=(X\odotsigmoid(y))i
A'=Ai,
where
i=topk(y)
\odot
sigmoid( ⋅ )
A'
sigmoid( ⋅ )
p
We first set
y=GNN(X,A)
GNN
The Self-attention pooling layer can then be formalised as follows:
X'=(X\odoty)i
A'=Ai,
where
i=topk(y)
\odot
The self-attention pooling layer can be seen as an extension of the top-k pooling layer. Differently from top-k pooling, the self-attention scores computed in self-attention pooling account both for the graph features and the graph topology.
See also: AlphaFold.
Graph neural networks are one of the main building blocks of AlphaFold, an artificial intelligence program developed by Google's DeepMind for solving the protein folding problem in biology. AlphaFold achieved first place in several CASP competitions.
See also: Recommender system. Social networks are a major application domain for GNNs due to their natural representation as social graphs. GNNs are used to develop recommender systems based on both social relations and item relations.
See also: Combinatorial optimization. GNNs are used as fundamental building blocks for several combinatorial optimization algorithms. Examples include computing shortest paths or Eulerian circuits for a given graph, deriving chip placements superior or competitive to handcrafted human solutions, and improving expert-designed branching rules in branch and bound.
See also: Intrusion detection system. When viewed as a graph, a network of computers can be analyzed with GNNs for anomaly detection. Anomalies within provenance graphs often correlate to malicious activity within the network. GNNs have been used to identify these anomalies on individual nodes[4] and within paths[5] to detect malicious processes, or on the edge level[6] to detect lateral movement.
See also: Water distribution system.
Water distribution systems can be modelled as graphs, being then a straightforward application of GNN. This kind of algorithm has been applied to water demand forecasting,[7] interconnecting District Measuring Areas to improve the forecasting capacity. Other application of this algorithm on water distribution modelling is the development of metamodels.[8]