High-order structure preserving graph neural network for few-shot learning

2021-06-04

论文笔记 / 小样本图学习

字数统计: 4.5k | 阅读时长≈ 21 分钟

https://arxiv.org/pdf/2005.14415

https://github.com/yangfeifei02/HOSP

High-order structure preserving graph neural network for few-shot learning，2020

总结：文章提出的HOSP-GNN是对EGNN模型的改进，创新点在于将高阶结构引入GNN中，近似统一了不同任务中的度量标准，提高了小样本元学习算法的准确度。另外在GNN逐层迭代的过程中增加了流行结构约束，进一步提高了模型性能。

1. 简介

1.1 摘要

Few-shot learning can find the latent structure information between the prior knowl-edge and the queried data by the similarity metric of meta-learning to construct thediscriminative model for recognizing the new categories with the rare labeled samples.Most existing methods try to model the similarity relationship of the samples in the intra tasks, and generalize the model to identify the new categories. However, the relationship of samples between the separated tasks is difficultly considered because of thedifferent metric criterion in the respective tasks. In contrast, the proposed high-orderstructure preserving graph neural network(HOSP-GNN) can further explore the richstructure of the samples to predict the label of the queried data on graph that enablesthe structure evolution to explicitly discriminate the categories by iteratively updat-ing the high-order structure relationship (the relative metric in multi-samples,insteadof pairwise sample metric) with the manifold structure constraints. HOSP-GNN cannot only mine the high-order structure for complementing the relevance between sam-ples that may be divided into the different task in meta-learning, and but also generatethe rule of the structure updating by manifold constraint. Furthermore, HOSP-GNNdoesn’t need retrain the learning model for recognizing the new classes, and HOSP-GNN has the well-generalizable high-order structure for model adaptability. Experi-ments show that HOSP-GNN outperforms the state-of-the-art methods on supervised and semi-supervised few-shot learning in three benchmark datasets that are miniIma-geNet, tieredImageNet and FC100.

小样本学习能够通过元学习的相似度度量学习先验知识和查询数据之间的潜在结构信息，来构建判别模型，用于区分只有少量标记样本的新类。现有的方法大多都是对任务内的样本间的相似度关系进行建模，对模型进行泛化来识别新类。但是不同任务之间的度量标准不同，因此不同任务之间的样本间的关系难以考量。相比之下，本文提出的HOSP-GNN模型能够更进一步挖掘样本间丰富的结构，来预测图上查询数据的标签，从而使结构演化能够通过迭代更新模型来明确区分类别，具有流形结构的约束（乱吹）。HOSP-GNN不仅能够挖掘高阶结构来补充样本之间的相关性，这些样本在元学习中可能被划分到了不同任务中，还能生成流形约束下的结构更新规则。另外，HOSP-GNN不需要重新训练就能用于新的类别，而且HOSP-GNN具有well-generalizable高阶结构，模型自适应性更好。miniImageNet、tieredImageNet和FC100三个数据集上的实验表明作者的方法在全监督和半监督小样本学习任务上的性能要优于当前最先进方法。

1.2 本文工作

1.2.1 背景

利用在大规模标记数据集上训练的基于深度学习的判别模型，视觉内容的识别和理解取得了很大进展。事实上，有两个原因限制了深度学习方法在新类上的学习效率：一是大规模数据集上人工标记成本过高，二是新类上的少量样本不足以支撑判别模型的训练。因此如何在只有少量样本的新类上学习判别模型仍然具有很大挑战。为了解决这个问题，受人类视觉系统的启发，即人类只需要少量样本通过feature learning或者meta-learning就能学会判别一个新的类别，研究人员提出了小样本学习。Feature learning主要强调基于各种可迁移信息来学习特征生成和提取模型，而Meta-learning主要关注于relevance模型，通过episode训练挖掘数据样本之间的共同关系。

元学习在不同任务之间迁移知识，传播潜在的结构信息以提高模型的泛化能力避免过拟合，是当前小样本学习最重要的方向之一。**但是元学习的构建依赖于大规模独立的任务，不同任务之间独立的度量标准导致了不同任务的样本之间难以迁移信息。**尽管现有的方法通过将相同的样本填充到不同的任务中，可以在一定程度上缓解这一差距，但是还是很难在不同任务之间构建相似的度量标准，进行有效的信息迁移和传播。

1.2.2 本文工作

