Press "Enter" to skip to content

普林斯顿高研院, 浙大, CMU和MIT联合提出图核函数与图神经网络的融合方法

 

本文内容来自将门机器学习主题社群

 

论文作者: Simon S. Du  编译:T.R

 

本文为 将门好声音 第 25 期 ,也是 NeurlPS 2019系列分享第 ·4 · 期 。

 

论文作者之一是来自 将门机器学习主题社群、普林斯顿高等研究院博士后 杜少雷 ,本次将分享其团队发表在今年NeurlPS上的工作——【图神经切线核】。

 

如果你也想与广大群友分享自己的研究工作、文章观点、出坑经验,点击 “阅读原文” 或联系将门小姐姐!只要内容合适,我”门”送你头条出道!

 

 

虽然图内核 (graph kernel,GK) 易于训练并享有可证明的理论保证,但其实际性能受其表达能力的限制,因为内核函数往往依赖于图的手工组合特性。与图内核相比,图神经网络通常具有更好的实用性能,因为图神经网络使用多层结构和非线性激活函数来提取图的高阶信息作为特征。

 

然而,由于训练过程中存在大量的超参数,且训练过程具有非凸性,使得GNN的训练更加困难。GNN的理论保障也没有得到很好的理解。此外,GNN的表达能力随参数的数量而变化,在计算资源有限的情况下,很难充分利用 GNN的表达能力。

 

本文提出了一类新的图内核,即 图神经切线核 (GNTKs) ,它对应于通过梯度下降训练的无限宽的多层 GNN。GNTK充分发挥了GNN的表现力,继承了GK的优势。从理论上讲,我们展示了GNTK可以在图上学习一类平滑函数。根据经验,我们在图分类数据集上测试GNTK并展示它们实现了强大的性能。

 

从社交网络到生物网络,大量的图结构数据不断出现。为了从图数据中进行学习,需要我们设计有效的方法来探索图结构。目前用于图数据学习最主要的两类方法分别是图核函数(Graph Kernels,GK)和图神经网络(Graph Neural Networks, GNNs)的方法。对于GK方法来说,无论是显式还是隐式的方法都基于输入图的组合特性建立起特征向量。GK方法具有核函数方法的所有优点,由于其对应着凸优化问题使得基于图核函数的方法便于训练。此外核函数方法具有精确的表达,可以利用理论工具进行详尽的分析和验证。但图核函数方法却受限于其手工特征的表达能力,对于涉及节点间复杂相互作用的高维特征捕捉能力还存在很多不足。

 

而随着卷积神经网络的发展,使用多层卷积结构进行局域信息聚合的图神经网络方法,无需精确的人工特征就能从图中抽取出有效的特征。其对图数据的高维特征抽取能力比核函数方法更为强大,在众多基于图结构数据的任务上取得了优异的结果。然而,由于图卷积网络的目标函数是非凸的,需要仔细地调节超参数来稳定训练过程。同时,训练过程的非凸性质使得任务无法直接分析图网络的学习结果,限制了我们对于GNN的理解。此外,GNN的表达能力与参数量直接相关,在计算资源受限的情况下我们很难学习到一个具有强大特征学习抽取能力的图神经网络模型。

 

核方法和神经网络方法都各有优势,那幺 能不能通过优势互补创造出一种既容易训练又容易解释并具有强大表达能力的模型呢?

 

来自 普林斯顿高研院、浙江大学、CMU 和MIT 的研究人员们在近年研究的启发下,提出了一种新的图核函数—— 图神经切线核函数(Graph Neural Tangent Kernels, GNTKs) 。这种方法等价于利用梯度下降法训练具有无限宽度的GNNs,其中tangent(切线)的命名主要来源于其训练方法—梯度下降法。虽然GNTKs是从无限宽的GNN推导而来,但在预测时GNTK仅仅依赖于图之间的成对的核函数值,可以通过解析式进行高效的计算。这使得GNTK方法同时具有了GNN的强大表达能力和GK核函数容易训练和分析的优势。

 

图神经网络

 

首先我们要回顾一下图神经网络GNN,这是一种对于图数据十分强大的学习框架,它通过多层网络对相邻节点表达的转移与融合来实现局域特征聚合,随后通过池化方式得到整个图结构额表达。基于聚合与池化方式的不同,人们提出了各种各样的图神经网络结构。但在这篇文章中,作者 首先将邻域的聚合过程定义为BLOCK操作,随后将整个图数据上的池化定义为READOUT操作 。

 

BLOCK操作主要用于从邻域中进行特征聚合,可以使用相加、多层感知机等方式进行非线性聚合、或者利用全连接层和ReLU来实现。在GNN中BLOCK操作等价于图卷积操作,其主要目的在于对邻域特征进行抽取表达,基于网络层对特征进行传递和聚合。

 

READOUT操作的目的在于从整个图的特征中得到完整图表示,既可以通过将所有节点的特征进行叠加,也可以通过更为复杂的方式来得到图特征,例如将不同层的特征进行聚合获取完整的图全局特征。

 

在BLOCK和READOUT的基础上,人们就可以构建GNN了。可以通过L个Block操作得到特征,而后通过READOUT操作得到全局图特征。

 

 

GNTK

 

