https://arxiv.org/pdf/2006.07889

https://github.com/mims-harvard/G-Meta

Graph Meta Learning via Local Subgraphs ，NIPS，2020

总结：本文算法上没有太大的创新，将MAML拓展到图学习领域，基于度量学习判别样本标签。

1. 在元任务上学习一个GNN参数，将其代入目标任务的GNN中进行微调
2. 使用子图学习每个节点的嵌入，利用局部子图实现元学习（这块理论证明比较充分）

还有一点就是文章故事讲的很好，完整的定义了图上的元学习以及常见的三种类型的元学习任务，然后提出了可以同时适用这三种类型问题的模型，而其他模型通常只能解决其中一种。

1.简介

1.1 摘要

Prevailing methods for graphs require abundant label and edge information forlearning. When data for a new task are scarce, meta learning can learn fromprior experiences and form much-needed inductive biases for fast adaption to newtasks. Here, we introduceG-META, a novel meta-learning algorithm for graphs.G-METAuses local subgraphs to transfer subgraph-specific information and learntransferable knowledge faster via meta gradients.G-METAlearns how to quicklyadapt to a new task using only a handful of nodes or edges in the new task and doesso by learning from data points in other graphs or related, albeit disjoint, label sets.G-METAis theoretically justified as we show that the evidence for a prediction canbe found in the local subgraph surrounding the target node or edge. Experiments onseven datasets and nine baseline methods show thatG-METAoutperforms existingmethods by up to 16.3%. Unlike previous methods,G-METAsuccessfully learnsin challenging, few-shot learning settings that require generalization to completelynew graphs and never-before-seen labels. Finally,G-METAscales to large graphs,which we demonstrate on a new Tree-of-Life dataset comprising 1,840 graphs, atwo-orders of magnitude increase in the number of graphs used in prior work.

目前主流的图学习方法都需要大量的标签和边信息。当遇到数据稀缺的任务的时候，元学习可以从之前的经验中学习知识，形成归纳偏差使模型可以快速适应新的任务。本文，我们提出了G-META模型——一种用于图的原生元学习算法。G-META利用局部子图来迁移subgraph-specific信息，并通过meta gradients更快地学习可迁移的知识。G-META通过学习其他图或标签集（尽量不相交）中的相关数据点，来快速适应只有少量节点或边的新任务。作者证明了可以在目标节点或者边周围的局部子图中找到prediction，因此G-META理论上是合理的。7个数据集和9个baseline方法上的实验表明，G-META和现有方法相比性能提高了16.3%。和先前的方法不同，G-META成功应用于具有挑战性小样本学习场景（需要一般化到完全信的图和从未见过的标签）。最后，G-Meta可以扩展到大型图上，作者在一个包含1840个图的Tree-of-Life数据集上演示了这一点，这比之前的实验中使用的图的数量增加了两个数量级。

1.2 本文工作

1.2.1 图元学习的定义

图上的元学习通常指模型在两个层次上学习的场景：1.第一个层级上，在单个任务中快速学习，例如GNN某个特定的图上快速学习节点分类；2.第二个层级上，通过在多个任务上不断积累学习到的知识来捕捉任务结构在不同目标域中是如何变化的。

1.2.2 元学习问题

- 单个图上，不同任务使用的标签集合不同 - 多个图上，不同任务使用的标签集合相同 - 多个图上，不同任务使用的标签集合不同

目前的一些方法如Meta-Graph等只能解决上述问题中的一种，本文的方法可以同时适用于这三种问题。

1.2.3 作者方法

本文作者提出了G-Meta元学习模型，其核心思想是用一个局部子图来表示每个节点，并且用子图来训练GNNs达到元学习的目的。作者从理论上分析了可以在目标节点或者边周围的子图中找到一个合适的预测。

之前的一些小样本学习方法都是基于整个图来做的，作者从理论上分析了这些方法不可能在标签稀少且分布在多个图的小样本设定下取得成功。之前的方法虽然捕捉了整张图的结构信息，但是丢失了更精细的局部结构信息。另外，通过子图得到的结构相似度更有利于G-META通过元学习形成归纳偏置，而且局部子图可以通过GNN实现有效的特征传播和标签平滑。

1.2.4 问题定义

