Method and system for behavior query construction in temporal graphs using discriminative sub-trace mining

Patent metadata

Field	Value
Publication number	US-2016125094-A1
Application number	US-201514932799-A
Country	US
Kind code	A1
Filing date	Nov 4, 2015
Priority date	Nov 5, 2014
Publication date	May 5, 2016
Grant date	—

Abstract

A method and system for constructing behavior queries in temporal graphs using discriminative sub-trace mining. The method includes generating system data logs to provide temporal graphs, wherein the temporal graphs include a first temporal graph corresponding to a target behavior and a second temporal graph corresponding to a set of background behaviors, generating temporal graph patterns for each of the first and second temporal graphs to determine whether a pattern exists between a first temporal graph pattern and a second temporal graph pattern, wherein the pattern between the temporal graph patterns is a non-repetitive graph pattern, pruning the pattern between the first and second temporal graph patterns to provide a discriminative temporal graph, and generating behavior queries based on the discriminative temporal graph.

First claim

What is claimed is:

1 . A computer implemented method for constructing behavior queries in temporal graphs using discriminative sub-trace mining, comprising:
generating system data logs to provide temporal graphs, wherein the temporal graphs include at least a first temporal graph corresponding to a target behavior and a second temporal graph corresponding to a set of background behaviors; generating temporal graph patterns for each of the first and second temporal graphs to determine whether a pattern exists between a first temporal graph pattern and a second temporal graph pattern, wherein the pattern between the temporal graph patterns is a non-repetitive graph pattern; pruning the pattern between the temporal graph patterns to provide at least one discriminative temporal graph; and generating behavior queries based on the at least one discriminative temporal graph.

2 . The computer implemented method according to claim 1 , wherein the pattern is determined when each edge in the first temporal graph pattern corresponds to each edge in the second temporal graph pattern such that node mappings between each edge are one-to-one.

3 . The computer implemented method according to claim 1 , wherein the pattern includes temporal graph patterns that are identical in linear time.

4 . The computer implemented method according to claim 1 , wherein the system data logs are generated in a closed environment such that the at least one target behavior is performed independently from the set of background behaviors.

5 . The computer implemented method according to claim 1 , wherein the pattern includes a consecutive growth pattern.

6 . The computer implemented method according to claim 5 , wherein the consecutive growth pattern includes at least one of a forward growth pattern, a backward growth pattern, and an inward growth pattern.

7 . The computer implemented method according to claim 1 , wherein the temporal graphs are T-connected temporal graphs.

8 . The computer implemented method according to claim 1 , wherein pruning includes at least one of subgraph pruning and supergraph pruning.

9 . The computer implemented method according to claim 1 , further comprising minimizing overheard from at least one of subgraph tests and residual graph set equivalence tests.

10 . A system for constructing behavior queries in temporal graphs using discriminative sub-trace mining, comprising:
a monitoring device to generate system data logs to provide temporal graphs, wherein the temporal graphs include at least a first temporal graph corresponding to a target behavior and a second temporal graph corresponding to a set of background behaviors; a temporal graph pattern generator to generate temporal graph patterns for each of the first and second temporal graphs; a pattern determiner to determine whether a pattern exists between a first temporal graph pattern and a second temporal graph pattern, wherein the pattern between the temporal graph patterns is a non-repetitive graph pattern; a pattern pruner comprising a processor, coupled to a bus, to prune the pattern between the temporal graph patterns to provide at least one discriminative temporal graph; and a behavior query generator, coupled to the bus, to generate behavior queries based on the at least one discriminative temporal graph.

11 . The system according to claim 10 , wherein the pattern is determined when each edge in the first temporal graph pattern corresponds to each edge in the second temporal graph pattern such that node mappings between each edge are one-to-one.

12 . The system according to claim 10 , the monitoring device is further configured to generate the system data logs in a closed environment such that the at least one target behavior is performed independently from the set of background behaviors.

13 . The system according to claim 10 , wherein the pattern includes a consecutive growth pattern.

14 . The system according to claim 13 , wherein the consecutive growth pattern includes at least one of a forward growth pattern, a backward growth pattern, and an inward growth pattern.

15 . The system according to claim 11 , wherein the pattern pruner is further configured to prune using at least one of subgraph pruning and supergraph pruning.

16 . A computer program product comprising a non-transitory computer readable storage medium having computer readable program code embodied therein for a method for constructing behavior queries in temporal graphs using discriminative sub-trace mining, the method comprising:
generating system data logs to provide temporal graphs, wherein the temporal graphs include at least a first temporal graph corresponding to a target behavior and a second temporal graph corresponding to a set of background behaviors; generating temporal graph patterns for each of the first and second temporal graphs to determine whether a pattern exists between a first temporal graph pattern and a second temporal graph pattern, wherein the pattern between the temporal graph patterns is a non-repetitive graph pattern; pruning the pattern between the temporal graph patterns to provide at least one discriminative temporal graph; and generating behavior queries based on the at least one discriminative temporal graph.

17 . The computer program product of claim 16 , wherein the pattern is determined when each edge in the first temporal graph pattern corresponds to each edge in the second temporal graph pattern such that node mappings between each edge are one-to-one.

18 . The computer program product of claim 16 , wherein the system data logs are generated in a closed environment such that the at least one target behavior is performed independently from the set of background behaviors.

19 . The computer program product of claim 16 , wherein pruning includes at least one of subgraph pruning and supergraph pruning.

20 . The computer program product of claim 19 , further comprising minimizing overheard from at least one of subgraph tests and residual graph set equivalence tests.

Assignees

• Nec Lab America Inc

Inventors

• Li Zhichun
• Xiao Xusheng
• Wu Zhenyu
• Zong Bo
• Jiang Guofei

Classifications

• G06F17/30958 Primary

  Physics · mapped topic

• G06F17/30917

  Physics · mapped topic

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F21/552

  involving long-term monitoring or reporting · CPC title