Dans le cadre d'un mécanisme d'apprentissage relation- nel, la propositionnalisation formelle a pour but de trans former la description structurelle des exemples en une description propositionnelle équivalente. Cette équivalence n'est pas basée sur l'expressivité ou la syntaxe mais sur l'équivalence des possibilités de discrimination du langage propositionnel par rapport au langage structurel et ce pour les exemples utilisés. Cette formalisation permet une caractérisation précise des motifs à sélectionner. Dans ce but nous utilisons une méthode performante de fouille de graphes pour l'extraction de motifs qui sont dans ce cas des chemins et des arbres répétés dans un ensemble de graphes. Ces motifs sont alors fournis à une méthode incrémentale, au niveau de l'ajout des motifs, qui sélectionne les motifs pertinents. Une expérimentation sur un jeu de données est ensuite présentée pour valider l'approche d'un point de vue pratique.