潘嘉铖, 韩东明, 郭方舟, 郑文庭, 于金辉, 陈 为

(计算机辅助设计与图形学国家重点实验室(浙江大学),浙江 杭州 310058)

1 引 言

比特币交易以钱包作为基本单位,比特币在钱包之间进行流动.若将比特币钱包当作节点,并将钱包之间的交易当作连接节点的边,比特币交易就可以被转化为一个交易网络.它具有两个特点:首先,网络中的节点是匿名的.其次,网络规模大.

因为交易的匿名性,常常需要基于交易网络的拓扑结构对比特币交易进行分析.但是,当网络的规模非常大时,用户在分析之前很难对整个交易网络有清晰的认知.因此,在分析比特币交易网络之前,用户对整个网络进行交互式探索非常有必要.已有一些方法用于支持大图探索[1-3].一般基于两种通用的策略:(1)自顶向下的探索,往往会提供网络结构的一个概览,然后通过过滤或者查询来引导分析者到一个局部细节上.(2)自下向上的探索[4],首先在分析者需求的基础上,展示局部细节,并且能够支持跟踪感兴趣的节点和边(DOI).

在这两种策略下,分析者需要非常频繁地进入到局部区域来进行探索.在不同层次的细节间进行切换以对整个网络进行导航,或者说是在节点和边之间进行逐步探索,这是一个常用的操作.因此,自动推荐合适的视图(view)或者结构就会是一种更高效的方法[1,5,6].

在图论中,结构指的是图中一系列节点和边的集合,在本文中,节点指的是交易网络中的一部分钱包,边则是钱包之间的联系,故而结构指的是钱包和钱包之间的交易模式.一个结构描述了交易网络中的一个特定的交易模式.在根据范例来推荐结构的过程中,最主要的挑战就是子图匹配问题,但这个问题在无标记的简单网络中被证明是一个NP 问题[7].已存在的子图匹配方法经常以有特定特征的网络为目标[8](比如有标记或属性的网络节点).找寻相似子图还难以被实时计算,通过推荐相似结构的交互式探索仍然是一个挑战.本文通过将网络中的节点转换成向量,将相似子图搜索的过程转换到高维空间中进行,从而有效地加速了相似子图的搜索过程,使得推荐的交互式探索成为可能.

本文提出了一种基于拓扑结构推荐的比特币交易网络可视分析系统.系统使用了一种“表达&查询”的构架,支持在用户探索比特币交易网络的过程中,以用户定义的范例结构为基础,为用户推荐合适的结构.在基于样本查询所有候选结构之前,预先计算每个结构的向量化表示.本文所提方法从一个范例结构开始,支持交互式查询、辨认、标记、比较和分析.

2 相关工作

2.1 比特币交易网络分析

Baumann 等人在2014 年的工作[9]将描述统计学和图挖掘算法应用于比特币交易网络数据分析,他们利用了一些聚合算法来突出网络特征,并聚焦于研究网络的时序变化.

在利用可视化系统对比特币交易网络进行深层次的分析方面,Battista 等人在2015 年的工作[10]中利用高级隐喻来表示交易网络以及交易的特征,从而能够对比特币网络进行高层次的分析.他们引入一个真实的洗钱系统的例子来进行分析,证明了工作的有效性.在此基础上,2017 年,Kinkeldey 等人开发了一个可视分析系统[11],用于分析比特币交易网络上的金融活动,该系统通过后端的数据转换,可以访问基于实体的区块链数据,并开发了一个前端系统,通过过滤和聚类等方式,使用户能够在高层次视角下观察比特币的交易数据.

针对利用比特币交易来进行洗钱的行为,Möser 等人[12]的工作系统地介绍了比特币交易系统中存在的洗钱模式,并以此作为提出反洗钱工具的基础工作.在此基础上,Dan 等人在2016 年[13]利用力引导图可视化来帮助加速大规模比特币交易数据的探索,并提供了协作模式,用以发现一些意想不到却又高频发生的交易模式,比如洗钱操作.

2.2 大图可视化

大图可视化往往用于进行大规模网络数据的分析和认知[14],这些大图可视化的技术可以分成两大类:自顶向下的技术和自下向上的技术.

