Star-Motifs: Revealing Single-Cell Spatiotypes from Routine Histology Using Star-Convex Neighborhoods

The tumor microenvironment (TME) is a dynamic interplay among cancer, immune, and stromal cells that profoundly influences tumor growth, progression, and treatment response. Although recent spatial transcriptomics and multiplex imaging technologies offer fine-grained insights into the TME, their high cost and lengthy turnaround times limit routine clinical use. In contrast, whole slide images (WSIs) of Hematoxylin and eosin (H&E)-stained are readily available for most patients and provide valuable information about tumor biology. Here, we present a method that explicitly models each cells local neighborhood to identify recurrent spatial patterns, which we call "Star-Motifs." We first encode the local microenvironment of each cell using a "Star-Environment" representation that captures distances and angles to multiple surrounding cell types. We then perform unsupervised clustering of these descriptors to discover distinct Star-Motifs. We validated our method on 1.8 billion cells across 3,105 diagnostic slides from The Cancer Genome Atlas, spanning five distinct cell types: neoplastic, inflammatory, stromal, necrotic, and non-neoplastic. Our method uncovered a diverse range of Star-Motifs, from densely packed tumor clusters to tumor cells surrounded by immune cells (tumor-infiltrating lymphocytes). At the patient level, the relative abundances of these Star-Motifs correlate with patient survival outcomes, immune subtypes, and molecular alterations, offering interpretable, clinically relevant insights. Moreover, classical machine learning models trained on these abundances match or surpass deep learning approaches in predicting overall survival and immune-related biomarkers while remaining interpretable. By capturing higher-order spatial arrangements from routinely available histology slides, Star-Motifs provides a scalable, transparent platform for TME profiling, biomarker discovery, and personalized risk assessment in oncology.