Accelerating Dependency Graph Learning from Heterogeneous Categorical Event Streams via Knowledge Transfer
Chen Luo Zhengzhang Chen Lu-An Tang Anshumali Shrivastava Zhichun Li












The work was done when the first author was on an internship at NECLA.


  Rice University

  Houston 
  Texas 


cl67@rice.edu




  NEC Labs America

  Princeton 
  New Jersey 


zchen@nec-labs.com




  NEC Labs America

  Princeton 
  New Jersey 


ltang@nec-labs.com




  Rice University

  Houston 
  Texas 


anshumali@rice.edu




  NEC Labs America

  Princeton 
  New Jersey 


zhichun@nec-labs.com






Dependency graph, as a heterogeneous graph representing the intrinsic relationships between different pairs of system entities, is essential to many data analysis applications, such as root cause diagnosis, intrusion detection, etc. Given a well-trained dependency graph from a source domain and an immature dependency graph from a target domain, how can we extract the entity and dependency knowledge from the source to enhance the target? One way is to directly apply a mature dependency graph learned from a source domain to the target domain. But due to the domain variety problem, directly using the source dependency graph often can not achieve good performance. Traditional transfer learning methods mainly focus on numerical data and are not applicable.






In this paper, we propose , a knowledge transfer based model for accelerating dependency graph learning from heterogeneous categorical event streams. In particular, we first propose an entity estimation model toestimate the probability of each source domain entity that can be included in the final dependency graph of the target domain. by utilizing source domain heterogeneous relations from the categorical event streams. Then, we propose a domain adaptation model to construct the dependency relationships for the target domain graph. filter out irrelevant entities from the source domain based on entity embedding and manifold learning. Only the entities with statistically high correlations are transferred to the target domain. On the surviving entities, we propose a dependency construction model for constructing the unbiased dependency relationships by solving a two-constraint optimization problem.  The experimental results on synthetic and real-world datasets demonstrate the effectiveness and efficiency of . 
We also apply  to a real enterprise security system for intrusion detection. 
Our method is able to achieve superior detection performance at least 20 days lead lag time in advance with more than 70% accuracy.




































 




Accelerating Dependency Graph Learning from Heterogeneous Categorical Event Streams via Knowledge Transfer
    Zhichun Li
    
==========================================================================================================





§ INTRODUCTION


The heterogeneous categorical event data are ubiquitous. 
Consider system surveillance data in enterprise networks, where each data point is a system event that involves heterogeneous types of entities: time, user, source process, destination process, and so on. 
Mining such event data is a challenging task due to the unique characteristics of the data: (1) the exponentially large event space. For example, in a typical enterprise network, hundreds (or thousands) of hosts incessantly generate operational data. A single host normally generates more than 10,000 events per second; And (2) the data varieties and dynamics. The variety of system entity types may necessitate high-dimensional features in subsequent processing, and the event data may changing dramatically over time, especially considering the heterogeneous categorical event streams <cit.>. 



To address the above challenges, the recent studies of dependency graphs <cit.> have witnessed a growing interest. Such dependency graphs can be applied to model a variety of systems including enterprise networks <cit.>, societies <cit.>, ecosystems <cit.>, etc. For instance, we can present an enterprise network as a dependency graph, with nodes representing system entities of processes, files, or network sockets, and edges representing the system events between entities (e.g., a process reads a file). 
This enterprise system dependency graph can be applied to many forensic analysis tasks such as intrusion detection, risk analysis, and root cause diagnosis <cit.>.
A social network can also be modeled as a dependency graph representing the social interactions between different users.
Then, this social dependency graph can be used for user behavior analysis or abnormal user detection <cit.>.






 


However, due to the aforementioned data characteristics, learning a mature dependency graph from heterogeneous categorical event streams often requires a long period of time. 

For instance, the dependency graph of an enterprise network needs to be trained for several weeks before it can be applied for intrusion detection or risk analysis as illustrated in Fig. <ref>.

Furthermore, every time, when the system is deployed in a new environment, we need to rebuild the entire dependency graph. 
This process is both time and resource consuming.

Enlightened by the cloud services <cit.>, 
one way to avoid the time-consuming rebuilding process is by reusing a unified dependency graph model in different domains/environments.
However, due to the domain variety, directly apply the dependency graph learned from an old domain to a new domain often can not achieve good performance. 
For example, the enterprise network from an IT company (active environment) is very different from the enterprise network from an electric company (stable environment). Thus, the enterprise dependency graph of the IT company contains many unique system entities that can not be found in the dependency graph of the electric company. 
Nevertheless, there are still a lot of room for transfer learning.
Directly deploy the model learned from one environment to a new environment will suffered from the domain differences. 
Our experiment in Section <ref> demonstrate the impracticable of direct reuse.

