江苏龙网

  1. 首页 > 资讯 > 科技 > >

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


选自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 的映射 。 核的局部等变性意味着 ， 如果有局部同构的边的空集


推荐阅读


上一篇：|第七次人口普查11月启动 微信申报即可完成

下一篇：中年|VTK9.0中的屏幕空间环境光遮蔽