A Neural Subgraph Matching Model for Graph Sequence Retrieval

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.