关于图神经网络图正则化的再思考

正则化的再思考"/>

关于图神经网络图正则化的再思考

《Rethinking Graph Regularization for Graph Neural Networks》

PaperInfo

• 作者：Han Yang, Kaili Ma, James Cheng
• 单位：香港中文大学
• 发表时间：2020年9月4日
  paper

目录

• • 1 Introduction
  • 2 Propagation-Regularization
  • 3 Understanding P-reg through Laplacian Regularization and Infinite-Depth GCN
  • • 3.1 Equivalence of Squared-Error P-Reg to Squared Laplacian Regularization
    • 3.2 Equivalence of Minimizing P-Reg to Infinite-Depth GCN
    • 3.3与其他现有工作的连接
  • 4 Why P-Reg can improve existing GNNs
  • • 4.1 Benefits of P-Reg from the Graph Regularization Perspective
    • • 4.1.1 Graph Regularization Provides Extra Supervision Information
      • 4.1.2图拉普拉斯正则化的局限性遗憾的是，图拉普拉斯正则化很难提供现有GNN无法捕捉的额外信息。
      • 4.1.3 P-REG如何解决图拉普拉斯正则化的局限性P-REG为GNN提供了新的监督信息。
    • 4.2 Benefits of P-Reg from the Deep GCN Perspective
    • • 4.2.1 Deeper GCN Provides Information from Farther Nodes
      • 4.2.2 Limitations of Deep GCNs
      • 4.2.3 P-REG如何解决深度GCNS P-REG的局限性P-REG能够以低成本有效地平衡信息捕获和过度平滑。
  • 5 Experimental Results
  • • 5.1 Improvements on Node Classification Accuracy
    • 5.2 Comparison with the State-of-the-Art Methods (using the Standard Split)
    • 5.3 Experiments of Graph-Level Tasks
  • 6 Conclusions

Abstract

图的拉普拉斯正则化项通常用于半监督表示学习，以提供模型f(X)的图结构信息。然而，随着最近图神经网络(GNN)的流行，将图结构A直接编码成一个模型，即f(A，X)，已经成为更常用的方法。同时，我们证明了图拉普拉斯正则化对现有的GNN几乎没有好处，并提出了一种简单但非平凡的图拉普拉斯正则化的变体，称为传播正则化(P-REG)，以提高现有GNN模型的性能。我们通过形式化分析表明，P-REG不仅为GNN注入了传统的图拉普拉斯正则化所不能捕捉到的额外信息，而且具有相当于无限深度图卷积网络的容量。我们证明了P-REG可以有效地提高现有GNN模型在许多不同数据集的节点级和图形级任务上的性能。

1 Introduction

半监督节点分类是图学习中最常用、最重要的问题之一。许多有效的方法已经被提出用于通过向特征映射模型f(X)添加正则化项(例如，拉普拉斯正则化)来进行节点分类： F ( X ) ： R N × F → R N × C F(X)：R^{N×F}→R^{N×C} F(X)：RN×F→RN×C，其中N是节点数量，F是节点特征的维度，C是预测类别的数量，并且 X ∈ R N × F X∈R^{N×F} X∈RN×F是节点特征矩阵。这些方法的一个已知缺点是模型F本身仅对图中每个节点的特征进行建模，而没有考虑节点之间的关系。基于相邻节点可能共享同一类标签的假设，它们依赖正则化项来捕捉图的结构信息。然而，这一假设在许多现实世界的图表中并不成立，因为这些图表中的节点之间的关系可能很复杂，如(Kipf和Well 2017)中所指出的。这推动了早期图形神经网络(GNN)模型的发展，例如图形卷积网络(GCN)(Kipf和Welling2017)。

许多GNN将图的结构信息直接编码到它们的模型中为 f ( A ， X ) ： ( R N × N ， R N × F ) → R N × C f(A，X)：(R^{N×N}，R^{N×F})→R^{N×C} f(A，X)：(RN×N，RN×F)→RN×C，其中 A ∈ R N × N A∈R^{N×N} A∈RN×N是图的邻接矩阵。然后，他们通过最小化有监督的分类损失来简单地训练模型，而不使用图的正则化。然而，在这项工作中，我们提出了一个问题：图正则化是否也能像传统节点分类模型那样提高现有GNN模型的性能？

我们对这个问题给出了肯定的回答。我们证明了现有的GNN已经捕捉到了传统的图拉普拉斯正则化所能提供的图结构信息。因此，我们提出了一种新的图正则化方法–传播正则化(P-REG)，它是基于拉普拉斯正则化的图正则化的变体，它为图中的节点提供新的监督信号。此外，我们还证明了P-REG具有与无限深度GCN相同的能力，这意味着P-REG使每个节点能够从更远的节点获取信息(与深度GCN一样，但更灵活，可以避免过度平滑，并且计算成本要低得多)。我们通过实验验证了P-reg作为提高现有GNN模型性能的通用工具的有效性。我们相信，我们的工作可以为GNN框架设计提供一个新的方向。

2 Propagation-Regularization

附录A中还给出了本文使用的符号及其描述。为了便于说明，我们使用一个两层的GCN模型 f 1 f_{1} f1​作为GNN的例子。GCN模型f1可以表示为 f 1 ( A , X ) = f_{1}(A, X)= f1​(A,X)= A ^ ( σ ( A ^ X W 0 ) ) W 1 \hat{A}\left(\sigma\left(\hat{A} X W_{0}\right)\right) W_{1} A^(σ(A^XW0​))W1​，其中 W 0 ∈ R F × H W_{0} \in \mathbb{R}^{F \times H} W0​∈RF×H， W 1 ∈ R H × C W_{1} \in \mathbb{R}^{H \times C} W1​∈RH×C是线性映射矩阵， H H H是隐藏单元的大小。 A = D − 1 A A=D^{−1}A A=D−1A是归一化邻接矩阵，其中 D ∈ R N × N D∈R^{N×N} D∈RN×N是对角度矩阵， D i i = ∑ j = 1 N A i j D_{i i}=\sum_{j=1}^{N} A_{i j} Dii​=∑j=1N​Aij​ and D i j = 0 D_{i j}=0 Dij​=0 if i ≠ j . σ i \neq j . \quad \sigma i​=j.σ是激活函数。F1将图的结构和结点特征作为输入，然后输出 Z = f 1 ( A , X ) ∈ R N × C Z=f_{1}(A, X) \in \mathbb{R}^{N \times C} Z=f1​(A,X)∈RN×C， P i j = exp ⁡ ( Z i j ) ∑ k = 1 C exp ⁡ ( Z i k ) P_{i j}=\frac{\exp \left(Z_{i j}\right)}{\sum_{k=1}^{C} \exp \left(Z_{i k}\right)} Pij​=∑k=1C​exp(Zik​)exp(Zij​)​ for i = 1 , … , N i=1, \ldots, N i=1,…,N and j = 1 , … , C j=1, \ldots, C j=1,…,C。这里， P ∈ R N × C P \in \mathbb{R}^{N \times C} P∈RN×C是所有节点的预测类别后验概率。通过输出 Z Z Z 的输出 f 1 f_{1} f1​的进一步传播，将获得 Z ′ = A ^ Z ∈ Z^{\prime}=\hat{A} Z \in Z′=A^Z∈ R N × C \mathbb{R}^{N \times C} RN×C.对应的softmax最大概率输出 Z ′ Z^{\prime} Z′由 Q i j = exp ⁡ ( Z i j ′ ) ∑ k = 1 C exp ⁡ ( Z i k ′ ) Q_{i j}=\frac{\exp \left(Z_{i j}^{\prime}\right)}{\sum_{k=1}^{C} \exp \left(Z_{i k}^{\prime}\right)} Qij​=∑k=1C​exp(Zik′​)exp(Zij′​)​ for i = 1 , … , N i=1, \ldots, N i=1,…,N and j = 1 , … , C j=1, \ldots, C j=1,…,C给出。

传播正则化的定义如下： L P − r e g = 1 N ϕ ( Z , A ^ Z ) , \mathcal{L}_{P-r e g}=\frac{1}{N} \phi(Z, \hat{A} Z), LP−reg​=N1​ϕ(Z,