Refining Heuristic-Based Bitcoin Address Clustering with Graph Neural Networks

# Refining Heuristic-Based Bitcoin Address Clustering with Graph Neural Networks
Source: [https://arxiv.org/html/2609.01942](https://arxiv.org/html/2609.01942)
Roman BressonAffiliation:Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE \*Corresponding author:hugo\.schnoering@ip\-paris\.frMichalis VazirgiannisAffiliation:École Polytechnique, Institut Polytechnique de Paris, France Affiliation:Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE \*Corresponding author:hugo\.schnoering@ip\-paris\.fr

###### Abstract

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\.

## 1Introduction

Bitcoin\([Nakamoto, 2009](https://arxiv.org/html/2609.01942#bib.bib6)\)is the first and most widely adopted cryptocurrency, designed as a decentralized payment system without reliance on a central authority\. Its operation is enabled by a peer\-to\-peer network that collectively maintains a shared, immutable record of transactions\([Antonopoulos, 2017a](https://arxiv.org/html/2609.01942#bib.bib28)\)\. This record, known as the blockchain, provides transparency and auditability while preserving a certain level of pseudonymity for its users; it is organized as a chronological sequence of blocks, each batching the transactions that happened during a certain time interval\.

##### Bitcoin Address Clustering\.

Bitcoin transactions are pseudonymous in nature, as users are identified by random pseudonyms called addresses\([Antonopoulos, 2017b](https://arxiv.org/html/2609.01942#bib.bib27)\)\. A single user can reuse an address or generate new ones at any time; it is therefore common for a user to control many different addresses\. Since addresses are generated randomly, there is no direct way to associate multiple addresses with the same user\. While analyzing transactions at the address level can be informative, a user\-level analysis provides greater insight\. The task ofaddress clusteringconsists of grouping together addresses that belong to the same user \(without necessarily identifying said user\)\.

##### Graph Construction from Transactions\.

Graph\-based representations are particularly well suited for visualizing and analyzing blockchain data\. Two primary types of graphs are commonly employed: those where nodes represent transactions and edges represent transferred bitcoin amounts\([Weber et al\., 2019](https://arxiv.org/html/2609.01942#bib.bib24)\), and those where nodes represent users and edges represent transactions\([Bellei et al\., 2024](https://arxiv.org/html/2609.01942#bib.bib25);[Schnoering and Vazirgiannis, 2025](https://arxiv.org/html/2609.01942#bib.bib15)\)\. In this paper, we focus on the latter, as it offers a more intuitive representation\. Constructing a user\-level graph from a set of transactions𝒯\\mathcal\{T\}typically involves the following steps\([Schnoering and Vazirgiannis, 2025](https://arxiv.org/html/2609.01942#bib.bib15);[Bellei et al\., 2024](https://arxiv.org/html/2609.01942#bib.bib25);[Meiklejohn et al\., 2013](https://arxiv.org/html/2609.01942#bib.bib19);[Harrigan and Fretter, 2016](https://arxiv.org/html/2609.01942#bib.bib26)\):

1. 1\.extracting the addresses involved in the transactions𝒯\\mathcal\{T\};
2. 2\.clustering the addresses into users using a heuristicℋ\\mathcal\{H\}\(or a combination thereof\) applied to𝒯\\mathcal\{T\}, potentially augmented with external information;
3. 3\.creating directed edges with associated features between users, derived from𝒯\\mathcal\{T\};
4. 4\.generating node features by aggregating information from edges;
5. 5\.incorporating external information \(off\-chain\) into both node and edge features\.

##### Hierarchical Clustering\.

Hierarchical clustering constructs a hierarchy of nested clusters over a set of pointsVVendowed with a dissimilarity functiondd\([Heller and Ghahramani, 2005](https://arxiv.org/html/2609.01942#bib.bib2)\)\. In the agglomerative variant, each node initially forms its own cluster\. At each step, two clustersA,B⊂VA,B\\subset Vare merged according to a linkage rule based ondd\. After the final step, all nodes are merged into a single cluster\. This hierarchy is naturally represented by a rooted binary tree, or*dendrogram*, where leaves correspond to individual nodes, internal nodes represent successive merges, and node height indicates the merge distance\. An example of a dendrogram is illustrated in Figure[1](https://arxiv.org/html/2609.01942#S3.F1.fig1)\.

##### Graph Neural Networks \(GNNs\)\.

GNNs extend neural architectures to graph\-structured data by propagating and transforming node features along edges\. At each layer, a node updates its representation by aggregating information from its neighbors, allowing the model to capture both local connectivity and node attributes\. By stacking multiple layers, GNNs learn embeddings that encode multi\-hop structural context and can be used for tasks such as node classification, link prediction, and graph\-level inference\([Kipf, 2016](https://arxiv.org/html/2609.01942#bib.bib43);[Hamilton et al\., 2017](https://arxiv.org/html/2609.01942#bib.bib14);[Veličković et al\., 2017](https://arxiv.org/html/2609.01942#bib.bib18)\)\.

##### Contributions\.

The main contributions of this paper are threefold:

1. 1\.We publicly release a dataset of large\-scale Bitcoin transaction graphs with a substantial number of clusters, enabling the training and evaluation of clustering algorithms at scale\([Schnoering and Vazirgiannis, 2026](https://arxiv.org/html/2609.01942#bib.bib1)\)\.
2. 2\.We propose a methodology for learning address embeddings consistent with traditional blockchain heuristics, supported by theoretical guiding intuitions and empirical analyses\.
3. 3\.We show how these learned representations can refine heuristic\-based clustering by flagging potential cluster collapses, proposing candidate splits, and providing a hierarchical clustering that improves intelligibility and visualization\.

## 2Related Work

##### Heuristic\-Based Clustering\.

To achieve address clustering, a variety of human\-made, rule\-based heuristics have been proposed\([Schnoering et al\., 2024](https://arxiv.org/html/2609.01942#bib.bib16)\), often based on behavioral patterns and human biases\. The most prominent is the*common\-input heuristic*, which assumes that all addresses providing inputs to the same transaction are controlled by a single entity\. Clustering heuristics play a crucial role in Bitcoin analysis by approximating user\-level structures from pseudonymous transaction data\. They allow researchers and investigators to reduce complexity, uncover patterns of address ownership, and make sense of large\-scale transaction graphs\. Beyond their methodological value, such heuristics have become essential tools in several domains: in forensic contexts\([Meiklejohn et al\., 2013](https://arxiv.org/html/2609.01942#bib.bib19);[Foley et al\., 2019](https://arxiv.org/html/2609.01942#bib.bib20)\); in compliance and anti\-money\-laundering efforts\([Möser et al\., 2013](https://arxiv.org/html/2609.01942#bib.bib21);[Yang et al\., 2023](https://arxiv.org/html/2609.01942#bib.bib22)\); and in privacy research\([Androulaki et al\., 2013](https://arxiv.org/html/2609.01942#bib.bib23)\)\.

##### Other Methods for Address Clustering\.

Aside from heuristic clustering, other methods have been used on Bitcoin transaction networks for similar tasks\. Machine learning\-based methods tend to focus more on the orthogonal task of address classification\([Toyoda et al\., 2018](https://arxiv.org/html/2609.01942#bib.bib53);[Lin et al\., 2019](https://arxiv.org/html/2609.01942#bib.bib54);[Garin and Gisin, 2023](https://arxiv.org/html/2609.01942#bib.bib51);[Sie et al\., 2025](https://arxiv.org/html/2609.01942#bib.bib57);[Jia et al\., 2018](https://arxiv.org/html/2609.01942#bib.bib30);[Lee et al\., 2020](https://arxiv.org/html/2609.01942#bib.bib44)\), which consists of identifying the usage of addresses \(e\.g\., scams, marketplaces\)\. Some of these approaches\([Kang et al\., 2020](https://arxiv.org/html/2609.01942#bib.bib55)\)use heuristic clustering as a first step before training a classifier\. More recently, several approaches leverage GNNs to obtain powerful representations of transaction graphs for downstream tasks\([Zhao et al\., 2025](https://arxiv.org/html/2609.01942#bib.bib56);[Zhang et al\., 2025](https://arxiv.org/html/2609.01942#bib.bib58);[Huang et al\., 2022b](https://arxiv.org/html/2609.01942#bib.bib31)\)\.

##### Enhancing Clustering Heuristics with GNNs\.

Despite their usefulness, heuristic methods have notable limitations\. They yield only*flat*cluster assignments—single\-level groupings in which addresses are either linked or not—making large clusters difficult to interpret\. Some heuristics also merge addresses based on a single transaction, which can erroneously combine unrelated users and cause cluster collapse\([Androulaki et al\., 2013](https://arxiv.org/html/2609.01942#bib.bib23);[Harrigan and Fretter, 2016](https://arxiv.org/html/2609.01942#bib.bib26)\)\. Only a few studies attempt to refine or correct the traditional heuristics\.[Möser and Narayanan \(2022\)](https://arxiv.org/html/2609.01942#bib.bib29)use a random forest to estimate the likelihood that a heuristic\-based merge is valid and block merges with low confidence, thereby mitigating cluster collapse\. Similarly,[Ermilov et al\. \(2017\)](https://arxiv.org/html/2609.01942#bib.bib52)use off\-chain information as votes for separating clusters\.

Our method differs in key ways\. Instead of assigning confidence scores to individual merges, we learn address embeddings that capture the global transaction structure while staying consistent with heuristic clusters\. Agglomerative hierarchical clustering on these embeddings yields a dendrogram that reveals nested substructures and provides a principled criterion for detecting suspicious merges, producing both a refined flat clustering and a multi\-resolution view of the address graph\.

## 3Methodology

### 3\.1Methodology Overview

We present a method to learn address embeddings consistent with standard heuristics, mapping nodes from the same cluster close together and pushing nodes from different clusters apart\. These embeddings are then used to build dendrograms whose hierarchical structure reveals discrepancies in the heuristic partitions—most notably cases of cluster collapse—and to propose candidate refinements\. Throughout the paper, letG=\(V,E\)G=\(V,E\)denote the graph, whereVVis the set of nodes \(Bitcoin addresses\) andEEthe set of edges \(value transfers\)\. We write𝒞=\{C1,…,Ck\}\\mathcal\{C\}=\\\{C\_\{1\},\\dots,C\_\{k\}\\\}for a partition ofVV\(e\.g\., obtained via heuristics\), wherekkis the number of clusters\.

##### Rationale for the Two\-Stage Methodology\.

Our approach is in line with a broad body of prior work and offers a key practical advantage: it naturally accommodates dynamic graphs with continuously arriving addresses and transactions, closely reflecting real\-world blockchain conditions\. In contrast, most end\-to\-end GNN pooling methods\([Ying et al\., 2018](https://arxiv.org/html/2609.01942#bib.bib38);[Bianchi et al\., 2020](https://arxiv.org/html/2609.01942#bib.bib39)\)construct a fixed hierarchy of merged nodes whose depth and cluster sizes are predetermined by the network architecture\. Such constraints hinder adaptation to a continually growing transaction graph and reduce the interpretability of the resulting merges\. Other pooling approaches\([Lee et al\., 2019](https://arxiv.org/html/2609.01942#bib.bib42)\)merely score and retain important nodes without producing a true hierarchical clustering, offering saliency rather than an interpretable dendrogram of successive merges\.

### 3\.2Data Acquisition and Graph Construction

We construct our graphs using the pipeline of[Schnoering and Vazirgiannis \(2025\)](https://arxiv.org/html/2609.01942#bib.bib15)111[https://github\.com/hugoschnoering2/BTCGraphConstruction](https://github.com/hugoschnoering2/BTCGraphConstruction)\. The procedure follows the steps outlined in the introduction—parsing the blockchain, extracting transactions, and forming entity\-to\-entity links—but, unlike the original work, we do not pre\-cluster addresses into user entities\. The resulting network is a directed graph whose nodes are addresses\. User clusters serving as heuristic training labels for supervised learning are obtained with the same set of address\-clustering heuristics as in[Schnoering et al\. \(2024\)](https://arxiv.org/html/2609.01942#bib.bib16), also implemented in the above GitHub repository\. Constructing a graph from the entire history would yield billions of nodes and edges, rendering most algorithms intractable\. We therefore sample a subset of transactions from a contiguous block interval to build the graph; the sampling strategy is described in Appendix[A\.1\.1](https://arxiv.org/html/2609.01942#A1.SS1.SSS1)\. For complete implementation details, we refer readers to the original paper and accompanying code\. The raw blockchain data for graph construction and clustering were obtained by running Bitcoin Core222[https://bitcoin\.org/en/bitcoin\-core](https://bitcoin.org/en/bitcoin-core)\.

### 3\.3Learning Node Embeddings with GNNs and Contrastive Loss

We train a GNNggto produce node embeddings consistent with the clustering𝒞\\mathcal\{C\}: nodes within the same cluster \(user\) should have similar embeddings, whereas embeddings of nodes from different clusters should be dissimilar\. To enforce this, we adopt the contrastive InfoNCE loss\([Oord et al\., 2018](https://arxiv.org/html/2609.01942#bib.bib32);[Chen et al\., 2020](https://arxiv.org/html/2609.01942#bib.bib33)\)

ℒ=𝔼ℙα​\[−log⁡exp⁡\(g⁡\(X\)⋅g⁡\(X\+\)/τ\)exp⁡\(g⁡\(X\)⋅g⁡\(X\+\)/τ\)\+∑i=1pexp⁡\(g⁡\(X\)⋅g⁡\(Xi−\)/τ\)\],\\mathcal\{L\}=\\mathbb\{E\}\_\{\\mathbb\{P\}\_\{\\alpha\}\}\\\!\\left\[\-\\log\\frac\{\\exp\\bigl\(g\(X\)\\\!\\cdot\\\!g\(X^\{\+\}\)/\\tau\\bigr\)\}\{\\exp\\bigl\(g\(X\)\\\!\\cdot\\\!g\(X^\{\+\}\)/\\tau\\bigr\)\+\\sum\_\{i=1\}^\{p\}\\\!\\exp\\bigl\(g\(X\)\\\!\\cdot\\\!g\(X^\{\-\}\_\{i\}\)/\\tau\\bigr\)\}\\right\],\(1\)whereℙα\\mathbb\{P\}\_\{\\alpha\}is the sampling distribution over tuples of anchor, positive, and negative nodes,τ\\tauis a temperature hyperparameter, andppis the number of negative samples\. For each anchorX∈VX\\in V, the positive sampleX\+X^\{\+\}is drawn from the same cluster, while the negatives\{Xi−\}i=1p\\\{X^\{\-\}\_\{i\}\\\}\_\{i=1\}^\{p\}come from different clusters\. Clusters are drawn from a mixture of uniform and size\-proportional sampling controlled byα\\alpha, and nodes are then sampled uniformly within each chosen cluster\. Our use of a contrastive objective is theoretically aligned with previous works\([HaoChen et al\., 2021](https://arxiv.org/html/2609.01942#bib.bib50);[Tan et al\., 2024](https://arxiv.org/html/2609.01942#bib.bib49)\), which prove that contrastive losses recover eigenvector\-like representations of an underlying data graph, yielding cluster\-separable embeddings under mild connectivity assumptions\. Full details of this sampling scheme are provided in Appendix[B\.1](https://arxiv.org/html/2609.01942#A2.SS1)\. Although the formula omits explicit normalization, we normalize embeddings in practice so that the dot product computes cosine similarity\.

### 3\.4Detecting and Mitigating Potential Cluster Collapse

We perform agglomerative hierarchical clustering on the embeddings using cosine distance, consistent with the contrastive loss\. Starting from the coarse partition𝒞\\mathcal\{C\}, we cluster eachCiC\_\{i\}independently, building a dendrogram that records the merge distances within every initial community\.

Given a thresholdλ\>0\\lambda\>0, we flag as suspicious any merge whose cosine distance exceedsλ\\lambda\. This provides a principled way to flag suspicious merges—likely combining addresses from different users—and highlights potential failures of the original flat clustering\. To mitigate such potential collapses, we split the affected clusters into their hierarchical subcomponents, yielding a refined partition that may better reflect the true user structure\.

Mathematically, each dendrogram induces an ultrametricdud\_\{u\}on the node setVV, wheredu​\(x,y\)d\_\{u\}\(x,y\)is the height of the lowest common ancestor ofxxandyy\. Two nodesxxandyyare grouped together if they belong to the same initial clusterCiC\_\{i\}and satisfydu​\(x,y\)<λd\_\{u\}\(x,y\)<\\lambda\. This refinement process is illustrated in Figure[1](https://arxiv.org/html/2609.01942#S3.F1.fig1)\.

Figure 1:Example of a refinement\. The dotted line represents the cut\. Sub\-clusters are distinguished by node fill patterns\. Merges above the threshold are flagged as potential collapses\.A practical variant of this approach uses heuristic\-generated clusters as the initial partition, motivated by the observation that such heuristics often merge distinct communities \(i\.e\., distinct Bitcoin users\)\.

## 4Theoretical Guiding Intuitions

We provide a theoretical intuition for why GNN embeddings can separate nodes according to cluster membership in a hierarchical dendrogram under idealized conditions\. Letddbe the working distance onVV\. We build a dendrogram fromddusing single, average, or complete linkage\. Assume the ground\-truth clusters are welldd\-separated: there exist constants0<r<s0<r<ssuch thatd⁡\(x,y\)≤r<s≤d⁡\(x,z\)d\(x,y\)\\leq r<s\\leq d\(x,z\)for allx,y∈Cℓx,y\\in C\_\{\\ell\}and everyz∈Cmz\\in C\_\{m\}withℓ≠m\\ell\\neq m\. In other words, intra\-cluster distances are uniformly smaller than inter\-cluster distances\. It then follows that any horizontal cut of this dendrogram at a thresholdλ∈\(r,s\)\\lambda\\in\(r,s\)exactly recovers𝒞\\mathcal\{C\}; the resulting flat clustering coincides with the ground truth\. Although these conditions are stronger than those typically encountered in practice, they provide a clean idealized framework for interpreting the analysis that follows and already motivate the use of a contrastive loss\([HaoChen et al\., 2021](https://arxiv.org/html/2609.01942#bib.bib50);[Tan et al\., 2024](https://arxiv.org/html/2609.01942#bib.bib49)\)\. The formal statements and derivations are provided in Appendix[F](https://arxiv.org/html/2609.01942#A6)\.

##### Notation\.

LetLLbe the \(unnormalized\) graph Laplacian ofGG, defined asL=D−A,L=D\-A,whereAAis the adjacency matrix ofGGandDDis the diagonal degree matrix with entriesDi​i=∑jAi​jD\_\{ii\}=\\sum\_\{j\}A\_\{ij\}\. Letλ1≤λ2≤⋯≤λn\\lambda\_\{1\}\\leq\\lambda\_\{2\}\\leq\\dots\\leq\\lambda\_\{n\}be its eigenvalues andu1,…,unu\_\{1\},\\dots,u\_\{n\}the associated orthonormal eigenvectors, which form an orthonormal basis ofℝn\\mathbb\{R\}^\{n\}\. LetU∈ℝn×nU\\in\\mathbb\{R\}^\{n\\times n\}be the matrix whose columns are these eigenvectors\. The spectral decomposition ofLLisL=U​D​U⊤L=UDU^\{\\top\}, whereD=diag⁡\(λ1,…,λn\)D=\\mathrm\{diag\}\(\\lambda\_\{1\},\\dots,\\lambda\_\{n\}\)is the diagonal matrix of eigenvalues\. LetUk∈ℝn×kU\_\{k\}\\in\\mathbb\{R\}^\{n\\times k\}be the matrix formed by the firstkkeigenvectors\. For a nodei∈Vi\\in V, its spectral embedding iseis=\(ui,1,ui,2,…,ui,k\)∈ℝke\_\{i\}^\{s\}=\(u\_\{i,1\},u\_\{i,2\},\\dots,u\_\{i,k\}\)\\in\\mathbb\{R\}^\{k\}, wherekkis the number of clusters in the partition𝒞\\mathcal\{C\}\. We write‖x‖2\\\|x\\\|\_\{2\}for the Euclidean norm of a vectorxx\. For any matrixAA,A⊤A^\{\\top\}denotes its transpose,σmin​\(A\)\\sigma\_\{\\min\}\(A\)the smallest singular value ofAA, and‖A‖op\\\|A\\\|\_\{\\mathrm\{op\}\}the operator norm ofAAinduced by∥⋅∥2\\\|\\cdot\\\|\_\{2\}\.

### 4\.1Results

Building on the perfect\-cut criterion above, our goal is to derive a separability condition on the problem data that guarantees a dendrogram built from GNN embeddings admits such a perfect cut\. Both results in this section assume that the working distance is Euclidean\. The arguments, however, remain valid for cosine distance provided that the GNN embeddings lie on a common sphere\. As a first step, Lemma[1](https://arxiv.org/html/2609.01942#Thmtheorem1)establishes an analogous condition for spectral embeddings\. This intermediate result is natural because GNNs typically act as low\-pass spectral filters\([Nt and Maehara, 2019](https://arxiv.org/html/2609.01942#bib.bib36)\), so their embeddings concentrate in the subspace spanned by the Laplacian eigenvectors with the smallest eigenvalues, i\.e\., the classical spectral embeddings\([Von Luxburg, 2007](https://arxiv.org/html/2609.01942#bib.bib11)\)\. The result involves the spectral distance between the LaplacianLLand the LaplacianL∘L^\{\\circ\}of an*ideal cluster graph*, where two nodes are connected if and only if they belong to the same cluster\. This ideal graph represents a perfectly homophilic scenario in which edges exist only within clusters\. The appearance of this quantity is motivated by empirical observations on the data, where addresses controlled by the same user tend to form connected subgraphs\.

###### Lemma 1\.

The spectral embeddings are cluster\-separable whenever

M:=4​2​k​\(1−1Smax\)​‖L−L∘‖op<12​Smax,M:=4\\sqrt\{2k\}\\,\\Bigl\(1\-\\tfrac\{1\}\{S\_\{\\max\}\}\\Bigr\)\\,\\\|L\-L^\{\\circ\}\\\|\_\{\\mathrm\{op\}\}<\\frac\{1\}\{\\sqrt\{2S\_\{\\max\}\}\},whereSmaxS\_\{\\max\}is the size of the largest cluster, andL∘L^\{\\circ\}is the Laplacian of the ideal cluster graph\.

The proof in Appendix[F\.1](https://arxiv.org/html/2609.01942#A6.SS1)relies on a version of the Davis–Kahan theorem from matrix perturbation theory\. The separability condition is satisfied whenever the graph LaplacianLLis sufficiently close to the ideal block\-diagonal Laplacian\.

We assume that the node embeddingsHHproduced by the GNN can be written asH=p⁡\(L\)​X​WH=p\(L\)\\,XW, whereppis a polynomial,XXis the matrix of initial node features, andWWis the learned weight matrix \(as in the linearized GCN\([Kipf, 2016](https://arxiv.org/html/2609.01942#bib.bib43)\), for example\)\. Using the spectral decompositionL=U​D​U⊤L=UDU^\{\\top\}, this becomes

H=U​D~​U⊤​X​W,H=U\\,\\tilde\{D\}\\,U^\{\\top\}XW,whereD~=diag⁡\(p⁡\(λ1\),…,p⁡\(λn\)\)\\tilde\{D\}=\\mathrm\{diag\}\(p\(\\lambda\_\{1\}\),\\ldots,p\(\\lambda\_\{n\}\)\)\. The polynomialppacts as a*spectral filter*, selectively amplifying or attenuating the eigencomponents ofLLaccording to their eigenvalues\. In the special case of an ideal low\-pass filter,p\(λi\)=𝟏\{i≤k\}p\(\\lambda\_\{i\}\)=\\mathbf\{1\}\_\{\\\{i\\leq k\\\}\}, so the embeddings lie entirely in the subspace spanned by the firstkkeigenvectors\. To measure how well a GNN approximates this ideal filter, we defineα=maxi≤k⁡\|p⁡\(λi\)\|\\alpha=\\max\_\{i\\leq k\}\|p\(\\lambda\_\{i\}\)\|,β=maxi\>k⁡\|p⁡\(λi\)\|\\beta=\\max\_\{i\>k\}\|p\(\\lambda\_\{i\}\)\|, andγ=mini≤k⁡\|p⁡\(λi\)\|\\gamma=\\min\_\{i\\leq k\}\|p\(\\lambda\_\{i\}\)\|\. Theorem[2](https://arxiv.org/html/2609.01942#Thmtheorem2)transfers this spectral result to the linearized GNN embeddings, yielding a sufficient separability condition for the existence of a perfect cut in this idealized setting\.

###### Theorem 2\.

The GNN embeddings are cluster\-separable whenever

‖X​W‖op​\(β\+α​M\)<γ​σmin​\(Uk⊤​X​W\)​\(2/Smax−M\)\.\\\|XW\\\|\_\{\\mathrm\{op\}\}\\bigl\(\\beta\+\\alpha M\\bigr\)\\;<\\;\\gamma\\,\\sigma\_\{\\min\}\\\!\\bigl\(U\_\{k\}^\{\\top\}XW\\bigr\)\\left\(\\sqrt\{2/S\_\{\\max\}\}\-M\\right\)\.

The embeddings learned by the GNN inherit the geometric separability of the spectral embeddings, up to perturbations controlled by the low\-pass approximation quality ofppand by the alignment of the feature matrixX​WXWwith the leading eigenspace\. Because the left\-hand side of the inequality is positive, the separability condition can be satisfied only if three requirements are met: \(i\)γ\>0\\gamma\>0, so the GNN retains all eigencomponents of the informative subspace; \(ii\)σmin​\(Uk⊤​X​W\)\>0\\sigma\_\{\\min\}\(U\_\{k\}^\{\\top\}XW\)\>0, ensuring that the transformed features are not orthogonal to this subspace; and \(iii\)M≤2/SmaxM\\leq\\sqrt\{2/S\_\{\\max\}\}, meaning the observed graph is sufficiently close to the ideal block\-diagonal Laplacian so that spectral embeddings themselves already separate the clusters\.

We emphasize that these results are not intended as directly verifiable guarantees on real Bitcoin transaction graphs\. Rather, they formalize the geometric intuition that hierarchical refinement is meaningful when learned embeddings exhibit a separation between intra\-cluster and inter\-cluster distances\.

### 4\.2Related Work

Spectral embeddings have long been central to graph clustering\([Von Luxburg, 2007](https://arxiv.org/html/2609.01942#bib.bib11)\)\. Most theoretical analyses relate these embeddings to the*optimal*solutions of node\-partitioning problems, including RatioCut minimization\([Von Luxburg, 2007](https://arxiv.org/html/2609.01942#bib.bib11)\),kk\-way partitioning\([Peng et al\., 2015](https://arxiv.org/html/2609.01942#bib.bib9)\), and maximum\-margin clustering\([Hofmeyr, 2020](https://arxiv.org/html/2609.01942#bib.bib10)\)\. The guarantees in these works require the reference clustering to coincide with the optimal solution of the respective problem\. Our approach makes no such assumption\. We instead study graphs that are small perturbations of an*ideal cluster graph*whose connected components match the ground\-truth clusters, and we apply matrix perturbation theory to obtain sufficient separability conditions\. This technique was also used by[Ng et al\. \(2001\)](https://arxiv.org/html/2609.01942#bib.bib8)to bound intra\-cluster variance\. In contrast, we establish*pairwise*bounds—both within and across clusters—yielding separability conditions that ensure a perfect cut\.

## 5Experimental Setup

All experiments were performed on a Mac M3 Max equipped with 36 GB of RAM, using only CPU computation and no GPU acceleration\.

We use the pipeline described in Section[3](https://arxiv.org/html/2609.01942#S3)to generate graphs from Bitcoin transactions\. In total, we construct three graphs for training, one for validation, and one for testing\. To avoid information leakage, transaction sets are sampled from non\-overlapping block intervals so that no transaction appears in more than one graph\. The main characteristics of these graphs are provided in Appendix[A](https://arxiv.org/html/2609.01942#A1), and all datasets, including the graphs used in the experiments with ground\-truth labels in Section[6\.3](https://arxiv.org/html/2609.01942#S6.SS3), are publicly available on Zenodo\([Schnoering and Vazirgiannis, 2026](https://arxiv.org/html/2609.01942#bib.bib1)\)at[https://doi\.org/10\.5281/zenodo\.22239038](https://doi.org/10.5281/zenodo.22239038)under the CC BY 4\.0 license\.

Before being fed to the GNNs, features undergo the normalization and log\-scaling procedure detailed in Appendix[B\.2](https://arxiv.org/html/2609.01942#A2.SS2)\. This step ensures consistent feature distributions across the different graphs\.

### 5\.1Training

##### Setup\.

We train two\-layer GNNs to minimize the contrastive loss of Equation[1](https://arxiv.org/html/2609.01942#S3.E1), monitoring progress by evaluating the same loss on a validation graph\. We experiment with three popular architectures: Graph Convolutional Network \(GCN\)\([Kipf, 2016](https://arxiv.org/html/2609.01942#bib.bib43)\), GraphSAGE\([Hamilton et al\., 2017](https://arxiv.org/html/2609.01942#bib.bib14)\), and Graph Attention Network \(GAT\)\([Veličković et al\., 2017](https://arxiv.org/html/2609.01942#bib.bib18)\)\. Optimization uses Adam\([Kingma and Ba, 2014](https://arxiv.org/html/2609.01942#bib.bib17)\)with a learning rate halved when the validation loss does not improve for 20 consecutive epochs\. Because we have three training graphs, we cycle through them every 15 epochs to promote generalization\. To accelerate training, we adopt neighborhood sampling\([Hamilton et al\., 2017](https://arxiv.org/html/2609.01942#bib.bib14)\), drawing 15 neighbors for the first GNN layer and 5 for the second\. All experiments rely on thePyTorch Geometricimplementations of GNN models, the Adam optimizer, learning\-rate scheduler, and neighbor sampling\. The code used in this study is publicly available at[https://github\.com/hugoschnoering2/btc\-graph\-hc](https://github.com/hugoschnoering2/btc-graph-hc)\. Unless otherwise specified, all hyperparameters are listed in Table[6](https://arxiv.org/html/2609.01942#A2.T6)of Appendix[B\.3](https://arxiv.org/html/2609.01942#A2.SS3)\.

##### Model Variations\.

We evaluate three main variations of the base model\. \(1\) Because the constructed graphs are directed, we optionally symmetrize them before input to the GNN\. \(2\) Since edges carry attributes, we can include or ignore these edge features whenever the architecture supports them\. \(3\) We optionally add a structural positional encoding to enhance locality\. GNN message passing tends to make nodes with similar neighborhoods appear similar—even when they are far apart\([Xu et al\., 2019](https://arxiv.org/html/2609.01942#bib.bib12)\)—which can spuriously cluster structurally alike but unrelated nodes\. Yet Bitcoin addresses belonging to the same user are usually close in the graph, as they often participate in the same transactions\. To exploit this property, we follow the position\-aware GNN framework\([You et al\., 2019](https://arxiv.org/html/2609.01942#bib.bib7)\): we select the highest\-degree nodes as landmarks and represent each node by its vector of shortest\-path distances to these landmarks\. These distances are converted to similarities viax↦\(1\+x\)−1x\\mapsto\(1\+x\)^\{\-1\}and normalized dimension\-wise\. The resulting distance\-based vector is then concatenated with the original node feature vector before message passing\.

### 5\.2Evaluation

We evaluate our method by its ability to recover both hierarchical and flat clusterings consistent with the heuristic partition\. For the hierarchical step, we apply agglomerative clustering with cosine distance on the GNN embeddings using average linkage\. Because the graphs are large and computing the full pairwise distance matrix is impractical, we first obtain a coarse partition with the Leiden algorithm\([Traag et al\., 2019](https://arxiv.org/html/2609.01942#bib.bib13)\), limiting the maximum community size to 65 000 nodes to control memory usage, following the strategy described in Section[3\.4](https://arxiv.org/html/2609.01942#S3.SS4)\.

##### Metrics\.

We score the resulting dendrograms with*dendrogram purity*\([Heller and Ghahramani, 2005](https://arxiv.org/html/2609.01942#bib.bib2)\), which ranges from 0 to 1 and measures how well nodes from the same heuristic cluster merge together\. Flat clusterings are obtained by cutting each dendrogram at a thresholdλ\\lambda\(Figure[1](https://arxiv.org/html/2609.01942#S3.F1.fig1)\)\. This threshold is selected by first maximizing the silhouette score locally within each Leiden community\([Rousseeuw, 1987](https://arxiv.org/html/2609.01942#bib.bib35)\), and then aggregating the resulting local thresholds through a size\-weighted average\. Full details are provided in Appendix[C\.2](https://arxiv.org/html/2609.01942#A3.SS2)\. We then compare the flat partition to the heuristic partition using Normalized Mutual Information \(NMI\) and Adjusted Rand Index \(ARI\)\([Vinh et al\., 2009](https://arxiv.org/html/2609.01942#bib.bib34)\): NMI captures global agreement and is robust to cluster\-size imbalance, while ARI emphasizes local consistency but is more sensitive to class imbalance\. Additional implementation details on how these metrics are computed, as well as their formal definitions, are provided in Appendix[C\.1](https://arxiv.org/html/2609.01942#A3.SS1)\. For all metrics, we evaluate only nodes with degree≥2\\geq 2, excluding peripheral addresses that often lack sufficient transactional context for reliable user clustering and can artificially inflate cluster counts, making global metrics less informative\.

##### Baselines\.

To highlight the added value of the contrastive loss, we compare our model to three unsupervised baselines: \(i\) an untrained GAT, \(ii\) a GAT trained as a non\-probabilistic Graph Auto\-Encoder \(GAE\)\([Kipf and Welling, 2016](https://arxiv.org/html/2609.01942#bib.bib40)\), and \(iii\) a GAT trained with Deep Graph Infomax \(DGI\)\([Veličković et al\., 2018](https://arxiv.org/html/2609.01942#bib.bib41)\), which maximizes mutual information between local and global representations\. All baselines produce node embeddings that are clustered exactly as in our contrastive pipeline\. Implementation details are provided in Appendix[B\.5](https://arxiv.org/html/2609.01942#A2.SS5)\.

## 6Results

### 6\.1Ablation Study

We report in Table[1](https://arxiv.org/html/2609.01942#S6.T1)the performance results for different variations, including graph symmetrization, use of edge features, and the number of landmarks in the structural embedding\. For each model variation, results are averaged over five runs with different random seeds on the test graph\. Additional experiments on the embedding dimension, the sampling parameterα\\alpha, and the number of negative samples in the contrastive loss, as well as empirical indicators related to the theoretical intuitions, are reported in Appendix[D](https://arxiv.org/html/2609.01942#A4)\.

ModelSym\.Edge feat\.\# LMDPNMIARILouvain✓\\checkmarknanana0\.642​\(±0\.000\)0\.642\\ \(\\pm 0\.000\)0\.289​\(±0\.000\)0\.289\\ \(\\pm 0\.000\)Leiden✓\\checkmarknanana0\.665​\(±0\.000\)0\.665\\ \(\\pm 0\.000\)0\.311​\(±0\.000\)0\.311\\ \(\\pm 0\.000\)Random GAT✓\\checkmark×\\times00\.699​\(±0\.010\)0\.699\\ \(\\pm 0\.010\)0\.692​\(±0\.008\)0\.692\\ \(\\pm 0\.008\)0\.557​\(±0\.005\)0\.557\\ \(\\pm 0\.005\)GAE✓\\checkmark×\\times00\.738​\(±0\.008\)0\.738\\ \(\\pm 0\.008\)0\.755​\(±0\.011\)0\.755\\ \(\\pm 0\.011\)0\.609​\(±0\.015\)0\.609\\ \(\\pm 0\.015\)DGI✓\\checkmark×\\times00\.683​\(±0\.004\)0\.683\\ \(\\pm 0\.004\)0\.685​\(±0\.008\)0\.685\\ \(\\pm 0\.008\)0\.558​\(±0\.041\)0\.558\\ \(\\pm 0\.041\)GAT×\\times×\\times000\.638​\(±0\.013\)0\.638\\ \(\\pm 0\.013\)0\.709​\(±0\.008\)0\.709\\ \(\\pm 0\.008\)0\.341​\(±0\.085\)0\.341\\ \(\\pm 0\.085\)×\\times×\\times64640\.682​\(±0\.002\)0\.682\\ \(\\pm 0\.002\)0\.728​\(±0\.001\)0\.728\\ \(\\pm 0\.001\)0\.588​\(±0\.010\)0\.588\\ \(\\pm 0\.010\)×\\times×\\times1281280\.684​\(±0\.002\)0\.684\\ \(\\pm 0\.002\)0\.737​\(±0\.004\)0\.737\\ \(\\pm 0\.004\)0\.593​\(±0\.009\)0\.593\\ \(\\pm 0\.009\)×\\times×\\times2562560\.678​\(±0\.002\)0\.678\\ \(\\pm 0\.002\)0\.728​\(±0\.004\)0\.728\\ \(\\pm 0\.004\)0\.588​\(±0\.005\)0\.588\\ \(\\pm 0\.005\)GAT×\\times✓\\checkmark000\.635​\(±0\.005\)0\.635\\ \(\\pm 0\.005\)0\.707​\(±0\.006\)0\.707\\ \(\\pm 0\.006\)0\.344​\(±0\.049\)0\.344\\ \(\\pm 0\.049\)×\\times✓\\checkmark64640\.680​\(±0\.002\)0\.680\\ \(\\pm 0\.002\)0\.730​\(±0\.002\)0\.730\\ \(\\pm 0\.002\)0\.586​\(±0\.007\)0\.586\\ \(\\pm 0\.007\)×\\times✓\\checkmark1281280\.683​\(±0\.005\)0\.683\\ \(\\pm 0\.005\)0\.733​\(±0\.004\)0\.733\\ \(\\pm 0\.004\)0\.585​\(±0\.005\)0\.585\\ \(\\pm 0\.005\)×\\times✓\\checkmark2562560\.678​\(±0\.002\)0\.678\\ \(\\pm 0\.002\)0\.732​\(±0\.005\)0\.732\\ \(\\pm 0\.005\)0\.582​\(±0\.006\)0\.582\\ \(\\pm 0\.006\)GAT✓\\checkmark×\\times000\.771¯​\(±0\.004\)\\underline\{0\.771\}\\ \(\\pm 0\.004\)0\.760¯​\(±0\.015\)\\underline\{0\.760\}\\ \(\\pm 0\.015\)0\.637¯​\(±0\.007\)∗\\underline\{0\.637\}\\ \(\\pm 0\.007\)^\{\*\}✓\\checkmark×\\times64640\.789​\(±0\.004\)∗⁣∗0\.789\\ \(\\pm 0\.004\)^\{\*\*\}0\.768​\(±0\.002\)∗⁣∗0\.768\\ \(\\pm 0\.002\)^\{\*\*\}0\.627​\(±0\.003\)0\.627\\ \(\\pm 0\.003\)✓\\checkmark×\\times1281280\.784​\(±0\.002\)0\.784\\ \(\\pm 0\.002\)0\.764​\(±0\.011\)0\.764\\ \(\\pm 0\.011\)0\.620​\(±0\.017\)0\.620\\ \(\\pm 0\.017\)✓\\checkmark×\\times2562560\.785​\(±0\.002\)∗0\.785\\ \(\\pm 0\.002\)^\{\*\}0\.759​\(±0\.012\)0\.759\\ \(\\pm 0\.012\)0\.614​\(±0\.014\)0\.614\\ \(\\pm 0\.014\)GAT✓\\checkmark✓\\checkmark000\.773​\(±0\.006\)0\.773\\ \(\\pm 0\.006\)0\.762​\(±0\.013\)0\.762\\ \(\\pm 0\.013\)0\.649​\(±0\.012\)∗⁣∗0\.649\\ \(\\pm 0\.012\)^\{\*\*\}✓\\checkmark✓\\checkmark64640\.782​\(±0\.004\)0\.782\\ \(\\pm 0\.004\)0\.756​\(±0\.007\)0\.756\\ \(\\pm 0\.007\)0\.609​\(±0\.006\)0\.609\\ \(\\pm 0\.006\)✓\\checkmark✓\\checkmark1281280\.778​\(±0\.003\)0\.778\\ \(\\pm 0\.003\)0\.756​\(±0\.013\)0\.756\\ \(\\pm 0\.013\)0\.611​\(±0\.019\)0\.611\\ \(\\pm 0\.019\)✓\\checkmark✓\\checkmark2562560\.780​\(±0\.002\)0\.780\\ \(\\pm 0\.002\)0\.755​\(±0\.010\)0\.755\\ \(\\pm 0\.010\)0\.612​\(±0\.011\)0\.612\\ \(\\pm 0\.011\)GCN✓\\checkmark×\\times000\.722​\(±0\.001\)0\.722\\ \(\\pm 0\.001\)0\.731​\(±0\.009\)0\.731\\ \(\\pm 0\.009\)0\.598​\(±0\.007\)0\.598\\ \(\\pm 0\.007\)GraphSAGE✓\\checkmark×\\times000\.765​\(±0\.003\)0\.765\\ \(\\pm 0\.003\)0\.766​\(±0\.011\)∗0\.766\\ \(\\pm 0\.011\)^\{\*\}0\.630​\(±0\.008\)0\.630\\ \(\\pm 0\.008\)Table 1:Performance across different variations: graph symmetrization \(Sym\.\), edge features \(Edge feat\.\), number of landmarks \(\# LM\), with evaluation metrics NMI, ARI, and dendrogram purity \(DP\), not applicable \(na\)\. The best score for each metric is marked with∗∗, the second\-best with∗, and the performance of the model with all default parameters isunderlined\. All metrics in this table are computed with respect to heuristic\-derived labels\.All baselines achieve ARI scores well above zero—substantially better than random clustering—confirming that graph topology alone carries meaningful cluster information and supporting the homophily hypothesis\. Louvain and Leiden remain significantly below all GNN\-based approaches, both in NMI and ARI\. The untrained GAT already substantially outperforms Louvain and Leiden, indicating that node features alone contain strong clustering signals\. This is consistent with previous results showing that even untrained message\-passing models perform well on structured data\([Huang et al\., 2022a](https://arxiv.org/html/2609.01942#bib.bib45)\)\. Among unsupervised baselines, GAE achieves higher dendrogram purity \(DP\) than the random GAT and also improves NMI and ARI, suggesting that link\-reconstruction objectives capture useful structural regularities\. DGI performs comparably to the random GAT in DP and NMI, while exhibiting slightly more variable ARI scores, indicating less stable local separation\.

When training GAT models on non\-symmetrized graphs, performance deteriorates markedly across all metrics compared to the untrained GAT\. This highlights the importance of reciprocal connectivity for capturing address relationships\. Introducing structural positional encodings \(landmarks\) substantially improves performance in the non\-symmetric setting\. In contrast, incorporating edge features in the non\-symmetrized case does not provide consistent gains and yields nearly identical results to the feature\-free setting\.

All symmetrized GAT variants outperform the baselines across metrics\. The best overall dendrogram purity and NMI are achieved with 64 landmarks and no edge features\. Interestingly, the highest ARI is obtained with symmetrization and edge features but without positional encoding, indicating that flat clustering quality may benefit from edge attributes even when hierarchical purity does not\. Structural positional encodings consistently improve dendrogram purity in the symmetrized setting, though their impact on NMI and ARI is less systematic\. The optimal number of landmarks appears to be 64, with diminishing or slightly negative returns beyond that\. This suggests that moderate structural bias improves hierarchical coherence, whereas excessive positional information may introduce redundancy or overfitting effects\.

Among alternative architectures, GraphSAGE slightly outperforms the default GAT in NMI and achieves competitive ARI, whereas GCN remains below\. Nevertheless, the best overall performance across hierarchical and flat metrics is still obtained with the GAT architecture, supporting its use as the primary model in our framework\.

### 6\.2Illustrating Cluster Refinement

We illustrate how the procedure of Section[3](https://arxiv.org/html/2609.01942#S3)can flag and mitigate potential cluster collapse\. Starting from the heuristic clustering, we build a hierarchical clustering within each heuristic cluster and obtain a refined flat partition by cutting each dendrogram at the thresholdλ\\lambdathat maximizes the silhouette score\. Figure[2](https://arxiv.org/html/2609.01942#S6.F2)shows the resulting dendrogram for a representative cluster, with the selected cut level indicated\. Its structure reveals the sequence of merges and highlights several late merges occurring above the optimal threshold\. In particular, the final two subclusters merge at a cosine distance of 0\.45, well above the chosen cut, indicating a candidate split that may deserve further inspection\. A few other merges also exceed the threshold, although most nodes merge below it into a single coherent group\.

![Refer to caption](https://arxiv.org/html/2609.01942v1/images/dendrogram_example_1_crop.png)Figure 2:Dendrogram for a representative heuristic cluster\. The dashed horizontal line indicates the cut levelλ\\lambdaselected to maximize the global silhouette score\.Figure[3](https://arxiv.org/html/2609.01942#S6.F3)displays the minimal subgraph induced by the cluster and its neighbors\. Cutting the dendrogram at the optimal threshold reveals coherent sub\-groups, offering a clearer view of the cluster’s internal organization\. This approach naturally scales to much larger clusters—tens of thousands of nodes in our data and potentially millions in larger transaction sets—where direct graph visualization becomes impractical\. Dendrograms provide a hierarchical, navigable representation that exposes meaningful substructures at multiple resolutions\.

![Refer to caption](https://arxiv.org/html/2609.01942v1/images/graph_example_1_crop.png)Figure 3:Minimal subgraph induced by the representative cluster and its immediate neighbors\. Nodes belonging to the cluster are numbered, while external neighbors remain unnumbered\. Cutting the dendrogram at the optimal threshold reveals distinct sub\-groups, shown here with different gray shades and marker shapes\.
### 6\.3Additional Experiments with Independent Ground\-Truth Labels

In each experiment, we focus on transactions for which ground\-truth labels specify whether pairs of addresses belong to the same entity\. For every labeled transaction, we extract a local transaction subgraph using the sampling procedure described in Section[3\.2](https://arxiv.org/html/2609.01942#S3.SS2)\(see Appendix[A\.1\.2](https://arxiv.org/html/2609.01942#A1.SS1.SSS2)for details\), and construct the corresponding address\-level graph\. On each resulting graph, we compare three clustering strategies: \(i\) standard heuristic clustering, \(ii\) our default GNN–HAC pipeline, and \(iii\) a hybrid approach in which GNN embeddings refine the heuristic partition as described in Section[3\.4](https://arxiv.org/html/2609.01942#S3.SS4)\. We further evaluate three linkage criteria and three dendrogram\-cutting strategies \(Appendix[C\.2](https://arxiv.org/html/2609.01942#A3.SS2)\)\.

In addition, we compare our approach to the refinement strategy of[Möser and Narayanan \(2022\)](https://arxiv.org/html/2609.01942#bib.bib29), which, to our knowledge, constitutes the only prior attempt at systematically refining heuristic\-based address clustering\. All implementation details required to reproduce this baseline, including our re\-implementation and evaluation protocol, are provided in Appendix[E](https://arxiv.org/html/2609.01942#A5)\.

Clustering quality is assessed using binary pairwise metrics: a prediction is correct if it groups addresses from the same entity or separates addresses from different entities, and incorrect otherwise\. To prevent transactions with many labeled addresses from dominating the evaluation, we consider at most five randomly sampled labeled pairs per graph\.

#### 6\.3\.1Entity Labels

We use the dataset of approximately 100,000 addresses labeled with entity names introduced in[Schnoering and Vazirgiannis \(2025\)](https://arxiv.org/html/2609.01942#bib.bib15)\. After excluding addresses associated with individuals, we sample 500 transactions between blocks 550,000 and 700,000 that involve at least two distinct labeled addresses\. For each sampled transaction, addresses sharing the same entity label are expected to be assigned to the same cluster, whereas addresses associated with different entities should be placed in separate clusters\. All experiments are repeated over five random seeds, corresponding to different random samples of labeled address pairs used for evaluation\. The results are reported in Table[2](https://arxiv.org/html/2609.01942#S6.T2)\.

ModelLink\.CutTP\(%\)FP\(%\)FN\(%\)TN\(%\)bACC\(%\)F1\(%\)Heuristicsnana42\.6​\(±0\.3\)42\.6\\ \(\\pm 0\.3\)22\.7​\(±0\.2\)22\.7\\ \(\\pm 0\.2\)15\.8​\(±0\.5\)15\.8\\ \(\\pm 0\.5\)18\.9​\(±0\.6\)18\.9\\ \(\\pm 0\.6\)59\.2​\(±0\.7\)59\.2\\ \(\\pm 0\.7\)59\.2​\(±0\.7\)59\.2\\ \(\\pm 0\.7\)[Möser and Narayanan \(2022\)](https://arxiv.org/html/2609.01942#bib.bib29)nana41\.2​\(±0\.1\)41\.2\\ \(\\pm 0\.1\)22\.4​\(±0\.2\)22\.4\\ \(\\pm 0\.2\)17\.8​\(±0\.3\)17\.8\\ \(\\pm 0\.3\)18\.6​\(±0\.3\)18\.6\\ \(\\pm 0\.3\)57\.6​\(±0\.2\)57\.6\\ \(\\pm 0\.2\)57\.6​\(±0\.2\)57\.6\\ \(\\pm 0\.2\)GNN\-HACavg\.sil\.38\.0​\(±0\.4\)38\.0\\ \(\\pm 0\.4\)16\.7​\(±0\.9\)16\.7\\ \(\\pm 0\.9\)20\.3​\(±0\.6\)20\.3\\ \(\\pm 0\.6\)25\.0​\(±0\.7\)25\.0\\ \(\\pm 0\.7\)62\.6​\(±0\.6\)62\.6\\ \(\\pm 0\.6\)62\.3​\(±0\.5\)∗62\.3\\ \(\\pm 0\.5\)^\{\*\}GNN\-HACavg\.inc\.58\.3​\(±0\.7\)58\.3\\ \(\\pm 0\.7\)41\.7​\(±0\.7\)41\.7\\ \(\\pm 0\.7\)0\.0​\(±0\.0\)0\.0\\ \(\\pm 0\.0\)0\.0​\(±0\.0\)0\.0\\ \(\\pm 0\.0\)50\.0​\(±0\.0\)50\.0\\ \(\\pm 0\.0\)36\.8​\(±0\.3\)36\.8\\ \(\\pm 0\.3\)GNN\-HACavg\.gap\.51\.3​\(±0\.7\)51\.3\\ \(\\pm 0\.7\)32\.6​\(±0\.8\)32\.6\\ \(\\pm 0\.8\)7\.0​\(±0\.5\)7\.0\\ \(\\pm 0\.5\)9\.0​\(±0\.5\)9\.0\\ \(\\pm 0\.5\)54\.8​\(±0\.9\)54\.8\\ \(\\pm 0\.9\)51\.7​\(±1\.2\)51\.7\\ \(\\pm 1\.2\)GNN\-HACwardsil\.34\.5​\(±1\.4\)34\.5\\ \(\\pm 1\.4\)15\.5​\(±1\.0\)15\.5\\ \(\\pm 1\.0\)23\.8​\(±1\.8\)23\.8\\ \(\\pm 1\.8\)26\.2​\(±0\.8\)26\.2\\ \(\\pm 0\.8\)61\.0​\(±0\.9\)61\.0\\ \(\\pm 0\.9\)60\.4​\(±1\.1\)60\.4\\ \(\\pm 1\.1\)GNN\-HACwardinc\.38\.7​\(±1\.3\)38\.7\\ \(\\pm 1\.3\)17\.5​\(±0\.9\)17\.5\\ \(\\pm 0\.9\)19\.6​\(±1\.6\)19\.6\\ \(\\pm 1\.6\)24\.1​\(±0\.6\)24\.1\\ \(\\pm 0\.6\)62\.2​\(±1\.5\)62\.2\\ \(\\pm 1\.5\)62\.0​\(±1\.6\)62\.0\\ \(\\pm 1\.6\)GNN\-HACwardgap\.49\.3​\(±0\.8\)49\.3\\ \(\\pm 0\.8\)27\.3​\(±1\.3\)27\.3\\ \(\\pm 1\.3\)9\.0​\(±0\.9\)9\.0\\ \(\\pm 0\.9\)14\.4​\(±0\.9\)14\.4\\ \(\\pm 0\.9\)59\.5​\(±1\.0\)59\.5\\ \(\\pm 1\.0\)58\.6​\(±1\.3\)58\.6\\ \(\\pm 1\.3\)GNN\-HACcom\.sil\.28\.5​\(±1\.0\)28\.5\\ \(\\pm 1\.0\)12\.2​\(±0\.7\)12\.2\\ \(\\pm 0\.7\)29\.8​\(±1\.0\)29\.8\\ \(\\pm 1\.0\)29\.4​\(±0\.4\)29\.4\\ \(\\pm 0\.4\)59\.8​\(±0\.9\)59\.8\\ \(\\pm 0\.9\)57\.9​\(±0\.9\)57\.9\\ \(\\pm 0\.9\)GNN\-HACcom\.inc\.58\.3​\(±0\.7\)58\.3\\ \(\\pm 0\.7\)41\.6​\(±0\.7\)41\.6\\ \(\\pm 0\.7\)0\.1​\(±0\.1\)0\.1\\ \(\\pm 0\.1\)0\.1​\(±0\.1\)0\.1\\ \(\\pm 0\.1\)50\.0​\(±0\.0\)50\.0\\ \(\\pm 0\.0\)37\.0​\(±0\.3\)37\.0\\ \(\\pm 0\.3\)GNN\-HACcom\.gap\.49\.0​\(±0\.4\)49\.0\\ \(\\pm 0\.4\)30\.5​\(±1\.4\)30\.5\\ \(\\pm 1\.4\)9\.3​\(±1\.0\)9\.3\\ \(\\pm 1\.0\)11\.2​\(±1\.1\)11\.2\\ \(\\pm 1\.1\)55\.4​\(±1\.5\)55\.4\\ \(\\pm 1\.5\)53\.5​\(±1\.8\)53\.5\\ \(\\pm 1\.8\)Hybridavg\.sil\.32\.9​\(±1\.2\)32\.9\\ \(\\pm 1\.2\)8\.8​\(±0\.8\)8\.8\\ \(\\pm 0\.8\)25\.5​\(±1\.3\)25\.5\\ \(\\pm 1\.3\)32\.8​\(±0\.8\)32\.8\\ \(\\pm 0\.8\)67\.6​\(±0\.6\)∗⁣∗67\.6\\ \(\\pm 0\.6\)^\{\*\*\}65\.7​\(±0\.8\)∗⁣∗65\.7\\ \(\\pm 0\.8\)^\{\*\*\}Hybridavg\.inc\.42\.6​\(±0\.3\)42\.6\\ \(\\pm 0\.3\)22\.7​\(±0\.2\)22\.7\\ \(\\pm 0\.2\)15\.8​\(±0\.5\)15\.8\\ \(\\pm 0\.5\)18\.9​\(±0\.6\)18\.9\\ \(\\pm 0\.6\)59\.2​\(±0\.7\)59\.2\\ \(\\pm 0\.7\)59\.2​\(±0\.7\)59\.2\\ \(\\pm 0\.7\)Hybridavg\.gap\.42\.3​\(±0\.3\)42\.3\\ \(\\pm 0\.3\)22\.1​\(±0\.4\)22\.1\\ \(\\pm 0\.4\)16\.0​\(±0\.6\)16\.0\\ \(\\pm 0\.6\)19\.6​\(±0\.6\)19\.6\\ \(\\pm 0\.6\)59\.8​\(±0\.7\)59\.8\\ \(\\pm 0\.7\)59\.9​\(±0\.7\)59\.9\\ \(\\pm 0\.7\)Hybridwardsil\.34\.7​\(±0\.6\)34\.7\\ \(\\pm 0\.6\)16\.1​\(±0\.7\)16\.1\\ \(\\pm 0\.7\)23\.6​\(±1\.2\)23\.6\\ \(\\pm 1\.2\)25\.6​\(±0\.8\)25\.6\\ \(\\pm 0\.8\)60\.5​\(±1\.2\)60\.5\\ \(\\pm 1\.2\)60\.0​\(±1\.3\)60\.0\\ \(\\pm 1\.3\)Hybridcom\.sil\.23\.9​\(±0\.4\)23\.9\\ \(\\pm 0\.4\)6\.4​\(±0\.7\)6\.4\\ \(\\pm 0\.7\)34\.4​\(±0\.9\)34\.4\\ \(\\pm 0\.9\)35\.3​\(±0\.9\)35\.3\\ \(\\pm 0\.9\)62\.9​\(±1\.1\)∗62\.9\\ \(\\pm 1\.1\)^\{\*\}58\.7​\(±1\.2\)58\.7\\ \(\\pm 1\.2\)

Table 2:Clustering performance with ground\-truth entity labels\. Linkage \(Link\.\) criteria: average linkage \(avg\.\), Ward linkage \(ward\), and complete linkage \(com\.\)\. Dendrogram cut methods: silhouette\-based cut \(sil\.\), inconsistency cut \(inc\.\), and largest\-gap cut \(gap\.\)\. Metrics reported include true positives \(TP\), false positives \(FP\), false negatives \(FN\), true negatives \(TN\), along with balanced accuracy \(bACC\), defined as the mean of positive and negative recalls, and the macro\-averaged F1 score \(F1\)\. Results are averaged over five random seeds corresponding to different random samples of labeled address pairs, with standard deviations reported in parentheses\. The best score for bACC and F1 is marked with \*\*, and the second\-best with \*\.The average\-linkage / silhouette\-score configuration yields substantial improvements over the heuristic baselines\. The best results are obtained with the refinement pipeline \(Hybrid avg\./sil\.\), underscoring the importance of the hybrid approach: macro\-F1 increases from59\.2%59\.2\\%to65\.7%65\.7\\%, and balanced accuracy from59\.2%59\.2\\%to67\.6%67\.6\\%\. In addition, the false\-positive rate is reduced by more than half, from22\.7%22\.7\\%to8\.8%8\.8\\%, suggesting that the refinement mitigates some false merges in this labeled setting\. Complete linkage also strongly reduces false positives in the refinement setting, but this comes at the cost of a substantially higher false\-negative rate and therefore lower macro\-F1\. In contrast, Ward linkage exhibits more mixed behavior: it performs competitively without refinement but does not benefit from the hybrid correction step\. The largest\-gap criterion yields only modest improvements within the refinement pipeline\. Finally, the inconsistency\-based cut is generally not well suited to this task, as it either produces degenerate merge\-heavy solutions with poor negative\-class performance or collapses to behavior close to the heuristic baseline\. Importantly, the best\-performing configurations also outperform the refinement strategy of[Möser and Narayanan \(2022\)](https://arxiv.org/html/2609.01942#bib.bib29), demonstrating the added value of representation learning over rule\-based merge filtering\.

#### 6\.3\.2CoinJoin Transaction Labels

CoinJoin transactions involve multiple independent users and are explicitly designed to defeat the common\-input heuristic\([Schnoering and Vazirgiannis, 2025](https://arxiv.org/html/2609.01942#bib.bib15)\)\. Based on an analysis of open\-source CoinJoin protocol implementations,[Schnoering and Vazirgiannis \(2023\)](https://arxiv.org/html/2609.01942#bib.bib5)proposed detection heuristics capable of identifying most such transactions\. In a CoinJoin transaction, all input addresses are expected to belong to distinct entities and therefore should be assigned to different clusters\. For each protocol examined in[Schnoering and Vazirgiannis \(2023\)](https://arxiv.org/html/2609.01942#bib.bib5), we randomly selected 100 transactions between blocks 550,000 and 700,000, totaling 500 CoinJoin transactions\. Because these transactions contain only negative pairs \(i\.e\., no two labeled input addresses should be clustered together\), performance is evaluated solely through the true\-negative rate\. Classical heuristics without CoinJoin\-aware safeguards, as reported in[Schnoering et al\. \(2024\)](https://arxiv.org/html/2609.01942#bib.bib16), yield a true\-negative rate of zero under this setting\. To quantify sensitivity to the sampled CoinJoin set, we repeated only the evaluation\-set sampling procedure five times with different random seeds, while keeping the trained model fixed, and report the mean and standard deviation across the five evaluations\. Results for the different clustering methods are reported in Table[3](https://arxiv.org/html/2609.01942#S6.T3)\.

ModelLink\.CutTN\(%\)TN\(%\) \+ CoinJoin negativesHeuristicsnana0\.00\.00\.00\.0GNN\-HACavg\.sil\.25\.1​\(±1\.4\)25\.1\\ \(\\pm 1\.4\)58\.0​\(±2\.3\)58\.0\\ \(\\pm 2\.3\)GNN\-HACwardsil\.43\.9​\(±1\.5\)43\.9\\ \(\\pm 1\.5\)57\.9​\(±1\.9\)57\.9\\ \(\\pm 1\.9\)GNN\-HACcom\.sil\.45\.8​\(±1\.8\)45\.8\\ \(\\pm 1\.8\)63\.4​\(±2\.1\)63\.4\\ \(\\pm 2\.1\)Hybridavg\.sil\.14\.0​\(±0\.7\)14\.0\\ \(\\pm 0\.7\)51\.5​\(±2\.0\)51\.5\\ \(\\pm 2\.0\)Hybridwardsil\.11\.4​\(±0\.3\)11\.4\\ \(\\pm 0\.3\)30\.2​\(±0\.5\)30\.2\\ \(\\pm 0\.5\)Hybridcom\.sil\.20\.5​\(±0\.8\)20\.5\\ \(\\pm 0\.8\)53\.9​\(±2\.1\)53\.9\\ \(\\pm 2\.1\)Table 3:Clustering performance with ground\-truth CoinJoin labels\. Results are reported as mean true\-negative rate \(TN\) and standard deviation across five independently sampled CoinJoin graph datasets\. Results are shown for average linkage \(avg\.\), Ward linkage \(ward\), and complete linkage \(com\.\) combined with silhouette\-based dendrogram cuts \(sil\.\)\.Embeddings learned with the standard contrastive objective of Equation[1](https://arxiv.org/html/2609.01942#S3.E1)already improve robustness to CoinJoin\-induced false positives\. The best GNN\-HAC configuration reaches a TN rate of45\.8%45\.8\\%with complete linkage, compared to0\.0%0\.0\\%for the heuristic baseline\. The hybrid refinement setting also improves over the baseline, although its TN rates remain lower than those of the unconstrained GNN\-HAC pipeline\. To better understand these results, we analyze in Appendix[D\.4](https://arxiv.org/html/2609.01942#A4.SS4)the cosine distances between embeddings for CoinJoin negative pairs\. This analysis shows that CoinJoin inputs often remain close in the embedding space under the standard contrastive objective\. This is expected: input addresses of the same CoinJoin transaction are close in the transaction graph, yet they belong to distinct users\. CoinJoin transactions therefore introduce strongly heterophilic patterns, with many independent users interacting within the same local transaction context\. Our observations align with the findings of[Zhu et al\. \(2020\)](https://arxiv.org/html/2609.01942#bib.bib47), who demonstrate that GNNs relying on homophily can misinterpret structural proximity as semantic similarity\. CoinJoin transactions exemplify this issue in Bitcoin graphs, since they deliberately mix unrelated addresses and thus violate homophily assumptions\. This is further amplified by the divergence between the typical address connectivity and that of CoinJoin transactions, leading to negative transfer on those de facto anomalous structures\([Wang et al\., 2024](https://arxiv.org/html/2609.01942#bib.bib46)\)\.

To adapt the model to this heterophilic failure mode, we augment the training objective with a CoinJoin\-specific repulsion term, using CoinJoin input\-address pairs as hard negatives\. The resulting loss isℒ=ℒInfoNCE\+λCoinJoin​ℒCoinJoin,\\mathcal\{L\}=\\mathcal\{L\}\_\{\\mathrm\{InfoNCE\}\}\+\\lambda\_\{\\mathrm\{CoinJoin\}\}\\mathcal\{L\}\_\{\\mathrm\{CoinJoin\}\},whereλCoinJoin\\lambda\_\{\\mathrm\{CoinJoin\}\}controls the weight of the CoinJoin repulsion term\. This additional term penalizes high similarity between CoinJoin input embeddings and can be interpreted as a purely repulsive InfoNCE\-like loss\. Its full definition is provided in Appendix[B\.4](https://arxiv.org/html/2609.01942#A2.SS4), together with the hyperparameters used for the augmented training procedure\. To avoid leakage from the evaluation set, we sampled a separate set of 1,000 CoinJoin\-centered graphs used only for training\. The corresponding results are also reported in Table[3](https://arxiv.org/html/2609.01942#S6.T3)\. The augmented loss leads to substantially stronger CoinJoin robustness, with large TN gains across all linkage choices and particularly in the hybrid refinement setting\. This demonstrates that the framework can naturally adapt once the relevant heterophilic patterns are incorporated into the supervision signal\.

## Conclusion and Limitations

This work presents a principled framework for refining heuristic\-based Bitcoin address clustering through contrastive GNN embeddings that remain consistent with standard heuristics while uncovering richer hierarchical structure\. Starting from classical clustering rules, our method learns embeddings that encode heuristic\-consistent similarity and applies agglomerative hierarchical clustering to reveal substructures and flag potentially suspicious merges\. Together, these elements provide a unified toolkit—data, theory, and methodology—for moving from flat heuristic clusters to interpretable, multi\-resolution user graphs\. A key limitation, however, is the limited number of ground\-truth labels available for evaluating user clusters at scale\.

An important direction for future work is to adapt this procedure to a dynamic transaction graph that grows as new blocks and addresses appear, enabling online refinement of user clusters\. A key challenge will be scalability\. While node embeddings can be approximated by sampling subgraphs of manageable size, constructing the hierarchical structure is far less scalable, as illustrated in Appendix[G](https://arxiv.org/html/2609.01942#A7)\. Nevertheless, this limitation can be partially mitigated by sampling very local subgraphs, either around specific transactions or within narrow temporal windows\. This approximation is validated by the strong generalization to other similarly sampled subgraphs observed in the empirical results\. Future research should therefore focus on scalable hierarchical clustering techniques capable of handling continuously evolving blockchain graphs\.

##### Broader Impact\.

Bitcoin address clustering has important dual\-use implications\. While it can support legitimate forensic, compliance, and anti\-money\-laundering applications, it may also weaken the practical pseudonymity of users who rely on address separation for privacy\. All datasets and experiments in this work are derived from publicly available blockchain data and do not incorporate private off\-chain information\. Still, our results show that learned refinement methods can improve user\-level clustering in some settings, which may affect privacy\-seeking but legitimate users\. We therefore frame this work as an analysis of the strengths and failure modes of heuristic clustering, including known privacy mechanisms such as CoinJoin, rather than as a production\-ready deanonymization tool\.

##### LLM Usage\.

The research ideas, work, and content presented in this paper were fully designed and produced by the authors\. LLMs were used only to improve grammar and wording after the fact, with no contribution other than reformulating for clarity\. In particular, no new idea or element was introduced through the use of an LLM\.

## References

- Androulakiet al\.\(2013\)E\. Androulaki, G\. O\. Karame, M\. Roeschlin, T\. Scherer, and S\. CapkunEvaluating user privacy in bitcoin\.InInternational conference on financial cryptography and data security,pp\. 34–51\.Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px3.p1.1)\.
- Antonopoulos \(2017a\)A\. M\. AntonopoulosMastering bitcoin: unlocking digital cryptocurrencies\.InMastering Bitcoin: Unlocking Digital Cryptocurrencies \(2nd ed\.\),Cited by:[§1](https://arxiv.org/html/2609.01942#S1.p1.1)\.
- Antonopoulos \(2017b\)A\. M\. AntonopoulosMastering bitcoin: unlocking digital cryptocurrencies\.InMastering Bitcoin: Unlocking Digital Cryptocurrencies \(2nd ed\.\),Cited by:[§1](https://arxiv.org/html/2609.01942#S1.SS0.SSS0.Px1.p1.1)\.
- Belleiet al\.\(2024\)C\. Bellei, M\. Xu, R\. Phillips, T\. Robinson, M\. Weber, T\. Kaler, C\. E\. Leiserson, J\. Chen,et al\.The shape of money laundering: subgraph representation learning on the blockchain with the elliptic2 dataset\.arXiv preprint arXiv:2404\.19109\.Cited by:[§1](https://arxiv.org/html/2609.01942#S1.SS0.SSS0.Px2.p1.1)\.
- Bianchiet al\.\(2020\)F\. M\. Bianchi, D\. Grattarola, and C\. AlippiSpectral clustering with graph neural networks for graph pooling\.InInternational conference on machine learning,pp\. 874–883\.Cited by:[§3\.1](https://arxiv.org/html/2609.01942#S3.SS1.SSS0.Px1.p1.1)\.
- Chenet al\.\(2020\)T\. Chen, S\. Kornblith, M\. Norouzi, and G\. HintonA simple framework for contrastive learning of visual representations\.InProceedings of the 37th International Conference on Machine Learning \(ICML\),pp\. 1597–1607\.Cited by:[§3\.3](https://arxiv.org/html/2609.01942#S3.SS3.p1.1)\.
- Dhulipalaet al\.\(2023\)L\. Dhulipala, J\. Łącki, J\. Lee, and V\. MirrokniTeraHAC: hierarchical agglomerative clustering of trillion\-edge graphs\.Proc\. ACM Manag\. Data1\(3\)\.External Links:[Link](https://doi.org/10.1145/3617341),[Document](https://dx.doi.org/10.1145/3617341)Cited by:[Appendix G](https://arxiv.org/html/2609.01942#A7.p2.1)\.
- Ermilovet al\.\(2017\)D\. Ermilov, M\. Panov, and Y\. YanovichAutomatic bitcoin address clustering\.In2017 16th IEEE International Conference on Machine Learning and Applications \(ICMLA\),Vol\.,pp\. 461–466\.External Links:[Document](https://dx.doi.org/10.1109/ICMLA.2017.0-118)Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px3.p1.1)\.
- Foleyet al\.\(2019\)S\. Foley, J\. R\. Karlsen, and T\. J\. PutniņšSex, drugs, and bitcoin: how much illegal activity is financed through cryptocurrencies?\.The review of financial studies32\(5\),pp\. 1798–1853\.Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px1.p1.1)\.
- Garin and Gisin \(2023\)L\. Garin and V\. GisinMachine learning in classifying bitcoin addresses\.The Journal of Finance and Data Science9,pp\. 100109\.External Links:ISSN 2405\-9188,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.jfds.2023.100109),[Link](https://www.sciencedirect.com/science/article/pii/S2405918823000259)Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px2.p1.1)\.
- Hamiltonet al\.\(2017\)W\. Hamilton, Z\. Ying, and J\. LeskovecInductive representation learning on large graphs\.Advances in neural information processing systems30\.Cited by:[§1](https://arxiv.org/html/2609.01942#S1.SS0.SSS0.Px4.p1.1),[§5\.1](https://arxiv.org/html/2609.01942#S5.SS1.SSS0.Px1.p1.1)\.
- HaoChenet al\.\(2021\)J\. Z\. HaoChen, C\. Wei, A\. Gaidon, and T\. MaProvable guarantees for self\-supervised deep learning with spectral contrastive loss\.InAdvances in Neural Information Processing Systems,A\. Beygelzimer, Y\. Dauphin, P\. Liang, and J\. W\. Vaughan \(Eds\.\),External Links:[Link](https://openreview.net/forum?id=mjyMGFL8N2)Cited by:[§3\.3](https://arxiv.org/html/2609.01942#S3.SS3.p1.2),[§4](https://arxiv.org/html/2609.01942#S4.p1.1)\.
- Harrigan and Fretter \(2016\)M\. Harrigan and C\. FretterThe unreasonable effectiveness of address clustering\.In2016 intl ieee conferences on ubiquitous intelligence & computing, advanced and trusted computing, scalable computing and communications, cloud and big data computing, internet of people, and smart world congress \(uic/atc/scalcom/cbdcom/iop/smartworld\),pp\. 368–373\.Cited by:[§1](https://arxiv.org/html/2609.01942#S1.SS0.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px3.p1.1)\.
- Heller and Ghahramani \(2005\)K\. A\. Heller and Z\. GhahramaniBayesian hierarchical clustering\.InProceedings of the 22nd international conference on Machine learning,pp\. 297–304\.Cited by:[§C\.1\.1](https://arxiv.org/html/2609.01942#A3.SS1.SSS1.Px1.p1.1),[§1](https://arxiv.org/html/2609.01942#S1.SS0.SSS0.Px3.p1.1),[§5\.2](https://arxiv.org/html/2609.01942#S5.SS2.SSS0.Px1.p1.1)\.
- Hofmeyr \(2020\)D\. P\. HofmeyrConnecting spectral clustering to maximum margins and level sets\.Journal of Machine Learning Research21\(18\),pp\. 1–35\.Cited by:[§4\.2](https://arxiv.org/html/2609.01942#S4.SS2.p1.1)\.
- Huanget al\.\(2022a\)T\. Huang, T\. Chen, M\. Fang, V\. Menkovski, J\. Zhao, L\. Yin, Y\. Pei, D\. C\. Mocanu, Z\. Wang, M\. Pechenizkiy, and S\. LiuYou can have better graph neural networks by not training weights at all: finding untrained gnns tickets\.InProceedings of the First Learning on Graphs Conference,B\. Rieck and R\. Pascanu \(Eds\.\),Proceedings of Machine Learning Research, Vol\.198,pp\. 8:1–8:17\.External Links:[Link](https://proceedings.mlr.press/v198/huang22a.html)Cited by:[§6\.1](https://arxiv.org/html/2609.01942#S6.SS1.p2.1)\.
- Huanget al\.\(2022b\)Z\. Huang, Y\. Huang, Y\. Zheng, Y\. Zhang, and X\. LiDemystifying bitcoin address behavior via graph neural networks\.InInternational Conference on Database Systems for Advanced Applications \(DASFAA\),pp\. 257–273\.Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px2.p1.1)\.
- Jiaet al\.\(2018\)C\. Jia, Z\. Zhou, Y\. Wang, and K\. XuIdentifying bitcoin users using deep neural network\.InInternational Conference on Algorithms and Architectures for Parallel Processing \(ICA3PP\),pp\. 56–70\.Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px2.p1.1)\.
- Jinget al\.\(2021\)L\. Jing, P\. Vincent, Y\. LeCun, and Y\. TianUnderstanding dimensional collapse in contrastive self\-supervised learning\.arXiv preprint arXiv:2110\.09348\.Cited by:[§D\.1](https://arxiv.org/html/2609.01942#A4.SS1.p1.1)\.
- Kanget al\.\(2020\)C\. Kang, C\. Lee, K\. Ko, J\. Woo, and J\. W\. HongDe\-anonymization of the bitcoin network using address clustering\.InBlockchain and Trustworthy Systems,Z\. Zheng, H\. Dai, X\. Fu, and B\. Chen \(Eds\.\),Singapore,pp\. 489–501\.External Links:ISBN 978\-981\-15\-9213\-3Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px2.p1.1)\.
- Kingma and Ba \(2014\)D\. P\. Kingma and J\. BaAdam: a method for stochastic optimization\.arXiv preprint arXiv:1412\.6980\.Cited by:[§5\.1](https://arxiv.org/html/2609.01942#S5.SS1.SSS0.Px1.p1.1)\.
- Kipf and Welling \(2016\)T\. N\. Kipf and M\. WellingVariational graph auto\-encoders\.arXiv preprint arXiv:1611\.07308\.Cited by:[§B\.5](https://arxiv.org/html/2609.01942#A2.SS5.SSS0.Px4.p1.1),[§5\.2](https://arxiv.org/html/2609.01942#S5.SS2.SSS0.Px2.p1.1)\.
- Kipf \(2016\)T\. KipfSemi\-supervised classification with graph convolutional networks\.arXiv preprint arXiv:1609\.02907\.Cited by:[§1](https://arxiv.org/html/2609.01942#S1.SS0.SSS0.Px4.p1.1),[§4\.1](https://arxiv.org/html/2609.01942#S4.SS1.p3.1),[§5\.1](https://arxiv.org/html/2609.01942#S5.SS1.SSS0.Px1.p1.1)\.
- Leeet al\.\(2020\)C\. Lee, S\. Maharjan, K\. Ko, J\. Woo, and J\. W\. HongMachine learning based bitcoin address classification\.InBlockchain and Trustworthy Systems,Z\. Zheng, H\. Dai, X\. Fu, and B\. Chen \(Eds\.\),Singapore,pp\. 517–531\.External Links:ISBN 978\-981\-15\-9213\-3Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px2.p1.1)\.
- Leeet al\.\(2019\)J\. Lee, I\. Lee, and J\. KangSelf\-attention graph pooling\.InInternational conference on machine learning,pp\. 3734–3743\.Cited by:[§3\.1](https://arxiv.org/html/2609.01942#S3.SS1.SSS0.Px1.p1.1)\.
- Linet al\.\(2019\)Y\. Lin, P\. Wu, C\. Hsu, I\. Tu, and S\. LiaoAn evaluation of bitcoin address classification based on transaction history summarization\.In2019 IEEE International Conference on Blockchain and Cryptocurrency \(ICBC\),Vol\.,pp\. 302–310\.External Links:[Document](https://dx.doi.org/10.1109/BLOC.2019.8751410)Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px2.p1.1)\.
- Meiklejohnet al\.\(2013\)S\. Meiklejohn, M\. Pomarole, G\. Jordan, K\. Levchenko, D\. McCoy, G\. M\. Voelker, and S\. SavageA fistful of bitcoins: characterizing payments among men with no names\.InProceedings of the 2013 conference on Internet measurement conference,pp\. 127–140\.Cited by:[§1](https://arxiv.org/html/2609.01942#S1.SS0.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px1.p1.1)\.
- Monathet al\.\(2021\)N\. Monath, K\. A\. Dubey, G\. Guruganesh, M\. Zaheer, A\. Ahmed, A\. McCallum, G\. Mergen, M\. Najork, M\. Terzihan, B\. Tjanaka,et al\.Scalable hierarchical agglomerative clustering\.InProceedings of the 27th ACM SIGKDD Conference on knowledge discovery & data mining,pp\. 1245–1255\.Cited by:[Appendix G](https://arxiv.org/html/2609.01942#A7.p2.1)\.
- Möseret al\.\(2013\)M\. Möser, R\. Böhme, and D\. BreukerAn inquiry into money laundering tools in the bitcoin ecosystem\.In2013 APWG eCrime researchers summit,pp\. 1–14\.Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px1.p1.1)\.
- Möser and Narayanan \(2022\)M\. Möser and A\. NarayananResurrecting address clustering in bitcoin\.InInternational Conference on Financial Cryptography and Data Security,pp\. 386–403\.Cited by:[Appendix E](https://arxiv.org/html/2609.01942#A5.p1.1),[Appendix E](https://arxiv.org/html/2609.01942#A5.p2.1),[Appendix E](https://arxiv.org/html/2609.01942#A5.p3.1),[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px3.p1.1),[§6\.3\.1](https://arxiv.org/html/2609.01942#S6.SS3.SSS1.p2.1),[§6\.3](https://arxiv.org/html/2609.01942#S6.SS3.p2.1),[Table 2](https://arxiv.org/html/2609.01942#S6.T2.3.1.3.1)\.
- Nakamoto \(2009\)S\. NakamotoBitcoin: a peer\-to\-peer electronic cash system\.bitcoin\.org\.External Links:[Link](http://www.bitcoin.org/bitcoin.pdf)Cited by:[§1](https://arxiv.org/html/2609.01942#S1.p1.1)\.
- Nget al\.\(2001\)A\. Ng, M\. Jordan, and Y\. WeissOn spectral clustering: analysis and an algorithm\.Advances in neural information processing systems14\.Cited by:[§4\.2](https://arxiv.org/html/2609.01942#S4.SS2.p1.1)\.
- Nt and Maehara \(2019\)H\. Nt and T\. MaeharaRevisiting graph neural networks: all we have is low\-pass filters\.arXiv preprint arXiv:1905\.09550\.Cited by:[§4\.1](https://arxiv.org/html/2609.01942#S4.SS1.p1.1)\.
- Oordet al\.\(2018\)A\. v\. d\. Oord, Y\. Li, and O\. VinyalsRepresentation learning with contrastive predictive coding\.InAdvances in Neural Information Processing Systems \(NeurIPS\) Workshop,Cited by:[§3\.3](https://arxiv.org/html/2609.01942#S3.SS3.p1.1)\.
- Penget al\.\(2015\)R\. Peng, H\. Sun, and L\. ZanettiPartitioning well\-clustered graphs: spectral clustering works\!\.InConference on learning theory,pp\. 1423–1455\.Cited by:[§4\.2](https://arxiv.org/html/2609.01942#S4.SS2.p1.1)\.
- Rousseeuw \(1987\)P\. J\. RousseeuwSilhouettes: a graphical aid to the interpretation and validation of cluster analysis\.Journal of computational and applied mathematics20,pp\. 53–65\.Cited by:[§5\.2](https://arxiv.org/html/2609.01942#S5.SS2.SSS0.Px1.p1.1)\.
- Schnoering and Vazirgiannis \(2026\)H\. P\. P\. Schnoering and M\. VazirgiannisBitcoin transaction graphs: training, labelled entities, and CoinJoins\.Note:ZenodoDOI: 10\.5281/zenodo\.22239038External Links:[Link](https://doi.org/10.5281/zenodo.22239038)Cited by:[Appendix A](https://arxiv.org/html/2609.01942#A1.p1.1),[item 1](https://arxiv.org/html/2609.01942#S1.I2.i1.p1.1),[§5](https://arxiv.org/html/2609.01942#S5.p2.1)\.
- Schnoeringet al\.\(2024\)H\. Schnoering, P\. Porthaux, and M\. VazirgiannisAssessing the efficacy of heuristic\-based address clustering for bitcoin\.arXiv preprint arXiv:2403\.00523\.Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px1.p1.1),[§3\.2](https://arxiv.org/html/2609.01942#S3.SS2.p1.1),[§6\.3\.2](https://arxiv.org/html/2609.01942#S6.SS3.SSS2.p1.1)\.
- Schnoering and Vazirgiannis \(2023\)H\. Schnoering and M\. VazirgiannisHeuristics for detecting coinjoin transactions on the bitcoin blockchain\.arXiv preprint arXiv:2311\.12491\.Cited by:[§6\.3\.2](https://arxiv.org/html/2609.01942#S6.SS3.SSS2.p1.1)\.
- Schnoering and Vazirgiannis \(2025\)H\. Schnoering and M\. VazirgiannisBitcoin research with a transaction graph dataset\.Scientific Data12\(1\),pp\. 404\.Cited by:[§1](https://arxiv.org/html/2609.01942#S1.SS0.SSS0.Px2.p1.1),[§3\.2](https://arxiv.org/html/2609.01942#S3.SS2.p1.1),[§6\.3\.1](https://arxiv.org/html/2609.01942#S6.SS3.SSS1.p1.1),[§6\.3\.2](https://arxiv.org/html/2609.01942#S6.SS3.SSS2.p1.1)\.
- Sieet al\.\(2025\)M\. Sie, Y\. Chang, C\. Lin, C\. Chang, and S\. LiaoEfficient Bitcoin address classification using quantum\-inspired feature selection\.Quantum Machine Intelligence7\(2\),pp\. 75\.External Links:2411\.15425,[Document](https://dx.doi.org/10.1007/s42484-025-00302-3)Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px2.p1.1)\.
- Tanet al\.\(2024\)Z\. Tan, Y\. Zhang, J\. Yang, and Y\. YuanContrastive learning is spectral clustering on similarity graph\.InThe Twelfth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=hLZQTFGToA)Cited by:[§3\.3](https://arxiv.org/html/2609.01942#S3.SS3.p1.2),[§4](https://arxiv.org/html/2609.01942#S4.p1.1)\.
- Toyodaet al\.\(2018\)K\. Toyoda, T\. Ohtsuki, and P\. T\. MathiopoulosMulti\-class bitcoin\-enabled service identification based on transaction history summarization\.In2018 IEEE International Conference on Internet of Things \(iThings\) and IEEE Green Computing and Communications \(GreenCom\) and IEEE Cyber, Physical and Social Computing \(CPSCom\) and IEEE Smart Data \(SmartData\),Vol\.,pp\. 1153–1160\.External Links:[Document](https://dx.doi.org/10.1109/Cybermatics%5F2018.2018.00208)Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px2.p1.1)\.
- Traaget al\.\(2019\)V\. A\. Traag, L\. Waltman, and N\. J\. Van EckFrom louvain to leiden: guaranteeing well\-connected communities\.Scientific reports9\(1\),pp\. 1–12\.Cited by:[§5\.2](https://arxiv.org/html/2609.01942#S5.SS2.p1.1)\.
- Veličkovićet al\.\(2017\)P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Lio, and Y\. BengioGraph attention networks\.arXiv preprint arXiv:1710\.10903\.Cited by:[§1](https://arxiv.org/html/2609.01942#S1.SS0.SSS0.Px4.p1.1),[§5\.1](https://arxiv.org/html/2609.01942#S5.SS1.SSS0.Px1.p1.1)\.
- Veličkovićet al\.\(2018\)P\. Veličković, W\. Fedus, W\. L\. Hamilton, P\. Liò, Y\. Bengio, and R\. D\. HjelmDeep graph infomax\.arXiv preprint arXiv:1809\.10341\.Cited by:[§B\.5](https://arxiv.org/html/2609.01942#A2.SS5.SSS0.Px5.p1.1),[§5\.2](https://arxiv.org/html/2609.01942#S5.SS2.SSS0.Px2.p1.1)\.
- Vinhet al\.\(2009\)N\. X\. Vinh, J\. Epps, and J\. BaileyInformation theoretic measures for clusterings comparison: is a correction for chance necessary?\.InProceedings of the 26th annual international conference on machine learning,pp\. 1073–1080\.Cited by:[§5\.2](https://arxiv.org/html/2609.01942#S5.SS2.SSS0.Px1.p1.1)\.
- Von Luxburg \(2007\)U\. Von LuxburgA tutorial on spectral clustering\.Statistics and computing17\(4\),pp\. 395–416\.Cited by:[§F\.1](https://arxiv.org/html/2609.01942#A6.SS1.p1.1),[§4\.1](https://arxiv.org/html/2609.01942#S4.SS1.p1.1),[§4\.2](https://arxiv.org/html/2609.01942#S4.SS2.p1.1)\.
- Wanget al\.\(2024\)Z\. Wang, Z\. Zhang, C\. Zhang, and Y\. YeSubgraph pooling: tackling negative transfer on graphs\.InProceedings of the Thirty\-Third International Joint Conference on Artificial Intelligence,IJCAI ’24\.External Links:ISBN 978\-1\-956792\-04\-1,[Link](https://doi.org/10.24963/ijcai.2024/570),[Document](https://dx.doi.org/10.24963/ijcai.2024/570)Cited by:[§6\.3\.2](https://arxiv.org/html/2609.01942#S6.SS3.SSS2.p2.1)\.
- Weberet al\.\(2019\)M\. Weber, G\. Domeniconi, J\. Chen, D\. K\. I\. Weidele, C\. Bellei, T\. Robinson, and C\. E\. LeisersonAnti\-money laundering in bitcoin: experimenting with graph convolutional networks for financial forensics\.arXiv preprint arXiv:1908\.02591\.Cited by:[§1](https://arxiv.org/html/2609.01942#S1.SS0.SSS0.Px2.p1.1)\.
- Xuet al\.\(2019\)K\. Xu, W\. Hu, J\. Leskovec, and S\. JegelkaHow powerful are graph neural networks?\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=ryGs6iA5Km)Cited by:[§5\.1](https://arxiv.org/html/2609.01942#S5.SS1.SSS0.Px2.p1.1)\.
- Yanget al\.\(2023\)G\. Yang, X\. Liu, and B\. LiAnti\-money laundering supervision by intelligent algorithm\.Computers & Security132,pp\. 103344\.Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px1.p1.1)\.
- Yinget al\.\(2018\)Z\. Ying, J\. You, C\. Morris, X\. Ren, W\. Hamilton, and J\. LeskovecHierarchical graph representation learning with differentiable pooling\.Advances in neural information processing systems31\.Cited by:[§3\.1](https://arxiv.org/html/2609.01942#S3.SS1.SSS0.Px1.p1.1)\.
- Youet al\.\(2019\)J\. You, R\. Ying, and J\. LeskovecPosition\-aware graph neural networks\.InProceedings of the 36th International Conference on Machine Learning,K\. Chaudhuri and R\. Salakhutdinov \(Eds\.\),Proceedings of Machine Learning Research, Vol\.97,pp\. 7134–7143\.External Links:[Link](https://proceedings.mlr.press/v97/you19b.html)Cited by:[§5\.1](https://arxiv.org/html/2609.01942#S5.SS1.SSS0.Px2.p1.1)\.
- Yuet al\.\(2015\)Y\. Yu, T\. Wang, and R\. J\. SamworthA useful variant of the davis–kahan theorem for statisticians\.Biometrika102\(2\),pp\. 315–323\.Cited by:[§F\.1](https://arxiv.org/html/2609.01942#A6.SS1.p3.1)\.
- Zhanget al\.\(2025\)Y\. Zhang, Q\. Ren, Y\. Chen, and M\. HanBeyond contrastive learning: adaptive graph representations with mutual information maximization for blockchain and structured data\.Complex Intell\. Syst\.11\(9\) \(en\)\.Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px2.p1.1)\.
- Zhaoet al\.\(2025\)Z\. Zhao, J\. Wang, and J\. WeiGraph neural network\-based transaction link prediction method for public blockchain in heterogeneous information networks\.Blockchain: Research and Applications6\(2\),pp\. 100265\.External Links:ISSN 2096\-7209,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.bcra.2024.100265),[Link](https://www.sciencedirect.com/science/article/pii/S2096720924000782)Cited by:[§2](https://arxiv.org/html/2609.01942#S2.SS0.SSS0.Px2.p1.1)\.
- Zhuet al\.\(2020\)J\. Zhu, Y\. Yan, L\. Zhao, M\. Heimann, L\. Akoglu, and D\. KoutraBeyond homophily in graph neural networks: current limitations and effective designs\.InAdvances in Neural Information Processing Systems,H\. Larochelle, M\. Ranzato, R\. Hadsell, M\.F\. Balcan, and H\. Lin \(Eds\.\),Vol\.33,pp\. 7793–7804\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2020/file/58ae23d878a47004366189884c2f8440-Paper.pdf)Cited by:[§6\.3\.2](https://arxiv.org/html/2609.01942#S6.SS3.SSS2.p2.1)\.

## Appendix ADataset

### A\.1Transaction Sampling Strategy

#### A\.1\.1Sampling from Coinbase Transactions

Constructing a graph from the full history of Bitcoin transactions would yield a network with several billion nodes and edges, rendering most graph algorithms computationally infeasible\. To obtain a manageable subgraph, we sample transactions occurring between two block indicest1<t2t\_\{1\}<t\_\{2\}\.

A Bitcoin transaction transforms input value units into new output value units \(TXOs\), with unspent outputs known as UTXOs\. Inputs originate from previous transactions, while outputs can be spent by future transactions\. The only exception is the*coinbase transaction*—the first transaction in each block—which has no inputs and generates new currency units as a mining reward\.

This structure naturally defines a directed acyclic graph \(DAG\): sources correspond to coinbase transactions; an edge exists from transactionAAto transactionBBwhenever outputs fromAAare consumed byBB; sinks correspond to transactions whose outputs have not been spent\. An example of such a transaction DAG is shown in Figure[4](https://arxiv.org/html/2609.01942#A1.F4)\.

Figure 4:Bitcoin transaction graph\. Circles represent transaction nodes, and directed edges indicate the flow of bitcoin between transactions\. Double\-circled nodes denote coinbase transactions\.Our sampling procedure performs a breadth\-first search \(BFS\) on this transaction DAG, initialized from a coinbase transaction chosen uniformly at random between blockst1t\_\{1\}andt2t\_\{2\}\. Because block indices increase monotonically along transaction paths, all sampled transactions necessarily have indices greater thant1t\_\{1\}, and exploration is truncated at blockt2t\_\{2\}, ensuring that every sampled transaction lies within the interval\[t1,t2\]\[t\_\{1\},t\_\{2\}\]\. To further control the graph size, we cap the exploration depth at 15 and limit the number of transactions expanded at each BFS step to 5,000\.

#### A\.1\.2Sampling from Transactions with Labels

In contrast to the directed exploration used for coinbase\-based sampling, we perform a breadth\-first search on the*undirected*transaction graph\. This allows the procedure to explore not only future transactions consuming outputs of the seed, but also past transactions whose outputs were used as inputs to it\.

To preserve locality, we use a maximum BFS depth of 3 and limit the number of expanded transactions per depth to 100\. These constraints ensure that the sampled subgraph remains compact while capturing the relevant transactional context surrounding the labeled addresses\. Aside from these modifications, the overall exploration logic follows the same structure as the coinbase\-based sampling procedure described above in Appendix[A\.1\.1](https://arxiv.org/html/2609.01942#A1.SS1.SSS1)\.

### A\.2Graph Characteristics

Table[4](https://arxiv.org/html/2609.01942#A1.T4)summarizes the key statistics of the sampled Bitcoin transaction graphs used for training, validation, and testing\.

Table 4:Dataset statistics\. Blk int\. denotes the block interval, \#Tx the number of sampled transactions, \#Nodes the number of nodes, \#Edges the number of edges, and \#Clust\. the number of clusters\.
### A\.3Node and Edge Features

Table[5](https://arxiv.org/html/2609.01942#A1.T5)lists the columns and their descriptions for each table \(nodes, edges, and clusters\) in the released graph dataset\.

TableColumn nameDescriptionNodesnode\_idIdentifier of the nodedegree\_inThe number of incoming edges to the nodedegree\_outThe number of outgoing edges from the nodetotal\_transaction\_inTotal count of transfers received by the nodetotal\_transaction\_outTotal count of transfers initiated by the nodefirst\_transaction\_inBlock index of the first transfer receivedlast\_transaction\_inBlock index of the last transfer receivedfirst\_transaction\_outBlock index of the first transfer sentlast\_transaction\_outBlock index of the last transfer sentmin\_sentSmallest value sent out in a single transactionmax\_sentLargest value sent out in a single transactiontotal\_sentCumulative value of all outgoing transfersmin\_receivedSmallest value received in a single transactionmax\_receivedLargest value received in a single transactiontotal\_receivedCumulative value of all incoming transfersEdgesaNode ID of the senderbNode ID of the recipientrevealBlock index of the first transactionlast\_seenBlock index of the last transactiontotalTotal number of transactionsmin\_sentMinimum sent in a single transactionmax\_sentMaximum sent in a single transactiontotal\_sentCumulative value sent along the edgeClustersnode\_idIdentifier of the nodealiasIdentifier of the clusterTable 5:Description of the columns of the different tables constituting the graph dataset\.

## Appendix BTraining

### B\.1Sampling Function for Contrastive Learning

We assume a reference clustering𝒞=\{C1,…,Ck\}\\mathcal\{C\}=\\\{C\_\{1\},\\dots,C\_\{k\}\\\}over the node setVV\. Let the latent variables\(Z,Z1−,…,Zp−\)\(Z,Z\_\{1\}^\{\-\},\\dots,Z\_\{p\}^\{\-\}\)denote the cluster labels of\(X,X1−,…,Xp−\)\(X,X\_\{1\}^\{\-\},\\dots,X\_\{p\}^\{\-\}\)under𝒞\\mathcal\{C\}\. The joint sampling distribution of Equation[1](https://arxiv.org/html/2609.01942#S3.E1)is

ℙα​\(x,x\+,x1−,…,xp−\)=∑z,z1−,…,zp−ℙα​\(z\)​ℙ​\(x∣z\)​ℙ​\(x\+∣z,x\)​∏i=1pℙα​\(zi−∣z\)​ℙ​\(xi−∣zi−\)\\mathbb\{P\}\_\{\\alpha\}\(x,x^\{\+\},x\_\{1\}^\{\-\},\\dots,x\_\{p\}^\{\-\}\)=\\sum\_\{z,z\_\{1\}^\{\-\},\\dots,z\_\{p\}^\{\-\}\}\\mathbb\{P\}\_\{\\alpha\}\(z\)\\,\\mathbb\{P\}\(x\\mid z\)\\,\\mathbb\{P\}\(x^\{\+\}\\mid z,x\)\\prod\_\{i=1\}^\{p\}\\mathbb\{P\}\_\{\\alpha\}\(z\_\{i\}^\{\-\}\\mid z\)\\,\\mathbb\{P\}\(x\_\{i\}^\{\-\}\\mid z\_\{i\}^\{\-\}\)whereℙα​\(Z=z\)=α​\|Cz\|\|V\|\+\(1−α\)​1\|𝒞\|\\mathbb\{P\}\_\{\\alpha\}\(Z=z\)=\\alpha\\,\\tfrac\{\|C\_\{z\}\|\}\{\|V\|\}\+\(1\-\\alpha\)\\,\\tfrac\{1\}\{\|\\mathcal\{C\}\|\}is a mixture between size\-proportional sampling \(α=1\\alpha=1\) and uniform sampling over clusters \(α=0\\alpha=0\)\.ℙ⁡\(X=x∣Z=z\)\\mathbb\{P\}\(X=x\\mid Z=z\)is uniform over all nodes in clusterCzC\_\{z\},ℙ⁡\(X\+=x\+∣Z=z,X=x\)\\mathbb\{P\}\(X^\{\+\}=x^\{\+\}\\mid Z=z,X=x\)is uniform overCz∖\{x\}C\_\{z\}\\setminus\\\{x\\\},ℙα​\(Zi−=zi−∣Z=z\)\\mathbb\{P\}\_\{\\alpha\}\(Z\_\{i\}^\{\-\}=z\_\{i\}^\{\-\}\\mid Z=z\)is uniform over allzi−≠zz\_\{i\}^\{\-\}\\neq z, andℙ⁡\(Xi−=xi−∣Zi−=zi−\)\\mathbb\{P\}\(X\_\{i\}^\{\-\}=x\_\{i\}^\{\-\}\\mid Z\_\{i\}^\{\-\}=z\_\{i\}^\{\-\}\)is uniform over all nodes in clusterCzi−C\_\{z\_\{i\}^\{\-\}\}\.

This scheme provides a principled sampling strategy for contrastive learning: positive pairs are always drawn from the same cluster as the anchor, while negatives come from different clusters\. The parameterα\\alphabalances diversity and representativeness by interpolating between uniform and size\-proportional cluster sampling\.

### B\.2Feature Preprocessing

Some input features encode amounts denominated in bitcoins \(Table[5](https://arxiv.org/html/2609.01942#A1.T5)\)\. Because the bitcoin price varies substantially across graph samples, we augment these features with their corresponding U\.S\.\-dollar values, computed from the bitcoin price at each graph’s starting date\.

Feature preprocessing is performed independently for each graph\. First, all features are log\-transformed usingx↦log⁡\(1\+x\)x\\mapsto\\log\(1\+x\)to reduce skewness\. Next, we apply min–max normalization based on the empirical 5th and 95th percentiles of each feature, and missing values are imputed with zeros\.

### B\.3Hyperparameters

Table[6](https://arxiv.org/html/2609.01942#A2.T6)summarizes the model architecture, preprocessing options, and optimization settings used for training the GNNs\.

HyperparameterValueModelNumber of attention heads4Size of hidden embeddings64Size of output embeddings128Number of layers2Activation functionLeaky ReLUDropout0\.2PreprocessingSymmetrize the input graphTrueUse edge featuresFalseNumber of landmarks in the positional encoding0OptimizerInitial learning rate2\.5×10−32\.5\\times 10^\{\-3\}Weight decay10−510^\{\-5\}Learning rate schedulerReduction factor0\.5Patience20Gradient descentNumber of epochs250Num\. anchors per batch512Num\. negative samples per anchor \(pp\)4Temperature \(τ\\tau\)0\.07Parameter of sampling function \(α\\alpha\)0\.5Table 6:Hyperparameters used for training\.
### B\.4CoinJoin Hard\-Negative Training

Let𝒢\\mathcal\{G\}denote the set of available CoinJoin\-centered training graphs\. At each training step, we sampleNgN\_\{g\}graphs from𝒢\\mathcal\{G\}\. For each sampled graph, we sampleNpN\_\{p\}pairs of distinct input nodes involved in the CoinJoin transaction used to generate that graph\. We denote these pairs by\(Ag,j,Ig,j\)j=1Np\(A\_\{g,j\},I\_\{g,j\}\)\_\{j=1\}^\{N\_\{p\}\}\. The CoinJoin repulsion loss is defined as

ℒCoinJoin=𝔼⁡\[1Ng​∑g=1Ng1Np​∑j=1Nplog⁡\(1\+exp⁡\(g⁡\(Ag,j\)⋅g⁡\(Ig,j\)τ\)\)\],\\mathcal\{L\}\_\{\\mathrm\{CoinJoin\}\}=\\mathbb\{E\}\\left\[\\frac\{1\}\{N\_\{g\}\}\\sum\_\{g=1\}^\{N\_\{g\}\}\\frac\{1\}\{N\_\{p\}\}\\sum\_\{j=1\}^\{N\_\{p\}\}\\log\\\!\\left\(1\+\\exp\\\!\\left\(\\frac\{g\(A\_\{g,j\}\)\\cdot g\(I\_\{g,j\}\)\}\{\\tau\}\\right\)\\right\)\\right\],\(2\)where the expectation is over the sampling of the CoinJoin\-centered graphs and negative pairs\.

The full augmented training objective is then

ℒInfoNCE\+λCoinJoin​ℒCoinJoin,\\mathcal\{L\}\_\{\\mathrm\{InfoNCE\}\}\+\\lambda\_\{\\mathrm\{CoinJoin\}\}\\mathcal\{L\}\_\{\\mathrm\{CoinJoin\}\},\(3\)whereλCoinJoin\\lambda\_\{\\mathrm\{CoinJoin\}\}controls the weight of the CoinJoin repulsion term\.

The hyperparameters specific to this auxiliary CoinJoin loss are reported in Table[7](https://arxiv.org/html/2609.01942#A2.T7)\.

Table 7:Hyperparameters used for the CoinJoin hard\-negative training\.
### B\.5Training of Baselines

##### Louvain\.

We use the Louvain implementation from theNetworkXlibrary\. The resolution parameter, which controls the granularity of the detected communities, is tuned by grid search in the range\[0\.5,3\.0\]\[0\.5,3\.0\]on the validation graph to maximize the modularity score\.

##### Leiden\.

For Leiden, we rely on theleidenalgpackage, using theRBConfigurationVertexPartitionobjective \(the standard modularity\-based configuration\)\. The resolution parameter is likewise tuned by grid search in the range\[0\.5,3\.0\]\[0\.5,3\.0\]on the validation graph, and the number of refinement iterations is fixed to 10 to ensure convergence\.

##### Untrained GAT\.

We follow exactly the same procedure as for the trained GNN experiments—using the default hyperparameters of Table[6](https://arxiv.org/html/2609.01942#A2.T6)—except that the number of training epochs is set to zero\.

##### Graph Auto\-Encoder \(GAE\)\.

We follow the non\-probabilistic graph auto\-encoder training procedure of[Kipf and Welling \[2016\]](https://arxiv.org/html/2609.01942#bib.bib40)\. The encoder is a GAT with the default hyperparameters of Table[6](https://arxiv.org/html/2609.01942#A2.T6), while the decoder is a simple dot product\. Given adjacency matrixAAand encoder embeddingsHH, the loss is the binary cross\-entropy

ℒGAE=−∑i,j\[Ai​jlogσ\(hi⊤hj\)\+\(1−Ai​j\)log\(1−σ\(hi⊤hj\)\)\],\\mathcal\{L\}\_\{\\text\{GAE\}\}=\-\\\!\\\!\\sum\_\{i,j\}\\bigl\[A\_\{ij\}\\log\\sigma\(h\_\{i\}^\{\\top\}h\_\{j\}\)\+\(1\-A\_\{ij\}\)\\log\\bigl\(1\-\\sigma\(h\_\{i\}^\{\\top\}h\_\{j\}\)\\bigr\)\\bigr\],whereσ\\sigmais the sigmoid function\. Embeddings are trained to reconstructAA\. We apply the same neighbor sampling, training\-graph rotation, and learning\-rate scheduling as in the main experiments, monitoring performance via the validation\-graph reconstruction loss\. The only change in hyperparameters is a shorter training duration of 20 epochs\.

##### Deep Graph Infomax \(DGI\)\.

We adopt the training procedure of[Veličković et al\. \[2018\]](https://arxiv.org/html/2609.01942#bib.bib41)for Deep Graph Infomax\. The encoder is a GAT with the default hyperparameters of Table[6](https://arxiv.org/html/2609.01942#A2.T6)\. DGI learns node embeddings by maximizing mutual information between local node representations and a global summary vector\. Given node embeddingsHHand a readout summarys=σ⁡\(1n​∑ihi\)s=\\sigma\\\!\\left\(\\tfrac\{1\}\{n\}\\sum\_\{i\}h\_\{i\}\\right\), a corrupted graphG~\\tilde\{G\}is produced by randomly shuffling node features to create negative samplesH~\\tilde\{H\}\. The loss is the binary cross\-entropy

ℒDGI=−∑i\[logσ\(hi⊤Ws\)\+log\(1−σ\(h~i⊤Ws\)\)\],\\mathcal\{L\}\_\{\\text\{DGI\}\}=\-\\sum\_\{i\}\\bigl\[\\log\\sigma\(h\_\{i\}^\{\\top\}Ws\)\+\\log\\bigl\(1\-\\sigma\(\\tilde\{h\}\_\{i\}^\{\\top\}Ws\)\\bigr\)\\bigr\],whereWWis a trainable scoring matrix andσ\\sigmathe sigmoid function\. We use the same neighbor sampling, rotation of training graphs, and learning\-rate scheduling as in the main experiments, and monitor training with the DGI objective on the validation graph\. Training is limited to 20 epochs to match the GAE baseline\.

## Appendix CEvaluation

### C\.1Evaluation Metrics

We evaluate hierarchical and flat clusterings using standard information\-theoretic and pairwise similarity measures\.

#### C\.1\.1Hierarchical Clustering

##### Dendrogram Purity\.

Following[Heller and Ghahramani \[2005\]](https://arxiv.org/html/2609.01942#bib.bib2), letTTbe a dendrogram with leaves1,…,n1,\\dots,nand class labelsc1,…,cnc\_\{1\},\\dots,c\_\{n\}\. To compute the purity ofTT:

1. 1\.Sample a leafℓ\\elluniformly at random\.
2. 2\.Sample another leafjjuniformly at random among those with the same class label,cj=cℓc\_\{j\}=c\_\{\\ell\}\.
3. 3\.LetS⁡\(ℓ,j\)S\(\\ell,j\)be the smallest subtree ofTTcontaining bothℓ\\ellandjj\.
4. 4\.Compute the fraction of leaves inS⁡\(ℓ,j\)S\(\\ell,j\)that share the classcℓc\_\{\\ell\}\.

The expected value of this fraction over the sampling procedure defines the*dendrogram purity*, which equals11if and only if every ground\-truth class forms a pure subtree\.

*Implementation\.*We provide an open\-source implementation in our public repository\. Purity is estimated by Monte Carlo withN=10,000N=10\{,\}000sampled pairs\(ℓ,j\)\(\\ell,j\)\. Each pair is drawn*within the same coarse Leiden cluster*; because this Leiden partition is identical across all evaluations, this sampling constraint does not introduce bias\.

#### C\.1\.2Flat Clustering

##### Normalized Mutual Information \(NMI\)\.

The uncertainty of a clustering is quantified by its*entropy*,H\(U\)=−∑up\(u\)logp\(u\)H\(U\)=\-\\sum\_\{u\}p\(u\)\\log p\(u\), wherep⁡\(u\)p\(u\)is the probability of clusteruu\. The similarity between two clusteringsUUandVVcan then be measured by their*mutual information*,I⁡\(U,V\)=∑u,vp⁡\(u,v\)​log⁡p⁡\(u,v\)p⁡\(u\)​p​\(v\)I\(U;V\)=\\sum\_\{u,v\}p\(u,v\)\\log\\frac\{p\(u,v\)\}\{p\(u\)p\(v\)\}, which captures how much knowingVVreduces the uncertainty ofUU\. The NMI score normalizes mutual information to the range\[0,1\]\[0,1\]via

NMI⁡\(U,V\)=2​I​\(U,V\)H⁡\(U\)\+H⁡\(V\)\.\\operatorname\{NMI\}\(U,V\)=\\frac\{2\\,I\(U;V\)\}\{H\(U\)\+H\(V\)\}\.Because mutual information captures the overall dependency between the two label distributions, this normalization measures*global agreement*between entire clusterings rather than only local pairwise matches\. Moreover, the ratio form compensates for differing cluster entropies, making the score*robust to cluster\-size imbalance*and directly comparable across datasets of varying class distributions\.

##### Adjusted Rand Index \(ARI\)\.

To assess pairwise agreement, the*Rand index*is defined asRI=a\+b\(n2\)\\operatorname\{RI\}=\\frac\{a\+b\}\{\\binom\{n\}\{2\}\}, whereaadenotes the number of element pairs assigned to the same cluster in bothUUandVV, andbbdenotes the number of pairs assigned to different clusters in both\. The Rand index is corrected for chance agreement with

ARI=RI−𝔼⁡\[RI\]max⁡\(RI\)−𝔼⁡\[RI\],\\operatorname\{ARI\}=\\frac\{\\operatorname\{RI\}\-\\mathbb\{E\}\[\\operatorname\{RI\}\]\}\{\\max\(\\operatorname\{RI\}\)\-\\mathbb\{E\}\[\\operatorname\{RI\}\]\},placing the score in\[−1,1\]\[\-1,1\]and emphasizing local consistency\.

*Implementation\.*All NMI and ARI computations use the standard implementations fromsklearn\.

### C\.2Dendrogram Cutting Methods

Let𝒞=\{C1,…,CK\}\\mathcal\{C\}=\\\{C\_\{1\},\\dots,C\_\{K\}\\\}be a coarse partition\. For each clusterCkC\_\{k\}withnk=\|Ck\|≥nminn\_\{k\}=\|C\_\{k\}\|\\geq n\_\{\\min\}, we compute cosine distances between embeddingsHCkH\_\{C\_\{k\}\}and build a hierarchical clustering linkage matrix\.

Each cutting rule produces a local thresholdtkt\_\{k\}\. We define a global threshold by size\-weighted averaging:

λ=∑k:nk≥nminnktk∑k:nk≥nminnk\.\\lambda=\\frac\{\\sum\_\{k:\\,n\_\{k\}\\geq n\_\{\\min\}\}n\_\{k\}\\,t\_\{k\}\}\{\\sum\_\{k:\\,n\_\{k\}\\geq n\_\{\\min\}\}n\_\{k\}\}\.
##### Silhouette\-based cut\.

For a given cut level producing a flat partitiony^\\hat\{y\}ofCkC\_\{k\}, we evaluate its quality using the silhouette score\. LetDkD\_\{k\}denote the cosine distance matrix withinCkC\_\{k\}\. For each pointii, define

a⁡\(i\)=1\|C⁡\(i\)\|−1​∑j∈C⁡\(i\),j≠iDk​\(i,j\),a\(i\)=\\frac\{1\}\{\|C\(i\)\|\-1\}\\sum\_\{j\\in C\(i\),\\,j\\neq i\}D\_\{k\}\(i,j\),the average intra\-cluster distance, and

b⁡\(i\)=minC′≠C⁡\(i\)⁡1\|C′\|​∑j∈C′Dk​\(i,j\),b\(i\)=\\min\_\{C^\{\\prime\}\\neq C\(i\)\}\\frac\{1\}\{\|C^\{\\prime\}\|\}\\sum\_\{j\\in C^\{\\prime\}\}D\_\{k\}\(i,j\),the minimal average distance to another cluster\. The silhouette coefficient ofiiis

s⁡\(i\)=b⁡\(i\)−a⁡\(i\)max⁡\{a⁡\(i\),b⁡\(i\)\},s\(i\)=\\frac\{b\(i\)\-a\(i\)\}\{\\max\\\{a\(i\),b\(i\)\\\}\},and the global silhouette score is

Sil⁡\(Dk,y^\)=1nk​∑i∈Cks⁡\(i\)\.\\mathrm\{Sil\}\(D\_\{k\},\\hat\{y\}\)=\\frac\{1\}\{n\_\{k\}\}\\sum\_\{i\\in C\_\{k\}\}s\(i\)\.
The selected cut is the one maximizingSil⁡\(Dk,y^\)\\mathrm\{Sil\}\(D\_\{k\},\\hat\{y\}\)\.

##### Largest\-gap cut\.

Lethk,1,…,hk,nk−1h\_\{k,1\},\\dots,h\_\{k,n\_\{k\}\-1\}denote the merge heights in the dendrogram ofCkC\_\{k\}, and lethk,\(1\)≤⋯≤hk,\(nk−1\)h\_\{k,\(1\)\}\\leq\\dots\\leq h\_\{k,\(n\_\{k\}\-1\)\}be their sorted values\. Define the consecutive gaps

Δi=hk,\(i\+1\)−hk,\(i\),i=1,…,nk−2\.\\Delta\_\{i\}=h\_\{k,\(i\+1\)\}\-h\_\{k,\(i\)\},\\qquad i=1,\\dots,n\_\{k\}\-2\.Let

i⋆=arg⁡maxi⁡Δi\.i^\{\\star\}=\\arg\\max\_\{i\}\\Delta\_\{i\}\.The cut level is chosen as the midpoint of the largest gap,

hk,\(i⋆\)\+12​Δi⋆\.h\_\{k,\(i^\{\\star\}\)\}\+\\frac\{1\}\{2\}\\Delta\_\{i^\{\\star\}\}\.

##### Inconsistency\-based cut\.

The inconsistency coefficient quantifies how unusually large a merge height is compared to merges occurring below it in the dendrogram\. It is computed by normalizing the difference between the merge height and the mean height of descendant merges by their standard deviation\. High values indicate potentially spurious merges\.

We select the threshold adaptively asμv\+α​σv\\mu\_\{v\}\+\\alpha\\sigma\_\{v\}, whereμv\\mu\_\{v\}andσv\\sigma\_\{v\}are the empirical mean and standard deviation of the inconsistency coefficients within the cluster, andα\>0\\alpha\>0controls the sensitivity of the split\.

## Appendix DAdditional Experiments

### D\.1Embedding dimension

A critical design choice is the number of dimensions in the embedding space produced by the GNN\. If the dimensionality is too low, the model cannot adequately separate the numerous clusters\. Conversely, a very high dimensionality increases algorithmic complexity and computational cost, and may even lead to dimensional collapse\[[Jing et al\., 2021](https://arxiv.org/html/2609.01942#bib.bib3)\]\. To investigate this trade\-off, we experimented with different embedding sizes and compared their performance in Table[8](https://arxiv.org/html/2609.01942#A4.T8)\. For consistency, we set the number of hidden dimensions in the GAT to2×Size of output embedding spaceNumber of attention heads\\frac\{2\\times\\text\{Size of output embedding space\}\}\{\\text\{Number of attention heads\}\}\.

Table 8:Performance across different embedding dimensions with evaluation metrics NMI, ARI, and dendrogram purity \(DP\)\. The best score for each metric is marked with∗∗and the second\-best with∗\. All metrics are computed on the test graph / heuristic clustering, and results are averaged over five runs\.Model performance improves consistently as the embedding dimension increases across all three metrics\. Dendrogram purity \(DP\) exhibits a strictly monotonic rise from 16 to 512 dimensions, indicating progressively better hierarchical separation\. Both NMI and ARI follow the same upward trend, with the highest scores obtained at 512 dimensions\. While intermediate dimensions \(64–128\) already yield strong performance, larger embeddings further enhance both global agreement \(NMI\) and local consistency \(ARI\)\. These results suggest that, in our setting, increasing the embedding dimensionality does not induce degradation and instead provides additional representational capacity that translates into measurable clustering gains\.

### D\.2Parameter of the sampling function

In this section, we evaluate the influence of the sampling parameterα\\alphaon the performance of our methodology\. The sampling parameterα\\alphacontrols the balance between uniform and size\-proportional cluster selection in the contrastive sampling distribution\. Table[9](https://arxiv.org/html/2609.01942#A4.T9)reports the results\. The results reveal a clear dependence on the sampling parameterα\\alpha\. ARI is maximized atα=0\\alpha=0, indicating that uniform cluster sampling favors stronger local pairwise consistency\. In contrast, both dendrogram purity and NMI peak atα=0\.2\\alpha=0\.2, suggesting that a slight bias toward size\-proportional sampling improves both hierarchical coherence and global agreement with the heuristic partition\. For larger values ofα\\alpha\(≥0\.6\\geq 0\.6\), performance gradually degrades, particularly in terms of NMI and ARI, reflecting a loss of local discriminative power\. Overall, small but non\-zero values ofα\\alphaprovide the best trade\-off, balancing global structure preservation and local cluster separability\.

Table 9:Performance across differentα\\alphawith evaluation metrics NMI, ARI, and dendrogram purity \(DP\)\. The best score for each metric is marked with∗∗and the second\-best with∗\. All metrics are computed on the test graph / heuristic clustering, and results are averaged over five runs\.
### D\.3Number of negative samples

In this section, we evaluate the impact of the number of negative examples per anchor used in the contrastive loss on the performance of our methodology\. The results are reported in Table[10](https://arxiv.org/html/2609.01942#A4.T10)\. Increasing the number of negative samplesppgenerally improves hierarchical clustering quality\. Dendrogram purity \(DP\) rises almost monotonically fromp=1p=1top=64p=64, reaching its maximum atp=64p=64, indicating that stronger contrastive separation enhances hierarchical structure\. NMI follows a similar upward trend, also peaking atp=64p=64, suggesting improved global agreement with the heuristic partition as more negatives are incorporated\. In contrast, ARI is highest atp=1p=1and remains relatively stable thereafter, with only minor variations across larger values ofpp\. Overall, larger numbers of negatives benefit hierarchical coherence and global structure recovery, while local pairwise consistency appears comparatively insensitive toppbeyond very small values\.

Table 10:Performance across differentppwith evaluation metrics NMI, ARI, and dendrogram purity \(DP\)\. The best score for each metric is marked with∗∗and the second\-best with∗\. All metrics are computed on the test graph / heuristic clustering, and results are averaged over five runs\.
### D\.4Approaching the Theoretical Conditions

##### Cluster homophily\.

Ideally, homophily would be measured by the spectral norm‖L−L∘‖op\\\|L\-L^\{\\circ\}\\\|\_\{\\mathrm\{op\}\}between the graph LaplacianLLand the ideal block\-diagonal LaplacianL∘L^\{\\circ\}, but this is infeasible for graphs with millions of nodes\. As a practical alternative, we use the*cut ratio*, the fraction of edges that cross between clusters: a low cut ratio indicates that most edges remain inside clusters and thus reflects strong homophily\. On the validation graph, the overall cut ratio is 87%; restricted to subgraphs of size 10–100 it is 77%, for size 100–1000 it is 51%, and for size 1000–5000 it is 49%\. To assess the significance of these scores given the graph topology, we randomly permuted 1% of node labels and recomputed the cut ratio over 300 trials\. For each case, we calculated a z\-score as the difference between the original score and the mean of the permuted scores, divided by their standard deviation\. The corresponding p\-value is the empirical probability that a random permutation yields a clustering more homophilic than the original\. The resulting z\-scores are \-9\.42 \(global\), \-3\.04 \(10\-100\), \-1\.09 \(100\-1000\), and \-1\.49 \(1000–5000\), with all p\-values below 0\.01, confirming that the observed homophily is highly significant for the graph topology\.

##### Low\-pass GNN behavior\.

For embeddingsH\(ℓ\)H^\{\(\\ell\)\}at layerℓ\\ell, the Dirichlet energyℰ⁡\(H\(ℓ\)\)=Trace⁡\(\(H\(ℓ\)\)⊤​L​H\(ℓ\)\)=∑i=1nλi​‖Hi\(ℓ\)‖22\\mathcal\{E\}\(H^\{\(\\ell\)\}\)=\\mathrm\{Trace\}\\bigl\(\(H^\{\(\\ell\)\}\)^\{\\top\}LH^\{\(\\ell\)\}\\bigr\)=\\sum\_\{i=1\}^\{n\}\\lambda\_\{i\}\\\|H^\{\(\\ell\)\}\_\{i\}\\\|\_\{2\}^\{2\}measures the concentration ofH\(ℓ\)H^\{\(\\ell\)\}on high\-frequency eigenvectors\. Normalizing by total energy gives the Rayleigh quotientR⁡\(H\(ℓ\)\)=Trace⁡\(\(H\(ℓ\)\)⊤​L​H\(ℓ\)\)/Trace⁡\(\(H\(ℓ\)\)⊤​H\(ℓ\)\)R\(H^\{\(\\ell\)\}\)=\\mathrm\{Trace\}\\bigl\(\(H^\{\(\\ell\)\}\)^\{\\top\}LH^\{\(\\ell\)\}\\bigr\)\\big/\\mathrm\{Trace\}\\bigl\(\(H^\{\(\\ell\)\}\)^\{\\top\}H^\{\(\\ell\)\}\\bigr\)\. A GNN acting as a low\-pass filter should yield small Rayleigh quotients that decrease across layers\. Across five training runs of a two\-layer GAT with default parameters, the Rayleigh quotient decreases from 6\.54 for the input embeddingsH\(0\)H^\{\(0\)\}to 1\.29 after the first convolutionH\(1\)H^\{\(1\)\}, then to 1\.20 after the first activation \(stillH\(1\)H^\{\(1\)\}\), and finally to 0\.99 at the outputH\(2\)H^\{\(2\)\}on the validation subgraph\. This monotonic drop confirms the expected low\-pass filtering behavior\.

##### Embedding\-Distance Distributions and Separability\.

The theoretical analysis in Section[4](https://arxiv.org/html/2609.01942#S4)relies directly on a separation condition between intra\-cluster and inter\-cluster distances: pairs belonging to the same cluster should be close in the embedding space, while pairs belonging to different clusters should be farther apart\. To empirically assess this intuition, we compare several distributions of cosine distances between embeddings, reported in Figure[5](https://arxiv.org/html/2609.01942#A4.F5): positive and negative pairs derived from the heuristic labels used during training, positive and negative pairs from the independent entity\-label evaluation, and negative pairs induced by CoinJoin transactions\.

![Refer to caption](https://arxiv.org/html/2609.01942v1/images/pair_distance_distribution.png)Figure 5:Empirical CDFs of cosine distances between embedding pairs without CoinJoin hard negatives\.This separability is very clear for pairs defined by the heuristics\. Heuristic positive pairs are strongly concentrated at small distances, whereas heuristic negative pairs are shifted toward much larger distances\. This confirms that the contrastive objective learns the geometry it is explicitly trained to produce: pulling together addresses from the same heuristic cluster and pushing apart addresses from different heuristic clusters\. The separation is less pronounced for pairs derived from independent entity labels, which is expected since these labels are not used as direct supervision during training and may reflect a noisier structure that is not perfectly aligned with the heuristics\. Nevertheless, the separation remains visible: entity\-label positives tend to be closer than entity\-label negatives\. This suggests that the embeddings do not merely reproduce heuristic labels mechanically, but partially transfer to an independent notion of entity identity\. This empirical separation also provides a geometric explanation for the strong results obtained in Table[2](https://arxiv.org/html/2609.01942#S6.T2)\.

CoinJoin negative pairs exhibit a different behavior, as shown in Figure[5](https://arxiv.org/html/2609.01942#A4.F5)\. Without CoinJoin hard\-negative training, they remain concentrated at much smaller distances than ordinary negative pairs, and their distribution is closer to the positive\-pair distributions\. This shows that the standard contrastive objective does not sufficiently separate CoinJoin inputs in the embedding space\. This behavior is consistent with the structure of CoinJoin transactions: many independent users appear in the same local transaction context\. The graph therefore induces strong structural proximity, although the corresponding addresses belong to distinct users\. CoinJoin transactions thus create a strongly heterophilic pattern, where proximity in the graph does not correspond to common ownership\.

After adding the CoinJoin repulsion loss, Figure[6](https://arxiv.org/html/2609.01942#A4.F6)shows that the distance distribution of CoinJoin negative pairs shifts markedly toward larger values\. The model therefore learns to better separate these hard negatives, and their distribution becomes closer to that of ordinary negative pairs\. This provides a geometric explanation for the improved true\-negative rates reported in Table[3](https://arxiv.org/html/2609.01942#S6.T3), and shows that the framework can adapt once the relevant heterophilic patterns are explicitly incorporated into the supervision signal\.

![Refer to caption](https://arxiv.org/html/2609.01942v1/images/pair_distance_distribution_with_coinjoin_loss.png)Figure 6:Empirical CDFs of cosine distances between embedding pairs with CoinJoin hard negatives\.

## Appendix EReproducing the Moser and Narayanan Heuristic

In this section, we reproduce the heuristic\-refinement methodology introduced by[Möser and Narayanan \[2022\]](https://arxiv.org/html/2609.01942#bib.bib29)\. The methodology focuses on payment transactions with exactly two outputs: one corresponding to the payment itself, and the other returning change, defined as the excess input value relative to the payment amount\. Under common privacy practices, it is often impossible to determine which output represents the payment and which represents the change\. Consequently, a number of heuristics have been proposed to infer the change address based on recurring behavioral patterns\.[Möser and Narayanan \[2022\]](https://arxiv.org/html/2609.01942#bib.bib29)employ twenty\-six such heuristics\. Given a dataset of payment transactions with two outputs,[Möser and Narayanan \[2022\]](https://arxiv.org/html/2609.01942#bib.bib29)train a random\-forest classifier to identify the change address using as features the individual decisions of each heuristic\. The source code used for both the heuristics and the model training is not publicly available, but the training dataset containing \(transaction identifier, index of the change output\) pairs is publicly available\.

We implemented all heuristics introduced in[Möser and Narayanan \[2022\]](https://arxiv.org/html/2609.01942#bib.bib29)and selected 30,000 transactions from the publicly released dataset to train our classifier\. To ensure full reproducibility, we provide our complete implementation in the same repository, together with an augmented dataset containing, for each transaction, all features required to apply the heuristics\. These heuristics are summarized in Table 1 of[Möser and Narayanan \[2022\]](https://arxiv.org/html/2609.01942#bib.bib29)\. The Random Forest classifier was trained usingscikit\-learn\. The training dataset includes, for each transaction, the individual heuristic decisions encoded as−1\-1,00, or11\(see Section 3\.3 and Appendix E of[Möser and Narayanan \[2022\]](https://arxiv.org/html/2609.01942#bib.bib29)\), together with additional transaction\-level features described in Appendix E\. We use the optimal hyperparameters reported in Appendix E of[Möser and Narayanan \[2022\]](https://arxiv.org/html/2609.01942#bib.bib29)\. On a20%20\\%held\-out test set, the classifier achieves an accuracy of99\.43%99\.43\\%, consistent with the performance reported in the original study\.

For experiments involving ground\-truth labels, we follow the clustering procedure described in Section 4 of[Möser and Narayanan \[2022\]](https://arxiv.org/html/2609.01942#bib.bib29)\. Specifically, we apply the common\-input heuristic and augment it with change\-address predictions produced by our classifier\. An address is classified as change and merged into the input cluster whenever the predicted probability exceeds0\.990\.99, matching the conservative threshold used in Section 4 of[Möser and Narayanan \[2022\]](https://arxiv.org/html/2609.01942#bib.bib29)\. For the experiment involving entity labels, we construct a dataset following the same format as Table 5 in[Möser and Narayanan \[2022\]](https://arxiv.org/html/2609.01942#bib.bib29), enabling full reproducibility\. In the CoinJoin experiment, the methodology achieves the same performance as the base heuristics, as it ultimately relies on the common\-input heuristic, which is known to be systematically misled by CoinJoin transactions \(see Sections 2 and 4 of[Möser and Narayanan \[2022\]](https://arxiv.org/html/2609.01942#bib.bib29)\)\.

## Appendix FProofs of Section[4](https://arxiv.org/html/2609.01942#S4)

### F\.1Proof of Lemma[1](https://arxiv.org/html/2609.01942#Thmtheorem1)

We begin by deriving a few spectral properties of the LaplacianL∘L^\{\\circ\}of the*ideal cluster graph*, in which two nodes are adjacent if and only if they belong to the same cluster\. It is well known that the LaplacianL∘L^\{\\circ\}of this ideal graph has00as an eigenvalue with multiplicity equal to the number of connected components—equivalently, the number of clusters\[[Von Luxburg, 2007](https://arxiv.org/html/2609.01942#bib.bib11)\]\. For each clusterCjC\_\{j\}, the normalized indicator vector

uj,i∘=\{\|Cj\|−1/2,if​i∈Cj,0,otherwise,u^\{\\circ\}\_\{j,i\}=\\begin\{cases\}\|C\_\{j\}\|^\{\-1/2\},&\\text\{if \}i\\in C\_\{j\},\\\\\[5\.69054pt\] 0,&\\text\{otherwise\},\\end\{cases\}is an eigenvector associated with the eigenvalue00, and these vectors form an orthonormal basis of the corresponding eigenspace\.

The spectral embedding of nodeiiin the*ideal model*, using the firstkkeigenvectors, is its coordinate vector in this basis:

\(ei∘\)j=\{\|Cj\|−1/2,if​i∈Cj,0,otherwise\.\(e^\{\\circ\}\_\{i\}\)\_\{j\}=\\begin\{cases\}\|C\_\{j\}\|^\{\-1/2\},&\\text\{if \}i\\in C\_\{j\},\\\\\[5\.69054pt\] 0,&\\text\{otherwise\}\.\\end\{cases\}Consequently, ifi,j∈Cai,j\\in C\_\{a\}thenei∘=ej∘e^\{\\circ\}\_\{i\}=e^\{\\circ\}\_\{j\}; and ifi∈Cai\\in C\_\{a\}andj∈Cbj\\in C\_\{b\}witha≠ba\\neq b,

‖ei∘−ej∘‖22=1\|Ca\|\+1\|Cb\|⇒‖ei∘−ej∘‖2≥2Smax\.\\\|e^\{\\circ\}\_\{i\}\-e^\{\\circ\}\_\{j\}\\\|\_\{2\}^\{2\}=\\frac\{1\}\{\|C\_\{a\}\|\}\+\\frac\{1\}\{\|C\_\{b\}\|\}\\qquad\\Rightarrow\\qquad\\\|e^\{\\circ\}\_\{i\}\-e^\{\\circ\}\_\{j\}\\\|\_\{2\}\\geq\\sqrt\{\\frac\{2\}\{S\_\{\\max\}\}\}\.
We now view the empirical LaplacianLLas a perturbation of the ideal LaplacianL∘L^\{\\circ\}and invoke spectral perturbation theory\. LetUk,Uk∘∈ℝn×kU\_\{k\},U\_\{k\}^\{\\circ\}\\in\\mathbb\{R\}^\{n\\times k\}collect the eigenvectors associated with thekksmallest eigenvalues ofLLandL∘L^\{\\circ\}, respectively\. By the Davis–Kahan–type result of[Yu et al\. \[2015\]](https://arxiv.org/html/2609.01942#bib.bib37), there exists an orthogonal matrixQ∈ℝk×kQ\\in\\mathbb\{R\}^\{k\\times k\}such that

‖Uk−Uk∘​Q‖F≤2​2​k​‖L−L∘‖opλk\+1​\(L∘\),\\\|U\_\{k\}\-U\_\{k\}^\{\\circ\}Q\\\|\_\{\\mathrm\{F\}\}\\;\\leq\\;\\frac\{2\\sqrt\{2k\}\\,\\\|L\-L^\{\\circ\}\\\|\_\{\\mathrm\{op\}\}\}\{\\lambda\_\{k\+1\}\(L^\{\\circ\}\)\},where∥⋅∥F\\\|\\cdot\\\|\_\{F\}is the Frobenius norm andλk\+1​\(L∘\)\\lambda\_\{k\+1\}\(L^\{\\circ\}\)denotes the\(k\+1\)\(k\+1\)\-th eigenvalue ofL∘L^\{\\circ\}\.

Leteise\_\{i\}^\{s\}be the spectral embedding of nodeiiobtained fromLL\. Applying the bound row\-wise gives, for every nodeii,

‖eis−ei∘​Q‖2≤2​2​k​‖L−L∘‖opλk\+1​\(L∘\)\.\\\|e\_\{i\}^\{s\}\-e\_\{i\}^\{\\circ\}Q\\\|\_\{2\}\\;\\leq\\;\\frac\{2\\sqrt\{2k\}\\,\\\|L\-L^\{\\circ\}\\\|\_\{\\mathrm\{op\}\}\}\{\\lambda\_\{k\+1\}\(L^\{\\circ\}\)\}\.By the triangle inequality and the orthogonality ofQQ,

‖eis−ejs‖2\\displaystyle\\\|e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\\\|\_\{2\}≤‖eis−ei∘​Q‖2\+‖\(ei∘−ej∘\)​Q‖2\+‖ej∘​Q−ejs‖2\\displaystyle\\leq\\\|e\_\{i\}^\{s\}\-e\_\{i\}^\{\\circ\}Q\\\|\_\{2\}\+\\\|\(e\_\{i\}^\{\\circ\}\-e\_\{j\}^\{\\circ\}\)Q\\\|\_\{2\}\+\\\|e\_\{j\}^\{\\circ\}Q\-e\_\{j\}^\{s\}\\\|\_\{2\}≤4​2​k​‖L−L∘‖opλk\+1​\(L∘\)\+‖ei∘−ej∘‖2\.\\displaystyle\\leq\\frac\{4\\sqrt\{2k\}\\,\\\|L\-L^\{\\circ\}\\\|\_\{\\mathrm\{op\}\}\}\{\\lambda\_\{k\+1\}\(L^\{\\circ\}\)\}\+\\\|e\_\{i\}^\{\\circ\}\-e\_\{j\}^\{\\circ\}\\\|\_\{2\}\.
In particular, ifiiandjjlie in the same cluster, thenei∘=ej∘e\_\{i\}^\{\\circ\}=e\_\{j\}^\{\\circ\}and

‖eis−ejs‖2≤4​2​k​‖L−L∘‖opλk\+1​\(L∘\)\.\\\|e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\\\|\_\{2\}\\;\\leq\\;\\frac\{4\\sqrt\{2k\}\\,\\\|L\-L^\{\\circ\}\\\|\_\{\\mathrm\{op\}\}\}\{\\lambda\_\{k\+1\}\(L^\{\\circ\}\)\}\.A symmetric argument yields the complementary lower bound

‖eis−ejs‖2≥‖ei∘−ej∘‖2−4​2​k​‖L−L∘‖opλk\+1​\(L∘\)\.\\\|e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\\\|\_\{2\}\\;\\geq\\;\\\|e\_\{i\}^\{\\circ\}\-e\_\{j\}^\{\\circ\}\\\|\_\{2\}\-\\frac\{4\\sqrt\{2k\}\\,\\\|L\-L^\{\\circ\}\\\|\_\{\\mathrm\{op\}\}\}\{\\lambda\_\{k\+1\}\(L^\{\\circ\}\)\}\.Hence, ifiiandjjbelong to different clusters,

‖eis−ejs‖2≥2Smax−4​2​k​‖L−L∘‖opλk\+1​\(L∘\)\.\\\|e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\\\|\_\{2\}\\;\\geq\\;\\sqrt\{\\tfrac\{2\}\{S\_\{\\max\}\}\}\-\\frac\{4\\sqrt\{2k\}\\,\\\|L\-L^\{\\circ\}\\\|\_\{\\mathrm\{op\}\}\}\{\\lambda\_\{k\+1\}\(L^\{\\circ\}\)\}\.
Finally, for the ideal cluster graph—a disjoint union of cliques—one hasλk\+1​\(L∘\)=SmaxSmax−1\\lambda\_\{k\+1\}\(L^\{\\circ\}\)=\\frac\{S\_\{\\max\}\}\{S\_\{\\max\}\-1\}, recovering the explicit constant used earlier\.

### F\.2Proof of Theorem[2](https://arxiv.org/html/2609.01942#Thmtheorem2)

Recall thatUk∈ℝn×kU\_\{k\}\\in\\mathbb\{R\}^\{n\\times k\}is the matrix whose columns are thekkorthonormal eigenvectors ofLLassociated with itskksmallest eigenvalues\. LetUk⟂U\_\{k\}^\{\\perp\}denote the matrix whose columns form an orthonormal basis of the orthogonal complement ofspan⁡\(Uk\)\\operatorname\{span\}\(U\_\{k\}\)\. The block matrix

U:=\[Uk​Uk⟂\]U:=\\bigl\[\\,U\_\{k\}\\;\\;U\_\{k\}^\{\\perp\}\\,\\bigr\]is therefore orthogonal and provides a full orthonormal basis ofℝn\\mathbb\{R\}^\{n\}\.

Under our structural assumption on the GNN, for input featuresX∈ℝn×dX\\in\\mathbb\{R\}^\{n\\times d\}and weight matrixW∈ℝd×mW\\in\\mathbb\{R\}^\{d\\times m\}, the linearized GNN can be written as

whereppis a polynomial filter\. Using the spectral decompositionL=U​D​U⊤L=UDU^\{\\top\}, this becomes

H=U​p​\(D\)​U⊤​X​W\.H=U\\,p\(D\)\\,U^\{\\top\}XW\.
This representation naturally separates the embedding into its low\-frequency and residual components,

H=Uk​p​\(Dk\)​Uk⊤​X​W\+Uk⟂​p​\(Dk⟂\)​\(Uk⟂\)⊤​X​W,H=U\_\{k\}\\,p\(D\_\{k\}\)\\,U\_\{k\}^\{\\top\}XW\+U\_\{k\}^\{\\perp\}\\,p\(D\_\{k\}^\{\\perp\}\)\\,\(U\_\{k\}^\{\\perp\}\)^\{\\top\}XW,highlighting the projection ofHHonto the informative subspace spanned byUkU\_\{k\}and its complement alongUk⟂U\_\{k\}^\{\\perp\}\.

LetPk:=Uk​Uk⊤P\_\{k\}:=U\_\{k\}U\_\{k\}^\{\\top\}denote the orthogonal projector onto the eigenspace spanned byUkU\_\{k\}\. Then

\(I−Pk\)​H=Uk⟂​p​\(Dk⟂\)​\(Uk⟂\)⊤​X​W,\(I\-P\_\{k\}\)H\\;=\\;U\_\{k\}^\{\\perp\}\\,p\(D\_\{k\}^\{\\perp\}\)\\,\(U\_\{k\}^\{\\perp\}\)^\{\\top\}XW,so the leakage ofHHoutsidespan⁡\(Uk\)\\mathrm\{span\}\(U\_\{k\}\)is controlled by

‖\(I−Pk\)​H‖op\\displaystyle\\\|\(I\-P\_\{k\}\)H\\\|\_\{\\mathrm\{op\}\}=‖p⁡\(Dk⟂\)​\(Uk⟂\)⊤​X​W‖op\\displaystyle=\\\|\\,p\(D\_\{k\}^\{\\perp\}\)\\,\(U\_\{k\}^\{\\perp\}\)^\{\\top\}XW\\,\\\|\_\{\\mathrm\{op\}\}≤‖p⁡\(Dk⟂\)‖op​‖X​W‖op\.\\displaystyle\\leq\\\|p\(D\_\{k\}^\{\\perp\}\)\\\|\_\{\\mathrm\{op\}\}\\,\\\|XW\\\|\_\{\\mathrm\{op\}\}\.BecauseDk⟂D\_\{k\}^\{\\perp\}is diagonal with entries given by the eigenvaluesλk\+1,…,λn\\lambda\_\{k\+1\},\\dots,\\lambda\_\{n\}ofLL, the operator norm ofp⁡\(Dk⟂\)p\(D\_\{k\}^\{\\perp\}\)is simply the largest absolute value ofp⁡\(λi\)p\(\\lambda\_\{i\}\)fori\>ki\>k\. Hence

‖\(I−Pk\)​H‖op≤\(maxi\>k⁡\|p⁡\(λi\)\|\)​‖X​W‖op=β​‖X​W‖op\.\\\|\(I\-P\_\{k\}\)H\\\|\_\{\\mathrm\{op\}\}\\leq\\Bigl\(\\max\_\{i\>k\}\|p\(\\lambda\_\{i\}\)\|\\Bigr\)\\,\\\|XW\\\|\_\{\\mathrm\{op\}\}=\\beta\\,\\\|XW\\\|\_\{\\mathrm\{op\}\}\.
Since for any matrixAAone hasmaxi∥Ai,:∥2≤∥A∥op\\max\_\{i\}\\\|A\_\{i,:\}\\\|\_\{2\}\\leq\\\|A\\\|\_\{\\mathrm\{op\}\}, it follows that for each nodeii, whose embedding is theii\-th rowhih\_\{i\}ofHH,

∥hi−\(PkH\)i,:∥2≤∥\(I−Pk\)H∥op≤β∥XW∥op\.\\\|\\,h\_\{i\}\-\(P\_\{k\}H\)\_\{i,:\}\\,\\\|\_\{2\}\\;\\leq\\;\\\|\(I\-P\_\{k\}\)H\\\|\_\{\\mathrm\{op\}\}\\;\\leq\\;\\beta\\,\\\|XW\\\|\_\{\\mathrm\{op\}\}\.
LetZ:=Uk⊤​H∈ℝk×mZ:=U\_\{k\}^\{\\top\}H\\in\\mathbb\{R\}^\{k\\times m\}; thenPk​H=Uk​ZP\_\{k\}H=U\_\{k\}Z, so that\(PkH\)i,:=\(eis\)⊤Z\(P\_\{k\}H\)\_\{i,:\}=\(e\_\{i\}^\{s\}\)^\{\\top\}Z\. Therefore, for any nodesi,j∈Vi,j\\in V,

‖hi−hj‖2\\displaystyle\\\|h\_\{i\}\-h\_\{j\}\\\|\_\{2\}≤∥hi−\(PkH\)i,:∥2\+∥\(eis−ejs\)⊤Z∥2\+∥\(PkH\)j,:−hj∥2\\displaystyle\\leq\\\|h\_\{i\}\-\(P\_\{k\}H\)\_\{i,:\}\\\|\_\{2\}\+\\\|\(e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\)^\{\\top\}Z\\\|\_\{2\}\+\\\|\(P\_\{k\}H\)\_\{j,:\}\-h\_\{j\}\\\|\_\{2\}≤2​β​‖X​W‖op\+‖\(eis−ejs\)⊤​Z‖2\.\\displaystyle\\leq 2\\,\\beta\\,\\\|XW\\\|\_\{\\mathrm\{op\}\}\+\\\|\(e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\)^\{\\top\}Z\\\|\_\{2\}\.
SinceZ=Uk⊤​H=p⁡\(Dk\)​Uk⊤​X​WZ=U\_\{k\}^\{\\top\}H=p\(D\_\{k\}\)\\,U\_\{k\}^\{\\top\}XW, we obtain

‖Z‖op≤‖p⁡\(Dk\)‖op​‖Uk⊤​X​W‖op≤\(maxi≤k⁡\|p⁡\(λi\)\|\)​‖X​W‖op=α​‖X​W‖op\.\\\|Z\\\|\_\{\\mathrm\{op\}\}\\;\\leq\\;\\\|p\(D\_\{k\}\)\\\|\_\{\\mathrm\{op\}\}\\,\\\|U\_\{k\}^\{\\top\}XW\\\|\_\{\\mathrm\{op\}\}\\;\\leq\\;\\Bigl\(\\max\_\{i\\leq k\}\|p\(\\lambda\_\{i\}\)\|\\Bigr\)\\,\\\|XW\\\|\_\{\\mathrm\{op\}\}=\\alpha\\,\\\|XW\\\|\_\{\\mathrm\{op\}\}\.Consequently,

‖\(eis−ejs\)⊤​Z‖2≤‖eis−ejs‖2​‖Z‖op≤α​‖X​W‖op​‖eis−ejs‖2\.\\\|\(e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\)^\{\\top\}Z\\\|\_\{2\}\\;\\leq\\;\\\|e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\\\|\_\{2\}\\,\\\|Z\\\|\_\{\\mathrm\{op\}\}\\;\\leq\\;\\alpha\\,\\\|XW\\\|\_\{\\mathrm\{op\}\}\\,\\\|e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\\\|\_\{2\}\.
Combining the two displays gives the upper bound

‖hi−hj‖2≤‖X​W‖op​\(2​β\+α​‖eis−ejs‖2\)\.\\\|h\_\{i\}\-h\_\{j\}\\\|\_\{2\}\\;\\leq\\;\\\|XW\\\|\_\{\\mathrm\{op\}\}\\left\(2\\,\\beta\+\\alpha\\,\\\|e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\\\|\_\{2\}\\right\)\.
A symmetric lower bound follows from the reverse triangle inequality:

∥hi−hj∥2≥∥\(eis−ejs\)⊤Z∥2−∥hi−\(PkH\)i,:∥2−∥hj−\(PkH\)j,:∥2\.\\\|h\_\{i\}\-h\_\{j\}\\\|\_\{2\}\\;\\geq\\;\\\|\(e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\)^\{\\top\}Z\\\|\_\{2\}\-\\\|h\_\{i\}\-\(P\_\{k\}H\)\_\{i,:\}\\\|\_\{2\}\-\\\|h\_\{j\}\-\(P\_\{k\}H\)\_\{j,:\}\\\|\_\{2\}\.Using the fact that‖\(eis−ejs\)⊤​Z‖2≥σmin​\(Z\)​‖eis−ejs‖2\\\|\(e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\)^\{\\top\}Z\\\|\_\{2\}\\geq\\sigma\_\{\\min\}\(Z\)\\,\\\|e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\\\|\_\{2\}and recalling thatZ=p⁡\(Dk\)​Uk⊤​X​WZ=p\(D\_\{k\}\)\\,U\_\{k\}^\{\\top\}XW, we obtain

σmin​\(Z\)≥\(mini≤k⁡\|p⁡\(λi\)\|\)​σmin​\(Uk⊤​X​W\)=γ​σmin​\(Uk⊤​X​W\)\.\\sigma\_\{\\min\}\(Z\)\\;\\geq\\;\\Bigl\(\\min\_\{i\\leq k\}\|p\(\\lambda\_\{i\}\)\|\\Bigr\)\\,\\sigma\_\{\\min\}\(U\_\{k\}^\{\\top\}XW\)=\\gamma\\,\\sigma\_\{\\min\}\(U\_\{k\}^\{\\top\}XW\)\.Hence,

‖hi−hj‖2≥γ​σmin​\(Uk⊤​X​W\)​‖eis−ejs‖2−2​β​‖X​W‖op\.\\\|h\_\{i\}\-h\_\{j\}\\\|\_\{2\}\\;\\geq\\;\\gamma\\,\\sigma\_\{\\min\}\(U\_\{k\}^\{\\top\}XW\)\\,\\\|e\_\{i\}^\{s\}\-e\_\{j\}^\{s\}\\\|\_\{2\}\-2\\,\\beta\\,\\\|XW\\\|\_\{\\mathrm\{op\}\}\.
Using the bounds from Lemma[1](https://arxiv.org/html/2609.01942#Thmtheorem1)and substituting them into the inequalities above, we obtain the following estimates\.

For nodesi,ji,jin the*same*cluster,

‖hi−hj‖2≤‖X​W‖op​\(2​β\+4​2​k​αλk\+1​\(L∘\)​‖L−L∘‖op\)\.\\\|h\_\{i\}\-h\_\{j\}\\\|\_\{2\}\\;\\leq\\;\\\|XW\\\|\_\{\\mathrm\{op\}\}\\left\(2\\,\\beta\+\\frac\{4\\sqrt\{2k\}\\,\\alpha\}\{\\lambda\_\{k\+1\}\(L^\{\\circ\}\)\}\\\|L\-L^\{\\circ\}\\\|\_\{\\mathrm\{op\}\}\\right\)\.
For nodesi,ji,jin*different*clusters,

‖hi−hj‖2≥γ​σmin​\(Uk⊤​X​W\)​\(2Smax−4​2​kλk\+1​\(L∘\)​‖L−L∘‖op\)−2​β​‖X​W‖op\.\\\|h\_\{i\}\-h\_\{j\}\\\|\_\{2\}\\;\\geq\\;\\gamma\\,\\sigma\_\{\\min\}\(U\_\{k\}^\{\\top\}XW\)\\left\(\\sqrt\{\\frac\{2\}\{S\_\{\\max\}\}\}\-\\frac\{4\\sqrt\{2k\}\}\{\\lambda\_\{k\+1\}\(L^\{\\circ\}\)\}\\\|L\-L^\{\\circ\}\\\|\_\{\\mathrm\{op\}\}\\right\)\-2\\,\\beta\\,\\\|XW\\\|\_\{\\mathrm\{op\}\}\.

## Appendix GComputational Complexity Analysis

We summarize here the computational costs associated with each step of our pipeline\. LetN=\|V\|N=\|V\|denote the number of nodes,M=\|E\|M=\|E\|the number of edges,ddthe embedding dimension,ksk\_\{s\}the maximum number of neighbors sampled at each GNN layer, andklk\_\{l\}the maximum size of the Leiden pre\-clusters\. Table[11](https://arxiv.org/html/2609.01942#A7.T11)reports asymptotic time and memory requirements for each stage of the method\. These complexity estimates are based on thePyTorchimplementations used for the GNN components, theSciPyimplementation used for hierarchical agglomerative clustering, and theleidenalgpackage for the Leiden pre\-clustering step\.

Table 11:Complexity analysis\.These results highlight the main computational bottlenecks\. Embedding computation scales linearly in bothNNandMM, especially when neighbor sampling is applied\. In contrast, operations involving pairwise distances or hierarchical clustering scale quadratically inNN, which motivates the need for pre\-clustering or highly local sampling strategies\. As an illustration, both[Monath et al\. \[2021\]](https://arxiv.org/html/2609.01942#bib.bib4)and[Dhulipala et al\. \[2023\]](https://arxiv.org/html/2609.01942#bib.bib48)propose scalable HAC algorithms that mitigate these quadratic costs\.