Adaptive Diffusion in Graph Neural Networks论文阅读笔记

Abstract

​ 最近提出了图扩散卷积（GDC），利用广义图扩散来扩展传播邻域。然而，GDC中的邻域大小是通过在验证集上进行网格搜索来手动对每个图进行调整的，这使得其泛化实际上受到了限制。为了解决这个问题，我们提出了自适应扩散卷积（ADC）策略，从数据中自动学习最优邻域大小。我们打破了传统的假设，即所有的GNN层和特征通道（维数）都应该使用相同的邻域大小来进行传播。我们设计的策略使ADC能够为每个GNN层和每个特征通道学习一个专用的传播邻域，使GNN体系结构与图结构完全耦合——这是GNN不同于传统神经网络的独特特性。通过将ADC直接插入到现有的gnn中。

Introduction

​ 现有的方法有一个隐式的假设，即所有的图数据集在消息传递过程中共享相同大小的接受域。为了打破这一问题，最近提出了图扩散卷积（GDC），将GCN中的离散信息传递过程扩展到扩散过程，使其能够从更大的邻域聚合信息。对于每个输入图，GDC通过网格搜索验证集上的参数，手工调整特征聚合的最佳邻域大小，使其实际应用受到限制和并且很敏感

​ 为了消除GDC中最优传播邻域的人工搜索过程，我们提出了自适应扩散卷积（ADC）策略，支持从数据中自动学习最优邻域。ADC通过将任务形式化为一个二层优化问题来实现这一点，允许为每个数据集定制学习一个最优传播邻域大小。换句话说，在在每个图上传递消息时，所有GNN层和特征通道（维度）共享相同的邻域大小。

​ 为了进一步发展这个方向，我们还允许ADC从数据中自动学习每个GNN层和每个特征通道的定制邻域大小。通过为每一层学习一个独特的传播邻域，ADC可以使gnn从不同的图结构中捕获邻居的信息，这完全依赖于数据和下游的学习目标。类似地，通过学习每个特征通道的不同邻域大小，gnn就能够有选择性地建模每个邻居的多个特征信号。总之，ADC使gnn与图结构和所有特征通道完全耦合。

​

GNN的邻域半径

​ 基于图的模型可以表示为：\(\gamma^{(l)}(\mathbf{\hat{H}},G)=f(\mathbf{T})\mathbf{\hat{H}}\)，f(T)可以表示为：\(\sum_{k=0}^\infty\theta_k\mathbf{T}^k\)，其中：\(\mathbf{T}=\mathbf{\tilde{D}}^{-\frac12}\mathbf{\tilde{AD}}^{-\frac12}\)于是我们就可以定义邻域半径为：

​ \(r=\frac{\sum_{k=0}^\infty\theta_kk}{\sum_{k=0}^\infty\theta_k}\)

​ 对于较大的节点，这意味着模型更强调长距离节点，即全局信息。对于一个较小的r，这意味着该模型放大了局部信息。

​ 对于GCN，邻域半径r = 1，它只是直接连接到它的节点的范围。为了收集直接连接之外的信息，需要堆叠多个GCN层，以到达高阶邻居。并且对于所有的多跳模型，跳数的离散性质使得r不可微。

​ 对于图扩散卷积来说，\(\gamma^{(l)}(\mathbf{\hat{H}},G)=\sum_{k=0}^\infty\theta_k\mathbf{T}^k\mathbf{\hat{H}}\) 且 \(\begin{aligned}\sum_{k=0}^\infty\theta_k=1\end{aligned}\),这样，信号的强度就不会通过传播而被放大或降低。两个常用的权重系数为PangeRank：\(\begin{aligned}\theta_{k}=\alpha(1-\alpha)^{k}\end{aligned}\)和热核

\(\theta_k=e^{-t}\frac{t^k}{k!}\)

​ 根据上述的邻域半径的公式，可得热核的邻域半径是t，这说明t是基于热核的GDC的邻域半径，即t在多跳模型中成为跳数的完美连续替代品。

自适应图扩散卷积

​ 图扩散卷积的热核版本为：

​ \(\gamma^{(l)}(\mathbf{\hat{H}},G)=e^{-\mathbf{L}t}\mathbf{\hat{H}}=\sum_{k=0}^\infty e^{-t}\frac{t^k}{k!}\mathbf{T}^k\mathbf{\hat{H}}\)，其中\(\mathbf{L}=\mathbf{I}-\mathbf{T}\)

​ 对于每个图形数据集，都需要手动网格搜索步骤来确定与邻域半径相关的参数t。此外，每个数据集中的所有特征通道和传播层都是固定的。在这项工作中，我们探索了如何自适应地从每个图的数据中学习邻域半径，并进一步研究了如何将其推广到不同的特征通道和GNN层的潜力。

训练邻域的半径

​ 扩散卷积使我们能够用连续热核代替GNNs的离散特征传播函数。我们可以计算t的梯度，并更新t，收敛到最优邻域，这与学习模型中的其他权重和偏差参数相同。

​ 但是发现直接在训练集上应用上述的方法的效果并不理想，为了解决这个问题，我们提出了一种通过在验证集上使用模型的梯度来训练t的方法。该模型的目标是找到最小化验证损失\(\mathcal{L}_{val}(t,w^*)\)，其中w表示特征变换函数中的所有其他可训练参数，w∗表示最小化训练损失\(\mathcal{L}_{train}(t,w)\)的参数集。该策略可以形式化为一个二层优化问题：

\[\begin{aligned}t^*&=\arg\min_t\mathcal{L}_{val}(t,w^*(t))\\\\w^*(t)&=\arg\min_w\mathcal{L}_{train}(t,w)\end{aligned} \]

​ 通过这样做，每次更新t，我们需要使w收敛到最优值，这对训练太昂贵了。一种近似方法是每次我们更新w时都更新t，即

\(w^{(e+1)}=w^{(e)}-\alpha_1\bigtriangledown_w\mathcal{L}_{train}(t^{(e)},w^{(e)})\)

\(t^{(e+1)}=t^{(e)}-\alpha_2\bigtriangledown_t\mathcal{L}_{val}(t^{(e)},w^{(e+1)})\)

​ 其中，e为训练周期的个数，α1和α2分别表示在训练集和验证集上的学习率。在基于梯度的超参数调优和神经结构搜索中也提出了类似的想法。使用这种方法有助于避免过拟合，从而提供了更好的泛化，因为没有测试精度下降的迹象。同时，t不减小到零，表明该参数-邻域半径的有意义的学习。

​

训练每个层和通道的邻域半径

模型的示意图如下：

聚合的策略为：

\(\gamma^{(l)}(\mathbf{\hat{H}},G)_i=\sum_{k=0}^\infty e^{-t_i^{(l)}}\frac{\left(t_i^{(l)}\right)^k}{k!}\mathbf{T}^k\mathbf{\hat{H}}_i\)

广义自适应扩散卷积（GADC）。目前，我们引入了基于热核的自适应扩散卷积方法。在不丧失一般性的情况下，我们可以将ADC扩展到一个广义的ADC（GADC），即不限制权重系数θk作为热核。因此，我们有GADC的特征传播为：

\(\gamma^{(l)}(\mathbf{\hat{H}},G)_i=\sum_{k=0}^\infty\theta_{ki}^{(l)}\mathbf{T}^k\mathbf{\hat{H}}_i\) 且 \(\sum_{k=0}^{\infty}\theta_{ki}^{(l)}=1\)