Transfer learning has shed light on how to tackle the domain differences <cit.>.
It has been successfully applied in various data mining and machine learning tasks, such as clustering and classification <cit.>.
However, most of the transfer learning algorithms focus on numerical data <cit.>. 
When it comes to graph structure data, there is less existing work <cit.>, not to mention the dependency graph. 

This motivates us to propose a novel knowledge transfer-based method for dependency graph learning.

In this paper, we propose , a knowledge transfer based method for accelerating dependency graph learning from heterogeneous categorical event streams.

 consists of two sub-models: EEM (Entity Estimation Model) and DCM (Dependency Construction Model).
Specifically, first, EEM filters out irrelevant entities from source domain based on entity embedding and manifold learning.
Only the entities with statistically high correlations can be transferred to the target domain.

Then, based on the reduced entities, DCM model effectively constructs unbiased dependency relationships between different entities for the target dependency graph by solving a two-constraint optimization problem. We launch an extensive set of experiments on both synthetic and real-world data to evaluate the performance of .
The results demonstrate the effectiveness and efficiency of our proposed algorithm. 
We also apply  to a real enterprise security system for intrusion detection.
Our method is able to achieve superior detection performance at least 20 days lead lag time in advance with more than 70% accuracy.












§ PRELIMINARIES AND PROBLEM STATEMENT








In this section, we introduce some notations and define the problem.

Heterogeneous Categorical Event.
A heterogeneous categorical event e = (a_1, · · · , a_m) is a record contains m different categorical attributes, and the i-th attribute value a_i denotes an entity from the type 𝒯_i. 

For example, in the enterprise system (as illustrated in Fig. <ref>), a process event (e.g., a program opens a file or connects to a server) can be regarded as a heterogeneous categorical event.
It contains information, such as timing, type of operation, information flow directions, user, and source/destination process, etc.

By continuous monitoring/auditing the heterogeneous categorical event data (streams) generated by the physical system, one can generate the corresponding dependency graph of the system, as in <cit.>.
This dependency graph is a heterogeneous graph representing the dependencies/interactions between different pairs of entities. Formally, we define the dependency graph as follows:















Dependency Graph.
A dependency graph is a heterogeneous undirected weighted graph G = {V, E}, 
where V = {v_0, v_1, ..., v_n} is the set of heterogeneous system entities, and n is the total number of entities in the dependency graph; E = {e_0, e_1, ..., e_m} is the set of dependency relationships/edges between different entities. For ease of discussion, we use the terms edge and dependency interchangeably in this paper. A undirected edge e_i(v_k, v_j) between a pair of entities v_k and v_j exists depending on whether they have a dependency relation or not. The weight of the edge denotes the intensity of the dependency relation. A undirected edge e_i(v_s, v_d) between a pair of entities v_s and v_d exists depending on whether the they have a causality relation or not.
The weight for the dependency denotes the intensity of the causality relation.

In an enterprise system, a dependency graph can be a weighted graph between different system entities, such as processes, files, users, Internet sockets.
The edges in the dependency graph are the causality relations between different entities. 

As shown in Fig. <ref>, the enterprise security system utilities the accumulated historical heterogeneous system data from event streams to construct the system dependency graph and update the graph periodically. The learned dependency graph is applied to forensic analysis applications such as intrusion detection, risk analysis, and incident backtrack etc.

However, learning a dependency graph often requires a system auditing for a long period of time which in turn causes overwhelmingly large amount of system audit events. 
A system dependency graph needs to be trained for more than three weeks before deployed to the real world anomaly detection systems. 
In addition, when we deploy the security system to a new environment. 
We often need to spend other several weeks to retrain the dependency graph.














The problems of cold-start and time-consuming training reflect a great demand for an automated tool for effectively transferring dependency graphs between different domains.
Motivated by this, this paper focuses on accelerating the dependency graph learning via knowledge transfer. Based on the definitions described above, we formally define our problem as follows:

Knowledge Transfer for Dependency Graph Learning.
Given two domains: a source domain 𝒟_S and a target domain 𝒟_T. 
In the source domain 𝒟_S, we have a well-trained dependency graph G_S generated from the heterogeneous categorical event streams. 
In target domain 𝒟_T, we have a small incomplete dependency graph G_T trained by a short period of time.
The task of knowledge transfer for dependency graph learning is to use G_S to help construct a mature dependency graph G_T in the domain 𝒟_T. 
 
There are two major assumptions for this problem: (1) The event streams in the source domain and target domain are generated by the same physical system; (2) The entity size of source dependency graph G_S should be larger than the size of the intersection graph G_S ∩G_T. Because transferring knowledge from a less informative dependency graph to an informative graph is unreasonable.

 
For example, 𝒟_S can be an enterprise system environment from an IT company, and 𝒟_T can be another enterprise system environment from electronic management servers.
In next section, we present a motivation example for this problem.

However, there is no existing approach that can be directly used to solve this problem. This motivates us to design a new approach to effectively and efficiently transferring dependency graphs from different domains. In the next section, we will introduce the details of our proposed transferring framework.

































