Graph Neural Networks: Learning on Graphs

Every time someone sends money using UPI, through PhonePe, Google Pay, Paytm, or any of the apps built on India's Unified Payments Interface (launched by the National Payments Corporation of India, or NPCI, in 2016), a new link is added to an enormous, invisible network. The two bank accounts involved are the endpoints; the transaction between them is the connection. Multiply this by the billions of transactions UPI now handles every month, and what you get is not a spreadsheet of independent rows. It is one sprawling structure of hundreds of millions of accounts, tied together by an ever-growing web of who paid whom.

Now suppose a bank's fraud team needs to catch a "mule account": an account used to quietly move stolen money from a scam victim to a cash-out point, one hop removed from the person actually behind the scam. Looked at on its own, a mule account can look completely unremarkable: a modest balance, transaction sizes that trigger no threshold, a few months of history. Nothing in its own record says fraud. What gives it away is not what the account is, but who it is connected to: a cluster of unrelated victims feeding money in, and a small number of already-flagged accounts pulling money out soon after. That pattern lives entirely in the shape of the network around the account, not in the account's own features.

This is exactly the kind of problem graph neural networks (GNNs) are built to solve: making predictions about data where the relationships between items carry as much signal as the items themselves. Over the rest of this chapter we build up, step by step, how a neural network learns to "read" a network. We will use one small five-account UPI example throughout, tracing every number by hand and then confirming the arithmetic in code.

Representing a Network as Data

A graph is a structure made of nodes (or vertices) and edges, where each edge connects a pair of nodes. You have already met graphs as a data structure (adjacency lists, breadth-first search), but this chapter needs the exact notation used across GNN research, so it is worth re-establishing it here.

Take five UPI accounts, labelled P through T, with five transactions between them: P–Q, P–R, Q–R, R–S, and S–T. Accounts P, Q, and R transact with each other constantly, forming a tight triangle; R also transacts with S, and S with T, trailing off from that triangle like a chain. This structure is usually stored as an adjacency matrix, an N × N grid (N = number of nodes) whose entry is 1 if the row-node and column-node are connected, and 0 otherwise:

       P   Q   R   S   T
   P [ 0,  1,  1,  0,  0 ]
   Q [ 1,  0,  1,  0,  0 ]
   R [ 1,  1,  0,  1,  0 ]
   S [ 0,  0,  1,  0,  1 ]
   T [ 0,  0,  0,  1,  0 ]

Alongside the adjacency matrix, every node carries its own feature vector: the raw signals we already have about it, before the graph is used at all. For our accounts, say each one is described by two flags a bank might realistically log: whether it was involved in an unusually large transaction recently, and whether it was opened in the last 30 days.

Account   large_txn_flag   new_account_flag
   P            1                1
   Q            1                1
   R            0                0
   S            0                0
   T            0                0

P and Q are already flagged on their own features. R, S, and T are not; all three read as clean, identical [0, 0] rows. If a bank's model only ever looked at these two columns, it would treat R, S, and T as equally low-risk. But R sits directly beside two flagged accounts, S is two hops from those same flagged accounts, and T is three hops from them. The rest of this chapter is about a network that can tell the three apart, using nothing but the graph structure.

Why an Ordinary Neural Network or a CNN Won't Work Here

You have already used two kinds of networks built for structured input: a plain feed-forward network (MLP) for fixed-length feature vectors, and a convolutional network (CNN) for images. Both assume a very regular shape for their input, and a graph like the one above breaks that assumption in two distinct ways.

First, an MLP needs a fixed-length input vector, with a fixed, meaningful order to its entries. A graph has neither. One UPI subgraph might involve 5 accounts, another 50,000. Even for a fixed set of accounts, there is no natural order to list them in: account "P" is not inherently first, it is just the label we happened to choose. If you relabelled every account tomorrow (call P "account 9" and R "account 2"), the underlying network of who-pays-whom would not have changed at all, so a correct model's predictions must not change either. A model with this property is called permutation invariant (or, when it must produce one output per node rather than a single graph-level output, permutation equivariant: relabel the nodes, and the outputs simply relabel the same way, without changing in value). Feeding a flattened adjacency matrix straight into an MLP violates this immediately, since the MLP would learn to associate meaning with specific row and column positions that are really just an arbitrary bookkeeping choice.

Second, a CNN's convolution filter assumes every position has the same fixed pattern of neighbors: a pixel always has up to eight neighbors, always in the same relative positions, which is exactly what lets one small filter slide across the whole image and reuse its weights everywhere. In a graph, the number of neighbors a node has (its degree) varies enormously and unpredictably. In our example, T has one neighbor and R has three; in the real UPI graph, a personal account might have a handful of connections while a large merchant's payment gateway has millions. There is no fixed-size window to slide a filter over.

