# Graph Neural Networks (GNNs), Simply Explained

#99 Apr 27 Architecture

https://www.aibutsimple.com/p/graph-neural-networks-gnns-simply-explained

Hello from the AI, but simple team! If you enjoy our content and custom visuals, consider sharing this newsletter with others or [upgrading](http://www.aibutsimple.com/pro?utm_source=newsletter.aibutsimple.com&utm_medium=referral&utm_campaign=graph-neural-networks-gnns-simply-explained) so we can keep doing what we do.

Traditional Neural Networks are reputable and well-integrated models used to process text, video, and image data.

Vectors are used as numerical inputs into neural networks, where each component takes the form of a single neuron in a network. The models themselves rely on inputs that are fixed in size and shape.

- A 224x224 image always has 224x224 pixels. A sentence can be padded to a fixed length. The structure is consistent, and that consistency is something traditional networks depend on.

However, traditional neural networks are ineffective for particular types of structure, which are found surprisingly often in our daily lives.

Consider a molecule. Or a social network. Or a city's road map.

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/73b98d31-c3f7-4ba3-9b60-17f4685f0b68/Graph_Neural_Networks_Examples__GNNs___3_.png)

These are graphs: collections of nodes (entities) and edges (relationships between them).

Molecules have varying numbers of atoms, and road networks look different in varying countries.

So, how do you feed something so irregular into a neural network?

Graphs can model the connection between two, three, or many different things all at once, but can we extend our understanding of their current state to train models to classify characteristics and even predict future connections?

As we'll see, the solution borrows a surprisingly familiar idea.

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/99b8f690-fece-43bc-abdb-8c89e5d235ea/Graph_Neural_Networks__ABS_APR_26__5_.png)

In this issue, we will provide a highly visual breakdown of how Graph Neural Networks (GNNs) operate on graph data and produce results that are newly useful for real-world applications.

### Neural Networks at a Glance

A standard neural network takes a vector of numbers, passes it through layers of learned weights, and produces an output. Each layer transforms the representation, extracting increasingly abstract features.

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/ed90058a-7819-417e-bde6-df7c709dcd6d/Graph_Neural_Networks__ABS_APR_26__6_.png)

[Convolutional Neural Networks (CNNs)](https://newsletter.aibutsimple.com/p/convolutional-neural-networks-explained-mathematically) extend this idea for images. Instead of connecting every pixel to every neuron, CNNs apply small filters (typically 3x3 or 5x5 grids of learned weights) that slide across the image and make a computation that involves all pixels in that filter.

This process is called a convolution. Each convolution detects a local pattern like an edge, a curve, or a texture.

What’s important to know is that the filter is applied the same way at every position.

This is called weight sharing, and it's what makes CNNs efficient: rather than learning a unique set of weights for every pixel, one filter learns a single pattern and detects it anywhere it appears.

A CNN convolution is really just asking, at each pixel, "What do my neighbors look like, and how do I combine that with what I know about myself?" That question, it turns out, translates almost directly to graphs.

### An Introduction To Graphs

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/7c9becd9-6695-460a-97f4-59c71ef1db8e/Graph_Neural_Networks__ABS_APR_26__3_.png)

A graph G is defined by a set of nodes V and edges E. Each node v carries a feature vector xv​, encoding information we know about that entity.

For instance, for a molecule, it might be the atom type and charge, or for a paper in a citation network, it might be the textual/bag-of-words representation of its abstract.

Edges may also carry an additional feature vector (euv), potentially representing something like the type of chemical bond (single, double, etc.).

We represent the graph's connectivity with an adjacency matrix A, where Avu = 1 if an edge exists between nodes v and u, and 0 otherwise.

From A, we can construct the degree matrix D, a diagonal matrix where each entry​ simply counts how many neighbors node v has.

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/05b2aeb7-4cd6-4a2f-ab9f-754f8bbc14b1/image.png)

From these two matrices, we obtain one of the most important objects in graph theory: the Graph Laplacian, L.

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/598dfb16-eb31-4b9a-b226-6808b62fdcfd/Graph_Neural_Networks__ABS_APR_26__7_.png)

