Markov Logic Networks (MLNs) combine Markov Networks and first-order logic by attaching weights to first-order formulas and viewing them as templates for features of Markov Networks. Learning a MLN can be decomposed into structure and weights learning. In this paper we present a new algorithm for the generative learning of the structure of Markov Logic Networks. This algorithm relies on a graph of predicates, that summarizes the links existing between predicates in the training database. Candidate clauses are produced by the mean of a heuristical variabilization technique. According to our first experiments, this approach appears to be promising.