https://arxiv.org/pdf/2007.02914

https://github.com/llan-ml/MetaTNE

Node Classification on Graphs with Few-Shot Novel Labels via Meta Transformed Network Embedding，NIPS，2020

总结：最大的创新点就是嵌入转换函数，利用自注意力机制对节点嵌入进行调整使其task-specific。针对小样本设置还是利用元学习思想，学习不同类别间统一的内在模式，提高目标任务上的分类准确度。

目前图上的小样本问题大多都是针对有标签节点数量较少，且基本都是利用元学习思想来做，可以尝试着用小样本学习中的其他方法比如基于生成等等。另外可以探索一下关系或者属性在小样本场景下该如何做。

1.简介

1.1 摘要

We study the problem of node classification on graphs with few-shot novel labels,which has two distinctive properties: (1) There are novel labels to emerge in thegraph; (2) The novel labels have only a few representative nodes for training a clas-sifier. The study of this problem is instructive and corresponds to many applicationssuch as recommendations for newly formed groups with only a few users in onlinesocial networks. To cope with this problem, we propose a novel Meta TransformedNetwork Embedding framework (MetaTNE), which consists of three modules: (1)Astructural moduleprovides each node a latent representation according to thegraph structure. (2) Ameta-learning modulecaptures the relationships between thegraph structure and the node labels as prior knowledge in a meta-learning manner.Additionally, we introduce anembedding transformation functionthat remedies thedeficiency of the straightforward use of meta-learning. Inherently, the meta-learnedprior knowledge can be used to facilitate the learning of few-shot novel labels.(3) Anoptimization moduleemploys a simple yet effective scheduling strategy totrain the above two modules with a balance between graph structure learning andmeta-learning. Experiments on four real-world datasets show that MetaTNE bringsa huge improvement over the state-of-the-art methods.

本文我们研究了具有少量新类标签下的图的节点分类问题，新类标签具有两个特性：（1）新类标签出现在图中；（2）新类标签只有少量代表性节点用于训练分类器。该研究对许多应用场景（如对在线社交网络中只有少数用户的新组建的群体进行推荐）具有重要意义。为了解决这个问题，我们提出了一个原生的Meta Transformed Network Embedding（MetaTNE）架构，它包含三个模块：（1）结构化模块：根据图结构学习每个节点的潜在表示；（2）元学习模块：按照元学习的方式捕捉图结构和节点标签之间的关系作为先验知识，另外我们引入了一个embedding transformation function来弥补直接使用元学习的不足。本质上元学习学到的先验知识可以用来增强在只有少量样本情况下的学习性能。（3）优化模块：采用一种简单但是有效的策略来训练上述两个模块，并在图结构学习和元学习之间取得平衡。4个真实数据集上的实验表明MetaTNE和当前最优方法相比带来了很大的提升。

1.2 本文工作

图被广泛应用于很多领域来表示数据，包括社交网络分析、生物信息、推荐系统以及计算机网络安全中。节点分类、链路预测、社区发现等图分析任务对我们的现实生活具有重大意义。本文我们主要针对节点分类任务，具体来说是小样本情景下的分类任务，即一些新类标签只有少量样本可以用来训练模型。小样本 的图节点分类可以指导很多实际任务，比如：

1. 一些在线社交网络组织如Facebook、Twitter和Flickr，会有很多广告，我们希望知道用户对这些广告是否感兴趣。通过小样本学习，这些组织就可以通过少量用户的反馈更好地预测其他用户的喜好，提供更好的服务或者推荐。
2. 对于生物里面的蛋白质网络，一些研究人员可能发现某些蛋白质之间有一种新的生物反应。给定一些蛋白质（有或者没有这一反应），小样本学习可以预测其他蛋白质之间是否有这一反应，这可以为实验人员提供新的研究方向。

本文作者考虑：图中的不同类别标签可能共享一些内在的演化模式（比如标签信息在图上的传播方式）。假定有部分类别已经有足够多的的支持集节点（有标签），我们希望能从这些节点中提取出共同的内在信息，然后利用这些提取到的信息帮助新类上（只有少量节点有标签）的分类。但是图结构和节点标签之间的关系十分复杂，节点间信息传播模式也多种多样，因此如何建模捕捉这些信息并将其应用到小样本新类上仍然具有很大挑战。