自顶向下的技术往往比较直观,一般会先为用户提供一整个网络结构的概览,帮助用户对整体网络数据有一个初步认知[15,16].但当网络规模扩大时,生成网络概览的计算代价也会跟着升高,用户在分析网络时的认知代价也会相应提升.一般会用诸如聚类[17,18]、采样[19]、过滤[20]等方式来降低需要用于网络概览计算、展示的对象的数量,或者通过边绑定的技术来降低视觉拥挤[21,22],并辅助以缩放[23,24]、展开[3,25]等交互技术,以应对大规模网络数据.自下向上的方法,则提供了另外一种思路.用户从某个节点或者网络中一个小结构出发,开始迭代地探索和分析这些已展示的节点的邻接或者相关节点.像Link Sliding 和Bring&Go[4]的技术则单纯基于网络拓扑进行探索分析,而对于有标记的图,则可以用一些基于相似度的方法来找到相关节点用以探索[1,5,26],Peinta 等人设计了称为Facets 的技术[6],通过相似度以及“惊奇分数”对大规模网络进行探索分析.在焦点上下文可视化中,往往会使用兴趣度(DOI)技术来帮助用户进行大规模网络探索[27-29].Van Ham等人的工作[3]使用兴趣度(DOI)技术在某个选定的节点周围抽取了一个最小兴趣子图,并支持用户在任意方向对这个子图进行伸展.Abello 等人的工作[30]提出了一种交互式的DOI 技术,用以分析动态网络.Kairam 等人开发的称为Refinery[31]的可视化系统,通过计算DOI 分数来支持异构网络的探索.最近,Srinivasan 等人开发的Orko 系统[2]则是用多模式交互来支持网络探索分析.最近的一些可视查询技术,通过交互式地构造图查询并对查询结构进行分析.Cao 等人提出的g-miner 技术[32]用来对多元网络的节点组进行可视挖掘.Graphite[33]、Vogue[34]和Visage[35]则为用户提供了可视化界面,用来交互式地构造、优化图查询.而Vigor[36]作为一个可视化系统,用户可以在其中交互式地对图查询结构进行交互式的探索和分析.

2.3 相似子图挖掘

子图挖掘是数据挖掘中的重要领域,已有许多工作总结了近年来的子图挖掘相关算法[37,38].例如,VF2plus[39]、VF3[40]等同构子图挖掘算法,这些算法可以得到完全匹配的子图,这需要庞大的计算量进行支持,很难在交互的时间内返回结果;gSpan[41]、rami[42]等频繁子图挖掘算法等可以搜索得到图中的频繁子图,但是不能搜索到子图所处位置.而本文所用的方法是搜索相似的结构,并可以返回其所在网络中的位置.

3 方法概述

本文主要聚焦于无标记的简单比特币交易网络(无向无权,不带自循环和多重边)的可视探索.首先计算每个网络结构中节点的向量化表达,再根据向量化表达查询候选结构.在进行向量化表达时,节点会被转化到高维空间中.相对于拓扑空间而言,在高维空间对节点的分析和比较会更快,进而加快了基于结构的查询和探索.

本文工作的基础流程分成3 步:(1)首先在预处理过程中,比特币交易数据会被抽取为比特币交易网络,并且利用将网络中的每一个节点转换成向量化表达;(2)在可视化系统中,用户可以通过交互,指定一个范例.系统将与范例具有拓扑相似性的结构推荐给用户,用户可以对被推荐的结构进行探索和分析;(3)通过对整个比特币交易网络的迭代式的探索分析,用户能够修正该推荐结构.

经过上述过程后,用户可以迭代式地对比特币交易网络进行高效探索,在这种探索模式下,即便不同的区域在网络中相距较远,也能够被同时展示给用户.

4 算法设计

在开始详细描述向量化表达和结构查询的过程之前,需要定义一些符号.定义一个简单的无标记网络为G=(V,E),其中,V={v1,v2,…,vn}是n个节点的集合,E={e1,e2,…,ek|ei=(vm,vn),vm,vn∈V}表示连接V中节点的边.我们用N(v)来表示节点v的邻接节点的集合,gS表示用户指定的范例结构,C+表示gS中的所有节点的k最近邻中包含的所有连通子图,C表示C+中的一个连通子图.Dis 则是G的所有节点之间的距离矩阵.Co 表示了范例结构中的节点与检测到的结构中的节点之间的对应关系.order 函数的两个参数分别为一组连通子图和目标子图,返回这组连通子图以及和目标子图的相似度从大到小排序后的结果.

