Air pollution has become a world-wide concern due to its negative impact on the population's health and well-being. To mitigate its effects, it is essential to accurately monitor pollutant concentrations across regions and time. Traditional solutions rely on physics-driven approaches, leveraging equations of particle motion to predict pollutants’ shift in time. Despite being reliable and easy-to-interpret, they are computationally highly expensive. Recent works have shown that following a deep-learning data-driven approach significantly reduces the computational expenses and provides accurate predictions; yet, at the cost of lower interpretability. This PhD aims to develop innovative air pollution monitoring solutions with high accuracy, manageable complexity and high interpretability. To this end, the focus will be put on physics-guided deep learning approaches, that is, to design deep-learning-based models following well-studied physical equations. With this purpose, graph convolutional networks (GCNs) and recurrent neural networks (RNNs) will be leveraged. In addition, innovative data fusion techniques will be incorporated into the models to merge data from multiple modalities. The research is envisioned to produce state-of-the-art models that combine the best of both physics- and deep-learning-based approaches for monitoring air pollution. The developed techniques, based on GCNs and RNNs, could also lead to various applications in modelling other natural processes such as weather prediction and water monitoring, and applications on the Internet such as recommender systems or fake news analysis.