HDR of Céline Robardet


Subject:
Constraint-based pattern mining approaches for the analysis of relational attributed dynamic graphs

Summary:

In this Habilitation à Diriger des Recherches, I present the main results I have contributed to in the areas of local pattern extraction under constraints and of dynamic graph analysis. Constraint-based pattern mining covers data mining algorithms that apply an exact search strategy to achieve the exhaustive extraction of the whole set of patterns satisfying some constraints over the data. These constraints are Boolean expressions based on evaluation criteria that measure the relevance of patterns in a specific data set. Besides, the use of constraints increases the computational efficiency of the process, making possible to truncate the search space while preserving the completeness of the extraction. After studying the constraint properties that have been identified as useful in this framework, I discuss the special case of formal concept extraction under constraints. Then I introduce the principles of a generic algorithm that 'pushes' constraints with various properties in the data mining system to optimize its efficiency. Considering relational dynamic graphs, I present two case studies of mobility networks for which main global properties have been revealed thanks to statistical time-series analysis and clustering techniques. In the last part, I discuss my main contributions on local pattern discovery in attributed and/or dynamic relational graphs. I first present an approach to characterize the relationship between vertex attributes and the graph topology in static attributed graphs. It consists in the extraction of co-variations between vertex attributes and measures describing the relationship of the vertex with the rest of the graph. Then, I propose to analyze dynamic graphs by discovering the main temporal changes as locally strong associations between vertices and their evolution through time. Finally, I introduce the mining of trends in attributed dynamic graphs to identify connected parts of the graph whose vertex attributes evolve in the same way.


Defense date: monday, december 9, 2013