Angela Bonifati
email: angela.bonifati@inria.fr

Radu Ciucanu
email: radu.ciucanu@inria.fr

Aurélien Lemay
email: aurelien.lemay@inria.fr

Learning Path Queries on Graph Databases

We investigate the problem of learning graph queries by exploiting user examples. The input consists of a graph database in which the user has labeled a few nodes as positive or negative examples, depending on whether or not she would like the nodes as part of the query result. Our goal is to handle such examples to find a query whose output is what the user expects. This kind of scenario is pivotal in several application settings where unfamiliar users need to be assisted to specify their queries. In this paper, we focus on path queries defined by regular expressions, we identify fundamental difficulties of our problem setting, we formalize what it means to be learnable, and we prove that the class of queries under study enjoys this property. We additionally investigate an interactive scenario where we start with an empty set of examples and we identify the informative nodes i.e., those that contribute to the learning process. Then, we ask the user to label these nodes and iterate the learning process until she is satisfied with the learned query. Finally, we present an experimental study on both real and synthetic datasets devoted to gauging the effectiveness of our learning algorithm and the improvement of the interactive approach.

' Let G φ " pV φ , E φ q be the graph that intuitively encodes the formula ϕ. Formally, V φ " tν φ , u 1 , . . . , u k`1 , ν 1φ u and E φ " tpν φ , s 1 , u 1 q, pu k`1 , s 2 , ν 1φ qu Y tpu ì , a ij , u ì`1 q | 1 ď i ď k, 1 ď j ď 3u,

INTRODUCTION

Graph databases [START_REF] Wood | Query languages for graph databases[END_REF] are becoming pervasive in several application scenarios such as the Semantic Web [START_REF] Arenas | Querying semantic web data with SPARQL[END_REF], social [START_REF] Ronen | SoQL: A language for querying and creating data in social networks[END_REF] and biological [START_REF] Palaga | High-performance information extraction with AliBaba[END_REF] networks, and geographical databases [START_REF] Angles | Survey graph database models[END_REF], to name a few. A graph database is essentially a directed, edge-labeled graph. As an example, consider in Figure 1 a graph representing a geographical database having as nodes the neighborhoods of a city area (N1 to N6), along with cinemas (C1 and C2), and restaurants (R1 and R2) in such neighborhoods. The edges represent public transportation facilities from a neighborhood to another (using labels tram and bus), along with other kind of facilities (using labels cinema and restaurant). For instance, the graph indicates that one can travel by bus between the neighborhoods N2 and N3, that in the neighborhood N4 exists a cinema C1, and so on. Many mechanisms have been proposed to query a graph database, the majority of them being based on regular expressions [START_REF] Barceló | Querying graph databases[END_REF][START_REF] Wood | Query languages for graph databases[END_REF]. By continuing on our running example, imagine that a user wants to know from which neighborhoods in the city represented in Figure 1 she can reach cinemas via public transportation. These neighborhoods can be retrieved using a path query defined by the following regular expression:

q " ptram `busq ˚¨cinema

The query q selects the nodes N1, N2, N4, and N6 as they are entailed by the following paths in the graph:

N1 tram ÝÝÑ N4 cinema ÝÝÝÝÑ C1, N2 bus Ý Ñ N1 tram ÝÝÑ N4 cinema ÝÝÝÝÑ C1, N4 cinema ÝÝÝÝÑ C1, N6 cinema ÝÝÝÝÑ C2.
Although very expressive, graph query languages are difficult to understand by non-expert users who are unable to specify their queries with a formal syntax. The problem of assisting non-expert users to specify their queries has been recently raised by Jagadish et al. [START_REF] Jagadish | Making database systems usable[END_REF][START_REF] Nandi | Guided interaction: Rethinking the query-result paradigm[END_REF]. More concretely, they have observed that "constructing a database query is often challenging for the user, commonly takes longer than the execution of the query itself, and does not use any insights from the database". While they have mentioned these problems in the context of relational databases, we argue that they become even more difficult to tackle for graph databases. Indeed, graph databases usually do not carry proper metadata as they lack schemas and/or do not ex-hibit a clear distinction between instances and schemas. The absence of metadata along with the difficulty of visualizing possibly large graphs make unfeasible traditional query specification paradigms for non-expert users, such as query by example [START_REF] Zloof | Query by example[END_REF]. Our work follows the recent trend of specifying graph queries by example [START_REF] Mottin | Exemplar queries: Give me an example of what you need[END_REF][START_REF] Jayaram | Towards a query-by-example system for knowledge graphs[END_REF]. Precisely, we focus on graph queries using regular expressions, which are fundamental building blocks of graph query languages [START_REF] Barceló | Querying graph databases[END_REF][START_REF] Wood | Query languages for graph databases[END_REF], while both [START_REF] Mottin | Exemplar queries: Give me an example of what you need[END_REF][START_REF] Jayaram | Towards a query-by-example system for knowledge graphs[END_REF] consider simple graph patterns.

While the problem of executing path queries defined by regular expressions on graphs has been extensively studied recently [START_REF] Bagan | A trichotomy for regular simple path queries on graphs[END_REF][START_REF] Losemann | The complexity of regular expressions and property paths in SPARQL[END_REF][START_REF] Koschmieder | Regular path queries on large graphs[END_REF], no research has been done on how to actually specify such queries. Our work focuses on the problem of assisting non-expert users to specify such path queries, by exploiting elementary user input.

By continuing on our running example, we assume that the user is not familiar with any formal syntax of query languages, while she still wants to specify the above query q on the graph database in Figure 1 by providing examples of the query result. In particular, she would positively or negatively label some graph nodes according to whether or not they would be selected by the targeted query. Thus, let us imagine that the user labels the nodes N2 and N6 as positive examples because she wants these nodes as part of the result. Indeed, one can reach cinemas from N2 and N6, respectively, through the following paths:

N2 bus Ý Ñ N1 tram ÝÝÑ N4 cinema ÝÝÝÝÑ C1, N6 cinema ÝÝÝÝÑ C2.
Similarly, the user labels the node N5 as a negative example since she would not like it as part of the query result. Indeed, there is no path starting in N5 through which the user can reach a cinema. We also observe that the query q above is consistent with the user's examples because q selects all positive examples and none of the negative ones. Unfortunately, there may exist an infinite number of queries consistent with the given examples. Therefore, we are interested to find either the "exact" query that the user has in mind or, alternatively, an equivalent query, which is close enough to the user's expectations.

Apart from assisting unfamiliar users to specify queries, our research has other crucial applications, such as mining scientific workflows. Regular expressions have already been used in the literature as a well-suited mechanism for inter-workflow coordination [START_REF] Heinlein | Workflow and process synchronization with interaction expressions and graphs[END_REF]. The path queries on graph databases that we study in this paper can be applied to assist scientists in identifying interrelated workflows that are of interest for them. For instance, assume that a biologist is interested in retrieving all interrelated workflows having a pattern that starts with protein purification, continues with an arbitrary number of protein separation steps, and ends with mass spectrometry. This corresponds to the following regular expression: ProteinPurification ¨ProteinSeparation ˚¨MassSpectrometry.

Instead of specifying such a pattern in a formal language, the biologist may be willing to label some sequences of modules from a set of available workflows as positive or negative examples, as illustrated in Figure 2. Our algorithms can be thus applied to infer the workflow pattern that the biologist has in mind. Typically in graphs representing workflows the labels are attached to the nodes (e.g., as in Figure 2) instead of the edges. In this paper, we have opted for edge-labeled graphs rather than node-labeled graphs, but our algorithms and learning techniques for the considered class of queries are applicable to the latter class of graphs in a seamless fashion. The problem of mining scientific workflows has been considered in recent work [START_REF] Belhajjame | Annotating the behavior of scientific modules using data examples: A practical approach[END_REF], which leverages data instances as representatives of the input and output of a workflow module. In our approach, we rely on simpler user feedback, namely Boolean labeling of sequences of modules across interrelated workflows.

Since our goal is to infer the user queries while minimizing the amount of user feedback, our research is also applicable to crowdsourcing scenarios [START_REF] Franklin | CrowdDB: answering queries with crowdsourcing[END_REF], in which such minimization typically entails lower financial costs. Indeed, we can imagine that crowdworkers provide the set of positive and negative examples mentioned above for path query learning. Moreover, our work can be used in assisting nonexpert users in other fairly complex tasks, such as specifying schema mappings [START_REF] Yan | Data-driven understanding and refinement of schema mappings[END_REF] i.e., logical assertions between two path queries, one on a source schema and another on a target schema.

To the best of our knowledge, our work is the first to study the problem of learning path queries defined by regular expressions on graphs via user examples. More precisely, we make the following main contributions:

' We investigate a learning framework inspired by computational learning theory [START_REF] Kearns | An introduction to computational learning theory[END_REF], in particular by grammatical inference [START_REF] De La Higuera | Grammatical Inference: Learning Automata and Grammars[END_REF] and we identify fundamental difficulties of such a framework. We consequently propose a definition of learnability adapted to our setting.

