Many of the known prognostic gene signatures for cancer are individual genes or combination of genes, found by the analysis of microarray data. However, many random gene expression signatures are more predictive than known cancer signatures, and such predictive power of random signatures is largely attributed to cell proliferation genes. With the availability of RNA-seq gene expression data for thousands of human cancer patients, we have analyzed RNA-seq and clinical data of cancer patients and constructed gene correlation networks specific to individual cancer patients. From the gene correlation networks, we derived potential prognostic gene pairs for liver cancer, pancreatic cancer, and stomach cancer. In this paper, we present a new approach to inferring prognostic signatures from patient-specific gene correlation networks. Evaluation of our approach with comprehensive data of liver cancer, pancreatic cancer, and stomach cancer showed that our approach is general and that gene pairs found by our approach are more reliable prognostic signatures than genes. Our approach will be useful for constructing patient-specific gene correlation networks and for the prognosis of patients. The web server for dynamically constructing patient-specific gene networks and for finding prognostic gene pairs is accessible at http://bclab.inha.ac.kr/LPS.