$\mathcal G=\{G_1,...,G_N\}$表示N张图，$G=(\mathcal V,\mathcal E,X)$，$\mathcal V$表示节点集合，$\mathcal E$表示边集合，$X=\{x_1,...,x_n\}$表示属性向量集合，$x_u\in\mathbb R^d$表示节点$u$的d维特征向量。$\mathcal Y=\{Y_1,...,Y_M\}$表示M个不同的标签，用Y表示从$\mathcal Y$中随机选取的标签集合。G-Meta的核心准则是用局部子图表示节点，然后用子图在不同任务、图和标签集合之间传递知识。用S表示节点的局部子图集合，$S=\{S_1,...,S_n\}$。节点分类的目标是训练一个GNN $f_\theta:\mathcal S\rightarrow\{1,...,|Y|\}$，只需要少量有标签节点就可以准确的将节点u对应的局部子图$S_u$映射成节点对应的标签。

• 问题1：Single Graph and Disjoint Labels

  给定图G，标签集合的分布$p(Y|G)$，目标是让经过其他标签集合$Y_i\sim p(Y|G)$训练好的模型能够快速适应unsee标签集合$Y_*\sim p(Y|G)$，其中$Y_i\cap Y_*=\varnothing$

• 问题2：Multiple Graphs and Shared Labels

  给定服从分布$p(G)$的图集合$\mathcal G$和一个标签集合Y，目标是让经过$G_j\sim p(G)$训练好的模型可以快速适应unseen graph $G_*\sim p(G)$，其中$G_j$和$G_*$是disjoint的。所有的任务都共享一个标签集合。

• 问题3：Multiple Graphs and Disjoint Labels

  给定服从分布$p(G)$的图集合$\mathcal G$，每个任务有自己的标签集合$Y_i$，但是不同图的标签集合可以相同，目标是让经过$Y_i\sim p(Y|\mathcal G)$训练好的模型能够快速适应unseen标签集合$Y_*\sim p(Y|\mathcal G)$，其中$Y_i\cap Y_*=\varnothing$。

2. G-META

首先为每个节点构造一个局部子图（h-hop邻居），然后使用GNN encoder为每个子图生成嵌入，最后使用原型损失作为归纳偏差，使用MAML在不同的图和标签之间传递知识。

2.1 局部子图及其理论分析

首先介绍如何构造局部子图，然后从理论上分析了局部子图如何帮助G-Meta捕捉到充足的结构信息、特征以及标签，并将这些信息用于图元学习。

对于节点u，其对应的局部子图定义为$S_u=(\mathcal V^u,\mathcal E^u, X^u)$表示一个节点集合$\{v|d(u,v)\leq h\}$，$d(u,v)$表示节点u和节点v之间的最短路径，h定义了子图的邻居大小。然后用GNNs对这些局部子图进行编码（学习节点表示），但是一个直接的问题是这个子图是否会由于排除了子图外节点而丢失信息。下面作者从理论上分析了将GNN应用于子图和应用于整个图相比而言也可以保留有用的信息。

以GCN为对象，研究信息传播过程中节点之间是如何相互影响的。

2.1.2 定理1：节点影响的衰减特性

t表示节点u和节点v之间的一条路径，$D_{GM}^t$表示路径t上节点度的集合平均值。令$D_{GM}^{t_*}=min_t\{D_{GM}^t\}$，$h_*=d(u,v)$，考虑节点v到u的节点影响$I_{u,v}$，有$I_{u,v}\leq C/(D_{GM}^{t_*})^{h_*}$。

证明见原始论文Appendix C。定理1表明节点v对u的影响随着他们之间距离$h_*$的增加指数衰减。另一个发现就是节点影响很大程度上取决于两个节点之间路径累计的节点度，换句话说，如果节点间的路径是直线（累计的节点度最小），节点影响非常高，相反，如果路径上包含大量到其他节点的连接（累计的节点度很大），那么节点影响很小。直觉上的理解就是，累计节点度较高的路径会带来更复杂的消息，从而减弱每个节点的影响，而累计节点度较低的路径上消息更简单，可以直接将消息传递给目标节点。由于现实世界中的图通常边的密度比较高，因此节点影响会非常小。下面分析在局部子图上运行GNN和在整个图上运行GNN相比，不会丢失有用的信息。

（这个我觉得还挺有意思的，通过子图是不是可以曲线救国，解决大规模图上GNN难以训练的问题？）

2.1.3 定理2：局部子图可以保留属性

