Demystifying Graph Neural Networks
Through this article, I aim to introduce you to a growingly popular Deep Learning algorithm, Graph Neural Networks (GNNs). GNNs are gradually emerging from the realm of research and are already demonstrating impressive results on real-world problems, suggesting their vast potential. The main objective of this article is to demystify this algorithm. If, by the end, you can answer questions like, Why would I use a GNN? How does a GNN work? I would consider my mission accomplished.
Before delving into the subject, it's necessary to recall two concepts intrinsically related to our topic:
Graphs and Embeddings
Graphs in Computer Science
Let's start with a quick reminder of what a graph is. Graphs are used in countless domains. Particularly in computer science, a graph is a data structure composed of two elements: a set of vertices, or nodes, and a set of edges connecting these nodes.
A graph can be directed or undirected. A directed graph is a graph in which edges have a direction, as shown below.
So, a graph is a representation of relationships (edges) between objects (nodes).
Embeddings
Embeddings are a way to represent information. Let me explain with an example before discussing it more formally. Suppose I have a set of 10,000 objects to know about. The "natural" representation of these objects is the discrete representation, which is a vector with as many components as elements in the set. So, in the image, the discrete representation is the one on the right, where only one of the vector components is 1 (black) and the rest are 0.
This representation clearly poses a dimensionality problem. This is where embeddings come into play. They reduce the dimensionality of the problem by representing data in a much lower-dimensional space. The representation is continuous, meaning the vector components' values are different from 0 and 1. However, determining what each component represents in this new space is not straightforward, as is the case with discrete representation.
More formally, an embedding is the mapping of a discrete variable to a continuous vector.
Graph Neural Networks
Now that we've revisited what a graph is, let's focus on the subject of the article: GNNs.
What does a GNN bring?
Many things can be modeled as graphs (e.g., traffic, recommendation systems, a molecule, etc.). This representation highlights the dependencies between the different elements involved. Traditionally, deep learning algorithms do not effectively exploit graph data structures. These data are processed to have a simpler representation (e.g., real-valued vectors). Consequently, information such as node dependencies related to the graph structure is lost.
So, the GNN is a deep learning algorithm that enables the incorporation of all the information inherent in a graph.
Imagine a scenario where we have a graph representing a social network. If a user (node) likes a certain type of content, it is likely that their friends (neighbor nodes) also like that content. GNNs can exploit this dependency to make more accurate predictions.
How does it enable this?
To answer this question, we need to explain how this algorithm works.
First, we need an initial representation of the problem we want to solve.
So, we have a series of nodes connected by edges. Each node carries information in the form of embeddings, which we'll call messages, and edges can represent identical or different links (e.g., if we want to represent a molecule having single and double bonds as a graph, we need to distinguish these two types of bonds, so they need to be associated with different links (edges)).
We can already provide a partial answer to the question. The algorithm will move the graph information (structure, link type, etc.) to the information carried by each node. But how?
The functioning of a GNN can be divided into three principles:
- Ingest the graph
- Build node dependency-related information
- Update node-carried information
So, the GNN takes the graph as input and finds ways to capture graph information. First, it assigns a function f (e.g., a neural network) to each edge. This allows it to build node dependency-related information. It also assigns a function q to each node (e.g., the GRU function), which enables it to update node knowledge, meaning "each node gets to know itself" and learns more about its neighbor
Earlier, we called the information carried by each node "message" because each node's knowledge is built through message passing.
Message passing is a fundamental principle of GNNs. Simply put, each node gathers information or messages carried by its neighbors through their respective neural networks and then updates its information, taking all these messages into account.
Information propagation
This is an iterative process where each node repeats this operation several times, allowing information to propagate throughout the graph. Over iterations, each node accumulates more and more information about its surroundings, enabling it to better understand the graph's overall context.
Applications of GNNs
GNNs have proven their effectiveness in various fields.
Protein folding:
- AlphaFold, developed by Google's DeepMind, uses Graph Neural Networks (GNNs) to solve the protein folding problem.
It has won first place in several CASP competitions.
Social networks:
- GNNs are widely used in social networks because they can be naturally represented as social graphs.
They help develop recommendation systems based on social relationships and relationships between elements.
Combinatorial optimization:
- GNNs are essential for many combinatorial optimization algorithms.
They are used to calculate shortest paths, Eulerian circuits, improve chip placements, and optimize branching rules.
Cybersecurity:
- GNNs can analyze a computer network represented as a graph to detect anomalies.
These anomalies can indicate malicious activity in the network, whether at the node, path, or edge level.
Limitations and Challenges
-
Inability to distinguish simple graph structures: Traditional GNNs, like GCN and GraphSAGE, struggle to distinguish certain graph structures, even simple ones. If node features are uniform, these models may not capture structural differences due to different combinations of edges. Remediation: Use the Graph Isomorphism Network (GIN).
- Noise sensitivity: GNNs are not robust to noise in graph data. Slight perturbations, whether by node perturbation or adding or removing edges, can adversely affect GNN outputs.
-
Non-injectivity: For GNNs to effectively distinguish graphs, they must be injective. However, popular models like GCN (which uses mean pooling) and GraphSAGE (which uses max pooling) are not injective. This means they can produce the same output for different inputs, limiting their ability to distinguish certain graph structures. Remediation: Design an injective multiset function using neural networks.
Conclusion
Graph Neural Networks represent a major advancement in the field of deep learning, offering a new perspective for dealing with structured data in the form of graphs. They combine the power of neural networks with the flexibility of graphs to provide innovative solutions to complex problems. If you work with data that can be represented as a graph, it's worth considering GNNs as an option for your analyses.
Ultimately, GNNs are a powerful tool, but like any tool, they must be used judiciously. With a solid understanding of how they work and their applications, you will be well-equipped to harness their full potential
Unless otherwise noted, all images are by the author
