Arya: Arbitrary Graph Pattern Mining with Decomposition-based Sampling
summary
Arya is an approximate graph pattern miner that uses decomposition-based sampling (fractional edge cover to split patterns into cycles and stars) and edge-sampling of subpatterns with failure-aware scheduling to cut sample complexity. It implements a single-machine pipeline handling 5 billion edges and a 32-server distributed mode for 10 billion edges, exposes an Error-Latency Profile to set error vs time, and reports results within 5% error while running up to 20,000x faster than some exact systems and 1,000x faster than graphpi in the paper's benchmarks.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:47Pattern Mining is An Important Analytics Task
- 2:01Graph Pattern Mining
- 2:30Exact Mining Solutions
- 3:32Scalability Challenge in Exact Mining
- 4:13Approximate Pattern Mining
- 6:15ASAP Cannot Scale to Complex Patterns
- 7:33Graph Decomposition Theory
- 9:08Accelerate the computation
- 9:28The "Failure Probability" of Cycle/Star Samplers
- 12:34Evaluation: Exact Mining Systems Distributed replicated graph setting
- 13:20Evaluation: Approximate Mining Systems
related talks
19mCyclosa: Redundancy-Free Graph Pattern Mining via Set Dataflowi
24mLarge Scale Graph Computation with Apache Giraph
20mGraphWalker: An I/O-Efficient and Resource-Friendly Graph Analytic System...
56mGraph Analytic Systems
32mStreaming Algorithms for Matchings in Low Arboricity Graphs
01h 21mAn Overview on Data Streams Algorithms
10mScaling Time Series Analysis With Argo Workflows: Patterns and Practi...
24mGLogS: Interactive Graph Pattern Matching Query At Large Scale