Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together
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.
Han, Myoungji
Kim, Hyunjoon
Gu, Geonmo
Park, Kunsco
Han, Wook-Shin
Subgraph matching (or subgraph isomorphism) is one of the fundamental problems in graph analysis. Extensive research has been done to develop practical solutions for subgraph matching. The state-of-the-art algorithms such as textsfCFL-Match and textsfTurbotextsubscriptiso convert a query graph into a spanning tree for obtaining candidates for each query vertex and obtaining a good matching order with the spanning tree. However, by using the spanning tree instead of the original query graph, it could lead to lower pruning power and a sub-optimal matching order. Another limitation is that they perform redundant computation in search without utilizing the knowledge learned from past computation. In this paper, we introduce three novel concepts to address these inherent limitations: 1) dynamic programming between a directed acyclic graph (DAG) and a graph, 2) adaptive matching order with DAG ordering, and 3) pruning by failing sets, which together lead to a much faster algorithm textsfDAF for subgraph matching. Extensive experiments with real datasets show that textsfDAF outperforms the fastest existing solution by up to orders of magnitude in terms of recursive calls as well as in terms of the elapsed time.
 I'm Hyun-Jun Kim from South National University, and I'll talk about a new efficient sub-grap matching algorithm. And I will briefly show the challenges of sub-grap matching and existing solutions, and briefly introduce the overview of our algorithm and three main techniques using our algorithm. So given a query graph and a data graph, an embedding is a mapping from a query vertex to a data vertex such that for different query vertices, their mappings are different, and for every query vertex, its label should be same as its mappings label. And for every edge U and U prime in a query graph, M U and M U prime should be also in a data graph. And on embedding of an induced sub-grap of a query in a data graph is a partial embedding. So in this figure, we can find a blue sub-grap, a blue embedding of a query graph in a data graph. And for induced sub-grap with U1, U2, and U3, we can find partial embedding U1 to V1, U2 to V3, and U3 to V5. And sub-grap matching is to find all these things embeddings of a query in a data graph, which is an NP-hard problem. So in this example, we should find these two embeddings. And traditionally, existing solutions adopt, use the general framework. First they adopt a filtering process to find a candidate set for each query vertex, where CU is a subset of data vertices which U can be mapped to. In this figure, U1's candidate set can be of V1 and V2. Next choose a linear order of query vertices called matching order and apply backtracking based on the matching order. For in this example, for matching order U1, U2, U3, and U4, we first match U1 to one of the data vertices and match U2 and so on. There are two state-of-the-art algorithms which are table iso proposed in 2013 and CFO match in 2016. Both use the spanning tree of a query graph for a filtering process. So they find potential embeddings of a spanning tree in a data graph. And next, candidate sets computed in the filtering process are stored in an auxiliary data structures. And eventually they find all embeddings of a query graph by checking the entry edges during backtracking. There are some limitations in existing solutions. So since spanning tree does not have all the edges in a query graph, the auxiliary data structures may contain many false positives. So let's say they're considering this query graph in a data graph and there are two routes to leave paths P1 and P2. And there are 50 embeddings of P1 and 100 embeddings of P2 starting from V1 in a data graph. And most of them will not lead to an embedding of a query graph. So to deal with this problem, we suggest a technical dynamic programming between DAG and GRAP. And another important problem is the matching order. So let's say there are 50 embeddings of P1 and 100 embeddings of P2 after the filtering process. Then pass ordering select P1 and then P2 as a matching order. Then backtracking will generate 50 times 100 partial embedding. But if we check edge between U3 and U4 in a query graph earlier during backtracking, we can eliminate most of the partial embeddings. So to handle this problem, we suggest DAG ordering. And some existing work use the global matching order where a pre-computed matching order is used throughout the whole search process. So as opposed to this order, we proposed adaptive matching order. And to reduce redundant computations in such, we propose a printing by Fellingstead, which I'll be showing later. So this is our brief overview of our algorithm. Given a query graph, we first build a rooted DAG. To build a DAG, we first select root to have a large degree and a small number of candidates in a data graph. Next, we traverse a query graph in BFS order and direct all edges from earlier to later visitor vertices. Next, we build a candidate space called CS by using our technique called DAG-Graph-DP or dynamic programming between DAG and GRAP. And after computing this our auxiliary data structure, we find all embeddings of query in CS by applying adaptive matching order and printing by Fellingstead. So CS is a complex search space. Once we compute a CS, we don't need a data graph to search for all embeddings of query graph. So CS on a query and a data graph consists of candidate set and edges. There's a candidate set for every query product you and there's edge between candidates in a between different candidates. If and only if there's an edge in a query graph and corresponding edge is in a data graph. So given a query DAG, we can compute refined candidates set by using a dynamic programming in a reverse topological order in a DAG. So in this figure, we can remove a V8 from U2's candidate set because V8 is not connected to any of the candidate in a U4's candidate set while there's an edge between U2 and U4 in a query graph. And next, we can remove V2 from U1's candidate set accordingly. In this way, we build a compact CS. So starting from this initial CS, we repeat DAG graph dynamic programming with different kinds of query DAGs alternately. So for, we first use this reverse DAG and then we can obtain a refined candidate set. And next, in this time, we use an original query DAG to obtain a further refined candidate set. And next, we also, we use a reverse query DAG once again and we can compute a further refined candidate set. So in this CS structure, we search for embeddings of query graph, but during backtracking, since edges are source of printing, edges should be checked as soon as possible. So first, we define an unvisited query vertex as extendable regarding partial embedding M if all its parents are matched in M. So we always select extendable vertex as next vertex. So in this figure, let's suppose there are gray query vertices are already matched than blue query vertices, U4 and U7 are extendable vertices. And extendable candidates of extendable vertex U is defined as an intersection of an adjacency list of its parent mappings. So for example, U4's extendable candidates is V2 in CS and U7's extendable candidate is V11. So in our backtracking framework, we first select extendable vertex U and next, we map U to each unvisited extendable candidates and recurs. And I will briefly show how our adaptive matching order works. So suppose we extend a partial embedding M, and there may be more than one extendable vertex, then which extendable vertex should be selected first? We suggest two adaptive matching order to select next extendable vertex to match. First candidate-sized order is to select query vertex such that its number of extendable candidates is minimum. Passage order is to select a query vertex such that its weight is minimum, where weight estimates the number of pass embeddings in a deck. So considering these running examples, let's suppose yellow query vertices are already matched to corresponding databases in a CS. And we can visualize this whole search process as such tree of backtracking where each node corresponds, represents a partial embedding ending with a mapping from mapping that node. So regarding, for example, regarding yellow partial embedding, we select U7 as the next extendable vertex because U7's weight is minimum. On the other hand, regarding green partial embedding, we select U4 because U4. So since weight is computed for every partial embedding, the next extendable vertex to match may be different for different partial embeddings. So this is adaptive matching order. So our last technique is called pruning by failing sets. Considering these running examples, let's suppose we just finished exploring subtree written at M, you want to V1, U2 to V2, and U4 to 1003. And we tried all possible extensions to map U3 and U5, and all attempts failed by conflict in mappings of U2 and U5 while U4 was not relevant to any failures. No matter how we change mappings of U4, all extensions will end up with failures in the same way. So I'm not going to go detail, but we can compute a set of quadripertices for every partial embedding so that one quadripertice, if one quadripertice is not in the failing set, then all siblings of node MR, node M are redundant, or all partial embeddings are redundant. So in this such tree, failing set for this partial embedding is U1, U2, and U3, U4. But we try to map U4, but U4 is not in a failing set. So we don't need to map U4 anymore so that we can prune out a lot of such space. And we evaluated our algorithm mainly with state-of-the-art CFL match, and we tested to test our individual, effectiveness of our individual technique, we tested DA, which used the graph DEP and adaptive matching order, and DA, the A plus failing set. And we evaluated on six real datasets and a billion scale graph tweeter. For each data graph, eight quadripsets are generated, and 100 quadripsets are in each set. In this figure, for example, 50 admins, 100 non-spots, quadripsets for 50 vertices. And due to NP hardness, some queries are bad instances, so not finishing in a reasonable time. So we set the time limit of 10 minutes for every query, and consider the queries finishing in 10 minutes as solved or unsolved otherwise. We measured average running time and number of requested calls in such, and the percentage of solved queries. In most cases, DEF outperforms a state-of-the-art algorithm, especially in East, it outperforms by up to four orders of magnitude in running time, and six orders of magnitude in a number of requested calls. For the remaining datasets, in most cases, DEF outperforms CFO match. For example, while CFO match solved 76% of queries, DEF solved all queries for 40 admins of email. And DEF outperformed CFO match by up to five orders of magnitude in a number of requested calls and three orders of magnitude in running time. We also evaluated on the billion-scale graph Twitter, which has four million vertices and more than one billion edges. And DEF outperforms CFO match, and general trend is that as queries increases, the gap between them in solved queries increases. And DEF, we also divided a total time into pre-processing time and such time, where such time is time for backtracking. And DEF was three orders of magnitude faster in such time. We also parallelized our algorithm to test scalability and issues near linear speedup, where the speedup is 12.7 for non-spot queries for 16 threads. So we briefly introduced three techniques in our algorithm, and we will extend our work to parallel and distributed platforms. Thank you for listening.
 I'm Hyun-Jun Kim from South National University, and I'll talk about a new efficient sub-grap  matching algorithm.  And I will briefly show the challenges of sub-grap matching and existing solutions, and briefly  introduce the overview of our algorithm and three main techniques using our algorithm.  So given a query graph and a data graph, an embedding is a mapping from a query vertex  to a data vertex such that for different query vertices, their mappings are different,  and for every query vertex, its label should be same as its mappings label.  And for every edge U and U prime in a query graph, M U and M U prime should be also in  a data graph.  And on embedding of an induced sub-grap of a query in a data graph is a partial embedding.  So in this figure, we can find a blue sub-grap, a blue embedding of a query graph in a data  graph.  And for induced sub-grap with U1, U2, and U3, we can find partial embedding U1 to V1,  U2 to V3, and U3 to V5.  And sub-grap matching is to find all these things embeddings of a query in a data graph,  which is an NP-hard problem.  So in this example, we should find these two embeddings.  And traditionally, existing solutions adopt, use the general framework.  First they adopt a filtering process to find a candidate set for each query vertex, where  CU is a subset of data vertices which U can be mapped to.  In this figure, U1's candidate set can be of V1 and V2.  Next choose a linear order of query vertices called matching order and apply backtracking  based on the matching order.  For in this example, for matching order U1, U2, U3, and U4, we first match U1 to one  of the data vertices and match U2 and so on.  There are two state-of-the-art algorithms which are table iso proposed in 2013 and CFO  match in 2016.  Both use the spanning tree of a query graph for a filtering process.  So they find potential embeddings of a spanning tree in a data graph.  And next, candidate sets computed in the filtering process are stored in an auxiliary data structures.  And eventually they find all embeddings of a query graph by checking the entry edges  during backtracking.  There are some limitations in existing solutions.  So since spanning tree does not have all the edges in a query graph, the auxiliary data  structures may contain many false positives.  So let's say they're considering this query graph in a data graph and there are two routes  to leave paths P1 and P2.  And there are 50 embeddings of P1 and 100 embeddings of P2 starting from V1 in a data  graph.  And most of them will not lead to an embedding of a query graph.  So to deal with this problem, we suggest a technical dynamic programming between DAG  and GRAP.  And another important problem is the matching order.  So let's say there are 50 embeddings of P1 and 100 embeddings of P2 after the filtering  process.  Then pass ordering select P1 and then P2 as a matching order.  Then backtracking will generate 50 times 100 partial embedding.  But if we check edge between U3 and U4 in a query graph earlier during backtracking,  we can eliminate most of the partial embeddings.  So to handle this problem, we suggest DAG ordering.  And some existing work use the global matching order where a pre-computed matching order  is used throughout the whole search process.  So as opposed to this order, we proposed adaptive matching order.  And to reduce redundant computations in such, we propose a printing by Fellingstead, which  I'll be showing later.  So this is our brief overview of our algorithm.  Given a query graph, we first build a rooted DAG.  To build a DAG, we first select root to have a large degree and a small number of candidates  in a data graph.  Next, we traverse a query graph in BFS order and direct all edges from earlier to later  visitor vertices.  Next, we build a candidate space called CS by using our technique called DAG-Graph-DP  or dynamic programming between DAG and GRAP.  And after computing this our auxiliary data structure, we find all embeddings of query  in CS by applying adaptive matching order and printing by Fellingstead.  So CS is a complex search space.  Once we compute a CS, we don't need a data graph to search for all embeddings of query  graph.  So CS on a query and a data graph consists of candidate set and edges.  There's a candidate set for every query product you and there's edge between candidates in  a between different candidates.  If and only if there's an edge in a query graph and corresponding edge is in a data  graph.  So given a query DAG, we can compute refined candidates set by using a dynamic programming  in a reverse topological order in a DAG.  So in this figure, we can remove a V8 from U2's candidate set because V8 is not connected  to any of the candidate in a U4's candidate set while there's an edge between U2 and U4  in a query graph.  And next, we can remove V2 from U1's candidate set accordingly.  In this way, we build a compact CS.  So starting from this initial CS, we repeat DAG graph dynamic programming with different  kinds of query DAGs alternately.  So for, we first use this reverse DAG and then we can obtain a refined candidate set.  And next, in this time, we use an original query DAG to obtain a further refined candidate  set.  And next, we also, we use a reverse query DAG once again and we can compute a further  refined candidate set.  So in this CS structure, we search for embeddings of query graph, but during backtracking, since  edges are source of printing, edges should be checked as soon as possible.  So first, we define an unvisited query vertex as extendable regarding partial embedding  M if all its parents are matched in M. So we always select extendable vertex as next  vertex.  So in this figure, let's suppose there are gray query vertices are already matched than  blue query vertices, U4 and U7 are extendable vertices.  And extendable candidates of extendable vertex U is defined as an intersection of an adjacency  list of its parent mappings.  So for example, U4's extendable candidates is V2 in CS and U7's extendable candidate  is V11.  So in our backtracking framework, we first select extendable vertex U and next, we map  U to each unvisited extendable candidates and recurs.  And I will briefly show how our adaptive matching order works.  So suppose we extend a partial embedding M, and there may be more than one extendable  vertex, then which extendable vertex should be selected first?  We suggest two adaptive matching order to select next extendable vertex to match.  First candidate-sized order is to select query vertex such that its number of extendable  candidates is minimum.  Passage order is to select a query vertex such that its weight is minimum, where weight  estimates the number of pass embeddings in a deck.  So considering these running examples, let's suppose yellow query vertices are already  matched to corresponding databases in a CS.  And we can visualize this whole search process as such tree of backtracking where each node  corresponds, represents a partial embedding ending with a mapping from mapping that node.  So regarding, for example, regarding yellow partial embedding, we select U7 as the next  extendable vertex because U7's weight is minimum.  On the other hand, regarding green partial embedding, we select U4 because U4.  So since weight is computed for every partial embedding, the next extendable vertex to match  may be different for different partial embeddings.  So this is adaptive matching order.  So our last technique is called pruning by failing sets.  Considering these running examples, let's suppose we just finished exploring subtree  written at M, you want to V1, U2 to V2, and U4 to 1003.  And we tried all possible extensions to map U3 and U5, and all attempts failed by conflict  in mappings of U2 and U5 while U4 was not relevant to any failures.  No matter how we change mappings of U4, all extensions will end up with failures in the  same way.  So I'm not going to go detail, but we can compute a set of quadripertices for every  partial embedding so that one quadripertice, if one quadripertice is not in the failing  set, then all siblings of node MR, node M are redundant, or all partial embeddings are  redundant.  So in this such tree, failing set for this partial embedding is U1, U2, and U3, U4.  But we try to map U4, but U4 is not in a failing set.  So we don't need to map U4 anymore so that we can prune out a lot of such space.  And we evaluated our algorithm mainly with state-of-the-art CFL match, and we tested  to test our individual, effectiveness of our individual technique, we tested DA, which  used the graph DEP and adaptive matching order, and DA, the A plus failing set.  And we evaluated on six real datasets and a billion scale graph tweeter.  For each data graph, eight quadripsets are generated, and 100 quadripsets are in each  set.  In this figure, for example, 50 admins, 100 non-spots, quadripsets for 50 vertices.  And due to NP hardness, some queries are bad instances, so not finishing in a reasonable  time.  So we set the time limit of 10 minutes for every query, and consider the queries finishing  in 10 minutes as solved or unsolved otherwise.  We measured average running time and number of requested calls in such, and the percentage  of solved queries.  In most cases, DEF outperforms a state-of-the-art algorithm, especially in East, it outperforms  by up to four orders of magnitude in running time, and six orders of magnitude in a number  of requested calls.  For the remaining datasets, in most cases, DEF outperforms CFO match.  For example, while CFO match solved 76% of queries, DEF solved all queries for 40  admins of email.  And DEF outperformed CFO match by up to five orders of magnitude in a number of requested  calls and three orders of magnitude in running time.  We also evaluated on the billion-scale graph Twitter, which has four million vertices and  more than one billion edges.  And DEF outperforms CFO match, and general trend is that as queries increases, the gap  between them in solved queries increases.  And DEF, we also divided a total time into pre-processing time and such time, where such  time is time for backtracking.  And DEF was three orders of magnitude faster in such time.  We also parallelized our algorithm to test scalability and issues near linear speedup,  where the speedup is 12.7 for non-spot queries for 16 threads.  So we briefly introduced three techniques in our algorithm, and we will extend our work  to parallel and distributed platforms.  Thank you for listening.
