acceptodds
Under review as a conference paper at ICLR 2027

A Neural Subgraph Matching Model for Graph Sequence Retrieval

Abstract

Subgraph-isomorphism-based retrieval traditionally compares a query graph against individual corpus graphs, whereas many relational systems are observed as evolving graph sequences. In this work, we focus on graph-sequence retrieval, where relevance is defined by the presence of an order-preserving subsequence in the corpus sequence, such that each graph in the subsequence contains the corresponding query graph as a subgraph. A brute-force approach would require solving subgraph-matching problems across query–corpus timestep pairs and then searching over order-preserving subsequences, leading to a costly combinatorial procedure. A straightforward neural adaptation would apply an independent graph-matching model to all timestep pairs before using a sequence-level matcher, but this ignores the temporally correlated structure of evolving graph sequences. We formalize this problem as Subgraph Isomorphism-based Graph Subsequence Matching (Sigma), where relevance depends jointly on a shared node alignment and an order-preserving timestep alignment. We propose SigmaNet, an end-to-end neural retrieval model that replaces discrete optimization with differentiable node and timestep alignments. Across five graph-sequence retrieval benchmarks, Sigmanet consistently outperforms dynamic graph models and graph-matching baselines adapted to graph-sequence retrieval using sequence matchers.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph subsequence matching, graph neural networks

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_44HFOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces SIGMA, a retrieval task for graph sequences. A corpus sequence is relevant when its timesteps contain the query graphs in the right order, with the same node alignment across all matched timesteps. SIGMANET uses a GNN and causal transformers to represent each sequence. It then computes one shared node alignment and uses a staircase aligner to match timesteps. The authors build five benchmarks from reaction, event, and protein interaction data. SIGMANET has the best MAP on all five datasets in the main comparison, where the baselines use Soft-DTW.

Critical strengths
  1. The problem is defined clearly. Definition 1 and Equations 1–6 explain why both the node mapping and the timestep mapping matter. Requiring one node mapping across time is reasonable when node identities persist.

  2. The benchmarks cover several different kinds of graph sequences. Table 8 gives useful information about the query and corpus sets. The paper also says that code and data are provided as supplementary material.

  3. The appendix contains useful additional experiments. It studies where to place the temporal transformer, shared versus separate node alignments, finite timestep gaps, a strict DP matcher, and runtime against an exact solver. Table 18 also shows that using one shared node alignment saves memory.

Critical weaknesses
  1. Some ablation results are exactly the same to three decimal places on all five datasets. In Tables 11–14, “IsoNet + TFθ” has the same MAP and MRR values as “SIGMANET − SA”, while “IsoNet + SA” has the same values as “SIGMANET − TFθ”. If these configurations are actually identical, the paper should explain this relationship and state more clearly what SIGMANET adds to IsoNet. If they are different configurations, the authors should explain why the reported values coincide. This matters because the ablations are used to support the contribution of each component.

  2. The main results may reflect the choice of sequence matcher. All baselines in Table 2 use Soft-DTW, which aligns full sequences and is not a natural choice for finding a contained subsequence. When the baselines use the proposed staircase aligner in Table 13, GEN + SA scores 0.822 on PaRoutes, slightly above SIGMANET’s 0.818. GraphSSM + SA scores 0.814 on FlowER, slightly above SIGMANET’s 0.812. These small differences need uncertainty estimates. The authors should make this comparison more central and consider a subsequence-DTW or DP matcher with representative baseline encoders. As it stands, I cannot tell how much of the main improvement comes from the graph encoder.

  3. I am not fully convinced by the explanation of the alignment method. The paper starts from a joint optimization over node and timestep alignments, but the model first predicts the node alignment from the final node embeddings and only then computes the timestep alignment. The order penalty is produced by a CNN, rather than obtained by optimizing a dual variable. The paper already describes this as an approximation. In the main setting, (b_1=1) and (b_2=\infty), so the ordered timestep matching can be solved exactly for a given node alignment and pairwise costs by the DP in Appendix F.6. The no-λ model has MAP of 0.133 on PaRoutes and 0.144 on FlowER, while strict DP drops to 0.234 on FlowER (Tables 16 and 21). I would like to understand the large strict-DP drop on FlowER. More analysis of training and learned pairwise costs would help.

  4. I could not find enough detail about how the ground-truth labels are produced, although Table 28 reports an exact SIGMA solver. RDKit and Glasgow solve graph matching problems for individual graph pairs, but SIGMA also requires one node alignment shared across the selected timesteps. The paper should explain how it checks this shared alignment and searches over ordered timestep choices. The main result tables also do not show variation across runs or splits, although Appendix F.3 reports paired tests over ten splits. This is especially relevant for PaRoutes, which has only 122 queries in total and roughly 30 test queries per split. MRR is already close to one for many methods on Ito and Uetz, so small MRR differences are hard to interpret. Finally, Table 9 counts only baseline encoder parameters, while Table 10 counts the whole SIGMANET model. Full model parameter counts and clearer information about baseline-specific tuning would make the comparison easier to judge.

