{'fraction_non_alphanumeric': 0.04351139843484178, 'fraction_numerical': 0.015719632528070772, 'mean_word_length': 4.148983882270498, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 6, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
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. Specifically, we first formally differentiate two different kernels of K-hop message passing which are often misused in previous works. We then characterize the expressive power of K-hop message passing by showing that it is more powerful than 1-WL and can distinguish almost all regular graphs. Despite the higher expressive power, we show that K-hop message passing still cannot distinguish some simple regular graphs and its expressive power is bounded by 3-WL. To further enhance its expressive power, we introduce a KP-GNN framework, which improves K-hop message passing by leveraging the peripheral subgraph information in each hop. We show that KP-GNN can distinguish many distance regular graphs which could not be distinguished by previous distance encoding or 3-WL methods. Experimental results verify the expressive power and effectiveness of KP-GNN. KP-GNN achieves competitive results across all benchmark datasets.


Introduction
Currently, most existing graph neural networks (GNNs) follow the message passing framework, which iteratively aggregates information from the neighbors and updates the representations of nodes. It has shown superior performance on graph-related tasks [1,2,3,4,5,6,7] comparing to traditional graph embedding techniques [8,9]. However, as the procedure of message passing is similar to the 1-dimensional Weisfeiler-Lehman (1-WL) test [10], the expressive power of message passing GNNs is also bounded by the 1-WL test [7]. Namely, GNNs cannot distinguish two non-isomorphic graph structures if the 1-WL test would fail.
In normal message passing GNNs, the node representation is updated by the direct neighbors of the node, which are called 1-hop neighbors. Recently, some works extend the notion of message passing into K-hop message passing [11,12,13,14,15]. K-hop message passing is a type of message passing where the node representation is updated by aggregating information from not only 1st hop but all the neighbors within K hops of the node. However, there is no work on theoretically 36th Conference on Neural Information Processing Systems (NeurIPS 2022). characterizing the expressive power of GNNs with K-hop message passing, e.g., whether it can improve the 1-hop message passing or not, and to what extent it can.
In this work, we theoretically characterize the expressive power of K-hop message passing GNNs. Specifically, 1) we formally distinguish two different kernels of the K-hop neighbors, which are often misused in previous works. The first kernel is based on whether the node can be reached within k steps of the graph diffusion process and it is used in GPR-GNN [14] and MixHop [11]. The second one is based on the shortest path distance of k and it is used in GINE+ [15] and Graphormer [16]. Further, we show that different kernels of K-hop neighbors will result in different expressive power of K-hop message passing. 2) We show that K-hop message passing is strictly more powerful than 1-hop message passing and can distinguish almost all regular graphs. 3) However, it still failed in distinguishing some simple regular graphs, no matter which kernel is used, and its expressive power is bounded by 3-WL. This motivates us to further improve K-hop message passing.
Here, we introduce KP-GNN, a new GNN framework with K-hop message passing, which significantly improves the expressive power of standard K-hop message passing GNNs. In particular, during the aggregation of neighbors in each hop, KP-GNN not only aggregates neighboring nodes in that hop but also aggregates the peripheral subgraph (subgraph induced by the neighbors in that hop). This additional information helps the KP-GNN to learn more expressive local structural features around the node. We further show that KP-GNN is able to distinguish many distance regular graphs with a proper encoder for the peripheral subgraph. The proposed KP-GNN has several additional advantages. First, it can be applied to most existing K-hop message-passing GNNs with only slight modification. Second, it only adds little computational complexity to standard K-hop message passing. We demonstrate the effectiveness of the KP-GNN framework through extensive experiments on both simulation and real-world datasets.
2 K-hop message passing and its expressive power 2

.1 Notations
Denote a graph as G = (V, E), where V = {1, 2, ..., n} is the node set and E ⊆ V × V is the edge set. Meanwhile, denote A ∈ {0, 1} n×n as the adjacency matrix of graph G. Denote x v as the feature vector of node v and denote e uv as the feature vector of the edge from u to v. Finally, we denote Q 1 v,G as the set of 1-hop neighbors of node v in graph G and N 1 v,G =Q 1 v,G ∪ {v}. Note that when we say K-hop neighbors of node v, we mean all the neighbors that have distance from node v less than or equal to K. In contrast, k-th hop neighbors mean the neighbors with exactly distance k from node v. The definition of distance will be discussed in section 2.3.

1-hop message passing framework
Currently, most existing GNNs are designed based on 1-hop message passing framework [17]. Denote h l v as the output representation of node v at layer l and h 0 v = x v . Briefly, given a graph G and a 1-hop massage passing GNN, at layer l of the GNN, h l v is computed by where m l v is the message to node v at layer l, MES l and UPD l are message and update functions at layer l respectively. After L layers of message passing, h L v is used as the final node representation of node v. Such a representation can be used to conduct node-level tasks like node classification and node regression. To get the graph representation, a readout function is used: where READOUT is the readout function for computing the final graph representation. Then h G can be used to conduct graph-level tasks like graph classification and graph regression.

K-hop message passing framework
The 1-hop message passing framework can be directly generalized to K-hop message passing, as it shares the same message and update mechanism. The difference is that an independent message and update function can be employed for each hop. Meanwhile, a combination function is needed to combine the results from different hops into the final node representation at this layer. First, we differentiate two different kernels of K-hop neighbors, which are interchanged and misused in previous research.
The first kernel of K-hop neighbors is shortest path distance (spd) kernel. Namely, the k-th hop neighbors of node v in graph G is the set of nodes that have the shortest path distance of k from v.
Definition 1. For a node v in graph G, the K-hop neighbors N K,spd v,G of v based on shortest path distance kernel is the set of nodes that have the shortest path distance from node v less than or equal to K. We further denote Q k,spd v,G as the set of nodes in G that are exactly the k-th hop neighbors (with shortest path distance of exactly k) and N 0,spd v,G = Q 0,spd v,G = {v} is the node itself.
The second kernel of the K-hop neighbors is based on graph diffusion (gd).
Definition 2. For a node v in graph G, the K-hop neighbors N K,gd v,G of v based on graph diffusion kernel is the set of nodes that can diffuse information to node v within the number of random walk diffusion steps K and the diffusion kernel A. We further denote Q k,gd v,G as the set of nodes in G that are exactly the k-th hop neighbors (nodes that can diffuse information to node v with k diffusion steps) and N 0,gd v,G = Q 0,gd v,G = {v} is the node itself.
Note that a node can be a k-th hop neighbor of v for multiple k based on the graph diffusion kernel but it can only appear in one hop for the shortest path distance kernel. We include more discussions of K-hop kernels in Appendix A. Next, we define the K-hop message passing framework as follows: where t ∈ {spd, gd}, spd is the shortest path distance kernel and gd is the graph diffusion kernel.
Here, for each hop, we can apply unique MES and UPD functions. Note that for k > 1, there may not exist the edge feature e uv as nodes are not directly connected. But we leave it here since we can use other types of features to replace it like path encoding. We further discuss it in Appendix I.
Comparing to the 1-hop message passing framework described in Equation (1), the COMBINE function is introduced to combine the representations of node v at different hops. It is easy to see that a L layer 1-WL GNNs is actually a L layer K-hop message passing GNNs with K = 1. We include more discussions of K-hop message passing GNNs in Appendix A. To aid further analysis, we also prove that K-hop message passing can injectively encode the neighbor representations at different hops into h l v in Appendix B.

