Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a statement that subgraph matching can be degenerated to subtree matching and provide proof. Based on this degeneracy property, the authors propose a matching method that utilizes GNN to model subtrees. Also, they adopt GNN to learn node representations to boost the performance of matching.
strength_and_weaknesses: **Strength:**
1. The idea of degenerating subgraph matching to subtree matching is novel. The theoretical study is interesting, regarding existing graph matching learning papers are usually empirical.
2. The proposed method improves performances on 7 experimented datasets, some by a substantial margin.
3. The empirical results show that GNNs tend to capture the data distribution divergence, and have bad performance on evenly distributed data, motivating further research.

**Weakness:**
1. The degeneracy property can be broken by simply inserting or removing an edge, so the model can be easily attacked and may not be robust to noise.
2. The ablation study of GNN shows that the improvement is mainly from the GNN module. Also, the paper does not show the subtree modeling's effect on performance improvement, such as demonstrating recall on experimented datasets.
clarity,_quality,_novelty_and_reproducibility: This work may not possess good reproducibility if the code is not released.
summary_of_the_review: The paper proposes a novel idea on the degeneracy property of subgraph matching, and the tree-degeneration fits the way of aggregation of GNN. The theoretical results seem novel and interesting. Empirical results show the shortcomings of GNN, which is significant for future research.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This main contribution of this paper is that it provides an idea and corresponding theoretical proof about degenerating subgraph matching problem to subtree matching with the help of Graph Neural Network.
strength_and_weaknesses: Strength: Theoretical proof and support for each claims mentioned. 

Weakness:
1. The datasets used in the experiments are relative small and old. It will be interesting to see the performance of the proposed method on more recent datasets, such as ogb (https://ogb.stanford.edu/)
2. Training-test split may have large impact on the performance, e.g., on Mutag and Protein. Please specify the details (e.g., random seeds, how many time the 5-fold CV was run)
3. It is unclear if the proposed method work for graphs containing edges/nodes with continuous attributes. 









	 From the examples above, they have the same chordless cycle ABC and ACD

clarity,_quality,_novelty_and_reproducibility: The proposed idea is interesting and novel for certain types of graphs. 
Writing can be improved.
1. The usage of the word “neighbor” for different scenarios at the same time made me confused. For example, in section 4: “Motivated by Hall’s marriage Theorem 3.1, we develop an efficient algorithm to address the perfect matching procedure. A straightforward solution is to randomly select a subset W from the given set of neighbors, N(q), and count whether the corresponding neighbors of W, i.e. N(W), have more elements than this subset. After repeating this process multiple times for all node pairs, we obtain a perfect matching when no instance violates the criterion.”
2. Figure 1 perfect matching table is a bit confusing. 

summary_of_the_review: This study proposes an interesting method with theoretical proof. Experimental results are good. Running experiments on the suggested datasets will strengthen the paper. Writing can be improved. The paper lacks discussions about the application of the proposed method to graphs with continuous node/edge attributes.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper identifies a degenerated case of subgraph matching, in which it falls to subtree matching. Then, the matching procedure can be implemented by the built-in tree-structured aggregation mechanism on graph neural networks. The paper proposes a new deep learning method for approximate subgraph matching.
strength_and_weaknesses: Strength:
- The proposed idea is novel.
- The experimental results are strong.

Weakness:
- The writing of the paper should be improved.
- Although the paper provides a complexity analysis, the paper should also provide a runtime analysis to compare with baseline approaches. Given that there is an extra operation of converting a graph to a subtree, I assume the proposed method is slower compared to other deep learning based approaches. However, this is not discussed in the paper.
- Although I understand that this approach is proposed for approximate subgraph matching, I believe the paper should at least include some comparisons with exact subgraph matching methods. Please feel free to skip CO-based methods in settings where they are not applicable.
- The paper is kind of overclaiming the theoretical contribution of the paper. The paper relaxes the sufficient and necessary conditions to that of necessary only. However, I didn't find a bound or analysis regarding the error introduced in this relaxation.
clarity,_quality,_novelty_and_reproducibility: I find the proposed idea to be novel.
However, the writing of the paper should be significantly improved.
Concretely, 
- The figures are not clear. For example, Figure 1 has a very brief caption, making the figure very hard to understand.
- Equation 2 is defined very vaguely. T_v^(l) is not defined, should we interpret it as a WL subtree? 
- Definition of "perfect matching" is confusing, "a matching of a graph in which every node of the graph is incident to exactly one edge". Based on the definition of graph matching, we always match a query graph with a target graph. How do we match within a single graph?
summary_of_the_review: Overall, this paper outlines a novel approach for deep learning based subgraph matching. Although I agree with the novelty of the proposed idea, I feel the paper is kind of overclaiming the theoretical contribution of the paper. The paper also needs to evaluate the proposed approach more thoroughly, by including runtime analysis and comparing against exact graph-matching baselines. Finally, the writing of the paper should be improved.
Overall, I think there is significant room for improving this paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper considers the NP-hard subgraph matching problem: given graphs G1 and G2 with G1 having at most as many vertices as G2, is there an injective map from the vertices of G1 to the vertices of G2 that exactly preserves edges? This is NP-hard since if, e.g., G1 is the complete graph on k vertices, then this subgraph matching problem is the same as the NP-hard k-clique problem on the graph G2. This paper develops some necessary conditions for this problem. It shows that subgraph matching can degenerate to subtree matching, and that the latter is equivalent to the polynomial-time-solvable perfect-matching problem on bipartite graphs. This matching procedure is further shown to be implementable by the built-in “tree-structured aggregation mechanism” of GNNs, leading to a linear time complexity in some cases. It is good to see such ML-based approaches to hard CO problems. 

Some of the concerns raised include robustness with respect to the addition or deletion of graph edges, which needs further study. Here is an important classical benchmark problem due to Richard Karp, for the authors to try their algorithms on (and to possibly improve their algorithms). Generate the Erdos-Renyi random graph G = G(n, ½)---i.e., G has n vertices and an edge is added between each pair of edges independently with probability ½. With high probability, the maximum clique size in this graph is around 2 * log_2 n. It is a very interesting problem to construct even a clique of size, say, 1.5 * log_2 n in such a graph. That is, the authors are encouraged to try their method when G1 is the complete graph on k vertices where k = floor(1.5 * log_2 n), and G2 is the random graph G(n, ½) where n is, say, on the order of several thousands. 

The authors are also asked to improve their writing as suggested by the referees.

justification_for_why_not_higher_score: There is work needed on more-classical benchmarks to see how well the method does.
Decision: Reject