# ProvG-Searcher: A Graph Representation Learning Approach for Efficient Provenance Graph Search

arXiv: https://arxiv.org/abs/2309.03647 · HTML: https://mlsanity.com/paper/2309.03647/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2023.

## Built on by (most cited first, 5 of 5)

- [OCR-APT: Reconstructing APT Stories from Audit Logs using Subgraph Anomaly Detection and LLMs](https://mlsanity.com/paper/2510.15188/) (2025)
- [OMNISEC: LLM-Driven Provenance-based Intrusion Detection via Retrieval-Augmented Behavior Prompting](https://mlsanity.com/paper/2503.03108/) (2025)
- [Deep Learning-based Intrusion Detection Systems: A Survey](https://mlsanity.com/paper/2504.07839/) (2025)
- [An End-to-End Framework for Functionality-Embedded Provenance Graph Construction and Threat Interpretation](https://mlsanity.com/paper/2603.17100/) (2026)
- [TGCM: Topic-Guided Consistency Modeling for One-Step Disentanglement of Interleaved APT Technique Sequences](https://mlsanity.com/paper/2606.18651/) (2026)

## Abstract (arXiv)

We present ProvG-Searcher, a novel approach for detecting known APT behaviors within system security logs. Our approach leverages provenance graphs, a comprehensive graph representation of event logs, to capture and depict data provenance relations by mapping system entities as nodes and their interactions as edges. We formulate the task of searching provenance graphs as a subgraph matching problem and employ a graph representation learning method. The central component of our search methodology involves embedding of subgraphs in a vector space where subgraph relationships can be directly evaluated. We achieve this through the use of order embeddings that simplify subgraph matching to straightforward comparisons between a query and precomputed subgraph representations. To address challenges posed by the size and complexity of provenance graphs, we propose a graph partitioning scheme and a behavior-preserving graph reduction method. Overall, our technique offers significant computational efficiency, allowing most of the search computation to be performed offline while incorporating a lightweight comparison step during query execution. Experimental results on standard datasets demonstrate that ProvG-Searcher achieves superior performance, with an accuracy exceeding 99% in detecting query behaviors and a false positive rate of approximately 0.02%, outperforming other approaches.