图智能分析利器-Graph Embedding与动态图异常检测

一.图数据库应用背景

金融机构每年因欺诈带来的坏账损失每年高达数百万美元。随着在线数据量的增长，骗子的行骗能力也水涨船高，精心设计的骗局、身份窃取、欺诈手段及一些新型的诈骗手段层出不穷，方法复杂且容易广泛复制，当事后发现时，已经太迟了，客户和企业往往已经损失惨重。

使用关系数据库来进行欺诈侦测不是不可行，但表形式并不适合描述数据之间的某些特定的复杂关系，而且在海量数据的情况下，表之间的JOIN操作会带来大量系统性能的损耗，单次运算时间甚至以小时计，导致反欺诈策略无法实时返回结果。与关系数据库相反，图数据库是基于现实世界的描述，非常易于理解，也非常容易能形成信息之间的链接，可以轻松遍历整个图来对欺诈活动进行实时侦测。图数据库以图论为基础，数据本身以图的方式存储(比如邻接表)，在处理与图相关的任务时占有先天的优势。

图模型所提供的关联分析能力是金融反欺诈、威胁情报、黑产打击和案件溯源等业务所需要的核心能力。图模型的需求非常多，例如金融安全业务希望使用图数据库进行金融反欺诈关联分析、威胁情报业务希望通过图数据库进行黑产研究和情报分析、还有社交关系分析、知识图谱等需求场景。

本文首先介绍动态图异常检测的相关内容；然后简单介绍动态图嵌入(Dynamic Graph Embedding)技术及当前研究进展；最后介绍如何利用图嵌入技术实现动态图异常检测。

二.动态图异常检测

当前图模式在各个领域得到了广泛的应用，阿里的GDB云图数据库，百度的HugeGraph图数据已经在安全领域进行推广应用，还有360投资的JanusGraph。国内各大厂商也纷纷开发自己的图数据库以满足应用的需求。异常检测是安全领域的一个基础问题，很多应用及检测方法都是基于异常检测，而安全知识图谱的应用必然使得图数据的异常检测成为上层业务支撑的基础。

动态图模型异常检测指给定连续的静态图序列，寻找特定的时间节点对应于图上显著的变化或事件发生，同时找出影响最大的相关的节点、边或子结构。图模式的应用与图数据规模的激增使得动态图分析技术成了当前研究的热点

DPADS[1]算法把静态图的异常检测算法GBAD和并行异常检测(Parallel Anomaly Detection, PLAD)算法扩展到大规模动态图的异常检测中，如图 1所示，Ti-1、Ti、Ti+1为时间滑动窗口。本文定义3种基本类型图的异常：添加、修改和移除。添加异常是正常模式增加了顶点或边。修改异常包含了一个顶点或边的意外标签。移除异常的子结构比正常子结构缺少了边或顶点。

图1 DPADS算法处理图异常检测

DPADS算法检测图的异常基于这样的思想：异常的子结构(或子图)是正常模式的结构变种(正常模式边和节点的增加或者缺失)。假设d(G1, G2)表示2个图G1和G2之间的结构差异度量，计算把图G1转化为G2的同构图的计算量(添加、删除点与改变标签的变化数量)，衡量G1和G2之间的差异。

虽然针对动态图异常检测方法已经有了一些研究，但是这些图分析方法一直停留在“规则引擎”、“图计算”的浅层层面，智能图数据分析方法-图嵌入进一步打开了图模式智能分析的篇章。

三.动态图嵌入

1什么是Graph Embedding

传统的机器学习大多处理的是以特征向量所表示的结构化样本，而图(Graph)是非结构化的数据。所以，要想用丰富的机器学习模型来挖掘图中的信息，第一步就是将图数据嵌入到向量空间中。

图2 将图（Graph）在各种尺度上嵌入到二维中

如图2所示，图在不同尺度上被嵌入到低维向量空间(此处为2维)，从而化为结构化的数据，并尽可能的保留了原有的信息。静态图嵌入算法就是在这种不变的拓扑结构上将图映射到低维空间。

2动态图的表示

2.1 为什么要研究动态图模型的嵌入？

图嵌入算法是一种通过学习图中节点（和连边）的低维稠密特征表达，从而将整个图模型映射到低维向量空间中的方法。该方法极大的降低了储存超大型图结构对存储空间的需求，简化了图模型之间的计算方式。图嵌入算法在近年来获得了学术界和工业界的广泛关注与兴趣。在实际生活中，我们常见的图结构，例如社交网络，生物网络等，都是会随着时间的推移而发生演进的动态图结构。但是当前几乎所有的图嵌入算法研究都只集中在静态图结构。

在图发生演进变化后，如果是重新对整个图利用静态图模型嵌入算法计算各个节点的嵌入向量，会耗费极大的计算代价。同时当演进变化只占整个图极小的一部分时，重复采用静态图嵌入算法会显得效率降低。本文中我们重点学习最近关于动态图模型及对应图嵌入算法的几篇相关论文。

文献[2]设计了一种增量式的图嵌入方法，作者称之为ICMEN，即Incremental Convex Meta Embedding for Nodes。该算法分别为每个时刻的图生成节点的向量表示，并采用线性求和的方式生成新时刻的节点嵌入向量。算法主要思想如下：

图3 ICMEN算法示意图

Goyal在18年初发表了DynGEM模型[3]，该模型基础是SDNE嵌入算法，同时也是将动态图表示成Snapshots。DynGEM的想法也非常简单：为了保留上一时刻的嵌入信息，并为下一时刻所用，可以让下一时刻的嵌入模型直接继承上一时刻训练好的模型参数，如下图：

