论文名称：Characterizing Long-Tail Categories on Graphs

摘要

长尾数据分布在许多现实世界网络中普遍存在，包括金融交易网络、电子商务网络和协作网络。尽管最近的发展取得了成功，但现有的研究主要集中在通过图增强或目标重加权来消除机器学习模型的偏见。然而，目前文献中缺乏提供理论工具来表征图中长尾类别行为并了解实际场景中的泛化性能。为了弥补这一空白，我们提出了第一个用于图中长尾分类的泛化界限，通过将问题形式化为多任务学习的方式，即每个任务对应于一个特定类别的预测。我们的理论结果表明，长尾分类的泛化性能主要受到所有任务的损失范围和任务总数的影响。基于理论发现，我们提出了一个新颖的通用框架 TAIL2LEARN，以提高图中长尾类别的性能。具体而言，我们从一个分层任务分组模块开始，该模块允许标记有限的类别从其他类别共享的相关信息中受益；然后，我们进一步设计了一个平衡对比学习模块，以平衡头部和尾部类别的梯度贡献。最后，对各种真实数据集进行的大量实验表明了 TAIL2LEARN 在捕捉图中长尾类别方面的有效性。

1 引言

图为建模各种关系数据提供了基本的数据结构，涵盖了从金融交易网络 $[10,48]$ 到电子商务网络 $[49,51]$，从社会科学 $[12,64]$ 到神经科学 $[4,9]$ 的广泛范围。图神经网络 (GNNs) 在节点分类任务上取得了出色的表现 $[1,66]$，因为它们能够从图结构化数据中学习表达丰富的表示。尽管取得了显著成功，GNNs 的性能主要归因于高质量和丰富的注释数据 [14, 18, 21, 56]。

然而，与理想情况下的基准数据集不同，许多高风险领域通常呈现出长尾分布，即少数头部类别 ${}^1$ (大多数类别) 已经得到充分研究并具有丰富数据，而大量尾部类别 (少数类别) 则研究不足且数据稀缺。例如，在金融交易网络中，少数头部类别对应于正常交易类型 (例如，信用卡支付、电汇)，而大量尾部类别可以代表各种欺诈交易类型 (例如，洗钱、合成身份交易)。尽管欺诈交易很少发生，但检测它们可能至关重要 [2, 43]。另一个例子是协作网络。如图 1 所示，Cora-Full 网络 [5] 包含基于研究领域的 70 个类别，其数据分布高度不平衡 (例如，在最小众领域有 15 篇论文，而在最流行领域有 928 篇论文)。复杂的数据和任务复杂性 (数据不平衡、大量类别) 结合有限的监督给 GNNs 带来了巨大挑战。

图 1：协作网络 (Cora-Full [5]) 中长尾分布的示意图，绿色和红色曲线显示了 GCN 和 TAIL2LEARN 对每个类别进行节点分类的平衡准确率 (bAcc) (%)。蓝色和黄色条表示未标记和已标记节点的类别频率。

尽管这很重要，但目前文献中缺乏提供理论基础来表征图中长尾类别行为并了解实际环境中的泛化性能。为了弥补这一空白，我们提供见解，并在长尾分类在图上的背景下确定了三个基本挑战。第一 (C1. 高度倾斜的数据分布)，数据表现出极度倾斜的类成员关系。因此，头部类别对学习目标的贡献更大，可以更好地被 GNNs 表征；尾部类别对目标的贡献较小，因此受到更高的系统误差的影响[65]。第二 (C2. 标签稀缺)，由于自然界尾部类别的稀缺性和多样性，注释尾部类别往往比注释头部类别更昂贵且耗时 [37]。更糟糕的是，从稀缺标签训练 GNNs 可能导致表示差异和不可避免的错误 $[50,68]$​，这加剧了从高度倾斜的数据分布中消除 GNN 的困难。

GNN 面临着高度倾斜的数据分布。第三点（C3. 任务复杂性）随着类别数量的增加，对支持区域 [17] 进行特征化的困难程度急剧增加。在低预测置信度的类别之间可能会遇到支持区域重叠的高风险 [33, 63]。为了处理长尾类别，现有文献主要集中在增强观察到的图 [40, 52, 67] 或重新权衡基于类别的损失函数 [42, 61]。尽管取得了一些成就，一个自然的研究问题是：我们是否可以通过从头部类和尾部类中学习更多知识来进一步提高整体性能？

为了回答上述问题，我们首次研究了长尾分类的泛化界限。关键思想是将长尾分类问题形式化为多任务学习的方式 [44]，即每个任务对应于预测一个特定类别。特别地，泛化界限是在所有任务的损失范围和任务总数方面。基于理论发现，我们提出了 TAIL2LEARN，一个通用学习框架，用于表征图中的长尾类别。具体而言，我们利用分层结构进行任务分组以解决 C2 和 C3，使得具有有限标签的类别能够从其他类别共享的相关信息中受益。此外，我们实现了一个平衡对比模块来解决 $\mathrm{C}$，有效平衡头部类别和尾部类别之间的梯度贡献。

总的来说，我们的贡献总结如下。

• 问题定义：我们对图中的长尾分类问题进行了形式化，并开发了一个名为长尾比率的新指标，用于表征长尾分布数据的特性。
• 理论：我们推导了图中长尾分类的第一个泛化界限，这启发了我们提出的框架。
• 算法：我们提出了一种名为 TAIL2LEARN 的新方法，通过分层任务分组提取跨类别的可共享信息，并平衡头部类别和尾部类别的梯度贡献。
• 评估：我们确定了六个用于图中长尾分类的真实数据集。我们通过与十个基线模型的比较系统评估了 TAIL2LEARN 的性能。结果表明了 TAIL2LEARN 的有效性，并验证了我们的理论发现。
• 可复现性：我们在 https:// anonymous.4open.science/r/Tail2Learn-CE08/ 上发布了我们的数据和代码。

本文的其余部分组织如下。在第 2 节中，我们介绍了初步和问题定义。在第 3 节中，我们推导了图中长尾分类的泛化界限，并介绍了我们提出的框架 TAIL2LEARN 的详细信息。第 4 节报告了实验结果和讨论。在第 5 节中，我们回顾了现有的相关文献。最后，在第 6 节中，我们总结了本文。

2 初步

在本节中，我们介绍了背景并给出了正式的问题定义。附录 A 中的表 4 总结了本文中使用的主要符号。我们使用普通字母表示标量 (例如，$\mu$ )，粗体小写字母表示向量 (例如，v)，粗体大写字母表示矩阵 (例如，X)。

(b)

图 2：两种长尾分布指标在 (a) 原始 Cora-Full 数据集的困难案例和 (b) 下采样 Cora-Full 数据集的简单案例之间的比较。我们观察到类不平衡比例无法很好地表征这两个数据集的任务复杂性，而长尾比率可以。

我们将图表示为 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$，其中 V = { v 1 , … , v n } \mathcal{V}=\left\{\mathbf{v}_{1}, \ldots, \mathbf{v}_{n}\right\} V={v1​,…,vn​} 表示节点集，$n$ 是节点数，$\mathcal{E}\subseteq \mathcal{V}\times \mathcal{V}$ 表示边集，$\mathrm{X}\in {\mathbb{R}}^{n\times d}$ 表示节点特征矩阵，$d$ 是特征维度。 A ∈ { 0 , 1 } n × n \mathrm{A} \in\{0,1\}^{n \times n} A∈{0,1}n×n 是邻接矩阵，其中 ${\mathbf{A}}_{ij}=1$ 表示在 $\mathcal{G}$ 中从 ${\mathbf{v}}_i$ 到 ${\mathbf{v}}_j$ 存在边 ${\mathbf{e}}_{ij}\in \mathcal{E}$，否则 ${\mathrm{A}}_{ij}=0$。接下来，我们简要回顾图神经网络和长尾分类。

图神经网络。图神经网络旨在生成捕获图特征和结构的嵌入空间中的低维表示。一般来说，图卷积网络 (GCN) [23] 层可以写为

$$\begin{array}{c}\mathbf{Z}=\sigma \left({\hat{\mathbf{D}}}^{-1/2}\hat{\mathbf{A}}{\hat{\mathbf{D}}}^{-1/2}\mathbf{XW}\right)\end{array}\text{\hspace{1em}(1)}$$
问题定义。我们考虑一个具有长尾分布的图 $\mathcal{G}$。虽然 [52] 中的类别不平衡比率考虑了数据分布的不平衡性，但忽视了长尾分类任务中的任务复杂性。随着类别数量的增加，分类任务的难度也随之增加。例如，我们从原始的 Cora-Full 数据集中对 7 个类别进行了下采样，如图 2 所示。尽管原始数据集和下采样数据集的类别不平衡比率保持不变（原始和下采样数据集的比率均为 0.02），但任务复杂性却有显著差异，即图 2 (a) 中的 70 个类别与图 2 (b) 中的 7 个类别。因此，我们引入了一种名为长尾度比的新型基于分位数的度量，用于共同量化长尾数据集的类别不平衡比率和任务复杂性。值得注意的是，所提出的度量是通用的，不限于图结构数据。长尾度比的正式定义如下：

