PaperlayerView exact revision on arXiv

Source-linked AI summary

Refining Heuristic-Based Bitcoin Address Clustering with Graph Neural Networks

Hugo Schnoering, Roman Bresson, Michalis Vazirgiannis

arXiv:2609.01942v1cs.LG

TL;DR

Bitcoin address clustering lacks direct user associations and heuristic methods often yield flat partitions. This paper learns heuristic-consistent contrastive GNN embeddings and applies hierarchical clustering to refine those partitions, flagging potential collapses and proposing candidate splits. The resulting representations provide more interpretable, multi-resolution structure for analyzing user graphs.

  • Problem

    Because users can control multiple pseudonymous Bitcoin addresses, clustering addresses by user remains a central challenge for user-level transaction analysis.

  • Method

    The method learns contrastive GNN embeddings that pull heuristic-linked addresses together and separate others, then uses agglomerative hierarchical clustering to identify discrepancies and candidate refinements.

  • Results

    The learned representations refine heuristic clusters by flagging potential collapses, proposing candidate splits, and producing hierarchical structure that improves intelligibility and visualization.

  • Takeaways & Limitations

    The framework provides a unified toolkit for moving from flat heuristic clusters to interpretable, multi-resolution Bitcoin user graphs.

  • Takeaways & Limitations

    Hierarchical clustering remains difficult to scale to dynamically growing transaction graphs, although local subgraph sampling can partially mitigate this limitation.

Abstract

from arXiv · show

Bitcoin's pseudonymous nature makes it challenging to analyze user-level activity, since a single user may control multiple identifiers (addresses). Existing heuristic-based methods attempt to identify addresses belonging to the same user, but they often produce flat cluster assignments with limited modularity and are prone to errors such as merging different users together. In this work, we propose a method for refining heuristic-obtained clusters by grounding our clustering on contrastive embeddings yielded by graph neural networks. Our contributions are threefold: (i) we release a publicly available dataset of Bitcoin transaction graphs containing a substantial number of clusters; (ii) we propose a methodology for learning address embeddings consistent with heuristics, and back it up with theoretical guiding intuitions; (iii) through hierarchical clustering, we enable a finer analysis of heuristic clusters and provide a quantitative criterion for flagging suspicious merges.

1 Introduction

The paper addresses the difficulty of inferring user-level activity from pseudonymous Bitcoin addresses, where one user may control multiple identifiers. It proposes graph-based embeddings and hierarchical clustering to refine heuristic-based address clusters, supported by a new large-scale dataset and theoretical and empirical analyses.

  • Bitcoin Address Clustering: Bitcoin users are identified by pseudonymous addresses, and a single user may control many addresses, preventing direct association between addresses and users.Address-level transaction analysis is informative but does not directly provide a user-level view.
  • Graph Construction from Transactions: The method represents users as graph nodes and transactions as edges, deriving edge and node features from transaction and external information.The construction extracts transaction addresses, applies heuristics to cluster them into users, creates directed feature-bearing edges, and aggregates edge information into node features.
  • Hierarchical Clustering: Hierarchical clustering organizes points into nested clusters through successive agglomerative merges represented by a dendrogram.In the agglomerative variant, each node begins as its own cluster and pairs are merged according to a linkage rule based on dissimilarity.
  • Graph Neural Networks (GNNs): GNNs learn address embeddings by propagating and transforming node features across edges to capture local connectivity, node attributes, and multi-hop structural context.These embeddings can support graph tasks including node classification, link prediction, and graph-level inference.
  • Contributions: The paper releases large-scale Bitcoin transaction graphs, proposes heuristic-consistent address embeddings, and uses learned representations to refine heuristic clustering.The contributions include theoretical guiding intuitions, empirical analyses, and flagging potential clustering issues.

2 Related Work