Expressive power of K-hop message passing framework
In this section, we theoretically analyze the expressive power of K-hop message passing. We assume there is no edge feature and all nodes in the graph have the same feature, which means that GNNs can only distinguish two nodes with the local structure of nodes. Note that including node features only increases the expressive power of GNNs as nodes/graphs are more easily to be discriminated. It has been proved that the expressive power of 1-hop message passing is bounded by the 1-WL test on discriminating non-isomorphic graphs [7,18]. In this section, We show that the K-hop message passing is strictly more powerful than 1-WL test when K > 1. Across the analysis, we utilize regular graphs as examples to illustrate our theorems since they cannot be distinguished using either 1-hop message passing or the 1-WL test. To begin the analysis, we first define proper K-hop message passing GNNs. Definition 3. A proper K-hop message passing GNN is a GNN model where the message, update, and combine functions are all injective given the input from a countable space.
A proper K-hop message passing GNN is easy to find due to the universal approximation theorem [19] of neural network and the Deep Set for set operation [20]. In the latter sections, by default all mentioned K-hop message passing GNNs are proper. Next, we introduce node configuration: Definition 4. The node configuration of node v in graph G within k hops under t kernel is a list A k,t v,G = (a 1,t v,G , a 2,t v,G , ..., a k,t v,G ), where a i,t v,G = |Q i,t v,G | is the number of i-th hop neighbors of node v.  When we say two node configurations A k,t v1,G (1) and A k,t v2,G (2) are equal, we mean that these two lists are component-wise equal to each other. Now, we state the first proposition: Proposition 1. A proper K-hop message passing GNN is strictly more powerful than 1-hop message passing GNNs when K > 1.
To see why this is true, we first discuss how node configuration is related to the first layer of message passing. In the first layer of K-hop message passing, each node aggregates neighbors from up to K hops. As each node has an identical label, an injective message function can only know how many neighbors at each hop, which is exactly the node configuration. In other words, The first layer of K-hop message passing is equivalent to inject node configuration to each node label. When K = 1, the node configuration of v 1 and v 2 are d v1,G (1) and d v2,G (2) , where d v,G is the node degree of v. After L layers, GNNs can only get the node degree information of each node within L hops of node v. Then, it is straightforward to see why these GNNs cannot distinguish any n-sized r-regular graph, as each node in the regular graph has the same degree.
Next, when K > 1, the K-hop message passing is at least equally powerful as 1-hop message passing since node configuration up to K hop includes all the information the 1 hop has. To see why it is more powerful, we use two examples to illustrate it. The first example is shown in the left part of Figure 1. Suppose here we use graph diffusion kernel and we want to learn the representation of node v 1 and node v 2 in the two graphs, we know that the 1-hop GNNs produce the same representation for two nodes as they are both nodes in 6-sized 3-regular graphs. However, it is easy to see that v 1 and v 2 have different local structures and should have different representations. Instead, if we use the 2-hop message passing with the graph diffusion kernel, we can easily distinguish two nodes by checking the 2nd hop neighbors of the node, as node v 1 has four 2nd hop neighbors but node v 2 only has two 2nd hop neighbors. The second example is shown in the right part of Figure 1. Two graphs in the example are still regular graphs. Suppose here we use shortest path distance kernel, node v 1 and v 2 have different numbers of 2nd hop neighbors and thus will have different representations by performing 2-hop message passing. These two examples convincingly demonstrate that the K-hop message passing with K > 1 can have better expressive power than K = 1. To further study the expressive power of K-hop message passing on regular graphs, we show the following result: Theorem 1. Consider all pairs of n-sized r-regular graphs, let 3 ≤ r < (2log2n) 1/2 and be a fixed constant. With at most K = ( 1 2 + ) log 2n log (r−1) , there exists a 1 layer K-hop message passing GNN using the shortest path distance kernel that distinguishes almost all 1 − o(n −1/2 ) such pairs of graphs.
We include the proof and simulation results in Appendix C. Theorem 1 shows that even with 1 layer and a modest K, K-hop GNNs are powerful enough for distinguishing almost all regular graphs.
Finally, we characterize the existing K-hop methods with the proposed K-hop message passing framework. Specifically, we show that 1) the expressive power of K layer GINE [15] is bounded by K layer K-hop message passing with the shortest path distance kernel. 2) The expressive power of the Graphormer [16] is equal to K-hop GNNs with the shortest path distance kernel and infinity K.
3) For spectral GNNs and existing K-hop GNNs with the graph diffusion kernel like MixHop [11] and MAGNA [13], we find they actually use a weak version of K-hop than the definition of us. Specifically, it is shown that the expressive power of spectral GNNs is also bounded by 1-WL test [21], which seems to contradict our result as graph diffusion can be viewed as a special case of spectral GNN. However, we show that our definition of K-hop message passing with graph diffusion kernel actually injects a non-linear function on the spectral basis, thus achieving superior expressive power. We leave the detailed discussion in Appendix D. Further, Distance Encoding [22] also uses the shortest path distance information to augment the 1-hop message passing, which is similar to K-hop GNNs with the shortest path distance kernel. However, we find the expressive power of the two frameworks is different from each other. We leave the detailed discussion in Appendix E.

Limitation of K-hop message passing framework
Although we show that K-hop GNNs with K > 1 are better at distinguishing non-isomorphic structures than 1-hop GNNs, there are still limitations. In this section, we discuss the limitation of K-hop message passing. Specifically, we show that the choice of the kernel can affect the expressive power of K-hop message passing. Furthermore, even with K-hop message passing, we still cannot distinguish some simple non-isomorphic structures and the expressive power of K-hop message passing is bounded by 3-WL.
Continue looking at the provided examples. In example 1, if we use the shortest path distance kernel instead of the graph diffusion kernel, two nodes have the same number of neighbors in the 2nd hop, which means that we cannot distinguish two nodes this time. Similarly, in example 2, two nodes have the same number of neighbors in both 1st and 2nd hops with graph diffusion kernel. These results highlight that the choice of the kernel can affect the expressive power of K-hop message passing and none of them can distinguish both two examples with 2-hop message passing.
Recently, Frasca et al. [23] show that any subgraph-based GNNs with node-based selection policy can be implemented by 3-IGN [24,25] and thus their expressive power is bounded by 3-WL test.
Here, we show that the K-hop message passing GNNs can also be implemented by 3-IGN for both two kernels and thus: Theorem 2. The expressive power of a proper K-hop message passing GNN of any kernel is bounded by the 3-WL test.
We include the proof in Appendix F. Given all these observations, we may wonder if there is a way to further improve the expressive power of K-hop message passing?
3 KP-GNN: improving the power of K-hop message passing by peripheral subgraph In this section, we describe how to improve the expressive power of K-hop message passing by adding additional information to the message passing framework. Specifically, by adding the peripheral subgraph information, we can improve the expressive power of the K-hop message passing by a large margin.

Peripheral edge and peripheral subgraph
First, we define peripheral edge and peripheral subgraph.
Definition 5. The peripheral edge E(Q k,t v,G ) is defined as the set of edges that connect nodes within set Q k,t v,G . We further denote |E(Q k,t v,G )| as the number of peripheral edge in E(Q k,t v,G ). The peripheral subgraph G k,t v,G = (Q k,t v,G , E(Q k,t v,G )) is defined as the subgraph induced by Q k,t v,G from the whole graph G.
Briefly speaking, the peripheral edge E(Q k,t v,G ) record all the edges whose two ends are both from Q k,t v,G and the peripheral subgraph is a graph constituted by peripheral edges. It is easy to see that the peripheral subgraph G k,t v,G automatically contains all the information of peripheral edge E(Q k,t v,G ). Next, we show that the power of K-hop message passing can be improved by leveraging the information of peripheral edges and peripheral subgraphs. We again refer to the examples in Figure 1. Here we only consider the peripheral edge information. In example 1, we notice that at the 1st hop, there is an edge between node 3 and node 4 in the left graph. More specifically, In contrast, we have E(Q 1,t v2,G (2) ) = {} in the right graph, which means there is no edge between the 1st hop neighbors of v 2 . Therefore, by adding this information to the message passing, we can successfully distinguish these two nodes. Similarly, in example 2, there is one edge between the 1st hop neighbors of node v 2 but no such edge exists for node v 1 . By leveraging peripheral edge information, we can distinguish the two nodes as well. The above examples demonstrate the effectiveness of the peripheral edge and peripheral subgraph information.