定义 1（长尾度比）。假设我们有一个包含长尾类别的数据集 $\mathcal{D}$，其按照实例数量降序排列。长尾度比定义为

$${\mathrm{Ratio}}_{LT}(p)=\frac{Q(p)}{T-Q(p)}$$

其中 Q ( p ) = min ⁡ { y : Pr ⁡ ( y ≤ y ) = p , 1 ≤ y ≤ T } Q(p)=\min \{y: \operatorname{Pr}(\boldsymbol{y} \leq y)=p, 1 \leq y \leq T\} Q(p)=min{y:Pr(y≤y)=p,1≤y≤T} 是变量 $\mathcal{Y}$ 的顺序为 $p\in (0,1)$ 的分位数函数，$T$ 是类别数量。分子表示 $p$ 百分比实例所属的类别数量，分母表示剩余 $(1-p)$ 百分比实例所属的类别数量。

长尾度比实质上暗示了长尾分类的任务复杂性，并表征了 $\mathcal{D}$ 的两个属性：(1) 类成员倾斜度，(2) 类别数量。直观地说，数据分布的倾斜程度越高，比率就越低；任务的复杂性越高（即大量类别），长尾度比就越低。图 2 通过比较之前引入的长尾度比和类别不平衡比率 [52] 在原始 Cora 数据集和其下采样数据集上的案例研究。一般来说，我们观察到，与类别不平衡比率不同，长尾度比更好地表征了原始 Cora 数据集（${\mathrm{Ratio}}_{LT}(0.8)=1.09$）和其下采样数据集（${\mathrm{Ratio}}_{LT}(0.8)=1.33$）之间的差异。在我们的实现中，我们选择 $p=0.8$，遵循帕累托原则 [35]。

正如图 1 所示，长尾分类存在几个障碍。首先，高度倾斜的数据使得图模型偏向于头部类别，并且在尾部类别上表现不佳。此外，尾部类别分类的训练受到尾部类别标记实例的缺乏的影响。最后，这些方法未考虑长尾分布的复杂性，即当类别数量增加时，会遇到大量尾部类别，从而加剧任务的复杂性。大多数关于图上长尾分类的先前工作 [27, 36, 40, 52, 67] 集中于设计不同的增强和/或重新加权方法来解决这个问题，但缺乏理论分析。鉴于上述符号，我们正式定义问题如下。

问题 1. 基于图的长尾类别特征化。已知：(i) 具有低长尾度比 Ratio ${}_{LT}$ 的输入图 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$，(ii) 每个类别的少样本标注数据 $\mathbf{Y}$。

求解：在图 $\mathcal{G}$ 中准确预测头部和尾部类别节点的 $\hat{Y}$。

3 TAIL2LEARN 模型

在本节中，我们介绍了一个名为 TAIL2LEARn 的通用学习框架，旨在对图上的长尾类别进行特征化，并提高模型对尾部类别节点的性能。
我们首次提出以多任务学习的方式重新表述长尾分类问题。我们推导了一个泛化界限（第 3.1 节），这表明长尾分类的性能由两个因素主导：任务数量和所有任务的损失范围。前者启发我们构建了一个分层任务分组模块（第 3.2 节），它使得在不同任务之间共享信息成为可能。后者导致我们开发了一个平衡对比学习模块（第 3.2 节），用于平衡头部类别节点和尾部类别节点对整体目标函数的贡献。最后，我们提出了一个针对 TAIL2LEARN 的端到端优化算法（第 3.3 节）。

3.1 理论分析

在本小节中，我们提出了在图上的长尾类别设置下的第一个泛化保证。在本文中，我们将每个类别的分类视为图 $\mathcal{G}$ 上的一个学习任务 ${}^2$，其中 $\mathrm{X}$ 是节点特征，$\mathbf{y}$ 是标签，共有 $T$ 个任务和总共 $n$ 个节点。第 $t$ 个任务的训练集 D t = { ( x i t , y i t ) } i = 1 n t \mathcal{D}_{t}=\left\{\left(\mathbf{x}_{i}^{t}, y_{i}^{t}\right)\right\}_{i=1}^{n_{t}} Dt​={(xit​,yit​)}i=1nt​​ 包含 $n_t$ 个带标注的节点，${\mathrm{x}}_i^t$ 是类别 $t$ 中第 $i$ 个训练节点，对所有 $i$ 都有 $y_i^t=t$。注意不同任务包含在相同的特征空间中，因此我们有 ${\mathbf{x}}_i^t\in {\mathbb{R}}^d,\forall t,i.{\mathrm{X}}_t$ 表示类别 $t$ 中所有节点的 $d$ 维特征矩阵，并遵循概率测度 ${\mu }_t$，即 { X 1 , … , X T } ∼ ∏ t = 1 T ( μ t ) n t \left\{\mathbf{X}_{1}, \ldots, \mathbf{X}_{T}\right\} \sim \prod_{t=1}^{T}\left(\mu_{t}\right)^{n_{t}} {X1​,…,XT​}∼∏t=1T​(μt​)nt​。

我们工作的一个关键假设是任务相关性，即相关任务应该共享相似的模型参数。因此，同时学习相关任务有可能改善两个任务的性能。我们的目标是同时学习这些任务，以增强每个任务的整体性能。多任务学习模型的假设 $g$ 可以由 g = { f t } t = 1 T ∘ h g=\left\{f_{t}\right\}_{t=1}^{T} \circ h g={ft​}t=1T​∘h 表示，其中 $\circ$ 是函数组合，$g_t(x)=f_t\circ h(x)\equiv f_t(h(x))$ 表示每个分类任务的预测器。函数 $h:\mathrm{X}\to {\mathbb{R}}^K$ 是在不同任务之间共享的表示提取函数，$f:{\mathbb{R}}^K\to \mathbb{R}$ 是任务特定的预测器，$K$ 是隐藏层的维度。表示提取 $h$ 和预测器 $f_1,\dots ,f_T$ 的任务平均风险定义为 $ϵ\left(h,f_1,\dots ,f_T\right)$，相应的经验风险定义为 $\widehat{ϵ}\left(h,f_1,\dots ,f_T\right)$。

$$\begin{array}{c}ϵ\left(h,f_1,\dots ,f_T\right)=\frac{1}{T}\sum _{t=1}^T{\mathbb{E}}_{(\mathbf{X},y)\sim {\mu }_t}l\left(f_t(h(\mathbf{X})),\mathcal{Y}\right)\\ \widehat{ϵ}\left(h,f_1,\dots ,f_T\right)=\frac{1}{T}\sum _{t=1}^T\frac{1}{n_t}\sum _{i=1}^{n_t}l\left(f_t(h(\mathbf{X})),\mathcal{Y}\right)\end{array}\text{\hspace{1em}(2)(3)}$$

其中 $l(\cdot ,\cdot )$ 是损失函数。为了推导关于 $ϵ\left(h,f_1,\dots ,f_T\right)$ 和 $\widehat{ϵ}\left(h,f_1,\dots ,f_T\right)$ 的长尾分类的泛化误差，我们在定义 2 中正式定义了 $f_1,\dots ,f_T$ 的损失范围：

定义 2（损失范围）。在多任务学习中，$T$ 个预测器 $f_1,\dots ,f_T$ 的损失范围定义为所有任务中损失函数最低值和最高值之间的差异。

$$\begin{array}{rl}\mathrm{Range}\left(f_1,\dots ,f_T\right)& =\underset{t}{\max }\frac{1}{n_t}\sum _{i=1}^{n_t}l\left(f_t\left(h\left({\mathbf{x}}_i^t\right)\right),y_i^t\right)\\ & -\underset{t}{\min }\frac{1}{n_t}\sum _{i=1}^{n_t}l\left(f_t\left(h\left({\mathbf{x}}_i^t\right)\right),y_i^t\right)\end{array}\text{\hspace{1em}(4)}$$

其中 $l(\cdot ,\cdot )$ 是损失函数。对于节点分类的情况，$l(\cdot ,\cdot )$ 是交叉熵损失。