Related work centers on heuristic Bitcoin address clustering, especially the common-input heuristic, while noting that machine-learning approaches often address classification instead. Heuristic methods provide useful user-level approximations but can produce flat, error-prone clusters; the proposed GNN embeddings and hierarchical clustering refine these assignments and expose suspicious merges.

  • Heuristic-Based Clustering: Heuristic clustering uses behavioral, rule-based assumptions to approximate user-level structures from pseudonymous Bitcoin transaction data.The common-input heuristic assumes that all input-providing addresses in one transaction belong to a single entity.
  • Other Methods for Address Clustering: Machine-learning approaches often target address classification—identifying usages such as scams or marketplaces—rather than clustering addresses.The supplied passage identifies address classification as an orthogonal task to heuristic clustering.
  • Enhancing Clustering Heuristics with GNNs: Heuristics produce flat assignments that make large clusters difficult to interpret and can merge unrelated users through single-transaction evidence.Such erroneous merges may cause cluster collapse.
  • Enhancing Clustering Heuristics with GNNs: The proposed method learns globally informed address embeddings consistent with heuristic clusters, then applies agglomerative hierarchical clustering to reveal nested structures and suspicious merges.This produces both a refined flat clustering and a multi-resolution view of the address graph.

3 Methodology

The methodology learns contrastive address embeddings consistent with heuristic clusters, then hierarchically analyzes each initial cluster to identify suspicious merges and produce refinements. Its thresholded dendrogram procedure separates subcomponents when merge distances indicate potential cluster collapse.

  • Embedding learning: The method maps addresses from the same heuristic cluster close together and addresses from different clusters apart, producing embeddings for downstream refinement.It trains a GNN with a contrastive InfoNCE objective.
  • Embedding learning: Contrastive training samples one positive address from the anchor’s cluster and negatives from different clusters, with cluster sampling mixing uniform and size-proportional choices via α.The number of negatives is p, and τ denotes the temperature hyperparameter.
  • Hierarchical refinement: The learned embeddings are hierarchically clustered with cosine distance within each initial cluster, creating dendrograms that expose discrepancies in flat heuristic partitions.The two-stage design accommodates dynamic graphs with continuously arriving addresses and transactions, unlike architectures with predetermined hierarchy depth and cluster sizes.
  • Hierarchical refinement: A merge is flagged as suspicious when its cosine distance exceeds λ, and affected clusters are split into hierarchical subcomponents to mitigate potential collapses.The procedure is defined by grouping nodes within the same initial cluster when their ultrametric distance du(x, y) is below λ.

4 Theoretical Guiding Intuitions

The section formalizes when GNN embeddings can support a perfect hierarchical clustering cut by separating intra-cluster from inter-cluster distances. Its idealized guarantees depend on graph proximity to an ideal cluster structure, spectral-filter quality, and feature alignment, while serving primarily as geometric intuition for real transaction graphs.

  • Perfect-cut criterion: A dendrogram exactly recovers ground-truth clusters when all intra-cluster distances are below threshold r and all inter-cluster distances exceed s, with a cut λ between them.These assumptions apply to single, average, and complete linkage, but are stronger than conditions typically encountered in practice.
  • Spectral embeddings: The spectral-embedding separability condition follows from matrix perturbation theory and holds when the observed Laplacian is sufficiently close to the ideal block-diagonal Laplacian.The proof uses a version of the Davis–Kahan theorem, with Smax denoting the largest cluster size.
  • GNN embedding condition: GNN embeddings inherit spectral separability when their polynomial filter preserves informative eigencomponents, suppresses others, and the transformed features align with the leading eigenspace.The embeddings are modeled as H = p(L)XW; filter quality is summarized by α, β, and γ, while alignment is measured through the leading eigenspace.
  • Interpretation and limitation: The results are not intended as directly verifiable guarantees for real Bitcoin transaction graphs, but formalize when hierarchical refinement is geometrically meaningful.The relevant geometry is a separation between intra-cluster and inter-cluster distances.

5 Experimental Setup

