Understanding Graph Neural Network with hands-on example| Part-1
Hello and welcome to this post, in which I will study a relatively new field in deep learning involving graphs — a very important and widely used data structure. This post includes the fundamentals of graphs, combining graphs and deep learning, and an overview of Graph Neural Networks and their applications.
Through the next series of this post here, I will try to make an implementation of Graph Convolutional Neural Network.
So, let’s get started!
What are Graphs?
A graph is a non-linear data structure made up of nodes and edges. Sometimes the nodes are also called vertices and the edges are lines or arcs connecting the graph with two nodes.
A graph can be defined more formally like this.
In the above Graph, the set of vertices V = {0,1,2,3,4} and the set of edges E = {{0,1}, {1,2}, {2,3}, {3,4},{ 0,4}, {1,4}, {1,3}}.
Graphs are used to solve a wide variety of real-world problems. Networks are represented graphically using graphs. Paths in a city, a telephone network, or a circuit network are examples of networks that can be used. Additionally, graphs can be found on social networking sites such as Linkedin and Facebook. A vertex is used to represent each individual in social media sites such as Facebook (or node). Each node is a structure that contains information such as a person's id, name, gender, location, and other attributes. These are a few examples of applications that make extensive use of the graph data structure.
There are many different types of graphs, each with its own set of characteristics such as the number of vertices, the number of edges, the degree of interconnection, and the overall structure.
Before talking about Graph Neural Networks, we should first talk about the input for these models: graph data.
Graph data is pretty simple. You have a set of nodes (or vertices = V) and you have edges (= E) between those nodes. The information about the connections in a graph is usually represented by adjacency matrices (or sometimes adjacency lists).
The adjacency matrix is symmetrical and lists all nodes along the rows and columns. If two nodes are connected in a graph, the adjacency matrix will have a one at the corresponding position; otherwise, for disconnected vertices, there is a 0.
Finally, the nodes or edges can have further properties — this means more specific information about the node/edge.
Graph Neural Network
Graph Neural Network is a type of Neural Network which directly operates on the Graph data structure. A typical application of GNN is node classification. Essentially, every node in the graph is associated with a label.
GNNs are a hybrid of an information diffusion mechanism and neural networks that are used to process data, representing a set of transition functions and a set of output functions. The information diffusion mechanism is defined by nodes updating their states and exchanging information by passing “messages” to their neighboring nodes until they reach a stable equilibrium. The process involves first a transition function that takes as input the features of each node, the edge features of each node, the neighboring nodes’ state, and the neighboring nodes’ features and outputting the nodes’ new state.
Applications of GNNs
Graph-structured data can be found almost everywhere. The problems that GNNs are used to solve can be divided into the following categories:
- Node Classification: The goal of this task is to determine the labeling of samples (represented as nodes) by examining the labels of their immediate neighbors (i.e., their neighbors’ labels). Typically, problems of this nature are trained in a semi-supervised manner, with only a portion of the graph being labeled during the training process.
- Graph Classification: The goal here is to categorize the entire graph into various categories. It is similar to image classification, except that the target is now in the graph domain. The applications of graph classification are numerous, and they range from determining whether a protein is an enzyme or not in bioinformatics to categorizing documents in natural language processing (NLP) or social network analysis, among other things.
- Graph visualization: Information visualization is a branch of mathematics and computer science that exists at the intersection of geometric graph theory and computer science. It is concerned with the visual representation of graphs that reveals structures and anomalies that may be present in the data and aids the user in comprehending the graphs they are presented with.
- Link prediction: Specifically, the algorithm must comprehend the relationship between entities in graphs, as well as attempt to forecast the likelihood of the existence of a connection between two entities. It is necessary in social networks to infer social interactions or to suggest potential friends to users in order for them to function properly. It has also been applied to problems involving recommender systems and the prediction of criminal associations.
- Graph clustering: The visualization of data in the form of graphs is referred to as clustering. On graph data, there are two distinct types of clustering that can be performed. Vertex clustering attempts to group the nodes of a graph into groups of densely connected regions based on the edge weights or edge distances between the nodes of the graph. When using the second form of graph clustering, the graphs are treated as the objects to be clustered, and the objects are clustered based on their similarity.
How do Graph Neural Networks work?
Having established the fundamental structure of the graph neural network (nodes with their embeddings and edges with feed-forward layers), we can proceed to a deeper understanding of how GNNs function in actual practice.
The basic idea is to learn neighborhood embeddings by aggregating information from a node’s neighbors via edges using neural networks.
Neighborhood Aggregation or Message Passing
Message passing is the process of exchanging and receiving information about a node’s neighborhood between nodes. Consider the following example of a target node with its initial embeddings: It receives information via edge neural networks from its neighbors. The data from these edges are aggregated (a variety of techniques are used, including maximum pooling, averaging, and so on) and passed to a node’s activation unit to generate a new set of embeddings for the node.
Each node in the initial configuration has the property x v.After message transmission, the embeddings of each node can be defined as follows:
Types of Graph Neural Networks
Graphs are used with various existing neural network architectures to yield promising results for various machine-learning problems. The two most dominant networks are discussed briefly below.
Graph Convolutional Networks (GCNs)
Convolutional neural networks(CNNs) have been vastly used for image classification and segmentation problems. Convolutional operation refers to applying a spatial filter to the input image and getting a feature map as a result.
You can read more about CNNs here.
In graph computation, GCNs refer to the process of applying a spatially moving filter over the nodes of a graph that contains embeddings or data relevant to each node in order to obtain a feature representation of each node. It is also possible to incorporate information from larger neighborhoods by stacking a number of convolutional layers, similar to how a regular CNN is constructed.
The simplest GCN has only three different operators:
- Graph convolution
- Linear layer
- Nonlinear activation
In most cases, the operations are completed in this order. They work together to form a single network layer. In order to create a complete GCN, we can combine one or more layers.
Graph Auto-Encoder Networks
A decoder takes the representation provided by the encoder as an input and attempts to reconstruct the input according to the representation provided by the encoder, and an encoder, which downsamples the input by passing it through convolutional filters to provide the compact feature representation of the image; and a bottleneck layer, which connects the two networks together.
You can read more about auto-encoders here.
When learning a compact representation of a graph, graph auto-encoders attempt to learn that representation and then re-construct the graph using the decoder. In order to learn graph embeddings, they can be used to predict embeddings for nodes that have not yet been observed as well as to classify newer nodes into existing categories within a graph, among other things.
Conclusion
The primary goal of this post is to provide an understanding of graphs and graph neural networks (GNN). Unstructured data can be made sense of using graph neural networks, which are an intuitive solution that can be applied to a wide range of real-world problems.
Hope you will like this post.
Until next time!
[1]: Nikita Sharma.(October 28,2020),Introduction to graph Neural Network-https://heartbeat.fritz.ai/introduction-to-graph-neural-networks-c5a9f4aa9e99
[2]: Understanding Graph Neural Networks-https://deepfindr.com/understanding-graph-neural-networks-part-1-3/
[3]:Graph Neural Network and Some of GNN Applications — Everything You Need to Know-https://neptune.ai/blog/graph-neural-network-and-some-of-gnn-applications
[4]: http://snap.stanford.edu/proj/embeddings-www/files/nrltutorial-part2-gnns.pdf
