A Graph Convolutional Network Implementation.

Recently I gave a talk in the ScalaCon about Graph Convolutional Networks using Spark and AnalyticsZoo where I explained the available options to apply neural networks on top of graph structures.

Several techniques have arisen in the last years and one of the most famous is the Spectral Graph Convolutional Network (Thomas N. Kipf, Max Welling, Semi-Supervised Classification with Graph Convolutional Networks (ICLR 2017)) that explains how to implement spectral based convolutions without translating the graph representation into the Fourier Domain. This paper, along with other publications, describes how powerful these algorithms, which mix neural networks and graph theory, can be. There are many resources related to this topic and awesome posts like this.

To see the effect of the localized first-order approximation of spectral graph convolutions I took the data from the Cora Dataset (you can see a description of this dataset here) and implemented two experiments:

1. Using as propagation function the Renormalization Trick :

Renormalization Trick Eq.

2. Using no propagation function. So the resulting model is a Multilayer Perceptron model:

Multilayer Perceptron Eq.

• Â is the graph´s adjacency matrix. Note that the nodes self connections are added to this matrix: Â =A+I.
• D̂ is the degree matrix of Â.
• X corresponds to the output of the previous layer.
• Θ as the matrix of trainable parameters.

The model consists in a two layer Graph Convolution:

I wanted to create a model visualization to see the impact of the convolution so I decided to extract the output of the last hidden layer and put it in a two dimensional axis. The model representation is made taking a snapshot of the last layer (seven activation units) each 200 epochs, and applying tSNE (t-Distributed Stochastic Neighbor Embedding) to reduce the dimensions of the vector from seven to two.

Results

1. Without using propagation function:

• 1000 Epochs.
• Snapshot taken each 200 epochs.
• 140 labeled examples.
• No propagation function

Accuracy: 0.531019

2. With Renormalization Trick as propagation function:

• Training 1000 Epochs.
• Snapshot taken each 200 epochs.
• 140 labeled examples.
• Renormalization Trick.

Accuracy: 0.769202

You can clearly see how the convolution helps the model to create a representation of k clusters, in this case seven, much clearer and how this representation evolves as long as the network is being trained. Note how the model rotates trying to group every point in its corresponding block.

You can take a look to the whole experiment in the following repo: https://github.com/emartinezs44/SparkGCN.

References:

Graph Convolutional Networks

Semi-Supervised Classification with Graph Convolutional Networks

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

Math Behind GCN