§ THE  MODEL


In this section, we introduce the proposed model in details. 
We now describe the  model in details.
As we introduced in section <ref>, a dependency graph consists of two basic elements: (1) entities and (2) dependencies between entities.
So we design two sub-models for estimating each element respectively.
These two models are: EEM (Entity Estimation Model) and DCM (Dependency Construction Model) as illustrated in Fig. <ref>.
We first introduce these two sub-models in details separately and then combine them into a uniform algorithm.
To learn a mature dependency graph G_T, intuitively, we would like to leverage the entity and dependency information from the well-trained source dependency graph G_S to help complete the original small dependency graph G_T. One naive way is to directly transfer all the entities and dependencies from the source domain to the target domain. However, due to the domain difference, it is likely that there are many entities and their corresponding dependencies that appear in source domain but not in the target domain. Thus, one key challenge in our problem is how to identify the domain-specific/irrelevant entities from the source dependency graph. After removing the irrelevant entities, another challenge is how to construct the dependencies between the transferred entities by adapting the domain difference and following the same dependency structure as in G_T. To address these two key challenges in dependency graph learning, we propose a knowledge transfer algorithm with two sub-models: EEM (Entity Estimation Model) and DCM (Dependency Construction Model) as illustrated in Fig. <ref>. We first introduce these two sub-models separately in details, and then combine them into a uniform algorithm.






 §.§ EEM: Embedding-based Entity Estimation Model



For the first sub-model, Entity Estimation Model, our goal is to filter out the entities in the source dependency graph G_S that are irrelevant to the target domain. 

To achieve this, we need to deal with two main challenges: (1) the lack of intrinsic correlation measures among categorical entities, and (2) heterogeneous relations among different entities in the dependency graph.

To overcome the lack of intrinsic correlation measures among categorical entities, we embed entities into a common latent space where their semantics can be preserved. 
More specifically, each entity, such as a user, or a process in computer systems, is represented as a d-dimensional vector and will be automatically learned from the data. 
In the embedding space, the correlation of entities can be naturally computed by distance/similarity measures in the space, such as Euclidean distances, vector dot product, and so on. Compared with other distance/similarity metrics defined on sets, such as Jaccard similarity, the embedding method is more flexible and it has nice properties such as transitivity <cit.>.

To address the challenge of heterogeneous relations among different entities, we use the meta-path proposed in <cit.> to model the heterogeneous relations.
For example, in a computer system, a meta-path can be a 
“Process-File-Process", or a "File-Process-Internet Socket".
“Process-File-Process" denotes the relationship of two processes load the same file, and "File-Process-Internet Socket" denotes the relationship of a file loaded by a process who opened an Internet Socket.

The potential meta-paths induced from the heterogeneous network G_S can be infinite, but not every one is relevant and useful for the specific task of interest. There are some works <cit.> for automatically selecting the meta-paths for specific tasks.
For more details about meta-path selecting methods, please refer <cit.>.



















Given a set of meta-paths P = { p_1, p_2, ...}, where p_i denotes the i-th meta-path and let |P| denotes the number of meta-paths.
We can construct |P| graphs G_p_i by each time only extracting the corresponding meta-path p_i from the dependency graph <cit.>. Let u_S denotes the vector representation of the entities in G_S.
Then, we model the relationship between two entities u_S(i) and u_S(j) as:

    u_S(i) - u_S(j)_F^2 ≈ S_G(i,j),







In the above, S_G is a weighted average of all the similarity matrices S_p_i: 

    S_G = ∑_i=1^|P| w_i S_p_i,

where w_i's are non-negative coefficients, and S_p_i is the similarity matrix constructed by calculating the pairwise shortest path between each entities in A_p_i.
Here, A_p_i is the adjacent matrix of the dependency graph G_p_i.
By using the shortest path in the graph, one can capture the long term relationship between different entities <cit.>.
Putting Eq. <ref> into Eq. <ref>, we have:

    u_S(i) - u_S(j)_F^2    ≈∑_i=1^|P| w_i S_p_i,

where *_F^2 is is the Frobenius norm <cit.>.

Then, the objective function of EEM model is:

    ℒ_1 ^(u_S, W) = ∑_i,j^n( u_S(i) - u_S(j)_F^2 - S_G)^θ + Ω (u_S, W),

where W = {w_1, w_2, ..., w_|P|}, and Ω (u_S, W) = λ u_S  + λ W is the generalization term <cit.>, which prevents the model from over-fitting.

λ is the trade-off factor of the generalization term. 
In practice, we can choose θ as 1 or 2, which bears the resemblance to Hamming distance and Euclidean distance, respectively.

Putting everything together, we get:

    ℒ_1 ^(u_S, W)    = ∑_i,j^n(  u_S(i) - u_S(j)_F^2 - S_G)^θ  + Ω (u_S, W)
       = ∑_i,j^n(  u_S(i) - u_S(j)_F^2 - ∑_i=0^|P|-1 w_i S_p_i)^θ  + λ u_S  + λ W


