Answering Why-questions by Exemplars in Attributed Graphs
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Namaki, Mohammad Hossein
Song, Qi
Wu, Yinghui
Yang, Shengqi
This paper studies the problem of answering Why-questions for graph pattern queries. Given a query Q, its answers Q(G) in a graph G, and an exemplar E that describes desired answers, it aims to compute a query rewrite Q', such that Q'(G) incorporates relevant entities and excludes irrelevant ones wrt E under a closeness measure. (1) We characterize the problem by Q-Chase. It rewrites Q by applying a sequence of applicable operators guided by E, and backtracks to derive optimal query rewrite. (2) We develop feasible Q-Chase-based algorithms, from anytime solutions to fixed-parameter approximations to compute query rewrites. These algorithms implement Q-Chase by detecting picky operators at run time, which discriminately enforce E to retain answers that are closer to exemplars, and effectively prune both operators and irrelevant matches, by consulting a cache of star patterns (called star views). Using real-world graphs, we experimentally verify the efficiency and effectiveness of qchase techniques and their applications.
 Today I'm going to present our paper answering why questions by exemplars in attributed graphs. So first let's see what is a tribute graph and the subgraph query. So multi-attribute graph is a labeled graph with attributes on the nodes. And the subgraph query is also a labeled subgraph pattern with a focus node UO. So for example, here we see a graph that contains the products from an online store. It contains information regarding cell phones and companies. And we see each node may have a label and also a set of attributes. And we may also have a subgraph query which in this case asks the user wants to find a cell phone. That is a Samsung cell phone packed with color pink and carrier and cheaper than $500. So typically we use subgraph as a morphism to answer this query. And this kind of subgraph query can be used in large extraction, PLI recondition, meto-agnesis, and so on and so forth. So we saw a lot of work trying to do optimization on how to answer these queries faster, such as the second and the third talk on this session. But here we focus on a different problem. We're trying to help users to write queries and to help users to understand the query result. So the challenge here is the multi-attributed graphs could be very huge and complex. So it's very hard for users to write accurate queries. And the users may rewrite the queries multiple times to get the desired answer. So for example, giving this query and its answer, in this case, is Samsung A5 and S6, the users may ask two types of questions. The first one is why some unexpected entities are in the query answer. In this case, the user don't want to see some entities, but it's in the query answer. The second question is why certain entities are missing from the query result. In this case, the user want to see some entity when he uses the query, but the entity is not in the answer. So in this case, there's something wrong with the query. And we write some queries for, it's a little bit hard for user, but it's easier for user to provide some examples. So the example here are a set of user-specified entities, or it could be a set of circle statements to categorize the answers. So for example, the user may say, OK, I want to see some cell phones which are similar to S9, but S9 is not in the query result. So based on this S9, the example, we derived a set of relevant entities. So in this case, S6 is pretty similar to S9. So the relevant entity set is S6 and S9, and the irrelevant entity set is A5. So giving this example, we want to return query, to answer these two types of why questions, we want to return a query write that returns exactly the relevant entities as the answer. So in this case, we can modify the original query by applying some query operators. For example, we can remove some literals. We can add some literals or remove edges. And we can generate a query rewrite Q prime in this case, and it indeed returns the matches S6 and S9, which is the user want to see. And the operators here can also be used to explain why some entities are missing and why some unexpected entities are in the query result. So in this paper, we study the problem of graph exploratory search guided by examples, giving a query and answer, its answer, and a set of examples. We generate, we suggest query rewrite, and we return this query write to users. So this is kind of an interactive process. And our major contribution is we formalize this problem as an optimization problem, and we propose a Q-Chase as a new symbolic formalization to characterize this process. And we propose a set of algorithms with performance guarantees, and finally, we develop a demo system called navigate. So before, so let's first look at the problem formulation. So we formulate why question as a table here. So Q-UO is the query, and UO is the output node. And the examples, as I said, it could be a set of user-specified entities, or it could be a set of conjunction of conditions along with a table that contains all the attributes from the graph. And we call those nodes in V that satisfy the constraints as the representation of this example. And the answer for why question is actually query rewrite. So giving an original query, we have two sets of operators, the refinement operator and relaxation operator. So refinement operator is used to remove those unexpected entities, and relaxation operator is used to involve those entities missing. So we can remove literal, remove age, relax literal, and we can also add literal, age, or refine the literal. And also for some special matching semantic, for example, P-homomorphism, we can also relax or refine the edge bound. And each operator here, along with graph editing cost. So how to measure if query write is good or not? We define the answer closeness here. So the green cycle is actually the original query answer, and the yellow cycle is the representation of the example. So we have the relevant matches, and we have the relevant candidates. So our goal is to include these relevant candidates into the query result and remove those irrelevant matches from the query result. So we define the answer closeness as this formula. So here basically we reward the number of relevant matches, and we penalize the number of irrelevant matches in the answer set. So giving this definition, our problem is we want to find a query rewrite, or equally we want to find a set of operators that maximize the closeness function. But we have a constraint here. We want the cost of all the operators to be smaller or equal to a bound. So the motivation is we don't want to modify the query too much, since if it's a totally different query, it's hard for users to understand. So we have proved that the problem of answering why questions is NP-hard, and also it's hard to approximate. So I'll give an overview of our solutions. So for general why answering why questions, we proposed the exact algorithm with some optimization strategies, and we proposed a faster heuristic algorithm. And for why many questions, which is a special case of why question, it returns a large number of answers. The user want to remove some answers from the result. So we proposed an approximated algorithm for this case with an approximation ratio, and for why empty question is another special case of why question. So it returns empty answer set. So in this case, the user want to see at least some answers. So we proposed an algorithm, which is a P-time algorithm for a special case when we only have star-like queries. So before go to the detail of the algorithm, we first proposed the, we extended the chase to categorize this process. So traditional, the chase process is used to like enforce the value constraints on the relational table. And in this case, different, in contrast to conventional chase, we enforce the value constraints over subgraph queries and their answers instead of the data itself. So we initialize the query process, sorry, we initialize the queue chase with the original query and the examples. And at each chase step, we're going to apply my operator to modify the query to a new query rewrite, and it satisfies at least one constraints in the example E. So this queue chase is terminated when all the constraints in E are certified, which means the user see what he exactly want to see. So the problem now becomes we want to find the optimal terminal sequence that maximizes the answer closeness. So I will introduce the algorithm to, exact algorithm to solve the general wide questions to answer that question. So our idea is to perform best first search strategy with backtracking to simulate queue chase. So the first step is we generate and prioritize a set of PQ operators. And instead of considering all possible operators, here we only consider those operators that are likely to improve the answer closeness. And we call them PQ operators. And then based on these operators, we're going to construct the query rewrite and evaluate them to get the answer closeness. And this process terminates when there's no budget for the operator set or we achieve optimal query rewrite. So for example, here starting from the original query queue with some relevant match and irrelevant match. For example, we first apply O1 and we exclude one irrelevant match. But here we cannot remove any more irrelevant match. So we go back. So with backtracking, we first do relaxation to involve more missing entities. So like we apply O2, O3, and finally we apply O1 to remove irrelevant matches. So this is basically our idea. And we have some optimizations, like we have pruning strategies and we have some star view as index to optimize this process. And this algorithm is actually an anytime algorithms and the delay time to simulate one queue chase state here is this formula. So here BM is the maximum edge bound. This is for the P-homomorphism. I mean for subgraphomorphism, the maximum edge bound is one. And this part is the BM-hom neighbors of the edges in star views. So now let's go to the optimization parts. As I said, we have some estimated upper bound to do pruning, to pruning the search space. And we have a star view as the primitive structure to suggest to PK operators and to also do incremental query evaluation. So we construct star view index by decomposing the original query into a set of stars. So for example, this star query Q1 is a star, it's a star decomposed from the original query. And we also construct star table which contains the edges in the star and some matches. So I mean using star views to do incremental query evaluation is commonly used in query evaluation. And here we also use star views to suggest to PK operators. So for example, giving this table and these relevant matches, if we want to involve p3, p2, p5, we can see we can add a literal carrier domain equals sprint. So this is actually a PK operator. Another operator is we can add carrier domain equals to AT&T. But this one is not a PK operator since it cannot include relevant match. So this is basically the exact algorithm. And we also have a heuristic algorithm which is faster but with no performance guarantee. So now let's go to the experiment setting. So for the datasets, we leverage different kind of datasets from a large graph to moving network to financial dataset. And we also have a synthetic dataset which contains the e-commerce information. So we have the size of these graphs and we also have the number of the attributes per node. So this is an average value. So some nodes may have a large number of attributes. And in order to save the experiment, we construct a set of ground-choose queries by, we find a benchmark queries and we also leverage a query generator to generate a set of queries. And we disturb the query and their answer by injecting some random atomic operators. We kind of do a reverse way to generate the ground-choose. And for the algorithms, as I said, we have our exact algorithm, OSW, and we have its counterparts without those optimization strategies. And we also have a heuristic algorithm and its variance which we randomly select the PK operator instead of we rank them and then select from the top. And we find baseline from Motein, this one is actually not doing the exact same thing, but it constructs the query by my frequent patterns from the user, from the examples. So let's see some experiment results. So the left part is the efficiency. So we can see that our algorithm outperforms the baseline by almost 11 times and without the optimizations and it outperforms the counterparts without the optimization strategies by 3.4 and 2.1 times. So the heuristic algorithm is actually much faster, but from the right-hand side, we can see the relative closeness. So the heuristic one actually cannot return a very good answer. And since this is a bounded optimization problem and we have a budget, so our exact algorithm cannot always achieve the 100% accuracy. And we also have a user study that will ask users to write some queries and give some examples. And after we return the query we write, we ask them to re-rank the top-3 query write from our algorithm. And the NDE-CG top-3 value is 0.7, which indicates that our algorithm achieves good relevance. And finally, we have a case analysis. So this is a very simple query that the first-person I was in turn at the e-commerce company. So this is a real-world query. It's very simple, the users want to find a MacBook powered with NVIDIA GPU, and we know this is a wide-empty question because this query has no answer. So in this case, the user may provide some examples to say, I indeed want a MacBook. Then we are going to return a query write by removing the constraint of the GPU, and this query returns the answer like a set of MacBook computers powered with either Intel or AMD GPU. And we also developed a demo system which user can write queries and give examples and to see how we answer the wide questions by examples. And it's this afternoon in the demonstration, so welcome to play with it. So to conclude in this paper, we started the problem of answering wide questions by examples, we provide several algorithms to solve the problem, and we also developed a demo system, and that's all. Thank you.
 Today I'm going to present our paper answering why questions by exemplars in attributed graphs.  So first let's see what is a tribute graph and the subgraph query.  So multi-attribute graph is a labeled graph with attributes on the nodes.  And the subgraph query is also a labeled subgraph pattern with a focus node UO.  So for example, here we see a graph that contains the products from an online store.  It contains information regarding cell phones and companies.  And we see each node may have a label and also a set of attributes.  And we may also have a subgraph query which in this case asks the user wants to find a cell phone.  That is a Samsung cell phone packed with color pink and carrier and cheaper than $500.  So typically we use subgraph as a morphism to answer this query.  And this kind of subgraph query can be used in large extraction, PLI recondition,  meto-agnesis, and so on and so forth.  So we saw a lot of work trying to do optimization on how to answer these queries faster,  such as the second and the third talk on this session.  But here we focus on a different problem.  We're trying to help users to write queries and to help users to understand the query result.  So the challenge here is the multi-attributed graphs could be very huge and complex.  So it's very hard for users to write accurate queries.  And the users may rewrite the queries multiple times to get the desired answer.  So for example, giving this query and its answer, in this case, is Samsung A5 and S6,  the users may ask two types of questions.  The first one is why some unexpected entities are in the query answer.  In this case, the user don't want to see some entities, but it's in the query answer.  The second question is why certain entities are missing from the query result.  In this case, the user want to see some entity when he uses the query, but the entity is  not in the answer.  So in this case, there's something wrong with the query.  And we write some queries for, it's a little bit hard for user, but it's easier for user  to provide some examples.  So the example here are a set of user-specified entities, or it could be a set of circle statements  to categorize the answers.  So for example, the user may say, OK, I want to see some cell phones which are similar  to S9, but S9 is not in the query result.  So based on this S9, the example, we derived a set of relevant entities.  So in this case, S6 is pretty similar to S9.  So the relevant entity set is S6 and S9, and the irrelevant entity set is A5.  So giving this example, we want to return query, to answer these two types of why questions,  we want to return a query write that returns exactly the relevant entities as the answer.  So in this case, we can modify the original query by applying some query operators.  For example, we can remove some literals.  We can add some literals or remove edges.  And we can generate a query rewrite Q prime in this case, and it indeed returns the matches  S6 and S9, which is the user want to see.  And the operators here can also be used to explain why some entities are missing and  why some unexpected entities are in the query result.  So in this paper, we study the problem of graph exploratory search guided by examples,  giving a query and answer, its answer, and a set of examples.  We generate, we suggest query rewrite, and we return this query write to users.  So this is kind of an interactive process.  And our major contribution is we formalize this problem as an optimization problem, and  we propose a Q-Chase as a new symbolic formalization to characterize this process.  And we propose a set of algorithms with performance guarantees, and finally, we develop a demo  system called navigate.  So before, so let's first look at the problem formulation.  So we formulate why question as a table here.  So Q-UO is the query, and UO is the output node.  And the examples, as I said, it could be a set of user-specified entities, or it could  be a set of conjunction of conditions along with a table that contains all the attributes  from the graph.  And we call those nodes in V that satisfy the constraints as the representation of this  example.  And the answer for why question is actually query rewrite.  So giving an original query, we have two sets of operators, the refinement operator and  relaxation operator.  So refinement operator is used to remove those unexpected entities, and relaxation operator  is used to involve those entities missing.  So we can remove literal, remove age, relax literal, and we can also add literal, age,  or refine the literal.  And also for some special matching semantic, for example, P-homomorphism, we can also relax  or refine the edge bound.  And each operator here, along with graph editing cost.  So how to measure if query write is good or not?  We define the answer closeness here.  So the green cycle is actually the original query answer, and the yellow cycle is the  representation of the example.  So we have the relevant matches, and we have the relevant candidates.  So our goal is to include these relevant candidates into the query result and remove those irrelevant  matches from the query result.  So we define the answer closeness as this formula.  So here basically we reward the number of relevant matches, and we penalize the number  of irrelevant matches in the answer set.  So giving this definition, our problem is we want to find a query rewrite, or equally  we want to find a set of operators that maximize the closeness function.  But we have a constraint here.  We want the cost of all the operators to be smaller or equal to a bound.  So the motivation is we don't want to modify the query too much, since if it's a totally  different query, it's hard for users to understand.  So we have proved that the problem of answering why questions is NP-hard, and also it's hard  to approximate.  So I'll give an overview of our solutions.  So for general why answering why questions, we proposed the exact algorithm with some  optimization strategies, and we proposed a faster heuristic algorithm.  And for why many questions, which is a special case of why question, it returns a large number  of answers.  The user want to remove some answers from the result.  So we proposed an approximated algorithm for this case with an approximation ratio, and  for why empty question is another special case of why question.  So it returns empty answer set.  So in this case, the user want to see at least some answers.  So we proposed an algorithm, which is a P-time algorithm for a special case when we only  have star-like queries.  So before go to the detail of the algorithm, we first proposed the, we extended the chase  to categorize this process.  So traditional, the chase process is used to like enforce the value constraints on the  relational table.  And in this case, different, in contrast to conventional chase, we enforce the value  constraints over subgraph queries and their answers instead of the data itself.  So we initialize the query process, sorry, we initialize the queue chase with the original  query and the examples.  And at each chase step, we're going to apply my operator to modify the query to a new query  rewrite, and it satisfies at least one constraints in the example E.  So this queue chase is terminated when all the constraints in E are certified, which  means the user see what he exactly want to see.  So the problem now becomes we want to find the optimal terminal sequence that maximizes  the answer closeness.  So I will introduce the algorithm to, exact algorithm to solve the general wide questions  to answer that question.  So our idea is to perform best first search strategy with backtracking to simulate queue  chase.  So the first step is we generate and prioritize a set of PQ operators.  And instead of considering all possible operators, here we only consider those operators that  are likely to improve the answer closeness.  And we call them PQ operators.  And then based on these operators, we're going to construct the query rewrite and evaluate  them to get the answer closeness.  And this process terminates when there's no budget for the operator set or we achieve  optimal query rewrite.  So for example, here starting from the original query queue with some relevant match and irrelevant  match.  For example, we first apply O1 and we exclude one irrelevant match.  But here we cannot remove any more irrelevant match.  So we go back.  So with backtracking, we first do relaxation to involve more missing entities.  So like we apply O2, O3, and finally we apply O1 to remove irrelevant matches.  So this is basically our idea.  And we have some optimizations, like we have pruning strategies and we have some star view  as index to optimize this process.  And this algorithm is actually an anytime algorithms and the delay time to simulate one  queue chase state here is this formula.  So here BM is the maximum edge bound.  This is for the P-homomorphism.  I mean for subgraphomorphism, the maximum edge bound is one.  And this part is the BM-hom neighbors of the edges in star views.  So now let's go to the optimization parts.  As I said, we have some estimated upper bound to do pruning, to pruning the search space.  And we have a star view as the primitive structure to suggest to PK operators and to also do  incremental query evaluation.  So we construct star view index by decomposing the original query into a set of stars.  So for example, this star query Q1 is a star, it's a star decomposed from the original  query.  And we also construct star table which contains the edges in the star and some matches.  So I mean using star views to do incremental query evaluation is commonly used in query  evaluation.  And here we also use star views to suggest to PK operators.  So for example, giving this table and these relevant matches, if we want to involve p3,  p2, p5, we can see we can add a literal carrier domain equals sprint.  So this is actually a PK operator.  Another operator is we can add carrier domain equals to AT&T.  But this one is not a PK operator since it cannot include relevant match.  So this is basically the exact algorithm.  And we also have a heuristic algorithm which is faster but with no performance guarantee.  So now let's go to the experiment setting.  So for the datasets, we leverage different kind of datasets from a large graph to moving  network to financial dataset.  And we also have a synthetic dataset which contains the e-commerce information.  So we have the size of these graphs and we also have the number of the attributes per  node.  So this is an average value.  So some nodes may have a large number of attributes.  And in order to save the experiment, we construct a set of ground-choose queries by, we find  a benchmark queries and we also leverage a query generator to generate a set of queries.  And we disturb the query and their answer by injecting some random atomic operators.  We kind of do a reverse way to generate the ground-choose.  And for the algorithms, as I said, we have our exact algorithm, OSW, and we have its  counterparts without those optimization strategies.  And we also have a heuristic algorithm and its variance which we randomly select the  PK operator instead of we rank them and then select from the top.  And we find baseline from Motein, this one is actually not doing the exact same thing,  but it constructs the query by my frequent patterns from the user, from the examples.  So let's see some experiment results.  So the left part is the efficiency.  So we can see that our algorithm outperforms the baseline by almost 11 times and without  the optimizations and it outperforms the counterparts without the optimization strategies by 3.4  and 2.1 times.  So the heuristic algorithm is actually much faster, but from the right-hand side, we can  see the relative closeness.  So the heuristic one actually cannot return a very good answer.  And since this is a bounded optimization problem and we have a budget, so our exact algorithm  cannot always achieve the 100% accuracy.  And we also have a user study that will ask users to write some queries and give some  examples.  And after we return the query we write, we ask them to re-rank the top-3 query write  from our algorithm.  And the NDE-CG top-3 value is 0.7, which indicates that our algorithm achieves good relevance.  And finally, we have a case analysis.  So this is a very simple query that the first-person I was in turn at the e-commerce company.  So this is a real-world query.  It's very simple, the users want to find a MacBook powered with NVIDIA GPU, and we know  this is a wide-empty question because this query has no answer.  So in this case, the user may provide some examples to say, I indeed want a MacBook.  Then we are going to return a query write by removing the constraint of the GPU, and  this query returns the answer like a set of MacBook computers powered with either Intel  or AMD GPU.  And we also developed a demo system which user can write queries and give examples and  to see how we answer the wide questions by examples.  And it's this afternoon in the demonstration, so welcome to play with it.  So to conclude in this paper, we started the problem of answering wide questions by  examples, we provide several algorithms to solve the problem, and we also developed a  demo system, and that's all.  Thank you.
