赞
踩
论文标题:Measuring and Relieving the Over-smoothing Problem for Graph NeuralNetworks from the Topological View(AAAI 2019)
论文链接:链接
图神经网络(GNNs)在许多基于图的任务中都取得了令人满意的性能。但是GNN存在过度平滑问题(在深层图神经网络中不同类别节点的表征不可区分)。本文对GNNs的过平滑问题进行了定量研究。首先,引入两个量化指标MAD
和MADGap
分别度量图节点表示的平滑性和过平滑性;其次证明了平滑是GNNs的固有特性,导致过平滑的主要原因是节点接收到的信息的低信噪比,这部分原因取决于图的拓扑结构。最后,本文从拓扑的角度提出了两种方法来缓解过平滑问题:
(1)MADReg,它在训练目标(Loss)上添加了一个基于MADGap的正则化项;
(2)AdaEdge,它根据模型的预测来优化拓扑结构。
过度平滑问题基础知识可以参考链接。
论文提出了两种度量关于平滑性的方法:
平均距离(MAD, Mean Average Distance)
:它通过计算图中节点表示(或表征)之间的平均距离来度量图的平滑性(本文中的平滑性是指图中节点表示的相似性)。GNN的MAD值随着GNN层数的增加而变小,通过GNN消息传播的节点交互将使它们的表示更加接近,因此在堆叠多层图神经网络时,整个图的表示将不可避免地变得平滑。MADGap
来度量图表示中的过平滑性。本文认为导致过平滑问题
的一个主要原因是信息和噪声的过度混合。来自其他节点的交互消息可能是有用的信息或有害的噪声。例如,在节点分类任务中,同类别节点交互可以带来有用的信息,而不同类别之间节点交互可能导致节点表征的不可区分性。
为了保证节点接收到的消息的质量,我们通过将GNN模型 信息噪声比
定义为同类别节点与所有有交互的节点的比例(个人理解是:在同一个连通图中,某一个类别节点与所有节点数量的比值)。我们注意到两个拓扑距离很近的节点(通过几跳即可到达)更可能属于同一类,反之亦然。因此,本文定义了远程节点
和相邻节点
(remote and neighboring node)两种类别节点,通过计算远程节点和相邻节点之间的MADGap的值来衡量图节点表征的过平滑程度。实验结果证明,MADGap与模型性能具有高度相关性,如下图所示。进一步的实验表明,随着信噪比的提高,模型性能和MADGap值都有所提高,验证了信噪比在很大程度上影响图表示的平滑性的假设。
论文认为低信息噪声比的原因是图的拓扑结构与下游任务(例如节点分类)的目标不一致。在节点分类任务中,如果不同类别的边过多,则经过几个传播步骤后,节点从其他类别的节点接收到的消息过多,从而导致过平滑。
论文提出了两种从拓扑角度解决过平滑问题的方法:
MADReg
:加上基于MADGap的正则化项,可直接增加接收到的信息,减少噪声(即无用的信息);自适应边优化(AdaEdge)
:通过迭代训练GNN模型,根据预测进行边删除/添加操作,对学习目标自适应调整图结构。论文的贡献可以分为三点:
MAD
和过平滑度的MADGap
,MADGap与模型性能具有高相关性。MADReg
和AdaEdge
来解决GNNs的过平滑问题。为了度量图表示的平滑度,论文首先提出了一个定量度量:平均距离(MAD)
。MAD通过计算节点到其他节点表征的平均距离来反映图形表示的平滑性。形式上,给定图的表示矩阵
H
∈
R
n
×
h
H∈R^{n×h}
H∈Rn×h(使用GNN最后一层的隐藏表示。称
h
h
h为隐藏层维度大小,
n
n
n为图节点数量),首先通过计算每个节点对之间的余弦距离得到表示矩阵
H
H
H距离矩阵
D
∈
R
n
×
n
D∈R^{n×n}
D∈Rn×n:
其中 H k , : H_{k,:} Hk,:是 H H H的第 k k k行。之所以使用余弦距离,是因为余弦距离不受节点向量绝对值的影响,从而更好地反映了图表示的光滑性。
然后用掩码矩阵
M
t
g
t
M^{tgt}
Mtgt对距离矩阵
D
D
D进行逐元素乘法滤波
式中 ◦ ◦ ◦表示按元素乘法; M t g t ∈ { 0 , 1 } n × n M^{tgt}∈\{0,1\}^{n×n} Mtgt∈{0,1}n×n;若节点对Node(i,j)为目标(指的应该是需要进行计算时)时,则 M i j = 1 M_{ij}=1 Mij=1
注: M t g t M^{tgt} Mtgt的作用和dropout中的矩阵作用差不多,取0时对应的节点对不计算距离。
接着按每行求得
D
t
g
t
D^{tgt}
Dtgt的非零值的平均距离矩阵
D
−
t
g
t
D^{-tgt}
D−tgt:
其中,如果x>0,则 1 ( x ) = 1 1(x)=1 1(x)=1,否则为 1 ( x ) = 0 1(x)=0 1(x)=0。注:因为余弦距离的范围为[0,2],即余弦距离不可为负。个人认为上式分母其实就是每行元素的个数,可简化。
最后,通过对
D
−
t
g
t
D^{-tgt}
D−tgt中的非零值求平均来计算给定目标节点对的MAD值
对于不同层数的GNN模型,我们通过考虑所有节点对,即
M
t
g
t
M^{tgt}
Mtgt中的所有值都是
1
1
1,来计算
M
A
D
MAD
MAD值
M
A
D
G
l
o
b
a
l
MAD_{Global}
MADGlobal,以度量学习到图表示的全局光滑性。
注: M A D t g t MAD^{tgt} MADtgt就是两两节点对的cos距离 D i j D_{ij} Dij之和求平均
CORA数据集的结果如下图所示。我们可以观察到,随着GNN层数量的增加,MAD值变小。特别的,深层GNNs的MAD值接近于0,这意味着深层GNNs中所有的节点(注:确切的说应该是同一连通分量中的所有节点)表征都变得不可区分(或趋于同一个值)。GNN模型根据相邻节点的特性更新节点表示,节点之间的相互作用(即聚合)使得它们的表征趋于相同。
论文假设过平滑问题是由信息和噪声的过度混合引起的,而信息和噪声的过度混合受节点接收信息质量的影响。从其他节点得到的交互信息可能是有用的信息,也可能是干扰噪声。例如,在节点分类任务中,同一类节点之间的交互(聚合)带来了有用的信息,使得它们的表示形式更加相似,从而提高了被分类到同一类的概率。相反,来自其他类别的节点的聚合动作带来了噪声。因此,GNNs能有效运行的原因是接收到的有用信息多于噪音,即当噪声大于信息量时,学习到的图表征会变得过于平滑(即过于相似)。
为了定量地衡量节点接收信息的质量,论文将信息噪声比(信噪比)
定义为通过GNN进行交互的某一类别节点与所有节点的比值。用于下图为CORA、CiteSeer和Pubmed数据集的的信息噪声比。我们可以发现在低阶时类内节点对较多,反之亦然。当模型层变大时,信息噪声比将降低,即高阶邻居之间的交互会产生过多的噪音并稀释有用的信息,这就是导致平滑问题的原因。在此基础上,我们将MAD
扩展到MADGap
来度量图表示中的过平滑性。在下图中我们可注意到两个具有较小拓扑距离的节点(低阶邻居)更可能属于同一类别。
因此论文提出利用拓扑学来逼近节点类别,并计算低阶邻居和高阶邻居的MAD值的差值来衡量图表示的过平滑性,即MADGap
:
其中 M A D r m t MAD^{rmt} MADrmt和 M A D n e b MAD^{neb} MADneb分为高阶邻居和低阶邻居的
平均距离(MAD)
MADGap
说明:
模型精度和MADGap之间的Pearson相关性系数,越接近+1代表正相关性越高。
pass
论文一共提供了两种方法来解决过平滑问题,具体如下:
将MADGap添加到训练目标(Loss)中,以使图节点收到更多有用的信息并减少干扰噪声:
交叉熵 L L L中, X X X为输入图特征矩阵, A A A为邻接矩阵, l h a t l^{hat} lhat和 l l l分别为节点的预测标签和正确标签, Θ Θ Θ为GNN的参数,而 λ λ λ是控制MADReg影响程度的正则化系数。(就是正则化公式,改变了正则化项)
本文提出了一种基于模型预测结果的自学习算法AdaEdge来优化图的拓扑结构,用以自适应地调整图的拓扑结构,使其更适合于特定的任务目标(即下游任务)。首先在原始图上训练GNN,然后根据模型的预测结果通过删除不同类别节点的边和添加相同类别的边来调整图的拓扑结构;然后在更新后的图上重新训练GNN模型。上述图形拓扑优化操作多次执行。
这篇论文对GNNs的过平滑问题进行了定量研究。
首先设计了两个量化指标:MAD
表示平滑度,MADGap
表示过平滑度。平滑是GNNs的本质,过平滑是由于信息和噪声的过度混合造成的。
此外,这篇论文发现MADGap与模型性能之间存在着显著的高度相关性。这篇论文还证明了噪声信息与图的拓扑结构有关,并通过优化图的拓扑结构使其更适合于下游任务,从而缓解了过度平滑问题。
这篇论文提出了两种方法来消除GNNs中的过平滑问题:MADReg方法和AdaEdge方法。
优化图拓扑是提高GNNs性能的有效途径,本文提出的AdaEdge方法仍然存在图调整操作错误的问题。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。