Factored Score Matching on Graphical Models: Exact Computation on Trees and Convergent Approximation on Loopy Graphs

Score-based diffusion models learn to reverse a Gaussian noising process by estimating the score of the noisy data distribution at each noise level. For high-dimensional structured data—graphs, molecules, spatial networks—the score is typically approximated with a global neural network that ignores the conditional independence structure of the data. We show that when the data distribution is a Markov random field (MRF) with a known factor graph $G$, the score of the corresponding noisy distribution can be computed exactly on tree-structured $G$ via a message-passing algorithm with depth equal to the diameter of $G$, and approximately on loopy graphs with error decaying geometrically in the MPNN depth at rate $\kappa^L$, where $\kappa < 1$ is the Dobrushin contractivity constant of the MRF. We prove both results rigorously and show that $\kappa_t \to 0$ as the noise level $t$ increases, making loopy approximations progressively more accurate. We instantiate these findings in FSGM (Factored Score Generative Model), a score-based diffusion model whose score network is a message-passing neural network parameterised to respect the factor graph of the data. On the QM9 molecular benchmark, FSGM with depth $L = 6$ achieves $93.8\%$ validity, $97.1\%$ uniqueness, and FCD $2.89$, matching or surpassing the full-attention DiGress baseline while requiring fewer parameters and admitting interpretable inductive biases.