Today, there is an increasing abundance of information and services available to mobile users. Many ubiquitous services retrieval architectures are based on keyword or interface matching which does not provide very accurate match results. More recently, semantic languages have been used to improve accuracy. However, this often requires the use of reasoning software which is very resource intensive. Therefore, in this paper we propose a semantic approach to service retrieval in ubiquitous computing environments, which improves accuracy over keyword / interface matching approaches but avoids the use of a semantic reasoned in order to provide improved efficiency over inference based proposals. In addition, our proposal incorporates a user profile to limit the search space and takes account of the capabilities of the requesting mobile device. Our approach also transforms BPEL service descriptions into a graph to perform atomic-level graph matching. Thus, we calculate semantic similarity between two graph nodes to provide a service ranking, so that it is possible obtain an approximate match if there is no service that exactly matches the user requirements. We have implemented our approach and provide a performance evaluation on a mobile device which clearly demonstrates that our approach is more efficient than reasoning and produces accurate match results. Keywords-matching; context-aware discovery; ubiquitous environments; personalization