We consider the problem of inferring the hidden structure of high-dimensional dynamic systems from the perspective of graph learning. In particular, we aim at capturing the dynamic relationships between nodes by a sequence of graphs. Our approach is motivated by the observation that imposing a meaningful graph topology to the data decreases the number of samples necessary to learn meaningful structures. To regularize learning and improve performance on dynamic graphs, we introduce a new prior that asserts that the graph edges change smoothly in time. We propose a primal-dual optimization algorithm that scales linearly with the number of allowed edges and is easy to parallelize. Our new model is shown to outperform standard graph learning and other baselines both on a synthetic and a real dataset.