Charting the Design Space of Neural Graph Representations for Subgraph Matching

We thank the reviewer for their insightful review. The weaknesses and questions raised in the review are addressed below.

It seems all the 10 datasets are relatively small, e.g. up to 50 nodes. I wonder if there is a reason for not choosing much larger graphs, e.g. graphs up to 1M nodes as the target graph to be searched for (while using a small query graph of ~50 nodes).

There are two key reasons why we could not work with large graphs in the original version. But now, we have made strong evaluations on large graphs as well.

Similar to other ML tasks, our work also requires multiple graphs for training; here, one entire graph represents one instance of data. Data sets with a single large graph are more common than data sets containing multiple large graphs, which prevents a neural method to test its performance on large graphs. Moreover, the need for our and existing works are driven by practical applications like molecular retrieval. For instance, works such as GMN [Li et al., 2019], Neuromatch [Lou et al., 2020] and IsoNet [Roy et al., 2021] focus on small- to medium-sized graphs in their benchmarks. This scale is largely motivated by application domains such as molecular graph retrieval and object detection in images via scene graphs, where the focus is more on retrieving multiple smaller graphs rather than processing single extremely large graphs.

Still, we consider the following datasets drawn from the SNAP repository (https://snap.stanford.edu/data/index.html):

1. com-Amazon: Represents an Amazon product co-purchasing network, with nodes as products and edges denoting co-purchasing relationships. It consists of 334,863 nodes and 925,872 edges.
2. email-Enron: Represents an email communication network, with nodes as individuals and edges as email exchanges. It consists of 36,692 nodes and 183,831 edges.
3. roadnet-CA: Represents the road network of California, with nodes as road intersections and edges as connecting roads. It consists of 1,965,206 nodes and 2,766,607 edges.

Recent work such as Greed [Ranjan et al., 2022] proposes a heuristic for adapting small-scale, fast neural graph solvers to the problem of subgraph localization within large-scale graphs. Inspired by this approach, we extended our experiments on the above datasets.

Tables 1–4 present the results in terms of MAP for all proposed variations discussed in our study, corresponding to Node-Late, Edge-Late, Node-Early, and Edge-Early approaches, respectively.

Table 1: MAP for Node-Late interaction models for three diverse datasets.

Table 2: MAP for Edge-Late interaction models for three diverse datasets.

“Challenging the widely held expectation that early interaction is more powerful, IsoNet’s late interaction approach outperforms GMN, even when GMN’s final score computation is made asymmetric” – It is a bit unclear what it means by “asymmetric”, especially due to the fact this is written at the beginning of intro and the audience may not be familiar with this area of research.

Thanks for the suggestion ― indeed the reference to "asymmetric" was too early and cryptic; we have removed it.

Some of the paper writing can be made more clearer. It may be useful to introduce/outline the summarized findings at the end of the introduction section.

We have added the following para at the end of the intro. In addition, we have clearly summarized the effect of each design axis at the end of the respective sections. These are highlighted in the PDF for convenience.

💡 Key takeaways and design tips Our systematic navigation of the design space resolves hitherto unexplained observations and provides reliable guidelines for future methods.

1. We conclusively explain (late-interaction) IsoNet’s earlier-observed superiority over (early-interaction) GMN. If GMN’s early interaction is supplemented with any of set alignment, injective structure, hinge nonlinearity, or edge-based interaction, it can readily outperform IsoNet.
2. These five design principles are vital, and their combination unveils a novel graph retrieval model that surpasses all existing methods.
3. Shifting from late to early interaction may increase computational cost, but compensates for the limitations of relevance distance defined using aggregated single-vector embeddings.

How is this work related to neural architecture search (NAS)? It might be worth comparing/surveting works in NAS, e.g. https://arxiv.org/pdf/2403.05064v1, https://openreview.net/pdf?id=GcM7qfl5zY, etc. Referencing such works can position this work better within the broader literature and bring out further discussion.

We thank the reviewer for referring us to the relevant domain of Neural Architecture Search. Upon further study, we have decided to add the following discussion to our Related Works section and cite the two papers as references.

Within specific families of graph encoder networks, such as GNNs/GATs [NAS 1] or graph transformers [NAS 2], researchers have proposed super-networks to explore the parametric space of encoder networks, using a bi-level optimization framework. We have discussed and referenced the papers our revised version. Thanks for bringing forward these related work. It would be of future interest to investigate if NAS methods can be extended to subgraph search and other combinatorial graph problems, to automatically explore network design spaces.

[NAS 1, Zhang et. al.] Unsupervised Graph Neural Architecture Search with Disentangled Self-supervision. Neural Information Processing Systems, 2023

[NAS 2, Zhang et. al.] AutoGT: Automated Graph Transformer Architecture Search. International Conference on Learning Representations, 2023

Table 3: MAP for Node-Early interaction models for three diverse datasets.

Table 4: MAP for Edge-Early interaction models for three diverse datasets.

We note that the performance trends observed on the small molecule datasets are consistent with those on these diverse real-world datasets. In particular, we note that:

1. Edge-level granularity outperforms node-level granularity, as evidenced by comparisons between corresponding cells in Table 1 (Node-Late) and Table 2 (Edge-Late), as well as Table 3 (Node-Early) and Table 4 (Edge-Early).
2. Early interaction variants (Tables 3 and 4) demonstrate significantly higher MAP values compared to late-interaction models (Tables 1 and 2).
3. Across all four tables, Set Alignment relevance distance consistently achieves the highest MAP values in most cases.
4. Injective interaction structure variants generally provide higher MAP values compared to their non-injective counterparts across all tables.
5. The combination of Set Alignment with an injective interaction structure and Hinge interaction non-linearity is particularly effective, yielding the highest MAP values for these datasets

The performance on subgraph localization tasks on these larger real-world datasets, aligning with the performance trends on the smaller and medium-sized datasets, reinforces the generality of our findings and conclusions.

These results further suggest that our observations can be extended to heuristics operating on much larger graphs. While this is not the primary focus of our study, these experiments highlight the broader applicability of our approach to large graph scenarios.

While the paper does a thorough job of exploring the design space or structured ablation studies, it does not provide a principled explanation of why certain configurations (or subcomponents) yield performance improvements. Adding a more in-depth empirical and theoretical analysis can address this issue. This can not only strengthen the contributions but also offer a more principled foundation for future research in this area.

We appreciate this insightful feedback and acknowledge the importance of providing a more principled explanation of the performance improvements observed in the various configurations. In response, we have made an effort to distill the key empirical observations and present them succinctly. Additionally, we highlight the key takeaways from these analyses. A detailed discussion on the design choice axes is presented separately below.

Relevance Distance: Choice of Agg-* v/s Set Aligned

We present a comparison between set alignment-based relevance distance and aggregated embedding-based distance. Table 1 shows the MAP for Node-Late interaction models, while Table 2 presents the MAP for Edge-Late interaction models. The Agg-* variants rely on aggregated graph-level embeddings, which are subsequently processed through either an NTN module, a hinge scoring layer, or a general MLP. The interaction structure and non-linearities employed by the set alignment relevance distance are specified in brackets. In most cases, the set alignment relevance distance outperforms the aggregated distance variants.

Table 1: MAP for Node-Late interaction models for the first three datasets.

Table 2: MAP for Edge-Late interaction models for the first three datasets.

Takeaways and Design Tips

Compressing the entire graph into a low-dimensional vector can result in information loss. Therefore, comparing the node embeddings at the set-level granularity yields better performance than their single-vector representations. Similar observations have been reported in other domains.

In knowledge graph alignment, encoding the neighborhood of an entity as a set and then aligning two such sets has been found to perform better than comparing compressed single-vector representations of each entity [BERT-INT].

In textual entailment [Lai et al., 2017; Chen et al., 2020; Bevan et al., 2023], allowing cross-interaction between all tokens of the two sentences is generally more effective than compressing each sentence into a single vector and comparing them.

Our work reconfirms this intuition for subgraph retrieval as well.

[BERT-INT] X. Tang, J. Zhang, B. Chen, Y. Yang, H. Chen, and C. Li. Bert-int: A bert-based interaction model for knowledge graph alignment. interactions, 100:e1, 2020.

[Lai et al., 2017] A. Lai and J. Hockenmaier. Learning to predict denotational probabilities for modeling entailment.

[Chen et al., 2020] T. Chen, Z. Jiang, A. Poliak, K. Sakaguchi, and B. Van Durme. Uncertain natural language inference.

[Bevan et al., 2023] R. Bevan, O. Turbitt, and M. Aboshokor. Mdc at semeval-2023 task 7: Fine-tuning transformers for textual entailment prediction and evidence retrieval in clinical trials

Interaction Stage: Choice of Late v/s Early

We compare late and early interaction variants for both the top-performing aggregated embedding-based method (Agg-NTN) and the best-performing set alignment-based method. Table 3 presents the results for Node interaction granularity, while Table 4 shows the results for Edge interaction granularity. Early interaction is seen to afford significant performance improvements over its late interaction counterparts.

Table 3: MAP for Node interaction models for the first three datasets.

Table 4: MAP for Edge interaction models for the first three datasets.

Takeaways and Design Tips Although late interaction potentially enables fast nearest neighbor search, early interaction is generally known to be superior in text retrieval [ColBERT, Figure~1]. The comparison between IsoNet [ISONET] vs GMN [GMN] apparently contradicts this general trend. Therefore, it is important to resolve this issue using carefully controlled experiments.

[ColBERT] O. Khattab and M. Zaharia. Colbert: Efficient and effective passage search via contextualized late interaction over bert.

[ISONET] I. Roy, V. S. Velugoti, S. Chakrabarti, and A. De. Interpretable neural subgraph matching for graph retrieval.

[GMN] Y. Li, C. Gu, T. Dullien, O. Vinyals, and P. Kohli. Graph matching networks for learning the similarity of graph structured objects

Interaction Structure: Injective v/s non-Injective

We compare injective and non-injective interaction variants for both the top-performing aggregated embedding-based method (Agg-NTN) and the best-performing set alignment-based method. Table 5 presents the results for Node-Early variants, while Table 6 shows the results for Edge-Early variants. Injective interaction structure is seen to afford significant performance improvements over non-injective interaction in a majority of cases. Furthermore, we observe that the performance improvement from switching to injective interaction is more pronounced in set alignment relevance distance-based methods compared to aggregated NTN-based methods.

Table 5: MAP for Node-Early interaction models for the first three datasets.

Table 6: MAP for Edge-Early interaction models for the first three datasets.

Takeaways and Design Tips The combinatorial definition of graph matching includes finding an injective mapping between pairs of nodes from the two graphs. The mapping is also an interpretable artifact. Attention from one node to all nodes in the other graph, even if maintained from each graph separately, cannot achieve a consistent 1-1 mapping. Our experiments suggest that an injective mapping (or its continuous relaxation --- doubly stochastic matrices) performs better.

Although the best combination shows performance benefits, its novelty is limited. The only differences between the best model and the existing state-of-the-art (IsoNet) are the interaction stage and non-linearity (which have been proposed in existing studies). Without providing principled rationales (as the first bullet), this could make the contributions appear incremental.

Our key contribution is not providing another new model. We rather identify the key design choices and while doing that, we demystify many existing works, as reviewer 6vg7 also pointed out. While there are so many excellent papers, there is a lack of study why some methods work and some methods don't. We find out key design choices involving the representation of and interaction between graph representations, and then systematically explore subtle interplay between these design choices.

Our systematic navigation of the design space resolves hitherto- unexplained observations and provides reliable guidelines for future methods. (1) We conclusively explain (late-interaction) IsoNet’s earlier-observed superiority over (early-interaction) GMN. If GMN’s early interaction is supplemented with any of set alignment, injective structure, hinge nonlinearity, or edge-based interaction, it can readily outperform IsoNet. (2) These five design principles are vital, and their combination unveils a novel graph retrieval model that surpasses all existing methods. (3) Shifting from late to early interaction may increase computational cost, but compensates for the limitations of relevance distance defined using aggregated single-vector embeddings.

The dense presentation makes it challenging for readers to immediately see the paper’s structure and key subcomponents. I think the authors should present a clearer organization and structured outline. In particular, Figure 1 is hard to interpret. I think that the authors can provide more human-readable visualization. Plus, please put some margin to the bottom of Figure 1.

We appreciate the feedback and have made significant improvements to enhance clarity. Figure 1 has been revised to provide a more readable and intuitive visualization, with an updated caption for better interpretation. We have also restructured the treatment of each design axis and included a dedicated section summarizing the key takeaways.

Many thanks for your feedback. We now better understand your concerns, which we address below.

Novelty and surprise in results:

Fig 3 suggests that (1) components interact; (2) components that are suboptimal within the individual axes may be combined to give high accuracy in fast inference time. This figure clearly guides a practitioner to choose the model combination based the inference time cost permissible in the underlying usecase, rather than trying all possible combinations. We provide some novel and surprising observations as follows:

(1) Components do interact. Suppose, we just switch one axis (relevance distance) from the optimal combination: SA+Early+Injective+Hinge+Edge to Agg-NTN+Early+Injective+Hinge+Edge, performance degrades drastically (by 7%). We expected that if we further change choice across another axis, MAP would decrease more. Contrary to this expectation, when we change injective to non-injective (Agg-NTN+Early+Non-Injective+Hinge+Edge), the performance actually boosts significantly. Moreover, inference becomes much faster (2X faster than the best MAP setup). This was indeed surprising to us, since Injective mapping is a key criteria which is advocated by IsoNet. But it turns out Injectivity only shows its effect if set alignment is the final score.

However, injective maps may not always be the preferred solution, because the Sinkhorn network consumes large compute resources. The designer may choose non-injective mapping which may result in considerable speed up. In this case, Agg-NTN+Early+Non-Injective+Hinge+Edge may be the best design.

(2) In principle, an MLP with cascaded layers of Linear-ReLU-Linear networks should be able to learn any underlying nonlinearity, certainly simple nonlinearities like hinge. Hence, if we change SA+Early+Injective+Hinge+Edge to SA+Early+Injective+Neural+Edge, we expect comparable performance . However, the performance drops drastically (by 11.3%). This is surprising since SA+Early+Injective+Neural+Edge is the superclass of the hypotheses modeled using SA+Early+Injective+Hinge+Edge.

(3) Most surprisingly, in IsoNet, injective vs Non-injective does not make any difference. See the bottom left cluster in scatter plot Fig 3: (Late interaction, set alignment, edge (also node)), where injective and non-injective points are overlapping.

Moreover, IsoNet claimed that edge alignment model, set alignment and injective mapping are the key components for subgraph matching model. They claimed that due to these factors, GMN are outperformed by them even if we use asymmetric scores in GMN. However, as the table here (also page 22, Table4) suggests, if we just change GMN’s nonlinearity to hinge, then it performs better than Isonet, despite use of node alignment, aggregated scoring (no set alignment) and non-injective mapping.

Leveraging prior studies' ablation findings could have narrowed the search space

As we have seen in the above table Node alignment, non-injective mapping, aggregated-hinge with hinge nonlinearity work better than IsoNet’s edge alignment. Hence, IsoNet’s claim that node alignment is always worse than edge alignment is not true and therefore, narrowing down the search from related work may not be helpful.

differences between your best and IsoNet are two

The best model reported in the paper corresponds to early interaction with injective mapping. This is extremely costly and it is not preferred by the practitioner where the usecase involves time constraint. Apart from this expensive combination, Fig 3 in our paper allows for a wide variety of combinations, catering to various inference time costs. Under such time constraint, one has to perform changes across several axes of IsoNet, which still outperforms IsoNet. Following table shows that changes across multiple axes are necessary to beat Isonet in comparable run-time. Our-early-1 is close to our-early-best but more than 2x faster, and it is different from IsoNet in four out of five axes. It provides excellent trade off between accuracy and time.

We are keen to hear from you on whether your concerns have been addressed.

Beyond educated guesses, what are the fundamental reasons why a certain combination performs so well

We answer this question directly from the following theoretical underpinning. Specifically, we describe the combinatorial formulation of subgraph matching and then show why certain combination works so well and others don't.

First consider the combinatorial cost:

The standard way to minimize it is a Projected gradient descent approach, where P is updated as

Z _{t+1}[u, u'] = \frac{Z _t[u, u']}{\sum _{v' \in [N]} Z_t[u, v']}, \quad \text{where} \quad Z _t'[u, u'] = \frac{Z _t[u, u']}{\sum _{v \in [N]} Z _t[v, u']}, \quad \text{for all } (u, u')

Academic values derived from underperforming combinations

The key underperforming combinations are as follows:

1. Poor design choices for $\nabla _P \text{dist}(G _q, G _c)$ significantly impact performance. The widely used Dot Product interaction (commonly found in attention-based models like GMN and H2MN) and the neural interaction non-linearity introduced by IsoNet are consistently outperformed by the Hinge non-linearity. Hinge offers a clear advantage across all metrics and is the preferred choice for interaction modeling.

2. Using dot product or neural methods, pivoting to set alignment relevance distance improves MAP values. However, this comes at the cost of a significant increase in inference time, making it suboptimal for achieving the best MAP-inference time Pareto trade-off.

3. In the above, while using dot product or neural methods, transitioning to non-injective set alignment in an effort to improve inference times results in a notable performance drop. This approach fails to provide a satisfactory trade-off between accuracy and efficiency.

4. When using Early Interaction with Hinge non-linearity and non-injective interaction, the choice of relevance distance becomes less critical. In such cases, opting for faster aggregated relevance variants over set alignment achieves similar performance while reducing computational overhead.

We elaborate on both underperforming and well-performing combinations in the Takeaways and Design Tips (pages 5–7) and the Design Guidelines (pages 9–10). Please refer to the text highlighted in teal for detailed insights.

On another note, I recently came across the following study: https://openreview.net/forum?id=udTwwF7tks Could you let me know which combination in your submission this model aligns with?

If cast into our specified design axes, this paper employs Early Interaction, with an injective interaction structure, neural interaction non-linearity, and set alignment relevance distance. However, their early interaction model is more sophisticated than prior works, factoring in node pairs and updating alignments lazily at fixed intervals. While this approach appears to improve MAP, it is computationally extremely expensive, requiring further investigation to address: (1) How this novel interaction model interacts with other design choices, such as whether hinge non-linearity could further enhance performance or interact adversely; (2) Its position in the MAP-inference time Pareto trade-off compared to other design choices.

Of course, this is a neurips 2024 paper, so it does not necessarily have to be included in this submission, but it would be nice to have it mentioned later. And I am also planning to compare the results in the paper and your submission.

We agree this study is relevant to our submission. However, as it became publicly available only recently (just three weeks before today and more than one month later than submission deadline). Comparing the results of this paper against ours is beyond the scope of our current work. We will certainly mention clearly later. Notably, this paper underscores the importance of our current submission in the rapidly evolving landscape of subgraph matching methods.

As with many recent proposals, this paper appears to treat its specific design choices as achieving a robust (local) maximum in performance. However, without systematically incorporating superior design options—such as injective interaction, neural non-linearity, and edge granularity—for baselines like GMN, it may be challenging to attribute performance gains solely to novel aspects like node-pair attention and lazy updates. This highlights the need for a principled framework to evaluate and benchmark design choices systematically.

Our work addresses this need by proposing clear guidelines for evaluating new models and understanding the combinatorial interplay of design choices. We believe this will inspire more confidence and measurable progress in subgraph matching research.

We reiterate that our proposal is not in competition with this new paper and this new paper does not diminish the significance of our work. Instead, this paper aligns with our specified design axes and can further advance the field when analyzed using our proposed guideline. In fact, our analysis can be used to enhance the quality of this paper too.

Appeal to Reviewer SvpM

We greatly appreciate your continued engagement in improving this work. We has earlier highlighted the key takeaways and design tips throughout the paper and elaborated on the theoretical underpinnings of hinge non-linearity in Section D.1 of the Appendix. Your feedback has helped us refine these insights more coherently. While we are unable to update the paper PDF at this stage, we will ensure these improvements are incorporated in final revision, if the paper gets accepted. Kindly let us know if this further discussion has addressed your concerns.

The use of notations and are not consistent between L124 and Figure 1.

Thank you for your careful reading and for pointing out this inconsistency. We have addressed this issue and corrected the notation. Additionally, based on this feedback and comments from other reviewers, we have significantly overhauled the figure and revised the caption to provide clearer explanations regarding the sequence of the design choices and the complexity of the implied design space though various combinations of the design choices.

Q1. Does the use of hinge distance make sense for set alignment and aggregated-hinge (L216-236)? In particular, the authors justify the use of hinge distance for adjacency matrices, but the adjacency matrices are binary while node/aggregated node embeddings are just real-valued.

This is a very important question and we are glad to include further intuition, which comes from Bloom filters. Given a universe of elements $U$ and $X, Y \subseteq U$, we can use bit vectors in $\\{ 0,1 \\}^{|U|}$ to represent $X,Y$, let's call them $\vec{X}, \vec{Y}$. The direct test for $X\subseteq Y$ is easily seen as the test $\vec{X} \le \vec{Y}$ (elementwise). A Bloom filter may be used to compress these bit-vectors into much shorter ones in $\\{0,1\\}^M$ where $M\ll|U|$, however, the test for $X\subseteq Y$ remains the same. Bloom filters have long been replaced by Learnt Bloom Filters (LBFs) and various forms of set transformers. Our work makes the natural progression from set encoders to graph encoders.

References

[Davitkova et. al., 2024] Learning over Sets for Databases. Extending Database Technology (EDBT), 2024

Table 3: MAP for Node-Early interaction models for three diverse datasets.

Table 4: MAP for Edge-Early interaction models for three diverse datasets.

We note that the performance trends observed on the small molecule datasets are consistent with those on these diverse real-world datasets. In particular, we note that:

1. Edge-level granularity outperforms node-level granularity, as evidenced by comparisons between corresponding cells in Table 1 (Node-Late) and Table 2 (Edge-Late), as well as Table 3 (Node-Early) and Table 4 (Edge-Early).
2. Early interaction variants (Tables 3 and 4) demonstrate significantly higher MAP values compared to late-interaction models (Tables 1 and 2).
3. Across all four tables, Set Alignment relevance distance consistently achieves the highest MAP values in most cases.
4. Injective interaction structure variants generally provide higher MAP values compared to their non-injective counterparts across all tables.
5. The combination of Set Alignment with an injective interaction structure and Hinge interaction non-linearity is particularly effective, yielding the highest MAP values for these datasets

This consistency reinforces the generality of the observations and conclusions outlined in the paper.

By incorporating these diverse datasets, we address the reviewer’s concerns regarding the representativeness of our experimental suite. We believe this extension strengthens the study and aligns it more closely with the practical applications of subgraph matching discussed in the introduction.

W2. There is a lack of understanding in subgraph matching performance with respect to the intrinsic challenge of the setting, e.g., highly regular graphs, different graph sizes, different feature distributions, out-of-distribution settings. Such study may be best achieved with synthetic datasets.

We thank the reviewer for pointing us in the very interesting direction of studying different graph sizes, feature distributions and out-of-distribution settings. Towards this goal, we formula two new experiments:

Transfer ability (out-of-distribution setting)

We choose the model trained on dataset X and perform inference on dataset Y, where X ≠ Y. In particular, we fix Y to be the AIDS dataset and vary X in the set {Mutag, PTC-FR, MOLT-4H}. We compare the performance of these OOD models with the model trained on the AIDS dataset itself. For clarity of understanding, we show results on early interaction models with node-level granularity (Table 5) and edge-level granularity (Table 6). Boldface represents the dataset that provides the best transfer ability. The following observations can be made -

1. The strongest transfer abilities are displayed by models trained on PTC-FR, followed by Mutag, and finally MOLT-4H, which shows severe degradation in performance compared to the baseline AIDS-based model. This pattern can be explained by the extent of relative dissimilarity between the source datasets and AIDS, which is maximum for MOLT-4H (doubly-sized graphs as AIDS), followed by Mutag (mean node/edge counts off by one/two) and finally PTC-FR (similar graph size distribution).
2. Despite the strong transfer ability, the model trained originally on AIDS is the best performer with almost every network configuration.

Table 5: MAP for transfer ability of different Node-Early interaction models on the AIDS dataset.

Table 6: MAP for transfer ability of different Edge-Early interaction models on the AIDS dataset.

Variation in performance with latent dataset characteristics

To study how dataset characteristics affect our proposed networks, we create splits of our datasets and perform inference on them. In particular, we select a metric and divide the corpus set of the AIDS dataset sorted by this metric into 4 contiguous splits. Inference is performed with all query graphs using the model trained on AIDS, on each of the corpus splits and the MAP scores are reported. Subset 0 represents the split with graphs pertaining to the lowest values for the corresponding metric while Subset 3 represents that with the highest values.

In the tables below, boldface represents the subset with the highest MAP score for the corresponding row.

(1) Metric = Node Count

Node count is one measure of graph size and is extremely relevant to the problem at hand, since a smaller node count requires a larger number of padding nodes to allow batched processing, which can be detrimental towards performance. In Table 7, we display dataset statistics for each split. The statistics are shown for the corpus graphs only, since the query graphs used for inference are identical across all splits.

Table 7: Dataset statistics for splits of the AIDS dataset based on the Node Count metric.

Observation: The effect of padding nodes is clearly noticeable for both node-early (Table 8) and edge-early (Table 9) models. Subset 0 (minimum number of nodes) corresponds to the smallest MAP score, which consistently increases as we increase node size and peaks for Subset 3.

Table 8: MAP for Node-Early interaction models for splits of the dataset with increasing node count

Table 9: MAP for Edge-Early interaction models for splits of the dataset with increasing node count

(2) Metric = Edge Count

Edge count is another measure of graph size. Since the logical unit of computation in edge-granularity models is an edge, we may expect to see similar trends as shown by node-granularity models with the Node Count metric (Table 8).

In Table 10, we display dataset statistics for each split.

Table 10: Dataset statistics for splits of the AIDS dataset based on the Edge Count metric.

Observation: The effect of increasing Edge Count, while quite prominent, is not as monotonic as that seen for Node Count. In particular, for models with Injective interaction structure or a Set alignment based relevance distance, Subset 0 often shows the best performance, which indicates that usage of injective mapping and set-alignment is more immune towards the presence of padding nodes/edges.

Table 11: MAP for Node-Early interaction models for splits of the dataset with increasing edge count.

Table 12: MAP for Edge-Early interaction models for splits of the dataset with increasing edge count.

We thank the reviewer for their detailed review and valuable feedback that helps improve our work. We address the concerns posed by the reviewer below:

W1. Most datasets considered are for small molecules despite the various applications of subgraph matching mentioned in the introduction.

While the datasets currently included in the paper are widely recognized benchmarks, the reviewer correctly highlights that most of these are sourced from small molecule datasets (e.g., AIDS, MUTAG) and computer vision tasks (e.g., MSRC). We acknowledge this limitation and have extended our dataset suite to include three large-scale, real-world datasets that reflect diverse and practical applications of subgraph matching. These datasets were obtained from the SNAP repository (https://snap.stanford.edu/data/index.html) and were processed to align with the experimental setup described in our study. The details of the newly added datasets are as follows:

1. com-Amazon (Amazon): This dataset represents an Amazon product co-purchasing network, where nodes correspond to products and edges denote frequent co-purchasing relationships. Subgraph matching in this dataset is relevant for tasks such as identifying frequent co-purchase patterns or improving recommendation systems.

2. email-Enron (Email): This dataset comprises an email communication network from the Enron corporation, where nodes represent individuals and edges correspond to email exchanges. Subgraph matching in this context can provide insights into communication patterns and aid in identifying specific organizational structures.

3. roadnet-CA (RoadNet): This dataset represents the highway network of California, where nodes correspond to road intersections, and edges denote roads connecting them. Subgraph matching in this setting can assist in applications such as traffic management and subnetwork optimization.

To integrate these datasets into our study, we followed the same preprocessing and subgraph extraction methodology outlined in the paper and ran all the designed experiments to further explore the design space of the subgraph matching methods.

Tables 1–4 present the results in terms of MAP for all proposed variations discussed in our study, corresponding to Node-Late, Edge-Late, Node-Early, and Edge-Early approaches, respectively.

Table 1: MAP for Node-Late interaction models for three diverse datasets.

Table 2: MAP for Edge-Late interaction models for three diverse datasets.

Thank you for your detailed and well-thought responses, which have addressed most of my questions and concerns. I've increased my scores in accordance. The paper's primary strength lies in its elegant simplification and demystification of existing approaches - a contribution I consider to be of significant value to the field. Such work that brings clarity and accessibility is essential for advancing future research. Regardless of the final acceptance decision, the review process has been intellectually enriching to me, and I want to thank the authors for preparing a high-quality submission, from which I've also learnt a lot.