The tumor microenvironment is widely recognized for its central role in driving cancer progression and influencing prognostic outcomes. Despite extensive research efforts dedicated to characterizing this complex and heterogeneous environment, considerable challenges persist. In this study, we introduce a novel data-driven approach for identifying tumor microenvironment patterns that, we show, are closely tied to patient prognoses. Our methodology relies on the construction of a bi-level graph model: (i) a cellular graph, which models the intricate tumor microenvironments, and (ii) a population graph that captures inter-patient similarities, given their respective cellular graphs, by means of a soft Weisfeiler-Lehman kernel. This systematic integration of information across different scales enables us to identify patient subgroups exhibiting unique prognoses while unveiling certain tumor microenvironment patterns that characterize them. We demonstrate our approach in a cohort of breast cancer patients, identify crucial tumor microenvironment patterns associated with patient prognosis, and validate these patterns in a completely independent cohort. Our study provides valuable insights into the prognostic implications of the breast tumor microenvironment, and this methodology holds the potential to analyze other cancers.