Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper deals with supervised learning on graph structured data for which the most common framework of GNN is limited in expressivity by 1-WL test in terms of its identifying capacity of graphs. 
Higher order $K$-WL hierarchy of algorithms are well-known to improve the expressivity of GNN models with increasing $K$. However, the complexity of the $K$-WL increases exponentially with increasing $K$, making it infeasible to apply in practice. The authors propose $(k,c)(\leq)$-SetWL hierarchy in place of WL-hierarchy. a It is a “finer-grained ruler” than WL-hierarchy and mainly depends on sets (size $\leq k$) instead of tuples of nodes and connected components ($\leq c$). The authors develop the method moving from tuples in WL to multisets, then to sets and then to sets with connected components and design its neural counterpart $(k,c)(\leq)$-SETGNN. Experimental results on both synthetic and real datasets show that the method is promising.

strengths_and_weaknesses: ### Strengths:
1. The paper addresses an important problem of going beyond 1-WL, however, in such a manner such that expressivity is improved in a progressive way while runtime is still manageable 
1. The idea naturally follows from K-WL models of moving from tuples to multisets, then to sets. The paper rigorously explores this.
1. Experimental results on graph classification and substructure identification as well as regression Zinc12k are promising.
1. The paper is well-written with needed rigor. However, the presentation could be improved for better readability.

### Weaknesses/Comments:
+ The result in Theorem-1 of k-Multiset-WL being equal to K-WL is surprising. I think this should have been discussed with some intuitive figures to show where exactly is the redundancy in K-WL that is being exploited by K-Multiset-WL. I could not follow the proof properly, however it seems to me that with the perm[] function, you would spend same amount of time as K-WL in updating the node colors. Exact number of supernodes in K-Multiset-WL in comparison with K-WL is also missing.
+ Runtime analysis is not complete. Though it is nice to see the exact ratio of speedup of K-SETWL with respect to WL, it would be much clearer if we see the runtime of WL, Multiset-WL, SET-WL,  in BigO notation. Further, what is the cost with respect to $c$ in (k,c)(\leq)-SETWL is also not clear. Asymptotic runtime would also help in visualizing where exactly the speedup comes from.
+ The empirical evaluation should include additional recent expressive GNN models to properly understand the benefits of SET-GNN in comparison with other more expressive models like GraphSNN (Wijesinghe, et al. (2021)), PF-GNN (Dupty et al. (2021)), GNNML3 (Balcilar et al. (2021)) etc. This would also be important since these methods employ different techniques to achieve expressivity and SETGNN can be analysed in perspective.
+ The paper can be significantly improved in readability if some pictures are added to describe the key points where redundancy is removed from tuple to multisets, then multisets to sets.
+ Line 238: derivation not in Appendix
+ Line 183, it should n_u in place of n_n

**Overall**, I find the idea of the paper novel as well as very significant for improving the expressivity of GNNs. Also, the idea is systematically and rigorously developed towards providing a finer scale for measuring expressivity. 

However, I could not fully grasp the proofs and hence I’m less confident, especially since the results are somewhat surprising. Furthermore, experimental results need to be properly placed with respect to the recent literature.

### References:

+ [1] Wijesinghe, et al. (2021).  A New Perspective on" How Graph Neural Networks Go Beyond Weisfeiler-Lehman?". In International Conference on Learning Representations.
+ [2] Dupty et al. (2021) "PF-GNN: Differentiable particle filtering based approximation of universal graph representations." International Conference on Learning Representations.
+ [3] Balcilar et al. (2021)  "Breaking the limits of message passing graph neural networks." International Conference on Machine Learning. PMLR.
questions: Please address the weakness mentioned above.

limitations: The authors have discussed some limitations. There is no potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work proposes a more fine-grained graph isomorphism test hierarchy, namely (k,c)(<=)-SetWL, by further considering removing order, removing repetition, and graph sparsity over the original k-WL algorithm. Based on the obtained graph isomorphism test algorithm, it further develops a progressively expressive GNN accordingly. Experiments on synthetic and real datasets are performed to evaluate the effectiveness of the proposed GNN.
strengths_and_weaknesses: +++ Pros

(1) It is technically sound to consider removing order, removing repetition, and graph sparsity over the original k-WL algorithm. The step-by-step derivation is sound and clearly present.

(2) This work also characterizes the expressiveness of the obtained k-WL variants clearly. It is impressive to me to know that k-MultisetWL is as expressive as the original k-WL. This result might have impact to the community.

(3) The presentation of this work is great. Although it has a lot of math, the flow is generally easy to follow.

(4) The empirical results are strong to demonstrate the effectiveness of the proposed GNN.

+++ Cons

(1) Although the presentation is good enough, there are several places which are hard to understand, given that this is a math-heavy work. For example, the result given in Theorem 1 is amazing, it would be great to provide some intuitive explanation of the proof in the main text. This can also help readers to understand why we consider removing orders.

(2) Similarly, the derivation of Theorem 4 is also unclear to me. Please see the following question for details.

questions: (1) I am not fully understand the derivation of Theorem 4 ((k,c)(<=)-SetGNN is as expressive as (k,c)(<=)-SetWL). In the given proof, it is mainly based on the results of DeepSet. In other words, MLP with summation is universal so that it can learn the desired injective function. However, this may not prove that Eq. (9) is injective directly, since the input of the outer MLP in Eq. (9) has four parts. It is unclear and non-trivial that how to ensure that this MLP can learn an injective function.

+++minor points
Line 182, a should be an

limitations: Not applicable.
review_title: null

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 goal of this paper is to develop more expressive GNNs using the k-WL hierarchy. While the one-dimensional Weisfeiler Leman (1-WL) helps to distinguish isomorphic graphs, the use of k-WL hierarchy helps build more expressive GNNs.  The authors propose (k,c) <= SETWL which reduces the complexity of the k-WL hierarchy. Tweaking k and c in this model, helps develop practical and progressively expressive GNNs. 

strengths_and_weaknesses: Strengths
- The paper is well written with both theoretical and empirical work. 
- An interesting problem on expressiveness of GNNs is explored using set theoretic tools along with message passing algorithms

Weakness
- The problem needs to be better motivated -- how is expressiveness related to generalization performance? Why use (k,c) (<=)-SETGNN at all?
- The paper assumes an audience well versed with graph isomorphism, Weisfeiler Leman hierarchy, and other kinds of isomorphism test. A reader unfamiliar with these concepts would wonder why even this is relevant. Motivating with concrete real world examples would perhaps make it easier to see why this is an important problem to solve.
questions: - What is the basic definition of "expressiveness" of a GNN model? Does increased expressiveness of the super-graph imply better generalization performance?
 
- Is expressiveness related to interpretability of the model? If not, what marks the fundamental difference between them?
 
- Why is the work consistently using GNNs when the literature is replete with many other kinds of neural networks whose expressiveness can be studied and interpreted?
 
- The motivation for (k,c) (<=)-SETGNN has not been well discussed.
 
 - Section 5: What is a SOTA expressive GNN? The acronym has not been defined.
 -For ease of readability, consider having a notation table instead of the section 3
 -Table 1,2,3,4 and 5 should simply use two places of decimals for ease of readability
 
 The authors claim "Such a hierarchy could enable us to gradually build more expressive models which admit improved scaling, and avoid unnecessary leaps in model complexity for tasks which do not require them, guarding against overfitting."
 What is the relation between expressivity of a graph and graph isomorphism?
 
 In Table 2, with k=3 or 4, and more than one connected components, the performance on the test set is much worse than on the train set. So for these highly expressive graphs, how is generalization performance demonstrated to be better?
 

limitations: Complexity of the proposed technique in addition to scalability are clearly limitations which the authors try to solve and are successful to a good extent.
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: The paper introduces a family of models, namely (k, c)(≤)-SETGNN, whose expressiveness increases with k and c.
The expressiveness is measured in terms of the newly proposed hierarchy (k, c)(≤)-SETWL which is more "granular" than the standard k-WL hierarchy.
The presentation guides the reader to the derivation of the (k, c)(≤)-SETWL by iteratively refining the k-WL hierarchy.
The paper comes with proofs relating the various refinements and experiments that investigate the progressive expressiveness of the proposed architecture for varying k and c.

strengths_and_weaknesses: **Strengths**
- The empirical evaluation shows increased performance wrt existing methods
- The proposed architecture's expressiveness can be modulated easily through the k and c parameters.

**Weaknesses**
- It's unclear whether one can use the new proposed "ruler" (the (k, c)(≤)-SETWL hierarchy) to compare existing models and whether new models other than (k, c)(≤)-SETGNN can be built around it. Consequently, the significance appears rather limited.


Minor comments:
- $s$ is not defined in line 135 but introduced much later in line 175
- Fig. 1 needs a few more iterations. Many edges are disconnected from their endpoints and the labels (1, 5 etc.) of the nodes are not centered.
questions: - Is it possible to analyse the expressiveness of existing approaches in term on the new hierarchy?
- Did you use the parameter budget (100K or 500K) as prescribed by ZINC-12K?
- The linked repository is empty, please update it.
limitations: n/a
review_title: null

Meta-review: metareview: The papers recognizes an important open question in GNNs: expressiveness-complexity tradeoff. Current more expressive GNNs (k-WL equivalent GNNs) are not practical for even small values of k, and several works have found great empirical success in graph learning tasks without highly expressive models. This paper puts forth a more “fine-grained ruler,” which can more gradually increase expressiveness to investigate the expressiveness-complexity tradeoff. 

The paper addresses an important problem of going beyond 1-WL, however, in such a manner such that expressivity is improved in a progressive way while runtime is still manageable. Experimental results on graph classification and substructure identification as well as regression Zinc12k are promising.

However, the committee has concerns on the presentation of the paper. The authors are suggested to make the paper more accessible by providing more high-level descriptions and interpretations of the results. 
confidence: Less certain
Decision: Accept