Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors designed a GNN-based framework for subgraph counting. Previous exact/heuristic methods are often slow, given  an NP hard problem. There are several key ideas: 1. canonical partition, 2. heterogeneous message passing, and 3. gossip correction. Extensive experiments are conducted to evaluate the effectiveness of the proposed approach.
strength_and_weaknesses: Strength:

1. Experimental analysis (including those in appendix) is extensive. Additional scalability study / q-error analysis present new insights.

2. The idea of canonical partitioning is novel to me.

Weakness:

1. Apart from exact methods, there are also many recent sampling based estimation methods. Sampling-based methods are not exact, but are significantly faster and often have theoretical guarantees. Some discussion or even comparison to this line of work is needed.

[1] Bressan, Marco, Stefano Leucci, and Alessandro Panconesi. "Faster motif counting via succinct color codingand adaptive sampling." ACM Transactions on Knowledge Discovery from Data (TKDD) 15.6 (2021): 1-27.
[2] Wang, Pinghui, et al. "Efficiently estimating motif statistics of large networks." ACM Transactions onKnowledge Discovery from Data (TKDD) 9.2 (2014): 1-27.

2. Traditional methods like VF2 runs on CPU, which is not exactly a fair comparison to GNN methods which runs on GPUs. There are also some GPU-based exact methods [3]

[3] Lin, Wenqing, et al. "Network motif discovery: A GPU approach." IEEE transactions on knowledge and dataengineering 29.3 (2016): 513-528.

3. There are also some newer GNN-based baseline [4].

[4] Liu, Xin, and Yangqiu Song. "Graph convolutional networks with dualmessage passing for subgraph isomorphism counting and matching." Proceedings of the AAAI Conference onArtificial Intelligence. 2022.

4. It would be more beneficial if the authors can demonstrate some case work--- how reduced error translate to accuracy in downstream tasks that makes use of such counts? While it is certainly good that MSE is reduced, e.g. from 1 to 0.6, it is not intuitive how significant is such reduction.
clarity,_quality,_novelty_and_reproducibility: The paper is well written. There is some novelty in the proposed idea.
summary_of_the_review: In short, i think the strengths slightly outweigh the weaknesses.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a deep learning model for the task of subgraph counting. This is a challenging algorithmic problem and a well-known #P problem with applications in biology and social science. Deep learning approaches for subgraph counting have been proposed before, but the model presented by the authors improves both in the accuracy and, most notably, in scalability over existing approaches.
strength_and_weaknesses: Strengths:
- Improved performance for a well-studied, relevant problem in the graph theory / network analysis literature
- There is some novelty on the proposed SHMP module
- Paper is well-organized and the visuals are very useful for understanding the proposed method

Weaknesses:
- It is not clear how the improved performance in MSE translates to better results in practice. Why should a practitioner care that the proposed method is more accurate? Is there, for instance, a case study where the proposed approach leads to new biological insights?
- It is not clear why the authors decided to present squared error as a distribution in Figure 5. I think it would be more informative to see raw squared error numbers, as they present in the rest of the paper.
- No comparison in terms of runtime to DIAMNet
- Many typos across the paper 
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is clear overall. The problem, competing methods, proposed approach, and experiments are clear to me.
Quality: The manuscript would benefit from proof-reading to fix the numerous typos, which start at the first sentence in the abstract and end at the next-to-last sentence in the conclusions. The technical quality is below average.
Originality: In general terms, the idea of breaking down the subgraph counting problem into subproblems has been explored before (see, for instance, all the work in color-coding algorithms). However, I believe that there is novelty in the particular way in which the authors partition the graph.

summary_of_the_review: See my comments above. Overall, I believe this paper would make a fine addition to the conference and to the subgraph counting literature.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the problem of solving the subgraph counting problem using approaches based on neural networks. The proposed method leverages canonical partition to decompose the considered problem into subproblems, and the entire counting is further calibrated by gossip correction balancing homophily and antisymmetry. Experimental studies are provided to support the proposed designs.

strength_and_weaknesses: Strength:

The proposed ideas are reasonable. The identified example for showing the expressiveness of SHMP is particularly interesting. Most of the sections are well-written and easy to follow. Source codes are provided through external links. 


Weaknesses:

- W1: The proposed method is reasonable but does not address the fundamental challenge in subgraph counting: the problem is still computationally hard after fixing a pair of nodes or a certain order of the nodes. That is, the acquired subproblems are in general as hard as the original problem. In this regard, the methods of canonical partition and gossip correction seem simplistic. 

- W2: The theoretical contribution is not strong enough, as there is no formal analysis other than one example. It would be better to justify the model expressiveness in a formal way. In addition, the results in Sec 4.2 are pretty straightforward. 

- W3: The experiments could be improved in the following aspects:
  - Given the nature of the proposed method, the performance seems to depend on the node indexing schemes. Such an issue should be investigated at least in experiments.
  - To justify the statistical significance of the learning performance, one should provide the robustness over the testing set (e.g., std) as well as the robustness over multiple individual trainings (e.g., cross-validation), which are required to rule to out the cases where a) the average error is low but the standard deviation is overly high and b) the trained model is accidentally good. 
  - To make it possible to have an in-depth understanding of the results, it is better to show the exact counting results rather than MSE. 
  - The hyperparameter P seems important, and therefore, it would be better to carefully study its impacts in experiments.
  - One of the common practices is to select fixed query graphs, and then examine the performance; this paper lists a collection of query graphs, but it is not completely clear to me how they form the training-testing sets. Since this paper involves existing methods in experiments, it could be better to follow the exact settings in those papers, which will make the comparison clearer.
  -The paper mentions pretraining but not training, which is a little bit confusing.

- W4: Some minor comments:
  - What does it mean by “combinatorially long runtime”?
  - The paper claims that their approach can easily support graphs with node features, which, however, seems non-trivial. A small experiment can be included to support such a claim.
  - Some notations in Sec 4.1 are not well-defined.

clarity,_quality,_novelty_and_reproducibility: The clarity is good, but the quality and novelty are less satisfactory.

The reproducibility could be better supported by showing the robustness of performance.

summary_of_the_review: This paper has some interesting ideas, but the overall contribution is not significant. The experiments need to be more convincing.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper presents a new algorithm, DeSCo, for subgraph counting in large graphs. The new proposed algorithm works in three stages. It first builds a canonical partition to reduce the problem from the entire graph to small subgraphs. Then it uses a novel subgraph-based GNN approach to improve expressiveness and finally a gossip correction phase is used to improve the accuracy of the model.

Overall, the paper introduces some nice new ideas and it presents some interesting results but the paper still has some drawbacks that should be addressed before publication.

First, the experiments are not fully convincing and they are run only on a small dataset. As a comparison, the previous paper in the topic analyze graphs larger by 3 orders of magnitude.

Second, there have been important advances in the sampling based estimation methods(for example the one presented in Bressan "Efficient and near-optimal algorithms for sampling connected subgraphs". ACM STOC 2021) that are not discussed in the paper but that theoretically should lead to better accuracy.

Overall, the paper is interesting and contains some nice ideas but it is not ready for publication in the current state.
justification_for_why_not_higher_score: The paper shows improvements for a very narrow task and do not consider the most advanced techniques.
Decision: Reject