Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels
arXiv:2104.02995
Abstract
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.
arXiv comment11 pages
References in corpus (14)
- Inductive Representation Learning on Large Graphs
- Neural Message Passing for Quantum Chemistry
- Simplifying Graph Convolutional Networks
- Biological network comparison using graphlet degree distribution
- graph2vec: Learning Distributed Representations of Graphs
- How Powerful are Graph Neural Networks?
- Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
- A Survey on The Expressive Power of Graph Neural Networks
- DDGK: Learning Graph Representations for Deep Divergence Graph Kernels
- A simple yet effective baseline for non-attributed graph classification
- RetGK: Graph Kernels based on Return Probabilities of Random Walks
- Can Graph Neural Networks Count Substructures?
- Convolutional Kernel Networks for Graph-Structured Data
- A Novel Higher-order Weisfeiler-Lehman Graph Convolution