本文作者针对上述讨论的元学习存在的问题，提出了HOSP-GNN模型。作者尝试通过挖掘高阶结构来构建相似的度量标准，并且通过约束数据流形结构来更新样本之间的度量值，实现小样本学习。下图展示了HOSP-GNN和现有的元学习方法之间的差异：

2. 方法

2.1 问题定义

$C_e$ 和 $C_n$ 分别表示有大量标记样本的已知类集合和只有少量标记样本的新类集合，$C_e\cap C_n= \emptyset $。
$D_e=\{(x_i,y_i)|y_i\in C_e,i=1,...,|D_e|\}$ ，其中 $x_i$ 表示第i张图片，类别标签为 $y_i$ ， $|D_e|$ 表示集合 $D_e$ 中元素数量。
$D_n=\{(x_i,y_i)|y_i\in C_n,i=1,...,|D_n|\}$ ，其中 $x_i$ 表示第i张图片，类别标签为 $y_i$ ， $|D_n|$ 表示集合 $D_n$ 中元素数量。

如果新类 $C_n$ 中每个类别只有K个标记样本，则称之为K-shot问题，即 $|D_n|=K|C_n|$ 。小样本学习的目标就是从 $D_n$ 学习一个判别模型，能够准确预测测试集 $D_t$ 中数据的类别（来自 $C_n$ ）， $D_n\cap D_t=\emptyset$ 。

2.2 基于图神经网络的元学习

元学习的训练阶段通过构建一个任务集合来训练分类器模型，每个任务 $\mathcal T=\{S,Q\}$ 包含有标签的支持集 $S\subseteq D_n$ 和用于测试的查询集 $Q\subseteq D_t$ 。其中S包含N个类别，每个类别有K个有标签样本，此时称之为N-way-K-shot小样本分类。

在实际应用中，使用只有少量标记样本的 $D_n$ 数据集训练处的分类模型，在 $D_t$ 上难以取得好的分类表现。因此大多数方法都会从 $D_e$ （有大量有标签样本）中进行数据采样来训练分类模型。一种常用的元学习方法就是episodic training，从 $D_e$ 中进行数据采样来模拟 $D_n$ 和 $D_t$ 下的N-way-K-shot分类任务。每个episodic都从 $D_e$ 中采样数据构建任务 $\mathcal T_{ep}=(S_{ep},Q_{ep})$ ，称之为N-way-K-shot T查询样本的小样本分类任务。其中 $S_{ep}=\{(x_i,y_i)|y_i\in C_{ep},i=1,...,N\times K\}$ ， $Q_{ep}=\{(x_i,y_i)|y_i\in C_{ep},i=1,...,N\times T\}$ ， $S_{ep}\cap Q_{ep}=\empty$ ， $|C_{ep}|=N$ 。在训练阶段 $C_{ep}\in C_e$ ，在测试阶段 $C_{ep}\in C_n$ 。

在每个episodic，作者构建一个图 $G_{ep}=(\mathcal V_{ep},\mathcal E_{ep},\mathcal T_{ep})$ 来描述样本间的结构特征，其中 $\mathcal V_{ep}$ 表示顶点集合， $\mathcal E_{ep}$ 表示边集合， $\mathcal T_{ep}$ 表示图片特征。模型损失如下：

\begin{aligned} L_{ep}&=-\sum_{l=1}^L\sum_{(x_i,y_i)\in Q_{ep}}y_ilog(h_W^l(f(x_i,W_f);S_{ep},G_{ep}))\\ &=-\sum_{l=1}^L\sum_{(x_i,y_i)\in Q_{ep}}y_ilog(\hat y_i^l) \end{aligned}\tag 1

\begin{aligned} \hat y_i^l=softmax(\sum_{j\neq i\ and\ c\in C_{ep}}e_{ij}^l\delta(y_i=c)) \end{aligned} \tag 2

其中 $\delta$ 是指示函数， $y_i=c$ 时值为1，否则为0。

2.3 高阶结构

在每个元任务中，现有的小样本方法都是采用pairwise的方式计算样本之间的结构关系，根据图中的相似度矩阵生成一个具有唯一度量标准的独立的度量空间。在不同的元任务中，不同的度量标准导致不同样本之间结构关系存在差异，如下图所示：

这种差异影响了模型在新类任务中的分类准确度。为了降低不同任务度量标准的差异，作者尝试通过不可见的潜在联系来获取样本的高阶结构信息。由于样本是在每个独立任务中分别进行标准化的，因此传统的pairwise度量方式不具备一个统一的度量标准。而绝对统一的bench marking难以在不同任务的样本之间构建高阶关系结构。因此作者将任务中的**多样本的相对度量图**定义为高阶关系结构。

