Hexagonal boron nitride is the only substrate that has so far allowed graphene devices exhibiting micrometer-scale ballistic transport. Can other atomically flat crystals be used as substrates for making quality graphene heterostructures? Here we report on our search for alternative substrates. The devices fabricated by encapsulating graphene with molybdenum or tungsten disulfides and hBN are found to exhibit consistently high carrier mobilities of about 60 000 cm(2) V(-1) s(-1). In contrast, encapsulation with atomically flat layered oxides such as mica, bismuth strontium calcium copper oxide, and vanadium pentoxide results in exceptionally low quality of graphene devices with mobilities of ∼1000 cm(2) V(-1) s(-1). We attribute the difference mainly to self-cleansing that takes place at interfaces between graphene, hBN, and transition metal dichalcogenides. Surface contamination assembles into large pockets allowing the rest of the interface to become atomically clean. The cleansing process does not occur for graphene on atomically flat oxide substrates.