The demands of migrating on-premises complex enterprise applications to cloud dramatically increase with the wide adoption of cloud computing. A recent research validates the possibility of combining multiple proprietary migration services offered by different vendors together to complete cloud migration. Pattern based service composition has been proven as an appealing approach to accelerate the service composition and ensure the qualities in the Service Oriented Architecture (SOA) domain and can be applied to the cloud migration service composition theoretically. However, current pattern discovery approaches are not applicable for the cloud migration due to lack of either existing cloud migration business process knowledge or execution logs. This paper proposes a novel approach to discover cloud migration patterns from a set of service composition solutions. The authors formalize the pattern discovery as a special graph similarity matching problem and present an algorithm to calculate the similarities of these service composition solutions. Patterns are chosen out of the solutions by similarity under designed criteria. The benchmark results and quantitative analysis show that our proposed approach is effective and efficient in pattern discovery for cloud migration service composition.