微信支付自研GNN链接预测技术与潜在应用

本文PPT,在微信公众号「DataFunSummit」,回复「20220409」领取


导读:本文主题是图链接预测技术及其潜在应用。主要包括以下三大部分:

  • 链接预测简述
  • 自研GNN链接预测技术
  • 风控场景的应用展望

01

链接预测简述

1. 图链接预测问题

图链接预测问题,可以简单地描述为:给定一个图,预测潜在的未观测到的关系,或者未来可能出现的关系。

在图机器学习中,目前比较受关注的任务是节点分类问题和图级别的分类问题。比如,在风控场景下,给定一个子图去判断这个子图是不是一个异常团伙,或者在图中去找到一些异常的节点。链接预测是介于节点粒度和(子)图粒度之间的任务,受到的关注度相对较低。

图链接预测问题大概可以分为以下几类:

  • 按照图的动静态性,可以分为静态图和动态图。

如果是动态图的链接预测,往往要考虑到图在历史演化过程中的序列,一般会将时序信息和图信息结合起来建模。

  • 按照节点类型,可以分为单节点类型和多节点类型。

常见的多类型节点的例子:user-item二部图的链接预测,也就是经典的给user推荐item的任务。

  • 按照边关系类型,可以分为单关系类型和多关系类型。

比较典型的多关系类型图就是知识图谱。知识图谱中关系补齐任务,就是一个多关系的链接预测问题。

2. 图链接预测技术价值

图链接预测技术可以应用在多个领域中,例如下面三个例子

  • 在生物化学领域中的蛋白质交互检测的应用

根据生物化学研究中已知的蛋白质交互关系,可以构造如上图所示的蛋白质关系图,利用图链接预测技术来预测尚未被发现的潜在关系(边),为蛋白质交互检测做了召回工作,缩小了范围,节省了人力。

  • 在社交网络领域中的好友推荐的应用

比如在Facebook中的好友suggestions功能,会列出可能认识的人。这种好友推荐,就是基于当前社交关系的链接预测。

  • 在风控领域中的异常关系检测的应用(后文会有介绍)

3. 图链接预测技术调研

(1)启发式

  • 核心思想:通过各种统计信息(比如共同好友数)计算两个节点间的结构相似度。
  • 优点:简单。
  • 缺点:泛化能力弱,在不同类型的图中表现不稳定。

(2)浅层Embedding

  • 核心思想:通过graph embedding算法,如DeepWalk、LINE、Node2Vec等,得到两个节点的结构信息的向量表示,然后通过两个向量的相似度来判断两个节点的连边概率(分数)。
  • 优点:相比于启发式,对结构信息的捕捉更有效。
  • 缺点:大部分浅层的embedding学习无法结合节点自身的属性。

比如,在好友推荐中,两个用户可能无共同好友,但是他们来自同一个学校,这种情况下,他们成为好友的概率可能要高于其他无共同好友的用户。如果仅考虑社交关系,而不考虑学校这一节点属性,就无法做出有效的区分了。

(3)GNN

  • 核心思想:通过GNN对两个目标节点进行结构编码,然后基于编码信息对两个节点的连边概率进行预测。
  • 优点:强大的编码能力,能够融合节点属性。
  • 缺点:大部分GNN模型没有考虑链接预测任务独有的性质。

下面,针对通用GNN的缺点,重点介绍下我们对GNN在链接预测任务上的一些改进。

--

02

自研GNN链接预测技术

我们的研究工作整体框架如下图:

首先,给定如上的示意图,正样本就是我们观测到的有连边的节点对(比如图中的A和B),负样本是采样到的没有连边的节点对(比如图中的C和E)。

得到正负样本后,通过图神经网络的编码器,得到样本节点或者节点对的表示。这里,我们把图神经网络的编码器分为了两类。一类是通用的图神经网络,即节点级别的邻域编码器(比如GCN、Graph SAGE、GAT),这类编码器可以得到一个样本中两个节点各自的表示。另一类是面向链接预测的图神经网络,即节点对级别的邻域编码器。这类编码器通常会对整个节点对的邻域子图进行编码,考虑到了邻域之间的交互信息,相比于通用的GNN的方式,节点对表示更加面向链接预测问题。

在得到节点或节点对的表示后,可以通过链接打分函数计算两个节点连边的概率或分数,常用的链接打分函数有MLP、两个节点表示向量的內积等。

得到分数后,我们采用Pairwise Ranking的目标函数去对整个模型的参数进行学习。之前的方法更多是把该问题转化为分类问题,选择交叉熵作为目标函数。而我们考虑到了链接预测任务中正负样本数量的极度不均衡性,把Pairwise Ranking的目标函数引入进来,得到了比较明显的提升。在上述框架的各个模块中,我们都有一些自研的工作,下面进行一一的讲解。

1. 自研编码器

  • 邻域注意力神经网络

经典的基于邻域信息的启发式算法:

经典的基于邻域信息的启发式算法通过邻域的统计信息,如共同邻居数、Jaccard系数,去衡量两个节点的相似度。我们发现这些经典的算法在公开的基准数据集上的表现还是能达到不错的效果的,但是在不同的数据集上的波动比较大的。

