Supports estimation via graph sampling

Xin Wang

doi:10.1016/j.eswa.2023.122554

2024-04-01

PRE

Xin Wang

Yu Fang

Wen-Bo Xie *

DOI：10.1016/j.eswa.2023.122554

原文链接

原文求助

摘要

En 中文

Frequent pattern mining (FPM), whose goal is to identify patterns with appearance frequencies above a specified support threshold on a large graph, has attracted increasing attention owing to its diverse applications. The task suffers from an issue of support setting, as an inappropriate support threshold may lead to either extremely high computational cost along with a huge pattern set or very few patterns caused by excessive pruning. Thus, supports estimation is crucial for FPM, since an appropriate support threshold enables users to discover a limited number of patterns within affordable computational resources. In light of this, we investigate the problem of supports estimation under the constraint of pattern number B and propose a comprehensive approach to the issue. Our approach leverages a neural network to predict the support 0B that corresponds to the B-th pattern on a graph G. To train the prediction model, we first present a sampling algorithm that leverages typical motifs to produce sampled graphs of G under different sampling ratios. Owing to the typical structures brought about by motifs, the sampled graphs are embedded supports of the top -ranked patterns in proportion to the sampling ratios. We next develop techniques to efficiently infer the support 0B of the B-th pattern on each sampled graph and introduce a method to encode (sampled) graphs with 0B and other typical features, thereby forming the training data. Extensive experimental studies on real -life and synthetic graphs demonstrate the superiority of our approach, compared to other baselines.

Keyword:

Supports estimation

Graph sampling

Frequent pattern mining

Motifs