Graph neural network

In addition to the graph representation, the input also includes known chemical properties for each of the atoms.

The task is to predict the efficacy of a given molecule for a specific medical application, like eliminating E. coli bacteria.

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,[2][3][9][10][11] which implement different flavors of message passing,[12][13] started by recursive[2] or convolutional constructive[3] approaches.

[14] In the more general subject of "geometric deep learning", certain existing neural network architectures can be interpreted as GNNs operating on suitably defined graphs.

Relevant application domains for GNNs include natural language processing,[15] social networks,[16] citation networks,[17] molecular biology,[18] chemistry,[19][20] physics[21] and NP-hard combinatorial optimization problems.

[22] Open source libraries implementing GNNs include PyTorch Geometric[23] (PyTorch), TensorFlow GNN[24] (TensorFlow), Deep Graph Library[25] (framework agnostic), jraph[26] (Google JAX), and GraphNeuralNetworks.jl[27]/GeometricFlux.jl[28] (Julia, Flux).

The architecture of a generic GNN implements the following fundamental layers:[12] It has been demonstrated that GNNs cannot be more expressive than the Weisfeiler–Leman Graph Isomorphism Test.

[34][35][13] As of 2022[update], whether or not future architectures will overcome the message passing primitive is an open research question.

is a permutation invariant aggregation operator that can accept an arbitrary number of inputs (e.g., element-wise sum, mean, or max).

Intuitively, in an MPNN computational block, graph nodes update their representations by aggregating the messages received from their neighbours.

Graph nodes in an MPNN update their representation aggregating information from their immediate neighbours.

Oversquashing refers to the bottleneck that is created by squeezing long-range dependencies into fixed-size representations.

Countermeasures such as skip connections[10][38] (as in residual neural networks), gated update rules[39] and jumping knowledge[40] can mitigate oversmoothing.

The graph convolutional network (GCN) was first introduced by Thomas Kipf and Max Welling in 2017.

[9] 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 graph attention network (GAT) was introduced by Petar Veličković et al. in 2018.

For the final GAT layer, the outputs from each attention head are averaged before the application of the activation function.

[11] 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

The gated graph sequence neural network (GGS-NN) was introduced by Yujia Li et al. in 2015.

The message passing framework is implemented as an update rule to a gated recurrent unit (GRU) cell.

In other words, the nodes with the top-k highest projection scores are retained in the new adjacency matrix

Homophily principle, i.e., nodes with the same labels or similar attributes are more likely to be connected, has been commonly believed to be the main reason for the superiority of Graph Neural Networks (GNNs) over traditional Neural Networks (NNs) on graph-structured data, especially on node-level tasks.

[41] However, recent work has identified a non-trivial set of datasets where GNN’s performance compared to the NN’s is not satisfactory.

In the past few years, considerable effort has been devoted to studying and addressing the heterophily issue in graph learning.

[41][43][44] 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.

[48] Examples include computing shortest paths or Eulerian circuits for a given graph,[39] deriving chip placements superior or competitive to handcrafted human solutions,[49] and improving expert-designed branching rules in branch and bound.

[50] When viewed as a graph, a network of computers can be analyzed with GNNs for anomaly detection.

Water distribution systems can be modelled as graphs, being then a straightforward application of GNN.