发布时间:2023-01-04 08:30
本文约3400字,建议阅读5分钟
本文提出了用于建模工业级规模异构图的异构图转换架构(HGT),针对三方面问题进行解决。
图神经网络是2017年兴起的研究方向,主要作用是利用节点aggregate的方式将每个节点的其他的邻居的信息聚合到自己的节点。通过神经网络自动表征学习能力,来自动选取出最适合的节点表征以及边表征,从而处理一些下游任务。
在处理图的异构性方面,使用节点和边特定类型的参数依赖,构建交互异构注意力,可以自动提取用于处理特定下游任务的元路径;在处理图的动态性方面,引入相对时间编码机制;在处理大规模的图数据方面,设计了mini-batch图采样算法——HGSampling。同时,还介绍了基于生成式任务的异构图图神经网络的预训练方式。
代码链接:
https://github.com/acbull/pyHGT
主要内容
01 异构图的应用场景
异构图是一种关系型图数据,它和普通图最大的不同之处在于异构图还包含点的类别、边表示的不同关系、节点的特征等,能表征更丰富的语义。
异构图有丰富的应用场景。在论文的表征中,节点类型有“论文”“作者”,边的类型有“写”“引用”。以及节点的类型——譬如“论文的所属会议”“作者所属的学校、机构”以及“论文从属的领域”。用异构图来处理这一类学术图谱数据,对于像Google Search或者Microsoft academic的学术论文的推荐,都有非常重要的作用。
同时,异构图在工业级的图数据里面应用也非常广泛——譬如推荐系统。微软office的推荐系统,会将所有的“邮件”“文件”“任务”“笔记”“消息”等,整理成同一个图;在典型的电商推荐系统里面,节点类型有用户和商品。 当然,如果考虑更细粒度的用户行为,还有“查询”“属性”“地点”等等。连接这些节点的边,也包含各种不同的语义信息——购买行为、偏好、浏览历史等。
总而言之,我们需要更优的异构图算法,去表征如上的语义信息。
02 传统处理异构图数据的方法——Meta paths
一个很自然而然的想法——对边抽取基本模式水平(schema level)的信息。举个简单的例子,如果我们在描述两个节点连接的一条边时,不仅知道了这两个节点是相连的,还知道这两个节点的类别信息,就可以定义一个元关系(meta relation)三元组:从起始节点的类型,到边的类型,再到目标节点的类型。运用这个我们就可以将任意的异构图抽取出不同的schema。
基于上述所言,我们就可以定义一个元路径(meta path)——由一系列元关系(meta relation)组成的序列。在学术网络当中,可利用不同类型的meta path寻找和某一学者研究性质最相似的其他学者。例如,通过A-P-A,我们就能找到和他合作最多的学者;通过A-P-V-P-A,我们就能找到发表同一个类型文章数量最多的学者。其实,利用元路径的传统能力,就已经可以对异构图数据做一些下游任务了;但是,不同元路径(meta path)的选择对下游任务的准确率影响很大。
因此,我们想要设计一种新的异构图图神经网络,结合元路径的表征能力以及图神经网络的自动特征抽取能力,来实现自动选取最适合的元路径(meta path)来处理某一个下游任务,通过学习得到对于某一个任务的图表征以及推理模型。
03 为异构图设计的图神经网络
我们将现有的一些基本框架总结成为了如下的注意力机制图神经网络框架,含有三大模块——Attention、Message、Aggregation。Attention,给定起始节点和目标节点,计算这两个节点间的相关性;aggregation,也就是将邻居节点信息进行聚合,最简单的方式是计算出attention后的加权平均;message,每一个起始节点本身包含的节点信息。
但现有的模型大多针对同质图,没有考虑节点和边的类型信息。
因此,在设计算法时有三大挑战:
(1)建模不同的节点和边的类型
(2)囊括动态图的信息变化,
(3)考虑工业级异构图规模大的特点。
(一)异构交互注意力和消息传递
使用元关系来参数化权值矩阵,以计算每条边上的注意力系数。我们将之前提到的元关系(meta relation)引入到图神经网络中,利用元关系机制的参数化计算两个节点之间的注意力。
下面举一个简单的例子进行解释:
为了方便讨论,我们将题设进行简化。假设一个图只有两种节点类型,author和paper,现在要获得上方paper t的节点表征。我们并不会把S1和S2当做同类型的节点去处理,而是需要考虑节点的类型、边的类型。因此,S1和S2传递到t的这个权重可以拆分成由节点和边的类型决定的权重。通过这样的方式,我们就可以将异构图中的结构信息引入到传递的权值当中。
我们将这种思想引入到了现在表现非常好的的框架当中进行消息传递。
还是以paper和author两种节点的异构图模型为例。对目标节点paper t,首先计算它的查询值query;并且对每个不同的源节点,我们也会根据节点类型计算key;然后根据key和query计算注意力,并在计算过程中考虑边的类型。基于此可以得到更细粒度的节点之间的关系建模,因此将其引入到了图神经网络的消息传递过程中。
下图是整体框架,可以注意到整个这个框架还是会引入更多计算量。接下来,我们会针对如何让一个复杂的模型处理动态、大规模数据进行说明。
(二)处理动态图:相对时间编码
传统的处理动态图的方法,是将整个图根据不同的时间片做切片。例如,学术网络中,我们针对每个年份建立不同的图,之后利用诸如RNN的时序模型,进行时间建模。
但是,这种传统方法计算开销很大,不适用于工业级大规模的图。因此我们选择了更加高效的方式,可以在一个图里维护不同时间发生的所有边。我们在每一个包含的时间的节点上面增加一个时间戳,由此可以计算源节点和目标节点之间的时间间隔。同时,下图也简单介绍了如何处理和多个时间戳有关的节点。
(三)对大规模的异构图进行采样
接下来,我们会简单介绍如何针对大规模的图做采样,从而处理海量的数据。
传统的方法,通常是在一张在包含所有节点的图当中,做一次前馈计算,得到所有节点的表征信息。但是这种方法对于大规模的图数据是不现实的。
因此,我们需要去做采样。而在异构图数据当中,不同类型的节点分布差别很大。因此在我们提出了针对异构图数据的相应的采样的方式。
基本的思想就是,在计算每个节点采样的重要性时,我们考量了节点类型,针对不同的节点类型设定不同的budget;然后根据sampling budget,去计算和待采样节点相连的不同类型的节点,分别会有多少相对度和已经采样的图相连。将这些度平均起来以后,就可以得到在每一种budget下面的所有的节点的采样重要性,然后基于重要性进行采样。
这里略过一些细节,大家如果感兴趣的话可以自行查看。
(四)实验
本文主要的实验测试在微软的Open Academic Graph上,是在现有公开的数据集中数量级较大的。在论文发表时,本文的HGT模型,相较于之前的方法(包括普通的GNN和一些异构图的GNN),处理下游任务时,会有9%到21%的提升;同时HGT工作也被部署在微软内部官网以及office等的应用场景里,相较于之前方法取得了很大的提升。
最后简单介绍一下,HGT如何捕捉图的动态变化。例如,关注学术界的人肯定知道,不同的会议,随着时间发展,研究的主题也会发生非常大的变化。基于之前介绍的相对时间编码技术,可以挖掘出不同时间下,和某个会议最相似的其他会议。利用这种简单的处理方式,就可以捕捉到研究方向的变化。
在最开始介绍的时候,我们提到HGT可以自动抽取最相关的元路径,实现方式就是刚刚提到的计算的不同路径的注意力。
下图给了一个具体的例子。总而言之,即使在设计模型后,不给定事先的假设,模型也能够自动抽取出针对特定下游任务的元路径。
04 针对异构图的自监督预训练图神经网络
甚至对于一些很重要的下游任务来说,相关高质量的标注是没有办法获得的。但是,无标注的数据大量存在。我们可以在无标注的大规模数据上进行预训练之后,得到一个模型,然后将它迁移到下游任务当中,此时即使只有少量的高质量标注数据,也能取得较好的训练效果。
现在无监督预训练在NLP和CV领域都有非常杰出的突破——这在当时便启发我们思考,能否对异构图图神经网络也进行无监督预训练学习?
基本思想是利用generation task做预训练。我们将generation task分解为节点属性生成,和边的生成。由于二者具有关联性,不能看作独立的两项单独生成,因此采用耦合的生成方式。首先假设针对一个新节点,我们已经观测出了部分它和现有的节点相连的一些边,称之为observed edge。先利用observed edge预测新节点的属性;再基于observed edge和预测的节点属性,生成余下的边。
同时,引入高效的并行训练。
将预训练模型的结果在两大异构图数据集上进行测试:Microsoft Open Academic Graph和Amazon Review Recommendation。测试结果如下。
编辑:王菁