作者借鉴元学习思想，提出了一种原生的Meta Transformed Network Embedding架构，称之为MetaTNE，来捕捉共同的内在模式。如上图所示，MetaTNE共有3个模块：structural module，meta-learning module和optimization module。

2. 方法

MetaTNE包含三部分：结构模块、元学习模块和优化模块。给定一个图和一些已知标签：

1. structural模块首先根据图结构学习每个节点的标签；
2. 元学习模块学习一个转换函数，为每个元学习任务调整节点表示（只和图结构有关），然后使用基于距离的分类器判别节点标签；
3. 最后按照某种概率分别优化结构模块和元学习模块。

2.1 Structural模块

该模块主要利用图结构信息来学习每个节点的潜在表示。从数学角度来看就是：对于每个节点$v_i\in\mathcal V$，我们要最大化其邻居共现的对数概率即$min\sum_{v_i\in\mathcal V}\sum_{v_j\in\mathcal N(v_i)}log\mathbb P(v_j|v_i)$，$\mathcal N(v_i)$表示$v_i$的邻居。

关于节点邻居集合$\mathcal N(·)$的重构方法有很多，本文采用的是1-hop邻居（Line），通过优化上面的目标函数，我们可以得到一个嵌入矩阵$U\in\mathbb R^{|V|\times d}$，其第i行$u_i$表示节点$v_i$的表示。

2.2 Meta-Learning模块

作者采用基于度量的元学习架构来解决小样本问题，提出了一种转换函数，将与任务无关的嵌入转换成task-specific的嵌入，以便更好地处理多标签问题。

2.2.1 数据设置

和传统的半监督学习不一样，我们根据已知标签$\mathcal Y_{known}$（样本数量比较少）建立一个小样本节点分类任务池。和基于元学习的小样本图像分类任务类似，小样本节点分类任务$\mathcal T_i=(S_i,Q_i,y_i)$由支持集$S_i$，查询集$Q_i$以及从$\mathcal Y_{known}$随机采样的标签$y_i$（$y_i$表示某个类别标签，判别查询集中样本是否有$y_i$标签，每个任务相当于是2-Way k-shot小样本任务）。其中支持集$S_i=S_i^+\cup S_i^-$，$S_i^+\subset\mathcal D_{y_i}^+$表示随机采样的正类样本，$S_i^-\subset\mathcal D_{y_i}^-$表示随机采样的负类样本。$\mathcal Q_i=Q_i^+\cup Q_i^-$，但是$\mathcal S_i\cap Q_i=\varnothing $。每个**任务的目标是**：给定支持集node-label对，寻找一个分类器$f_{\mathcal T_i}$尽可能正确的预测查询集中节点标签。

2.2.2 元学习方法

对于每一个任务$\mathcal T_i=(S_i,Q_i,y_i)\sim p(\mathcal T|\mathcal Y_{known})$，我们希望为label $y_i$构建一个分类器$f_{\mathcal T_i}$，给定支持集$S_i$，分类器能够正确判别$Q_i$中节点的类别。对于每一个$(v_q,l_{v_q,y_i})\in\mathcal Q_i$，模型损失定义为：

$\mathcal L(\hat l_{v_q,y_i},l_{v_q,y_i})=-l_{v_q,y_i}log\hat l_{v_q,y_i}-(1-l_{v_q,y_i})log(1-\hat l_{v_q,y_i})$

其中$\hat l_{v_q,y_i}$表示预测$v_q$标签为$y_i$的概率（这其实就是二分类逻辑回归的损失）。

对于每一个任务$T_i$，分类器$f_{T_i}$有两个参数（d维向量）：$c_+^{(i)}$表示正类原型，$c_-^{(i)}$负类原型。我们基于节点表示和这两个原型之间的距离预测节点标签。从数学角度来看就是：给定每个查询节点$v_q$的嵌入向量$u_q$，我们按照下面方式计算概率：

