Accurately predicting air quality levels at a fine resolution is a critical task to ensuring the public's health is not at risk. In this work, we construct a graph representation of the road network in Mitcham, London, and model nitrogen dioxide levels using a Gaussian process defined on the vertices of our graph. We introduce a heteroscedastic noise process into our model to capture the complex variations that exist in nitrogen dioxide observations. Defining our model in this way offers superior predictive performance to its spatial analogue. Further, a graph representation allows us to infer the air pollution exposure that an individual would experience on a specific journey and their subsequent risk. We demonstrate this approach for the district of Mitcham, London.