简单高效的异构图神经网络
摘要
异构图神经网络(HGNN)具有将异构图的丰富结构和语义信息嵌入到节点表示中的强大能力。 现有的 HGNN 继承了针对同质图设计的图神经网络(GNN)的许多机制,特别是注意力机制和多层结构。 这些机制带来了过度的复杂性,但很少有人研究它们在异构图上是否真正有效。 在本文中,我们对这些机制进行了深入细致的研究,并提出了简单高效的异构图神经网络(SeHGNN)。 为了轻松捕获结构信息,SeHGNN 使用轻量级均值聚合器预先计算邻居聚合,通过消除过度使用的邻居注意力并避免在每个训练时期重复邻居聚合来降低复杂性。 为了更好地利用语义信息,SeHGNN 采用长元路径的单层结构来扩展感受野,并采用基于 Transformer 的语义融合模块来融合来自不同元路径的特征。 因此,SeHGNN 表现出网络结构简单、预测精度高、训练速度快的特点。 对五个真实世界异构图的广泛实验证明了 SeHGNN 在准确性和训练速度方面均优于最先进的技术。
介绍
近年来,为了追求图表示学习的性能提升,图神经网络(GNN)出现了爆炸式增长(Wu 等人 2020;Liu 等人 2022b;Lin 等人 2022)。 GNN 主要针对与单一类型的节点和边相关的同质图而设计,遵循邻域聚合方案来捕获图的结构信息,其中每个节点的表示是通过递归聚合邻居节点 的特征来计算的( Kipf 和 Welling 2017)。
然而,GNN 不足以处理除了结构信息之外还拥有丰富语义信息的异构图(Shi 等人 2016)。 复杂系统中的许多现实世界数据自然地表示为异构图,其中多种类型的实体及其之间的关系分别由各种类型的节点和边来体现。 例如,如图1所示,引文网络ACM包括几种类型的节点:论文(P)、作者(A)和主题(S),以及许多不同语义的关系含义,例如作者论文、论文论文、论文主题。 这些关系可以相互组合形成高级语义关系,其表示为元路径(Sun等人2011;Sun和Han 2012)。 例如,2 跳元路径 Author-Paper-Author (APA) 表示共同作者关系,而 4 跳元路径 Author-Paper-Subject-Paper-Author (APSPA) 则描述两位作者曾从事过同一主题的研究。 异构图包含更全面的信息和丰富的语义,需要专门设计的模型。
人们提出了各种异构图神经网络(HGNN)来捕获语义信息,在异构图表示学习方面取得了良好的性能(Dong 等人 2020; Yang 等人 2020; Wang 等人 2020; Cheng 等人 2022; Yan 等人2022)。 因此,HGNN 是广泛应用的核心,例如社交网络分析 (Liu 等人 2018)、推荐 (Fan 等人 2019; Niu 等人 2020)、知识图谱推理(Bansal 等人 2019; Vashishth 等人 2020; Wang 等人 2021a)。
图1描述了HGNN的两个主要类别。 基于元路径的方法 (Schlichtkrull 等人 2018; Zhu 等人 2019; Wang 等人 2019; Fu 等人 2020) 先捕获相同语义的结构信息,然后再捕获融合不同的语义信息。 这些模型首先聚合每个元路径范围内的邻居特征以生成语义向量,然后融合这些语义向量以生成最终的嵌入向量。 无元路径方法 (Zhu 等人 2019; Hong 等人 2020; Hu 等人 2020b; Lv 等人 2021) 同时捕获结构和语义信息。 这些模型像传统的 GNN 一样聚合来自节点本地邻居的消息,但使用额外的模块(例如注意力)将节点类型和边缘类型等语义信息嵌入到传播的消息中。
现有的HGNN在同构图上继承了GNN的许多机制,特别是注意力机制和多层结构,如图1所示,但很少有人研究这些机制在异构图上是否真正有效。 此外,多层网络中的层次注意力计算和每个时期的重复邻居聚合带来了过多的复杂性和计算量。 例如,在基于元路径的模型 HAN (Wang 等人 2019) 和无元路径的模型 HGB (Lv等人2021),这已经成为HGNN在更大规模异构图上应用的速度瓶颈。
本文对这些机制进行了深入而详细的研究,并得出了两个发现:(1)语义注意力是必不可少的,而邻居注意力不是必需的,(2)模型具有单层结构和长元路径的性能优于多层和短元路径的。 这些发现意味着邻居注意力和多层结构不仅引入了不必要的复杂性,而且阻碍了模型获得更好的性能。
为此,我们提出了一种名为 SeHGNN 的新型基于元路径的方法。 SeHGNN 采用均值聚合器(Hamilton、Ying 和 Leskovec 2017) 来简化邻居聚合,采用具有长元路径的单层结构来扩展感受野,并利用基于 Transformer 的语义融合模块学习语义对之间的相互关注。 此外,由于SeHGNN中的简化邻居聚合是无参数的并且仅涉及线性运算,因此它有机会在预处理步骤中仅执行一次邻居聚合。 因此,SeHGNN 不仅表现出更好的性能,而且避免了在每个训练时期重复邻居聚合的需要,从而显着提高了训练速度。
我们对 HGB 基准测试中的四个广泛使用的数据集(Lv 等人 2021) 和 OGB 挑战的大规模数据集(Hu 等人 2020a) 进行了实验。 结果表明,SeHGNN 在异构图上的节点分类方面实现了优于现有技术的性能。
这项工作的贡献总结如下:
-
•
我们对 HGNN 中的注意力机制和网络结构进行了深入研究,并获得了两个重要发现,揭示了邻居注意力的不需要性以及利用单层结构和长元路径的优越性。
-
•
受上述发现的启发,我们提出了一种简单有效的 HGNN 架构 SeHGNN。 为了轻松捕获结构信息,SeHGNN 在预处理步骤中使用轻量级均值聚合器预先计算邻居聚合,这消除了过度使用的邻居注意力并避免在每个训练时期重复邻居聚合。 为了更好地利用语义信息,SeHGNN 采用长元路径的单层结构来扩展感受野,并采用基于 Transformer 的语义融合模块来融合来自不同元路径的特征。
-
•
对五个广泛使用的数据集的实验证明了 SeHGNN 相对于最先进的技术的优越性,即预测精度高和训练速度快。
初步知识
定义 1 异构图。 异构图定义为,其中是具有节点类型映射函数的节点集合,是具有边类型映射函数的边集合。 每个节点 都附加有一个节点类型 。 每条边(简称)都附加有一个关系(简称),从源节点 到目标节点。当时,图退化为齐次图。
的图结构可以用一系列邻接矩阵来表示。 对于每个关系,是相应的邻接矩阵,其中非零值表示当前关系的边的位置。
定义 2 元路径。 元路径定义了多种边缘类型的复合关系,表示为(简称)。
给定元路径,元路径实例 是遵循定义的模式的节点序列,表示为。 特别地,表示跳邻域的关系,其中是目标节点,是 的基于元路径的邻居。
给定一个元路径,其两端的节点类型为,可以构造一个元路径邻居图 ,其中边 存在于 中当且仅当存在 的元路径实例 > 在 中。
相关工作
对于同构图,GNN 被广泛用于从图结构中学习节点表示。 先驱 GCN (Kipf 和 Welling 2017) 提出了一种遵循逐层传播规则的多层网络,其中 层学习嵌入向量 通过聚合每个节点 的本地 1 跳邻居集 中的特征 。 GraphSAGE (Hamilton、Ying 和 Leskovec 2017) 通过引入小批量训练和邻居采样(Liu 等人 2022a) 提高了大型图的可扩展性。 GAT (Veličković 等人 2018) 引入了注意力机制,鼓励模型关注邻居最重要的部分。 SGC (Wu 等人 2019) 消除了连续图卷积层之间的非线性,带来了很大的加速,并且不影响模型效果。
除了结构信息之外,异构图还包含丰富的语义,由多种类型的节点和边揭示。 根据处理不同语义的方式,HGNN 分为基于元路径和无元路径的方法。
基于元路径的 HGNN 首先聚合相同语义的邻居特征,然后融合不同的语义。 RGCN (Schlichtkrull 等人 2018) 是第一个根据边缘类型分离 1 跳邻居聚合的。 HetGNN (Zhang 等人 2019) 使用不同跳的邻居。 它使用随机游走来收集不同距离的邻居,然后聚合相同节点类型的邻居。 HAN (Wang 等人 2019) 利用元路径来区分不同的语义。 它在邻居聚合步骤中使用每个元路径邻居图中的邻居注意力来聚合结构信息,然后在语义融合步骤中将不同子图的输出与每个节点的语义注意力融合起来。 MAGNN (Fu 等人 2020) 进一步利用元路径实例中的所有节点,而不仅仅是两个端点的节点。
无元路径 HGNN 与 GNN 一样,在本地 1 跳邻域内同时聚合来自所有节点类型的邻居的消息,但使用附加模块(例如注意力)将节点类型和边缘类型等语义信息嵌入到传播的消息中。 RSHN (Zhu 等人 2019) 构建粗化线图以获得不同边缘类型的全局嵌入表示,然后使用邻居特征和边缘类型嵌入的组合进行每层的特征聚合。 HetSANN (Hong 等人 2020) 使用具有特定类型评分函数的多层 GAT 网络来生成不同关系的注意力。 HGT (Hu 等人 2020b) 提出了一种基于 Transformer (Vaswani 等人 2017) 的新型异构相互关注机制,针对不同类型的节点使用特定类型的可训练参数,边缘。 HGB (Lv 等人 2021) 以多层 GAT 网络为骨干,结合节点特征和可学习的边型嵌入来生成注意力值。
DBLP | ACM | |||
---|---|---|---|---|
macro-f1 | micro-f1 | macro-f1 | micro-f1 | |
HAN | 92.59 | 93.06 | 90.30 | 90.15 |
HAN* | 92.75 | 93.23 | 90.61 | 90.48 |
HAN† | 92.19 | 92.66 | 89.78 | 89.67 |
HGB | 94.15 | 94.53 | 93.09 | 93.03 |
HGB* | 94.20 | 94.58 | 93.11 | 93.05 |
HGB† | 93.77 | 94.15 | 92.32 | 92.27 |
DBLP | ACM | |||
network | macro-f1 | micro-f1 | macro-f1 | micro-f1 |
(1,) | 79.43 | 80.16 | 89.81 | 90.03 |
(1,1) | 85.06 | 86.69 | 90.79 | 90.87 |
(2,) | 88.18 | 88.83 | 91.64 | 91.67 |
(1,1,1) | 88.38 | 89.37 | 87.95 | 88.84 |
(3,) | 93.33 | 93.72 | 92.67 | 92.64 |
(1,1,1,1) | 89.55 | 90.44 | 88.62 | 88.93 |
(2,2) | 91.88 | 92.35 | 92.57 | 92.53 |
(4) | 93.60 | 94.02 | 92.82 | 92.79 |
除了上述两大类 HGNN 之外,基于 SGC 的工作如 NARS (Yu 等人 2020)、SAGN (Sun, Gu, and Hu 2021),以及GALP (Zhang 等人 2022) 在异构图上也显示了令人印象深刻的结果,但它们将所有类型节点的特征聚合在一起,而没有明确区分不同的语义。
动机
现有的 HGNN 继承了 GNN 的许多机制,但没有分析其效果。 在本节中,我们对广泛使用的机制进行深入细致的研究,即 HGNN 的注意力机制和多层结构。 通过实验,我们获得了两个重要的发现,指导我们设计 SeHGNN 的架构。 本节中提供的所有结果都是使用不同数据分区运行 20 次的平均值,以减轻随机噪声的影响。
研究注意力。 HGNN 使用多重注意力,如图 1 所示,这些注意力是使用不同的模块或参数计算的。 这些注意力可以分为两种类型:相同关系的邻居内的邻居注意力和不同关系之间的语义注意力。 HAN 等基于元路径的方法分别在邻居聚合步骤和语义融合步骤中纳入了两个注意力机制。 像 HGB 这样的无元路径方法通过特定于关系的嵌入来计算 1 跳邻居的注意力。 虽然在无元路径方法中区分两种类型的注意力可能具有挑战性,但我们可以执行额外的计算来消除任一注意力的影响。 具体来说,对于每个节点的邻居的注意力值,我们可以在每个关系中对它们进行平均,这等于删除邻居注意力,或者在每个关系中对它们进行归一化,以便每个关系对最终结果的贡献相等,以删除语义注意力。
HGB 的重新实现实验表明,训练有素的 HGB 模型倾向于在每个关系中分配相似的注意力值,这使我们研究不同注意力的必要性。 我们在 HAN 和 HGB 上进行了实验,其中 * 表示删除邻居注意力,† 表示删除语义注意力。 表1中的结果表明,没有语义注意力的模型表现出模型效果的下降,而没有邻居注意力的模型则没有,从中我们得到了第一个发现。
发现1:语义注意力是必要的,而邻居注意力不是必需的。 这一发现是合理的,因为语义注意力能够权衡不同语义的重要性。 对于邻居注意力,各种基于 SGC 的工作(Wu 等人 2019;Rossi 等人 2020;Zhang 等人 2022) 已经证明,简单的均值聚合可以与注意力模块的聚合一样有效。
多层结构的研究。 在没有邻居关注的情况下,无元路径方法具有等效形式,首先对每个关系中邻居的特征进行平均,然后融合不同关系的输出。 因此,它们可以转换为基于元路径的多层结构且每层只有 1 跳元路径的方法。 因此,在下面的实验中,我们重点关注基于元路径的方法中层数和元路径的影响。
我们使用一系列数字来表示每个变体的结构,对 HAN 进行实验。 例如,在 ACM 数据集上,结构 (1,1,1,1) 表示每层具有 1 跳元路径 PA、PS 的四层网络,(4) 表示具有所有元路径的单层网络不超过4跳,如PA、PS、PAP、PSP、PAPAP、PSPSP等。 这些列表还显示了感受野的大小。 例如,结构(1,1,1,1),(2,2),(4)具有相同的感受野大小,其中涉及4跳邻居。 根据表2所示的结果,我们得出第二个发现。
发现 2:具有单层结构和长元路径的模型优于具有多层和短元路径的模型。 如表2所示,单层和长元路径的模型在感受野大小相同的情况下取得了更好的性能。 我们将此归因于多层网络融合每层语义,使得难以区分高层语义。 例如,在具有结构(4)的模型中,多跳元路径的利用使我们能够区分高级语义,例如由同一作者(PAP)或熟悉的作者(PAPAP)撰写,而这些在四层网络 (1,1,1,1) 中无法区分,因为两个连续层之间的所有中间向量都表示不同语义的混合。 此外,增加最大元路径长度可以通过引入更多具有不同语义的元路径来增强模型的性能。
SeHGNN 的提案。 受这两个发现的启发,一方面,我们可以通过在每个元路径范围内采用均值聚合来避免冗余邻居注意,而无需牺牲模型效果;另一方面,我们可以使用单层简化网络结构,但使用更多、更长的元路径来扩大感受野并获得更好的性能。 此外,由于没有注意模块的邻居聚合部分仅涉及线性操作并且没有可训练参数,因此它提供了在预处理步骤中仅执行一次邻居聚合的机会,而不是在每个训练时期执行邻居聚合,这显着减少了训练时间。 总的来说,这些优化简化了网络结构并使其更加高效,这是SeHGNN的关键点。
方法
本节正式提出简单高效的异构神经网络(SeHGNN)。 SeHGNN 的架构如图2所示,包括三个主要组件:简化的邻居聚合、多层特征投影和基于 Transformer 的语义融合。 图2还强调了SeHGNN与其他基于元路径的HGNN之间的区别,即SeHGNN在预处理步骤中预先计算邻居聚合,从而避免了在每个训练中重复邻居聚合的过度复杂性时代。 算法1概述了整个训练过程。
简化的邻居聚合
简化的邻居聚合仅在预处理步骤中执行一次,并为所有给定元路径的集合生成不同语义的特征矩阵列表。 一般来说,对于每个节点,它采用均值聚合来聚合每个给定元路径的基于元路径的邻居的特征,并输出语义特征向量列表,表示为
其中 是与元路径 对应的所有元路径实例的集合, 表示具有目标节点 的一个元路径实例,源节点。
我们提出了一种新方法来简化基于元路径的邻居的收集。 HAN 等现有的基于元路径的方法构建元路径邻居图,枚举每个元路径的所有基于元路径的邻居,这会带来很高的开销,因为元路径实例的数量随着元路径的长度呈指数增长。 受 GCN 逐层传播的启发,我们使用邻接矩阵的乘法计算每个节点对目标的最终贡献权重。 具体来说,令 为属于类型 的所有节点的原始特征矩阵,其中 为特征维度,并且则简化的邻居聚合过程可以表示为
其中, 是 跳元路径, 是节点类型 和 之间邻接矩阵 的行规范化形式。 请注意,短元路径的聚合结果可以用作长元路径的中间值。 例如,给定 ACM 数据集的两个元路径 PAP 和 PPAP,我们可以先计算 ,然后计算 。
此外,之前的(Wang and Leskovec 2020;Wang 等人 2021b;Shi 等人 2021)研究表明,将标签作为附加输入可以提高模型性能。 为了利用这一点,类似于原始特征的聚合,我们以 one-hot 格式表示标签,并将它们传播到各种元路径。 该过程生成一系列矩阵,反映相应元路径邻居图的标签分布。 请注意,任何元路径的两个端点都应该是节点分类任务中的目标节点类型。 给定一个元路径,标签传播过程可以表示为
其中 是原始标签矩阵。 矩阵中,训练集中节点对应的行取one-hot格式标签的值,其他行用0填充。 为了避免标签泄漏,我们通过删除邻接矩阵相乘结果中的对角线值来防止每个节点接收其自身的真实标签信息。 标签传播也在邻居聚合步骤中执行,并生成语义矩阵作为后续训练的额外输入。
DBLP | IMDB | ACM | Freebase | ||||||
macro-f1 | micro-f1 | macro-f1 | micro-f1 | macro-f1 | micro-f1 | macro-f1 | micro-f1 | ||
1st | RGCN | 91.52±0.50 | 92.07±0.50 | 58.85±0.26 | 62.05±0.15 | 91.55±0.74 | 91.41±0.75 | 46.78±0.77 | 58.33±1.57 |
HetGNN | 91.76±0.43 | 92.33±0.41 | 48.25±0.67 | 51.16±0.65 | 85.91±0.25 | 86.05±0.25 | - | - | |
HAN | 91.67±0.49 | 92.05±0.62 | 57.74±0.96 | 64.63±0.58 | 90.89±0.43 | 90.79±0.43 | 21.31±1.68 | 54.77±1.40 | |
MAGNN | 93.28±0.51 | 93.76±0.45 | 56.49±3.20 | 64.67±1.67 | 90.88±0.64 | 90.77±0.65 | - | - | |
2nd | RSHN | 93.34±0.58 | 93.81±0.55 | 59.85±3.21 | 64.22±1.03 | 90.50±1.51 | 90.32±1.54 | - | - |
HetSANN | 78.55±2.42 | 80.56±1.50 | 49.47±1.21 | 57.68±0.44 | 90.02±0.35 | 89.91±0.37 | - | - | |
HGT | 93.01±0.23 | 93.49±0.25 | 63.00±1.19 | 67.20±0.57 | 91.12±0.76 | 91.00±0.76 | 29.28±2.52 | 60.51±1.16 | |
HGB | 94.01±0.24 | 94.46±0.22 | 63.53±1.36 | 67.36±0.57 | 93.42±0.44 | 93.35±0.45 | 47.72±1.48 | 66.29±0.45 | |
3rd | SeHGNN | 95.06±0.17 | 95.42±0.17 | 67.11±0.25 | 69.17±0.43 | 94.05±0.35 | 93.98±0.36 | 51.87±0.86 | 65.08±0.66 |
4th | Variant#1 | 93.61±0.51 | 94.08±0.48 | 64.48±0.45 | 66.58±0.42 | 93.06±0.18 | 92.98±0.18 | 33.23±1.39 | 57.60±1.17 |
Variant#2 | 94.66±0.27 | 95.01±0.24 | 65.27±0.60 | 66.68±0.52 | 93.46±0.43 | 93.38±0.44 | 46.82±1.12 | 64.08±1.43 | |
Variant#3 | 94.86±0.14 | 95.24±0.13 | 66.63±0.34 | 68.21±0.32 | 93.95±0.48 | 93.87±0.50 | 50.71±0.44 | 63.41±0.47 | |
Variant#4 | 94.52±0.05 | 94.93±0.06 | 64.99±0.54 | 66.65±0.50 | 93.88±0.63 | 93.80±0.64 | 50.30±0.23 | 64.53±0.38 |
多层特征投影
特征投影步骤将语义向量投影到相同的数据空间中,因为不同元路径的语义向量可能具有不同的维度或位于不同的数据空间中。 一般来说,它为每个元路径定义一个特定于语义的转换矩阵并计算。 为了获得更好的表示能力,我们对每个元路径 使用多层感知块 ,并在两个连续线性层之间包含归一化层、非线性层和 dropout 层。 那么这个过程可以表示为
基于 Transformer 的语义融合
语义融合步骤融合语义特征向量并为每个节点生成最终的嵌入向量。 我们没有使用简单的加权和格式,而是提出了基于 Transformer (Vaswani 等人 2017) 的语义融合模块来进一步探索每对语义之间的相互关系。
基于 Transformer 的语义融合模块旨在学习语义向量对之间的相互关注,给定每个节点的预定义元路径列表 和投影语义向量 。 对于每个语义向量,该模块将该向量映射为查询向量、键向量和值向量。 相互注意力权重是查询向量和关键向量经过softmax归一化后的点积结果。 当前语义的输出向量是所有值向量加上残差连接的加权和。 语义融合的过程可以表示为
其中 是所有元路径共享的可训练参数。
每个节点的最终嵌入向量是所有这些输出向量的串联。 对于节点分类等下游任务,使用另一个 MLP 来生成预测结果,可以表示为
实验
在HGB基准(Lv等人2021)中的DBLP、ACM、IMDB和Freebase等四种广泛使用的异构图以及OGB挑战中的大规模数据集ogbn-mag上进行了实验(胡等人2021)。 所有实验设置和网络配置的详细信息记录在附录中222附录可在https://arxiv.org/abs/2207.02547找到。 代码可在 https://github.com/ICT-GIMLab/SeHGNN 获取。.
HGB 基准结果
表 3 显示了 SeHGNN 在四个数据集上与 HGB 基准测试中的几个基线相比的性能,包括四种基于元路径的方法(第一个块)和四种无元路径的方法(第二个块)。 结果证明了 SeHGNN 的有效性,因为它在所有这些基线上实现了最佳性能,但在 Freebase 数据集上的 micro-f1 精度方面排名第二。
此外,我们还进行了全面的消融研究,以验证动机部分的两项研究结果并确定其他模块的重要性。 表3的第四块显示了SeHGNN的四种变体的结果。
变体#1 与 HAN 一样,在邻居聚合步骤中对每个元路径使用 GAT。 Variant#2采用两层结构,每层都有独立的邻居聚合和语义融合步骤,但每层元路径的最大跳数是SeHGNN的一半,以确保SeHGNN和其Variant#2具有相同的大小的感受野。 SeHGNN 与其两个变体之间的性能差距证明这两个发现也适用于 SeHGNN。
Variant#3 不包含标签作为额外输入,Variant#4 用 HAN 等加权和融合取代了基于转换器的语义融合。 值得注意的是,虽然不如 SeHGNN,但 Variant#3 已经优于 Freebase 数据集上除 micro-f1 之外的大多数基线。 这些结果表明,标签传播和基于 Transformer 的融合的利用提高了模型性能。
Methods | Validation accuracy | Test accuracy |
---|---|---|
RGCN | 48.35±0.36 | 47.37±0.48 |
HGT | 49.89±0.47 | 49.27±0.61 |
NARS | 51.85±0.08 | 50.88±0.12 |
SAGN | 52.25±0.30 | 51.17±0.32 |
GAMLP | 53.23±0.23 | 51.63±0.22 |
HGT+emb | 51.24±0.46 | 49.82±0.13 |
NARS+emb | 53.72±0.09 | 52.40±0.16 |
GAMLP+emb | 55.48±0.08 | 53.96±0.18 |
SAGN+emb+ms | 55.91±0.17 | 54.40±0.15 |
GAMLP+emb+ms | 57.02±0.41 | 55.90±0.27 |
SeHGNN | 55.95±0.11 | 53.99±0.18 |
SeHGNN+emb | 56.56±0.07 | 54.78±0.17 |
SeHGNN+ms | 58.70±0.08 | 56.71±0.14 |
SeHGNN+emb+ms | 59.17±0.09 | 57.19±0.12 |
Ogbn-mag 上的结果
ogbn-mag数据集提出了两个额外的挑战:(1)某些类型的节点缺乏原始特征,(2)目标类型节点根据年份进行分割,导致训练节点和测试节点具有不同的数据分布。 现有方法通常通过以下方式解决这些挑战:(1) 使用 ComplEx (Trouillon 等人 2016) 等无监督表示学习算法生成额外的嵌入(缩写为 emb),以及 (2) 利用多阶段学习(简写为ms),在最后一个训练阶段选择具有可信预测的测试节点,将这些节点添加到训练集中,并在新阶段重新训练模型(李、韩、吴 2018;孙、林、朱 2020;杨等人 2021)。 为了提供全面的比较,我们比较了使用或不使用这些技巧的结果。 对于没有 emb 的方法,我们使用随机初始化的原始特征向量。
表 4 显示了大型数据集 ogbn-mag 上的结果与 OGB 排行榜上的基线的比较。 结果表明,SeHGNN 在相同条件下优于其他方法。 值得注意的是,具有随机初始化特征的 SeHGNN 甚至优于其他具有来自附加表示学习算法的训练有素嵌入的 SeHGNN,这反映了 SeHGNN 从图结构中学习了更多信息。
时间分析
首先,我们从理论上分析了 SeHGNN 与 HAN 和 HGB 相比的时间复杂度,如表5所示。 我们假设 SeHGNN 和 HAN 具有 元路径的单层结构,以及 HGB 的 层结构。 元路径的最大跳数也是,以保证感受野大小相同。 目标类型节点数333为了简洁比较,我们只考虑HAN和HGB方法上目标类型节点线性投影的复杂度。 详情请参阅附录。 为,输入向量和隐藏向量的维度为。 HAN 上元路径邻居图中的平均邻居数和 HGB 上多层聚合期间涉及的邻居数分别为 。 请注意, 和 都随着元路径的长度和层数 呈指数增长。对于上述五个数据集,我们最多使用数十个元路径,但每个节点平均聚合来自数千个邻居的信息。 一般来说,我们有,因此SeHGNN的理论复杂度远低于HAN和HGB。
为了验证我们的理论分析,我们进行了实验来比较 SeHGNN 与之前的 HGNN 的时间消耗。 图3显示了这些模型的训练micro-f1分数相对于每个训练epoch的平均时间消耗,这反映了SeHGNN在速度和模型效果上的优越性。
|
|
|
Total | |||||||
---|---|---|---|---|---|---|---|---|---|---|
SeHGNN | – | |||||||||
HAN | ||||||||||
HGB |
结论
本文提出了一种称为 SeHGNN 的异构图表示学习新方法,该方法基于关于注意力利用和网络结构的两个关键发现。 SeHGNN采用轻量级均值聚合器来预先计算邻居聚合,有效捕获结构信息,同时避免过度使用邻居注意力和重复邻居聚合。 此外,SeHGNN 利用具有长元路径的单层结构来扩展感受野,并利用基于 Transformer 的语义融合模块来更好地利用语义信息,从而显着提高模型有效性。 对五个常用数据集的实验表明,SeHGNN 在准确性和训练速度方面均优于最先进的方法。
致谢
该工作得到了国家自然科学基金项目(批准号: 61732018、61872335和62202451),奥中合作研发项目(FFG和CAS)(批准号: 171111KYSB20200002),中科院青年科学家基础研究项目(批准号:171111KYSB20200002) YSBR-029)和CAS青年创新促进会项目。
参考
- Bansal et al. (2019) Bansal, T.; Juan, D.-C.; Ravi, S.; and McCallum, A. 2019. A2N: Attending to neighbors for knowledge graph inference. In Proceedings of the 57th annual meeting of the association for computational linguistics, 4387–4392.
- Dong et al. (2020) Dong, Y.; Hu, Z.; Wang, K.; Sun, Y.; and Tang, J. 2020. Heterogeneous Network Representation Learning. In IJCAI, volume 20, 4861–4867.
- Fan et al. (2019) Fan, S.; Zhu, J.; Han, X.; Shi, C.; Hu, L.; Ma, B.; and Li, Y. 2019. Metapath-guided heterogeneous graph neural network for intent recommendation. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, 2478–2486.
- Fu et al. (2020) Fu, X.; Zhang, J.; Meng, Z.; and King, I. 2020. Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding. In Proceedings of The Web Conference 2020, 2331–2341.
- Hamilton, Ying, and Leskovec (2017) Hamilton, W.; Ying, Z.; and Leskovec, J. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems, 30.
- Hong et al. (2020) Hong, H.; Guo, H.; Lin, Y.; Yang, X.; Li, Z.; and Ye, J. 2020. An attention-based graph neural network for heterogeneous structural learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, 4132–4139.
- Hu et al. (2021) Hu, W.; Fey, M.; Ren, H.; Nakata, M.; Dong, Y.; and Leskovec, J. 2021. OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs. In Vanschoren, J.; and Yeung, S., eds., Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, volume 1.
- Hu et al. (2020a) Hu, W.; Fey, M.; Zitnik, M.; Dong, Y.; Ren, H.; Liu, B.; Catasta, M.; and Leskovec, J. 2020a. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33: 22118–22133.
- Hu et al. (2020b) Hu, Z.; Dong, Y.; Wang, K.; and Sun, Y. 2020b. Heterogeneous graph transformer. In Proceedings of The Web Conference 2020, 2704–2710.
- Kingma and Ba (2015) Kingma, D. P.; and Ba, J. 2015. Adam: A Method for Stochastic Optimization. In Bengio, Y.; and LeCun, Y., eds., International Conference on Learning Representations, ICLR 2015.
- Kipf and Welling (2017) Kipf, T. N.; and Welling, M. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations, ICLR 2017.
- Li, Han, and Wu (2018) Li, Q.; Han, Z.; and Wu, X.-M. 2018. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI conference on artificial intelligence.
- Lin et al. (2022) Lin, H.; Yan, M.; Ye, X.; Fan, D.; Pan, S.; Chen, W.; and Xie, Y. 2022. A Comprehensive Survey on Distributed Training of Graph Neural Networks. arXiv preprint arXiv:2211.05368.
- Liu et al. (2022a) Liu, X.; Yan, M.; Deng, L.; Li, G.; Ye, X.; and Fan, D. 2022a. Sampling Methods for Efficient Training of Graph Convolutional Networks: A Survey. IEEE/CAA Journal of Automatica Sinica, 9(2): 205–234.
- Liu et al. (2022b) Liu, X.; Yan, M.; Deng, L.; Li, G.; Ye, X.; Fan, D.; Pan, S.; and Xie, Y. 2022b. Survey on Graph Neural Network Acceleration: An Algorithmic Perspective. In Raedt, L. D., ed., Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, 5521–5529.
- Liu et al. (2018) Liu, Z.; Chen, C.; Yang, X.; Zhou, J.; Li, X.; and Song, L. 2018. Heterogeneous graph neural networks for malicious account detection. In Proceedings of the 27th ACM international conference on information and knowledge management, 2077–2085.
- Lv et al. (2021) Lv, Q.; Ding, M.; Liu, Q.; Chen, Y.; Feng, W.; He, S.; Zhou, C.; Jiang, J.; Dong, Y.; and Tang, J. 2021. Are we really making much progress? Revisiting, benchmarking and refining heterogeneous graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 1150–1160.
- Niu et al. (2020) Niu, X.; Li, B.; Li, C.; Xiao, R.; Sun, H.; Deng, H.; and Chen, Z. 2020. A dual heterogeneous graph attention network to improve long-tail performance for shop search in e-commerce. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 3405–3415.
- Rossi et al. (2020) Rossi, E.; Frasca, F.; Chamberlain, B.; Eynard, D.; Bronstein, M.; and Monti, F. 2020. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.11198.
- Schlichtkrull et al. (2018) Schlichtkrull, M.; Kipf, T. N.; Bloem, P.; Berg, R. v. d.; Titov, I.; and Welling, M. 2018. Modeling relational data with graph convolutional networks. In European semantic web conference, 593–607. Springer.
- Shi et al. (2016) Shi, C.; Li, Y.; Zhang, J.; Sun, Y.; and Philip, S. Y. 2016. A survey of heterogeneous information network analysis. IEEE Transactions on Knowledge and Data Engineering, 29(1): 17–37.
- Shi et al. (2021) Shi, Y.; Huang, Z.; Feng, S.; Zhong, H.; Wang, W.; and Sun, Y. 2021. Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification. In Zhou, Z.-H., ed., Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, 1548–1554.
- Sun, Gu, and Hu (2021) Sun, C.; Gu, H.; and Hu, J. 2021. Scalable and adaptive graph neural networks with self-label-enhanced training. arXiv preprint arXiv:2104.09376.
- Sun, Lin, and Zhu (2020) Sun, K.; Lin, Z.; and Zhu, Z. 2020. Multi-stage self-supervised learning for graph convolutional networks on graphs with few labeled nodes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, 5892–5899.
- Sun and Han (2012) Sun, Y.; and Han, J. 2012. Mining heterogeneous information networks: principles and methodologies. Synthesis Lectures on Data Mining and Knowledge Discovery, 3(2): 1–159.
- Sun et al. (2011) Sun, Y.; Han, J.; Yan, X.; Yu, P. S.; and Wu, T. 2011. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks. Proceedings of the VLDB Endowment, 4(11): 992–1003.
- Trouillon et al. (2016) Trouillon, T.; Welbl, J.; Riedel, S.; Gaussier, É.; and Bouchard, G. 2016. Complex embeddings for simple link prediction. In International conference on machine learning, 2071–2080. PMLR.
- Vashishth et al. (2020) Vashishth, S.; Sanyal, S.; Nitin, V.; and Talukdar, P. 2020. Composition-based Multi-Relational Graph Convolutional Networks. In International Conference on Learning Representations.
- Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; and Polosukhin, I. 2017. Attention is all you need. Advances in neural information processing systems, 30.
- Veličković et al. (2018) Veličković, P.; Cucurull, G.; Casanova, A.; Romero, A.; Liò, P.; and Bengio, Y. 2018. Graph Attention Networks. International Conference on Learning Representations, ICLR 2018.
- Wang and Leskovec (2020) Wang, H.; and Leskovec, J. 2020. Unifying graph convolutional neural networks and label propagation. arXiv preprint arXiv:2002.06755.
- Wang et al. (2021a) Wang, S.; Wei, X.; Nogueira dos Santos, C. N.; Wang, Z.; Nallapati, R.; Arnold, A.; Xiang, B.; Yu, P. S.; and Cruz, I. F. 2021a. Mixed-curvature multi-relational graph neural network for knowledge graph completion. In Proceedings of the Web Conference 2021, 1761–1771.
- Wang et al. (2020) Wang, X.; Bo, D.; Shi, C.; Fan, S.; Ye, Y.; and Yu, P. S. 2020. A survey on heterogeneous graph embedding: methods, techniques, applications and sources. arXiv preprint arXiv:2011.14867.
- Wang et al. (2019) Wang, X.; Ji, H.; Shi, C.; Wang, B.; Ye, Y.; Cui, P.; and Yu, P. S. 2019. Heterogeneous graph attention network. In The world wide web conference, 2022–2032.
- Wang et al. (2021b) Wang, Y.; Jin, J.; Zhang, W.; Yu, Y.; Zhang, Z.; and Wipf, D. 2021b. Bag of tricks of semi-supervised classification with graph neural networks. arXiv preprint arXiv:2103.13355.
- Wu et al. (2019) Wu, F.; Souza, A.; Zhang, T.; Fifty, C.; Yu, T.; and Weinberger, K. 2019. Simplifying graph convolutional networks. In International conference on machine learning, 6861–6871. PMLR.
- Wu et al. (2020) Wu, Z.; Pan, S.; Chen, F.; Long, G.; Zhang, C.; and Philip, S. Y. 2020. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1): 4–24.
- Yan et al. (2022) Yan, M.; Zou, M.; Yang, X.; Li, W.; Ye, X.; Fan, D.; and Xie, Y. 2022. Characterizing and Understanding HGNNs on GPUs. IEEE Computer Architecture Letters, 21(2): 69–72.
- Yang et al. (2020) Yang, C.; Xiao, Y.; Zhang, Y.; Sun, Y.; and Han, J. 2020. Heterogeneous network representation learning: A unified framework with survey and benchmark. IEEE Transactions on Knowledge and Data Engineering.
- Yang et al. (2021) Yang, H.; Yan, X.; Dai, X.; Chen, Y.; and Cheng, J. 2021. Self-enhanced gnn: Improving graph neural networks using model outputs. In 2021 International Joint Conference on Neural Networks (IJCNN), 1–8. IEEE.
- Yu et al. (2020) Yu, L.; Shen, J.; Li, J.; and Lerer, A. 2020. Scalable graph neural networks for heterogeneous graphs. arXiv preprint arXiv:2011.09679.
- Zhang et al. (2019) Zhang, C.; Song, D.; Huang, C.; Swami, A.; and Chawla, N. V. 2019. Heterogeneous graph neural network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 793–803.
- Zhang et al. (2022) Zhang, W.; Yin, Z.; Sheng, Z.; Li, Y.; Ouyang, W.; Li, X.; Tao, Y.; Yang, Z.; and Cui, B. 2022. Graph Attention Multi-Layer Perceptron. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’22, 4560–4570. ISBN 9781450393850.
- Zheng et al. (2022) Zheng, X.; Liu, Y.; Pan, S.; Zhang, M.; Jin, D.; and Yu, P. S. 2022. Graph Neural Networks for Graphs with Heterophily: A Survey. arXiv preprint arXiv:2202.07082.
- Zhu et al. (2019) Zhu, S.; Zhou, C.; Pan, S.; Zhu, X.; and Wang, B. 2019. Relation structure-aware heterogeneous graph neural network. In 2019 IEEE international conference on data mining (ICDM), 1534–1539. IEEE.
附录A附录
HGB 模型中的观察
无元路径方法 HGB (Lv 等人 2021) 使用两个端点的节点嵌入和边类型嵌入的串联来计算每条边上的注意力值,表示为
RGCN | HetGNN | HAN | MAGNN | |||||||
|
||||||||||
Neighbor aggregation |
|
|||||||||
|
|
|
在我们对 HGB 的重新实现实验中,我们发现注意力值主要由边缘类型嵌入主导。 从观察中可以看出,每个关系内的注意力值相似,而不同关系之间的注意力值则显着。 图4(a)描述了这一观察结果,图4(b)显示了每个关系内以及每个目标节点的所有关系之间注意力值标准差的统计ACM 数据集。
这一观察促使我们研究 HGNN 中每个关系内的邻居注意力以及不同关系之间的语义注意力的必要性。
现有基于元路径的方法的框架
对于现有的基于元路径的方法的每一层,计算可以分为三个主要步骤,特征投影、邻居聚合和语义融合 ,如表6所示。 特征投影步骤旨在将不同类型节点的原始特征向量映射到同一数据空间,通常表示为一个线性投影层。 然后,邻居聚合步骤聚合每个语义范围的邻居的特征向量,例如,对于RGCN中的每个关系(可以被视为1跳元路径),对于HetGNN中的每个节点类型,或者对于HAN和MAGNN中的每个元路径。 最后,语义聚合步骤融合所有语义中的这些语义向量,并输出每个节点的最终嵌入。
去除邻居注意力后,由于一层特征投影和邻居聚合都不包含非线性函数,因此可以交换两个步骤的顺序。 此外,由于邻居聚合步骤不涉及任何可训练参数,因此可以将其放在预处理步骤中,并且其结果在所有训练时期共享。
在后来的实验中,我们发现用于特征投影的多层块可以进一步提高性能。 因此,SeHGNN 在特征投影步骤中对每个元路径采用 MLP 块而不是单个线性层。
实验设置
SeHGNN 的评估涉及 HGB benchmark(Lv 等人 2021) 的四个中型数据集和一个大型数据集 ogbn-mag444https://ogb.stanford.edu/docs/nodeprop/#ogbn-mag 来自 OGB 挑战 (Hu等人2021)。 这些异构图的统计数据总结在表7中。 对于中等规模的数据集,我们遵循HGB基准的数据集配置要求。 具体来说,目标类型节点分为30%用于本地训练,70%用于在线测试,其中测试节点的标签不公开,研究人员必须将其预测提交到HGB基准网站进行在线评估。 对于本地训练,我们将 30% 的节点随机分为 24% 进行训练,6% 进行验证。 我们将我们的结果与 HGB 论文中报告的基线分数进行比较,所有分数都是 5 个不同本地数据分区的平均值。 对于 ogbn-mag 数据集,我们遵循官方数据分区,其中 2018 年之前、2018 年和 2019 年以来发表的论文分别是训练、验证和测试的节点。 我们将我们的结果与 OGB 排行榜上的分数进行比较,所有分数都是 10 次单独训练的平均值。
Dataset | #Nodes |
|
#Edges | #Classes | ||
---|---|---|---|---|---|---|
DBLP | 26,128 | 4 | 239,566 | 4 | ||
ACM | 10,942 | 4 | 547,872 | 3 | ||
IMDB | 21,420 | 4 | 86,642 | 5 | ||
Freebase | 180,098 | 8 | 1,057,688 | 7 | ||
Ogbn-mag | 1,939,743 | 4 | 21,111,007 | 349 |
Feature propagation | Label Propagation | |||
Max Hop | #Metapaths | Max Hop | #Metapaths | |
DBLP | 2 | 5 | 4 | 4 |
IMDB | 4 | 25 | 4 | 12 |
ACM | 4 | 41 | 3 | 9 |
Freebase | 2 | 73 | 3 | 9 |
Ogbn-mag | 2 | 10 | 2 | 5 |
我们采用一种简单的元路径选择方法,其中预设最大跳数并使用不超过此最大跳数的所有可用元路径。 我们测试了原始特征传播和标签传播的最大跳数的不同组合,最终选择如图8所示。
对于所有实验,SeHGNN 在特征投影步骤中对每个元路径采用两层 MLP,其中隐藏向量的维度为 512。 在基于Transformer的融合模块中,查询向量和键向量的维度是隐藏向量的1/4,值向量的维度等于隐藏向量的维度,头的数量为1。
SeHGNN 在训练过程中使用 Adam (Kingma and Ba 2015) 进行优化。 Freebase数据集的学习率为0.0003,权重衰减为0.0001,其他数据集的学习率为0.001,权重衰减为0。
进一步分析时间复杂度
|
|
|
|||||||
---|---|---|---|---|---|---|---|---|---|
HAN | |||||||||
HGB |
HAN 和 HGB 方法的计算复杂性难以估计,因为它包含各种节点类型以及邻居聚合步骤中投影邻居节点特征的重用。 为了进行直观的比较,表 5 包含了 HAN 和 HGB 中目标类型节点的线性投影复杂度,而省略了其他类型节点的线性投影复杂度。 如表9所示,我们添加了其他类型节点的计算训练复杂度,假设一批中涉及的这些节点的数量为。这些添加包括特征投影步骤中的线性投影和邻居聚合步骤中邻居注意力的计算。
当采用full-batch模式训练时,和分别表示异构图中目标类型节点和其他类型节点的总数。 如果和相当,即,则表9中的结果可以简化为表5中的结果。
但是,对于小批量训练,每个训练批次的 可能明显大于 。 在小批量 且几乎没有可重用的投影邻居节点特征的情况下, 随着元路径长度或层数呈指数增长(即 对于 HAN, 对于 HGB)。 在这种情况下,表 5 中 HAN 和 HGB 的计算复杂度结果显示出明显的低估。
相比之下,估计 SeHGNN 的计算复杂度要简单得多。 由于邻居聚合是在预处理步骤中计算的,因此消除了每个训练批次中其他类型节点的参与。