干货！Labeling Trick: 一个图神经网络多节点表示学习理论

点击蓝字

关注我们

AI TIME欢迎每一位AI爱好者的加入！

GNN 旨在学习单节点表示。当我们想要学习一个涉及多个节点的节点集表示（如链路表示）时，以往工作中的一个常见做法是将 GNN 学习到的多个单节点表示直接聚合成节点集的联合表示。在本文中，我们展示了这种方法的一个基本缺陷，即无法捕获节点集中节点之间的依赖关系，并论证了直接聚合单节点表示不能得到多节点集合的有效联合表示。然后，我们注意到之前一些成功的多节点表示学习工作，包括 SEAL、DE和 ID-GNN，都使用了节点标记。这些方法首先根据节点与目标节点集的关系在图中标记节点，然后再应用 GNN，并将标记图中获得的节点表示聚合为节点集表示。通过研究它们的内部机制，我们将这些节点标记技术统一为一个单一且最基本的形式，即labeling trick。我们证明，通过labeling trick，具有足够节点表达能力的 GNN 可以学习最具表达力的节点集表示，因此原则上可以解决节点集上的任何联合学习任务。一项重要的两节点表示学习任务——链接预测——的实验验证了我们的理论。我们的工作为使用 GNN 进行节点集上的联合预测任务奠定了理论基础。

本期AI TIME PhD直播间，我们邀请到北京大学人工智能研究院助理教授、博士生导师——张牧涵，为我们带来报告分享《Labeling Trick: 一个图神经网络多节点表示学习理论》。

张牧涵：

北京大学人工智能研究院助理教授、博士生导师，北京通用人工智能研究院（BIGAI）研究员，2021年国家优青（海外）项目获得者。主要研究方向为机器学习/深度学习和图神经网络的算法、理论、应用等。提出了图神经网络的多种经典算法，如图分类的SortPooling、链路预测的SEAL算法、矩阵补全的IGMC算法等。成果被多次写入图深度学习标准库，如PyTorch Geometric和DGL。2015年本科毕业于上海交通大学IEEE试点班，2019年于美国圣路易斯华盛顿大学获得计算机科学博士学位。2019-2021年期间曾担任Facebook AI研究科学家，参与开发Facebook内部大型图深度学习系统并应用于社交网络和广告推荐中。担任ICML 2022领域主席、IEEE BigData 2021副主席，并常年担任NeurIPS、ICML、ICLR、AAAI、IJCAI和TPAMI、TNNLS、TKDE、AOAS、JAIR等顶级会议和期刊的审稿人。

什么是多节点表示学习？多节点表示学习指的是我们要学习图中不止一个节点，而是一个节点集的表示。因为图神经网络是用于单节点表示学习的，当我们想要获得多节点表示的时候通常是把这些GNN学到的单节点表示聚合成一个多节点的表示。经过我们的研究，我们发现这种多节点表示的学习方法是不好的。我们也提出了一个方法——Labeling Trick，并证明了相关理论。

虽然多节点表示学习理论是通用的，但是我们选择link prediction（链路预测）这样一个双节点表示学习任务作为例子。

在一个不完全的网络中，link prediction预测两个节点之间是否会形成链路，即一个连边。它有很多现实应用，比如如今现实生活中的各种推荐系统。

传统的链路预测大多是根据启发式的方法，定义一些节点在网络中的相似度度量来预测链路。这些启发式的方法往往方便计算而且具有较好的可解释性。我们接下来看几个知名的启发式方法。

这也启发了我们用图神经网络直接学习图上的结构特征，而不是使用手工定义的那些特征。

这样就有了这两个知名的工作：VGAE/GAE 和 SEAL

自动的在链路周边学习和链路形成强关联的结构特征。
对于链路形成机制是没有假设的，因为是直接从邻近的节点结构进行学习。
SEAL达到了新的state-of-the-art 线路预测性能。

结果

我们可以看到SEAL和VGAE两种方法都是使用图神经网络来学习链路表示并进行预测，但是性能相差很多，我们接下来主要回答这个问题。

上图为两个食物链的网络，左图为陆地上的食物链网络，右图为海洋上的食物链网络。

这两个食物链网络是同构的。

问：海豹seal吃什么？远洋鱼or红松鼠
GNN无法区分海豹和红松鼠之间的链路与海豹和远洋鱼之间的链路
所以说GNN真的不适合链路预测任务么？

Labeling Trick节点标注技巧

定义：给定节点集S和图A，我们会在A的第三个维度上叠加一个diagonal labeling matrix L(S)得到一个新的A(S),即标注后的A。L(S)满足以下条件：

Main Theorem

如果Γ(i,A)是node i的structural representation，那么对节点集S和S’，以及使用labeling trick标注过的A(S)和A(S’)，我们聚合他们在标注后的A(S)得到的Γ(i,A(S))，作为节点集的表示。这可以保证我们学到了一个节点集S的structural representation。

解释：

我们不在之前为标注过的原始图A中去学习节点表示，而是在通过labeling trick标注过的A(S)中去学习节点表示。

然后我们将学到的节点表示聚合起来，得到的就是节点集的聚合表示，可以帮助我们解决一切节点集上的任务。

但是，如果我们在原始图A上学习节点表示得到的并不是节点集的结构表示，那么为什么我们在标注过的图上进行节点表示的聚合就可以得到节点集的结构表示呢？

How to implement labeling trick？

如何实现这种标注技巧

The SEAL Framework

比如（A,B）和（C,D）是一组training links，首先取一个local 子图对其进行距离标注。然后将标注后的子图feed给一个图神经网络，去训练一个链路的分类器。

Experiments

比较了Labeling Trick与Plain GAN（简单直接把两个节点链路表示聚合成链路表示）之间的关系，我们可以看出Labeling Trick在链路预测上体现出了极佳的性能，而且强于启发式方法。

Takeaway

如果直接聚合两个节点的表示，通常会得到一个不太好的链路表示
总结得出了Labeling Trick，即对图中所有节点进行标注，让target nodes得以与其他节点区分出来
在标注过后的图中聚合GNN学到的节点表示可以得到一个非常expressive的链路表示
SEAL就是实际使用了Labeling Trick来进行链路预测
加上Labeling Trick之后，GNN可以获得 state-of-the-art的链路预测性能
加上Labeling Trick之后，我们不必再去关注GNN的链路表示性能；保证我们只去关注如何提升节点的表示，因为Labeling Trick可以由好的节点表示自动转化成为好的链路表示

Recent work:将Labeling Trick用在子图的表示学习任务上