$S_u$表示节点u对应的邻居大小为h的局部子图，节点v定义为$v=argmax_w(\{I_{u,w}|w\in\mathcal V \setminus\mathcal V^u\})$。令$\bar t$表示u和v之间的一条路径，$D_{GM}^{\bar t}$表示路径$\bar t$上节点度的几何平均，$D_{GM}^{\bar t_*}=min_t\{D_{GM}^{\bar t}\}$，则有$R_h(u)\leq C\setminus (D_{GM}^{\bar t_*})^{t_*})^{h+1}$。

定理证明见原始论文Appendix D。定理2说明图的影响损失的上界受指数衰减项增长的限制（也就是公式中的$D_{GM}^{\bar t_*}$），换句话说，局部子图公式就是对整图公式的一个h-th阶近似。

2.1.4 利用局部子图实现小样本元学习

下面介绍局部子图如何帮助G-Meta实现小样本元学习。上面构建的子图捕捉了：（1）结构，图结构可以作为预测的一种alternative source of strong signal，尤其在节点标签有限的情况下。GNN由于训练复杂度过高，无法捕捉大型图结构，但是可以捕捉小型图的结构信息，比如本文中的子图。（2）特征，上面的理论分析表明局部结构子图保留了有效的信息。（3）标签，当只有少量有标签节点时，标签信息难以在整个图上得到有效传播。

基于度量学习的方法学习一个task-specific度量，通过计算和支持样本之间的距离判别查询样本的标签类别，这已经被证明了是一种很好地归纳偏置。通过同时捕捉了结构和特征信息的子图表示，G-Meta使用度量学习比较查询子图嵌入和支持子图嵌入之间的类型做预测。通过这些手段就可以规避掉只有少量标签导致信息不能有效传播的问题。

2.2 具体实现

2.2.1 子图编码

1. 在每个meta-task中，首先使用h-hops 邻居为每个节点$u$构造一个子图$S_u$（也可以使用其他子图提取算法）
2. 然后将子图$S_u$喂给一个h-layer的GNN来获取子图中每个节点的embedding，这里的h表示子图领域的大小。
3. 子图的中心节点$u$的嵌入用来表示整个子图的嵌入$h_u=Centroid(GNN(S_u))$。采用中心节点表示整个图的嵌入只是一种方法，也可以考虑其他的子图表示方法比如子图神经网络或者通过readout函数获取整个图的表示。

2.2.2 原型损失

得到子图表示后，作者利用表示和标签之间的归纳偏置来弥补小样本设定下标签信息不足的问题。对于每个标签k，我们用该标签下所有子图的表示的平均值作为原型$c_k$，即$c_k=1/N_k\sum_{y_j=k}h_j$作为标签k的标志。这样支持集和查询集中的所有子图对于标签k的类分布向量可以通过和支持原型之间的欧式距离计算得到：p_k=(exp(-||h_u-c_k||))/(\sum_\hat kexp(-||h_u-c_\hat k||))。然后基于此优化交叉熵损失：$L(p,y)=\sum_jy_jlog p_j$，其中y表示真实的标签one-hot向量。（这里就是度量学习常用的套路）

2.2.3 基于优化的元学习

为了在不同的图和标签之间迁移结构化知识，作者使用基于优化的元学习方法MAML。作者通过将节点划分到一个独立的局部子图来打破节点对图的依赖，这允许我们直接将子图应用到MAML，因为可以把单个子图看作传统小样本元学习设定下的单个图像。具体来说，我们首先采样一系列任务，每个任务包含一个子图集合。

元训练阶段

• 在元学习的inner-loop阶段，使用常规的stochastic梯度下降来由化每个任务$\mathcal T_i:\theta_j=\theta_{j-1}-\alpha\bigtriangledown\mathcal L_{support}$，更新后的参数用于query集，$\mathcal T_i$查询集的损失记作$\mathcal L^i_{query}$。上述操作重复执行$\eta$次。
• 然后将这一个batch的所有任务的最后一步得到的损失$\mathcal L_{query}^i$求和，然后执行元更新操作：$\theta=\theta-\beta\bigtriangledown\sum_i\mathcal L_{query}^i$。
• 然后采样新一批的任务，执行上述同样地步骤更新参数$\theta$。

元测试阶段

在meta-testing阶段，使用训练阶段最终得到的参数$\theta_*$执行训练阶段同样地流程。$\theta_*$是从多个meta-training任务中学习的的知识，是可以快速适应unseen任务的最优参数。

2.3 G-META的优点