K-hop peripheral-subgraph-enhanced graph neural network
In this section, we propose K-hop Peripheral-subgraph-enhanced Graph Neural Network (KP-GNN), which equips K-hop message passing GNNs with peripheral subgraph information for more powerful GNN design. Recall the K-hop message passing defined in Equation (3). The only difference between KP-GNN and original K-hop GNNs is that we revise the message function as follows: Briefly speaking, in the message step at the k-th hop, we not only aggregate information of the neighbors but also the peripheral subgraph at that hop. The implementation of KP-GNN can be very flexible as any graph encoding function can be used. To maximize the information the model can encode while keeping it simple, we implement the message function as: where MES l,normal k denotes the message function in the original GNN model, C k k is the kconfiguration, which encode both node configuration and the number of peripheral edge of all nodes in G k,t v,G up to k hops. It can be regarded as running another 1 layer KP-GNN on each peripheral subgraph. EMB is a learnable embedding function. With this implementation, any GNN model can be incorporated into and be enhanced by the KP-GNN framework by replacing MES l,normal k and UPD l k with the corresponding functions for each hop k. We leave the detailed implementation in Appendix I.

The expressive power of KP-GNN and comparison with existing methods
In this section, we theoretically characterize the expressive power of KP-GNN and compare it with the original K-hop message passing framework. The key insight is that, according to Equation (4), the message function at the k-th hop additionally encodes G k,t v,G compared to normal K-hop message passing. As we have already shown in the last section, K-hop GNNs are bounded by 3-WL and thus cannot distinguish any non-isomorphic distance regular graphs, as well as Distance Encoding [22]. Let C k j,G be the k -configuration of peripheral subgraph at j-th hop of nodes in distance regular graph G. Here we show that with the aid of peripheral subgraphs, KP-GNN is able to distinguish distance regular graphs: Proposition 2. For two non-isomorphic distance regular graphs G (1) = (V (1) , E (1) ) and G (2) = (V (2) , E (2) ) with the same diameter d and intersection array (b 0 , b 1 , ..., b d−1 ; c 1 , c 2 , ..., c d ). Given a proper 1-layer d-hop KP-GNN with message functions defined in Equation (5), it can distinguish G (1) and G (2)   We include the proof in Appendix G. Here we leverage an example in Figure 2 to briefly show why KP-GNN is able to distinguish distance regular graphs. Figure 2 displays two distance regular graphs with intersection array of (6, 3; 1, 2). The left one is Shrikhande graph and the right one is the 4×4 Rook's graph. Now, let's look at the 1-hop peripheral subgraph of the green node. In the Shrikhande graph, there are 6 peripheral edges marked with red. Further, 6 edges constitute a circle. In the 4×4 Rook's graph, there are still 6 peripheral edges. However, 6 edges constitute two circles with 3 edges in each circle, which is different from the Shrikhande graph. Then, any peripheral subgraph encoder that can distinguish these two graphs like node configuration enables the corresponding KP-GNN to distinguish the example. Proposition 2 shows that the KP-GNN is capable of distinguishing distance regular graphs, which further distinguishes KP-GNN from DE-1 [22] as it cannot distinguish any two connected distance regular graphs with the same intersection arrays according to Theorem 3.7 in [22]. However, it is currently unknown whether can KP-GNN with Equation 5 distinguish all distance regular graphs. We leave the detailed discussion in Appendix G.
Moreover, both the subgraph-based GNNs like NGNN [26], GNNAK [27], ESAN [28], and KP-GNN leverage the information in the subgraph to enhance the power of message passing. However, KP-GNN is intrinsically different from them. Firstly, in KP-GNN, the message passing is performed on the whole graph instead of the subgraphs. This means that for each node, there is only one representation to be learned. Instead, for subgraph-based GNNs, the message passing is performed separately for each subgraph and each node could have multiple representations depending on which subgraph it is in. Secondly, in subgraph-based GNNs, they consider the subgraph as a whole without distinguishing nodes at different hops. Instead, KP-GNN takes one step further by dividing the subgraph into two parts. The first part is the hierarchy of neighbors at each hop. The second part is the connection structure between nodes in each hop. This gives us a better point of view to design a more powerful learning method. From the Corollary 7 in [23], we know that all subgraph-based GNNs with node selection as subgraph policy is bounded by 3-WL, which means they cannot distinguish any distance regular graph and KP-GNN is better at it.

Time, space complexity, and limitation
In this section, we discuss the time and space complexity of K-hop message passing GNN and KP-GNN. Suppose a graph has n nodes and m edges. Then, the K-hop message passing and KP-GNN have both the space complexity of O(n) and the time complexity of O(n 2 ) for the shortest path distance kernel. Note that the complexity of graph diffusion is no less than the shortest path distance kernel. We can see that KP-GNN only requires the same space complexity as vanilla GNNs and much less time complexity than the subgraph-based GNNs, which are at least O(nm). However, K-hop message passing including KP-GNN still have intrinsic limitation. We leave a detailed discussion on the complexity and limitation of KP-GNN in Appendix H.

Related Work
Expressive power of GNN. Analyzing the expressive power of GNNs is a crucial problem as it can serve as a guide on how to improve GNNs. Xu et al. [7] and Morris et al. [18] first proved that the power of 1-hop message passing is bounded by the 1-WL test. In other words, 1-hop message passing cannot distinguish any non-isomorphic graphs that the 1-WL test fails to. In recent years, many efforts have been put into increasing the expressive power of 1-hop messaging passing. The first line of research tries to mimic the higher-order WL tests, like 1-2-3 GNN [18], PPGN [24], ring-GNN [29]. However, they require exponentially increasing space and time complexity w.r.t. node number and cannot be generalized to large-scale graphs. The second line of research tries to enhance the rooted subtree of 1-WL with additional features. Some works [30,31,32] add one-hot or random features into nodes. Although they achieve good results in some settings, they deteriorate the generalization ability as such features produce different representations for nodes even with the same local graph structure. Some works like Distance Encoding [22], SEAL [33], labeling trick [34] and GLASS [35] introduce node labeling based on either distance or distinguishing target node set. On the other hand, GraphSNN [36] introduces a hierarchy of local isomorphism and proposes structural coefficients as additional features to identify such local isomorphism. However, the function designed to approximate the structural coefficient cannot fully achieve its theoretical power. The third line of research resorts to subgraph representation. Specifically, ID-GNN [37] extracts ego-netwok for each node and label the root node with a different color. NGNN [26] encodes a rooted subgraph instead of a rooted subtree by subgraph pooling thus achieving superior expressive power on distinguishing regular graphs. GNN-AK [27] applies a similar idea as NGNN. The only difference lies in how to compute the node representation from the local subgraph. However, such methods need to run an inner GNN on every node of the graph thus introducing much more computation overhead. Meanwhile, the expressive power of subgraph GNNs are bounded by 3-WL [23].
K-hop message passing GNN. There are some existing works that instantiate the K-hop message passing framework. For example, MixHop [11] performs messing passing on each hop with graph diffusion kernel and concatenates the representation on each hop as the final representation. Khop [12] sequentially performs the message passing from hop K to hop 1 to compute the representation of the center node. However, it is not parallelizable due to its computational procedure. MAGNA [13] introduces an attention mechanism to K-hop message passing. GPR-GNN [14] use graph diffusion kernel to perform graph convolution on K-hop and aggregate them with learnable parameters. However, none of them give a formal definition of K-hop message passing and theoretically analyze its representation power and limitations.

