KDD'21 | 异质图神经网络的可微元图搜索

论文标题：

DiffMG: Differentiable Meta Graph Search for Heterogeneous Graph Neural Networks

论文地址：

https://arxiv.org/pdf/2010.03250.pdf

代码链接：

https://github.com/AutoML-Research/DiffMG

摘要

图数据的表示学习与图神经网络是当前重要且热门的研究方向，不仅在学术界取得了很高的关注度（以图表示学习的两位国际领军学者为例）：

▲ 图1 Jure Leskovec的Google Scholar页面

▲ 图2 Michael Bronstein的Google Scholar页面

 

在工业界也有广泛的应用（例如在阿里巴巴、Pinterest 等互联网公司中应用的基于图表示学习的大规模推荐算法 [1, 2]）。

在这篇文章中，我们提出了一种在异质图（Heterogeneous Information Networks (HINs)）[3] 上进行表示学习的新方法。我们的方法受到了神经网络架构搜索（Neural Architecture Search (NAS)）[4] 的启发。NAS 旨在自动地搜索出适应于数据集与下游任务的神经网络结构。对于 HINs，我们希望可以使图神经网络（Graph Neural Networks (GNNs)）[5] 自动地选择利用异质图中与下游任务相关的语义信息。

具体地，我们的方法自动地搜索一个与异质网络和下游任务均匹配的“元图”（Meta Graph）[6] 来决定 GNNs 如何沿着异质网络中不同类型的边传播信息。我们设计了一个新颖且富有表达力的搜索空间（Search Space），这一搜索空间具有有向无环图的形式（Directed Acyclic Graph (DAG)），以充分表示可能的“元图”。

我们定义的搜索空间很大，为了高效地进行搜索，我们进一步提出了一个创新的可微搜索算法，使得搜索所需的时间与训练一个单独的 GNN 相当。我们在若干个真实的异质数据集上测评了我们的方法在节点分类（Node Classification）任务和推荐（Recommendation）任务中的表现，实验结果表明，相比于已有的为异质图设计的 GNNs，我们的方法可以在实现更好效果的同时保持高效率。

背景介绍

异质图（HINs）广泛地存在于真实世界的许多应用场景中，如互联网数据挖掘、推荐系统、生物信息，以表示众多个体间复杂的连接关系。相比于同质信息网络，除了网络的拓扑结构外，异质图同时含有丰富的语义信息。这些语义信息包括节点与边的类型等。例如，在一个电影推荐数据集中，节点可以分为电影、演员、导演等类型。这些附加的语义信息可以帮助下游任务，如何更好地利用它们是异质图表示学习的一个重要挑战。

▲ 图3 异质图示例

近年来，GNNs 在图表示学习的许多任务上都取得了显著的进展。然而，现有的方法在处理异质图时仍有不足之处。例如，经典的 GCN 模型 [7] 认为所有邻居节点是同质的，无法区分节点的不同类型，因此不能利用 HINs 中含有的语义信息。

一些专门为 HINs 设计的 GNNs，例如 HAN [8]、MAGNN [9]，依赖手工设计的规则“元路径”（Meta Path）[10] 来选取从哪些邻居节点收集信息。这类模型的主要限制在于，手工设计的规则需要领域的先验知识，因此它们很难应用在来自新的、复杂的领域的数据集（例如，为各种各样的化学粒子设计规则是极其困难的）。

另一个较新的方法 HGT [11] 借鉴了 Transformer 结构，对不同类型的节点和边计算 attention，以避免手工设计规则。然而，HGT 的参数量大，训练速度慢，这一问题在处理大规模的图数据时会变得尤为明显。

此外，即使 attention 可以对不同类型的邻居节点赋予不同的权重，它仍然可能收集到与下游任务不相关的语义信息。例如，当我们想要预测学术网络中作者的研究领域（CV、NLP 等）时，作者所在的机构/学校是无关的信息（噪声），收集它们可能不利于下游的预测任务。综上所述，如何使 GNNs 能自动地、高效地挖掘 HINs 中与下游任务相关的语义信息仍然没有被很好地解决。

