文献地址：https://arxiv.org/abs/1905.01436

摘要

EGNN：边标记图神经网络【将边标签图上的深度神经网络用于FSL】
与平时用于FSL的GNN的区别
- 平时的GNN采用的是基于 节点标记 框架的，其隐式地对 类内相似 和 类间不同 建模来更新节点的标签
- EGNN 采用的是基于 边标记 框架的，显式地对 类内相似 和 类间不同 来迭代更新边的标签，从而实现聚类进化【聚类进化：一种新的聚类方式，用于解决时间戳数据产生聚类 聚类序列 的问题】
特点：可以不需要重新训练就能在不同类别上执行，并且可以很容易执行转导推导
参数学习方式：对边进行分类，得到 loss，根据 loss更新参数
模型：根据上述得到的参数可以得到一个泛化性很好的模型，适用于小样本问题
实验证明：在两个基准数据集上执行有监督和半监督的小样本图像分类任务，EGNN相比于现有的GNNs性能更好

介绍

元学习

任务泛化问题：
- 小样本学习：基于以前经验中的知识，自动和有效地解决少量带标记数据的新任务
- 学会学习
- 非平稳强化学习
- 持续学习
解决的问题：不需要高度依赖大量带标签数据和繁琐的人为调整来解决新任务。

图神经网络

原理：通过 消息传递 机制迭代地对邻居执行特征聚合，进而对数据实例之间的复杂交互进行表示
方式：GNN 使用 深度神经网络 处理数据上的富关系结构
特点：必须根据聚类的基数分别训练模型

联合

原因：小样本算法需要充分利用支持集和查询集之间的关系，而GNN可以得到这个关系
两个利用探索GNN进行小样本学习的方法：
- 《Few-shot learning with graph neural networks》：
  - 1. 首先构建一张图【图中支持集和查询集都紧密结合在一起】
  - 1. 输入节点使用 嵌入特征（经过一个卷积神经网络的输出） 和 给定的标签信息（one-hot 编码） 进行表示
  - 1. 通过迭代更新邻域聚合的节点特征用于对无标签的查询集进行分类
《Transductive propagation network for few-shot learning》：
- 构建：使用经过深度神经网络得到的 节点特征 得到 TPN
- 测试阶段：使用一个普通的图参数集在整个支持实例和查询实例上迭代地传播一个 one-hot编码的标签
特点：以上的方法都是 基于节点标签框架，该框架是隐式地对 类内相似 和 类间不同 进行建模

边标签框架：

聚类方式：使用 表示学习 和 度量学习 来显示执行聚类
特点：
- 该框架对于一个已经存在的支持集聚类可以推断出与查询集之间的关联
- 不需要指定聚类的数量，即不需要指定类基数或者方式【直接查看两个节点是否属于同一聚类】、
- 不需要重新训练模型就可以处理各种类别
本文的要点：将边标签框架应用于小样本分类任务中
EGNN【多个层】
- 组成
  - 节点更新块
  - 边更新块
- 特点：
  - 对节点特征进行更新
  - 显示调整边的特征【两个连接节点之间的边】
  - 直接利用 类内相似 和 类间不同
  - 执行转导推导直接一次整体性地预测所有的查询样本
- 图示
  
  EGNN的图示
  - 图解：
    - 1. 在更新了许多可替代节点特征和边特征之后
    - 1. 根据最后的边特征进行边标签预测
    - 1. 计算出边损失，然后根据元学习策略【情景训练】更新EGNN的参数
  - 注意：
    - 节点更新阶段：使用边标签以及节点自身信息进行更新
    - 边更新阶段：使用相邻节点的特征信息进行更新

贡献：

首次提出 EGNN 用于 FSL，使用类内相似，类间不同来迭代更新边标签，可以不经过重新训练就可以应用于不同的类
EGNN 包含许多层，每层都有节点更新块和边更新块，相应的参数在情景训练框架下获得
将EGNN用于 转导学习（从彼个例到此个例） 和 非转导学习（归纳学习：从多个个例归纳出普遍性，再演绎到个例） 或者推理
使用两个基准数据集在有监督和半监督小样本图像分类任务上做实验，EGNN的效果显著提升了现有的GNN的性能，而且使用消融实验显示出显式聚类和分开利用类内相似，类间不同的好处

方法

问题定义：小样本分类

目的：在每个类别仅仅只有少数训练样本的时候学习出一个分类器
符号定义
- $T$ ：小样本分类任务，其包含支持集 $S$ 和查询集 $Q$
- $S$ ：支持集——带标签的数据集合
- $Q$ ：查询集——需要学习到的分类器进行评估的无标签数据
- $K$ ：带有标签的数据的个数
- $N$ ：类别数
- $N-way \ K-shot$ 分类问题：有 $N$ 个类别，每个类别有 $K$ 个样本，总共 $N \times K$ 个样本，根据这些样本得到一个分类器，该分类器能够对剩余的类别甚至新类别进行精准识别
元学习方法
- 原理：训练得到一个分类器，在只使用任务的支持集就可以为每个查询样本分配标签
- 缺点：现有的数据集无法训练出一个能够完全反映类间和类内关系的模型，以致最终的分类效果不明显
- 解决方法：在显示训练集上通过提取可迁移的知识，该知识能够在支持集执行更好的小样本学习，从而成功地对查询集进行分类
- 情景训练：
  - $N-way \ K-shot$ 问题定义： $T = S \cup Q$
  - $S = \{ (x_i, y_i) \}_{i=1}^{N \times K}$
  - $Q = \{ (x_i, y_i) \}_{i=N \times K + 1}^{N \times K + T}$
  - $T$ 查询样本数
  - $x_i, y_i \in \{C_1, \cdot \cdot \cdot, C_N\} = C_T \subset C$ 分别是第 $i$ 个输入数据及其标签
  - $C$ 是训练数据集或者是测试数据集的所有类别的集合
  - 虽然训练集和测试集都是从同一任务分布中采样得到的，但是它们之间的空间是互斥的，即 $C_{train} \cap C_{test} = \emptyset$
  - 在 每一个episode中的支持集 用作带标签的数据集，并且模型根据此数据集进行训练
  - 损失的优化是 最小化在查询集上的预测损失
  - 逐步执行这个训练过程，直到结果收敛
- 说明：如果上述 $N \times K$ 个支持集样本有些是无标签的，那么此任务成为半监督小样本分类

模型

图示：

EGNN总体框架
- 图中以 $2-way 2-shot$ 为例子，蓝色圈圈和绿色圈圈代表两个不同的类别
- 带有实现的节点表示带有标签的支持集样本
- 带有虚线的节点表示无标签的查询样本
- 边特征的强度使用正方形的颜色进行表示

符号说明
- 给定目标任务所有样本的特征表示（从联合训练的卷积神经网络中所提取）
- 构建一个全连接图，一个节点代表一个样本，边代表相连节点之间的关系类型
- $G = (V, \varepsilon; T)$ 是用于任务 $T$ 的样本构造得到的图
- $V := \{ V_i \}_{i=1, \cdot \cdot \cdot, |T|}$ 表示图的节点集合
- $\varepsilon := \{ E_{ij} \}_{i, j = 1, \cdot \cdot \cdot, |T|}$ 表示图的边集合
- $v_i$ 是节点 $V_i$ 的节点特征
- $e_{ij}$ 是 $E_{ij}$ 的边特征
- $|T| = N \times K +$ $\rm T$ 是任务 $T$ 的所有的样本数
- 边真实值标签 $y_{ij}$ 由节点真实值标签决定 $y_{ij}= \begin{cases} 1, &if\ y_i = y_j\\ 0, & otherwise \end{cases}$
- 边特征 $e_{ij} = \{ e_{ijd} \}_{d=1}^2 \in [0, 1]^2$ 是一个二维向量，代表连接的两点的类内和类间关系的标准化强度，因此能够分别利用类内相似，类间不同
- 节点特征使用卷积嵌入网络 $v_i^0 = f_{emb}(x_i; \theta_{emb})$ 的输出进行初始化，其中 $\theta_{emb}$ 表示相应的参数集，如下图所示
- 边特征由边标签进行初始化 - 边特征
  - 其中 $||$ 操作表示串联操作
EGNN 细节网络架构

EGNN 细节网络架构
- a)嵌入网络 $f_{emb}$
- b)特征(节点)转换网络 $f_v^l$
- c)度量网络 $f_e^l$

EGNN的组成
- 由L层组成用于处理图
- EGNN的用于推理的正向传播是选择进行节点特征更新还是进行边特征更新
- 细节描述：【从 $l-1$ 层更新 $l$ 层】
  - 节点的更新
    - 给定来自于 $l-1$ 层的节点 $v_i^{l-1}$ 和边 $e_{ij}^{l-1}$
    - 首先通过聚合邻域特征执行节点更新
    - 聚合与边特征成比例的其他节点的特征
    - 执行特征转换
    - 进而更新了第 $l$ 层的特征节点 $v_i^l$
  - 边的更新
    - 第层的边特征用作为相应邻居节点的贡献度，类似于注意力机制
      - $\widetilde{e}_{ijd} = \frac {e_{ijd}}{\sum_k e_{ijd}}$
      - $f_v^l$ 是特征转换矩阵
      - $\theta_v^l$ 是参数集
      - 不仅有常规的类内聚合还有类间聚合
      - 类内聚合为目标节点提供“相似邻居”的信息
      - 类内聚合提供“不同邻居”的信息
- 边特征的更新是基于新更新的节点特征
- 获得每对节点之间的相似度(不同度)
- 通过合并之前的边特征值和如下公式更新的相似度（不同度）
  - $\overline{e}_{𝑖𝑗1}^𝑙= \frac {𝑓_𝑒^𝑙 (𝑣_i^𝑙, 𝑣_𝑗^𝑙;𝜃_𝑒^𝑙 ) 𝑒_{𝑖𝑗1}^{(𝑙−1)}}{∑_𝑘𝑓_𝑒^𝑙 (𝑣_𝑖^𝑙, 𝑣_𝑘^𝑙;𝜃_{𝑖𝑘1}^{(𝑙−1)})/(∑_𝑘 𝑒_{𝑖𝑘1}^{(𝑙−1)})}$
  - $\overline{e}_{𝑖𝑗2}^𝑙=\frac {(1−𝑓_𝑒^𝑙 (𝑣_𝑖^𝑙,𝑣_𝑗^𝑙;𝜃_𝑒^𝑙 )) 𝑒_{𝑖𝑗2}^{(𝑙−1)}}{∑_𝑘 (1−𝑓_𝑒^𝑙 (𝑣_𝑖^𝑙, 𝑣_𝑘^𝑙; 𝜃_𝑒^𝑙) 𝑒_{𝑖𝑘2}^{(𝑙−1)}/∑_𝑘𝑒_{𝑖𝑘2}^{(𝑙−1)}}$
  - $𝑒_{𝑖𝑗}^𝑙=\frac {\overline{e}_{𝑖𝑗}^𝑙} {|| \overline{e}_{𝑖𝑗}^𝑙 ||_1}$
  - $f_e^l$ 表示用于计算相似度分数的度量网络，由参数集 $\theta_e^l$ 表示
- 节点特征流入边，边特征中每个元素的更新与标准化类内相似，类间不同的更新相分隔【即每个边更新不仅仅要考虑对应节点对之间的关系，还要考虑其他节点对之间的关系】{可以有选择地使用两个度量网络用于计算相似性和不同性（ $f_{e,dsim}$ 代替 $(1-f_{e, sim})$ ）}
- 边标签的获得，使用最后的边特征 $\widehat{y}_{ij} = e_{ij1}^L$
- $\widehat{y}_{ij} \in [0, 1]$ 可以看成是两个节点 $V_i$ 和节点 $V_j$ 来自于同一类别
- 因此可以通过具有支持集标签和边标签预测结果的简单加权投票来对每个节点 $V_i$ 进行分类
- 节点 $V_i$ 的预测概率可以表示为 $P(y_i = C_K|T) = p_i^{(k)}$
  $p_i^{(k)} = softmax(\sum_{\{ j:j \neq i \bigwedge (x_j, y_j) \in S\}}) \widehat{y}_{ij}\delta (y_j = C_k)$
  - $\delta(y_i = C_k)$ 是 Kronecker 增量函数
    $\delta(y_i = C_k) = \begin{cases} 1, &if\ y_i = C_k\\ 0, & otherwise \end{cases}$
- 节点分类的另一个方法是使用图聚类，整个图 $G$ 首先可以使用边预测和通过线性编程对能够有效地被划分成聚类，然后每个聚类由包含最多的支持集标签来标记
- 使用公式 $p_i^{(k)} = softmax(\sum_{\{ j:j \neq i \bigwedge (x_j, y_j) \in S\}}) \widehat{y}_{ij}\delta (y_j = C_k)$ 得到最终的分类结果
EGNN测试阶段的算法

EGNN用于推理的算法
定义
- 非转导推理：查询样本的数目为1或者一个接一个进行推理
- 转导推理：对整个图中的所有的查询样本进行分类

训练

给定M个训练任务 $\{T_m^{train}\}_{m=1}^M$
在一个episode训练的某个迭代中，EGNN中的参数 $\theta_{emb} \cap \{ \theta_v^l, v_e^l \}_{l=1}^L$ 以端到端方式进行训练
更新参数的方法：最小化以下损失
- $Y_{m, e}$ 是第 $l$ 层第 $m$ 个任务的所有 真实值查询边标签 的集合
- $\widehat{Y}_{m,e}^l$ 是第 $l$ 层第 $m$ 个任务的所有真实值 查询边预测 的集合
- $L_e$ 的定义为二进制交叉熵
边预测结果不仅可以从最后一层获得，还可以从其他的层获得，因此总损失包含所有层的损失{提升较低层的梯度流}

实验

基准数据集：

ImageNet：
- RGB
- 84 $\times$ 84
- 从100个类别中采样，每个类别有600个样本
- 训练集：64类
- 验证集：16类
- 测试集：20类
TieredImageNet
- RGB
- 84 $\times$ 84
- 700K张图片
- 608个类别采自 34类高级节点
- 训练集：20训练类别 -> 351个类别
- 验证集：6验证类别 -> 97个类别
- 测试集：8测试类别 -> 160个类别
- 每个类别的样本平均数是1281

实验设置

网络架构【见上图】
- 特征嵌入模块：卷积神经网络，由四个 blocks 组成
- blocks组成：3 $\times$ 3 卷积 + batch normalization + LeakyReLu激活函数
评估
- 对于imageNet数据集和TieredImageNet数据集，进行 $5-way 5-shot$ 实验
- 在一个episode test中，对5个类别中的每一个类别随机抽取15个查询样本
- 进行600次episodes，然后取其平均值
- 在miniImageNet数据集上执行 10-way 实验 -> 在元训练阶段和元测试阶段之间的类数不同时，EGNN具有灵活性
训练
- 优化方法：Adam
- 学习率： $5 \times 10^{-4}$
- 权值衰减： $10^{-6}$
- 对于 $5-way$ ，将任务的mini-batch大小设置为40
- 对于 $10-way$ ，将任务的mini-batch大小设置为20
- 对于miniImageNet，每15000个episodes衰减一半的学习率
- 对于TieredImageNet，每30000个epsode衰减一半的学习率【数据量太大，需要更多的迭代】

小样本分类

性能：

小样本分类性能
- Trans：转导
- BN：batch normalization
结论：
- 无论在转导还是非转导上，EGNN的性能优于节点标签框架
- EGNN + Transduction 在两个benchmark dataset 上的结果都好于 TPN
- EGNN不进可以传播查询节点的特征，还可以传播具有不同参数集的图层之间的边标签信息
- EGNN 的节点和边特征是动态改变的【与TPN相反，TPN中的节点特征是固定的，在边传播期间不变】

半监督小样本分类

性能:

半监督小样本分类准确性
- LabelOnly：表示仅仅使用带有标签的样本进行学习
- Semi：表示半监督设置【部分样本没有标签】
结论：
- 半监督学习提升了性能
- 在半监督学习中，当标记部分较少时，EGNN的优势远远高于以前的GNN
- 在EGNN-Semi + Transduction 中，性能更高
- 与节点标签框架相比，EGNN能够在转导和非转导设置下从无标签的样本中提取到更多的有用信息

消融研究

观点：EGNN具有多个节点和边更新层组成的深度架构，因此，模型越深，层数越多，样本之间的交互更加深入，最后得到的结果应该更好
性能：

EGNN中不同的层得到的结果
随着EGNN的层数的增加，性能的确越好
层数从1到2，性能提升明显，但是从2到3，性能就不是那么明显了
使用单独的类间聚合显然可以提升性能
EGNN 在节点/边更新中使用类内相似和类间不同的独立开发

与之前的节点标签的GNN相比，EGNN更加有利于解决在任意元测试情况下的小样本问题【特别是元训练和元测试数据类别不同的情况下】
性能：

类别不同的影响
- EGNN不需要重新训练模型就可以应用于多种类别
t-sne 可视化【上面是GNN，下面是EGNN】{初始嵌入，第一层，第二层，第三层}（x:查询，o:支持不同颜色不同的类别）

t-sne可视化
- GNN倾向于在支持样本之间得到良好的聚类，但是实际上查询样本以及支持样本不会靠的很近
- EGNN中，对着层传播的进行，如果查询集和支持集的标签不同，这些样本会被扯开，标签相同的查询样本和支持样本靠的很近
边特征在EGNN中的传播【初始边特征第一层第二层真实边标签】{红色值的 $e_{ij} = 1$ 较高，蓝色值 $e_{ij}=0$ 较低}

边特征在EGNN中的传播