Lagrangian relaxation (LR) is an approximate method to estimate the most probable configuration of an intractable MRF. LR is formulated with respect to an augmented graphical model, which includes replicas of the nodes and edges of the original graph. By dualizing the constraint that replicated variables (and, more generally, replicated features) must be equal in any valid assignment, we obtain a relaxed, convex "dual" problem, which is tractable to solve provided the augmented graph has a low tree width. In particular, if the augmented graph is chosen to correspond to a set of spanning trees of the original graph, then we recover essentially the same formalism as in the tree-reweighted max-product approach developed by Martin Wainwright. More generally, we allow relaxations based on small sub-graphs, narrow sub-graphs, "unwound" computation trees and multiscale representations. These extensions can lead to reduced duality gaps and faster convergence in the iterative methods used to solve the dual problem.