相对度量图 $\hat G_{ep}=(\hat{\mathcal V}_{ep},\hat{\mathcal E}_{ep},\mathcal T_{ep})$ ，其中 $\mathcal T_{ep}=\{(x_i,y_i)|(x_i,y_i)\in S_{ep}\ or\ (x_i,y_i)\in Q_{ep},S_{ep}\cap Q_{ep}=\empty,i=1,...,N\times (K+T)\}$ ， $\hat{\mathcal V}_{ep}=\{v_i|i=1,...,N\times(K+T)\}$ ， $\hat{\mathcal E}_{ep}=\{e_{ij}|i=1,..,N\times(K+T)\ and\ j=1,...,N\times(K+T)\}$ 。作者构建一个L层图神经网络来学习边特征 $e_{ij}^l$ 和节点特征 $v_i^l$ 。节点初始特征 $v_i^0$ 计算方法如下：

u_i^0=f(x_i),\qquad i=1,...,N\times(K+T)\tag 3

v_i^0=\left\{ \begin{aligned} &u_i^0-u_{i+1}^0,\quad i=1,...,N\times(K+T)-1, \\ &u_i^0-u_1^0,\qquad i=1N\times(K+T), \end{aligned} \right.\tag 4

其中 $f(·)$ 表示特征提取网络， $u_i^0$ 表示节点的原始特征， $v_i^0$ 表示在第0层基于 $u_i^0$ 的相对度量。作者希望基于这些相对度量 $v_i^l$ 构建高阶结构 $e_{ij1}^l$ 表示第l层节点i和节点j之间的边特征， $e_{ij2}^l$ 表示pairwise相似度， $e_{ij3}^l$ 表示不相似度。初始值 $e_{ij}^0$ 计算方法如下：

e_{ij}^0=\left\{ \begin{aligned} &[e_{ij1}^0||e_{ij2}^0=1||e_{ij3}^0=0],\quad y_i=y_j\ and\ (x_i,y_i)\in S_{ep}\\ &[e_{ij1}^0||e_{ij2}^0=0||e_{ij3}^0=1], \quad y_i\neq y_j\ and\ (x_i,y_i)\in S_{ep}\\ &[e_{ij1}^0||e_{ij2}^0=0.5||e_{ij3}^0=0.5],\quad otherwise \end{aligned} \right.\tag 5

$e_{ij1}^0$ 计算方法如下：

e_{ij1}^0=1-||v_i^0-v_j^0||_2/\sum_k||v_i^0-v_k^0||_2,\quad (x_i,y_i)\in S_{ep}\cup Q_{ep}\tag 6

下图展示了pairwise度量和high-order度量之间的区别：

## 2.4 高阶结构的保留

HOSP-GNN构建一个L层的GNN来更新顶点和边特征，更新方式如下列公式所示： $$ \begin{array}{c} u_{i}^{l}=f_{v}^{l}\left(\left[\sum_{j} \tilde{e}_{i j 1}^{l-1} v_{j}^{l-1}\left\|\sum_{j} \tilde{e}_{i j 2}^{l-1} u_{j}^{l-1}\right\| \sum_{j} \tilde{e}_{i j 3}^{l-1} u_{j}^{l-1}\right], W_{v}^{l}\right) \\ \end{array}\tag 7 $$

\begin{array}{c} v_{i}^{l}=\left\{\begin{array}{ll} u_{i}^{l}-u_{i+1}^{l}, & i=1, \ldots, N \times(K+T)-1 \\ u_{i}^{l}-u_{1}^{l}, & i=N \times(K+T) \end{array}\right. \end{array}\tag 8

$u_i^l$ 通过 $u_i^{l-1}$ ， $v_i^{l-1}$ ， $e_{ij}^{l-1}$ 计算得到，再计算得到 $v_i^l$ 。其中 $||$ 表示concatenation操作， $\tilde{e}_{i j k}^{l-1}=e_{ijk}^{l-1}/\sum_ke_{ijk}^{l-1}(k=1,2,3)$ ， $f_v^l(·)$ 表示顶点特征更新网络， $W_v^l$ 表示第l层的参数。

上面顶点的更新过程中，高阶结构影响下一层节点特征，但是不能有效地逐层传递下去，因此作者对边特征也逐层进行更新。更新方式如下列公式所示：

\bar{e}_{i j 1}^{l}=\frac{f_{h}^{l}\left(\left\|v_{i}^{l}-v_{j}^{l}\right\|_{2}, W_{h}^{l}\right) e_{i j 1}^{l-1}}{\sum_{k} f_{h}^{l}\left(\left\|v_{i}^{l}-v_{k}^{l}\right\|_{2}, W_{h}^{l}\right) e_{i k 1}^{l-1} / \sum_{k} e_{i k 1}^{l-1}},\tag {10}

\bar{e}_{i j 2}^{l}=\frac{f_{p}^{l}\left(\left\|u_{i}^{l}-u_{j}^{l}\right\|_{2}, W_{p}^{l}\right) e_{i j 2}^{l-1}}{\sum_{k} f_{p}^{l}\left(\left\|u_{i}^{l}-u_{k}^{l}\right\|_{2}, W_{p}^{l}\right) e_{i k 2}^{l-1} / \sum_{k} e_{i k 2}^{l-1}}\tag {11}

\bar{e}_{i j 3}^{l}=\frac{\left(1-f_{p}^{l}\left(\left\|u_{i}^{l}-u_{j}^{l}\right\|_{2}, W_{p}^{l}\right)\right) e_{i j 3}^{l-1}}{\sum_{k}\left(1-f_{p}^{l}\left(\left\|u_{i}^{l}-u_{k}^{l}\right\|_{2}, W_{p}^{l}\right)\right) e_{i k 3}^{l-1} / \sum_{k} e_{i k 3}^{l-1}},\tag {12}

e_{ij}^l=\bar e_{ij}^l/||\bar e_{ij}^l||_1\tag {13}

其中 $f_h^l(·)$ 表示计算高阶度量的网络， $f_p^l$ 表示计算pairwise度量的网络， $W_h^l$ 和 $W_p^l$ 分别表示这两个网络的参数。

根据manifold learning和structure fusion，数据从一个空间映射到另一个空间时，要想保留结构信息，可以通过最小化这两个空间度量差异来实现。高阶结构信息也遵循这样一个规则，因此作者构建了损失函数 $L_{ml}$ 来约束模型的优化：

\begin{aligned} L_{m l}=& \sum_{i, j, l} f_{h}^{l}\left(\left\|v_{i}^{l}-v_{j}^{l}\right\|_{2}, W_{h}^{l}\right) e_{i j 1}^{l-1}+\\ & \sum_{i, j, l} f_{p}^{l}\left(\left\|u_{i}^{l}-u_{j}^{l}\right\|_{2}, W_{p}^{l}\right) e_{i j 2}^{l-1}+\\ & \sum_{i, j, l}\left(1-f_{p}^{l}\left(\left\|u_{i}^{l}-u_{j}^{l}\right\|_{2}, W_{h}^{l}\right)\right) e_{i j 3}^{l-1} \end{aligned}\tag {9}

这样整个模型的损失函数 $L_{total}$ 包含 $L_{ep}$ 和 $L_{ml}$ 两部分：

L_{total}=L_{ep}+\lambda L_{ml}

HOSP-GNN的伪代码如下图所示：

整个算法分成四步，第一步初始化节点特征和边特征，第二步逐层更新节点特征，第三步逐层更新边特征，第四步预测查询样本的标签。

3. 实验

3.1 简介

baseline对比实验
state-of-the-art方法对比实验
半监督小样本学习
一些消融实验

3.1.1 数据集

miniImageNet，tieredImageNet和FC100

### 3.1.2 **实验设置**

特征提取部分和现有的其他方法一致，采用 $3\times 3$ 的卷积核，1个线性单元，1个batch正则化，1个leakReLU单元。

为了方便和其他方法作对比，作者设定层数L为3。

3.2 baseline对比实验

HOSP-GNN的主要架构是基于EGNN模型构建的，区别在于EGNN只考虑了相似性和不相似性，并且在逐层迭代的时候没有考虑manifold structure constraint，而HOSP-GNN尝试捕捉多个样本（不是两个）之间的高阶结构，将样本间的相似性和不相似性融合到一起，并且在更新过程中增加了约束条件。

作者设置的baseline方法有：EGNN，HOSP-GNN-H-S，HOSP-GNN-H-D，HOSP-GNN-H，HOSP-GNN-S，HOSP-GNN-D。（其中H表示高阶结构关系，S表示相似关系，D表示不相似关系）