Going Beyond Provenance: Explaining Query Answers with Pattern-based Counterbalances
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.
Miao, Zhengjie
Zeng, Qitian
Glavic, Boris
Roy, Sudeepa
Provenance and intervention-based techniques have been used to explain surprisingly high or low outcomes of aggregation queries. However, such techniques may miss interesting explanations emerging from data that is not in the provenance. For instance, an unusually low number of publications of a prolific researcher in a certain venue and year can be explained by an increased number of publications in another venue in the same year. We present a novel approach for explaining outliers in aggregation queries through counter- balancing. That is, explanations are outliers in the opposite direction of the outlier of interest. Outliers are defined w.r.t. patterns that hold over the data in aggregate. We present efficient methods for mining such aggregate regression pat- terns (ARPs), discuss how to use ARPs to generate and rank explanations, and experimentally demonstrate the efficiency and effectiveness of our approach.
 So for those of you who are here expecting to hear a provenance research, I'm sorry, but this first talk is talking about what provenance cannot do. But yeah, so here we, so our title is Going Beyond Provenance, Explaining Query Answers with Pattern-Based Counterbalances. And I'm Chitian. This is a collaboration between Noitec and Duke University. So a lot of data are being collected today. People query and analyze those data and try to understand them to help their actions. But the problem is understanding data is hard. When you expect to find something, there's always going to be surprising results in here. And so there's a need in database, which is to develop tools that help the users understand those surprising query results. And preferably it should be done in a non-technical way so that all this wide range of user can all benefit from it. And this explaining query result has been done in the past based on the provenance. So a lot of things, there are a lot of things there. There's a semi-range, which is good generalization and causality-based explanations. And also there's provenance systems that compute the provenance by re-inact queries. And also there are some researchers still explaining this surprising results by intervention, which is if you remove a subset of the provenance, your queries all goes to the opposite direction, then that subset is a good explanation for that surprising result. So to summarize, all previous works are based on provenance. So this fact inspired our question, like, do good explanations only come from provenance? And of course our answer is no, non-provenance can be useful. And for those of you who are the teaser, I'm sorry, but I'm going to tell the same joke again. So on the left, it's my advisor Boris, on the right, is myself. And Boris, if Boris is monitoring my work, and he found that suddenly I worked only two hours yesterday, and he asked me why. And if I answer him only based on provenance, my answer can only go as far as, yeah, I worked from like 1911. And he's obviously not going to be happy about that, I can just expect my stipend to be cut low. However, if my answer goes beyond provenance, I told him that I traveled for eight hours to come to SIGMOD, and this answer will be satisfactory to him, and my money will be safe. So yeah, let's look at the real dataset example. So this is a simplified publication dataset. So the schema is author, ID, year, and venue. So a user may use this query here to compute future authors publication per venue per year, and part of the result is shown here. And now the user may see in the middle, this author is KDD publication in 2007 is just one compared to the adjacent years, there are four. So let me ask why. And this forms the question that we're dealing with. So it's why high or why low question, and it's out of an aggregate query. So the provenance-based approach, as I mentioned before, to answer such questions by intervention, if you remove a part of the provenance, you can make the result go through the opposite direction, which means make this author's security 2007 paper go up, then that would be a good explanation. But in this case, it's impossible because removing tuples can never make count go up. Count is only monotone. And our approach is through counterbalance, and just like my low working time can be explained by my high traveling time, an author's low publication number in one venue one year can be explained by his high publication number in another venue or another year. So let's explain in detail. So when a user asks that question, why is this author's publication low? He's making two assumptions. One, is there is a pattern existing in the data that describes the data, and we call that pattern aggregate regression pattern, or ARP for short. And another assumption is the question tuple is a low outlier. So to answer this question, we must first mine all the patterns in the database, and we look for the high outliers that counterbalance the low outlier in the related patterns. And of course, there might be a lot of those counterbalances, not all of them make sense. We need to rank all the results and present top K to the user. And the first part is done offline so that the explanation generation can be done online, interactive with the user question. And this whole thing forms our framework CAPE, which stands for counterbalancing with aggregate pattern for explanation. Now I'm going to explain all those three parts one by one. First, before we talk about mining, we must talk about pattern first. Here an example pattern looks like this. For each author, the total publication is linear over the years. So here we have a set of attributes we call partition attributes. A set of attributes we call predictor attributes. There's an aggregate function and a regression model. So a pattern indicates that if we fix the value of partition attributes, then the predictor attributes can predict the aggregate results over this model. So a pattern can hold locally on the fixed value of prediction attributes. For example, in this case, it holds on author X. Or it can hold globally if it holds for sufficiently many values of partition attributes. In this case, a good number of authors, like those many authors. And after we know the pattern, we can start talking about mining. So even though we do this mining offline, boot force is still not acceptable because a pattern basically divides the attributes into three parts. Prediction attributes, predictor attributes, and the attributes that are not in a pattern. So because it's the three division, it grows exponentially to the number of attributes, which explodes very fast. We must apply some optimizations to it. The first one is restricting size. We only allow maximum four attributes in the pattern. And this alone will reduce the number of candidate patterns to polynomial. And the reason we do this is because patterns tend to appear when we generalize. So when there are too many attributes, it becomes too fine grained. And fine grained patterns tend to be not understandable and sometimes not even real patterns. You might wonder why after I fixed so many values, suddenly A can predict B. So it's not understandable. And we can reuse sort order because to mine patterns, for example, to mine patterns, that's out of an aggregate query with group ABCD, we need to sort on the partition attributes. And here, if we have a group ABCD and it's sorted on ABC, then it's also sorted on AB, also sorted on A. So in this way, we can mine all the patterns like this listed in there with one sort order. And further, we can detect and apply functional dependencies. And for example, it's here, if this pattern holds for each author, for each A, then C can predict the aggregate function over linear model. And A implies B as a functional dependency, then the following pattern for each A and B, this aggregate function is linear, obviously, holds trivially. And functional dependencies can either be given as input or we can detect them as we mine them. So here are some examples, are just some examples of our experiments that are down to compare all those, like compare all the time after we apply those optimizations. We see here, the naive one explodes very fast. And the blue line is we compare across mining pattern and the data cube. And the data cube works very well when there are not so many attributes, but it starts as the number of attributes gets more, it starts waste a lot of time on querying because we don't need a lot of the fine grained aggregate results. And the plot on the right hand side, we compared the width without functional dependency. We chose eight attributes out of the Chicago crime data where there's a lot of functional dependencies within it, like, because a lot of attributes are geographical. And we know there are at least three functional dependencies and the results shows in the right there's a list about a 20% speed improvement. And that's as much technical detail we're going to talk about in this presentation because the idea which is coming is cooler in this paper. So, yeah, in order to find counterbalance, the first thing we need is a relevant pattern which forms the basis of our counterbalance because not just all patterns are relevant for a question. For example, in this case, if we have a pattern that sounds some other author, it's not going to help us answer the question of this author. So, the first condition for a pattern to be relevant, it needs to hold on this question, which means it needs to hold on the partition attributes must come out of this user question tuple. So, for the pattern for each author and venue, the total publication is constant over the years. It's only relevant if it holds on author X and KDD. And of course, of course, it does hold in this case, but the problem is in this case we fixed author X and KDD, the only variable here is the year. So, it means we can only look for counterbalances in other years. And you can see here the adjacent years are not so much of an outlier. So, in order to find counterbalances in other conferences, we need to allow our relevant pattern to be more generalized. So, that's the second condition. As long as it's generalized, the user question. So, here's an example. For each author, the total publication is linear over the years. So, here we see author and year are the attributes in this pattern. And it's a subset of author, year and venue. So, this way we say generalized user question. And of course, it still needs to hold on author X. And if it holds, and here only author X is fixed, and it leaves room for us to find counterbalance in other conferences. But how do we do that? Because this pattern doesn't have conference itself. Like, in order to find counterbalances in other conferences, we need to refine this pattern. That leads us to this refinement. Like, for the pattern before, for author X, the total publication is linear over the years. We can refine it by adding more partition attributes. And also, at the same time, we allow the model type to change. It doesn't have to. But all we need is there to be a model. And in this case, as long as it holds, for author X and ICD, the total publication is constant over the years, we can start looking for counterbalancing points on this pattern. And we need to point out that in this example, it happens that we refine back to the same attributes as the user question, author, venue and year. But it doesn't have to be. Because this is a very simple example. There's only these three attributes. But if there are more attributes, like publication type, either research paper or demo paper, then we can add those things too. And if that pattern holds, it can provide the user with even more information. So, yeah, as it turned out, this pattern can hold. So the only thing we need to look for is a high outlier, which is this year's publication, the six at ICD. So the counterbalances, his low publication at one at KDD. So we see the explanation returned by Cape for this question. It contains this author's number of publications in other venues or other years. For example, it also contains his ICD publication in 2006, his VLDV publication in 2007. And it doesn't have to be the same schema as the user question. So, for example, this one. But you probably already see that not all counterbalances are good. We need to score them and return top ones. And the scoring is first based on the distance between the user question top one and explanation top one. Here, for example, for the user question author at KDD, 2007, one, to answer this question, 2007 would be better than 2006. And ICD would be better than some conferencing other area, like sitcom, which is in network. And the other part is based on the deviation of explanation top one from its expected value. Because we believe that higher deviation means more unusual. And more unusual events are more likely to cause other unusual events. Like the example here, why we don't just directly find counterbalancing his KDD publication? Because in the adjacent years, there are not so many of those publications and not so much of an outlier. However, in ICD, we can see in 2007, his publication is a lot higher than his expected value. So this would be a good counterbalance. So to convince you that our system actually does generate good explanations, we provide one more example here. This is based on Chicago. This is a simplified version of the Chicago crime data, which Illinois Tech is in. And it's simplified, of course, as the crime type, the community area, the crime is in, and the year, then the crime happened. And the user may wonder, why is the battery crime in 2011 at this community area 26 low, which is only 16? And I'm going to go through the top explanations generated by our system one by one. The first one is more generalized explanation. It says the total publication number in the, not publication, crime number in this area in the year after is high, which indicates that maybe 2011 is just the year that the criminals are hibernating, or maybe it's a year, it's a police intensive year. And the next one shows this year, the battery type of crime in the adjacent community is higher than expected, which indicates that maybe the criminals are slowly migrating. And the next one shows the battery crime in the previous year as a total in Chicago is high, which is probably why the police department's been put more police power the next year. And the last one, we see that the similar type of crime assault on that year in this area is high. And we know the difference between battery and assault is battery is when some act harm is actually being done, but assault is when someone's threatened that I'm going to harm you. So by a lot of batteries changing into assaults, that means the police are actually working that year. So you see each of the explanation helpful gives you a little more information. And they as a whole give you the whole picture that maybe because the previous year the crime is too much, the Chicago police department decided to put more police power. And then on the year, the criminals had to migrate to the adjacent neighborhood where maybe police patrol is not an intensive. And maybe the police department is out of money or the criminals get to test gets to desperate. They just came back worse the year after. So here comes our conclusion or more of a summarization. So providence can be insufficient and explaining surprising career results. And the reasonable explanations can be given by counterbalance. Here what we did with my patterns offline and we look for counterbalance and rank called counterbalances online and presented the hub ones to the users to help them understand and the unexpected results. And in the future, we would like to extend to larger classroom queries, for example, to support joins. And yeah, that's it for today. And here's a link for GitHub and also we'll have a demo for cave at the VLDB this year. You're welcome to come.
 So for those of you who are here expecting to hear a provenance research, I'm sorry,  but this first talk is talking about what provenance cannot do.  But yeah, so here we, so our title is Going Beyond Provenance,  Explaining Query Answers with Pattern-Based Counterbalances.  And I'm Chitian. This is a collaboration between Noitec and Duke University.  So a lot of data are being collected today. People query and analyze those data and try to  understand them to help their actions. But the problem is understanding data is hard.  When you expect to find something, there's always going to be surprising results in here.  And so there's a need in database, which is to develop tools that help the users  understand those surprising query results. And preferably it should be done in a non-technical  way so that all this wide range of user can all benefit from it.  And this explaining query result has been done in the past based on the provenance.  So a lot of things, there are a lot of things there. There's a semi-range,  which is good generalization and causality-based explanations. And also there's provenance systems  that compute the provenance by re-inact queries. And also there are some researchers  still explaining this surprising results by intervention, which is if you remove a subset  of the provenance, your queries all goes to the opposite direction, then that subset is a good  explanation for that surprising result. So to summarize, all previous works are based on  provenance. So this fact inspired our question, like, do good explanations only come from provenance?  And of course our answer is no, non-provenance can be useful. And for those of you who are the  teaser, I'm sorry, but I'm going to tell the same joke again. So on the left, it's my advisor Boris,  on the right, is myself. And Boris, if Boris is monitoring my work, and he found that suddenly  I worked only two hours yesterday, and he asked me why. And if I answer him only based on provenance,  my answer can only go as far as, yeah, I worked from like 1911. And he's obviously not going to  be happy about that, I can just expect my stipend to be cut low. However, if my answer goes beyond  provenance, I told him that I traveled for eight hours to come to SIGMOD, and this answer  will be satisfactory to him, and my money will be safe. So yeah, let's look at the real dataset  example. So this is a simplified publication dataset. So the schema is author, ID, year, and  venue. So a user may use this query here to compute future authors publication per venue per year,  and part of the result is shown here. And now the user may see in the middle, this author is KDD  publication in 2007 is just one compared to the adjacent years, there are four. So let me ask why.  And this forms the question that we're dealing with. So it's why high or why low question,  and it's out of an aggregate query. So the provenance-based approach, as I mentioned before,  to answer such questions by intervention, if you remove a part of the provenance,  you can make the result go through the opposite direction, which means make this author's  security 2007 paper go up, then that would be a good explanation. But in this case, it's impossible  because removing tuples can never make count go up. Count is only monotone.  And our approach is through counterbalance, and just like my low working time can be explained  by my high traveling time, an author's low publication number in one venue one year can  be explained by his high publication number in another venue or another year. So let's explain  in detail. So when a user asks that question, why is this author's publication low? He's making two  assumptions. One, is there is a pattern existing in the data that describes the data, and we call  that pattern aggregate regression pattern, or ARP for short. And another assumption is the  question tuple is a low outlier. So to answer this question, we must first mine all the patterns  in the database, and we look for the high outliers that counterbalance the low outlier  in the related patterns. And of course, there might be a lot of those counterbalances, not all of  them make sense. We need to rank all the results and present top K to the user. And the first part  is done offline so that the explanation generation can be done online, interactive with the user  question. And this whole thing forms our framework CAPE, which stands for counterbalancing with  aggregate pattern for explanation. Now I'm going to explain all those three parts one by one.  First, before we talk about mining, we must talk about pattern first. Here an example pattern  looks like this. For each author, the total publication is linear over the years. So here we  have a set of attributes we call partition attributes. A set of attributes we call predictor  attributes. There's an aggregate function and a regression model. So a pattern indicates that  if we fix the value of partition attributes, then the predictor attributes can predict the aggregate  results over this model. So a pattern can hold locally on the fixed value of prediction attributes.  For example, in this case, it holds on author X. Or it can hold globally if it holds for sufficiently  many values of partition attributes. In this case, a good number of authors, like those many authors.  And after we know the pattern, we can start talking about mining. So even though we do this  mining offline, boot force is still not acceptable because a pattern basically divides the attributes  into three parts. Prediction attributes, predictor attributes, and the attributes that are not in a  pattern. So because it's the three division, it grows exponentially to the number of attributes,  which explodes very fast. We must apply some optimizations to it. The first one is restricting  size. We only allow maximum four attributes in the pattern. And this alone will reduce the number  of candidate patterns to polynomial. And the reason we do this is because patterns tend to appear  when we generalize. So when there are too many attributes, it becomes too fine grained. And  fine grained patterns tend to be not understandable and sometimes not even real patterns. You might  wonder why after I fixed so many values, suddenly A can predict B. So it's not understandable.  And we can reuse sort order because to mine patterns, for example, to mine patterns,  that's out of an aggregate query with group ABCD, we need to sort on the partition attributes.  And here, if we have a group ABCD and it's sorted on ABC, then it's also sorted on AB,  also sorted on A. So in this way, we can mine all the patterns like this listed in there with one  sort order. And further, we can detect and apply functional dependencies. And for example,  it's here, if this pattern holds for each author, for each A, then C can predict the  aggregate function over linear model. And A implies B as a functional dependency,  then the following pattern for each A and B, this aggregate function is linear,  obviously, holds trivially. And functional dependencies can either be given as input  or we can detect them as we mine them. So here are some examples, are just some examples of our  experiments that are down to compare all those, like compare all the time after we apply those  optimizations. We see here, the naive one explodes very fast. And the blue line is we compare  across mining pattern and the data cube. And the data cube works very well when there are not so  many attributes, but it starts as the number of attributes gets more, it starts waste a lot of  time on querying because we don't need a lot of the fine grained aggregate results. And the plot  on the right hand side, we compared the width without functional dependency. We chose eight  attributes out of the Chicago crime data where there's a lot of functional dependencies within  it, like, because a lot of attributes are geographical. And we know there are at least  three functional dependencies and the results shows in the right there's a list about a 20%  speed improvement. And that's as much technical detail we're going to talk about in this presentation  because the idea which is coming is cooler in this paper. So, yeah, in order to find counterbalance,  the first thing we need is a relevant pattern which forms the basis of our counterbalance  because not just all patterns are relevant for a question. For example, in this case,  if we have a pattern that sounds some other author, it's not going to help us answer the  question of this author. So, the first condition for a pattern to be relevant, it needs to hold  on this question, which means it needs to hold on the partition attributes must come out of this  user question tuple. So, for the pattern for each author and venue, the total publication is  constant over the years. It's only relevant if it holds on author X and KDD. And of course,  of course, it does hold in this case, but the problem is in this case we fixed author X and KDD,  the only variable here is the year. So, it means we can only look for counterbalances in other  years. And you can see here the adjacent years are not so much of an outlier. So, in order to  find counterbalances in other conferences, we need to allow our relevant pattern to be more  generalized. So, that's the second condition. As long as it's generalized, the user question.  So, here's an example. For each author, the total publication is linear over the years.  So, here we see author and year are the attributes in this pattern. And it's a subset of author,  year and venue. So, this way we say generalized user question. And of course, it still needs to  hold on author X. And if it holds, and here only author X is fixed, and it leaves room for us to  find counterbalance in other conferences. But how do we do that? Because this pattern doesn't have  conference itself. Like, in order to find counterbalances in other conferences, we need to  refine this pattern. That leads us to this refinement. Like, for the pattern before, for  author X, the total publication is linear over the years. We can refine it by adding more partition  attributes. And also, at the same time, we allow the model type to change. It doesn't have to. But  all we need is there to be a model. And in this case, as long as it holds, for author X and ICD,  the total publication is constant over the years, we can start looking for counterbalancing points  on this pattern. And we need to point out that in this example, it happens that we refine back  to the same attributes as the user question, author, venue and year. But it doesn't have to be.  Because this is a very simple example. There's only these three attributes. But if there are more  attributes, like publication type, either research paper or demo paper, then we can add those things  too. And if that pattern holds, it can provide the user with even more information. So, yeah, as it  turned out, this pattern can hold. So the only thing we need to look for is a high outlier,  which is this year's publication, the six at ICD. So the counterbalances, his low publication at one  at KDD. So we see the explanation returned by Cape for this question.  It contains this author's number of publications in other venues or other years. For example,  it also contains his ICD publication in 2006, his VLDV publication in 2007. And it doesn't have to  be the same schema as the user question. So, for example, this one. But you probably already  see that not all counterbalances are good. We need to score them and return top ones. And the scoring  is first based on the distance between the user question top one and explanation top one. Here,  for example, for the user question author at KDD, 2007, one, to answer this question, 2007 would  be better than 2006. And ICD would be better than some conferencing other area, like sitcom, which  is in network. And the other part is based on the deviation of explanation top one from its  expected value. Because we believe that higher deviation means more unusual. And more unusual  events are more likely to cause other unusual events. Like the example here, why we don't just  directly find counterbalancing his KDD publication? Because in the adjacent years, there are not so  many of those publications and not so much of an outlier. However, in ICD, we can see in 2007,  his publication is a lot higher than his expected value. So this would be a good counterbalance.  So to convince you that our system actually does generate good explanations, we provide one more  example here. This is based on Chicago. This is a simplified version of the Chicago crime data,  which Illinois Tech is in. And it's simplified, of course, as the crime type, the community area,  the crime is in, and the year, then the crime happened. And the user may wonder, why is the  battery crime in 2011 at this community area 26 low, which is only 16? And I'm going to go through  the top explanations generated by our system one by one. The first one is more generalized  explanation. It says the total publication number in the, not publication, crime number in this area  in the year after is high, which indicates that maybe 2011 is just the year that the criminals  are hibernating, or maybe it's a year, it's a police intensive year. And the next one shows this year,  the battery type of crime in the adjacent community is higher than expected, which indicates that  maybe the criminals are slowly migrating. And the next one shows the battery crime in the previous  year as a total in Chicago is high, which is probably why the police department's been put  more police power the next year. And the last one, we see that the similar type of crime assault  on that year in this area is high. And we know the difference between battery and assault is  battery is when some act harm is actually being done, but assault is when someone's threatened  that I'm going to harm you. So by a lot of batteries changing into assaults, that means  the police are actually working that year. So you see each of the explanation helpful gives you a  little more information. And they as a whole give you the whole picture that maybe because the  previous year the crime is too much, the Chicago police department decided to put more police  power. And then on the year, the criminals had to migrate to the adjacent neighborhood where  maybe police patrol is not an intensive. And maybe the police department is out of money or  the criminals get to test gets to desperate. They just came back worse the year after.  So here comes our conclusion or more of a summarization. So providence can be insufficient  and explaining surprising career results. And the reasonable explanations can be given by  counterbalance. Here what we did with my patterns offline and we look for counterbalance and rank  called counterbalances online and presented the hub ones to the users to help them understand  and the unexpected results. And in the future, we would like to extend to larger  classroom queries, for example, to support joins. And yeah, that's it for today. And here's a link  for GitHub and also we'll have a demo for cave at the VLDB this year. You're welcome to come.
