DistanceJoin: Pattern Match Query In a Large Graph Database

Lei Zou, Lei Chen, M. Tamer Özsu

TL;DR

This paper introduces "Distance-Join," a novel approach for efficiently querying large graph databases. It tackles the challenge of finding patterns in graphs where connections are defined by shortest-path distances, not just direct links, by transforming graph queries into a distance-based multi-way join problem in a vector space. This method significantly outperforms existing techniques by orders of magnitude.

What Problem Does This Paper Address?

Graph databases are increasingly used to model complex relationships in various domains like social networks and biological systems. While subgraph search and shortest-path queries are common, "pattern match queries" offer a more flexible way to explore data. These queries look for specific structural patterns, but with an added constraint: the distance between connected nodes in the data graph must be within a specified threshold, rather than requiring a direct edge. This "distance pattern match" is more informative than simple reachability but computationally much harder. The core challenge is the massive search space created by the combinatorial explosion of possible matches, especially in large graphs. Existing methods for subgraph search or even simpler pattern matching (based on reachability) are not directly applicable or efficient for this distance-constrained problem.

Methods

The paper proposes a multi-stage approach:

  1. Graph Embedding: Vertices in the large data graph G are mapped into a lower-dimensional vector space using LLR embedding techniques. This transforms the graph structure into a set of points, making distance calculations more tractable.
  2. Distance-Based Multi-way Join: The pattern match query Q is then reformulated as a distance-based multi-way join operation over these embedded vectors. The goal is to find sets of vertices in G whose embedded representations satisfy the distance constraints defined by Q.
  3. Pruning Strategies: To combat the remaining search space explosion, several pruning techniques are introduced:
  4. Neighbor Area Pruning: This technique leverages the fact that if a vertex in G cannot find a neighbor within the specified distance δ for any of its required connections in Q, it can be safely discarded. This is applied in the high-dimensional vector space.
  5. Triangle Inequality Pruning: This method uses the triangle inequality property of distance metrics to prune candidate pairs during join operations.
  6. Hash Join: A modified hash join strategy is employed for efficient join processing in the vector space, particularly for high-dimensional data.
  7. Cost Model and Join Order Selection: A cost model is developed to estimate the expense of different join operations. This model guides a greedy join order selection algorithm to find an efficient query execution plan, prioritizing backward edges and then selecting forward edges with the lowest estimated cost.
  8. Edge Query Processing: For individual edge queries (pairs of connected vertices in Q), a "Distance-Join" (D-join) algorithm is proposed. It first uses the L∞ distance in the embedded space to find candidate matches and then verifies these candidates using exact shortest-path distance computations on the original graph (enabled by pre-computed 2-hop distance labels).

Datasets

The paper evaluates its methods on both synthetic and real-world datasets:

  • Synthetic Datasets:
    • Erdos-Renyi (ER) Model: A random graph with 100K vertices and 500K edges.
  • Scale-Free (SF) Model: A graph with 100K vertices exhibiting power-law distribution, generated using gengraphwin.
  • Real Datasets:
    • Citeseer: A co-author network derived from the Citeseer dataset, featuring approximately 388K vertices and 1.1M edges. Vertex labels are based on author affiliations.
  • Yeast: A protein-protein interaction network from budding yeast, with about 2.3K vertices and 6.6K edges. Vertex labels are based on protein clusters.

Key Insights and Ideas

  • Vector Space Transformation is Key: The core innovation is the transformation of graph structure and distance constraints into a vector space problem. This allows leveraging efficient vector-based join and pruning techniques, which are often more scalable than direct graph traversal for complex queries.
  • L∞ Distance as a Powerful Lower Bound: Using L∞ distance in the embedded space as a lower bound for shortest-path distance is crucial. It allows for efficient candidate generation and pruning, significantly reducing the number of expensive shortest-path computations.
  • Orthogonal Pruning Techniques: The combination of neighbor area pruning, triangle inequality pruning, and hash join proves highly effective because these methods address different aspects of the search space and are largely orthogonal, leading to substantial reductions in computation.
  • Join Order Matters Significantly: The paper highlights that the order in which edges are processed in a multi-way join can drastically impact performance. A well-designed cost model and greedy selection strategy are essential for efficient pattern matching.

Key Results

  • Orders of Magnitude Speedup: The proposed "Distance-Join" (D-join) method, especially when combined with LLR embedding and pruning techniques, consistently outperforms baseline methods (including an extension of R-join, D-join without embedding, RSJ, and EGO) by "orders of magnitude" in terms of query response time across various datasets and query complexities.
  • Effective Pruning: Neighbor area pruning, triangle inequality pruning, and hash join collectively reduce the number of distance computations by a significant margin. For instance, LLR embedding alone is shown to filter out about 90% of the search space.
  • Cost Model Accuracy: The sampling-based cost estimation method is shown to be more accurate than a dimension-independent assumption, especially in the correlated vector spaces generated by graph embeddings.
  • Scalability: The approach demonstrates good scalability with increasing graph sizes and query complexities.

Limitations and Future Work

  • Dimensionality Curse: While LLR embedding and specific join algorithms mitigate it, high dimensionality in the vector space remains a challenge for some similarity join algorithms (e.g., R-tree based).
  • Clustering Algorithm Orthogonality: The paper notes that the choice of clustering algorithm for the embedded points is orthogonal to their D-join approach, implying that improvements in clustering could further enhance performance.
  • Correlation in Embedded Dimensions: The dimension-independence assumption for selectivity estimation proved inaccurate due to correlations in the embedded vector space, necessitating more sophisticated sampling-based methods.
  • Future Work: The paper suggests exploring more advanced sampling techniques for selectivity estimation in high-dimensional spaces and investigating optimal clustering strategies. The authors also implicitly point towards further research in optimizing similarity join algorithms for specific distance metrics like L∞.

Summary updated

Abstract

The growing popularity of graph databases has generated interesting data management problems, such as subgraph search, shortest-path query, reachability verification, and pattern match. Among these, a pattern match query is more flexible compared to a subgraph search and more informative compared to a shortest-path or reachability query. In this paper, we address pattern match problems over a large data graph G. Specifically, given a pattern graph (i.e., query Q ), we want to find all matches (in G ) that have the similar connections as those in Q. In order to reduce the search space significantly, we first transform the vertices into points in a vector space via graph embedding techniques, coverting a pattern match query into a distance-based multi-way join problem over the converted vector space. We also propose several pruning strategies and a join order selection method to process join processing efficiently. Extensive experiments on both real and synthetic datasets show that our method outperforms existing ones by orders of magnitude.
BibTeX
@article{zou2009distancejoin,
  author = {Lei Zou and Lei Chen and M. Tamer Özsu},
  title = {{DistanceJoin: Pattern Match Query In a Large Graph Database}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  url = {https://openreview.net/forum?id=rvE0CRILsN},
}
Figure