在长尾类别分布的情况下，通常在保持头部类别性能和提高尾部类别性能之间存在紧张关系 [65]。最小化头部类别的损失可能导致一个偏见模型，从而增加尾部类别的损失。在模型能够在头部任务上保持良好性能的前提下，控制损失范围可以提高尾部任务的性能，并提高模型的泛化性能。在这里，我们通过以下三个步骤推导了长尾类别的基于范围的泛化误差界限：(S1) 基于高斯复杂度的界限给出与损失相关的泛化误差界限；(S2) 基于 S1 中的与损失相关的误差界限和高斯复杂度属性给出假设 $g$ 相关的泛化误差界限；(S3) 基于在 S2 中获得的假设 $g$ 相关界限推导与表示提取 $h$ 和任务特定预测器 $f_1,\dots ,f_T$ 范围相关的泛化误差界限。根据 [30]，我们可以得到关于训练集 $\mathrm{X}$ 的基于高斯复杂度的界限如下。

引理 1（基于高斯复杂度的界限）。设 $\mathcal{F}$ 是函数类 $f:\mathrm{X}\to [0,1{]}^T$，${\mathbf{x}}_i^t$ 表示属于类别 $t$ 的第 $i$ 个实例。那么，对于所有 $f\in \mathcal{F}$，以大于 $1-\delta$ 的概率，我们有
$$\begin{array}{rl}& \frac{1}{T}\sum _t\left({\mathbb{E}}_{\mathbf{X}\sim {\mu }_t}\left[f_t(\mathbf{X})\right]-\sum _i\frac{1}{n_t}{f}_t\left({\mathbf{x}}_i^t\right)\right)\\ \le & \sum _t\left(\frac{\sqrt{2\pi }G(\mathbf{y})}{n_t}+\sqrt{\frac{9\ln (2/\delta )}{2n_t}}\right)\end{array}\text{\hspace{1em}(5)}$$

其中 ${\mu }_1,\dots ,{\mu }_T$ 是概率测度，$\mathbf{y}\subset {\mathbb{R}}^n$ 是通过 Y = { ( f t ( x i t ) ) : f t ∈ F } \mathcal{Y}=\left\{\left(f_{t}\left(\mathrm{x}_{i}^{t}\right)\right): f_{t} \in \mathcal{F}\right\} Y={(ft​(xit​)):ft​∈F} 获得的随机集合，$G$ 是高斯复杂度。

引理1表明，在多任务学习中，任务平均估计误差受到高斯复杂度的限制。根据引理2中给出的Lipschitz映像的高斯平均的关键性质，我们可以进入第二步，为图上长尾的假设 $g$ 相关泛化误差提供界限。

引理2（高斯复杂度的性质 [30]）。假设 $\mathcal{Y}\subseteq$ ${\mathbb{R}}^n$，$\varphi :\mathcal{Y}\to {\mathbb{R}}^m$ 是（欧几里得）Lipschitz连续的，Lipschitz常数为 $L$，我们有
$$\begin{array}{c}G(\varphi (\mathcal{Y}))\le LG(\mathcal{Y})\end{array}\text{\hspace{1em}(6)}$$
根据引理2，我们得到了式（19）中与假设 $g$ 相关的界限。接下来，我们进入第三步：根据引理3中呈现的高斯复杂度链规则，推导与 $h$ 和 $f_1,\dots ,f_T$ 相关的泛化界限。

引理3（高斯复杂度的链规则）。假设我们有 $\mathbf{y}\subseteq {\mathbb{R}}^n$，其（欧几里得）直径为 $D(\mathbf{Y})$。$\mathcal{F}$ 是一类函数 $f:\mathcal{Y}\to {\mathbb{R}}^m$，所有这些函数的Lipschitz常数最多为 $L(\mathcal{F})$。那么，对于任意 $y_0\in \mathcal{Y}$，

$G(\mathcal{F}(\mathbf{Y}))\le c_{1}L(\mathcal{F})G(\mathcal{Y})+c_{2}D(\mathbf{Y})\mathrm{Range}\left(f_1,\dots ,f_T\right)+G\left(\mathcal{F}\left(y_0\right)\right)$，

其中 $c_1$ 和 $c_2$ 是通用常数。

最终，在图上长尾类别的设定下，泛化误差界限如下定理1所示。

定理1（泛化误差界限）。给定表示提取函数 $h\in \mathcal{H}$ 和任务特定预测器 $f_1,\dots ,f_T\in$ $\mathcal{F}$，至少以概率 $1-\delta ,\delta \in [0,1]$，在多样本 ${\prod }_{t=1}^T{\mu }_t^{n_t}$ 的抽样中，我们有
$$\begin{array}{rl}\mathcal{E}-\hat{\mathcal{E}}& \le \sum _t(\frac{c_{1}LG(\mathcal{H}(\mathbf{X}))}{n_t}+\frac{c_2{\sup }_{h\in \mathcal{H}}\Vert h(\mathbf{X})\Vert \mathrm{Range}\left(f_1,\dots ,f_T\right)}{n_t}\\ & +\sqrt{\frac{9\ln (2/\delta )}{2n_t}})\end{array}\text{\hspace{1em}(7)}$$
其中 $\mathrm{X}$ 是节点特征，$T$ 是任务数量，$n_t$ 是任务 $t$ 中的节点数量，$c_1$ 和 $c_2$ 是通用常数。

引理1、引理3 和定理1 的证明见附录B。定理1 暗示了泛化误差界限由共享表示提取 $h$ 的高斯复杂度、任务特定预测器 $f_1,\dots ,f_T$ 的损失范围、总任务数以及它们的倒数之和上界。正则化任务数 $T$ 和损失范围 Range $\left(f_1,\dots ,f_T\right)$ 可以收紧这个上界，这促使我们在下一小节开发 TAIL2LEARN。

3.2 TAIL2LEaRn 框架

TAIL2LEARN 的概述如图3所示，包括两个主要模块：M1. 分层任务分组 和 M2. 长尾平衡对比学习。特别是，定理1中的理论分析启发我们，减少总任务数可以提高泛化能力。因此，为了缓解 C2（标签稀缺）和 C3（任务复杂性），M1 旨在最小化任务数量，并捕获跨任务共享信息以提高整体性能。定理1中的另一个关键信息是，减少所有任务的损失范围，同时确保在头部任务上的性能可以提高泛化能力。因此，在 M2 中，我们设计了一个长尾平衡对比损失，以平衡头部类别和尾部类别，并控制损失范围。此外，M2 也是 C1（高度倾斜的数据分布）的一个自然解决方案，因为它减少了头部类别的主导地位，并强调尾部类别的重要性。总的来说，M1 和 M2 在表征图上长尾类别的任务中是相互有益的。特别是，M1 确保了任务的准确原型嵌入，这有助于 M2 中的对比学习，而 M2 通过将相似节点聚合在一起并将不相似节点推开，有助于改进 M1 中学习到的节点嵌入。我们的消融研究（表3）充分证明它们在成功地在图上进行长尾分类中是必不可少的。

图3：提出的 TAIL2LEARN 框架，具有 $L$ 个任务分组层。

在接下来的小节中，我们将详细介绍 TAIL2LEARN 的两个模块。

M1. 分层任务分组。我们提出通过利用在一个类别中学到的信息来帮助训练另一个类别，以解决图上长尾类别的 C2（标签稀缺）和 C3（任务复杂性）。受多任务学习的启发，我们实现了任务分组 [44]，通过分层池化 [13, 25, 29, 41, 59] 跨不同任务共享信息。分层池化的核心思想是选择重要节点，并保留所选节点之间的原始连接作为边来生成粗化图。如图4所示，任务分组操作由两个步骤组成：（步骤1）我们将节点分组为几个任务，（步骤2）学习任务原型的嵌入。这个操作可以很容易地推广到第 $l^{\text{th }}$ 层，从而导致分层任务分组。

具体来说，我们首先通过 GCN 层（式（1））为每个节点生成低维节点嵌入向量 ${\mathbf{Z}}^{(1)}=\left({\mathbf{z}}_1^{(1)},\dots ,{\mathbf{z}}_n^{(1)}\right)$。接下来，我们将节点分组为任务（具有相同数量的类别），然后通过堆叠几个任务分组层将这些任务分组为超任务。根据 [13]，在第 $l^{\text{th }}$ 层，我们对图进行下采样，并学习前 $T^{(l)}$ 个节点。第 $l^{\text{th }}$ 任务分组层定义如下：
$$\begin{array}{rl}& \mathcal{I}=TOP-RANK\left(\mathrm{PROJ}\left({\mathbf{Z}}^{(l)}\right),T^{(l)}\right)\\ & {\mathrm{X}}^{(l+1)}={\mathbf{Z}}^{(l)}(\mathcal{I},:)\odot \left(\mathrm{PROJ}\left({\mathbf{Z}}^{(l)}\right)1_d^T\right)\\ & {\mathrm{A}}^{(l+1)}={\mathrm{A}}^{(l)}(\mathcal{I},\mathcal{I})\end{array}\text{\hspace{1em}(8)}$$
其中 $l=1,\dots L$，$\mathrm{PROJ}(\cdot ,\cdot )$ 是一个可微投影，将每个嵌入 ${\mathbf{z}}^{(l)}$ 映射到一个标量，函数 TOP-RANK 选择投影后值最大的节点。我们生成一个新图，其中选择的 $T^{(l)}$ 个节点代表任务的原型，其中 $T^{(l)}$ 代表任务数量。$\mathcal{I}$ 是表示所选节点的索引，并暗示了一个任务分组过程。所选节点之间的连接保持为新图的边，新的邻接矩阵和特征矩阵通过行和/或列提取构建。$1_d$ 表示一个 $d$ 维全一向量，$\odot$ 是逐元素矩阵乘法。随后的 GCN 层根据 ${\mathrm{X}}^{(l+1)}$ 和 ${\mathbf{A}}^{(l+1)}$ 从每个节点的一阶邻居聚合信息，然后输出新图的嵌入 ${\mathbf{Z}}^{(l+1)}$。值得注意的是，${\mathbf{Z}}^{(1)}$ 是节点嵌入，${\mathbf{Z}}^{(2)}$ 是对应于类别的任务原型的嵌入，${\mathbf{Z}}^{(l)}(l>2)$ 是超任务原型的嵌入。

