We present a new technique of annealing the EM algorithm to allow for its tractable application to fitting models which include graph structures like assignments. The method, which can be generally used to sparsify dependence models, is applied to solve the as- signment problem for the shared-resources Gaussian mixture model (e.g. [4], [5],[9]), and is compared to (and contrasted to) the widely used technique of deterministic annealing (e.g. [8],[2]).