This might look arbitrary, but the [Laplacian](https://en.wikipedia.org/wiki/Laplace_operator?utm_source=newsletter.aibutsimple.com&utm_medium=referral&utm_campaign=graph-neural-networks-gnns-simply-explained) is the same as the calculus operator you may know from multivariable calculus, which essentially aggregates the second derivative in each basis direction but in matrix form for the graph.

Just as the continuous Laplacian measures how a function differs from its local average, the graph Laplacian measures how a node's features differ from its neighbors'.

It encodes the contrast structure of the graph, substituting for the kind of information a convolutional filter would want.

The Laplacian is a theoretical element used to measure how different each node is from its neighbors. In modern implementation (Pytorch, etc.), we use message passing to capture those differences, intuitively transforming data layer-by-layer.

Message passing is essentially a learned generalization of Laplacian-based smoothing applied repeatedly:

- Gather: The node looks at its edges, then collects current feature vectors of all its neighbors.
- Aggregate: It averages, sums, or mathematically combines the neighbor vectors into one single vector.
- Update: The node takes its own current feature vector, combines it with the aggregated neighbor vector, and passes that combined data into an MLP.

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/2d145197-4f00-4413-a624-8f1251261f18/Graph_Neural_Networks__ABS_APR_26__8_.png)

### Turning Vertices Into Vectors

Just like NLP models initialize each word as a vector xv before any learning begins, GNNs initialize each node with its raw feature vector. We call this the hidden state, represented as hv.

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/0f8fc431-623b-46c4-8e74-2fd0668e2857/image.png)

From here, the network's job is to iteratively refine these representations by aggregating neighborhood information. Here’s an example of a standard graph convolutional network (GCN) or pooling approach, where we aggregate by averaging.

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/fb6f02af-c6c6-4a14-9bbd-d1218e4394d3/image.png)

The left-side sum collects the previous-layer embeddings of every neighbor of v and averages them, acting as an aggregation step.

That average is then linearly transformed by a learned weight matrix W, which is shared across all nodes in the layer (just like a CNN filter). Finally, the sigma is a non-linear function, such as the ReLU, which helps the function learn complex patterns.

Each K-th layer represents both the neighbor v’s individual features along with every node that is K-degrees of separation from v.

Think of it like information spreading through a social network. Two layers means information travels two edges deep; three layers, three edges, and so on.

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/167f5323-f3c2-48f5-b852-b37a67cb8946/Graph_Neural_Networks__ABS_APR_26__9_.png)

In practice, most GNNs perform best at just two or three layers. We'll revisit why this is the case in the open research section.

### Convolutions In GNNs

So how does the CNN analogy work mathematically? Recall that CNNs learn to filter through the pixels of an image. For graphs, we move to spectral space, the domain defined by the eigenvectors of the Laplacian.

The Laplacian L is a symmetric positive semi-definite matrix, so it has a full set of real eigenvectors. We can decompose it as follows:

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/b7dc459c-98ea-46f7-8525-c58fa2dee0ee/image.png)

Here, the columns of U are eigenvectors, and Lambda (Λ) is a diagonal matrix of eigenvalues. The eigenvectors with smaller eigenvalues capture smooth, global structure. Those with larger eigenvalues capture sharp, localized variation.

A spectral convolution with a filter looks like this:

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/bc55f8bd-8df4-45aa-8aaa-7482b9521943/image.png)

In this equation, the node features x are brought into spectral space by the matrix multiplication with UT .

We apply learned weights to each frequency component g(Λ), then transform the result back into the original feature basis by multiplying it with U. This is the graph equivalent of sliding a filter across an image.

The problem though, is that computing U for large graphs is expensive, since eigendecomposition has a cubic runtime complexity of O(n3).

This is where Chebyshev polynomials come in. Rather than computing the g (graph convolution) directly, we approximate the filter as a truncated polynomial:

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/7ff857ec-5841-4060-ba02-c9a2a66ae13d/image.png)

Here, Tk represents a matrix of the Chebyshev polynomials with the eigenvalues as inputs.

Chebyshev polynomials are particularly well-suited here because they minimize numerical instability. In other words, they don't "blow up" the way high-degree standard polynomials can.

The result is a filter that never explicitly computes eigenvectors, instead aggregating the K-layer neighborhood information directly through repeated sparse matrix multiplications.

---

### [Level Up Your Career With AI, But Simple PRO](https://www.aibutsimple.com/pro?utm_source=newsletter.aibutsimple.com&utm_medium=referral&utm_campaign=graph-neural-networks-gnns-simply-explained)

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/281697a8-c915-435c-a68b-43374b671698/aibutsimple_academy.png)

Supporting us by purchasing a PRO membership will get you:

- Exclusive Hands-on Tutorials With Code
- Real-World Interview Questions and Cases (From Real Companies)
- Full Math Explanations and Beautiful Visualizations
- Ad-Free Reading for an Uninterrupted Learning Experience

