Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification
This addresses the problem of low expressiveness in graph neural networks for researchers and practitioners in graph machine learning, offering a novel method beyond incremental improvements.
The paper tackles the limited expressive power of message passing GNNs, which is bounded by the Weisfeiler-Lehman test, by proposing Twin-WL, a novel graph isomorphism test that passes both node labels and identities to encode complete rooted subgraph information, resulting in Twin-GNNs that significantly outperform state-of-the-art methods in graph classification.
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.