January 19, 2017

VF3 Library

VF2: The heritage

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.


From VF2 to VF3

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.


VF3 in action

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“.


References

If you are using this library please cite (for now):

  • A (sub)graph isomorphism algorithm for matching large graphs (The father of VF3, the so called VF2).

Other useful papers are:

  • A large database of graphs and its use for benchmarking graph isomorphism algorithms.
  • A performance comparison of five algorithms for graph isomorphism.
  • Thirty years of graph matching in pattern recognition.
  • Graph-Based Methods in Computer Vision: Developments and Applications.
  • A long trip in the charming world of graphs for Pattern Recognition.

Help

If you have any problems, do not hesitate to contact us here.