动机

我们的方法受到了神经网络架构搜索（Neural Architecture Search（NAS））的启发 [4]。NAS 旨在自动地搜索出适应于数据集与下游任务的神经网络结构。在计算机视觉的许多任务中，NAS 发现的网络结构已经取得了比手工设计的网络更好的效果。早期的基于强化学习或进化算法的 NAS 工作，对每一个候选的网络结构都要从头训练，然后验证它的表现，这使得搜索过程非常耗时（可多达数千个 GPU 天）。

 

近期的 one-shot NAS 方法使用参数共享（parameter sharing）[12]，即所有候选的网络结构共享一个更大的超网络的参数。这样，搜索问题就转化为了如何训练一个超网络及如何从超网络中得到理想的子模型，从而大大缩短了搜索时间。NAS 的这些进展吸引了我们的注意，并促使我们思考，能否基于这一框架提出一种方法来解决异质图表示学习的问题？

这样的延伸远不是容易的，因为不同领域的数据和任务有不同的性质，对应的网络结构也有各自的特点。一个首要的问题是：如何设计一个能表示 HINs 中包含的语义信息的搜索空间？我们借鉴了传统的数据挖掘方法在对 HINs 中节点的相似性进行建模时提出的两个概念，即“元路径”（Meta Path）[10] 和“元图”（Meta Graph）[6]。

这两个概念是由节点类型和边类型组成的复合关系，以表示 HINs 中的语义信息。例如，图 4(a) 是一个 meta path，表示两部电影有共同的导演，而图 4(b) 是一个 meta graph，表示两部电影不仅有共同的导演，还有相同的演员。

▲ 图4 “元路径”与“元图”

Meta Path 这一概念已经被一些相关工作采用（如 HAN [8] 与 MAGNN [9] 就采用手工设计 meta paths 的方式利用语义信息）。然而，相比于 Meta Path，Meta Graph 通过灵活地结合多个路径，可以更好地表示细粒度的语义信息。因此，我们希望把 Meta Graph 和 GNN 的消息传播（message passing）框架结合在一起，并设计一个搜索空间来表示可能的 meta graphs。

搜索空间

我们将搜索空间定义为一个有向无环图（DAG）。这个 DAG 中的每个节点表示  GNN 在 message passing 过程中的一个中间状态。在第 个状态时，异质图中节点的表示向量为 。 表示输入的初始特征。DAG 中的每条边从一个旧的状态 出发指向一个新的状态 k，表示将 沿着异质网络中某种类型的边（候选的边类型的集合为 ）传播一次，得到的传播后的表示向量以相加的方式参与构成 。

以一个学术网络为例，我们在图中展示了一个状态数为 2 的搜索空间以及这个搜索空间中的一个实例。在这一例子中，从 到 ，以及从 到 ，异质网络中的信息都由文章类型的节点传播至作者，然而，这两次信息传播的效果是不同的，因为 中的文章类型的节点已经收集了会议类型的节点的信息。

▲ 图5 搜索空间

为了使搜索空间更加灵活，我们在候选的可供信息传播的边类型的集合中还加入了Identity （即 不进行信息传播）和 Zero （即 不参与构成 ）。进一步地，我们注意到，对于某些信息传播步骤，只有特定的边类型需要被包含在候选集合中。

对于图中的例子，当我们预测作者的研究领域时（即节点分类），只有作者的表示会参与到下游任务中，因此 中只需包含由文章指向作者，以及从机构指向作者这两种边类型。这样的限制可以帮助我们提前过滤掉搜索空间中不必要的选择。然而，对于含有丰富语义信息的异质网络，搜索空间仍然非常大，因此需要我们设计一个高效的搜索算法。

搜索算法

