Graph Neural Networks: Learning on Non-Euclidean Data

Every month UPI clears billions of transactions across India. NPCI's fraud-analytics pipelines do not look at these transactions one at a time — they build a graph. Every bank account is a node; every transaction is a directed edge, weighted by amount and timestamp. A money-laundering "mule network" shows up in this graph as a distinctive shape: a small set of accounts that receive money from many sources and cycle it onward in a tight loop before it disappears into a withdrawal. A Graph Neural Network (GNN) scores each account by looking at its own transaction features and the features of the accounts it is connected to, several hops out — exactly the kind of pattern a row-by-row fraud model, which only ever sees one account's own statistics, cannot see at all.

A sibling chapter in this curriculum introduced the core idea of message passing — nodes exchange information with neighbors and update themselves. This chapter goes past the idea and into the machinery an engineer actually has to get right: the precise mathematical framework every message-passing GNN is built from, the attention mechanism that lets a GNN learn which neighbors matter, and the hard theoretical ceiling on what any such network can distinguish — a ceiling that, as you'll see worked out with real numbers, can quietly let a coordinated six-account fraud ring produce the exact same risk score as two unrelated three-account triangles.

The formal message-passing neural network framework

Gilmer, Schoenholz, Riley, Vinyals, and Dahl formalized message passing in "Neural Message Passing for Quantum Chemistry" (ICML 2017), originally to predict molecular properties from atom-bond graphs. Their framework, the Message Passing Neural Network (MPNN), decomposes every GNN layer into exactly three functions, and being precise about which function does what is what separates an engineer who can debug a GNN from one who can only call .fit() on it.

For a graph with node states h_v and edge features e_vw, layer t computes, for every node v:

message:   m_v^(t+1) = Σ_{w in N(v)}  M_t( h_v^t, h_w^t, e_vw )
update:    h_v^(t+1) =                U_t( h_v^t, m_v^(t+1) )
readout:   y_hat     =                R( { h_v^T | v in G } )

Message (M_t) is a learned function applied independently to each neighbor w of v, producing one vector per edge; these are then combined — almost always by sum, sometimes by mean or max — into a single aggregated message m_v. Update (U_t) is a second learned function, typically a small MLP or a GRU cell, that folds the aggregated message into the node's own previous state to produce its new state. Readout (R) runs only once, after the final layer T, and only if the task needs a single prediction for the whole graph (is this a fraud ring: yes/no) rather than one per node (is this specific account suspicious): it pools the full set of final node states into one graph-level vector.

This decomposition matters because "GCN," "GraphSAGE," and "GAT" are not three unrelated architectures — they are three different choices of M_t and U_t plugged into the identical three-step skeleton above. A GCN layer sets M_t(h_v,h_w,e_vw) = h_w / sqrt(deg(v)·deg(w)) (a fixed, degree-normalized copy of the neighbor's state) and U_t to a linear layer plus nonlinearity. GraphSAGE with mean aggregation sets M_t(h_v,h_w,e_vw) = h_w and concatenates the mean message with h_v before the update MLP. Neither lets the network decide that one neighbor matters more than another — every neighbor's message is weighted identically (by a fixed, structure-determined constant), regardless of what that neighbor's features actually say. That is the gap GAT closes.

def mpnn_layer(H, E, adjacency, message_fn, update_fn):
    # H: dict node_id -> feature vector h_v^t  (numpy arrays)
    # E: dict (u, v) -> edge feature e_uv        (optional, may be None)
    # adjacency: dict node_id -> list of neighbor node_ids
    H_next = {}
    for v in H:
        messages = [message_fn(H[v], H[w], E.get((v, w)))
                    for w in adjacency[v]]
        m_v = sum(messages)          # aggregation: elementwise sum of vectors
        H_next[v] = update_fn(H[v], m_v)
    return H_next

def readout(H_final, readout_fn):
    return readout_fn(list(H_final.values()))

This is the generic skeleton — message_fn and update_fn are supplied by the caller, so the function itself makes no claim about what a specific architecture computes; it is the scaffolding every one of them shares.

Graph Attention Networks: learning who to listen to

Veličković, Cucurull, Casanova, Romero, Liò, and Bengio's "Graph Attention Networks" (ICLR 2018) replace the fixed neighbor weighting of GCN with a learned one. For target node i and each neighbor j (including i itself via an added self-loop, the paper's standard convention), GAT first projects both nodes' features with a shared learned matrix W, then scores the pair with a learned attention vector a:

