In recent times, Neural Networks has gained huge popularity due to its application and ease of usage in the field of Pattern Recognition and Data Mining. The application of Deep Learning to tasks such as object detection and speech recognition using techniques such as CNN, RNN and autoencoders has brought huge amount of work into the research and development of Neural Networks.
Application of Deep Learning on the data such as images, text and videos are easily performed as they are based on Euclidean data. What about the applications where data is represented as graphs (Non-Euclidean) with highly complex relationships between objects?
This is where we bring in the concept of Graph Neural Networks (GNN). In this article, we shall go through the definitions and basics of Graphs and GNNs and see some of the latest applications of Graph Neural Networks.
What Is A Graph?
From the title – Graph Neural Networks, we see that the most fundamental part of GNN is a Graph.
In Computer Science, a Graph is defined as a data structure with two components. Vertices and Edges. A graph G, can be defined as G = VE. Where V is the set of vertices and E are the edges between them. The term vertices and nodes are often used interchangeably. If there is any arrow mark on the edges called directional dependency, then it is a directed graph. If not, they are undirected graphs.
A graph can represent several things – social media network, city network, molecules etc. Consider the following graph that represents a network of cities. The cities are represented as the nodes and the roads connecting them are the edges.
Using the above graph network, we can solve several problems pertaining to these cities such as finding which cities are well-connected or finding the shortest distance between two cities.
What Are Graph Neural Networks ?
As the Graphs have extremely strong expressive powers, they are widely gaining attention in the field of Machine Learning. Every node has an embedding associated along with it. That embedding defines the node in the data space. Graph Neural Networks refer to the neural network architectures operating on a graph.
The primary aim of a GNN architecture is to learn an embedding which contains information about its neighbourhood. Using this embedding, we can solve several problems like labelling the node, prediction of nodes and edges, etc.
In other words, Graph Neural Networks are an additional class of Deep Learning methods which are designed to perform inference on data which are given by graphs. They are applied on graphs and can easily perform node-level, edge-level and graph-level prediction tasks.
Why Not CNN ?
The main advantage of GNN is that it can perform tasks that the Convolutional Neural Networks (CNN) failed to do. CNNs are used to perform tasks like object detection, image classification and recognition. Using hidden convolutional layers and pooling layers, CNN achieves this.
It is computationally difficult to perform CNN on graph data as it is highly arbitrary and complex topology, which means that there is no spatial locality. Also, there is an unfixed node ordering which makes it more difficult to apply CNN.
Graph Neural Networks
Thus, it is understood that as it is called, GNN is a neural network that is directly applied to graphs providing convenient way for edge level, node level and graph level prediction tasks. There are mainly three types of Graph Neural Networks:
- Recurrent Graph Neural Network
- Spatial Convolutional Network
- Spectral Convolutional Network
One of the intuitions of GNN is that the nodes are defined by its neighbours and connections. We can visualize it by imagining that if all the neighbours of a node are removed, then the node will lose all its information. Thus, the concept of neighbours of a node and connections to neighbours define a node.
With this in mind, let us give every node a state (x) to represent its concept. We can use the node state (x) to produce an output (o), which is the decision about the concept. The final state (x_n) of the node is called as the “node embedding”. The main task of all the Graph Neural Network is to determine the “node embedding” of each node, by looking at the information on its neighbouring nodes.
Let us start with the most powerful version of GNN, Recurrent Graph Neural Network, or RecGNN
Recurrent Graph Neural Network
As mentioned in the original paper, RecGNN is built with an assumption of the Banach Fixed-Point Theorem which states that: Let (X,d) be a complete metric space and let (T:X→X) be a contraction mapping. Then T has a unique fixed point (x∗) and for any x∈X the sequence T_n(x) for n→∞ converges to (x∗). This means if I apply the mapping T on x for k times, x^k should be almost equal to x^(k-1).
Spatial Convolutional Network
The intuition of Spatial Convolutional Network is similar to that of the CNN. As we know in CNN, the idea is to perform convolution by summing the neighbouring pixels around a centre pixel with a filter and learnable weights. Spatial Convolutional Networks adopt a similar idea by aggregating the features of neighbouring nodes towards the centre node.
Spectral Convolutional Network
With contrast to other Graph Neural Networks, this type of GNN has a strong mathematics foundation. It is developed on Graph Signal Processing Theory. It uses Chebyshev polynomial approximation for simplification.
What can A GNN Do?
The problems that a GNN can solve are broadly classified into 3 categories –
- Node Classification
- Link Prediction
- Graph Classification
involves in predicting the node embedding for each node in a graph. In such cases, only a part of the graph is labelled and hence this is known as semi-supervised graph. Some applications are YouTube videos, Facebook friend recommendation, etc.
the main task is to identify the relationship between two entities in a graph and predict if there is any connection between the two entities. For example, consider a recommender system where a model is given a set of reviews by users of different products. The task is to predict the users’ preferences and tune the recommender system to promote products that match the users’ interest.
involves in classifying the whole graph into several different categories. It is quite similar to image classification task but the target here is in the graph domain. There are several examples of Graph Classification such as in chemistry, a model is given a molecular structure in the form of a graph and the task is to classify the target into a particular category.
Real-Time Applications Of GNN
Since its introduction in 2018, GNNs have found quite a few real-time applications which are summarized below.
Natural Language Processing
GNN finds its applications in a wide variety of NLP applications such as Sentiment Classification, Text Classification, Sequence Labelling. They are used in NLP because of its ease of application. They are also used in Social Network Analysis such as prediction of similar posts and recommending specific content to users.
Computer Vision is a vast field that has grown rapidly with the help of Deep Learning in areas such as Image Classification, Object Detection etc. The most popular application being the Convolutional Neural Networks. Off late, GNNs have also been applied in this domain. Though the application of GNN in Computer Vision is in its incipient stage, it shows huge potential in the coming years.
GNNs are also widely being used in Science such as the Physics Systems, Side Effects Prediction and Disease Classification. Chemists are also using GNNs to study the graph structure of compounds and molecules.
The application of GNN is not only limited to the above tasks. There have been several attempts in application of GNN to a variety of domains such as recommender systems, social network analysis etc.
In the past few years since GNNs have been introduced, they have become a strong and reliable tool to solve problems that can be modelled by graphs. This is due to its flexibility, expressive power and easy visualization. Thus, GNNs are an intuitive solution to unstructured data with a wide range of real-world applications.
If you want to know more about GCN and its features and benefits, do register at upGrad Education Pvt. Ltd. And IIITB’s Post Graduate and Diploma course on Machine Learning and Artificial Intelligence. This course on Machine Learning and AI is designed for students and working professionals.
The course provides a collection of case studies & assignments, industry mentorship sessions, IIIT Bangalore Alumni status, job placement assistance with top companies, and most importantly, a rich learning experience.