The experiments use leakage-controlled Bitcoin transaction graphs to train and compare contrastive GNN variants, then evaluate hierarchical and flat clusterings against unsupervised baselines. The pipeline combines embedding-based agglomerative clustering with Leiden preprocessing, dendrogram purity, and silhouette-based threshold selection.

  • Data: Five leakage-controlled graphs are constructed from non-overlapping block intervals: three for training, one for validation, and one for testing.This ensures that no transaction appears in more than one graph.
  • Models: Two-layer GCN, GraphSAGE, and GAT models minimize the contrastive loss with Adam, halving the learning rate after 20 validation-loss epochs without improvement.Features are normalized and log-scaled before entering the GNNs.
  • Model Variations: The base model varies graph symmetrization, edge-feature inclusion, and structural positional encoding to account for directed graphs and neighborhood locality.Experiments use CPU-only computation on a Mac M3 Max with 36 GB of RAM.
  • Clustering and Metrics: Hierarchical clustering applies average-linkage agglomeration with cosine distance to GNN embeddings after Leiden preprocessing capped at 65 000 nodes per community.Flat clusters are produced by cutting dendrograms at thresholds selected through locally optimized silhouette scores and size-weighted aggregation.
  • Clustering and Metrics: Dendrogram purity, ranging from 0 to 1, measures whether nodes from the same heuristic cluster merge together, while baselines include untrained, GAE-trained, and DGI-trained GATs.All baselines generate embeddings clustered using the same contrastive-pipeline procedure.

6 Results

The GNN-based methods outperform Louvain and Leiden, with symmetrized GAT variants providing the strongest overall clustering performance. Hierarchical refinement further improves labeled pairwise evaluation and exposes potential false merges, while CoinJoin transactions remain challenging.

  • Model comparisons: All GNN-based approaches outperform Louvain and Leiden in NMI and ARI, while all baselines achieve ARI scores substantially above random clustering.These results indicate that graph topology contains meaningful cluster information and support the homophily hypothesis.
  • Model comparisons: The untrained GAT substantially outperforms Louvain and Leiden, and GAE improves NMI, ARI, and dendrogram purity over the random GAT.The findings suggest that node features and link-reconstruction objectives capture useful clustering signals.
  • GAT variations: Symmetrized GAT variants outperform baselines across metrics, with 64 landmarks and no edge features achieving the best overall dendrogram purity and NMI.The highest ARI instead uses symmetrization and edge features without positional encoding, while positional encodings consistently improve dendrogram purity in the symmetrized setting.
  • Alternative architectures: GraphSAGE slightly outperforms the default GAT in NMI, but GAT delivers the best overall performance across hierarchical and flat metrics.GCN remains below the other architectures, supporting GAT as the framework’s primary model.
  • Hierarchical analysis: A representative dendrogram flags a candidate split when its final two subclusters merge at cosine distance 0.45, above the silhouette-optimized cut threshold.Dendrograms expose internal organization and scale to clusters containing tens of thousands of nodes or potentially millions in larger transaction sets.
  • Refinement evaluation: The Hybrid avg./sil. refinement raises macro-F1 from 59.2% to 65.7% and balanced accuracy from 59.2% to 67.6%.The false-positive rate falls from 22.7% to 8.8%, suggesting that refinement mitigates some false merges in the labeled setting.
  • CoinJoin robustness: The best GNN-HAC configuration reaches a TN rate of 45.8% for CoinJoin-induced false positives, compared with 0.0% for the heuristic baseline.CoinJoin transactions violate homophily assumptions and can cause negative transfer because their connectivity differs from typical address structures.

Conclusion and Limitations