这里给我们的一个启示(研究动机)就是:

① 启发式算法证明了邻域信息的重要性,但泛化能力弱。

② 通过GNN可以有效地编码邻域特征,但现有通用的GNN并未考虑链接预测任务的特性。

③ 设计面向链接预测任务的GNN,学习泛化能力更强的隐式邻域特征。

下面介绍下我们设计的一系列的邻域注意力神经网络,首先介绍的是基模型——自邻域注意力网络。

  • 自邻域注意力网络(基模型)

Zhitao Wang, et al., "Neighborhood Attention Networks With Adversarial Learning for Link Prediction" [TNNLS]

对于待预测的节点 i 和 j,先采样其各自邻居,利用类似GAT的方式去得到其各自邻域信息的embedding表示。这里选择类似GAT的多头注意力机制,是期望不同的子空间捕捉不同类型的启发式信息。随后,通过两个节点embedding的bilinear的乘积得到样本连边的预测分数。基模型中,通过注意力机制分别编码两个待预测节点各自的邻域信息,然后基于双方自身的邻域信息对连边打分。

这个模型中,完全依赖两个目标节点的邻域表示去捕捉所有的结构交互信息,粒度较粗。因此,我们提出了交叉邻域注意力网络,用以显示的捕捉目标节点和对方邻居的交互信息。

  • 交叉邻域注意力网络

Zhitao Wang, et al., "Neighborhood Attention Networks With Adversarial Learning for Link Prediction" [TNNLS]

这个模型不仅仅去学习节点和自身邻居的注意力,还学习和对方邻居的注意力。不仅能得到各自邻域之间的表示,还有这个节点基于对方邻域的表示和。同样的,将这些得到的表示进行交叉乘积对样本进行打分。相比于基模型,该模型编码了更多的链接预测的线索,即目标节点与对方邻域的交互信息。

然而交叉注意力网络仍然是将两个目标节点分开编码,即只考虑邻域信息和单一一个目标节点的交互,没有考虑到邻域信息对两个目标节点的作为一个整体时的影响。下面我们进一步对这个模型进行改造。

  • HalpNet

Zhitao Wang, et al., "Hierarchical Attention Link Prediction Neural Network" [KBS]

我们先得到这两个目标节点的表示()。通过的 element wise 的乘积得到这个节点对整体的交互表示。再通过注意力机制,聚合A和B所有的邻居信息,得到最终的一个表可以被看做是A和B自身以及其所有邻居构成的一个子图的表示。基于,我们可以通过一个MLP得到最终的分数。这个模型的思想是通过注意力机制去捕捉A和B的所有邻居节点对A和B的交互的贡献度。然而,这个模型没有考虑邻居和邻居之间的交互信息。例如,上图中,C和E之间的交互或者C和D之间的交互,这种邻居之间的交互也会提供额外的结构相似度信息。

邻居之间是否是连边的,也是很有用的信息。于是我们提出了邻域交互注意力网络捕捉邻居和邻居之间的交互信息。

  • 邻域交互注意力网络

