基于 NebulaGraph 图数据库的 ID Resolution 方法与代码示例
目录
本文是一个基于 NebulaGraph 上的图算法、图数据库、图神经网络的 ID-Mapping 方法综述，除了基本方法思想的介绍之外，我还给大家弄了可以跑的 Playground。
本文还在撰写中，TBD 的章节还请见谅。
1 基于图数据库的用户 ID 识别方法
用户 ID 识别，是一个很常见的图技术应用场景，在不同的语境下它可能还被叫做 Entity Correlation（实体关联）、Entity Linking（实体链接）、ID Mapping（身份映射）等等。ID 识别解决的问题是找出相同的用户在同一个系统或者不同系统中的不同账号。
由于 ID 识别天然地是一个关联关系问题，也是一个典型的图、图数据库应用场景。
1.1 建立图谱
1.1.1 图建模
我们从一个最简单、直接的图谱开始，如下边的图结构示意显示，我们定义了点：
- user
- Prop: [name, email, birthday, address, phone_num]
- phone
- device
- ip
- address
在他们之间有很自然的边：
- used_device
- Prop: time
- logged_in_from
- Prop: time
- has_phone
- has_address
- has_email
1.1.2 数据
这份数据是开源的，地址在 https://github.com/wey-gu/identity-correlation-datagen
1.1.3 写入 NebulaGraph
利用 Nebula Up，一行部署 NebulaGraph
地址：https://github.com/wey-gu/nebula-up/
1curl -fsSL nebula-up.siwei.io/install.sh | bash
图建模的 Schema 对应的 NebulaGraph DDL 是：
|
|
对于写入数据的 DML，这里只给出 user ，email 类型点、has_email 类型边的例子
|
|
1.2 根据确定规则获取 ID 映射关系
最简单、直接的方法，在特定的场景下也可能是有用的，试想像 email、IP 地址、上网设备这些有严格结构的数据，在它们成为图谱中的点的时候，简单的相等关系就足以找出这样对应关系，比如：
- 拥有相同的 email
- 使用过相同的 IP 地址
- 使用过相同的设备
在前边的图谱、图数据库中，拥有相同的 email 可以直接表达为如下的图模式（Graph Pattern）。
|
|
下图为顶点： user 与边：has_email 的一个图的可视化结果，可以看到这其中有两个三个点相连的串正是符合拥有相同 email 的模式的点。
注：
- 这个结果的数据源在 https://github.com/wey-gu/identity-correlation-datagen/tree/main/sample/hand_crafted
- 如果通过线上访问本文，你可以鼠标悬停（获取点上的属性）和框选放大每一个点和子图哦。
显然，在构建 ID Mapping 系统的过程中，我们就是通过在图数据库中直接查询，可视化渲染结果来看到等效的洞察，这个查询可以写成：
|
|
NebulaGraph 中的查询结果
同样，在上边交互图中可以放大看到这两对拥有相同 email 关联起来的账号：
然而，在更多真实世界中，这样的模式匹配往往不能解决更多稍微复杂一点的情形：
比如从上边的图中我们可以看到这两个匹配了的映射中，holly@welch.org 关联下的两个用户的姓名是不同的，而 veronica.j@yahoo.com 关联下的两个用户姓名是完全相同的。
|
|
再比如 Sharon91@gmail.com 和 Sharon91+001@gmail.com ，这两个人的姓名不同，但是手机和地址却是相同的。
|
|
比较庆幸的是我们只需要增加类似于"拥有相同邮箱"、“拥有相同地址”、“拥有相同电话"等其他条件就可以把这种情况考虑进来了，而随之而来的问题是：
- 不是所有的数据都至少存在某一个确定条件的相等（二元的是与否），所以不存在一条确定的边去连接它们，比如这两个账户中：
|
|
- 如何表现
4kelly@yahoo.com与4kelly@hotmail.com的相似性？ - 如何将多种匹配规则的信息都纳入关联系统？
1.3 非确定规则基于复合条件量化方法
前边提到了几种确定规则无法处理的情况，它们可以归结为这两点：
- 需要多因素（规则）进行综合考虑与判定
- 需要对非确定条件（属性）进行处理，挖掘隐含相等、相似的关联关系（边）
对于 1. ，很自然可以想到对多种关联条件进行量化评分（score），按照多种条件的重要程度进行加权，给出认定为关联的总分的阈值。
有了多因素评分的机制，我们只需要考虑如何在确定的多因素基础之上，增加对不确定因素的处理，从而解决 2.的情况。这里，非确定的条件可能是：
a. 表现结构化数据的相似性：Sharon91@gmail.com 与 Sharon91+001@gmail.com
b. 表现非结构化数据的相似性：
Schmidt Key Lake Charles AL 36174与Schmidt Key Lake Charles AL 13617600-192-2985x041与(600)-192-2985
对于 a. 的结构化数据中的相似性，有两个思路是可以考虑的：
- 直接进行两个值的相似度
- 直接判定子字符串
- 运算 Jaccard index 等类似的相似度
- 拆分为更细粒的多个属性
- 将 email
foo+num@bar.com拆分成三个子属性 email_handle:foo, email_alias:num, email_domain:bar.com- 然后就可以设计详细的确定性规则：email.handle 相等、甚至再在此基础上应用其他非确定规则
- 有时候，比如对于 email_domain 字段，我们还知道 gmail.com 和 googlemail.com 是等价的，这里的处理也是可以考虑的（像是
user_19,brettglenn@googlemail.com与user_8,brettglenn@gmail.com，但从邮箱判断背后就是同一个持有者)
- 将 email
而对于 b. 的非结构属性相似性距离，处理方式可以根据具体的 domain knowledge 千差万别：
- 像
Schmidt Key Lake Charles AL 36174与Schmidt Key Lake Charles AL 13617的地址信息，除了可以用值的相似度之外，还可以把它转换成地理类型的属性，比如一个经纬度组成的点，从而计算两个点之间的地理距离，根据给定的距离值来打分。
注，你知道吗？NebulaGraph 图数据库中原生支持地理类型的属性与索引，可以直接创建 Point 类型的地理属性，并计算两个 Point 之间的距离。
- 对于
600-192-2985x041与(600)-192-2985这种字符串形式的电话号码，则可以统一转化为<国家码>+<区域码>+<本地号码>+<分机号>这样的结构化数据，进一步按照结构化数据的方式处理。 - 如果账号存在图片对象 URL，可以对比其文件相似度。
另外，对于非结构属性的相似性计算我们要尽量避免两两穷举运算的方式（笛卡尔积），因为这是一个指数增长的量级，一个可行的方法是只比较建立了确定性关系（比如相同邮件前缀：email_handle，地址在相同街区，IP 在同一个网段等）的实体。
小结
总结来看，为了解决真实世界数据的复杂情形，基于复合条件的量化方法有：
-
通过细化结构数据（比如邮箱字段拆分为子属性或者点）、或者转变为结构化数据（处理字符串形式的电话号码）建立相似结构化数据之间的确定关联；
-
在有限存在确定性关联的点之间（避免两两穷举），运算其他量化、非确定相似性（字符距离、地理距离等、图片文件相似度）；
-
为不同关系赋予加权，计算相似度总分；
1.3.1 基于复合条件量化方法实操
下边，我们来给出这系列方法的实操案例。
1. 细化结构数据
通过细化结构数据（比如邮箱字段拆分为子属性或者点）、或者转变为结构化数据（处理字符串形式的电话号码）建立相似结构化数据之间的确定关联；
首先，我们把 email 的点拆成前缀 email_handle 与后缀 email_domain，自然地，会产生这样的边：
- has_email_with_handle (user -> email_handle)
- has_email_with_domain (user -> email_domain)
- with_handle (email -> email_handle)
- with_domain (email -> email_domain)
然而，可以想见 email_domain 是一个潜在的超级节点，并且，它的区分度在很多情况下是很小的，比如 gmail.com 这个公共邮箱后缀没有很大的关联性意义。我们可以只留下 email.handle 作为点，而对于 email_domain，把它留在边中作为属性：
- has_email_with_handle (user -> email_handle)
- Prop:
- email_domain
- Prop:
- with_handle (email -> email_handle)
- Prop:
- email_domain
- Prop:
对应的新的点类型、边类型的 NebulaGraph DDL 语句：
|
|
对应新的点、边的 DML 语句：
|
|
可以看到，经过这个处理，我们已经得到更多关联的用户了，它可以用这个图查询表达：
|
|
2. 非确定性相似性
在有限存在确定性关联的点之间（避免两两穷举），运算其他量化、非确定相似性（字符距离、地理距离等、图片文件相似度）；
这里用地址的地理距离来做为例子，我们预先处理每一个地址，将它们的经纬度导入图谱。
这样，我们更改地址这个点的类型 address 的 schema：
- address
- Prop: geo_point（
geography(point)经纬度类型）
- Prop: geo_point（
对应过来，它的 DDL 变化是：
|
|
在已经建立了初始的 address TAG 之上，可以用 ALTER TAG 的 DDL 去修改 address 的定义：
|
|
可以用
SHOW CREATE TAG查看修改之后的 Schema
1 2 3 4 5 6 7 8 9(root@nebula) [entity_resolution]> SHOW CREATE TAG `address` +-----------+------------------------------------+ | Tag | Create Tag | +-----------+------------------------------------+ | "address" | "CREATE TAG `address` ( | | | `address` string NOT NULL, | | | `geo_point` geography(point) NULL | | | ) ttl_duration = 0, ttl_col = """ | +-----------+------------------------------------+
对应的点、边的 DML：
|
|
有了经纬度信息，结合 NebulaGraph 原生对于 Geo Spatial 空间地理属性的处理能力，我们可以轻松获得两个点之间的距离（单位：米）
如下，ST_Distance(ST_Point(13.13, -87.65),ST_Point(13.12, -87.60)) 表示两个地球上的点 ST_Point(13.13, -87.65) 和 ST_Point(13.12, -87.60)) 之间的距离是 5559.9459840993895 米。
|
|
那么，我们可以用查询语句来表达”所有拥有相同邮箱前缀用户之间的距离“：
|
|
这里，为了展现出针对 ”非确定性“ 条件之间的 ”相似性”，我们可以把地址中字符串完全相同的结果过滤掉，WHERE a_start.address.address != a_end.address.address，如此：
|
|
它的结果是：
|
|
可以看出：
user_5与user_23之间的地址距离只相差 5559 米，因为他们的地址就在一个街区- 而
user_9与user_13之间距离相差 0 米，因为它们（“2 Klein Mission New Annetteton HI 05775” 与 “2 Klein HI 05775”）实际上是完全相同的地址。
这就是利用属性的具体含义（domain knowledge）计算的实质距离的一个最好的诠释，大家可以借助于图数据库中查询语句描述能力或者利用其他系统去运算用户间非确定性特征的量化距离/相似度。
3. 加权评分
为不同关系赋予加权，计算相似度总分；
下边是一个在实际应用中，可以综合考量的多种关联关系，包括但不限于：
确定性关系
- 同名（精确匹配）
- 相同电话（格式化处理）
- 使用过相同设备（精确匹配）
- 同邮件前缀（精细化处理）
非确定性
- 地址距离（处理成经纬度，计算地球球面距离）
- 头像图片背景相似度（训练模型计算图像距离）
一个很直觉的方法就是将多种条件按照不同的权重加权，获得两点间的总“疑似相同账号”的评分。
本例中，为求简洁，我们只给出考虑“同邮件前缀”、“同名”与“地理距离小于 10KM”的综合加权，并且认为两个因素的权重都是 1。
注，为了防止两两全匹配，我们从相同邮件前缀条件作为初始匹配条件。
|
|
结果是
|
|
然后，我们计算加权分数：
|
|
结果是
|
|
1.3.2 利用 Active Learning 的方法交互式学习评分权重
实际应用中，不同因素的加权关系也不是那么容易轻易给出的，我们可以利用有限的人力判断进行 Active Learning 的交互训练来习得权重。
TBD
1.4 利用新的边连接不同方法
进一步，对于这些确定（是否二元的）或非确定（量化的）关系，利用图库与外部系统获得了关联关系之后，常常可以直接把它们定义为图谱中直连的边，写回图库，提供给其他算法、系统作为输入，做进一步迭代、计算。
1.4.1 创建单独的直连边
假设之前对邮件、地址、姓名的处理之后，把结果作为用户实体之前的直连边插入图谱，这些种边叫做：
- shared_similar_email
- shared_similar_location
- shared_name
|
|
1.4.2 创建复合评分之后的边
比如，我们查询综合分数大于 2 的点：
|
|
然后根据返回结果建立新的边：
|
|
1.5 基于图算法的方法
前边的方法中我们直接利用了用户的各项属性、行为事件中产生的关系，并利用各种属性、值相似度的方法建立了基于概率或者带有评分的关联关系。而在通过其他方法增加了新的边之后的图上，我们也可以利用图算法的方法来映射潜在的相同用户 ID。
1.5.1 图相似性算法
利用节点相似性图算法，比如 Jaccard Index、余弦相似度等，我们可以或者 a. 利用图库之上的图计算平台全量计算相似度，或者 b. 用图查询语句实现全图/给定的点之间的相似度，最后给相似度一定的阈值来帮助建立新的（考虑了涉及边的）映射关系。
注，这里的 Jaccard index 和我们前边提到的比较两个字符串的方法本质是一样的，不过我们现在提及的是应用在图上的点之间存在相连点作为算法中的“交集”的实现。
1.5.2 社区发现算法
自然地，还可以用社区发现的算法全图找出给定的基于边之下的社区划分，调试算法，使得目标划分社区内部点为估计的相同用户。
1.5.3 基于图算法的方法
1.5.3.1 基于图查询的 Jaccard 实现
Jaccard Index 是一个描述两个集合距离的定义公式，非常简单、符合直觉，它的定义为： $$ J(A,B)= \frac {|A\cap B|}{|A\cup B|} $$ 这里，我们把交集理解为 A 与 B 共同连接的点（设备、IP、邮箱前缀、地址），而并集理解为这几种关系下与 A 或者 B 直连的所有点，于是，我们用这样的 NebulaGraph OpenCypher 查询就可以算出至少包含一跳关系的点和它相关的点、以及 Jaccard Index 值，越大代表关联度越大。
|
|
我们可以看到结果里：
|
|
user_8 与 user_19 的系数是最大的的，让我们看看他们之间的连接？
|
|
果然，他们之间的相似度很大：
1.5.3.2 基于 NebulaGraph Algorithm 图计算平台的 Jaccard 方法
1.5.3.2.1 前面方法的局限
利用图数据库查询计算 Jaccard 系数的方法有两方面局限。
首先，为了防止两两运算，我们假设了所有值得被运算的点之间已经存在某种确定链接（对应 MATCH 第一行），虽然这样的假设在大部分情况下是可以粗略被接受的，但是它是一种压缩和妥协。
其次，在数据量很大的情形里，这样的查询将不具有可操作性。
1.5.3.2.2 更 Scale 的方法
为了能处理更大规模，我们可以利用 Spark 等并行计算平台进行算法执行；
在全图运算时，我们可以利用局部敏感哈希 MinHash 来对两两比对降维，庆幸的是，Spark 中提供了 MinHash 的实现供我们使用！
参考：
- https://aksakalli.github.io/2016/03/01/jaccard-similarity-with-minhash.html
- https://en.wikipedia.org/wiki/MinHash
- https://spark.apache.org/docs/3.1.1/api/python/reference/api/pyspark.ml.feature.MinHashLSH.html
- https://github.com/apache/spark/blob/master/mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala
MinHash 的思想：
这个方法是用概率去有损估计 Jaccard 系数，这里的降维体现在它用 bit map 去数字化每一个集合，随机定义不同的集合上的 shuffle（乱序）变换，取变换之后 hash 的最小值。这里，两个集合的随机变换后最小值 相等的概率是等于 Jaccard 系数的。所以，这样偷梁换柱，就把需要两两集合运算比较的算法变成只需要对每一个集合做常数次随机变换取最小的降维近似运算了。
在图上，对于每一个点，我们认为它的邻居就是这个点的集合，那么在 Spark 中运算 Jaccard 系数的过程就是：
- 获取每一个点的邻居集合
- 对点的邻居进行 MinHash 运算，获得 Jaccard 系数
庆幸的是，开源的 NebulaGraph Algorithm 已经提供了这个算法的实现，感兴趣的同学可以访问 nebula-algorithm/src/main/scala/com/vesoft/nebula/algorithm/lib/JaccardAlgo.scala 了解它的实现，而我们只需要调用 NebulaGraph Algorithm 就可以了，使用方法参考 NebulaGraph Algorithm 文档。
注，配置中 jaccard.tol 的意涵是 approxSimilarityJoin 中的 threshold ：
1 2 3 4 5 6 7 8def approxSimilarityJoin( datasetA: Dataset[_], datasetB: Dataset[_], threshold: Double, distCol: String): Dataset[_] = { ... // Filter the joined datasets where the distance are smaller than the threshold. joinedDatasetWithDist.filter(col(distCol) < threshold)
读者到这里应该会注意到，这个方法显然是假设所有的点都是用户实体，边是他们之间的直连关系的。所以再应用这个方法之前，我们需要创建经过预处理的直连边，这个步骤正是前边章节“利用新的边连接不同方法”中的内容。
1.5.3.3 基于 NebulaGraph Algorithm 图计算平台社区发现算法
提到基于全图的算法，我们自然可以想到可以利用社区发现的手段去帮助识别相同用户的不同账号，弱联通分量（WCC）、Louvain 算法都是常见的手段。
同样，NebulaGraph Algorithm 开箱即用地提供了这两种算法，我们可以很容易在 NebulaGraph 得出社区划分，并在此基础上做复合方法的识别。
1.5.3.4 上手基于 NebulaGraph Algorithm 图计算方法
因为篇幅关系，这里不展示 NebulaGraph Algorithm 方法的上手环节，类似于在之前 Fraud Detection 方法文章中的对应章节，你可以利用 Nebula-Up 的 all-in-one 模式，一行命令搭建这样的环境并亲自体验。
- Nebula-Up 部署命令：
curl -fsSL nebula-up.siwei.io/all-in-one.sh | bash -s -- v3 spark
1.6 基于图神经网络的方法
我们注意到，在讲以上不同的方法相结合的时候，会把前导方法的结果作为图上的边，进而作为后边的方法的输入，而相同用户 ID 的识别本质上就是在图上去预测用户之间链接、边。
在 GNN 的方法中，除了我们在欺诈检测中利用到的节点分类（属性预测）之外，链接预测（Link Prediction）也是另一个常见的算法目标和应用场景。自然地，可以想到用 GNN 的方法结合 1. 非 GNN 方法获得的、 2. 已经有的人为标注的链接，来学习、预测图上的 ID 映射。
值得注意的是，GNN 的方法只能利用数字型的 feature、属性，我们没办法把非数字型的属性像在分类情况里那样枚举为数值，相反，我们在真正的 GNN 之前，可以用其他的图方法去建立基于打分、或者相似度的边建立。这时候，这些前边的方法成为了 GNN 链路预测的特征工程。
1.6.1 基于 GNN 的实操
和在 “基于 NebulaGraph 图数据库的欺诈检测方法与代码示例” 的欺诈检测类似，我将给出的例子也是 GNN 结合图数据库做实时预测的例子。
1.6.1.1 HDE[ICDM2021]
我们利用 Heterogeneous Graph Neural Network with Distance Encoding 给出的方法来做 Inductive Learning 的异构 GNN 上的链路预测，同时，我们将用一个更方便的 GNN 工具，OpenHGNN，有了它，本例中的代码量也会大大下降。
注：OpenHGNN 是由北邮 GAMMA Lab 开发的基于 PyTorch 和 DGL 的开源异质图神经网络工具包。
1.6.1.2 数据集
本利的数据集是前边方法中建立在 NebulaGraph 中的图谱，借助于 Nebula-DGL，我们可以一行代码把 NebulaGraph 中的图加载到 DGL 之中。
注：
这里，我们使用的的工具为 Deep Graph library（DGL），NebulaGraph 图数据库和他们之间的桥梁，Nebula-DGL。
DGL: https://www.dgl.ai/
Nebula-DGL: https://github.com/wey-gu/nebula-dgl
你可以直接 load 这个 .ngql 文件到 NebulaGraph。
1.6.1.3 数据处理
为了将 NebulaGraph 图谱进行工程处理，序列化成为 DGL 的图对象，我们要通过 Nebula-DGL 的 YAML 配置文件 API 描述所需的点、边类型以及关心的属性（特征）。
我们看下现在的图中有哪些点、边类型：
|
|
在本例中，我们不考虑属性(特征)。
nebulagraph_entity_resolution_dgl_mapper.yaml
|
|
然后，我们在安装好 Nebula-DGL 之后只需要这几行代码就可以将 NebulaGraph 中的这张图构造为 DGL 的 DGLHeteroGraph 图对象：
|
|
1.6.1.4 模型训练
参考 custom_link_prediction_dataset.py
HDE_link_predict.py
|
|
TBD：尚需把 g 处理成为 MyLPDataset() 可以接受的数据。
1.6.1.5 保存模型
OpenHGNN 中保存自定义数据集的模型的支持，有些问题，参考 https://github.com/BUPT-GAMMA/OpenHGNN/issues/112
1.6.1.6 应用落地
参考：https://github.com/wey-gu/NebulaGraph-Fraud-Detection-GNN
Feature image credit by Cosmin Serbin
