WWW2021 | 同源共流：一个优化框架统一与解释图神经网络

会员服务 ·

WWW2021 | 同源共流：一个优化框架统一与解释图神经网络

2021 年 2 月 26 日 专知

论文解读者：北邮 GAMMA Lab 硕士生朱美琪

题目： Interpreting and Unifying Graph Neural Networks with An Optimization Framework

会议： WWW 2021

论文链接： https://arxiv.org/pdf/2101.11859.pdf

百花齐放的图神经网络，是否遵循了某种一致的设计思想？
图神经网络的不同传播机制背后，是否能用一套规则统一与解释？
如若发现这种规则，又能对我们理解与设计新的图神经网络带来何种启发？

1 概览

图神经网络（GNNs）在各种图分析任务中得到了广泛的关注，设计良好的消息传播机制是GNNs中最基本的组成部分，并且被证明是十分有效的。虽然传播机制多种多样，但基本上都是以沿网络拓扑传播聚合节点特征的方式来利用拓扑与特征这两种信息的。鉴于此，一个问题自然会被提出：尽管不同图神经网络有不同的传播策略，是否存在统一的数学准则，能够从本质上指导着不同的传播机制？如果有的话，是什么？对这个问题较为完善的回答，可以帮助我们从宏观的角度考察不同图神经网络之间的关系与差异。这样的数学准则一旦被发现，就能够帮助我们发现现有图神经网络的不足之处，进而激发更多新的图神经网络被设计出来。

本文中，我们首先分析了几个具有代表性的图神经网络（例如GCN，SGC，PPNP）的传播过程，并抽象出他们的共性。我们发现它们均可以归结到一个统一的优化目标框架下，该优化目标由一个带有灵活图卷积核的特征拟合约束项和一个图拉普拉斯正则项组成。特征拟合约束项旨在建立节点表示与原始节点特征之间的关系，而图拉普拉斯正则项则起到拓扑平滑特征的作用。而对应图神经网络传播后的节点表示则可以隐式地看做这个统一优化目标的最优解。

同时，基于该统一优化目标框架也较容易发现现有图神经网络传播策略的不足之处，为设计新的图神经网络也提供了机会。通常来说，设计新的图神经网络往往侧重于设计特定的谱图滤波器或者空域聚合策略，而该统一框架为实现这一目标提供了另一种新的途径，即通过设计传播过程对应的优化目标函数来得到新的GNNs。这样，我们就能够清楚地知道传播过程背后的优化目标，使新设计的图神经网络更具有可解释性和可靠性。

本文的主要贡献总结如下：

提出了一个包含特征拟合项与图正则化项的统一优化目标框架，并从理论上证明了该框架能够解释多个图神经网络的传播策略，为理解图神经网络提供了一个较宏观的视角，也为设计新的图神经网络带来新思路。
基于该统一优化框架，我们设计了两种具有灵活图卷积核拟合项的图神经网络传播目标，并给出相应的网络模型。同时对他们的收敛性，表达能力等进行了理论分析。
我们在六个数据集上验证了提出两种图神经网络模型的效果，实验也表明他们具有较好的缓解过平滑的能力。这进一步验证了基于该统一框架设计新图神经网络的可行性。

2 统一的优化目标框架

不同GNNs精心设计的传播机制基本遵循相似的步骤，即节点特性沿网络拓扑结构进行一定深度的聚合和变换。在这里，我们首先将 -层传播机制归纳成以下的形式：

并且是 -层传播后的输出表示。表示沿着网络结构聚合第层的输出，是每层的特征变换操作：包括非线性激活函数和分层可学习的权重矩阵。通常取决于特定的GNN模型，表示 -层卷积之后的广义组合操作：对于像GCN、SGC、APPNP等图神经网络， $\big\langle\big\rangle_{K}$ 直接使用最后一层的输出；对于如JKNet、DAGNN等图神经网络，可能代表对来自部分（或全部）输出的拼接，加权求和等操作。

可以看出，包括特征聚合与变换的传播过程是图神经网络的核心，而网络拓扑和节点特征是传播过程中约束所学表示的两个重要信息来源：(1) 网络拓扑起到低通滤波的作用，平滑两个连接节点的特征信息，使得学习到的节点表示能够捕捉图结构的同质性。(2) 节点特征本身包含复杂的信息，如低频和高频信息，可以灵活地用于进一步约束已学习的节点表示。由此可以看到，图神经网络的传播过程实际上是为了实现两个目标：充分利用网络拓扑的平滑能力以及从特征中编码出有用的信息，这可以正式表述为以下优化目标：

这里，是非负系数，通常从中选取，是原始输入特征矩阵的变换，和为任意图卷积核，是学习的节点表示，即最终传播后的输出结果。

