Semantic Web technology is a promising first step for automated web service discovery. Most current approaches for web service discovery cater to semantic web services, i.e., web services that have associated semantic descriptions. It is unrealistic, however, to expect all new services to have associated semantic descriptions. Furthermore, the descriptions of the vast majority of already existing services do not have explicitly associated semantics. In this paper we present a novel approach for web service discovery that combines semantic and statistical association metrics. Semantic metrics are based on the semantic aspects of relevant ontology. Statistical association metrics are based on the association aspects of web services instances (their inputs and outputs). Specifically, our approach exploits semantic relationship ranking for establishing semantic relevance, and a hyperclique pattern discovery method for grouping web service parameters into meaningful associations. These associations combined by the semantic relevance are then leveraged to discover and rank web services.