Then, the optimized value {u_S, W }^opt can be obtained by:

    {u_S, W}^opt = min_u_S, Wℒ_1 ^(u_S, W).




  §.§.§ Inference Method

The objective function in Eq. <ref> contains two sets of parameters: (1) u_S, and (2) W.
Then, we propose a two-step iterative method for optimizing ℒ_1 ^(u_S, W), where the entity vector matrices u_S and the weight for each meta-path W mutually enhance each other. 
In the first step, we fix the weight vectors W and learn the best entity vector matrix u_S. In the second step, we fix the entity vector matrix u_S and learn the best weight vectors W.

Fix W and learn u_S:
when we fix W, then the problem is reduced to u_S(i) - u_S(j)_F^2 ≈ S_G(i,j), where S_G is a constant similarity matrix.
Then, the optimization process becomes a traditional manifold learning problem.
Fortunately, we can have a closed form to solve this problem, via so called multi-dimensional scaling <cit.>.
To obtain such an embedding, we compute the eigenvalue decomposition of the following matrix:

    - 1/2HS_GH = UΛ U,
 where H is the double centering matrix, U has columns as the eigenvectors and Λ is a diagonal matrix with eigenvalues. Then, the embedding u_S can be chosen as:

    u_S = U_k√(Λ_k).


Fix u_S and learn W:
When fixing u_S, the problem is reduced to:

    ℒ_1 ^W   = ∑_i,j^n( u_S(i) - u_S(j)_F^2 - ∑_i=1^|P| w_i S_p_i)^θ + λ u_S  + λ W 
       = ∑_i,j^n( C_1 - ∑_i=0^|P| w_i S_p_i)^θ + λ W  + C_2,

where C_1 = u_S(i) - u_S(j)_F^2 is a constant matrix, and C_2 = λ E_S is also a constant.
Then, this function becomes a linear regression. 

So, we also have the close form solution for W:

    W = (S_G^TS_G)^-1S_GC_1.


After we get the embedding vectors u_S, then the relevance matrix ℝ between different entities can be obtained as:

    ℝ = u_Su_S^T


One can use a user defined threshold to select the entities with high correlation with target domain for transferring.
But user defined threshold is often suffered by the lack of domain knowledge. 
So here, we introduce a hypothesis test based method for automatically thresholding the selection of the entities.

For each entity in G_T, we first normalize all the scores by:
ℝ(i,:)_norm = (ℝ(i,:) - μ)/δ, where μ = ℝ(i,:) is the average value of ℝ(i,:), and δ is the standard deviation of ℝ(i,:). This standardized scores can be approximated with a gaussian distribution.
Then, the threshold will be 1.96 with P=0.025. (or 2.58 for P=0.001) <cit.>.
By using this threshold, one can filter out all the statistically irrelevant entities from the source domain, and transfer highly correlated entities to the target domain.



By combining the transferred entities and the original target domain dependency graph G_T, we get G_T, as shown in Fig. <ref>.
Then, the next step is to construct the missing dependencies in G_T.




 §.§ DCM: Dependency Construction Model






To construct the missing dependencies/edges in G_T, there are two constraints need to be considered:


  * Smoothness Constraint: The predicted dependency structure in G_T needs to be close to the dependency structure of the original graph G_T.
The intuition behind this constraint is that the learned dependencies should more or less intact in G_T as much as possible.

  * Consistency Constraint: 
Inconsistency between G_T and G_S should be similar to the inconsistency between G_T and G_S.
Here, G_S and G_S are the sub-graphs of G_S which have the same entity set with G_T and G_T, respectively.
This constraint guarantees that the target graph learned by our model can keep the original domain difference with the source graph. 


Before we model the above two constraints, we first need a measure to evaluate the inconsistence between different domains.
In this work, we propose a novel metric named dynamic factor F(G_S,G_T) between two dependency graphs G_S and G_T from two different domains as:

    F(G_S,G_T)    = A_S - A_T/ |G_S|*(|G_S| - 1) / 2 = 2A_S - A_T/ n_S(n_S-1),

where n_s = |G_S| is the number of entities in G_S, A_S and A_T denote the adjacent matrix of G_S and G_T, respectively, and n_S(n_S-1) / 2 denotes the number of edges of a fully connected graph with n_S entities <cit.>. 

Next, we introduce the Dependency Construction Model in details.



  §.§.§ Modeling Smoothness Constraint


We first model the smoothness constraint as follows:

    ℒ_2.1 ^u_T    = ∑_i=1^n_S∑_j=0^n_S-1(u_T(i)u_t(j)^T - A_T(i,j) ) _F^2 + λ u_T 
       = u_Tu_T^T - A_T_F^2 + Ω(u_T),

