Introduction
Traditional network analysis often relies on First-Order Networks (FONs), which operate under the Markovian assumption: the future state of a system depends solely on its current state. While this simplification makes many problems tractable, it fails to capture the complex, non-Markovian dependencies inherent in real-world sequential data, such as maritime trajectories, taxi movements, or web clickstreams. This paper introduces BuildHON+, a scalable and parameter-free algorithm designed to represent these systems as Higher-Order Networks (HONs), enabling the detection of anomalies that are invisible to traditional models.
The Markovian Limitation and the "Invisible" Anomaly
In a FON, if a user moves from a "Weather" page to a "News" page, the model assumes the next destination is independent of how the user reached the "Weather" page. However, real-world behavior is often path-dependent. When we aggregate these sequences into a FON, we lose the "sequential flow."
A critical insight of this research is the existence of "invisible" anomalies. These occur when the aggregate traffic between nodes (the first-order topology) remains constant, but the underlying sequential patterns change. For example, if the total number of people moving from point A to point B stays the same, but the proportion of those coming from point C versus point D flips, a FON will detect no change. HONs, by contrast, make these "ghost" signals visible by explicitly modeling the history of movement.
The BuildHON+ Algorithm
BuildHON+ improves upon previous iterations by focusing on scalability and ease of use. Key technical innovations include:
- Lazy Construction: Rather than exhaustively searching all possible dependencies up to a fixed limit, BuildHON+ only explores higher-order rules when the data indicates a significant deviation from lower-order patterns.
- Parameter-Free Discovery: The algorithm removes the need for manual tuning of parameters like
MaxOrderorMinSupport. It utilizes a dynamic threshold based on Kullback–Leibler (KL) divergence to determine when a higher-order rule is statistically significant and when to stop growing the rule. - Indexing Cache: To manage massive datasets, the algorithm employs a hash-table-based indexing cache, allowing for rapid n-gram lookups without repeated traversals of the raw data.
Experimental Evaluation
The authors evaluated BuildHON+ across three diverse datasets:
- Global Ship Movement: Analyzing three years of voyages (4.7 million records) to test scalability and the ability to identify dependencies up to the 11th order.
- Synthetic Taxi Data: A massive dataset of 11 billion movements on a grid, injected with 10 specific anomalies (changes in 1st, 2nd, and 3rd-order rules).
- Real-World Porto Taxi Data: GPS trajectories from 442 taxis over one year, used to detect behavioral shifts during local festivals.
Key Results and Impact
The transition from FON to HON yields significant improvements in both performance and detection sensitivity:
- Efficiency: BuildHON+ achieved a 4.5x speedup and used 7.2x less memory than its predecessor on large-scale maritime data. It successfully extracted dependencies up to the 11th order in under two minutes.
- Detection Accuracy: On synthetic data, traditional FON-based methods detected at most 4 out of 10 anomalies. The HON-based approach successfully identified all 10 anomalies using standard distance metrics.
- Real-World Application: In the Porto taxi dataset, BuildHON+ identified significant shifts during the "Burning of the Ribbons" festival. While the number of first-order nodes remained stable, a spike in second- and third-order nodes revealed the emergence of event-specific navigation patterns.
Conclusion and Future Work
By representing complex systems as HONs, researchers can apply existing network distance metrics to achieve far greater sensitivity in anomaly detection. While BuildHON+ excels at detection, future work aims to classify the types of anomalies detected and develop distance measures that better account for the hierarchical nature of higher-order nodes. This framework paves the way for more robust monitoring of dynamic, path-dependent systems across various domains.
Summary updated