Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposed a new algorithm for performing subgraph matching under deep learning framework. To this end, the problem is formulated as a node-level metric learning problem. A main contribution of the paper is to introduce partial order preserving property for the metric and yields significant improvements over existing methods. I believe the paper is above the threshold in general.

However, I have the following concerns about the paper.

1) I see the author conduct the experiment with k up to 10. While this is a rational number for synthetic and small scale graphs, a feasible k can be much larger in other scenarios. I would like to see how the choice of k can be influenced by different datasets and what is the connection.

2) The result of the matching can rely heavily on the quality of the construction of the graphs. However, in real cases, a query graph may be constructed using some heuristic ways (e.g. k-nearest, \epsilon-ball or Delauney in graphics). This heuristic construction of graphs may lead to changes to the topology of the graph. Therefore, I think the authors should present more discussion on how to handle such uncertainty in practice.

3) The way of generating training and testing samples seems naive. In practice, both subgraphs of query and target can have semantic meanings, thus a random sampling of subgraphs cannot fully represent the true distribution. I would recommend the authors consider about more practical cases rather than synthetic ones.

4) What changes were made to the two selected baselines (GMNN and RDGCN) to adapt the subgraph matching tasks? It is necessary to give more details showing how the modifications are made. This can help to better understand the baselines.

5) While the authors claimed that subgraph isomorphism can be defined with both node and edges features, I didn't see any part of the paper handling edge features. Throughout the paper, only node features are considered. While edge features are essentials in a large variety of applications (e.g. drug compound matching, DNA matching), I think missing this portion can greatly limit the contribution of this paper. To me, it also seems that the proposed method cannot be readily extended to edge features. I suggest the authors to at least discuss the feasibility of extending this method to edge features.

I would consider raising the rating if the authors can address the aforementioned questions well.
review_title: A paper with novel idea. Above the acceptance threshold.

final_score: rating: 3: Clear rejection
review_content: 
This paper presents a method to solve the subgraph matching problem based on training a graph neural network to produce embeddings of 10-hop, apparently labelled, node neighborhoods in a way that allow for recognizing subgraph relationships among graphs via dominance relationships among their embeddings.

The results presented in the paper appear occasionally simply too good to be true, while several aspects of the presented method are poorly defined, or totally undefined. Among them the following:

1. Algorithm 1, which provides the main tool to be used in order to answer Problem 1, is defined as returning a subgraph of G_T that is isomorphic to G_Q. However, it is not clear how that is supposed to happen, and the algorithm's pseudocode provides no clue about it. Appendix D revisits this question, and offers that the Hungarian algorithm may be used in case when an explicit matching is desired, yet there is no elaboration on the topic and no results on it.

2. The pseudocode states that a binary prediction is made based on the *average* score of all value of subgraph prediction function f(z_q, z_u); there does not appear to be any way of returning an subgraph as output, apart from this prediction. In itself, the idea that merely taking an average of a binary subgraph prediction function over all node pairs would result in a correct prediction appears simply too good to be true.

3. The paper lacks a sufficient explanation of details regarding this predictive method. There appears to be a threshold t, or perhaps α (both names are used for it) on the magnitude of a violation E(z_q, z_u) on the subgraph constraint among the embedding dimensions of q and u. This threshold is mentioned in Section 2.3 by two names, and then it is never mentioned again. No discussion is offered on what values it has in experiments.

4. Appendix D mentions a sweep over hyperparameters, whose effect is supposed to be shown in Table 4. However, Table 4 shows the accuracy of matching on the ENZYMES data set in an unsystematic manner. No discussion is offered on the threshold parameter. The section on Hyperparameters lists a number of conclusions, which do not appear to relate directly to Table 4.

5. The writing fluctuates several times between the idea of using categorical node features and not using them. Eventually, the matter is left undefined, and the reader cannot tell whether such features are used or not. Section 2.1 leaves the question open. Appendix D comes back to this question, and defines that, with the FastPFP method, a prediction score uses the features matrices of nodes. This is the first time when it eventually becomes apparent that experiments are indeed using node labels all the way, yet the matter is not previously discussed.

6. The size of a k-hop subgraph is not explicitly specified. Section 2.1 suggests that k = 10 in experiments. The value of k is called number of layers. Table 4 in the Appendix also refers to a number of layers. It is not clear whether that refers to k or to a neural network architecture.
review_title: Several aspects poorly defined

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors propose neural network schemes for subgraph isomorphism.  Their main subroutine is a subgraph embedding that is trained to encourage the property that if A is a subgraph of B then the embedding emb(B) coordinatewise dominates emb(A).  Given this subroutine, the paper proceeds by producing an embedding of the neighborhood around each vertex of the original graph, then searching for the embeddings of the query subgraph, again centered at each node.  The results of this computation are then used to guess an alignment between the vertices of the query and (a subset of) the vertices of the target graph.

