ProvGrapher: A Top-K Approximate Tuple-Level Data Provenance Framework via Graph Neural Network

With the explosive growth of data scale, traditional annotation-based tuple-level data provenance methods face escalating challenges in storage overhead and inference efficiency. Recent vectorized approximate approaches for non-aggregate queries embed tuples into continuous spaces and infer lineage via vector similarity, improving scalability at the expense of some accuracy. However, these methods rely solely on tuple text to construct static representations, overlooking relational structures and query semantics, which limits provenance accuracy and generalization. To address this, we propose ProvGrapher, a graph-structured modeling approach for Top-K approximate tuple-level data provenance. ProvGrapher constructs data provenance graphs and integrates a Gated Multi-scale Multi-head Graph Attention Encoder (MSMH-GAT) with re-ranking optimization, which effectively capturing both table structures and query-driven data flow semantics to learn high-quality tuple embeddings. Experiments on the Olist and Movielens datasets, covering both single-table and multi-table SQL query scenarios, demonstrate that ProvGrapher consistently outperforms existing methods in terms of provenance coverage and ranking quality, while maintaining robustness with increasing data scale. Ablation studies further validate the effectiveness of key components including graph compression, gated multi-scale multi-head attention, and re-ranking. ProvGrapher provides a practical and scalable solution for approximate tuple-level data provenance in complex environments.