where u_T is the vector representation of the entities in G_T, and Ω(u_T) = λ u_T is the regularization term. 



  §.§.§ Modeling Consistency Constraint


We then model the consistency constraint as follows:

    ℒ_2.2 ^(u_T)    = 
     F(u_Tu_T^T, A_S) - F(A_S,A_T) _F^2 + Ω(u_T),

where F(*,*) is the dynamic factor as we defined before. Then, putting Eq. <ref> and Ω(u_T) into Eq. <ref>, we get:


    ℒ_2.2 ^E_T    = F(u_Tu_T^T, G_S) - F(G_S,G_T) _F^2 + Ω(u_T) 
        = 2 u_Tu_T^T - A_S/ n_s(n_S-1) - F(G_S,G_T) _F^2 + Ω(u_T) 
        = 2 u_Tu_T^T - A_S/ n_s(n_s-1) - C_3 _F^2 + Ω(u_T),

where C_3 = F(G_S,G_T).



  §.§.§ Unified Model

Having proposed the modeling approaches in Section <ref> and <ref>, we intend to put all the two constraints together.
The unified model for dependency construction is proposed as follows:

    ℒ_2 ^u_T    = μℒ_2.1 ^u_T + (1 - μ)ℒ_2.2 ^u_T
        = μu_Tu_T^T - A_T_F^2 
     + (1 - μ)2 u_Tu_T^T - A_S/ n_S(n_S-1) - C_3 _F^2 + Ω(u_T)


In the above, the symbols have the same meanings as introduced in previous sections. 
The first term of the model incorporates the Smoothness Constraint component, which keeps the u_T closer to target domain knowledge existed in the G_S. 
The second term considers the Consistency Constraint, that is the inconsistency between G_T and G_S should be similar to the inconsistency between G_T and G_S.

μ and λ are important parameters which capture the importance of each term, and we will discuss these parameters in Section <ref>.
To optimize the model as in Eq. <ref>, we use stochastic gradient descent <cit.> method. The derivative on u_T is given as:

    1/2∂ℒ_2^u_T/∂ E_T    = μ u_T (u_Tu_T^T - A_T)  + (1 - μ)u_T2 u_Tu_T^T - A_S/ n_S(n_S-1) - C_3  + u_T




 §.§ Overall Algorithm





The overall algorithm is then summarized as Algorithm <ref>.
This algorithm implements the methods we have introduced in the above subsections.
In the algorithm, line 5 to line 11 implements the Entity Estimation Model, and line 13 to 16 implements the Dependency Construction Model.
In the result of this section, we will discuss some practical issues of the ACRET algorithm.



  §.§.§ Setting Parameters

There are two parameters, λ and μ, in our model. 
For λ, as in <cit.>, it is always assigned manually based on the experiments and experience. Therefore, we only discuss the assignment of parameter μ in our model. 
For μ, when a large number of entities are transferred to the target domain, a large μ can improve the transferring result, because we need more information to be added from the source domain. 
On the other hand, when only a small number of entities are transferred to target domain, then a larger μ will bias the result. 
Therefore, the value of μ depends on how many entities are transferred from the source domain to the target domain.
In this sense, we can use the proportion of the transferred entities in G_T to calculate μ. 
Given the entity size of G_T as |G_T|, the entity size of G_T as |G_T|, then μ can be calculated as:

    μ = (|G_T| - |G_T|)/|G_T|,

















The experimental results in Section <ref> demonstrate the effectiveness of the proposed parameter selection method.





  §.§.§ Complexity Analysis


As shown in Algorithm <ref>, the time for learning our model is dominated by computing the objective functions and their corresponding gradients against feature vectors. 

For the Entity Estimation Model, the time complexity of computing the u_S in Eq. <ref> is bounded by O(d_1n), where n is the number of entities in G_S, and d_1 is the dimension of the vector space of u_S.
The time complexity for computing W is also bounded by O(d_1n).
So, suppose the number of training iterations for EEM is t_1, then the overall complexity of EEM model is O(t_1d_1n). 
For the Dependency Construction Model, the time complexity of computing the gradients of ℒ_2 against u_T is O(t_2d_2n), where t_2 is the number of iterations, d_2 is the dimensionality of feature vector. 
As shown in our experiment (see Section <ref>), t_1, t_2, d_1, and d_2 are all small numbers.
So that we can regard them as a constant, say C, so the overall complexity of our method is O(Cm), which is linear with the size of the entity set. This makes our algorithm practicable for large scale datasets.



§ EXPERIMENTS


In this section, we evaluate  using synthetic data and real system surveillance data collected in enterprise networks.



 §.§ Comparing Methods

We compare  with the following methods:

NT:
This method directly uses the original small target dependency graph without knowledge transfer.
In other words, the estimated target dependency graph G_T = G_T.


DT:
This method directly combines the source dependency graph and the original target dependency graph.
In other words, the estimated target dependency graph G_T= G_S + G_T. 


RW-DCM:
This is a modified version of the  method.

