Automatic detection of anomalies in graphs

Abstract

A method, apparatus and product for automatic detection of anomalies in graphs. The method comprising obtaining training data, the training data comprising a plurality of graphs, each defined by nodes and edges connecting between the nodes, at least some of the nodes are labeled; determining a statistical model of a graph in accordance with the training data, the statistical model takes into account at least one structured and labeled feature of the graph, wherein the structured and labeled feature of the graph is defined based on a connection between a plurality of nodes and based on at least a portion of the labels of the plurality of nodes; obtaining an examined graph; and determining a score of the examined graph indicative of a similarity between the examined graph and the training data, wherein the score is based on a value of the structured and labeled feature in the examined graph.

1 . A computer-implemented method comprising:
 obtaining training data, the training data comprising a plurality of graphs, each defined by nodes and edges connecting between the nodes, wherein at least some of the nodes are labeled;   determining, by a processor, a statistical model of a graph in accordance with the training data, the statistical model takes into account at least one structured and labeled feature of the graph, wherein the structured and labeled feature of the graph is defined based on a connection between a plurality of nodes and based on at least a portion of the labels of the plurality of nodes;   obtaining an examined graph; and   determining, by the processor, a score of the examined graph indicative of a similarity between the examined graph and the training data, wherein the score is based on a value of the structured and labeled feature in the examined graph.   
     
     
         2 . The computer-implemented method of  claim 1 , wherein the structured and labeled feature is one of the following features:
 a binary feature indicating existence of a labeled path in the graph;   a binary feature indicating existence of a labeled, non-path, sub-tree topology; and   a feature relating to a terminal value of a labeled path in the graph.   
     
     
         3 . The computer-implemented method of  claim 1 , wherein the graphs are trees. 
     
     
         4 . The computer-implemented method of  claim 1  further comprising, based on the training data building a consensus graph retaining information relating to the values of the structured and labeled feature in the plurality of graphs in the training data. 
     
     
         5 . (canceled) 
     
     
         6 . The computer-implemented method of  claim 1 , wherein the structured and labeled feature is associated with a motif present in the graph and at least a portion of the labels of the nodes that embody the motif in the graph. 
     
     
         7 . A computerized apparatus having a processor, the processor being adapted to perform the steps of:
 obtaining training data, the training data comprising a plurality of graphs, each defined by nodes and edges connecting between the nodes, wherein at least some of the nodes are labeled;   determining a statistical model of a graph in accordance with the training data, the statistical model takes into account at least one structured and labeled feature of the graph, wherein the structured and labeled feature of the graph is defined based on a connection between a plurality of nodes and based on at least a portion of the labels of the plurality of nodes;   obtaining an examined graph; and   determining a score of the examined graph indicative of a similarity between the examined graph and the training data, wherein the score is based on a value of the structured and labeled feature in the examined graph.   
     
     
         8 . The computerized apparatus of  claim 7 , wherein the structured and labeled feature is one of the following features:
 a binary feature indicating existence of a labeled path in the graph;   a binary feature indicating existence of a labeled, non-path, sub-tree topology; and   a feature relating to a terminal value of a labeled path in the graph.   
     
     
         9 . The computerized apparatus of  claim 7 , wherein the graphs are trees. 
     
     
         10 . The computerized apparatus of  claim 7 , wherein the processor is further adapted to perform the step of: based on the training data building a consensus graph retaining information relating to the values of the structured and labeled feature in the plurality of graphs in the training data. 
     
     
         11 . (canceled) 
     
     
         12 . The computerized apparatus of  claim 7 , wherein the structured and labeled feature is associated with a motif present in the graph and at least a portion of the labels of the nodes that embody the motif in the graph. 
     
     
         13 . A computer program product comprising a non-transitory computer readable medium retaining program instructions, which instructions when read by a processor, cause the processor to perform a method comprising:
 obtaining training data, the training data comprising a plurality of graphs, each defined by nodes and edges connecting between the nodes, wherein at least some of the nodes are labeled;   determining a statistical model of a graph in accordance with the training data, the statistical model takes into account at least one structured and labeled feature of the graph, wherein the structured and labeled feature of the graph is defined based on a connection between a plurality of nodes and based on at least a portion of the labels of the plurality of nodes;   obtaining an examined graph; and   determining a score of the examined graph indicative of a similarity between the examined graph and the training data, wherein the score is based on a value of the structured and labeled feature in the examined graph.