摘要
本文提出了GEM（Graph Embedding for Malicious accounts）模型，是一个异质图神经网络方法，用于支付宝恶意账户的检测。
本文的方法受到连通子图方法的启发，基于攻击者的两个基本弱点（device aggregation和activity aggregation），从异质的账户-设备（account-device）图中自适应地学习到embedding。
使用注意力机制，为不同类型的节点分配不同的注意力。聚合每种节点的信息时，使用的是求和的方式。
1 介绍
要能检测出恶意账户，首先要研究恶意账户的攻击特征。现有的研究主要从三个方面展开：
- 基于规则的方法：使用复杂的规则，识别恶意账户
- 基于图的方法：考虑用户之间的关联，恶意账户和正常账户之间有关联
- 基于机器学习的方法：利用大量的历史数据，建立统计模型
攻击者的攻击策略是会不断变化的，所以需要一个能够适应这种变化的检测系统。
作者总结了来自攻击者的两个主要特征：
设备聚集（device aggregation）
攻击者要承受计算资源带来的成本，所以大多数攻击者只在少数计算资源上注册或频繁地登录。
行为聚集（activity aggregation）
攻击者受攻击时间的限制，通常要在很短的时间内完成既定目标，所以恶意账户的行为可能在有限的时间内爆发。
虽然我们已经广泛地分析了攻击者的弱点，但保证识别的高准确率和高召回率还是非常具有挑战性的。
现有的方法通常假阳率（FP，模型判断是恶意账户，实际上不是）很低，也就是假阴率（FN，模型判断不是恶意账户，实际上是）很高。
这样虽然对用户友好，避免误伤，但是可能会错过识别出更多可疑账户的机会。产生这种情况的原因在于大量的良性账户和少量的可以账户交织在一起，形成了低信噪比。
因此，在不同设备构成的异构图中同时考虑”设备聚集”和”行为聚集”是很重要的。
Representation Learning on Graphs: Methods and Applications.
本文提出**GEM模型(Graph Embeddings for Malicious accounts)**，同时考虑了异质图中的“设备聚集”和“行为聚集”，是一种基于图网络的图表示学习方法。
本文提出的方法本质上是对异质的account-device图进行建模，同时考虑了局部结构中账户的行为特征。
模型的基本思想是：账户是正常的还是恶意的，取决于其他账户是如何通过设备与该设备聚集的，以及那些与该账户共享同一设备的账户的行为表现是什么样子的。
本文的贡献如下：
- 提出基于图表示学习方法的神经网络，同时关注攻击者“设备聚集”和“行为聚集”两个特点，以实现对恶意账户的检测。是第一个使用GNN方法进行欺诈检测的工作；
- 本文的模型已在支付宝中应用，每天可以有效检测出上万的恶意账户。
2 预备知识
在本节中，我们首先简要介绍最近发展起来的图表示学习技术。（GNN只是图表示学习的一种技术罢了）
2.1 图神经网络
第一类技术与在图、图的边或图的节点上预测标签有关。
Kipf提出的GCN是在一阶邻居上进行卷积。$X\in R^{N,D}$是节点特征向量$x_i\in R^D$组成的矩阵。无向图$G=(V,E)$,有$N$个节点$v_i\in V$，边$ (v_i,v_j)\in E$，邻接矩阵为$A\in R^{N\times N}$。卷积层计算如下：
其中$\tilde{A}$是$A$添加self-loops后对称归一化(symmetric normalization )的结果：$\tilde{A}=\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}$, $\hat{A}=A+I$,$\hat{D}$是$\hat{A}$中节点度的对角矩阵。
关于GCN的解释可以参考这位大佬的博客，总结的非常好：
图卷积网络 GCN Graph Convolutional Network（谱域GCN）的理解和详细推导-持续更新
GCN学习到了函数$f(X,A)$，使用$A$中节点$v_i$的邻居信息表示该节点。
文章中还介绍了两个GNN的工作
总之，GNN的工作可以看成是递归地聚合邻居信息的方法：
GNN中大多数的工作都是围绕”感受野(receptive fileds)“的研究，也就是进行聚合的范围。图结构的数据是非欧式的，每个节点的邻居数目不确定，不像图像数据每个像素点就只有8个邻居。
有学者提出了GeniePath，可以自适应地为每个节点设定不同的感受野，而不像GCN那样预先设定好卷积的感受野。
本文的工作可以看成是GCN的变形。作者使用求和(sum)的操作捕获每个节点$T$步邻居聚合来的信息，并且使用注意力机制衡量不同类型节点的重要性。
2.2 Node Embedding
第二类技术包括图嵌入方法，目的是在保留图结构带来的信息的同时学习每个节点的表示。
大多数方法目的都是最小化如下的衡量重构能力的经验损失：
3 提出的方法
- 描述在支付宝数据集上发现的两个pattern；
- 讨论一个基于连通子图的motivated方法；
- 基于2中提到的motivated的方法，利用1中发现的两个pattern构建HIN；
- 讲述最终的模型
3.1 数据分析
本节研究了支付宝中真实数据中体现出来的“设备聚集”和“行为聚集”的特性。
3.1.1 设备聚集（Device Aggregation）
基本思想是：若一个账户与大量的其他账户一起注册或登录同一组设备，则这些账户就会被怀疑是恶意账户。
计算连通子图的规模，通过规模的大小来衡量账户的风险。
3.1.2 行为聚集（Behavior Aggregation）
基本思想是：如果共享设备的账户成批运行，则这些账户就是可疑的。使用向量内积作为衡量标准，即$S^a_{i,i^{‘}}=<x_i, x_{i^{‘}}>$。
这样的度量两个账户关联性的方法，可以用于对连通子图进行进一步分割，来提高假阳性概率。
上图表示设备聚集，展示了支付宝中连续7天的account-device数据图。对于正常账户，蓝色的点均匀分布在图中。对于恶意账户，点的分布表明特定的设备以不同的模式连接了大量的账户。
也就是一个Device对应了大量的账户。
上图表示行为聚集，展示了账户在不同时间的行为模式。左图的正常账户的行为显示，每个新注册的账户在未来几天内的行为是均匀分布的。而右图中的恶意账户的行为往往只在短时间内爆发。
正如前面所说的，为了快速完成任务，恶意账号只会在一小段时间内活跃。而正常账号则是均匀的活动~
3.2 A Motivation: Subgraph Components
上述的设备聚集和行为聚集模式启发了作者使用图的方式来解决问题。
第一步尝试称为“连通子图(connected subgraph)”。
基本思想是建立只包含账户构成的图，希望用边建立起一组账户。
连通子图方法由以下三步组成：
给定图$G=(V,E)$，有$N$个节点，$M$条边。${(i,j)}$表示账户$i$在设备$j$上有登录行为。目标是构建一个只由账户节点构成的同质图。$G^a=(V^a,E^a)$，边$ (i,i^{‘})$表示账户$i$和$i^{‘}$有一段时间在同一设备上登录。
这样，同质图$G^a$就由多个连通子图所构成，每个子图表示一组相关的账户。这组账户数量越多，则为恶意账户的风险越大。
但是实际操作中有很多噪声，例如不同账户登录相同的ip地址，混淆正常账户和恶意账户的现象很普遍。
接着按照如下的方法删除掉一些边。由图2所示，异常账户的行为通常在特定的一天的短暂一段时间内爆发。为了衡量$G^a$中两个账户节点间的相似性，使用向量$x_i=[x_{i,1},…,x_{i,p}]^{\mathrm T}$表示账户$i$的行为，$x_{i,t}$表示账户$i$在第$t$小时行为的频率。
使用内积运算$x^{\mathrm{ T }} _ i {x} _ { i^{ \prime } }$ 衡量两个账户之间的相似度。若$x^{\mathrm{ T }} _ i {x} _ { i^{ \prime } } < \theta$，则在图$G^a$中删除边$(i,i^{\prime})$。$\theta$是一个调节$G^a$稀疏性的超参数。
既然是超参数，因此是需要学习的。
使用每个账户所属的子图的大小为其打分。
尽管该方法可以在最大的连通子图中准确检测出恶意账户，但是它不能很好地在较小的连通子图中检测出恶意账户。
能不能使用机器学习方法进行恶意账户识别呢？
与传统的先提取特征$X$，然后学习判别函数$f(X)$的方法不同，能否同时使用特征和图的结构，直接学习得到$f(X,G)$呢？
从上述构建连通子图的3步可以观察到两点：
连通子图的评分由以下两点确定：1）每个点和邻居的连通性；2）一个连通子图中的节点数目，连通性取决于$G^{ a }$（设备聚集）的结构以及节点间的向量内积（行为聚集）。子图中节点的数目反映了连通性的强度。
一个将account-device图$G$转换为account-account图$G^a$的转换函数。这一步是非常重要的，因为没有这一步，我们就不能度量不同账号之间的亲密度。但是，变成account-account图会损失很多的信息。
在下面的小节中，作者学习了一个带参数的评分函数，并且将每个节点映射到vector space中，这样可以模拟$G^a$中的连通性和。
3.3 Heterogeneous Graph Construction
假定$N$个节点包括账户和设备，每个设备都对应一个类型$d\in D。$给出在时间范围$[0,T)$的$M$条账户和设备之间的连边${\lbrace (i,j) \rbrace}$。每条边都表示账户$i$在设备$j$上有行为，例如注册、登录等。对于包含$N$个节点的图$G=(V,E)$，有邻接矩阵$A\in \lbrace 0,1 \rbrace ^{N,N}$。
图$G$中的一个连通子图展示如下，其中蓝色节点是正常账户，黄色节点是异常账户：
为了方便，作者按照设备(device)的类型，抽取出了$|D|$个子图$\lbrace G^{(d)} =(V,E^{(d)}) \rbrace$，每个子图都包含了$G$中的所有节点，但是擦去了不是该类型设备的边。这样的操作产生了$|D|$个邻接矩阵$\lbrace A^{(d)} \rbrace$。
注意，这里设备的概念比较宽泛，例如设备可以是
- IP地址
- 电话号码
- User Machine ID（UMID）
- MAC地址
- IMSI（International Mobile Subscriber Identity）
- APDID（Alipay Device ID）
- TID
这就构成了异质图。
在这些图的基础上，进一步处理每个账户的行为。假定矩阵$X\in R^{N,p+|D|}$，若$i$是账户节点则每一行$x_i$表示了节点$i$的行为。
账户$i$在时间范围$[0,T)$内的行为可以分$p$个时间小段，每一个时间小段表示账户在这段时间产生行为的次数。
对于和该账户相关联的设备，只需使用将向量的最后$|D|$维根据所属设备，编码成one-hot向量就可以了。
最终的目的：
给定邻接矩阵$A$、在$[0,T)$时间内的行为矩阵$X$，以及在$[0,T-1)$时间内$N_0$个已标注账户是否为恶意账户的标签，学习到函数$f(,X)$，正确预测在$T$时刻的恶意账户。
3.4 Models
上述章节讨论了数据中发现的模式（“设备聚集”和“行为聚集”），以及异质图的构建。并且说明了这些模式可以通过给定$A, X$的函数学习得到。但仍然需要一个强大的函数来捕获这些模式。
按照小杨的理解就是：
- adjacency matrix $A$可以用于求得一个个连通子图，而activities matrix $X$可以用于简化得到的连通子图，得到真正有嫌疑的连通子图。
我们希望通过聚合转换后的行为矩阵$X$，从而为每个节点$i$学习到有效的embedding $h_i$：
其中：
$H^{(t)}\in R^{N,k}$,表示$t$层的嵌入矩阵，每行表示一个节点的embedding。
$T$表示节点跳数，也表示隐藏层的层数。
$W, $是需要优化的参数。在给定了连通性（即Adjacency Matrix $A$）和账户的活动（即Activities Matrix $X$）情况下，这两个参数用于自动地获得更好的Device Aggregation和Activity Aggregation。
我们让$x_i$出现在每一层hidder layer中，这样可以像残差网络一样连接到深层的距离层？
随着迭代的加深(例如T步)，节点就可以在隐层聚合T-step的邻居信息，这就和连通子图中定义的打分函数（计算连通子图中的节点数）有相似之处。区别在于，我们的方法是在原始的account-device图上工作的，通过将T-step邻居的行为嵌入求和，来将节点映射到隐层空间。
最后，我们能学到一个只包含参数$W$和${V_1,…,V_{|D|}}$的函数，这些参数可以由机器学习的方法学习到。如果没有邻接矩阵A的情况下，我们的模型退化为具有“skip-connection”结构的，只依赖于特征X的深度神经网络。
损失函数定义如下：
使用EM算法优化，在e-step，基于参数$W$和${\lbrace V_d \rbrace}$使用（6）式计算embeddings；在m-step，优化（7）式中的参数并调整embeddings。
本文的方法可以看成是GCN的变形，主要区别在于：
1）本文的算法可以用于HIN；
2）聚合函数是不同的，本文的模型对不同类型的图$G^{(d)}$中的两种模式（设备聚集和行为聚集）进行的是求和操作，然后按照图类型的数目取了均值。
3.5 注意力机制
引入注意力机制，在学习过程中自适应地为不同类型的子图分配注意力：
4 实验
数据集：Alipay(支付宝)
实验任务：
对比方法：
- 连通子图：4.2中提出的方法
- GBDT+Graph：一种基于机器学习的方法，GBDT全称为Gradient Boosting Decision Tree
- GBDT+Node2Vec：基于随机游走的节点嵌入方法
- GCN：经典的图卷积网络方法，聚合公式是（1）式
实验结果：
不同方法在测试集上，第1,2,3,4周的precision-recall曲线对比如下：
5 总结
本文提出了GEM模型，用于日常在支付宝中恶意账户的发现。
总结了攻击者的两个基本特点：设备聚集、行为聚集。
是第一个使用GNN方法实现欺诈检测的方法。
未来的工作：在随时间变化的动态图上建立恶意账户检测系统。
6 存在的问题
Not reproducible.
No open dataset or open source code.
Lack details of secret weapons（e.g. User Machine ID(UMID)）.Adaptive adversary.
Fake Hardware ID by hijacking system APIs on rooted devices.
Malicious account can be more active.