Instead of using the proposed EEM model to perform entity estimation, this method uses the random walk to evaluate the correlations between entities and perform entity estimation.
Random walk is a widely-used method for relevance search in a graph <cit.>. For more details about random walk, please refer to <cit.>.




EEM-CMF:
This is another modified version of the  method.
In this method, we replace DCM model with collective matrix factorization <cit.> method.
Collective matrix factorization has been applied for link prediction in multiple domains <cit.>.
For the details about collective matrix factorization, please refer to <cit.>.







 §.§ Evaluation Metrics

Since in  algorithm, we use hypothesis-test for thresholding the selection of entities and dependencies, similar to <cit.>, we use the F1-score to evaluate the hypothesis-test accuracy of all the methods. 

Since all methods listed above are based on hypothesis test, similar to <cit.>, we use the F1-score to evaluate the hypothesis-test accuracy of all the methods. 
F1 score has been used in many research works for analyzing hypothesis-test accuracy.
We use the F1-score to evaluate the performance of all the methods. F1-score is the harmonic mean of precision and recall. In our experiment, the final F1-scorebetween the estimated dependency graph G_T and the ground-truth dependency graph G_T is calculated by averaging the entity F1-score and dependency/edge F1-score. 

To calculate the precision (recall) of both entity and link, we compare the estimated entity (edge) set with the ground-truth entity/link set. 
Then, precision and recall can be calculated as follows:

    Precision=N_C/N_E,
           
    Recall=N_C/N_T,

where N_C is the number of correctly estimated entities (edges), N_E is the number of total estimated entities (edges), and N_T is the number of ground truth entities (edges). 







 §.§ Synthetic Experiments
 






We first evaluate the  on synthetic graph data-sets to have a more controlled setting for assessing algorithmic performance. 
We control three aspects of the synthetic data to stress test the performance of our  method: 


  * Graph size is defined as the number of entities for a dependency graph. Here, we use |G_S| to denote the source domain graph size and |G_T| to denote the target one. 

  * Dynamic factor, denoted as F, has the same definition as in Section <ref>. 


  * Graph maturity score, denoted as M, is defined as the percentage of entities/edges of the ground-truth graph G_T, that are used for constructing the original small graph G_T. Here, graph maturity score is used for simulating the period of learning time of G_T to reach the maturity in the real system.


Then, given |G_S|, |G_T|, F, and M, we generate the synthetic data as follows:

We first randomly generate an undirected graph as the source dependency graph G_S based on the value of |G_S| <cit.>; Then, we randomly assign three different labels to each entity. Due to space limitations, we will only show the results with three labels, but similar results have been achieved in graphs with more than three labels; 
We further construct the target dependency graph G_T by randomly adding/deleting F = d% of the edges and deleting |G_S| - |G_T| entities from G_S.
Finally, we randomly select M = c% of entities/edges from G_T to form G_T. 








  §.§.§ How Does 's Performance Scale with Graph Size?

We first explore how the 's performance changes with graph size |G_S| and |G_T|.

Here, we fix the maturity score to M=50%, the dynamic factor to F=10%, and target domain dependency graph size to |G_T|=0.9.
Then, we increase the source graph size |G_S| from 0.9K to 1.4K.
From Fig. <ref>, we observe that with the increase of the size difference |G_S| - |G_T|, the performances of DT and RW-DCM are getting worse. This is due to the poor ability of DT and RW-DCM for extracting useful knowledge from the source domain.

In contrast, the performance of  and EEM-CMF increases with the size differences.
This demonstrates the great capability of EEM model for entity knowledge extraction. 

In sum, compared with all other methods, our  method achieves the best performance.

























  §.§.§ How Does 's Performance Scale with Domain Dynamic Factor?

We now vary the dynamic factor F to understand its impact on the 's performance. Here, the graph maturity score is set to M=50%, and two domain sizes are set to |G_S|=1.2K and |G_T|=0.6K, respectively.
Fig. <ref> shows that the performances of all the methods go down with the increase of the dynamic factor. This is expected, because transferring the dependency graph from a very different domain will not work well.
On the other hand, the performances of , RW-DCM, and EEM-CMF only decrease slightly with the increase of the dynamic factor. Since RW-DCM and EEM-CMF are variants of the  method, this demonstrates that the two sub-models of the  method are both robust to large dynamic factors.




  §.§.§ How Does 's Performance Scale with Graph Maturity?

Third, we explore how the graph maturity score M impacts the performance of .
Here, the dynamic factor is fixed to F=0.2.
The graph sizes are set to |G_S| = 1.2K and |G_T|=0.6.
Fig. <ref> shows that with the increase of the M, the performances of all the methods are getting better. The reason is straightforward: with the maturity score increases, the challenge of domain difference for all the methods is becoming smaller. 
In addition, our  and its variants RW-DCM, and EEM-CMF perform much better than DT and NT. This demonstrates the great ability of the sub-models of  for knowledge transfer.
Furthermore,  still achieves the best performance.




 §.§ Real-World Experiments