e_ij   = LeakyReLU( a^T [ W h_i || W h_j ] )        (0.2 negative slope)
α_ij   = softmax_j( e_ij )  =  exp(e_ij) / Σ_{k in N(i)} exp(e_ik)
h_i'   = σ( Σ_{j in N(i)} α_ij · W h_j )

where || is vector concatenation. α_ij is a probability distribution over i's neighbors — every neighbor gets a share of attention that sums to 1, but the shares need not be equal, and which neighbor gets the largest share is learned from the data rather than fixed by degree.

Worked example: one attention layer, by hand

Take target account 1 with three linked accounts, 2, 3, 4, plus its self-loop. Give each account a two-dimensional feature vector (say, [normalized transaction amount, normalized transaction frequency]):

h_1 = [ 1, 0]     h_2 = [0, 1]     h_3 = [1, 1]     h_4 = [-1, 1]

Fix a projection matrix W and attention vector a:

W = [[1, 0],
     [1, 1]]

a = [1, 1, -1, -1]

Project every node: W h_v is computed as a matrix-vector product, row by row.

Wh_1 = [1·1+0·0, 1·1+1·0] = [ 1, 1]
Wh_2 = [1·0+0·1, 1·0+1·1] = [ 0, 1]
Wh_3 = [1·1+0·1, 1·1+1·1] = [ 1, 2]
Wh_4 = [1·-1+0·1, 1·-1+1·1] = [-1, 0]

Now score node 1 against every candidate j in {1, 2, 3, 4}. Because Wh_1 = [1,1] is fixed, and a = [1,1,-1,-1], the raw score simplifies to a^T[Wh_1 || Wh_j] = (1+1) − (Wh_j[0] + Wh_j[1]) = 2 − sum(Wh_j), then passed through LeakyReLU (slope 0.2 on the negative side):

j=1: sum(Wh_1)=2  →  2-2=0   → LeakyReLU(0)   =  0.0
j=2: sum(Wh_2)=1  →  2-1=1   → LeakyReLU(1)   =  1.0
j=3: sum(Wh_3)=3  →  2-3=-1  → LeakyReLU(-1)  = -0.2   (0.2 × -1)
j=4: sum(Wh_4)=-1 →  2-(-1)=3→ LeakyReLU(3)   =  3.0

Exponentiate and normalize (softmax):

exp: e^0=1.000, e^1=2.718, e^-0.2=0.819, e^3=20.086
Z = 1.000 + 2.718 + 0.819 + 20.086 = 24.622

α_11 = 1.000 / 24.622 = 0.041
α_12 = 2.718 / 24.622 = 0.110
α_13 = 0.819 / 24.622 = 0.033
α_14 = 20.086 / 24.622 = 0.816     (sums to 1.000)

Node 4 — the neighbor whose projected feature vector points most sharply away from node 1's — receives 82% of the attention, roughly 25 times more than node 3, whose projected vector is closest to node 1's own. GAT has learned to attend most to the neighbor whose behavior is most different from the target's baseline, exactly the signal a fraud analyst would want a "how anomalous is this account's neighborhood" score to pick up on. Aggregate:

h_1' = 0.041·[1,1] + 0.110·[0,1] + 0.033·[1,2] + 0.816·[-1,0]
     = [-0.742, 0.218]      (pre-activation; σ, e.g. ELU, applied next)

Here is that entire computation as runnable code — every value it prints matches the trace above:

import numpy as np

h = {1: np.array([1.0, 0.0]), 2: np.array([0.0, 1.0]),
     3: np.array([1.0, 1.0]), 4: np.array([-1.0, 1.0])}
W = np.array([[1.0, 0.0], [1.0, 1.0]])
a = np.array([1.0, 1.0, -1.0, -1.0])

