# US 2016/0253232 A1 · Contextual graph matching based anomaly detection > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2016/0253232 A1 - Document ID: US20160253232A1 - Status: Published application - Kind: A1 - Application number: 15/152,066 - Filed: 2016-05-11 - Published: 2016-09-01 - Earliest claimed: 2013-10-11 - Assignees: Accenture Global Services Limited - Applicants: Accenture Global Services Limited - Inventors: Colin A. PURI; John K. Nguyen; Scott W. Kurth - Web page: https://patentgrep.com/patent/US20160253232A1 ## CPC - G06F 11/0706: {the processing taking place on a specific hardware platform or in a specific software environment} - G06F 11/0709: {in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems} - G06F 11/0751: {Error or fault detection not based on redundancy (power supply failures G06F1/30; network fault management H04L41/06)} - G06F 11/0778: {Dumping, i.e. gathering error/state information after a fault for later diagnosis} - G06F 11/079: {Root cause analysis, i.e. error or fault diagnosis (in a hardware test environment G06F11/22; in a software test environment G06F11/36)} - G06F 16/2455: Query execution - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F 21/552: {involving long-term monitoring or reporting} - G06N 5/04: Inference or reasoning models - H04L 63/1425: {Traffic logging, e.g. anomaly detection} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Contextual graph matching based anomaly detection may include evaluating computer-generated log file data to create a master directed graph that specifies known events and transitions between the known events. The master directed graph may be processed to determine a plurality of decomposed master graph walks. Incoming computer-generated log file data may be evaluated to create an incoming directed graph that specifies unknown events and transitions between the unknown events. The incoming directed graph may be processed to determine a decomposed incoming walk. Overlap, distance difference, and correlation scores may be determined for each walk pair of a plurality of walk pairs including each of the plurality of decomposed master graph walks and the decomposed incoming walk. One of the decomposed master graph walks may be selected based on the overlap score, the difference score, and the correlation score, to detect an anomaly. ## Claims ### Claim 1 A contextual graph matching based anomaly detection system comprising: at least one processor; a master directed graph generation module, executed by the at least one processor, to evaluate computer-generated log file data to create, in a computer memory, a master directed graph that specifies known events and transitions between the known events; a master directed graph decomposition module, executed by the at least one processor, to process the master directed graph to identify a plurality of unique walks through the master directed graph, and to decompose the plurality of unique walks into their probability distributions as a plurality of decomposed master graph walks; an incoming directed graph generation module, executed by the at least one processor, to evaluate incoming computer-generated log file data to create an incoming directed graph that specifies unknown events and transitions between the unknown events; an incoming directed graph decomposition module, executed by the at least one processor, to process the incoming directed graph to identify an incoming walk through the incoming directed graph, and to decompose the incoming walk into its probability distribution as a decomposed incoming walk; a graph matching module, executed by the at least one processor, to: determine an overlap score for each walk pair of a plurality of walk pairs including each of the plurality of decomposed master graph walks and the decomposed incoming walk, determine a distance difference score for each walk pair of the plurality of walk pairs, and determine a correlation score for each walk pair of the plurality of walk pairs; and an anomaly detection module, executed by the at least one processor, to select one of the plurality of decomposed master graph walks based on the overlap score, the difference score, and the correlation score, and to detect an anomaly based on the selected one of the plurality of decomposed master graph walks. ### Claim 2 (depends on 1) The contextual graph matching based anomaly detection system according to claim 1, wherein the graph matching module is to determine the overlap score by evaluating an intersection and a union of an edge set of one of the plurality of decomposed master graph walks and an edge set of the decomposed incoming walk. ### Claim 3 (depends on 1) The contextual graph matching based anomaly detection system according to claim 1, wherein the graph matching module is to determine the distance difference score by evaluating an edge weight from an edge set of one of the plurality of decomposed master graph walks and an edge weight from an edge set of the decomposed incoming walk. ### Claim 4 (depends on 1) The contextual graph matching based anomaly detection system according to claim 1, wherein the graph matching module is to determine the correlation score by evaluating an edge belonging to an edge set of one of the plurality of decomposed master graph walks and an edge belonging to an edge set of the decomposed incoming walk. ### Claim 5 (depends on 1) The contextual graph matching based anomaly detection system according to claim 1, wherein the master directed graph decomposition module is to rank the plurality of unique walks through the master directed graph according to a probability of occurrence, wherein the probability of occurrence is based on an edge set of one of the plurality of decomposed master graph walks and adjacent nodes within the master directed graph. ### Claim 6 (depends on 5) The contextual graph matching based anomaly detection system according to claim 5, wherein the anomaly detection module is to evaluate a scaled fitness metric related to each walk pair of the plurality of walk pairs for selecting the one of the plurality of decomposed master graph walks, wherein the scaled fitness metric is based on a ranking coefficient related to the rank of the plurality of unique walks through the master directed graph, and a degree of fitness metric related to each walk pair of the plurality of walk pairs. ### Claim 7 (depends on 5) The contextual graph matching based anomaly detection system according to claim 5, wherein the anomaly detection module is to determine a maximal anomaly metric from scaled fitness metrics related to each walk pair of the plurality of walk pairs for selecting the one of the plurality of decomposed master graph walks, wherein a scaled fitness metric of the scaled fitness metrics is based on a ranking coefficient related to the rank of the plurality of unique walks through the master directed graph, and a degree of fitness metric related to each walk pair of the plurality of walk pairs. ### Claim 8 (depends on 5) The contextual graph matching based anomaly detection system according to claim 5, wherein the anomaly detection module is to evaluate a scaled identified maximal walkpair fitness metric for each walk pair of the plurality of walk pairs for selecting the one of the plurality of decomposed master graph walks, wherein the scaled identified maximal walkpair fitness metric is based on a ranking coefficient related to the rank of the plurality of unique walks through the master directed graph, a degree of fitness metric related to each walk pair of the plurality of walk pairs, and the correlation score. ### Claim 9 (depends on 8) The contextual graph matching based anomaly detection system according to claim 8, wherein the scaled identified maximal walkpair fitness metric is to provide a percentage anomalousness of the decomposed incoming walk. ### Claim 10 (depends on 1) The contextual graph matching based anomaly detection system according to claim 1, wherein the anomaly detection module is to evaluate a kernel transformation function related to each walk pair of the plurality of walk pairs for selecting the one of the plurality of decomposed master graph walks. ### Claim 11 (depends on 10) The contextual graph matching based anomaly detection system according to claim 10, wherein the anomaly detection module is to evaluate a degree of fitness metric for each walk pair of the plurality of walk pairs for selecting the one of the plurality of decomposed master graph walks, wherein the degree of fitness metric is based on the kernel transformation function, the overlap score, and the distance difference score. ### Claim 12 (depends on 1) The contextual graph matching based anomaly detection system according to claim 1, wherein the anomaly detection module is to evaluate a directionality for each walk pair of the plurality of walk pairs for selecting the one of the plurality of decomposed master graph walks. ### Claim 13 A method for contextual graph matching based anomaly detection, the method comprising: evaluating, by a processor, computer-generated log file data to create, in a computer memory, a master directed graph that specifies known events and transitions between the known events; processing the master directed graph to identify a plurality of unique walks through the master directed graph, and to decompose the plurality of unique walks into their probability distributions as a plurality of decomposed master graph walks; evaluating incoming computer-generated log file data to create an incoming directed graph that specifies unknown events and transitions between the unknown events; processing the incoming directed graph to identify an incoming walk through the incoming directed graph, and to decompose the incoming walk into its probability distribution as a decomposed incoming walk; determining an overlap score for each walk pair of a plurality of walk pairs including each of the plurality of decomposed master graph walks and the decomposed incoming walk by evaluating an intersection and a union of an edge set of one of the plurality of decomposed master graph walks and an edge set of the decomposed incoming walk; determining a distance difference score for each walk pair of the plurality of walk pairs; determining a correlation score for each walk pair of the plurality of walk pairs; and selecting one of the plurality of decomposed master graph walks based on the overlap score, the difference score, and the correlation score, to detect an anomaly based on the selected one of the plurality of decomposed master graph walks. ### Claim 14 (depends on 13) The method of claim 13, wherein determining a distance difference score for each walk pair of the plurality of walk pairs further comprises: determining the distance difference score by evaluating an edge weight from an edge set of one of the plurality of decomposed master graph walks and an edge weight from an edge set of the decomposed incoming walk. ### Claim 15 (depends on 13) The method of claim 13, wherein determining a correlation score for each walk pair of the plurality of walk pairs further comprises: determining the correlation score by evaluating an edge belonging to an edge set of one of the plurality of decomposed master graph walks and an edge belonging to an edge set of the decomposed incoming walk. ### Claim 16 (depends on 13) The method of claim 13, further comprising: ranking the plurality of unique walks through the master directed graph according to a probability of occurrence, wherein the probability of occurrence is based on the edge set of one of the plurality of decomposed master graph walks and adjacent nodes within the master directed graph; evaluating a scaled identified maximal walkpair fitness metric for each walk pair of the plurality of walk pairs for selecting the one of the plurality of decomposed master graph walks, wherein the scaled identified maximal walkpair fitness metric is based on a ranking coefficient related to the rank of the plurality of unique walks through the master directed graph, a degree of fitness metric related to each walk pair of the plurality of walk pairs, and the correlation score; and providing a percentage anomalousness of the decomposed incoming walk based on the scaled identified maximal walkpair fitness metric. ### Claim 17 A non-transitory computer readable medium having stored thereon machine readable instructions for contextual graph matching based anomaly detection, the machine readable instructions when executed cause a processor to: evaluate computer-generated log file data to create, in a computer memory, a master directed graph that specifies frequencies of state transitions within the master directed graph; process the master directed graph to identify a plurality of unique walks through the master directed graph, and to decompose the plurality of unique walks into their probability distributions as a plurality of decomposed master graph walks; evaluate incoming computer-generated log file data to create an incoming directed graph that specifies frequencies of state transitions within the incoming directed graph; process the incoming directed graph to identify an incoming walk through the incoming directed graph, and to decompose the incoming walk into its probability distribution as a decomposed incoming walk; determine an overlap score for each walk pair of a plurality of walk pairs including each of the plurality of decomposed master graph walks and the decomposed incoming walk; determine a distance difference score for each walk pair of the plurality of walk pairs; determine a correlation score for each walk pair of the plurality of walk pairs based on the frequencies of state transitions within the master directed graph and the frequencies of state transitions within the incoming directed graph; and select one of the plurality of decomposed master graph walks based on the overlap score, the difference score, and the correlation score, to detect an anomaly based on the selected one of the plurality of decomposed master graph walks. ### Claim 18 (depends on 17) The non-transitory computer readable medium of claim 17, wherein the machine readable instructions to determine an overlap score for each walk pair of a plurality of walk pairs including each of the plurality of decomposed master graph walks and the decomposed incoming walk further comprise: determining the overlap score by evaluating an intersection and a union of an edge set of one of the plurality of decomposed master graph walks and an edge set of the decomposed incoming walk. ### Claim 19 (depends on 17) The non-transitory computer readable medium of claim 17, wherein the machine readable instructions to determine a distance difference score for each walk pair of the plurality of walk pairs further comprise: determining the distance difference score by evaluating an edge weight from an edge set of one of the plurality of decomposed master graph walks and an edge weight from an edge set of the decomposed incoming walk. ### Claim 20 (depends on 17) The non-transitory computer readable medium of claim 17, wherein the machine readable instructions to determine a correlation score for each walk pair of the plurality of walk pairs based on the frequencies of state transitions within the master directed graph and the frequencies of state transitions within the incoming directed graph further comprise: determining the correlation score by evaluating an edge belonging to an edge set of one of the plurality of decomposed master graph walks and an edge belonging to an edge set of the decomposed incoming walk.