In this Habilitation à Diriger des Recherches, I present the main results I have contributed to in the areas pattern mining in augmented graphs.

Materials:

• The report is available here: hdr_main.pdf
• Slides: pdf, pptx

<note>This work will be defended the 14th December 2018 at 10am in Room C1, bâtiment Nautibus, Villeurbanne. </note>

The members of the jury are:

• Toon Calders, Professor at University of Antwerp, reviewer,
• Florent Masseglia, Research Director at INRIA Sophia Antipolis - Méditerranée, reviewer,
• Dino Pedreschi, Professor at University of Pisa, reviewer,
• Angela Bonifati, Professor at Université Claude Bernard Lyon 1,
• Bruno Crémilleux, Professor at Université de Caen Normandie,
• Eric Gaussier, Professor at Université de Grenoble Alpes,
• Céline Robardet, Professor at INSA Lyon,
• Alexandre Termier, Professor at Université de Rennes 1.

In this Habilitation à Diriger des Recherches thesis, I present the main results I have contributed to in the field of pattern mining in augmented graphs.

Graphs are a powerful mathematical abstraction that enables to depict many real world phenomena. Vertices describe entities and edges identify relations between entities. Such graphs are often augmented with additional pieces of information. For instance, the vertices or the edges are enriched with attributes describing them and are called vertex (respectively edge) attributed graphs. Graphs can also be dynamic, i.e., the structure and the values of vertex attributes may evolve through time. The discovery of patterns in such graphs may provide actionable insights and boost the user knowledge.

This manuscript is structured in two parts. In the first part, I discuss the different pattern domains for augmented graphs I contributed to define. This includes the discovery of co-evolution patterns in dynamic attributed graphs, the study of links between the graph structure and the vertex attributes and the discovery of exceptional attributed subgraphs. I first introduce the co-evolution patterns to analyze dynamic attributed graphs as well as interestingness measures to assess these patterns according to each dimension of the graphs (i.e., the dynamics, the vertex attributes organized within a hierarchy or not, and the vertices). Examples of co-evolution patterns in spatio-temporal data are reported. I then present two pattern domains to analyze the links between the vertex attributes and the graph structure. These two types of patterns are illustrated on co-authorship network built from DBLP. This part ends with the discovery of exceptional attributed subgraphs in edge or vertex attributed graphs. The proposed methods are rooted in Subgroup Discovery / Exceptional Model Mining.

In the second part, I discuss how to find pattern of higher interest by taking into account the domain knowledge, user feedback and user's prior knowledge through different contributions. I first present a method that borrows mobility models from statistical physics to assess the unexpectedness of some trajectories in mobility network. This allows the discovery of exceptional attributed subgraphs by taking into account spatial information (i.e., distance between vertices, importance of the vertices in term of population). I then present a method to take the user feedback into biased quality measures in interactive explorations. This method is defined in the context of social media analysis, especially geo-located event detection. Based on user feedback, liked tags and areas are fostered thanks to a biased quality measure. Eventually, I address the problem of subjective interestingness in attributed graphs to take into account the user's prior knowledge. A particular interest is given to the assimilation of the patterns by the user. To ease this assimilation, alternative descriptions of exceptional attributed subgraphs are provided.

Finally, I conclude this thesis by discussing some research perspectives.