4.1 向量化表达

近年来,用图的小波变换(GraphWave[43])来生成向量化表达已经引起了很多关注,并应用在很多模式挖掘、噪声移除、信息压缩等领域[44],图的小波变换也被证明能够很好地提取到图中的一些局部拓扑特征,所以本文希望使用小波变换生成的向量化表达来捕获图的局部拓扑特征,并以之支持相似结构查询等.

算法的关键思想是为每个节点v(及其相关的局部结构)生成向量化表达,从而能够使用基于向量的相似度度量和查询.节点的拓扑结构信息可以对节点的表达进行定义,本系统选择了GraphWave 技术来对网络生成节点表达.其通过图的小波扩散模式,利用节点邻域的信息,为每个节点生成向量化表达.GraphWave 将小波视作是图上的概率分布,生成的向量即表达了这种概率分布.GraphWave 保证了局部邻域相似的节点,其对应的生成向量也会相似.

4.2 相似结构查询

对于用户给定的范例,要查询出相似的结构需要以下4 步(如图1 所示).

Fig.1 Pseudo-code of similar structure detection and the procedure diagram图1 相似结构检测算法伪代码和过程示意

(1)通过给定范例中节点向量化表达的相似度,构造一组候选节点的集合.

本工作通过选择与范例中的节点类似的节点来构建候选节点集.具体地,给出一个包含了m个节点的范例,检查每个节点v的k个最近邻,并将它们组合为候选节点集N.但是,不同节点的最近邻可能有重复,N的大小将小于m×k.

节点v的k最近邻是根据节点的向量化表示的相似度来构造的.本文使用了欧氏距离来表达向量之间的相异度.

(2)在这群候选节点中,根据原图存在的拓扑结构,构造出多个连通的子图.

给定了m个节点k个最近邻,精确的搜索空间是km.完全遍历这个空间以找到类似的结构将会有两个挑战.首先,时间复杂度太高,不足以支持交互式的探索;其次,它只支持精确匹配,即探测出的结构的节点必须与范例中的节点存在一一对应的映射关系.事实上,探测的结构很少能够完全一样,所以结构的检测必须容忍一定程度的差异.

因此,本工作建议检测所有搜索空间中的连通子图,它由候选节点及其边组成.检测到的子图被视为候选的目标结构.这里的假设条件是,检测到的结构必须是原始网络中的连通子图,并且其中每个节点必须与范例中的某个节点相似.

(3)建立范例中的节点与候选节点之间的对应关系.

对于检测到的结构,从连接的每个子图(组件)C中的节点会在范例gS中寻找向量空间中距离最短的节点,并与之建立对应关系.

(4)将检测出来的子图根据它们和范例的结构相似度进行排序和过滤.

检测到的结构会根据Weisfeiler-Lehman 图核[45]计算得到的结构相似度分数进行排序.与范例最为相似的结构会进行展示,而一些不相似的结构则会被过滤掉以减少需要探索的结构数量.在本文中,过小的连通结构或者过大的结构均会被过滤.

5 可视分析系统

本文开发了一个可视分析系统,用以支持基于拓扑结构的针对比特币交易网络推荐式探索分析.图2 展示了整个系统的用户界面,该系统由5 个主要视图组成:(1)节点链接视图(如图2(C)所示),显示了比特币交易网络的详细结构,用户可以在其中探索、识别感兴趣的结构;(2)热力图视图(如图2(A)所示),通过对交易网络的二维布局进行核密度估计生成的热力图,作为其概览;(3)向量投影视图(如图2(B)所示):交易网络中的节点向量化表达的投影视图,用以观察不同结构的节点向量化表达差异;(4)推荐展示视图(如图2(D)所示),用以展示推荐的结构;(5)探索历史树,用以记录探索过的结构.

Fig.2 System interface design图2 系统界面设计

5.1 节点链接视图

节点链接视图(如图2(C)所示)是对比特币交易网络进行探索以及对用户感兴趣的范例结构进行选取的主要工作空间.该视图用预先计算完毕的力引导布局来呈现比特币交易网络的详细结构,并提供了平移和缩放工具来支持对网络的探索导航.

5.2 热力图视图

