Weisfeiler and Lehman Go Cellular: CW Networks
Weisfeiler and Lehman Go Cellular: CW Networks
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Cristian Bodnar;Fabrizio Frasca;N. Otter;Yu Guang Wang;P. Lio’;Guido Montúfar;M. Bronstein
中科院分区：
文献类型：
--
作者：
Cristian Bodnar;Fabrizio Frasca;N. Otter;Yu Guang Wang;P. Lio’;Guido Montúfar;M. Bronstein
图神经网络（GNN）的表达能力有限，难以处理远程交互，并且缺乏对高阶结构建模的原则性方法。这些问题可以归因于计算图和输入图结构之间的强耦合。最近提出的消息传递简单网络通过在图的团复合体上执行消息传递来自然地解耦这些元素。然而，这些模型可能会受到单纯形复合体（SC）的严格组合结构的严重限制。在这项工作中，我们扩展最近的理论结果SC定期细胞复杂，拓扑对象，灵活suburbanSC和图形。我们表明，这种概括提供了一个强大的图形“提升”变换，每个导致一个独特的层次信息传递过程。由此产生的方法，我们统称为CW网络（CWNs），严格来说比WL测试更强大，并且不比3-WL测试更强大。特别是，我们证明了这样一个计划的有效性，基于环，当应用到分子图问题。所提出的架构受益于可证明的比常用GNN更大的表达能力，高阶信号的原则性建模以及压缩节点之间的距离。我们证明了我们的模型在各种分子数据集上实现了最先进的结果。
Graph Neural Networks (GNNs) are limited in their expressive power, struggle with long-range interactions and lack a principled way to model higher-order structures. These problems can be attributed to the strong coupling between the computational graph and the input graph structure. The recently proposed Message Passing Simplicial Networks naturally decouple these elements by performing message passing on the clique complex of the graph. Nevertheless, these models can be severely constrained by the rigid combinatorial structure of Simplicial Complexes (SCs). In this work, we extend recent theoretical results on SCs to regular Cell Complexes, topological objects that flexibly subsume SCs and graphs. We show that this generalisation provides a powerful set of graph"lifting"transformations, each leading to a unique hierarchical message passing procedure. The resulting methods, which we collectively call CW Networks (CWNs), are strictly more powerful than the WL test and not less powerful than the 3-WL test. In particular, we demonstrate the effectiveness of one such scheme, based on rings, when applied to molecular graph problems. The proposed architecture benefits from provably larger expressivity than commonly used GNNs, principled modelling of higher-order signals and from compressing the distances between nodes. We demonstrate that our model achieves state-of-the-art results on a variety of molecular datasets.