Zhitao Wang, et al., "Neighborhood Interaction Attention Network for Link Prediction" [CIKM'19]

首先,通过GAT可以得到目标节点对邻域子图中每个节点的表示,然后通过向量的element-wise,得到所有邻居的两两之间的交互(包括两个目标节点的交互)表示。通过自注意力机制去计算这些两两的交互信息中,哪些是重要的,哪些是不重要的,最终聚合得到整个邻域子图的表示c,随后再利用MLP进行连边打分。

2. 负采样

负采样大致分为两种:全局随机负采样和局部随机负采样。对于上图中(A, B)这样一个正例,全局随机负采样就是从所有未连边的pair对中随机去采样,得到C和E这样的全局的负例;局部随机负采样则是以正例中的某个节点为锚点去采样一个负例节点,比如这个例子中,我们以A节点为锚点去采样和A没有连边的节点E,得到A和E这样的局部的负例。

两种随机负采样策略有不同的适用场景:

全局负采样:这种策略适合寻求全局排序最优的问题。例如,对于蛋白质交互预测问题,需要在所有可能的蛋白质对中,找到交互可能性最大的那部分蛋白质对。

局部负采样:这种策略适用于对单一节点的局部排序最优。例如,在推荐场景中user-item二部图链接预测中,我们只需要对每一个用户,得到其各自偏好的item排序。

①自研负采样算法:对抗学习

动机:传统负采样方式由于完全的随机性,会造成学习过程不稳定(比如知识图谱嵌入,图片检索任务有类似问题)。已经学习到的负样例被反复采样,模型会陷入次优点。

思路:

  • 引入一个负例生成器(G),不断的在所有负例中挑选“难”的负样本。
  • 负例生成器(G)与链接预测器(D)形成对抗学习。

为了缩小G的搜索空间,G是一个局部采样的负例生成器。

②对抗学习负采样效果

从上图看,不管是从预测准确度,还是波动的稳定性来看,对抗学习负采样是更好的。

3. 目标函数

  • Pairwise Ranking

由于现实世界中绝大多数的图数据都是稀疏的,导致(单边关系类型的)链接预测问题通常是一个极度不均衡的二分类问题。同时,绝大多数链接预测任务的目标不是给所有的节点对预测标签,而是推断出最有可能出现边关系的一批节点对,即希望正样本(有边关系的节点对)的排序要高于负样本(不会出现边关系的节点对)。可以通过最大化AUC(Area Under ROC Curve)近似地逼近这一目标。

由于非凸性和非连续性,直接优化上式AUC是困难的。近年来,学界提出一系列替代损失函数(surrogate loss function)以达到近似优化AUC的目的。在这个工作中,我们选择了平方损失作为基础的替代函数,其被证明在理论上与AUC具有贝叶斯一致性:

上式有一个强约束,即要求正样本打分要大于负样本打分,且打分差强制等于1。我们可以放宽这个约束,只要求正样本与负样本的打分差大于等于间隔值1,可引入平方铰链损失来实现这个宽松后的约束:

上述两个目标函数适用于无权图,即正样本无权重区分。而对于有权图,即正样本权重不一,我们可以在目标函数中将权重考虑进来。例如,我们可以根据正样本的权重自适应的调整打分间隔,或是再整个损失值上乘以样本权重。在我们的实验中发现,把这两种方式结合起来,模型收敛会更稳定。具体的目标函数如下:

  • Pairwise Ranking效果

在公开学术研究的数据集上做了验证,如下图所示:

整体效果ranking loss都是优于classification loss。

在参与OGB Link Property Prediction测评的时也做了实验,结果如下图所示:

PLNLP是采用了Pairwise Ranking的目标函数。在四个OGB的数据集上,PLNLP的Pairwise Ranking目标函数都是优于Classification目标函数。

4. OGB参赛情况

①技术细节

基于上述研究工作,我们参与了OGB Link Property Prediction的测评,下面分享一些细节。我们在四个OGB的数据集上做了测评,具体的参数设置如下:

Table 1: Settings of PLNLP on OGB Datasets

同时,分享一下我们当时参与时用到的两个实用的trick:

负例共享机制:

  • 随机打乱已采样的负样本编号,与正样本再构建m个新的训练样本对,重复n-1。
  • 提升效率:一次采样m个负例,可以构建m*n个训练正负样本对。

基于随机游走的数据增强:

高阶相似性在某些数据集上很重要,增加GNN层数捕捉高阶信息成本过高,利用随机游走,采样高阶相似pair对,高阶pair加入正样本中,数据增强。

②OGB参赛成果

最终的成果就是,我们在三个数据集上做了提交,当时在两个任务上排名第一,在第三个任务上排名第三,成绩如下所示。

Leaderboard for ogbl-collab

The Hits@50 score on the test and validation sets. The higher, the better.

Package: >=1.2.1

Leaderboard for ogbl-ddi

The Hits@20 score on the test and validation sets. The higher, the better.

Package: >=1.2.1

Leaderboard for ogbl-citation2

The MRR score on the test and validation sets. The higher, the better.

Package: >=1.2.4

③论文及代码

论文:Zhitao Wang, et al., "Pairwise Learning for Neural Link Prediction" [arxiv]

代码:https://github.com/zhitao-wang/PLNLP

--

03

风控场景的应用展望

最后一部分,讲讲图链接预测技术在风控场景上一些潜在应用。

1. 基于链接预测的自监督学习

第一种应用方式就是基于图链接预测的自监督学习,提取有用的关系信息特征。自监督学习是目前流行的预训练方式,而链接预测本身就是一个自监督任务,即不会用到除图结构之外的额外标签信息。我们通过链接预测任务去训练模型的参数之后,可以把模型中的图神经网络编码器拿出来,再通过编码器去生成别的图或者训练图中的节点的embedding,再应用到下游的风控任务中。

2. 端到端的关系判别

第二种应用方式则是端到端的关系判别,在风控场景中,关系判别可以大致分为两类,一种是关系判白,另一种是关系判黑:

  • 关系判白

输入的图可以是可信关系,基于已有的可信关系进行训练,从而预测未来可能会出现的或当前未采集到的可信关系对。

  • 关系判黑

在关系判黑的场景中,输入的正样本则是异常关系对,图关系则需要根据业务的不同去找到合适的关联信息。输出则是目标节点对的异常打分。


今天的分享就到这里,谢谢大家。

阅读更多技术干货文章、下载讲师PPT,请关注微信公众号“DataFunSummit”


分享嘉宾:王志涛博士 腾讯 高级研究员

编辑整理:王龙飞 360

出品平台:DataFunTalk


01/分享嘉宾


02/报名看直播 免费领PPT


03/关于我们

DataFun:专注于大数据、人工智能技术应用的分享与交流。发起于2017年,在北京、上海、深圳、杭州等城市举办超过100+线下和100+线上沙龙、论坛及峰会,已邀请超过2000位专家和学者参与分享。其公众号 DataFunTalk 累计生产原创文章700+,百万+阅读,14万+精准粉丝。


欢迎转载分享,转载请私信留言。

链接   技术   GNN
发表评论
留言与评论(共有 0 条评论) “”
   
验证码:

相关文章

推荐文章