GQS: A graph query system for pattern mining under iso- and homomorphism
Thomas Fannes, Jan Ramon · Lirias · 2014
Graph databases are typically used for large amounts of networked data. Recent years have seen an increasing interest in graph databases, with applications in, e.g., social networks, biological interaction networks, etc. In our work, we focus on large databases where we are interested in listing and aggregating over embeddings of a pattern graph. Although these type of databases exists, efficient querying is not very deeply investigated, especially for certain aspects relevant to data mining and machine learning. GQS, our Graph Query System, is an integration of different, state-of-the-art contributions into a reusable query system. First of all, our query system allows for the mining of (rooted) bounded treewidth patterns under iomomorphism, only exponential in the treewidth and not in the network size. Secondly, GQS also allows for querying embeddings of a pattern under isomomorphism using a state-of-the-art randomization algorithm, only mildly exponential in the network size. Thirdly, in large networks, different embeddings can not be seen as statistically independent, which is required by many learning methods. We compute a measure for the effective sample size of a networked sample (i.e., the amount of statistical training information in a set of overlapping embeddings), which also generates weights for the training examples which then can be used by machine learning algorithms. Finally, we expose a set of operators that allow different query optimizations. Our graph query system is implemented in C++ and makes heavily use of template meta-programming.