KDD'21 | 图神经网络如何建模长尾节点?

Tail-GNN: Tail-Node Graph Neural Networks

KDD 2021

01

—

目前，许多领域中的图在其节点度上都遵循长尾分布，即大多数节点为具有小度的尾结点。尽管图神经网络可以学习节点表征，但它们统一对待所有节点，而没有关注到大量的尾节点。同时，尾节点的结构信息（如链接信息）较少，从而导致性能较差。故本文提出了一种新颖的图神经网络：Tail-GNN，以提高尾结点嵌入的鲁棒性。图1展示了长尾节点的分布，以及尾节点缺失的链接。

02

—

相关定义

给定图 ={V， ，X}，对于每个节点v∈V，定义N _v 表示节点v的邻居节点集合，也被称作邻域，而|N _v |则为节点v的度。同时，定义V _head 与V _tail 分别表示头、尾结点。对于阈值K，尾结点的度不超过K，即V _tail ={v：|N _v |≤K}，而头结点则作为尾结点的补充，即V _head ={v：|N _v| ＞K}。本文将K视为预先设定的超参数。

03

—

可转移的邻域转化

为了增强尾节点的表征学习，本文提出了一种名为邻域转化的新概念，在此基础上，进一步设计了一种从头结点到尾节点的知识转移。具体如图2所示。

3.1 邻域转化

通常，节点与其邻居节点之间紧密的结构连接产生了它们之间的联系，特别地，GNN与其他基于图的方法都假定节点与其相邻节点相似。例如，如图2（a）所示，对v₀及其邻居，使用生物学关键词来描述，而对节点v₆，则使用计算机科学关键词来描述。本文利用转化操作对节点v与其邻域N_v之间的关系进行建模，以模拟邻域中缺失的信息。形式上，设h_v表示头节点v的节点嵌入向量，并设表示v的邻域N_v的嵌入向量，其可以通过对v的邻域嵌入向量进行池化操作来得到，可表示为：

其中，r_v为翻译向量，其可以被一个可学习模型预测，该模型在下部分会具体阐述。

3.2 基于头尾转移预测丢失的邻域信息

本文通过将邻域转化的知识从头节点转移到尾节点以发现缺失的邻域信息。

3.2.1 头节点的邻域

由于头节点在图中连接良好，故假设其邻域完整且有代表性，则邻域转化自然存在于头节点及其邻域内。因此，可直接学习模型以预测头节点的转化向量。

3.2.2 尾节点邻域

相反，由于各种原因，尾节点在结构上受到了限制，从而导致了一个小的可观测邻域，即在GNN中，尾节点的观测邻域可能不足以代表有意义的聚合。因此，必须找出尾节点缺失的邻域信息。具体来说，尾节点v的缺失信息，可被m_v表示，而m_v则由其理想邻域以及观测邻域N_v的嵌入向量之间的差异给定。表示为：

此处，理想邻域不仅包含观测邻域，还包含可以链接到v的节点，理想邻域与观测邻域以及缺失邻域之间的关系如图2(c)所示。

3.2.3 预测缺失信息

为了计算式2，需要首先预测未知的理想邻域表征。具体来说，可以对头节点和尾节点利用统一的转化模型，以得出它们的理想邻域。对于头节点，由于它的观测邻域已经是理想的，故只需学习预测式1中的转化向量r_v；而对于尾节点，则为转化模型应用预测模型以构造理想模型，从而将知识从头节点转移到尾节点。可表示为：

其中，转化向量r_v由从头节点学习得来的转化模型学习而得到。尾节点的缺失邻域则可表示为：

04

—

Tail-GNN

Tail-GNN依赖于上文可转移邻域转化概念，Tail-GNN的整体框架如图3所示。

4.1 实现邻域转化

4.1.1 对比策略

由上文所述，本文在Tail-GNN的每一层都采用了式1的转化策略。故第l层中头节点v的嵌入向量应表示为：

其中， 表示第l层中节点v的转化向量，其可以由共享模型构建。而则表示节点v在第l层的理想邻域表示，由于假设v为头节点，故 可由 （即同一层中节点v的观测邻域）近似得出，上式可被改写为：

另一方面，则利用尾节点作为头节点的对比，以便模型更精确地利用尾节点的邻域转化来预测缺失的信息。然而，头尾节点之间不存在一一对应的关系，为此，为了增强对比，本文人工生成了一些尾节点，具体操作可以通过从头节点随机删除一些链接来模拟实际尾节点。伪造的尾节点可以与相对应的头节点直接进行对比，从而增强对缺失邻域信息的预测及利用。

基于式2与式4中的概念，尾节点v（真节点或伪造节点）在l层的缺失邻域信息可被预测为：

4.1.2 局部化策略

本文不使用一个全局共享向量r来构建转化向量r _v ，而是如图3(b)部分所示，首先从一个可学习的共享向量r出发，并为每个节点v基于其上下文将r个性化为一个位置感知转化向量r _v 。给定第l层的全局共享向量r ^l ，上述操作可定义为：

其中，表示本文定义的个性化函数，包含了在第l层中的参数。可考虑缩放和移动来实现个性化操作。上式可改写为：

LEAKYReLU被用作激活函数，而所有的W都为一个可学习的权值矩阵，可表示为：

4.2 邻域聚合

由于本文假设头节点无缺失邻域信息，故头节点的邻域聚合可遵循式1，即直接聚合其观测邻域信息。

而对于尾节点，则需先基于式7得出尾节点的缺失邻域信息，然后通过同时考虑观测邻域以及缺失信息，对(l+1)层进行邻域聚合，表示为：

4.3 总体损失

4.3.1 任务损失

输出层的节点表示可以以端到端的方式使用，以最小化特定任务（如节点分类、链接预测）的损失。以节点分类为例，给定一组训练节点V _tr （包含头节点对应的伪造节点），任务损失可表示为：

其中，输出层 (ℓ为总层数)维度与种类数量相同，并且使用softmax函数作为激活函数。y _v 为单热向量，其对节点v的类别进行了编码。CrossENT为交叉熵函数，Θ包含了Tail-GNN中所有可学习的参数。

4.3.2 缺失信息约束的损失

由于假设头节点无损失信息，故需确保头节点的缺失信息近似于0，因此，本文提出如下损失函数来约束缺失信息。

v为头节点时，I _v =1，其他情况时，则I _v =0。

4.3.3 对抗约束的损失

为了使得节点表征更具有鲁棒性，本文使用了一个鉴别器D，以根据节点的输出判断其是头节点还是尾节点。同时，将Tail-GNN的输出层作为生成器，从而在学习过程中测试鉴别器。鉴别器的损失函数如下表示：

其中，σ为sigmoid函数，θ_d={W_d，b_d，w_d}包含了鉴别器D所有可学习的参数，λ_d为超参。

4.3.4 总体损失

最后，将所有损失进行集成，表示为：

其中，μ与η为超参数。

05

—

实验

本文使用的数据集如下表所示。

本文模型在尾节点分类任务上的性能如表2表3所示，其中，表2中本文模型以GCN作为基准模型，表3以其他GNN模型作为基准模型。

本文模型在链接任务上的性能则如表4所示。

本文同样进行了消融实验以及延展性实验，实验结果分别如图4图5所示

对阈值K取值的实验结果如表5所示，同时，本文也对头节点分类任务进行了实验，实验结果如表6。

06

—

总结

本文研究了图神经网络中的尾节点嵌入问题。本文首先提出了一个可转移邻域转化的新概念，以获取节点与其邻居之间的关系。然后，本文提出了一种新的模型Tail-GNN，以缩小头尾结点之间的差异，并提高尾节点嵌入的鲁棒性。在基准数据集上的大量实验表明，与基线相比，本文的Tail-GNN拥有最先进的性能。

原文地址：https://dl.acm.org/doi/pdf/10.1145/3447548.3467276