The paper presents a new projection operator for graphs, named AC- projection, which exhibits good complexity properties as opposed to the graph isomorphism (Θ-subsumption) operator typically used in graph mining. We study the size of the search space and some practical properties of the projection operator. These properties give us a specialization algorithm using simple local operations. Then we prove ex- perimentally that we can achieve an important performance gain (poly- nomial complexity projection) without or with non-significant loss of discovered patterns quality.