How Powerful are K-hop Message Passing Graph Neural Networks
Authors: Jiarui Feng
Yixin Chen
Fuhai Li
Anindya Sarkar
Muhan Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Network
Expressive Power
Graph Isomorphism
Weisfeiler-Lehman

Abstract: 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.

How Powerful are K-hop Message Passing Graph Neural Networks
Jiarui Feng!:? Yixin Chen' Fuhai Li Anindya Sarkar' Muhan Zhang
(feng jiarui, fuhai. 1i, @wustl. edu, chen@cse wustl. edu, muhan@pku. edu. cn *Department of CSE, Washington University in St. Louis
Institute for Informatics, Washington University School of Medicine
"Institute for Artificial Intelligence, Peking University *Beijing Institute for General Artificial Intelligence
Abstract
The most popular design paradigm for Graph Neural Networks (GNNs) is I-hop message
information from 1-hop neighbors repeatedly. How- ever, the expressive power of 1-hop message passing is bounded by the Weisfeiler- Lehman (1-WL) test. Recently, researchers extended I-hop message passing to K- K-hop message passing by aggregating information from K- K-hop neighbors of nodes simultaneously. However, there is no work on analyzing the expressive power of K-hopp message passing. In this work, we theoretically characterize the expressive power of K-hopp message passing. Specifically, we first formally differ- entiate two different kernels of K-hop message passing which are often misused in previous works. We then characterize the expressive power of K 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 Khhop mes- sage 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 K-hop message passing by leveraging the peripheral subgraph information in each hop. We show that KP-GNN 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.
has shown superior performance on graph-related tasks 2 4 6 7 comparing to traditional graph embedding techniques [8] 9]. However, as the procedure of message passing similar to the I I-dimensional Weisfeiler-Lehman (I-WL) test [10), the expressive power of message passing GNNs is also bounded by the 1-WL test [T] Namely, GNNs cannot distinguish two non-isomorphic graph structures if the 1-WL test fails.
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 K-hop message passing [12 13
15. [6]. K-hop message passing is type of message passing where the node representation 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
14
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

characterizing the expressive power of GNNs with K hop message passing, e.g,, whether it can improve the I-hop message passing or not and to what extent it can.
In this work, we theoretically characterize the expressive power of Khhop message passing GNNs. Specifically, 1) we formally distinguish two different kernels of the K'hhop 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, which is used GPR-GNN [15] and MixHop [12]. The second one is based on the shortest path distance of k, which is used in GINE+ [6] and Graphormer [17. Further, we show that different kernels of K K-hop neighbors will result in different expressive power of K hop message passing. 2) We show that K K-hop message passing is strictly more powerful than 1-hop message passing and can distinguish almost all regular graphs. 3) However, still failed in distinguishing some simple regular graphs, no matter which kernel is used, and its expressive power bounded by W-. This motivates us to improve K K-hop message passing further.
Here, we introduce KP-GNN, new GNN framework with K-hop message passing, which signif- icantly improves the expressive power of standard K 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 learn more expressive local structural features around the node. We further show that KP-GNN can 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-hopp message-passilng passing GNNs with only slight modification. Second, only adds little computational complexity to standard K K-hop message passing. We demonstrate the effectiveness of the KP-GNN framework through extensive experiments on both simulation and real-world datasets.
K K-hop message passing and its expressive power
2.1 Notations
Denote a graph as G = (V, F), where V= 21.2..... is the node set and E C V x is the edge set. Meanwhile, denote A E [0, | as the adjacency matrix of graph G. Denote I, as the feature vector of node v and denote eue as the feature vector of the edge from u to V. Finally, we denote Q the set of 1-hop neighbors of node u in graph G and Nº. NN U (v). Note that when we say K- K-hop neighbors of node we mean all the neighbors that have distance from node less than or equal to K. In contrast, k-th hop neighbors mean the neighbors with exactly distance from node v. The definition of distance will be discussed in section 2.3
2.2 1-hop message passing framework
Currently, most existing GNNs are designed based on 1-hop message passing framework (18). Denote h1 as the output representation of node v at layer and h = Z.. Briefly, given a graph G and a 1-hop message passing GNN, at layer I of the GNN, hi, computed by 14-1 and Q u E Q1 L1
m MES' (E (((ht(tt cuv) E Qt,,c B),, ht = UPD' (m', k1-1),
(1)
where m., is the message to node e at layer 1, MES' and UPD' are message and update functions layer respectively. After L layers of message passing, h is used as the final representation of node v. Such a representation can be used conduct node-level tasks like node classification and node regression. To get the graph representation, a readout function is used:
hG READOUT (hg E VVD;
where READOUT is the readout function for computing the final graph representation. Then hGg can be used to conduct graph-level tasks like graph classification and graph regression.
2.3 K Khoop message passing framework
The --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 independent message

---

and update functions 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 K-hopp neighbors, which are interchanged and misused in previous research.
The first kernel of K Khhop neighbors is shortest path distance (spd) kernel. Namely, the k-th hop neighbors of node in graph G is the set of nodes with the shortest path distance of k from v.
Definition 1. For a node e in graph G, the K K-hop neighbors Ne. of v based on shortest path distance kernel the set of nodes that have the shortest path distance from node u less than or equal to K. We further denote at as the set of nodes in G that are exactly the k-th hop neighbors (with shortest path distance of exactly k) and N Aaaand Qu.ard =
is the node itself.
e.G
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- K-hop neighbors N of based on graph diffusion kernel is the set of nodes that can diffuse information to node u within the number of random walk diffusion steps K and the diffusion kernel A (adjacency matrix). We further denote Quac as the set of nodes in G that are exactly the k-th hop neighbors (nodes that can diffuse information to node u with & diffusion steps) and No.a = - = = is the node itself.
Note that a node can be a k-th hop neighbor of e for multiple & 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:
m l
MES k. (hhht) ,uvv)lu E (% h h = COMBINE'((1))) 1, 1,2.,.,KK KB)
UPD L. ,,1-)),,
(3)
where t E {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 Cav as nodes are not directly connected. But we leave it here since we can use other types of features replace it like path encoding. We further discuss it in Appendix I. Compared to the 1-hop message passing framework described in Equation (I). the COMBINE function is introduced to combine the representations of node at different hops. It is easy to that L layer 1-hop message passing 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 Khoop message passing can injectively encode the neighbor representations at different hops into hL in Appendix B.
2.4 Expressive power of K-hop message passing framework
In this section, we theoretically analyze the expressive power of K K-hop message passing. We assume there is 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 nodes/graphs are more easily be discriminated. It has been proved that the expressive power of 1 -hoop message passing is bounded by the 1-WL test on discriminating non-isomorphic graphs IT. In this section, We show that the K K-hop message passing is strictly more powerful than the I-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 K-hop message passing GNN is 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 K-hop message passing GNNs are proper. Next, we introduce node configuration:
Definition 4. The node configuration of node in graph G within K hops under kernel is list A K.t 1.2 2st
itt where a'j 12'; is the number of i-th hop neighbors of node v.
(a,
3

---

Example
Example 2
P1
6
Regular graphs input.
6
3
(83
G
G
1st hop
2
3
Graph diffusion
2nd hop
3
6
1st hop
3
Shortest path distance
2nd hop
5
6
6
Figure I: Here are two pairs of non-isomorphic regular graphs. With 2-hop message passing, example can be distinguished by the graph diffusion kernel, and example 2 can be distinguished by the shortest path distance kemnl.. However, both two examples become indistinguishable if we switch the kernel. Finally, both two examples can be distinguished by adding peripheral subgraph information.
When we say two node configurations K Gr and A K,t G2a 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 K-hop message passing GNN is strictly more powerful than 1-hop message passing GNNs when K > 1.
To why this is true, we first discuss how node configuration relates 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 the same node 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 01 and U2 are d,,, g0) and d d' G(a) where dy,G is the node degree of After T. layers, GNNs only get the node degree information of each node within I. hops of node v. Then, it is straightforward to see why these GNNs cannot distinguish any n-sized r-regular graph, each node in the regular graph has the same degree.
Next, when K > 1, the K K-hop message passing is at least equally powerful as I-hop message passing since node configuration up to K hop includes all the information the I hop has. To see why it is more powerful, we use two examples to illustrate The first example is shown the left part of Figure I Suppose here V1 and node 22 in the two graphs. We know that the 1-hop GNNs produce the same representation for two nodes they are both nodes in 6-sized 3-regular graphs. However, it is easy to see that 01 and U2 have different local structures and should have different representations. Instead, we use easily distinguish
graph diffusion kernel and want learn the representation of node
the 2-hop message passing with the graph diffusion kernel, checking the 2nd hop neighbors of the node, as node i1 has four 2nd hop neighbors but node 12 only has two 2nd hop neighbors. The second example is shown in the right part of Figure [ Two graphs in the example are still regular graphs. Suppose here we use shortest path distance kernel, node 01 and 02 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 Khhop message passing with K > can have better expressive power than expressive power of K K-hop message passing on regular graphs, we show the following result:
nodes by
1. To further study the
Theorem 1. Consider all pairs of n--ized r-regular graphs, let 3 < r < (2log2n)2/2 and e be log 2n. fixed constant. With at most K = =(} + +) log (1-1),, there exists a I layer K K-hop message passing GNN using the shortest path distance kernel that distinguishes almost all graphs.
(1/2) such pairs of
We include the proof and simulation results in Appendix C. Theorem T shows that even with layer and modest K, K -hop GNNs powerful enough to distinguish almost all regular graphs.

---

Finally, we characterize the existing K Kop methods with the proposed K Khhop message passing framework. Specifically, we show that 1) the expressive power of K layer GINE [T6] bounded by K layer K-hop message passing with the shortest path distance kernel. 2) The expressive power of the Graphormer [17] is equal to K-hop GNNs with the shortest path distance kernel and infinity K. 3) For spectral GNNs and existing K K-hop GNNs with the graph diffusion kernel like MixHop [12] and MAGNA [14), we find they actually use a weak version of K Khoop than the definition of us. Specifically, it is shown that the expressive power of spectral GNNs is also bounded by I-WL test [21] which contradicts our result as graph diffusion can be viewed as a special case of spectral GNN. However, we show that our definition of K Khhop 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 similar to K-hop GNNs with the shortest path distance kernel. However, we find the expressive power of the two frameworks differs from each other. We leave the detailed discussion in Appendix E.
2.5 Limitation of Khhop message passing framework
Although we show that K- K-hop GNNs with K > are better at distinguishing non-isomorphic structures than I-hop GNNs, there 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 K-hop message passing, still cannot distinguish some simple non-isomorphic structures and the expressive power of K K-hop message passing is bounded by 3-WI.
Continue looking the provided examples Figure I 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 using graph diffusion kernel. These results highlight that the choice of the kernel can affect the expressive power of K Khhop message passing, and none of them can distinguish both two examples with 2-hop message passing.
Recently, Frasca et 23 show that any subgraph-bass 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- Khhopp message passing GNNs can also be implemented by 3-IGN for both two kernels and thus:
Theorem 2. The expressive power of proper K 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 way to further improve the expressive power of K K-hop message passing?
3 KP-GNN: improving the power of K-hop message passing by peripheral subgraph
In this section, we describe how improve the expressive power of K-hop message passing by adding additional information to the message passing framework. Specifically, by adding peripheral subgraph information, we can improve the expressive power of the K K-hop message passing by large margin.
3.1 Peripheral edge and peripheral subgraph
First, we define peripheral edge and peripheral subgraph.
Definition 5. The peripheral edge F(QQttt)) defined as the set of edges that connect nodes within set Qut We further denote [E("":t) k,t as the number of peripheral edge in E(Q".t) The peripheral subgraph Glil ! E(Q).d)) is defined the subgraph induced by Q from the whole graph G.
5

---

Briefly speaking, the peripheral edge E(QU.G) record all the edges whose two ends are both from Quo and the peripheral subgraph is graph constituted by peripheral edges. It is easy to see that the peripheral subgraph G automatically contains all the information of peripheral edge E(Q",E) Next, we show that the power of K K-hop message passing can be improved by leveraging the information of peripheral edges and peripheral subgraphs. We again refer the examples in Figure T 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, = {(3, 4) In contrast, we have E(Q C2)) = O in the right graph, which means there no edge between the 1st hop neighbors of v2. Therefore, we can successfully distinguish these two nodes by adding this information to the message passing. Similarly, in example 2, there is one edge between the 1st hop neighbors of node U2, but no such edge exists for node U1 By leveraging peripheral edge information, we can also distinguish the two nodes. The above examples demonstrate the effectiveness of the peripheral edge and peripheral subgraph information.
E(Q", .a.) ",,
on
3.2 K Khhop peripherallsubgrapheennne
graph neural network
In this section, we propose K-hop Peripheral-subar weabbrapp--nhhaneee Graph Neural Network (KP-GNN), which equips K Kohop 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:
k.k m
MES (((() Bu E Qu Go
Briefly speaking, in the message step 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:
k MES, MES (H ewv) u E Q + f(C):t) f( EMB(E(QQ())CE))
(5)
where MES denotes the message function in the original GNN model, CK is the k'- configuration, which encode both node configuration and the number of the peripheral edge of all nodes in G.k. up to k' hops. can be regarded as running another layer KP-GNN and readout function on each peripheral subgraph. EMB a learnable embedding function. With this implemen- tation, any base GNN model can be incorporated into and be enhanced by the KP-GNN framework by replacing MES normal and UPD with the corresponding functions for each hop k. We leave the detailed implementation in Appendix I.
3.3 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 Equation 4
the message function at the k-th hop additionally encodes GoG compared to normal K Khhop message passing. As we have already shown in the last section, K KC-hop GNNs are bounded by 3-WL and thus cannot distinguish any non-isomorphic distance regular graphs, as well as Distance Encoding [22]. 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 able to distinguish distance regular graphs:
Let O be the k' k'-configurate
Proposition For two non-isomorphic distance regular graphs ())) (V(1),F(() and G( (V E(2) with the same diameter d and intersection array (bo. by.... ba- 1: C₁ C2 ..., Ca)- Given proper 1 I-layer d-hop KP-GNN with message functions defined in Equation (5), it can distinguish (()) and G()) if CK 5,gos * CK 5,003 for some O <j S d.

---

(6,3:1,2) distance regular graph
Shrikhande Graph
4x4 Rook's Graph
hop peripheral subgraph
Figure 2: An example of two non-isomorphic distance regular graph with intersection array (6, 1, 1)
We include the proof in Appendix G. Here we leverage example in Figure 2 to briefly show why KP-GNN is able to distinguish distance regular graphs. Figure F displays two distance regular graphs with intersection array of (6, 3: 1, 2). The left one is Shrikhande graph and the right one is 4x4 Rook's graph. Now, let's look at the 1 1-hop peripheral subgraph of the green node. In the Shrikhande graph, there 6 peripheral edges marked with red. Further, 6 edges constitute a circle. In the 4 Rook's graph, there are still 6 peripheral edges. However, 6 edges constitute two circles with edges in each cirele, 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 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 Theorem 3.7 in [2] However, it is currently unknown whether can KP-GNN with Equation 5 regular graphs. We leave the detailed discussion Appendix G.
distinguish all distance
Moreover, both the subgraph-based GNNs like NGNN 26 GNN-AK 277 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 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 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 each hop. This gives us better point of view design 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.
3.4 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 graph has nodes and m edges. Then, the K-hop message passing and KP-GNN have both the space complexity of (nn) and the time complexity of O(n²) 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 (nm) However, K- K-hop message passing including KP-GNN still have intrinsic limitation. We leave detailed discussion on the complexity and limitation of KP-GNN in Appendix H.
7

---

4 Related Work
Expressive power of GNN. Analyzing the expressive power of GNNs is crucial problem as it can serve as a guide on how to improve GNNs. Xu et al. 7 and Morris et al. []] first proved that the power of 1-hop message passing is bounded by the I-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 M. PPGN [24]. ring-GNN [9]]. 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 B1 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 (3), labeling trick (34) and GLASS 35 introduce node labeling based on either distance distinguishing target node set. On the other hand, GraphSNN (36] introduces 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 labels the root node with a different color. NGNN (26) encodes a rooted subgraph instead of 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-WI. 23].
K- K-hop message passing GNN. There are some existing works that instantiate the K K-hop message passing framework. For example, MixHop 12] performs message passing on each hop with graph diffusion kernel and concatenates the representation on each hop as the final representation. K- hop [33 sequentially performs the message passing from hop K to hop I to compute the representation of the center node. However, it is not parallelizable due to its computational procedure. MAGNA [14] introduces an attention mechanism to K K-hop message passing. GPR-GNN [15 use graph diffusion kernel to perform graph convolution on K K-hop and aggregate them with learnable parameters. However, none of them give a formal definition of K K-hop message passing and theoretically analyze its representation power and limitations.
5 Experiments
In this section, we conduct extensive experiments to evaluate the performance of KP-GNN. Specif- ically, 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 hhp message passing GNNs; 2) demon- strate the effectiveness of KP-GNN on identifying various node properties, graph properties, and substructures with simulation datasets; 3) show that the KP-GNN can achieve sfate-of-the--. performance on multiple real-world datasets; 4) analyze the running time of KP-GNN. The detail of each variant of KP-GNN described in Appendix I and the detailed experimental setting described in Appendix J. We implement the KP-GNN with PyTorch Geometric package 38 available at https:t/////
Our code is
com/ wwwruiaarraeeeee Fenuuiiienn//eeee Hiapg/KPGNNN
Datasets: To evaluate the expressive power of KP-GNN, we choose: 1) EXP dataset (31, which contains 600 pairs of iimmooooep graphs (I-WL failed). The goal is to map these graphs two different classes. 2) SR25 dataset [39]. which contains 15 non-isomorphic strongly regular graphs (3- WL failed) with each graph of 25 nodes. The dataset translated to 15-way classification problem with the goal of mapping each graph into different classes. 3) CSL dataset [40]. 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 counting 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 random graph dataset [4]] 2) Graph substructure counting (triangle, tailed triangle, star, and 4-cycle) tasks random graph dataset [2). To evaluate the performance of KP-GNN on
8

