Graph-Based Anomaly Detection for Transaction Networks

Most transaction monitoring scores one account at a time: amount, velocity, distance from the customer’s own history. That works on a fraudster acting alone and is blind by construction to a pattern whose only unusual property is the shape it makes across several accounts, each of which looks ordinary.

Why per-account scoring misses it

A per-entity model computes a feature vector for one account and compares it to a distribution over accounts. Every feature it can use is an aggregate: total in, total out, number of counterparties, mean transfer size, hour-of-day histogram, deviation from the last ninety days. If a group of accounts is coordinated so that each member stays inside the normal band on all of those, the model has nothing to fire on. It is not badly tuned. The information that identifies the group is not in any single account’s feature vector at all — it is in the relationships between them, which the model never sees.

This is the general case for structured abuse. The same argument applies to review rings, ad-click farms and mule networks. General treatments of anomaly detection assume points in a feature space; a transaction network is not points, it is a directed multigraph with timestamps and amounts on the edges, and the anomaly lives on the edges.

The pattern, worked

Take six accounts, A through F, at a mid-sized institution that processes several million transfers a month. Over four days the following happens. A receives 9,400 from an external source and sends 9,280 to B. B sends 9,150 to C. C sends 9,020 to D. D sends 8,900 to E. E sends 8,780 to F. F sends 8,650 back out to an external account, and separately F sends 120 to A.

account  in      out     counterparties  max transfer  days active
A        9,400   9,280   2               9,280         4
B        9,280   9,150   2               9,150         3
C        9,150   9,020   2               9,020         3
D        9,020   8,900   2               8,900         2
E        8,900   8,780   2               8,780         2
F        8,900   8,770   3               8,650         2

Read that table one row at a time and there is nothing to act on. No amount crosses a 10,000 reporting threshold. Two counterparties is fewer than a typical retail customer has in a week. In-and-out totals balance, which is what a normal pass-through account looks like. Every row sits comfortably inside the population distribution, which is exactly why per-node scoring returns six low scores.

Now look at the induced subgraph on {A, B, C, D, E, F}. It is a directed cycle of length six with one chord. Value is nearly conserved along it — each hop loses between 1.2% and 1.5%, a consistent skim. The edges are strictly ordered in time and every hop happens within a few hours of the one before it. And the subgraph is almost entirely closed: apart from the entry at A and the exit at F, the six accounts transact only with each other. Those four properties — cyclicity, near-conservation of value, temporal ordering, and isolation from the rest of the graph — are all properties of the set, and none of them can be computed from a single row.

What you actually compute

There is no single “graph anomaly score”. In practice you compute a small number of structural features and treat them the way you already treat behavioural ones.

• Egonet features. For each node, take the subgraph induced on that node and its neighbours, and record its node count, edge count, total edge weight and principal eigenvalue. Leman Akoglu, Mary McGlohon and Christos Faloutsos showed in OddBall (PAKDD 2010) that these pairs obey power laws across real weighted graphs, and that the interesting nodes are the ones far off the fitted line — near-cliques, where the egonet has far more edges than its size predicts, and near-stars, where it has far fewer.
• Directed cycles of bounded length. Enumerating all cycles is intractable, but cycles up to length six or eight with amount and time constraints are enumerable with a bounded depth-first search on the edges that survive an amount filter. The mechanics are the same as cycle detection on a dependency graph, with the extra condition that timestamps must increase along the path.
• Dense subgraph detection. A block of accounts that transact with each other far more than the ambient rate is a near-bipartite-core or near-clique. Bryan Hooi and colleagues’ FRAUDAR (KDD 2016) gives a density metric with a proven bound on how much a fraudster can dilute their block by adding legitimate-looking edges, which is the thing naive density measures fail at.
• Connected-component and motif statistics. Component size distribution, reciprocity, and counts of specific three- and four-node motifs. A sudden mass of size-six strongly connected components in a graph that normally has almost none is itself the alert.

Turning a structure into a score

Two families, and they fail differently. The first is feature engineering: compute the structural features above, append them to the existing per-account feature vector, and let whatever model you already run consume them. This is unglamorous and it is usually the right first move, because it reuses your labels, your thresholds and your review workflow, and because every feature is explainable to an investigator who has to justify a filing.

The second is to learn the representation, with a graph neural network over the transaction graph. That gives you features you did not think of, at the cost of needing labels and of producing an embedding nobody can read. It also inherits the depth problem: transaction fraud typically lives two or three hops out, and stacking more layers to reach further makes node representations converge toward each other rather than sharpen.

Whichever you choose, the label problem dominates. Confirmed fraud labels arrive months late, are heavily biased toward what the previous system caught, and cover a fraction of a percent of accounts. Treating the unlabelled majority as negatives trains the model to reproduce your current detector. The usual compromise is unsupervised structural scoring to generate candidates, ranked, with human review as the labelling function — and an explicit exploration budget so the queue does not collapse onto one pattern.

Where this breaks

Adversaries adapt to the metric you deploy. Length-six cycle detection produces length-nine cycles. Density thresholds produce padding with legitimate edges — which is precisely the camouflage FRAUDAR is designed to bound. Any structural signal that is cheap for you to compute is usually cheap for the other side to break, so treat the detector as one of several and expect to rotate it.

Legitimate structures look identical. Payroll disbursement is a near-perfect star. Treasury sweeps between a company’s own accounts are cycles with near-conserved value. Escrow, factoring and payment-service-provider settlement all produce dense pass-through blocks. Without a mechanism to whitelist known entity types, structural detection generates alerts at a rate that destroys the review queue, and a destroyed review queue means the real alerts are not read either.

The graph is a construction, not a given. Resolving which rows are the same real-world party, deciding whether to model a counterparty as a node or an attribute, and choosing a time window all change the answer more than the algorithm does. That work sits in turning tabular records into a graph and in ordinary data quality checks, and it is where most of the effort actually goes.