任务数量 $T^{(l)}$ 代表任务分组的抽象级别，并随着任务分组层的加深而减少。在高级别层次 $(l>2)$，任务数量可能小于类别数量。通过控制 $T^{(l)}$，可以获取跨任务共享的信息，以减轻任务复杂性（随着类别数量的增加，对其进行表征变得困难）。同时，在深度抽象层次上，具有高级语义相似性的来自不同类别的节点可以分配到一个任务中。通过与同一超任务内的其他不同类别共享标签信息，可以缓解标签稀缺问题。如图3所示，我们考虑了2个头部类别（即类别2和4）和2个尾部类别（即类别1和3）。通过将类别1、类别2和类别3的原型分组到第3层的同一超任务中，类别1可用的标签从 $n_1$ 扩展到 $n_1+n_2+n_3$。

为了很好地捕捉任务的分层结构并在不同任务之间传播信息，我们需要恢复图的原始分辨率以执行节点分类。具体来说，我们堆叠与任务分组层相同数量的上采样层，将特征上采样以恢复图的原始分辨率。为了实现这一点，记录并应用在相应任务分组层中选择的节点位置，将节点放回其原始位置。传播规则的数学形式可以表示如下：
$$\begin{array}{c}{\mathbf{X}}^{(l+1)}=\mathrm{DIST}\left(0_{n\times d},{\mathbf{X}}^{(l+1)},\mathcal{I}\right)\end{array}\text{\hspace{1em}(9)}$$

图 4：M1的示意图，具有两个任务分组层。步骤1：首先将节点分组为四个任务（每个代表一个类）。步骤2：我们学习任务原型的嵌入。最后，通过反向传播更新节点嵌入。

M2. 长尾平衡对比学习。为了更好地处理长尾分类并解决 C1（高倾斜数据分布），我们引入了一种原则性的图对比学习算法，进一步规范 M1（分层任务分组）。图对比学习（GCL）[16,39,54,62,72] 在具有图结构数据的各种任务中取得了卓越的性能，并可用于缓解长尾分类。它旨在通过构建正负实例对来学习高效的图/节点表示。然而，许多现有的图对比学习模型是无监督的，即在训练中未利用标签信息。因此，通过 GCL 学习的表示聚类可能不对应于长尾类别。例如，在图 4 中，类别 1 可能只有很少的节点，在第 1 层的无监督学习中错误地合并到类别 2 中。这种错误对于长尾分类中的尾部类别是致命的。

在本文中，我们提出将监督信号纳入图对比学习中。通过从带有标签信息的任务分组中学习实现对比学习的嵌入，并且原型被限制为与类别相关。通过执行对比学习，我们将节点嵌入与其对应的原型拉在一起，并将它们推开离其他原型，以提高长尾分类的性能。特别地，与普通的 InfoNCE 不同，这里我们利用平衡对比学习[71] 来平衡不同类别的梯度贡献。对于第 $l^{th}$ 任务分组层，我们将第 $l$ 层中的节点分组为 $T^{(l+1)}$ 个任务，并基于节点嵌入 ${\mathbf{Z}}^{(l)}$ 和任务原型 ${\mathbf{Z}}^{(l+1)}$ 计算平衡对比损失。这里任务的原型是基于标签计算的，因此是特定于类别的。M1 的损失函数 ${\mathcal{L}}_{BCL}$ 的数学形式可以表示如下[3]：
$$\begin{array}{rl}& {\mathcal{L}}_{BCL}\left({\mathrm{z}}_i\right)=-\frac{1}{n_t}\times \\ & \sum _{j\in {\mathcal{V}}_t\backslash i}\log \frac{\exp \left({\mathrm{z}}_i\cdot {\mathrm{z}}_j/\tau \right)}{{\sum }_{1\le q\le T}\frac{1}{n_q+1}{\sum }_{k\in {\mathcal{V}}_q}\exp \left({\mathbf{z}}_i\cdot {\mathrm{z}}_k/\tau \right)}\end{array}\text{\hspace{1em}(10)}$$
其中我们假设 ${\mathbf{z}}_i$ 属于任务 $t$，这里 ${\mathcal{V}}_t$ 是第 $t^{th}$ 任务中的所有节点，包括原型 ${\mathrm{z}}_t^{(l+1)}$，$n_t$ 表示任务 $t$ 中的节点数，$z_k=z_k^{(l)}$ 表示第 $k^{th}$ 节点的嵌入，温度 $\tau$ 控制负节点的惩罚强度，并且我们将每个节点分配给最近的任务原型。根据 M1，我们将第一层的任务数 $T^{(1)}$ 设置为类别数 $T$。

因此，${\mathcal{L}}_{BCL}$ 从两个方面解决了长尾分类问题：(1) ${\mathcal{L}}_{BCL}$ 减少了头部类别的比例，突出了尾部类别的重要性。分母中的 $n_j+1$ 项对每个类别的节点进行平均，以便每个类别在优化过程中具有近似的贡献；(2) 添加了一组 $T$ 个原型，以获得更稳定的平衡对比学习优化。

此外，我们在恢复原始图上引入了监督对比损失。它使属于同一类别的节点对彼此靠近，而不属于同一类别的节点对远离。与使用任务分组的任务信息的 ${\mathcal{L}}_{BCL}$ 不同，${\mathcal{L}}_{SCL}$ 使用标签信息：
$$\begin{array}{c}{\mathcal{L}}_{SCL}\left({\mathbf{z}}_i\right)=-\frac{1}{n_t}\times \sum _{j\in {\mathcal{V}}_t\backslash i}\log \frac{\exp \left({\mathbf{z}}_i\cdot {\mathbf{z}}_j/\tau \right)}{{\sum }_{1\le q\le T}\frac{1}{n_q}{\sum }_{k\in {\mathcal{V}}_q}\exp \left({\mathbf{z}}_i\cdot {\mathbf{z}}_k/\tau \right)}\end{array}\text{\hspace{1em}(11)}$$
其中 ${\mathbf{z}}_i$ 属于类别 $t$，$n_t$ 表示类别 $t$ 中的节点数，$z_k$ 表示第 $k^{th}$ 节点的嵌入，$\tau$ 是温度。总而言之，M2 使用平衡对比损失和监督对比损失来平衡头部和尾部类别的性能，以解决高倾斜数据分布的问题。

定理 1 表明，通过（1）减少所有任务的损失范围 Range $\left(f_1,\dots ,f_T\right)$，以及（2）控制总任务数 $T$，可以改善图上长尾类别的泛化性能。下面我们给出一个推论，从理论上解释 TAIL2LEARN 中的两个模块是如何起作用的。

推论 1（TAIL2LEARN 的有效性）。考虑一个具有节点特征矩阵 $\mathrm{X}$ 的长尾分类问题，实例的总数为 $n$。对于 TAIL2LEARN 的第 $l^{th}$ 层，我们将节点分组为 $T^{(l)}$ 个任务，并且任务特定的预测器为 $f_1^{(l)},\dots ,f_T^{(l)}$。对于 $(l+1{)}^{\text{th }}$ 层，我们将节点分组为 $T^{(l+1)}$ 个任务，其中 $T^{(l+1)}<T^{(l)}$。此外，我们可以学习任务特定的预测器 $f_1^{(l+1)},\dots ,f_T^{(l+1)}$，使得 Range $\left(f_1^{(l+1)},\dots ,f_T^{(l+1)}\right)<\mathrm{Range}\left(f_1^{(l)},\dots ,f_T^{(l)}\right)$。那么我们有，$(l+1{)}^{\text{th }}$ 层的误差上界小于 TAIL2LEARN 中给出的 $l^{\text{th }}$ 层的误差上界，即

