Press "Enter" to skip to content

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

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

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

 

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

 

 

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

Be First to Comment

发表回复

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