Questions for authors

Please see above weaknesses.

Reviewer_TH35OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies graph sequence retrieval under Subgraph Isomorphism-based Graph Subsequence Matching (SIGMA) and proposes SIGMANET, an end-to-end neural model. The model combines a sequence-aware graph encoder, shared node alignment estimated using Sinkhorn normalization, and differentiable staircase-based sequence alignment to preserve temporal ordering. The method is evaluated on five datasets using MAP and MRR as retrieval metrics.

Critical strengths
  • The problem formulation is clear
  • The experiments cover five datasets from different application domains
Critical weaknesses
  • I think the paper overstates the novelty of its problem formulation. Evolving/temporal subgraph matching has been extensively studied (Li et al., 2022; Aghasadeghi et al., 2024). SIGMA essentially uses the existence of a valid temporal subgraph match to define relevance. Learning to predict this relevance is a different solution approach, not a new matching problem.

  • The methodological contribution appears limited. The node alignment and asymmetric hinge-based matching largely follow IsoNet (Roy et al., 2022), while the sequence alignment mechanism is adopted from OPAS (Kohli et al., 2026). The proposed GSEQENC essentially combines spatial message passing with temporal self-attention, a well-established design in temporal graph learning (Sankar et al., 2020), and the paper does not clearly establish its methodological novelty.

  • The experimental evaluation is not convincing. Despite being designed for retrieval, SIGMANET achieves only marginal improvements over IsoNet on several datasets, while requiring substantially longer training and inference times. Moreover, relevant neural subgraph matching methods such as D²Match (Liu et al., 2023) and NC-Iso (Liu et al., 2025), as well as traditional temporal subgraph matching methods (Aghasadeghi et al., 2024; Min et al., 2024), are missing from the comparisons. The efficiency evaluation also raises concerns about fairness. Table 26 reports unusually large variations in GEN's inference time across datasets without sufficient explanation, while Table 28 does not clearly identify the exact solver or provide sufficient details about its implementation and experimental setup. These issues make it difficult to assess the claimed retrieval efficiency of SIGMANET.

  • The practical necessity of SIGMANET is unclear. All five benchmarks contain graph sequences with at most 50 distinct nodes and corpora of only 800–1,800 sequences. For graphs of this size, traditional subgraph matching algorithms may already provide efficient and exact retrieval, but the paper does not establish why a neural approximation is necessary. Moreover, existing neural subgraph matching methods such as GREED, D²Match, and NC-Iso have been evaluated on graphs with millions of nodes. The experiments neither demonstrate a clear practical advantage at the tested scale nor evaluate scalability to larger graph sequences.

Li, F., Zou, Z., Li, J., Yang, X., and Wang, B. (2022). Evolving subgraph matching on temporal graphs. Knowledge-Based Systems, 258, 109961. https://doi.org/10.1016/j.knosys.2022.109961

Aghasadeghi, A., Van den Bussche, J., and Stoyanovich, J. (2024). Temporal graph patterns by timed automata. The VLDB Journal, 33(1), 25–47. https://doi.org/10.1007/s00778-023-00795-z

Roy, I., Velugoti, V. S. B. R., Chakrabarti, S., and De, A. (2022). Interpretable neural subgraph matching for graph retrieval. Proceedings of the AAAI Conference on Artificial Intelligence, 36(7), 8115–8123. https://doi.org/10.1609/aaai.v36i7.20784

