Graphs provide a powerful framework to represent high-dimensional but structured data, and to make inferences about relationships between subsets of the data. In this work we consider graph signals that evolve dynamically according to a heat diffusion process and are subject to persistent perturbations. We develop an online algorithm that is able to learn the underlying graph structure from observations of the signal evolution. The algorithm is adaptive in nature and in particular able to respond to changes in the graph structure and the perturbation statistics.