SCIENCE@home

Efficient Mining of Frequent Patterns on Uncertain Graphs

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

Published 2019 in IEEE Transactions on Knowledge and Data Engineering

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.

PUBLICATION RECORD

  • Publication year

    2019

  • Venue

    IEEE Transactions on Knowledge and Data Engineering

  • Publication date

    2019-02-01

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    DOI 10.1109/TKDE.2018.2830336
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-45 of 45 references · Page 1 of 1

CITED BY

Showing 1-39 of 39 citing papers · Page 1 of 1