Graph mining has become highly popular, especially in certain fields such as chemoinformatics, bioinformatics, and networks for social system. The important challenging task is to find all frequent subgraphs. Developing efficient algorithm for frequent subgraph mining is a challenging task. In this paper, a parallel algorithm for frequent graph mining, called “PFSG” algorithm based on FSG algorithm is proposed. It is carried out by partitioning the graph sets HoriVerticaly: “Horizontally and Vertically”, in which partitions relied on parallel computing over cloud system. This gives a new property to reduce the computations and the dependency in the parallel computation. The accomplishment of the proposed algorithm is evaluated in multiple datasets of graphs.