' We propose a learning algorithm and we precisely characterize the conditions that a graph must satisfy to guarantee that every user's goal query can be learned. Essentially, the main theoretical result of the paper states that for every query q there exists a polynomial set of examples that given as input to our learning algorithm guarantees the learnability of q. Additionally, our learning algorithm is guaranteed to run in polynomial time, whether or not the aforementioned set of examples is given as input.

' We investigate an interactive scenario, which bootstraps with an empty set of examples and builds it along the way. Indeed, the learning algorithm finely interacts with the user by proposing nodes that can be labeled and repeats the interactions until the goal query is learned. More precisely, we analyze what it means for a node to be informative for the learning process, we show the intractability of deciding whether a node is informative or not, and we propose efficient strategies to present examples to the user.

' To evaluate our approach, we have run experiments on both real-world and synthetic datasets. Our study shows the effectiveness of the learning algorithm and the advantage of using an interactive strategy, which significantly reduces the number of examples needed to learn the goal query.

Finally, we would like to spend a few words on the class of queries that we investigate in this paper. As already mentioned, we focus on regular expressions, which are fundamental for graph query languages [START_REF] Barceló | Querying graph databases[END_REF][START_REF] Wood | Query languages for graph databases[END_REF] and lately used in the definition of SPARQL property paths 1 . Graph queries defined by regular expressions have been known as regular path queries. Intuitively, such queries retrieve pairs of nodes in the graph s.t. one can navigate between them with a path in the language of a given regular expression [START_REF] Barceló | Querying graph databases[END_REF][START_REF] Wood | Query languages for graph databases[END_REF]. Although the usual semantics of regular path queries is binary (i.e., selects pairs of nodes), in this paper we consider a generalization of this semantics that we call monadic, as it outputs only the originated nodes of the paths. The motivation behind using a monadic semantics is essentially threefold. First, it entails a larger space of potential solutions than a binary semantics. Indeed, with the latter semantics the end node of a path is fixed, which basically corresponds to have a smaller number of candidate paths that start at the originated node and that can be possibly labeled by the user. Second, in our learning framework, the amount of user effort should be kept as minimal as possible (which led to design an interactive scenario) and thus we let the user focus solely on the originated nodes of the paths rather than on pairs of nodes. Third, the development of the learning algorithm for monadic queries is extensible to binary queries and n-ary queries in a straightforward fashion, as shown in the paper.

Organization. In Section 2, we introduce some basic notions. In Section 3, we define our framework for learning from a set of examples, we present our learning algorithm, and we prove our learnability results. In Section 4, we propose an interactive algorithm and characterize the quantity of information of a node. In Section 5, we experimentally evaluate the performance of our algorithms. Finally, we conclude our paper and outline future directions in Section 6. Due to space restrictions, in this paper we omit the proofs of several results and we refer to the appendix of our technical report [START_REF] Bonifati | Learning path queries on graph databases[END_REF] for detailed proofs.

Related work

Learning queries from examples is a popular and interesting topic in databases. Very recently, algorithms for learning relational queries (e.g., quantifiers [START_REF] Abouzied | Learning and verifying quantified boolean queries by example[END_REF], joins [START_REF] Bonifati | Interactive inference of join queries[END_REF][START_REF] Bonifati | Interactive join query inference with JIM[END_REF]) or XML queries (e.g., tree patterns [START_REF] Staworko | Learning twig and path queries[END_REF]) have been proposed. Besides learning queries, researchers have investigated the learnability of relational schema mappings [START_REF] Cate | Learning schema mappings[END_REF], as well as schemas [START_REF] Bex | Learning deterministic regular expressions for the inference of schemas from XML data[END_REF] and transformations [START_REF] Laurence | Learning sequential tree-to-word transducers[END_REF] for XML. A fairly close problem to 1 http://www.w3.org/TR/sparql11-query/ learning is definability [START_REF] Antonopoulos | Definability problems for graph query languages[END_REF]. In this paragraph, we discuss the positioning of our own work w.r.t. these and other papers.

A wealth of research on using computational learning theory [START_REF] Kearns | An introduction to computational learning theory[END_REF] has been recently conducted in databases [START_REF] Abouzied | Learning and verifying quantified boolean queries by example[END_REF][START_REF] Bex | Learning deterministic regular expressions for the inference of schemas from XML data[END_REF][START_REF] Bonifati | Interactive inference of join queries[END_REF][START_REF] Laurence | Learning sequential tree-to-word transducers[END_REF][START_REF] Staworko | Learning twig and path queries[END_REF][START_REF] Cate | Learning schema mappings[END_REF]. In this paper, we use grammatical inference [START_REF] De La Higuera | Grammatical Inference: Learning Automata and Grammars[END_REF] i.e., the branch of machine learning that aims at constructing a formal grammar by generalizing a set of examples. In particular, all the above papers on learning tree patterns [START_REF] Staworko | Learning twig and path queries[END_REF], schemas [START_REF] Bex | Learning deterministic regular expressions for the inference of schemas from XML data[END_REF][START_REF] Ciucanu | Learning schemas for unordered XML[END_REF], and transformations [START_REF] Laurence | Learning sequential tree-to-word transducers[END_REF] are based on it.

Our definition of learnability is inspired by the well-known framework of language identification in the limit [START_REF] Gold | Complexity of automaton identification from given data[END_REF], which requires a learning algorithm to be polynomial in the size of the input, sound (i.e., always return a concept consistent with the examples given by the user or a special null value if such concept does not exist) and complete (i.e., able to produce every concept with a sufficiently rich set of examples). In our case, we show that checking the consistency of a given set of examples is intractable, which implies that there is no algorithm able to answer null in polynomial time when the sample is inconsistent. This leads us to the conclusion that path queries are not learnable in the classical framework. Consequently, we slightly modify the framework and require the algorithm to learn the goal query in polynomial time if a polynomially-sized characteristic set of examples is provided. This learning framework has been recently employed for learning XML transformations [START_REF] Laurence | Learning sequential tree-to-word transducers[END_REF] and is referred to as learning with abstain since the algorithm can abstain from answering when the characteristic set of examples is not provided.

The classical algorithm for learning a regular language from positive and negative word examples is RPNI [START_REF] Oncina | Inferring regular languages in polynomial update time[END_REF], which basically works as follows: (i) construct a DFA (usually called prefix tree acceptor or PTA [START_REF] De La Higuera | Grammatical Inference: Learning Automata and Grammars[END_REF]) that selects all positive examples; (ii) generalize it by state merges while no negative example is covered. Unfortunately, RPNI cannot be directly adapted to our setting since the input positive and negative examples are not words in our case. Instead, we have a set of graph nodes starting from which we have to select (from a potentially infinite set) the paths that led the user to label them as examples. After selecting such paths, we generalize by state merges, similarly to RPNI.

A problem closely related to learning is definability, recently studied for graph databases [START_REF] Antonopoulos | Definability problems for graph query languages[END_REF]. Learning and definability have in common the fact that they look for a query consistent with a set of examples. The difference is that learning allows the query to select or not the nodes that are not explicitly labeled as positive examples while definability requires the query to select nothing else than the set of positive examples (i.e., all other nodes are implicitly negative). Nonetheless, some of the intractability proofs for definability can be adapted to our learning framework to show the intractability of consistency checking (cf. Section 3). To date, no polynomial algorithms have been yet proposed to construct path queries from a consistent set of examples.

GRAPH DATABASES AND QUERIES

In this section we define the concepts that we manipulate throughout the paper.

Alphabet and words. An alphabet Σ is a finite, ordered set of symbols. A word over Σ is a sequence a1 . . . an of symbols from Σ. By |w| we denote the length of a word w. The concatenation of two words w1 " a1 . . . an and w2 " b1 . . . bm, denoted w1 ¨w2, is the word a1 . . . anb1 . . . bm. By ε we denote the empty word. A language is a set of words. By Σ ˚we denote the language of all words over Σ. We extend the order on Σ to the standard lexicographical order ď lex on words over Σ and define a well-founded canonical order ď on words: w ď u iff |w| ă |u| or |w| " |u| and w ď lex u.

Graph databases.

A graph database is a finite, directed, edge-labeled graph [START_REF] Barceló | Querying graph databases[END_REF][START_REF] Wood | Query languages for graph databases[END_REF]. Formally, a graph (database) G over an alphabet Σ is a pair pV , Eq, where V is a set of nodes and E Ď V ˆΣ ˆV is a set of edges. Each edge in G is a triple pνo, a, νeq P V ˆΣ ˆV , where νo is the origin of the edge, νe is the end of the edge, and a is the label of the edge. We often abuse notation and write ν P G and pνo, a, νeq P G instead of ν P V and pνo, a, νeq P E, respectively. For example, take in Figure 3 Paths. A word w " a1 . . . an matches a sequence of nodes ν0ν1 . . . νn if, for each 1 ď i ď n, the triple pνi´1, ai, νiq is an edge in G. For example, for the graph G0 in Figure 3, the word aba matches the sequences of nodes ν1ν2ν3ν4 and ν3ν2ν3ν4, respectively, but does not match the sequence ν1ν2ν7ν2. Note that the empty word ε matches the sequence νν for every ν P G. Given a node ν P G, by paths G pνq we denote the language of all words that match a sequence of nodes from G that starts by ν. In the sequel, we refer to such words as paths, and moreover, we say that a path w is covered by a node ν if w P paths G pνq. Paths are ordered using the canonical order ď. For example, for the graph G0 in Figure 3 we have paths G 0 pν5q " tε, a, b, cu. Note that ε P paths G pνq for every ν P G. Moreover, note that paths G pνq is finite iff there is no cycle reachable from ν in G. For example, for the graph G0 in Figure 3, paths G 0 pν1q is infinite. We naturally extend the notion of paths to a set of nodes i.e., given a set of nodes X from a graph G, by paths G pXq " Ť νPX paths G pνq.

