Once the data is collected, an important research area in security is to identify anomalous events and flag them as suspicious activities that warrant further investigation. Our approach to detecting abrupt changes (anomalies) in collected data is built upon our earlier work in the Subdue graph-based data mining system. Subdue discovers patterns in labeled graphs that maximize the compression of the graph. Patterns that perform well only in a small time increment can be flagged as anomalies. We are developing database mining and clustering techniques to address scalability and performance of mining very large volumes of heterogeneous data. We are investigating mining of transactional graph-based, and steaming text as all of them have different characteristics and applications. We are studying methods for identifying asymmetric (e.g., terrorist) threats to national defense by looking for patterns of such activity in large structural databases of entities and their relationships. The main objectives of this research are to design, implement and evaluate new methods for performing pattern learning on structured data represented as graphs and apply these methods to relational databases relevant to the asymmetric threat domain.