Twin Weisfeiler-Lehman: High Expressive GNNs for 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.