The paper presents a heuristic-consistent contrastive GNN framework with hierarchical clustering to expose address substructures and potentially suspicious merges. It identifies dynamic-graph scalability and Bitcoin clustering’s privacy implications as important limitations and future-work considerations.

  • Conclusion: The framework combines contrastive GNN embeddings with agglomerative hierarchical clustering to refine heuristic-based Bitcoin address clusters and flag potentially suspicious merges.The embeddings encode heuristic-consistent similarity while revealing richer hierarchical structure.
  • Limitations and Future Work: Future work should adapt the procedure to dynamic transaction graphs for online refinement as new blocks and addresses appear.Scalability is a key challenge, particularly for constructing the hierarchical structure rather than approximating node embeddings through manageable subgraph sampling.
  • Broader Impact: Bitcoin address clustering supports forensic, compliance, and anti-money-laundering uses but may weaken the practical pseudonymity of privacy-seeking users.The datasets and experiments use publicly available blockchain data without private off-chain information.
  • LLM Usage: The authors state that LLMs were used only to improve grammar and wording after the research was designed and produced.They report that LLMs introduced no new ideas or elements.

A Dataset … B.3 Hyperparameters

The paper releases sampled Bitcoin transaction graphs and defines a training pipeline that combines locality-preserving graph construction, heuristic cluster-based contrastive sampling, feature preprocessing, and documented GNN hyperparameters. Sampling is bounded by block intervals, search depth, and expansion limits to produce computationally manageable graphs while retaining relevant transactional context.

  • A Dataset: The released dataset contains sampled Bitcoin transaction graphs for GNN training, validation, and testing, with accompanying node, edge, and cluster tables.Dataset availability is provided through DOI 10.5281/zenodo.22239038.
  • A.1 Transaction Sampling Strategy: Full-history graph construction is computationally infeasible because Bitcoin transaction networks would contain several billion nodes and edges.The dataset therefore uses subgraphs sampled over transaction histories.
  • A.1.1 Sampling from Coinbase Transactions: Bitcoin transactions form a DAG in which coinbase transactions are sources, output-spending transactions define directed edges, and transactions with unspent outputs are sinks.Inputs consume outputs from previous transactions, while outputs may be spent by future transactions.
  • A.1.1 Sampling from Coinbase Transactions: Coinbase-based sampling starts from a uniformly selected coinbase transaction and applies BFS constrained to the block interval [t1, t2].Exploration follows transaction direction, and the procedure also caps exploration depth to control graph size.
  • A.1.2 Sampling from Transactions with Labels: Sampling from labeled transactions uses BFS on the undirected transaction graph, thereby including both future spending activity and past transactions supplying inputs.This changes the directed exploration used for coinbase-based sampling.
  • A.1.2 Sampling from Transactions with Labels: Labeled-transaction sampling uses a maximum BFS depth of 3 and expands at most 100 transactions per depth to preserve locality and compactness.The remaining exploration logic follows the coinbase-based procedure.
  • B.1 Sampling Function for Contrastive Learning: Contrastive learning samples positive pairs from the anchor’s cluster and negatives from different clusters, while α interpolates between uniform and size-proportional cluster sampling.The scheme is defined relative to a reference clustering over the node set.
  • B.2 Feature Preprocessing: Feature preprocessing adds U.S.-dollar values to bitcoin-denominated amounts, then applies per-graph log transformation, percentile-based min–max normalization, and zero imputation.Dollar values use the bitcoin price at each graph’s starting date; normalization uses empirical 5th and 95th percentiles.

B.4 CoinJoin Hard-Negative Training · B.5 Training of Baselines

