Interdependent training instances violate the common assumption of independently drawn examples and render classical learning algorithms an inappropriate choice. Collective inference approaches explicitly incorporate these dependencies by translating the examples into a graph where two training instances are connected if their values depend on each other. We present a support vector approach for collective inference allowing for arbitrary dependencies in the data and report on empirical results. Since exact inference for large graphs is infeasible, we integrate an approximate decoding technique based on loopy belief propagation into the optimization problem. We empirically compare versions of the procedure that are based on exact (using the Hugin algorithm) and approximate decoding (loopy belief propagation and others) in terms of accuracy and execution time.