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

2020-08-04 22:16
北京

选自arXiv

作者:Pim de Haan、Taco Cohen、Max Welling

机器之心编译

编辑:小舟、杜伟

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

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

近日,阿姆斯特丹大学 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 所示:

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

Amazon SageMaker 是一项完全托管的服务,可以帮助开发人员和数据科学家快速构建、训练和部署机器学习 模型。SageMaker完全消除了机器学习过程中每个步骤的繁重工作,让开发高质量模型变得更加轻松。

现在,企业开发者可以免费领取1000元服务抵扣券,轻松上手Amazon SageMaker,快速体验5个人工智能应用实例。

© THE END

转载请联系本公众号获得授权

投稿或寻求报道:content@jiqizhixin.com

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

阅读原文

    特别声明
    本文为澎湃号作者或机构在澎湃新闻上传并发布,仅代表该作者或机构观点,不代表澎湃新闻的观点或立场,澎湃新闻仅提供信息发布平台。申请澎湃号请用电脑访问https://renzheng.thepaper.cn。