Graph convolutional network

Graph convolutional networks (GCNs) are a type of graph neural network architecture. They extend the idea of traditional convolutional neural networks to graphs.

GCN layers can be described by:

$$H=\sigma (D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}XW)$$

where:

• $H$ is the layer output node feature matrix.
• $\sigma$ is the non-linear activation function.
• $A$ is the graph adjacency matrix with the identity added to it: $A=A+I$.
• $X$ is the node feature matrix.
• $D$ is a diagonal matrix.

We add the identity to the adjacency matrix to add self-loops (so that we sum the feature vectors of all neighbouring nodes and the node itself). We also symmetrically normalise $A$ with the diagonal matrices $D$ such that all rows sum to 1: $D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}$.

GCN layers update the node embeddings based on the features of the immediate neighbours, but we can influence the embeddings from further away by stacking GCN layers. This is roughly analogous to increasing the receptive field in CNNs.

The benefit of GCNs is that they’re interpretable (wrt local graph structure) and computationally efficient. However, they’re largely limited to the local structure.

See also

• Graph attention network