Wh = {i: W @ h[i] for i in h}

def leaky_relu(x, slope=0.2):
    return x if x > 0 else slope * x

neighbors = [1, 2, 3, 4]        # node 1's self-loop + its 3 neighbors
i = 1
e = {j: leaky_relu(float(a @ np.concatenate([Wh[i], Wh[j]])))
     for j in neighbors}
exp_e = {j: np.exp(e[j]) for j in neighbors}
Z = sum(exp_e.values())
alpha = {j: exp_e[j] / Z for j in neighbors}
h1_new = sum(alpha[j] * Wh[j] for j in neighbors)

print({k: round(float(v), 4) for k, v in alpha.items()})   # {1: 0.0406, 2: 0.1104, 3: 0.0333, 4: 0.8157}
print(np.round(h1_new, 4))                                 # [-0.7419  0.2175]

Real GAT layers run several attention heads in parallel — each with its own W and a — and concatenate (hidden layers) or average (final layer) their outputs, which stabilizes training the same way multi-head attention stabilizes transformers, a mechanism you have already seen from the other side in this curriculum's transformer-internals material.

What a GNN provably cannot see: the Weisfeiler–Leman ceiling

Every architecture above shares one structural trait: at each layer, a node updates itself using only the multiset of messages arriving from its neighbors. That single design choice — aggregating over an unordered multiset rather than, say, a full joint encoding of the neighborhood — turns out to cap what any such network can ever distinguish, and the cap has a name: the 1-dimensional Weisfeiler–Leman (1-WL) graph isomorphism test, also called color refinement.

1-WL is a purely combinatorial algorithm, no learning involved. Give every node an initial "color" (its degree is the standard choice). Then repeat:

c^(0)(v) = degree(v)
c^(t+1)(v) = HASH( c^(t)(v), sorted-multiset{ c^(t)(u) : u in N(v) } )

until the partition of nodes into color classes stops changing. Two graphs are run through this in parallel; if their final color histograms (how many nodes hold each color) differ, the graphs are definitely not isomorphic. If the histograms match, the test is inconclusive — 1-WL is a necessary but not sufficient isomorphism check, and there exist non-isomorphic graphs it cannot tell apart.

Xu, Hu, Leskovec, and Jegelka ("How Powerful are Graph Neural Networks?", ICLR 2019) proved the connection precisely: any message-passing GNN's ability to produce different embeddings for two non-isomorphic graphs is bounded above by 1-WL's ability to do the same. Their proof also identifies the ceiling's exact height: the AGGREGATE step (sum, mean, or max over neighbor messages) must be an injective function of the neighbor multiset for the GNN to match 1-WL's power, and only sum aggregation combined with an MLP can be made injective over countable inputs — which is why they designed the Graph Isomorphism Network (GIN) around exactly that combination. GCN's degree-normalized sum and GraphSAGE's mean are both provably non-injective, so they sit strictly below even that ceiling. No depth, no width, and no amount of training data changes this — it is a statement about what the architecture's update rule can distinguish in principle, not a capacity problem that scale fixes.

Worked failure case: two fraud-ring shapes, one color

Consider two possible layouts NPCI's fraud team might see in the UPI transaction graph, each on 6 accounts, each with every account having exactly 2 transaction-partners (a 2-regular graph):

• Graph A (C₆): one coordinated ring — accounts 1–2–3–4–5–6–1, money cycling through all six before exiting. A textbook laundering pattern.
• Graph B (2×C₃): two unrelated triangles — {1,2,3} and {4,5,6}, each a closed 3-cycle, with no edges between the two groups. Two small, independent (and here, harmless) closed loops.

Run color refinement on both, starting from degree as the initial color. Every node in both graphs has degree 2, so every node in both graphs starts in the identical color class, call it c₀.

Round 1: each node's new color is a hash of its own color and the multiset of its two neighbors' colors. In both graphs, every neighbor of every node currently holds color c₀ — because every node holds c₀. So every node's neighbor-multiset is {c₀, c₀}, and every node gets the same new color, c₁ = HASH(c₀, {c₀,c₀}), in both graphs.

