Introduction to Graph Neural Network (GNN)

Introduction

 

With their advanced applications and features, machine learning and deep learning have created a buzz in the technological world. Machine translation, natural language processing (NLP), data mining, object identification, and other characteristics have revolutionized technology and made life simpler than ever before. 

 

Deep Learning models like CNN, RNN, and autoencoders are all components of neural networks that have greatly aided in pattern identification and data mining. 

 

Graph Neural Networks (GNN) is a relatively recent branch of deep learning research that incorporates graphs, which are frequently used in mathematics, machine learning, and data structuring. 

 

In this article, we will comprehend and explore the following:

 

• What are Graphs?

• What is Graph Neural Network?

• Types of GNN

• Applications of GNN

 

(Must check: Data mining tools)

 

What are Graphs?

 

To start with Graph Neural Networks, we have to first understand what graphs are as a graph is the most fundamental part of GNN. Graphs are a sort of data structure that consists of two parts: nodes (or vertices) and edges that link two nodes. 

 

As a result, a graph may be described as a collection of nodes that are only weakly connected by edges. There are many types of graphs like undirected graphs, directed graphs, complete graphs, etc. Given below are examples of the three graphs:

---

Diagram of Undirected, Directed, and Complete graph (Source)

---

A graph's nodes might be homogeneous, with all nodes having the same structure, or heterogeneous, with diverse types of structure. The edges describe a node's connection to another. Edges can be bidirectional or unidirectional. 

 

Edges can also be weighted, which means that weight is applied to the edge, which may represent the cost or importance of the edge. Graphs can represent many things in real life, like social media networks, the interconnection between cities through roads, and many more. 

 

A, an adjacency matrix, is frequently used to depict a graph. A has a dimension of (n x n) if a graph contains n nodes. Sometimes the nodes have a set of characteristics (for example, a user profile). If the node contains f features, then the dimension of the node feature matrix X is (n x f).

 

(Suggested read: Introduction to Network Graph and Network Topology)

 

What is Graph Neural Network?

 

Now that we know the main objective of graphs, we understand that graphs have an enormous expressive capacity, and as a result, they are getting a lot of interest in the field of machine learning. Every node is coupled with an embedding, which specifies the node in the data space. 

 

Graph Neural Networks (GNNs) is a type of deep learning approach that performs inference on graph-described data. They are neural networks that can be applied directly to graphs and give a simple approach to anticipate node-level, edge-level, and graph-level events. 

 

The main goal of GNN is for each of the nodes to learn an embedding containing information about its surroundings. This process of embedding can be used for many applications like node labeling, node prediction, edge prediction, etc. Thus, once we've assigned embeddings to each node, we may transform edges by adding feed-forward neural network layers and merge graphs with neural networks. 

 

(Also read: Applications of neural networks)

 

Types of GNN

 

Two types of GNNs are mostly dominant: Graph Convolutional Network (GCN) and Graph Auto-Encoder Network. Let us understand the two below:

 

1. Graph Convolutional Network:

 

GCNs refer to the process of applying a spatially moving filter on the nodes of a graph that include embeddings or data relevant to each node to get a feature representation of each node. To include input from wider neighborhoods, several convolutional layers, similar to a standard CNN, can be stacked.

 

 

2. Graph Auto-Encoder Network:

 

Auto-encoders are neural networks that integrate two networks: an encoder that downsamples the input by transferring it through convolutional filters to provide a compact feature representation of the image, and a decoder that takes the encoder's interpretation as input and tries to reconstruct the input based on it. 

 

Graph auto-encoders strive to comprehend a visual illustration of the graph and then re-construct the graph using the decoder. They may be used to learn graph embeddings and hence anticipate embeddings for unseen nodes and categorize newer nodes into existing categories inside the network.

 

 

Applications of GNN:

 

There are many real-life applications of Graphical Neural Networks like recommender systems, natural sciences, posts prediction, etc. The following are some of the applications of GNN:

 

1. Graph Classification:

 

The goal here is to divide the graph into distinct groups. It's similar to picture classification, except the goal shifts to the graph domain. Graph classification has a wide range of uses, from identifying whether a protein is an enzyme or not in bioinformatics to categorizing articles in NLP or social network analysis and research.

 

 

