小舟、杜伟编译

图同构下等变、计算高效,韦灵思团队提出「自然图网络」消息传递方法

近日,韦灵思团队的一项研究通过研究图的局部对称性,提出了一种新的算法。该算法在不同的边上使用不同的核,从而使网络在局部与全局的图同构体上是等变的,也更易于表达。

通常来说,常规神经消息传递算法在消息排列下是不变的,因此会忘记信息流如何在网络中传递。

近日,阿姆斯特丹大学 ML 教授、高通技术副总裁韦灵思(Max Welling)团队通过研究图的局部对称性,提出了一种通用性更强的算法。该算法在不同的边上使用不同的核,从而使得网络在局部图和全局图同构上呈现等变化,也因而更易于表达。

论文地址:https://arxiv.org/abs/2007.08349v1

具体而言,研究者使用了初级范畴论,将许多显式等变神经网络形式化为自然图网络(Natural Graph Network, NGN),并表明它们的核正是两个函子(functor)之间的自然转换

他们还提供了一个自然网络的图实例,该网络使用等变消息网络参数化,在多个基准上实现了良好的性能。

接下来我们来看这篇论文的具体内容。

自然图网

在图上构建神经网络有一种完全不同的策略,即使用图卷积神经网络或消息传递网络(Kipf 和 Welling, 2016;Gilmer 等人, 2017)。研究者将这类方法称为局部图网络(local graph network, LIGN)。

以最简单的形式,这些每个节点上具有特征 v_p 的转换图信号 v,使用单个共享线性变换 W 在图的边上传递消息,如下公式 2 所示:

其中 E 是图的边集。这类卷积架构通常比全局方法具有更高的计算效率,这是因为计算线性变换的计算成本与边的数量呈线性比例关系。

为了克服现有消息传递网络的局限性,同时又保持更高的计算效率,研究者提出了一种新型的消息传递网络,其中的权重是由图结构决定的

也就是说,研究者对公式 2 做了改进,得到以下公式 3:

其中线性核在每个图每条边上都是不同的。显然,并非所有此类核都会导致等变网络。接下来研究者详细介绍了如何定义核空间。

全局和局部图对称性

研究者用整数数组表示图 G 中的节点 N_G,即,然后图中的边用整数对表示,边的集合是ε(G),则边(p,q)∈ε(G)。

如果图是带有 p→q 这样箭头符号的有向图,那么图 G 和 G’是相似或同构的。换句话说,图同构将节点映射到节点,边映射到边。一种特殊的同构是自同构,只是节点的排列顺序有所变化,边集保持不变。根据定义,一个组中的自同构,称为自同构组。

特征

为了使等变神经网络具有可表达的核,必须将节点 p 处的特征向量 v_p 进行变换,因为节点 p 通过某种全局对称性映射到 p’,而不是像固定消息传递网络中那样保持不变。研究者重新定义了特征向量在局部节点对称性下的变换规则。

局部等变性

边 (p,q) 上的核是 p 点的向量空间 V_p 到 q 点的向量空间 V_q 的映射。核的局部等变性意味着,如果有局部同构的边的空集,则这样做和以下两种情况的结果一样:

  • 将信号从 p 传递到 p’,然后再申请内核 K^(G’)_p’q’;

  • 先申请内核 K^G_pq,然后将 q 转换成 q’。

具体如下图 6 所示:

因此需要以下公式 4:

神经网络的消息参数

等变性只需要在具有同构邻域的边之间共享权重,因此在定理中,我们可以将分类参数用于每个同构类的边邻域,以参数化等变核的空间。

实际上,像社交图(social graph)这类图的异构性很强,很少有边是同构的,并且很少需要共享权重,因而学习和泛化也是很困难的。

这一点可以通过以下方式解决:将 p 到 q 的消息重新解释为函数,其中 G_pq 是边邻域,v_p 是 p 点的特征值,在 v_p 中可能被泛化为非线性的,K 是基于消息网络的神经网络

下图 7 所示为作为图卷积的消息传递过程:

