Technical Papers Archive

BatchMine: Accelerating Approximate Graph Pattern Mining via Batch Processing


Authors: Guang Wu and Zhengbin Pang (NUDT), Hongxu Jin (Zunyi Normal University), and Xinbiao Gan (NUDT)

Abstract: Approximate graph pattern mining, as a fundamental technique in graph analysis, has been widely applied in machine learning, biomedical research, and social network analysis. However, existing solutions still face significant challenges in efficiency and scalability when dealing with complex pattern graphs or giant data graphs. To address these limitations, we introduce BatchMine, an out-of-core system for approximate graph pattern mining. BatchMine leverages three key techniques: (1) a partition-based estimation method to accelerate convergence; (2) a batch-processing framework with adaptive refinement to enhance external-memory access locality and improve convergence efficiency; and (3) a hybrid data layout that balances sampling efficiency and storage overhead.

To the best of our knowledge, BatchMine is the first graph pattern mining system capable of handling graphs exceeding main memory capacity, enabling mining on graphs with nearly 100 billion edges on a single machine within 1,000 seconds. Extensive experiments further demonstrate the effectiveness and superiority of BatchMine.



Presentation: file

Back to Technical Papers Archive Listing