Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the expressive power of graph neural networks from a different angle than the classical $k$-WL hierarchy. Authors argue that $k$-WL is not very well-suited for developing new graph neural network architectures since (i) these algorithms are already computationally demanding with $k\geq 2$, (ii) this hierarchy is not ``granular enough'' to capture graphs that lie between $1$-WL and $3$-WL, and most importantly (iii) $k$-WL algorithms rely on computations over $k$-tuples (and associated neighbourhoods), which are not local, and this does not align with the initial motivation of graph neural networks which aggregate information locally. Based on these (and similar) observations, authors propose a new hierarchy of graph isomorphism tests, coined as Neighbourhood-WL ($N$-WL)
algorithms. They prove that this is a proper hierarchy and introduce Graph Neighbourhood Neural Network (G3N) based on
the $N$-WL algorithms, and report empirical findings.
strength_and_weaknesses: Strengths:

- The study of expressive power of GNNs is important, and there is a value in looking beyond the WL hierarchy in designing novel models.
- Looking at multi-hop neighbourhoods in aggregation is at the core of this work, which is well-understood concept with potential benefits/

Weaknesses:

- The paper is hard to follow: For example, it is not immediately clear what the parameter $t$ exactly stands for in $N(d,t)$ and why it is important. It is stated relatively early that this is the size of the induced subgraphs, but there is no justification as to why this parameter needs to be controlled. In my understanding, this is due to computational inefficiency: the proposed class of algorithms enumerate all subgraphs of order $t$ within a $d$-hop neighbourhood, and this should be clearly stated. 

- The paper is not very well-placed in the literature. Authors have an extensive related work (a bulk of it is in the appendix, which is not a great practice in my opinion), but there are no concrete connections to other well-known concepts: To elaborate on this:

   -  $N(d,t)$ algorithms operate over $d$-hop neighbourhoods, which are defined using shortest path distances. Authors hint to the fact that that the class of $N(d,t)$ algorithms may not be a natural choice, since increasing $d$, while fixing $t$ does not necessarily yield more expressive power. They propose to use the positional information in the respective hops, which leads to a more intuitive class of algorithms: In my opinion, this is the right way of using the shortest path kernel within the algorithm. This paper builds on this idea to use positional info in the induced subgraphs, but the connections are not explored/explained. 

   -  It is not very clear whether one gains more by using the induced subgraphs, as compared to just using multi-hop aggregation (which also has strictly more expressive power than 1-WL and generally incomparable to the hierarchy). The presented ablation study confirms the role of $d$, but the same cannot be easily claimed for $t$.

   -  Authors are understandably critical about the $k$-WL hierarchy, but this is not always well-calibrated. I suggest authors tone these statements differently. There are many well-known connections between $k$-WL hierarchy and logics, which precisely inform us about the formal properties of these algorithms.

   -  There are many local variants of $k$-WL algorithms which are proposed with similar intuition: instead of aggregating over all $k$-tuple neighbourhoods, these algorithms only look at $k$-tuples within a local neighbourhood, which is not far away from the intuitions presented in this paper. The connections need to be discussed in depth, clarifying whether the proposed model has advantages over local WL algorithms.


- In the actual model, authors inject isomorphism types into node features (which is different than operating over isomorphism types), quoting the authors: ``However, we found that using different learnable linear transformations for all possible isomorphism
and positional types leads to much slower training. ... To remedy this problem, we instead only use different weight matrices for
positional types only, and inject the isomorphism type information as additional features to node embeddings."

- The given review time is not sufficient to check the proofs in detail. The theorem statements are not very specific: It should be stated what is fixed, and how the other parameter ranges. It is also unclear whether the statements are over the class of all graphs, or just over graph pairs. The WL hierarchy is an infinite hierarchy: Is the same true here? 

- WL algorithms can be used to analyse node-level, or link-level properties, and the same applies here, but it is unclear to me, e.g., under which conditions $(G_1,u)$ can be distinguished from $(G_2,v)$. I understand if this is left as future work, but it is important to highlight.

- The runtime of these class of algorithms is also prohibitive, and using a small $t$ seems the only way around the issue. I am not convinced that this new class of algorithms suggests a promising direction. 



