# Detecting dynamic patterns in dynamic graphs using subgraph isomorphism

Kamaldeep Singh Oberoi, Géraldine del Mondo, Benoit Gaüzère, Yohan

Dupuis, Pascal Vasseur

► To cite this version:

Kamaldeep Singh Oberoi, Géraldine del Mondo, Benoit Gaüzère, Yohan Dupuis, Pascal Vasseur. Detecting dynamic patterns in dynamic graphs using subgraph isomorphism. Pattern Analysis and Applications, 2023, 26 (3), pp.1205-1221. 10.1007/s10044-023-01145-z. http://dx.doi.org/10.1007/s10044-023-01145-z

HAL Id: hal-0401116

https://hal.science/hal-0401116v1

Submitted on 2 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Detecting Dynamic Patterns In Dynamic Graphs
Using Subgraph Isomorphism

Kamaldeep Singh Oberoi¹,², Géraldine Del Mondo¹*,
Benoît Gaüzère¹, Yohan Dupuis³, Pascal Vasseur⁴,⁵

¹Normandie Univ, INSA Rouen, LITIS, 76000 Rouen, France

²IRIT, University of Toulouse, CNRS, UT3, Toulouse, France

³LINEACT CESI, CESI, 92074 Paris La Défense, France

⁴Normandie Univ, UNIROUEN, LITIS, 76000 Rouen, France

⁵Laboratoire MIS - Université de Picardie Jules Verne - Amiens,
France

## Abstract

Graphs have been used in different fields of research for performing structural analysis of various systems. In order to compare the structure of two systems, the correspondence between their graphs has to be verified. The problem of graph matching, especially subgraph isomorphism (SI), has been well studied in case of static graphs. However, many applications require incorporating temporal information, making the corresponding graphs dynamic. In this paper, we apply SI to detect dynamic patterns in dynamic graphs. We propose an algorithm for induced SI to detect all the matchings for a given pattern graph while considering snapshot-based representation of dynamic graphs and taking into account the chronological order of these snapshots. This is the novelty of the proposed approach since the existing state-of-the-art algorithms model dynamic graphs using an aggregated model with time-stamped edges. To the best of our knowledge, there does not exist another approach which considers snapshot-based representation of dynamic pattern and dynamic target graphs for this problem. We discussed the time complexity of our algorithm and tested its performance while comparing it with two existing algorithms using the real-world datasets. It was found that our algorithm is the second best overall in terms of the execution time. The results are promising given the fact that the choice of dynamic graph model affects the algorithmic design for solving the problem of SI. For the applications where aggregated model of dynamic graphs is not applicable and snapshot-based representation is indispensable, our algorithm can be directly applied as opposed to the existing ones.

<footnote>*Corresponding author</footnote>
# 1 Introduction

Graphs have been in use in various fields of research such as bioinformatics, telecommunication, social networks etc. The main idea of using a graph is to model the structure of the underlying system in terms of its constituents (represented using nodes) and their interactions (represented using edges). To verify if two given systems, modeled using graphs, are similar or exactly the same, or if one system is a sub-system of another, their corresponding graphs have to be examined. The problem of determining the exact correspondence between graphs falls under the realm of *exact graph matching* [9], and *Subgraph Isomorphism (SI)* is one such problem. In SI, the objective is to find an injective mapping between the nodes of the two graphs while preserving the adjacency as well as the non-adjacency (induced SI) between the nodes. The graph to be matched is referred to as the *pattern graph* and the graph in which the matching has to be searched is called the *target graph*. SI finds applications in various fields. For example, in bioinformatics, target graphs represent molecules or protein interaction networks within which some user-defined patterns are detected [4]. In social network analysis, target graphs represent relationships between people (for example, drug traffickers in [15]) which are analysed to find interesting patterns. In video analysis for object tracking, target graphs represent the adjacency between different object planes present in the video and the pattern graph represents the object to be tracked in that video [13].

Most of the existing research related to SI either considers both pattern and target graphs to be static [9] or considers target graphs to be dynamic in which static patterns have to be detected [13, 33]. However, time can also be incorporated in the pattern graph in order to model dynamic patterns. Recently, some research has been published where dynamic patterns are detected in dynamic target graphs. For example, [28] proposes an algorithm to efficiently detect 2-node and 3-node, 3-edge dynamic patterns in dynamic graphs. The approach presented in [28] is further extended in [23] to detect larger patterns in larger target graphs. More recently, an algorithm, called RI [4], initially proposed to solve SI in static graphs, has been extended to dynamic graphs [22, 26].

In our opinion, the problem of SI in case of dynamic pattern and target graphs is still at the early stage of development and has not yet reached its full maturity. The existing approaches model a dynamic graph $\mathcal{G}$ as an “aggregated” graph with its edges annotated with the time instants and/or time intervals at which they are present. Such an aggregated model (with time-stamped edges) of dynamic graphs has been applied to represent events such as telephone calls between two individuals [1, 20], chronological events in a company [23], for detecting dynamic communities in dynamic graphs [30] etc. However, there exist applications where this modeling approach is not suitable and a snapshot-based model, where a dynamic graph $\mathcal{G}$ is represented using a set of static graphs (snapshots) $G_i$ at time $t_i \in T$, is preferred (here $T$ represents the time domain of $\mathcal{G}$). In the literature, this approach has been applied for link prediction [14], for detecting small-world behaviour [36], for graph clustering [12] etc. in dynamic graphs. The main difference between the two approaches, in
terms of the definition of the model is that, in the former, the temporal order in which the edges appear in the graph is important, while in the latter, the temporal order of the entire snapshots, which represents the evolution of the graph over time, takes precedence.

In addition, concerning the formulation of the problem of SI, the representation of the dynamic graph, either using aggregated model with time-stamped edges or using graph snapshots, affects the way the algorithms are designed. For example, the algorithms proposed in [28], [23] and [26] first map the corresponding edges between pattern and target graphs, and then check for nodes, to find suitable matchings. However, this method is not suitable when the sequence of graph snapshots is considered. In this case, as in case of static graphs [9], the corresponding nodes between the pattern and target graphs have to be mapped before checking for the edges in order to find suitable matchings. This could be attributed to the algorithmic design choice since in case of aggregated representation, the temporal order of the edges presents a constraint which should be solved first before checking for the correspondence between the nodes, whereas in case of snapshot-based representation, the snapshot to be matched is a static graph, hence this constraint is absent. However, as mentioned before, the temporal order of the entire sequence of snapshots has to be considered.

In this paper, considering the snapshot-based representation of dynamic graphs, we propose an algorithm to find all the induced subgraphs of dynamic target graph isomorphic to a dynamic pattern graph. Our algorithm takes into account the chronological order of the snapshots of both graphs and maps the corresponding nodes (before checking the edges) to find the solution(s). To the best of our knowledge, there does not exist another algorithm which considers snapshot-based representation to solve the problem of SI in case of dynamic pattern and dynamic target graphs. The core of our algorithm is the algorithm VF3 [6] which was developed for SI in static graphs. Our choice of using VF3 is due to its performance outlined in [7]. Using the knowledge of previously matched nodes of the pattern graph, we propose the pruning strategy in order to reduce the size of the state-space of VF3. To showcase the performance of the proposed algorithm, we tested and compared it with two existing state-of-the-art algorithms using real-world datasets as target graphs and synthetically generated pattern graphs. It was found that the runtime of our algorithm was at par with the existing algorithms and in case of larger graphs, it was better than one of the existing algorithms. Hence, the proposed algorithm can easily be applied to applications where snapshot-based representation of dynamic graphs is required without having to compromise on the overall performance.

The paper is organised as follows. Section 2 describes the related work for the problem of SI. We discuss the existing approaches for the case of static and dynamic graphs and conclude that for dynamic graphs, the approach proposed in this paper is novel. In Section 3, we formalize the problem of subgraph isomorphism for dynamic graphs using the snapshot-based representation. Before delving into the details of the proposed algorithm in Section 5, we describe the main concepts behind VF3 in Section 4. Section 6 presents the experiments performed, the compar-
ison with existing algorithms and discusses the results obtained. Finally, Section 7 concludes the paper.

# 2 Related work

## 2.1 Subgraph isomorphism for static graphs

The problem of exact graph matching has been well studied by Pattern Recognition community in the last decades [9, 39] and graph isomorphism is its most restrictive form requiring the mapping between the nodes of the two graphs while preserving node adjacency as well as non-adjacency. Its variant, subgraph isomorphism (SI), which is the focus of this paper, is known to be NP-Complete in the general case [10].

Various techniques are present in the literature which solve SI by using some heuristics and pruning strategies to reduce the overall runtime. One of the famous algorithms, which is based on tree-based search and backtracking strategy was proposed by Ullmann [37], and was applied to both graph and subgraph isomorphism problems. In the same year, another contribution, also based on backtracking, was made for solving graph isomorphism problem for directed graphs [32]. Other noteworthy algorithms which use tree-based search strategy are VF2 [11], L2G [2], RI [4] and VF3 [6]. Both VF2 and VF3 use a set of feasibility rules to prune the search space, however, VF3 also considers the order on the nodes of the pattern graph to match most constrained nodes first. RI also takes the approach of ordering the nodes on the basis of their structural information. L2G focuses on the backtracking stage in the matching process and improves the pruning power and scalability.

SI could also be modeled as a constraint satisfaction problem (CSP) where the nodes of the pattern graph are assigned different domains i.e., the set of nodes of the target graph which could be mapped to a particular node of the pattern graph. The objective here is to reduce the size of this domain while satisfying the conditions required for isomorphism. This approach was introduced by McGregor [25] and was later enhanced in [34, 38].

Another perspective for applying the techniques of exact graph matching is proposed by Database research community which looks for a given pattern graph in a large database of target graphs. While querying a database of graphs, they propose indexing techniques which directly incorporate the structure and semantics of the query graph and help to reduce the time required to process the query. GraphGrep [17] is one such method designed for querying graph databases. It uses graph expression based query language and prunes the search space by using path-based indexing. He et al. [18] propose graph query language which uses generalized graph matching operator while querying graph database. It uses a pruning strategy based on the neighbourhood and the radius of the node to be included in the mapping.
## 2.2 Subgraph isomorphism for dynamic graphs

