Understanding movement behaviors is critical for urban mobility and transport problems, including robust path matching, behavior analysis, and anomaly detection. We investigate a graph-based, probabilistic method for matching behaviors of entities operating on networks embedded in some geographic context (e.g., road networks) under different types of uncertainty. Our method uses a decay function that allows network topology and attribute information associated with that topology (geographic or otherwise) to guide generalizations of the activity patterns and model learning process. This allows the system to recognize when two routes within a network are similar, even when those routes share little explicit path information. We demonstrate this method’s robust ability to distinguish between fundamentally different behaviors, even when data are both incomplete and subject to noise. The results show good performance when matching behaviors on different sized and attributed synthetic networks, as well as on a real-world road network; it examines situations in which observed entity behavior is noisy, as well as situations in which observed behaviors differ from learned models as a result of systemic noise in the underlying network. Finally, our approach provides a robust method of detecting anomalous activity patterns on the network.