clarity,_quality,_novelty_and_reproducibility: There is room for improvement in the presentation (please refer to my earlier comments). The main idea is clear but the proposed class of algorithms are somewhat new but they not very novel - they are closely related to local version of WL algorithms, WL sub-graph kernel, and shortest path kernel, which are not discussed.
summary_of_the_review: I agree with many points of the paper, but I am not convinced that this class of algorithms is the way forward. It is also unclear to me whether, or to what extent, this study improves our understanding of the field.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work tries to propose a new class of graph isomorphism testing algorithm, called Neighbourhood WL ($\mathscr{N}$-WL), which stores complex information in low dimension, instead of using high-order tuples in $k$-WL. It develops two Neighbourhood WL algorithms with parameters ($t$,$d$) and theoretically discusses whether the algorithms gain expressivity with parameters increased. Then, to reduce complexity, it further develops a connected-subgraph version of $\mathscr{N}$-WL and its GNN implementation. The proposed GNN model is evaluated on a number of synthetic and real-world experiments.
strength_and_weaknesses: Pros:
1. The discussion of related works in Section 2 and Appendix B is comprehensive.
2. The theoretical arguments of weak-hierarchy-related $\mathscr{N}^-$-WL and strong-hierarchy-related $\mathscr{N}$-WL seem to be nice, with sufficient proof and counter-examples for general settings of parameters ($t$,$d$).
3. The development from $\mathscr{N}$-WL to its connected-subgraph version $\mathscr{N}^c$-WL is great, accompanied with clear reasoning in Section 3.2.

Concerns:
1. I am a little confused by the definition of $f_{pos}$ under ''Strong Hierarchy''. Here are a series of questions:
    * there is a parameter $d$ in $\mathscr{N}$-WL. But there is again $\forall~ d\ge 1$ as the condition of ''... $f_{pos}(S_i)\neq f_{pos}(S_j)$''. Is the second $d$ not related to the first $d$? 
    * Is $f_{pos}$ unique or universal for any target node $u$? If unique, it seems very complicated to parameterize the representation of $J_d$ in Eq(4). If $f_{pos}$ is universal: moreover, if the answer to the above question is ''not related'', then it seems $f_{pos}$ is coloring everything distinctly because the target node can be arbitrary.
    * again, how is $J_d$ obtained in the model in Eq(4)?
2. The compared baselines in the ZINC experiment are not enough, because it only includes PPGN as the GNN beyond 1-WL. For instance, GSN is missing, which is cited and discussed by the authors for many times. It would be great to see the comparison with more expressive GNNs to show the sufficiency and efficiency of the proposed model.
clarity,_quality,_novelty_and_reproducibility: The reproducibility is good.

For clarity, please see the above concerns.

For quality, theorems and their proof generally seem to be in good shape, but I need to get the above concerns clarified to check the quality again.
summary_of_the_review: For now, I would like to recommend ''below acceptance threshold'' due to the mentioned concerns. I am willing to raise my score if the concerns are addressed.

=== Acknowledgement ===

Due to time limit, I only read the main text and the proof of Theorem 3.1. Other parts in Appendix were not thoroughly checked.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new hierarchy of expressive isomorphism test algorithm and GNN model, with combining k-WL tuple idea and rooted subgraph idea from subgraph GNNs. More specifically, the author still work on subgraph GNNs with each node representing the encoding of d-hop rooted subgraph around the node. Unliking 1-WL encoding of the d-hop rooted subgraph, the author proposes to apply t-set extraction for the d-hop rooted subgraph which should be much more powerful than 1-WL encoding. The author proved strictly increased expressivity with respect to increasing t and d, under the help of positional information of every t-set. Furthermore, the author claim that one only need to consider (≤)t-set whose induced subgraph are connected, and it does not lose any expressivity. The corresponding GNN model is also designed, and the author conducts extensive experiments over several widely used benchmark datasets for evaluating expressivity. 
strength_and_weaknesses: **Strength**: 
1. Going beyong k-WL hierarchy is an important direction, as k-WL is not practical with k > 3.
2. The designed hierarchy combines recently hot subgraph GNNs and k-WL, which is novel and an interesting angle.
3. The author proved strictly increasing expressivity with respect to increasing d hop and t size, which is a great contribution in theory. 
4. I personally find that theorem 3.7 is the most interesting one, however I'm not fully convinced that the theorem is correct, as I cannot fully  follow their proofs. (This theorem can reduce a lot t-sets, which can greatly improve runtime. It's hard to believe that this won't lose expressivity. )

**Weaknesses**:
1. Although the proposed hierarchy has increased expressivity with d and t. It is not clear the upper bound expressivity of the method. And the connect to k-WL is not clear also. It's possible that its maximum expressivity is limited.  
2. The proof of theorem 3.7 is questionable. 
3. The runtime analysis shows that the method is faster over sparse graph, but for denser graph this can be very slow.
4. When d is large, the computational cost can be closer to k-WL (its set version) for extracting all t-tuples. The main difference to k-WL will be that the intermediate representation is size n instead of size n^t. 
5. The experimental result over real-world datasets is not very good, this may suggests the expressivity upper bound of this method is limited. 

**Missing Reference**:
Studying an improved expressivity hierarchy has been explored. The paper [Zhao et al. NeurIPS 2022] improved k-WL by using ≤k sets and studied its expressivity theoretically. The theorem 8 in [Zhao et al. NeurIPS 2022] is similar to the paper's Lemma 3.6 and has connection to Theorem 3.7. They also used connected components. I suggest the author to have a check. 

