Graph neural networks

At 3 a.m., your fraud model flags an account. Its row says the account is 19 days old, has made 14 payments, and has never missed one.

Nothing looks especially suspicious.

Then you notice that it paid three accounts which paid one another, all within six minutes, using the same device fingerprint. The useful evidence was not in the account’s row. It was in the shape of its relationships.

This is the problem graph neural networks solve.

A graph is a collection of entities, called nodes, and relationships between them, called edges. An account can be a node and a payment an edge.

Other examples include:

• Atoms and chemical bonds
• Users and products
• People and follows relationships

A graph neural network, or GNN, learns a vector representation for each node by repeatedly exchanging information with its neighbors. It asks not only, “What is this account?” but also, “What do the accounts connected to it look like?”

Why a graph breaks ordinary neural networks

An MLP expects a fixed-length vector with fixed meanings for each position: account age, transaction count, and average payment amount, for example.

A graph has neither guarantee. One account may have two neighbors and another 20,000. There is no natural position 1, position 2, and position 3 in a neighbor list. Reordering graph rows should not change the graph.

CNNs work on images because an image is a regular grid. “Three pixels to the right” means the same thing everywhere. On a graph, “the third neighbor” has no stable meaning: degree varies and neighbors have no canonical order.

You can force a graph into an adjacency matrix, but predictions then depend on how you numbered the nodes. Swap two account IDs and the model sees a different pattern, even though the fraud ring is identical. Padding small graphs to a maximum size is another compromise.

Permutation behavior

The required property is permutation equivariance: re-labeling input nodes should re-label node outputs in the same way. If P is a permutation matrix, X the node-feature matrix, and A the adjacency matrix:

F(PX, PAP^T) = P F(X, A)

Shuffle node IDs, and the prediction for account A should move with account A.

For graph-level prediction, such as “is this molecule toxic?”, the output should instead be permutation invariant: reordering atoms must leave the prediction unchanged.

The central mechanism: message passing

A GNN layer has two jobs: aggregate messages from neighbors, then update the node’s representation using that aggregate. This is message passing.

For node i at layer l:

m_i = AGGREGATE({h_j : j in N(i)})

h_i^(l+1) = UPDATE(h_i^l, m_i)

h_i^l is node i’s vector and N(i) its neighbor set. The braces mean a collection, not an ordered list.

AGGREGATE might be a sum, mean, maximum, or attention-weighted sum. UPDATE is usually a small neural network or a linear transformation followed by an activation.

The same update weights are used at every node, so the model handles graphs of different sizes. Order-independent aggregation gives permutation equivariance.

After one layer, a node’s representation includes one-hop neighbors. After two layers, it can include nodes two hops away. This expanding receptive field is the graph equivalent of a CNN seeing a larger patch after several convolutions.

Here is the flow.

A five-node walk-through

Return to the fraud network. Use five accounts:

• A is connected to B and C.
• B is connected to A and C.
• C is connected to A, B, and D.
• D is connected to C and E.
• E is connected to D.

Treat these payment relationships as undirected for this example. Give each account one initial feature:

h_A^0 = 1, h_B^0 = 2, h_C^0 = 0, h_D^0 = 3, and h_E^0 = 1

Use this simple layer:

h_i^(l+1) = 0.5 h_i^l + mean(neighbor features)

The first term preserves the node’s own information; the second imports neighborhood information.

For the first layer:

• A: neighbor mean (2 + 0) / 2 = 1, so h_A^1 = 0.5 times 1 + 1 = 1.5
• B: neighbor mean (1 + 0) / 2 = 0.5, so h_B^1 = 0.5 times 2 + 0.5 = 1.5
• C: neighbor mean (1 + 2 + 3) / 3 = 2, so h_C^1 = 0.5 times 0 + 2 = 2
• D: neighbor mean (0 + 1) / 2 = 0.5, so h_D^1 = 0.5 times 3 + 0.5 = 2
• E: neighbor mean 3, so h_E^1 = 0.5 times 1 + 3 = 3.5

