图形网络的自适应扩散笔记-易微帮

1 Title

Adaptive Diffusion in Graph Neural Networks（Jialin Zhao、Yuxiao Dong、Ming Ding、Evgeny Kharlamov、Jie Tang）【NIPS 2021】

2 Conclusion

The neighborhood size in GDC is manually tuned for each graph by conducting grid search over the validation set, making its generalization practically limited. To address this issue,this study proposes the adaptive diffusion convolution (ADC)* strategy to automatically learn the optimal neighborhood size from the data. Furthermore, this paper breaks the conventional assumption that all GNN layers and feature channels (dimensions) should use the same neighborhood size for propagation.

3 Good Sentences

1、B oth strategies are limited to a pre-determined and fixed neighborhood for passing and receiving messages. Essentially, these methods have an implicit assumption that all graph datasets share the same size of receptive field during the message passing process.(The limitations of previous GCN methods)
2、To eliminate the manual search process of the optimal propagation neighborhood in GDC, we propose the adaptive diffusion convolution (ADC) strategy that supports learning the optimal neighborhood from the data automatically. ADC achieves this by formalizing the task as a bilevel optimization problem, enabling the customized learning of one optimal propagation neighborhood size for each dataset. In other words, all GNN layers and feature channels (dimensions) share the same neighborhood size during message passing on each graph.（The motivation of this study which can solve the problems GDC meets）
3、

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

为了进一步实现这一目标，ADC能够从数据中自动学习每个GNN层和每个特征通道的自定义邻域大小。通过为每层学习唯一的传播邻域，ADC可以使gnn从不同的图结构中捕获邻居信息，这完全依赖于数据和下游学习目标。

同样，通过学习每个特征通道的不同邻域大小，gnn能够选择性地对每个邻居的多个特征信号进行建模。总之，ADC使gnn与图结构和所有特征通道完全耦合。

Neighborhood Radius in GNNs

本文研究了半监督节点分类问题。输入包括无向网络G = (V;E)，其中节点集V包含n个节点，E为边集，A∈ $R^{n\times n}$ 为图G的对称邻接矩阵。给定输入特征矩阵X和节点标签Y的一个子集，任务是预测剩余节点的标签。

Neighborhood Radius in Message Passing Networks：

在消息传递网络中，每个节点会收集来自其邻居节点的特征信息，并将这些信息聚合起来以更新自己的状态。消息传递网络可以简单定义为：

这个过程通常在图神经网络的每一层中进行。"Neighborhood Radius" 指的是在消息传递过程中，一个节点能够聚合多远距离邻居的信息。其中， $H(l)$ 表示第 $l$ 层的隐藏特征， $H(0)=X$ , X为输入特征的第1层隐藏特征， $\varphi$ (·)表示特征变换，γ(·)表示特征传播。

特征转换函数描述了特征如何在每个节点内部转换，特征传播函数描述了特征如何在节点之间传播。

，D为对角线上的元素是节点的度的矩阵， $\tilde{H}$ 表示变换后的隐特征，不过GCN使用带有自循环的邻接矩阵A。

大多数基于图的模型都可以表示 $f(T)$ =，

邻居半径r被定义为：， $\theta _k$ 表示k个步距节点的影响。对于较大的r，这意味着模型更强调远距离节点，即全局信息。对于较小的r，这意味着模型放大了局部信息。对于GCN，邻域半径r = 1

Neighborhood Radius in Graph Diffusion Convolution

图扩散卷积(GDC)的传播解决了从离散跳数的特征传播到连续图扩散的推广问题：，k从0到无穷求和，使得每个节点都聚集了整个图的信息。而权重系数满足，这样在传播过程中信号强度不会被放大或减弱。论文原句：In this work, we focus on heat kernel，也就是说作者令

HK：热核将先验知识引入到GNN模型中，这意味着特征在节点之间的传播遵循牛顿冷却定律，即两个节点之间的特征传播速度与它们之间的特征差成正比。在形式上，这种先验知识可以描述为:

其中N(i)表示节点i的邻域， $x_i(t)$ 表示节点i在扩散时间t后的特征。微分方程可解为:，X(t)为扩散时间t后的特征矩阵，是热核

Neighborhood radius $r_h$ in diffusion models

根据邻域半径的定义，GDC的热核版本邻域半径 $r_h$ 的定义为：

这表明t是基于热核的GDC的邻域半径，即t成为多跳数模型中跳数（hop-number）的完美连续替代。

Adaptive Diffusion Convolution

其中，拉普拉斯矩阵 $L=I-T$ ，对于每个图数据集，需要手动网格搜索步骤来确定与邻域半径相关的参数t，此外，对于每个数据集中的所有特征通道和传播层，t是固定的。

Training Neighborhood Radius

上图显示了学习t的训练过程。随着epoch的增加，在训练集(蓝色)上学习时，t和训练损失都减小。同时，验证和测试精度急剧下降，因为t趋于零(更多的epoch) -表示每个节点只能使用自己的特征来预测标签，也就是说，直接在训练集上学习t会导致过拟合。

为了解决这个问题，本文提出了一种通过在验证集上使用模型的梯度来训练t的方法。该模型的目标是找到使验证损失，其中w表示特征变换函数中所有其他可训练参数，w *表示使训练损失。该策略可以形式化为一个双层优化问题

如果按上面的方法，每次更新t时，需要使w收敛到最优值，这就太贵了。一种近似方法是每次更新w时更新t，也就是说，，其中，e表示训练epoch的个数，α1和α2分别表示训练集和验证集的学习率。

Training Neighborhood Radius for Each Layer and Channel：

对于GDC，一个数据集有一个邻域半径t，即所有GNN层和所有特征通道(维度)都有相同的t。先前模型无法实现这一目标的障碍在于，考虑到随着参数数量的增加，时间复杂度呈指数增长，对每个特征通道和GNN层的传播函数分别进行手动调整或网格搜索是不可行的挑战。然而，前面提到的在模型训练过程中更新t的策略使得ADC能够自适应地学习所有层和所有特征通道的特定t。本文通过将特征传播函数扩展到每个层和通道，即从t到 $t_i^{(l)}$ ，得到自适应扩散卷积(ADC)，，其中 $t_i^{(l)}$ 表示第 $l$ 层和第 $i$ 通道的邻域半径t, $\hat{H}_i$ 表示隐藏特征 $\hat{H}$ 的第 $i$ 列，即通道 $i$ 上的特征，表示第 $l$ 层和第 $i$ 通道上的特征传播函数.