Graph neural network: Difference between revisions

Revision as of 14:44, 30 June 2022

Revision as of 14:49, 30 June 2022

Line 3:

A '''Graph neural network''' ('''GNN''') is a class of [[artificial neural network]]s for processing data that can be represented as [[Graph (abstract data type)|graphs]]<ref name="scarselli2008 /><ref name="sanchez2021" /><ref name="daigavane2021" />.

[[File:GNN building blocks.png|thumb|Basic building blocks of a Graph Neuralneural Networknetwork (GNN). <math>(1)</math> Permutation equivariant layer. <math>(2)</math> Local pooling layer. <math>(3)</math> Global pooling (or readout) layer. Colors indicate [[Feature (machine learning)|features]].]]

In the more general subject of "Geometric [[Deep Learning]]", existing neural network architectures can be interpreted as GNNs operating on suitably defined graphs<ref name=bronstein2021 />. [[Convolutional neural network]]s, in the context of [[computer vision]], can be seen as a GNN applied to graphs structured as grids of [[pixel]]s. [[Transformer (machine learning model) | Transformers]], in the context of [[natural language processing]], can be seen as GNNs applied to [[complete graph]]s whose nodes are [[words]] in a [[Sentence (linguistics) | sentence]].

Line 15:

[[NP-hard]] [[combinatorial optimization]] problems<ref name="li2018" />.

Several [[open source]] [[Library (computing)|libraries]] implementing Graph Neuralneural Networksnetwork are available, such as PyTorch Geometric <ref name=fey2019 /> ([[PyTorch]]), Tensorflow GNN<ref name=tfgnn2022 /> ([[Tensorflow]]), and jGraph<ref name=jraph2022/> ([[Google JAX]]).

== Architecture ==

The architecture of a generic GNN implements the following fundamental [[Layer (deep learning)|layers]]<ref name=bronstein2021 />:

* <em>Permutation Equivariantequivariant</em>: a permutation equivariant layer [[Map (mathematics)|maps]] a representation of a graph into an updated representation of the same graph. In literature, permutation equivariant layers are implemented via pairwise message passing between graph nodes<ref name=bronstein2021 /><ref name=velickovic2022 />. Intuitively, in a message passing layer, nodes ''<em>update''</em> their representations by ''<em>aggregating''</em> the ''<em>messages''</em> received from their immediate neighbours. As such, each message passing layer increases the receptive field of the GNN by one hop.

* <em>Local Poolingpooling</em>: a local pooling layer coarsens the graph via downsampling. Local pooling is used to increase the receptive field of a GNN, in a similar fashion to pooling layers in [[Convolutional neural network]]s. Examples include [[Nearest neighbor graph|k-nearest neighbours pooling]], top-k pooling<ref name=gao2019 />, and self-attention pooling<ref name=lee2019 />.

* <em>Global Poolingpooling</em>: a global pooling layer, also known as ''readout'' layer, provides fixed-size representation of the whole graph. The global pooling layer must be permutation invariant, such that permutations in the ordering of graph nodes and edges do not alter the final output<ref name=lui2022 />. Examples include element-wise sum, mean or maximum.

It has been demonstrated that GNNs cannot be more expressive than the Weisfeiler–Lehman Graph Isomorphism Test<ref name="douglas2011" /><ref name="xu2019" />. 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 complex|simplicial complexes]] can be designed<ref name=bronstein2021-2 />. {{As of|2022}}, whether or not future architectures will overcome the message passing primitive is an open research question<ref name=velickovic2022 />.

Line 30:

[[File:GNN representational limits.png|thumb|[[Graph isomorphism|Non-isomorphic]] graphs that cannot be distinguished by a GNN due to the limitations of the Weisfeiler-Lehman Graph Isomorphism Test. Colors indicate node [[Feature (machine learning)|features]].]]

== Message Passingpassing Layerslayers ==

[[File:Message Passing Neural Network.png|thumb|Node representation update in a Message Passing Neural Network (MPNN) layer. Node <math>\mathbf{x}_0</math> receives messages sent by all of his immediate neighbours <math>\mathbf{x}_1</math> to <math>\mathbf{x}_4</math>. Messages are computing via the message function <math>\phi</math>, which accounts for the features of both senders and receiver.]]

Message Passingpassing layers are permutation-equivariant layers mapping a graph into an updated representation of the same graph. Formally, they can be expressed as Messagemessage Passingpassing Neuralneural Networksnetworks (MPNNs)<ref name="bronstein2021" />.

