In this paper we propose a novel approach to define task-driven regularization constraints in deformable image registration using learned deformation priors. Our method consists of representing deformation through a set of control points and an interpolation strategy. Then, using a training set of images and the corresponding deformations we seek for a weakly connected graph on the control points where edges define the prior knowledge on the deformation. This graph is obtained using a clustering technique which models the co-dependencies between the displacements of the control points. The resulting classification is used to encode regularization constraints through connections between cluster centers and cluster elements. Additionally, the global structure of the deformation is encoded through a fully connected graph on the cluster centers. Then, registration of a new pair of images consists of displacing the set of control points where on top of conventional image correspondence costs, we introduce costs that are based on the relative deformation of two control points with respect to the learned deformation. The resulting paradigm is implemented using a discrete Markov Random Field which is optimized using efficient linear programming. Promising experimental results on synthetic and real data demonstrate the potential of our approach.