Transcription
World runs on networks. Think of social circles, molecules, even the web. But conventional neural networks struggle to make sense of these connections. Today, we're breaking down a type of model that that is graph neural networks, or GNNs.
Most machine learning models expect data in a nice clean table, but the world is messy, so this isn't always possible. Graphs on the other hand capture both the features of things and the structure that connects them. And the relations are called edges, and they connect entities called nodes. So mathematically, a graph G can be represented as a tuple of a set of nodes or vertices and a set of edges. And each edge is a pair of two vertices and represents a connection between them.
A simple way of visualizing the connectivity of a graph is through its adjacency matrix. Which can represent both undirected and directed graphs. So for instance, node zero in a directed graph connects to node one. But the inverse is not true because of the directionality of the connection. And this can mean node zero is a student, node one is a teacher, and the edge between them represents a "is student of" relation. So node 0 is a student of node 1, its teacher, but clearly the inverse wouldn't be true. Hence why, in the adjacency matrix, row 0, column 1, contains a 1, whereas row 1, column 0, does not. And since node 0, is also a student, of nodes 2 and 4, for instance, this is also evident in the Adjacency Matrix.
To make use of this information, we can generate embeddings. And these can be for not only the nodes but also the edges and even graphs as a whole. Embeddings are crucial because they convert graph data into dense low-dimensional vectors that capture both structural and feature-based relationships. And we can use GNNs for both heterogeneous and homogenous graphs. So heterogeneous GNNs. Are ones with different types of nodes and edges, like the student-teacher graph that we just saw, whereas homogeneous graphs are ones with only one type of node and one type edge.
Great, so now we know the basics of nodes and edges. Now let's talk about how we can represent communication between nodes. GNNs use a message passing mechanism to aggregate information from neighboring nodes, allowing them to capture the complex relationships in graphs. And the key idea is that nodes don't make predictions alone. They exchange information with their neighboring nodes and aggregate that information to update their own representations. And this happens in layers. So let's look at node A. In layer one, the node looks at its immediate neighbors. So that can be these two. Then, in layer 2... The node looks at neighbors of neighbors. So perhaps here. And as you can imagine, with each layer, its representation becomes richer and richer. And this is how a GNN learns both local patterns and global structure.
Let's break this down into typical message passing steps. So the first step is message creation. So this is where each neighbor sends node A some encoded information such as feature vectors, edge weights, and so on. Next is aggregation. So node A combines all incoming messages using operations like taking the sum, mean, max, or attention-weighted combinations. We'll get to those in just a bit. Finally, node A can update. Its representation based on the aggregated messages.
We've seen how nodes communicate, sending messages, aggregating them, and updating their representations. But not all GNNs do this in the same way. Different architectures take different approaches. Today, we'll look at graph convolutional networks, graph sage, graph attention networks, graph isomorphism networks, and graph transformers. Lots of new terms, I know, but don't worry, I'm here to help.
Let's start with the classic one, graph convolutional networks, or GCNs. These work kind of like CNNs, but over graphs instead of images or videos. So each node gets a smoothed aggregated representation of its neighbors. It's a great choice for semi-supervised classification tasks. So for the embedding of node V at layer L, we first aggregate over each neighbor I have node V. The previous layer L minus 1. So we'll notate this like so. And then we pass this through the weight matrix at layer L, so that's WL. And finally we can apply some nonlinear activation. So this will be sigma. Nonlinearity lets the actually learn complex patterns in the graph? Instead of collapsing everything into one big linear transformation.
Next is graph sage. So this is short for graph, sample, and aggregate. As you can probably guess, graph sage learns how to aggregate information and sample neighbors instead of using the entire graph. And this makes it great for really large networks like ones with millions of notes. So for, again, a node V at layer L, we first aggregate the embeddings of its neighbors from the previous layer L minus 1. We can then concatenate that with node V's own embedding from layer L-1. So we'll put a concat here. And the result is then passed through the There's weight matrix. So we'll multiply that by W. And a nonlinear activation to produce the updated embedding. So again, sigma here.
And then we have graph attention networks, or GAT for short, where not all neighbors are treated the same. The model learns which connections matter more, assigning larger attention weights to more important neighbors than others. And so again, for the embedding of node V at layer L, We look at all its neighbors u at the previous layer l minus 1. So u at l minus one. And we can transform these features with a weight matrix w at the current layer. And we can multiply each one by an attention coefficient. So we'll represent this as alpha v u. And this tells us how important that neighbor is. And the attention coefficients are initialized as random learnable parameters, and they're updated during training via backpropagation to dynamically weigh the importance of neighbors. And these alpha values are all positive and normalized as they must sum to one. We can then sum everything up. So again, we're looking at the neighbors of node V, and we can pass it through an activation function. So that'll be sigma again. And in doing so, node V learns to focus more on the neighbors that matter most when updating its representation.
Another important architecture to mention is the graph isomorphism network, or GIN. It's actually one of the most expressive GNNs. We use multilayer perceptrons, or MLPs, instead of fancy operations, and somehow that simplicity makes it even better at telling different graph structures apart. So again, for the embedding of node V at layer L, we take each node that it neighbors with. So we sum over the neighbors. And we take their embeddings at the previous level, so HU0-1, and we sum them with node V's own features. So that's a summation here with H of V at the previously, and we can scale this by a value so that's one. Then that combined vector is passed through an MLP. Which adds non-linearity and expressive power. And this simple sum and MLP structure makes Jin especially strong at distinguishing different graph structures. It's particularly interesting considering most GNN architectures actually struggle to tell apart certain graph structures, especially when two graphs look similarly, but aren't actually the same.
So let's take this example. Both graphs have the same number of nodes and edges. And each node has the same degree, since every node connects to exactly two others. So looking at this, structurally everything lines up, that's why these graphs are considered isomorphic. But here's the catch, a standard GCN would still struggle to tell them apart. It's message passing, especially mean and max pooling. Tend to smooth away important structural differences, treating distinct neighborhood patterns as if they were identical. And because this type of aggregation isn't injective, two different graph structures can collapse into the same representation. And it's exactly the kind of limitation that the WL test was designed to address. The WL Test is a classic and surprisingly powerful method. For determining whether two graphs are structurally identical. Gins were built to match its expressive power, meaning they can reliably distinguish graph structures that simpler GNNs, and especially GCNs would incorrectly map to the same embedding.
Last but not least, of course, transformers have made their way into graphs, too. So graph transformers use global attention. Meaning any node in theory attend to any other node. And they're great when you need to capture long-range relationships or you're working with messy complex graph data. So as before, the model starts with a matrix of node embeddings, matrix H. It then applies three learned linear transformations to that matrix to produce queries, keys, and values. So that's Q equals H double Q. Same for keys and the same for values. And these determine what information it looks for, what information that offers, and what information gets passed along. Next, the model computes the attention score for each node pair. So the attention of Q, K. It compares each node's query to every other node's key to compute attention scores. So our numerator is Q K transpose. And we can optionally adjust this by using graph structure. So that can be the square root of the key or query vector dimension. So square root D. And in standard transformers, attention scores are computed purely from the similarity between node embeddings. But in graphs, the structure of the graph itself matters, so graph transformers account for this by adding a bias term to the attention score, plus B. And that encodes structural information such as whether two nodes are connected, how far apart they are in the or what type of edge connects them. Then it takes a weighted combination of value vectors, so that's V, to update its representation, allowing every node to attend globally, not just to its immediate neighbors. Then this all gets passed through the softmax function.
Note that instead of using one attention mechanism, graph transformers use multiple attention heads in parallel, and each attention head is computed by applying the attention mechanism to its own set of queries, keys, and values. Now for multi-head attention. Of the same queries, keys, and values. After all attention has produced their outputs, they are concatenated. And they're passed through a Learnable Projection Matrix, W-O. Which combines the information from the different heads into a single representation. After the multi-head attention step, the output is passed through a feed-forward network, or FFN. This is a small neural network made up of two fully connected layers with a non-linear activation in between them, such as ReLU. And the purpose of this step is to transform the representations further and make the model more expressive. And like the attention step... Transformer uses a residual connection and layer normalization. This means the original input is added back to the output before applying normalization, and these techniques help stabilize training and make it easier to train deeper models. Overall, this step refines the node representations so they can capture more complex relationships in the data.
All right, so we've covered several architectures. And each of them uses the same core idea, message passing, but they have different approaches to how nodes aggregate information and how far they can look into the graph structure. So remember GCNs, smooth, graph sage, samples, graph attention networks, focus attention, and GINs maximize expressivity. And of course, graph transformers scale up to global reasoning. So that's the world of GNNs. Hopefully this introduction gives you a clear mental model for how they work and when to use them. Is there a specific GNN architecture you'd like to hear more about? Let us know down below. And if you learned something new today, make sure to like and subscribe for more content like this.