A Stability-Aware Consensus Framework for Urban Anomaly Discovery in Multi-Relational POI Graphs

Urban anomalies such as rare facilities, unusual spatial configurations, and atypical functional patterns can provide valuable insights into urban dynamics and planning processes. However, graph-based anomaly discovery methods often suffer from instability, producing substantially different results across training runs and making the detected anomalies difficult to reproduce and interpret. In this paper, we use the term anomaly to denote automatically detected abnormal urban entities, while the term urban irregularity refers to their interpretation within the urban context. We present a consensus-driven framework for stable anomaly discovery using multi-relational point-of-interest (POI) graphs. Urban facilities are represented as nodes connected through multiple spatial and semantic relations, including geographic proximity, shared categories, shared facility types, and region-based associations. Four graph autoencoder architectures (GAE, ResGAE, VGAE, and SAGEAE) are employed to learn node representations, while reconstruction-, cluster-, neighborhood-, and relation-based anomaly scoring strategies are combined with multi-seed stability analysis to identify consensus anomalies. Experiments conducted on five large-scale cities (Baku, Turin, Vienna, Prague, and Kuala Lumpur) show that the proposed framework identifies recurring anomaly patterns across repeated runs and analytical configurations. Comparisons with representative anomaly detectors reveal partial but method-dependent overlap, while cross-city control experiments indicate that a subset of the detected anomalies exhibits non-random semantic and structural correspondence across different urban environments. Additional analyses suggest that consensus anomalies are frequently associated with semantically distinctive urban entities, including recreational areas, utility infrastructure, institutional facilities, specialized services, and cultural landmarks. Overall, the results indicate that stability-aware consensus provides a more reproducible and consistent basis for graph-based urban anomaly discovery and supports the interpretation of recurrent anomaly patterns in large-scale urban POI graphs, without requiring ground-truth anomaly labels.