Let <math>G = (V,E)</math> be a [[Graph (discrete mathematics)|graph]], where <math>V</math> is the node set and <math>E</math> is the edge set. Let <math>N_u</math> [[Neighbourhood (graph theory)|neighbourhood]] of node <math>u \in V</math>. Additionally, let <math>\mathbf{x}_u</math> be the [[Feature (machine learning)|features]] of node <math>u \in V</math>, and <math>\mathbf{e}_{u, v}</math> be the features of edge <math>(u, v) \in E</math>. An MPNN [[Layer_(deep learning)|layer]] can be expressed as follows<ref name="bronstein2021" />:

Line 47:

Other "flavours" of MPNN have been developed in the literature<ref name=bronstein2021 />, such as Graph Convolutional Networks<ref name=kipf2016 /> and Graph Attention Networks<ref name=velickovic2018 />, whose definitions can be expressed in terms of the MPNN formalism.

=== Graph Convolutionalconvolutional Networknetwork ===

The Graphgraph Convolutionalconvolutional Networknetwork (GCN) was first introduced by [[Thomas Kipf]] and [[Max Welling]] in 2017<ref name=kipf2016 />.

A GCN layer defines a [[Order of approximation|first-order approximation]] of a localized spectral [[Filter (signal processing)|filter]] on graphs. GCNs can be understood as a generalization of [[Convolutional Neural Network]]s to graph-structured data.

Line 63:

=== Graph Attention Network ===

The Graphgraph Attentionattention Networknetwork (GAT) was introduced by [[Petar Veličković]] et al. in 2018<ref name=velickovic2018 />.

A multi-head GAT layer can be expressed as follows:

Line 85:

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 <math>w_{uv}</math>.

== Local Poolingpooling Layerslayers ==

Local pooling layers coarsen the graph via downsampling. In literature, several learnable local pooling strategies have been proposed<ref name=lui2022 />.

=== Top-k Poolingpooling ===

The Toptop-k Poolingpooling layer <ref name=gao2019 /> can be formalised as follows:

:<math>\mathbf{y} = \frac{\mathbf{X}\mathbf{p}}{\Vert\mathbf{p}\Vert}</math>

Line 100:

Where <math>\mathbf{X}</math> is the matrix of node features, <math>\mathbf{A}</math> is the graph adjacency matrix, <math>\odot</math> denotes element-wise [[matrix multiplication]], and <math>\mathbf{p}</math> is a learnable [[Projection (mathematics)|projection]] vector. The projection vector <math>\mathbf{p}</math> computes a scalar projection value for each graph node. The nodes with the top-k highest projection scores are retained in the new adjacency matrix <math>\mathbf{A}'</math>. The <math>\text{sigmoid}(\cdot)</math> operation makes the projection vector <math>\mathbf{p}</math> trainable by [[backpropagation]], which otherwise would produce discrete outputs<ref name=gao2019 />.

=== Self-Attentionattention Poolingpooling ===

The Self-Attentionattention Poolingpooling layer <ref name=lee2019 /> can be formalised as follows:

:<math>\mathbf{y} = \text{GNN}(\mathbf{X}, \mathbf{A})</math>

Line 113:

Where <math>\mathbf{X}</math> is the matrix of node features, <math>\mathbf{A}</math> is the graph adjacency matrix, <math>\odot</math> denotes element-wise [[matrix multiplication]], and <math>\text{GNN}</math> is a generic permutation equivariant GNN layer (e.g., GCN, GAT, MPNN).

The Selfself-Attentionattention Poolingpooling layer can be seen as an extension of the Toptop-k Poolingpooling layer. Differently from Toptop-k Poolingpooling, the self-attention scores computed in Selfself-Attentionattention Poolingpooling account both for the graph features and the graph topology.

== Applications ==

=== Protein Foldingfolding ===

{{See Also|AlphaFold}}

Graph Neuralneural Networksnetworks 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<ref name=guardian2018 /><ref name=mit2020 />.

=== Social Networks ===

Line 126:

[[Social networks]] are a major application ___domain for GNNs due to their natural representation as [[social graph]]s. GNNs are used to develop recommender systems based on both [[social relations]] and item relations<ref name=fan2019 /><ref name=ying2018/>.

=== Combinatorial Optimizationoptimization ===

{{See Also|Combinatorial Optimization}}

GNNs are used as fundamental building blocks for several combinatorial optimization algorithm <ref name=cappart2021 />. Examples include computing superior or competitive [[Placement (electronic design automation)|chip placements]] with handcrafted human solutions<ref name=mirhoseini2021 />, and improving expert-designed bracing rules in [[Branch and Bound]]<ref name=gasse2019 />.