Approximating Graph Pattern Queries Using Views

Jia Li, Yang Cao, Xudong Liu2016 · DOI

TL;DR

This paper introduces a novel framework for approximating graph pattern queries using pre-computed views. It proposes methods to find "upper" and "lower" bound queries that can be answered using existing views, providing approximate answers to complex queries that cannot be directly answered. This approach significantly speeds up query execution while maintaining reasonable accuracy, making it practical for large-scale graph data.

What Problem Does This Paper Address?

Answering complex graph pattern queries (like those used in social network analysis or recommendation systems) directly on large datasets can be computationally expensive. While using pre-computed "views" (smaller, materialized query results) can speed up exact query answering, it's often impossible to answer complex queries exactly with a limited set of views. This paper addresses this gap by proposing a method to find approximate answers. Instead of an exact match, they aim to find two queries: an "upper approximation" that contains all possible answers and a "lower approximation" that is contained within all possible answers. Crucially, both these approximations can be answered using the available views, offering a trade-off between exactness and efficiency. They consider two common graph query semantics: graph simulation and subgraph isomorphism.

Methods

The core of the paper lies in defining and computing "upper" and "lower" approximations of a query $Q$ with respect to a set of views $V$.

  • Approximation Definition: An upper approximation $Q_u$ is a query answerable by $V$ such that $Q \subseteq Q_u$, meaning $Q_u$'s answers contain all of $Q$'s answers. A lower approximation $Q_l$ is similarly answerable by $V$ such that $Q_l \subseteq Q$, meaning $Q_l$'s answers are contained within $Q$'s answers. They also define "complete" approximations where the containment is exact.
  • Characterizations: The authors provide theoretical characterizations for when such approximations exist and how they relate to query containment and answering using views.
  • Algorithms: They develop algorithms for:
  • Existence: Determining if upper/lower approximations exist.
  • Closest Approximation: Finding the approximations that are "closest" to the original query $Q$ using a defined "closeness" metric based on edge differences. This involves algorithms like CUAsim for complete upper approximations and CLAsim for complete lower approximations.
  • Answering Approximations: Generating query plans to answer these approximations using only the view data.
  • Subgraph Queries: The framework is extended to handle subgraph queries, which have different matching semantics than simulation queries.

Datasets

The experiments were conducted on two real-life graph datasets:

  • DBpedia: A knowledge graph with 4.43 million nodes and 8.43 million edges.
  • YouTube: A video network with 2.03 million video nodes and 12.22 million directed edges.

The paper does not introduce new benchmark datasets but uses these existing ones to evaluate their proposed methods.

Key Insights and Ideas

  • Bridging the Gap: The most significant insight is that even if a complex graph query cannot be answered exactly using available views, it can often be approximated effectively. This opens up possibilities for query processing in scenarios with limited exact answerability.
  • Upper and Lower Bounds as a Solution: The concept of finding both an upper and a lower bound query that can be answered by views provides a practical way to bound the true answer set, offering a trade-off between accuracy and computational cost.
  • Approximation is Often Necessary: The experimental results highlight that only a small percentage of queries can be answered exactly using views, underscoring the practical need for approximation techniques.
  • Complete Approximations are More Accurate: The study shows that "complete" approximations (where the approximation is a subgraph or supergraph of the original query) generally yield higher accuracy than "generic" approximations.
  • Combining Approximations Improves Results: Using both the upper and lower approximations together (specifically, the weak F-measure) significantly improves the overall accuracy compared to using either approximation alone.

Key Results

  • Effectiveness: The proposed algorithms for finding closest upper and lower approximations are effective. For simulation queries on DBpedia, the F-measure of approximations is consistently above 0.7, and for subgraph queries, it's above 0.6.
  • Accuracy: Complete approximations are more accurate than generic ones. For instance, complete approximations achieved an F-measure of 0.89 compared to 0.82 for generic ones on larger subgraph queries.
  • Speedup: Querying using approximations with views offers substantial speedups. For simulation queries on YouTube, evaluation time was 80-300 times faster than direct evaluation.
  • Efficiency: The algorithms for computing approximations are efficient, taking at most 2.7 seconds for all queries on both datasets, even with all views.
  • Answerability vs. Approximation: While only a small percentage of queries were exactly answerable using views (e.g., 12% for simulation queries on DBpedia), a much larger percentage (e.g., 85% for simulation queries on DBpedia) could be approximated.

Limitations and Future Work

  • Approximation Quality: While effective, approximations are not exact. The paper acknowledges that the quality of approximation depends on the available views and the query structure.
  • Closeness Metric: The "closeness" metric is based on edge differences, which might not always perfectly align with user-perceived similarity.
  • Future Work: The authors suggest several directions:
  • Studying optimal approximations when views have associated costs.
  • Investigating optimal pairs of upper and lower approximations that cover specific parts of queries.
  • Extending the framework to other query types, such as relational queries.
  • Adapting the techniques for dynamic data graphs.

Summary updated

Abstract

This paper studies approximation of graph pattern queries using views. Given a pattern query Q and a set V of views, we propose to find a pair of queries Qu and Ql, referred to as the upper and lower approximations of Q w.r.t. V, such that (a) for any data graph G, answers to (part of) Q in G are contained in Qu(G) and contain Ql(G); and (b) both Qu and Ql can be answered by using views in V. We consider pattern queries based on both graph simulation and subgraph isomorphism. We study fundamental problems about approximation using views. Given Q and V, (1) we study whether there exist upper and lower approximations of Q w.r.t. V. (2) How to find approximations that are closest to Q w.r.t. V if exist? (3) How to answer upper and lower approximations using views in V? We give characterizations of the problems, study their complexity and approximation-hardness, and develop algorithms with provable bounds. Using real-life datasets, we verify the effectiveness and efficiency of approximating simulation and subgraph queries using views.
BibTeX
@misc{li2016approximating,
  author = {Jia Li and Yang Cao and Xudong Liu},
  title = {{Approximating Graph Pattern Queries Using Views}},
  year = {2016},
  doi = {10.1145/2983323.2983766},
}

Loading related content...

Figure