Querying Subgraph Sets with G-Tries

Pedro Ribeiro and Fernando Silva

2012

Abstract

In this paper we present an universal methodology for finding all the occurrences of a given set of subgraphs in one single larger graph. Past approaches would either enumerate all possible subgraphs of a certain size or query a single subgraph. We use g-tries, a data structure specialized in dealing with subgraph sets. G-Tries store the topological information on a tree that exposes common substructure. Using a specialized canonical form and symmetry breaking conditions, a single non-redundant search of the entire set of subgraphs is possible. We give results of applying g-tries querying to different social networks, showing that we can efficiently find the occurrences of a set containing subgraphs of multiple sizes, outperforming previous methods.

Keywords

Graph Mining, Subgraphs, G-Tries, Network Motifs

Awards/Notice

Best Paper Award

Reference (text)

Pedro Ribeiro and Fernando Silva. Querying Subgraph Sets with G-Tries. (Best Paper Award) Proceedings of the 2nd ACM SIGMOD Workshop on Databases and Social Networks (DBSocial), pp. 25-30, ACM, Scottsdale, USA, May, 2012.

Bibtex

@inproceedings{ribeiro-DBSOCIAL2012,
  author = {Pedro Ribeiro and Fernando Silva},
  title = {Querying Subgraph Sets with G-Tries},
  doi = {10.1145/2304536.2304541},
  booktitle = {2nd ACM SIGMOD Workshop on Databases and Social Networks},
  pages = {25-30},
  publisher = {ACM},
  month = {May},
  year = {2012}
}