Projects per year
Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 307-332 |
Number of pages | 26 |
Journal | Journal of Intelligent Information Systems |
Volume | 42 |
Issue number | 2 |
Early online date | 27 Dec 2013 |
DOIs | |
Publication status | Published - Apr 2014 |
Keywords
- Graph mining
- Anomaly detection
Fingerprint
Dive into the research topics of 'Finding the Most Descriptive Substructures in Graphs with Discrete and Numeric Labels'. Together they form a unique fingerprint.Projects
- 1 Finished
-
R1118ECI: Centre for Secure Information Technologies (CSIT)
McCanny, J. V. (PI), Cowan, C. (CoI), Crookes, D. (CoI), Fusco, V. (CoI), Linton, D. (CoI), Liu, W. (CoI), Miller, P. (CoI), O'Neill, M. (CoI), Scanlon, W. (CoI) & Sezer, S. (CoI)
01/08/2009 → 30/06/2014
Project: Research