Refining Heuristic-Based Bitcoin Address Clustering with Graph Neural Networks
Hugo Schnoering, Roman Bresson, Michalis Vazirgiannis
cs.LG
Quick verdict
Claims GNN contrastive embeddings refine Bitcoin heuristic clusters; F1 65.7% vs 59.2% on labeled pairs, but gains partly circular and theory idealized.
Summary
The paper addresses cluster collapse in heuristic Bitcoin address clustering: single-transaction merges (e.g., the common-input heuristic) can fuse unrelated users into one flat cluster. The authors train two-layer GNNs (GAT, GCN, GraphSAGE) with an InfoNCE contrastive loss that pulls addresses sharing a heuristic cluster together and pushes other pairs apart, then run agglomerative hierarchical clustering (cosine distance, average linkage) on the embeddings within Leiden pre-clusters, cutting dendrograms at a silhouette-selected threshold to flag and split suspicious merges. They also release a public dataset of five sampled Bitcoin transaction graphs (0.49-1.07M nodes) with heuristic cluster labels, and prove spectral sufficient conditions (Davis-Kahan perturbation bounds) under which embeddings admit a 'perfect cut'. On the test graph, a symmetrized GAT with 64 landmark positional encodings reaches dendrogram purity 0.789 and NMI 0.768, beating Louvain/Leiden, untrained GAT, GAE and DGI baselines (Table 1). Against independent entity labels (500 transactions), the hybrid refinement lifts macro-F1 from 59.2% to 65.7% and halves false positives (22.7% to 8.8%), also beating a reproduced Moser-Narayanan merge filter (Table 2); with CoinJoin hard negatives, the true-negative rate on CoinJoin pairs rises from 0% to 63.4% in the best configuration (Table 3). Main limitations: headline metrics are computed against the same heuristic labels used for training (circularity), independent ground truth is small, the theory's assumptions are empirically far from satisfied (87% cross-cluster edge ratio), and hierarchical clustering scales quadratically.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
4 strengths · 4 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Contrastive GNN embeddings consistent with heuristic clusters enable dendrogram-based refinement that flags suspicious merges and splits collapsed clusters (Section 3.4).
- The released Zenodo dataset provides large-scale sampled Bitcoin transaction graphs with a substantial number of heuristic cluster labels for training and evaluation (Contribution 1).
- Hybrid refinement outperforms both raw heuristics and a reproduced Moser-Narayanan random-forest merge filter on entity-labeled pairs (Table 2: macro-F1 65.7% vs 59.2% and 57.6%).
- CoinJoin hard-negative training raises the true-negative rate on CoinJoin input pairs from 0% (heuristics) to 63.4% in the best configuration (Table 3).
- Lemma 1 and Theorem 2 give spectral sufficient conditions for embeddings admitting a perfect dendrogram cut, though the authors disclaim direct verifiability on real graphs.
Strengths
Reusable public artifacts
Five sampled Bitcoin graphs (0.49-1.07M nodes, 3.7-15.1M edges, Table 4) with heuristic cluster labels on Zenodo (CC BY 4.0, DOI 10.5281/zenodo.22239038); graph-construction and clustering code on GitHub; a full reimplementation of the Moser-Narayanan filter with released code (Appendix E); all experiments CPU-only on a Mac M3 Max, so the whole pipeline is tractable for other groups.
Evaluation beyond training supervision
Independent entity labels on 500 transactions (Table 2: macro-F1 59.2%→65.7%, FP 22.7%→8.8%, beating the reproduced Moser-Narayanan filter at 57.6%) and adversarial CoinJoin labels on 500 transactions (Table 3: TN 0%→45.8% base GNN-HAC, 63.4% with hard negatives) test qualities the heuristic labels themselves cannot measure.
Heterophilic failure mode handled explicitly
Systematic ablations and honest limitations
Weaknesses
Circular headline evaluation
Theory-practice gap
Much of the signal predates the contrastive objective
Thin statistical treatment
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper tackles a known failure mode of heuristic Bitcoin address clustering: flat clusters produced by rules such as common-input ownership absorb unrelated users when a single transaction misleads the rule ("cluster collapse"). The proposed two-stage refinement (1) trains a GNN with an InfoNCE contrastive loss whose positives are addresses co-clustered by the heuristics and whose negatives come from other clusters (Eq. 1, mixture sampling parameter α), and (2) runs agglomerative hierarchical clustering (cosine distance, average linkage) within Leiden pre-clusters capped at 65,000 nodes, cutting dendrograms at a silhouette-selected threshold λ to flag suspicious merges and derive a refined partition (Section 3.4). Three claims structure the paper: a released dataset of five sampled transaction graphs with heuristic cluster labels; a supervised-contrastive embedding methodology "consistent with heuristics"; and spectral sufficient conditions (Lemma 1, Theorem 2) under which the dendrogram admits a "perfect cut". A CoinJoin-specific repulsion loss (Eqs. 2-3) handles a documented heterophilic failure mode.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 4 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What problem does this paper solve in Bitcoin address clustering?
Heuristic clustering (e.g., the common-input heuristic) produces flat clusters and sometimes merges unrelated users into one giant cluster when a single transaction misleads the rule — called cluster collapse. This paper refines those clusters: a graph neural network learns address embeddings consistent with the heuristics, and hierarchical clustering on those embeddings flags suspicious merges and splits them into sub-groups.
How much does the GNN refinement improve clustering accuracy?
On 500 transactions with independent entity labels, macro-F1 improves from 59.2% (raw heuristics) to 65.7% and false positives drop from 22.7% to 8.8%; it also beats a reproduced Moser-Narayanan merge filter (57.6%). Against CoinJoin transactions, where plain heuristics score 0% true negatives, the best configuration reaches 45.8%, or 63.4% after adding CoinJoin hard-negative training.
Are the dataset and code publicly available?
Yes. Five Bitcoin transaction graphs with cluster labels are on Zenodo under CC BY 4.0 (DOI 10.5281/zenodo.22239038), the graph-construction pipeline and the clustering/training code are on GitHub, and all experiments run on CPU only.
What are the main limitations of the paper?
Headline metrics are measured against the same heuristic labels used for training; independent ground truth is small (500 entity-labeled and 500 CoinJoin transactions); the theoretical guarantees assume near-ideal cluster structure that the real data does not exhibit (87% of edges cross clusters); and hierarchical clustering scales quadratically, limiting dynamic on-chain use.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The provided text is a sampled excerpt with three '[...sampling gap...]' regions; the formal perfect-cut definition opening Section 4, part of the Section 6.1-6.2 discussion, and portions of the references and Appendix E fall inside those gaps — no judgment above relies on their content.
- Appendix B.4's Table 7 is cut mid-row ('Number of CoinJoin-centered graphs sa…'), so the exact CoinJoin-augmentation hyperparameter values are not visible.
- Figures appear only as captions; visual content (dendrogram example, distance CDFs in Figures 5-6) could not be assessed.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.