Kohli, B., Sarangi, S., Shameem, A., and De, A. (2026). Learning right monotone permutation matrices for neural subsequence search. Proceedings of the 29th International Conference on Artificial Intelligence and Statistics, PMLR 300, 4024–4032.

Sankar, A., Wu, Y., Gou, L., Zhang, W., and Yang, H. (2020). DySAT: Deep neural representation learning on dynamic graphs via self-attention networks. Proceedings of the 13th International Conference on Web Search and Data Mining, 519–527. https://doi.org/10.1145/3336191.3371845

Liu, X., Zhang, L., Sun, J., Yang, Y., and Yang, H. (2023). D2Match: Leveraging deep learning and degeneracy for subgraph matching. Proceedings of the 40th International Conference on Machine Learning, PMLR 202, 22454–22472.

Liu, Z., Liu, N., Chen, Y., He, J., Jia, M., and Li, D. (2025). Hierarchy-aware neural subgraph matching with enhanced similarity measure. IEEE Transactions on Knowledge and Data Engineering, 37(9), 5298–5310. https://doi.org/10.1109/TKDE.2025.3583003

Min, S., Jang, J., Park, K., Giammarresi, D., Italiano, G. F., and Han, W.-S. (2024). Time-constrained continuous subgraph matching using temporal information for filtering and backtracking. Proceedings of the 40th IEEE International Conference on Data Engineering, 3257–3269. https://doi.org/10.1109/ICDE60146.2024.00252

Questions for authors
  • How is the shared node alignment required by Definition 1 enforced during ground-truth generation? The released code appears to perform subgraph matching independently at each timestep.

  • Why are recent neural and traditional temporal subgraph matching methods missing from the comparisons?

  • Why does GEN's inference time vary so significantly across datasets in Table 26?

  • Which exact solver was used in Table 28, and what was the experimental setup?

Reviewer_vG61OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The manuscript studies how to retrieve graph sequences that contain a given query sequence. A match must preserve the order of the query snapshots and use the same node mapping across all matched timesteps. The authors call this matching condition SIGMA and propose SIGMANet, a neural model that learns to rank database sequences by relevance to a query. The model combines graph structure with temporal information, estimates a shared node mapping, and uses soft timestep assignments with order penalties to identify the matching subsequence. The authors evaluate SIGMANet on five benchmarks constructed from chemical, interaction, and protein-network data. In the main comparison, SIGMANet achieves the highest mean average precision among baselines that use Soft-DTW for sequence alignment.

Critical strengths

S1. The manuscript clearly states the requirement that the same node mapping must work across all matched snapshots. Its matrix formulation also provides a reasonable explanation of how the matching problem leads to the neural scoring function.

S2. SIGMANet achieves the highest MAP on all five datasets in the main comparison against baselines using Soft-DTW, although the stronger appendix comparisons give a more mixed picture.

S3. The authors investigate temporal information, skip connections, the sequence aligner, order penalties, and shared versus separate node mappings. These experiments help explain which parts of the model contribute to its performance.

Critical weaknesses

W1. Sequence mining is widely popular in the data mining area. Inokuchi and Washio’s FRISSMiner paper (DOI:10.1587/TRANSINF.E95.D.1590) defines a graph subsequence using both an increasing sequence of time steps and a shared mapping of vertex identities. The claim that the manuscript introduces a new matching problem is too strong.

W2. Some baselines were originally designed for representation learning or related matching tasks. Although they can still provide useful comparisons when properly adapted, the question is whether SIGMANet improves on the adaptations. The exact baseline implementations also need clarification. For example, the manuscript describes IsoNet in terms of node alignment, whereas the original method emphasizes edge alignment.

W3. The experiments do not show whether the constructed queries and matching labels capture what users would actually want to retrieve. The benchmarks are relatively small: they contain 122–300 queries and fixed corpora of 800–1,800 sequences. Only the queries are divided into training, validation, and test sets. This is a valid evaluation setting, but it mainly shows performance on new queries over the same corpus. It does not establish performance on unseen corpora, substantially larger graphs, or longer sequences.

Questions for authors

Q1. What is new in the problem formulation relative to prior subgraph-subsequence definitions?

Q2. Is it possible to show one application-driven query, explain why its retrieved sequences are useful, and demonstrate the main benefit?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.