Graph neural network

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

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:

${\displaystyle \mathbf {H} =\sigma \left({\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}\mathbf {X} \mathbf {\Theta } \right)}$

where ${\displaystyle \mathbf {H} }$ is the matrix of node representations ${\displaystyle \mathbf {h} _{u}}$, ${\displaystyle \mathbf {X} }$ is the matrix of node features ${\displaystyle \mathbf {x} _{u}}$, ${\displaystyle \sigma (\cdot )}$ is an activation function (e.g., ReLU), ${\displaystyle {\tilde {\mathbf {A} }}}$ is the graph adjacency matrix with the addition of self-loops, ${\displaystyle {\tilde {\mathbf {D} }}}$ is the graph degree matrix with the addition of self-loops, and ${\displaystyle \mathbf {\Theta } }$ is a matrix of trainable parameters.

In particular, let ${\displaystyle \mathbf {A} }$ be the graph adjacency matrix: then, one can define ${\displaystyle {\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {I} }$ and ${\displaystyle {\tilde {\mathbf {D} }}_{ii}=\sum _{j\in V}{\tilde {A}}_{ij}}$, where ${\displaystyle \mathbf {I} }$ denotes the identity matrix. This normalization ensures that the eigenvalues of ${\displaystyle {\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}}$ are bounded in the range ${\displaystyle [0,1]}$, avoiding numerical instabilities and exploding/vanishing gradients.

A limitation of GCNs is that they do not allow multidimensional edge features ${\displaystyle \mathbf {e} _{uv}}$.[7] It is however possible to associate scalar weights ${\displaystyle w_{uv}}$ to each edge by imposing ${\displaystyle A_{uv}=w_{uv}}$, i.e., by setting each nonzero entry in the adjacency matrix equal to the weight of the corresponding edge.

The graph attention network (GAT) was introduced by Petar Veličković et al. in 2018.[9]

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:

${\displaystyle \mathbf {h} _{u}={\overset {K}{\underset {k=1}{\Big \Vert }}}\sigma \left(\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)}$

where ${\displaystyle K}$ is the number of attention heads, ${\displaystyle {\Big \Vert }}$ denotes vector concatenation, ${\displaystyle \sigma (\cdot )}$ is an activation function (e.g., ReLU), ${\displaystyle \alpha _{ij}}$ are attention coefficients, and ${\displaystyle W^{k}}$ is a matrix of trainable parameters for the ${\displaystyle k}$-th attention head.

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:

${\displaystyle \mathbf {h} _{u}=\sigma \left({\frac {1}{K}}\sum _{k=1}^{K}\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)}$

Attention in Machine Learning is a technique that mimics cognitive attention. In the context of learning on graphs, the attention coefficient ${\displaystyle \alpha _{uv}}$ measures how important is node ${\displaystyle u\in V}$ to node ${\displaystyle v\in V}$.

Normalized attention coefficients are computed as follows:

${\displaystyle \alpha _{uv}={\frac {\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {h} _{u}\Vert \mathbf {W} \mathbf {h} _{v}\Vert \mathbf {e} _{uv}]\right))}{\sum _{z\in N_{u}}\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {h} _{u}\Vert \mathbf {W} \mathbf {h} _{z}\Vert \mathbf {e} _{uz}]\right))}}}$

where ${\displaystyle \mathbf {a} }$ is a vector of learnable weights, ${\displaystyle \cdot ^{T}}$ indicates transposition, and ${\displaystyle {\text{LeakyReLU}}}$ is a modified ReLU activation function. Attention coefficients are normalized to make them easily comparable across different nodes.[9]

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 ${\displaystyle w_{uv}}$.

The gated graph sequence neural network (GGS-NN) was introduced by Yujia Li et al. in 2015.[32] The GGS-NN extends the GNN formulation by Scarselli et al.[2] 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:

${\displaystyle \mathbf {h} _{u}^{(0)}=\mathbf {x} _{u}\,\Vert \,\mathbf {0} }$

${\displaystyle \mathbf {m} _{u}^{(l+1)}=\sum _{v\in N_{u}}\mathbf {\Theta } \mathbf {h} _{v}}$

${\displaystyle \mathbf {h} _{u}^{(l+1)}={\text{GRU}}(\mathbf {m} _{u}^{(l+1)},\mathbf {h} _{u}^{(l)})}$

where ${\displaystyle \Vert }$ denotes vector concatenation, ${\displaystyle \mathbf {0} }$ is a vector of zeros, ${\displaystyle \mathbf {\Theta } }$ is a matrix of learnable parameters, ${\displaystyle {\text{GRU}}}$ is a GRU cell, and ${\displaystyle l}$ denotes the sequence index. In a GGS-NN, the node representations are regarded as the hidden states of a GRU cell. The initial node features ${\displaystyle \mathbf {x} _{u}^{(0)}}$ are zero-padded up to the hidden state dimension of the GRU cell. The same GRU cell is used for updating representations for each node.

We first set

${\displaystyle \mathbf {y} ={\frac {\mathbf {X} \mathbf {p} }{\Vert \mathbf {p} \Vert }}}$

where ${\displaystyle \mathbf {p} }$ is a learnable projection vector. The projection vector ${\displaystyle \mathbf {p} }$ computes a scalar projection value for each graph node.

The top-k pooling layer [22] can then be formalised as follows:

${\displaystyle \mathbf {X} '=(\mathbf {X} \odot {\text{sigmoid}}(\mathbf {y} ))_{\mathbf {i} }}$

${\displaystyle \mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }}$

where ${\displaystyle \mathbf {i} ={\text{top}}_{k}(\mathbf {y} )}$ is the subset of nodes with the top-k highest projection scores, ${\displaystyle \odot }$ denotes element-wise matrix multiplication, and ${\displaystyle {\text{sigmoid}}(\cdot )}$ is the sigmoid function. In other words, the nodes with the top-k highest projection scores are retained in the new adjacency matrix ${\displaystyle \mathbf {A} '}$. The ${\displaystyle {\text{sigmoid}}(\cdot )}$ operation makes the projection vector ${\displaystyle \mathbf {p} }$ trainable by backpropagation, which otherwise would produce discrete outputs.[22]

We first set

${\displaystyle \mathbf {y} ={\text{GNN}}(\mathbf {X} ,\mathbf {A} )}$

where ${\displaystyle {\text{GNN}}}$ is a generic permutation equivariant GNN layer (e.g., GCN, GAT, MPNN).

The Self-attention pooling layer[23] can then be formalised as follows:

${\displaystyle \mathbf {X} '=(\mathbf {X} \odot \mathbf {y} )_{\mathbf {i} }}$

${\displaystyle \mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }}$

where ${\displaystyle \mathbf {i} ={\text{top}}_{k}(\mathbf {y} )}$ is the subset of nodes with the top-k highest projection scores, ${\displaystyle \odot }$ denotes element-wise matrix multiplication.

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.

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.[34][35][33]

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.[36][12]

GNNs are used as fundamental building blocks for several combinatorial optimization algorithms.[37] Examples include computing shortest paths or Eulerian circuits for a given graph,[32] deriving chip placements superior or competitive to handcrafted human solutions,[38] and improving expert-designed branching rules in branch and bound.[39]

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[40] and within paths[41] to detect malicious processes, or on the edge level[42] to detect lateral movement.