Source-linked AI summary
Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs
Emaad A. Manzoor, Sadegh Momeni, Venkat N. Venkatakrishnan, Leman Akoglu
TL;DR
Detecting anomalous heterogeneous graphs in real time from an unbounded stream while using bounded memory is motivated by host-level APT detection. StreamSpot combines shingle-based graph similarity, sketches, and online clustering, and the paper reports over 90% average precision while processing more than 100,000 edges per second.
Problem
How to detect anomalous heterogeneous graphs in real time from a stream using bounded memory matters for applications such as host-level APT detection.
Source: §1 · p. 1Method
Results
Over 90% average precision for the course of the stream, with performance sustained under strict memory constraints and processing over 100,000 edges per second.
Source: §7 · p. 10Takeaways & Limitations
StreamSpot ranks incoming heterogeneous graphs by anomalousness throughout a stream, including under strict memory constraints.
Source: §7 · p. 10The stated scope requires timestamped typed edges and online similarity updates with bounded space for an infinite stream.
Source: §3 · p. 3
Abstract
from arXiv · showhide
Given a stream of heterogeneous graphs containing different types of nodes and edges, how can we spot anomalous ones in real-time while consuming bounded memory? This problem is motivated by and generalizes from its application in security to host-level advanced persistent threat (APT) detection. We propose StreamSpot, a clustering based anomaly detection approach that addresses challenges in two key fronts: (1) heterogeneity, and (2) streaming nature. We introduce a new similarity function for heterogeneous graphs that compares two graphs based on their relative frequency of local substructures, represented as short strings. This function lends itself to a vector representation of a graph, which is (a) fast to compute, and (b) amenable to a sketched version with bounded size that preserves similarity. StreamSpot exhibits desirable properties that a streaming application requires---it is (i) fully-streaming; processing the stream one edge at a time as it arrives, (ii) memory-efficient; requiring constant space for the sketches and the clustering, (iii) fast; taking constant time to update the graph sketches and the cluster summaries that can process over 100K edges per second, and (iv) online; scoring and flagging anomalies in real time. Experiments on datasets containing simulated system-call flow graphs from normal browser activity and various attack scenarios (ground truth) show that our proposed StreamSpot is high-performance; achieving above 95% detection accuracy with small delay, as well as competitive time and memory usage.
1. INTRODUCTION
StreamSpot targets real-time anomaly detection in interleaved streams of typed graph edges under bounded-memory constraints. It uses shingling-based graph sketches and incrementally maintained clustering to score and flag anomalous graphs online.
Problem setting
- The task is to identify graphs significantly different from prior observations in a stream where timestamped typed edges from multiple graphs may be interleaved.Detection must be fast and real-time while using bounded memory.Source: §1 · p. 1
Motivation
- The motivating application is host-level APT detection, where typed information-flow graphs represent system events and malicious activity is assumed to differ sufficiently from normal behavior.The system-call events arrive rapidly, making low-overhead, real-time processing important.Source: §1 · p. 1
Related work
Contributions
- StreamSpot compares typed graphs using shingling-based substructure frequencies, fixed-memory sketches that preserve similarity, and dynamically maintained centroid-based clustering to score and flag anomalies.The sketches and clustering are updated as new edges arrive.Source: §1 · p. 2
- StreamSpot is designed for continuous edge-level processing, constant-complexity sketch and clustering updates, user-controlled constant memory, and real-time anomaly scoring.These properties avoid snapshot-oriented processing while supporting online detection.Source: §1 · p. 2
Evaluation
- Experiments quantitatively evaluate StreamSpot’s effectiveness and time and space efficiency on simulated normal host activity and attack scenarios, and examine sketch approximation and parameter variation.The attack scenarios provide ground truth, and memory size is among the varying parameters.Source: §1 · p. 2
2. PROBLEM & OVERVIEW
StreamSpot detects anomalies in real time by maintaining bounded-memory representations of evolving heterogeneous information-flow graphs and dynamically clustering them. Its approach combines shingle-based graph similarity, compact sketches, and centroid-based anomaly scoring.
Streaming heterogeneous graphs
- Host logs yield typed information-flow graphs whose timestamped edges carry endpoint IDs and types, edge type, and flow tag; edges from multiple evolving flows may interleave.Edge types correspond to system calls, while node types include objects such as sockets, files, and memory.Source: §2 · p. 2, Figure 1 · p. 2
Similarity of heterogeneous graphs
- StreamSpot represents each graph with a shingle-frequency vector counting strings formed by temporally ordered traversals of k-hop neighborhoods, and compares graphs by cosine similarity.Graphs with more shingles in common are more similar.Source: §2 · p. 2
Memory-efficient sketches
- Constant-size sketches approximate shingle-vector cosine similarity, avoiding the potentially unbounded number of unique shingles in heterogeneous graphs.Similarity between sketches approximates similarity between the original shingle vectors.Source: §2 · p. 2
Efficient maintenance of sketches
- Each arriving edge updates its graph’s sketch in constant time without additional memory overhead.The shingle vector is not explicitly maintained in memory.Source: §2 · p. 2
Clustering and anomaly detection
- Dynamic centroid clustering captures normal behavior, while distance to the nearest centroid and the cluster’s distance distribution support real-time anomaly scoring and flagging.The clustering is updated as graphs evolve or new graphs arrive.Source: §2 · pp. 2–3
3. SKETCHING TYPED GRAPHS
The section develops a bounded-space representation of heterogeneous graphs that preserves local structure and edge order while supporting online updates. It builds from ordered k-shingle frequency vectors to L-bit sketches, then describes incremental maintenance and controllable time and space costs.
3. SKETCHING TYPED GRAPHS
- The representation must capture edge order, support efficient online updates, and use bounded space; prior approaches fail these requirements through correspondence needs, fixed substructure spaces, global metrics, or heuristic edit-distance steps.StreamSpot’s shingling-based representation is designed to capture local structure and temporal order without storing all possible substructures.Source: §3 · p. 3
3.1 Graph Similarity by Shingling
- Each node’s k-shingle records its type and, in timestamp order, the edge and destination-node types encountered in a directed k-hop traversal; graph similarity is cosine similarity between shingle-frequency vectors.The parameter k trades expressiveness of local neighborhoods against the number of vector entries updated per incoming edge.Source: §3.1 · p. 3
3.2 Graph Sketches by Hashing
- The shingle universe can grow combinatorially with node and edge types, making its full frequency vectors infeasible to store; locality-sensitive hashing provides a constant-space approximation.LSH projects high-dimensional vectors to a lower-dimensional space while preserving similarity.Source: §3.2 · p. 3
3.2.1 SimHash
- SimHash uses random Gaussian projection vectors and maps each input vector to L signs; the fraction of agreeing hash values estimates cosine similarity.Each graph can be represented by an L-bit sketch instead of retaining its full shingle vector.Source: §3.2.1 · pp. 3–4
3.2.2 Simplified SimHash
- Simplified SimHash draws projection-vector entries from {+1, −1}, but remains unsuitable for streaming because it requires explicit vectors, a known shingle-universe size, and potentially huge dimensions.The simplification reduces each projection vector’s storage to |S| bits rather than 32·|S| bits, assuming four bytes per float.Source: §3.2.2 · p. 4
3.2.3 StreamHash
- StreamHash replaces explicit random projection vectors with L random hash functions on shingles, enabling incremental L-bit sketches without storing the full shingle universe.Each projection coordinate sums shingle counts hashed to +1 minus those hashed to −1; the sketch is the sign of that projection vector.Source: §3.2.3 · p. 4
3.3 Maintaining Sketches Incrementally
- For each new edge, StreamSpot updates shingles for nodes that can reach its destination within k hops, adding incoming shingles and removing outgoing ones.The affected shingles are constructed with modified ordered k-hop breadth-first traversals, and their hash values update projection coordinates and sketch bits when signs change.Source: §3.3 · p. 5
3.4 Time and Space Complexity
- Sketch updates take O(L+|s|max^2) time per edge, while total space is O(cL+N) under a cap of N retained edges and c in-memory graphs.When memory exceeds N edges, the oldest edge incident on the least recently touched node is evicted; L controls similarity approximation quality.Source: §3.4 · p. 5
4. ANOMALY DETECTION
StreamSpot bootstraps clusters from benign flow-graphs, then updates graph and cluster representations as edges arrive to assign graphs to clusters or an attack class. It scores each graph by its distance to the nearest cluster centroid.
Bootstrap Clusters
- Benign training flow-graphs are clustered by K-medoids with K selected by silhouette coefficient, and each cluster’s threshold is set three standard deviations above its mean distance.The threshold is derived from Cantelli’s inequality with an upper bound of 10% on the false positive rate.Source: §4 · p. 6
- Each cluster centroid is the average of its training graphs’ projection vectors; StreamSpot sketches the centroids and discards the bootstrap graphs from memory.The centroid represents the union of member graphs’ shingle-vector counts divided by the number of graphs.Source: §4 · p. 6
Streaming Cluster Maintenance
- Each arriving edge updates the graph sketch and projection; StreamSpot compares against the nearest centroid, updates cluster membership within threshold, and assigns out-of-threshold graphs to the attack class.Cluster sizes and projection vectors are updated when graphs are added, retained, or moved between clusters.Source: §4 · p. 6
- After updating the nearest cluster centroid, StreamSpot scores a graph by its distance to that centroid; nearest-cluster search takes O(KL) time and scoring takes O(L) time.Source: §4 · p. 6, Time and Space Complexity · p. 6
Time and Space Complexity.
StreamSpot updates each edge in O(KL) time and uses O(c + KL) space for clustering and anomaly detection.
Time complexity
- Each edge requires O(KL) time to update a cluster and perform the associated computation.Updating a cluster and the operation in Eq. (16) each take O(L) time.Source: Time and Space Complexity · p. 6
Space complexity
- Clustering and anomaly detection use O(c + KL) space when at most c graphs are retained.Cluster assignments and anomaly scores require O(c) space; centroid sketches and projection vectors require O(KL).Source: Time and Space Complexity · p. 6
5. EVALUATION
Across simulated system-call flow-graphs, StreamSpot ranks attack graphs effectively in static and streaming tests, while retaining performance under memory constraints and processing edges at high throughput.
5. EVALUATION
- The evaluation used flow-graphs from five benign scenarios and one drive-by-download attack, and tested both offline static ranking and edge-by-edge streaming initialized with bootstrap clustering.Streaming tests retained anomaly-score snapshots every 10,000 edges and also constrained sketch size and stored edges.Source: §5 · p. 6
5.1 Static Evaluation
- On test data (attacks and remaining 25% benign graphs), StreamSpot achieved near-ideal performance with C = 25, 100, 50 and K = 5, 5, 10 for YDC, GFC, ALL; average precision appeared robust to cluster count in the safe region.The safe region for C is near and to the right of the point of maximum pairwise-distance entropy.Source: §5.1 · p. 7
- With 25% of the data for training, static StreamSpot achieved AP above 0.9 and near-ideal AUC across the datasets.Curves were averaged over 10 independent random samples.Source: Figure 7 · p. 7, §5.1 · p. 7
5.2 Streaming Evaluation
- Streaming rankings dip as new graph groups arrive but recover quickly to near-ideal attack ranking; dips lessen as clustering matures, while threshold errors are false negatives.Similar results are reported for B = 50; the streamed scores are evaluated every 10,000 edges.Source: Figure 10 · p. 8, §5.2 · p. 8, Figure 9 · p. 8
- With L = 100, streaming performance is as good as with L = 1000, and remains reasonable at L = 10; restricting stored edges reduces performance only slightly but lengthens recovery.Performance is reported as robust across a wide range of sketch sizes and memory limits, with stable end-of-stream results.Source: Figure 11 · p. 8, §5.2 · p. 8, Figure 12 · p. 9
- At L = 100, StreamSpot processes over 100,000 edges per second; at L = 1000, it processes more than 14,000 edges per second with per-edge runtime under 70 microseconds.Sketch updates dominate runtime; L = 100 produces comparable performance to the larger sketch.Source: §5.2 · pp. 8–9, Figure 14 · p. 9
- At L = 1000 and N = 12.5M stored edges, StreamSpot used 240 MB overall; graph memory grew with N, while projection vectors used 32 times the sketch-vector memory.The reported memory result is for the ALL dataset.Source: Table 2 · p. 9, §5.2 · p. 9
6. RELATED WORK
The related work spans graph similarity, typed-graph anomaly detection, streaming graph analysis, and graph sketches; prior approaches face constraints involving edge order, static data, or task-specific representations.
Graph similarity
- Prior graph-similarity methods require node correspondence or use global metrics that miss edge order; GED is NP-hard, while graph kernels require a fixed substructure universe.GED is often approximated with local-search heuristics that provide no error bound.Source: §6 · p. 9
Heterogeneous/typed graphs
Streaming graphs
- Streaming methods include GMicro, which clustered untyped graph streams using a centroid-based approach and edge-frequency distance, GOutlier’s reservoir sampling for unlikely-edge anomalies, and Classy’s approximate GED for call-graph clustering.Source: §6 · pp. 9–10
Graph sketches and compact representations
- Graph skeletons and sketches approximate specific graph tasks with error bounds, but existing sketches cannot directly detect graph-based anomalies.Source: §6 · p. 10
7. CONCLUSION
StreamSpot summarizes and clusters evolving heterogeneous graphs from typed-edge streams using bounded-memory, online updates. It ranks anomalous graphs in real time and applies beyond APT detection to other streams of typed graphs.
7. CONCLUSION
- StreamSpot achieves over 90% average precision throughout the stream while processing over 100,000 edges per second, with performance sustained under strict memory constraints.Its summaries use bounded memory.Source: §7 · p. 10
- StreamSpot represents heterogeneous ordered graphs by shingling and uses StreamHash for online summaries with constant-time updates and bounded memory.Mergeable summaries support online centroid-based clustering and anomaly ranking as new graphs emerge and existing graphs evolve.Source: §7 · p. 10
- Beyond APT detection from system-log streams, StreamSpot applies to event detection in sentence streams and anomaly detection in streams of chemical compounds or protein structure elements.These applications represent sentences as syntax trees and process typed graphs arriving as edge streams.Source: §7 · p. 10