Concepts and Models
Don’t Think Twice
The Artificial Neuron at the Core of Deep Learning
Methods, Best Practices, Applications
Bias Neuron, Overfitting and Underfitting
Methods and Applications
Optimization Methods and Real World Model Management
The Complete Guide
How to Build One in Keras & PyTorch
Concepts, Process, and Real World Applications
Is it the Right Choice?
Origin, Characteristics, and Advantages
Process, Example & Code
Uses, Types, and Basic Structure
How to Choose?
A Graph Neural Network, also known as a Graph Convolutional Network (GCN), is an image classification method. In this article, we’ll provide an introduction to the concepts of graphs, convolutional neural networks, and Graph Neural Networks.
Read on to discover an example of a simple GCN in action, and see applications of graph convolutional networks including, generating predictions in physical systems and image classification. Learn how to scale GCNs on large numbers of machines using the MissingLink deep learning platform.
Let’s start with basic definitions to get an orientation of the subject.
A graph in computer science is a data structure consisting of Vertices (also called nodes) and Edges (also called connections). Graphs are extremely useful and expressive mathematical structures, which can be used to model real-world phenomena like social networks, molecular structures, semantic structures, geographical or physical models, and more.
Here are two ways to represent a graph: using an equation with a group of vertices V and a group of edges E. And a diagram with nodes and the connections between those nodes. The example below shows a directed graph, but edges can also be undirected.
A Convolutional Neural Network (CNN) is a neural network structure which breaks down an input, typically an image, into smaller pieces and performs feature extraction – it derives important parts of the input which can be used to make a decision, typically a classification decision.
The CNN alternates between convolution and pooling layers. The convolution layers pass a filter over the source image and extract the important information from each piece. The pooling layers take the extracted information and downsample it to retain only the most important information. When the essential data is extracted, it is passed through a fully connected layer to arrive at the final classification decision.
A Graph Neural Network, also known as a Graph Convolutional Networks (GCN), performs a convolution on a graph, instead of on an image composed of pixels.
Just like a CNN aims to extract the most important information from the image to classify the image, a GCN passes a filter over the graph, looking for essential vertices and edges that can help classify nodes within the graph.
Source: Zonghan Wu et. al., 2019
Following is a simplified formula that shows how a graph can be normalized and “packaged” into a regular neural network function, that takes parameters and weights and returns the output to the next neural network layer. The function also has a non-linear element, enabling backpropagation.
A few important evolutions of GSNs provide additional capabilities:
Source: Zonghan Wu et. al., 2019
Below we can see a simple GCN in action. It goes through the following stages:
Note: There are new approaches for pooling over a graph representation, which are more elegant and could enable multiple convolutions for GNNs.
Note: In a large graph, SoftMax could become very computationally intensive, and so GNN frameworks like DeepWalk use hierarchical Softmax to save time and compute Softmax for only some of the nodes.
GCNs can be used to model real-world entities as graphs, and predict their interaction and future behavior. The network can treat real-world objects as vertices, and their interactions as edges. A GCN can make accurate inferences about properties of a physical system, such as collision dynamics, trajectories of objects, and even the effect of objects not seen in the image on other objects.
Image classification was traditionally performed by regular CNNs. However, practitioners are now applying GCN architectures to image classification problems, with encouraging results. A particular focus is on Zero Shot Learning (ZSL), in which a model needs to recognize and label an image belonging to an unknown label, by inferring which known labels it may be similar to. GCNs can use knowledge graphs to categorize a “zero shot”, based on similarities between the images, objects extracted from the images, or semantic information in the category labels.
GCNs are used to solve community prediction problems like Zachary’s Karate Club—a small social network where there is a conflict between the administrator and instructor in a karate club, and we need to predict which side each member of the club will choose. A GCN can address similar problems using semi-supervised classification via spectral graph convolutions.
Tobias Jepsen showed that with just using two labeled nodes, a GCN can achieve a high degree of separation and generate accurate predictions for the two communities in the Karate Club problem. Below is the correct Karate Club classification and one of the results obtained by his GCN model.
Correct Classification of Karate Club Problem
Classification Achieved by Jepsen’s GCN Model
Molecular structures are also graph structures. GCNs can learn about existing molecular structures and help researchers discover new ones. Taking a fixed-length molecular fingerprint as their input, they train on known molecules and generate predictions regarding unknown molecular structures. Generative Graph Networks such as MolGAN can be trained to create new molecular structures that have certain desired properties.
The field of operations research has a deep interest in combinatorial optimization problems, in which the objective is to find an optimal solution object from a set of objects representing possible strategies. For example, researchers have applied GCNs to the classic travelling salesman problem, combining a GCN with reinforcement learning to iteratively lean a solution, starting from an input graph. GCN outperforms traditional algorithms like Quadratic Assignment Problem.
In this article, we learned the basics of GCNs, a new and powerful tool in the deep learning arsenal. Training GCNs is very computationally intensive, and you may have to experiment with several architectures or variants to get things right. Don’t wait for hours for GCNs to train. Use the MissingLink deep learning framework to:
MissingLink can also help you manage large numbers of experiments, track and share results, and manage large datasets and sync them easily to training machines.
Learn more about the MissingLink deep learning platform.
The most comprehensive platform to manage experiments, data and resources more frequently, at scale and with greater confidence.
MissingLink is the most comprehensive deep learning platform to manage experiments, data, and resources more frequently, at scale and with greater confidence.
Request your personal demo to start training models faster