The VFLib graph matching library is a graph matching library which provides several algorithms for graph isomorphism, graph-subgraph isomorphism and graph monomorphism. The library is an efficient implementation of the VF2 graph matching algorithm, currently among the fastest ones, able to process very huge graphs due to its linear memory complexity. The library is written in C++, and can be easily adapted to use different formats for the graphs, and different types of attributes.
The library documentation, including some usage examples, can be downloaded here.
Attention: VF3 in now available! Please find more information at the following link.
The software and the library documentation can be downloaded by requesting it at the following link.
If you use this library please cite:
- A (sub)graph isomorphism algorithm for matching large graphs
@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}
}
Other reference papers are:
- 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}
}
- An Algorithm for Subgraph Isomorphism
@article{Ullmann1976,
author = {Ullmann, J. R.},
title = {An Algorithm for Subgraph Isomorphism},
journal = {J. ACM},
year = {1976},
}
- A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices
@article{Schmidt1976,
author = {Schmidt, Douglas C. and Druffel, Larry E.},
title = {A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices},
journal = {J. ACM},
year = {1976},
}
Useful papers are:
- 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 first 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 presentation of some of the algorithms implemented in our VFLib can be found here. (Available soon!!)
- Brian Kelley, at MIT Whitehead Institute for Biomedical Research, has developed a Python interfaceto VFLib, which can be found using this link. Brian has used this binding in his FROWNS chemioinformatics system.Python is a very popular scripting language, with object orientation, a clean syntax, and a very large library, making it one of the most powerful tools for complex application prototyping. See www.python.org for more information on this language.
- VF2 has been included in Boost C++ library, widely used by the scientific community since providing support for tasks and structures such as linear algebra, image processing, regular expressions etc.
- VF2 has been included in NetworkX 2.0 Python library
Some of the applicative domains where the VF method has been used are the following:
- Virtual Network Mapping
@inproceedings{Lischka2009,
author = {Lischka, Jens and Karl, Holger},
title = {A virtual network mapping algorithm based on subgraph isomorphism detection},
booktitle = {Proceedings of the 1st ACM workshop on Virtualized infrastructure systems and architectures},
series = {VISA ’09},
year = {2009},
acmid = {1592662},
publisher = {ACM},
}
- Design of systems-on-chip
@INPROCEEDINGS{1395585,
author={Ogras, U.Y. and Marculescu, R.},
booktitle={Design, Automation and Test in Europe, 2005. Proceedings},
title={Energy- and performance-driven NoC communication architecture synthesis using a decomposition approach},
year={2005},
pages={352-357 Vol. 1},
doi={10.1109/DATE.2005.137},
ISSN={1530-1591},
}
- RDF Index
@inproceedings{Udrea:2007:GGB:1619797.1619880,
author = {Udrea, Octavian and Pugliese, Andrea and Subrahmanian, V. S.},
title = {GRIN: a graph based RDF index},
booktitle = {Proceedings of the 22nd national conference on Artificial intelligence – Volume 2},
series = {AAAI’07},
year = {2007},
publisher = {AAAI Press},
}
- Biological Networks
@article{Ferro01042007,
author = {Ferro, A. and Giugno, R. and Pigola, G. and Pulvirenti, A. and Skripin, D. and Bader, G. D. and Shasha, D.},
title = {NetMatch: a Cytoscape plugin for searching biological networks},
year = {2007},
doi = {10.1093/bioinformatics/btm032},
journal = {Bioinformatics}
}
- Molecules detector
@article{journals/jcheminf/RahmanBHST09,
author = {Rahman, Syed Asad and Bashton, Matthew and Holliday, Gemma L. and Schrader, Rainer and Thornton, Janet M.},
journal = {J. Cheminformatics},
title = {Small Molecule Subgraph Detector (SMSD) toolkit.},
volume = {1},
year = {2009},
}
- Automated Discovery of Custom Instructions
@INPROCEEDINGS{4430002,
author={Bonzini, P. and Pozzi, L.},
booktitle={Application -specific Systems, Architectures and Processors, 2007. ASAP. IEEE International Conf. on},
title={A Retargetable Framework for Automated Discovery of Custom Instructions},
year={2007},
doi={10.1109/ASAP.2007.4430002},
ISSN={2160-0511},
}
- Disk-based graph indexing techniques
@article{Han2010,
author = {Han, Wook-Shin and Lee, Jinsoo and Pham, Minh-Duc and Yu, Jeffrey Xu},
title = {iGraph: a framework for comparisons of disk-based graph indexing techniques},
journal = {Proc. VLDB Endow.},
year = {2010},
publisher = {VLDB Endowment},
}
If you use this method in your application, please contact us in order to update this list!
If you have any problems, do not hesitate to contact us here.
