ARG Database

The ARG Database is a huge collection of labeled and unlabeled graphs realized by the MIVIA Group. The aim of this collection is to provide the graph research community with a standard test ground for the benchmarking of graph matching algorithms.The database is organized in two section: labeled and unlabeled graphs.
Both labeled and unlabeled graphs have been randomly generated according to six different generation models, each involving different possible parameter settings. As a result, 168 diverse kinds of graphs are contained in the database. Each type of unlabeled graph is represented by thousands of pairs of graphs for which an isomorphism or a graph-subgraph isomorphism relation holds, for a total of 143,600 graphs. Furthermore, each type of labeled graph is represented by thousands of pairs of graphs holding a not trivial common subgraph, for a total of 166,000 graphs.
Some useful information about the dataset, including some usage examples, can be downloaded here.

The whole dataset (for both the isomorphism and subgraph isomorphism parts and for the minimum common subgraph part) can be downloaded by requesting it at this link, while at this link you can find the graph generator software.

More information about the use of the ARG Database and about the graph generator software can be found here.

If you use this dataset please cite:

• 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 Database of Graphs for Isomorphism and Sub-Graph Isomorphism Benchmarking

  @inproceedings{foggia2001-2,
  title = {A Database of Graphs for Isomorphism and Sub-Graph Isomorphism Benchmarking},
  author = {P. Foggia and C. Sansone and M. Vento},
  year = {2001},
  date = {2001-01-01},
  booktitle = {-},
  pages = {176–187},
  keywords = {Graph based classification and learning}
  }

Other reference papers are:

• 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}
  }

• 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 recognitionA 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 ApplicationsMany 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},
  }
  

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