Two real-world system monitoring datasets are used in this experiment.
The data is collected from an enterprise network system composed of 47 Linux machines and 123 Windows machines from two departments, in a time span of 14 consecutive days.
In both datasets, we collect two types of system events: (1) communications between processes, and (2) system activity of processes sending or receiving Internet connections to/from other machines at destination ports.
Three different types of system entities are considered: (1) processes, (2)
Unix domain sockets, and (3) Internet sockets.
The sheer size of the Windows dataset is around 7.4 Gigabytes, and the Linux dataset is around 73.5 Gigabytes.
Both Windows and Linux datasets are split into a source domain and a target domain according to the department name.
The detailed statistics of the two datasets are shown in Table <ref>.


In this experiment, we construct one target domain dependency graph G_T per day by increasing the learning time daily.
The final graph is the one learned for 14 days.
The result is shown in Fig. <ref>.
From Fig. <ref>, we observe that for both Windows and Linux datasets, with the increase of the training time, the performances of all the algorithms are getting better. 
On the other hand, compared with all the other methods,  achieves the best performance on both Windows and Linux datasets.
In addition, our proposed  algorithm can make the dependency graph deplorable in less than four days, instead of two weeks or longer by directly learning on the target domain.





 §.§ Convergence Analysis


As described in Section <ref>, the performance bottleneck of  model is the learning process of the two sub-models: EEM (Entity Estimation Model) and DCM (Dependency Construction Model). 
In this section, we report the convergence speed of our approach.

We use both synthetic and real-world data to validate the model convergence speed.
For the synthetic data, we choose the one with dynamic factor to be F = 0.2, the dependency graph size to be |G_S|=1.2K and |G_T|=0.6K, and the graph maturity to be 50%.
For the two real-world datasets, we fix the target dependency graph learning time as 4 days. The convergence rate of different models is shown in Fig. <ref>.

From Fig. <ref>, we can see that in all three datasets,  converges very fast (i.e., with less than 10 iterations). This makes our model applicable for the real-world large-scale systems.



 §.§ Parameter Study






The result is shown in Fig. <ref>.
In this section, we study the impact of parameter μ in Eq. <ref>.
We use the same datasets as in Section <ref>. As shown in Fig. <ref>, when the value of μ is too small or too large, the results are not good, because μ controls the leverage between the source domain information and target domain information.
The extreme value of μ (too large or too small) will bias the result.
On the other hand, the μ value calculated by Eq. <ref> is 0.23 for the synthetic dataset, 0.36 for the Windows dataset, and 0.46 for the Linux dataset. And Fig. <ref> shows the best results just appear around these three values.
This demonstrates that our proposed method for setting the μ value is very effective, which successfully addresses the parameter pre-assignment issue.




 §.§ Case Study on Intrusion Detection


As aforementioned, dependency graph is essential to many forensic analysis applications like root cause diagnosis and risk analysis. In this section, we evaluate the 's performance in a real commercial enterprise security system (see Fig. <ref>) for intrusion detection. 

In this case, the dependency graph, which represents the normal profile of the enterprise system, is the core analysis model for the offshore intrusion detection engine. It is built from the normal system process event streams (see Section <ref> for data description) during the training period.The security system has just been deployed in one Japanese electric company for three days, but it has been deployed in a US IT company for 1 month. In order to achieve good intrusion detection results in the electric company with the only three days' training,  is applied for accelerating the dependency graph learning process by leveraging the knowledge learned from the IT company. The same security system has been deployed in two companies: one Japanese electric company and one US IT company. We obtain one dependency graph from the IT company after 30 days' training, and two dependency graphs from the electric company after 3 and 30 days' training, respectively.  is applied for leveraging the well-trained dependency graph from the IT company to complete the 3 days' immature graph from the electric company. in the Electronic company with the only three days' training,  is applied for accelerating the dependency graph learning process by leveraging the knowledge learned from the IT company.

In the one-day testing period, we try 10 different types of attacks <cit.>, including Snowden attack, ATP attack, botnet attack, Sniffer Attack and etc., which resulted in 30 ground-truth alerts. All other alerts reported during the testing period are considered as false positives.

We deploy  to a real world commercial anomaly detection system in an IT company X in Princeton, NJ. 
The anomaly detection system in this company utilizes the dependency graph as the core analysis engine.
Learning the dependency graph for the detection system needs more than three weeks.
We omit and anonymize some details for confidentiality reasons.

Table <ref> shows the intrusion detection results using the dependency graph generated by , comparing to other four baseline methods. 

