Uplifting the Expressive Power of Graph Neural Networks through Graph
  Partitioning
Asela Hevapathige Qing Wang
Graph Neural Networks (GNNs) have paved its way for being a cornerstone in
graph related learning tasks. From a theoretical perspective, the expressive
power of GNNs is primarily characterised according to their ability to
distinguish non-isomorphic graphs. It is a well-known fact that most of the
conventional GNNs are upper-bounded by Weisfeiler-Lehman graph isomorphism test
(1-WL). In this work, we study the expressive power of graph neural networks
through the lens of graph partitioning. This follows from our observation that
permutation invariant graph partitioning enables a powerful way of exploring
structural interactions among vertex sets and subgraphs, and can help uplifting
the expressive power of GNNs efficiently. Based on this, we first establish a
theoretical connection between graph partitioning and graph isomorphism. Then
we introduce a novel GNN architecture, namely Graph Partitioning Neural
Networks (GPNNs). We theoretically analyse how a graph partitioning scheme and
different kinds of structural interactions relate to the k-WL hierarchy.
Empirically, we demonstrate its superior performance over existing GNN models
in a variety of graph benchmark tasks.