Although most of the research for SI has been focused on static graphs, recent years have seen an emerging interest for dealing with this problem in case of dynamic graphs. Kovanen et al. [19] introduce the framework of temporal motifs defined as the isomorphic temporal subgraphs of dynamic graphs having edges representing consecutive temporal events (aggregated model of dynamic graphs). Isomorphism for such (temporal) subgraphs takes into account their topology as well as the temporal order on their edges. To search for temporal motifs in target graphs, both these properties need to be satisfied, which can be done in different orders. Redmond et al. [29] have proposed three methods - Topology before Time, Time before Topology, and Time and Topology Together - and have compared their performance, reaching to the conclusion that the hybrid approach has the least computational complexity. They consider a temporal order on the edges of the temporal motif and look for the matchings where the edges follow the same order.

Another interesting approach to deal with temporal motifs and to prune the search space is to define a time window within which all the edges belonging to the matched subgraph must occur. Temporal motifs which define such restriction are termed as $\delta$-temporal motifs [28]. Such motifs/patterns have also been searched by the approach described in [23]. Patterns considered in [23] have single edge at each time instant and the temporal order on the edges is given importance to find suitable matchings within a given time window (aggregated model of dynamic graphs).

Recently, the algorithm RI [4], originally developed for static graphs, has been extended to dynamic graphs and the new algorithm proposed is called TemporalRI [22, 26]. The first version of TemporalRI maps the corresponding nodes of pattern and target graphs to find suitable matchings [22], and the second version matches the corresponding edges first and then checks for the nodes [26]. However, none of the two versions of this algorithm allow multiple edges at a given time instant between two nodes and both consider the aggregated model of dynamic graphs.

The need to apply subgraph search in dynamic graphs also appears in case of streaming graphs, where a stream of graphs is queried in a continuous fashion, while the graph is being updated, to find isomorphic subgraphs [8, 35]. Instead of starting the subgraph search from scratch each time the graph stream gets updated, these algorithms perform graph matching in an online fashion while keeping track of partial matchings obtained in the previous time steps [16]. Schiller et al. [31] developed an algorithm to count 4-vertex motifs in streaming graphs. They define motif as a class of isomorphic subgraphs which are searched while continuously updating the given graph. However, they give the classes of such subgraphs as input to the algorithm and update their frequencies without actually solving the problem of SI. A similar approach is taken by [27] to count the frequency of motif instances in a given graph.
## 2.3 Concluding remarks about related work

It is clear that the problem of SI has been well studied for static graphs and there has been a growing interest for this problem in the realm of dynamic graphs. However, the formalisation of dynamic graphs changes the way this problem is approached and the existing work only considers the aggregated model of dynamic graphs with time-stamped edges. However, to understand and/or visualize the evolution of a dynamic graph over time, it is of interest to model dynamic graphs as a sequence of snapshots [3, 5]. For such use cases, the existing algorithms for subgraph isomorphism in dynamic graphs cannot be applied directly. The contribution of this paper is the algorithm which can be applied to find all the subgraphs of a dynamic target graph isomorphic to a dynamic pattern graph, where both pattern and target graphs are represented as a sequence of snapshots. Streaming graphs and related algorithms are out of scope of this paper. The related work is mentioned for the sake of completeness.

# 3 Problem formulation

We start by considering a simple static graph $G = (V, E)$ with a set of nodes $V$ and set of edges $E \subseteq V \times V$. Given a pair of static pattern graph $H = (V_H, E_H)$ and static target graph $G = (V_G, E_G)$, the problem of SI is to find an injective mapping $\mu$ between the nodes of the two graphs. Mathematically, $\mu \subset V_H \times V_G$ represents a set of pairs of mapped nodes of pattern and target graphs. Following equations give the formal definition of the problem.

$$ \forall u \in V_H, \exists v \in V_G \mid (u, v) \in \mu \qquad (1) $$

$$ \forall u, \forall u' \in V_H, u \neq u' \mid \{(u, v), (u', v')\} \in \mu \Leftrightarrow v \neq v' \qquad (2) $$

$$ \forall (u, u') \in E_H, \exists (v, v') \in E_G \mid \{(u, v), (u', v')\} \in \mu \qquad (3) $$

$$ \forall u, \forall u' \in V_H, \forall (v, v') \in E_G \mid \{(u, v), (u', v')\} \in \mu \Leftrightarrow (u, u') \in E_H \qquad (4) $$

Equations 1 and 2 state that all distinct nodes of the $H$ must be mapped to some (but distinct) nodes of $G$. Equation 3 states that all edges of $H$ are mapped to some edges of $G$. Lastly, Equation 4 verifies the “induced” version of SI by checking that a mapped edge of $G$ has a corresponding edge in $H$. Note that in Equations 2 and 4, the double-sided arrow (representing “if and only if”) means that both left and right side should be true for the equation to be true. Additionally, if all conditions mentioned above are satisfied, we represent SI between graphs $H$ and $G$ as $\mu: H \hookrightarrow G$. Otherwise, we use the notation $H \not\hookrightarrow G$.

Next, we define a simple dynamic graph $\mathcal{G} = (V_G, E_G, \mathcal{T}_G)$ with set of nodes $V_G$ and set of edges $E_G$. Its time domain $\mathcal{T}_G$ is considered to be discrete and can be represented as a set of time instants $\mathcal{T}_G = \{t_1, t_2, ..., t_k\}$. We consider a snapshot-based model where a graph snapshot $G_i$ at time instant $t_i$ represents its state. Following this, a dynamic graph can be represented as a set of its discrete states, i.e., $\mathcal{G} = \{G_1, G_2, ..., G_k\}$. Given a pair of dynamic pattern graph $\mathcal{H} = (V_H, E_H, \mathcal{T}_H) = \{H_1, H_2, ..., H_m\}$, having $m$ snapshots, and dynamic target graph $\mathcal{G} = (V_G, E_G, \mathcal{T}_G) =$
`$\{G_1, G_2, ..., G_n\}$`, having $n$ snapshots, with $m \le n$, the problem of induced SI can be extended to dynamic graphs, i.e.,

* Each snapshot of $\mathcal{H}$ must be mapped to some snapshot of $\mathcal{G}$ while respecting the equations of induced SI mentioned above. Formally,

$$ \forall H_i \in \mathcal{H}, 1 \le i \le m, \exists \mu_{ij} : H_i \hookrightarrow G_j, G_j \in \mathcal{G}, 1 \le j \le n \quad (5) $$

* The temporal order of $\mathcal{H}$ and $\mathcal{G}$ must be respected, i.e., if a snapshot $H_i, 1 \le i \le m$ of $\mathcal{H}$ is mapped to a snapshot $G_j, 1 \le j \le n$ of $\mathcal{G}$, then the next snapshot $H_{i+1}$ of $\mathcal{H}$ must be mapped to some snapshot $G_f$ of $\mathcal{G}$ where $f > j$. Formally,

$$ \begin{array}{l} \forall H_i \in \mathcal{H}, 1 \le i \le m, \exists \mu_{ij} : H_i \hookrightarrow G_j, G_j \in \mathcal{G}, 1 \le j \le n \Leftrightarrow \\ \phantom{\forall H_i \in \mathcal{H}, 1 \le i \le m, \exists \mu_{ij} : } \exists \mu_{(i+1)f} : H_{i+1} \hookrightarrow G_f, G_f \in \mathcal{G}, j < f \le n \end{array} \quad (6) $$

* To find a complete matching of $\mathcal{H}$, a node $v \in V_{\mathcal{H}}$ must be mapped to the same node $v' \in V_{\mathcal{G}}$ at every time instant where the matching is possible and both nodes $v$ and $v'$ exist. Formally,

$$ \begin{array}{l} \forall H_i \in \mathcal{H}, 1 \le i \le m, \exists \mu_{ij} : H_i \hookrightarrow G_j, G_j \in \mathcal{G}, 1 \le j \le n \Leftrightarrow \\ \phantom{\forall H_i \in \mathcal{H}, 1 \le i \le m, \exists \mu_{ij} : } \exists v \in V_{H_i} \wedge v' \in V_{G_j} | (v, v') \in \mu_{ij}, \forall v \in V_{H_i} \wedge \forall v' \in V_{G_j} \end{array} \quad (7) $$

* It is possible to have some snapshots of $\mathcal{G}$ to which no snapshots of $\mathcal{H}$ are matched. Such snapshots represent noise. We include such snapshots of target graph to be more realistic in terms of the sampling rate. For real-world applications, depending on this sampling rate, it is possible to have some snapshots in which no matching is found. Formally,

$$ \exists G_j \in \mathcal{G}, 1 \le j \le n | H_i \not\to G_j, H_i \in \mathcal{H}, 1 \le i \le m \quad (8) $$

Figure 1 shows an example where the pattern graph has five snapshots and the target graph has seven snapshots. The pattern and target graph snapshots are matched as follows: $H_1 \to G_1, H_2 \to G_2, H_3 \to G_3, H_4 \to G_4$ and $H_5 \to G_7$, while nodes of the pattern graph are matched as: $A1 \to A100, A4 \to A35, A5 \to A15$ and $A3 \to A25$. Note that the temporal order of $\mathcal{H}$ is maintained in the solution found and a node of the pattern graph (e.g. $A1$) is matched to the same node of target graph ($A100$) at every time instant where the matching between $\mathcal{H}$ and $\mathcal{G}$ is possible and the nodes $A1 \in V_{\mathcal{H}}$ and $A100 \in V_{\mathcal{G}}$ exist. Some target graph snapshots ($G_5$ and $G_6$) represent “noise”, i.e., they are not matched to any snapshot of the pattern graph.