[Break Into AI With PRO](https://www.aibutsimple.com/pro?utm_source=newsletter.aibutsimple.com&utm_medium=referral&utm_campaign=graph-neural-networks-gnns-simply-explained)

---

### How Are GNNs Used?

The embeddings GNNs produce are flexible enough to support several task types, each operating at a different scale of the graph.

Node classification predicts a label for each individual node. A common example is a citation network like Cora, where each paper is a node and edges are citations.

The GNN learns to predict each paper's research field using both its content and who it cites.

Link prediction scores pairs of nodes for likely connections. Rather than classifying nodes, the model produces embeddings and asks, “Do these two nodes belong together?”

- Link prediction is used in recommendation engines on LinkedIn (e.g., suggested connections) and Netflix (e.g., movie recommendations).

Graph classification collapses an entire graph into a single embedding for prediction.

An impactful application here is molecular property prediction: given a molecule represented as a graph of atoms and bonds, can the GNN predict whether it's toxic, soluble, or likely to bind to a specific receptor?

![](https://media.beehiiv.com/cdn-cgi/image/fit=scale-down,width=1200,format=auto,onerror=redirect,quality=80/uploads/asset/file/679f1b03-8d4d-41b5-9047-2b6e4e28ec36/Graph_Neural_Networks__ABS_APR_26__10_.png)

This has accelerated drug discovery pipelines considerably, replacing expensive lab experiments with fast model inference as a first-pass filter.

Beyond these three core tasks, GNNs have found traction in traffic forecasting (predicting congestion), fraud detection (transaction networks), and physics simulation (particles as nodes, interactions as edges).

The latter is being used by [DeepMind](https://arxiv.org/abs/2002.09405?utm_source=newsletter.aibutsimple.com&utm_medium=referral&utm_campaign=graph-neural-networks-gnns-simply-explained) to simulate fluid dynamics and rigid body physics with a physical computation speed advantage compared with traditional solvers.

### Open Research Areas

GNNs still have open problems worth knowing about.

[Over-smoothing](https://arxiv.org/abs/2303.10993?utm_source=newsletter.aibutsimple.com&utm_medium=referral&utm_campaign=graph-neural-networks-gnns-simply-explained) is perhaps the most well-documented: as shown in recent benchmarks, adding more layers beyond two or three tends to hurt performance, because repeated aggregation can wash out the distinctions between nodes.

[Expressivity limits](https://arxiv.org/abs/2603.14846?utm_source=newsletter.aibutsimple.com&utm_medium=referral&utm_campaign=graph-neural-networks-gnns-simply-explained) are a more theoretical concern. It turns out that standard GNNs are at most as powerful as the Weisfeiler-Lehman (WL) graph isomorphism test, a classical algorithm for determining whether two graphs are structurally identical.

- This means there exist pairs of structurally different graphs that a GNN cannot distinguish, no matter how it's trained. Higher-order GNNs that consider subgraph structures can exceed this limit, but at significant computational cost.

Scalability also remains an open engineering challenge. Full-graph message passing requires loading the entire adjacency matrix into memory, which is infeasible for billion-node graphs like Facebook's social network.

Finding the right tradeoff between compute power and accuracy is an active area of research.

### The Bottom Line

What CNNs do for pixels, GNNs do for nodes: aggregate local neighborhood information through learned filters, iteratively build richer representations, and do so in a way that's invariant to the arbitrary ordering of inputs.

The Graph Laplacian formalizes what "neighborhood" means, spectral convolutions define what "filtering" means, and Chebyshev polynomials make the whole thing tractable at scale.

Graphs are everywhere, and GNNs are finally giving us the tools to learn from them.

---

Here’s a special thanks to our [biggest supporters](https://www.aibutsimple.com/upgrade?utm_source=newsletter.aibutsimple.com&utm_medium=referral&utm_campaign=graph-neural-networks-gnns-simply-explained):

- Sushant Waidande
- Sai Krishna Pashapu (AI Developer, BTech, [LinkedIn](https://www.linkedin.com/in/sai-krishna-pashapu-997358283/?utm_source=newsletter.aibutsimple.com&utm_medium=referral&utm_campaign=graph-neural-networks-gnns-simply-explained), [Github](https://github.com/saikrishna-pashapu?utm_source=newsletter.aibutsimple.com&utm_medium=referral&utm_campaign=graph-neural-networks-gnns-simply-explained))
- Bob Boncella
- Demet Yazici

---

If you enjoy our content, consider supporting us so we can keep doing what we do. Please share this with a friend!

Want to reach 50000+ ML engineers? Let’s work together:

[WORK WITH US 📈](https://tally.so/r/A7Dgdk?utm_source=newsletter.aibutsimple.com&utm_medium=referral&utm_campaign=graph-neural-networks-gnns-simply-explained)

Feedback or inquiries? Send us an email at [edwin@aibutsimple.com](mailto:edwin@aibutsimple.com).

---

That’s it for this week’s issue of AI, but simple. See you next week!

—AI, but simple team