CoinJoin hard-negative training samples distinct node pairs from CoinJoin-centered graphs to add a weighted repulsion objective. Baselines use tuned community-detection procedures or 20-epoch graph representation-learning objectives, while the untrained GAT uses zero epochs.

  • B.4 CoinJoin Hard-Negative Training: The augmented objective includes a CoinJoin repulsion term weighted by λCoinJoin, with expectations over sampled graphs and negative pairs.The auxiliary term is based on the embedding similarity expression 1 + exp(g(Ag,j) · g(Ig,j)).
  • B.5 Training of Baselines: Louvain uses NetworkX, tuning its resolution parameter over [0.5, 3.0] on the validation graph to maximize modularity.The resolution parameter controls the granularity of detected communities.
  • B.5 Training of Baselines: Leiden uses RBConfigurationVertexPartition, tunes resolution over [0.5, 3.0], and fixes refinement iterations at 10 for convergence.The implementation relies on the leidenalg package.
  • B.5 Training of Baselines: Untrained GAT follows the trained GNN procedure with Table 6 default hyperparameters, except training epochs are set to zero.This baseline preserves the experimental procedure while removing training.
  • B.5 Training of Baselines: GAE uses a GAT encoder, dot-product decoder, adjacency reconstruction by binary cross-entropy, and a shorter training duration of 20 epochs.It retains neighbor sampling, training-graph rotation, and learning-rate scheduling, monitoring validation-graph reconstruction loss.
  • B.5 Training of Baselines: DGI maximizes mutual information between local node representations and a global summary, using shuffled node features as negative samples and training for 20 epochs.The procedure retains neighbor sampling, graph rotation, and learning-rate scheduling, while monitoring the validation-graph DGI objective.

C Evaluation … D.3 Number of negative samples

The paper evaluates hierarchical and flat clusterings with complementary information-theoretic and pairwise measures, then studies dendrogram cutting and contrastive-learning parameters. Larger embeddings and more negative samples primarily improve hierarchical structure, while ARI favors uniform sampling and remains relatively insensitive to additional negatives.

  • C Evaluation / C.1 Evaluation Metrics: Evaluation uses information-theoretic and pairwise similarity measures for hierarchical and flat clusterings.The reported measures include dendrogram purity, NMI, and ARI.
  • C.1.1 Hierarchical Clustering: Dendrogram purity is the expected fraction of same-class leaves in the smallest subtree containing a sampled same-class pair, reaching 1 exactly for pure ground-truth subtrees.Purity is estimated by Monte Carlo using N = 10,000 pairs sampled within the same coarse Leiden cluster.
  • C.2 Dendrogram Cutting Methods: Three dendrogram cutting rules are evaluated: silhouette maximization, midpoint selection at the largest merge-height gap, and adaptive inconsistency thresholding.High inconsistency coefficients indicate potentially spurious merges; the adaptive threshold is µv + ασv.
  • D Additional Experiments / D.1 Embedding dimension: Embedding dimensionality trades off cluster separation against complexity, computational cost, and possible dimensional collapse.The hidden GAT dimensionality is set to 2× the output embedding size.
  • D.1 Embedding dimension: Performance improves consistently with embedding dimension, with dendrogram purity rising monotonically from 16 to 512 dimensions and NMI and ARI peaking at 512.Intermediate dimensions of 64–128 already provide strong performance.
  • D.2 Parameter of the sampling function: The sampling parameter α balances uniform and size-proportional cluster selection, with ARI maximized at α = 0 while dendrogram purity and NMI favor different behavior.The supplied passage establishes ARI’s optimum but truncates the corresponding dendrogram-purity and NMI conclusions.
  • D.3 Number of negative samples: Increasing negative samples generally improves hierarchical quality: DP rises almost monotonically from p = 1 to p = 64, whereas ARI is highest at p = 1 and stable thereafter.Larger negative sets benefit hierarchical coherence and global structure recovery, while local pairwise consistency is comparatively insensitive beyond small p.

D.4 Approaching the Theoretical Conditions … F.1 Proof of Lemma 1

