https://arxiv.org/abs/2002.12815

https://github.com/chauhanjatin10/GraphsFewShot

FEW-SHOT LEARNING ON GRAPHS VIA SUPER-CLASSES BASED ON GRAPH SPECTRAL MEASURES

个人见解：

1. 小样本在图领域的应用暂时还是个比较新的方向，可能主要有两个方向：一是将已经成熟的小样本训练方法（比如元学习、半监督等等）缝合到最近一些比较好的图学习方法中；二是对图学习方法进行改造，使其适合小样本场景。
2. 本文作者一方面将小样本中的一种训练策略“initialization based strategy”引入到图学习中，另一方面对图学习算法进行改进，作者认为某个样本类别数量很少时，在做消息传播时，如果图神经网络层数比较浅，那么该类别样本很难影响到大范围的其他节点，因此作者提出了一种计算超类并生成超图的方案使得图神经网络更适用于小样本场景。

1. 简介

1.1 摘要

We propose to study the problem of few-shot graph classification in graph neural networks (GNNs) to recognize unseen classes, given limited labeled graph examples. Despite several interesting GNN variants being proposed recently for node and graph classification tasks, when faced with scarce labeled examples in the few-shot setting, these GNNs exhibit significant loss in classification performance. Here, we present an approach where a probability measure is assigned to each graph based on the spectrum of the graph’s normalized Laplacian. This enables us to accordingly cluster the graph base-labels associated with each graph into superclasses, where the $L^p$ Wasserstein distance serves as our underlying distance metric. Subsequently, a super-graph constructed based on the super-classesis then fed to our proposed GNN framework which exploits the latent inter-class relationships made explicit by the super-graph to achieve better class label separation among the graphs. We conduct exhaustive empirical evaluations of our proposed method and show that it outperforms both the adaptation of state-of-the-art graph classification methods to few-shot scenario and our naive baseline GNNs. Additionally, we also extend and study the behavior of our method to semi-supervised and active learning scenarios.

我们提出了一种用GNNs来研究小样本图分类问题的方法，在只给定少量有标签图样本的情况下，识别不可见类。虽然最近已经有一些GNN变体被应用到节点和图分类任务中了，但是当面临样本数量过少的问题时，GNNs的分类效果较差。本文中，我们提出一种方法，根据图的标准化拉普拉斯谱图将概率度量分配给每个图。这可以让我们将每个图的基础标签聚集成超类，其中$L^p$ Wasserstein距离作为我们基础度量。随后，我们将基于超类构建的超图喂给GNN网络，它利用超图表示的隐藏类间关系来更好地实现图之间的标签分离。我们对提出的方法进行了详细的实验评估，表明我们的模型在小样本场景下优于最新的图分类方法和原生GNN baseline。另外，我们也拓展并研究了我们的方法在半监督和主动学习场景中的表现。

1.2 本文工作简介

GNNs虽然在很多领域都取得了不错的效果，但是在小样本场景下效果比较差。在小样本设定下，novel-class样本数量很少，它需要多轮迭代才能影响到更大范围的领域，因此导致GNN深度过大。但是，实验研究表明，随着GNN层数的增加会导致性能显著下降。基于这个问题，本文提出了一种新解决方案。

1. 超类

   作者首先进行一个一次性的预处理步骤：基于图的正则化拉普拉斯矩阵的谱，为每个图分配一个概率度量，我们称之为“图的谱度量”。给定图的谱度量的度量空间和基础距离（$L^p$ Wasserstein 距离），我们为属于某个基类的一组图计算Wasserstein barycenters，将其看做原型图。通过这些基类的原型图构成的集合，我们将Wasserstein空间中每个和原型图相关联的谱距离进行聚类，创建一个超类标签。

2. 超图

   利用超类信息，作者构建了一个graph of graphs，称之为超图。直觉上，这样可以通过谱度量来利用图之间的非显示和隐性类内间关系，并在其上使用GNN来引入relational inductive bias。这样为我们提供了改进的样本复杂性，并且在少量样本下提供了更好地组合泛化。