What we need instead is a building block that works with however many neighbors a node happens to have, does not care what order those neighbors are listed in, and still reuses the same learned parameters everywhere, so that the model both fits on a computer and generalizes to graphs of a different size than the ones it trained on.

The Core Idea: Message Passing

The mechanism that satisfies all three requirements is called message passing, and its logic is close to how information actually spreads through a social or transaction network: your own state is updated based on what your immediate connections currently look like.

Every node v starts with a feature vector, its layer-0 embedding, written h_v^(0). This is simply its raw input features. Each subsequent layer updates every node's embedding using two steps:

• Aggregate: collect the current embeddings of v's neighbors (written N(v)) and combine them with a function that does not depend on the order they are listed in. A sum, a mean, or an element-wise maximum all qualify, because reordering the numbers you are adding, averaging, or comparing never changes the result. Concatenating the neighbor vectors in list order would not qualify, since a different listing order would produce a different concatenated vector even though the neighborhood itself hadn't changed.
• Update: combine that aggregated neighbor signal with the node's own previous embedding, typically through a learned weight matrix and a non-linearity, exactly like one layer of any neural network you have already built.

Written as a single equation, one message-passing layer is:

h_v^(l+1) = UPDATE( h_v^(l), AGGREGATE({ h_u^(l) : u in N(v) }) )

Stack L of these layers, and a node's final embedding has absorbed information from every node within L hops along the graph, its receptive field, growing outward one hop per layer, the same way stacking convolutional layers grows a CNN's receptive field one pixel-neighborhood at a time. Because the same AGGREGATE and UPDATE functions, with the same learned weights, run at every node, the model is reused across the whole graph rather than storing separate parameters per node. It is the same weight-sharing trick a CNN uses across pixel positions and an RNN uses across time steps, applied here across nodes instead.

Two Concrete Recipes: GCN and GraphSAGE

"AGGREGATE" and "UPDATE" are placeholders; real architectures fill them in differently. Two of the most influential choices:

The Graph Convolutional Network (GCN), introduced by Thomas Kipf and Max Welling in 2017, aggregates neighbors through a degree-weighted average rather than a plain mean, so that a node with thousands of connections does not silently dominate a node with two. Applied to an entire graph at once, its layer rule is:

H^(l+1) = sigma( D_tilde^(-1/2) . A_tilde . D_tilde^(-1/2) . H^(l) . W^(l) )

Here H^(l) is the matrix of every node's layer-l embedding (one row per node), W^(l) is a learned weight matrix shared by every node, sigma is a non-linearity such as ReLU, A_tilde is the adjacency matrix with a self-loop added to every node (A + I, so a node's own previous embedding is included in its own average), and D_tilde is the corresponding degree matrix, a diagonal matrix recording each node's degree after the self-loops are added, used to normalize the averaging by degree on both sides.

GraphSAGE, introduced by William Hamilton, Rex Ying, and Jure Leskovec in 2017 (the name is short for "sample and aggregate"), keeps the self- and neighbor-terms separate instead of folding them into one normalized matrix, and typically aggregates with a plain mean:

h_v^(l+1) = sigma( W_self . h_v^(l)  +  W_neigh . mean( h_u^(l) for u in N(v) ) )

GraphSAGE adds one more idea that matters at real-world scale: instead of aggregating over every single neighbor a node has, it randomly samples a fixed-size subset of neighbors at each layer. On a graph the size of India's UPI network, a large payment gateway could have millions of edges; sampling trades a small amount of noise for the ability to train at all. This also makes GraphSAGE inductive: because it learns a general aggregation rule rather than memorizing a fixed graph, it can compute an embedding for an account that joined UPI five minutes ago, something a model trained only to operate on one fixed, unchanging adjacency matrix cannot do without retraining.

Worked Example: Spotting the Account That Doesn't Look Suspicious Alone

We now trace one full message-passing layer over the five-account graph, by hand. To keep the arithmetic transparent, use the GraphSAGE-style rule with the self- and neighbor-weight matrices both set to the identity matrix and no bias, so the update is simply "add the neighbor mean to your own features, then apply ReLU." (In a trained network these weight matrices are learned by backpropagation, the same way every weight in every network you have built so far is learned; here we fix them to the simplest possible value so the aggregation step itself is visible.)

h_v^(1) = ReLU( h_v^(0) + mean_{u in N(v)} h_u^(0) )

Work through node R in full. Its neighbors are N(R) = {P, Q, S}. Their layer-0 features are [1, 1], [1, 1], and [0, 0]. The mean is:

mean = ( [1,1] + [1,1] + [0,0] ) / 3 = [2/3, 2/3] = [0.667, 0.667]

