VF2 has been, for more than a decade, one of the most used exact graph matching algorithm. The reason can be found in its high efficiency: indeed, it has been for several years the fastest algorithm available in the literature; furthermore, its linear memory complexity has allowed to profitably use it for dealing with large graphs.
The authors made available the source code of VF2 (more details at the following link), so as to encourage its usage; VF2 has been used in a wide variety of application fields, ranging from bioinformatics and semantic web technologies to computer vision and SoC designing.
Its popularity is also confirmed by the well-known software libraries including it: NetworkX 2.0, the most used Python library for managing complex networks; Boost, one of the most famous collection of C++ libraries (some of them already included in the Standard C++11), widely used by the scientific community since providing support for tasks and structures such as linear algebra, image processing, regular expressions etc.
VF3 is a graph matching algorithm, specialized in solving graph isomorphism and graph-subgraph isomorphism. In particular, it is able to solve both testing and listing problems, being able to determine not only if the isomorphism exists (testing) but also where and how many times a pattern graph is present inside the target graph (listing).
VF3 has been designed from the experience of the authors of VF2: it preserves the general framework of VF2 (a State Space Representation with backtracking and a set of feasibility rules), but also introduces several optimizations aimed to exploit some characteristics often encountered on real world large graphs. VF3 has the ability to maintain a low memory requirement (linear with respect to the graphs size) as its predecessor, but being definitively faster than VF2, with an improvement in terms of processing time with respect to VF2 which varies from 10 to 1000 times.
VF3 is general enough to deal with any typology of graphs. Its efficiency with respect to state of the art algorithms is evident especially when dealing with very huge and dense graphs. In this case, in fact, it confirms to be the fastest one available nowadays in the literature.
VF3 has been tested on the MIVIA large dense graphs dataset, a new and very wide dataset composed by dense graphs whose size ranges from 300 to 10.000 nodes. The results achieved by VF3 have been compared with four state of the art algorithms (VF2, RI, L2G and LAD), confirming its effectiveness. Some graphics confirming VF3 efficiency are reported at the following link.
The source code (together with the executable) is available under the MIT license and can be requested at the following link. More details on the software are provided here. Thanks to the available code and documentation, you can easily integrate VF3 in your application domain for solving your specific problem.
A brief example of the algorithm in action can be found at the following link, while you can download a presentation at the following link. For more details you can refer to the following paper, submitted in 2016 to IEEE Transaction on PAMI: “Challenging memory and time complexity of subgraph isomorphism problem with VF3“.
If you are using this library please cite (for now):
-
Challenging the Time Complexity of Exact Subgraph Isomorphism for Huge and Dense Graphs with VF3
@ARTICLE{CarlettiPAMI,
author={V. Carletti and P. Foggia and A. Saggese and M. Vento},
journal={IEEE Transactions on Pattern Analysis and Machine Intelligence},
title={Challenging the Time Complexity of Exact Subgraph Isomorphism for Huge and Dense Graphs with VF3},
year={2018},
volume={40},
number={4},
pages={804-818},
doi={10.1109/TPAMI.2017.2696940},
ISSN={0162-8828},
month={April},
}
-
Introducing VF3: A New Algorithm for Subgraph Isomorphism
@InProceedings{10.1007/978-3-319-58961-9_12,
title=”Introducing VF3: A New Algorithm for Subgraph Isomorphism”,
author=”Carletti, Vincenzo and Foggia, Pasquale and Saggese, Alessia and Vento, Mario”,
booktitle=”Graph-Based Representations in Pattern Recognition”,
editor=”Foggia, Pasquale and Liu, Cheng-Lin and Vento, Mario”,
year=”2017″,
publisher=”Springer International Publishing”,
address=”Cham”,
pages=”128–139″}
Other useful papers are:
- A (sub)graph isomorphism algorithm for matching large graphs (The father of VF3, the so called VF2).
@ARTICLE{Cordella2004,
author={Cordella, L.P. and Foggia, P. and Sansone, C. and Vento, M.},
journal={Pattern Analysis and Machine Intelligence, IEEE Transactions on},
title={A (sub)graph isomorphism algorithm for matching large graphs},
year={2004},
volume={26},
number={10},
pages={1367-1372},
doi={10.1109/TPAMI.2004.75},
ISSN={0162-8828}
}
- A large database of graphs and its use for benchmarking graph isomorphism algorithms.
@article{DeSanto2003,
author = {De Santo, M. and Foggia, P. and Sansone, C. and Vento, M.},
title = {A large database of graphs and its use for benchmarking graph isomorphism algorithms},
journal = {Pattern Recogn. Lett.},
issue_date = {May 2003},
volume = {24},
number = {8},
month = may,
year = {2003},
issn = {0167-8655},
pages = {1067–1079},
numpages = {13},
url = {http://dx.doi.org/10.1016/S0167-8655(02)00253-2},
doi = {10.1016/S0167-8655(02)00253-2},
acmid = {763457},
publisher = {Elsevier Science Inc.},
address = {New York, NY, USA},
}
- A performance comparison of five algorithms for graph isomorphism.
@INPROCEEDINGS{Foggia2001,
author = {P. Foggia and C. Sansone and M. Vento},
title = {A performance comparison of five algorithms for graph isomorphism},
booktitle = {in Proceedings of the 3rd IAPR TC-15 Workshop on Graph-based Representations in Pattern Recognition},
year = {2001},
pages = {188–199}
}
- Thirty years of graph matching in pattern recognition.
A recent paper posed the question: “Graph Matching: What are we really talking about?”. Far from providing a definite answer to that question, in this paper we will try to characterize the role that graphs play within the Pattern Recognition field. To this aim two taxonomies are presented and discussed. The fi rst includes almost all the graph matching algorithms proposed from the late seventies, and describes the different classes of algorithms. The second taxonomy considers the types of common applications of graph-based techniques in the Pattern Recognition and Machine Vision field.
@article{doi:10.1142/S0218001404003228,
author = {CONTE, D. and FOGGIA, P. and SANSONE, C. and VENTO, M.},
title = {Thirty years of graph matching in pattern recognition},
journal = {International Journal of Pattern Recognition and Artificial Intelligence},
volume = {18},
number = {03},
pages = {265-298},
year = {2004},
doi = {10.1142/S0218001404003228},
}
- Graph-Based Methods in Computer Vision: Developments and Applications.
Many computer vision applications require a comparison between two objects, or between an object and a reference model. When the objects or the scenes are represented by graphs, this comparison can be performed using some form of graph matching. The aim of this chapter is to introduce the main graph matching techniques that have been used for computer vision, and to relate each application with the techniques that are most suited to it.
@inbook{vento,
title = {Graph-Based Methods in Computer Vision: Developments and Applications},
author = {Mario Vento and Pasquale Foggia},
url = {http://www.igi-global.com/viewtitlesample.aspx?id=69068&ptid=63867&t=graph%20matching%20techniques%20for%20computer%20vision},
issn = {9781466618916},
year = {2013},
date = {2013-01-01},
pages = {1–41},
publisher = {Idea Group, Information Science Reference},
address = {Hershey — USA},
chapter = {Graph Matching Techniques for Computer Vision},
keywords = {Graph based classification and learning},
}
- A long trip in the charming world of graphs for Pattern Recognition.
This paper is a historical overview of graph-based methodologies in Pattern Recognition in the last 40 years; history is interpreted with the aim of recognizing the rationale inspiring the papers published in these years, so as to roughly classify them. Despite the extent of scientific production in this field, it is possible to identify three historical periods, each having its own connotation common to most of the corresponding papers, which are called here as the pure, the impure and extreme periods.
@article{Vento2015,
title = “A long trip in the charming world of graphs for Pattern Recognition “,
journal = “Pattern Recognition “,
volume = “48”,
number = “2”,
pages = “291 – 301”,
year = “2015”,
note = “”,
issn = “0031-3203”,
doi = “http://dx.doi.org/10.1016/j.patcog.2014.01.002”,
url = “http://www.sciencedirect.com/science/article/pii/S0031320314000053”,
author = “Mario Vento”
}
If you have any problems, do not hesitate to contact us here.