---

PROTEINS 44, PTC-MR [5]. and 49 for molecular properties prediction. The detailed statistics of the datasets are described in Appendix L. Without further highlighting, all error bars in the result tables are the standard deviations of multiple runs.
real-world datasets. we select 1) MUTAG 43
D&D
44
IMDB-B [46] from TU database. 2) QM9 47 and ZINC
Table 1: Empirical evaluation of the expressive power.
Empirical evaluation of the expressive power: For empirical evaluation of the ex- pressive power, we conduct the ablation study on hop K for both normal K Khhop GNNs and KP-GNN, For K K-hop GNNs, we implement K-GIN which uses GIN 7 as the base encoder. For KP-GNN, we imple- ment KP-GIN. The results are shown in Ta- ble 1 Based on the results, we have the following conclusions: 1) K K-hop GNNs with both two kernels have expressive power higher than the 1-WL test as shows the per- fect performance on the EXP dataset and performance better than random guess on the CSL dataset. 2) Increasing K can improve the expressive for both two kernels. 3) K K-hopp GNNs cannot distinguish any strong regular graphs in SR25 dataset, which is aligned with Theorem 2 4) KP-GNI has much higher expressive power than normal K K-hop GNNs by showing better performance on every dataset given the same K. Further, it achieves perfect results the SR25 dataset even with K which demonstrates its ability on distinguishing distance regular graphs.
EXP (ACC)
SR (ACC)
CSL (ACC)
Method
SPD
GD
SPD
GD
SPD
GD
K=1
6.67
6.67
12
12
K=2
50
50
6.67
6.67
32
22.7
K-GIN
K=3
100
66.9
6.67
6.67
62
42
Km4
100
100
6.67
6.67
92.7
62.7
K=1
50
100
100
22
22
K=2
52.7
52.7
KP-GIN
K=3
100
100
90
90
K=4
100
100
100
100
100
100
Table 2: Simulation dataset result. The top two are highlighted by First, Second.
Node Propertics (log (MSE)
Graph Properties (log (MSE))
Counting Substructures (MAE)
Method
SSSP
Ecc.
Lap.
Connect.
Diameter
Radius
Tri.
Tailed Tri.
Star
4-Cycle
GIN
-2.0000
-1.9000
-1.6000
-1.9239
-3.3079
-475844
0.3569
0.2373
0.0224
0.2185
PNA
-2,8900
-2,8900
-3.7700
-1,9395
3.4382
-494470
0.3532
0.2648
0.1278
0.2430
PPGN
-1,9804
-3.6177
-5.8878
0.0089
0.0096
0.0148
0.0090
GIN-AK+
-2.7513
-3.9887
-5.1846
0.0123
0.0112
0.0150
0.0126
K-GIN+
-2.7919
-2.5938
-463660
-2,1782
-3,9695
-5.3488
0.2593
0.1930
0.0165
0.2079
KP-GIN+
-2.7969
-2.6169
-4.7687
-4,4322
-3.9361
-5.3345
0.0060
0.0073
0.0151
0.0395
Effectiveness on node/graph properties and substructure prediction: To evaluate the effectiveness of KP-GNN 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 the I-WL test. For more powerful baselines, we use GIN-AK+ (27], PNA [4], and PPGN [24]. For normal K K-hop GNNs, we implement K-GIN+, and for KP-GNN, we implement KP-GIN+ The results are shown in Table 2 Baseline results taken from 27 and 4... We can KP-GIN+ achieve SOTA on majority of tasks. Meanwhile, K-GIN+ also gets great performance on node/graph properties prediction. These results demonstrate the capability of KP-GNN identify various properties and substructures. We leave the detailed results on counting substructures in Appendix K
Table 3: TU dataset evaluation result.
Method
MUTAG
D&D
PTC-MR
PROTEINS
IMDB-B
WL
90.4+5..7
79.4+0.3
59.9
75.0+3.1
73.8+3.9
GIN
89.4+5.66
64.647.0
75.942.8
75.1
DGCNN
85.8+117
79.3 +0.9
58.5
75.5+009
70.0
GraphSNN
91.24112.5
82.46:12.7
66.96.13.5
76.51
76.9313.3
GIN-AK+
91.30=7.0
68.20115.6
77.1015.7
75.60
KP-GCN
91.7+6.0
79.0+4.77
67.1+6.3
75.8+
75.9+33.8
KP-GraphSAGE
91.716.5
78.142.66
66,514.0
76.5
76.412277
KP-GIN
92.2-1.55
79.413.8
66,81168
75.8:14.6
76.6:14.2
GIN-AK+*
95.0+-6.1
OOM
74.145.99
78.9+5.44
77.3++3.1
GraphSNN
94.70+11.9
83,93+2.
70.58+3..1
78.42+227
78.51+2.8
KP-GCN*
96.1+44.6
83.2+2.2
77.1+4.1
80.3+4.2
79.6+2.5
KP-GrappSAGE"
96.1114.6
83.6124
76,244.5
80.414.3
80,3124
KP-GIN'
95.6-14.4
83.542.22
76,2-1455
79.5
80.7-2.

---

Table 4: QM9 results. The top two are highlighted by First, Second.
Target
DTNN
MPNN
Deep LRP
PPGN
N-1-2-3-GNN
KP-GIN+
KP-GIN'
0.244
0.358
0.364
0.231
0,433
0.367
0.358
0.95
0.89
0.298
0.382
0.265
0.242
0.233
EHOMO
0.00388
0.00541
0.00254
0.00276
0.00279
0.00247
0.00240
ELUMO
0.00512
0.00623
0.00277
0.00287
0.00276
0.00238
0.00236
A
0.0112
0.0066
0.00353
0,00406
0.00390
0.00345
0.00333
(R²)
17.0
28.5
19.3
16.7
20.1
16.49
16.51
ZPVE
0.00172
0.00216
0.00055
0.00064
0.00015
0.00018
0.00017
Uo
2.43
2.05
0.413
0.234
0.205
0.0728
0.0682
2.43
2.00
0.413
0.234
0.200
0.0553
0.0696
H 2.43
2.02
0.413
0.229
0.249
0.0575
0.0641
G
2,43
2.02
0.413
0.238
0.253
0.0526
0.0484
C.
0.27
0.42
0.129
0.184
0.0811
0.0973
0.0869
Evaluation on TU datasets: For baseline models, we select: 1) graph kernel-based method: WL
subtree kernel [50]; 2) vanilla GNN methods: GIN [ and DGCNN [ 3) advanced GNN meth-
ods: GraphSNN (36] and GIN-AK+ (27]. For the proposed KP-GNN, we implement GCN (Л. GraphSAGE 1 and GIN 7 using the KP-GNN framework, denoted KP-GCN, KP-GraphSAGE, and KP-GIN respectively. The results are shown Table For a more fair and comprehensive comparison, report the results from two different evaluation settings. The first setting follows Xu et al. 7 and the second setting follows Wijesinghe and Wang [6]. We denote the second setting with in the table. We can KP-GNN achieves SOTA performance most of datasets under the second setting and still comparable performance to other baselines under the first setting.
Table 5: 7INC result.
Evaluation on molecular prediction tasks: For QM9 dataset, we report baseline results of DTNN and MPNN from [88). We further select Deep LRP 42 PPGN 224,
Method
# param.
test MAE
MPNN
480805
0.145:10.007
and Nested 1-2-3-GNN (26 as baseline models. For
PNA
387155
0.142:10.010
the ZINC dataset, we report results of MPNN [8] and
Graphormer
489321
0.022:00.006
PNA from (17). We further pick Graphormer [17],
GSN
-500000
0.0011
GSN 111, GIN-AK+ 27), and CIN (52). For KP-GNN, we choose KP-GIN+ and KP-GIN' The results of the QM9 dataset are shown in Table We can KP-
GIN-AK+
0.080:10.001
CIN
0.006
GNN achieves SOTA performance on most of the targets. The results of the ZINC dataset shown in Table 5 Although KP-GNN does not achieve the best result, it still comparable to other methods.
KP-GIN+
499099 488649
0.111110.006
KP-GIN'
0.0037
Running time comparison: In this section, compare the running time of KP-GNN 1-hop message passing GNN and K-hop message pass- ing GNN. We use GIN 7 as the base model. We also include the KP-GIN+. All models use the same number of layers and hidden dimensions for fair comparison. The results shown in Ta- ble We set = 4 for all datasets. We can see the computational overhead is almost linear to K. This is reasonable practical graphs sparse and the number of K-hopp neighbors is far less than n when using a small K.
Table 6: Running time (s/epoch).
Method
D&D
ZINC
Graph property
GIN
1.10
3.59
1.02
K-GIN
3.94
6.44
1.67
KP-GIN
4.19
7.38
1.94
KP-GIN+
4.28
6.74
1.93
Conclusion
In this paper, 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 prove that K K-hop GNNs can distinguish almost all regular graphs but 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.
each hop. Theoretically,
7 Acknowledgement
This work is partially supported by NSF grant CBE-2225809 and NSF China (No. 62276003).
10

---

References
[1] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017.
[2] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pages 2224- 2232, 2015.
[3] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1025-1035, 2017.
[4] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. /tRLittts:///peeeeiiee..
JXMpkcc
[5] Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv: / 1.05493, 2015.
[6] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to- deep learning architecture for graph classification. In AAAI, pages 4438 4445, 2018.
[7] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019, URL https //openreview. nww/tfrumm wewerrummiddyyGeeei55.
[8] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864. ACM, 2016.
[9] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pages 701-710. ACM, 2014.
[10] Boris Weisfeiler and AA Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Vanchno--echnnicheskayy Informatsia, 2(9):12-16, 1968.
[11] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 4602-4609, 2019.
[12] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pages 21-29. PMLR, 2019.
[13] Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks. Neural Networks, 130:195 195-205, 2020.
[14] Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Multi-hop attention graph neural networks. In International Joint Conference Artificial Intelligence, 2021.
[15] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021. URL htRL:hhts::////t/ htttps::/openrrrieer http://ppnrrrrieeeeeeeeeffrrrrrr net:/forummiddmn6]77LL..
[16] Rémy Brossard, Oriel Frigo, and David Dehaene. Graph convolutions that can finally model local structure, arXiv preprint arXiv:2011. 2020.
[17] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? In A. Beygelz- imer, Y. Dauphin, P. Liang, and Wortman Vaughan, editors, Advances Neural Information Processing Systems, 2021. https:// http://wwww.......oeo.ooooooooaa

---

[18] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals. and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1263-1272. JMLR. org, 2017.
[19] George V. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2.303-314, 1989.
[20] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in Neural Information Processing Systems, pages 3391-3401, 2017.
[21] Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. ICML, 2022.
[22] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. In Advances in Neural Information Processing Systems, volume 33, pages 4465 4478, 2020.
[23] Fabrizio Frasca, Beatrice Bevilacqua, Michael M Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. In Advances in Neural Information Processing Systems, 2022.
[24] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pages 2166-2167, 2019.
[25] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019. URL https //openreview
[26] Muhan Zhang and Pan Li. Nested graph neural networks. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. httt/tttt///:peerreeee wttp://wwww.teeeoe/m///////..... _eEvFF
[27] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations, 2022. URL /tt/atttss///operriiiii
nwt/eeeuurtttie forromiddddddp.ooo WYKoEH MrKKW
(28) Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022. URL htttps://pperreiier http:pawwwweeeeeeeoorooruuaaaaa
[29] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Information Processing Systems, pages 15894-15902, 2019.
[30] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), 2021.
[31] Ralph Abboud, ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 2112-2118 8 2021. doi: 10.24966iicci..22222999 URL httph:tt////cc //doi. org/ 10. 24963/1jcca. 2021/291
[32] Andreas Loukas. What graph neural networks cannot learn: depth width. arXiv preprint 1rX.v:190..03199, 2019.
[33] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pages 5165-5175, 2018.
12

---

[34] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. In A. Beygelzimer, Y. Dauphin. P. Liang, J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL URL wtttt::t/tpttteeeeeeee http://eeeeeeooom/m//occccgoaaaa
[35] Xiyuan Wang and Muhan Zhang. GLASS: GNN with labeling tricks for subgraph representation learning. In International Conference on Learning Representations, 2022. URI. https
7 //openreview ket//oormm2dd-Xxahj]
[36] Asiri Wijesinghe and Qing Wang. A new perspective on "how graph neural networks go beyond weisfeiler-lehman?" In International Conference on Learning Representations, 2022. URL
https://openreviee..tt
[37] Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12):10737- 10745, May 2021.
[38] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 02428, 2019.
[39] Muhammet Balcilar, Pierre Héroux, Benoit Gaüizèe, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
[40] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. International Conference on Machine Learning, pages 4663-4673, PMLR, 2019.
[41] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Systems, 2020.
[42] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 2020.
[43] Asim Kumar Debnath, de Compadre RL Lopez, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. acrtiture-attvvity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-797, 1991.
[44] Paul D Dobson and Andrew J Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
[45] Hannu Toivonen, Ashwin Srinivasan, Ross D King, Stefan Kramer, and Christoph Helma. Statistical evaluation of the predictive toxicology challenge 2000-2001. Bioinformatics, 19(10):
1 1183-1193, 2003.
[46] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1365-1374. ACM, 2015.
[47] Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):177, 2014.
[48] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, (2):513-530, 2018
[49] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003. 00982, 2020.
13

