IEEE Transactions on Knowledge and Data Engineering

Download PDF

Keywords

Approximation Methods, Probability, Uncertainty, Data Mining, Computational Complexity, Graph Theory, Uncertain Graphs, Frequent Subgraphs, Approximation Algorithms, Pattern Mining

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.
Like what you’re reading?
Already a member?
Get this article FREE with a new membership!

Related Articles