Miao_Zeng_Glavic_Roy_0_143.png Miao_Zeng_Glavic_Roy_144_227.png Miao_Zeng_Glavic_Roy_228_347.png Miao_Zeng_Glavic_Roy_348_623.png Miao_Zeng_Glavic_Roy_624_1619.png Miao_Zeng_Glavic_Roy_1620_2171.png Miao_Zeng_Glavic_Roy_2172_2219.png Miao_Zeng_Glavic_Roy_2220_2363.png Miao_Zeng_Glavic_Roy_2364_2963.png Miao_Zeng_Glavic_Roy_2964_3335.png Miao_Zeng_Glavic_Roy_3336_4439.png Miao_Zeng_Glavic_Roy_4440_5243.png Miao_Zeng_Glavic_Roy_5244_6167.png Miao_Zeng_Glavic_Roy_6168_6587.png Miao_Zeng_Glavic_Roy_6588_8267.png Miao_Zeng_Glavic_Roy_8268_9563.png Miao_Zeng_Glavic_Roy_9564_12035.png Miao_Zeng_Glavic_Roy_12036_14567.png Miao_Zeng_Glavic_Roy_14568_17771.png Miao_Zeng_Glavic_Roy_17772_19931.png Miao_Zeng_Glavic_Roy_19932_22391.png Miao_Zeng_Glavic_Roy_22392_25919.png Miao_Zeng_Glavic_Roy_25920_26687.png Miao_Zeng_Glavic_Roy_26688_26879.png Miao_Zeng_Glavic_Roy_26880_27251.png Miao_Zeng_Glavic_Roy_27252_27364.png