Scalable and Adaptive Graph Querying with MapReduce

Song-Hyon Kim, Kyong-Ha Lee, Inchul Song, Hyebong Choi, Yoon-Joon LeeIEICE Trans. Information and Systems 2013 · OpenReview

Abstract

We address the problem of processing graph pattern matching queries over a massive set of data graphs in this letter. As the number of data graphs is growing rapidly, it is often hard to process such queries with serial algorithms in a timely manner. We propose a distributed graph querying algorithm, which employs feature-based comparison and a filter-and-verify scheme working on the MapReduce framework. Moreover, we devise an efficient scheme that adaptively tunes a proper feature size at runtime by sampling data graphs. With various experiments, we show that the proposed method outperforms conventional algorithms in terms of scalability and efficiency.

Introduction

Graph pattern matching—finding data graphs containing a specific query graph—is a critical task in fields like bioinformatics and chemical informatics. However, the underlying subgraph isomorphism test is NP-complete, making it computationally prohibitive for massive datasets. This paper introduces MR-Graph, a distributed framework designed to scale this task using MapReduce. MR-Graph's primary innovation is AdaptiveTune, a mechanism that dynamically balances the trade-off between filtering efficiency and computational overhead.

The Challenge: Scalability and the "Goldilocks" Feature Problem

Traditional "filter-and-verify" techniques use small subgraphs (features) to prune the search space. However, they face two significant hurdles:

  1. Scalability: Serial algorithms cannot process modern datasets reaching tens of terabytes.
  2. Feature Optimization: Small features lead to weak filtering (too many false positives), while large features incur high extraction and storage costs. Finding the optimal feature size ($k$) is difficult because it varies based on the specific query and data characteristics.

The MR-Graph Framework

MR-Graph implements a distributed filter-and-verify scheme across the MapReduce pipeline:

  • Map Stage: Mappers extract features from data graphs and compare them against query features. If a match is possible, the mapper performs the subgraph isomorphism test using the VF2 algorithm.
  • Reduce Stage: Reducers aggregate and group valid matches by query ID.

AdaptiveTune Mechanism

The core of MR-Graph is AdaptiveTune, which avoids static indexing by sampling data at runtime. The system uses the first few mappers as "trial mappers" to test different values of $k$. These trials report performance metrics to a Distributed Coordination System (DCS), implemented via Apache ZooKeeper. The DCS then estimates the most efficient strategy and instructs all active mappers to switch to that feature size mid-job.

The AdaptiveTune mechanism uses trial mappers and a Distributed Coordination System (DCS) to optimize feature size at runtime.

Experimental Evaluation

The researchers evaluated MR-Graph using two datasets of 10 million graphs each: PubChem (real-world chemical compounds) and a Synthetic dataset. They tested the system against 1,000 query graphs to measure throughput and latency.

Key Results and Insights

MR-Graph demonstrates significant improvements in both efficiency and scalability:

  • Dynamic Optimization: AdaptiveTune reduced execution time by 52.5% on the real-world PubChem dataset compared to using a fixed, preset feature size.
  • Superiority over State-of-the-Art: MR-Graph consistently outperformed previous MapReduce-based methods, such as the edge-index approach by Luo et al., particularly as the number of queries increased.
  • Horizontal Scalability: The system showed excellent horizontal scaling, performing 25.3 times faster than a basic non-filtering MapReduce approach when scaled to 8 data nodes.
MR-Graph outperforms existing methods like Luo et al. and a basic MapReduce approach as the number of queries increases.

Conclusion and Future Work

MR-Graph proves that runtime adaptation is a powerful tool for large-scale graph processing. By performing expensive isomorphism tests in the Map phase, the system maximizes parallelization and avoids the shuffle bottleneck common in MapReduce applications. Future work may extend this approach to single massive interconnected graphs (like social networks) and explore adaptive selection between different feature types, such as paths or cycles.

Summary updated

Abstract

We address the problem of processing graph pattern matching queries over a massive set of data graphs in this letter. As the number of data graphs is growing rapidly, it is often hard to process such queries with serial algorithms in a timely manner. We propose a distributed graph querying algorithm, which employs feature-based comparison and a filter-and-verify scheme working on the MapReduce framework. Moreover, we devise an efficient scheme that adaptively tunes a proper feature size at runtime by sampling data graphs. With various experiments, we show that the proposed method outperforms conventional algorithms in terms of scalability and efficiency.
BibTeX
@article{kim2013scalable,
  author = {Song-Hyon Kim and Kyong-Ha Lee and Inchul Song and Hyebong Choi and Yoon-Joon Lee},
  title = {{Scalable and Adaptive Graph Querying with MapReduce}},
  journal = {IEICE Trans. Information and Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=QhfHMLQFPc},
}
Figure