The competing endogenous RNA (ceRNA) hypothesis motivates the existence of so-called sponges, i.e., genes that exert strong regulatory control via miRNA binding in a ceRNA interaction network. This poses a powerful disease mechanism that disrupts parts of the cellular transcriptional program through one or few key sponge genes. In particular in cancer, non-coding RNAs may facilitate changes in transcriptional programs without the risk of lethal side effects caused by expressing a protein at abnormally high or low levels. In spite of the importance of this phenomenon, we currently lack an efficient method for inferring sponge interactions on a genome-wide scale. Moreover, confounding factors such as large differences in sample numbers prevent comparisons across different cancer cohorts. This motivated us to develop sparse partial correlation on gene expression (SPONGE), a method that is orders of magnitude faster than previous approaches and allows for the construction of genome-wide ceRNA interaction networks. SPONGE is the first method to compute empirical p-values efficiently based on a series of null models and can thus control for confounding factors that were underestimated in previous studies. SPONGE enabled us to build the most comprehensive set of genome-wide ceRNA regulation models for 22 cancer types based on miRNA and gene expression data from The Cancer Genome Atlas. Since SPONGE accounts for confounding factors, we could perform pan-cancer analyses and reveal hundreds of novel sponge genes. In particular non-coding genes appear suitable as survival markers in different cancer types. Our results highlight the relevance of ceRNA network inference for clinical research, in particular considering the potential of targeting disease-associated non-coding RNAs in personalized medicine.