Graph Neural Networks- Architectures review!

In short: a walk through the graph neural networks I found most useful. GCN, DeepWalk and GraphSAGE, starting from the three matrices you need before any of it makes sense.

If a problem can be drawn as a graph, a graph neural network is often the accurate and efficient way to answer it. I start with the simple models and work up to the newer ones. ChebNet gets its own post.

The vocabulary you need first

I am mostly following Kipf and Welling on semi-supervised classification with GCNs [1]. I plotted the example graph with GraphOnline.

G = (v, e)

That is, a graph G is made of v nodes and e edges.

Three matrices do most of the work:

Those three are the key to graph-based processing. You can define others. The feature matrix holds the features of each node. If the nodes are people, the features might be age, height and weight. So it has n rows and f columns, where f is the number of features.

Graph Convolutional Network (GCN)

Think of the graph you just drew as layer one. What is layer two? You apply some math to the matrices, and the math runs on the node features. So you have a function F, adjacency A, and features X. Define H^l for the values at each layer.

In math:

F can be anything. I use ReLU. You also need a matrix W to carry the layer-specific trainable weights.

In a GCN, each node ends up as the aggregation of its neighbours. This is where semi-supervised learning comes in. In a graph you often do not have a label for every node, so you use the labelled ones to predict the rest. In fully supervised learning you have all the labels. Here you do not, hence semi-supervised.

I is the identity matrix, which is what lets you normalize A. D hat is the diagonal degree matrix of A hat. That gives the final equation:

DeepWalk

My reference here is "DeepWalk: Online Learning of Social Representations" by Perozzi et al., who demonstrate it on Zachary's Karate network [2]. This one learns unsupervised, so there may be no feature matrix at all. The algorithm starts from random features and develops them each iteration.

The problem they were solving: cluster the members of a karate club.

They separated labels from features to prevent cascading errors. You learn from a subset of the data, and RandomWalk plus SkipGram get you the rest of the way. In RandomWalk, at each node you pick a walk size and a walk length.

GraphSAGE

GraphSAGE is the practical one. With the earlier networks, growing the graph means retraining the model. GraphSAGE makes that easy [3].

1. Sample the neighbourhoodPick which neighbours of a node you are going to look at.
2. AggregateCombine the feature information coming from those neighbours.
3. PredictProduce the graph context and the label.

Time to define embedding, which is not a strange thing at all. It is a calculation on node features. Picture a graph of three nodes in a triangle. To get the new value for node 0, you feed its neighbours' values into a function. Averaging, for example.

First assign random values to each node. Here are the random numbers I gave the example graph:

Take node 2. Capture its neighbours and apply the function. Nodes 0, 3 and 4 are the input, so 0.8, 0.6 and 0.7 go in and the output is the new value of node 2.

Repeat for every node and you have layer one. Do it again for layer two.

Which function should you use? Anything, even a small neural network. Mostly people average:

Or take the maximum, which picks 0.8 in this example. That is the pool aggregator. And note this was one-hop embedding. In two-hop you pull in the neighbours of the neighbours as well.

Next

In the next posts I will cover the networks used in graph signal processing (GSP).

References

1. arxiv.org/abs/1609.02907
2. arxiv.org/abs/1403.6652
3. snap.stanford.edu/graphsage