为帮助用户了解网络的大致形状并定位感兴趣的结构,系统展示了基于核密度估计的热力图以及提取的轮廓线(如图2(A)所示).该视图中,用户已经探索过的区域会被标记为灰色,未探索到的区域标注为蓝色.热力图视图提供了一系列的交互工具,包括放大/缩小、兴趣区域(ROI)的选择和平移以及推荐结构的定位.

(1)缩放:支持了不同级别缩放技术,多级别利用不同带宽的核密度估计函数来生成.

(2)兴趣区域(ROI)的选择和平移:用户可以通过在该视图中绘制一个矩形来选择兴趣区域(ROI).用户可以通过拖动来平移兴趣区域(ROI),并在节点链接视图中同步浏览该兴趣区域(ROI)的详细信息.

(3)推荐结构的定位:当用户定义了一个范例时,该范例及推荐结构将会被标记在热力图视图中.用户能够通过点击标记来定位范例或推荐结构.

5.3 向量投影视图

向量投影视图(如图2(B)所示),利用了t-SNE 投影算法[29],将比特币交易网络中每个节点的向量化表达投影至二维空间中.首先,t-SNE 投影算法将两个向量之间的相似度表示成概率分布,使得相似的向量表示为高概率,不相似的向量表示为低概率,之后,在二维空间中构建这些点的概率分布,并优化这个二维空间的概率分布,使其尽可能地接近高位空间的概率分布.在该视图中,用户能比较不同网络结构中节点的向量化表达的差别.当用户指定某个结构时,该结构会在向量投影视图中高亮显示.当用户指向悬浮在某个投影点上时,会高亮该节点、该节点的一级邻域以及它们之间的连接边.向量投影视图还提供了缩放、平移等交互.在该视图中,用户也可以指定范例,通过双击某个节点,将会选中该节点以及该节点的邻接节点,然后,用户可以通过套索工具(lasso)来删减不需要的节点,最终将选中的节点及其连接边作为范例结构.

5.4 推荐展示视图

推荐展示视图(如图2(D)所示),利用推荐结构和指定范例之间的结构相似度,对推荐结构进行降序排列.用户可以通过“上一页”和“下一页”按钮,对这些推荐结构进行浏览.范例位于视图的最左侧.推荐的结构和范例通过以下3 个步骤进行统一的布局,以便进行比较.

(1)使用力引导布局来计算指定的范例的布局.

(2)设置每个推荐结构的初始布局.推荐结构的每个节点都能映射到范例的节点,将推荐结构的节点初始位置设置为范例中相对应的节点的位置.

(3)在上一步的初始布局中加入扰动以防止重叠.当多个节点映射到范例的同一个节点时,会有视觉混乱.可以用力引导算法对节点位置进行几次迭代产生扰动来避免该问题.实现过程中发现,3 次迭代就足够有效.

6 用户实验

我们实现了一个基于Web 的系统.系统采用React、D3.js 和PixiJS 来实现前端应用.使用Python 3.0 来实现后端服务器.数据处理使用了Scipy 和Numpy.MongoDB 用于数据存储.

我们邀请一名网络关系分析相关研究者来使用我们的系统,在基本的指导下,使用者开始对一个真实世界存在的比特币交易网络进行分析.网络数据是从Blockchain 的公开数据中提取的比特币交易网络.该网络是2018 年1 月1 日交易日志的子集,包含了207 689 个节点和547 500 条边.

案例1 展示了系统最基础的功能:概览+细节交互模式的应用,用户可以在热力图视图中刷选感兴趣区域,在节点链接视图中查看细节;案例2 则展示了系统的相似结构检测算法用于比特币交易网络分析的过程.

假设有一个财务分析师想要了解比特币交易的模式,却从未接触过比特币交易模式的相关分析.分析师需要向上级汇报比特币交易中存在的一些普遍存在的以及一些特殊的交易模式,以便对整个比特币交易网络有一个大致的了解.

6.1 案例1

首先,这名分析师将网络载入系统中,然后从热力图视图开始进行分析.热力图显示出,有3 个密度较高的区域,则先从这些区域开始探索.