# 4 Description of VF3 algorithm

VF3 falls in the category of algorithms which use a state-space representation, with backtracking, to keep track of the partial matchings. The state-space is represented as a tree whose nodes represent distinct states. A state is the candidate pair of nodes of pattern and target graphs. It
<figure><img src="image_2.png" /><figcaption>Figure 1: Example showing snapshots of target graph $\mathcal{G}$ and pattern graph $\mathcal{H}$ with detected pattern highlighted in $\mathcal{G}$. Snapshots $G5$ and $G6$ of $\mathcal{G}$ represent “noise” and are not mapped to any snapshot of $\mathcal{H}$. Set of nodes in both graphs remains constant over time but the isolated nodes are not shown</figcaption></figure>
is said to be “consistent” if the partial mapping between the pattern and
target graphs satisfies the conditions of SI. All consistent states, with
complete mapping of the pattern graph, represent “goal” states. Starting
from an empty initial state, VF3 progressively develops the state-space
for all nodes of the pattern graph to find suitable matchings. If an “in-
consistent” state is encountered, the algorithm backtracks to the previous
state and continues the search from a different candidate pair. The algo-
rithm VF3 can be broken down into three steps: (1) ordering the nodes
of the pattern graph, (2) computing feasibility sets for pattern and target
graphs, and (3) the matching process.

4.1 Ordering the nodes of pattern graph

To determine the order in which the nodes of the pattern graph should
be explored, VF3 generates the node exploration sequence before start-
ing the matching procedure. The calculation of this sequence is based
on computing the probability that a node *u* of the pattern graph has a
corresponding node *v* in the target graph. This probability function takes
into account the structural and semantic information of both pattern and
target graphs (the semantic information may represent the node labels).
The generated ordering sequence is to used to formalise, in part, the states
in the state-space, i.e., the nodes corresponding to the pattern graph are
incorporated, according to this order, into the state-space before starting
the matching procedure. The depth of the state-space depends on the
number of nodes of the pattern graph.

4.2 Computing feasibility sets

VF3 uses some sets to find the appropriate candidate pair. These sets,
called feasibility sets, are computed for both pattern and target graphs.
Since the node exploration sequence for the pattern graph is calculated
before starting the matching procedure, it is, in turn, used to calculate the
feasibility sets once for the pattern graph. However, the feasibility sets for
the target graph are updated during the matching process. Concretely,
the feasibility sets are the sets of nodes of pattern and target graphs which
are not included in the mapping $\mu$ but are connected to the nodes already
present in $\mu$. In the original paper, there are two kinds of feasibility sets,
called predecessor feasibility sets and successor feasibility sets, since the
authors have considered the graphs to be directed. However, they can
easily be defined for undirected as well as labeled graphs.

4.3 Matching process

The matching process starts from an initial empty state. Using the node
exploration sequence generated previously, the pattern graph node for
each level of the state-space is fixed. Then, starting from the first node in
the sequence, the algorithm looks for the appropriate target graph node.
First, a set of potential candidates among all the unmatched nodes of the
target graph is computed. For each candidate pair of nodes, before adding
it to the state-space, VF3 verifies if it is feasible, i.e., if it satisfies the conditions of SI and whether it will lead to further consistent states. For this, VF3 applies 1-lookahead and 2-lookahead rules which check if the current candidate pair, if added in the state-space, will lead (or not) to a consistent state in one step (or in two steps). This is done using the feasibility sets of the target graph. The objective here is to restrict the size of the state-space and improve the overall performance. If the current candidate pair satisfies all three conditions, it is added as a consistent state in the state-space, the feasibility sets of target graph are updated, and the algorithm moves on to the next possible pair of nodes. It is noteworthy that the state-space is extended following the depth-first process. If, however, the current candidate pair is not feasible, the algorithm backtracks to the previous consistent state and checks other candidate pair of nodes. In the end, the goal states, containing the mappings for all pattern graph nodes, represent the final solution. Since there could be multiple matchings, it is possible to have multiple goal states.

## 4.4 Time complexity analysis

It is important to discuss the time complexity of VF3 since it would help in understanding the time complexity of our algorithm presented in the next section.

The algorithm VF3 is inspired by another algorithm called VF2 [11] which also uses the tree-based search strategy with backtracking for solving the problem of SI in static graphs. The tree represents the state-space which has to be explored to find suitable matchings between the two graphs. In the original paper of VF2, the time complexity is calculated in terms of the size of the state-space to be explored, and in the worst-case is given as $O(N \cdot N!)$ while the best-case is given as $O(N^2)$, where N represents the number of nodes.

The motivation behind VF3 is to improve the state-space exploration by restricting the number of un-feasible states in the state-space. This is done using some heuristics and pre-computing some data structures before starting the matching process. In this paper, we discuss three steps of VF3 and in this section we will describe the time complexity for each step.

The first step of VF3, i.e., ordering the nodes of the pattern graph is a two-step process: (1) calculation of the probability value for each pattern graph node and (2) ordering the nodes according to this probability value. In the original article of VF3 [6], the complexity to calculate the probability is mentioned as $O(\|V_H\|)$, where $\|V_H\|$ is the number of nodes of the pattern graph $H$. Theoretically, sorting these nodes can be done using an existing sorting algorithm such as quicksort with the worst-case time complexity of $O(\|V_H\|^2)$. Hence, the overall worst-case time complexity for this step becomes $O(\|V_H\|^2)$.

Next, pre-computing the feasibility set for the pattern graph depends on the degree of each node of $H$ included in the mapping $\mu$ and the depth of the state-space to be explored. The degree of a node in the pattern graph is proportional to the total number of edges in the graph, i.e., $O(\|E_H\|)$ and the depth of the state-space is $\|V_H\| - 1 \approx O(\|V_H\|)$. Hence, the time complexity to pre-compute the feasibility set of the pattern graph is
$\mathcal{O}(\|V_H\| \cdot \|E_H\|)$. The feasibility set for the target graph $G$ is calculated during the matching process.

Finally, using the candidate selection process and predefined node ordering of the pattern graph nodes, less un-feasible states are generated and the size of the state-space is reduced during the matching process. A loose upper-bound on the time complexity of the matching process of VF3 can be given as $\mathcal{O}(\|V_H\| \cdot \|V_G\|)$. Hence, the overall time complexity of VF3 can be given as $\text{Comp}(\text{VF3}) = \mathcal{O}(\|V_H\|^2) + \mathcal{O}(\|V_H\| \cdot \|E_H\|) + \mathcal{O}(\|V_H\| \cdot \|V_G\|)$.

Here, it is important to note that VF3 introduced heuristics, like ordering the nodes and pre-computing the feasibility set of the pattern graph, to perform better than VF2. However, there could be cases where these heuristics do not work.

For example, the nodes of the pattern graph are ordered on the basis of the probability that, for a given pattern node, a corresponding node exists in the target graph. As mentioned above, this probability is calculated using structural (and semantic, if required) information about both graphs. Now, it is possible to have the same probability value for each pattern node and in this case, the node ordering does not make much sense.

Furthermore, given the feasibility sets for both graphs, finding the right node mapping may require high complexity since the choice for node mapping made at the first step may have consequences on all other node mappings.

Hence, in the worst-case, where the heuristics introduced in VF3 do not work, the complexity of VF3 approaches the worst-case complexity of VF2. Although, as shown empirically in the original paper of VF3 [6], VF2 performs worse than VF3, thanks to these heuristics and in practical situations, we can do better with VF3 [7]. Finally, SI in general case rests NP-Complete [10].

In the next section, after presenting our algorithm, we will discuss its time complexity while considering that VF3 performs optimally.

# 5 Proposed algorithm

In this section we will present our algorithm. It takes as input the dynamic pattern graph $\mathcal{H}$ and the dynamic target graph $\mathcal{G}$, given as the sets of their static snapshots $\mathcal{H} = \{H_1, ..., H_m\}$ and $\mathcal{G} = \{G_1, ..., G_n\}$ respectively, with $m \le n$, and returns all the matchings between these two graphs if they exist. Given the definition of SI for dynamic graphs (see Section 3), the proposed algorithm performs optimally.

We start the matching process from the first pattern graph snapshot and enumerate through all the snapshots (Algorithm 1). Hence, the description of the algorithm follows the same order.

## 5.1 Matching first pattern graph snapshot

To match the first pattern graph snapshot with one (or more) target graph snapshots (Algorithm 2), we apply VF3 recursively, taking as inputs $H_1 \in \mathcal{H}$ and $G_j \in \mathcal{G}, 1 \le j \le n-m+1$. At this stage, the state-space for
**Algorithm 1 Main($\mathcal{H}$, $\mathcal{G}$)**
1: *Tree* ← $\emptyset$
2: *root* ← *null*
3: **for** i = 1 to m **do**
4:     *Solution*<sub>*i*</sub> ← $\emptyset$
5:     $\mathcal{G}_i$ ← $\emptyset$
6:     **if** i = 1 **then**
7:         *Tree* = MapFirstPatternGraph(*i*, *n*, *m*, *Solution*<sub>*i*</sub>, $\mathcal{G}_i$, *Tree*)
8:         **end if**
9:     **if** i > 1 **then**
10:         *Tree* = MapNextPatternGraphs(*i*, *n*, *m*, *Solution*<sub>*i*</sub>, $\mathcal{G}_i$,
11:                                     *Solution*<sub>(*i*−1)</sub>, $\mathcal{G}_{i-1}$, *Tree*)
12:     **end if**
13: **end for**
14: *P* ← $\emptyset$
15: *P* = GetRootLeafPaths(*Tree*)
16: **for all** *rlp* ∈ *P* **do**
17:     **if** len(*rlp*) = m + 1 **then**
18:         $\mu_{\mathcal{H}\mathcal{G}}$ = {*µ* | $\forall$*µ* ∈ *rlp*}
19:     **end if**
20: **end for**

$\triangleright$ stores all possible matchings for $H_i$
$\triangleright$ stores all induced subgraphs isomorphic to $H_i$

every call to VF3 starts from an empty initial state, and we get all possible
matchings for the snapshot $H_1$ (which are stored in the set $Solution_{ij}$,
line 5; Algorithm 2). The subgraph of $G_j$ induced by the matching $\mu_{ij}$
is given as $g_{ij}$. Since we want to find the matchings for all the snapshots
of the pattern graph in the given target graph sequence (according to the
conditions described in Section 3), while matching $H_1$, we do not need to
check the target graph snapshots for $j > n - m + 1$. Hence, the search
space is limited to some extent.

5.2 Matching next pattern graph snapshots

Once we have all possible matchings for $H_1$, we continue to match next
pattern graph snapshots $H_i$, $1 < i \le m$ (Algorithm 3).

For a snapshot $H_i$ (current pattern snapshot to be matched), present
at time instant $t_i \in T_{\mathcal{H}}$, $1 < i \le m$, we compare its node set ($V_{H_i}$) with the
node set ($V_{H_{i-1}}$) of the previous snapshot $H_{i-1}$ which is already matched
(lines 1-2; Algorithm 3). Since VF3 maps all the nodes of a given pattern
graph, the nodes common between $V_{H_i}$ and $V_{H_{i-1}}$ were already mapped
while matching $H_{i-1}$. Our objective here is to use this knowledge to prune
the state-space of VF3. Hence, if there exist nodes in $H_i$ which did not
exist in $H_{i-1}$, we call the function FindNewMapping(), else we call the
function UsePreviousMapping() (line 3-7; Algorithm 3).

Let us suppose that the previous snapshot $H_{i-1}$ gets matched to some
snapshot $G_j$ (with node set $V_{G_j}$) of the target graph (at time instant
$t_j \in T_G$) (Algorithm 4). Corresponding matching between two graphs can
be written as $\mu_{(i-1)j}$ which is a set of pair of nodes of snapshots $H_{i-1}$ and
<caption>**Algorithm 2 MapFirstPatternGraph(i, n, m, Solution<sub>i</sub>, G<sub>i</sub>, Tree)**</caption>

1: **for** j = 1 to n - m + 1 **do**
2:     Solution<sub>ij</sub> ← ∅
3:     G<sub>ij</sub> ← ∅
4:     **if** VF3(H<sub>i</sub>, G<sub>j</sub>) = true **then**
5:         Solution<sub>ij</sub> ← {μ<sub>ij</sub> | μ<sub>ij</sub> = V<sub>H<sub>i</sub></sub> × V<sub>g<sub>ij</sub></sub>, g<sub>ij</sub> ⊂ G<sub>j</sub>}
6:         ▷ Solution<sub>ij</sub> stores all matchings between H<sub>i</sub> and G<sub>j</sub>
7:         Add μ<sub>ij</sub> as child node of root in Tree
8:         Insert Solution<sub>ij</sub> in Solution<sub>i</sub>
9:         G<sub>ij</sub> ← {g<sub>ij</sub> | g<sub>ij</sub> ⊂ G<sub>j</sub>}
10:        ▷ G<sub>ij</sub> is set of subgraphs of G<sub>j</sub> isomorphic to H<sub>i</sub>
11:        ▷ len(Solution<sub>ij</sub>) = len(G<sub>ij</sub>)
12:    9: Insert G<sub>ij</sub> in G<sub>i</sub>
10: **end if**
11: **end for**
12: **return** Tree

<caption>**Algorithm 3 MapNextPatternGraphs(i, n, m, Solution<sub>i</sub>, G<sub>i</sub>, Solution<sub>(i-1)</sub>, G<sub>i-1</sub>, Tree)**</caption>

1: NAM<sub>i</sub> ← V<sub>H<sub>i</sub></sub> ∩ V<sub>H<sub>i-1</sub></sub>
2: NNM<sub>i</sub> ← V<sub>H<sub>i</sub></sub> - NAM<sub>i</sub>
3: **if** NNM<sub>i</sub> ≠ ∅ **then**
4:     Tree = FindNewMapping(i, n, m, NAM<sub>i</sub>, NNM<sub>i</sub>, Solution<sub>i</sub>, G<sub>i</sub>, Solution<sub>(i-1)</sub>, G<sub>i-1</sub>, Tree)
5:     ▷ set of nodes of H<sub>i</sub> already mapped
6:     ▷ set of nodes of H<sub>i</sub> not mapped
7:     **else**
8:         Tree = UsePreviousMapping(i, n, m, Solution<sub>i</sub>, G<sub>i</sub>, Solution<sub>(i-1)</sub>, G<sub>i-1</sub>, Tree)
9:     **end if**
10: **return** Tree
**Algorithm 4 FindNewMapping(i, n, m, NAMᵢ, NNMᵢ, Solutionᵢ, Gᵢ, Solutionᵢ₋₁, Gᵢ₋₁, Tree)**

1: $\mathbb{F}(H_i) \leftarrow \{u \mid u \in NNM_i, \exists u' \in NAM_i, (u, u') \in E_{H_i}\}$
   ▷ $\mathbb{F}(H_i)$ is the new feasibility set for $H_i$

2: **for** j = i - 1 to n - m + i - 1 **do**

3: $\mu_{(i-1)j} \leftarrow \text{Solution}_{(i-1)j}$
   ▷ previous matchings

4: $\mu'_{(i-1)j} \leftarrow$ subset of $\mu_{(i-1)j}$ with nodes present in $V_{H_i}$ and $V_{G_j}$

5: $g_{(i-1)j} \leftarrow$ subgraph of $G_j$ corresponding to $\mu'_{(i-1)j}$

6: **for** f = j + 1 to n - m + i **do**

7: **if** $g'_{(i-1)j} \subset G_f$ **then**

8: $\mathbb{F}(G_f) \leftarrow \{p \mid p \in V_{G_f}, \exists p' \in V'_{G'_{(i-1)j}}, (p, p') \in E_{G_f}\}$
   ▷ $\mathbb{F}(G_f)$ is the new feasibility set for $G_f$

9: **if** VF3($H_i$, $G_f$, $\mu'_{(i-1)j}$, $\mathbb{F}(H_i)$, $\mathbb{F}(G_f)$) = true **then**

10: $\text{Solution}_{if} \leftarrow \{\mu_{if} \mid \mu_{if} = V_{H_i} \times V_{G_{if}}, g_{if} \subset G_f\}$

11: Add $\mu_{if}$ as the child node of $\mu_{(i-1)j}$ in Tree

12: Insert $\text{Solution}_{if}$ in $\text{Solution}_i$

13: $G_{if} \leftarrow \{g_{if} \mid g_{if} \subset G_f\}$

14: Insert $G_{if}$ in $G_i$

15: **end if**

16: **end if**

17: **end for**

18: **end for**
**return** Tree

$G_j$ (line 3; Algorithm 4). Formally,

$$ \mu_{(i-1)j} = \{(u, v) \mid u \in V_{H_{i-1}} \wedge v \in V_{G_j}\} $$

Note that since both snapshots are static graphs, their node sets are represented using the corresponding notations (Section 3).

The induced subgraph of the snapshot $G_j$, isomorphic to $H_{i-1}$ and corresponding to the mapping $\mu_{(i-1)j}$, is written as $g_{(i-1)j}$. Since $H_i$ is the current snapshot to be matched, we consider only those node pairs in $\mu_{(i-1)j}$ which have the nodes present in $V_{H_i}$ as first part and their corresponding nodes in $V_{G_j}$ as second part (line 4; Algorithm 4). The updated set of matchings is given as $\mu'_{(i-1)j} \subset \mu_{(i-1)j}$ and the updated corresponding subgraph of $G_j$ is given as $g_{(i-1)j}$ (line 5; Algorithm 4).

Since the pattern snapshot $H_i$ occurs after (in the future of) the snapshot $H_{i-1}$, it must be matched to some snapshot $G_f$ of the target graph such that $f > j$. For this, we need to look for the subgraph $g'_{(i-1)j}$ in every snapshot $G_f$, $f > j$ of the target graph. Note that, here, we do not need to check all the snapshots of the target graph with index $f > j$. We use the *sliding window* (Figure 2) to define the limits within which the snapshot $H_i$ should be matched. Since we have to match all the snapshots of the pattern graph to find the complete solution, $H_i$ must be matched to some snapshot $G_f$ with $j < f \le n - m + i$. Here, again, some limitation is applied to restrict the size of the search space. For example, from Figure 2, if the snapshot $H_1$ gets matched to the snapshot $G_3$, then the matching
<figure><img src="image_3.png" /><figcaption>Figure 2: The location of the sliding window within which a match has to be searched depends on the index of the pattern graph snapshot, and its size depends on the number of snapshots of both graphs</figcaption></figure>

for the snapshot $H_2$ has to be searched in snapshot $G_4$ only.

### 5.2.1 Pruning the state-space of VF3

Once the snapshot $G_f$ of the target graph containing the subgraph $g'_{(i-1)j}$ of $G_j$ is selected, we need to apply VF3 again to map the un-mapped nodes of $H_i$ (the nodes which were not present in $H_{i-1}$). Hence, taking $H_i$ and $G_f$ as inputs we apply VF3 again. However, here we use the knowledge of the previously mapped nodes to prune the state-space of VF3.

Instead of starting from an empty initial state in the state space, as is done in the static version of VF3 or while matching $H_1$, we start with non-empty initial state represented using the mapping $\mu'_{(i-1)j}$, and continue with VF3 until all the un-mapped nodes of $H_i$ are mapped (line 9; Algorithm 4). To achieve this, we re-define the feasibility sets for both $H_i$ and $G_f$ (lines 1, 8; Algorithm 4). Recall that the feasibility set is the set of nodes of a graph which are neighbors of the nodes included in the mapping, and is defined for both pattern and target graphs to implement VF3 [6]. Finally, the matchings found between the snapshots $H_i$ and $G_f$ are stored in the set $Solution_{if}$ (line 10; Algorithm 4) and the corresponding subgraphs are stored in $G_{if}$ (line 13; Algorithm 4).

### 5.2.2 Matching pattern snapshots without using VF3

It is also possible that the node set of $H_i$ (the current pattern snapshot to be mapped) is the subset of the node set of $H_{i-1}$ (previous pattern snapshot which is already mapped), i.e., all the nodes of $H_i$ were also present in $H_{i-1}$ (Algorithm 5). In this case, since all the nodes of $H_{i-1}$ were mapped in the previous iteration, there is no need to apply VF3 again while matching the current snapshot $H_i$. We just need to look for the suitable target snapshot $G_f$ which contains the subgraph $g'_{(i-1)j}$ of $G_j$ in order to respect the temporal order in the final solution. This, in turn, increases the overall efficiency of the algorithm.
<caption>**Algorithm 5** UsePreviousMapping(i, n, m, Solution<sub>i</sub>, G<sub>i</sub>, Solution<sub>(i-1)</sub>, G<sub>i-1</sub>, Tree)</caption>

1: **for** j = i - 1 to n - m + i - 1 **do**
2: &nbsp;&nbsp;&nbsp;&nbsp;μ<sub>(i-1)j</sub> ← Solution<sub>(i-1)j</sub>
3: &nbsp;&nbsp;&nbsp;&nbsp;μ'<sub>(i-1)j</sub> ← subset of μ<sub>(i-1)j</sub> with node pairs present in V<sub>H<sub>i</sub></sub> and V<sub>G<sub>j</sub></sub>
4: &nbsp;&nbsp;&nbsp;&nbsp;g'<sub>(i-1)j</sub> ← subgraph of G<sub>j</sub> corresponding to μ'<sub>(i-1)j</sub>
5: **for** f = j + 1 to n - m + i **do**
6: &nbsp;&nbsp;&nbsp;&nbsp;**if** g'<sub>(i-1)j</sub> ⊂ G<sub>f</sub> **then**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;μ<sub>if</sub> ← μ'<sub>(i-1)j</sub> ▷ current matching is same as previous matching
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Solution<sub>if</sub> ← {μ<sub>if</sub> | μ<sub>if</sub> = V<sub>H<sub>i</sub></sub> × V<sub>g<sub>if</sub></sub>, g<sub>if</sub> = g'<sub>(i-1)j</sub>}
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Add μ<sub>if</sub> as the child node of μ<sub>(i-1)j</sub> in Tree
10: &nbsp;&nbsp;&nbsp;&nbsp;Insert Solution<sub>if</sub> in Solution<sub>i</sub>
11: &nbsp;&nbsp;&nbsp;&nbsp;G<sub>if</sub> ← {g<sub>if</sub> | g<sub>if</sub> ⊂ G<sub>f</sub>}
12: &nbsp;&nbsp;&nbsp;&nbsp;Insert G<sub>if</sub> in G<sub>i</sub>
13: **end if**
14: **end for**
15: **end for**
**return** Tree

5.3 Finding the complete solution

To keep track of the possible matchings for all the pattern graph snapshots, we maintain a *Tree* whose nodes represent the individual matchings (except empty *root* node). *Tree* corresponding to the example pattern and target graph pair in Figure 1 is shown in Figure 3. Matchings computed by looking for the induced subgraph *g*'<sub>(i-1)j</sub> in the snapshot *G*<sub>*f*</sub>, *j* < *f* ≤ *n* − *m* + *i* of the target graph are stored as the children of the node representing the previous matching *μ*<sub>(i-1)j</sub>, and all the matchings corresponding to the snapshot *H*<sub>*i*</sub> of the pattern graph are stored at depth *i*. Hence the maximum depth of *Tree* is equal to the number of snapshots of the pattern graph.

It is evident that there could be multiple matchings between a pair of
pattern and target graph snapshots at the same depth (e.g. μ<sup>1</sup><sub>11</sub> and μ<sup>2</sup><sub>11</sub>
are two separate matchings between H<sub>1</sub> and G<sub>1</sub> at depth 1). The set of
matchings lying on every root-to-leaf path of length m + 1 (considering
path length in terms of the number of nodes present on the path), high-
lighted in blue in Figure 3, gives the final solution and the size of this tree
depends on the number of all the matchings found for each pattern graph
snapshot.

5.4 Time complexity analysis

In this section, we will discuss the time complexity of our algorithm which,
as mentioned before, uses VF3 at its core.

In order to find the matching of the first snapshot $H_1 \in \mathcal{H}$ of the
dynamic pattern graph (Algorithm 2), we apply VF3 recursively between
$H_1$ and $G_j \in \mathcal{G}$, $j \in w = [1, n-m+1]$, where $w$ is the size of the sliding
window within which the solution has to be found. Given the complexity
<figure><img src="image_4.png" /><figcaption>Figure 3: *Tree* maintained throughout the execution of the algorithm. Nodes in blue represent the root-to-leaf path which gives the complete matching between $\mathcal{G}$ and $\mathcal{H}$ in Figure 1</figcaption></figure>

of VF3 as Comp(VF3) (see Section 4.4), the time complexity of Algorithm 2 can be given as $O(w \cdot Comp(VF3))$.

In Algorithm 3 (lines 1-2), the complexity of calculating the set $NAM_i$ of nodes of snapshot $H_i$, $i > 1$ already mapped while mapping the previous snapshot $H_{i-1}$ and the set $NNM_i$ of nodes not mapped depends on the number of nodes of snapshots $H_i$ and $H_{i-1}$ and, in the worst-case, can be given as $O(max(\|V_{H_i}\|, \|V_{H_{i-1}}\|))$.

The objective of Algorithm 4 is to map the nodes of the pattern snapshot $H_i$ which are not previously mapped. Here, the worst case is when all but one nodes of $H_i$ are not mapped, so $\|NNM_i\| = \|V_{H_i}\| - 1 \approx O(\|V_{H_i}\|)$. Hence, the worst-case time complexity to calculate the new feasibility set of snapshot $H_i$ (line 1) is $O(\|V_{H_i}\| \cdot \|E_{H_i}\|)$.

Then, for each target snapshot $G_j$ within the sliding window of size $w = [i-1, n-m+i-1]$, we have to iterate through all the previous matchings found (lines 3-5). McCreesh et al. [24] give the expected
number of matchings for induced subgraph isomorphism between a static pattern snapshot $H_{i-1}$ and target snapshot $G_j$ as

$$ \kappa = \frac{\|V_{G_j}\|! \cdot p(G_j)^{p(H_{i-1})} \cdot \binom{\|V_{H_{i-1}}\|}{2} \cdot (1-p(G_j))^{(1-p(H_{i-1}))} \cdot \binom{\|V_{H_{i-1}}\|}{2}}{\|V_{H_{i-1}}\|!} \quad (9) $$

where $p(G_j)$ (and $p(H_{i-1})$) is the probability of having an edge between a pair of nodes in target snapshot $G_j$ (and pattern snapshot $H_{i-1}$). Since this is induced subgraph isomorphism, the probability of not having an edge (i.e. non-adjacency) between two nodes is also considered to calculate $\kappa$. It is noteworthy that the probability of having an edge is related to the density of the graph, and that $\kappa$ gives an upper-bound on the size of the set $\mu_{(i-1)j}$ (line 3).

For each solution found, the next step is to look for a subgraph $g'_{(i-1)j}$, associated to it, in the snapshot $G_f$ (line 7). The time complexity for this step is proportional to $\|V_{G_f}\|$ and $\|E_{G_f}\|$. Similar to line 1, the feasibility set of $G_f$ is calculated in $\mathcal{O}(\|V_{G_f}\| \cdot \|E_{G_f}\|)$ (line 8) in the worst-case.

Finally, in line 9, we apply VF3 starting from a non-empty initial state to restrict the size of the state-space. In the worst-case, where only one node of $H_i$ is previously mapped (while matching $H_{i-1}$), we have to map all the remaining nodes. Hence the time-complexity of VF3 in this case would be $Comp(VF3) = \mathcal{O}(\|V_{H_i}\|^2) + \mathcal{O}(\|V_{H_i}\| \cdot \|V_{G_f}\|)$. However, in the best case, when only one node of $H_i$ has to be mapped (with all other nodes mapped previously), the time complexity of VF3 becomes $Comp(VF3) = \mathcal{O}(\|V_{G_f}\|)$.

Hence, the overall time complexity of Algorithm 4 is $\mathcal{O}(\|V_{H_i}\| \cdot \|E_{H_i}\|) + w \cdot \kappa \cdot [\mathcal{O}(\|V_{G_f}\| \cdot \|E_{G_f}\|) + Comp(VF3)]$.

Similar to Algorithm 4, the time complexity for Algorithm 5 can be given as $w \cdot \kappa \cdot \mathcal{O}(\|V_{G_f}\| \cdot \|E_{G_f}\|)$ since in this case there is no need to apply VF3 and the feasibility sets are not calculated. However, the subgraphs associated to previous solutions have to be searched.

To find the complete solution using Tree that is maintained throughout the execution, we find all root-to-leaf paths in Tree (lines 14-19, Algorithm 1) with the complexity of $\mathcal{O}(M)$, where $M$ is the number of nodes (individual matchings) in Tree.

In the next section, we perform the experiments to calculate the average runtime of our algorithm with different graph datasets and graph parameters.

# 6 Experiments

In this section, we will outline the experiments conducted to showcase the performance of our algorithm in terms of its runtime. We compare our algorithm with two existing ones, Mackey's algorithm proposed in [23], and the second version of TemporalRI proposed in [26]. Our choice is motivated due to the following reasons:

1. Both these algorithms are developed for solving the problem of induced SI in case of dynamic pattern and dynamic target graphs, al-
beit they represent a dynamic graph using an aggregated model with time-stamped edges as compared to the snapshot-based approach of our algorithm.

2. The general approach of TemporalRI algorithm is to extend an existing algorithm (RI [4]) to the case of dynamic graphs. We have taken a similar approach.

3. To the best of our knowledge, there does not exist another algorithm to solve induced SI which considers snapshot-based model of dynamic graphs.

4. In the original papers of TemporalRI [22, 26], the authors have compared it with Mackey's algorithm as well. Hence, our choice of comparing our algorithm with these two algorithms is meaningful.

5. The code for both these algorithms is provided by the respective authors.

For the comparison, we used two existing graph datasets - Email-Eu-core-temporal and CollegeMsg - available from SNAP Graph Library [21] as target graphs. Email-Eu-core-temporal was generated using email communication between employees of a European research institution. CollegeMsg represents communication between users on an online social network. Both datasets represent directed graphs. However, the proposed algorithm is applicable to undirected graphs as well. For the experiments, the pattern graphs were generated randomly having varying number of nodes and snapshots since our objective was to test our algorithm for different values of pattern graph parameters. However, note that since patterns are random, it cannot be stated that there exists dynamic sub-graph isomorphism between a pattern and target graph pair, and it is possible to find zero graph mappings (solutions) in this case.

We measured the total algorithm runtime, including pre-processing and matching time, excluding, however, the time required to load the graph files. All the experiments were performed on a PC with Intel Core-i7 3.6GHz CPU and 32GB RAM running Ubuntu 18.04 LTS. Our algorithm as well as Mackey's algorithm were implemented in C++, hence they were compiled with GNU C++ compiler (version 7.5.0) with level-3 optimisation whereas TemporalRI algorithm was implemented in Java, hence, was compiled and executed using OpenJDK version 17.0.1.

It needs to be pointed out that the implementation provided by the authors for Mackey's algorithm [23] did not suit our needs since it does not work correctly with the graphs having multiple edges at the same time. After discussing with the authors, we found out that if multiple edges have the same value for time attribute (which means, theoretically, they occur at the same time), the sequential order of occurrence of the edges takes precedence. For example, if two edges *e1* and *e2* have the time attribute *t* but if *e1* is read before *e2* in the list of edges given as input, the algorithm considers *e1* to occur before *e2*. This is suitable for the use cases where edges appear in the chronological order, however, it leads to unwanted matchings in our case. This problem has also been highlighted by the authors of TemporalRI [26], hence they had to slightly modify the implementation to make it work. Since the authors of TemporalRI
<table><caption>Table 1: Results obtained using Email-Eu-core-temporal dataset. Average runtime (in secs), standard deviation, percentage of graph instances solved for each pattern graph parameter are presented for three algorithms. Parameters correspond to zero number of matchings found between graph pairs</caption><thead><tr><th colspan="2">Pattern Graph</th><th colspan="3">Mackey's algorithm</th><th colspan="3">TemporalRI</th><th colspan="2">Our algorithm</th></tr><tr><th>Nodes</th><th>Snapshots</th><th>Time</th><th>Std. Dev.</th><th>%</th><th>Time</th><th>Std. Dev.</th><th>%</th><th>Time</th><th>Std. Dev.</th></tr></thead><tbody><tr><td>2</td><td>5</td><td>3.150</td><td>0.030</td><td>100</td><td>0.789</td><td>0.019</td><td>100</td><td>NULL</td><td>NULL</td></tr><tr><td>2</td><td>10</td><td>701.644</td><td>1.437</td><td>100</td><td>162.562</td><td>2.545</td><td>100</td><td>NULL</td><td>NULL</td></tr><tr><td>2</td><td>30</td><td>NULL</td><td>NULL</td><td>0</td><td>NULL</td><td>NULL</td><td>0</td><td>318.729</td><td>2</td></tr><tr><td>3</td><td>5</td><td>0.942</td><td>0.561</td><td>100</td><td>4.307</td><td>2.157</td><td>100</td><td>38.705</td><td>1</td></tr><tr><td>3</td><td>10</td><td>5.933</td><td>4.169</td><td>100</td><td>194.608</td><td>142.209</td><td>96</td><td>23.122</td><td>1</td></tr><tr><td>3</td><td>30</td><td>10.884</td><td>7.282</td><td>100</td><td>NULL</td><td>NULL</td><td>0</td><td>14.430</td><td>1</td></tr><tr><td>5</td><td>5</td><td>4.834</td><td>6.548</td><td>100</td><td>5.042</td><td>4.675</td><td>100</td><td>0.023</td><td></td></tr><tr><td>5</td><td>10</td><td>11.806</td><td>25.156</td><td>100</td><td>178.152</td><td>77.800</td><td>100</td><td>0.021</td><td></td></tr><tr><td>5</td><td>30</td><td>3.016</td><td>5.194</td><td>100</td><td>767.85</td><td>77.449</td><td>8</td><td>0.011</td><td></td></tr><tr><td>10</td><td>5</td><td>171.800</td><td>203.744</td><td>36</td><td>1.533</td><td>0.523</td><td>100</td><td>0.022</td><td></td></tr><tr><td>10</td><td>10</td><td>156.700</td><td>180.427</td><td>40</td><td>53.115</td><td>41.828</td><td>100</td><td>0.020</td><td></td></tr><tr><td>10</td><td>30</td><td>182.212</td><td>143.398</td><td>40</td><td>0.245</td><td>0.036</td><td>100</td><td>0.010</td><td></td></tr><tr><td>50</td><td>5</td><td>NULL</td><td>NULL</td><td>0</td><td>0.200</td><td>0.012</td><td>100</td><td>0.024</td><td></td></tr><tr><td>50</td><td>10</td><td>NULL</td><td>NULL</td><td>0</td><td>0.355</td><td>0.015</td><td>100</td><td>0.021</td><td></td></tr><tr><td>50</td><td>30</td><td>NULL</td><td>NULL</td><td>0</td><td>1.952</td><td>0.027</td><td>100</td><td>0.011</td><td></td></tr></tbody></table>

also provide the new implementation of Mackey's algorithm, we used this version of the implementation as opposed to the original version.

## 6.1 Dataset preprocessing

As mentioned above, we used two datasets. Originally, Email-Eu-core-temporal dataset is collected for the period of 803 days and CollegeMsg dataset is collected for the period of 193 days. Both these datasets are available as time-stamped edge lists with time granularity of one second. As a pre-processing step, we changed the time granularity of both the datasets to one day, thus having several edges at every time instant and every graph snapshot. Furthermore, duplicate and self-loop edges were removed. Finally, we only considered the data for a smaller duration. For Email-Eu-core-temporal dataset, we considered the data for 50 days having 738 total nodes and 20331 total edges, and for CollegeMsg dataset we considered the data for 100 days having 1765 total nodes and 29407 total edges. The reason behind this choice is explained in the following section.

## 6.2 Results with random pattern graphs

We generated random pattern graphs having different number of nodes and number of snapshots. For each set of parameters, 25 graphs were
<table><caption>Table 2: Results obtained using CollegeMsg dataset. Average runtime (in secs), standard deviation (in secs) and the number of graph instances solved for each pattern graph parameter are presented for three algorithms. Parameters in order to zero number of matchings found between graph pairs</caption><thead><tr><th colspan="2">Pattern Graph</th><th colspan="3">Mackey's algorithm</th><th colspan="3">TemporalRI</th><th colspan="2">Our algorithm</th></tr><tr><th>Nodes</th><th>Snapshots</th><th>Time</th><th>Std. Dev.</th><th>%</th><th>Time</th><th>Std. Dev.</th><th>%</th><th>Time</th><th>Std. Dev.</th></tr></thead><tbody><tr><td>2</td><td>5</td><td>0.255</td><td>0.001</td><td>100</td><td>0.210</td><td>0.011</td><td>100</td><td>111.391</td><td>1</td></tr><tr><td>2</td><td>10</td><td>3.795</td><td>0.014</td><td>100</td><td>1.969</td><td>0.110</td><td>100</td><td>170.280</td><td>1</td></tr><tr><td>2</td><td>30</td><td>11.153</td><td>0.018</td><td>100</td><td>1.771</td><td>0.022</td><td>100</td><td>128.407</td><td>1</td></tr><tr><td>2</td><td>100</td><td>11.127</td><td>0.012</td><td>100</td><td>0.079</td><td>0.009</td><td>100</td><td>0.001</td><td>1</td></tr><tr><td>3</td><td>5</td><td>0.288</td><td>0.060</td><td>100</td><td>0.601</td><td>0.180</td><td>100</td><td>106.194</td><td>1</td></tr><tr><td>3</td><td>10</td><td>0.290</td><td>0.067</td><td>100</td><td>1.791</td><td>1.163</td><td>100</td><td>93.871</td><td>1</td></tr><tr><td>3</td><td>30</td><td>0.291</td><td>0.080</td><td>100</td><td>1.480</td><td>0.460</td><td>100</td><td>61.631</td><td>1</td></tr><tr><td>3</td><td>100</td><td>0.321</td><td>0.089</td><td>100</td><td>0.151</td><td>0.010</td><td>100</td><td>0.001</td><td>1</td></tr><tr><td>5</td><td>5</td><td>23.893</td><td>41.811</td><td>100</td><td>0.525</td><td>0.113</td><td>100</td><td>0.109</td><td>1</td></tr><tr><td>5</td><td>10</td><td>26.239</td><td>56.002</td><td>100</td><td>1.465</td><td>0.336</td><td>100</td><td>0.106</td><td>1</td></tr><tr><td>5</td><td>30</td><td>9.606</td><td>16.745</td><td>100</td><td>0.154</td><td>0.011</td><td>100</td><td>0.085</td><td>1</td></tr><tr><td>5</td><td>100</td><td>31.611</td><td>65.074</td><td>100</td><td>0.185</td><td>0.013</td><td>100</td><td>0.001</td><td>1</td></tr><tr><td>10</td><td>5</td><td>166.803</td><td>197.719</td><td>20</td><td>0.389</td><td>0.103</td><td>100</td><td>0.110</td><td>1</td></tr><tr><td>10</td><td>10</td><td>235.464</td><td>135.553</td><td>28</td><td>0.966</td><td>0.229</td><td>100</td><td>0.105</td><td>1</td></tr><tr><td>10</td><td>30</td><td>316.184</td><td>249.576</td><td>24</td><td>0.163</td><td>0.012</td><td>100</td><td>0.083</td><td>1</td></tr><tr><td>10</td><td>100</td><td>332.44</td><td>72.745</td><td>12</td><td>0.271</td><td>0.035</td><td>100</td><td>0.001</td><td>1</td></tr><tr><td>50</td><td>5</td><td>NULL</td><td>NULL</td><td>0</td><td>0.237</td><td>0.012</td><td>100</td><td>0.113</td><td>1</td></tr><tr><td>50</td><td>10</td><td>NULL</td><td>NULL</td><td>0</td><td>0.389</td><td>0.018</td><td>100</td><td>0.107</td><td>1</td></tr><tr><td>50</td><td>30</td><td>NULL</td><td>NULL</td><td>0</td><td>1.976</td><td>0.027</td><td>100</td><td>0.084</td><td>1</td></tr><tr><td>50</td><td>100</td><td>NULL</td><td>NULL</td><td>0</td><td>23.161</td><td>0.927</td><td>100</td><td>0.002</td><td>1</td></tr></tbody></table>
generated (875 graphs in total) and we calculated average runtime (in seconds) and standard deviation using the two datasets as target graphs and random pattern graphs. The results of the experiments obtained with Email-Eu-core-temporal dataset are presented in Table 1 and for CollegeMsg dataset in Table 2. In both tables, we note the performance of all three algorithms as well as the percentage of graph instances solved (out of 25) within a pre-defined timeout of 900 seconds (15 minutes). If none of the instances were solved before timeout, the average runtime and standard deviation could not be calculated and NULL values were noted. For all the experiments, the number of snapshots of pattern graph were always less than or equal to the number of snapshots of the target graph (according to the requirements mentioned in Section 3).

Since we obtained multiple NULL values for all three algorithms (see Table 1 and 2) using the two considered “smaller” datasets, we do not report the results for any of the algorithms with larger datasets. As a test, we applied TemporalRI using Email-Eu-core-temporal dataset having the duration of 500 days (978 total nodes, 207025 total edges) and pattern graphs having 2 nodes, but we got NULL values for all 25 graph instances checked.

The results of the experiments can be summarized as follows:

* In general, for smaller pattern graphs, Mackey's algorithm and TemporalRI have similar performance and both are better than our algorithm.

* As the size and the number of snapshots of the pattern graph grow, the performance of Mackey's algorithm degrades since the algorithm suffers from memory issues (also noted by the authors of TemporalRI [22]). For the largest pattern graph with varying number of snapshots, Mackey's algorithm was never able to finish before timeout for both datasets.

* The performance of TemporalRI for large (and long) target graph is better than that of our algorithm. However, for small (and short) target graph, our algorithm performs better than TemporalRI. We believe this is due to the fact the our graph model is based on (multiple) snapshots whereas for TemporalRI, there is single pattern/target graph with timestamped edges. With more number of snapshots of the target graph, the execution time of our algorithm increases.

* In both Tables 1 and 2, for the pattern graph parameters shown in orange, all three algorithms returned zero mappings, i.e., no dynamic subgraph isomorphism was found between a pattern and target graph pair. In such cases, in general, the performance of TemporalRI and our algorithm is similar, i.e., both algorithms stop early when there does not exist any solution. Mackey's algorithm, on the other hand, does not properly use the heuristics to detect such cases.

* Looking at the number of graph instances solved before timeout by all three algorithms (the percentage column in Tables 1 and 2), Mackey's algorithm solves the least. TemporalRI and our algorithm are similar in this regard as they solve equivalent number of graph instances before timeout.
* In general, out of the three algorithms tested, for larger target and pattern graphs, TemporalRI performs the best and Mackey's algorithm performs the least best. Our algorithm is in the second place in terms of execution time. For smaller pattern graphs, both Mackey's algorithm and TemporalRI are better than ours.

Hence, looking at the results obtained, it can be said that for solving the problem of dynamic subgraph isomorphism, the choice of model of dynamic graphs plays a critical role. It is better to use an aggregated model of dynamic graphs with time-stamped edges for this problem, as is the case in Mackey's algorithm (ignoring the memory related issues) and in TemporalRI. However, in some applications, it is not possible to model the dynamic graph in such a way and snapshot-based model is indispensable. In such cases, for solving the problem of SI, the existing algorithms can not be applied. Our algorithm, on the other hand, inherently takes into account the snapshot-based modeling approach of dynamic graphs and can easily be applied in such cases.

<table><caption>Table 3: Results obtained by increasing the size of the sliding window for Email-Eu-core-temporal dataset. The initial size of the sliding window is *w*. Average runtime (in secs) is reported for each graph parameter. Parameters in orange correspond to zero number of matchings found between graph pairs</caption><thead><tr><th colspan="2">Pattern Graph</th><th rowspan="2">w</th><th rowspan="2">w + 1</th><th rowspan="2">w + 2</th><th rowspan="2">w + 3</th><th rowspan="2">w + 4</th></tr><tr><th>Nodes</th><th>Snapshots</th></tr></thead><tbody><tr><td>2</td><td>5</td><td>NULL</td><td>NULL</td><td>NULL</td><td>NULL</td><td>NULL</td></tr><tr><td>3</td><td>5</td><td><strong>75.806</strong></td><td><strong>78.987</strong></td><td><strong>83.048</strong></td><td><strong>84.744</strong></td><td><strong>86.143</strong></td></tr><tr><td>5</td><td>5</td><td>0.023</td><td>0.023</td><td>0.023</td><td>0.024</td><td>0.024</td></tr><tr><td>10</td><td>5</td><td>0.022</td><td>0.022</td><td>0.022</td><td>0.022</td><td>0.023</td></tr><tr><td>50</td><td>5</td><td>0.024</td><td>0.024</td><td>0.024</td><td>0.025</td><td>0.025</td></tr></tbody></table>

## 6.3 Effect of the size of the sliding window

In this section, we will discuss the effect of the size of the sliding window used in the proposed algorithm in order to find suitable matchings. The idea of using the sliding window is to restrict the number of snapshots of the target graph in which the matching has to be searched, for a given pattern graph snapshot. As mentioned in Section 5.2, the size of this window depends on the number of snapshots of the target and the pattern graph.

The experiments discussed in the previous section were performed using the sliding window whose size (say *w*) was calculated based on the number of snapshots of the input graphs. The experiments discussed in this section were performed with different sizes of the sliding window. The initial size (*w*) was incremented step-by-step for each experiment and the effect on the average runtime of the algorithm was noted. For these experiments, we used 10 graphs for each pattern graph parameter with both Email-Eu-core-temporal and CollegeMsg datasets and the timeout
<table><caption>Table 4: Results obtained by increasing the size of the sliding window for CollegeMsg dataset. The initial size of the sliding window is *w*. Average runtime (in secs) is reported for each graph parameter. Parameters in orange correspond to zero number of matchings found between graph pairs</caption><thead><tr><th colspan="2">Pattern Graph</th><th rowspan="2">w</th><th rowspan="2">w + 1</th><th rowspan="2">w + 2</th><th rowspan="2">w + 3</th><th rowspan="2">w + 4</th></tr><tr><th>Nodes</th><th>Snapshots</th></tr></thead><tbody><tr><td>2</td><td>5</td><td>97.915</td><td>99.194</td><td>99.963</td><td>100.502</td><td>100.472</td></tr><tr><td>3</td><td>5</td><td>162.201</td><td>164.631</td><td>166.660</td><td>169.547</td><td>169.006</td></tr><tr><td>5</td><td>5</td><td>0.109</td><td>0.106</td><td>0.107</td><td>0.109</td><td>0.109</td></tr><tr><td>10</td><td>5</td><td>0.107</td><td>0.105</td><td>0.106</td><td>0.106</td><td>0.108</td></tr><tr><td>50</td><td>5</td><td>0.111</td><td>0.109</td><td>0.110</td><td>0.111</td><td>0.112</td></tr></tbody></table>

of 900 seconds (15 minutes). The results are given in Table 3 and Table 4 respectively.

As can be seen from both tables, increasing the size of the sliding window increases the average runtime of the algorithm since more target graph snapshots are explored for finding one or more matchings for a given pattern graph snapshot. The graph parameters for which no solution exists (indicated in orange in Tables 3 and 4), increasing the size of the sliding window has no effect on the runtime of the algorithm since the algorithm does not continue exploring the snapshots in this case. And graphs for which the algorithm could not terminate before timeout (NULL values in Table 3) with initial size of the sliding window, it does not terminate when the size of the sliding window is increased.

Finally, it is noteworthy that we do not recommend increasing the size of the sliding window while using the proposed algorithm. During our experiments, we noted that the number of matchings found, for a given pattern and target graph pair, with different sizes of the sliding window remained the same. Increasing the sliding window size only increases the algorithm runtime without affecting the “goodness” of the final solution.

# 7 Conclusion

In this paper, we focused on the problem of subgraph isomorphism in case of dynamic graphs. Although this problem has been well studied for static graphs, it is still in its infancy for dynamic graphs. One of the possible reasons behind this could be the plethora of dynamic graph models present in the literature since the choice of the model affects the problem definition and, in turn, the performance of the designed algorithms.

We proposed an algorithm for solving the induced version of this problem. The proposed algorithm inherently considers the snapshot-based representation of dynamic graphs and respects the temporal order of these snapshots. This approach is novel since the existing state-of-the-art algorithms model the dynamic graphs as an aggregated graph with times-tamped edges. The difference in the modeling of the dynamic graphs affects the algorithm design. For the existing algorithms, the chronological
order of the edges presents an important constraint, whereas in our case,
the chronological order of the entire graph snapshot takes precedence.

The core of our algorithm is another algorithm (VF3) designed for the
case of static graphs. We extend it to be applied to dynamic graphs and
discuss the pruning strategy for the reduction of the state-space using the
knowledge of previously matched nodes. We present the theoretical time
complexity analysis of VF3 which helps in outlining the time complexity
analysis of our algorithm. Furthermore, we tested the performance of our
algorithm and compared it with two existing state-of-the-art algorithms
using the real-world datasets. From the results, it was concluded that
our algorithm is the second best overall in terms of runtime, especially
for larger target and pattern graphs. One of the existing state-of-the-art
could not solve any graph instances for larger pattern graphs. Further-
more, it was concluded that the snapshot-based model of dynamic graphs
is probably not the best choice for solving the problem of subgraph iso-
morphism. However, since in some applications, it is not possible to model
a dynamic graph using an aggregated model with timestamped edges, the
existing algorithms are not applicable. Since the performance of our al-
gorithm is at par with that of the existing algorithms, it can be applied
in cases where the snapshot-based model of dynamic graphs is required.
In fact, we have applied the proposed algorithm for detecting dynamic
patterns in two diverse domains - urban road traffic and invasive team
sports in our previous works.

Acknowledgements

This work has been funded partially with the support from European
Union with the European Regional Development Fund (ERDF) and with
the support of the pLaTINUM ANR project (ANR-15-CE23-0010-01).

Statements and Declarations

Competing interests

The authors declare that they have no competing interests.

Availability of data and materials

The datasets used in this paper as well as the source code can be found
here: https://github.com/KamalDSOberoi/DynamicSubgraphIsomorphism

References

[1] T. Alakörkkö and J. Saramäki. Circadian rhythms in temporal-network connectivity. *Chaos: An Interdisciplinary Journal of Non-linear Science*, 30(9):093115, 2020.
[2] I. Almasri, X. Gao, and N. Fedoroff. Quick mining of isomorphic exact large patterns from large graphs. In *2014 IEEE International Conference on Data Mining Workshop*, pages 517–524, Dec 2014.

[3] Michele Berlingerio, Francesco Bonchi, Björn Bringmann, and Aris- tides Gionis. Mining graph evolution rules. In Wray Buntine, Marko Grobelnik, Dunja Mladenić, and John Shawe-Taylor, editors, *Machine Learning and Knowledge Discovery in Databases*, pages 115–130. Springer Berlin Heidelberg, 2009.

[4] Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, and Alfredo Ferro. A subgraph isomorphism algorithm and its application to biochemical data. *BMC Bioinformatics*, 14(7):S13, Apr 2013.

[5] Eren Cakmak, Udo Schlegel, Dominik Jäckle, Daniel Keim, and To- bias Schreck. Multiscale snapshots: Visual analysis of temporal sum- maries in dynamic graphs. *IEEE Transactions on Visualization and Computer Graphics*, 27(2):517–527, 2021.

[6] V. Carletti, P. Foggia, A. Saggese, and M. Vento. Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 40(4):804–818, April 2018.

[7] Vincenzo Carletti, Pasquale Foggia, Antonio Greco, Alessia Saggese, and Mario Vento. Comparing performance of graph matching algo- rithms on huge graphs. *Pattern Recognition Letters*, 2018.

[8] Sutanay Choudhury, Lawrence Holder, George Chin, Khushbu Agar- wal, and John Feo. A selectivity based approach to continuous pat- tern detection in streaming graphs. In *18th International Conference on Extending Database Technology*, pages 157–168, 2015.

[9] Donatello Conte, Pasquale Foggia, Mario Vento, and Carlo Sansone. Thirty Years Of Graph Matching In Pattern Recognition. *International Journal of Pattern Recognition and Artificial Intelligence*, 18(3):265–298, 2004.

[10] Stephen A. Cook. The complexity of theorem-proving procedures. In *Third Annual ACM Symposium on Theory of Computing*, STOC '71, pages 151–158, New York, USA, 1971. ACM.

[11] L. P. Cordella, P. Foggia, C. Sansone, and M. Vento. A (sub)graph isomorphism algorithm for matching large graphs. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 26(10):1367–1372, Oct 2004.

[12] Joseph Crawford and Tijana Milenković. Cluenet: Clustering a tem- poral network based on topological similarity rather than denseness. *PLOS ONE*, 13(5):1–25, 2018.

[13] Fabien Diot, Elisa Fromont, Baptiste Jeudy, Emmanuel Marilly, and Olivier Martinot. Graph mining for object tracking in videos. In Peter A. Flach, Tijl De Bie, and Nello Cristianini, editors, *Machine Learning and Knowledge Discovery in Databases*, pages 394–409, Berlin Heidelberg, 2012. Springer.
[14] Aswathy Divakaran and Anuraj Mohan. Temporal link prediction: A survey. *New Generation Computing*, 38(1):213–258, 2020.

[15] Wenfei Fan. Graph pattern matching revised for social network analysis. In *Proceedings of the 15th International Conference on Database Theory*, page 8–21, 2012.

[16] Wenfei Fan, Jianzhong Li, Jizhou Luo, Zijing Tan, Xin Wang, and Yinghui Wu. Incremental graph pattern matching. In *International Conference on Management of Data*, pages 925–936, New York, NY, USA, 2011. ACM.

[17] R. Giugno and D. Shasha. Graphgrep: A fast and universal method for querying graphs. In *Object recognition supported by user interaction for service robots*, volume 2, pages 112–115 vol.2, Aug 2002.

[18] Huahai He and Ambuj K. Singh. Graphs-at-a-time: Query language and access methods for graph databases. In *International Conference on Management of Data*, pages 405–418, New York, NY, USA, 2008. ACM.

[19] Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. Temporal motifs in time-dependent networks. *Journal of Statistical Mechanics: Theory and Experiment*, 2011(11):P11005, nov 2011.

[20] Lauri Kovanen, Kimmo Kaski, János Kertész, and Jari Saramäki. Temporal motifs reveal homophily, gender-specific patterns, and group talk in call sequences. *Proceedings of the National Academy of Sciences*, 110(45):18070–18075, 2013.

[21] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, 2014. Accessed Jan. 2022.

[22] Giorgio Locicero, Giovanni Micale, Alfredo Pulvirenti, and Alfredo Ferro. TemporalRI: A subgraph isomorphism algorithm for temporal networks. In Rosa M. Benito, Chantal Cherifi, Hocine Cherifi, Esteban Moro, Luis Mateus Rocha, and Marta Sales-Pardo, editors, *Complex Networks & Their Applications IX*, pages 675–687, Cham, 2021. Springer International Publishing.

[23] P. Mackey, K. Porterfield, E. Fitzhenry, S. Choudhury, and G. Chin. A chronological edge-driven approach to temporal subgraph isomorphism. In *2018 IEEE International Conference on Big Data*, pages 3972–3979, Dec 2018.

[24] Ciaran Mccreesh, Patrick Prosser, Christine Solnon, and James Trimble. When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases. *Journal of Artificial Intelligence Research*, 61:723 – 759, 2018.

[25] J.J. McGregor. Relational consistency algorithms and their application in finding subgraph and graph isomorphisms. *Information Sciences*, 19(3):229 – 250, 1979.

[26] Giovanni Micale, Giorgio Locicero, Alfredo Pulvirenti, and Alfredo Ferro. TemporalRI: Subgraph isomorphism in temporal networks
with multiple contacts. *Applied Network Science*, 6(1):55:1–55:22, 2021.

[27] Kingshuk Mukherjee, Md Mahmudul Hasan, Christina Boucher, and Tamer Kahveci. Counting motifs in dynamic networks. *BMC Systems Biology*, 12(1):1–12, 2018.

[28] Ashwin Paranjape, Austin R. Benson, and Jure Leskovec. Motifs in temporal networks. In *10th International Conference on Web Search and Data Mining*, pages 601–610, New York, NY, USA, 2017. ACM.

[29] Ursula Redmond and Pádraig Cunningham. Subgraph isomorphism in temporal networks. *arXiv preprint arXiv:1605.02174*, 2016.

[30] Giulio Rossetti and Rémy Cazabet. Community discovery in dynamic networks: A survey. *ACM Computing Surveys*, 51(2):1–37, feb 2018.

[31] Benjamin Schiller, Sven Jager, Kay Hamacher, and Thorsten Strufe. Stream - a stream-based algorithm for counting motifs in dynamic graphs. In Adrian-Horia Dediu, Francisco Hernández-Quiroz, Carlos Martín-Vide, and David A. Rosenblueth, editors, *Algorithms for Computational Biology*, pages 53–67, Cham, 2015. Springer International Publishing.

[32] Douglas C. Schmidt and Larry E. Druffel. A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices. *Journal of ACM*, 23(3):433–445, July 1976.

[33] Konstantinos Semertzidis and Evaggelia Pitoura. Top-k durable graph pattern queries on temporal graphs. *IEEE Transactions on Knowledge and Data Engineering*, 31(1):181–194, 2019.

[34] Christine Solnon. Alldifferent-based filtering for subgraph isomorphism. *Artificial Intelligence*, 174(12):850–864, 2010.

[35] X. Sun, Y. Tan, Q. Wu, and J. Wang. Hasse diagram based algorithm for continuous temporal subgraph query in graph stream. In *6th International Conference on Computer Science and Network Technology*, pages 241–246, Oct 2017.

[36] J. Tang, S. Scellato, M. Musolesi, C. Mascolo, and V. Latora. Small-world behavior in time-varying graphs. *Phys. Rev. E*, 81:055101, May 2010.

[37] J. R. Ullmann. An algorithm for subgraph isomorphism. *Journal of ACM*, 23(1):31–42, January 1976.

[38] Julian R. Ullmann. Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. *Journal of Experimental Algorithmics*, 15:1.6:1.1–1.6:1.64, 2011.

[39] Mario Vento. A long trip in the charming world of graphs for pattern recognition. *Pattern Recognition*, 48(2):291–301, 2015.