Loading
How a neural network learns from a graph. The course starts with graphs as matrices, then covers the graph convolution, the general message passing pattern, sampling and attention over neighbours, pooling a whole graph into one vector, and the random walk behind PageRank.
01
A graph with n nodes is an n by n adjacency matrix, or a list of edges. Degrees, self loops and normalisation are all simple operations on that matrix.
02
A GCN layer averages each node's features with its neighbours' through the normalised adjacency, then applies shared weights. Two layers are often enough to label nodes from a few examples.
03
Most GNN layers make a message along each edge, combine the messages at each node, and update the node. In code this is a gather of source rows and a scatter add into the targets.
04
GraphSAGE keeps a node's own vector apart from the mean of its neighbours and joins the two. It learns a function of the neighbourhood, so it works on nodes and graphs it did not see in training.
Practise it
05
A graph attention layer learns a weight for each neighbour from the two nodes' features, with a softmax over the neighbourhood. Important neighbours then count for more than others.
Practise it
06
To label a whole graph, pool its node vectors into one vector. Sum pooling can count, so it can tell apart graphs that mean and max pooling cannot, and many small graphs train together as one disconnected graph.
07
PageRank scores a node by how often a random walker visits it, with a small chance to jump anywhere. The scores are the stationary distribution of a Markov chain, found by power iteration.
Practise it