Using Hypervectors for Efficient Anomaly Detection in Graph Streams

We present an online algorithm for detecting changes in computer network activity. Anomalous activity in IT systems often appear as changes in network topology as edges evolve in a dynamic graph; identifying these behavioral changes can be a challenging task. We propose a method that uses principles of Hyperdimensional Computing to encode graphs to a real valued space where anomalies are easily identifiable. With reasonable assumptions of the baseline edge generating process, our approach operates in real time and can produce an anomaly score primitive for one sample independently of all others. This score lends itself easily to an online Bayesian confidence estimate in constant memory, which is essential for real-world applications where networks are extremely large and interpretable predictions are needed in real time. We demonstrate the effectiveness of our approach on both synthetic and real-world datasets.