Graph-Based Anomaly Detection
|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 (http://ailab.wsu.edu/subdue/).