Introduction to Graph Neural Networks

A puzzle you can solve without a computer

Look at this small group of five friends: A, B, C, D and E. Each of them has rated how much they enjoy watching cricket highlights, on a scale of 0 to 10. A scores 8, B scores 6, C scores 4, and E scores 9. But D never filled in the survey — you don't know D's score. What you do know is who is friends with whom: A, B and C are all direct friends of D, and C also happens to be friends with E (but D and E have never met).

Before reading further, make a guess: what would you estimate D's cricket-interest score to be? Most people instinctively look at D's direct friends — A, B and C — and average their scores, ignoring E, because E isn't directly connected to D at all. That instinct, "estimate an unknown value by combining information from directly connected neighbours," is the entire idea behind a Graph Neural Network (GNN). Everything in this chapter is that one idea, made precise, written as code, and then made powerful enough to be useful for real prediction problems on networks — social networks, road networks, molecules, and more.

What exactly is a graph, in programming terms?

You have already met graphs as a data structure: a graph is a set of nodes (also called vertices) and a set of edges connecting pairs of nodes. A city's metro map is a graph — stations are nodes, and a direct line segment between two stations is an edge. If you have studied the Delhi Metro or any similar network, you already know that some stations connect directly to three or four others, while some connect to only one. Graphs are rarely as tidy as a grid; the number of neighbours a node has (its degree) varies wildly from node to node.

In code, the most common way to represent a graph is an adjacency list: a dictionary where each key is a node, and its value is the list of nodes it connects to.

graph = {
    "A": ["D"],
    "B": ["D"],
    "C": ["D", "E"],
    "D": ["A", "B", "C"],
    "E": ["C"]
}

for node in graph:
    print(node, "has", len(graph[node]), "neighbour(s):", graph[node])