Table <ref> shows the intrusion detection results in the electric company using the dependency graphs generated by different transfer learning methods and the 30 days' training from the electric company. From the results, we can clearly see that  outperforms all the other transfer learning methods by at least 18% in precision and 13% in recall. On the other hand, the performance of the dependency graph (3 days' model) accelerated by  is very close to the ground truth model (30 days' model). This means, by using , we can achieve similar performance in one-tenth training time, which is of great significant to some mission critical environments.





this case study experiment, we choose the anomaly detection system of an electronic factory Y in XXX as the source domain.
We choose the the branch office of X in Princeton as the target domain.
The target domain original graph is a 3 day immature dependency graph.
We deployed  and the comparing methods into the anomaly detection system of X.
The experimental result of anomaly detection test is reported in Table <ref>. The real target model in Table. <ref> denotes the model trained in Y for two weeks.
From the result, we can clearly see that  outperforms all the other methods.
On the other hand, the performance of the dependency graph (3 days model) accelerated by  is very close to the ground truth model (30 days model).
That means, by using , we can achieve the same performance in less than half training time, which is of great significant to industry companies. 



§ RELATED WORK


In this section, we briefly introduce some related research efforts.


 §.§ Transfer Learning

Transfer learning has been widely studied in recent years <cit.>. Most of the traditional transfer learning methods focus on numerical data <cit.>. 
When it comes to graph (network) structured data, there is less existing work.
One line of transfer learning research that related to our work is transfer learning on the graph (network) structured data.
In <cit.>, the authors presented TrGraph, a novel transfer learning framework for network node classification. TrGraph leverages information from the auxiliary source domain to help the classification process of the target domain.A similar approach proposed by them in <cit.> is <cit.>. In <cit.>, the authors proposed a transfer learning method In one of their earlier work, a similar approach was proposed <cit.> to discover common latent structure features as useful knowledge to facilitate collective classification in the target network. In <cit.>, the authors proposed a framework to propagates the label information from the source domain to the target domain via the example-feature-example tripartite graph.
Transfer learning has also been applied to the deep neural network structure. 
In <cit.>, the authors introduced Net2Net, a technique for rapidly transferring the information stored in one neural net into another. Net2Net utilizes function preserving transformations to transfer knowledge from neural networks. Different from existing methods, we aim to expedite the dependency graph learning process through knowledge transfer. 
However, none of the methods have done the knowledge transfer for reconstruction the dependency graphs.



 §.§ Link Prediction and Relevance Search

Graph link prediction is a well-studied research topic <cit.>.
There are some link prediction works that related to our paper. 
In <cit.>, Ye et al. presented a transfer learning algorithm to address the edge sign prediction problem in signed social networks. Because edge instances are not associated with a pre-defined feature vector, this work was proposed to learn the common latent topological features shared by the target and source networks, and then adopt an AdaBoost-like transfer learning algorithm with instance weighting to train a classifier. 
The other work related to our work is collective matrix factorization Collective matrix factorization <cit.> is another popular technique that can be applied to detect mission links by combining the source domain and target domain graphs. However, all the existing link prediction methods can not deal with dynamics between the source domain and target domain as introduced in our problem.
 
Graph Relevance Search
Finding relevant nodes or similarity search in graphs is also related to our work. Many different similarity metrics have been proposed such as Jaccard coefficient, cosine similarity, and Pearson correlation coefficient <cit.>, and Random Walks <cit.>. 
However, none of these similarity measures consider the multiple relations exist in the data.
Recent advances in heterogeneous information networks <cit.> have offered several similarity measures for heterogeneous relations, such as meta-path and relation path <cit.>.
However, these methods can not deal with the multiple domain knowledge.



§ CONCLUSION

Dependency graphs capture intrinsic relationships between different pairs of system entities of physical systems. A well-trained dependency graph can be used for many data analysis application such as anomaly detection, system behavior analysis, recommendation, etc.
However, learning dependency graph is a time-consuming process.
To speed up the learning process, 
In this paper, we proposed , the first transfer learning model for accelerating dependency graph learning. 
 can effectively extract useful knowledge (e.g., entity and dependency relations) from the source domain, and transfer it to the target dependency graph. 
 also  the dynamic factor between different domains.
The experimental results on simulation datasets and two real datasets demonstrate the effectiveness and efficiency of .
We also deployed ACRET into real world commercial systems.

In this paper, we investigate the problem of transfer learning on dependency graph. Different from traditional methods that mainly focus on numerical data, we propose , a two-step approach for accelerating dependency graph learning from heterogeneous categorical event streams. 
By leveraging entity embedding and constrained optimization techniques,  can effectively extract useful knowledge (e.g., entity and dependency relations) from the source domain, and transfer it to the target dependency graph. 
 can also adaptively learn the differences between two domains, and construct the target dependency graph accordingly.
We evaluate the proposed algorithm using extensive experiments. The experiment results convince us of the effectiveness and efficiency of our approach.
We also apply  to a real enterprise security system for intrusion detection.
Our method is able to achieve superior detection performance at least 20 days lead lag time in advance with more than 70% accuracy.

ACM-Reference-Format
 

