Efficient Mining of Frequent Patterns on Uncertain Graphs

摘要

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 problemNof frequent subgraphmining on single uncertain graphs, and investigates two different - probabilistic and expected - semantics in terms of support definitions. First, we present an enumeration-evaluation algorithmto solve the problemunder 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 algorithmis extended in a similar flavor to handle the problemunder 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.