This work presents a robust graph mapping approach for the unsupervised heterogeneous change detection problem in remote sensing imagery. To address the challenge that heterogeneous images cannot be directly compared due to different imaging mechanisms, we take advantage of the fact that the heterogeneous images share the same structure information for the same ground object, which is imaging modality-invariant. The proposed method first constructs a robust K -nearest neighbor graph to represent the structure of each image, and then compares the graphs within the same image domain by means of graph mapping to calculate the forward and backward difference images, which can avoid the confusion of heterogeneous data. Finally, it detects the changes through a Markovian co-segmentation model that can fuse the forward and backward difference images in the segmentation process, which can be solved by the co-graph cut. Once the changed areas are detected by the Markovian co-segmentation, they will be propagated back into the graph construction process to reduce the influence of changed neighbors. This iterative framework makes the graph more robust and thus improves the final detection performance. Experimental results on different data sets confirm the effectiveness of the proposed method. Source code of the proposed method is made available at https://github.com/yulisun/IRG-McS.