基于神经稀疏化的鲁棒图表示学习-ICML2020

摘要：提出了NeuralSparse，这是一种监督图的稀疏化技术，通过学习从输入图中取出潜在的与任务无关的边来提高泛化能力。该方法以结构和非结构信息维输入，利用深度神经网络参数化稀疏化过程，并通过来自下游任务的反馈信号对参数进行优化。在NeuralSparse框架下，有监督的图稀疏化可以现有的图神经网络无缝衔接，从而或的更鲁棒的性能。

一、引言

1、问题引入

• 两个节点连接的潜在动机可能与目标下游任务无关，这种与任务无关的边可能会损害邻域聚合，影响gnn的性能。

2、方案

• 我们提出了神经稀疏(Neural Sparsification, NeuralSparse)，这是一个通用的框架，它可以同时学习通过来自下游任务的反馈信号来选择与任务相关的边和图表示。NeuralSparse由两个主要部分组成:稀疏化网络和GNN。
  （1）对于稀疏化网络，我们利用深度神经网络参数化稀疏化过程:如何从给定固定预算的单跳邻域中选择边。在训练阶段，网络学习优化一个有利于下游任务的稀疏化策略。在测试阶段，网络按照学习到的策略对输入图进行稀疏化，而不是根据预定义的分布对子图进行抽样。与传统的稀疏化技术不同，我们的技术采用结构性和非结构性信息作为输入，并通过来自下游任务的反馈来优化稀疏化策略，而不是使用(可能不相关的)启发式。
  （2）对于GNN组件，NeuralSparse将稀疏化的图馈给GNN，并学习图的表示，以完成后续的预测任务。在NeuralSparse框架下，通过标准的随机梯度下降和反向传播技术，我们可以同时优化图的稀疏化和表示。

二、相关工作

• 图表示学习：
  1）Scarsellli等人研究了如何通过迭代邻域聚合提取多跳邻居特征。
  2） ABU-研究GNN的表达能力。
  3） Ying利用训练好的GNN识别关键子图结构。
  4）Franceschi等人研究了如何通过学习单个边上的伯努利变量，从转导设置中采样高质量的子图。
  5）最近的研究还试图从预定义的分布中采样子图，以及通过随机边下降来正则化图学习。

三、提出的方法：神经稀疏

1、符号定义

2、理论调整

• 我们希望利用稀疏的子图来删除与任务无关的信息，而不是直接使用原始图。换句话说，我们对下面的变量感兴趣，
  
• 一般情况下，由于图的组合复杂性，很难列举出所有可能的g，也很难估计P (Y |g)和P (g |g)的精确值，因此，我们用可处理函数逼近分布：
  
• 此外，为了使上述图的稀疏化过程可微，我们采用重参数化技巧(Jang et al.， 2017)使\(Q_{φ}(g | G)\)直接生成可微样本，从而
  

3、架构

• 如图2所示，NeuralSparse由两个主要组件组成:稀疏化网络和gnn。
  （1）稀疏化网络是一种实现\(Q_{φ}(g | G)\)的多层神经网络:以G为输入，根据学习分布生成g的随机稀疏化子图。
  
  (2) gnn实现\(Q_{θ}(Y | g)\)，以稀疏化的子图作为输入，提取节点表示，并对下游任务进行预测。

四、稀疏化网络

• 根据上面讨论的理论，稀疏化网络的目标是为输入图生成稀疏化子图，作为近似函数\(Q_{φ}(g | G)\)，因此，在稀疏化网络中，我们需要回答以下三个问题:
  i).方程1中的SG是什么，我们关注的一类子图?
  ii).如何对稀疏化的子图进行采样?
  iii).如何使稀疏化子图采样过程对端到端训练具有可微性?下面，我们将逐一回答这些问题

1、k跳邻居子图

我们关注SG的k-neighbor子图(Sadhanala et al.， 2016):给定一个输入图，一个k-neighbor子图与输入图共享相同的节点集，子图中的每个节点可以从它的单跳邻域中选择不超过k条边。

