Abstract Gene coexpression network analysis has been shown effective in identifying functional coexpressed gene modules associated with complex human diseases. However, existing techniques to construct coexpression networks require some critical prior information such as predefined number of clusters, numerical thresholds for defining coexpression/interaction, or do not naturally reproduce the hallmarks of complex systems such as the scalefree degree distribution of smallworldness. Previously, a graph filtering technique called Planar Maximally Filtered Graph (PMFG) has been applied to many realworld data sets such as financial stock prices and gene expression to extract meaningful and relevant interactions. However, PMFG is not suitable for largescale genomic data due to several drawbacks, such as the high computation complexity O(|V|3), the presence of falsepositives due to the maximal planarity constraint, and the inadequacy of the clustering framework. Here, we developed a new coexpression network analysis framework called Multiscale Embedded Gene Coexpression Network Analysis (MEGENA) by: i) introducing quality control of coexpression similarities, ii) parallelizing embedded network construction, and iii) developing a novel clustering technique to identify multiscale clustering structures in Planar Filtered Networks (PFNs). We applied MEGENA to a series of simulated data and the gene expression data in breast carcinoma and lung adenocarcinoma from The Cancer Genome Atlas (TCGA). MEGENA showed improved performance over wellestablished clustering methods and coexpression network construction approaches. MEGENA revealed not only meaningful multiscale organizations of coexpressed gene clusters but also novel targets in breast carcinoma and lung adenocarcinoma.