${\sum }_t(\frac{c_{1}LG(\mathcal{H}(\mathbf{X}))}{n_t^{(l+1)}}+\frac{c_2{\sup }_{h\in \mathcal{H}}\Vert h(\mathbf{X})\Vert \mathrm{Range}\left(f_1^{(l+1)},\dots ,f_T^{(l+1)}\right)}{n_t^{(l+1)}}$

$+\sqrt{\frac{9\ln (2/\delta )}{2n_t^{(l+1)}}})\le {\sum }_t(\frac{c_{1}LG(\mathcal{H}(\mathbf{X}))}{n_t^{(l)}}$

$+\frac{c_2{\sup }_{h\in \mathcal{H}}\Vert h(\mathbf{X})\Vert \mathrm{Range}\left(f_1^{(l)},\dots ,f_T^{(l)}\right)}{n_t^{(l)}}+\sqrt{\frac{9\ln (2/\delta )}{2n_t^{(l)}}})$

其中共享表示提取为 $h\in \mathcal{H}$。第 $l^{th}$ 层中第 $t^{\text{th }}$ 类别的实例数为 $n_t^{(l)}$，第 $(l+1)$ 层中第 $t^{\text{th }}$ 类别的实例数为 $n_t^{(l+1)}$，${\sum }_t{n}_t^{(l)}={\sum }_t{n}_t^{(l+1)}=n$。

证明见附录 B。

备注：推论 1 从理论上证明了 TAIL2LEARn 的有效性。我们的算法通过减少 M1 中的任务数和控制 M2 中的损失范围 Range $\left(f_1,\dots ,f_T\right)$，在图上长尾分类中实现了显著改进的泛化误差上界。

3.3 优化

总体上，训练过程的目标是最小化节点分类损失（用于少样本标注数据）、无监督平衡对比损失（用于每层的任务组合）和监督对比损失（用于类别）。节点分类损失定义如下：
$$\begin{array}{c}{\mathcal{L}}_{NC}=\sum _{i=1}^T{\mathcal{L}}_{CE}(g(\mathcal{G}),\mathbf{y})\end{array}\text{\hspace{1em}(13)}$$
其中 ${\mathcal{L}}_{CE}$ 是交叉熵损失，$\mathcal{G}$ 表示带有少样本标记节点的输入图，$\mathcal{Y}$ 表示标签。然后整体损失函数可以写成如下形式：
$$\begin{array}{c}{\mathcal{L}}_{\text{total }}={\mathcal{L}}_{NC}+\gamma \ast \left({\mathcal{L}}_{BCL}+{\mathcal{L}}_{SCL}\right)\end{array}\text{\hspace{1em}(14)}$$
其中 $\gamma$ 平衡三个项的贡献。

TAIL2LEARN 的伪代码见附录 C 中的算法 1。给定一个带有少样本标签信息 $\mathcal{Y}$ 的输入图 $\mathcal{G}$，我们提出的 TAIL2LEARN 框架旨在预测图 $\mathcal{G}$ 中未标记节点的 $\hat{y}$。我们在步骤 1 中初始化所有任务分组、反池化层和分类器。步骤 4-6 对应任务分组过程：我们生成下采样图并使用 GCNs 计算节点表示。然后步骤 7-9 对应反池化过程：我们恢复原始图分辨率并使用 GCNs 计算节点表示。在步骤 10 中，在任务分组和反池化层之间的跳跃连接后，使用 MLP 计算预测。最后，在步骤 11 中，通过最小化目标函数训练模型。在步骤 13 中，基于训练好的分类器，我们返回图 $\mathcal{G}$ 中的预测标签 $\hat{y}$。

4 实验

在本节中，我们评估了 TAIL2LEARN 在六个基准数据集上的有效性。TAIL2LEARN 相对于几种最先进的基线表现出卓越的性能。我们通过消融研究展示了 TAIL2LEARN 每个组件的必要性。我们还在附录 G 中报告了 TAIL2LEARN 的参数和复杂性敏感性，表明 TAIL2LEARN 在进行最小调整的情况下实现了令人信服的性能，并且具有可扩展性。

4.1 实验设置

对比基线

我们将TAIL2LEARN与以下五种不平衡分类方法和五种基于GNN的长尾分类方法进行比较。基线的详细信息在附录E中进一步描述。

• 不平衡分类方法：Origin（即GCN [24]）、Oversampling [6]、Re-weighting [60]、SMOTE [7]和Embed-SMOTE [3]是五种经典的不平衡分类模型。
• 基于GNN的长尾分类方法：GraphSMOTE的两个流行变体[67]（GraphSMOTE ${}_T$ 和GraphSMOTE ${}_O$ ）、GraphMixup [52]、ImGAGN [40]和LTE4G [61]是五种最先进的基于GNN的长尾分类模型。

实现细节：对于TAIL2LEARN的评估，我们在高度长尾分布下进行节点分类，使用Adam [22]作为优化器。我们使用10个不同的随机种子运行所有实验，并报告评估指标以及标准偏差。参数设置包含在附录F中。

考虑到长尾类成员分布，平衡准确率（bAcc）、Macro-F1和几何平均数（G-Means）被用作评估指标，同时准确率（Acc）也作为传统评估指标报告。值得注意的是，对于AmazonClothing和Amazon-Electronics，我们保持每个类别的节点数相同作为测试实例，因此bAcc和Acc的值相同。

4.2 性能分析

整体评估。我们将TAIL2LEARN与十种基线方法在六个真实图上进行比较，节点分类的性能报告在表1和表2中。总体而言，我们有以下观察：（1）TAIL2LEARN在各种长尾设置下始终表现良好，特别是在严格的长尾设置下（例如，当长尾比率约为0.25时）优于其他基线方法，这证明了我们模型的有效性和泛化能力。更具体地说，以Amazon-Electronics数据集（共167个类别，前33个类别包含总实例的80%）为例，我们模型在bAcc（Acc）上比第二好的模型（LTE4G）提高了12.9%。这意味着TAIL2LEARN不仅可以解决高度倾斜的数据，还可以捕捉大量的类别。（2）经典的长尾学习方法表现最差，因为它们忽略了图结构信息，只在特征空间中进行过采样或重新加权。TAIL2LEARN在自然数据集（BlogCatalog）上将bAcc提高了高达36.1%，在手动处理的数据集（Amazon-Clothing）上将其提高了71.0%，相比于经典的长尾学习方法。（3）基于GNN的长尾学习方法在除了Email数据集之外的情况下表现第二好，这表明在捕获或传输图拓扑知识方面是有益的，但这些模型忽略了大量的类别。特别是，由于ImGAGN只考虑高度倾斜的分布，随着类别数量的增加（从Wiki到Cora-Full），模型变得不太有效。我们的模型在自然数据集（BlogCatalog）上比这些基于GNN的方法提高了高达14.0%，在手动处理的数据集（Amazon-Electronics）上提高了高达12.9%。值得注意的是，所有基于GNN的方法在Email图上失败，而TAIL2LEARN仍然表现最佳。

表1：在长尾比率${\mathrm{Ratio}}_{LT}(0.8)\approx 0.25$的半合成长尾数据集上不同方法在节点分类任务中的比较。

表2：在自然数据集上不同方法在节点分类任务中的比较。

各类别性能。为了观察我们模型在长尾分类中的表现，在图1中，我们绘制了每个类别上的模型性能（bAcc）。我们发现TAIL2LEARN在尾部类别上优于原始GCN方法（未考虑长尾类成员分布），特别是在尾部类别上。此外，我们提出的长尾比率在这六个长尾数据集中反映了与类别不平衡比率类似的趋势。然而，由于它考虑了总类别数，长尾比率可以更准确地衡量长尾类成员分布。

4.3 消融研究

表3展示了考虑以下因素时的节点分类性能：（a）完整的TAIL2LEARN；（b）考虑分层长尾类别分组和节点分类损失；以及（c）仅考虑节点分类损失。由于篇幅限制，我们在本节中使用Cora-Full进行说明。从结果中，我们得出几个有趣的观察：（1）长尾平衡对比学习模块导致bAcc提高了1.9%，显示了它在通过确保准确的节点嵌入来改善长尾分类方面的优势$((a)>(b))$。 （2）分层任务分组有助于模型更好地跨任务共享信息，在Cora-Full上取得了高达3.2%的显著改进$((b)>(c))$。

表3：TAIL2LEARN各组件的消融研究。

4.4 参数和复杂性分析

超参数分析。我们研究了TAIL2LEARN的七个超参数：(1)平衡三个损失的权重$\gamma$；(2)M1中平衡对比损失的温度$\tau$；(3)使用一阶GCN还是普通GCN；(4)GCN中的激活函数；(5)隐藏维度的数量；(6)dropout率；以及(7)分层图神经网络的结构，包括深度和任务数量$k$。对于前两个重要超参数的敏感性分析见附录G中的图5。图中显示bAcc（z轴）的波动小于5%。当权重$\gamma$和温度$\tau$变大时，bAcc略有降低。其余五个超参数的分析结果见图6。总体而言，我们发现TAIL2LEARN在广泛范围内是可靠的，对超参数不敏感。

