  Recently, graph mining approaches have become very popular, especially in
domains such as bioinformatics, chemoinformatics and social networks. In this
scope, one of the most challenging tasks is frequent subgraph discovery. This
task has been motivated by the tremendously increasing size of existing graph
databases. Since then, an important problem of designing efficient and scaling
approaches for frequent subgraph discovery in large clusters, has taken place.
However, failures are a norm rather than being an exception in large clusters.
In this context, the MapReduce framework was designed so that node failures are
automatically handled by the framework. In this paper, we propose a large-scale
and fault-tolerant approach of subgraph mining by means of a density-based
partitioning technique, using MapReduce. Our partitioning aims to balance
computation load on a collection of machines. We experimentally show that our
approach decreases significantly the execution time and scales the subgraph
discovery process to large graph databases.
