KDD 2022 | 深度图神经网络中的特征过相关：一个新的视角

admin • 2022-11-20 20:03 • 人工智能

前言

题目： Feature Overcorrelation in Deep Graph Neural Networks: A New Perspective
会议： KDD 2022
论文地址：Feature Overcorrelation in Deep Graph Neural Networks: A New Perspective

众所周知，当图神经网络中层数过多时，会造成过平滑问题。所谓过平滑，是指随着GNN的深度增加，越来越多的节点表示倾向于收敛到某个固定的值，从而变得不可区分，这会大大降低模型的性能。

本文从一个全新的视角来研究深度GNN的性能退化问题，即特征过相关，更具体地讲，是特征的所有维度两两之间的相关性过高。文章发现，当GNN层数过多时，不仅仅只会出现过平滑，同时，最后得到的节点特征在维度间存在着较高的相关性。本文通过对这一问题的实证和理论研究，证明了更深层次的GNN中特征过相关的存在，并揭示了导致这一问题发生的潜在原因。为了减少特征相关性，本文提出了一个通用框架DeCorr，它可以让GNN编码更少的冗余信息。实验表明DeCorr可以帮助实现更深层次的GNN，并对现有的解决过平滑问题的技术起到了补充作用。

1 引言

图神经网络应用越来越广泛，一个很自然的想法是：能不能通过增加层数来增加模型精度？因为更深的层意味着更大的感受野，模型能够提取到节点的更多跳邻居的信息。然后，事实却是当模型深度增加时，GNN的性能或急速下降。现有的工作大多将其归因于过平滑，本文另辟蹊径，提出了特征维度过相关的概念。

本文通过回答三个问题来系统地研究深层GNN中的过相关问题：(1)过相关问题是否存在？(2)是什么导致了过相关问题？(3)过相关和过平滑之间的关系和区别是什么？通过探索这些问题，文章发现当堆叠更多的GNN层时，过多进行特征传播和变化通常会导致特征维度更加相关，同时也会过平滑。但反之，特征过平滑时不一定特征维度过相关。

2 背景和相关工作

本文中图被表示为

(

)

mathcal{G}=(mathcal{V},mathcal{E},X)

$G = (V, E, X)$ ，其中

{

}

mathcal{V}={ v_{1}, v_{2},...,v_{N} }

$V = {v_{1}, v_{2}, ..., v_{N}}$ 表示

$N$ 个节点的集合，

∈

mathcal{E} in mathcal{V} times mathcal{V}

$E \in V \times V$ 是描述节点之间关系的一组边，

∈

X in R^{N times d}

$X \in R^{N \times d}$ 为节点的特征矩阵。图也可以用邻接矩阵

∈

{

}

A in { 0, 1 }^{N times N}

$A \in {0, 1}^{N \times N}$ 来表示，如果节点

v_{i}

$v_{i}$ 和

v_{j}

$v_{j}$ 间存在边，则

A_{ij}=1

$A_{ij} = 1$ ，否则

A_{ij}=0

$A_{ij} = 0$ 。此时，图也可以表示为

(

)

mathcal{G}=(A, X)

$G = (A, X)$ 。

2.1 GNN

图神经网络模型通常由几个GNN层组成，其中每一层都将前一层的输出作为输入。每个GNN层通过传播和变换其邻居的表示来更新所有节点的表示。更具体地说，第

$l$ 个GNN层可以描述如下：

(

)

(

−

)

∣

∈

(

)

∩

{

}

)

H_{i,:}^{(l)}={rm Transform}({rm Propagate}(H_{j,:}^{(l-1)} | v_{j} in mathcal{N}(v_{i}) cap { v_{i} }))

$H_{i, : (l)} = Transform (Propagate (H_{j, : (l - 1)} ∣ v_{j} \in N (v_{i}) \cap {v_{i}}))$
其中

(

)

H_{i,:}^{(l)}

$H_{i, : (l)}$ 表示经过第

$l$ 个GNN层后节点

v_{i}

$v_{i}$ 的表示，

(

)

mathcal{N}(v_{i})

$N (v_{i})$ 表示节点

v_{i}

$v_{i}$ 的邻居节点集合。对于一个

$L$ 层的图神经网络模型来讲，令

(

)

H^{(L)}

$H^{(L)}$ 为所有节点的最终表示，其可用于各种下游任务。

我们所熟知的GCN将上式实现为：

(

)