在这个统一框架中，第一部分是一个拟合项，它通过设计不同的图卷积核和，将中的信息灵活地编码为学习到的表示。和可以从全通滤波器，低通滤波器，高通滤波器等中选择。第二部分是一个拉普拉斯正则化项，利用拓扑平滑节点特征，约束两个连通节点的学习表示变得相似，从而可以捕获网络的同质性。

3 解释经典图神经网络

我们从理论上证明了一些典型图神经网络的传播机制实际上是该统一框架的特殊情况。统一的理论框架建立起了经典图神经网络之间的联系，使我们能够从全局的角度来理解各种GNN。下面我们只简述文中给出传播过程的形式与对应定理，详细证明过程请参见论文。

3.1 解释GCN与SGC

(1) 解释 -层GCN/SGC

GCN的传播过程：

2. S GC的传播过程：

3. 解释 -层GCN/SGC：

(2) 解释图卷积操作

图卷积操作：

2. 使用一阶近似解释图卷积操作：

3.2 解释PPNP与APPNP

PPNP的传播过程：
APPNP的传播过程：
解释PPNP/APPNP：
证明：

3.3 解释JKNet与DAGNN

(1) 解释JKNet

JKNet的传播过程：
解释JKNet：

(2) 解释DAGNN

DAGNN的传播过程：
解释DAGNN：

3.4 讨论

为了清晰起见，我们在表1中总结了不同GNN和对应目标函数之间的总体关系。可以看出，我们提出的框架抽象了不同有代表性GNN之间的共性。基于这个框架，我们可以更容易地理解它们之间的关系。例如定理3.1中对应的SGC优化目标只有一个图正则化项，而定理3.3中对应的APPNP目标既有拟合项也有图正则化项。目标函数的差异能够很好地解释深层APPNP（PPNP）在过平滑问题上优于SGC（GCN）的原因：它额外编码了原始特征信息到所学的节点表示中。

另一方面，我们提出的框架通过对目标优化函数的数学建模，显示了一个宏大的GNN设计图景。既然现有的不同GNN可以被归纳到这个框架下，那么就可以很容易地基于该框架提出新的GNN。我们所需要做的就是根据特定场景设计这个框架的可变内容（如不同的图卷积核和的选择），这样对应的传播过程就可以很容易的推导出来，进而设计出新的GNNs架构。鉴于传播过程的目标函数已经确定，对应的图神经网络就具有更高的可解释性与可靠性。

表1. 图神经网络的传播机制与优化目标之间的对应关系

4 基于统一框架的图神经网络设计

基于上述统一框架，我们可以发现当前大多数GNN在特征拟合项中只是简单地将和设置为，这意味着它们需要将中的所有原始信息编码为。而事实上，可能不可避免地包含噪音或不确定信息，很难确定需要对什么信息进行编码，只考虑一种信息较难满足下游不同任务的需要。在本节中，我们将重点设计新颖的和，以便在框架下灵活地编码更全面的信息。

这里我们以两个设计方案为例来说明基于该统一框架的设计思路，下文中只列举设计的优化目标与推导的网络模型形式，其他具体内容见论文。

4.1 设计低通滤波性质的卷积核

这里我们首先考虑在原始空间和低频滤波空间中构建和的关系。

传播过程的优化目标：
通过调整平衡系数，该设计目标可以灵活约束和在原始空间和低频滤波空间的相似性，有利于满足不同任务的需求。
基于闭式解设计的网络：
基于迭代解设计的网络：

4.2 设计高通滤波性质的卷积核

与4.1节的模型相似，我们现在考虑在原始滤波空间和高频滤波空间中保持和的相似性。为了后续分析的整洁性，我们选择以下目标：

传播过程的优化目标：
基于闭式解设计的网络：
基于迭代解设计的网络：

5 实验

表2 节点分类实验

图1 不同模型性能受传播深度影响的分析结果

图2 模型性能受三个可调系数、、影响的分析

6 总结

本文研究了不同神经网络传播机制的内在关系。我们建立了不同图神经网络与一个灵活的优化目标框架之间的关系。本文所提出的框架为理解和分析不同图神经网络提供了一个较为宏观的视角，并且进一步帮助我们识别出现有图神经网络的弱点。基于该统一的优化目标框架，我们提出了两种具有可调低通和高通滤波器的新图神经网络模型，并分析了它们表达能力。大量的实验证明了这两种GNNs在现实世界数据集上优于最新模型的性能，并进一步验证了基于该统一框架设计新图神经网络的可行性。

本期责任编辑：王啸

本期编辑：刘佳玮

北邮 GAMMA Lab 公众号

主编：石川

责任编辑：王啸、杨成

编辑：刘佳玮

副编辑：郝燕如，纪厚业

专知便捷查看