$\hat l_{v_q,y_i}=f_{T_i}(v_q|c_+^{(i)},c_-^{(i)})=\frac{exp(-dist(u_q,c_+^{(i)}))}{\sum_{m\in\{+,-\}}exp(-dist(u_q,c_m^{(i)}))} \tag 2$

即节点表示和正类原型的相似度除以节点表示和正类原型与负类原型相似度之和。其中$dist(·,·):\mathbb R^d\times\mathbb R^d\rightarrow[0,+\infty)$表示欧氏距离的开方，正类原型和负类原型通常为相应所有节点表示的均值。

2.2.2.1 嵌入转换

公式2是在“每个节点的嵌入向量是相同的或者是任务无关的，与节点的标签或者当前任务无关”这一条件下计算预测概率的。这种方法在单标签小样本分类（每个样本只有一个标签）中是合理的，但是在多标签场景（每个节点可能被分配多个标签）下存在问题。

比如在社交网络中，$\mathcal T_1$和$\mathcal T_2$是两个分类任务，其对应的标签分别为$"Sports"\in\mathcal Y_{known}$和$"Music"\in\mathcal Y_{novel}$。$A$和$B$是这两个任务中涉及到的两个用户，假如A和B对于“Sports”的反馈都是positive，对于“Music”的反馈分别是positive和negative。此时，经过$\mathcal T_1$任务训练，这种task-agnostic方式得到的A和B的表示会很相似，这种节点表示不适用与$\mathcal T_2$。

为了解决上述问题，作者提出了一个转换函数$Tr(·)$：可以将task-agnostic嵌入转换成task-specific嵌入。

1. 不同的查询节点和支持集中节点的关联模式不同，为了全面挖掘查询节点和支持节点之间的关系，对于每个查询节点我们都要对节点嵌入做针对性调整
2. 为了对查询节点进行分类，我们对查询节点和支持节点（正类或负类）之间的距离的关系更感兴趣，而不是查询节点和支持节点（正类和负类）之间的关系。换句话说就是，查询节点和支持节点之间的关系要将支持节点分为正类和负类单独讨论。因此在转换过程中，分别使用正类支持节点和负类支持节点对查询节点进行调整。

基于这两点，对于每个查询节点，我们首先构建两个集合：一个包含查询节点的task-agnostic嵌入和正类支持节点，另一个包含查询节点的task-agnostic嵌入和负类支持节点。然后分别将这两个集合喂给转换函数，即给定一个任务$\mathcal T_i=(S_i,Q_i,y_i)$，对于每个查询节点$v_q\in\mathcal V_{\mathcal Q_i}$：

\begin{align} \{\tilde u_{q,+}^{(i)}\}\cup\{\tilde u_{k,q}^{(i)}|v_k\in\mathcal V_{S_i^+}\}=Tr(\{u_q\}\cup\{u_k|v_k\in\mathcal V_{S_i^+}\})\\ \{\tilde u_{q,-}^{(i)}\}\cup\{\tilde u_{k,q}^{(i)}|v_k\in\mathcal V_{S_i^-}\}=Tr(\{u_q\}\cup\{u_k|v_k\in\mathcal V_{S_i^-}\}) \end{align}\tag 3

其中$\tilde u_{q,+}^{(i)}$和$\tilde u_{q,-}^{(i)}$分别表示用正类支持节点和负类支持节点调整后的查询节点的嵌入，$\tilde u_{k,q}^{(i)}$表示针对查询节点$v_q$调整后的支持节点的嵌入。这样每个查询节点都有两种调整后的嵌入，可以捕捉节点间多种关系来适应多标签场景。

2.2.2.2 转换函数的具体实现

作者使用“ Attention is all you need ”一文中的自注意力架构来实现转换函数。self-attention中每个输入元素都扮演三个角色：

1. 和其他每个元素进行比较，计算一个权重（反映了它对其他元素的影响）
2. 和其他每个元素进行比较，计算一个权重（反映其他元素对它的影响）
3. 用作每个元素输出的一部分

每个元素都有三个向量：query、key和value，分别表示三个角色。

