GRAPH REPRESENTATION LEARNING APPROACH FOR EFFICIENT PROVENANCE GRAPH SEARCH

1 . A system for querying large provenance graph repositories comprising:

a server;

a processor; and

a memory storing instructions, which when executed by the processor, cause the processor to

apply an embedding function, and

apply a subgraph prediction function.

2 . The system of claim 1 , wherein the server receives kernel logs.

3 . The system of claim 1 , wherein the embedding function is a learned function that utilizes an inductive graph neural network with an order embedding technique and a max-margin loss, and wherein the embedding function is:

η: G p →R d , that maps each ego-graph G p (G p ⊆ ) to a d-dimensional representation z∈R d , where,

G p : The k-hop ego-graph centered around node p.

: The original provenance graph.

R d : The d-dimensional real vector space.

z: The d-dimensional embedding vector corresponding to the ego-graph G p .

4 . The system of claim 1 , wherein the subgraph prediction function is:

φ: R d ×R d →{0, 1}, where,

R d : The d-dimensional real space in which the embeddings z p and z q are represented.

z p , z q : The d-dimensional embeddings of ego-graphs G p and G q , respectively.

G p , G q : The k-hop ego-graph centered around nodes p and q, respectively.

φ(z p , z q )=1: Indicates that G p is a subgraph of G q .

φ(z p , z q )=0: Indicates that G p is not a subgraph of G q .

5 . A method for querying large provenance graph repositories comprising:

receiving kernel logs from a server;

converting kernel logs to a graph representation;

simplifying the graph representation;

versioning nodes in the graph representation;

partitioning the nodes into overlapping subgraphs; and

identifying a subgraph relation of the overlapping subgraphs.

6 . The method of claim 5 , wherein converting kernel logs to a graph representation comprises applying a converting function, the converting function being:

: → where represents the set of kernel logs, and =( ,ε) represents the graph. A graph is defined as a set of nodes V=v 1 , . . . , v N and a set of edges ε=e 1 , . . . , e M where each node and each edge are associated with a type.

a. Each node v i ∈ is labeled with a system entity identifier and typed based on the nature of the entity it represents, such as a process, file, or network socket.

b. Each directed edge e j ∈ε represents the flow of information between nodes, corresponding to a specific event that occurred, and is labeled with the event type and timestamp.

The converting function processes each kernel log entry l∈ to determine the corresponding nodes and edges in the graph . For a given log entry (l k ), the function identifies the involved system entities, assigns them to nodes in , and maps the system event and timestamp to an edge in ε. Formally, for each log entry l k ∈ , the converting function (f) defines: f(l k )=(v src ,v dst ,e k ) where v src and v dst are the source and destination nodes respectively, corresponding to the entities involved in the edge, and e k is the directed edge with event type and timestamp.

7 . The method of claim 5 , wherein simplifying the graph representation comprises applying a simplifying function, the simplifying function being:

( )=( ′,ε′), where ( =( ,ε)) is the original graph, ( ′⊆ ) and (ε′⊆ε). The function(S) operates by merging nodes and edges based on specific criteria to reduce the complexity of the graph while maintaining the essential temporal dependencies. Specifically:

a. Node Merging: Nodes (v i ) and (v j ) are merged into a single node (v k ) if they represent the same network entity at different time points and their timestamps are within a predefined time window (Δt). Formally,

v k =v i ∪v j if |t i −t j |≤Δt where (t i ) and (t j ) are the timestamps associated with connection events related to (v i ) and (v j ) respectively.

b. Edge Simplification: The edge set (ε′) is derived by aggregating edges that connect merged nodes. If (v i ,v j ) and (v m ,v n ) are edges in (ε) and (v i ) and (v m ) are merged into (v k ), then the edges are simplified to (v k ,v j ) or (v k ,v n ) based on the preservation of the temporal order.

c. Timestamp Propagation: Each merged node (v k ) inherits the earliest timestamp from its constituent nodes to ensure the causal order is preserved. Thus, t k =min (t i ,t j ) when (v k ) is the source node, otherwise t k =max(t i ,t j )

Therefore, the simplified graph ( ′) retains the critical temporal structure of the original graph while reducing its complexity, making it more efficient for further analysis.

8 . The method of claim 5 , wherein versioning nodes in the graph representation comprises applying a versioning function, the versioning function being:

v : × → v where ( ) is the set of nodes, ( ) is the set of timestamps, and ( v ) is the set of versioned nodes. The function ( v ) maps a node (v∈ ) and a timestamp (t∈ ) to a versioned node (v v ∈ v ):

a. Node Update: When node (v) receives new information at time (t), create (v v =(v,t)).

b. Path Consistency: For any path (P) in an ego-graph, edges must have:

t

i

<

t

i

+

1

∀

,

t

i

,

t

i

+

1

∈

𝒯

c. Edge Representation: For an edge (e) between nodes (v v1 =(v 1 ,t 1 )) and (v v2 =(v 2 ,t 2 ): t 1 <t 2

This preserves causal order and temporal integrity in the provenance graph.

9 . The method of claim 5 , wherein partitioning the nodes into overlapping subgraphs comprises applying a partitioning function, the partitioning function being:

P: × ×Z + →{G p |p∈ }, where,

: The set of process nodes in the graph .

: The original provenance graph.

k∈Z + : The depth of the ego-graph.

G p : The k-hop ego-graph centered around the node p, such that:

G p ={v∈ |distance(p, v)≤k} where,

distance(p, v): is the shortest path length between node p and any other node v.

10 . The method of claim 5 , wherein identifying the subgraph relation of the overlapping subgraphs comprises training positive and negative pairs of graphs through an embedding function and a subgraph prediction function.

11 . The system of claim 10 , wherein the embedding function is:

η: G p →R d , that maps each ego-graph (G p ⊆ ) to a d-dimensional representation z∈R d , where,

G p : The k-hop ego-graph centered around node p.

: The original provenance graph.

R d : The d-dimensional real vector space.

z: The d-dimensional embedding vector corresponding to the ego-graph G p .

12 . The system of claim 10 , wherein the subgraph prediction function is:

φ: R d ×R d →{0, 1}, where,

R d : The d-dimensional real space in which the embeddings z P and z Q are represented.

z p , z q : The d-dimensional embeddings of ego-graphs G p and G q , respectively.

G p , G q : The k-hop ego-graph centered around nodes p and q, respectively.

φ(z p , z q )=1: Indicates that G p is a subgraph of G q .

φ(z p , z q )=0: Indicates that G p is not a subgraph of G q .