HYPA: Efficient Detection of Path Anomalies in Time Series Data on Networks

Abstract

The unsupervised detection of anomalies in time series data has important applications in user behavioral modeling, fraud detection, and cybersecurity. Anomaly detection has, in fact, been extensively studied in categorical sequences. However, we often have access to time series data that represent paths through networks. Examples include transaction sequences in financial networks, click streams of users in networks of cross-referenced documents, or travel itineraries in transportation networks. To reliably detect anomalies, we must account for the fact that such data contain a large number of independent observations of paths constrained by a graph topology. Moreover, the heterogeneity of real systems rules out frequency-based anomaly detection techniques, which do not account for highly skewed edge and degree statistics. To address this problem, we introduce HYPA, a novel framework for the unsupervised detection of anomalies in large corpora of variable-length temporal paths in a graph. HYPA provides an efficient analytical method to detect paths with anomalous frequencies that result from nodes being traversed in unexpected chronological order.

arXiv comment11 pages with 8 figures and supplementary material. To appear at SIAM Data Mining (SDM 2020)

References in corpus (10)

• Estimating Potential Infection Transmission Routes in Hospital Wards Using Wearable Proximity Sensors
• Memory in network flows and its effects on spreading dynamics and community detection
• Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
• Representing higher-order dependencies in networks
• Modeling sequences and temporal networks with dynamic community structures
• HypTrails: A Bayesian Approach for Comparing Hypotheses About Human Trails on the Web
• From Relational Data to Graphs: Inferring Significant Links using Generalized Hypergeometric Ensembles
• HYPA: Efficient Detection of Path Anomalies in Time Series Data on Networks
• MixedTrails: Bayesian hypothesis comparison on heterogeneous sequential data
• Keeping it Short and Simple: Summarising Complex Event Sequences with Multivariate Patterns

Cited by in corpus (3)

• HYPA: Efficient Detection of Path Anomalies in Time Series Data on Networks
• Predicting Sequences of Traversed Nodes in Graphs using Network Models with Multiple Higher Orders
• Locating Community Smells in Software Development Processes Using Higher-Order Network Centralities