The problem of detecting changes with multiple sensors has received significant attention in the literature. In many practical applications such as critical infrastructure monitoring and modeling of disease spread, a useful change propagation model is one where change eventually happens at all sensors, but where not all sensors witness change at the same time instant. While prior work considered the case of known change propagation dynamics, this paper studies a more general setting of unknown change propagation pattern (trajectory). A Bayesian formulation of the problem in both centralized and decentralized settings is studied with the goal of detecting the first time instant at which any sensor witnesses a change. Using the dynamic programming (DP) framework, the optimal solution structure is derived and in the rare change regime, several more practical change detection algorithms are proposed. Under certain conditions, the first-order asymptotic optimality of a proposed algorithm called multichart test is shown as the false alarm probability vanishes. To further reduce the computational complexity, change detection algorithms are proposed based on online estimation of the unknown change propagation pattern. Numerical studies illustrate that the proposed detection techniques offer near-optimal performance. Further, in the decentralized setting, it is shown that if an event-triggered sampling scheme called level-crossing sampling with hysteresis (LCSH) is used for sampling and transmission of local statistics, the detection performance can be significantly improved using the same amount of communication resources compared to the conventional uniform-in-time sampling (US) scheme.