Metabolic pathways are regarded as functional and basic components of the biological system. In metabolomics, metabolite set enrichment analysis (MSEA) is often used to identify the altered metabolic pathways (metabolite sets) associated with phenotypes of interest (POI), e.g., disease. However, in most studies, MSEA suffers from the limitation of low metabolite coverage. Random walk (RW)-based algorithms can be used to propagate the perturbation of detected metabolites to the undetected metabolites through a metabolite network model prior to MSEA. Nevertheless, most of the existing RW-based algorithms run on a general metabolite network constructed based on public databases, such as KEGG, without taking into consideration the potential influence of POI on the metabolite network, which may reduce the phenotypic specificities of the MSEA results. To solve this problem, a novel pathway analysis strategy, namely, differential correlation-informed MSEA (dci-MSEA), is proposed in this paper. Statistically, differential correlations between metabolites are used to evaluate the influence of POI on the metabolite network, so that a phenotype-specific metabolite network is constructed for RW-based propagation. The experimental results show that dci-MSEA outperforms the conventional RW-based MSEA in identifying the altered metabolic pathways associated with colorectal cancer. In addition, by incorporating the individual-specific metabolite network, the dci-MSEA strategy is easily extended to disease heterogeneity analysis. Here, dci-MSEA was used to decipher the heterogeneity of colorectal cancer. The present results highlight the clustering of colorectal cancer samples with their cluster-specific selection of differential pathways and demonstrate the feasibility of dci-MSEA in heterogeneity analysis. Taken together, the proposed dci-MSEA may provide insights into disease mechanisms and determination of disease heterogeneity.