Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 
strengths_and_weaknesses: Strength: 
1. The author studies the K-hop message passing framework in depth, and provide several interesting theorems for regular graphs. 
2. The paper is well-written and easy to follow. 
Weakness:
1. 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.
2. 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. 
3. 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. 
4. 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. 
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
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
1. The authors provide the theoretical analysis for the expressive power of K-GNNs and KP-GNN. 
2. Experiments demonstrate that KP-GNN achieves competitive results on all benchmark datasets.
3. The authors provide many typical examples so that the derivation of KP-GNN is easy to follow.

Weaknesses:

My major concerns are follows.
1. 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]. 
2. 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]. 
3. The authors may want to compare the time and space complexity of KP-GNN with other powerful GNNs such as PPGN [6]. 

- [1] Xu Keyulu, Weihua Hu, Jure Leskovec and Stefanie Jegelka. "How Powerful are Graph Neural Networks?" International Conference on Learning Representations. 2018.
- [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.
- [3] Nikolentzos, Giannis, George Dasoulas, and Michalis Vazirgiannis. "K-Hop Graph Neural Networks." Neural Networks. 2020.
- [4] Guangtao Wang, Rex Ying, Jing Huang and Jure Leskovec. "Multi-hop Attention Graph Neural Networks." IJCAI. 2021.
- [5] Eli Chien, Jianhao Peng, Pan Li and Olgica Milenkovic. "Adaptive Universal Generalized PageRank Graph Neural Network." International Conference on Learning Representations. 2020.
- [6] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky and Yaron Lipman. "Provably Powerful Graph Networks." Advances in Neural Information Processing Systems. 2019.

questions: 1. How are the shortest path distance kernel and graph diffusion kernel misused in existing works? 
2. Why is the increase of the computational costs in terms of $K$ far less than the theoretical results?
3. 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. 
4. 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\}$.
5. Some important experiment settings are missing, including times of each experiment and the definition of error bars in Tables 3, 5, 6. 

limitations: The authors may want to address the limitations of the proposed method, e.g. types of data or tasks the method might fail.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: ++++ Strengths

(1) The unified view of K-hop message passing GNNs (Figure 1) is clear and potentially useful to the community.

(2) The presentation of this paper is well organized and easy to follow.

++++ Weaknesses

The 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.

(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.

In 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. 

(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.
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.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths
- The paper is theoretically sound, and the experiments give an idea about the effectiveness of the proposed techniques in graphs of practical interest.

Weakness
- 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.

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

- 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.
questions: Please refer to the section on Weaknesses.
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: The reviewers generally agreed that the paper is well written (with many examples), that the theoretical analysis is interesting, and that the experimental results are promising. 

The reviewers raised questions regarding four main aspects of the work that were satisfactorily addressed by the authors during the rebuttal: 
1. The relation between K-hop/KP-GNN message passing and other methods, such as distance encoding and subgraph-based GNNs. The authors explained the relations in a convincing manner by showing that a) KP-GNN is strictly more powerful in terms of distinguishing distance regular graphs than subgraph-based GNNs and b) by proving that neither K-hop nor distance encoding is strictly more expressive than the other.
2. The complexity of KP-GNN, which was shown to be similar to to vanilla GNN.
3. The ability of the COMBINE function to distinguish between nodes at different hops. I am convinced by the detailed explanation of the authors that this is not an issue in the setup where the message and update functions can be chosen arbitrarily. In any way, the point is not very important as the distance can be trivially incorporated. 
4. The standard deviation reported in the TU dataset (Table 3) is higher than for other methods. This is true, but not a deal breaker.
   
Points 1 and 2 above are already addressed in the revised document. *For point 3, I ask the authors to include in their appendix a formal proof of why k is not crucial and to perform an ablation where the effect of adding k is examined.* (Concatenating k, e.g., represented as a one-hot vector, could be practically beneficial by making the learning of the message and update functions easier.)

It is my opinion that the ratings offered by the reviewers are outdated (they were not updated in light of the author rebuttal). For this reason, I decided to accept the work.
confidence: Certain
Decision: Accept