414. Graph Neural Network Basics

▮ GNNS

For this post, I’d like to share the basics of Graph Neural Networks.

▮ Graphs

First let’s look through the main elements of a graph in order to understand GNN’s.

• Nodes (Vertices)
• Edges: the connection between nodes
• Adjacency Matrix: a matrix to store information on which edges are connected to which.

Graph data is used in various situations such as social networks and recommendation systems.

▮ Differences From Image Data

1. Size And Shape
   When training a neural network, the dimensions of the input data are fixed. For images, you can easily resize it. However, when it comes to graph data, you can’t just remove edges and nodes.
2. Isomorphism
   For image data, when you flip it, you get a new data. However, when it comes to graph data, even when you flip an image, the underlying graph structure representing an object within the image must be the same.
3. Non-Euclidean
   Unlike images, which are structured in a grid manner(pixels), graph data is not aligned

▮ Machine Learning Tasks

Like all machine learning algorithms, we also want to understand what are the tasks that can be achieved by GNNs. Here are the main three tasks.

• Node-Level Prediction:
  ex) Does this person smoke?
• Edge-Level Prediction
  ex) Which video to recommend on Netflix?
• Graph-Level Prediction
  ex) Is this molecule a suitable drug?

▮ Forward Pass

The overview would look like the image below. You feed in a graph(set of vectors) and the GNN algorithm would output another set of vectors.

The procedures within the passing layers, are similar to convolutions.

1. Pick a Node(Vector)
2. Aggregate adjacent Node Vectors.
3. Update the node vector chosen on step 1 with the aggregated vector
4. Repeat above processes for all nodes

You iterate this process multiple times to get the final graph representation. In the first step, each node only acquires adjacent node information, but if you repeat this, each nodes would get information beyond their adjacent nodes(In the image above, you can see that the information for node 5, which is green, is not included in the information for node 1 in STEP 1, but included by STEP N).

This means, there are 2 main procedures during forward propagation.

1. Aggregation Method for Adjacent Nodes
2. Update Method for the chosen node

There are many GNN algorithms, but most of them are proposing how to do the calculation I’ve mentioned above.

▮ Reference

• Graph Neural Networks