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
772516776 2613146847 2423652555 2097746044
Subgraph isomorphism is a common problem in several application fields where graphs are the best suited data representation, but it is known to be an NP-Complete problem. However, several algorithms exist that are fast enough on commonly encountered graphs so as to be practically usable; among them, for more than a decade VF2 has been the state of the art algorithm used to solve this problem and it is still the reference algorithm for many applications. Nevertheless, VF2 has been designed and implemented ten years ago when the structural features of the commonly used graphs were considerably different. Hence a renovation is required to make the algorithm able to compete in the challenges arisen in the last years, such as the use of graph matching on the very large graphs coming from bioinformatics applications. In this paper we propose a significant set of enhancements to the original VF2 algorithm that enable it to compete with more recently proposed graph matching techniques. Finally, we evaluate the effectiveness of these enhancement by comparing the matching performance both with the original VF2 and with several recent algorithms, using both the widely known MIVIA graph database and another public graph dataset containing real-world graphs from bioinformatics applications. Several graph-based applications require to detect and locate occurrences of a pattern graph within a larger target graph. Subgraph isomorphism is a widely adopted formalization of this problem. While subgraph isomorphism is NP-Complete in the general case, there are algorithms that can solve it in a reasonable time on the average graphs that are encountered in specific real-world applications. In 2015 we introduced one such algorithm, VF2Plus, that was specifically designed for the large graphs encountered in bioinformatics applications. VF2Plus was an evolution of VF2, which had been considered for many years one of the fastest available algorithms. In turn, VF2Plus proved to be significantly faster than its predecessor, and among the fastest algorithms on bioinformatics graphs. In this paper we propose a further evolution, named VF3, that adds new improvements specifically targeted at enhancing the performance on graphs that are at the same time large and dense, that are currently the most problematic case for the state-of-the-art algorithms. The effectiveness of VF3 has been experimentally validated using several publicly available datasets, showing a significant speedup with respect to its predecessor and to the other most advanced state-of-the-art algorithms. In this paper, we study the problem of subgraph matching that extracts all subgraph isomorphic embeddings of a query graph q in a large data graph G. The existing algorithms for subgraph matching follow Ullmann's backtracking approach; that is, iteratively map query vertices to data vertices by following a matching order of query vertices. It has been shown that the matching order of query vertices is a very important aspect to the efficiency of a subgraph matching algorithm. Recently, many advanced techniques, such as enforcing connectivity and merging similar vertices in query or data graphs, have been proposed to provide an effective matching order with the aim to reduce unpromising intermediate results especially the ones caused by redundant Cartesian products. In this paper, for the first time we address the issue of unpromising results by Cartesian products from "dissimilar" vertices. We propose a new framework by postponing the Cartesian products based on the structure of a query to minimize the redundant Cartesian products. Our second contribution is proposing a new path-based auxiliary data structure, with the size O(|E(G)| x |V(q)|), to generate a matching order and conduct subgraph matching, which significantly reduces the exponential size O(|V(G)||V(q)|-1) of the existing path-based auxiliary data structure, where V (G) and E (G) are the vertex and edge sets of a data graph G, respectively, and V (q) is the vertex set of a query @math . Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms by up to @math orders of magnitude. In this paper, we propose a general framework for graph matching which is suitable for different problems of pattern recognition. The pattern representation we assume is at the same time highly structured, like for classic syntactic and structural approaches, and of subsymbolic nature with real-valued features, like for connectionist and statistic approaches. We show that random walk based models, inspired by Google's PageRank, give rise to a spectral theory that nicely enhances the graph topological features at node level. As a straightforward consequence, we derive a polynomial algorithm for the classic graph isomorphism problem, under the restriction of dealing with Markovian spectrally distinguishable graphs (MSD), a class of graphs that does not seem to be easily reducible to others proposed in the literature. The experimental results that we found on different test-beds of the TC-15 graph database show that the defined MSD class "almost always" covers the database, and that the proposed algorithm is significantly more efficient than top scoring VF algorithm on the same data. Most interestingly, the proposed approach is very well-suited for dealing with partial and approximate graph matching problems, derived for instance from image retrieval tasks. We consider the objects of the COIL-100 visual collection and provide a graph-based representation, whose node's labels contain appropriate visual features. We show that the adoption of classic bipartite graph matching algorithms offers a straightforward generalization of the algorithm given for graph isomorphism and, finally, we report very promising experimental results on the COIL-100 visual collection.