We propose a service mining framework for exploring interesting compositions of existing Web services. The framework first screens Web services for composition leads using a "coarse-grained" filtering approach. It then verifies these leads based on runtime conditions. Top candidates are selected from the verified leads and evaluated for their interestingness. We present algorithms to automate the screening phase of the framework. Finally, we study the effects of key variables on lead compositions? interestingness. As a motivating example, we apply these algorithms to the field of biological pathway discovery and rely on knowledge obtained from reverse engineering online resources to assess their effectiveness.