Air pollution has become a worldwide concern, negatively impacting the popu- lation{\textquoteright}s health and well-being. To mitigate its effects, it is essential to moni- tor pollutant concentrations across regions and time. Traditional solutions rely on physics-driven approaches, leveraging particle motion equations to predict pollu- tants{\textquoteright} shifts in time. Despite being reliable and easy to interpret, they are com- putationally expensive and require background domain knowledge. Alternatively, data-driven approaches, especially deep learning models, significantly reduce the computational expense while providing accurate predictions; yet, at the cost of massive data and storage requirements, lower interpretability and liability issues. This PhD research develops innovative air pollution modelling solutions focusing on high accuracy, generalizability, manageable complexity, and explainability. To this end, the research proposes various graph-based deep learning solutions focusing on two key aspects, namely, physics-guided deep learning and explainability. First, as smart city data is spatially correlated, we propose exploiting it us- ing graph-based deep learning techniques. Specifically, we leverage deep generative models that are efficient in data generation tasks, namely, variational graph au- toencoders. The proposed models employ graph convolutional operations and data fusion techniques to leverage the graph structure and the multi-modality of the data at hand. Additionally, we design physics-guided deep-learning models that follow well-studied physical equations. By updating the operator of graph convolutional networks to leverage the convection-diffusion equation, we can physically guide the learning curve of our network. The second key contribution relates to novel ex- plainability techniques for graph deep learning. We explore existing explainability techniques, and effectively design explanation tools that are specifically-tailored for graph-based architectures using Lasso- and a LRP-based techniques. Our expla- nation techniques are able to provide insights and visualizations based on various input data sources, such as the graph structure and the node features. Overall, the research has produced state-of-the-art models that combine the best of physics-guided, graph deep learning and explainable approaches for inferring and explaining air pollution. The developed techniques can also be deployed in modelling graphs on the Internet, such as recommender systems applications.