The extracellular matrix (ECM) provides essential structural and biochemical support to tissues, yet its spatial organization is often underrepresented in computational analyses of spatial proteomics. We present Cell-ECM Graphs, a computational framework that integrates ECM and cellular components into a unified graph structure, enabling joint modelling of cell-cell, ECM-ECM, and cell-ECM interactions. Using both simulated and real data, we evaluate performance across interaction profiling, node classification, spatial clustering, and explainable graph neural networks. Incorporating ECM enhances node classification and reveals biologically meaningful spatial patterns, including disrupted immune-ECM connectivity in allergen-exposed lungs. Cell-ECM Graphs offer a novel approach to analysing ECM architecture and its role in shaping the tissue microenvironment in health and disease.