Edward Ma | 4 Graph Neural Networks you Need to Know (WLG, GCN, GAT, GIN).

[NorbertZheng]

Edward Ma. 4 Graph Neural Networks you Need to Know (WLG, GCN, GAT, GIN).

[NorbertZheng]

Overview

We went through Knowledge Graph Embeddings and Random Walk in previous graph neural network stories. Knowledge graph embeddings train entity embeddings for downstream tasks. On the other hand, several neural networks model apply random walk theory to train entity embeddings.

In this story, we will go focus on 4 graph neural network models:

• Weisfeiler-Lehman Graph Kernel (Shervashidze et al., 2011),
• Graph Convolutional Network (Kipf and Welling, 2017),
• Graph Attention Networks (Veličković et al., 2017),
• Graph Isomorphism Network (Xu et al., 2019).

[NorbertZheng]

Weisfeiler-Lehman (WL) Graph Kernel

Shervashidze et al. (2011) introduce a way to measure graph similarity (WL test) on graph neural networks. Passed WL test means either of the graphs is an isomorphism or cannot prove graphs are not an isomorphism.

In WL test, you can define the height of the graph. Height means the number of iterations. The following procedure is WL test with $h=1$:

• Name node for every node.
• Add the connected node number. Taking graph $G$ as an example, node $4$ updated to node $4,1135$ as node $4$ connects to node $1$ (2 times), node $3$ and node $5$.
• Simplify node name. For example, convert node $4,1135$ to node $11$. (Just rename it in sequence)
• Check counts of both the original node labels and the newly generated labels. If both nodes' counts (feature vector) are the same, these two graphs are isomorphisms.

[NorbertZheng]

Graph Convolutional Network (GCN)

Kipf and Welling introduced Graph Convolutional Network (GCN) in 2017. The basic idea of GCN is

• aggregating both self features and neighbor features.

The below figure shows the overall architecture of GCN. Taking $X{2}$ node as an example, it absorbs $X{2}$ features (self), $X{1}$, $X{3}$ and $X_{4}$ (neighbor) features and feeding into neural network to train a model.

Regarding the feature of the node, it can be random initialization or numeric features. Taking paper citing as an example, a document is a node while the edge is citing. Node features (e.g. document) can be one-hot encoded-word count, year of publication, and authors. Another example is the social network. A person is a node while the edge is relationships (e.g. friendship). Features include the birth of a city, the number of friends.

[NorbertZheng]

Graph Attention Network (GAT)

Inspired by attention mechanism, Veličković et al. propose to apply it on the graph neural network. Same as GCN (Kipf and Welling, 2017), Graph Attention Networks (GAT) (Veličković et al., 2017) leverages self node features and neighbor features to train a model. Same as BERT in natural language processing (NLP) field, authors use multi-head attention to learn more different attention.

Using attention comes with several advantages:

• High computation efficiency as attention layers can be calculated in parallel.
• Play more attention to important neighbors.
• More powerful as it can support both direct graph and undirect graphs.
• It is inductive learning so it can handle unseen nodes.

[NorbertZheng]

Graph Isomorphism Network (GIN)

Topologically identical can be one of the ways to measure the graph's similarity. Traditionally, we can have the Weisfeiler-Lehman (WL) test it. Xu et al. proved that GIN is as powerful as WL test:

• Graph Neural Network (GNN) can be as powerful as the WL test by using simple architecture (multi-layer perceptron).
• GCN (Kipf and Welling, 2017) and GraphSAGE (Hamilton et al., 2017) cannot distinguish some graph structure.
• Sum aggregation is better than mean and max aggregation in terms of distinguishing graph structure.

[NorbertZheng]

Take Away

• If you need to handle unseen nodes, GCN may not be your choice while GAT can handle unseen nodes.
• GIN shows a way to better represent neighbors' aggregation.
• You can simply use PyTorch Geometric to apply GCN, GAT, and GIN.

[NorbertZheng]

Extension Reading

• Knowledge Graph Embeddings
• Random Walk in Graph Neural Network
• GCN Explanation
• GCN code
• GAT code](https://github.com/PetarV-/GAT)
• GIN code

[NorbertZheng]

Reference

• N. Shervashidze, P. Schweitzer, E. J. Leeuwen, K.Mehlhorn and K. M. Borgwardt. Weisfeiler-Lehman Graph Kernels. 2011
• T. Kipf and M. Welling. Semi-supervised Classification with Graph Convolutional Networks. 2017
• P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò and Y. Bengio. Graph Attention Networks. 2017
• K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How Powerful are Graph Neural Networks?. 2018.