Strengths of the paper:
* The authors propose the study of this neural subgraph matching problem.  I believe we're past the days in which applying deep learning to a new problem is considered a novel contribution in its own right, but it's still an interesting topic to read about.
* The authors generate training data for the system by sampling subgraphs from a given graph.  This has the advantage of tailoring the subgraphs they find to the input distribution, and provides a clean way to structure the training data.  They also do some nice study of alternate sampling approaches at inference, to test sensitivity to the particulars of the data generation scheme.
* The authors propose a particular approach to the embedding learning based on geometric set embeddings that is well chosen for this problem, and seems to perform well in practice.  
* The post-inference alignment problem is a way to bring significant knowledge about the problem domain into the solution, after the learned part of the system completes.

Weaknesses of the paper:
* I feel that the runtime isn't well described or analyzed, including in Section F of the supplementary material appendix.  Without the coordinatewise constraint on embeddings, it would be natural to implement the matching of each query subgraph using nearest neighbor search.  However, I didn't see discussion of how to perform the lookups efficiently in the proposed scheme.  Scanning the entire database of target subgraphs doesn't seem ideal.
* I don't have a good sense of whether an 18% improvement from a general graph matching solution to this tailored solution for subgraphs is a significant advance or not.
* I felt that the details of the sampling scheme and the alignment algorithm would result in significant changes to the performance of the system, but I didn't see detailed discussion of these issues.

Questions:
Q1: Could the authors speak a little to efficiently querying for the best dominating target subgraph at runtime?
Q2 The embedding constraint has the interesting property that it is not invariant under rotations.  Do the authors have any observations about whether this results in difficulties in the learning?
Q3: In section 3.2, you comment "This benefit is a result of avoiding the loss of information when pooling node embeddings and a better inductive bias stemming from order embeddings."  Could you describe the evidence in support of this hypothesis?
Q4: Why is it that in Table 2, FastPFP performs better than NeuroMatch for synthetic data?  It's not a concern for the overall eval, but NeuroMatch by design seems as though it should perform well in this setting.

Other comments:
* I suggest introducing the set embeddings (McFee & Lanckriet '90) in the paper.

Summary of recommendation: I think this is a borderline paper.  The approach seems reasonable.  There is some novelty in the problem choice, in the framework of generating training data, and in the geometric constraints on the embeddings, but none of these alone is a significant advance in the area.  The empirical results look quite good, but of course the problem hasn't had the same level of scrutiny as better-known pieces of the ML canon.  

review_title: Subgraph matching by geometric embedding

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper presents a sub-graph isomorphism method using neural networks and embeddings that are supposed to preserve important topological structure of subgraphs. Sub-graph isomorphism is NP-complete and has fascinated researchers with approximate solutions using heuristics and pre-processing (graph indexes) of many varieties over the years. The approach of using a neural network to learn to perform tasks such as link prediction, label prediction etc., through meaningful node embeddings, is a welcome extension when applied to sub-graph matching.

That being said, the paper skips over large volumes of progress in sub-graph matching work. From indexing methods, analysis of vertex relationships etc., many methods have proven efficient and effective in sub-graph isomorphism ( http://www.vldb.org/pvldb/vol8/p617-ren.pdf , https://dl.acm.org/doi/10.1145/2463676.2465300 , https://dl.acm.org/doi/10.1145/3299869.3319880 to cite a few) . It is only appropriate that a paper on this topic present a reasonable analysis of the prior work. Also, the embedding design decisions could possibly take-away important conclusions from these methods and lastly, compare against solid benchmarks instead of much older and outdated ones.

In conclusion, this work is quite interesting. However, at the moment it is not clear for this reviewer how to put it in perspective with respect to decades of systems and theoretical work on sub-graph isomorphism. A fair empirical evaluation should compare the GNN method to one of the state of the art non-neural methods. 

Thanks to the authors for providing a response to the review comments.
review_title: Interesting application of GNNs but lacks appropriate background study

Meta-review: This paper proposes an interesting approach for learning to decide whether a query graph is isomorphic to a subgraph within the target graph.  The approach has a number of interesting aspects from the machine learning perspective, e.g. the anchored graphs and the order embeddings.  Empirical results show promise in ablation studies and against a few baselines.

However this paper also has a number of issues as pointed out by the reviewers, placing it right on the borderline.  Most notably the clarity of the presentation could be improved as it seems to confuse a few reviewers at various points.  Another thing that I’d like to highlight is that the way to convert the pairwise scores f(z_q, z_u) into the final decision about G_T and G_Q seems worthy of a longer discussion.  Is a simple average across all pairs the best we can do?  I imagine if the query graph is small but the target graph is large then even if the G_Q does match a subgraph of G_T the average score can be quite low.

Overall I do like the ideas proposed in this paper, but also recognize that the paper can benefit from more improvement, so I’d like to recommend rejection but encourage the authors to submit again in the next round.
Decision: Reject