图同构下等变,计算高效,韦灵思团队提出''自然图网络''消息传递方法
选自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 的映射 。 核的局部等变性意味着 ， 如果有局部同构的边的空集
推荐阅读
- Java|计算机专业的本科生，该选择学习Java技术体系还是.NET技术体系
- 电子|两市百元股达123只 医药生物、电子、计算机行业较集中
- 生物|两市百元股达123只 医药生物、电子、计算机行业较集中
- 边缘计算平台规划实施，企业必须掌握的十大方法
- 树袋熊|中国科学家发布亿级神经元类脑计算机
- 上游新闻|腾讯西部云计算数据中心二期一半的项目规划已建成
- 娱见现实|计算方式被吐槽：当我们傻？，赵丽颖上任第一天就赚了六千多
- 彭实戈摘得未来科学大奖“数学与计算机科学奖”
- 一枚小公仆|表格计算原来如此简单，Word
- 精英联盟总队|IFA前瞻解读｜看5G手机、移动计算、毫米波等创新变革