Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work studies the counting ability of subgraph MPNN models, and present I^2-GNN to increase the counting ability of subgraph MPNNs. The proposed I^2-GNN is able to discriminate 6-cycles in theory and achieves good performance in molecular property prediction.
strength_and_weaknesses: Strengths:  
(+) This work makes very solid and novel contributions to developing more expressive graph neural network models. The idea of improving the subgraph counting ability by assigning different identifiers to the root node is interesting and elegant.  
(+) Comprehensive theoretical analysis and empirical studies are presented to show the effectiveness of the proposed I^2-GNN model.  
(+) The writing of this paper is very clear and well-organized.  

Weaknesses:  
(-) Some experimental settings are unclear to me in graph substructure counting. For experiments in section 6.2, the prediction targets are cycle or graphlet counts, which are discrete numbers. Do GNN models output continuous numbers to approximate discrete targets and the MAE is evaluated between them?
clarity,_quality,_novelty_and_reproducibility: This paper clearly clarifyies the novelty of the proposed method. The quality of this work is solid and strong in the aspects of both theory and experiments. Source codes and detailed experiment settings in the appendix are provided to ensure good reproducibility.
summary_of_the_review: Overall, this work proposes a novel method in enhancing the representation ability and counting power and of graph neural networks. Both the theorical and experimental contributions of this work are strong. I vote for accepting this work.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Message Passing Neural Network (MPNN) is a simple yet efficient class of Graph Neural Networks (GNNs), which have been widely adopted in many previous works. However, it is also known that MPNN has limited representational power due to its simple structure. This paper, in particular, considers subgraph methods. The authors first show that Subgraph MPNNs can count 3-cycles and 4-cycles, but cannot count 5-cycle or any longer cycles at the node level. The cycle counting is important to understand structure since cycles are the basic elements constructing some important substructures. Then, they propose I^2-GNN that can count cycles with lengths less than 7. Based on this, I^2-GNN has a stronger discriminative power than subgraph MPNNs. I^2-GNN outperforms baselines in molecular prediction benchmarks.
strength_and_weaknesses: Strengths

- The proposed algorithm $I^2$-GNN theoretically guarantees the power of counting 6-cycles. This is the first algorithm that can guarantee such power. 

- The algorithm's empirical performances support the theoretical results.


Weakness

- The computational complexity of $I^2$-GNN is proportional to the degree of the graph. So, when the degree follows a power law (a heavy tail distribution), the complexity could be much higher than before.

- The empirical study considers QM9 and ZINC. This could be a limited set. It would nice to consider node OGB data set and classification tasks with cora, citeceer, pubmed. 
clarity,_quality,_novelty_and_reproducibility: The algorithm is novel, and the proof looks correct, although I couldn't check all the details.
summary_of_the_review: This paper has a novel method and its theoretical motivation. However, the experiment section is weak.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new Graph Neural Network architecture enhancing the standard message passing architectures (MPNN). The main idea is to run various MPNNs on rooted subgraphs of the original graph. The authors show that their architecture I2-GNN is more powerful than previous MPNN. They show theoretical results where I2-GNN is able to count longer cycles (3,4, 5 or 6-cycles) and paths (3 or 4-paths). They also show some theoretical limits of I2-GNN. In their last section, they conduct experiments to substantiate their claims.
strength_and_weaknesses: The theoretical analysis made in this paper is rather convincing.
The main weakness is the special focus on counting (short) cycles and paths. The expressive power of MPNN can be improved by adding extra-features like it is done in this paper but it is not clear that focusing on cycles and paths is actually the best use of resources. Indeed, the experimental results on real datasets are quite disappointing in this respect as CIN seems to outperform the I2-GNN on ZINC and ogbg-molhiv.
clarity,_quality,_novelty_and_reproducibility: The paper is well written. If possible, I would recommend to move the discussion about the complexities of the various architecture in the main part of the paper.
The code is provided but I did not run it.
summary_of_the_review: The paper presents interesting theoretical results but experimental results are weak.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors of this paper propose a new Subgraph MPNN architecture, called $I^2$-GNNs, that can count up to 6-cycles in contrast to other Subgraph MPNNs which cannot count such long cycles. For each rooted subgraph centered at node $i$, they construct d(i) subgraphs, where d(i) is the degree of the center node, defining a mapping between the generated subgraphs and the neighbors of the root node. Then, they assign a unique identifier to the center node $i$, and another unique identifier to one of the neighbors of the center node, for each generated subgraph. They use MPNNs in each subgraph to construct the graph's final representation, followed by a readout layer. They evaluate their model in cycle counting tasks as well as in molecular property prediction benchmarks, achieving competitive performance.

