Sankofa: Online Query-Adaptive Dynamic Graph Summaries

Abstract

Knowledge Graphs (KGs) model semantic relationships between entities and are widely used in tasks such as question answering, recommendation, and large language model training. As KGs grow to billions of triples, storing and querying them on local devices becomes infeasible and also raises privacy concerns. KG summarization methods produce compact representations, yet existing methods are either static or not attuned to user interests. In this paper, we propose Sankofa, a query-adaptive, incremental, and online KG summarization method. Sankofa maintains personalized summaries on-device by incrementally updating them in response to new queries and data using a random-walk-based adaptation of node-centric Personalized PageRank, efficiently identifying the most relevant nodes while bounding summary size. We provide formal guarantees for our PPR approximation and demonstrate experimentally that Sankofa outperforms existing personalized KG summarization techniques in speed and accuracy, enabling adaptive, privacy-preserving KG summaries that evolve with user interests on dynamic knowledge graphs.