After one layer, A knows about B and C, but not E. Apply the same layer again:

• h_A^2 = 0.5 times 1.5 + mean(1.5, 2) = 1.75
• h_B^2 = 0.5 times 1.5 + mean(1.5, 2) = 2.5
• h_C^2 = 0.5 times 2 + mean(1.5, 1.5, 2) = 2.667
• h_D^2 = 0.5 times 2 + mean(2, 3.5) = 3.75
• h_E^2 = 0.5 times 3.5 + 2 = 3.75

C can now receive information originating at E through C → D → E. That is the causal effect of stacking layers: each layer adds one hop of context. It also explains why depth is not free.

Three common message-passing designs

The basic pattern stays the same. The difference is how a layer weighs and obtains neighbor messages.

GCN: normalized neighborhood mixing

A graph convolutional network, or GCN, uses a fixed, degree-aware weighted average:

H^(l+1) = sigma(D_hat^(-1/2) A_hat D_hat^(-1/2) H^l W^l)

• A_hat = A + I adds self-loops.
• D_hat contains the resulting degrees.
• W is learned.
• sigma is an activation such as ReLU.

The edge from i to j receives weight:

1 / sqrt(degree_hat_i times degree_hat_j)

A raw sum gives high-degree nodes a much larger signal. A plain mean controls only the destination degree. GCN normalization controls both ends and keeps propagation better behaved.

In our graph, the original degrees are A 2, B 2, C 3, D 2, and E 1. With self-loops they become 3, 3, 4, 3, and 2.

The A-to-B edge has weight 1 / sqrt(3 times 3) = 0.333; A-to-C has weight 1 / sqrt(3 times 4), approximately 0.289. This is structured linear algebra that mixes neighboring rows while respecting the graph.

GraphSAGE: learn an aggregator and sample neighbors

GraphSAGE means “graph sample and aggregate.” It samples a bounded number of neighbors and learns how to combine their features:

h_i^(l+1) = sigma(W [h_i^l || AGGREGATE(sampled neighbors)])

The double bar means concatenation. Mean and max-pooling are common aggregators.

Sampling is the production feature. If a node samples 25 neighbors at layer one and 10 neighbors for each of those at layer two, computation touches at most:

1 + 25 + 25 times 10 = 276 nodes

Without sampling, a popular account might connect to hundreds of thousands of accounts. GraphSAGE is also inductive: its learned aggregator can process a new node when its features and neighbors are available.

Sampling adds variance. Different batches see different neighborhoods, and high-degree nodes may be underrepresented. Fanout is both a model-quality and systems parameter.

GAT: learn which neighbors matter

A graph attention network, or GAT, gives each neighbor a data-dependent weight. A simplified layer scores (i, j) after transforming features:

e_ij = LeakyReLU(a^T [W h_i || W h_j])

It normalizes scores over node i’s neighbors:

alpha_ij = softmax_j(e_ij)

Then:

h_i' = sigma(sum(alpha_ij W h_j))

A’s neighbors might receive weights 0.7 and 0.3. Each node gets its own distribution.

To use edge attributes such as payment type or device relationship, include an edge-feature vector in the message or attention score.

GAT is not global attention: a node still attends only to supplied neighbors. It can be more expensive on high-degree nodes, and an attention weight is a learned mixing coefficient, not proof of causality.

Scaling: the neighbor explosion

A full-batch GCN processes every node and edge in a step. That is elegant on 10,000 nodes and awkward on 100 million edges.

If average degree is d, an L-layer computation can touch roughly d^L nodes around one target before accounting for overlap. With 100 neighbors and three layers, the naive upper bound is one million third-hop paths. Real graphs overlap, but memory pressure arrives first.

Mini-batch GNN training starts with target nodes and builds a sampled computation subgraph. Other systems partition the graph into clusters.

Practical controls include:

• Reduce layers or fanout.
• Use sparse representations.
• Partition the graph.
• Cap pathological degrees.
• Measure sampled nodes per batch.

