Towards Hybrid Methods for Graph Pattern Queries Foteini Katsarou Nikos Ntarmos Peter Triantafillou School of Computing Science School of Computing Science School of Computing Science University of Glasgow, UK University of Glasgow, UK University of Glasgow, UK f.katsarou.1@ nikos.ntarmos@ peter.triantafillou@ research.gla.ac.uk glasgow.ac.uk glasgow.ac.uk ABSTRACT graph is contained in each graph and/or find all its occur- In the subgraph querying problem, given a query graph and rences within a larger stored graph. Subgraph querying a dataset of graphs, we want to locate which graphs in the entails the subgraph isomorphism problem (abbreviated as dataset contain the query and/or find all its occurrences. sub-iso), which is known to be NP-complete. Over the years, Over the years, numerous methods, fragmented in 2 cate- subgraph querying has received a lot of attention which is gories, were proposed to tackle the problem. In the first cat- evident by the numerous proposed methods. Related work egory, methods follow the filter-then-verify (FTV) paradigm is categorized in 2 major categories: the filter-then-verify where an index is used to filter out graphs that definitely do (FTV) methods and the no-filter, verify (NFV) methods. not contain the query as an answer. On the remaining set Various recent experimental analysis papers (e.g. [2, 3, 1]) of graphs, a subgraph isomorphism algorithm is applied to compare and stress-test the proposed methods and provide verify the graphs that contain the query graph. A second interesting insights about the performance of both FTV and category, so called no-filter, verify (NFV), invested in opti- NFV methods. mizing the subgraph isomorphism process, by employing a lightweight index primarily to locate candidate vertices on 2. APPROACH, RESULT OVERVIEW, AND the graphs in the dataset. The current trend is to totally dis- CONCLUSIONS miss the FTV methods and employ NFV methods instead. The latest works, e.g. [3], tend to dismiss the FTV meth- With this work we wish to point out that a hybrid solution ods with the claim that the fast sub-iso test of the NFV that is, a combination of the filtering of some FTV method methods significantly outperforms the index-based scan of with the subgraph isomorphism test of top-performing NFV the FTV methods. In the current work, we put forth our methods, can be highly competitive in terms of performance concern about the possibility that lots of current state of vis-a-vis methods from either the FTV or the NFV category. the art and on-going efforts miss a potential for deriving We will present some preliminary results, based on experi- highly performant algorithms by investigating hybrid solu- ments, where such a combination proves to be beneficial by tions which maintain the filtering of the FTV and the much primarily avoiding the initiation of a large number of redun- faster sub-iso test algorithms of the NFV methods. Based dant subgraph isomorphism tests. on our initial experiments, this design option can introduce very significant performance gains in the subgraph match- Keywords ing problem. Essentially, the benefits stem from using the FTV-style indexes in order to avoid the need to perform the Graph databases, graph query processing, subgraph isomor- sub-iso test on a large majority of the graphs in the graph phism DB. And the benefits are large both against FTV and NFV methods alone. 1. INTRODUCTION Graphs are ideal for representing complex entities as they 3. REFERENCES physically incorporate relationships/interactions in the form [1] F. Katsarou, N. Ntarmos, and P. Triantafillou. of edges. Revealing the existence of a pattern graph in vari- Subgraph Querying with Parallel Use of Query ous graphs/parts of the same graph is essential to graph an- Rewritings and Alternative Algorithms. In EDBT, ’17. alytics. In subgraph querying, given a pattern graph (query) [2] F. Katsarou, N. Ntarmos, and P. Triantafillou. and a dataset of graphs, we want to know whether the query Performance and scalability of indexed subgraph query processing methods. PVLDB, 8(12):1566–1577, 2015. [3] J. Lee, W.-S. Han, R. Kasperovics, and J.-H. Lee. An in-depth comparison of subgraph isomorphism algorithms in graph databases. PVLDB, 6(2), 2012. c 2017, Copyright is with the authors. Published in the Workshop Pro- ceedings of the EDBT/ICDT 2017 Joint Conference (March 21, 2017, Venice, Italy) on CEUR-WS.org (ISSN 1613-0073). Distribution of this paper is permitted under the terms of the Creative Commons license CC- by-nc-nd 4.0