The section empirically tests the theoretical conditions behind the embeddings, reproduces the heuristic-refinement pipeline, and proves spectral separation bounds for ideal cluster graphs under Laplacian perturbations. Results show low-pass behavior, heuristic-pair separability, and improved CoinJoin-negative separation after explicit repulsion training.

  • D.4 Approaching the Theoretical Conditions: 87% is the overall validation-graph cut ratio, motivating cut ratio as a scalable practical proxy for cluster homophily.The spectral-norm criterion is infeasible for million-node graphs; lower cut ratios indicate that more edges remain within clusters.
  • D.4 Approaching the Theoretical Conditions: 6.54 to 1.29 to 1.20 to 0.99 is the monotonic Rayleigh-quotient decrease across a two-layer GAT, confirming expected low-pass filtering.The values correspond to H(0), H(1) after convolution, H(1) after activation, and H(2), respectively, across five training runs.
  • D.4 Approaching the Theoretical Conditions: Heuristic positive pairs concentrate at small cosine distances, while heuristic negative pairs shift toward larger distances, demonstrating the contrastive objective’s intended embedding geometry.Separability is less pronounced for pairs derived from independent labels.
  • D.4 Approaching the Theoretical Conditions: CoinJoin negative pairs remain unusually close to positive pairs without hard-negative training, but CoinJoin repulsion shifts them toward larger distances and ordinary-negative behavior.The shift provides a geometric explanation for improved true-negative rates reported in Table 3.
  • E Reproducing the Moser and Narayanan Heuristic: The reproduced Möser and Narayanan methodology targets two-output payment transactions, where privacy practices make payment and change outputs difficult to distinguish.The change output is defined as excess input value relative to the payment amount.
  • E Reproducing the Moser and Narayanan Heuristic: 30,000 transactions were selected to train the classifier, with all heuristics implemented and the complete implementation and augmented feature dataset released for reproducibility.The classifier uses heuristic decisions encoded as −1, 0, or 1 together with additional transaction-level features.
  • E Reproducing the Moser and Narayanan Heuristic: A predicted change probability exceeding 0.99 merges the change address into the input cluster, following the conservative ground-truth clustering procedure.The procedure combines the common-input heuristic with classifier-predicted change addresses.
  • F.1 Proof of Lemma 1: In the ideal cluster graph, zero is an eigenvalue with multiplicity equal to the number of clusters, and Davis–Kahan perturbation theory bounds empirical spectral embeddings after orthogonal alignment.For the disjoint-union-of-cliques model, λk+1(L◦) = Smax Smax−1, recovering the explicit constant used earlier.

F.2 Proof of Theorem 2

The proof decomposes the linearized GNN embedding into low-frequency and residual components relative to the informative eigenspace, then bounds residual leakage using the polynomial spectral filter. Applying Lemma 1 yields separate estimates for node pairs within the same cluster and across different clusters.

  • Spectral decomposition: The orthonormal eigenvectors Uk and their orthogonal complement form a complete basis used to decompose the embedding space.Uk contains the k eigenvectors associated with the k smallest eigenvalues of L.
  • Spectral decomposition: The linearized GNN representation separates each embedding into low-frequency and residual components through the spectral decomposition L = UDU⊤.The low-frequency component lies in the subspace spanned by Uk, while the residual lies in its orthogonal complement.
  • Leakage bounds: Residual leakage outside span(Uk) is bounded by the operator norm of the polynomial filter on the complementary eigenspace.This norm is determined by the largest absolute filtered eigenvalue among indices i > k, and row norms are bounded by the operator norm.
  • Pairwise estimates: Combining upper and symmetric lower bounds with Lemma 1 produces estimates for embeddings of nodes in the same cluster and in different clusters.The proof explicitly treats same-cluster pairs and different-cluster pairs separately.

G Computational Complexity Analysis

The pipeline’s embedding computation scales linearly with graph size, while pairwise-distance and hierarchical-clustering operations scale quadratically in the number of nodes. These quadratic costs motivate pre-clustering and highly local sampling strategies.

  • Computational bottlenecks: Embedding computation scales linearly in both N and M, particularly with neighbor sampling.N denotes the number of nodes and M the number of edges.
  • Computational bottlenecks: Pairwise-distance and hierarchical-clustering operations scale quadratically in N.This scaling motivates pre-clustering or highly local sampling strategies.
  • Computational bottlenecks: Scalable HAC algorithms proposed by Monath et al. (2021) and Dhulipala et al. (2023) mitigate quadratic clustering costs.These methods are presented as examples of approaches addressing the computational burden of hierarchical agglomerative clustering.
Loading 2609.01942v1…