Experiments
In this section, we conduct extensive experiments to evaluate the performance of KP-GNN. Specifically, we 1) empirically verify the expressive power of KP-GNN on 3 simulation datasets and demonstrate the benefits of KP-GNN compared to normal K-hop message passing GNNs; 2) demonstrate the effectiveness of KP-GNN on identifying various node properties, graph properties, and substructures with 3 simulation datasets; 3) show that the KP-GNN can achieve state-of-the-art performance on multiple real-world datasets; 4) analyze the running time of KP-GNN. The detail of each variant of KP-GNN is described in Appendix I and the detailed experimental setting is described in Appendix J. We implement the KP-GNN with PyTorch Geometric package [38]. Our code is available at https://github.com/JiaruiFeng/KP-GNN.
Datasets: To evaluate the expressive power of KP-GNN, we choose: 1) EXP dataset [39], which contains 600 pairs of non-isomorphic graphs (1-WL failed). The goal is to map these graphs to two different classes. 2) SR25 dataset [40], which contains 15 non-isomorphic strongly regular graphs with each graph of 25 nodes. The dataset is translated to a 15-way classification problem with the goal of mapping each graph into different classes. 3) CSL dataset [41], which contains 150 4-regular graphs (1-WL failed) divided into 10 isomorphism classes. The goal of the task is to classify them into corresponding isomorphism classes. To demonstrate the capacity of KP-GNN on node/graph properties and substructures, we pick 1) Graph property regression (connectedness, diameter, radius) and node property regression (single source shortest path, eccentricity, Laplacian feature) task on graph random dataset [42]. 2) Graph substructure counting (triangle, tailed triangle, star, and 4-cycle) tasks on random graph dataset [43]. To evaluate the performance of KP-GNN on real-world dataset, we select 1) MUTAG [44], D&D [45], PROTEINS [45], PTC-MR [46], and IMDB-B [47] from TU database. 2) QM9 [48,49] and ZINC [50] for molecular properties prediction. The detailed statistics of the datasets are described in Appendix K. Without further highlighting, all error bars in the result tables are the standard deviations of multiple runs (more details are in Appendix J).  Table 1.
Based on the results, we have the following conclusions: 1) K-hop GNNs with both two kernels have expressive power higher than the 1-WL test as it shows the perfect performance on the EXP dataset and performance better than a random guess on CSL dataset. 2) Increasing K can improve the expressive for both two kernels. 3) K-hop GNNs cannot distinguish any strong regular graphs in SR25 dataset, which is aligned with Theorem 2. 4) KP-GNN has much higher expressive power than normal K-hop GNNs by showing better performance on every dataset given the same K. Further, it achieves perfect results on the SR25 dataset even with K = 1, which demonstrates its ability on distinguishing distance regular graphs. Effectiveness on node/graph properties and substructure prediction: To evaluate the effectiveness of KP-GNN on node/graph properties and substructure prediction, we compare it with several existing models. For the baseline model, we use GIN [7], which has the same expressive power as 1-WL test. For more powerful baselines, we use GIN-AK+ [27], PNA [42] and PPGN [24]. For normal K-hop GNNs, we implement K-GIN+, and for KP-GNN, we implement KP-GIN+. The results are shown in Table 2. Baseline results are taken from [27] and [42]. We can see KP-GIN+ achieve SOTA on almost all tasks with a large margin to other baseline methods. Meanwhile, K-GIN+ also get great performance, especially on node/graph properties prediction. These results demonstrate the capability of KP-GNN to identify various properties and substructures.  Evaluation on TU datasets: For baseline models, we select: 1) graph kernel-based method: WL subtree kernel [51]; 2) vanilla GNN methods: GIN [7] and DGCNN [6]; 3) advanced GNN methods: GraphSNN [36] and GIN-AK+ [27]. For the proposed KP-GNN, we implement GCN [1], Graph-SAGE [3], and GIN [7] using the KP-GNN framework, denoted as KP-GCN, KP-GraphSAGE, and KP-GIN respectively. The results are shown in Table 3. For more fair and comprehensive comparison, we report the results from two different evaluation settings. The first setting follows Xu et al. [7] and the second setting follows Wijesinghe and Wang [36]. We denote the second setting with * in the table. We can see KP-GNN achieves state-of-the-art performance on all datasets under the second setting and still comparable performance to other baselines under the first setting. Evaluation on molecular prediction tasks: For QM9 dataset, we report baseline results of DTNN and MPNN from [49]. We further select Deep LRP [43], PPGN [24], and Nested 1-2-3-GNN [26] as baseline models. For ZINC dataset, we report results of MPNN [17] and PNA [42] from [50]. We further pick Graphormer [16], GSN [52], GIN-AK+ [27], and CIN [53]. The results of QM9 dataset are shown in Table 4. We can see KP-GNN achieves state-ofthe-art performance on most of the targets. The results of ZINC dataset is shown in Table 5. Although KP-GNN does not achieve the best result, it is still comparable to other methods.  [7] as the base model. We also include the KP-GIN+. All models use the same number of layers and hidden dimensions for a fair comparison. The results are shown in Table 6. We set K = 4 for all datasets. We can see the computational overhead is almost linear to K. This is reasonable as practical graphs are sparse and the number of K-hop neighbors is far less than n when using a small K.

Conclusion
In this paper, we theoretically characterize the power of K-hop message passing GNNs and propose the KP-GNN to improve the expressive power by leveraging the peripheral subgraph information at each hop. Theoretically, we prove that K-hop GNNs can distinguish almost all regular graphs but are bounded by the 3-WL test. KP-GNN is able to distinguish many distance regular graphs. Empirically, KP-GNN achieves competitive results across all simulation and real-world datasets.

Acknowledgement
This work is partially supported by NSF grant CBE-2225809 and NSF China (No. 62276003). In this section, we further discuss two different types of K-hop kernel and K-hop message passing.

A.1 More about K-hop kernel
First, recall the shortest path distance kernel and graph diffusion kernel defined in Definition 1 and 2. Given two definitions, the first thing we can conclude is that the K-hop neighbors of node v under two different kernels will be the same, namely N K,spd v,G = N K,gd v,G as both two kernels capture all nodes that can be reached from node v within the length of K. Second, we have N 1,spd v,G = Q 1,spd v,G = N 1,gd v,G = Q 1,gd v,G , which means the neighbor set is same for both the shortest path distance kernel and the graph diffusion kernel when K = 1. The third thing is that Q k,spd v,G will not always equal to Q k,gd v,G for some k. Since for shortest path distance kernel, one node will only appear in at most one of Q k,spd v,G for k = 1, 2, ..., K. Instead, nodes can appear in multiple Q k,gd v,G . This is the key reason why choice of the kernel can affect the expressive power of K-hop message passing.

A.2 More about K-hop message passing
Here, we use an example shown in Figure 3 to illustrate how K-hop message passing works and compare it with 1-hop message passing. The input graph is shown on the left top of the figure. Suppose we want to learn the representation of node v1 using 2 layer message passing GNNs. First, if we perform 1-hop message passing, it will encode a 2-height rooted subtree, which is shown on the right top of the figure. Note that each node is learned using the same set of parameters, which is indicated by filling each node with the same color (white in the figure). Now, we consider performing 2-hop message passing with the shortest path distance kernel. The rooted subtree of node v1 is shown in the middle of the figure. we can see that at each height, both 1st hop neighbors and 2nd hop neighbors are included. Furthermore, different sets of parameters are used for different hops, which is indicated by filling nodes in the different hops with different colors (blue for 1st hop and yellow for 2nd hop). Finally, at the bottom of the figure, we show the 2-hop message passing graph neural network with graph diffusion kernel. It is easy to see the rooted subtree is different from the one that uses the shortest path distance kernel, as nodes can appear in both 1st hop and 2nd hop of neighbors.