strength_and_weaknesses: Strengths: 
- The authors of the paper present some new theoretical results regarding Subgraph MPNNs. Specifically, they prove that the proposed models can count 3-cycles and 4-cycles, but cannot count 5-cycles or any longer cycles.

- The authors also present a new Subgraph MPNN architecture that is more powerful than existing Subgraph MPNNs. They also prove that it can count all cycles with length less than 7 which is important for real-world applications (e.g., identifying benzene rings).

- The proposed models achieve competitive performance in graph classification and regressions tasks (QM9, ZINC and ogbg-molhiv) and demonstrate increased expressiveness in discriminating non-isomorphic graphs and in substructure counting.

Weaknesses: 
- My main concern with this paper is with regards to the novelty of the work, as in essence, it proposes to add an extra identifier for each pair of nodes. There are many works that add unique node identifiers in GNNs to increase the expressive power of the models [1,2] and in the current paper, a proper discussion of these approaches is missing. Also, a comparison with [3,4] would be interesting, as they also build more expressive GNNs with extra node features.

- The proposed model generates a new subgraph for each edge in the original graph, and therefore the computational complexity is higher than that of other subgraph MPNNs. As the authors mentioned, the proposed model is evaluated only on graphs with a small average node degree. I would suggest the authors discuss how the proposed approach can be applied to graphs with high average node degree and also evaluate their model on such graphs, for example, in the TUD benchmark [5]. 

[1] Andreas Loukas. How hard is to distinguish graphs with graph neural networks? In Advances in Neural Information and Processing Systems (NeurIPS), 2020.\
[2] Andreas Loukas. What graph neural networks cannot learn: depth vs width. In ICLR, 2020.\
[3] Dwivedi, Vijay Prakash, et al. "Graph neural networks with learnable structural and positional representations." arXiv preprint arXiv:2110.07875 (2021).\
[4] Wijesinghe, Asiri, and Qing Wang. "A New Perspective on" How Graph Neural Networks Go Beyond Weisfeiler-Lehman?"." International Conference on Learning Representations. 2021.\
[5] Morris, Christopher, et al. "Tudataset: A collection of benchmark datasets for learning with graphs." arXiv preprint arXiv:2007.08663 (2020).
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is well written, and the idea is clear and well presented.\
Quality: The quality of the paper is high.\
Novelty: The paper has some novelty, as it enhances Subgraph MPNNs with a new strategy of node pair identifiers, but the general concept of node identifiers in GNNs has been studied in previous works. Also, a more detailed related work, discussing these approaches is missing.\
Reproducibility: The experimental setup is well described and also the source code is provided by the authors. 

summary_of_the_review: The proposed method is technically sound, well written, and leads to performance gains on some molecular property prediction datasets. However, I think that the main idea of incorporating identity node features has been studied in the past thoroughly and the paper does not discuss these methods in details. Specifically, I would suggest the authors do the following:
- Discuss more and extend the related work with other similar approaches that incorporate extra node features/identifiers and explain why the current approach is more suitable than the others.
- Compare with more baselines and evaluate the model in more benchmarks (see above).
- Explain how the current approach can be applied to dense graphs, where the average node degree is high, probably by employing some sampling strategies.

I would be happy to increase my score if my concerns are well addressed.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Message-passing neural networks (MPNNs) and their extensions (Subgraph MPNNs) have inspired state-of-the-art models for graph data; however, their counting power is still limited and it is known that Subgraph GNNs cannot count cycles with more than $4$ nodes.

To boost the counting power, this paper extends the idea of having a single root node identifier in Subgraph GNNs to two identifiers for a (root node, neighbour) pair resulting in the proposed I$^2$-GNN model.

I$^2$-GNN has the following properties:
1. It can count all cycles of length at most $6$,
2. It has linear space and time complexity provided the node degree is bounded,
3. It achieves competitive results on open benchmarks compared to existing models.

___
strength_and_weaknesses: \
**Strengths**

\+ The paper is well-organised, well-written, and the problem of counting power is well-motivated.

\+ The proposed method is potentially scalable to large-scale real-world data and potentially useful for real-world chemical data involving cycles of length at most $6$ (e.g., benzene rings).

\+ Under certain conditions (e.g., bounded node degree), the proposed model is the first linear-time GNN model to count $6$-cycles.


**Weakness**  

The only major weakness of the paper is the lack of positioning/comparison of the idea of using multiple identifiers for node pairs (of edges) with labelling tricks [1] (used in the context of link prediction)

[1] Labelling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning, In NeurIPS'21

___
clarity,_quality,_novelty_and_reproducibility: \
**Clarity**

The paper is generally clearly written.

Explaining what the accuracies mean in Table 1 and their extreme differences ($0\%$ vs. $100\%$) in Table 1 would improve the clarity (especially for non-expert readers).

\
**Quality**

The paper is technically sound and both the theory and the experiments support the claims.

Since the complexity depends on the node degrees, an inference time and number of parameter comparison on real data (e.g., datasets of tables 4 and 5) would strengthen the quality of the paper.

Since benzene rings were used as an example real-world scenario of counting power, performing experiments (or highlighting if already performed) on real data with benzene rings would also strengthen the soundness of the claims.


\
**Novelty**

The proposed model is the first linear-time GNN model to count $6$-cycles.

The novelty of the work can be further strengthened by positioning the contributions with respect to GNNs for link prediction which also exploit subgraphs around each edge.

A discussion of the differences between the expressivity of labelling trick vs. I$^2$-GNNs would further strengthen the contributions.

1. Labelling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning, In NeurIPS'21
2. Link Prediction Based on Graph Neural Networks, In NeurIPS'18



\
**Reproducibility**

The main part and the supplementary part include enough material, e.g., proofs of theorems, dataset details, baselines with references, hyperparameters, ablation study, for an expert to replicate the results of the paper.

___
summary_of_the_review: While the paper is well-motivated and the claims are well-supported with theory and experiments, positioning with respect to relevant prior work can further strengthen the contributions.
___
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work studies the counting ability of subgraph MPNN models, and present I^2-GNN to increase the counting ability of subgraph MPNNs. The main idea is to run various MPNNs on rooted subgraphs of the original graph. For each rooted subgraph centered at node i, they construct d(i) subgraphs, where d(i) is the degree of the center node, defining a mapping between the generated subgraphs and the neighbors of the root node. Then, they assign a unique identifier to the center node i, and another unique identifier to one of the neighbors of the center node, for each generated subgraph. They use MPNNs in each subgraph to construct the graph's final representation, followed by a readout layer. The proposed I^2-GNN is able to discriminate up to 6-cycles in theory and achieves good performance in molecular property prediction. In contrast, the other Subgraph MPNNs cannot count such long cycles. Based on this, I^2-GNN has a stronger discriminative power than subgraph MPNNs. I^2-GNN has linear space and time complexity provided the node degree is bounded, and outperforms baselines in molecular prediction benchmarks. The reviewers raised concerns including comparison of the idea of using multiple identifiers for node pairs (of edges) with labelling tricks, justification of novelty given other expressive GNNs, computational complexity and scalability to denser graphs, the special focus on counting (short) cycles and paths, need for additional datasets. The authors did a good job addressing reviewers’ comments and adding suggested experiments, resulting in overall positive assessment of reviewers after the response period.
justification_for_why_not_higher_score: Modest novelty.
justification_for_why_not_lower_score: The reviewers raised concerns including comparison of the idea of using multiple identifiers for node pairs (of edges) with labelling tricks, justification of novelty given other expressive GNNs, computational complexity and scalability to denser graphs, the special focus on counting (short) cycles and paths, need for additional datasets. The authors did a good job addressing reviewers’ comments and adding suggested experiments, resulting in overall positive assessment of reviewers after the response period.
Decision: Accept: poster