A process killed by the operating system or a GPU at 100% memory is often a neighbor-explosion failure, not a need for a larger model.

Transductive and inductive graphs

A transductive task has one known graph. Training, validation, and test nodes belong to it, though only some labels train the model. A GCN can propagate across the graph and predict held-out nodes.

An inductive task handles new nodes or entirely new graphs. A new customer may join tomorrow, or a new molecule may never have appeared in training. GraphSAGE-style learned aggregation is designed for this setting.

Transductive access is not permission to leak the future. If a fraud model is evaluated on January transactions, it should not use February edges just because they are in a database snapshot. Build each example from information available at prediction time.

The depth limit: over-smoothing

Adding layers expands context, but repeated mixing causes over-smoothing: neighboring representations become nearly indistinguishable. Pairwise cosine similarities climb toward one, and accuracy falls as the classifier receives nearly identical vectors.

Repeated normalized propagation behaves partly like diffusion. Differences between neighboring vectors are damped; the model washes detail into the neighborhood.

This differs from over-squashing. Over-smoothing makes representations too similar. Over-squashing compresses exponentially many distant signals into a fixed-width vector. Both can result from stacking layers.

Residual connections, jumping-knowledge connections, normalization, and retaining original features can help. Often the best defense is simpler: use two or three layers and improve the graph or node features.

Choosing the tool

The question is whether relationships contain predictive information that is difficult to summarize without the graph.

Approach	Use it when the data is	Why it can win	Main risk
MLP or gradient-boosted trees	Fixed per-entity features	Simple, cheap, easy to debug	Summaries may lose structure
CNN	A regular grid such as an image	Local offsets are meaningful	Graph ordering has no such offsets
RNN or Transformer	An ordered sequence	Position and time matter	A neighbor set is not a sequence
GNN	Entities with informative relationships	Learns structure and features together	Construction, sampling, and leakage are difficult

A well-engineered tabular model often wins. For fraud, features such as devices shared by an account’s neighbors, payments from known mule accounts, and time-correct changes in those values may give a gradient-boosted tree enough structure. It can be faster and easier to explain than a GNN.

Use a GNN when the graph pattern itself matters and is too costly or brittle to summarize. Establish a tabular baseline first. If the GNN does not beat it on a time-correct holdout, the graph may not justify its operational complexity.

Failure modes you can diagnose

Predictions change when node IDs are shuffled. You likely concatenated neighbors in ID order instead of using shared updates and commutative aggregation.

Some batches run out of memory. A high-degree hub inflated the sampled subgraph. Log unique sampled nodes and edges, then lower fanout, cap hubs, or partition the graph.

Validation is astonishingly good, then production collapses. Suspect temporal or relational leakage. Rebuild each training example from its prediction-time information boundary.

More layers lower accuracy while embeddings become similar. This is over-smoothing. Try fewer layers, residual connections, or methods that preserve original features.

The GNN never beats the tree baseline. The graph may be noisy, stale, sparse, or already summarized by tabular features. Be willing to ship the simpler model.

What to remember

• Graphs have variable degree and no natural node or neighbor ordering.
• Message passing aggregates order-independent neighbor information, then updates each node with shared weights.
• GCNs normalize by degree; GraphSAGE samples neighbors; GAT learns data-dependent weights.
• More layers add hops but risk over-smoothing; larger fanouts cause neighbor explosion.
• A GNN earns its complexity only when relational structure adds signal beyond a fair, time-correct tabular baseline.

Quick check

0/3

Q1

Because every graph must have the same number of nodesBecause re-labeling nodes should re-label predictions without changing their meaningBecause graph edges are always directedBecause attention weights must sum to one

Check answer

Q2

Information originating from nodes up to two hops awayThe labels of every node in the graphA canonical ordering of its neighborsThe exact future edges in the graph

Check answer

Q3

A deep GNN that averages the empty neighborhood many timesA GNN trained transductively on future customersA tabular baseline using the available features, possibly with a GNN once reliable edges appearA CNN applied to a padded adjacency matrix

Check answer