Elliptic: the graph neural network that lost to a random forest

The other three guides in this topic are about deterministic inference — union-find over co-spending, FIFO over provenance. This one is about the statistical alternative, and it is here partly as a counterweight. Weber et al. released the Elliptic data set, still the largest public labelled transaction graph in any cryptocurrency, and then benchmarked graph convolutional networks against ordinary supervised learning on it. The GCN lost. Random Forest on hand-built aggregate features reaches illicit-F1 0.796; a two-layer GCN reaches 0.628. That result is worth more to a database engineer than a win would have been, because it says something precise about when graph structure pays for itself — and because a single real-world event, the shutdown of a dark market in the middle of the test period, breaks every model in the table.

Every number below is quoted from Anti-Money Laundering in Bitcoin (Weber et al., KDD 2019 AML workshop, arXiv:1908.02591): the counts from §2, the scores from Table 1 and Table 2. Nothing here is a repo-measured lane — this guide is a reading companion, not a bench.

The problem in one sentence

Classify each Bitcoin transaction as licit or illicit from a labelled graph where only 23% of nodes have a label at all, the illicit class is 2%, and the process generating the labels changes under you.

The concepts, step by step

Step 1 — The data set

In: the public Elliptic data set — a labelled sub-graph of the Bitcoin transaction network. Out: the raw material every later step consumes: 203,769 nodes, 234,355 edges, 166 features per node, 49 time steps, and a 2%/21%/77% illicit/licit/unlabelled label split. Step 2 dissects the 166 features.

   203,769 node transactions          234,355 directed edge payment flows
   (the full Bitcoin network: ~438M nodes, 1.1B edges — this is a subgraph)

   labels:   4,545 illicit (2%)      42,019 licit (21%)    rest unlabelled (77%)
   features: 166 per node
   time:     49 steps, ~2 weeks apart, 1,000–8,000 nodes each

Nodes are transactions; a directed edge means BTC flowed from one transaction to the next. A transaction is licit or illicit according to the entity that initiated it — exchanges, wallet providers, miners, licit services on one side; scams, malware, terrorist organisations, ransomware, Ponzi schemes on the other. The labelling is heuristic, and the paper says so: “a higher number of inputs and the reuse of the same address is commonly associated with higher address-clustering, which results in a degrade of anonymity for the entity signing the transaction” — i.e. the labels were produced partly by the clustering machinery of the other guides in this topic. Circularity worth noticing.

Step 2 — Two kinds of feature, and what the split measures

In: the 166-feature node vectors from Step 1. Out: a split of those features into 94 local (about the transaction itself) and 72 aggregated (one-hop neighbourhood statistics) — the split that makes the later GCN comparison fair. Step 3 looks at the time dimension.

The 166 features divide sharply:

• 94 local features: time step, number of inputs/outputs, transaction fee, output volume, and aggregates over the transaction’s own inputs and outputs.
• 72 aggregated features: the maximum, minimum, standard deviation and correlation coefficients of the same local features taken over the node’s one-hop neighbours, forward and backward.

So the 72 are a hand-rolled, single-layer, fixed-aggregation message pass. (A message pass is the operation at the heart of a graph neural network: each node updates its own vector from an aggregate of its neighbours’ vectors; doing it once reaches one-hop neighbours, twice reaches two-hop, and so on.) This is the comparison the paper is really running: hand-built one-hop aggregation vs a learned multi-hop one. Keep that in mind when you read the results, because it is a fairer fight than “features vs graphs”.

The paper flags the limitation itself: “In building the 72 aggregated features, the problem of heterogeneous neighborhoods is addressed by naively constructing statistical aggregates (minimum, maximum, etc.) of the local features of a neighbor transaction. In general, this solution is sub-optimal because it carries a significant loss of information.”

Step 3 — The temporal structure, and the choice that deletes it

In: the 49 time steps from Step 1, and the edge set from Step 2’s neighbourhoods. Out: the key structural fact — the 49 steps are disjoint graphs with no edges between them — and the train/test split built on it. Step 4 reads the scores this split produces.

Each of the 49 time steps is “a single connected component of transactions that appeared on the blockchain within less than three hours between each other; there are no edges connecting different time steps.”

