Privacy-Preserving Analytics on Outsourced Streaming Graphs: The Case of Pattern Detection

Streaming graphs widely exist in various application domains due to their excellent capability to capture temporal relationships between different entities. In recent years, outsourcing streaming graphs to the cloud for storage and analytics has become increasingly popular. Among others, pattern detection on streaming graphs, which aims to continuously detect subgraphs matching a given query pattern, benefits practical applications like credit card fraud detection and cyber-attack detection. However, conducting such streaming graph analytics in the cloud also raises critical privacy concerns. This paper introduces GraphGuard, the first system aimed at privacy-preserving pattern detection on outsourced streaming graphs. GraphGuard is designed through a tailored synergy of insights from graph modeling, lightweight secret sharing, edge differential privacy, and data encoding/padding. It conceals edge and vertex labels, as well as the relationship between vertices, for both the outsourced streaming graph and query pattern. We implement GraphGuard and perform comprehensive performance evaluations. The results show that GraphGuard is able to securely perform one detection on a streaming graph’s snapshot (with a sliding time window of size 50,000) in just a few seconds. In comparison to a baseline utilizing general secure multiparty computation techniques, GraphGuard is up to 60× faster in query latency and achieves up to 98% savings in communication. © 1989-2012 IEEE.