The World Is Not a Grid: Why Graphs Matter

The Prediction That Refused to Work

In the autumn of 2014, a data scientist I will call Maya sat in front of her laptop at a mid-sized e-commerce company in Berlin, staring at a confusion matrix that refused to improve. Her task seemed, on paper, to be the kind of thing a competent practitioner could solve in a week. Given the last ten purchases of a customer, a few demographic features pulled from the loyalty program, and the timestamp of the last visit, predict what the customer would buy next. She had cleaned the data, normalized the prices, one-hot encoded the categories, engineered time-since-last-purchase features, computed rolling averages, and fed the resulting matrix into a multilayer perceptron with two hidden layers, ReLU activations, dropout, and early stopping. The model trained. The loss went down. The validation accuracy plateaued at 61.4 percent, and no amount of hyperparameter tuning, weight decay, or extra hidden units would push it past that ceiling. Worse, the precision on her best category—repeat purchases of premium coffee—was so close to chance that her product manager politely asked, in a meeting that Maya still finds painful to recall, whether she was sure she had not accidentally swapped the labels.

The problem, as Maya would eventually realize in a long Sunday afternoon conversation with an older colleague, was not the model. It was not the features. It was not even the data, although the data had its own issues with sparsity and cold-start users. The problem was that Maya was throwing away the most informative signal in her dataset before her network ever saw it. Every customer existed inside a web of relationships: customers who bought the same products, products that were bought together, products that were viewed but not purchased, products that were returned, products that were later repurchased after a discount. Each customer was a node. Each relationship was an edge. The structure of that web—who was connected to whom, who was two hops away from whom, which communities overlapped, which products sat at the boundary between clusters—contained more predictive signal than any combination of demographic attributes she could engineer by hand. The multilayer perceptron could not see any of this because a multilayer perceptron does not have a concept of "two hops away." It only knows about the row it is looking at. Maya had reduced a graph to a table and then wondered why the table could not predict the graph.

She was not alone. The mistake she made is one of the most common, most expensive, and most instructive mistakes in modern machine learning, and it is the mistake this book is built around. We have been extraordinarily successful at building models for data that lives on grids. Images are grids of pixels. Audio is a one-dimensional grid of amplitudes. Text is a one-dimensional grid of tokens. For these modalities, we have convolutional networks, recurrent networks, transformers, and an entire zoo of architectures that exploit the regular structure of the grid. But most of the interesting phenomena in the world are not arranged on a grid. They are arranged in graphs. Molecules are graphs of atoms. Social networks are graphs of people. The web is a graph of pages. Citations are graphs of papers. Transactions are bipartite graphs of buyers and sellers. Diseases are graphs of symptoms and genes. Languages are graphs of words and meanings. Recommendation systems are graphs of users and items. Fraud detection is graph search. Drug discovery is graph generation. When we force this kind of data into a table and feed it to a model designed for a grid, we keep the values and discard the relationships. We keep the nodes and throw away the edges. We keep the pixels and lose the picture.

The central claim of this book is that the edges are not optional decoration. They are the signal. And learning to use them well is one of the deepest, most rewarding problems in contemporary AI.

Why a Grid Is a Special Kind of Graph (and Why That Matters)

To understand why graphs need their own machinery, it helps to start from the grids we already know how to handle. An image is a graph in a trivial sense: each pixel is a node, and each pixel is connected to its immediate neighbors in a regular lattice. A sentence is also a graph: each word is a node, and the words are connected in a chain that respects temporal order. The reason convolutional and recurrent networks work so well on these modalities is not that grids are easy. It is that grids have very specific structural regularities that we can hard-code into the architecture, and that hard-coding saves us enormous amounts of data and compute.

Consider a 224-by-224 RGB image. Every pixel has exactly eight neighbors, or fewer near the boundary. The neighbors of one pixel look exactly like the neighbors of any other pixel, up to position. The notion of "above," "below," "left," and "right" is globally consistent. If I tell you the value of pixel (50, 50), you already know the relative coordinates of every other pixel in the image, because the coordinate system is shared. A convolutional kernel exploits this regularity directly: the same small set of weights slides across the entire image, and the meaning of those weights is preserved at every position. Translation invariance is not learned; it is built into the architecture. We do not need to teach the network that a cat looks like a cat whether it is in the upper-left corner or the lower-right; the convolutional structure guarantees it.

Sequences have similar regularity, just in one dimension. Every token has a left neighbor and a right neighbor, or fewer at the boundaries. The notion of "previous" and "next" is consistent. A recurrent kernel exploits this by maintaining a hidden state that gets updated in order, and a transformer exploits it by allowing every token to attend to every other token through positional encodings that preserve the same arithmetic relationships for every position in the sequence. The locality structure of sequences—tokens that are close in index tend to be semantically related—is something we can take for granted when designing the architecture.

Now imagine you are handed a graph that does not look like a grid at all. Suppose you are working with a citation network of machine learning papers, where each paper cites some subset of other papers. Paper A might cite three papers. Paper B might cite thirty. Paper C might cite zero. Some papers have a hundred references; some have a single one. There is no global notion of "above" or "below" or "neighbor" in any geometric sense. There is no fixed shape. There is no consistent ordering. The graph of one thousand papers and the graph of one million papers are not the same shape, and you cannot slide a 3-by-3 kernel across either of them because there is no notion of "the third row down." If you try to apply a convolutional kernel to a graph, what does "slide" even mean? If you try to apply a recurrent kernel, what does "next" mean? There is no sequence to walk through.

This is the fundamental mismatch that graph neural networks were invented to solve. They are not a tweak on top of convolutional or recurrent networks. They are a different family of architectures, designed around the actual symmetries and irregularities of relational data. The rest of this chapter is going to introduce you to that family from the ground up, beginning with the formal definition of a graph and ending with the three threads that will run through the rest of this book.

What Is a Graph, Really?

A graph $G = (V, E)$ is, at its most austere, two sets. $V$ is a set of vertices, sometimes called nodes. $E$ is a set of edges, where each edge is a pair of vertices. If the pair is ordered, the graph is directed. If unordered, the graph is undirected. That is the entire definition. Everything else—weights, features, types, attributes—is a decoration on this simple skeleton, and the