In this paper a new formulation of probabilistic relaxation labeling is developed using the theory of diffusion processes on graphs. According to this picture, the label probabilities are given by the state-vector of a continuous time random walk on a support graph. The state-vector is the solution of the heat equation on the support-graph. The nodes of the support graph are the Cartesian product of the object-set and label-set of the relaxation process. The compatibility functions are combined in the weight matrix of the support graph. The solution of the heat-equation is found by exponentiating the eigensystem of the Laplacian matrix for the weighted support graph with time. We demonstrate the new relaxation process on a feature correspondence matching problem abstracted in terms of relational graphs.