Thread by @simocristea

Graph Neural Networks (#GNNs) & their applications to life sciences are an exciting #DeepLearning area to discover!

But, to develop or apply GNN methods, we first need to understand the maths behind.

So, back to basics!

Here's a plain language summary of what's behind GNNs👇

This summary is based on @PetarV_93’s recent paper with introductory theoretical notions on Graph Neural Networks.

This resource is very much an introductory one.

arxiv.org/abs/2301.08210

If you are already familiar with Graph Neural Networks, but still want to better understand the maths behind in a formalized logical framework, I recommend the following book/paper by @mmbronstein @joanbruna @TacoCohen @PetarV_93

arxiv.org/abs/2104.13478

-- The basics --

A graph consists of nodes & edges connecting pairs of nodes.

The connectivity of the graph is encoded in its adjacency matrix.

Each node is attached some characteristics, i.e. a feature vector.

Tasks that GNNs can achieve:

1. Node classification: predict the class of nodes in a graph, e.g. classifying protein function in a protein interaction graph

2. Graph classification: predict a single label for the graph, e.g. drug screening (yes/no per drug represented as graph)

3. Edge prediction: predict edge properties, e.g. drug repurposing, find whether novel edges between drugs and diseases exist in a graph.

All these tasks involve different formulations of mathematical optimization problems defined over the elements and structure of the graph👇

-- Notations 1 --

V - vertices: elements called u
E - edges
A - adjacency matrix: square, with size the number of nodes
x_u - feature vector: information for each node u
X - feature matrix: stacking feature vectors for all nodes [x1,...xV]^T

-- Notations 2 --

N_u - neighborhood nodes: set of neighboring nodes for each node u
X_N_u - neighborhood features: set of feature vectors for all neighboring nodes
h_u - local function, takes into account the neighborhood

h_u = \theta(x_u, X_N_u)

-- Message passing --

Have you heard of "message passing" for Graph Neural Networks but didn't know what it was?

Here you do: \theta is also known as "propagation" or "message passing"

The are three main types of \theta, with equation 10 the message passing one.

1. For each node: a "message" value is computed by applying a (neural network) function for all its neighbors in its neighborhood N_u

2. The values computed at 1. (as many values as neighbors) are then aggregated by e.g. sum (adding up all values), average (averaging) or maximum

3. Then the (neural network) function \theta is applied over the value(s) resulting from 2. & the node's own feature vector.

Don't forget that the above 1-2-3 sequence is computed for every node! These values are then used directly as e.g. input to a node classification problem.

-- Transformers --

What happens if we don't know the real connectivity of the graph, i.e. we don't have A?

Let's assume an extreme case: the graph is in fact fully connected, i.e. A is full of 1.

Then, attentional GNNs (eq 9 above) reduces to the forward pass of a Transformer!

This makes sense, as Transformers model the interactions among words in a sentence. These interactions start off with a complete graph (everything can be related to everything), and are iteratively improved to only keep the relevant links.

More in-depth: graphdeeplearning.github.io/post/transform…

Almost everything in Biology can be thought of as a graph, therefore the potential of applying these techniques is huge.

Don't forget that AlphaFold2 (already cited 8,100 times) is also a Graph Neural Network!

nature.com/articles/s4158…

Fin 🧵