Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The main contribution of this paper is Cy2C-GNN, a model that can distinguish pairs of isomorphic graphs that 1-, 2- and 3-WL tests cannot. The proposed approach identifies the cycle basis of the graph and then constructs complete subgraphs consisting of the nodes of each basis element. The clique adjacency matrix is created from these subgraphs. Then, the model produces some features by performing a neighborhood aggregation step using the clique adjacency matrix and these features are concatenated with features emerging from multiple standard neighborhood aggregation steps. The proposed model is evaluated on standard graph classification datasets where it achieves competitive performance with state-of-the-art methods.
strength_and_weaknesses: Strengths:

- The proposed method is relatively simple, but still it is more powerful than several standard GNNs since it can distinguish graphs that WL and its variants cannot.

- The proposed approach seems to perform relatively well on the considered graph classification datasets. It outperforms all the baselines on 8 out of the 16 datasets.

Weaknesses:

- Since the authors claim that the Cy2C-GNN model can distinguish graphs that standard or even more powerful GNNs cannot distinguish, one would expect the authors to empirically verify that. There exist datasets that are created to measure the expressiveness of GNNs such as the Circular Skip Link dataset [1], and the EXP and CEXP datasets [2]. I would suggest the authors also evaluate the proposed model on these or other similar datasets. 

- Even though the underlying idea is relatively simple, the paper is difficult to follow and contains mathematical notation that takes quite a bit of time to parse. I would thus recommend the authors to try and simplify the presentation. 

- The main theoretical result (Theorem 4.3) shows that if one graph has a chordless cyclic element in its basis of different length than all the chordless cyclic elements of the basis of another graph, then the proposed method can distinguish the two graphs. Can all those graphs also be distinguished by some higher-order variant of WL (i.e., the $k$-WL algorithm for some $k>1$)? Are there any real-world problems which require such graphs to be mapped to different embeddings? What is also the intuition behind constructing a complete subgraph consisting of the nodes of a cyclic element?
 
- The authors discuss in details the computational complexity of the proposed method. However, they do not provide any empirical results. I would suggest the authors also measure the running time of the method (including preprocessing steps such as computing the set of cycles that form a basis for cycles of each input graph). Since the authors have evaluated Cy2C-GNN on REDDIT-M-5K, which contains large graphs, I would guess that the running time is not prohibitive.

- The writing is not very clear. There are several grammatical and syntactic mistakes, while notation is not always clearly defined (for instance, in Lemma 4.1, what do symbols $\cong$ and $\not \cong$ denote?). Therefore, the considered manuscript lacks clarity and I suggest the authors work on improving that.\
page 1: "The graph data set The adjacency matrix" --> The sentence does not make sense\
page 5: "to each nodes" --> "to each node"\
page 7: "3 social network dataset" --> "3 social network datasets"\
page 7: "3 small molecules" --> "3 small molecular datasets"

- Are there any results that link universal covers with stable colorings that emerge from the WL algorithm?

- Tables 1 and 2 have too small font size, and are not readable when printed. Please increase the font size.

[1] Murphy, R., Srinivasan, B., Rao, V., & Ribeiro, B., "Relational pooling for graph representations", In International Conference on Machine Learning, pp. 4663-4673, 2019.\
[2] Abboud, R., Ceylan, I. I., Grohe, M., & Lukasiewicz, T., "The Surprising Power of Graph Neural Networks with Random Node Initialization", In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pp. 2112-2118, 2021.

clarity,_quality,_novelty_and_reproducibility: As discussed above, the paper is generally not well-written and it is not very easy to read. The authors provide enough details for the reader to reproduce the reported results. The quality of the paper is good, but as discussed above there are several weak points. There is some novelty in the work and the method is of some interest.

summary_of_the_review: In my view, the paper seems to be proposing an interesting contribution for the graph representation learning community. The quality of the paper is good, and a novel theoretical results is presented. The proposed method is simple and it seems to perform well on standard datasets. However, I have some concerns mainly with the clarity of the paper, the motivation behind some parts of the method, the significance of the theoretical result, and the empirical evaluation.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this article, the authors propose to improve graph neural networks by characterizing and processing the graph cycles using universal covers, which is motivated by a characterization of the classes of graphs that usual graph neural nets can distinguish. More precisely, they provide a simple yet efficient procedure for turning cycles into cliques and for processing clique adjacency matrices with new graph neural network layer combined with standard aggregation schemes. They finally show improvements over competitors over several real-world data sets. 
strength_and_weaknesses: Strengths:
---The paper is well written and easy to follow
---The experiments are quite exhaustive
---To my knowledge, Theorem 3.3 is new and interesting 

Weaknesses:
---The method sounds a bit complicated. It would be nice to better motivate the use of universal covers: as far as I understand, extended persistent homology would be enough to detect and process such cycles in separate layers. Thus, it would be nice to either discuss or compare more to this alternative.
---In terms of architecture design, the proposed neural net seems a bit incremental
clarity,_quality,_novelty_and_reproducibility: The paper is quite clear, and the theoretical results looks quite original. Practically speaking, the new proposed architecture is quite incremental though.
summary_of_the_review: Overall, the paper looks good to me, even though I am no expert in graph neural networks.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a new graph neural network architecture termed Cycle to Clique Graph Neural Network (Cy2C-GNN). The new architecture is simple in that it just adds a separate layer in standard graph neural networks, and thus it maintains the efficiency of simple GNNs such as GCN; at the same time, the new architecture is based on graph theoretic considerations and is provably more powerful than standard GNNs at distinguishing certain isomorphism classes of graphs. The authors also empirically demonstrate that Cy2C-GNN can efficiently and reliably represent cyclic structures of graph datasets. Over a range of benchmark datasets Cy2C-GNN achieves superior or comparable graph classification performance than the current state-of-the-art methods.
strength_and_weaknesses: The paper is well motivated and nicely written. The authors provide solid theoretical justifications for the proposed Cy2C-GNN architecture. I liked the fact that this architecture is provably more powerful and simple at the same time, which makes it very accessible to practitioners. I also liked that the authors discuss the limitations of the architecture in the conclusion.

The weak part of this paper is the empirical evaluations. It seems that the authors are comparing the best performance between baseline models and Cy2C-GNN models. Based on the results reported in Table 1 and Table 2, it is difficult to understand the effect of the additional neighborhood aggregation layer that uses the clique adjacency matrix. For example, for PROTEINS(FULL) in Table 1, the reported baseline GNN is GAT-3 whereas the reported Cy2C-GNN is Cy2C-GCN-4. Both methods use different GNN architecture and also different number of layers (please correct me if I am wrong), therefore it is difficult the understand what exactly had led to the performance gain. The results would be more informative if the authors report results in the setting where the only architectural difference is the additional clique averaging layer (and the final layer of course).
clarity,_quality,_novelty_and_reproducibility: Clarity is good. The authors can further improve the clarity of the paper by referring to where in the appendix the definition of certain graph theoretic term is provided. For example, cycle basis is defined in Definition A.31 and the author could refer to Definition A.31 when the term first appeared in the main text.

Quality is good, the empirical experiments section can be improved.

Originality is good. I think the idea that uses cliques from cyclic substructures of the graph to perform neighborhood aggregation is novel.
summary_of_the_review: The paper proposes a simple and novel graph neural network architecture based on universal covering graphs. The new architecture is backed by theoretical insights and also it is shown empirically to achieve state-of-the-art graph classification performance. Even though I think the empirical evaluations are not good enough, overall the strengths of this paper oversights its weaknesses.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a new graph neural network architecture termed Cycle to Clique Graph Neural Network (Cy2C-GNN). The main contribution of this paper is Cy2C-GNN, a model that can distinguish pairs of isomorphic graphs that 1-, 2- and 3-WL tests cannot. The authors characterize and process the graph cycles using universal covers, which is motivated by a characterization of the classes of graphs that usual graph neural nets can distinguish. More precisely, they provide a simple yet efficient procedure for turning cycles into cliques and for processing clique adjacency matrices with new graph neural network layer combined with standard aggregation schemes. The proposed model is evaluated on standard graph classification datasets where it achieves competitive performance with state-of-the-art methods. The authors did a nice job in response such as adding additional experiments suggested by reviewers (e.g., on classifying "Circular Skip Link dataset"), and clarifying mathematical expositions. Overall, the reviewers’ attitudes are positive regarding the contribution of this paper. AC recommends the authors more completely address reviewer’s remarks on relations with higher-order variant of WL. 
justification_for_why_not_higher_score: AC recommends the authors more completely address reviewer’s remarks on relations with higher-order variant of WL. 
justification_for_why_not_lower_score: The authors did a nice job in response such as adding additional experiments suggested by reviewers (e.g., on classifying "Circular Skip Link dataset"), and clarifying mathematical expositions. Overall, the reviewers’ attitudes are positive regarding the contribution of this paper.
Decision: Accept: poster