B Proof of injectiveness of Equation (3)
In this section, we formally prove that Equation (3) is an injective mapping of the neighbor representations at different hops. As here each layer l is doing exactly the same procedure, we only need to prove it for one iteration. Therefore we ignore the superscript and rewrite Equation (3) as: Next, we state the following proposition: Proposition 3. There exist injective functions MES k , UPD k , k = 1, 2, ..., K, and an injective multiset function COMBINE, such thatĥ v is an injective mapping of (k, Proof. The existence of injective message passing (MES k ,UPD k ) and multiset pooling (COMBINE) functions are well proved in [7]. So below we prove the injectiveness ofĥ v . First, we combine MSE k and UPD k together into φ k : Note that φ k is still injective as the composition of injective functions is injective. Next, we need to prove that h k v is an injective mapping of (k, To prove it, we rewrite the function φ k (·) into φ(k)(·), that is, φ is an injective function taking k as input and outputs a function φ k = φ(k). We let φ(k 1 )(x 1 ) and φ(k 2 )(x 2 ) output different values for k 1 = k 2 given any input x 1 , x 2 , e.g., always let the final output dimension be k. Then, we can rewrite h k v as where we have composed two injective functions φ(·) and φ(k)(·) into a single one ψ(·). Since given different k, φ(k)(·) always outputs distinct values for any input, and given fixed k, φ(k)(·) always outputs different values for different ({ {(h u , e uv )|u ∈ Q k,t v,G } }, h v ), the resulting ψ(·) always outputs different values for different (k, Finally, since COMBINE is an injective multiset function, we conclude that its outputĥ v is an injective mapping of (k,

C Proof of Theorem 1 and simulation result C.1 Proof of Theorem 1
Here we restate Theorem 1: Consider all pairs of n-sized r-regular graphs, let 3 ≤ r < (2log2n) 1/2 and be a fixed constant. With at most K = ( 1 2 + ) log 2n log (r−1) , there exists a 1 layer K-hop message passing GNN using the shortest path distance kernel that distinguishes almost all 1 − o(n −1/2 ) such pairs of graphs.
As we state in the main paper, 1 layer K-hop GNN is equivalent to inject node configuration for each node label. Therefore, it is sufficient to show that given node configuration A K,spd v,G for all v ∈ V , we can distinguish almost every pair of regular graphs. First, we introduce the following lemma. Lemma 1. For two graphs G (1) = (V (1) , E (1) ) and G (2) = (V (2) , E (2) ) that are randomly and independently sampled from n-sized r-regular graphs with 3 ≤ r < (2log2n) 1/2 . We pick two nodes v 1 and v 2 from two graphs respectively. Let K = ( 1 2 + ) log 2n log (r−1) where is a small constant, A K,spd v1,G (1) = A K,spd v2,G (2) with the probability at most o(n −3/2 ).
Proof. This Lemma can be obtained based on Theorem 6 in [54] with minor corrections. Here we state the proof.
We first introduce the configuration model [55] of n-sized r-regular graphs. Suppose we have n disjoint sets of items, W i , i ∈ {1, 2, ..., n}, where each set has r items and corresponds to one node in the configuration model. A configuration is a partition of all nr items into nr 2 pairs. Denote by Ω the set of configurations and turn it into a probability space with each configuration the same probability. Turns out among all configurations in Ω, given r < (2logn) 1/2 , there are about exp(− r 2 −1 4 ) or Ω(n −1/2 ) portion of them are simple r-regular graphs [55]. Then for these configurations, If there is a pair containing items W i and W j , then there is an edge between node i and j in the corresponding r-regular graph.
Let l 0 = ( 1 2 + ) log n log (r−1) . We first look at two nodes randomly selected from the configuration model and consider the following procedure to generate a graph. Let node i and node j be the selected nodes. In the first step, we select all the edges that directly connect to node i and node j. Then we have all nodes that are at a distance of 1 to i or j. In the second step, we select all the edges that connect to nodes at a distance of 1 to either node i or node j. Doing this iteratively for n − 1 steps and we end up with the union of components of i and j in a random configuration.
We call an edge is indispensable if it is the first edge that ensure a node k is at certain distance to {i, j}. Similarly, an edge is dispensable if 1) both two ends of the edge are connected to either i or j; 2) nodes in both two ends of the edge already have at least one edge. Note that edges with both two ends in the same node are dispensable. As the first k − 1 edges selected so far can connect to at most k + 1 nodes, the probability that the k-th edge selected is dispensable is at most: Therefore the probability that more than 2 of the first k o = n 1/6 edges are dispensable is at most: The probability that more than l 1 = n 1/8 of the first k 1 = n 6/13 edges are dispensable is at most The probability that more than l 2 = n 5/13 of the first k 2 = n 2/3 edges are dispensable is at most Now, let A be the event that at most 2 of the first k o , at most l 1 of the first k 1 , and at most l 2 of the first k 2 edges be dispensable. Given Equation (9)-(11), we know the probability of A is 1 − o(n −2 ). Therefore, it is sufficient to prove Lemma condition on A is o(n −3/2 ). Now, we consider another way of generating a graph with configuration model. Similar to the above, suppose we have selected all the edges connecting to at least one node with a distance less than k from {i, j} after the k-th step. At the k + 1-th step, we first select all the edges with one node at a distance of k from node i. Next, we select all the edges with both two ends at a distance of k from node j. It is easy to see that after these two procedures, the only edges left for completing the k + 1-th step are the edges that have one end at the distance of k from the node j and another end at the distance of k + 1 from the node j. Suppose there are t k edges in the nodes at distance k from node j that have not been generated so far and there are s k nodes that have not generate any edge yet. Then the final procedure of completing the k + 1-th step is to connect t k edges to s k nodes. This procedure goes on for every k to generate the final graph. Assuming in the statement of Lemma satisfies that 0 < < 1 8 . Then we have 2 + r(r − 1) l0 ≤ 2 + rn 1/2+ < n 2/3 Now let us assume that A holds. It is easily seen that then for k ≤ l 0 , we have: Now, after the first two procedures of k + 1-th step, we have all the nodes at the distance of k + 1 from node i, which means we already determined Q k+1,spd  (12) is at most the maximum of the probability that t k edges connect to l nodes from s k nodes. This probability is bounded by: where t k ≤ cs 5/8 k for some constant c and c o is also a constant. The proof of this can be found in Lemma 7 of [55]. Given Equation (13), the probability that A l,spd i,G = A l,spd j,G for l ≤ l 0 is at most where h = 1 2 logn log(r−1) + 3 . Since (r − 1) l0 ≥ n (1+ )/2 , the product above is o(n −2 ). Since there are at least Ω(n −1/2 ) of all the graphs generated by the configuration model that are simple r-regular graphs, there are at most o(n −2 /n −1/2 ) = o(n −3/2 ) of probability that A l0,spd i,G = A l0,spd j,G .
Next, for any pair of n-sized r-regular graphs G (1) and G (2) , we can combine these two graphs and generate a single regular graph with 2n nodes. Denote this combined graph as G c and G c has two disconnected components. It is easy to see that the above proof is still valid on G c . This means that: suppose we randomly pick a node v 1 from the first component and node v 2 from another component. Then, given 3 ≤ r < (2log2n) 1/2 and K = ( 1 2 + ) log 2n log (r−1) , we have A K,spd v1,Gc = A K,spd v2,Gc with probability of o(n −3/2 ). As node v 1 and v 2 are in two disconnected components G (1) and G (2) . Therefore, it is easy to see A K,spd v1,Gc = A K,spd v1,G (1) and A K,spd v2,Gc = A K,spd v1,G (2) , which completes the proof.
Theorem 1 is easy to prove with the aid of Lemma 1. Basically, we consider a node v 1 in graph G (1) and compare the A K,spd v1,G (1) with A K,spd v2,G (2) for all nodes v 2 ∈ V (2) . The probability that . Therefore, with an injective readout function, we can guarantee that 1 layer K-hop message passing GNN can generate different embedding for two graphs.

C.2 Simulation experiments to verify Theorem 1
In this section, we conduct simulation experiments to verify both Lemma 1 and Theorem 1. The results are shown in Figure 4. We randomly generate 100 n-sized 3 regular graphs with n range from 20 to 1280. Then, we apply a 1-layer untrained K-GIN model on these graphs (1 as node feature) with K range from 1 to 6. On the left side, we compare the final node representations for all nodes output by K-GIN, If the difference between two node representations ||h v − h u || 2 is less than machine accuracy, they are regarded as indistinguishable. The colors of the scatter plot indicate the portion of two nodes that are not distinguishable by K-GIN. The darker, the more indistinguishable node pairs. We can see that the result matches almost perfectly with Lemma 1, where K is larger than 1 2 log 2n log (r−1) , almost all nodes are distinguishable by K-GIN. On the right side, we compare the final graph representation output by K-GIN. We can see even with K = 2, almost all graphs are distinguishable. This is because as long as there exists one single node from one graph that has a different representation from all nodes in another graph, 1 layer K-hop message passing with an injective readout function can distinguish two graphs.

D General K-hop color refinement and discussion on existing K-hop message passing GNNs
In this section, we introduce a general K-hop color refinement algorithm and use this algorithm to characterize the expressive power of existing K-hop methods further.

D.1 General K-hop color refinement algorithm
It is well-known that 1-WL test updates the label of each node in the graph by color refinement algorithm, which iteratively aggregates the label of its neighbors. Here, we extend it and define a more general color refinement algorithm. First, we denote [n] = {0, 1, ..., n} and introduce refinement configuration. Definition 6. Given L and K, the refinement configuration C L,K = (C 0,K , C 1,K , ..., C L,K ), where C l,K = (C l,K 0 , C l,K 1 , ..., C l,K K ) and C l,K k ⊆ [l] for any l ∈ [L] and k ∈ [K].
Briefly speaking, refinement configuration defines how the color refinement algorithm aggregates information from K-hop neighbors at each iteration l given the maximum iteration of L and the maximum number of hop K. Given the refinement configuration C L,K , we define general color refinement algorithm CR(C L,K ): Equation (14) define the general color refinement algorithm. Then, given different refinement configurations, we can end up with different procedures for the algorithm. Specifically, we define the following refinement configurations: Definition 7. The 1-WL refinement configuration is defined as C L,K 1-WL = (C 0,K 1-WL , C 1,K 1-WL , ..., C L,K 1-WL ), where C l,K 1-WL,k = {l} for k = 0, 1, and C l,K 1-WL,k = ∅ for others. It is easy to see that CR(C L,K 1-WL ) is exactly the same as the color refinement algorithm in 1-WL test. Next, we can analyze the expressive power of the general color refinement algorithm given different refinement configurations. We say C L,K ) is at least equally powerful as CR(C L,K 2 ) in terms of expressive power. Then, we have the following properties for the general refinement algorithm. Property 1. C L+1,K C L,K .
These two properties are easy to validate, as given the injective HASH function, an algorithm with more information is always at least equally powerful as an algorithm with less information. Moreover, we have the following proposition.
3. At iteration l + 1, the condition in the proposition means color refinement algorithm with C l,K 2 can only aggregate results from earlier iteration than C l,K 1 at any hops. Meanwhile, as C l−1,K 1 C l−1,K 2 holds, as long as R l,1 v1,G = R l,1 v2,G , we have R t,i v1,G = R t,i v2,G holds for any t ∈ [l] and i = 1, 2 given the injectiveness of HASH function. This means that if R l+1,1 v1,G = R l+1,1 v2,G , then R l+1,2 v1,G = R l+1,2 v2,G . Therefore, C l,K 1 C l,K 2 also holds. this completes the proof.
Given two properties and Proposition 4, we have the following results.
Proof. Using the Property 1 and Property 2 of general color refinement algorithm, it is easy to prove that C L,K Theorem 3 provide a general comparison between different color refinement configurations. Based on Theorem 3, we can actually extend the Proposition 1 in the main paper as Corollary 1. Suppose K ≥ L, L layer K-hop message passing GNNs defined in Equation (3) with the shortest path distance kernel is at least equally powerful as L layer GINE+ [15]. L layer GINE+ is strictly more powerful than L layer 1-hop message passing GNNs.
The above Corollary is trivial to prove as corresponding models with injective message and update functions have at most the same expressive power as general color refinement algorithm with corresponding refinement configurations and permutation invariant readout function. However, one remaining question given the general color refinement algorithm is the comparison of the expressive power between K layer 1-hop GNNs and 1 layer K-hop GNNs. Here we show that: Proposition 5. Assume we use the shortest path distance kernel for K-hop message passing GNNs. There exists pair of graphs that can be distinguished by 1 layer K-hop message passing GNNs but not K layer 1-hop message passing GNNs and vice versa.
(") ($) [ , ] [ , ] [ , ] [ , ] [ , ] [ , ] [ , ] [ , ] [ , ] [ , ] To prove Proposition 5, we provide two examples. The first example is exactly example 2 in Figure 1. we know that a 1-hop GNN with 2 layers cannot distinguish two graphs as they are all regular graphs. Instead, a 1-layer 2-hop GNN is able to achieve that. From another direction, we show two graphs in Figure 5. We know that 1 layer 2-hop message passing GNN is equivalent to inject node configuration up to 2-hop into nodes. As we show in Figure 5, two graphs have the same node configuration set, which means an injective readout function will produce the same representation. Therefore, two graphs cannot be distinguished by 1 layer 2-hop message passing GNNs. Instead, it is easy to validate that these two graphs can be distinguished by 2 layer 1-hop message passing GNNs.
D.2 Discussion on existing K-hop models GINE+ [15]: GINE+ tries to increase the representation power of graph convolution by increasing the kernel size of convolution. However, in l layer of GINE+, it only aggregates information from the neighbor of hop 1, 2, ..., l, which means that after L layer of convolution, the GINE+ still has a receptive field of size L. As we discussed in the previous section, L layer K-hop message passing GNNs with the shortest path distance kernel and K ≥ L is at least equally powerful as L layer GINE+.
Graphormer [16]: Graphormer introduce a new way to apply transformer architecture [56] on graph data. In each layer of Graphormer, the shortest path distance is used as spatial encoding to adjust the attention score between each node pair. Although the Graphormer does not apply the K-hop message passing directly, the attention mechanism (each node can see all the nodes) with the shortest path distance feature implicitly encodes a rooted subtree similar to the K-hop message passing with the shortest path distance kernel. To see it clearly, suppose we have K-hop message passing with K = ∞ and graphs only have one connected component. It will aggregate all the nodes at each layer, which is similar to Graphormer. Meanwhile, the injective message and update function implicitly encode the shortest path distance to each node in aggregation. Then it is trivial to see that Graphormer is actually a special case of K-hop message passing with the shortest path distance kernel.
Spectral GNNs: spectral-based GNNs serve as an important type of graph neural network and gain lots of interest in recent years. Here we only consider one layer as spectral-based GNNs usually only use 1 layer. the general spectral GNNs can be written as: where φ and ϕ are typically multi-layer perceptrons (MLPs),L is normalized laplacian matrix, α k is weight for each spectral basis, and ρ is an element-wise function of matrix. In normal spectral GNNs, ρ is always an identity mapping function. We can see spectral GNNs have a close relationship to K-hop message passing with graph diffusion kernel asL k actually compute the Q k,gd v,G for each node by only keeping element in the matrix that is larger than 0. As K in Equation (15) can be greater than 1, it looks like spectral GNNs fit Proposition 1 as well. However, according to Proposition 4.3 in [21], all such spectral-based methods have expressive power no more than 1-WL test. This seems like a discrepancy. The reason lies in the ρ function in Equation (15). K-hop message passing with graph diffusion kernel can be regarded as using a non-linear ρ function shown in the following: Original Graph

Example 1 Example 2
(1) (2) This non-linear function is the key difference between the normal spectral GNNs and K-hop message passing and it endows normal spectral GNNs with extra expressive power than 1-WL test.
MixHop [11], GPR-GNN [14], and MAGNA [13]: All three methods extend the scope of 1-hop message passing by consider multiple graph diffusion step simultaneously. However, all these methods use normal spectral GNNs as the base encoder and thus they obey Proposition 4.3 in [21] instead of Proposition 1. It can be seen as a "weak" version of K-hop message passing with graph diffusion kernel.

E Comparison between K-hop message passing and Distance Encoding
In this section, we further discuss the connection and difference between K-hop message passing and Distance Encoding [22]. Here we assume that the kernel of K-hop message passing is the shortest path distance kernel and Distance Encoding with the shortest path distance as distance feature.
To simplify the discussion, suppose there are two graphs G (1) = (V (1) , E (1) ) and G (2) = (V (2) , E (2) ). We pick two nodes v 1 and v 2 from each graph respectively and learn the representation for these two nodes. First, let us consider what 1 layer K-hop message passing and DE-1 without message passing. As we stated in the main paper, 1 layer of K-hop message passing actually injects each node with the label of node configuration. Instead, DE-1 injects each node with the distance to the center node (v 1 and v 2 here). Then we can see there is a clear difference between the two methods even if they all implicitly or explicitly use the distance feature as shown in the upper part of Figure 6. Next, it is easy to see that applying L + 1 layer K-hop message passing is equivalent to applying L layer K-hop message passing on a graph with node configuration as the initial label. Applying L layer DE-1 is equivalent to applying L layer 1-hop message passing on a graph with the distance to the center node as the initial label. In the following, we show that the two methods cannot cover each other in terms of distinguishing different nodes: Proposition 6. For two non-isomorphic graphs G (1) = (V (1) , E (1) ) and G (2) = (V (2) , E (2) ), we pick two nodes v1 and v 2 from each graph respectively. Then there exist pairs of graphs that nodes v 1 and v 2 can be distinguished by K-hop message passing with the shortest path distance kernel but not DE-1, and vice versa.
To prove the Proposition 6, we provide two examples in the lower part of Figure 6. Example 1 in the figure is exactly the same pair of regular graphs in example 1 of Figure 1. As discussed before, K-hop message passing with the shortest path distance kernel cannot distinguish node v 1 and v 2 . However, after injecting the distance feature to the center node in two graphs and performing 2 layers of message passing, DE-1 is able to assign different representations for two nodes. In example 2, DE-1 cannot distinguish nodes v 1 and v 2 in the two graphs, even if they are not regular graphs. Instead, using K-hop message passing with only K = 2, the two nodes will get different representations. We omit the detailed procedure here as it is easy to validate. Using these two examples, we have shown that K-hop message passing and DE-1 are not equivalent to each other even if they all use the shortest path distance feature. The root reason is that although DE-1 uses the distance feature, it still aggregates information only from 1-hop neighbors in each iteration, while K-hop message passing directly aggregates information from all K-hop neighbors. That is, their ways of using distance information are different. However, we also notice that in example 2, if we label the graph with DE-1 on another pair of nodes, two nodes can be distinguished, which means DE-1 is able to distinguish these two graphs. However, to achieve that, DE-1 need to label the graph n times and run the message passing on all n labeled graphs. Instead, K-hop message passing only needs to run the message passing once, which is both space and time efficient.
Besides DE-1, Li et al. [22] also proposed the DEA-GNN which is at least no less powerful than DE-1. The DEA-GNN extends DE-1 by simultaneously aggregating all other nodes in the graph but the message is encoded with the distance to the center node. This can be seen as exactly performing K-hop message passing. In other words, DEA-GNN is the combination of K-hop message passing and DE-1. Therefore it is easy to see: Proposition 7. The DEA-GNN [22] is at least equally powerful as K-hop message passing with the shortest path distance kernel.

F Proof of Theorem 2
In this section, we prove Theorem 2. We first restate Theorem 2: The expressive power of a proper K-hop message passing GNN of any kernel is bounded by 3-WL test. Our proof is inspired by the recent results in SUN [23], which bound all subgraph-based GNN with the 3-WL test by proving that all such methods can be implemented by 3-IGN. Here we prove that K-hop message passing can also be implemented by 3-IGN. We will not discuss the detail of 3-IGN and all its operations. Instead, we directly follow all the definitions and notations and refer readers to Appendix B of [23] for more details.
K-hop neighbor extraction: To implement the K-hop message passing, we first implement the extraction of K-hop neighbors. The key insight is that we can use the l-th channel in X iij to store whether node j is the neighbor of node i at l-th hop, which is similar to the extraction of ego-network.
Here we suppose d ≥ K. Same as all node selection policies, we first lift the adjacency A to a three-way tensor Y ∈ R n 3 ×d using broadcasting operations: Now, X (0),1 iij store the 1-hop neighbors of node i. Next, l-th hop neighbor of node i is computed and stored in X ,l iij . To get neighbor of l-th hop for l = 2, 3, ..., K, we first copy it into d + 1 channels: The d + 1-th channel is used to compute high-order neighbors. Next, we extract all K hop neighbors by iteratively following steps K − 1 times and describe the generic l-th step. We first broadcast the current reachability pattern into X ijk , writing it into the l-th channel: Message broadcasting: This procedure is similar to the base encoder of DSS-GNN but here we only need to broadcast X iij . However, since we need to perform message passing for K times, we need to broadcast it K times: Now, we successfully implement both K-hop neighbor extraction and K-hop message passing layer. Note that other parts like the readout function can be easily implemented and we omit the detail. This means the expressive power of K-hop message passing with either graph diffusion kernel or shortest path distance kernel is bounded by 3-IGN. Based on the Theorem 2 in [57], we conclude the Theorem 2. Further, it is intuitive that all methods that use the node pair distance feature are also bounded by 3-WL as this feature can be computed by 3-IGN. We leave the formal proof in our future work.
G Proof and discussion of Proposition 2 Proposition 2 seems intuitive and easy to prove. However, it also unclear how powerful are KP-GNN. So here we still give a more detailed discussion on it. we first give the definition of distance regular graph. Definition 10. A distance regular graph is a regular graph such that for any two nodes v and u, the number of nodes with the distance of i from v and distance of j from u depends only on i, j and the distance between v and u.
Space complexity: For both K-hop message passing and KP-GNN, as we only need to maintain one representation for each node, the space complexity is O(n) like in vanilla 1-hop message passing.
Time complexity: First, we analyze the time complexity of K-hop message passing GNNs. For each node, suppose in the worst case we extract neighbors from all nodes from all hops, the number of neighbors we need to aggregate from all hops is n (all nodes in the graph). Then, n nodes need at most O(n 2 ) time complexity. Next, we analyze the time complexity of KP-GNN. The additional time complexity comes from counting the peripheral edges and k -configuration. Since the counting can be done in a preprocessing step and reused at each message passing iteration, it will be amortized to zero finally. So the practical time complexity is still O(n 2 ).

H.2 Discussion on the complexity
From the above analysis, we know that K-hop GNNs and KP-GNN only need O(n) space complexity, which is equal to vanilla message passing GNNs and much less than subgraph-based GNNs which require O(n 2 ) space (due to maintaining a different representation for each node when appearing in different subgraphs). Thus, KP-GNN has a much better space complexity than subgraph-based GNNs, PPGN [24] (also O(n 2 )) and 3-WL-GNNs (O(n 3 )).
The worst-case time complexity of K-hop GNNs and KP-GNN is much higher than that of normal GNNs due to aggregating information from more than 1-hop nodes in each iteration. However, we also note that the larger receptive field could reduce the number of message passing iterations because 1-layer of K-hop message passing can cover the receptive field of K-layer 1-hop message passing. Furthermore, K-hop GNN and KP-GNN have better time complexity O(n 2 ) than that of subgraph-based GNNs (which require O(nm) for doing 1-hop message passing O(m) in all n subgraphs). For sparse graphs, we can already save a factor of d avg = m/n complexity. For dense graphs, the worst-case time complexity of subgraph-based GNNs becomes O(n · n 2 ) = O(n 3 ), and our time complexity advantage becomes even more significant.

H.3 Limitations
We discuss the limitation of the proposed KP-GNN from two aspects.
Stability: Using K-hop instead of 1-hop can make the receptive field of a node increase with respect to K. For example, to compute the representation of a node with L layer K-hop, GNN, the node will get information from all LK-hop neighbors. The increased receptive field can hurt learning, as mentioned in GINE+ [15]. It is an intrinsic limitation that exists in all K-hop GNNs. GINE+ [15] proposed a new way to fix the receptive field as L by only considering L − i layer representation of neighbor in i hop during the aggregation. We also apply this approach and it helps mitigate the issue and shows great practical performance gain.
Time complexity: As we show above, we need O(n 2 ) time complexity for KP-GNN, which is much higher than O(m) of MPNN. However, this limitation exists for all subgraph-based methods like NGNN [26], GNN-AK [27], and ESAN [28] as they all require O(nm) time complexity [23]. This is the sacrifice for better expressive power.

I Implementation detail of KP-GNN
In this section, we discuss the implementation detail of KP-GNN.
Combine function: 1-hop message passing GNNs do not have COM BIN E l function. Here we introduce two different COM BIN E l functions. The first one is the attention [58] based combination mechanism, which automatically learns the importance of representation for each node at each hop. The second one uses the well-known geometric distribution [13]. The weight of hop i is computed based on θ i = α(1 − α) i , where α ∈ (0, 1]. The final representation is calculated by weighted summation of the representation of all the hops. In our implementation, the α is learnable and different for each feature channel and each hop. Peripheral subgraph information: In the current implementation, KP-GNN will compute two pieces of information. The first one is the peripheral edge set E(Q k,t v,G ). In our implementation, we compute the number of edges for each distinct edge type. The second one is node configuration and peripheral edge set for all nodes in the peripheral subgraph C k . this is equivalent to running 1 layer of KP-GNN on each peripheral subgraph. Specifically, for node configuration, we compute the node configuration for each node and sum them up. For the peripheral edge set, we compute the total number of edges across all hops (do not consider edge type here). Finally, these two pieces of information are combined as C k . All these steps are down in the preprocessing stage.
KP-GCN, KP-GIN, and KP-GraphSAGE: We implement KP-GCN, KP-GIN, and KP-GraphSAGE using the message and update function defined in GCN [1], GIN [7], and GraphSAGE [3] respectively. In each hop, independent parameter sets are used and the computation in each hop strictly follows the corresponding model. However, increasing the number of K will also increase the total number of parameters, which is not scalable to K. To avoid this issue, we design the K-hop message passing in the following way. Suppose the total hidden size of the model is H, then the hidden size of each hop is H/K. In this way, the model size is still on the same scale even with large K.
KP-GIN+: In a normal K-hop message passing framework, all K-hop neighbors will be aggregated for each node. It means that, after L layers, the receptive field of GNN is LK. This may cause the unstable of the training as unrelated information may be aggregated. To alleviate this issue, we adapted the idea from GINE+ [15]. Specifically, we implement KP-GIN+, which applies exactly the same architecture as GINE+ except here we add peripheral subgraph information. At layer l, GINE+ only aggregates information from neighbors within l-hop, which makes a L layer GINE+ still have a receptive field of L. Note that in KP-GIN+, we use a shared parameter set for each hop.
Path encoding: To further utilize the information of graph structure on each hop, we introduce the path encoding to KP-GNN. Specifically, we not only count whether two nodes are neighbors at hop k, but also count the number of paths with length k between two nodes. Such information can be obtained with no additional cost as the A k of a graph G with adjacency A is a path counter with length k. Then the information is added to the AGG l,normal k function as additional features.
Other implementation: For all GNNs, we apply the Jumping Knowledge method [59] to get the final node representation. The possible methods include sum, mean, concatenation, last, and attention. Batch normalization is used after each layer.
J Experiential setting details EXP dataset: For both K-GIN and KP-GIN, we use a hidden size of 48. The final node representation is output from the last layer and the pooling method is the summation. In the experiment, we use 10-fold cross-validation. For each fold, we use 8 folds for training, 1 fold for validation, and 1 fold for testing. We select the model with the best validation accuracy and report the mean results across all folds. The training epoch is set to 40. In this experiment, we do not use path encoding for fair comparison. The learning rate is set to 0.001 and we use ReduceLROnPlateau learning rate scheduler with a patience of 5 and a reduction factor of 0.5.
SR25 dataset: For both K-GIN and KP-GIN we use a hidden size of 64. The final node representation is output from the last layer and the pooling method is the summation. For SR25 dataset, we directly train the validate the model on the whole dataset and report the best performance across 200 epochs. For each fold, we use 8 folds for training, 1 fold for validation, and 1 fold for testing. We select the model with the best validation accuracy and report the mean results across all folds. The training epoch is set to 200. In this experiment, we do not use path encoding for a fair comparison. The learning rate is set to 0.001.
CSL dataset: For both K-GIN and KP-GIN we use a hidden size of 48. The final node representation is output from the last layer and the pooling method is the summation. In the experiment, we use 5-fold cross-validation.
Graph&Node property dataset: For graph and node property prediction tasks, we train models with independent 4 runs and report the mean results. For both K-GIN+ and KP-GIN+, the hidden size of models is set as 96. The final node representation is the concatenation of each layer. The pooling method is attention for graph property prediction tasks and sum for node property prediction tasks. The learning rate is 0.01 and we use ReduceLROnPlateau learning rate scheduler with a patience of 10 and a reduction factor of 0.5. We use the shortest path distance kernel. The maximum number of epochs for each run is 250. For both K-GIN+ and KP-GIN+, we search K from 3 to 6 with/without path encoding and report the best result.
Graph substructure counting dataset: For graph substructure counting tasks, we train models with independent 4 runs and report the mean results. For both K-GIN+ and KP-GIN+, the hidden size of models is set as 96. The final node representation is the concatenation of each layer. The pooling method is the summation. The learning rate is 0.01 and we use ReduceLROnPlateau learning rate scheduler with a patience of 10 and a reduction factor of 0.5. We use the shortest path distance kernel. The maximum number of epochs for each run is 250. For both K-GIN+ and KP-GIN+, we search K from 1 to 4 with/without path encoding and report the best result.
TU datasets: For TU datasets, we use 10-fold cross-validation. We report result for both setting in [7] and [36]. For the first setting, we use 9 folds for training and 1 fold for testing in each fold. After training, we average the test accuracy across all the folds. Then a single epoch with the best mean accuracy and the standard deviation is reported. For the second setting, we still use 9 folds for training and 1 fold for testing in each fold but we directly report the mean best test results. For KP-GNN, we implement GCN [1], GraphSAGE [3] and GIN [7] version. we search (1)the number of layer {2, 3, 4}, (2)the number of hop {2, 3, 4}, (3) the kernel of K-hop {spd, gd} , and (4) the COM BIN E function {attention, geometric}. The hidden size is 33 when K = 3 and 32 for the rest of the experiments. The final node representation is the last layer and the pooling method is the summation. The dropout rate is set as 0.5, the number of training epochs for each fold is 350 and the batch size is 32. The initial learning rate is set as 1e − 3 and decays with a factor of 0.5 after every 50 epochs.
QM9 dataset: For QM9 dataset, we implement KP-GIN+. The hidden size of the model is 128. The number of hops and the number of layers are both 8. The final node representation is the concatenation of each layer and the pooling method is attention. The dropout rate is 0. We use the shortest path distance kernel. The maximum number of the peripheral edge is 6 and the maximum number of the component is 3. We also use additional path encoding in each layer. The learning rate is 0.001 and we use ReduceLROnPlateau learning rate scheduler with a patience of 5 and a reduction factor of 0.7. If the learning rate is less than 0.000001, the training is stopped.
ZINC datraset: For ZINC dataset, we run the experiment 4 times independently and report the mean results. For each run, the maximum number of epochs is 500 and the batch size is 64. We implement the KP-GIN+ for the dataset. The hidden size is 104. The final node representation is the concatenation of each layer and the pooling method is the summation. We use the shortest path distance kernel. The number of hops and the number of layers are both 8. The initial learning rate is 0.001 and we use ReduceLROnPlateau learning rate scheduler with a patience of 10 and a reduction factor of 0.5. If the learning rate is less than 0.000001, the training is stopped.