Theoretically Improving Graph Neural Networks via Anonymous Walk Graph
  Kernels
  Graph neural networks (GNNs) have achieved tremendous success in graph
mining. However, the inability of GNNs to model substructures in graphs remains
a significant drawback. Specifically, message-passing GNNs (MPGNNs), as the
prevailing type of GNNs, have been theoretically shown unable to distinguish,
detect or count many graph substructures. While efforts have been paid to
complement the inability, existing works either rely on pre-defined
substructure sets, thus being less flexible, or are lacking in theoretical
insights. In this paper, we propose GSKN, a GNN model with a theoretically
stronger ability to distinguish graph structures. Specifically, we design GSKN
based on anonymous walks (AWs), flexible substructure units, and derive it upon
feature mappings of graph kernels (GKs). We theoretically show that GSKN
provably extends the 1-WL test, and hence the maximally powerful MPGNNs from
both graph-level and node-level viewpoints. Correspondingly, various
experiments are leveraged to evaluate GSKN, where GSKN outperforms a wide range
of baselines, endorsing the analysis.