Namaki_Song_Wu_Yang_0_131.png Namaki_Song_Wu_Yang_132_191.png Namaki_Song_Wu_Yang_192_263.png Namaki_Song_Wu_Yang_264_467.png Namaki_Song_Wu_Yang_468_899.png Namaki_Song_Wu_Yang_900_2663.png Namaki_Song_Wu_Yang_2664_3779.png Namaki_Song_Wu_Yang_3780_4775.png Namaki_Song_Wu_Yang_4776_5159.png Namaki_Song_Wu_Yang_5160_5663.png Namaki_Song_Wu_Yang_5664_6755.png Namaki_Song_Wu_Yang_6756_6971.png Namaki_Song_Wu_Yang_6972_7751.png Namaki_Song_Wu_Yang_7752_8939.png Namaki_Song_Wu_Yang_8940_10151.png Namaki_Song_Wu_Yang_10152_12251.png Namaki_Song_Wu_Yang_12252_13991.png Namaki_Song_Wu_Yang_13992_15803.png Namaki_Song_Wu_Yang_15804_17219.png Namaki_Song_Wu_Yang_17220_19667.png Namaki_Song_Wu_Yang_19668_22127.png Namaki_Song_Wu_Yang_22128_24971.png Namaki_Song_Wu_Yang_24972_25643.png Namaki_Song_Wu_Yang_25644_25775.png Namaki_Song_Wu_Yang_25776_25823.png Namaki_Song_Wu_Yang_25824_25979.png