Mining exceptional closed patterns in attributed graphs

• DOI: 10.1007/s10115-017-1109-2
• Publication Date: 2017-10-06T01:05:54Z
• Authors: Anes Bendimerad; Marc Plantevit; Céline Robardet
• Keywords: Pruning; Closure (psychology); Sample (material)

Geo-located social media provide a large amount of information describing urban areas based on user descriptions and comments. Such data make possible to identify meaningful city neighborhoods on the basis of the footprints left by a large and diverse population that uses this type of media. In this paper, we present some methods to exhibit the predominant activities and their associated urban areas to automatically describe a whole city. Based on a suitably attributed graph model, our approach identifies neighborhoods with homogeneous and exceptional characteristics. We introduce the novel problem of exceptional subgraph mining in attributed graphs and propose a complete algorithm that takes benefits from closure operators, new upper bounds and pruning properties. We also define an approach to sample the space of closed exceptional subgraphs within a given time budget. Experiments performed on ten real datasets are reported and demonstrated the relevancy of both approaches, and also showed their limits.