在理解图神经切线核函数之前需要首先明确神经切线核函数的概念。先前的研究已经证明,人工神经网络在无穷宽度极限在可以等价为高斯过程,这就将核方法和神经网络方法衔接了起来。在这样的情况下,网络的训练过程可以用核函数来描述:网络的参数通过梯度下降法进行更新的时候,网络代表的映射f(θ)更新方向将会沿着函数损失的核函数梯度,从而可以引出一个新的核函数方法: 神经切线核函数(Neural Tangent Kernel, NTK) 。

 

下面我们可以从数学上来进一步理解,首先对通用的网络模型 f( θ ,x)  定义损失函数:

 

 

但学习率足够小时,利用参数方程将 f( θ (t),x) 表达为 u(t)  作为网络的输出,此时u满足下面的表达式:

 

 

H代表切向核

 

近年来神经网络的相关研究显示,足够过参数化的网络中H可以在训练过程中基本保持不变。此外在参数随机初始化的情况下,随机矩阵 H(0)  将会以一定概率收敛到确定性的核函数矩阵上,而这一核函数就称为NTK,其对应着无限宽的神经网络。

 

 

在先前关于神经切线核的启发下,研究人员将这套理论应用于图结构数据中,其中f(θ,G)代表了图神经网络,在两个图数据输入的情况下需要计算其对应的GNTK值。首先需要计算下式的取值:

 

 

但网络的输出维度m趋向于无穷时并且θ都是高斯随机变量,其可以被视为高斯过程。对于GNN中的每一层,可以使用Σ来表示输出的协方差,Σ来表示对应层协方差的偏导。由于GNN具有多层结构,这些协方差矩阵可以通过动态规划来进行计算。

 

在此基础上,我们针对两个图数据输入G,G’和一个包含L个BLOCK操作,每个操作包含R层全连接和ReLU激活函数的GNN。可以计算出逐对核函数值Θ(G,G′)的GNTK公式。下面的公式分别展示了进行邻域聚类操作和通过R个全连接层进行转移操作的协方差和中间核函数值的计算公式。

 

 

进行邻域聚类操作

 

 

通过R个全连接层进行转移操作的协方差和中间核函数值

 

在利用BLOCK得到中间输出后,就可以利用下面的公式来得到GNTK的最终结果:

 

 

注:如果需要详细理解推导过程,请参看原文及参考文献

 

https://arxiv.org/abs/1905.13192

 

理论优势和实验结果

 

这种方法对于GNN具有很好的泛化性,下图显示了如何将GNN转化为GNTK的方法。其中对应的特征聚合过程和非线性操作可以通过协方差和核函数值函数进行计算。

 

 

同时在这一理论框架下,我们不仅通过分析得到计算过程中的一些解析表达式和取值上界,同时也能从理论上GNTK可以通过多项式样本学习到图上的平滑函数。这使得GNTK不仅保留了神经网络的强大表达能力,同时也具有核函数方法的高效计算训练特性以及有效的理论支撑。

 

最后研究人员在图数据分类任务上对这一新方法进行了实验。分别在四个生物信息数据三个社交网络数据集上与常见了GK和GNN方法进行了比较,结果与下图所示:

 

 

实验显示在多个数据集上融合GK和GNN的GNTK方法都取得了良好的效果,并在四个数据集上超过了先前的方法。此外在相同架构的情况下,GNTK方法比GNN具有更高的计算效率。

 

研究人员还对GNTK中的参数进行了研究,下图展示了两个数据集上的测试结果随BLOCK操作中的尺度因子的变化情况。研究人员发现在生物数据上拥有更多层数的GNTK具有更好的表现,针对社交网络数据加法聚合比平均聚合的效果更好。

 

 

最后研究人员还分析了 jumping knowledge network (JK) 对结果的影响。实验显示JK与GNN中的结果类似,可以提高网络的性能。同时增加MLP的层数也能够提升模型的表现。

 

 

GNTK通过结合图核函数GK和图卷积GNN的优点,实现了更为有效的图表示学习,如果想要了解更多的细节,请参看论文和详细的代码实现:

 

Paper: https://papers.nips.cc/paper/8809-graph-neural-tangent-kernel-fusing-graph-neural-networks-with-graph-kernels.pdf

 

Code: https://github.com/KangchengHou/gntk/blob/master/gntk.py

 

将门好声音·NeurlPS系列

 

 

1麻省理工HAN Lab提出Point-Voxel CNN用于高效的三维深度学习
2滴滴出行与UC Berkeley联合提出多源域自适应学习新方法
3Facebook与密歇根大学提出加快联合学习的新方法

 

ref:

 

http://simonshaoleidu.com/

 

https://github.com/KangchengHou/gntk/blob/master/gntk.py

 

https://papers.nips.cc/paper/8809-graph-neural-tangent-kernel-fusing-graph-neural-networks-with-graph-kernels

 

组合图论: http://math.xmu.edu.cn/html/xwgl/xydongtai/5070.html

 

Weisfeiler-Lehman(WL)算法:

 

https://zhuanlan.zhihu.com/p/90645716

 

https://www.slideshare.net/pratikshukla11/graph-kernelpdf

 

http://videolectures.net/kdd2017_zhang_link_prediction/

 

over-paramters: https://www.jiqizhixin.com/articles/2019-06-25-18

 

Neural Tangent Kernel: https://arxiv.org/pdf/1806.07572.pdf

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注