---

[50] Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(Sep): 2,61, 2011.
[51] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting, 2021. URL https //openreview net/foruu/2ad--ToKsPPP0
[52] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montufar, and Michael M. Bronstein. Weisfeiler and lehman go cellular: CW networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL
[53] Béla Bollobás. Distinguishing vertices of random graphs. In Béla Bollobás, editor, Graph Theory, volume 62 of Nolth-Holland Mathematicc Studies, pages 33 49, North-Holland, 1982. doi: htoo///coonz/fficcce//////000060
X. httptttss: htt.ttppppp//w.....ieeeerrrrrr scweecedrreecrcttt
[54] Béla Bollobás. A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs. European Jourmal of Combinatorics, (4):311-316) December 1980. ISSN 0195-6698. doi: 10. 10.1016//50995566668888000883330
URL https: http://ww.cienccdiee....
com/science// /ttpo//ce//rrrteee//////1/666630
[55] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-6008, 2017.
[56] Floris Geerts. The expressive power of kth-order invariant graph networks. ArXiv, 2atp20077.200355 2020.
[57] Thang Luong, Hieu Pham. and Christopher D. Manning. Effective approaches to attention- based neural machine translation. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1412-1421, Lisbon, Portugal, Septem- ber 2015. Association for Computational Linguistics. doi: 10.186////DDD5-1116 URL
attps://aclanthology org/ 1
[58] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, 2018.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as URL)? [Yes] The implementation of KP-GNN can be found http:///gtuub.ooommaaiif////////
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
14

