江苏龙网

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

局部|如何设计局部的、计算效率高的、可证明的图神经网络？


最近的开创性论文【1】【2】建立了图神经网络和图同构测试之间的联系 ， 并观察了消息传递机制与 Weisfeiler-Lehman（WL）测试之间的相似性【3】 。 Weisfeiler-Lehman 测试是图论多项式时间迭代算法的层次结构的总称 ， 用于确定图的同构性 。 k-WL 测试在每一步根据邻域聚集规则对图的顶点的 k 元组进行重新着色 ， 并在着色达到稳定后停止 。 如果两个图的颜色直方图不同 ， 则认为这两个图不是同构的；否则 ， 这两个图（但不一定）是同构的 。
消息传递神经网络最多只能和 1-WL 测试（也称为节点颜色细化）一样强大 ， 因此 ， 即使是非常简单的不同构图实例也无法区分 。 例如 ， 消息传递神经网络不能计算三角形【4】 ， 这是已知在社交网络中扮演重要角色的模式 ， 它与表示用户“紧密结合”程度的聚类系数有关【5】 。 设计出表达力更强的图神经网络来复制越来越强大的 k-WL 测试是可以实现的【2】【6】 。 然而 ， 这样的架构会导致很高的复杂性 ， 并带来大量的参数 ， 但最重要的是 ， 通常需要非局部操作 ， 这使得它们不切实际 。
局部|如何设计局部的、计算效率高的、可证明的图神经网络？
本文插图


因此 ， 基于 Weisfeiler-Lehman 层次结构的可证明功能强大的图神经网络 ， 要么功能不强但实用 ， 要么功能强大但不切实际【7】 。 我们在与 Giorgos Bouritsas 和 Fabrizio Frasca【8】的合作的一篇新论文中提出 ， 我认为有一种不同的简单方法可以设计出高效且可证明功能强大的图神经网络 。
图子结构网络（Graph Substructure Networks） 。 这个想法实际上非常简单 ， 在概念上类似于位置编码或图元描述符（graphlet descriptors）【9】：我们使消息传递机制了解局部图结构 ， 允许根据端点节点之间的拓扑关系以不同方式计算消息 。 这是通过向消息传递函数传递与每个节点【10】相关联的附加结构描述符来实现的 ， 这些描述符是通过子图同构计数构造的 。 通过这种方式 ， 我们可以将图中的节点划分成不同的等价类 ， 这些等价类反映了每个图中的节点之间以及不同图之间共享的拓扑特征 。
我们将这种架构成为图子结构网络（Graph Substructure Network ， GSN） 。 它具有与标准消息传递神经网络相同的算法设计、存储和计算复杂度 ， 并增加了构造结构描述符的预计算步骤 。 计数子结构的选择对于 GSN 的表达能力和预计算步骤的计算复杂度都是至关重要的 。

在具有 n 个节点的图中 ， 对大小为 k 的子结构进行计数的最坏情况复杂度为 (n?) 。 因此 ， 它类似于高阶图神经网络模型或 Morris【2】和 Maron【6】 。 然而 ， 与这些方法相比 ， GSN 有几个优点 。 首先 ， 对于某些类型的子结构 ， 例如道路和环 ， 计数的复杂度可以大大降低 。 其次 ， 计算成本高的步骤作为预处理只做一次 ， 因此不影响保持线性的网络训练和推理 ， 这与消息传递神经网络中的方式相同 。 训练和推理的记忆复杂度也是线性的 。 第三 ， 也是最重要的一点 ， GSN 的表达能力不同于 k-WL 测试 ， 在某些情况下更强 。
GSN 有多强大？ 与标准的消息传递网络相比 ， 子结构计数赋予了 GSN 更强的表达能力 。 首先 ， 必须澄清的是 ， GSN 的表达能力取决于所使用的图子结构 。 正如我们有一个 k-WL 测试的层次结构一样 ， 我们可能会有基于对一个或多个结构的技术来获得不同的 GSN 变体 。 使用比星图更复杂的结构 ， GSN 可以严格地比 1-WL（或等效的 2-WL）更强大 ， 因此也比标准消息传递架构更强大 。 对于 4-clique ， GSN 的能力至少不低于 3-WL ， 如下面的强正则图示例所示 ， 其中 ， GSN 成功 ， 而 3-WL 失败：
局部|如何设计局部的、计算效率高的、可证明的图神经网络？


推荐阅读


上一篇：中年|电动车越严管越受车主排斥，这说明了什么？看看是不是这些原因

下一篇：互联网|无债一身轻，贾跃亭这一次真要回国了吗？