Add R's own features, [0, 0], and apply ReLU (which leaves these non-negative numbers unchanged):

h_R^(1) = ReLU( [0,0] + [0.667,0.667] ) = [0.667, 0.667]

Running the identical rule at every node gives:

Account   h_v^(1)
   P      [1.50, 1.50]
   Q      [1.50, 1.50]
   R      [0.67, 0.67]
   S      [0.00, 0.00]
   T      [0.00, 0.00]

Compare this to the raw features. P and Q, already flagged, reinforce each other and grow. S and T are completely unchanged after this single layer: S is two hops from the flagged pair and T is three, but one layer of message passing only reaches as far as a node's immediate, one-hop neighbors, and at layer 0 neither of S's neighbors (R, T) nor T's neighbor (S) carried any signal yet. R is the interesting case: its own raw features never changed, and yet its embedding jumped from [0, 0] to [0.67, 0.67], clearly separating it from S and T even though all three started out numerically identical. One layer of message passing has encoded exactly the fact that mattered, that R sits directly beside two flagged accounts, without a human ever writing a rule for it.

Feed h^(1) back through the same layer to get h^(2), and the pattern keeps propagating outward exactly as far as you would expect. S, two hops from the flagged pair, first moves off zero at layer 2: it becomes [0.33, 0.33], because it now aggregates R's already-updated layer-1 embedding, which carries a trace of P and Q, rather than R's original all-zero layer-0 vector. T, three hops away, is still exactly [0, 0] after two layers, and only shifts to [0.33, 0.33] once a third layer lets the signal travel the full distance. Each additional layer extends the receptive field by exactly one more hop, visible here in the literal numbers.

It is also worth noticing that the numbers keep climbing rather than settling: P moves from 1.50 to 2.58 to 4.71 across three layers. That is a direct consequence of the simplified rule used here, which sums a full, unnormalized neighbor mean into each node every layer with nothing to keep the scale in check. It is exactly why the real GCN formula from the previous section divides through by degree on both sides (the D_tilde^(-1/2) terms): without that normalization, embeddings in a well-connected neighborhood grow without bound as more layers are stacked.

From Hand-Traced Numbers to Code

The following NumPy implementation performs exactly the computation above. Running it reproduces the layer-1 table verbatim, a useful way to check your own hand arithmetic on any graph.

import numpy as np
np.set_printoptions(precision=4, suppress=True)

nodes = ["P", "Q", "R", "S", "T"]

# Node features: [large_txn_flag, new_account_flag]
H0 = np.array([
    [1.0, 1.0],   # P
    [1.0, 1.0],   # Q
    [0.0, 0.0],   # R
    [0.0, 0.0],   # S
    [0.0, 0.0],   # T
])

# Adjacency list: P-Q, P-R, Q-R, R-S, S-T
neighbors = {
    0: [1, 2],     # P's neighbors: Q, R
    1: [0, 2],     # Q's neighbors: P, R
    2: [0, 1, 3],  # R's neighbors: P, Q, S
    3: [2, 4],     # S's neighbors: R, T
    4: [3],        # T's neighbor:  S
}

def gnn_layer(H, neighbors):
    """One round of mean-aggregation message passing (identity weights)."""
    H_new = np.zeros_like(H)
    for v, neighs in neighbors.items():
        agg = H[neighs].mean(axis=0)   # AGGREGATE: mean of neighbor features
        z = H[v] + agg                  # UPDATE: combine with own features
        H_new[v] = np.maximum(z, 0)     # ReLU
    return H_new

H1 = gnn_layer(H0, neighbors)
for name, vec in zip(nodes, H1):
    print(f"{name}: {vec}")

This prints P: [1.5 1.5], Q: [1.5 1.5], R: [0.6667 0.6667], S: [0. 0.], T: [0. 0.], matching the hand-traced table exactly. Calling gnn_layer again on H1, and again on the result, reproduces the layer-2 and layer-3 numbers from the previous section. A production GNN replaces the identity weights with real trainable matrices, replaces this Python loop with a single matrix multiplication for speed, and trains W by backpropagating a loss computed on the handful of accounts a bank already knows are fraudulent. But mechanically, the loop above is exactly what each layer computes.

Letting the Network Decide Which Neighbor Matters More

Averaging treats every neighbor equally, which is not always right: R's connection to a heavily flagged account probably ought to count for more than its connection to a quiet one. Graph Attention Networks (GAT), introduced by Petar Veličković and coauthors (including Yoshua Bengio) in 2018, replace the plain mean with a learned, per-edge weight. For each edge between node v and neighbor u, a small learnable function scores how much attention v should pay to u, those scores are normalized with a softmax across all of v's neighbors (so they sum to 1), and the aggregation becomes a weighted average using those attention scores instead of equal weights. Several attention "heads" are typically learned in parallel, each free to focus on a different notion of relevance, and their results are combined. The appeal for a fraud graph is direct: the model can learn, from data, that an edge to a previously flagged account should be weighted far more heavily than an edge to an ordinary one, rather than treating both edges identically as a plain mean does.

