logo for gbad


                                           Graph-Based Anomaly Detection                                       




Download (Rev. 3.3)


GBAD discovers anomalous instances of structural patterns in data, where the data represents entities, relationships and actions in graph form. Input to GBAD is a labeled graph in which entities are represented by labeled vertices and relationships or actions are represented by labeled edges between entities.  Using the minimum description length (MDL) principle to identify the normative pattern that minimizes the number of bits needed to describe the input graph after being compressed by the pattern, GBAD embodies novel algorithms for identifying the three possible changes to a graph:  modifications, insertions and deletions.  Each algorithm discovers those substructures that match the closest to the normative pattern without matching exactly.  As a result, GBAD is looking for those activities that appear to match normal (or legitimate) transactions, but in fact are structurally different.

The normative pattern discovery aspects of the GBAD system are based upon the SUBDUE graph-based pattern learning system (www.subdue.org).