#
Efficient Discovery of Frequent Subgraph Patterns in Uncertain Graph Databases

###
Odysseas Papapetrou, Ekaterini Ioannou, Dimitrios Skoutas

L3S Research Center, University of Hannover

### {papapetrou, ioannou, skoutas}@L3S.de

**Abstract:**
Mining frequent subgraph patterns in graph databases is a challenging and
important problem with applications in several domains. Recently, there is a
growing interest in generalizing the problem to uncertain graphs, which can model
the inherent uncertainty in the data of many applications. The main difficulty in
solving this problem results from the large number of candidate subgraph patterns
to be examined and the large number of subgraph isomorphism tests required to
find the graphs that contain a given pattern. The latter becomes even more
challenging, when dealing with uncertain graphs. In this paper, we
propose a method that uses an index of the uncertain graph database to reduce the
number of comparisons needed to find frequent subgraph patterns. The proposed
algorithm relies on the apriori property for enumerating candidate subgraph
patterns efficiently. Then, the index is used to reduce the number of comparisons
required for computing the expected support of each candidate pattern. It also
enables additional optimizations with respect to scheduling and early termination, that
further increase the efficiency of the method. The evaluation of our approach on
three real-world datasets as well as on synthetic uncertain graph databases
demonstrates the significant cost savings with respect to the state-of-the-art
approach.

Appeared at the 14th International Conference on Extending Database Technology (EDBT) 2011.

@inproceedings{DBLP:conf/edbt/PapapetrouIS11,
author = {Odysseas Papapetrou and
Ekaterini Ioannou and
Dimitrios Skoutas},
title = {Efficient discovery of frequent subgraph patterns in uncertain
graph databases},
booktitle = {EDBT},
year = {2011},
pages = {355-366},
ee = {http://doi.acm.org/10.1145/1951365.1951408},
bibsource = {DBLP, http://dblp.uni-trier.de}
}