DNA methylation, a well-studied mechanism of epigenetic regulation, plays important roles in cancer. Increased levels of global DNA methylation is observed in primary solid tumors including endometrial carcinomas and is generally associated with silencing of tumor suppressor genes. The role of DNA methylation in cancer recurrence after therapeutic intervention is not clear. Here, we developed a novel computational method to analyze whole-genome DNA methylation data for endometrial tumors within the context of a human protein-protein interaction (PPI) network, in order to identify subnetworks as potential epigenetic biomarkers for predicting tumor recurrence. Our method consists of the following steps. First, differentially methylated (DM) genes between recurrent and non-recurrent tumors are identified and mapped onto a human PPI network. Then, a PPI subnetwork consisting of DM genes and genes that are topologically important for connecting the DMs on the PPI network, termed epigenetic connectors (ECs), are extracted using a Steiner-tree based algorithm. Finally, a random-walk based machine learning method is used to propagate the DNA methylation scores from the DMs to the ECs, which enables the ECs to be used as features in a support vector machine classifier for predicting recurrence. Remarkably, we found that while the DMs are not enriched in any cancerrelated pathways, the ECs are enriched in many well-known tumorgenesis and metastasis pathways and include known epigenetic regulators. Moreover, combining the DMs and ECs significantly improves the prediction accuracy of cancer recurrence and outperforms several alternative methods. Therefore, the network-based method is effective in identifying gene subnetworks that are crucial both for the understanding and prediction of tumor recurrence.