复杂性分析。我们报告了TAIL2LEARN和GCN的运行时间。为了更好地展示性能，我们在逐渐增加的图大小上运行实验，即从1,000到30,000个节点。从附录G中的图7中，我们可以看到我们模型的运行时间是线性的。

5 相关工作

长尾问题。数据集的长尾分布在现实世界的应用中很常见，其中少数类（即头部类）拥有大部分样本点，而其他类（即尾部类）只与少数样本相关[65]。许多不同研究领域的任务都面临这个问题，例如医学图像诊断[19]、计算机视觉中的分类[20,45]和推荐[8, 58]，并且有一些工作专注于解决长尾问题$[6,7,11,26,60,70]$。在数据级方法中，普通过采样方法$[6,26]$通过复制现有的少数类样本来解决这个问题。然而，这可能导致过拟合，因为没有引入额外信息。2002年，Chawla等人[7]提出了SMOTE，通过特征插值尾部类的样本与最近邻的样本生成新样本。在算法级方法中，成本敏感方法$[11,60,70]$引入不同的成本矩阵，为特定类别的样本分配不同的错误分类惩罚。然而，先前绝大多数的工作集中在独立同分布（i.i.d.）数据上，这不能直接应用于图数据。

最近，一些关于图上长尾分类的相关工作[27, 28, 36, 40, 42, 52, 61, 67]引起了关注。2021年，赵等人[67]提出了第一个名为GraphSMOTE的工作，考虑了图上节点类别不平衡。它通过在原始图上预训练的边生成器插值尾部节点嵌入并生成边来扩展SMOTE到图结构数据。GraphMixup [52]是一个基于混合的框架，同时在端到端的方式中实现三级混合（特征、边和标签）。ImGAGN [40]是一种基于对抗学习的方法。它使用生成器模拟少数节点和拓扑结构，然后使用鉴别器区分真实和虚假节点，以及少数和多数节点。然而，图上长尾类成员方法通常缺乏理论基础。它们在类别不平衡设置下进行实验：对于类别不平衡学习，类别数量可能较少，少数节点的数量可能不少；但对于长尾学习，类别数量较多，尾部节点稀缺。在这里，我们考虑节点类别的长尾分布度量，并在长尾数据集上进行实验。

6 结论

本文研究了图上的长尾分类问题，旨在提高头部和尾部类别的性能。通过将这个问题建模为多任务学习的方式，我们提出了第一个由所有任务的损失范围和任务总数主导的泛化界。基于理论发现，我们还提出了TAIL2LEARN。它是一个通用的框架，包含两个主要模块：M1. 分层任务分组来解决C2（标签稀缺）和C3（任务复杂性）；M2. 长尾平衡对比学习来解决C1（高度倾斜的数据分布）。在六个真实世界的数据集上进行了大量实验证明，TAIL2LEARN始终优于最先进的基线模型，证明了我们的模型在捕捉图上的长尾类别方面的有效性。

可重现性：我们已经在https://anonymous.4open.science/r/Tail2Learn-CE08/上发布了我们的代码和数据。

A 符号和注释

这里给出了本文中的主要符号和注释。

表4：符号和注释。

符号	描述
$\mathcal{G}$	输入图。
$\mathcal{V}$	$\mathcal{G}$ 中的节点集合。
$\mathcal{E}$	$\mathcal{G}$ 中的边集合。
$\mathrm{X}$	$\mathcal{G}$ 的节点特征矩阵。
$\mathrm{Z}$	$\mathcal{G}$ 中的节点嵌入。
$\mathrm{A}$	$\mathcal{G}$ 的邻接矩阵。
$\mathbf{y}$	$\mathcal{G}$ 中的标签集合。
$n$	节点数 $|\mathcal{V}|$。
$T$	节点类别数。
比率 $LT$	长尾比率。

B 定理的证明

引理1（基于高斯复杂度的界）。设 $\mathcal{F}$ 是一个函数类 $f:\mathrm{X}\to [0,1{]}^T$，${\mathbf{x}}_i^t$ 表示属于类别 $t$ 的第 $i$ 个实例。那么，对于所有 $f\in \mathcal{F}$，以概率大于 $1-\delta$，我们有
$$\begin{array}{rl}& \frac{1}{T}\sum _t\left({\mathbb{E}}_{\mathbf{X}\sim {\mu }_t}\left[f_t(\mathbf{X})\right]-\sum _i\frac{1}{n_t}{f}_t\left({\mathbf{x}}_i^t\right)\right)\\ \le & \sum _t\left(\frac{\sqrt{2\pi }G(\mathbf{y})}{n_t}+\sqrt{\frac{9\ln (2/\delta )}{2n_t}}\right)\end{array}\text{\hspace{1em}(5)}$$
其中 ${\mu }_1,\dots ,{\mu }_T$ 是概率测度，$\mathbf{Y}\subset {\mathbb{R}}^n$ 是由 Y = { ( f t ( x i t ) ) : f t ∈ F } \mathcal{Y}=\left\{\left(f_{t}\left(\mathrm{x}_{i}^{t}\right)\right): f_{t} \in \mathcal{F}\right\} Y={(ft​(xit​)):ft​∈F} 得到的随机集合，$G$ 是高斯复杂度。

证明。首先，我们考虑一个特殊情况，令 $T=1$，我们有 ${\mathbb{E}}_{\mathbf{X}\sim {\mu }_t}\left[f_t(\mathbf{X})\right]-{\sum }_i\frac{1}{n_t}{f}_t\left({\mathbf{x}}_i^t\right)\le \frac{\sqrt{2\pi }G(\mathbf{y})}{n_t}+\sqrt{\frac{9\ln (2/\delta )}{2n_t}}$，根据[30]。接下来，我们推广它并对 $t$ 进行求和操作。然后我们完成证明。

引理2（高斯复杂度的性质 [30]）。假设 $\mathcal{Y}\subseteq$ ${\mathbb{R}}^n$，$\varphi :\mathcal{Y}\to {\mathbb{R}}^m$ 是（欧几里得）利普希茨连续的，利普希茨常数为 $L$，我们有
$$\begin{array}{c}G(\varphi (\mathcal{Y}))\le LG(\mathbf{Y})\end{array}\text{\hspace{1em}(6)}$$
引理3（高斯复杂度的链式规则）。假设我们有 $\mathbf{Y}\subseteq {\mathbb{R}}^n$，其（欧几里得）直径为 $D(\mathcal{Y})$。$\mathcal{F}$ 是一个函数类 $f:\mathbf{y}\to {\mathbb{R}}^m$，其中所有函数的利普希茨常数最多为 $L(\mathcal{F})$。那么，对于任意 $y_0\in y$，

$G(\mathcal{F}(\mathbf{Y}))\le c_{1}L(\mathcal{F})G(\mathbf{Y})+c_{2}D(\mathbf{Y})$ Range $\left(f_1,\dots ,f_T\right)+G\left(\mathcal{F}\left(y_0\right)\right)$，

其中 $c_1$ 和 $c_2$ 是通用常数。

证明。令
$$\begin{array}{c}R(\mathcal{F})=\underset{\mathbf{y},{\mathbf{y}}^{\prime }\in \mathcal{Y},\mathbf{y}\ne {\mathbf{y}}^{\prime }}{\sup }\mathbb{E}\underset{f\in \mathcal{F}}{\sup }\frac{⟨\gamma ,l\left(f(\mathbf{y})-f\left({\mathbf{y}}^{\prime }\right)\right)⟩}{\Vert \mathbf{y}-{\mathbf{y}}^{\prime }\Vert }\end{array}\text{\hspace{1em}(15)}$$
其中 $\gamma$ 是独立标准正态变量的向量。然后根据 Rademacher 复杂度的定义和[30]中给出的链式规则，我们有
$$\begin{array}{c}G(\mathcal{F}(\mathcal{Y}))\le c_{1}L(\mathcal{F})G(\mathcal{Y})+c_{2}D(\mathcal{Y})R(\mathcal{F})+G\left(\mathcal{F}\left(y_0\right)\right)\end{array}\text{\hspace{1em}(16)}$$
其中 $c_1$ 和 $c_2$ 是常数。此外，
$$\begin{array}{rl}& \underset{\mathbf{y},{\mathbf{y}}^{\prime }\in \mathcal{Y},\mathbf{y}\ne {\mathbf{y}}^{\prime }}{\sup }\mathbb{E}\underset{f\in \mathcal{F}}{\sup }\frac{⟨\gamma ,l\left(f(\mathbf{y})-f\left({\mathbf{y}}^{\prime }\right)\right)⟩}{\Vert \mathbf{y}-{\mathbf{y}}^{\prime }\Vert }\\ \le & \underset{\mathbf{y},{\mathbf{y}}^{\prime }\in \mathcal{Y},\mathbf{y}\ne {\mathbf{y}}^{\prime }}{\sup }\mathbb{E}[\underset{f\in \mathcal{F}}{\sup }⟨\gamma ,l(f(\mathbf{y})-y))⟩-\underset{f\in \mathcal{F}}{\sup }⟨\gamma ,l\left(f\left({\mathbf{y}}^{\prime }\right)-y^{\prime }\right))⟩]\\ \le & \underset{\mathbf{y},{\mathbf{y}}^{\prime }\in \mathcal{Y},\mathbf{y}\ne {\mathbf{y}}^{\prime }}{\sup }\left[\frac{1}{n}\sum l(f(h(\mathbf{X})),\mathbf{y})-\frac{1}{n}\sum l\left(f\left(h\left({\mathbf{X}}^{\prime }\right)\right),{\mathbf{y}}^{\prime }\right)\right]\\ \le & \underset{t}{\max }\frac{1}{n_t}\sum _{i=1}^{n_t}l\left(f_t\left(h\left({\mathbf{x}}_i^t\right)\right),y_i^t\right)-\underset{t}{\min }\frac{1}{n_t}\sum _{i=1}^{n_t}l\left(f_t\left(h\left({\mathbf{x}}_i^t\right)\right),y_i^t\right)\end{array}\text{\hspace{1em}(17)}$$
然后我们完成证明。

定理1（泛化误差界）。给定表示提取函数 $h\in \mathcal{H}$ 和任务特定的预测器 $f_1,\dots ,f_T\in$ $\mathcal{F}$，以至少 $1-\delta ,\delta \in [0,1]$ 的概率，在多样本 ${\prod }_{t=1}^T{\mu }_t^{n_t}$ 的抽样中，我们有
$$\begin{array}{rl}\mathcal{E}-\hat{\mathcal{E}}& \le \sum _t(\frac{c_{1}LG(\mathcal{H}(\mathbf{X}))}{n_t}+\frac{c_2{\sup }_{h\in \mathcal{H}}\Vert h(\mathbf{X})\Vert \mathrm{Range}\left(f_1,\dots ,f_T\right)}{n_t}\\ & +\sqrt{\frac{9\ln (2/\delta )}{2n_t}})\end{array}\text{\hspace{1em}(7)}$$
其中 $\mathrm{X}$ 是节点特征，$T$ 是任务数，$n_t$ 是任务 $t$ 中的节点数，$c_1$ 和 $c_2$ 是通用常数。

证明。根据引理1，我们有
$$\begin{array}{c}\mathcal{E}-\hat{\mathcal{E}}\le \sum _t\left(\frac{\sqrt{2\pi }G(S)}{n_t}+\sqrt{\frac{9\ln (2/\delta )}{2n_t}}\right)\end{array}\text{\hspace{1em}(18)}$$
其中 S = { ( l ( f t ( h ( X i t ) ) , Y i t ) ) : f t ∈ F S=\left\{\left(l\left(f_{t}\left(h\left(X_{i}^{t}\right)\right), Y_{i}^{t}\right)\right): f_{t} \in \mathcal{F}\right. S={(l(ft​(h(Xit​)),Yit​)):ft​∈F and $h\in \mathcal{H}\}\subseteq {\mathbb{R}}^n$。根据损失函数 $l(\cdot ,\cdot )$ 的利普希茨性质和收缩引理2，我们有 $G(S)\le G\left(S^{\prime }\right)$，其中 S ′ = { ( f t ( h ( X i t ) ) ) : f t ∈ F S^{\prime}=\left\{\left(f_{t}\left(h\left(X_{i}^{t}\right)\right)\right): f_{t} \in \mathcal{F}\right. S′={(ft​(h(Xit​))):ft​∈F and $h\in \mathcal{H}\}\subseteq {\mathbb{R}}^n$。然后
$$\begin{array}{c}\mathcal{E}-\hat{\mathcal{E}}\le \sum _t\left(\frac{\sqrt{2\pi }G\left(S^{\prime }\right)}{n_t}+\sqrt{\frac{9\ln (2/\delta )}{2n_t}}\right).\end{array}\text{\hspace{1em}(19)}$$
回顾一下 $\mathcal{H}(\mathrm{X})\subseteq {\mathbb{R}}^{Kn}$ 的定义为
$$\begin{array}{c}\mathcal{H}(\mathbf{X})=\left\{\left(h_k\left(X_i^t\right)\right):h\in \mathcal{H}\right\},\end{array}\text{\hspace{1em}(20)}$$
并定义一个函数类 ${\mathcal{F}}^{\prime }:{\mathbb{R}}^{Kn}\to {\mathbb{R}}^n$，其中
$$\begin{array}{c}{\mathcal{F}}^{\prime }=\left\{y\in {\mathbb{R}}^{Kn}\mapsto \left(f_t\left(y_i^t\right)\right):f_1,\dots ,f_T\in \mathcal{F}\right\}.\end{array}\text{\hspace{1em}(21)}$$
我们有 $S^{\prime }={\mathcal{F}}^{\prime }(\mathcal{H}(\mathrm{X}))$。根据引理3，对于通用常数 $c_1^{\prime }$ 和 $c_2^{\prime }$，我们有
$$\begin{array}{rl}G\left(S^{\prime }\right)& \le c_1^{\prime }L\left({\mathcal{F}}^{\prime }\right)G(\mathcal{H}(\mathbf{X}))+c_2^{\prime }D(\mathcal{H}(\mathbf{X}))\mathrm{Range}\left(f_1^{\prime },\dots ,f_T^{\prime }\right)\\ & +\underset{y\in Y}{\min }G(\mathcal{F}(y)).\end{array}\text{\hspace{1em}(22)}$$
我们现在对上述右侧的各项进行界定。取 $y,y^{\prime }\in {\mathbb{R}}^{Kn}$，其中 y = { y i t } y=\left\{y_{i}^{t}\right\} y={yit​}，$y_i^t\in {\mathbb{R}}^K$， y ′ = { y i t ′ } y^{\prime}=\left\{y_{i}^{t \prime}\right\} y′={yit′​}，$y_i^{t\prime }\in {\mathbb{R}}^K$。那么对于 $f_1,\dots ,f_T\in \mathcal{F}$，我们有
$$\begin{array}{rl}{\Vert f(y)-f\left(y^{\prime }\right)\Vert }^2& =\sum {\left(f_t\left(y_i^t\right)-f_t\left(y_i^{t\prime }\right)\right)}^2\\ & \le L^2\sum {\Vert y_i^t-y_i^{t\prime }\Vert }^2=L^2{\Vert y-y^{\prime }\Vert }^2\end{array}\text{\hspace{1em}(23)}$$
因此 $L\left({\mathcal{F}}^{\prime }\right)\le L$。接下来，我们取 $y_0=0$，则 (22) 中的最后一项消失，因为对于所有 $f\in \mathcal{F}$，我们有 $f(0)=0$。代入 (22) 并使用 $G(S)\le G\left(S^{\prime }\right)$，我们有
$$\begin{array}{c}G(S)\le c_1^{\prime }LG(\mathcal{H}(\mathbf{X}))+c_2^{\prime }\sqrt{T}D(\mathcal{H}(\mathbf{X}))\text{ Range }\left(f_1,\dots ,f_T\right)\end{array}\text{\hspace{1em}(24)}$$
最后，我们界定 $D(\mathcal{H}(\mathbf{X}))\le 2{\sup }_h\Vert h(\mathbf{X})\Vert$，代入 (18)，证明完成。
${\sum }_t(\frac{c_{1}LG(\mathcal{H}(\mathbf{X}))}{n_t^{(l+1)}}+\frac{c_2{\sup }_{h\in \mathcal{H}}\Vert h(\mathbf{X})\Vert \mathrm{Range}\left(f_1^{(l+1)},\dots ,f_T^{(l+1)}\right)}{n_t^{(l+1)}}$

$+\sqrt{\frac{9\ln (2/\delta )}{2n_t^{(l+1)}}})\le {\sum }_t(\frac{c_{1}LG(\mathcal{H}(\mathbf{X}))}{n_t^{(l)}}$

$+\frac{c_2{\sup }_{h\in \mathcal{H}}\Vert h(\mathbf{X})\Vert \mathrm{Range}\left(f_1^{(l)},\dots ,f_T^{(l)}\right)}{n_t^{(l)}}+\sqrt{\frac{9\ln (2/\delta )}{2n_t^{(l)}}})$

其中，共享表示提取为 $h\in \mathcal{H}$。第 $t$ 类在第 $l$ 层的实例数为 $n_t^{(l)}$，第 $t$ 类在第 $(l+1)$ 层的实例数为 $n_t^{(l+1)}$，满足 ${\sum }_t{n}_t^{(l)}={\sum }_t{n}_t^{(l+1)}=n$。

证明。由于我们有 $\mathrm{Range}\left({\mathcal{F}}^{(l+1)}\right)<\mathrm{Range}\left({\mathcal{F}}^{(l)}\right)$，为了比较这两个上界，我们只需要比较 ${\sum }_t\frac{1}{n_t^{(l+1)}}$ 和 ${\sum }_t\frac{1}{n_t^{(l)}}$ 之间的关系。考虑一个特殊情况，将任务 $1,\cdots ,t$ 分组到第 $l$ 层的同一超任务中。然后我们在第 $l$ 层有 $t$ 个任务，每个任务 $t$ 包含 $n_t$ 个节点；在第 $(l+1)$ 层有一个任务，包含 $n_1+n_2+\cdots +n_t$ 个节点。根据调和平均数和算术平均数之间的关系，我们有
$$\begin{array}{rl}\frac{1}{n_1+n_2+\cdots +n_t}& \le \frac{t^2}{n_1+n_2+\cdots +n_t}\\ & \le \frac{1}{n_1}+\frac{1}{n_2}+\cdots +\frac{1}{n_t}\end{array}\text{\hspace{1em}(25)}$$

不失一般性，我们有 ${\sum }_t\frac{1}{n_t^{(l+1)}}\le {\sum }_t\frac{1}{n_t^{(l)}}$，证毕。

C 伪代码

在本节中，我们提供了 TAIL2LEARN 的伪代码。

D 数据集细节

我们提供了六个数据集的详细信息和描述，以补充第 4.1 节。（1）Cora-Full 是一个引文网络数据集。每个节点代表一篇论文，具有稀疏的词袋向量作为节点属性。边表示两篇相应论文之间的引用关系，节点类别代表研究主题。（2）BlogCatalog 是一个社交网络数据集，每个节点代表一个博主，每条边表示博主之间的友谊关系。节点属性是根据 Deepwalk [38] 生成的。（3）Email 是一个由研究机构的电子邮件交流构建的网络，其中每个节点代表一个成员，每条边表示机构成员之间的电子邮件通信。（4）Wiki 是一个维基百科页面的网络数据集，每个节点代表一个页面，每条边表示页面之间的超链接关系。（5）Amazon-Clothing 是一个产品网络，包含亚马逊“服装、鞋靴和珠宝”中的产品，每个节点代表一个产品，并标有用于分类的低级产品类别。节点属性基于产品描述构建，边基于它们的可替代关系（“也查看”）建立。（6）Amazon-Electronics 是另一个产品网络，由“电子产品”中的产品构成，节点、属性和标签的构建方式相同。不同之处在于边是根据产品之间的互补关系（“一起购买”）创建的。

为了进一步处理，前四个数据集根据训练/验证/测试比例 $=1:1:8$ 进行随机抽样。对于最后两个数据集，节点被移除，直到类别分布遵循长尾分布（这里我们使头部 $20\%$ 的类别包含总节点数的 $80\%$），同时保持剩余节点之间的连接。我们按节点包含的类别数量对类别进行排序，然后均匀下采样尾部 $80\%$ 的类别。在消除节点时，我们移除度较低的节点及其相应的边。经过半合成处理后，训练集的长尾比例 $0.8\left({\mathrm{Ratio}}_{LT}(0.8)\right)$ 约为 0.25。对于验证/测试集，我们从每个类别中抽样 25/55 个节点。总之，TAIL2LEARN 基于四个自然数据集进行评估，并使用两个具有半合成长尾设置的额外数据集。

每个数据集的统计信息、原始类别不平衡比例和原始长尾比例（如定义 1 中定义的 Ratio ( ${}_{LT}(0.8)$）总结在表 5 中。

表 5：数据集统计信息。

数据集	#节点	#边	#属性	#类别	不平衡比例	长尾比例
Cora-Full	19,793	146,635	8,710	70	0.016	1.09
BlogCatalog	10,312	333,983	64	38	0.002	0.77
Email	1,005	25,571	128	42	0.009	0.79
Wiki	2,405	25,597	4,973	17	0.022	1.00
Amazon-Clothing	24,919	91,680	9,034	77	0.097	1.23
Amazon-Electronics	42,318	43,556	8,669	167	0.107	1.67

E 基线模型细节

在本节中，我们更详细地描述每个基线模型，以补充第 4.1 节。

经典长尾学习方法：Origin 使用 GCN [24] 作为编码器，MLP 作为分类器。过采样 [6] 复制尾部类别的节点，并创建具有过采样节点连接性的新邻接矩阵。重新加权 [60] 惩罚尾部节点以补偿头部节点的优势。SMOTE [7] 通过特征插值生成合成节点，将尾部节点与其最近邻居进行插值，并根据其邻居的边分配边。Embed-SMOTE [3] 在嵌入空间而不是特征空间中执行 SMOTE。基于 GNN 的长尾学习方法：GraphSMOTE [67] 将经典 SMOTE 扩展到图数据，通过插值节点嵌入并通过预训练的边生成器连接生成的节点。它有两个变体：GraphSMOTE ${}_T$ 和 GraphSMOTE ${}_O$，取决于预测的边是离散的还是连续的。GraphMixup [52] 执行语义特征混合和上下文边混合以捕获图特征和结构，然后开发一种强化混合来确定尾部类别的过采样比例。ImGAGN [40] 是一种基于对抗的方法，使用生成器模拟少数节点和鉴别器区分真实节点和伪造节点。LTE4G [61] 将节点分为四个考虑类别和度长尾分布的平衡子集。然后，为每个平衡子集训练一个专家，并使用知识蒸馏获得头部学生和尾部学生进行进一步分类。

F 参数设置细节

在这里，我们提供参数设置的详细信息。为了公平比较，我们将基线和 TAIL2LEARN 中所有 GCN 的隐藏层维度设置为 Cora-Full、Amazon-Clothing、Amazon-Electronics 为 128，BlogCatalog、Email、Wiki 为 64。我们使用 Adam 优化器，学习率为 0.01，权重衰减为 $5e-4$。对于基于过采样的基线，不平衡类别的数量设置与 [61] 中相同。过采样的规模设置为 1.0，即对于每个尾部类别，过采样相同数量的节点。对于 GraphSMOTE，我们将边重建损失的权重设置为 $1e-6$，与原始论文 [67] 中相同。对于 GraphMixup，除了最大迭代次数和 Adam 设置外，我们使用与原始论文 [52] 相同的默认超参数值。对于 LTE4G，我们采用论文 [61] 中报告的最佳超参数设置。对于我们的模型，对比损失的权重 $\gamma$ 选择在 { 0.01 , 0.1 } \{0.01,0.1\} {0.01,0.1} 中，对比学习的温度 $\tau$ 在 { 0.01 , 0.1 , 1.0 } \{0.01,0.1,1.0\} {0.01,0.1,1.0} 中选择。我们将分层图神经网络的深度设置为 3；第一层计算节点嵌入，第二层的任务数量设置为类别数量，第三层的任务数量设置为类别数量的一半。此外，所有模型的最大训练周期设置为 10000。如果原始论文中没有额外设置，我们将提前停止的周期设置为 1000，即如果模型性能在 1000 个周期内没有改善，则提前停止训练。所有实验均在 A100 SXM4 80GB GPU 上进行。

G 参数和复杂性分析细节

超参数分析：首先，我们展示了关于权重 $\gamma$ 和温度 $\tau$ 的敏感性分析，结果如图 5 所示。bAcc（z 轴）的波动小于 $5\%$。当权重 $\gamma$ 和温度 $\tau$ 变大时，bAcc 稍微降低。剩余四个超参数的详细分析结果见附录 G。为了分析这些超参数，所有实验均以权重 $\gamma =0.01$ 和温度 $\tau =0.01$ 进行。隐藏层维度设置为 16，除了研究隐藏层维度的实验。对于分层结构，我们研究了不同的分层深度和任务大小：（1）使用节点嵌入和 70（类别数）个任务的原型嵌入；（2）使用节点嵌入、198 个任务的原型嵌入和 70 个超任务的原型嵌入；（3）使用节点嵌入、70 个任务的原型嵌入和 35 个超任务的原型嵌入。从实验结果可以看出，我们的模型对超参数不敏感。

图 6：Cora-Full 数据集的超参数分析。

复杂度分析：对于每个特定大小，我们在合成数据集上运行 10 次。图 7 中的每个点是基于这 10 次运行的平均值计算得出的。我们可以看到我们的模型的运行时间也是近似线性的。

图 7：节点数量与复杂度分析。