范畴论

全局对称性的等变约束,比如机器学习中广泛使用的公式 1 最近已经被扩展到局部对称性或规范对称性中。

但是,这些形式不包括图的动态局部对称性,并且需要一种通用性更强的语言。

基于此,研究者使用了范畴论,该理论最初是从代数拓扑发展而来的,近来也被用作更多问题的建模工具。范畴论的结构为建立等变消息传递网络(称为自然网络)提供了一个良好的框架,研究者称为「自然网络(Natural Network)」。

实验

二十面体(Icosahedral)的 MNIST

为了在实验中验证该方法与全局对称的等变性,并增强在不变消息传递网络(GCN)上的可表达性,研究者对投影到二十面体的 MNIST 进行了分类。

下表 1 第一列显示了在一个固定(fixed)投影上进行训练和测试的准确率。在第二列中,研究者在通过随机二十面体对称性变换的投影上测试了相同的模型。

结果表明,NGN 的性能优于 GCN,并且准确率相等表明该模型是完全等变的。

图分类

在 Yanardag 和 Vishwanathan 于 2015 年提出的 8 个标准图分类基准集上(包括 5 个生物学数据集和 3 个社交图),研究者使用 GCN 消息参数化评估了该模型。

具体而言,研究者使用了十倍交叉验证(10-fold cross validation)方法,并给出了十倍情况下的最佳平均准确率,如下表 2 所示:

实验结果表明,在大多数数据集上,该研究提出的局部等变方法性能不逊于全局等变方法。

理论图网络自然图网络韦灵思消息传递
相关数据
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

范畴论技术

范畴论是抽象地处理数学结构以及结构之间联系的一门数学理论,以抽象的方法来处理数学概念,将这些概念形式化成一组组的“物件”及“态射”。有些人开玩笑地称之为“一般化的抽象废话”。范畴论出现在很多数学分支中,以及理论计算机科学和数学物理的一些领域。

图神经网络技术

图网络即可以在社交网络或其它基于图形数据上运行的一般深度学习架构,它是一种基于图结构的广义神经网络。图网络一般是将底层图形作为计算图,并通过在整张图上传递、转换和聚合节点特征信息,从而学习神经网络基元以生成单节点嵌入向量。生成的节点嵌入向量可作为任何可微预测层的输入,并用于节点分类或预测节点之间的连接,完整的模型可以通过端到端的方式训练。

交叉验证技术

交叉验证,有时亦称循环估计, 是一种统计学上将数据样本切割成较小子集的实用方法。于是可以先在一个子集上做分析, 而其它子集则用来做后续对此分析的确认及验证。 一开始的子集被称为训练集。而其它的子集则被称为验证集或测试集。交叉验证的目标是定义一个数据集到“测试”的模型在训练阶段,以便减少像过拟合的问题,得到该模型将如何衍生到一个独立的数据集的提示。

图网技术

ImageNet 是一个计算机视觉系统识别项目, 是目前世界上图像识别最大的数据库。

图卷积神经网络技术

图卷积神经网络(Graph Convolutional Network)是一种能对图数据进行深度学习的方法。GCN的三个主要特征:它是卷积神经网络在 graph domain 上的自然推广;它能同时对节点特征信息与结构信息进行端对端学习;适用于任意拓扑结构的节点与图;

图网络技术

2018年6月,由 DeepMind、谷歌大脑、MIT 和爱丁堡大学等公司和机构的 27 位科学家共同提交了论文《Relational inductive biases, deep learning, and graph networks》,该研究提出了一个基于关系归纳偏置的 AI 概念:图网络(Graph Networks)。研究人员称,该方法推广并扩展了各种神经网络方法,并为操作结构化知识和生成结构化行为提供了新的思路。

图分类技术

图分类是许多不同领域中实际应用的问题。为了解决这个问题,通常会计算某些图形统计数据(即图形特征),它们有助于区分不同类别的图形。在计算这些特征时,大多数现有方法会对全图进行处理。

推荐文章
暂无评论
暂无评论~