**Additional Suggestion**:
As mentioned above, the proposed hierarchy is under the rooted subgraph WL presented in [Zhao et al, ICLR 2022]. The difference would be improving encoding of rooted subgraph with higher-order sets. The original paper uses 1-WL to encode rooted subgraph, which has overall expressivity upper bounded by 3-WL [Frasca et al. NeurIPS 2022]. It would be interesting to know that assuming we have the most expressive rooted subgraph encoder, what is the expressivity upper bound of the rooted subgraph WL? This upper bound would also be the upper bound of the proposed hierarchy. The author needs to study the upper bound of the proposed hierarchy to see whether it can achieve universality. 

[Zhao et al. NeurIPS 2022] A Practical, Progressively-Expressive GNN, https://arxiv.org/pdf/2210.09521.pdf.   
[Zhao et al. ICLR 2022] From stars to subgraphs: Uplifting any GNN with local structure awareness.   
[Frasca et al. NeurIPS 2022] Understanding and extending subgraph gnns by rethinking their symmetries.   
clarity,_quality,_novelty_and_reproducibility: The paper is clear written and not hard to follow. And the paper is focusing on an important direction of designing progressively expressive GNN not restricted by k-WL. The ideas and theorems presented are novel, given all theorems are assumed to be correct. 
summary_of_the_review: The author proposes an interesting design of color updating isomorphism test algorithm, and study it theoretically. It would be further improved if its upper bound is studied or the connection to k-WL is much more clear.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduces a new family of isomorphism testing algorithms based on the WL tests hierarchy called Neighborhood-WL ($\mathcal{N}-$WL). Similarly to the WL test, the proposed algorithms iteratively refine a node coloring to determine whether two graphs are isomorphic. The difference from the WL test is that the node coloring is updated by aggregating the colors of subgraphs of size $t$ in the node’s $d$-hop neighborhood. The authors show that the parameters $(t,d)$ induce a strict hierarchy of isomorphism testing algorithms and further suggest and prove equivalence to a more computationally efficient variant aggregating a connected heredity neighborhood. Inspired by the $\mathcal{N}$-WL hierarchy, the authors propose a corresponding GNN design that can match the expressive power of $\mathcal{N}$-WL tests.


strength_and_weaknesses: ### 1. Strengths

- The paper proposes a new isomorphism testing hierarchy. 
- The authors provide a thorough theoretical characterization of the suggested hierarchy - expressivity, connection to WL tests, and complexity. 
- The paper introduces a flexible and general GNN architecture design based on the $\mathcal{N}$-WL hierarchy.
- An extensive experimental evaluation and ablation study is performed.

### 2. Weaknesses

#### 	1. **Relation to K-hop GNNs** - 
[1] analyses the expressive power of K-hop GNNs which basically, similar to this work, aggregate information from the k-hop neighborhood of each node and use this information to update the node's color at each iteration. In [1] they show that K-hop GNNs' expressive power is bounded by the 3-WL test. They further suggest a variant of K-hop GNNs to increase the expressive power, called KP-GNNs. I find the idea in KP-GNNs very similar to the addition of the positional types in the current work. 

#### 	2. **Experimental Results** - 
The experimental results, as in many GNN papers, justify the theoretical statements but do not exhibit any significant improvement in real-life datasets. Furthermore, I find the comparison on the ZINC dataset rather lacking (see Table 5 in [1]).

#### 	3. **Name of the paper** - 
The name of the paper is quite general and does not reflect the properties of the proposed hierarchy. I would suggest changing it to something of the flavor "Neighborhood WL hierarchy of expressivity for graph neural networks"

[1] Feng et. al. [How Powerful are K-hop Message Passing Graph Neural Networks](https://arxiv.org/abs/2205.13328 ) (NeurIPS 2022) 

clarity,_quality,_novelty_and_reproducibility: The paper is well-written and easy to follow. Statements and theorems are proven and proofs are generally written in a clear way. 


summary_of_the_review: The paper provides a well-defined new hierarchy of isomorphism testing hierarchy. I find this construction elegant, and the generality of the suggested framework is appealing. My main concern regarding this work is the lack of discussion of the relation to K-hop GNNs that share many ideas with this work. Furthermore, [1] somewhat overlaps with this work, and an elaborate discussion on that is also required. 

I rate this paper as marginally below the acceptance threshold but would reconsider it upon clarifying and addressing my concerns.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a new WL-like expressive power hierarchy for graph isomorphism testing, and derives a new GNN architecture based on these principles. While the reviewers appreciated the new hierarchy, they questioned the novelty wrt related works on k-hop CNNs. Furthermore, the experimental results were not very impressive. The AC believes that the paper presents a direction somewhat different from the majority of GNN literature that might be interesting and worth being presented at the conference. 
justification_for_why_not_higher_score: not sufficiently novel
justification_for_why_not_lower_score: interesting idea
Decision: Accept: poster