Read that twice. The data set is 49 disjoint graphs, not one temporal graph. Every path is confined to a three-hour window, so no model on this data can learn anything about how money moves across time steps — which is exactly the money-laundering behaviour anyone would want to detect. Topic 33 spends a whole topic on time-respecting paths; this data set makes them impossible by construction. That is a modelling decision with consequences, and it is the subject of one of the questions below.

The evaluation uses a 70:30 temporal split: train on the earliest 34 steps, test on the last 15 (steps 35–49). A temporal split trains only on data from before a cut-off time and tests only on data after it, unlike a random split that shuffles all rows together — it is the honest way to measure a model that must predict the future, and much harder, because the test distribution is genuinely unseen.

Step 4 — The results table, read carefully

In: the train/test split from Step 3, the features from Step 2, and seven classifiers (Logistic Regression, Random Forest, MLP, GCN, Skip-GCN, EvolveGCN). Out: Table 1 — illicit-class precision, recall and F1 per model — the headline result that the Random Forest beats the GCN. Step 5 is the event that breaks all of them.

First, the metrics, because the whole table is read through them. For the illicit class, precision is the fraction of transactions flagged illicit that really are (TP / (TP + FP)); recall is the fraction of actually illicit transactions that were flagged (TP / (TP + FN)); F1 is their harmonic mean, 2·P·R / (P + R), which is low unless both are high. A GCN (graph convolutional network) is a neural network whose layers are learned message passes (Step 2) over the graph; a node embedding (NE) is the vector a GCN learns for each node, which can be fed to another model as extra features.

Illicit-class precision / recall / F1, plus micro-averaged F1. AF = all 166 features, LF = the 94 local ones only, NE = node embeddings from a GCN concatenated on.

Four readings, in order of usefulness:

1. Random Forest wins, comfortably. 0.788 vs the GCN’s 0.628. The paper’s explanation is architectural: “Random Forest uses a voting mechanism to ensemble the prediction results from a number of decision trees… GCN, in contrast, like most deep learning models, uses Logistic Regression as the final output layer; hence, it can be considered a nontrivial generalization of Logistic Regression.” And Logistic Regression is bottom of the table.
2. The graph helps, but as features. Every model improves from LF to AF (Random Forest 0.694 → 0.788), so the one-hop aggregates carry real signal. And AF+NE — Random Forest over the GCN’s embeddings — is the best row in the table at 0.796. The winning configuration uses both.
3. Skip connections matter a lot. Skip-GCN (0.705) beats plain GCN (0.628) by adding a direct path from the input features to the output, which makes it “at least as powerful as Logistic Regression”. A four-point-nine-percentage-point-per-architecture-tweak result on a model that was already losing.
4. Temporal modelling helps a little. EvolveGCN, which drives the GCN’s weights through a recurrent network across time steps, reaches 0.720 — “consistently outperforms GCN, although the improvement is not substantial for this data set.” Which is what you would expect, given Step 3: there are no cross-time edges for a temporal model to exploit.

Step 5 — The dark market shutdown: the finding that actually matters

In: the per-time-step predictions of every model from Step 4, plotted over the 15 test steps. Out: Figure 2’s finding — at time step 43 a real-world event collapses every model’s illicit F1, and re-training does not recover it. Step 6 explains why the aggregate metric hides this.

At time step 43 — inside the test period — a dark market closed. Figure 2 plots illicit F1 per time step, and every method falls off a cliff there and does not recover.

One interesting aspect of this data set is the sudden closure of a dark market occurring during the time span of the data (at time step 43). As seen in Figure 2, this event causes all methods to perform poorly after the shutdown. Even a Random Forest model re-trained after every test time step, assuming the availability of ground truth after each time, is not able to reliably capture new illicit transactions after the dark market shutdown. The robustness of methods to such events emerges as a major challenge to address.

Note the strength of that: re-training after every step with fresh ground truth does not fix it. This is not a stale-model problem, it is a distribution-shift problem — the illicit behaviour that remains after the market closes is different behaviour, and no amount of fitting the old behaviour helps.

If you have read topic 40, you have met this shape already: the adversary reads your score and changes. Topic 39’s FRAUDAR answers it by choosing a metric camouflage cannot move. There is no equivalent move here, which is the honest state of the art.

Step 6 — Why 2% illicit changes the whole evaluation

In: the micro F1 column of Step 4’s table and the 2% illicit base rate from Step 1. Out: the reason that column is worthless and the illicit-class columns are not — a class-imbalance argument, worked below. Step 7 generalises the lessons.

Micro-averaged F1 pools true positives, false positives and false negatives across all classes before computing one score; for single-label classification that makes micro-precision, micro-recall and micro-F1 all equal to plain accuracy. So it is above 0.92 for every method in the table, including the worst one, and it is meaningless here. Work it:

   predict "licit" for every node.
   let p = fraction illicit.

   full node set, p = 0.02:
       accuracy = 1 − p = 0.98  →  micro-F1 = 0.98
   labelled test set actually scored, illicit = 4,545 of (4,545 + 42,019) = 46,564:
       p = 4,545 / 46,564 = 0.098
       accuracy = 1 − 0.098 = 0.902  →  micro-F1 ≈ 0.90

Either way the do-nothing classifier scores ~0.90–0.98 micro-F1 — higher than the GCN’s illicit F1 of 0.628. A metric a trivial classifier wins is no metric. That is why the paper reports illicit-class precision/recall/F1 separately, and trains the GCN “using a weighted cross entropy loss to provide higher importance to the illicit samples” at a 0.3/0.7 ratio. Weighted cross entropy simply multiplies each class’s contribution to the loss by a weight, so mislabelling a rare illicit node costs the optimiser more than mislabelling a common licit one — the training-time counterpart to reporting the minority class separately.

The paper also frames the business constraint precisely: “Industry standard high false positive rates of upwards of 90% inhibit this effort. We want to reduce false positive rates without increasing false negative rates.” Random Forest’s 0.956 precision against Logistic Regression’s 0.404 is exactly that axis, and it is why the boring model wins in production.

Step 7 — What this says about graph ML generally

In: everything above — the fair-fight feature split (Step 2), the results (Step 4), the distribution shift (Step 5), the imbalance (Step 6). Out: three transferable rules for deciding when graph structure earns its complexity. This is the guide’s takeaway.

Three transferable lessons:

1. A learned aggregation must beat a hand-built one to be worth it. Here the hand-built 72-feature one-hop aggregate, fed to a strong tabular model, beat two learned graph models. Before reaching for a GNN, build the aggregates and measure.
2. Embeddings compose with tabular models. The best row is Random Forest over features-plus-GCN-embeddings. Use the graph model as a feature extractor rather than an end-to-end classifier when the tabular model is stronger.
3. The data set’s structure caps what any model can learn. No cross-time edges means no temporal path can be learned, and EvolveGCN’s small gain follows directly. Check what the graph you are given makes impossible before comparing architectures on it.

How to read the paper (with the concepts in hand)

• §2 The Elliptic Data Set. §2.1.1–2.1.3 for the node/edge/feature/time counts. Make sure you register the “no edges connecting different time steps” sentence and think about it before moving on.
• §2.2 Notes on feature construction. The circularity between labelling heuristics and address clustering, and the honest paragraph about naive aggregation losing information.
• §3.1–3.2. The benchmark methods and the GCN formulation. The Skip-GCN paragraph is short and is the explanation for a five-point jump; read it.
• §3.3 Temporal modelling. EvolveGCN in three paragraphs.
• §4 + Table 1. The results. Read the LF vs AF rows first (does the graph help at all?), then AF vs AF+NE (do embeddings add to features?), and only then the GCN rows.
• §4 + Figure 2 + Table 2. The per-time-step F1 plot and the dark market shutdown. This is the paper’s real contribution.
• §5 Discussion. Why Random Forest beat the GCN, and the suggestion to make decision trees differentiable so the two can be trained end to end.
• After the paper. Do not implement a GCN here — topic 25 already does that. Instead, take this topic’s clustering.rs output as a feature (cluster size, cluster age) and ask whether it would have helped: which of Elliptic’s 166 features is a cluster-derived feature in disguise?

Questions to answer in notes.md

1. The 72 aggregated features are a hand-built one-hop message pass. Rewrite the comparison in Table 1 as “learned vs hand-built aggregation” and say what result would have made the GCN clearly worth its complexity.
2. There are no edges between time steps. Name two laundering behaviours this makes undetectable in principle, and say what the data set would need to look like (in topic 33’s vocabulary) for them to be detectable.
3. Micro-F1 is above 0.92 for every method including the worst. Compute what a “predict-licit-always” classifier scores on micro-F1 with 2% illicit, and write one sentence on why the paper reports illicit-class metrics separately.
4. Re-training after each test step does not recover performance after the dark market shutdown. Distinguish concept drift from covariate shift here, and say which one this is and how you would detect it in production before the F1 drops.
5. The labels come partly from address clustering, and this topic’s lane 3 shows clustering can collapse. If a super-cluster merged a licit exchange with an illicit service, what would that do to the labels, the features, and the measured F1 — and would you be able to tell?

Done when

Answer each before unfolding it.

• You can state the data set’s size, label balance and temporal structure from memory.

  Answer

  203,769 nodes (transactions), 234,355 directed edges (payment flows), 166 features each; 4,545 illicit (2%), 42,019 licit (21%), the rest unlabelled (77%); 49 time steps ~2 weeks apart, 1,000–8,000 nodes each, and crucially no edges between time steps — 49 disjoint graphs (Steps 1 and 3).

• You can explain the 94/72 feature split and why it makes the GCN comparison a fair fight.

  Answer

  94 local features describe the transaction itself; 72 aggregated features are min/max/std/corr of those local features over one-hop neighbours (Step 2). The 72 are therefore a hand-built, single-layer, fixed-aggregation message pass — so Table 1 is really “hand-built one-hop aggregation vs a learned multi-hop GCN”, a fairer contest than “features vs graphs”.

• You can give the headline result (RF 0.788/0.796 vs GCN 0.628, Skip-GCN 0.705, EvolveGCN 0.720) and the paper’s explanation for it.

  Answer

  Random Forest on all features scores illicit-F1 0.788, and 0.796 with GCN embeddings added — the best row; the plain GCN scores 0.628, Skip-GCN 0.705, EvolveGCN 0.720 (Step 4). The paper’s explanation: RF ensembles many decision trees by voting, whereas a GCN ends in a logistic- regression output layer and is “a nontrivial generalization of Logistic Regression” — which sits at the bottom of the table.

• You can describe the dark market shutdown and why re-training does not fix it.

  Answer

  At test time step 43 a dark market closed; Figure 2 shows every model’s illicit F1 collapses and never recovers, and even a Random Forest re-trained after every step with fresh ground truth cannot capture the new illicit transactions (Step 5). It is a distribution-shift problem, not a stale-model one: the post-shutdown illicit behaviour is genuinely different, so fitting the old behaviour cannot help.

• You can say why micro-F1 is the wrong metric here.

  Answer

  Micro-F1 pools all classes and equals accuracy for single-label prediction, so a predict-licit-always classifier scores 1 − p: about 0.98 on the full 2%-illicit node set, or ≈0.90 on the labelled test set where illicit is 4,545/46,564 = 9.8% (Step 6). Both beat the GCN’s illicit F1 of 0.628, so micro-F1 rewards doing nothing — which is why the paper reports illicit-class precision/recall/F1 separately.

• You wrote answers to all five questions in notes.md.

  Answer

  Done when notes.md holds your five written answers — Table 1 recast as learned-vs-hand-built aggregation, two laundering behaviours the missing cross-time edges make undetectable, the worked predict-licit-always micro-F1, concept drift vs covariate shift for the dark-market collapse, and what a licit/illicit super-cluster merge would do to labels, features and F1.

References

• Weber, Domeniconi, Chen, Weidele, Bellei, Robinson, Leiserson. Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics. KDD 2019 Workshop on Anomaly Detection in Finance — arXiv:1908.02591.
• Pareja et al. EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs. AAAI 2020 — the temporal model in §3.3.
• The Elliptic Data Set is public on Kaggle; 203,769 nodes, 234,355 edges, 166 features.
• Topic 25 (graph neural networks) — GCN, GraphSAGE and the message-passing framework this benchmarks; topic 33 (temporal graphs) — what the missing cross-time edges cost.