Finding the Most Descriptive Substructures in Graphs with Numeric Labels
Michael Davis, Weiru Liu, Paul C. Miller · Research Portal (Queen's University Belfast) · 2012
Many graph datasets are labelled with numeric attributes. Frequent substructure discovery algorithms usually ignore these attributes; in this paper we show that they can be used to improve discrimination and search performance. 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 propose an outlierdetection step during substructure discovery to prune anomalous vertices and edges, which gives more weight to the most descriptive substructures. Our experiments on a real-world access control database returns similar substructures to Subdue with 30% fewer graph isomorphism tests.