3. GNN

   得到超类和超图后，作者开始在图上训练GNN模型。作者GNN模型包含：一个GIN模型作为图嵌入特征提取器$F_\theta(·)$，一个分类器$C(·)$。分类器包含两部分：一个MLP层$C^{sup}$用于学习和预测图的超类类别；还有一个GAT网络$C^{GAT}$，来预测图的实际类别标签。模型的整体损失函数是$C^{sup}$和$C_{GAT}$的交叉熵损失。作者遵循“initialization based strategy”，使用训练和微调两个阶段。在微调阶段，冻结$F_\theta(·)$和$C^{sup}$相关的参数，少量有标签新类样本被用于更新$C^{GAT}$学习到的权重和注意力。

作者本文的贡献或者创新点可以总结为：

1. 领域上，首次将小样本学习引入到图分类任务中。
2. 使用谱度量生成超类，构造超图，学习潜在的类间关系。

2. 方法

2.1 预备知识

1. 数据

   $\mathcal G$表示无权重无向图，$\mathcal Y$表示对应的标签类别。$G_B=\{(g_i^{(B)},y_i^{(B)})\}_{i=1}^n$表示基类中有标签图，$G_N={(g_i^{(N)},y_i^{N})}_{i=1}^m$表示新类中有标签图，其中$g_i^{(B)},g_i^{(N)}\in\mathcal G$，$y_i^{(B)}\in\mathcal Y^{B}=\{1,...,K\}$，$y_i^{(N)}\in\mathcal Y^{(N)}=\{K+1,...,K'\}$，$K'>K$且\mathcal Y^{(B)}\cap\mathcal Y^{(N)}=\O。需要注意的是：$m<<n$，也就是新类有标签图数量远远小于基类有标签图的数量。另外处理$G_B$和$G_N$，还有t个无标签不可见图$G_U:=\{g_1^{U},...,g_t^{(U)}|g_i^{U}\in\pi_1(G_N),i=1...t\}$用于测试。$\pi_1(p)$和$\pi_2(p)$分别表示有序对p的左和右投影。

2. 学习过程

   受$initialization\ based\ methods$的启发，作者训练过程包含两个阶段：训练和微调。在训练时，作者用神经网络训练一个图特征提取器$F_\theta(G_B)$和一个分类器$C(G_B)$，损失函数采用标准的交叉熵损失函数$\mathcal L_c$。为了更好地识别新类上的样本，在微调阶段，$F_\theta(·)$相关的参数被冻结，用新类样本微调$C(G_N)$。（为什么冻结$F_\theta(·)$，微调$C(G_N)$）

3. 问题定义

   训练阶段，给定n个基类有标签数据；微调阶段，给定m个有标签新类数据；其中$m<<n$；小样本图分类的目标就是：能够正确分辨t种类型不可见样本的类别。如果令$m=qT,\ T=K'-K$，其中q表示$G_n$中每个类别标签出现q次，那么该问题就是个T-way，q-shot任务。

4. Graph spectral distance

   （1）图拉普拉斯

   ​ 对于图$g\in\mathcal G$，标准的图拉普拉斯定义为$\Delta_g=I-D^{-1/2}AD^{1/2}$，其中A和D分别是图g的邻接矩阵和度矩阵。$\Delta_g$的特征值集合$\{\lambda_i\}_{i=1}^{|V|}$称之为$\Delta_g$的谱，表示为$\sigma(g)$。一个标准拉普拉斯矩阵的谱$\sigma(g)$的范围在$[0,2]$。我们给每一个$\lambda_i\in\sigma(g)$分配一个Dirac mass $\delta_{\lambda_i}$（狄拉克函数），从而将概率度量与[0,2]上的$\sigma(g)$相关联，称之为graph spectral measure $\mu_{\sigma(g)}$。另外，定义$P([0,2])$表示区间[0,2]上所有概率度量的集合。

   （2）p-th Wasserstein distance

   Wasserstein距离，一种用于度量两个概率分布之间的距离的方法。 相比于这些度量方式，Wasserstein距离有如下一些好处。

   • 能够很自然地度量离散分布和连续分布之间的距离；

• 不仅给出了距离的度量，而且给出如何把一个分布变换为另一分布的方案；

  • 能够连续地把一个分布变换为另一个分布，在此同时，能够保持分布自身的几何形态特征。

  令$p\in[1,+\infty]$，$c:[0,2]\times[0,2]\rightarrow[0,+\infty]$为概率度量$\mu,v\in P([0,2])$之间的代价函数。$\mu$和$v$之间的p-th Wasserstein距离定义为：$W_p(\mu,v)=\Big(\mathop{inf}\limits_\gamma\int_{[0,2]\times[0,2]}c(x,y)^pd\gamma|\gamma\in\Pi(\mu,v)\Big)^{\frac{1}{p}}$，其中 $\Pi(\mu,v)$是transport plans集合，即$[0,2]\times[0,2]$上所有边界为$\mu$和$v$的度量的集合。

  （3）graph spectral distance

  给定两个图$g$和$g'$，它们之间的谱距离定义为：

  $W^p(g,g'):=W_p(\mu_{\sigma(g)},\mu_{\sigma(g')})$

  换句话说，$W^p(g,g')$表示从图g的谱度量到$g'$的最优移动质量代价，其单位移动质量和与区间[0,2]上的实数特征值之差的p次方成正比。

2.2 计算超类

1. 计算每个类别的原型

   首先将$G_B$按照类别划分成$G^{(i)}，i=1...K$，表示类别为i的图构成的集合，这样$G_B=\sqcup_{i=1}^KG^{(i)}$。然后按照如下方式计算每个类别集合的原型：

   $p_i=\mathop{argmin}\limits_{g_i\in\pi_1(G^{(i)})}\frac{1}{|G^{(i)}|}\sum\limits_{j=1}^{|G^{(i)}|}W^p(g_i,g_j)$

   这样每个类别的原型和该类别中所有图的平均谱距离最小。得到所有类别的原型后，使用Lloyd’s的方法（k-means）对其进行聚类。

2. 对原型进行聚类

   给定K个无标签原型$p_1,...,p_K\in\pi_1(G_B)$以及它们对应的谱度量$\mu_{\sigma(p_1)},...\mu_{\sigma(p_K)}$，我们给谱度量重新命名为$s_0,...,s_K$。我们的目标是将这K个原型聚类成最多k个类别，$k\geq1$是用户定义的一个参数。k-means聚类方法（具体见下面第3点）会寻找一种划分$C=\{C_1,...,C_k\}$，使得下面的目标函数最小：

   $\mathop{argmin}\limits_C\sum\limits_{i=1}^{k}\sum\limits_{s_i\in C_i}W_p(s_i,B(C_i))$

   其中$s_i$是$C_i$中的一个原型，$B(C_i)$表示聚类$C_i$中的Wasserstein barycenter，计算方法如下：

   $B(C_i)=\mathop{argmin}\limits_{p\in P([0,2])}\sum\limits_{j=1}^{|C_i|}W_p(p,s(i,j))$

   其中$s(i,j)$表示$C_i$中的第j个spectral measure。

3. Lloyd’s algorithm

   给定$t=1$时刻的初始Wasserstein barycenters集合$B^{(1)}(C_1),...B^{(1)}(C_k)$，交替执行下面两个公式：

   \begin{align} C_i^{(t)}&=\Big\{s_p:W_p(s_p,B^{(t)}(C_i))\leq W_p(s_p,B^{(t)}(C_j)),\forall j,1\leq j\leq k,1\leq p\leq K\Big\}\\ C_i^{(t+1)}&=B(C_i^{(t)}) \end{align}

   最后输出的是将所有原型图划分成k个类别，同时相应的将基类进行了分组。我们称这些类别为超类，用$\mathcal Y^{sup}$表示超类构成的集合。

2.3 神经网络架构

2.3.1 特征提取器

GNN通常采用如下的消息传播架构：

$H^{(j)}=M(A,H^{(j-1)},\theta^{(j)})$

其中$H^{(j)}\in\mathbb R^{|V|\times d}$表示j轮迭代后的节点嵌入，M是依赖于图邻接矩阵的消息传播函数，$\theta^{j}$表示第j轮的可训练参数，$H^{(j-1)}$表示上一轮的节点嵌入。本文作者采用GIN作为特征提取器（效果比GCN、Graphsage好）：

$H^{(j)}=MLP((1+\epsilon)^j\odot H^{(j-1)}+A^TH^{(j-1)})$

其中$\epsilon$是layer wise的可学习常量。GIN模型迭代R轮后得到的最终节点嵌入表示为$H^{(R)}$，但是GIN考虑到早期迭代得到的特征对于提高模型判别力也有帮助。因此，R轮迭代后，最终的嵌入表示为：

$H_g=\Big|\Big|_{j=1}^RH^{(j)}$

其中$H^{(j)}=\sum_{v\in V}H_v^{(j)}$，$H_i^{(j)}$表示第j轮迭代中，第i个节点的嵌入。$||$表示concatenation操作。这样$H_g$作为整个图的嵌入传递到分类器中进行分类。

2.3.2 分类器

一、训练期间

1. $C^{sup}$

   将$F_\theta(·)$提取的特征传递给MLP网络$C^{sup}$来学习对应的超类标签。$C^{GAT}$和$C^{sup}$共同组成了分类器$C(·)$。

2. $C^{GAT}$

   在训练期间，首先在基类的一个batch样本上构建超图$g^{sup}$作为k-NN图集合，其中每个k-NN图都是基于同一个超类的图构建的。之后将$g^{sup}$传递给多层GAT网络$C^{GAT}$来学习可能的类概率。使用GAT背后的直觉是：通过引入GATR固有的关系归纳偏差来进一步提高聚类效果。

$C^{GAT}$和$C^{sup}$的交叉熵损失相加就是最终分类器$C(·)$的损失函数。

二、微调期间

微调阶段，将有标签新类图作为输入，$F_\theta(·)$参数固定，$C^{sup}$用来推断新图的超类标签。然后在新图样本上创建超图，最后通过损失来更新$C^{GAT}$的参数。最后，用不可见测试集中的样本进行测试。

2.4 总结

1. 首先使用GIN提取图的特征，用单个向量表示。
2. 然后按照图的标签类别计算每个类别的原型。
3. 再使用k-means对原型进行聚类，构造超类。
4. 训练阶段，一方面每个超类中的图会构造成一个k-NN图，然后通过GAT网络对图进行分类，另一方面训练一个MLP分类器，预测图所属超类类别。
5. 微调阶段，输入新类图，通过特征提取器提取特征，将特征喂给$C^{sup}$获取图的超类标签，再构造给k-NN超图，调节GAT参数。

3. 实验

3.1 数据集和Baseline

主要采用Reddit-12K，ENZYMES，Letter-High和TRIANGLES四个数据集：

将数据集按照如下方式进行划分：

Validation Graphs用于评估模型在训练类别上的表现，检查过拟合以及选择超参。由于TRIANFLES数据集样本数量过大，因此许多DL或者non-DL baseline无法在其上运行。因此作者从每个类别中选取200个图，让其样本总量变成2000。同样地，对Reddit-2K数据集进行降采样，抽取1111个样本（每个类101个样本），否则会导致一些kernel方法和dl方法运行过慢。

3.2 实验结果

作者提出对自己的模型提出了两种变体：第一种使用GCN代替GAT，称之为OurMethod-GCN，用来评估GCN和GAT的效果；第二种变体使用k-NN代替整个分类器，称之为GIN-k-NN，用来强调构建超图并使用GAT来利用关系归纳偏差的重要性。

下表中的结果均是运行50次后取平均值。每次运行时选取不同的新的有标签集合$G_N$来微调模型的分类器。对于TRIANGLES和ENZYMES数据集每次随机选取500个样本作为测试集$G_U$，对于ENZYMES选取150个样本，对于Reddit选取300个样本作为测试集。

从实验结果可以看到：GIN-k-NN性能显著低于OurMethod-GCN和OurMethod-GAT，说明作者构建的以超图作为输入的GNN网络可以显著提高模型在小样本场景下的表现。

3.3 消融实验

1. 研究$C^{sup}$的作用

原文是这样说的“ Using super-classes help in reducing the sample complexity of the large Hypothesis spaceand makes tuning of the model parameters easier during fine-tuning stage with less samples and few iterations. ”（暂时不懂）

在ENZYMES数据集上两者区别可以忽略不计，因为trainning classes和testing classes的数量都很小，即使不适用super-class，模型效果也很好。

2. 超类类型数量k的选取

基本在2和3个的时候效果最好，超类类型过多会使得每个超类cluster过于稀疏，内部只有很少的图类型，从而导致不同图类型之间的信息不足。

3. 构建超图时k值得选取

   Heuristic表示使用$\sqrt b_s$个最近邻构建超图，$b_s$为 the number of samples in the mini-batch corresponding to super-classess。

3.4 可视化

作者使用t-SNE对模型最后一层输出的embedding进行可视化：