Fast Approximate Pattern Counting For Static Graphs
Ruini Xue, Yijun Wang, Lingwei Chao, Wenhong Tian · 2023
Pattern counting is a fundamental computational graph mining task. Recently, extensive research has been conducted on approximate pattern counting, but existing algorithms are not scalable, especially for large-scale static graphs. To address this challenge, we propose FAPC- a fast and efficient method for approximate pattern counting by exploiting the fact that the distribution of pattern numbers to degrees follows the power-law function as well. Unlike existing sampling processes, our approach can quickly fit the formula coefficients and calculate directly the pattern frequency. The prototype of FAPC has been evaluated against multiple public datasets and experimental results demonstrate that it outperforms current approaches by up to 50x speed.