Circular RNA (circRNA)-microRNA (miRNA) interaction (CMI) plays crucial roles in cellular regulation, offering promising perspectives for disease diagnosis and therapy. Therefore, it is necessary to employ computational methods for the rapid and cost-effective prediction of potential circRNA-miRNA interactions. However, the existing methods are limited by incomplete data; therefore, it is difficult to model molecules with different attributes on a large scale, which greatly hinders the efficiency and performance of prediction. In this study, we propose an effective method for predicting circRNA-miRNA interactions, called RBNE-CMI, and introduce a framework that can embed incomplete multiattribute CMI heterogeneous networks. By combining the proposed method, we integrate different data sets in the CMI prediction field into one incomplete network for modeling, achieving superior performance in 5-fold cross-validation. Moreover, in the prediction task based on complete data, the proposed method still achieves better performance than the known model. In addition, in the case study, we successfully predicted 18 of the 20 potential cancer biomarkers. The data and source code can be found at https://github.com/1axin/RBNE-CMI.