This is now an inductive trap: if all nodes in a graph share one color at round t, then at round t+1 every node again sees the identical neighbor-multiset (because there is only one color to see), so every node again gets one shared color. The coloring can never split into more than one class, in either graph, for any number of rounds. Final color histograms: Graph A → {6 nodes: one color}; Graph B → {6 nodes: the same one color}. 1-WL reports "possibly isomorphic" for both — and it is wrong, since Graph A is connected and Graph B is not, so they are certainly not isomorphic. This is the standard counterexample cited in the GNN-expressiveness literature: any two regular graphs of the same degree, given uniform initial labels, are 1-WL-indistinguishable regardless of their global structure.

def color_refine(adjacency, rounds=3):
    colors = {v: len(adjacency[v]) for v in adjacency}   # c^(0) = degree
    for _ in range(rounds):
        colors = {
            v: hash((colors[v], tuple(sorted(colors[u] for u in adjacency[v]))))
            for v in adjacency
        }
    return sorted(colors.values())   # histogram (as a sorted list of colors)

C6   = {1:[2,6], 2:[1,3], 3:[2,4], 4:[3,5], 5:[4,6], 6:[5,1]}
C3x2 = {1:[2,3], 2:[1,3], 3:[1,2], 4:[5,6], 5:[4,6], 6:[4,5]}

print(color_refine(C6)   == color_refine(C3x2))   # True — indistinguishable

Because every message-passing GNN's discriminative power is bounded by 1-WL, this result is not specific to GIN. A GCN, a GraphSAGE-mean network, and — this is the deeper point this chapter's two threads connect on — a GAT all fail identically here, and for a mechanistically specific reason: on a graph where, by symmetry, every node's neighbors always carry identical embeddings, the attention scores e_ij computed from those embeddings are also identical across a node's neighbors, so the softmax necessarily collapses to a uniform 1/deg weighting — GAT degenerates into exactly GCN's fixed aggregation. Learned attention only buys extra power when neighbors are locally distinguishable; the C₆-versus-2×C₃ pair is constructed precisely so they never are. Whichever architecture NPCI's team deployed, a sum-pooled graph embedding (readout R = sum of final node states) would be numerically identical for the coordinated 6-account ring and the two harmless triangles — the classifier head receives the same input vector for both and is mathematically forced to output the same risk score. That is not a training failure to fix with more data; it is a representational failure baked into the architecture family.

Common misconception

Students consistently assume that a GNN's ceiling is a capacity problem — "surely a deeper network, or a wider hidden layer, would eventually notice the difference." It will not. The C₆-versus-2×C₃ argument above never mentions layer count or hidden dimension; it is a purely structural fact about what a permutation-invariant aggregation over a multiset can extract, and it holds at 3 layers or 300, at width 8 or width 8192. The fix has to change what information the aggregation step has access to, not how much compute processes that information. Two production-tested routes: add structural features that break the symmetry directly — explicit triangle counts, cycle counts, or random-walk structural encodings, as used in the graph-transformer architectures surveyed by Rampášek, Galkin, Dwivedi, Luu, Wolf, and Beaini (NeurIPS 2022) — or move to a strictly more expressive architecture, such as the k-GNNs of Morris, Ritzert, Fey, Hamilton, Lenssen, Rattan, and Grohe (AAAI 2019), which operate on node tuples rather than single nodes and provably exceed 1-WL.

Active recall

Attempt each question before reading its answer.

1. State the three functions of the MPNN framework (Gilmer et al., 2017) and what each one operates over.
2. In the worked GAT example, if a different attention vector a had produced e_14 = -3 instead of 3, what would α_14 become (approximately), and what would that mean operationally for the fraud-ring detector?
3. Ripple effect: suppose the analyst rescales the projection matrix to W' = 0.5 × W, halving every Wh_v. Recompute the four attention weights for node 1. Do they stay the same as before, and why or why not?
4. Would stacking 10 message-passing layers instead of 1 let a sum-aggregation GNN distinguish C₆ from 2×C₃? Justify your answer from the color-refinement argument.
5. If the readout function is sum-pooling over final node embeddings, what does the C₆-vs-2×C₃ result imply about the graph-level vectors the classifier head receives for the two graphs?
6. Name two concrete engineering fixes, tied to real published architectures, that let a GNN exceed the 1-WL ceiling.

