<p>Smart cities, as a constantly evolving field, offer numerous opportunities for advancement and innovation. In particular, more and more specific sectors within smart cities currently require increased attention and development. Notably, the integration of emerging technologies holds promise for significant progress in efficiency and management across various urban issues, with urban waste management being a key focus of this research. In this paper, we propose a new methodology for intelligent waste management combining graph-based modeling and advanced machine learning techniques. A case study of a municipality in the Melbourne area (Australia) is examined, where smart bins equipped with fill-level sensors have been deployed, and their data made publicly accessible. The core of this investigation lies in utilizing sophisticated machine learning models, including Long Short-Term Memory (LSTM) and Gated Recurrent Unit (GRU), for predicting bin fill levels. Additionally, we introduce a graph-based spatial representation in which bins are modeled as nodes of a weighted graph, and graph embedding techniques are employed to capture and encode spatial dependencies among them. The findings validate the effectiveness of the proposed methodology, achieving a Mean Absolute Error (MAE) of 0.16, a Root Mean Squared Error (RMSE) of 0.21, a Mean Squared Error (MSE) of 0.044, and an R² of 0.83, which outperforms the reference baseline. Our results highlight how the integration of spatial information through graph embedding holds promise for improving predictions in smart waste management. Furthermore, the study suggests a transferable methodological framework, applicable at the architectural level to smart city challenges where spatially distributed entities exhibit interdependent temporal dynamics, pending empirical validation across further domains and cities.</p>