<p>A major challenge in single-cell RNA sequencing (scRNA-seq) analysis is recovering biologically meaningful cell ontology trees and conserved gene modules across datasets. Data integration and batch-effect correction methods have enabled effective analyses of multiple datasets but often fail to disentangle cell states in heterogeneous samples, such as cancer and the immune system. Here, we present Super Single-Cell Clustering (SuperSCC), a computational framework that utilizes machine learning models to discover cell identities and gene modules across multiple datasets without the need for data integration. Notably, SuperSCC can be implemented at both the cell lineage and cell state levels, thereby allowing the creation of hierarchies of cell programs with specific cell identities and gene modules. This information can be used to identify shared rare populations across datasets regardless of batch effects and has advantages for mapping cell labels from reference to query datasets. We used SuperSCC to perform atlas-level data analysis with more than 90 datasets and built cell state maps of complex tissues, such as the human lung, in healthy and diseased states. SuperSCC outperforms existing approaches in identifying cellular contexts, achieves higher annotation accuracy, and identifies gene modules that indicate conserved immune cell statuses in the lung microenvironment.</p>