In this paper, we consider the problem of decoding network coded correlated data when the decoder does not receive sufficient information for exact decoding. We propose an iterative decoding algorithm based on belief propagation that efficiently exploits the data correlation and provides approximate reconstruction of the sources when conventional decoding methods fail. The dependencies among the sources are captured by means of a factor graph. A simple noise model is used in order to describe the pairwise source relationships. The decoding decision is based on MAP estimates that are inferred by message passing over the underlying factor graph. Performance evaluation of the proposed decoding algorithm on correlated data sets consisting of video sequences confirms the efficiency of the proposed algorithm. Simulation results show that high quality reconstruction can be achieved even if significant amount of network coded information is missing at the decoder.