In the subgraph querying problem, given a query graph and a dataset of graphs, we want to locate which graphs in the dataset contain the query and/or nd all its occurrences. Over the years, numerous methods, fragmented in 2 categories, were proposed to tackle the problem. In the rst category, methods follow the lter-then-verify (FTV) paradigm where an index is used to lter out graphs that de nitely do not contain the query as an answer. On the remaining set of graphs, a subgraph isomorphism algorithm is applied to verify the graphs that contain the query graph. A second category, so called no- lter, verify (NFV), invested in optimizing the subgraph isomorphism process, by employing a lightweight index primarily to locate candidate vertices on the graphs in the dataset. The current trend is to totally dismiss the FTV methods and employ NFV methods instead. With this work we wish to point out that a hybrid solution that is, a combination of the ltering of some FTV method with the subgraph isomorphism test of top-performing NFV methods, can be highly competitive in terms of performance vis-a-vis methods from either the FTV or the NFV category. We will present some preliminary results, based on experiments, where such a combination proves to be bene cial by primarily avoiding the initiation of a large number of redundant subgraph isomorphism tests. Graph databases, graph query processing, subgraph isomorphism 1. INTRODUCTION

Graphs are ideal for representing complex entities as they physically incorporate relationships/interactions in the form of edges. Revealing the existence of a pattern graph in various graphs/parts of the same graph is essential to graph analytics. In subgraph querying, given a pattern graph (query) and a dataset of graphs, we want to know whether the query graph is contained in each graph and/or nd all its occurrences within a larger stored graph. Subgraph querying entails the subgraph isomorphism problem (abbreviated as sub-iso), which is known to be NP-complete. Over the years, subgraph querying has received a lot of attention which is evident by the numerous proposed methods. Related work is categorized in 2 major categories: the lter-then-verify (FTV) methods and the no- lter, verify (NFV) methods. Various recent experimental analysis papers (e.g. [2, 3, 1]) compare and stress-test the proposed methods and provide interesting insights about the performance of both FTV and NFV methods. 2.

APPROACH, RESULT OVERVIEW, AND CONCLUSIONS

The latest works, e.g. [3], tend to dismiss the FTV methods with the claim that the fast sub-iso test of the NFV methods signi cantly outperforms the index-based scan of the FTV methods. In the current work, we put forth our concern about the possibility that lots of current state of the art and on-going e orts miss a potential for deriving highly performant algorithms by investigating hybrid solutions which maintain the ltering of the FTV and the much faster sub-iso test algorithms of the NFV methods. Based on our initial experiments, this design option can introduce very signi cant performance gains in the subgraph matching problem. Essentially, the bene ts stem from using the FTV-style indexes in order to avoid the need to perform the sub-iso test on a large majority of the graphs in the graph DB. And the bene ts are large both against FTV and NFV methods alone. 3.