Han_Kim_Gu_Park_Han_0_131.png Han_Kim_Gu_Park_Han_132_203.png Han_Kim_Gu_Park_Han_204_275.png Han_Kim_Gu_Park_Han_276_683.png Han_Kim_Gu_Park_Han_684_2339.png Han_Kim_Gu_Park_Han_2340_4247.png Han_Kim_Gu_Park_Han_4248_7031.png Han_Kim_Gu_Park_Han_7032_8267.png Han_Kim_Gu_Park_Han_8268_8603.png Han_Kim_Gu_Park_Han_8604_9167.png Han_Kim_Gu_Park_Han_9168_9983.png Han_Kim_Gu_Park_Han_9984_11339.png Han_Kim_Gu_Park_Han_11340_12791.png Han_Kim_Gu_Park_Han_12792_13115.png Han_Kim_Gu_Park_Han_13116_14231.png Han_Kim_Gu_Park_Han_14232_15815.png Han_Kim_Gu_Park_Han_15816_15863.png Han_Kim_Gu_Park_Han_15864_15947.png Han_Kim_Gu_Park_Han_15948_18215.png Han_Kim_Gu_Park_Han_18216_18947.png Han_Kim_Gu_Park_Han_18948_20579.png Han_Kim_Gu_Park_Han_20580_21479.png Han_Kim_Gu_Park_Han_21480_22379.png Han_Kim_Gu_Park_Han_22380_22787.png Han_Kim_Gu_Park_Han_22788_23171.png Han_Kim_Gu_Park_Han_23172_23285.png