I. Introduction
Protein complexes are important for understanding principles of cellular organization and function. In the post-genome era, high-throughput experimental techniques have produced a large amount of protein interactions, making it possible to predict protein complexes from the protein interaction networks (PINs). Many complex identification approaches have been proposed to detect protein complexes from the PIN, including MCODE [1], CMC [2], COACH [3]. However, most of above methods are unsupervised learning methods, which predict the protein complexes based on the pre-defined rules and can not make full use of the information of available known complexes. In this paper, we present a supervised learning based method to discover the complexes in the PIN.