Applications of Graph Neural Networks
Graphs and their study have received a lot of attention since ages due to their ability of representing the real world in a fashion that can be analysed objectively. Indeed, graphs can be used to represent a lot of useful, real world datasets such as social networks, web link data, molecular structures, geographical maps, etc. Apart from these cases which have a natural structure to them, non-structured data such as images and text can also be modelled in the form of graphs in order to perform graph analysis on them. Due to the expressiveness of graphs and a tremendous increase in the available computational power in recent times, a good amount of attention has been directed towards the machine learning way of analysing graphs, i.e. Graph Neural Networks.
So, what are Graph Neural Networks (GNNs)?
According to this paper, Graph neural networks (GNNs) are connectionist models that capture the dependence of graphs via message passing between the nodes of graphs. They are extensions of the neural network model to capture the information represented as graphs. However, unlike the standard neural nets, GNNs maintain state information to capture the neighbouurhood properties of the nodes. These states of the nodes of a graph can then be used to produce output labels such as a classification of the node or an arbitrary function value computed by the node. The network tries to learn these encodings(hv) for each of the nodes through a mutual sharing of data among the nodes’ neighbours in an iterative manner until convergence.
Given the wide range of domains in which GNNs can be applied, most of them could either be classified as structural applications or as non-structural applications based on the type of data. The structural case represents data that has an inherent structure to it such social interaction networks or molecular networks. Consequently, the non-structural scenarios represent cases where the structure in the data is not explicit such as text and images. In these non-structural scenarios then, the general approach is to try to transform the data to a structured format and then apply GNN. There are a few other applications as well that do not fall into the purview of either of the classes mentioned above. We will discuss some interesting applications from each of these categories here.
Physical Systems
The human brain is said to aid its reasoning process through the creation of graphs learned from daily experiences of the real world. Hence great importance is being assigned to the modelling of real-world entities and their interactions as graphs. This is deemed as a first steps towards human-like artificial intelligence. By considering objects as nodes and the relations or interactions between them as edges, simple physical systems can be modelled as graphs and can be effectively analysed using GNN.
Interaction networks can be trained to reason about the interactions of objects in a complex physical system. It can make predictions and inferences about various system properties in domains such as collision dynamics (rigid and non-rigid). It simulates these systems using object and relation centric reasonings using deep neural networks on graphs. These GNNs have been shown to predict the trajectories of different objects thousands of time steps into the future.
Visual interaction networks make use of the above interaction network to go a step further and learn about the dynamics of a system from just its raw visual observation or to put it simply, with as little as six video frames of the system in action. Apart from predicting the future trajectories of a range of physical systems just like its parent network, this model can also infer the mass and future states of unknown objects from their influence on the visible ones! This is achieved through the co-training of a perceptual front-end convolutional neural network that parses a visual scene to provide a set of object node representations to a back-end interaction network.
Chemistry
The nano-scale molecules have an inherent graph like structure with the ions or the atoms being the nodes and the bonds between them, edges. GNNs can be applied in both scenarios: learning about existing molecular structures as well as discovering new chemical structures. This has had a significant impact in computer aided drug design.
Molecular fingerprints are feature vectors that represent molecules. Machine learning models to predict the properties of a new molecule by learning from example molecules use fixed length fingerprints as inputs. GNNs can replace the traditional means that give a fixed encoding of the molecule to allow the generation of differentiable fingerprints adapted to the task for which they are required. Furthermore, these molecular fingerprints learned by the GNN from the graph structure of the molecule need not be as large as the fixed fingerprints which must encode all possible substructures in a single feature vector. The differentiable fingerprints can be optimised to encode only relevant features, reducing downstream computation and regularisation requirements.
Image classification
Image classification, a classic computer vision problem, has outstanding solutions from a number of state-of-the-art machine learning mechanisms, the most popular being convolutional neural networks (CNN). GNN, which drive their motivation out of CNN, have also been applied in this domain. Most of these models, including GNN, do provide attractive results when given a huge training set of labelled classes. The focus now is towards getting these models to perform well on zero-shot and few-shot learning tasks. Zero shot learning (ZSL) refers to trying to learn to recognise classes that the model has not encountered in its training. ZSL recognition relies on the existence of a labelled training set of seen classes and the knowledge about how each unseen class is semantically related to the seen ones. One approach is to leverage structural information, in the form of graphs, in ZSL image classification. GNN, consequently, appear quite appealing in this respect. Knowledge graphs can provide the necessary information to guide the ZSL task. Different approaches differ in the kind of information they represent in the knowledge graph. These graphs may be based on the similarities between the images themselves or those of the objects in the images extracted through object detection. The graphs may also incorporate semantic information from word embeddings of the category labels of the images. GNNs can then be applied to this structured data to aid the ZSL image classification-recognition task.
Text
Like images, the relation within text is also not explicit, i.e. text cannot be considered structured data to which GNN can be applied directly. However, there are ways to convert a text document into structured data such as a graph of words or of sentences and then use graph convolution to convolve the word graphs. Another approach to structure the text data is to use Sentence LSTM which views an entire sentence as a single state (node) consisting of sub-states i.e. words. Document citation relations can also be used to construct graphs with documents as the nodes. Text GNNs can then be used to learn embeddings for words and documents. These approaches can be used for various NLP tasks such as text classification, sequence labelling, machine translation, relation and event extraction.
One interesting area of application is reading comprehension; given a text passage, the model must be able to answer questions based on it by consolidating information in the passage.
Reading comprehension is one of the complex reasoning tasks performed by humans; the answer to a question may not be located in any single part of the extract but may need global inferencing. Representing the passage in the form of a graph using a Sentence LSTM helps in better connecting the global evidences.
Combinatorial Optimization
Combinatorial optimization problems over graphs are a set of NP-hard problems. Some of these can be solved by heuristic methods. In recent times, attempt is being made to solve them using deep neural networks. Consequently, GNNs are also being leveraged to operate over these graph structured datasets.
Interestingly, a general GNN based framework can be applied to a number of optimisation problems over graphs such the minimum vertex cover problem, maximum cut, the travelling salesman problem, minimum spanning tree, etc. A few approaches combine GNNs with reinforcement learning to iteratively learn a solution given an input graph. One of the instances in which GNNs outperform traditional methods is the Quadratic Assignment Problem. It aims to measure the similarity of two graphs. The comparison of the graphs using GNN-learned node embeddings offers better performance than standard relaxation-based techniques.
Conclusion
Graph Neural Networks are increasingly gaining popularity, given their expressive power and explicit representation of graphical data. Hence, they have a wide range of applications in domains that can harness graph structures out of their data. Presented above is just the tip of the iceberg. As newer architectures continue to crop up, GNNs will continue to foray into diverse domains.
Graph Neural Networks have now evolved into Graph Convolution Networks which, as the name suggests, are inspired by Convolution Neural Networks. These are much more efficient and powerful and form the baseline for other complex Graph Neural Network architectures such as Graph Attention Networks, Graph Auto-Encoders, Graph Generative Networks and Graph Spatio-temporal Networks. Explore these advanced architectures in this post: Beyond Graph Convolution Networks.
