标题：GRAIN: 通过多样化影响力最大化提升GNN的数据效率

编者的总结

1. 本文的问题是GNN中数据选取的问题（即，选取固定数量的输入子集使得模型效果不受大的影响），主要贡献是把数据选取的问题和图算法中影响力最大化的问题结合起来，将图上的特征传播（GNN中的主要奏效部分）视为影响力的传播，因此只需找到能使得影响力最大化的数据子集即完成任务。
2. 最终的选择算法是贪心的，很简单；主要的挑战点在于如何定义一个点的特征对另一个点的影响力（特征传播后的结果对出发点的求导）、如何评估coreset传播后对整个图的影响程度（激活点+激活点周围的区域）。
3. 由于只保留了原始图特征上的特征传播，没有引入GNN中的层间转换（线性变换+激活），所以大大减少了计算量。

2 PRELIMINARY

2.1 Data Selection Problems

给定一个图，每个节点都代表一个d维输入特征向量，ground truth标签是一个C维向量，只有一个元素是1，代表属于该分类。
将图分区，分为训练集、验证集和测试集。

2.1.1 Active Learning

主动学习的是从训练集中选出一部分点去打标签，然后利用这部分数据训练模型，最终使得在测试集上损失函数最小。

2.1.2 Core-set Selection

核心集选取是说从训练集中取出一部分，使得用这个子集来训练模型和用全集训练的模型得到的效果差不多，即测试集上损失函数值相近。和主动学习的概念其实很相似，方法也有些通用。
主要工作有：

• greedy k-centers：选择和有标签的点最小距离最大的点去打标签；
• forgetting events：是指那些曾经在训练过程中分类正确的点但后来又分类错误了；
• max entropy：选择那些熵值最高的点。

2.2 Graph Neural Networks

3 GRAIN FRAMEWORK

image.png

3.1 Feature Influence Mode

3.1.1 Decoupled Feature Propagation

• 作者认为GNN包含两部分的映射，一部分是层内的特征传播，另一部分是层间的特征转换（即传统NN上的线性组合+非线性激活）。
• 在这二者之中，前者，也就是层内的特征传播（文中称作邻居间的特征平滑）是GNN效果的主要来源；（此观点是近5年顶会中提出）
• 与之相对，层间的层次化非线性转换则并不重要，这和经典的CNN理论是不一样的。

• 在这种情况下，作者选择把这二者从训练模型中解耦出来，即只做层内的特征传播，通过传播函数传播k次。这个传播函数没有训练参数，没有激活函数，只依赖输入特征和传播模型，典型的传播模型如下表：（其中的T是传播函数，依赖于图结构，即邻接矩阵）

  
  image.png

3.1.2 Feature Influence Viewpoint

• 在给定上述的特征传播下，可以获得k-跳的特征传播结果，即每个节点的聚合特征。
• 这种特征传播也可以看作是一种影响力传播，那现在我们希望能判定一个点u在另一个点v上的影响力有多大（即特征影响力），则可以通过计算u的输入特征多大程度上影响了k-跳后v的传播结果。

• 如下式，具体定义为雅克比矩阵期望的一范数。

  
  image.png
• 一个点集S对点v的影响可以被定义为S中的点对v影响的最大值。

3.2 Diversified Influence Maximization

• 在定义好一个/组点对另一个点的影响力之后，就可以通过一个阈值来确定一个点能否被激活。
• 这里是说：我们有一组种子点已经激活了，现在通过影响力传播的方式看看哪些其他的点也能被激活。
• 注意我们的问题是在图数据上选择一组最关键的数据子集用于训练，现在开始考虑能否用影响力传播最大化的指标来判断哪些数据点是关键点。也就是说，如果某一组点k-跳在图上造成的传播效果更好，比如能激活更多的点，就可以作为关键点选取出来。
• 如果上述的这个关系成立，图数据选取的问题就演变成了寻找能使得影响力最大化的点集的问题。

• 针对这个关系的验证，作者做了预实验，如下图a，相同数量的一个子集，如果传播影响点的数量越多，模型准确率也会越高。这个现象启示我们去寻找能激活更多点的子集。

  
  image.png
• 但如果细看图a，会发现蓝色区域其实很大，这个规律的方差是比较大的。作者解释原因是只考虑数量的话会忽视掉节点间的关系，也就是图结构。换句话讲，激活一些点比激活另一些点的用处会大一些。
  • 具体来说，因为k-跳后的传播图里包含了图结构信息和原有的特征信息，所以大概可以判断相近的点会预测出类似的结果；因此我们最好把coreset互相选的比较远，以此覆盖更多的区域。

到此为止，就可以给出本文提出的coreset selection的判定函数，见下式：第一项是传播的数量，第二项是传播的多样性，或者说覆盖的区域大小。

image.png

• D(S)的具体计算方式可见下图，作者提出用一个固定半径的以激活点为中心的球进行覆盖，覆盖到的点算间接影响的，计入上式第二项。

• 和传统的覆盖式方法相比，这里的计算是在传播之后确定的，因此图的结构也是纳入考虑的。

  
  image.png

3.4 Selection Algorithm

下面我们把整体的方法汇总一下，输入是一个图，每个节点有特征向量，输出是一个coreset，即节点子集，有固定的大小，为用户输入：

1. 第一步把原始图k-跳传播算出来；
2. 初始化coreset为空；
3. 遍历所有的未选择节点，让每一个点v尝试加入coreset：
   1. 计算加入v后能多激活图中多少点；
   2. 计算加入v后多样性能提升多少；
   3. 根据上面两项，计算判定函数能增加多少；
   4. 选择判定函数增益最多的点加入coreset。
4. 重复过程3，直到coreset已满。

这个整体算法明显是贪心的，但是判定的函数设计过程中注意保持了一些性质（单调性和边际效应submodular），使得增益函数的质量是有数学保证的，不详细展开了。