论文标题
Twin Weisfeiler-Lehman：图形分类的高表情GNN
Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification
论文作者
论文摘要
消息传递GNNS的表达力是由Weisfeiler-Lehman（WL）测试限制的。为了实现超出WL检验的高表达性GNN，我们提出了一种新型的图形同构测试方法，即Twin-WL，该方法同时传递了节点标记和节点身份，而不仅仅是将节点标记作为WL传递。标识的机制编码了根部的子图的完整结构信息，因此Twin-WL可以在区分图结构时提供额外的功率。基于Twin-WL，我们通过在根部子图上定义读取函数来实现两个双胞胎分类：一个简单地读取了rooted子图的大小和其他读数的大小在GNN式之后，子图的丰富结构信息丰富的结构信息。我们证明，这两个双胞胎GNN都具有比传统消息传递GNN具有更高的表达能力。实验还证明了在图形分类任务下，双胞胎gnns显着胜过最先进的方法。
The expressive power of message passing GNNs is upper-bounded by Weisfeiler-Lehman (WL) test. To achieve high expressive GNNs beyond WL test, we propose a novel graph isomorphism test method, namely Twin-WL, which simultaneously passes node labels and node identities rather than only passes node label as WL. The identity-passing mechanism encodes complete structure information of rooted subgraph, and thus Twin-WL can offer extra power beyond WL at distinguishing graph structures. Based on Twin-WL, we implement two Twin-GNNs for graph classification via defining readout function over rooted subgraph: one simply readouts the size of rooted subgraph and the other readouts rich structure information of subgraph following a GNN-style. We prove that the two Twin-GNNs both have higher expressive power than traditional message passing GNNs. Experiments also demonstrate the Twin-GNNs significantly outperform state-of-the-art methods at the task of graph classification.
