Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper focuses on generalizing graph neural networks to model higher-order structures. It proposes a new message passing scheme operating on regular cell complexes. The induced models, called CW Networks, generalize and subsume the message passing simplicial networks (MPSNs) which operate on simplicial complexes, and are proved more powerful than the WL test and in some cases not less powerful than the 3-WL test. 



main_review: The paper is well written. It makes a comprehensive theoretic analysis of the proposed model as well as a thorough empirical study. The concept of using cell complexes seems to be a natural but novel extension of simplicial complexes and has some intuitive advantages on molecular datasets (with a lot of rings). The experimental results are also quite good compared to other recent models. I think it is already in good shape and ready for publication. 

As to the negative points, the authors actually already indicated the limitation of the method in the paper, i.e. the high computational complexity on more general large graphs, which would impede the applicability of the model. 

Another minor problem may be the experiments of long-range interaction. The synthetic data only contains chordless rings and it seems all nodes are in the same rings. That may be not a general case, or we can say it just covers one case of long-range interactions. To make the experiments more convincing, maybe in addition to the central rings there should also be some associated branches? 

I have also another question for the authors: if we pre-process the graphs to decompose them into nodes, edges, rings, and use these elements as nodes to form one heterogenous graph, would a GNN on that graph be equal to the cellular message passing to some extent?


limitations_and_societal_impact: No major negative social impact.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper presents an extension of the message passing simplicial network based introduced in [4] on cell complex. The authors first introduce background on regular cell complex. They present an extension of the Weisfeiler Lehman test that generalises the simplicial WL from [4] to Cellular WL and give theoretical results about the power of this new test. Then they introduce CW Networks which is a natural extension of message passing GNN to message passing on cells and show that their architecture is permutation equivariant. Finally, they show on synthetic benchmarks and real-world graphs that their architecture achieves better performances.
main_review: 1- The idea of lifting graphs to higher order representation is interesting but not new and the authors should clarify it: [34] already showed that the expressive power is increased when dealing with high-order tensor representations of the graphs with linear layers. 

2- Since Cellular WL add a lot of information, Theorem 13 is not really surprising. Indeed, the analysis made in Section 3 is rather misleading. The interest of the various WL tests is to show the trade-off between the complexity of the algorithm and its expressive power. 1-WL is less complex than 3-WL and so on but you gain in term of expressiveness.  This is the main motivation for comparing the expressive power of a GNN with the k-WL test. See [34], or Waiss Azizian, Marc Lelarge. Expressive Power of Invariant and Equivariant Graph Neural Networks, ICLR 2021, for a general overview about GNN and WL tests. In Section 3, the authors completely ignore the complexity part. For example, if I understand correctly, the clique complex lifting will include the information about all cliques in the graph which might be very costly to compute, hence Corollary 14 is just telling that if you have access to this information you can do better than a very simple algorithm. It is clearly true but not very interesting.

3- The authors mention the complexity of their GNN on page 6 and write that under some conditions the complexity is "linear in the size of the input complex". But how big can this size of the input complex be in term of the size of the graph?

4- In their Theorem 17, the authors show that CW Network layers are cell permutation invariant. Does it imply that the GNN is graph permutation invariant?

5- It seems that the authors only look at graph embedding with their CWN. Is it possible to obtain node embedding by modifying the READOUT function?

6- In the experiment section, it would have been nice to compare CIN with other algorithms having access to the same information as CIN. Since, the authors compute all the rings in the graph for their CIN, how is the perfomance of a standard GNN improved if we add the statistics of the rings in addition to the embedding computed by the GNN? Such result would allow to demonstrate whether the improvement seen in the paper is due to the new architecture or to the new features added. Similarly, you can probably increase the performance of the WL kernel by adding this new feature to get very good results.
limitations_and_societal_impact: OK
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Recently, there have been several attempts to put higher-order structures on graphs and perform message passing over these structures. One example is the Message Passing Simplicial Networks proposed in e.g, ref[4]. The present paper extends the higher-order structures from simplicial complexes (SCs) to regular cell complexes (also known as CW complexes), or more precisely, generalizes the Simplicial WL of ref[4] to a Cellular WL (CWL). Both theoretical understanding, and experimental studies of CWL are presented. Specific contributions include: 

(1) To obtain a CW complex from a graph, the paper introduces a ``cellular lifting map", and shows a skeleton-preserving lifting map gives rise to a CWL that is at least as powerful as standard WL (Weisfeiler-Lehman) in graph isomorphism testing. It also gives examples of specific natural lifting maps (which includes the previous SWL in [4] as a special case) that is at least as powerful as the so-called 3-WL. 

(2) It describes and implements a CW network using a lifting map that attaches 2-cells to all induced cycles in the input graphs. This architecture (CWN) makes sense especially for molecular graphs applications (in capturing both the covalent bonds and chemical rings). 

(3) It presents various experimental results on synthetic and real datasets, which show that a specific instantiation of CWN, called CIN, can both differentiate certain hard cases for graph isomorphism testing (e.g, 4-regular graphs), comparable or better performance on TUDatasets, and better performance in molecular benchmark datasets. 

main_review: I want to thank the authors for their responses to my questions in the review and during the discussion period. Please add a discussion/clarification of Theorem 15 as discussed. I maintain my score of the paper. 

See the above for the summary of the paper and its contribution. 

** strength of the paper: 
(1) Graph neural networks (especially message passing graph networks) have received great attention in recent years. Recently there has been much interest in message passing over higher order structures, mostly to increase the expressiveness power of graph networks. Using CW complexes as in this paper is more flexible (e.g, filling induced cycles by 2-cells) than using simplicial complexes. The use of CWL is both natural and useful in practical applications. 

(2) The authors present several theoretical results on CWL and CWN. The formulation of lifting map is interesting. 

(3) Good empirical studies are presented, with both synthetic datasets to show the expressiveness and real benchmark datasets to see performance improvements. 


** weakness of the paper: 
(a) The development of CWL is a generalization of the simplicial version (SWL, ref[4]). Most of the theoretical results feel incremental compared to the work of ref[4]. (The notion of cellular lifting map is new but perhaps not surprising. I have read the supplement briefly as well, and understand that there are complications / technicality that need to be addressed due to the use of cells instead of simplices. The concept of cellular message passing also exists in ref[24].) If there are significant new ideas, it would be great if they can be articulated. 
Furthermore, just being more expressive than WL is not a very strong theoretical result, especially since CWL is using high-dimensional cells. 

(b) (A minor one:) I like the discussions and theoretical results on expressive power in distinguishing non-isomorphic graphs. There are other ways to increase expressive power, for example, by using more powerful initial node features (say sth. that captures cycle information) or by using node coloring (e.g, the following reference): 
      [Ref]: "Coloring Graph Neural Networks for Node Disambiguation",
      George Dasoulas, Ludovic Dos Santos, Kevin Scaman, Aladin Virmaux, 
      IJCAI 2020. 
It could be good to include a comparison with the approach in the above Ref. 

** overall evaluation: 
Overall, I think this is a solid paper that presented nice studies over a natural object with reasonably convincing experimental results (especially over molecular graphs). The originality is somewhat limited (e.g., when compared to work of Ref[4]). Nevertheless, it is well-written and I enjoyed reading it. 

** other comments:
-- Maybe I missed it in the submission and supplement: how is the ring size $k$ chosen in experiments (especially for real datasets)? Different values of $k$ seem to be used for different applications. Is there a consistent strategy to choose it? 
There is a range of hyperparameters listed in Table 8 in supplement. Why not having $k$ as another hyperparameter? Also, how does the number of hyperparameters compare to other standard approaches, say GIN? 
-- In Definition 1, is "regularity" important for the CW network? Is it needed for any of the results later? 
limitations_and_societal_impact: Adequate
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: In this work, the authors propose a new member of graph neural networks, called CWN, that considers the higher-order structure of graphs. The proposed model leverages the topological properties of cell complexes and establishes a novel hierarchical message passing procedure. The authors demonstrate that the proposed CWN is more powerful than the WL test and can be comparable to the 3-WL test. The proposed model achieves encouraging performance on graphs with complicated structures, e.g., molecules, while it requires a preprocessing step with the tolerable time cost.
main_review: Overall, I like this work because of its solid theoretical analysis, sufficient and convincing experimental results, and detailed supplementary materials. Additionally, in Section 4, the authors connect the proposed method with existing works and highlight its advantages, which further clarifies the contribution of this work to the community.

I only have four suggestions:

1. Line 121: 	“Simplicial WL” -> “Simplicial WL (SWL)”, such that SWL will be understandable.

2. The GWL coloring procedure (the preprocessing step) shown in Figure 3 provides a hierarchical way to extract features from graphs. If my understanding is correct, we can define a graph kernel based on the features and provide a kind of high-order WL kernel accordingly. Could the authors take this potential kernel method as a baseline in the experiment?

3. The introduction of CWN in Section 4 is too brief. It would be nice if the authors can illustrate the molecular message-passing model by a figure — after doing the coloring procedure, how to apply message passing to the coloring result? Maybe the authors can consider using a simple molecule as the graph in Figure 3 and adding a subfigure to it.

4. Reading this paper is challenging for the readers without topological background. Section 2 is not a good starting point for such readers. Before showing Figure 1, it would be necessary to add a Figure to illustrate topological space X, its partitions, and cells, with sufficient symbols and notations, such that it will be much easier to understand the concepts in definition 1.
limitations_and_societal_impact: I did not find any obvious or potential negative societal impact of the proposed work.
review_title: null

Meta-review: This paper proposes a new graph neural network framework allowing message passing for high-order structures. The paper provides clear theoretical foundation and also delivers convincing empirical evidence. Although it was mentioned that the contribution is a bit incremental over existing work [4,24], overall the paper was positively/passionately accepted. One reviewer did raise strong concern about the presentation of the paper. But based on the paper and all other reviewers' opinions, the presentation concern does not seem general. Therefore, the AC recommends the paper to be accepted.   
Decision: Accept (Poster)