Classification using projection of graphs into summarized spaces

1. A computer-implemented method for anomaly detection using grouping-based graph summarization, the method being performed by one or more computing devices, each comprising one or more processors, the method comprising:

identifying a first graph from a stream of incoming graphs;

generating a first summary of the first graph;

classifying the first summary in a first category of a plurality of graph categories;

identifying a second graph from the stream of incoming graphs;

generating a second summary of the second graph;

comparing the first summary with the second summary;

mapping the first summary and the second summary to the first category upon determining that the comparing indicates a similarity between the first summary and the second summary satisfies a graph similarity threshold;

analyzing a frequency of graphs being mapped to the plurality of graph categories, the plurality of graph categories comprising at least the first category; and

detecting an anomaly in one of the graph categories based at least in part on the analysis.

2. The method of claim 1 , further comprising:

determining whether the anomaly indicates malware; and

performing a security action to protect the one or more computing devices from the malware upon determining the anomaly indicates malware, the security action including at least one of quarantining the malware, deleting the malware, scanning the malware, identifying characteristics of the malware, classifying the malware, or any combination thereof.

3. The method of claim 2 , determining whether the anomaly indicates malware further comprising:

analyzing graphs that have been mapped to the graph category having the anomaly; and

determining, based at least in part on the analysis of the graphs, details about the anomaly.

4. The method of claim 1 , detecting the anomaly in one of the graph categories further comprising:

comparing the frequency of graphs being mapped to the plurality of graph categories; and

determining the frequency of graphs being mapped to the one of the graph categories satisfies a mapping frequency threshold.

5. The method of claim 1 , wherein generating the summary of the first graph comprises:

selecting one or more nodes from the first graph; and

grouping the selected one or more nodes into a supernode.

6. The method of claim 5 , generating the summary of the first graph further comprises:

grouping one or more edges from the first graph corresponding to the selected one or more nodes into a superedge.

7. The method of claim 5 , wherein the selecting of the one or more nodes is based at least in part on selecting a reduction ratio, the selected reduction ratio determining a ratio of a number of summarized nodes in the summary of the first graph to a total number of nodes in the first graph.

8. The method of claim 7 , wherein a higher the reduction ratio, a lower a storage size for the summary of the first graph.

9. The method of claim 5 , wherein the selecting of the one or more nodes is based at least in part on selecting a utility value, the selected utility value determining an extent to which one or more regions of interest of the first graph are preserved in the summary of the first graph.

10. The method of claim 9 , wherein a lower the utility value, a lower a storage size for the summary of the first graph.

11. The method of claim 1 , further comprising:

classifying the second graph in a second category of the plurality of graph categories upon determining that a result of the comparing of the first summary with the second summary does not satisfy the graph similarity threshold.

12. The method of claim 1 , further comprising:

identifying a third graph from the stream of incoming graphs;

generating a summary of the third graph; and

comparing the summary of the third graph to at least one of the first summary and the second summary, or both.

13. The method of claim 12 , further comprising:

mapping the third graph to the first summary upon determining that the comparing indicates a similarity between the first summary and the third summary satisfies the graph similarity threshold.

14. The method of claim 1 , wherein at least one node of the first graph represents an event associated with a client device or a user of the client device, or an event associated with the client device and the user of the client device.

15. A computing device configured for anomaly detection using grouping-based graph summarization, comprising:

a processor;

memory in electronic communication with the processor, wherein the memory stores computer executable instructions that when executed by the processor cause the processor to perform the steps of:

identifying a first graph from a stream of incoming graphs;

generating a first summary of the first graph;

classifying the first summary in a first category of a plurality of graph categories;

identifying a second graph from the stream of incoming graphs;

generating a second summary of the second graph;

comparing the first summary with the second summary;

mapping the first summary and the second summary to the first category upon determining that the comparing indicates a similarity between the first summary and the second summary satisfies a graph similarity threshold;

analyzing a frequency of graphs being mapped to the plurality of graph categories, the plurality of graph categories comprising at least the first category; and

detecting an anomaly in one of the graph categories based at least in part on the analysis.

16. The device of claim 15 , wherein the executable instructions when executed cause the processor to perform the step of:

determining whether the anomaly indicates malware; and

performing a security action to protect one or more computing devices from the malware upon determining the anomaly indicates malware, the security action including at least one of quarantining the malware, deleting the malware, scanning the malware, identifying characteristics of the malware, classifying the malware, or any combination thereof.

17. The device of claim 16 , wherein the executable instructions when executed cause the processor to perform the step of:

analyzing graphs that have been mapped to the graph category having the anomaly; and

determining, based at least in part on the analysis of the graphs, details about the anomaly.

18. The device of claim 15 , wherein the executable instructions when executed cause the processor to perform the step of:

comparing the frequency of graphs being mapped to the plurality of graph categories; and

determining the frequency of graphs being mapped to the one of the graph categories satisfies a mapping frequency threshold.

19. The device of claim 15 , wherein the executable instructions when executed cause the processor to perform the step of:

classifying the second graph in a second category of the plurality of graph categories upon determining that a result of the comparing of the first summary with the second summary does not satisfy the graph similarity threshold.

20. A computer-program product for using customer context to detonate malware, the computer-program product comprising a non-transitory computer-readable medium storing instructions thereon, the instructions being executable by a processor to:

identify a first graph from a stream of incoming graphs;

generate a first summary of the first graph;

classify the first summary in a first category of a plurality of graph categories;

identify a second graph from the stream of incoming graphs;

generate a second summary of the second graph;

compare the first summary with the second summary;

map the first summary and the second summary to the first category upon determining that the comparing indicates a similarity between the first summary and the second summary satisfies a graph similarity threshold;

analyze a frequency of graphs being mapped to the plurality of graph categories, the plurality of graph categories comprising at least the first category; and

detect an anomaly in one of the graph categories based at least in part on the analysis.