我们采用 one-shot 的思路，在搜索时引入额外的“结构参数” （区别于 GNN 自身的参数 ）来表示候选的各个边类型的重要程度。在 one-shot NAS 的框架下，搜索问题转化为一个 Bi-level 优化问题，实践中通常采取交替更新 和 的做法。然而，直接训练经过 加权混合后的超网络有两个潜在的问题。一是训练超网络不够高效，因为我们需要对每个候选的边类型都计算一次信息传播操作，然后再把它们加权相加。二是优化超网络的过程与最后测试时的实验设置不一致。

测试时我们只从超网络中导出一个最好的子模型（基于优化后的 ）从头训练，但优化超网络时不同的子模型可能会互相关联，导致 无法很好地反映每个子模型单独训练时的好坏。因此，我们提出了一个基于贪心策略的搜索算法，每轮迭代只从候选的信息传播操作中挑选一个参与计算，这样一方面提高了搜索效率，同时也使得优化后的超网络能更好地反映子模型的表现。算法的详细推导请参看原论文。

▲ 图6 搜索算法

实验结果

我们在节点分类任务和推荐任务上对我们的方法进行了测试，实验结果表明我们的方法可以取得比现有的为 HINs 设计的 GNNs 更好的效果。

 

▲ 图7 实验结果

我们比较了我们的搜索算法与其他搜索方法的搜索效率，结果表明我们的搜索算法显著地缩短了搜索时间，使得搜索耗时与从头训练一个单独的 GNN 模型相当。当我们从头训练搜索得到的模型时，其达到最好的验证集表现所需的时间比最好的基准方法 HGT 短得多，相比于最简单的结构 GCN，其大幅提高了表现且只需要很少的额外时间完成训练。这样的结果表明我们的方法可以很好地应用于大规模的异质图。

▲ 图8 搜索效率比较

▲ 图9 搜索出的“元图”

未来工作

最后，我们结合本组的相关研究简单谈一下未来工作。

自动化图神经网络近两年成为一个比较重要且热门的方向，本文主要探索了异质图上的元图搜索，这是异质图上的核心任务之一。后续的改进方向之一，就是将元图搜索和图神经网络的聚合算子搜索相结合。本组之前的工作，针对同质网络，提出了 可微图神经网络架构搜索  [13]，未来可以考虑将两者融合在一起，寻求在异质图上更为强大的图神经网络架构。

从知识图谱中挖掘逻辑规则是引领人工智能从感知走向认知的一个重要方向，区别于异质图的元路径和元图，图谱中的逻辑强调关系层面的复合推理，比如工作于+位于，有大概率推导出居住于的关系，由于关系种类的多样性，这种模式更难被挖掘。后续的改进方向之一，就是基于元图搜索的想法，结合图谱上递归结构搜索 [14]，在知识图谱中搜索逻辑模式，学习更高阶的知识，提升知识图谱对知识的表达能力。

合作机会

清华大学电子工程系博士后（水木学者计划）；第四范式实习生、研究员（需博士学位）。

有意者请垂询：qyaoaa@tsinghua.edu.cn

参考文献

[1] Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba. KDD, 2018.

[2] Graph Convolutional Neural Networks for Web-Scale Recommender Systems. KDD, 2018.

[3] Heterogeneous Network Representation Learning: A Unified Framework with Survey and Benchmark. TKDE, 2020.

[4] Neural Architecture Search: A Survey. JMLR, 2019.

[5] Graph neural networks: A review of methods and applications. AI Open, 2020.

[6] Meta-Graph Based Recommendation Fusion over Heterogeneous Information Networks. KDD, 2017.

[7] Semi-Supervised Classification with Graph Convolutional Networks. ICLR, 2017.

[8] Heterogeneous Graph Attention Network. WebConf, 2019.

[9] MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding. WebConf, 2020.

[10] PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks. VLDB, 2011.

[11] Heterogeneous Graph Transformer. WebConf, 2020.

[12] Understanding and Simplifying One-Shot Architecture Search. ICML, 2018.

[13] Search to aggregate neighborhood for graph neural network. ICDE, 2021.

[14] Interstellar: Searching Recurrent Architecture for Knowledge Graph Embedding. NeurIPS, 2020.