• 我们可以通过调整超参数k来调整对任务相关图数据量的估计。直观地说，当k被低估时，gnn访问的任务相关图数据量可能不足，从而导致性能低下。当k过高估计时，下游的gnn可能会对引入的噪声或无关图数据进行过拟合，从而导致性能不佳。可能很难设置一个全天候工作的黄金超参数，但人们可以自由选择最适合特定任务的k。
• k近邻图对并行计算是友好的。由于每个节点独立于其邻域选择自己的边，我们可以在现有的深度学习框架中利用张量运算，如tensorflow (Abadi et al.， 2016)，来加速k-neighbor子图的稀疏化过程

2、采样k跳邻居子图

在给定k和一个输入图G = (V, E, A)的情况下，通过对原始图中每个节点的边进行多次采样，得到一个k-neighbor子图。不失一般性，我们通过关注图g中的一个特定节点u来描述这个采样过程。设Nu是节点u的单跳邻居集合。

• v~\(f_{φ}(V(u)， V(N_{u})， A(u))\)，其中fφ(·)是根据节点u的属性、u的邻居v(Nu)的节点属性及其边属性A(u)，从学习到的分布中生成一个单跳邻居v的函数。特别地，学习分布是用参数φ进行编码的.
• 边E(u, v)被选
• 上述过程重复k次
• 注意，上面的流程执行的采样不需要替换。给定一个节点u，它的每一条相邻边最多被选中一次。节点间共享采样函数fφ(·);因此，参数φ的个数与输入图的尺寸无关。

3、使样本可微

• 虽然传统方法可以生成离散样本(Sadhanala et al.， 2016)，但这些样本是不可微的，因此很难利用它们来优化样本生成。为了使样本具有可微性，我们提出了一个基于GumbelSoftmax的多层神经网络来实现上面讨论的采样函数fφ(·)。
• 为了使讨论独立，我们简要讨论了Gumbel-Softmax的概念。Gumbel-Softmax是一种用于生成可微离散样本的重参数化技巧(Jang等人，2017;麦迪森等人，2017)。在适当的超参数设置下，Gumbel-Softmax能够生成与广泛用于编码离散数据的单一热向量一样“尖锐”的连续向量。
• 不失一般性，我们关注图G = (V, E, A)中的一个特定节点u。设\(N_{u}\)为节点u的单跳邻居集。我们实现\(f_{φ}(·)\)如下所示。
  （1）
  （2）
  （3）而τ是一个称为温度的超参数，它控制着离散分布和连续分类密度之间的插值
  注意，当我们采样k条边时，zu,v和πu,v的计算只需要执行一次。对于超参数τ，我们将如下讨论如何调优它

4、Discussion on temperature τ tuning

• 当τ很小时，Gumbel-Softmax分布近似于离散分布，具有较强的稀疏性;然而，小τ也会引入高方差梯度，从而阻碍有效的反向传播。当τ值较大时，不能产生期望的稀疏化效应。在(Jang et al.， 2017)的实践之后，我们采用了这样的策略:以高温开始训练，并在有指导的时间表下将其退火到一个小值。

六、总结

在本文中，我们提出了神经稀疏(Neural Sparsification, NeuralSparse)来解决现实生活中的大型图上任务相关信息带来的噪声问题。NeuralSparse由两个主要部分组成:(1)稀疏化网络通过按照学习后的分布进行边采样来对输入图进行稀疏化;(2) gnn以稀疏化的子图作为输入，为下游任务提取节点表示。
NeuralSparse中的两个组件可以通过监督损耗、梯度下降和反向传播技术联合训练。对真实数据集的实验研究表明，NeuralSparse始终能够提供更健壮的图表示，与最先进的GNN模型相比，其准确性提高了7.2%。

【
1、Gumbel-Softmax：用于生成可微离散样本的重参数化技巧
2、自监督、梯度下降、反向传播技术联合
】