2. Node Classification:

 

The objective here is to identify the labeling of samples (shown as nodes) by looking at their neighbors’ labels. Typically, problems of this sort are trained semi-supervised, with only a portion of the graph labeled.

 

 

3. Link Prediction:

 

In this case, the algorithm must comprehend the link between entities in graphs and attempt to forecast if two entities are connected. It is critical in social networks to infer social connections or to recommend potential buddies to users. It's also been used to solve recommender system issues and forecast criminal connections. 

 

 

4. Graph clustering:

 

It refers to data clustering in the form of graphs. On graph data, there are two unique types of clustering. Vertex clustering attempts to organize network nodes into clusters of highly linked areas based on edge weights or edge distances. 

 

The second type of graph clustering considers graphs to be the objects to be grouped and groups them based on similarity.

 

 

5. Graph visualization:

 

It is a branch of mathematics and computer science that combines geometric graph theory with information visualization. It is focused on the visual depiction of graphs, which shows structures and abnormalities in the data and assists the user in understanding the graphs.

 

(Suggested reading: Applications of Data visualization)

 

GNN vs CNN

 

GNN is the solution to the limitation of Convolutional Neural Networks (CNN) as CNNs fail on graphs. CNN’s are very useful in tasks like image classification, image recognition, or object detection. 

 

The convolution operator window is slid across a 2-dimensional image and some function is computed as it is passed through many layers. Now, the result from this that allows us to reach our goal is that convolution takes a small rectangular section of the image,  applies a function to it, and creates a new portion (a new pixel).

 

The center node of that center pixel combines information from its neighbors as well as from itself to generate a new value. Because of the unlimited size of the graph and the complicated topology, which implies there is no spatial locality, doing CNN on graphs is extremely challenging. 

 

There's also node ordering that isn't corrected. If we originally named the nodes A, B, C, D, E, and subsequently labeled them B, D, A, E, C, the matrix inputs in the network will change. Because graphs are invariant to node ordering, we want to receive the same result no matter how we order the nodes.

 

 

How does Graph Neural Network work?

 

By now, we understand the basic structure of GNN. Let us understand with the help of this diagram, how GNNs work:

---

Working of GNN (source)

---

To understand the working of GNN, we have to study how neural networks are used to learn neighborhood embeddings by aggregating information from a node's neighbors through edges. 

 

Neighborhood aggregation is a process of forwarding and receiving back the data between nodes, throughout their neighborhood. Let us consider a target node that already has its original embeddings. It gets input from its neighbors, which are routed through edge neural networks. 

 

Data from these edges are collected using techniques such as max pooling, averaging, and so on, and then sent to a node's activation unit to generate a new set of embeddings for the node.

 

Every node in the initial configuration contains the feature x_v. After message forwarding, the embeddings for each node may be defined as follows, according to this source:

 

 

Where xv represents the features of v's neighbors, x co[v] represents the edge features related to v, and h ne[v] represents the embedding of v's neighbors.

 

According to this diagram and information are taken from this source, 

---

---

In the diagram above, hA(1)  represents the node's initial embedding, while hNa(1) represents the aggregated embeddings of its neighbors. Combining these and submitting them to the node's activation unit or filter yields the new embedding for node A, which additionally includes information about its neighbors. 

 

As a result, each node receives a new set of embeddings, which defines its location in the graph. A node learns more and more about its immediate and distant neighbors through different iterations or K levels of message passing. Finally, each node has a basic notion of the entire graph.

 

(Must catch: Basics of Modular Neural Networks)

 

Conclusion

 

GNN is a relatively newer topic of study and is still growing in its applications every day. It is widely used in image classification, Natural Language Processing, text classification and so much more. Even real-life problems like traffic speed, the density of roads, and forecasting of traffic networks, in general, takes the help of GNN. 

 

GNNs have been used to solve a wide range of issues, including program verification, program reasoning, social influence prediction, recommender systems, electronic health records modeling, brain networks, and adversarial attack protection. 

 

Over the years, this field of study is getting more influential and powerful and anyone who wants to work with deep learning algorithms must know the basics of Graph Neural networks. This article is an overview of GNN.