In this paper, we address the problem of sampling on graphs for change detection in large multi-spectral (MS) and synthetic aperture radar (SAR) images by proposing a graph-based data-driven framework. The main steps of the proposed approach are: (i) the segmentation of regions that enclose the change; (ii) the use of smoothness prior for learning a graph of the regions; (iii) the integration of blue-noise sampling (BN) in the change detection scheme. We validate our approach in 14 real cases of remote sensing according to quantitative analyses. The results confirm that using a structured sampling such as BN outperforms recent state-of-the-art methods in change detection for multimodal data.