In recent years, the rapid development of high-throughput technology has led to huge amounts of protein–protein interaction (PPI) data and unannotated protein sequences. Many approaches for protein function prediction have been developed which use PPI networks information. Traditional methods usually use the dependencies among interacting proteins for each same function only. However, the functions which are barely linked with the same function are more difficult to predict. In multi-label settings, the dependencies among related instances with multiple labels are more complex; rationally using these associations can make up for the shortcomings of traditional methods. In this paper, an iterative algorithm is applied to predict protein function based on the new network. The proposed method is able to capture the dependencies among functions based on proteins and interactions for protein function prediction. The test results show that the algorithm performs better than most of existing network based PPI algorithms; adding sequence similarity edges and spread function information can really improve the prediction performance. In addition, the dependencies among functions based on proteins and interactions can be effectively applied to the prediction of protein function.