论文标题：Towards Deeper Graph Neural Networks
论文作者：Meng Liu, Hongyang Gao, Shuiwang Ji
论文来源：2020, KDD
论文地址：download
论文代码：download
问题引入：
图卷积是领域聚合的代表，这些邻域聚合方法中的一层只考虑近邻，当进一步深入以实现更大的接受域时，性能会下降，这种性能恶化归因于过平滑问题（ over-smoothing），即当感受域增大时，在传播和更新过程中将不同标签的节点的嵌入变得一样。
问题解决：
提出 Deep Adaptive Graph Neural Network (DAGNN) 当感受域增大时，来自适应的接收领域信息。
大多数流行的图卷积操作遵循邻域聚合（或消息传递）的方式，通过传播（propagating）相邻节点的表示并随后应用转换来（transformation）学习节点表示。一般图卷积的第 $l$ 层可以描述为：
$begin{aligned}a_{i}^{(ell)} &=operatorname{PROPAGATION}^{(ell)}left(left{x_{i}^{(ell-1)},left{x_{j}^{(ell-1)}leftlfloor j in mathcal{N}_{i}right}right}right)right.\boldsymbol{x}_{i}^{(ell)} &=operatorname{TRANSFORMATION~}^{(ell)}left(a_{i}^{(ell)}right) .end{aligned}quadquadquad(1)$
典型代表 GCN 的前向传播过程可以表达为 ：
$boldsymbol{X}^{(ell)}=sigmaleft(widehat{boldsymbol{A}} boldsymbol{X}^{(ell-1)} W^{(ell)}right) quadquadquad(2)$
在这里，首先定义节点 $i$ 和节点 $j$ 的表示之间的欧氏距离的相似性度量：
$Dleft(boldsymbol{x}_{i}, boldsymbol{x}_{j}right)=frac{1}{2}left|frac{boldsymbol{x}_{i}}{left|boldsymbol{x}_{i}right|}-frac{boldsymbol{x}_{j}}{left|boldsymbol{x}_{j}right|}right| quadquadquad(3)$
注意：$Dleft(boldsymbol{x}_{i}, boldsymbol{x}_{j}right) in [0,1]$ 。
基于 $text{Eq.3}$ 提出的节点 $i$ 平滑度度量 $S M V_{i}$ ：
$S M V_{i}=frac{1}{n-1} sumlimits _{j in V, j neq i} Dleft(x_{i}, x_{j}right) quadquadquad(4)$
故图 $G$ 的平滑性度量如下：
$S M V_{G}=frac{1}{n} sumlimits _{i in V} S M V_{i} quadquadquad(4)$
显然，$S M V_{G}$ 和图平滑性呈负相关。
对比试验：
对于深度为 $0$ 的 GNN ，可认为是只考虑了语义信息，没有考虑结构信息的 MLP。从上图观察到测试精度随着层数先增加后下降。
t-SNE 可视化的结果：
节点表示随着层数的增加不断趋于相似，当层数达到 $6$ 层时，节点表示已经很难分离。
上述问题产生的原因：节点表示在大量的迭代中重复传播，特别是对于具有稀疏连接边的图，因此，从理论上讲，多次传播迭代并不足以产生过度平滑。
本文认为由于转换和传播的纠缠，损害了 GNNs 的性能。论点来源于：首先，他们之间的参数交织在一起，当感受域增大时，需要更多的参数。因此，训练具有大量参数的深度GNN。这可能可以解释为什么 Figure 2 中多个GCN层的性能波动很大。其次，表示的转换和传播应该被视为两个独立的操作。
从 Figure 2 和 Figure 1 所示 发现节点的类可以通过其初始特性完全预测，不使用任何图形结构信息，结果反而好。
基于图结构的传播，在连接节点通常属于同一类的情况下，使同一类中的节点表示相似，从而简化分类任务。因此，表示转换和传播分别从特征和结构两个方面发挥着不同的作用。
为了验证上述论点，解耦了 $text{Eq.2}$ 中的传播和转换 ：
$begin{aligned}Z &=operatorname{MLP}(X) \X_{o u t} &=operatorname{softmax}left(widehat{A}^{k} Zright)end{aligned} quadquadquad (6)$
其中
变换后，应用 $k$ 步传播推导出输出特征矩阵 $X_{text {out }} in mathbb{R}^{n times c}$，采用 $softmax$ 计算分类概率。在这项工作中，我们系统地分析了这个方案，并揭示了它可以帮助构建更深层次的模型，而不遭受性能下降。
在 $text{Eq.6}$ 中采用的不同层数表示的测试精度和平滑度度量值 Cora 上的结果如 Figure 4 所示
在解决了特征转换和传播的纠缠之后，更深层次的模型能够利用更大的接受域而不影响性能退化。可以观察到，过度平滑的问题在一个大的接受域开始受影响，如在Cora 数据集上 75 hop 时，才出现平滑度度量值大大下降，度量值接近 $0$。
在实践中，通常不需要一个非常大的接受域，因为在一个被连接的组件中，最大的最短路径距离通常是一个可接受的小数字。因此，训练信号可以用少量的层传播到整个图中。具有 $2$ 个或 $3$ 个GCN层的图神经网络通常具有竞争能力，这就证明了这一点。
在本节对过平滑问题做一个严格推导。
$widehat{A}_{oplus}=widetilde{D}^{-1} widetilde{A}$ 和 $widehat{A}_{odot}=widetilde{D}^{-frac{1}{2}} widetilde{A} widetilde{D}^{-frac{1}{2}} $，是两种常用的传播机制。行平均归一化 $widehat{A}_{oplus}$ 用于 GraphSAGE [9] 和 DGCNN [38]，对称的标准化 $widehat{A}_{odot}$ 用于 GCN 。下面，我们通过证明 $ widehat{A}_{oplus}^{k} $ 和 $widehat{A}_{odot}^{k}$ 在 $k$ 趋于无穷时的收敛性来描述过平滑问题。
假设 $boldsymbol{e}=[1,1, cdots, 1] in mathbb{R}^{1 times n}$ 是一个值全为 $1$ 的行向量，函数 $Psi(boldsymbol{x})=frac{boldsymbol{x}}{operatorname{sum}(boldsymbol{x})} $ 将向量规范化为和为 $1$，函数 $Phi(boldsymbol{x})=frac{boldsymbol{x}}{|boldsymbol{x}|}$ 使一个向量标准化，使其大小为 $1$。
THEOREM 3.1. Given a connected graph $G$, $lim _{k rightarrow infty} widehat{A}_{oplus}^{k}=Pi_{oplus}$ , where $Pi_{oplus}$ is the matrix with all rows are $pi_{oplus}$ and $pi_{oplus}=Psi(e widetilde{D})$ .
THEOREM 3.2. Given a connected graph $G$, $lim _{k rightarrow infty} widehat{A}_{odot}^{k}=Pi_{odot}$ , where $Pi_{odot}=Phileft(widetilde{D}^{frac{1}{2}} boldsymbol{e}^{T}right)left(Phileft(widetilde{D}^{frac{1}{2}} boldsymbol{e}^{T}right)right)^{T} $.
从上述两个定理中，我们可以分别推导出在无限深度模型中 $k$ 趋于无穷时 $widehat{A}_{oplus}^{k} $ 和 $widehat{A}_{odot}^{k} $ 的精确收敛值。因此，应用无限层迭代传播信息相当于利用一步 $Pi_{oplus}$ 或 $Pi_{odot}$ 传播特征。$Pi_{oplus}$ 的行是相同的，$Pi_{odot}$ 的行与相应节点的度的平方根值成正比。因此，$Pi_{oplus}$ 或 $Pi_{odot}$ 的行是线性不可分割的，利用它们作为传播机制会产生难以区分的表示，从而导致过平滑问题。
为了证明这两个定理，我们首先引入以下两个引理。这两个引理的证明可以在附录中找到A.5和A.6.
Lemma 3.3. Given a graph $G$, $lambda$ is an eigenvalue of $widehat{boldsymbol{A}}_{oplus}$ with left eigenvector $boldsymbol{v}_{l} in mathbb{R}^{1 times n}$ and right eigenvector $boldsymbol{v}_{r} in mathbb{R}^{n times 1}$ if and only if $lambda$ is an eigenvalue of $widehat{boldsymbol{A}}_{odot}$ with left eigenvector $boldsymbol{v}_{l} widetilde{mathbf{D}}^{-frac{1}{2}} in mathbb{R}^{1 times n}$ and right eigenvector $widetilde{boldsymbol{D}}^{frac{1}{2}} boldsymbol{v}_{r} in mathbb{R}^{n times 1}$ .
Lemma 3.4. Given a connected graph $G$, $widehat{A}_{oplus}$ and $widehat{A}_{odot}$ always have an eigenvalue $1$ with unique associated eigenvectors and all other eigenvalues $lambda$ satisfy $|lambda|<1$ . The left and right eigenvectors of $widehat{boldsymbol{A}}_{oplus}$ associated with eigenvalue $1$ are $boldsymbol{e} widetilde{D} in mathbb{R}^{1 times n}$ and $boldsymbol{e}^{T} in mathbb{R}^{n times 1} $, respectively. For $widehat{boldsymbol{A}}_{odot}$ , they are $boldsymbol{e} widetilde{D}^{frac{1}{2}} in mathbb{R}^{1 times n}$ and $widetilde{boldsymbol{D}}^{frac{1}{2}} boldsymbol{e}^{T} in mathbb{R}^{n times 1}$ .
这两个定理适用于图神经网络中经常研究的连通图。对于一个不连通的图，这些定理也可以应用于它的每个连通组件，这意味着无限次应用这些传播机制将在每个连通组件中产生难以区分的节点表示。
上述定理表明，过平滑将使节点表示不可分割，并提供了常用传播机制的精确收敛值。理论上，我们已经证明了在超平滑模型中是不可避免的。此外，收敛速度是我们在实践中应该考虑的一个更重要的因素。在数学上，根据 $Eq.7$ 的说法，收敛速度依赖于除传播矩阵的 $1$ 以外的其他特征值，特别是第二大特征值。直观地说，传播矩阵由相应图的拓扑信息决定的。这可能是我们在第2.2节中观察到的稀疏连通图只有在应用极深模型时，稀疏连接图才会出现过度平滑的原因。
整体框架如下：
该框架分解为：转换（transformation）、 传播（propagation）、自适应调整（adaptive adjustment）
公式化：
$begin{array}{ll}Z=operatorname{MLP}(boldsymbol{X}) & in mathbb{R}^{n times c} \H_{ell}=widehat{A}^{ell} Z, ell=1,2, cdots, k & in mathbb{R}^{n times c} \H=operatorname{stack}left(Z, H_{1}, cdots, H_{k}right) & in mathbb{R}^{n times(k+1) times c} \S=sigma(H s) & in mathbb{R}^{n times(k+1) times 1} \widetilde{S}=operatorname{reshape}(S) & in mathbb{R}^{n times 1 times(k+1)} \X_{text {out }}=operatorname{softmax}(text { squeeze }(widetilde{S} H)) & in mathbb{R}^{n times c}end{array}quadquadquad(8)$
其中
$S=sigma(H s)$ 利用这种自适应调整机制，DAGNN可以自适应地平衡来自每个节点的本地和全局邻域的信息。显然，转换过程 $Z=operatorname{MLP}(X)$ 和自适应调整过程 $S=sigma(H s)$ 具有可训练的参数，而在传播过程 $H_{ell}=widehat{A}^{ell} Z, ell=1,2, cdots, k$ 中没有可训练的参数，从而形成了一个参数高效的模型。
在 DAGNN 中，最终的表示形式 $X_{text {out }}$ 被用作最终的预测。因此，所有带标签的样本的交叉熵损失都可以计算为
$mathcal{L}=-sumlimits_{i in V_{L}} sumlimits_{p=1}^{c} Y_{[i, p]} ln X_{o u t}[i, p]quadquadquad(9)$
其中：
节点分类：
在本文中，我们考虑了当前深度图神经网络中存在的性能退化问题，并对深层图神经网络提出了新的见解。我们首先对这个问题进行了系统的分析，并认为影响网络性能的关键因素是表示转换和传播的纠缠。我们建议将这两个操作解耦，并证明了没有这种纠缠的深度图神经网络可以利用大的接受域，而不会受到性能下降的影响。此外，在建立非常深的模型时，我们对上述策略进行了理论分析，这可以作为对过度平滑问题的严格和温和的描述。利用我们的见解，DAGNN被提出进行节点表示学习，并能够从大的和自适应的接受域捕获信息。根据我们的综合实验，我们的DAGNN比目前最先进的模型取得了更好的性能，特别是在训练样本有限的情况下，这证明了它的优越性。
Lemma 3.3 证明：
If $lambda$ is an eigenvalue of $widehat{A}_{oplus}$ with left eigenvector $v_{l}$ and right eigenvector $boldsymbol{v}_{r}$
thus ,we have $boldsymbol{v}_{l} widehat{A}_{oplus}=lambda boldsymbol{v}_{l} $ and $widehat{A}_{oplus} boldsymbol{v}_{r}= lambda boldsymbol{v}_{r}$
then, We right multiply the first eigenvalue equation with $widetilde{D}^{-frac{1}{2}}$ and left multiply the second eigenvalue equation with $widetilde{D}^{frac{1}{2}} $
so, $left(boldsymbol{v}_{l} widetilde{D}^{-frac{1}{2}}right) widetilde{D}^{-frac{1}{2}} widetilde{A} widetilde{D}^{-frac{1}{2}}=lambdaleft(boldsymbol{v}_{l} widetilde{D}^{-frac{1}{2}}right)$ 、$widetilde{D}^{-frac{1}{2}} widetilde{A}_{D}^{-frac{1}{2}}left(widetilde{D}^{frac{1}{2}} boldsymbol{v}_{r}right)= lambdaleft(widetilde{D}^{frac{1}{2}} boldsymbol{v}_{r}right)$
hence, $lambda$ is also an eigenvalue of $widehat{A}_{odot}$ with left eigenvector $boldsymbol{v}_{l} widetilde{D}^{-frac{1}{2}}$ and right eigenvector $widetilde{D}^{frac{1}{2}} boldsymbol{v}_{r} $.
Lemma 3.4 证明：
首先，证明：“ $widehat{A}_{oplus}$ and $widehat{A}_{odot}$ always have an eigenvalue $1$ with unique associated eigenvectors and all other eigenvalues $lambda$ satisfy $|lambda|<1$ . ”
We have $widehat{A}_{oplus} boldsymbol{e}^{T}=boldsymbol{e}^{T}$ because each row of $widehat{A}_{oplus}$ sums to $1$ .Therefore, 1 is an eigenvalue of $widehat{A}_{oplus}$ .
Suppose that there exists an eigenvalue $lambda$ that $|lambda|>1$ with eigenvector $boldsymbol{v}$ , then the length of the right side in $widehat{A}_{oplus}^{k} boldsymbol{v}=lambda^{k} boldsymbol{v}$ grows exponentially when $k$ goes to infinity. This indicates that some entries of $widehat{A}_{oplus}^{k}$ shoulde be larger than $1$ . Nevertheless, all entries of $widehat{A}_{oplus}^{k}$ are positive and each row of $widehat{A}_{oplus}^{k}$ always sums to $1$ , hence no entry of $widehat{A}_{oplus}^{k}$ can be larger than $1$, which leads to contradiction.
From Lemma 3.3, $widehat{A}_{oplus}$ and $widehat{A}_{odot}$ have the same eigenvalues. Therefore, $widehat{A}_{oplus}$ and $widehat{A}_{odot}$ always have an eigenvalue $1$ and all eigenvalues $lambda$ satisfy $|lambda| leq 1 $.
其次，证明 “The left and right eigenvectors of $widehat{boldsymbol{A}}_{oplus}$ associated with eigenvalue $1$ are $boldsymbol{e} widetilde{D} in mathbb{R}^{1 times n}$ and $boldsymbol{e}^{T} in mathbb{R}^{n times 1} $, respectively. For $widehat{boldsymbol{A}}_{odot}$ , they are $boldsymbol{e} widetilde{D}^{frac{1}{2}} in mathbb{R}^{1 times n}$ and $widetilde{boldsymbol{D}}^{frac{1}{2}} boldsymbol{e}^{T} in mathbb{R}^{n times 1}$ .”
We then compute the eigenvectors associated with eigenvalue $1$. Obviously, $boldsymbol{e}^{T}$ is the right eigenvector of $widehat{A}_{oplus} $ associated with eigenvalue $1$ .
Next, assume $boldsymbol{v}_{l}$ is the left eigenvector of $widehat{A}_{oplus}$ associated with eigenvalue $1$ and thus $ boldsymbol{v}_{l} widetilde{D}^{-frac{1}{2}}$ is the left eigenvector of $widehat{A}_{odot}$ associated with eigenvalue $1$ .
We know $widehat{A}_{odot}$ is a symmetric matrix, whose left and right eigenvectors associated with the same eigenvalue are simply each other's transpose. Hence, we utilize $boldsymbol{v}_{l} widetilde{D}^{-frac{1}{2}}=left(widetilde{D}^{frac{1}{2}} boldsymbol{e}^{T}right)^{T}$ to obtain $boldsymbol{v}_{l}=boldsymbol{e} widetilde{D}$ . After deriving the eigenvectors of $widehat{A}_{oplus}$ associated with eigenvalue $1 $, corresponding eigenvectors of $ widehat{A}_{odot}$ can be computed by Lemma 3.3.
Theorem 3.1 证明：
$widehat{A}_{oplus}$ can be viewed as a transition matrix because all entries are nonnegative and each row sums to $1$ . The graph $G$ can be further regarded as a Markov chain, whose transition matrix $boldsymbol{P}$ is $widehat{boldsymbol{A}}_{oplus}$ . This Markov chain is irreducible and aperiodic because the graph $G$ is connected and self-loops are included in the connectivity. If a Markov chain is irreducible and aperiodic, then $lim _{k rightarrow infty} P^{k}=Pi$ , where $Pi$ is the matrix with all rows equal to $pi$ and $pi$ can be computed by $pi P=pi$ , s.t. $sum_{i} pi_{i}=1$ . It is obvious that $pi$ is the unique left eigenvector of $P$ and is normalized such that all entries sum to $1$ . Hence, $lim _{k rightarrow infty} widehat{A}_{oplus}^{k}=Pi_{oplus}$ , where $Pi_{oplus}$ is the matrix with all rows are $pi_{oplus}$ and $pi_{oplus}=Psi(e widetilde{D})$ from Lemma 3.4 .
Theorem 3.2 证明：
Although $widehat{boldsymbol{A}}_{odot}$ cannot be processed as a transition matrix like $ widehat{A}_{oplus}$ , it is a symmetric matrix, which is diagonalizable. We have $widehat{A}_{odot}=Q Lambda Q^{T}$ , where $Q$ is an orthogonal matrix whose columns are normalized eigenvectors of $widehat{boldsymbol{A}}_{odot}$ and $Lambda$ is the diagonal matrix whose diagonal entries are the eigenvalues. Then the $k -th$ power of $widehat{boldsymbol{A}}_{odot}$ can be computed by
$widehat{A}_{odot}^{k}=Q Lambda Q^{T} cdots Q Lambda Q^{T}=Q Lambda^{k} Q^{T}=sum_{i=1}^{k} lambda_{i}^{n} boldsymbol{v}_{i} boldsymbol{v}_{i}^{T} quadquadquadquad(7)$
where $boldsymbol{v}_{i}$ is the normalized right eigenvector associated with $lambda_{i}$ . From Lemma 3.4, $widehat{boldsymbol{A}}_{odot}$ always has an eigenvalue $1$ with unique associated eigenvectors and all other eigenvalues $ lambda$ satisfy $|lambda|<1$ . Hence, $lim _{k rightarrow infty} widehat{A}_{odot}^{k}=Phileft(widetilde{D}^{frac{1}{2}} boldsymbol{e}^{T}right)left(Phileft(widetilde{D}^{frac{1}{2}} boldsymbol{e}^{T}right)right)^{T} $.
