江苏龙网

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

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


【5】图子结构在复杂网络中的应用已有十几年的历史 。 在生物信息学方面的开创性论文有：《网络模式：复杂网络的简单构建构建块》（Network motifs: simple building blocks of complex networks） ， R. Milo 等人 ， 2002 年 ， Science 298 (5594):824–827 。 以及《交互式建模：无尺度还是几何？》（Modeling Interactome: Scale-free or geometric?） ， N. Pr?ulj 等人 ， 2004 年 ， Bioinformatics 20(18):3508–3515 ， 该论文介绍了用于生物相互作用网络分析的图模式和图元 。 在这叫网络中 ， 对三角形模式的研究至少可以追溯到《社交网络中的局部结构》（Local structure in social networks） ， P. W. Holladn 和 S. Leinhardt ， 1976 年 ，Sociol. Methodol. 1–45 。

【6】《可证明功能强大的图神经网络》（Provably powerful graph neural networks） ， H. Maron 等人 ， 2019 年 ， Proc. NeurIPS 。
【7】 Morris 的 3-WL 等价图神经网络结构具有 (n3) 空间复杂度和 (n?) 时间复杂度 。 Maron 的架构具有稍微好一些的 (n2) 空间复杂度和 (n3) 时间复杂度 。 对于一个只有 1M 节点的中等大小的图来说 ， 这仍然可以转化为巨大的 1TB 内存和百万万亿次计算 。
【8】 《利用子图同构计数提高图神经网络的表达能力》（Improving graph neural network expressivity via subgraph isomorphism counting） ， G. Bouritsas 等人 ， 2020 年 ， arXiv:2006.09252 。
【9】 基于子结构计数的图分析方法显然遭遇最近关于图深度学习的研究工作 。 值得注意的例子包括 T. Milenkovi? 和 N. Pr?ulj 于 2008 年在 Cancer Inform. 6:257–273 发表的论文《利用图元度签名揭示生物网络功能》（Uncovering biological network function via graphlet degree signatures）中提出的生物信息学中的图元签名 。 或图元核（graphlet kernels） ， 《用于大型图比较的高效图元核》（Efficient graphlet kernels for large graph comparison） ， N. Shervashidze 等人 ， 2009 年 ， Proc. AISTATS 。
【10】 我们也展示了用于边的相同机制 ， 为简洁起见 ， 我省略了这些 。

【11】 3-WL 的子结构计数方面似乎相当薄弱 。 例如 ， 它可以计算多大 7 个节点的模式环 ， 但不能计算有道的 4 个环或长度为 4 的道路 。 目前尚不清楚通过在 WL 层次结构中向上可获得什么样的子结构计数能力 。
【12】 《 Weisfeiler-Lehman 方法和图同构测试》（The Weisfeiler-Lehman method and graph isomorphism testing） ， B. L. Douglas ， 2011 年 ， arXiv:1101.5211 。 请注意 ， 在不同的参考文献所称的“k-WL”之间存有一定程度的混淆 。 Douglas 使用 k-WL 这一术语来报时其他人所说的 (k-1)-FWL（“民间”WL） 。 在我们的术语中 ， k-WL 在（k-1）等正则图上失败 。 强正则图是 2- 等正则图 。
【13】 《树的同余定理》（A congruence theorem for trees） ， P. J. Kelly ， 1957 年 ，Pacific J. Math. 7:961–968 。
【14】 《小图是可重构的》（Small graphs are reconstructible） ， B. D. McKay ， 1997 年 ， Australasian J. Combinatorics 15:123–126 。
【局部|如何设计局部的、计算效率高的、可证明的图神经网络？】


推荐阅读


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

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