(

−

(

−

)

(

)

H^{(l)}=sigma(tilde{D}^{-frac{1}{2}}tilde{A}tilde{D}^{-frac{1}{2}}H^{(l-1)}W^{(l)})

$H^{(l)} = σ (D ~^{- \frac{1}{2}} A ~ D ~^{- \frac{1}{2}} H^{(l - 1)} W^{(l)})$
这里

tilde{A}=A+I

$A ~ = A + I$ ，

tilde{D}

$D ~$ 为相应的度矩阵，

(

)

W^{(l)}

$W^{(l)}$ 为参数矩阵，

(

⋅

)

sigma(cdot)

$σ (\cdot)$ 表示某种激活函数。在公式(3)中，

(

)

W^{(l)}

$W^{(l)}$ 用于特征变换，而

−

tilde{D}^{-frac{1}{2}}tilde{A}tilde{D}^{-frac{1}{2}}

$D ~^{- \frac{1}{2}} A ~ D ~^{- \frac{1}{2}}$ 则用于特征传播过程。

2.2 相关工作

深度堆叠GNN层会导致显著的性能恶化，这通常归因于过平滑问题，即学习的节点表示变得高度不可区分。为了解决过平滑问题并实现更深层次的GNN，已经提出了各种方法。例如，PairNorm通过规范化层保持节点表示的总成对距离恒定。类似地，DGN还通过独立地规范化每组相似节点来规范化节点表示，以保持组距离比和实例信息增益。与归一化方法不同，DropEdge建议从图中随机删除一定数量的边，这已被证明可以缓解过平滑和过拟合问题。然而，大多数工作的目标是解决过平滑问题，而忽略了特征过相关问题。在本文中，对过相关问题进行了系统的研究，并提供了有效的解决方案。

3 Preliminary Study

这节主要讲解过平滑和过相关间的联系与区别。

3.1 过相关和过平滑

这节证明了堆叠多个图神经网络层可以显著增加特征维度之间的相关性。文章选择皮尔逊相关系数来评估深层GNN中特征维度之间的相关性。具体来讲，给定两个向量

∈

xin R^{N}

$x \in R^{N}$ 和

∈

yin R^{N}

$y \in R^{N}$ ，它们间的皮尔逊相关系数可以定义如下：

(

)

∑

(

−

)

(

−

)

∑

(

−

)

∑

(

−

)

rho(x, y) = frac{sum_{i=1}^{N}(x_{i}-bar{x})(y_{i}-bar{y})}{sqrt{sum_{i=1}^{N}(x_{i}-bar{x})^{2}} sum_{i=1}^{N}(y_{i}-bar{y})^{2}}

$ρ (x, y) = \sum _{i = 1 N} ( x _{i} - x ˉ ) ^{2}$

∑i=1N(yi−yˉ)2∑i=1N(xi−xˉ)(yi−yˉ)
其中

bar{x}

$x ˉ$ 和

bar{y}

$y ˉ$ 分别表示

$x$ 和

$y$ 的平均值。本质上，皮尔逊相关系数将两个变量之间的协方差归一化，并度量两个变量彼此线性相关的程度。

(

)

rho(x, y)

$ρ (x, y)$ 的值范围为

[

−

]

[-1, 1]

$[- 1, 1]$ ，值的绝对值越高表明两个变量越相关。此外，本文提出了

Corr

$C orr$ 用于度量

∈

Xin R^{N times d}

$X \in R^{N \times d}$ 中所有维度间的相关性：

(

)

(

−

)

∑

≠

∣

(

)

∣

Corr(X) = frac{1}{d(d-1)}sum_{i neq j}|rho(X_{:,i}, X_{:,j})|

$C orr (X) = \frac{1}{d ( d - 1 )} i \neq = j \sum ∣ ρ (X_{:, i}, X_{:, j}) ∣$
其中

X_{:,i}

$X_{:, i}$ 表示

$X$ 的第

$i$ 列，简单来讲，就是计算所有列两两之间的皮尔逊相关系数再求均值。由于也需要研究过平滑问题，文章使用一些文献中提出的度量

SMV

$SM V$ ，其使用归一化节点表示来计算它们的欧几里得距离：

(

)

(

−

)

∑

≠

∣

(

)

∣

SMV(X) = frac{1}{N(N-1)}sum_{i neq j}left | D(X_{i,:}, X_{j,:}) right |

$SM V (X) = \frac{1}{N ( N - 1 )} i \neq = j \sum ∣ D (X_{i, :}, X_{j, :}) ∣$
其中

(

⋅

)

D(cdot, cdot)

$D (\cdot, \cdot)$ 表示两个向量之间的归一化欧几里得距离：

(

)

∥

−

∥

D(x, y) = frac{1}{2}left | frac{x}{left | x right |} - frac{y}{left | y right |} right |_{2}

$D (x, y) = \frac{1}{2} ∥$

∥∥x∥x−∥y∥y∥

∥2

SMV

$SM V$ 越小，节点表示越平滑。

基于上述度量，本文研究了三个代表性GNN模型中的过相关和过平滑问题，即GCN、GAT和ChebyNet。具体地，将三个模型的深度从2改变到50，并计算节点最终表示的相关度

(

)

(Corr)

$(C orr)$ 和平滑度

(

)

(SMV)

$(SM V)$ 的值：

可以看出：

当层数增加时，维度之间的相关性显著增加。例如，对于50层GCN和GAT，两个数据集上的
对于前几层（即层数小于10），
通常，随着层数的增加，学习的表示变得更加相关和平滑。然而，二者显示出非常不同的模式。这一观察表明，过相关和过平滑虽然有关联，但却有所不同。因此，解决这些问题可以从不同的角度帮助构造更深层次的GNN，并且二者可以是互补的。我们在第5.2节和第5.3节中的实验结果中验证了这一点。

从这项研究中可以明显看出：(1)深层GNN存在过相关问题，即随着层数的增加，学习到的特征的维度变得越来越相关；(2)随着层数的增加，过相关和过平滑呈现不同的模式。

3.2 过相关分析

如第2.1节所述，传播和变换是图神经网络中的两个主要组成部分。在本小节中，首先证明了传播和变换可以增加特征相关性，然后讨论了过相关特征引起的潜在问题。

3.2.1 传播导致更高的相关性

一些文章表明，应用无限传播可以使连通图中的节点表示彼此成比例，这在本文中被称之为极端过光滑特征。接下来，文章证明了极端过平滑特征的维度是相关的。

给定一个极端过平滑矩阵

$X$ ，

$X$ 中每行彼此成比例，于是有

(

)

Corr(X)=1

$C orr (X) = 1$ 。

证明如下：由于每行彼此成比例，所以每列也将彼此成比例。我们取

$X$ 的两个任意维度（列），并将它们表示为

[

]

[x, wx]

$[x, w x]$ 。皮尔逊系数

(

)

∣

⋅

(

−

)

(

−

)

∥

−

∥

−

∥

rho(x, wx) = frac{w}{|w|} cdot frac{(x-bar{x})^{T} (x-bar{x})}{left | x-bar{x} right | left |x-bar{x}right |}

$ρ (x, w x) = \frac{w}{∣ w ∣} \cdot \frac{( x - x ˉ ) ^{T} ( x - x ˉ )}{∥ x - x ˉ ∥ ∥ x - x ˉ ∥}$ 为

$1$ 或

−

-1

$- 1$ 。由于任意两个维度之间的相关性为

$1$ 或

−

-1

$- 1$ ，因此

(

)

Corr(x)=1

$C orr (x) = 1$ 。

上述命题表明，多重传播可以导致更高的特征维度相关性。尽管该分析仅针对连通图，但如果训练节点位于同一部分中，它们的表示仍然会过度相关，并损害下游任务的性能。

本文通过实验证明了传播可以增加连通图和不连通图中的特征相关性。具体地说，文章使用Cora数据集的完整图(FULL)和最大连通分量(LCC)（最初由78个连通分量组成）来计算传播矩阵

−

hat{A}=tilde{D}^{-frac{1}{2}}tilde{A}tilde{D}^{-frac{1}{2}}

$A^= D ~^{- \frac{1}{2}} A ~ D ~^{- \frac{1}{2}}$ 。然后，将多重传播作用于相关性非常接近于0的维度为100的随机生成的节点特征。通过改变传播次数(

$K$ )，并在图2a中展示了100次运行结果的

(

)

Corr(hat{A}^{K}X)

$C orr (A^^{K} X)$ 的平均值：

从图中我们可以看到，无论图是否连通，执行多次传播都会导致不相关的特征最终过相关。

尽管在极端情况下，过平滑时也会过相关，但本文证明了反之不成立。具体而言，有以下命题：给定极端过相关的节点表示

$X$ ，

$X$ 的行不一定彼此成比例。

证明如下：我们取

$X$ 的两个任意维度，因为它们彼此线性相关，所以将它们表示为

[

]

[x, wx+b]

$[x, w x + b]$ 。然后，我们从两个维度取两行，将其表示为

[

]

[

]

[[x_{1}, wx_{1}+b], [x_{2}, wx_{2}+b]]

$[[x_{1}, w x_{1} + b], [x_{2}, w x_{2} + b]]$ 。如果两行彼此成比例，它们需要满

(

)

(

)

x_{1}(wx_{2}+b)=x_{2}(wx_{1}+b)

$x_{1} (w x_{2} + b) = x_{2} (w x_{1} + b)$ ，即

bx_{1}=bx_{2}

$b x_{1} = b x_{2}$ 。当

bx_{1}=bx_{2}

$b x_{1} = b x_{2}$ 不成立时，

$X$ 将不是极端过平滑矩阵。

3.2.2 变换导致更高的相关性

通过实证研究，文章还发现，除了传播外，变换同样可以使特征更加相关。直观地说，过度叠加变换会导致过度参数化，这会让神经网络提取到冗余特征。一些文章表明，更深的网络具有更高的提取冗余特征的倾向，即特征维度之间的相关性更高。

本文通过实验验证了这一说法。具体而言，随机生成维度为100的不相关的节点特征，并将特征经过隐藏单元数为16的

$K$ 层多层感知器(MLP)。通过改变

$K$ 的值，文章在图2b中绘制最终表示的

Corr

$C orr$ 值随

$K$ 的变化情况。需要注意的是，在这个过程中不训练MLP，而只是关注神经网络的前向传递，MLP的权重是随机初始化的。从图中我们可以看到，重复应用（线性或非线性）变换将增加特征维度的相关性。直观地说，这是因为变换过程线性地组合了特征维度并增加了特征维度之间的交互。因此，重复变换可能会使最终表征的每个维度都包含来自前几层的类似信息量，并变得过度相关。另一方面，由于目标下游任务将指导参数的训练过程，反向传播可以在一定程度上缓解过相关问题。然而，训练非常深度的神经网络可能会面临其他挑战，如梯度消失/爆炸和过拟合，因此其无法有效地降低表示相关性（如图1所示），这也可能是经过训练的深层GNN仍然表现出过相关问题的原因。

3.3 深入讨论

在本小节中，文章进一步讨论了过相关和过平滑之间的区别和关系，并重新审视现有的处理过平滑的方法。

3.3.1 过相关与过平滑

先前的研究表明，过相关和过平滑既不相同也不独立。特征维度相关不表示节点特征过平滑。如图6所示，当Pubmed和CoauthorCS上的

Corr

$C orr$ 值增加时，

SMV

$SM V$ 却变化不大。因此我们可以推测，导致这两个数据集性能下降的不是过平滑，而是过相关。另一方面，两个概念也高度相关：(1)过相关和过平滑都会使学习到的表示编码更少的信息，并损害下游任务性能；(2)两者都可能由多重传播引起，因为极端过平滑的情况下也会出现过相关。

3.3.2 以往解决过平滑问题的方法

前面介绍了过相关问题，接下来我们回顾了以前处理过平滑的方法，这些方法可能有助于缓解过相关问题：

DropEdge。DropEdge通过随机删除图中的边来解决过平滑问题，这可能有利于减少相关性：(1)它可以削弱传播过程，从而缓解过相关性；(2)如图2a所示，删除一些边会使图变得更加不连续，并进一步降低特征相关性。
基于残差的方法。ResGCN为GCN加入了残差连接，GCNII加入了初始残差和恒等映射。这种残差连接可以从先前的层引入额外的信息，这可以帮助最终表示编码更有用的信息，从而缓解过相关问题。
归一化和其他方法。这些方法旨在推动GNN学习不同的表示，它们可以隐式地减少特征相关性。

4 本文模型

在本节中，将介绍本文所提出的用以解决过相关问题的框架DeCorr。具体而言，该框架由两个部分组成：(1)显式特征去相关，它用于直接降低特征维度之间的相关性；(2)互信息最大化，其最大化输入特征和表示之间的互信息以丰富信息，从而隐式地使特征更独立。

4.1 显式特征维度去相关

为了对学习的到的表示的维度去相关，一个最直观的建议就是最小化表示的维度之间的相关性。为了简单起见，本文使用协方差作为皮尔逊相关系数的替代，以最小化节点表示维度之间的相关性。具体来说，给定一组维度特征

{

…

}

{ x_{1}, x_{2},…,x_{d} }

${x_{1}, x_{2}, \dots, x_{d}}$ ，其中

∈

x_{i} in R^{N times 1}

$x_{i} \in R^{N \times 1}$ ，目标是最小化以下损失函数：

−

(

∑

≠

(

−

)

(

−

)

∑

(

−

)

(

−

)

−

)

frac{1}{N-1}( sum_{i, j, i neq j}( (x_{i}-bar{x_{i}})^{T}(x_{j}-bar{x_{j}}) )^{2} + sum_{i}( (x_{i}-bar{x_{i}})^{T} (x_{i}-bar{x_{i}}) - 1 )^{2} )

$\frac{1}{N - 1} (i, j, i \neq = j \sum ((x_{i} - x_{i} ˉ)^{T} (x_{j} - x_{j} ˉ))^{2} + i \sum ((x_{i} - x_{i} ˉ)^{T} (x_{i} - x_{i} ˉ) - 1)^{2})$
其中

bar{x_{i}}

$x_{i} ˉ$ 是一个向量，向量中每个元素都为

x_{i}

$x_{i}$ 的平均值。在上式中，通过最小化第一项以减少不同特征维度之间的协方差，并且当第一项为零时，特征维度间将变得不相关。通过最小化第二项，我们让每个维度的范数（减去平均值后）趋向于1。上式的矩阵形式为：

−

∥

(

−

)

(

−

)

−

∥

frac{1}{N-1}left | (X-bar{X})^{T}(X-bar{X}) - I_{d} right |_{F}^{2}

$\frac{1}{N - 1} ∥$

∥(X−Xˉ)T(X−Xˉ)−Id∥

∥F2
其中

[

]

∈

bar{X}=left [bar{x}_{1}, bar{x}_{2}, ..., bar{x}_{d} right ] in R^{N times d}

$X ˉ = [x ˉ_{1}, x ˉ_{2}, ..., x ˉ_{d}] \in R^{N \times d}$ ，

∥

⋅

∥

left | cdot right |_{F}

$∥ \cdot ∥_{F}$ 表示Frobenius范数。值得注意的是，

∥

−

∥

left | X^{T}X - I right |_{F}^{2}

$∥$

∥XTX−I∥

∥F2的梯度为

(

−

)

4X(X^{T}X-I)

$4 X (X^{T} X - I)$ 。因此，梯度计算的复杂度为

(

)

O(N^{2}d^{2})

$O (N^{2} d^{2})$ ，当图非常大（例如数百万节点）时，该方法是不可扩展的。为了解决这个问题，文章建议不使用所有节点来计算协方差，而是应用蒙特卡罗采样以等概率对

N

sqrt{N}

$N$

个节点进行采样，然后用以估计的协方差，此时计算梯度的复杂度将降低到

(

)

O(Nd^{2})

$O (N d^{2})$ ，随着图的大小线性增加。此外，采样策略在模型训练过程中注入了随机性，从而有助于实现更好的泛化。

最小化上式类似于最小化以下去相关损失

ℓ

ell_{D}

$ℓ_{D}$ ，通过将上式中的项除以它们的Frobenius范数使其归一化，进而使得

≤

ℓ

≤

0 leq ell_{D} leq 2

$0 \leq ℓ_{D} \leq 2$ ：

ℓ

(

)

∥

(

−

)

(

−

)

∥

(

−

)

(

−

)

∥

−

∥

ell_{D}(X)=left | frac{(X-bar{X})^{T}(X-bar{X})}{left | (X-bar{X})^{T}(X-bar{X}) right |_{F}} - frac{I_{d}}{sqrt{d}} right |_{F}

$ℓ_{D} (X) = ∥$

∥∥

∥(X−Xˉ)T(X−Xˉ)∥

∥F(X−Xˉ)T(X−Xˉ)−d

Id∥

∥F
其中

$X$ 可以是当前GNN层的输出表示矩阵。由于我们希望每个层之后的表示可以较少相关，因此最终去相关损失公式为：

∑

−

ℓ

(

)

mathcal{L}_{D} = sum_{i=1}^{K-1}ell_{D}(H^{(i)})

$L_{D} = i = 1 \sum K - 1 ℓ_{D} (H^{(i)})$
其中

(

)

H^{(i)}

$H^{(i)}$ 表示第

$i$ 层输出的隐藏表示，

$K$ 表示总层数。通过最小化

mathcal{L}_{D}

$L_{D}$ ，保证了每个层之后的隐藏表示不太相关，从而减轻了过相关问题。

4.2 互信息最大化

在第3.1节中，文章已经证明了深层GNN模型最终学习到的特征是高度冗余的，其编码的有用信息很少。为了解决这个问题，除了直接限制特征的相关性之外，还建议通过最大化输入特征和学习到的特征之间的互信息(MI)来进一步丰富编码信息。由于更深的GNN在表示中编码的信息更少，所以MI最大化过程可以确保学习的表示保留来自输入的一部分信息。具体而言，给定两个随机变量

$A$ 和

$B$ ，将MI最大化过程公式化如下：

(

)

(

)

−

(

∣

)

(

)

−

(

∣

)

{rm max} MI(A, B) = H(A) - H(A|B) = H(B) - H(B|A)

$max M I (A, B) = H (A) - H (A ∣ B) = H (B) - H (B ∣ A)$
其中

(

⋅

)

H(cdot)

$H (\cdot)$ 表示熵函数，

(

)

MI(A, B)

$M I (A, B)$ 用于度量A和B之间的依赖性。然而，当我们通过神经网络获得

$A$ 或

$B$ 时，直接最大化互信息通常很难，因此我们最大化

(

)

MI(A, B)

$M I (A, B)$ 的下限。具体而言，文章遵循MINE，通过训练分类器区分联合分布

(

)

P(A, B)

$P (A, B)$ 和

(

)

(

)

P(A)P(B)

$P (A) P (B)$ 的样本对，进而估计互信息的下限。形式上，互信息的这个下限可以描述如下：

(

)

≥

(

)

[

(

)

]

−

(

)

(

)

[

(

)

]

MI(A, B) geq mathbb{E}_{P(A, B)}[mathcal{D}(A, B)]-{rm log} mathbb{E}_{P(A)P(B)}[e^{mathcal{D}(A, B)}]

$M I (A, B) \geq E_{P (A, B)} [D (A, B)] - log E_{P (A) P (B)} [e^{D (A, B)}]$
其中

(

)

mathcal{D}(A, B)

$D (A, B)$ 是二元判别器。为了最大化第

$K$ 层隐藏表示

(

)

H^{(k)}

$H^{(k)}$ 和输入特征

$X$ 之间的互信息

(

)

MI(H^{(k)}, X)

$M I (H^{(k)}, X)$ ，我们最小化以下目标：

ℓ

(

)

−

(

)

[

(

)

]

(

)

(

)

[

(

)

]

ell_{M}(H^{(k)}, X) = -mathbb{E}_{P(h_{i}^{(k)}, x_{i})}[mathcal{D}(h_{i}^{(k)}, x_{i})] + {rm log} mathbb{E}_{P(h^{(k)})P(x)}[e^{mathcal{D}(h_{i}^{(k)}, x_{i})}]

$ℓ_{M} (H^{(k)}, X) = - E_{P (h_{i (k)}, x_{i})} [D (h_{i (k)}, x_{i})] + log E_{P (h^{(k)}) P (x)} [e^{D (h_{i (k)}, x_{i})}]$
其中

(

)

h_{i}^{(k)}

$h_{i (k)}$ 和

x_{i}

$x_{i}$ 分别表示节点

v_{i}

$v_{i}$ 的隐藏层表示和输入。判别器

(

⋅

)

mathcal{D}(,cdot,)

$D (, \cdot,)$ 表示如下：

(

)

(

)

mathcal{D}(x_{i}, h_{i}^{(k)}) = sigma(x_{i}^{T}Wh_{i}^{(k)})

$D (x_{i}, h_{i (k)}) = σ (x_{i T} W h_{i (k)})$
实际上，在每个批次中，从联合分布

(

)

P(h_{i}^{(k)}, x_{i})

$P (h_{i (k)}, x_{i})$ 中采样一组

{

(

)

}

{ (h_{i}^{(k)}, x_{i}) }_{i=1}^{B}

${(h_{i (k)}, x_{i})}_{i = 1 B}$ ，以估计公式中的第一项，然后在批次中打乱

x_{i}

$x_{i}$ 以生成用于估计第二项的“负对”。

值得注意的是，本文并不是对GNN的每一层都运用了互信息最大化，而是每

$t$ 层执行一次，如下所示：

∑

∈

[

−

]

ℓ

(

)

mathcal{L}_{M} = sum_{i in [t,2t,3t,...,frac{K-1}{t}t]}ell_{M}(H^{(i)})

$L_{M} = i \in [t, 2 t, 3 t, ..., \frac{K - 1}{t} t] \sum ℓ_{M} (H^{(i)})$
根据经验，当

t=5

$t = 5$ 时足以实现令人满意的性能。

4.3 目标函数和复杂度分析

4.3.1 总体目标函数

总体目标函数可表述为：

∣

∑

∈

ℓ

(

)

∑

−

ℓ

(

)

∑

∈

[

−

]

ℓ

(

)

begin{aligned} mathcal{L} &= mathcal{L}_{class} + alpha mathcal{L}_{D} + beta mathcal{L}_{M}\ &= frac{1}{|mathcal{V}_{L}|}sum_{v_{i} in mathcal{V}_{L}} ell ({rm softmax}(H_{i,:}^{K}), y_{i}) \ &+ alpha sum_{i=1}^{K-1} ell_{D}(H^{(i)}) + beta sum_{i in [t,2t,3t,...,frac{K-1}{t}t]}ell_{M}(H^{(i)}) end{aligned}

$L = L_{c l a ss} + α L_{D} + β L_{M} = \frac{1}{∣ V _{L} ∣} v_{i} \in V_{L} \sum ℓ (softmax (H_{i, : K}), y_{i}) + α i = 1 \sum K - 1 ℓ_{D} (H^{(i)}) + β i \in [t, 2 t, 3 t, ..., \frac{K - 1}{t} t] \sum ℓ_{M} (H^{(i)})$
其中

mathcal{V}_{L}

$V_{L}$ 是带标签的节点，

y_{i}

$y_{i}$ 是节点

v_{i}

$v_{i}$ 的标签；

alpha

$α$ 和

beta

$β$ 分别是控制

mathcal{L}_{D}

$L_{D}$ 和

mathcal{L}_{M}

$L_{M}$ 对总体损失贡献的超参数。

4.3.2 复杂度分析

通过分析模型参数和时间方面的额外复杂性，本文将所提出的方法与普通GNN进行了比较。为了简单起见，文章假设所有隐藏维度为

$d$ ，输入维度为

d_{0}

$d_{0}$ 。

模型复杂度 与普通GNN相比，当对正/负样本的一致性进行评分时，本文模型引入的唯一附加参数是权重矩阵

$W$ ，其复杂度为

(

)

O(d_{0}d)

$O (d_{0} d)$ ，其不依赖于图的大小。由于隐藏维度通常比图中的节点数小得多，因此额外的模型复杂度可以忽略不计。

时间复杂度 如第4.1和4.2节所示，额外的计算成本来自对

mathcal{L}_{D}

$L_{D}$ 和

mathcal{L}_{M}

$L_{M}$ 的计算和反向传播。由于我们对

sqrt{N}

$N$

个节点进行了蒙特卡罗采样，因此计算

mathcal{L}_{D}

$L_{D}$ 的复杂度变为

(

)

O(Ksqrt{N}d^{2})

$O (K N$

d2)，反向传播的复杂度为

(

)

O(KNd^{2})

$O (K N d^{2})$ ；计算

mathcal{L}_{M}

$L_{M}$ 及其梯度的复杂度为

(

)

O(KNd_{0}d)

$O (K N d_{0} d)$ 。考虑到

$d$ 和

$K$ 通常比节点数

$N$ 小得多，因此总附加时间复杂度变为

(

)

O(KNd^{2} + KNd_{0}d)

$O (K N d^{2} + K N d_{0} d)$ ，随节点数线性增加。

5 实验

实验旨在回答以下问题：RQ1: DeCorr能否帮助训练更深层次的GNN？RQ2: 通过实现更深层次的GNN，DeCorr是否能够帮助GNN实现更好的性能？RQ3: DeCorr能否配备解决过平滑问题的方法，并作为一种补充技术？RQ4: 两个不同的模块如何影响DeCorr的性能？

5.1 实验设置

为了验证所提出的框架，文章在9个基准数据集上进行了实验，包括Cora、Citeser、Pubmed、CoauthorCS、Chameleon、Texas、Cornell、Wisconsin和Actor。文章考虑了三种基本GNN模型，GCN、GAT和ChebyNet，并为它们配备了以下方法来解决过度平滑问题：PairNorm、BatchNorm、DGN和DropEdge。

5.2 深层GNN的性能

在本小节中，文章将GCN、GAT和ChebyNet集成到我们提出的框架中，并将其性能与以前在正常图和缺少特征的图的设置下处理过平滑的方法进行比较。

5.2.1 缓解更深层次GNN的性能下降

实验结果中，"None"表示未使用任何方法的普通GNN。表1中报告了具有2/15/30层的GNN的性能：
从表中可以看出，DeCorr可以极大地改善深层GNN的性能。此外，在层数相同时，DeCorr在大多数情况下始终实现最佳性能，并显著减缓性能下降。例如，在Cora数据集上，DeCorr将15层GCN和30层GCN分别提高了58.9%和60.3%。上述结果表明，处理特征过相关问题可以允许使用深层GNN，其甚至比仅关注于处理过平滑的GNN实现更好的性能。

值得注意的是，在大多数情况下，建议的框架还可以提高2层GNN的性能，例如，在Citeser数据集上，DeCorr将GCN、GAT和ChebyNet分别提高了1.5%、0.4%和5.3%，而最强的基线DGN无法实现这一点，甚至有时会降低性能。这表明，去相关后学习到的特征通常有助于改进各种模型的泛化，而不仅仅是更深层次的模型。

5.2.2 在缺失的功能设置下实现更深更好的GNN

在第5.2.1节中，已经证明了减少特征过相关在帮助训练更深的GNN方面的优势。然而，如表1所示，较深的GNN实现的性能不如较浅的GNN（2层GNN）。那么一个自然的问题是：较深层次的GNN在何时是有用的？ 为了回答这个问题，文章删除了验证和测试集中的节点特征，这种情况经常发生在现实世界中。例如，社交网络中的新用户在与少数其他用户连接时往往缺乏个人资料信息。为了学习这些新用户的有效表示，我们需要更多的传播步骤来传播现有用户的属性信息。因此，在这种情况下，较深的GNN可以比较浅的GNN表现得更好。我们让层数

$K$ 取

{

…

}

left { 1,2,…,10,15,…,30 right }

${1, 2, \dots, 10, 15, \dots, 30}$ 中的值，并在表2中报告了性能：

"None"表示普通GNN，

# K

$# K$ 表示模型达到最佳性能时的层数。从表中，我们得出以下两个结论：

在缺失特征设置下，最好的性能总是由更深的模型实现，即达到最佳性能时
DeCorr在12种情况中的8种情况下实现了最佳性能，并显著优于浅层GNN。例如，在Pubmed数据集上，DeCorr在GCN、GAT和ChebyNet上分别实现了36.9%、33.9%和19.5%的改进。它进一步证明了在实现更深层的GNN中缓解过相关性的重要性。

5.2.3 训练时的相关性和平滑度

如表1所示，DeCorr在Citeseer数据集的GAT中取得了比其他基线明显的改进。因此，文章进一步探索其背后的原因。具体而言，本文绘制了DGN和DeCorr在配备15层GAT时的

Corr

$C orr$ 、

SMV

$SM V$ 、训练/验证/测试精度。结果如图3所示：

从图中可以看出，尽管DGN可以保持较高的

SMV

$SM V$ 值（约0.6），但它们的性能仍然不太令人满意。此外，它们的

Corr

$C orr$ 值远高于DeCorr：DGN约为0.6，DeCorr约为0.35。

5.3 与其他深度GNN方法结合

在本小节中，文章回答了第三个问题，并将DeCorr集成到其他深度GNN方法中。

5.3.1与DGN结合

为了验证DeCorr是否可以作为解决过平滑问题的方法的补充技术，文章选择最强的基线DGN与DeCorr相结合。具体而言，让

$K$ 取

{

…

}

left { 2, 4, …, 20, 25, …, 40 right }

${2, 4, \dots, 20, 25, \dots, 40}$ 中的值，并在图4中报告了Cora数据集上DGN+DeCorr、DGN和DeCorr的测试精度和Corr值：

从图中，我们得出以下观察结果：

当将DGN与DeCorr相结合时，我们可以获得比每个单独方法更好的性能，这表明过相关和过平滑并不相同，它为开发更深层次的GNN提供了新的见解，因为我们可以将解决过相关的策略与解决过平滑的策略相结合，以实现更强的更深层次模型。
在图4b中，我们可以观察到DGN在降低特征相关性

5.3.2 与DeepGCN结合

文章还在DeepGCN的层上进行了实验。由于DeepGCN层由残差连接（具有层范数）和膨胀卷积组成，我们在下表中分别报告了它们的性能。具体而言，我们通过堆叠15/30层报告了DeepGCN、无膨胀卷积的DeepGCN（表示为Res）、无残差连接的DeepGCN（表示为DConv）的结果。我们还报告了为这些模型使用DeCorr的结果，所有结果总结在表4中：

从表中，我们得出了三个结论：(1)残差连接可以有效地提高性能，并有助于缓解过相关问题，这与我们在第3.3节中的讨论一致。(2)膨胀卷积无助于缓解问题，因此残差连接应该是DeepGCN能够堆叠多层的主要原因。(3)残差连接和DeCorr结合可以实现更高的性能，例如，15/30层的增益为2.6%/1.7%。

5.3.3 与其他深度模型结合

除了那些缓解过平滑问题的通用框架之外，本文还将深度模型GCNII和GCNII*(深度为

{

}

left{ 16, 32, 64 right}

${16, 32, 64}$ )与DeCorr相结合。我们对8个基准数据集进行了实验，并在表3中报告了10个随机种子实验下的平均精度：

如表3所示，我们发现DeCorr可以进一步改善GCNII和GCNII在大多数数据集中的表现。例如，Decorr将GCNII在Citeser、Pubmed、Cornell、Texas、Wisconsin和Chameleon上的表现分别提高了0.6%、0.4%、5.4%、1.9%、3.3%和4.7%。这些结果进一步说明了特征维度去相关可以帮助提高模型性能。

5.4 消融实验

本文选择了GCN进行消融实验，具体而言，我们构建了以下消融模型：

None:普通GCN，不含任何其他成分。
Decorr- $mathcal{L}_{M} LM，保留 L D mathcal{L}_{D} LD。$
Decorr- $mathcal{L}_{D} LD，保留 L M mathcal{L}_{M} LM。$

结果如图5所示：

如图所示，Decorr-

alpha

$α$ 和Decorr-

beta

$β$ 都可以大大提高15层GCN的性能，这表明优化

mathcal{L}_{D}

$L_{D}$ 和

mathcal{L}_{M}

$L_{M}$ 都可以帮助降低特征相关性并提高性能。请注意，Decorr-

alpha

$α$ 和Decorr-

beta

$β$ 可以在15层GCN上实现相当的性能。然而，在30层GCN上，Decorr-

beta

$β$ 在四个数据集上的改进不如Decorr-

alpha

$α$ 。这一观察表明，当GNN非常深时，显式特征去相关（

mathcal{L}_{D}

$L_{D}$ ）比隐式方法（

mathcal{L}_{M}

$L_{M}$ ）更重要。

6 总结

当深度堆叠层时，图神经网络的性能会严重降低。最近的研究表明，过平滑问题是造成这种现象的主要原因。在本文中引入了深层GNN的新视角，即特征过相关，并进行了理论和实验研究。文章发现，过相关和过平滑呈现不同的模式，但它们也相互关联。为了解决过相关问题，本文提出了一个通用框架DeCorr，其目的是直接减少特征维度之间的相关性，同时最大化输入和学习到的表示之间的互信息。大量实验表明，所提出的DeCorr可以帮助更深层次的GNN编码更多有用的信息，并在正常图和缺少特征的图的设置下都实现了更好的性能。未来，计划研究将DeCorr应用于各种现实应用程序（如推荐系统）的潜力。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

二维码

初入Kaggle之数据集的使用及预测结果生成

< <上一篇

传统图像处理（一）

下一篇>>

搜索内容

KDD 2022 | 深度图神经网络中的特征过相关：一个新的视角

目录

前言

1 引言

2 背景和相关工作

2.1 GNN

2.2 相关工作

3 Preliminary Study

3.1 过相关和过平滑

3.2 过相关分析

3.2.1 传播导致更高的相关性

3.2.2 变换导致更高的相关性

3.3 深入讨论

3.3.1 过相关与过平滑

3.3.2 以往解决过平滑问题的方法

4 本文模型

4.1 显式特征维度去相关

4.2 互信息最大化

4.3 目标函数和复杂度分析

4.3.1 总体目标函数

4.3.2 复杂度分析

5 实验

5.1 实验设置

5.2 深层GNN的性能

5.2.1 缓解更深层次GNN的性能下降

5.2.2 在缺失的功能设置下实现更深更好的GNN

5.2.3 训练时的相关性和平滑度

5.3 与其他深度GNN方法结合

5.3.1与DGN结合

5.3.2 与DeepGCN结合

5.3.3 与其他深度模型结合

5.4 消融实验

6 总结

最新文章

分类

标签云