Tracing this by hand: Python dictionaries preserve the order in which keys were inserted, so the loop visits A, B, C, D, E in that order. For A, graph["A"] is ["D"], a list of length 1, so the line prints A has 1 neighbour(s): ['D']. The same logic gives B has 1 neighbour(s): ['D'], then C has 2 neighbour(s): ['D', 'E'], then D has 3 neighbour(s): ['A', 'B', 'C'], and finally E has 1 neighbour(s): ['C']. Notice this graph is the same friend network from the opening puzzle. This adjacency-list representation, plus a numeric "feature" attached to each node (D's cricket score, for instance), is all the raw material a GNN needs.

The core idea: message passing

A GNN updates every node's value by having each node collect information from its direct neighbours and combine it. This process is called message passing, and one round of it is called a layer. The simplest way to combine neighbour information is to take their mean (average). Written as a formula, for a node v with neighbour set N(v) and each neighbour u holding a value h(u), the new value for v is:

new_h(v) = ( sum of h(u) for every u in N(v) ) / (number of neighbours of v)

Let's apply this to D. D's neighbours are A, B and C, with scores 8, 6 and 4. So:

new_h(D) = (8 + 6 + 4) / 3 = 18 / 3 = 6

D's estimated cricket-interest score after one message-passing layer is 6. Notice that E's score of 9 played no role at all — E is not a direct neighbour of D, so its information hasn't reached D yet. The diagram below shows this exact calculation.

Writing message passing as code

The formula above translates directly into a short Python function. We store each node's current value in a dictionary, using None for D's unknown score:

graph = {
    "A": ["D"],
    "B": ["D"],
    "C": ["D", "E"],
    "D": ["A", "B", "C"],
    "E": ["C"]
}
features = {"A": 8, "B": 6, "C": 4, "D": None, "E": 9}

def aggregate_neighbours(graph, features, node):
    neighbour_values = [features[n] for n in graph[node] if features[n] is not None]
    if not neighbour_values:
        return features[node]
    return sum(neighbour_values) / len(neighbour_values)

new_D = aggregate_neighbours(graph, features, "D")
print("new score for D:", new_D)

Tracing this: graph["D"] is ["A", "B", "C"], so the list comprehension collects features["A"], features["B"] and features["C"], giving [8, 6, 4] (none of them are None, so nothing is filtered out). The list is non-empty, so the function returns sum([8, 6, 4]) / len([8, 6, 4]), which is 18 / 3 = 6.0. The program prints new score for D: 6.0, matching our hand calculation exactly.

Real GNN code updates every node in one pass, not just D. There is one subtle but important rule: every node's new value must be computed from the old snapshot of features, and only afterwards do all the new values get written back together. If we updated nodes one at a time and let later nodes read already-updated values, the result would depend on the order we happened to loop through the dictionary — which makes no sense, since a graph has no built-in "first" node. Here is a full layer done correctly:

old_features = dict(features)  # snapshot before this layer
new_features = {}

for node in graph:
    new_features[node] = aggregate_neighbours(graph, old_features, node)

print(new_features)

Trace it node by node, always reading from old_features: A's only neighbour is D, and old_features["D"] is None, so it gets filtered out, leaving an empty list — the function falls back to returning A's own old value, 8. B works the same way and stays 6. C's neighbours are D and E; D is filtered out (its value is None), leaving just E's value 9, so C becomes 9.0. D's neighbours are A, B, C with values 8, 6, 4, giving 18/3 = 6.0 as before. E's only neighbour is C, whose old value was 4, so E becomes 4.0. The final printed dictionary is {'A': 8, 'B': 6, 'C': 9.0, 'D': 6.0, 'E': 4.0}.

Look closely at what happened to C: it jumped from 4 to 9.0 because it directly absorbed E's high score. D, meanwhile, still knows nothing about E, because E is two hops away and this was only one layer of message passing. This is the key limitation — and the key lever — of GNNs: one layer only reaches one hop.

Stacking layers: how far can information travel?

To let D find out about E indirectly, we run a second layer, using the results of the first layer as the new starting values. After layer 1, A = 8, B = 6, C = 9.0 (updated!), D = 6.0, E = 4.0. Running the same aggregation again for D:

new_D_layer2 = (8 + 6 + 9.0) / 3 = 23 / 3 ≈ 7.67

D's value shifted from 6.0 up to about 7.67 — noticeably higher — purely because C had already picked up a signal from E in the previous layer, and that signal now flows one hop further, into D. This is the general pattern: after k layers of message passing, a node's value has been influenced by every other node that is within k hops of it, and no farther. Stacking layers is how a GNN reaches further out into the graph — exactly like stacking more BFS levels lets a breadth-first search reach nodes farther from the start.

Real GNN layers add one more ingredient beyond plain averaging: a set of learnable weights. You may already know that a single artificial neuron computes w · x + b (multiply the input by a weight, add a bias) and then passes the result through a non-linear function. A GNN layer does the same thing to the aggregated neighbour value:

new_h(v) = activation( W * mean(h(u) for u in N(v)) + b )

Here W and b are numbers (or, for richer features, small matrices) that the network learns from training data, exactly as an ordinary neural network learns its weights — by comparing predictions to correct answers and adjusting. The aggregation step (mean, in our examples) decides which information a node sees; the weights and activation decide how the network transforms that information. Both pieces are trained together.

Why can't a normal neural network just do this?

It's a fair question: why not just feed D's neighbours' scores into a regular neural network (the kind that takes a fixed-size list of numbers, like an MLP)? Two problems arise immediately. First, a fixed-size input assumes every node has the same number of neighbours — but in our graph A has 1 neighbour, C has 2, and in a real social network some people have 5 friends and others have 500. An MLP with, say, 500 input slots would need to pad A's input with 499 fake zero-neighbours, and the network would have to somehow learn to ignore them, which is wasteful and error-prone.

Second, and more subtle, is order. A graph's neighbour list has no natural sequence — D's neighbours are the set {A, B, C}, not the ordered list [A, B, C]. If we fed neighbour values into an MLP by concatenating them into fixed positions (slot 1, slot 2, slot 3), then listing them as [8, 6, 4] versus [4, 8, 6] would produce two different outputs from the same underlying friendship — which is nonsensical, since nothing about D's real-world situation changed. A GNN avoids this by using an aggregation function like mean or sum, which is mathematically guaranteed to give the same answer no matter what order you add the numbers in. This property is called permutation invariance, and it is the real reason GNNs use aggregation instead of concatenation.

This also explains why a Convolutional Neural Network (CNN), which is excellent at images, doesn't directly apply either. A CNN's convolution filter relies on every pixel having exactly the same neighbourhood shape — up, down, left, right, and diagonals, always in the same fixed positions relative to the centre pixel. A graph has no such regular grid: node degrees vary, and there is no consistent notion of "the neighbour above" or "the neighbour to the left." A GNN can be seen as generalising the idea of convolution — "combine information from nearby positions" — to structures where "nearby" doesn't follow a grid at all.

A common misconception, corrected

A mistake many learners make when first meeting GNNs is thinking: "A GNN just flattens the entire graph into one big list of numbers, the way we flatten an image into pixel values, and feeds that list into a regular neural network." This is incorrect, and it's worth being precise about why. Flattening requires deciding on a fixed order and a fixed maximum size in advance — but graphs in the real world vary enormously in size (a friend group of 5 people versus a social network of 5 million people) and have no natural ordering of their nodes. If you flattened a graph, you would also throw away the very thing that makes it a graph — which nodes are connected to which — unless you separately fed in the entire adjacency structure as more numbers, which defeats the purpose.

What a GNN actually does is fundamentally local and structural: each node runs the same small calculation (aggregate-then-transform), using only its own direct neighbours, and this calculation works correctly no matter how large the overall graph is or how it happens to be numbered. The graph's structure isn't an extra input alongside the features — it is the computation graph along which information flows. That is the core design idea that separates GNNs from ordinary neural networks, and it's why they can be applied to a 5-node friend graph and a 5-million-node network using the exact same code.

A second, related caution worth knowing: it is tempting to assume "more layers must mean a smarter GNN," since more layers reach more hops. In practice, researchers have found that stacking too many layers can cause a problem called over-smoothing, where, after enough rounds of averaging, every node's value drifts toward the same overall graph average and nodes become hard to tell apart — the opposite of useful. This is why real GNNs are usually kept to a small, carefully chosen number of layers (often just 2 to 4) rather than as many as possible.

Where this kind of model is actually used

Graph-shaped data is everywhere once you start looking for it, and the CS ideas you already have — adjacency lists, BFS/DFS traversal, degree of a node — are exactly the foundation GNNs build on. A few areas where nodes-and-edges thinking, combined with learned aggregation, has been genuinely useful:

• Molecules, for drug and materials research: an atom is a node, a chemical bond is an edge, and a GNN aggregates information across bonded atoms to predict properties like solubility or reactivity before anyone runs a physical experiment.
• Road-network travel-time prediction: researchers at Google have described representing road segments and intersections as a graph and using graph neural networks to improve estimated-time-of-arrival predictions in mapping software, since travel time on one road segment genuinely depends on conditions on the segments connected to it.
• Any social or transaction network: wherever you can model people, accounts, or entities as nodes and their relationships as edges — such as a friend network, a citation network of research papers, or the route map of the Indian Railways — the same message-passing idea could, in principle, be used to estimate unknown information about a node from what its connections reveal, exactly like our five-friend cricket example.

Notice the common thread: in every case, the thing being predicted about an entity depends heavily on the entities it's directly connected to — which is precisely the assumption message passing is built on.

Check your understanding

Work through these before checking the answers below. They use the same aggregate-then-average rule from this chapter.

1. Node P is connected to four neighbours with scores 10, 4, 4 and 6. What is P's value after one mean-aggregation layer?
2. If you listed P's neighbours in a different order — say 4, 4, 10, 6 instead of 10, 4, 4, 6 — would the aggregated result change? Explain why, using the term "permutation invariance."
3. True or False: "A trained GNN can only be used on graphs that have exactly the same number of nodes as the graph it was trained on, similar to how an image classifier expects a fixed image size." Justify your answer.
4. In our worked A–B–C–D–E example, after layer 1 the values were A=8, B=6, C=9.0, D=6.0, E=4.0. Compute E's value after a second layer of mean-aggregation (E's only neighbour is C).