• 伸缩性好：G-META在min-batch的子图上操作，子图大小和batch大小都很小，因此和之前那些在整个图上操作的方法相比，G-META计算很快，需要的内存也很小。
• 归纳学习：G-META的输入是GNN编码得到的不同的子图表示，强制模型在不可见子图上进行归纳推理。这种归纳学习对于小样本学习十分重要，小样本场景下模型需要适应unseen节点。归纳学习允许将知识从meta-training子图迁移到meta-testing子图上。
• 过平滑正则化：GNN的一个缺点就是过平滑问题，G-META不存在这个问题，因为每一轮都是单独将子图喂给GNN，并且子图的结构、大小和节点都是不一样的，这就规避了GNN的过平滑问题。
• 小样本学习：G-META只需要少量有标签节点就能取得不错的效果，而之前的GNN方法大多依赖于大量的有标签节点来传播信息。
• 应用广泛：G-META可以应用于许多图元学习问题，之前的方法通常只能解决其中一个。和之前的方法相比，G-META可以同时应用于节点分类和小样本链路预测。

作者对G-Meta的重要性做了一个总结：

1. G-Meta advances ML research
2. G-Meta can expedite scientific discovery
3. G-Meta can bring economic values
4. G-Meta can imporve equality

虽然图元学习方法性能不错，但是也存在一些潜在风险：

1. Negative transfer，元学习其实是一种训练上的小trick，有时候迁移的知识对于目标任务可能产生负影响
2. Misuse，元学习并不是通用的，在标签样本很多的时候没有必要使用（这点感觉是凑数的）
3. Adversarial attacks，由于有标签样本数量很少，每个有标签样本对于模型都很重要，因此容易受到对抗攻击（这应该是所有小样本问题的通病）

3. 实验

3.1 数据集

**两个人造数据集**：节点标签依赖于节点所处的结构，证明G-META可以捕捉局部图结构。

• Cycle：使用cycle basis图，并附加上一些形状分布：房屋、信息、钻石、扇形。每个节点的标签取决于由形状定义的结构角色。在多图任务中，每个图的形状数量分布不同。

• BA：为了能够在更真实的通构图中对局部结构信息建模，作者构建了一个Barabasi-Albert（BA）图，然后在图上添加不同的形状。多于多图问题，在每个图上添加不同数量分布的形状。

真实数据集：三个用于节点分类，两个用于链路预测。

3.2 实验设置

3.2.1 节点分类

5种label用于元测试，5中label用于元验证，其余的用于元训练。每个任务中，采用2-ways 1-shot设定，元训练阶段执行5步梯度更新，元测试阶段执行10次梯度更新（人造数据集）3-ways 3-shots，元训练阶段执行10步梯度更新，元测试阶段执行20次梯度更新（真实数据集）

对于多图任务（shared labels），10%的图用于测试，其余的图用于训练。

3.2.2 链路预测

10%的图用于测试，10%的图用于验证，对于每个图支持集包含30%的边，查询集包含70%的边。随机采样和正类边数目相等的负类边。每个任务采用16-shots，也就是只使用32个节点来预测unseen图上的边。元训练阶段执行10次梯度更新，元测试阶段执行20次梯度更新。每个实验重复执行5次，计算结果的标准差，超参的选择参见附件。

3.2.3 baseline

Meta-Graph，Meta-GNN，FS-GIN，Few-shot SGC四个图小样本元学习方法。No-Finetune，KNN，Fintune，MAML和ProtoNet五个表现比较好的元学习模型；ProtoNet和MAML可以看做对G-META的消融实验，即分别去掉MAML和原型损失。

3.3 实验结果

人造数据集

**真实数据集** 1. G-META可以捕捉局部结构信息

Meta-GNN、FS-GIN和FS-SGC都是基于整个图来做的，和作者基于子图的方法G-META相比效果要差，证明了子图嵌入可以捕捉局部结构信息，而使用整个图无法捕捉这些信息。在单个图的disjoint label设定下，KNN取得了最好结果，这表明从训练的嵌入函数学习到的子图表示足够铺捉到结构信息，进一步证实了构造局部子图的有效性

2. G-META性能良好、通用的图元学习方法

   G-META的性能优于MAML和ProtoNet。

3. 局部子图对于图小样本学习十分重要

   对比Meta-GNN、FS-GIN和FS-SGC这些作用在整个图上的方法，G-META性能更加优越，可以学习可迁移的知识，即使标签集是disjoint的