Efficient Mining of Frequent Patterns on Uncertain Graphs

Yifan Chen, Xiang Zhao, Xuemin Lin, Yang Wang, Deke Guo

Abstract

Uncertainty is intrinsic to a wide spectrum of real-life applications, which inevitably applies to graph data. Representative uncertain graphs are seen in bio-informatics, social networks, etc. This paper motivates the problem of frequent subgraph mining on single uncertain graphs, and investigates two different - probabilistic and expected - semantics in terms of support definitions. First, we present an enumeration-evaluation algorithm to solve the problem under probabilistic semantics. By showing the support computation under probabilistic semantics is #P-complete, we develop an approximation algorithm with accuracy guarantee for efficient problem-solving. To enhance the solution, we devise computation sharing techniques to achieve better mining performance. Afterwards, the algorithm is extended in a similar flavor to handle the problem under expected semantics, where checkpoint-based pruning and validation techniques are integrated. Experiment results on real-life datasets confirm the practical usability of the mining algorithms.
BibTeX
@article{chen2019efficient,
  author = {Yifan Chen and Xiang Zhao and Xuemin Lin and Yang Wang and Deke Guo},
  title = {{Efficient Mining of Frequent Patterns on Uncertain Graphs}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2019},
  doi = {10.1109/tkde.2018.2830336},
}

Loading related content...

Figure