分析师首先在热力图中进行刷选,选择一个高密度区域,以观察节点链接视图.在节点链接视图中,他发现有少量节点具有高中心化的性质,也即,有一些实体(人或者组织)在与大量的实体进行交易.其中,有一个节点与大量的节点链接在一起(如图3(B)所示).该节点的高中心化特质,说明其与很多其他实体在进行交易,一般而言,存在这样高频次交易的实体,往往是某个交易所.同样地,分析师在另外的高密度区域也发现了类似的高中心化的交易模式,分析师认为这是一些交易所.但分析师并不确认这些交易所是否属于合法经营、用户在这些交易所进行的交易行为是否有安全保障.分析师将该节点记录下来,写入报告中,并建议继续调查该节点.

Fig.3 A:Heatmap of the bitcoin trading network;B:A high-density area:Highly centralized trading mode;C:An examplar;D:Structures found by using the examplar图3 A:所用比特币交易数据的热力图;B:其中一个高密度区:高中心化的交易模式;C:范例;D:基于范例确定的结构

6.2 案例2

在检查各个高密度中心时,分析师在附近发现了一种特殊的交易模式,几个不同的节点都与一群公共的节点进行连接,这些公共的节点互相之间不存在任何交易(如图3(C)所示),于是他在节点链接视图中选取这个结构作为范例结构,然后通过系统推荐算法,获得一些相似的推荐结构,如图3(D)所示.分析师把这种结构称为多中心的星状结构.

这些结构零散地出现在了其他区域中,表达了相似的交易模式:往往都是大量的实体与少量的实体存在交易,而这些大量的实体之间并不存在交易.

分析师认为,一般而言,这种小规模的多中心网络存在两种可能:(1)度数较低的节点只与中心节点进行交易的模式,可能代表了这是一种分布式比特币挖掘计算的模式,中心节点所代表的实体拥有一群用于比特币挖掘计算的“矿机”.而该实体习惯于和另一个实体进行交易,或者在这个双星结构中,两个中心所代表的账户为一个实体所有.(2)这种模式可能与洗钱行为相关.洗钱过程往往会存在大量重复的交易以掩盖非法手段获得的金钱转换成合法资产的过程,并且,为了逃避监管,洗钱者往往会将大笔的资金分割成多笔小数目的资金同时进行交易.于是,比特币从一个账户出发,通过大量的小笔交易,又汇总到一个账户下,经过几次迭代,达到洗钱的目的.

7 讨 论

与以往的分析系统相比,本文提出的方法支持用户通过选定范例来进行推荐式的交互探索.而与传统的查询方式(往往为图数据库设计)相比,本文提到的算法具有如下优势:(1)算法可以更广泛地应用于图数据查询,而基于数据库的查询方法往往是为带有属性的图设计的,而本文的方法只需要拓扑信息,并且在无标记图上也可以使用.(2)算法具有更高的容错率,所推荐的相似结构能够容忍细微的结构差异,从而提供更加包容性的查询结果.基于数据库的查询方法,通常需要显式表达范例结构,并且可能产生冗余的查询结果.例如,在一幅6 个节点的完全连通图中,查询一幅具有5 个节点的完全连通图,基于数据库的方法会返回6 个相互重叠的结果,而本文的方法使用的是描述性的结构,能够容忍一定程度的差异(比如节点数量),会直接返回一幅6 个节点的完全连通图,而非5 个互相重叠的结果.(3)本文的方法可以为更多的用户服务,他们可以在图中自由地选定需要查询的结构,而非像基于数据库的查询方法那样,需要用户根据自己的经验来构建具有节点属性、节点之间关系的目标结构表达式来进行显式查询.

当然,本文的方法还存在一些局限性.在构建查询范例时,往往不关注这个范例的上下文信息,然而节点的向量化表达来源于其上下文信息,因此推荐的结果倾向于与查询的范例拥有相似的上下文,但这个上下文的相似性往往不被关注,当网络结构非常复杂时,可能会导致一些意想不到的结果.

8 结 语

在未来的研究工作中,将对目前的查询算法作进一步的优化,深入研究如何进一步提高查询算法的准确度和计算效率,以更快、更准确地为用户在探索、分析比特币交易网络的过程中提供推荐结果.此外,希望能够对网络的向量化表达方法进行优化,缩短向量化表达的计算时间,降低预计算的耗时.最后,我们还将继续挖掘基于目前的探索分析模式在比特币网络上的分析场景,结合更多的信息来支持更多的分析任务.例如,结合一些公开的钱包信息,分析与比特币交易所相关的账户的交易模式,探索其中的异常交易行为等等.