图4 时刻的模型参数用于初始化 t 时刻的模型参数

还有一点需要注意，图的节点数目和连边多少对嵌入模型的架构有影响。所以文中利用启发式信息来根据新图结构调整SDNE的整体架构，使其能适用于新图。

Goyal在18年下半年又发表了一篇动态图嵌入的工作[8]DynGraph2vec( 动态图几乎被Goyal大神给霸占了，发现算法取名是亮点 )

这篇新工说明了DynGEM框架和其他动态嵌入算法只考虑前一步的信息，而忽略了更加丰富的历史信息。基于此，本文在对t+l时刻图做嵌入时，会输入t,t+1,t+2,......,t+l-1时刻和 t+l 时刻的图结构信息。文中给出了3个模型来嵌入这些丰富的历史信息：

图5 DynGraph2vec中的三个嵌入模型

简单来说，本文是将时序的图序列当做一段语料(将某时刻的图结构类比于句中的单词)，然后用RNN来编码历史信息。整体的嵌入框架仍旧是enc-dec的自编码器。虽然想法是好，期望将尽可能多的历史信息用来嵌入当前时刻的图，但是上述模型的算法复杂度比较大，不适合大图的嵌入。

2.2 动态图嵌入算法对比思考与PyTorchBigGraph神器

前一小节介绍了最新的关于动态图嵌入的内容，第一篇是利用旧的顶点嵌入表示来更新新顶点的表示，而后两种是只对动态更新的部分计算表示向量。第一篇文章第次只对更新的那一部分图结构进行计算，而占顶点表示向量是无法修改的。而后两篇是考虑了新更新的数据对整体图嵌入表示的影响，是一种真正的增量更新，但是话费的时间要高于第一篇论文的方法。

虽然学术界提出了各种眼花缭乱的动态图嵌入方法，但是图嵌入技术的落地应用是最近实现的，如阿里的基于Graph Embedding 的拼单，那么是什么制约Graph Embedding的使用呢？主要两个方面：一对大规模图数据Embedding效率很低，二很难应对图数据的动态更新。然而PyTorchBigGraph-图嵌入神器[]给了我们希望，号称无需GPU轻松搞定10亿数据。简单介绍下PyTorchBigGraph:

PyTorchBigGraph

PyTorchBigGraph简称PBG，它是一个分布式系统，在进行训练时，会一次装入所有的边。并给每一个节点，输出一个特征向量 (就是嵌入)，让两个相邻的节点在向量空间中离得近一些，让不相邻节点的离远一些。

为了提高实时性PBG采用了以下几个技术：

1.图分区(Graph Partitioning) ，这样就不需要把整个模型加载到内存里了。在图嵌入质量不损失的情况下，比不分区时节省了88%的内存占用。

2.一台机器进行多线程计算。

3.在多台机器上同时跑，在图上各自跑一个不相邻的区域。

4.批次负采样(Batched Negative Sampling) ，能让一台CPU每秒处理100万条边，每条边100次负采样。

四.图嵌入与动态图异常检测的碰撞

——NetWalk[6]

NetWalk是首次将图嵌入技术应用到动态图异常检测中，该方法首先提出了提出一种基于图嵌入的动态图异常检测框架NetWalk，提出一种新的Clique Embedding方法来编码动态图中的顶点，

图6 NetWalk异常检测流程

摘要受跳跃图结构[6]的启发，提出了一种基于深度自编码神经图的图嵌入算法Clique嵌入，该算法通过图步长流学习顶点的矢量表示，同时最小化每步中所有顶点之间的成对距离。图7描述了NetWalk中使用的Clique嵌入模型。

图7 NetWalk中使用的Clique Embedding

NetWalk的顶点的向量表示方法，可以很好的基于聚类进行顶点异常检测。同时NetWalk为了应对边异常，构建一个查询表，根据学习的图表示对新的边进行实时编码，该文的边的编码方法使用了文献[7]中的技术。

为了应对动态图的快速演化特性，NetWalk提出了有新和图嵌入表示更新方法，不需要显式地维护图结构的完整细节。每个添加/删除的边缘都会影响许多图遍历，这些遍历将用于更新当前图表示。在NetWalk中，设计了一种基于“容器”（Reservoir）的算法来维护一个紧凑的记录，该记录由每个顶点的一组“邻居”组成，并根据每个顶点的“容器”（Reservoir）更新步数。最终通过一个相似度计量来计算顶点、边或子图的异常得分。

参考链接：

[1].韩涛, 兰雨晴, 肖利民, 等. 一种增量并行式动态图异常检测算法. 北京航空航天大学学报, 2018, 44(1): 117-124.2

[2].Kajdanowicz T , Tagowski K , Falkiewicz M , et al. Incremental embedding for temporal networks[J]. 2019.

[3].Goyal P, Kamra N, He X, et al. DynGEM: Deep Embedding Method for Dynamic Graphs[J]. 2018.

[4].Goyal P, Chhetri S R, Canedo A. dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning[J]. 2018.

[5].Lerer, Adam, Wu, Ledell, Shen, Jiajun, et al. PyTorch-BigGraph: A Large-scale Graph Embedding System[J]. 2019.

[6].Yu W, Cheng W, Aggarwal C C, et al. NetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2018: 2672-2681.

[7].Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. (2016).

内容编辑：天枢实验室 薛见新 责任编辑：肖晴