How Powerful are K-hop Message Passing Graph Neural Networks

The most popular design paradigm for Graph Neural Networks (GNNs) is 1-hop message passing---aggregating information from 1-hop neighbors repeatedly. However, the expressive power of 1-hop message passing is bounded by the Weisfeiler-Lehman (1-WL) test. Recently, researchers extended 1-hop message passing to K -hop message passing by aggregating information from K -hop neighbors of nodes simultaneously. However, there is no work on analyzing the expressive power of K -hop message passing. In this work, we theoretically characterize the expressive power of K -hop message passing.