Regular expressions and automata. A regular language is a language defined by a regular expression i.e., an expression of the following grammar:

q :" ε | a pa P Σq | q1 `q2 | q1 ¨q2 | q ˚,
where by "¨" we denote the concatenation, by "`" we denote the disjunction, and by "˚" we denote the Kleene star.

By Lpqq we denote the language of q, defined in the natural way [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF]. For instance, the language of pa ¨bq ˚¨c contains words like c, abc, ababc, etc. Regular languages can alternatively be represented by automata and we also refer to [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF] for standard definitions of nondeterministic finite word automaton (NFA) and deterministic finite word automaton (DFA). In particular, we represent every regular language by its canonical DFA that is the unique smallest DFA that describe the language. For example, we present in Figure 4 the canonical DFA for pa ¨bq ˚c. Path queries. We focus on the class of path queries defined by regular expressions i.e., that select nodes having at least one path in the language of a given regular expression. Formally, given a graph G and a query q, we define the set of nodes selected by q on G:

qpGq

" tν P G | Lpqq X paths G pνq ‰ Hu.
For example, given the graph G0 in Figure 3, the query a selects all nodes except ν4, the query pa ¨bq ˚¨c selects the nodes ν1 and ν3, and the query b ¨b ¨c ¨c selects no node. In the rest of the paper, we denote the set of all path queries by pq and we refer to them simply as queries. We represent a query by its canonical DFA, hence the size of a query is the number of states in the canonical DFA of the corresponding regular language. For example, the size of the query pa¨bq ˚¨c is 3 (cf. Figure 4).

Equivalent queries. Two queries q and q 1 are equivalent if for every graph G they select exactly the same set of nodes i.e., qpGq " q 1 pGq. For example, the queries a and a ¨bå re equivalent since each node having a path ab . . . b has also a path a. This example can be easily generalized and yields to defining the class of prefix-free queries. Formally, we say that a query q is prefix-free if for every word from Lpqq, none of its prefixes belongs to Lpqq. Given a query q, there exists a unique prefix-free query equivalent to q, which, moreover, can be constructed by simply removing all outgoing transitions of every final state in the canonical DFA of q. Our interest in prefix-free queries is that they can be seen as minimal representatives of equivalence classes of queries and as such they are desirable queries for learning. Indeed, every prefix-free query q is in fact equivalent to an infinite number of queries q ¨pq 1 `εq, where q 1 can be every pq. In the remainder, we assume w.l.o.g. that all queries that we manipulate are prefix-free.

LEARNING FROM EXAMPLES

The input of a learning algorithm consists of a graph on which the user has annotated a few nodes as positive or negative examples, depending on whether or not she would like the nodes as part of the query result. Our goal is to exploit such examples to find a query that satisfies the user. In this paper, we explore two learning protocols: (i) the user provides a sample (i.e., a set of examples) that remains fixed during the learning process, and (ii) the learning algorithm interactively asks the user to label more examples until the learned query behaves exactly as the user wants.

First, we concentrate on the case of a fixed set of examples. We identify the challenges of such an approach, we show the unfeasability of the standard framework of language identification in the limit [START_REF] Gold | Complexity of automaton identification from given data[END_REF] and slightly modify it to propose a learning framework with abstain (Section 3.1). Next, we present a learning algorithm for the class of pq (Section 3.2) and we identify the conditions that a graph and a sample must satisfy to allow polynomial learning of the user's goal query (Section 3.3). We study the case of query learning from user interactions in Section 4.

Learning framework

Given a graph G " pV , Eq, an example is a pair pν, αq, where ν P V and α P t`, ´u. We say that an example of the form pν, `q is a positive example while an example of the form pν, ´q is a negative example. A sample S is a set of examples i.e., a subset of V ˆt`, ´u. Given a sample S, we denote the set of positive examples tν P V | pν, `q P Su by S`and the set of negative examples tν P V | pν, ´q P Su by S´. A sample is consistent (with the class of pq) if there exists a (pq) query that selects all positive examples and none of the negative ones. Formally, given a graph G and a sample S, we say that S is consistent if there exists a query q s.t. S`Ď qpGq and S´X qpGq " H. In this case we say that q is consistent with S. For instance, take the graph G0 in Figure 3 and the sample S s.t. S`" tν1, ν3u and S´" tν2, ν7u; S is consistent because there exist queries like pa ¨bq ˚¨c or c `pa ¨b ¨cq that are consistent with S.

Next, we want to formalize what means for a class of queries to be learnable, as it is usually done in the context of grammatical inference [START_REF] De La Higuera | Grammatical Inference: Learning Automata and Grammars[END_REF]. The standard learning framework is language identification the limit (in polynomial time and data) [START_REF] Gold | Complexity of automaton identification from given data[END_REF], which requires a learning algorithm to operate in time polynomial in the size of its input, to be sound (i.e., always return a query consistent with the examples given by the user or a special null value if no such query exists), and complete (i.e., able to produce every query with a sufficiently rich set of examples).

Since we aim at a polynomial time algorithm that returns a query consistent with a sample, we must first investigate the consistency checking problem i.e., deciding whether such a query exists. To this purpose, we first identify a necessary and sufficient condition for a sample to be consistent. Lemma 3.1 Given a graph G and a sample S, S is consistent iff for every ν P S`it holds that paths G pνq Ď paths G pS´q.

From this characterization we can derive that the fundamental problem of consistency checking is PSPACE-complete. Lemma 3.2 Given a graph G and a sample S, deciding whether S is consistent is PSPACE-complete.

Proof sketch. The membership to PSPACE follows from Lemma 3.1 and the known result that deciding the inclusion of NFAs is PSPACE-complete [START_REF] Stockmeyer | Word problems requiring exponential time: Preliminary report[END_REF]. The PSPACE-hardness follows by reduction from the universality of the union problem for DFAs, known as being PSPACE-complete [START_REF] Kozen | Lower bounds for natural proof systems[END_REF]. This implies that an algorithm able to always answer null in polynomial time when the sample is inconsistent does not exist, hence our class of queries is not learnable in the classical framework. One solution could be to study less expressive classes of queries. However, as shown by the following Lemma, consistency checking remains intractable even for a very restricted class of queries, referred as "SORE(¨)" in [START_REF] Antonopoulos | Definability problems for graph query languages[END_REF]. Lemma 3.3 Given a graph G and a sample S, deciding whether there exists a query of the form a1 ¨. . . ¨an (pairwise distinct symbols) consistent with S is NP-complete.

Proof sketch. For the membership of the problem to NP, we point out that a non-deterministic Turing machine guesses a query q that is a concatenation of pairwise distinct symbols (hence of length bounded by |Σ|) and then checks whether q is consistent with S. The NP-hardness follows by reduction from 3SAT, well-known as being NP-complete. The proofs of Lemma 3.2 and 3.3 rely on techniques inspired by the definability problem for graph query languages [START_REF] Antonopoulos | Definability problems for graph query languages[END_REF]. We also point out that the same intractability results for consistency checking hold for binary semantics.

Another way to overcome the intractability of our class of queries is to relax the soundness condition and adopt a learning framework with abstain, similarly to what has been recently done for learning XML transformations [START_REF] Laurence | Learning sequential tree-to-word transducers[END_REF]. More precisely, we allow the learning algorithm to answer a special value null whenever it cannot efficiently construct a consistent query. In practice, the null value is interpreted as "not enough examples have been provided". However, the learning algorithm should always return in polynomial time either a consistent query or null. As an additional clause, we require a learning algorithm to be complete i.e., when the input sample contains a polynomially-sized characteristic sample [START_REF] De La Higuera | Grammatical Inference: Learning Automata and Grammars[END_REF][START_REF] Gold | Complexity of automaton identification from given data[END_REF], the algorithm must return the goal query. More formally, we have the following. Definition 3.4 A class of queries Q is learnable with abstain in polynomial time and data if there exists a polynomial learning algorithm learner that is:

1. Sound with abstain. For every graph G and sample S over G, the algorithm learner pG, Sq returns either a query in Q that is consistent with S, or null if no such query exists or it cannot be constructed efficiently.

2.

Complete. For every query q P Q, there exists a graph G and a polynomially-sized characteristic sample CS on G s.t. for every sample S extending CS consistently with q (i.e., CS Ď S and q is consistent with S), the algorithm learner pG, Sq returns q.

Note that the polynomiality depends on the choice of a representation for queries and recall that we represent each pq with its canonical DFA. Next, we present a polynomial learning algorithm fulfilling the two aforementioned conditions and we point out the construction of a polynomial characteristic sample to show the learnability of pq.

Learning algorithm

In a nutshell, the idea behind our learning algorithm is the following: for each positive node, we seek the path that the user followed to label such a node, then we construct the disjunction of the paths obtained in the previous step, and we end by generalizing this disjunction while remaining consistent with both positive and negative examples.

More formally, the algorithm consists of two complementary steps that we describe next: selecting the smallest consistent paths and generalizing them.

Selecting the smallest consistent paths (SCPs). Since the labeled nodes in a graph may be the origin of multiple paths, classical algorithms for learning regular expressions from words, such as RPNI [START_REF] Oncina | Inferring regular languages in polynomial update time[END_REF], are not directly applicable to our setting. Indeed, we have a set of nodes in the graph from which we have to first select (from a potentially infinite set) the paths responsible for their selection. Therefore, the first challenge of our algorithm is to select for each positive node a path that is not covered by any negative. We call such a path a consistent path. One can select consistent paths by simply enumerating (according to the canonical order ď) the paths of each node labeled as positive and stopping when a consistent path for each node is found. We refer to the obtained set of paths as the set of smallest consistent paths (SCPs) because they are the smallest (w.r.t. ď) consistent paths for each node. As an example, for the graph G0 in Figure 3 and a sample s.t. S`" tν1, ν3u and S´" tν2, ν7u, we obtain the SCPs abc and c for ν1 and ν3, respectively. Notice that in this case the disjunction of the SCPs (i.e., the query c `pa ¨b ¨cq) is consistent with the input sample and one may think that a learning algorithm should return such a query. The shortcoming of such an approach is that the learned query would be always very simple in the sense that it uses only concatenation and disjunction. Since we want a learning algorithm that covers all the expressibility of pq (in particular including the Kleene star), we need to extend the algorithm with a further step, namely the generalization. We detail such a step at the end of this section.

Another problem is that the user may provide an inconsistent sample, by labeling a positive node having no consistent path (cf. Lemma 3.1). To clarify when such a situation occurs, consider a simple graph such as the one in Figure 5 having one positive node (labeled with `) and two negative ones (labeled with ´). We observe that the positive node has an infinite number of paths. However, all of them are covered by the two negative nodes, thus yielding an inconsistent sample. This example also shows that the simple procedure described above (i.e., enumerate the paths of the positive nodes and stop when finding consistent ones) fails because it leads to enumerating an infinite number on paths and never halting. On the other hand, we cannot perform consistency checking before selecting the SCPs since this fundamental problem is intractable (cf. Lemma 3.2 and 3.3). As a result, to avoid this possibly infinite enumeration, we choose to fix the maximal length of a SCP to a bound k. This bound engenders a new issue: for a fixed k it may not be possible to detect SCPs for all positive nodes. For instance, assume a graph that the user labels consistently with the query pa ¨bq ˚¨c, in particular she labels three positive nodes for which the SCPs are c, abc, and ababc. For a fixed k " 3, the SCP ababc is not detected and the disjunction of the first two SCPs (i.e., c`pa¨b¨cq) is not a query consistent with the sample. For all these reasons, we introduce a generalization phase in the algorithm, which permits to solve the two mentioned shortcomings i.e., (i) to learn a query that covers all the expressibility of pq, and (ii) to select all positive examples even though not all of them have SCPs shorter than k.

