Recently, ice with stacking disorder structure, consisting of random sequences of cubic ice (Ic ) and hexagonal ice (Ih ) layers, was reported to be more stable than pure Ih /Ic . Due to a much lower free energy barrier of heterogeneous nucleation, in practice, the freezing process of water is controlled by heterogeneous nucleation triggered by an external medium. Therefore, we carry out molecular dynamic simulations to explore how ice polymorphism depends on the lattice structure of the crystalline substrates on which the ice is grown, focusing on the primary source of atmospheric aerosols, carbon materials. It turns out that, during the nucleation stage, the polymorph of ice nuclei is strongly affected by graphene substrates. For ice nucleation on graphene, we find Ih is the dominant polymorph. This can be attributed to structural similarities between graphene and basal face of Ih . Our results also suggest that the substrate only affects the polymorph of ice close to the graphene surface, with the preference for Ih diminishing as the ice layer grows.