Answers: (1) (10 + 4 + 4 + 6) / 4 = 24 / 4 = 6. (2) No — addition and division don't care about the order their inputs arrive in (10+4+4+6 gives the same total as 4+4+10+6), so mean-aggregation is permutation invariant: the result depends only on the set of neighbour values, never their order, which correctly matches the fact that a graph's neighbours have no inherent ordering. (3) False — this is exactly the misconception this chapter warned about. Each node's update only ever looks at its own local neighbourhood, so the same aggregation rule applies unchanged whether the graph has 5 nodes or 5 million; there is no fixed-size requirement. (4) E's only neighbour after layer 1 is C, whose layer-1 value was 9.0, so new_E = 9.0 / 1 = 9.0 — E's value stays at C's updated score, since a node with a single neighbour simply inherits that neighbour's value under mean aggregation.

Summary

• A graph is nodes plus edges; in code it's commonly stored as an adjacency list (a dictionary from each node to its list of neighbours), the same representation used for BFS/DFS.
• A Graph Neural Network updates each node's value through message passing: aggregate values from direct neighbours, then transform the result — repeated for one or more layers.
• Mean (or sum) aggregation is used specifically because it is permutation invariant — the answer doesn't depend on the order neighbours are listed in, which correctly matches how graphs actually work.
• One layer only reaches nodes one hop away; stacking k layers lets information travel k hops, but stacking too many layers risks over-smoothing, where node values blur together.
• Ordinary neural networks (MLPs) and CNNs assume fixed-size, fixed-order, or grid-shaped input, which real graphs don't provide — this is precisely the gap GNNs are designed to fill.
• The misconception to avoid: a GNN does not flatten a whole graph into one input vector; it runs the same small local computation at every node, using the graph's structure as the path along which information actually flows.

Think About It

Think about this: How would you explain introduction to graph neural networks to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.