Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval

Summary

The paper introduces EINSMATCH, an early interaction graph neural network for subgraph matching and retrieval that maintains and refines explicit alignments between query and corpus graphs. EINSMATCH has several novelties: computing embeddings guided by injective alignments between graphs, updating alignments lazily over multiple rounds, and using node-pair partner interactions. The model learns to identify alignments between graphs despite only having access to pairwise preferences during training, without explicit alignments. Experiments on several datasets show that EINSMATCH significantly outperforms existing methods.

Strengths

1. The analysis of GMN’s worse performance compared to IsoNet (in Section 1) is intriguing. 2. Extensive experimental results are presented with ample baselines and std errors included as well for most numbers reported. 3. Source code with data splits is released for ease of reproducing the results. 4. A large amount of ablation and parameter sensitivity studies are performed.

Weaknesses

1. The datasets used in the experiments are relatively small, with at most ~20 nodes. 2. It would be interesting to see the transfer ability of the learned model across datasets, e.g. training on PTC and testing on AIDS, to see how the proposed model would handle such challenging but realistic scenarios.

Questions

N/A

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

This work proposes a GNN architecture for graph matching problem. The innovations in the work mainly lie in the early interaction between the query graph and the corpus graph, and the node-pair matching setting, as well as the lazy update technique in each round. Empirical results show that this work significantly outperforms the baselines on all the datasets.

Strengths

- The writing of the paper is clear and good. - The methodology is solid, and the illustration is informative. - The results are very promising, both in predictive performance and runtime. And the ablation experiments are well-designed.

Weaknesses

- Some background part is not well explained, for example the graph matching problem, and the optimal transport problem. Readers may need external resources to understand them. Of course it is hard to explain everything in detail in the main paper.

Questions

- Any related work indicating early interaction is good? As mentioned in line 36. - In line 124 the notation $A_q \leq PA_c P^T$ is a bit confusing. - In equation 5, what is the sign of $\tau$? If it's positive then you're encouraging the entropy to be higher, which means the entries of P are more uniform? That is a bit counter-intuitive. - What is the complexity of Sinkhorn Knopp algorithm and Gumbel Sinkhorn? - Is the K-layer GNN in each round t shared? - Any intuition why lazy updates works better? Is it easier to optimize or other aspects? - I don't quite understand why the work is not differentiable on nodes with different classes, as mentioned in appendix A. - Is there other measure between the $P$ and $P^*$? I feel $Tr(P^TP^*)$ does not capture all the information of the matrices.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

As mentioned by the authors, the quality of the matching relies on the distance function, which is a general problem for graph matching works. Also I am a little dubious about the time complexity of the P matrix update, in the experiments it is more expensive than the baseline GMN.

Summary

This paper proposes an early interaction network for subgraph matching. The proposed method enables (1) early interaction GNNs with alignment refinement at both node and edge levels, where the alignments are refined by GNNs; (2) eager or lazy alignment updates, and (3) node-pair partner interaction, instead of node partner interaction, which improves the model efficiency and embedding quality. The paper includes extensive experiments on real-world datasets, demonstrating the superiority and effectiveness of the proposed approach.

Strengths

1. The paper is well-written and easy to understand. The notations are clearly clarified and explained. 2. The idea of iteratively early interaction between graphs for more accurate subgraph retrieval is novel and reasonable to me, which is also verified by the experimental results. 3. The performance superiority of the proposed method against other baselines is significant and promising.

Weaknesses

1. Considering the high complexity of the proposed method, an ablation study (or a hyperparameter sensitivity study) would be beneficial to provide a clearer understanding of the success of the proposed method. In addition, how did the authors tune hyperparameters (apart from T and K) for their approach and the competitors? 2. Experiments are only conducted on small graph datasets (with an average of 11 nodes). It would be beneficial to discuss or evaluate the applicability of the proposed approach to larger graph datasets.

Questions

- What is the motivation and intuition behind lazy updates? In my understanding, "lazy" means updating the alignment map after every K GNN layers, and "eager" means updating the alignment map and letting the map affect the embedding at each layer. Is there any explanation for the consistently better performance of "lazy" updates? - What do the multiple points with the same color in Figure 6 represent? Do they indicate variants with different hyperparameters?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes. This paper discussed the limitations in terms of efficiency and

Summary

The paper proposes EinsMatch, a neural approach for graph retrieval, i.e. the problem of finding the best candidates of a corpus of graphs that contain a subgraph isomorphic to a given query graph. EinsMatch is based on a Graph Neural Network architecture and introduces technical improvements over existing methods: (i) message-passing iterations across query and candidate graphs which are guided by an injective alignment; (ii) the iterations are lazy in the sense that multiple of them are computed with a fixed alignment before refining it; (iii) node pairs are considered as potential partners instead of single nodes in the message-passing steps. In addition, the authors propose a variant which works at the level of edges and natively leverages edge matchings. This variant seems to be the most competitive one in the experiments the authors run. In general, EinsMatch significantly outperforms a variety of other methods. The authors also report insightful ablation studies on the number of alignment rounds and message passing layers.

Strengths

- The proposed architecture nicely interpolates between late and early aggregation approaches, whilst ensuring injectiveness of the candidate mapping. In this sense, it appears as a sensible generalisation of other approaches. - The proposed model is highly performant if compared with other methods, and, in particular offers a competitive accuracy-inference time tradeoff if compared with other approaches as GMNs. - The reported ablation studies are insightful in that they shed light on the impact of important hyperparameters, namely the number of layers and rounds.

Weaknesses

- I found the paper somewhat hard to follow. The contributions are rather technical and only one single figure in the manuscript illustrate the approach. I think it would be particularly helpful if the authors improved on this aspect. - Still on the presentation side, I found it hard to clearly understand the specific contributions w.r.t. previous works. I believe the paper would increase in quality if the authors would state these more clearly in the main corpus. - The authors only provide a high-level intuition behind some specific technical contributions, e.g. the choice of working with node-pair partners. Would it be possible to refer to more formal arguments around those?

Questions

Please see Weaknesses. Also: - The readers refer oversmoothing problems in some of the previous methods. Can they expand on how their approach side-steps this? - Can the authors better explain lines 333 — 336? I found them hard to understand. - How does the computational complexity compare with that of IsoNet?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors do not seem to explicitly discuss them in the main corpus, but mention two aspects in Appendix A.