Semantic Compression for Sound and Complete Query Answering Over Knowledge Graphs

To improve storage efficiency, semantic compression approaches filter triples in knowledge graphs (KGs) by mining and applying semantic patterns. However, these approaches typically require full decompression, which limits their practicality. To avoid decompression while keeping the reasoning capacity of KGs, we propose QSC, a queryable semantic compression approach for KGs, enabling sound and complete query answering over compressed KGs without decompression. QSC relies on logical rules and we introduce the notion of first-order rewritable language to express the rules in QSC. Through a first-order rewritable set of rules, a KG can be compressed into another one with fewer triples, while any given query can be rewritten to another query to which the set of answers over the compressed KG is the same as the set of answers to the original query over the original KG. We present a Bayesian optimization-based method for efficiently selecting compression configurations that balance compression and query performance. We also introduce a lightweight redundancy identification mechanism that incrementally filters triples. Compared to the uncompressed baseline, QSC is empirically shown to reduce the number of triples to averagely $\mathbf{7 8} \boldsymbol{\%}, \mathbf{7 6} \boldsymbol{\%}$, and $\mathbf{8 0} \boldsymbol{\%}$ while achieving averagely $\mathbf{0. 8 5} \times$, 0.89×, and 1.08× queries-per-second (QPS) for PostgreSQL, DuckDB and Neo4j, respectively. The code has been open-sourced at https://github.com/ma853529615/QSC.