Generalizing SCPs. We have seen how to select, whenever possible, a SCP of length bounded by k for each positive example. Next, we show how we can employ these SCPs to construct a more general query. The learning algorithm (Algorithm 1) takes as input a graph G and a sample S, and outputs a query q consistent with S whenever such query exists and can be built using SCPs of length bounded by k; otherwise, the algorithm outputs a special value null.

Algorithm 1 Learning algorithm -learner pG, Sq. Input: graph G, sample S Output: query q consistent with S or null Parameter: fixed k P N {{maximal length of a SCP 1: for ν P S`. Dp P Σ ďk . p P paths G pνqzpaths G pS´q do 2:

P :" P Y tminďppaths G pνqzpaths G pS´qqu 3: let A be the prefix tree acceptor for P 4: while Ds, s 1 P A. LpA s 1 Ñs q X paths G pS´q " H do

5:

A :" A s 1 Ñs 6: if @ν P S`. LpAq X paths G pνq ‰ H then 7:

return query q represented by the DFA A 8: return null

We illustrate the algorithm on the graph G0 in Figure 3 with a sample S s.t. S`" tν1, ν3u and S´" tν2, ν7u. For ease of exposition, we assume a fixed k " 3 (we explain how to obtain the value of k theoretically in Section 3.3 and empirically in Section 5). At first (lines 1-2), the algorithm constructs the set P of SCPs bounded by k for the positive nodes from which these paths in P can be constructed. Note that by Σ ďk we denote the set of all paths of length at most k. For instance, on our example in Figure 3, we obtain P " tabc, cu. Then (line 3), we construct the PTA (prefix tree acceptor ) [START_REF] De La Higuera | Grammatical Inference: Learning Automata and Grammars[END_REF] of P , which is basically a tree-like DFA accepting only the paths in P and having as states all their prefixes. Figure 6(a) illustrates the obtained PTA A for our example. Then (lines 4-5), we generalize A by merging two of its states if the obtained DFA selects no negative node. Note that by A s 1 Ñs we denote the DFA obtained from A by modifying each occurrence of the state s 1 in s. Recall that on our example we have P " tabc, cu and the PTA A in Figure 6(a). Next, we try to merge states of A: the states ε and a cannot be merged (because the obtained DFA would select the path bc that is covered by the negative ν2), the states ε and c cannot be merged (because the path ε is covered by both negatives), while the states ε and ab can be merged without covering any negative example. On our example, we obtain the DFA in Figure 6(b), where no further states can be merged. Finally, the algorithm checks whether the query represented by A selects all the positive examples (not only those from whose SCPs we have constructed A), and if this is the case, it outputs the query (lines 6-7). In our case, the obtained pa ¨bq ˚¨c selects all positive nodes hence is returned.

Learnability results

Recall that in Section 3.1 we have formally defined what means for a class of queries to be learnable while in Section 3.2 we have proposed a learning algorithm for pq. In this section, we prove that the proposed algorithm satisfies the conditions of Definition 3.4, thus showing the main theoretical result of the paper. We conclude the section with practical observations related to our learnability result.

By pq ďn we denote the pq of size at most n.

Theorem 3.5 The query class pq ďn is learnable with abstain in polynomial time and data, using the algorithm learner with the parameter k set to 2 ˆn `1.

Proof. First, we point out that learner works in polynomial time in the size of the input. Indeed, the number of paths to explore for each positive node (lines 1-2) is polynomial since the length of paths is bounded by a fixed k. Then, both testing the consistency of queries considered during the generalization (lines 3-5) and testing whether the computed query selects all positive nodes (lines 6-7) reduce to deciding the emptiness of the intersection of two NFAs, known as being in PTIME [START_REF] Lange | The emptiness problem for intersections of regular languages[END_REF]. Moreover, learner is sound with abstain since it returns either a query consistent with the input sample if it is possible to construct it using SCPs of length bounded by k, or null otherwise.

As for the completeness of learner , we show, for every q P pq, the construction of a graph G and of a characteristic sample CS on G with the properties from Definition 3.4 i.e., for every sample S that extends CS consistently with q (i.e., CS Ď S and q is consistent with S), the algorithm learner pG, Sq returns q. The idea behind the construction is the following: we know that RPNI [START_REF] Oncina | Inferring regular languages in polynomial update time[END_REF] is an algorithm that takes as input positive and negative word examples and outputs a DFA describing a consistent regular language, and moreover, the core of RPNI is based on DFA generalization via state merges similarly to learner ; hence, for a query q, we want a graph and a sample on it s.t. when learner selects the SCPs, it should get exactly the words that RPNI needs for learning q if we see it as a regular language. Then, since RPNI is guaranteed to learn the goal regular language from these words, we infer that if learner selects and generalizes the SCPs corresponding to them, then learner is also guaranteed to learn the goal pq.

We exemplify the construction on the query q " pa ¨bq ˚¨c. First, given q, we construct two sets of words P`and P´t hat correspond to a characteristic sample used by RPNI to infer the regular language of q. In our case, we obtain P`" tc, abcu and P´" tε, a, ab, ac, bcu. Then, the characteristic graph for learning the graph query q needs (i) for each p P P`, a node ν P CS `s.t. p " minďpLpqq X paths G pνqq, (ii) for each p P P´, a node ν P CS ´s.t. p P paths G pνq, and (iii) for each p 1 that is smaller (w.r.t. the canonical order ď) than a word p P P`and is not prefixed by any word in Lpqq, a node ν P CS ´s.t. p 1 P paths G pνq. For our query pa ¨bq ˚c, (i) implies two positive nodes: a node ν s.t. c P paths G pνq and another node ν 1 s.t. abc P paths G pν 1 q and c R paths G pν 1 q, while (ii) and (iii) imply a node ν 2 s.t. ν 2 R qpGq and tε, a, ab, ac, bcu Ď paths G pν 2 q (cf. ii) and tε, a, b, aa, ab, ac, ba, bb, bc, aaa, aab, aac, aba, abbu Ď paths G pν 2 q (cf. iii). In Figure 7 we illustrate such a graph and we highlight the two positive and one negative node examples. Recall that the size of a query is the number of states of its canonical DFA. According to the above construction, we need |CS `| " |P`| and |CS ´| " 1. Since |P`| is polynomial in the size of the query [START_REF] Oncina | Inferring regular languages in polynomial update time[END_REF], we infer that |CS | is also polynomial in the size of the query. Moreover, to learn the regular language of a query of size n, the longest path in P`is of size 2 ˆn `1 [START_REF] Oncina | Inferring regular languages in polynomial update time[END_REF]. Hence, to be able to select this path with learner (assuming the presence of a characteristic sample), we need the parameter k of learner to be at least 2 ˆn `1. Thus, for each possible size n of the goal query there exists a polynomial learning algorithm satisfying the conditions of Definition 3.4, which concludes the proof.

We end this section with some practical observations related to our learnability result.

First, we point out that although Theorem 3.5 requires a certain theoretical value for k to guarantee learnability of queries of a certain size, our experiments indicate that small values of k (between 2 and 4) are enough to cover most practical cases. Then, even though the definition of learnability requires that one characteristic sample exists, in practice there may be many of such samples and there exists an infinite number of graphs on which we can build them. In fact, a graph that contains a subgraph with a characteristic sample is also characteristic.

Second, we also point out that a practical sample may be characteristic without having all negative paths on the same node as required by the aforementioned construction. For instance, the sample that we have used to illustrate the learning algorithm (i.e., the sample s.t. S`" tν1, ν3u and S´" tν2, ν7u on the graph in Figure 3) is characteristic for pa ¨bq ˚¨c and all above mentioned negatives paths are covered by two negative nodes. Third, if a graph does not own a characteristic sample, the user's goal query on that graph cannot be exactly identified. In such a case, the learning algorithm returns a query equivalent to the goal query on the graph and hence indistinguishable by the user (i.e., they select exactly the same set of nodes). For instance, take the graph in Figure 8 and assume a user labeling the nodes w.r.t. the goal pa ¨bq ˚¨c. The learning algorithm returns the query a that selects exactly the same set of nodes on this graph.

Fourth, the presented learning techniques are directly applicable to different query semantics such as binary and nary queries. We give here only the intuition behind these applications and we point out that more details about the corresponding algorithms can be found in the appendix of our technical report [START_REF] Bonifati | Learning path queries on graph databases[END_REF]. To learn a binary query, the only change to Algorithm 1 is that each positive example implies a smaller number of candidate paths from which we have to choose a consistent one (since the destination node is also known). Then, for the n-ary case (i.e., when an example is a tuple of nodes labeled with `or ´), we have simply to apply the previous algorithm to learn a query for each position in the tuple and then to combine those.

LEARNING FROM INTERACTIONS

In this section, we investigate the problem of query learning from a different perspective. In Section 3 we have studied the setting of a fixed set of examples provided by the user and no interaction with her during the learning process. In this section, we consider an interactive scenario where the learning algorithm with an empty sample and continuously interacts with the user and asks her to label additional nodes until she is satisfied with the output of the learned query. To this purpose, we first propose the interactive scenario (Section 4.1). Then, we discuss different parameters for it, in particular what means for a node to be informative and what is a practical strategy of proposing nodes to the user (Section 4.2). We also point out that we have employed the aforementioned interactive scenario as the core of a system for interactive path query specification on graphs [START_REF] Bonifati | Interactive path query specification on graph databases[END_REF].

Interactive scenario

We consider the following interactive scenario. The user is presented with a node of the graph and indicates whether the node is selected or not by the query that she has in mind. We repeat this process until a sufficient knowledge of the goal query has been accumulated (i.e., there exists at most one query consistent with the user's labels). This scenario is inspired by the well-known framework of learning with membership queries [START_REF] Angluin | Queries and concept learning[END_REF] and we have recently formalized it as a general paradigm for learning queries on big data [START_REF] Bonifati | A paradigm for learning queries on big data[END_REF]. In Figure 9, we describe the current instantiation for path queries on graphs and we detail next its different steps.

1 2 We consider as input a graph database G. Initially, we assume an empty sample that we enrich via simple interactions with the user. The interactions continue until Output: learned query.

Get neighborhood for ν.

Ask label for ν.

No Yes visualize label ν with + or -learn a query from all labels propagate label for ν a halt condition is satisfied. A natural halt condition is to stop the interactions when there is exactly one consistent query with the current sample. In practice, we can imagine weaker conditions e.g., the user may stop the process earlier if she is satisfied by some candidate query proposed at some intermediary stage during the interactions.

3 We propose nodes of the graph to the user according to a strategy Υ i.e., a function that takes as input a graph G and a sample S, and returns a node from G. Since our goal is to minimize the amount of effort needed to learn the user's goal query, a smart strategy should avoid proposing to the user nodes that do not bring any information to the learning process. The study of such strategies yields to defining the notion of informative nodes that we formalize in the next section.

4 A node by itself does not carry enough information to allow the user to understand whether it is part of the query result or not. Therefore, we have to enhance the information of a node by zooming out on its neighborhood before actually showing it to the user. This step has the goal of producing a small, easy to visualize fragment of the initial graph, which permits the user to label the proposed node as a positive or a negative example. More concretely, in a practical scenario, all nodes situated at a distance k (as the parameter of Algorithm 1 explained in Section 3.2) should be sufficient for the user to decide whether she wants or not the proposed node. In any case, the user has neither to visualize all the graph that can be potentially large, nor to look by herself for interesting nodes because our interactive scenario proposes such nodes to the user. 5 6 The user visualizes the neighborhood of a given node ν and labels ν w.r.t. the goal query that she has in mind. Then, we propagate the given label in the rest of the graph and prune the nodes that become uninformative. Moreover, we run the learning algorithm learner (i.e., Algorithm 1 from Section 3.2), which outputs in polynomial time either a query consistent with all labels provided by the user, or null if such a query does not exist or cannot be constructed efficiently. When the halt condition is satisfied, we return the latest output of learner to the user. In particular, the halt condition may take into account such an intermediary learned query q e.g., when the user is satisfied by the output of q on the instance and wants to stop the interactions.

In the next section, we precisely describe what means for a node to be informative for the learning process and what is a practical strategy of proposing nodes to the user.

Informative nodes and practical strategies

Before explaining the informative nodes, we first define the set of all queries consistent with a sample S over a graph G: CpG, Sq " tq P pq | S`Ď qpGq ^S´X qpGq " Hu.

Assuming that the user labels the nodes consistently with some goal query q, the set CpG, Sq always contains q. Initially, S " H and CpG, Sq " pq. Therefore, an ideal strategy of presenting nodes to the user is able to get us quickly from S " H to a sample S s.t. CpG, Sq " tqu. In particular, a good strategy should not propose to the user the certain nodes i.e., nodes not yielding new information when labeled by the user. Formally, given a graph G, a sample S, and an unlabeled node ν P G, we say that ν is certain (w.r.t. S) if it belongs to one of the following sets: Cert`pG, Sq " tν P G | @q P CpG, Sq. ν P qpGqu, Cert´pG, Sq " tν P G | @q P CpG, Sq. ν R qpGqu.

In other words, a node is certain with a label α if labeling it explicitly with α does not eliminate any query from CpG, Sq. For instance, take the graph in Figure 10 with a positive, a negative, and an unlabeled node, which belongs to Certb ecause it is selected by the unique (prefix-free) query in CpG, Sq (i.e., b). Additionally, we observe that labeling it otherwise (i.e., with a -) leads to an inconsistent sample. The notion of certain nodes is inspired by possible world semantics and certain answers [START_REF] Imielinski | Incomplete information in relational databases[END_REF], and already employed for XML querying for non-expert users [START_REF] Cohen | Certain and possible XPath answers[END_REF] and for the inference of relational joins [START_REF] Bonifati | Interactive inference of join queries[END_REF]. Next, we give necessary and sufficient conditions for a node to be certain, for both positive and negative labels: Lemma 4.1 Given a sample S and a node ν from G:

1. ν P Cert`pG, Sq iff there exists

ν 1 P S`s.t. paths G pν 1 q Ď paths G pS´q Y paths G pνq, 2. ν P Cert´pG, Sq iff paths G pνq Ď paths G pS´q.
Additionally, given a graph G, a sample S, and a node ν, we say that ν is informative (w.r.t. S) if ν has not been labeled by the user nor it is certain. Unfortunately, by using the characterization from Lemma 4.1, we derive the following. Lemma 4.2 Given a graph G and a sample S, deciding whether a node ν is informative is PSPACE-complete.

An intelligent strategy should propose to the user only informative nodes. Since deciding the informativeness of a node is intractable (cf. Lemma 4.2), we need to explore practical strategies that efficiently compute the next node to label. Consequently, we propose two simple but effective strategies that we detail next and that we have evaluated experimentally. The basic idea behind them is to avoid the intractability of deciding informativeness of a node by looking only at a small number of paths of that node. More precisely, we say that a node is k-informative if it has at least one path of length at most k that is not covered by a negative example. If a node is k-informative, then it is also informative, otherwise we are not able to establish its informativeness w.r.t. the current k. Then, strategy kR consists of taking randomly a k-informative node while strategy kS consists of taking the k-informative node having the smallest number of non-covered k-paths, thus favoring the nodes for which computing the SCPs is easier. In the next section, we discuss the performance of these strategies as well as how we set the k in practice.

EXPERIMENTS

In this section, we present an experimental study devoted to gauge the performance of our learning algorithms. In Section 5.1, we introduce the used datasets: the AliBaba biological graph and randomly generated synthetic graphs. In Section 5.2 and Section 5.3, we present the results for the two settings under study: static and interactive, respectively. Our algorithms have been implemented in C and our experiments have been run on an Intel Core i7 with 4 ˆ2.9 GHz CPU and 8 GB RAM.

Datasets

Despite the increasing popularity of graph databases, benchmarks allowing to assess the performance of emerging graph database applications are still lacking or under construction [START_REF] Boncz | The linked data benchmark council project[END_REF]. In particular, there is no established benchmark devoted to graph queries defined by regular expressions. Due to this lack, we have adopted a real dataset recently used by [START_REF] Koschmieder | Regular path queries on large graphs[END_REF] to evaluate the performance of optimization algorithms for regular path queries. This dataset, called Al-iBaba [START_REF] Palaga | High-performance information extraction with AliBaba[END_REF], represents a real graph from research on biology, extracted by text mining on PubMed. The dataset has a semantic part consisting of a network of protein-protein interactions and a textual part, reporting text co-occurrence for words. The first part was more appropriate to apply our learning algorithms than the second. Therefore, we have extracted the semantic part from the original graph, thus obtaining a subgraph of about 3k nodes and 8k edges. Similarly, from the set of real-life queries reported in [START_REF] Koschmieder | Regular path queries on large graphs[END_REF], we have retained those that select at least one node on the graph to obtain at least one positive example for learning. Thus, we have used 6 biological queries (denoted by bio1, . . . , bio6), which are structurally complex and have selectivities varying from 1 to a total of 711 nodes i.e., from 0.03% to 22% of the nodes of the graph. We summarize these queries in Table 1. By small letters a, b we denote symbols from the alphabet while by capital letters A, C, E, I we denote disjunctions of symbols from the alphabet i.e., expression of the form a1 `. . . `an. These disjunctions contain up to 10 symbols, with possibly overlapping ones among them.

Additionally, we have implemented a synthetic data generator, which yields graphs of varying size and similar to real-world graphs. The latest feature let us generate scalefree graphs with a Zipfian edge label distribution [START_REF] Koschmieder | Regular path queries on large graphs[END_REF]. We report here the results for generated graphs of size 10k, 20k,

Query Selectivity bio1 b ¨A ¨A˚0 .03% bio2 C ¨C˚¨a ¨A ¨A˚0 .2% bio3 C ¨E 3% bio4 I ¨I ¨I˚1 1% bio5 A ¨A ¨A˚¨I ¨I ¨I˚1 2% bio6 A ¨A ¨A˚2 2% Table 1: Biological queries.
and 30k nodes, and with a number of edges three times larger. Moreover, we focus on synthetic queries that are similar in structure to the aforementioned real-life biological queries. In particular, the three queries that we report here (denoted by syn1, syn2, and syn3) have the structure A ¨B˚¨C , where A, B, and C are disjunctions of up to 10 symbols, with overlapping ones among them. The difference between these three queries is w.r.t. their selectivity: regardless the actual size of the graph, syn1, syn2, and syn3 select 1%, 15%, and 40% of the graph nodes, respectively. Before presenting the experimental results, we say a few words about how we set empirically the parameter k from learner . Since in our experiments we assume that the user labels the nodes of the graph consistently with some goal query, the input sample is always consistent. Hence, there exists a consistent path for each positive node and we dynamically discover the length of the SCPs. In particular, we start with k " 2; if for a given k, the query learned using SCPs shorter that k does not select all positive nodes, we increment k and iterate. For the interactive case, the aforementioned procedure becomes: start with k " 2; seek k-informative nodes (cf. Section 4.2) and increase k when the current k does not yield any k-informative node. In practice, in the majority of cases k " 2 is sufficient and it may reach values up to 4 in some isolated cases.

Static experiments

The setup of static experiments is as follows. Given a graph and a goal query, we take as positive examples some random nodes of the graph that are selected by the query and as negative examples some random nodes that are not selected by it. All these examples are given as input to learner , which returns a consistent query. We consider the learned query as a binary classifier and we measure the F1 score w.r.t. the goal query. Thus, for different percentages of labeled nodes in the graph, we measure the F1 score of the learned query along with the learning time. We present the summary of results in Figure 11 and 12, which show the F1 score and the learning time for the biological (a) and synthetic queries (b, c, d), respectively. Since the positive effect of the generalization in addition to the selection of SCPs is generally of 1% in F1 score, we do not highlight the two steps of the algorithm for the sake of figure readability.

We can observe that, not surprisingly, by increasing the percentage of labeled nodes of the graph, the F1 score also increases (Figure 11). Overall, the F1 score is 1 or sufficiently close to 1 for all queries, except a few cases that we discuss below. The worst behavior is clearly exhibited by query bio5, when we can observe that the F1 score converges to 1 less faster than the others. For this query, we can also observe that the learning time is higher (Figure 12(a)). This is due to the fact that the graph is not characteristic for it (cf. Section 3.3), hence the selection of SCPs yields paths that are not relevant for the target query.

For what concerns the learning time, this remains reasonable (of the order of seconds) for all the queries and for both datasets. The most selective queries (bio4, bio5, bio6) are more problematic since they entail a larger number of positive nodes in the step of selection of the SCPs. As a conclusion, notice that even when the F1 score is very high, these results on the static scenario are not fully beneficial since we need to label at least 7% of the graph nodes to have an F1 score equal to 1. As we later show with the interactive experiments, we can significantly reduce the number of labels needed to reach an F1 score equal to 1.

Finally, the synthetic experiments on various graph sizes and query selectivities confirm the aforementioned observations. In particular, when the queries are more selective (as syn2 and syn3), increasing the number of examples implies more visible changes in the learning time (cf. Figure 12). Additionally, we observe the goal queries with higher selectivity converge faster to a F1 score equal to 1 (cf. Figure 11). Intuitively, this is due to the fact that such cases imply a bigger number of positive examples from which the learning algorithm can benefit to generalize faster the goal query.

Interactive experiments

The setup of interactive experiments is as follows. Given a graph and a goal query, we start with an empty sample and we continuously select a node that we ask the user to label, until the learned query selects exactly the same set of nodes as the goal query or, in other words, until the goal query and the learned query are indistinguishable by the user (cf. Section 3.3). This corresponds to obtaining an F1 score of 1. In this setting, we measure the percentage of the labeled nodes of the graph and the learning time i.e., the time needed to compute the next node to label. In particular, the number of interactions corresponds to the total number of examples, the latter being the sum of the number of positive examples and the number of negative examples. The summary of interactive experiments is presented in Table 2.

We can observe that, differently from the static scenario, labeling around 1% of the nodes of the graph suffices to learn a query with F1 score equal to 1. Even for the most difficult one (bio5), we get a rather significant improvement, as the percentage of interactions is drastically reduced to 7.7% of the nodes in the graph (while in the static case it was 87% of the nodes in the graph). Overall, these numbers prove that the interactive scenario considerably reduces the number of examples needed to infer a query of F1 score equal to 1. The synthetic experiments confirm this behavior for various graph sizes and query selectivities. While learning a query with F1 score equal to 1 corresponds to the strongest halt condition of our interactive scenario (cf. Figure 9), we believe that in practice the user may choose to stop the interactions earlier (and hence label less nodes) if she is satisfied by an intermediate query proposed by the learning algorithm. We consider such halt conditions in our system demo [START_REF] Bonifati | Interactive path query specification on graph databases[END_REF].

Moreover, these experiments also show that the two strategies (kS and kR, cf. Section 4.2) have a similar behavior, even though kS is slightly better (w.r.t. minimizing the number of interactions) for the most selective queries. Intuitively, this happens because such a strategy favors the nodes for which computing the SCPs has a smaller space of solutions (cf. Section 4.2). Finally, we can observe that the two strategies are also efficient, as they lead to a learning time of the order of seconds in all cases.

CONCLUSIONS AND FUTURE WORK

We have studied the problem of learning path queries defined by regular expressions from user examples. We have identified fundamental difficulties of the problem setting, formalized what means for a class of queries to be learnable, and shown that the above class enjoys learnability. Additionally, we have investigated an interactive scenario, analyzed what means for a node to be informative, and proposed practical strategies of presenting examples to the user. Finally, we have shown the effectiveness of the algorithms and the improvements of using an interactive approach through an experimental study on both real and synthetic datasets.

We envision several directions of our work, one of which being to sample a graph and finding informative nodes on representative samples, in the spirit of [START_REF] Leskovec | Sampling from large graphs[END_REF]. Moreover, motivated by the absence of benchmarks devoted to queries defined by regular expressions, we want to develop such a benchmark. This would permit to better analyze the performance of algorithms involving regular expressions on graphs, including the learning algorithms proposed in this paper.

' Let G φ " pV φ , E φ q be the graph that intuitively forces any possible consistent query to end with an s 2 . Formally, V φ " tν φ , u 1 , . . . , u ḱ`1 u and E φ " tpν φ , s 1 , u 1 qu Y tpu í , a ij , u í`1 q | 1 ď i ď k, 1 ď j ď 3u, ' For 1 ď i ď n, if the variable x i appears in both positive and negative literals in clauses of ϕ, construct G i as the graph that intuitively encodes the fact that a variable x i cannot be assigned both the value true and false. If a variable x i appears only in positive or only in negative literals, then such graphs are not of interest. Before defining G i formally, let T i " ta jl | the clause C j has on position l the positive literal x i u and F i " ta jl | the clause C j has on position l the negative literal x i u. Next, let G i " tV i , E i u s.t. V i " tν i1 , . . . , ν i5 u and

E i " tpν i1 , s 1 , ν i2 qu Y tpν i2 , a, ν i2 q | a P Σzts 2 uzT i zF i u Y tpν i5 , a, ν i5 q | a P Σu Y tpν i2 , a, ν i3 q | a P F i u Y tpν i3 , a, ν i3 q | a P Σzts 2 uzT i u Y tpν i3 , a, ν i5 q | a P T i u Y tpν i2 , a, ν i4 q | a P T i u Y tpν i4 , a, ν i4 q | a P Σzts 2 uzF i u Y tpν i4 , a, ν i5 q | a P F i u.
Finally, take the sample Sϕ s.t. Sϕ `" tν φ u and Sϕ ´" tν φ u Y tν i1 | 1 ď i ď n and x i appears in both positive and negative literals in ϕu.

For example, we present in Figure 14 the graph and the sample constructed for the formula ϕ 0 " px 1 _ x 2 _ x 3 q ^p x 1 _ x 3 _ x 4 q. Notice that x 1 is the only variable that appears in both positive and negative literals in ϕ 0 hence we have constructed its corresponding subgraph and labeled the node ν 11 as a negative example. We claim that there exists a query of the form a 1 ¨. . . ¨an (with pairwise distinct symbols) consistent with S iff ϕ P 3SAT.

For the if part, take the valuation v : tx 1 , . . . , xnu Ñ ttrue, falseu that makes ϕ satisfiable. Then, for each clause C i (for 1 ď i ď k) let a il i (with 1 ď l i ď 3) be the label corresponding to a literal satisfied by the valuation v. Take the query q " s 1 ¨a1l 1 ¨. . . ¨akl k ¨s2 . Clearly ν φ P qpGq. Since q encodes a valuation, none of the existing ν i1 (with 1 ď i ď n) is in qpGq. Moreover, since q ends with s 2 , we infer that ν φ R qpGq. We conclude that q is a query consistent with S, and indeed, it has the form of a path with pairwise distinct symbols.

For the only if part, take the query q consistent with S. Since ν φ P qpGq and ν φ R qpGq, we infer that q has the form s 1 ¨a1l 1 ¨. . . äkl k ¨s2 , where each a il i (for 1 ď i ď k) corresponds to a literal from the clause C i . Moreover, since none of the existing ν i1 (with 1 ď i ď n) is in qpGq, we infer that the path w encodes a valuation v : tx 1 , . . . , xnu Ñ ttrue, falseu. Since ν φ P qpGq, we conclude that the valuation v makes ϕ satisfiable.

Note that the described reduction works in polynomial time. Proof. The subset CpG, S Y tpν, `quq Ď CpG, Sq is the set of queries in CpG, Sq that select ν while the subset CpG, S Y tpν, ´quq Ď CpG, Sq is the set of queries in CpG, Sq that do not select ν. Notice that the intersection of the two subsets is empty and their union is CpG, Sq. Lemma 4.1 Given a sample S and a node ν from G: 1. ν P Cert `pG, Sq iff there exists ν 1 P S `s.t. paths G pν 1 q Ď paths G pS ´q Y paths G pνq, 2. ν P Cert ´pG, Sq iff paths G pνq Ď paths G pS ´q.

Proof. From Lemma A.1, we can derive that given a graph G, a consistent sample S over G, and an unlabeled node ν from G, ν is informative iff both S Y tpν, `qu and S Y tpν, ´qu are consistent. Then, we can rewrite this equivalence and obtain a necessary and sufficient condition for a node to be certain i.e., ν is certain iff (i) S Y tpν, `qu is not consistent or (ii) S Y tpν, ´qu is not consistent. From this observation and the characterization of a sample to be consistent (Lemma 3.1) we infer that the two parts of the Lemma are true. Lemma 4.2 Given a graph G and a sample S, deciding whether a node ν is informative is PSPACE-complete.

Proof. The membership of the problem to PSPACE follows from Lemma 4.1 and the known result that deciding the inclusion of NFAs is PSPACE-complete [START_REF] Stockmeyer | Word problems requiring exponential time: Preliminary report[END_REF].

For the PSPACE-hardness, take the same reduction from the proof of Lemma 3.2, the only difference being that the node ν n`2 is unlabeled (i.e., it is no more a positive example). Hence, we have the same graph, the same set of negative examples S

´" tν 1 , . . . , νn, ν n`1 u and an empty set of positive examples S `" H. We claim that the union of the DFAs D 1 , . . . , Dn is not universal iff ν n`2 is informative. From Lemma A.1, we can derive that this is equivalent to saying that the union of the DFAs D 1 , . . . , Dn is not universal iff both S Y tpν n`2 , `qu and S Y tpν n`2 , ´qu are consistent. Notice that S Y tpν n`2 , ´qu is clearly consistent since any query a (where a P Σ) is consistent with it. Thus, we have to prove that S Y tpν n`2 , `qu is consistent iff the union of the DFAs D 1 , . . . , Dn is not universal, which follows exactly as in the proof of Lemma 3.2.

B.

LEARNING ALGORITHMS FOR BINARY AND N -ARY SEMANTICS

In Section 2, we have defined the class of queries that select the nodes having at least one path in the language of a given regular expression. This kind of semantics is usually called monadic since it selects single nodes of the graph. The results shown in the main body of the paper for monadic semantics are directly applicable to the case of binary and n-ary semantics. Here, we present the learning algorithms for binary and n-ary semantics (Algorithm 2 and Algorithm 3, respectively). First, let us introduce some auxiliary notions.

Given a graph G " pV , Eq and two nodes ν, ν 1 from V , by paths 2 G pν, ν 1 q we denote the set of all paths between the nodes ν and ν 1 . Formally, a word w " a 1 . . . an belongs to paths 2 G pν, ν 1 q if there exists a sequence of nodes νν 1 . . . ν n´1 ν 1 such that the triples pν, a 1 , ν 1 q, pν i´1 , a i , ν i q (with 2 ď i ď n ´1), and pν n´1 , an, ν 1 q belong to E. We naturally extend the notion of paths between two nodes to a set of pairs of nodes X Ď V ˆV i.e., paths 2 G pXq " Ť pν,ν 1 qPX paths 2 G pν, ν 1 q. An n-ary path query Q is a sequence of regular expressions pq 1 , . . . , q n´1 q. Given a graph G " pV , Eq and an n-ary path query Q " pq 1 , . . . , q n´1 q, the set of tuples of nodes of G selected by Q, denoted QpGq is as follows.

QpGq " tpν 1 , . . . , νnq | @1 ď i ď n ´1. paths 2 G pν i , ν i`1 q X Lpq i q ‰ Hu. By npq we denote the set of all n-ary path queries. We may refer to them simply as n-ary queries.

When n " 2, we have the particular case of binary semantics. In such a case, a query Q consists of a single regular expression q and selects the pairs of nodes of the graph that are linked via a path in the language of q. An example for learning is now a pair of nodes pν, ν 1 q labeled with `or ´. To learn a binary query, the only change to Algorithm 1 (cf. Section 3.2) is that each positive example implies a smaller set of candidate paths from which we have to choose a consistent one (since the destination node is also known). Algorithm 2 illustrates this idea.

Algorithm 2 Learning algorithm for binary semantics -learner 2 pG, Sq. Input: graph G, sample S Output: query q consistent with S or null Parameter: fixed k P N {{maximal length of a SCP 1: for pν, ν 1 q P S`. Dp P Σ ďk . p P paths 2 G pν, ν 1 qzpaths 2 G pS´q do 2:

P :" P Y tminďppaths 2 G pν, ν 1 qzpaths 2 G pS´qqu 3: let A be the prefix tree acceptor for P 4: while Ds, s 1 P A. LpA s 1 Ñs q X paths 2 G pS´q " H do 5:

A :" A s 1 Ñs 6: if @pν, ν 1 q P S`. LpAq X paths 2 G pν, ν 1 q ‰ H then 7:

return query Q " pqq where q is represented by the DFA A 8: return null For the n-ary case, an example is ppν 1 , . . . , νnq, αq where α P t`, ´u and pν 1 , . . . , νnq is a tuple of nodes of the graph. We have simply to apply the previous algorithm to learn a query for each position in the tuple and then to combine those. Algorithm 3 illustrates this idea.

Let npq ďs be the subset of npq consisting of the n-ary path queries Q s.t. the maximal size of a regular expression in Q is s (recall that the size is the number of states in its canonical DFA). Finally, using Algorithm 3 and the same proof technique as for the learnability of (monadic) path queries (i.e., Theorem 3.5), we can state the following result.

Corollary B.1

The query class npq ďs is learnable with abstain in polynomial time and data, using the algorithm learner n with the parameter k set to 2 ˆs `1.

Algorithm 3 Learning algorithm for n-ary semantics -learner n pG, Sq. Input: graph G, sample S Output: query q consistent with S or null Parameter: fixed k P N {{maximal length of a SCP 1: for i P t1, . . . , n ´1u do 2:

let S i `" tpνi, νi`1q | @pν1, . . . , νnq P S`qu 3:

let S i
´" tpνi, νi`1q | @pν1, . . . , νnq P S´qu let qi " learner 2 pG, S i q 5:

if qi is null then

6:
return null 7: return query Q " pq1, . . . , qn´1q

c 2015 ,Figure 1 :

 20151 Figure 1: A geographical graph database.

Figure 2 :

 2 Figure 2: A set of scientific workflows examples.

Figure 3 :

 3 Figure 3: A graph database G0.

Figure 4 :

 4 Figure 4: Canonical DFA for pa ¨bq ˚c.

Figure 5 :

 5 Figure 5: A graph with an inconsistent sample.

Figure 6 :

 6 Figure 6: DFAs considered by learner for Figure 3.

Figure 7 :

 7 Figure 7: Graph from the proof of Theorem 3.5.

Figure 8 :

 8 Figure 8: A graph and a sample for pa ¨bq ˚¨c.

6

  Input: a graph database G.Is the halt condition satisfied?Choose node ν w.r.t. a strategy Υ.

Figure 9 :

 9 Figure 9: Interactive scenario.

Figure 10 :

 10 Figure 10: Two labeled nodes and a certain node.

  (a) Biological queries. (b) Synthetic query syn1. (c) Synthetic query syn2. (d) Synthetic query syn3.

Figure 11 :

 11 Figure 11: Summary of static experiments -F1 score.

Figure 12 :

 12 Figure 12: Summary of static experiments -Learning time (seconds).

Figure 14 :

 14 Figure 14: Graph and sample constructed for the formula ϕ0 " px1 _ x2 _ x3q ^p x1 _ x3 _ x4q.

Table 2 :

 2 Summary of interactive experiments.

	Dataset	Bio query / Graph size	Labels needed for F1 score = 1 without interactions	Interactive strategy	Labels needed for with interactions F1 score = 1	Time between (seconds) interactions
		bio1	7%	kR kS	0.06% 0.06%	0.19 0.33
		bio2	7%	kR kS	1.78% 3.13%	0.26 0.48
	Biological	bio3	66%	kR kS	1.24% 1.49%	0.34 0.45
	queries	bio4	12%	kR kS	1.32% 0.22%	0.23 0.53
		bio5	87%	kR kS	7.7% 7.39%	3.45 3.79
		bio6	12%	kR kS	1.18% 0.35%	0.24 0.3
		10000	51%	kR kS	0.15% 0.17%	1.33 1.35
	Synthetic query syn1	20000	26%	kR kS	0.07% 0.06%	5.83 5.92
		30000	22%	kR kS	0.04% 0.04%	13.5 13.95
		10000	20%	kR kS	0.38% 0.36%	1.57 1.58
	Synthetic query syn2	20000	11%	kR kS	0.23% 0.22%	6.63 6.78
		30000	8%	kR kS	0.17% 0.16%	15.24 15.38
		10000	5%	kR kS	0.1% 0.1%	1.32 1.32
	Synthetic query syn3	20000	3%	kR kS	0.05% 0.05%	5.66 5.68
		30000	2%	kR kS	0.04% 0.04%	13.15 13.41

Section 4

 4 Given a graph G and a sample S, recall that by CpG, Sq we denote the set of all queries consistent with S. Also recall that CpG, Sq is not empty if the user has labeled the examples in S consistently with some goal query that she has in mind. Moreover, notice that for a consistent sample S and an unlabeled node ν from G, the two possible labels of ν split CpG, Sq in two disjoint sets. Formally, we have the following. Given a graph G, a consistent sample S over G, and an unlabeled node ν from G, it holds that

	Lemma A.1

CpG, Sq " CpG, S Y tpν, `quq Y CpG, S Y tpν, ´quq and CpG, S Y tpν, `quq X CpG, S Y tpν, ´quq " H.

Acknowledgements. We would like to thank the authors of [27] for sharing the AliBaba dataset and to Sarah Cohen-Boulakia for her comments on a draft of the paper.

APPENDIX A. OMITTED PROOFS Section 3

Before presenting the proofs, we first formally define automata. A nondeterministic finite word automaton (NFA) A is a tuple pQ, Σ, δ, I, F q, where Q is a finite set of states, I Ď Q is the set of initial states, F Ď Q is the set of final states, and δ : Q ˆΣ Ñ 2 Q is the transition function. A run of A on a word w " a 1 . . . an is a sequence of states q 0 q 1 . . . qn s.t. q i P δpq i´1 , a i q for 1 ď i ď n and q 0 P I. A run on w is accepting if qn P F . A word w is accepted by A if there is an accepting run of A on w. By LpAq we denote the set of words accepted by A. A deterministic finite word automaton (DFA) A is a NFA pQ, Σ, δ, I, F q s.t. I is a singleton, and δpq, aq is either a singleton or the empty set (for each q P Q and a P Σ).

Lemma 3.1 Given a graph G and a sample S, S is consistent iff for every ν P S `it holds that paths G pνq Ď paths G pS ´q.

Proof. For the if part, for 1 ď i ď |S `|, for ν i in S `, let p i be the path witnessing paths G pν i q Ď paths G pS ´q. Then, the query p 1 `. . . `p|S `| is consistent with S.

The only if part follows directly from the semantics of queries and the definition of consistency. Lemma

3.2

Given a graph G and a sample S, deciding whether S is consistent is PSPACE-complete.

Proof. The membership of the problem to PSPACE follows from Lemma 3.1 and the known result that deciding the inclusion of NFAs is PSPACE-complete [START_REF] Stockmeyer | Word problems requiring exponential time: Preliminary report[END_REF].

Next, we show the PSPACE-hardness by reduction from the universality of the union problem for DFAs, known as PSPACEcomplete [START_REF] Kozen | Lower bounds for natural proof systems[END_REF], and by using a proof technique inspired by [START_REF] Antonopoulos | Definability problems for graph query languages[END_REF]. The reduction works as follows. Take n DFAs D 1 , . . . , Dn over Σ and two fresh symbols s 1 , s 2 which are not in Σ. We construct a graph G as the disjoint union of n `2 graphs over Σ Y ts 1 , s 2 u:

Then, take the sample S s.t. S `" tν n`2 u and S ´" tν 1 , . . . , νn, ν n`1 u. We present in Figure 13 the graph and the sample that we construct by the described reduction. We claim that S is consistent iff the union of the DFAs D 1 , . . . , Dn is not universal i.e.,

For the if part, let w P Σ ˚be the word witnessing the non-universality of the DFAs D 1 , . . . , Dn. Then, take the query q " s 1 ¨w ¨s2 and notice that ν n`2 P qpGq. Since w R LpD i q, we infer that ν i R qpGq (for 1 ď i ď n). Moreover, since w ends with an s 2 and s 2 R Σ, we infer that ν n`1 R qpGq. We conclude that q is a witness of the consistency of S.

For the only if part, the consistency of S implies by Lemma 3.1 that there exists a path p P paths G pν n`2 q s.t. p R paths G pS ´q. Since p P paths G pν n`2 q and p R paths G pν n`1 q, we infer that p is of the form s 1 ¨w ¨s2 , with w P Σ ˚. Since paths G ptν 1 , . . . , νnuq is the set of prefixes of all paths of the form s 1 ¨w1 ¨s2 , where w 1 P LpD 1 q Y . . . Y LpDnq, we infer that w R LpD 1 q Y . . . Y LpDnq, hence w is a witness of the non-universality of the DFAs D 1 , . . . , Dn.

Note that the described reduction works in polynomial time. Lemma

3.3

Given a graph G and a sample S, deciding whether there exists a query of the form a 1 ¨. . . ¨an (pairwise distinct symbols) consistent with S is NP-complete.

Proof. To show the membership of the problem to NP, we point out that a non-deterministic Turing machine guesses a query q of the form a 1 ¨. . . ¨an with pairwise distinct symbols (hence of length bounded by |Σ|) and then checks whether q is consistent with S.

Next, we show the NP-hardness by reduction from 3SAT, known as NP-complete and by using a proof technique inspired by [START_REF] Antonopoulos | Definability problems for graph query languages[END_REF]. The reduction works as follows. Take a 3CNF formula ϕ " C 1 ^. . . ^Ck over the variables x 1 , . . . , xn. Take the alphabet Σ " ts 1 , s 2 , a 11 , a 12 , a 13 , . . . , a k1 , a k2 , a k3 , u. Note that for 1 ď i ď k, the labels a i1 , a i2 , a i3 correspond to the literals from the clause C i on the position 1, 2, and 3, respectively. Next, construct the graph G as the disjoint union of at most n `2 graphs over Σ: