  Approximate graph pattern mining (A-GPM) is an important data analysis tool
for many graph-based applications. There exist sampling-based A-GPM systems to
provide automation and generalization over a wide variety of use cases.
However, there are two major obstacles that prevent existing A-GPM systems
being adopted in practice. First, the termination mechanism that decides when
to end sampling lacks theoretical backup on confidence, and is unstable and
slow in practice. Second, they suffer poor performance when dealing with the
"needle-in-the-hay" cases, because a huge number of samples are required to
converge, given the extremely low hit rate of their fixed sampling schemes. We
build ScaleGPM, an accurate and fast A-GPM system that removes the two
obstacles. First, we propose a novel on-the-fly convergence detection mechanism
to achieve stable termination and provide theoretical guarantee on the
confidence, with negligible overhead. Second, we propose two techniques to deal
with the "needle-in-the-hay" problem, eager-verify and hybrid sampling. Our
eager-verify method improves sampling hit rate by pruning unpromising
candidates as early as possible. Hybrid sampling improves performance by
automatically choosing the better scheme between fine-grained and
coarse-grained sampling schemes. Experiments show that our online convergence
detection mechanism can detect convergence and results in stable and rapid
termination with theoretically guaranteed confidence. We show the effectiveness
of eager-verify in improving the hit rate, and the scheme-selection mechanism
in correctly choosing the better scheme for various cases. Overall, ScaleGPM
achieves a geomean average of 565x (up to 610169x) speedup over the
state-of-the-art A-GPM system, Arya. In particular, ScaleGPM handles
billion-scale graphs in seconds, where existing systems either run out of
memory or fail to complete in hours.