What You Can Actually Predict on a Graph

Everything above produces per-node embeddings, h_v, after L layers. What you do with them depends on the task:

• Node classification — predict a label for each node, such as fraudulent or not-fraudulent for each account, using its final embedding as input to an ordinary classifier (even a single extra layer with a sigmoid). This is the task in our worked example, and it was also the original motivating task for the GCN paper, which classified scientific papers by research topic using a citation network of roughly 2,700 papers (the Cora dataset), where an edge means one paper cited another.
• Link prediction — predict whether an edge should exist between two nodes that are not currently connected, or is likely to appear in future. Recommending a product to a shopper, or a new contact to follow, can be framed this way: represent shoppers and products as two kinds of nodes in one graph, with an edge whenever a shopper buys or clicks a product, and predict which currently-missing edges are likely.
• Graph classification — predict one label for an entire graph, by pooling (summing, averaging, or max-ing) every node's final embedding into a single graph-level vector. A molecule is naturally a graph (atoms as nodes, chemical bonds as edges), and graph classification over molecule graphs is used to predict properties such as toxicity or solubility, screening candidate compounds before any lab work happens.

Where This Is Already Working

Graph neural networks are not a laboratory curiosity. Pinterest's recommendation system, PinSAGE, is a GraphSAGE-style network running over a graph of billions of pins and boards, described in a 2018 paper by Rex Ying and coauthors at Pinterest and Stanford. It was one of the first published examples of a GNN running in production at web scale. In 2020, Google and DeepMind reported that a graph neural network (treating road intersections as nodes and road segments as edges) improved the accuracy of estimated arrival times in Google Maps. The general message-passing framework used throughout this chapter was formalized in 2017 by Justin Gilmer and coauthors at Google, specifically to predict quantum-chemical properties of molecules, and graph-based models remain widely used in drug discovery for exactly that reason. Closer to our opening example, banks and payment companies increasingly build graph-based models for fraud and money-laundering detection for the precise reason this chapter has demonstrated by hand: a coordinated ring of small, individually unremarkable accounts is only visible in the shape of the network around them.

The idea of a "graph neural network" is older than the current wave of results: Franco Scarselli and coauthors used the term and a related iterative propagation scheme as far back as 2009. What changed after 2017 was less the core idea than the arrival of formulations like GCN that could be trained efficiently with ordinary backpropagation on GPUs, at the same scale the rest of deep learning had already reached.

Two Real Limits

Two practical problems come up constantly when applying GNNs, and both appeared in disguise in the worked example above. The first is oversmoothing: stack too many plain graph-convolution layers, and repeatedly averaging every node with its neighbors behaves like repeatedly blurring a photograph. Each pass removes a little local detail, and after enough passes every node's embedding starts to look like every other node's, especially in a densely connected network where most nodes are only a few hops from most other nodes. Li, Han, and Wu demonstrated this formally in 2018, which is why most GCN and GAT models in practice use only two to four layers rather than the dozens common in image models. The second is scale: the real UPI network has orders of magnitude more nodes and edges than fit in memory as a dense adjacency matrix, and some nodes (a large merchant, a popular influencer account) have degrees in the millions. GraphSAGE's neighbor sampling, described earlier, is the standard answer: aggregate over a random subset of neighbors rather than all of them, and the resulting noise turns out to be a perfectly acceptable price for making training possible at all.

Back to the Fraud Team

Return to where this chapter started. A bank has confirmed fraud on only a handful of accounts (real-world labels are always scarce), and a vast, mostly-unlabelled transaction graph surrounds them. A node classifier trained on raw account features alone would never flag an account like R: its own numbers are perfectly ordinary. A graph neural network, trained by backpropagating a loss on just those few confirmed cases, learns an aggregation and update rule that gets reused at every node in the network, and that rule turns out to naturally raise the score of any account sitting one or two hops from known fraud: precisely the "guilt by association" signal a fraud team needs, computed automatically from the structure of who-paid-whom rather than hand-coded as a rule. That is the actual promise of learning on graphs: the moment your data has real relationships in it (accounts and transactions, atoms and bonds, papers and citations, shoppers and products), the connections themselves become something a network can learn from, not just the rows sitting at each end of them.

Think About It

Think about this: How would you explain graph neural networks: learning on graphs 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.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind graph neural networks: learning on graphs, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.