Finding the Most Descriptive Substructures in Graphs with Discrete and Numeric Labels

Many graph datasets are labelled with discrete and numeric attributes. Most frequent substructure discovery algorithms ignore numeric attributes; in this paper we show how they can be used to improve search performance and discrimination. Our thesis is that the most descriptive substructures are those which are normative both in terms of their structure and in terms of their numeric values. We explore the relationship between graph structure and the distribution of attribute values and propose an outlier-detection step, which is used as a constraint during substructure discovery. By pruning anomalous vertices and edges, more weight is given to the most descriptive substructures. Our method is applicable to multi-dimensional numeric attributes; we outline how it can be extended for high-dimensional data. We support our findings with experiments on transaction graphs and single large graphs from the domains of physical building security and digital forensics, measuring the effect on runtime, memory requirements and coverage of discovered patterns, relative to the unconstrained approach.

How useful are databases in environmental and criminal forensics?

Advances in computational and information technologies have facilitated the acquisition of geospatial information for regional and national soil and geology databases. These have been completed for a range of purposes from geological and soil baseline mapping to economic prospecting and land resource assessment, but have become increasingly used for forensic purposes. On the question of provenance of a questioned sample, the geologist or soil scientist will draw invariably on prior expert knowledge and available digital map and database sources in a ‘pseudo Bayesian’ approach. The context of this paper is the debate on whether existing (digital) geology and soil databases are indeed useful and suitable for forensic inferences. Published and new case studies are used to explore issues of completeness, consistency, compatibility and applicability in relation to the use of digital geology and soil databases in environmental and criminal forensics. One key theme that emerges is that, despite an acknowledgement that databases can be neither exhaustive nor precise enough to portray spatial variability at the scene of crime scale, coupled with expert knowledge, they play an invaluable role in providing background or
reference material in a criminal investigation. Moreover databases can offer an independent control set of samples.