---

(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasig new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No] The license can be found in their github.
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] All datasets used are all open-sourced.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A] There is no personal information in the datasets.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "lxAAYTxpv4w", "reviewer": "Reviewer_QvfD", "summary": "This work first formalizes the expressive power of the K-hop message passing GNNs. Then, it proposes KP-GNN, which uses the peripheral subgraph information, to improve the expressiveness of K-hop message passing GNNs. Experiments on various graph tasks are performed to evaluate the proposed KP-GNN.", "questions": "As in the above weaknesses.", "limitations": "The main limitation is that the time complexity of KP-GNN is quite high, which might be not scalable to large graphs.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "++++ Strengths\n\n(1) The unified view of K-hop message passing GNNs (Figure 1) is clear and potentially useful to the community.\n\n(2) The presentation of this paper is well organized and easy to follow.\n\n++++ Weaknesses\n\nThe main weakness of this paper is that the contribution is not clearly stated, the key differences with prior works are not clear, some of the claims are not clarified well. The details are as follows.\n\n(1) The expressive power of k-hop message passing GNNs are not clearly presented. Please correct me if I am understanding it wrongly. In Definition 3, we have a proper k-hop message passing GNNs if all three functions are injective. Then, in Definition 4, the node configuration is a list, which means it has an order. I think the gap from Definition 3 to Definition 4 has not been clearly stated. To my understanding, an injective COMBINE function in Eq. (3) does not guarantee the order of hops. For example, for two node v_1, v_2, let’s say the input to the COMBINE function is {{1}} and {{2}} if we only consider 1 hop. Then, when we consider 3 hops, an example input of the COMBINE function could be {{1,2,3}} and {{2,3,1}}. Then, the COMBINE function will yield the same output for these two nodes.\n\nIn other orders, in Collorary 1, the statement “the K-hop message passing is at least equally powerful as 1-hop message passing since the K-hop message passing includes all the information that 1-hop message passing has” may not hold, since the 1-hop information may be destroyed when we COMBINE it with more information from more hops. \n\n(2) The difference to GNN-AK and Nested GNN has not been clearly made. In these two works, they consider encoding the k-hop subgraphs for all nodes, which is quite related to the peripheral subgraph information considered in KP-GNN. The difference and advantages over these works are not clear in the current paper. For example, technically, how powerful of KP-GNN compared to these works? In the current manuscript, we cannot see significant improvements over these works in terms of empirical performance or time complexity.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lwsdgApxJ2u", "reviewer": "Reviewer_uewD", "summary": "This paper provides a theoretical analysis of the expressive power of K-hop message passing GNNs. In particular, the authors show that K-hop message passing GNNs are more powerful than 1-hop message passing GNNs and that a K-hop GNN can distinguish some regular graphs while they are indistinguishable for 1-hop GNNs. Going further, they propose another message-passing GNN called KP-GNN, which is more powerful than K-hop GNNs. KP-GNNs can distinguish between many distance-regular graphs by using subgraph (edge)  information from the K-hops in addition to the node information. The authors also provide experiments to empirically verify the expressiveness of the newly proposed architectures for small K greater than 1. They also give some runtime analysis to show the computational cost of the proposed techniques.", "questions": "Please refer to the section on Weaknesses.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper is theoretically sound, and the experiments give an idea about the effectiveness of the proposed techniques in graphs of practical interest.\n\nWeakness\n- While the paper shows that K-hop message passing GNNs are more powerful than 1-hop message passing GNNs and KP-GNNs are even more powerful than K-GNNs in expressiveness, the analysis doesn't provide an algorithm to check when a certain K suffices. It also doesn't tell us how these GNNs fit into established hierarchies. It is not clear how to use this analysis to inform practical applications.\n\n- It is also not clear from the analysis if these K-hop message-passing networks are less/more powerful or incomparable to other proposed methods that use graph substructures like CW complexes, and subgraph structures.\n\n- While the experiments show that the average values for KP-GNN-like models are higher the high variance in some tasks makes it unclear if they are much better than previous methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WqJKw4XCDyJ", "reviewer": "Reviewer_qmM3", "summary": "The paper studies the K-hop message passing GNN. The paper shows that the original K-hop GNN is more powerful than 1-WL. To further improve its expressivity, the author further proposes to use the induced subgraph at each hop to augment the original K-hop GNN. interesting theoretical results are proposed for distinguishing regular graphs. ", "questions": "Overall the paper studies the k-hop message passing in-depth and has done many experiments. I don't have much question over the proposed method as the presentation is good. However I'm worrying about the novelty and the soundness of its real-world ability comparing with other subgraph methods. ", "limitations": "N/A", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n1. The author studies the K-hop message passing framework in depth, and provide several interesting theorems for regular graphs. \n2. The paper is well-written and easy to follow. \nWeakness:\n1. The original K-hop message passing has close relationship with distance encoding proposed in Nested GNN(Zhang, 2021) and GNN-AK (Zhao, 2021), while the author ignores analyze the connections. Also the author said that they pickup a weak version of GNN-AK's result without considering distance encoding, which I think is improper especially given the close connection between distance encoding and K-hop message passing. The original GNN-AK's performance over Graph Properties and Counting Substructures is better.\n2. In theorem part, stronger than 1-WL is kind of trivial to show. Also Theorem 1 is kind of trivial. Theorem 2 and Theorem 3 could be very similar to theorems in Distance Encoding paper (Li, 2020). Also analyzing expressiveness limited to regular graphs is a weakness. \n3. The proposed enhanced K-hop message passing uses the information of subgraphs within kth-hop. However making using of subgraph information is well explored in Nested GNN, GNN-AK, and  Equivariant subgraph aggregation networks. Although there are some difference, the contribution is limited. \n4. The experimental result in TU dataset is also questionable. The author uses two type of evaluation settings, and in the first widely used setting the author doesn't show any performance improvement. If the author want to show the improvement over the second evaluation setting, it's better to also include baselines like GIN and GIN-AK. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5p9qun1AwNv", "reviewer": "Reviewer_1P51", "summary": "The authors theoretically analyze the expressive power of existing K-hop message passing graph neural networks (K-GNNs). Furthermore, the authors propose the K-hop peripheral-subgraph-enhanced graph neural network (KP-GNN), which aggregates peripheral subgraph information to enhance the expressive power of K-GNNs. Experiments demonstrate that KP-GNN achieves competitive results on all benchmark datasets.", "questions": "1. How are the shortest path distance kernel and graph diffusion kernel misused in existing works? \n2. Why is the increase of the computational costs in terms of $K$ far less than the theoretical results?\n3. Besides the running time at each epoch, the authors may want to directly use the total running time to evaluate the efficiency, as the total running time depends on not only the running time at each epoch but also the convergence rate. \n4. The authors may want to use the multiset to define the K-hop neighbors rather than the set in Definition 2. Following Definition 2 in the main text, $\\mathcal{N}_{v,G}^{2,gd}$ of node 2 in the example in Figure 2 in the appendix is $\\{v_1,3,4,5,6\\}$ rather than the multiset $\\{v_1,3,3,4,4,5,6\\}$.\n5. Some important experiment settings are missing, including times of each experiment and the definition of error bars in Tables 3, 5, 6. \n", "limitations": "The authors may want to address the limitations of the proposed method, e.g. types of data or tasks the method might fail.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The authors provide the theoretical analysis for the expressive power of K-GNNs and KP-GNN. \n2. Experiments demonstrate that KP-GNN achieves competitive results on all benchmark datasets.\n3. The authors provide many typical examples so that the derivation of KP-GNN is easy to follow.\n\nWeaknesses:\n\nMy major concerns are follows.\n1. The authors assume that all nodes in the graph have the same feature in the theoretical analysis, which is stronger than the assumption in [1]. The authors may want to analyze the expressive power of KP-GNN under the assumption of [1]. \n2. The authors claim that the expressive power of KP-GNN outperforms existing K-GNNs. Therefore, the authors may want to compare KP-GNN with more K-GNNs in experiments, such as MixHop [2], K-hop [3], MA-GNA [4], GPR-GNN [5]. \n3. The authors may want to compare the time and space complexity of KP-GNN with other powerful GNNs such as PPGN [6]. \n\n- [1] Xu Keyulu, Weihua Hu, Jure Leskovec and Stefanie Jegelka. \"How Powerful are Graph Neural Networks?\" International Conference on Learning Representations. 2018.\n- [2] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg and Aram Galstyan. \"Mixhop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing.\" International Conference on Machine Learning. 2019.\n- [3] Nikolentzos, Giannis, George Dasoulas, and Michalis Vazirgiannis. \"K-Hop Graph Neural Networks.\" Neural Networks. 2020.\n- [4] Guangtao Wang, Rex Ying, Jing Huang and Jure Leskovec. \"Multi-hop Attention Graph Neural Networks.\" IJCAI. 2021.\n- [5] Eli Chien, Jianhao Peng, Pan Li and Olgica Milenkovic. \"Adaptive Universal Generalized PageRank Graph Neural Network.\" International Conference on Learning Representations. 2020.\n- [6] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky and Yaron Lipman. \"Provably Powerful Graph Networks.\" Advances in Neural Information Processing Systems. 2019.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept