Many real world networks are considered temporal networks, in which the chronological ordering of the edges has importance to the meaning of the data. Performing temporal subgraph matching on such graphs requires the edges in the subgraphs to match the order of the temporal graph motif we are searching for. Previous methods for solving this rely on the use of static subgraph matching to find potential matches first, before filtering them based on edge order to find the true temporal matches. We present a new algorithm for temporal subgraph isomorphism that performs the subgraph matching directly on the chronologically sorted edges. By restricting our search to only the subgraphs with chronologically correct edges, we can improve the performance of the algorithm significantly. We present experimental timing results to show significant performance improvements on publicly available datasets for a number of different temporal query graph motifs with four or more nodes. We also demonstrate a practical example of how temporal subgraph isomorphism can produce more meaningful results than traditional static subgraph searches.
Subgraph matching algorithms have existed since at least the time of the publication of Ullmann's algorithm in 1976 @cite_14 . Since then, many modifications have been made to this approach to improve its performance. One of the most commonly used is known as the VF2 algorithm @cite_6 , itself an extension of the VF algorithm @cite_5 (named for two of its authors, Vento and Foggia). While this approach can be used to find patterns in static networks, by default it ignores the chronological ordering of edges, and only expects them to match a particular topological configuration. While it may be possible to add edge restrictions to enforce some temporal requirements in how the subgraphs are matched, it is not a natural part of the algorithm.
@cite_5 @cite_14 @cite_6
1910918478 2126359798
The paper discusses the performance of a graph matching algorithm tailored for dealing with large graphs in computer vision without using information about the topology of the graphs to be matched. The algorithm, presented in more detail in other papers (and publicly available on the WWW as VF), is now discussed with reference to its computational complexity and memory requirements. The performance analysis is carried out by theoretically characterizing the matching time and the required memory in the best and worst cases. The theoretical analysis is completed by tests on a database of graphs randomly generated. The algorithm is compared with the one proposed by Ullmann (1976): experimental results confirmed the theoretical expectations, highlighting the overall efficiency of the algorithm. Some results obtained by researchers who recently used the algorithm in application domains requiring a massive use of graph matching techniques are finally reported. Subgraph isomorphism can be determined by means of a brute-force tree-search enumeration procedure. In this paper a new algorithm is introduced that attains efficiency by inferentially eliminating successor nodes in the tree search. To assess the time actually taken by the new algorithm, subgraph isomorphism, clique detection, graph isomorphism, and directed graph isomorphism experiments have been carried out with random and with various nonrandom graphs. A parallel asynchronous logic-in-memory implementation of a vital part of the algorithm is also described, although this hardware has not actually been built. The hardware implementation would allow very rapid determination of isomorphism.