对于公式3，输入是两个集合$\{u_q\}\cup\{u_k|v_k\in\mathcal V_{S_i^m}\},m\in\{+,-\}$，对于任意两个节点$v_i,v_j\in\{v_q\}\cup\mathcal V_{S_i^m}$（$v_i$和$v_j$可能相同），我们首先计算$v_i$对$v_j$的注意力权重：

$w_{ij}=\frac{exp((W_Qu_i)·(W_Ku_j)/d'^{1/2})}{\sum_{v_k\in\{v_q\}\cup\mathcal V_{S_i^m}}exp((W_Qu_i)·(W_Ku_k)/d'^{1/2})}\tag 4$

其中$W_Q,W_K\in\mathbb R^{d'\times d}$分别是将输入向量转换成query向量和key向量的trainable矩阵，$d'$表示query、key和value向量的维度，"$·$"表示点乘操作，$\frac{1}{\sqrt {d'}}$是缩放因子（防止梯度太小）。

$w_{ij}$本质上表示的是：节点$v_j$和$v_i$之间的相关程度，或者说是$v_j$对$v_i$的影响程度。

这样转换后的节点表示向量（聚合了其他所有节点信息）可以通过加权的方式计算得到：$W_V\in\mathbb R^{d'\times d}$表示计算value向量的trainable矩阵，$W_O\in\mathbb R^{d\times d'}$表示确保输出向量和输入向量维度相同的另一个trainable矩阵，按照如下方式计算节点$v_q$转换后的向量：

$\tilde u_{q,m}^{(i)}=W_O\Big(w_{qq}W_Vu_q+\sum\limits_{v_k\in\mathcal V_{S_i^m}}w_{qk}W_Vu_k\Big)\tag 5$

按照如下方式计算针对查询节点$v_q$的支持节点的表示：

$\tilde u_{k,q}^{(i)}=W_O\Big(w_{kk}W_Vu_k+\sum\limits_{v_j\in\mathcal (V_{S_i^m}\backslash\{v_k\})\cup\{v_q\}}w_{kj}W_Vu_j\Big)\tag 6$

本文作者最终采用的是多头注意力机制，将每个头的输入拼接到一起后再通过$W_O$映射成原始输入维度。得到转换后的节点嵌入后，我们重新计算针对查询节点$v_q$的正类原型和负类原型及其预测概率：

$\begin{aligned} \tilde c_{m,q}^{(i)}&=\frac{1}{|S_i^m|}\sum\limits_{v_k\in V_{S_i^m}}\tilde u_{k,q}^{(i)},m\in\{+,-\}\\ \hat l_{v_q,y_i}&=\frac{exp(-dist(\tilde u_{q,+}^{(i)},\tilde c_{+,q}^{(i)}))}{\sum_{m\in\{+,-\}}exp(-dist(\tilde u_{q,m}^{(i)},\tilde c_{m,q}^{(i)}))} \end{aligned}\tag 7$

最终的元学习目标函数也调整为：

$\mathop{min}_{U,\Theta}\sum_{\mathcal T_i}\sum_{(v_q,l_{v_q},y_i\in\mathcal Q_i)}\mathcal L(\hat l_{v_q,y_i},l_{v_q,y_i})+\lambda\sum||\Theta||_2^2$

其中$\Theta$是转换函数的所有参数（$W_Q,W_K和W_V$），$\lambda>0$是平衡因子。（损失里面为什么最小化参数？）

2.3 模型优化

一种典型的方式是最小化structural损失和meta损失之和，但是图的结构信息在训练开始阶段并没有被正确的嵌入进去，节点的表示具有一定随机性，这对小样本分类任务没有意义。因此一种比较好的优化策略是：在开始阶段针对structural模块进行优化，然后逐渐增加meta-learning模块损失的权重。

为了实现这个策略，作者引入了一个概率阈值$\tau$，在每一步训练过程中分别按照$\tau$和$1-\tau$的概率对structural模块和meta-learning模块进行优化。阈值$\tau$按照阶梯式方式逐渐从1衰减到0：$\tau=1/(1+\gamma\lfloor\frac{step}{N_{decay}}\rfloor)$，其中$\gamma$表示衰减率，$step$表示当前的step number，$N_{decay}$表示衰减次数。时间复杂度如下：

• structural模块：时间复杂度为$O(kd|\mathcal E|)$，k表示每次迭代过程中负类节点数，d表示节点嵌入维度，$|\mathcal E|$表示边数；

• 元学习模块：时间主要花费在转换函数（自注意力模块）上，m表示查询节点数量，n表示负类或正类支持节点数量；计算query、key和value向量花费时间$O(mndd')$，$d'$表示三个向量的维度；计算注意力权重和value向量之和花费时间$O(mn^2d')$；计算最终输出向量花费时间$O(mndd')$。

因此总的时间复杂度为$O(kd|\mathcal E|+mndd'+mn^2d')$。整个算法优化流程如下：

我们最终的目标是：给定少量标签为$y\in\mathcal Y_{novel}$的支持节点，我们能判断其他节点是否具有标签$y$，这可以看做是一个小样本节点分类任务$\mathcal T=(S,Q,y)$。训练好模型后，我们可以得到task-agnostic节点表示$U$和参数为$\Theta$的转换函数$Tr(·)$。因此，如果我们要判别一个查询节点$v_q\in Q$的标签，我们只需要查询表示矩阵$U$得到其嵌入$u_q$，然后通过公式5和6的转换函数得到其转换后的嵌入表示$\tilde u_q^+$和$\tilde u_q^-$，再根据公式7计算其预测概率即可。算法流程如下：

3. 实验

3.1 数据集

每个数据集的标签按照6:2:2划分成训练集、验证集和测试集。训练阶段将训练标签看做known标签，并从里面采样小样本节点分类任务。将验证和测试标签看做novel标签并从中分别采样1000个任务。我们采用测试任务上的平均分类表现来比较不同方法的性能。$K_{S,+},K_{S,-},K_{Q,+},K_{Q,-}$分别表示支持集和查询集的正、负类样本数量。baseline方法采用Label Propagation，LINE，Node2Vec，GCN和Meta-GNN。

3.2 对比试验

设置$K_{S,+}=K_{Q,+}$，$K_{S,-}=K_{Q,-}$，用$K_{*,+}$和$K_{*,-}$简化表示正类样本和负类样本数量。考虑到负类样本数量更容易获取，作者设置$K_{*,+}=20$，$K_{*,-}=40$，对比结果如下表所示：

具体参数设置可以查看原始论文补充材料。

3.3 消融实验

验证不同模块的作用，提出5种变体：

1. 没有转换函数
2. 直接将查询节点和支持节点的表示直接喂给self-attention而不是像公式3一样将正类和负类分开
3. 两个模块的损失的平衡因子从$\{10^{-1},10^{-1},...,10{2}\}$里面选取
4. 最开始先学习节点嵌入，然后将其固定（即两个模块分开单独训练）
5. 每个节点的表示用one-hot向量表示，节点嵌入仅仅通过meta-learning模块训练

这五种变体分别用$V_1,V_2,V_3,V_4,V_5$表示，是研究结果如下表所示：

3.4 额外实验

1. 正类和负类节点数量

   

   在负类样本小于等于正类样本时，MetaTNE和Planetoid方法表现相当，但是当负类样本数大于正类样本数时，MetaTNE方法由于Planetoid。这证明了我们的方法优于Planetoid，因为在实际应用中负类节点数量通常多于正类节点数量。

2. 查询节点数量

   在前面试验中查询集合支持集的正负类样本数量相同，但是在实际应用中查询集正负类节点数量可能不同，因此作者进一步测试了查询及节点数对模型表现的影响。（感觉原文对这一部分实验结果的分析有点勉强）

   

3. 更少的正类节点数量

   设置正类样本数量为5。

   

4. 节点表示可视化

   如图a，未对节点嵌入做调整时，查询节点（真实类别为负类）距离正类原型更近，分类错误；对节点嵌入作调整后，查询节点（真实类别为负类）表示Query(+)到正类正类原型的距离大于Query(-)到负类原型的距离。图b也是同样地结果，说明作者提出的转换函数是有效的。