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

Michael Davis, Weiru Liu, Paul Miller

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
578 Downloads (Pure)


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 languageEnglish
Pages (from-to)307-332
Number of pages26
JournalJournal of Intelligent Information Systems
Issue number2
Early online date27 Dec 2013
Publication statusPublished - Apr 2014


  • Graph mining
  • Anomaly detection


Dive into the research topics of 'Finding the Most Descriptive Substructures in Graphs with Discrete and Numeric Labels'. Together they form a unique fingerprint.

Cite this