Answers.

1. Message (M_t): a learned function applied per-edge to a node's own state, a neighbor's state, and the edge feature, producing one message vector per neighbor, aggregated (usually summed) into m_v. Update (U_t): a learned function combining a node's previous state with its aggregated message to produce the next state. Readout (R): applied once, after the final layer, pooling all final node states into a single graph-level vector — used only for graph-level (not node-level) predictions.

2. In the worked example, e_14 already denotes the post-LeakyReLU value that gets exponentiated directly (that is exactly how the worked example itself proceeds: LeakyReLU(3) = 3.0, then e^3 = 20.086). So positing e_14 = -3 means -3 is likewise the post-activation value to plug straight into exp(): exp(-3) ≈ 0.0498 replaces exp(3) ≈ 20.086 in the softmax numerator for j=4. With the other three exponentials unchanged (1.000, 2.718, 0.819), the new denominator is 1.000+2.718+0.819+0.0498 ≈ 4.587, giving α_14 ≈ 0.0498/4.587 ≈ 0.011 — down from 0.816 to roughly 1%. Operationally: node 4's contribution is nearly completely zeroed out of node 1's update, not merely diluted — whatever anomalous signal node 4 carried is almost entirely discarded, and node 1's new embedding becomes close to a near-average of nodes 1–3 alone. A mistuned attention vector can silently erase exactly the neighbor most worth flagging.

3. They do not stay the same. Because LeakyReLU is positively homogeneous of degree 1 (LeakyReLU(c·x) = c·LeakyReLU(x) for c > 0, true on both its linear pieces), halving W exactly halves every pre-softmax score: e' = [0, 0.5, -0.1, 1.5] instead of [0, 1, -0.2, 3]. But softmax is not scale-invariant — shrinking the logits toward 0 flattens the distribution. Recomputing: exp values [1.000, 1.649, 0.905, 4.482], Z' ≈ 8.035, giving α' ≈ [0.125, 0.205, 0.113, 0.558]. α_14 drops from 0.816 to 0.558 — attention is markedly less peaked. This is the same phenomenon that motivates the 1/√d scaling in transformer dot-product attention: the scale of the pre-softmax logits directly controls how "confident" (peaked) the resulting weights are, independent of which neighbor ranks highest.

4. No. The induction in the worked failure case shows that once every node in a regular graph with uniform initial colors shares one color, every subsequent round's neighbor-color-multiset is still uniform, so the coloring never refines beyond a single class — at round 1, round 10, or round 1000. Since any message-passing GNN's discriminative power is bounded by 1-WL at the corresponding depth (Xu et al., 2019), 10 layers add no distinguishing information here; they only add oversmoothing risk.

5. Sum-pooling identical multisets gives identical vectors: since every node in C₆ shares one embedding and every node in 2×C₃ shares one embedding (by the same symmetry/induction argument), and both graphs have 6 nodes, the sum-pooled graph vector is 6 × (that shared embedding) in both cases — and since the embedding itself is identical across the two graphs (both start from the same uniform color and pass through the same update function at every layer), the two graph-level vectors are numerically identical. The classifier head sees the same input for a genuine 6-account laundering ring and for two harmless triangles, and must output the same score for both — a guaranteed misclassification of one of the two.

6. (a) Add structural features that are not purely degree-based — explicit cycle/triangle counts, or random-walk structural encodings as used in graph-transformer architectures (Rampášek et al., NeurIPS 2022) — which break the symmetry that keeps 1-WL colors uniform. (b) Move to a higher-order architecture such as the k-GNNs of Morris et al. (AAAI 2019), which aggregate over node tuples/subgraphs rather than single nodes and are provably strictly more expressive than 1-WL.

Think About It

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

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where graph neural networks: learning on non-euclidean data is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting graph neural networks: learning on non-euclidean data to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind graph neural networks: learning on non-euclidean data, 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.