Ph.D Elise Desmier
Co-evolution pattern mining in dynamic attributed graphs
Download Draft here
Defended on July 15th 2014 at INSA de Lyon
Committee
Pr. Jean-François Boulicaut, INSA Lyon, LIRIS, co-directeur
Pr. Bruno Crémilleux, Université de Caen, GREYC
Pr. Éric Gaussier, Université Grenoble 1, LIG
Pr. Donato Malerba, Univ. Degli Studi di Bari Aldo
Moro, Italy
Dr. Marc Plantevit, Université Lyon 1, LIRIS,
co-directeur
Pr.
Pascal Poncelet,
Université Montpellier 2, LIRMM
Résumé. Cette thèse s’est déroulée dans le cadre du projet ANR FOSTER, “FOuille de données Spatio-Temporelles : application à la compréhension et à la surveillance de l’ERosion” (ANR-2010-COSI-012-02, 2011-2014). Dans ce contexte, nous nous sommes intéressés à la modélisation de données spatio-temporelles dans des graphes enrichis de sorte que des calculs de motifs sur de telles données permettent de formuler des hypothèses intéressantes sur les phénomènes à comprendre. Plus précisément, nous travaillons sur la fouille de motifs dans des graphes relationnels (chaque noeud est identifié de façon unique), attribués (chaque noeud du graphe est décrit par des attributs qui sont ici numériques), et dynamiques (les valeurs des attributs et les relations entre les noeuds peuvent évoluer dans le temps). Nous proposons un nouveau domaine de motifs nommé motifs de co-évolution. Ce sont des triplets d’ensembles de noeuds, d’ensembles de pas de temps et d’ensembles d’attributs signés, c’est à dire des attributs associés à une tendance (croissance,décroissance). L’intérêt de ces motifs est de décrire un sous-ensemble des données qui possède un comportement spécifique et a priori intéressant pour conduire des analyses non triviales. Dans ce but, nous définissons deux types de contraintes, une contrainte sur la structure du graphe et une contrainte sur la co-évolution de la valeur des attributs portés par les noeuds. Prenons par exemple un graphe de co-publications scientifiques où les noeuds sont des auteurs reliés par une arête s’ils ont co-publié au moins un article au temps donné et où les attributs sont le nombre de publications dans un ensemble de conférences à chaque temps. Dans ce contexte, un motif peut être un ensemble d’auteurs qui ont co-publié ensemble sur plusieurs pas de temps et dont les publications ont augmenté sur ces pas de temps dans un sous-ensemble des conférences. Pour confirmer la spécificité du motif par rapport au reste des données, nous définissons trois mesures de densité qui tendent à répondre à trois questions. À quel point le comportement des noeuds en dehors du motif est similaire à celui des noeuds du motif ? Quel est le comportement du motif dans le temps, est-ce qu’il apparaît soudainement ? Est-ce que les noeuds du motif ont un comportement similaire seulement sur les attributs du motif ou aussi en dehors ? Considérant notre exemple, nous souhaitons extraire un ensemble d’auteurs dont les tendances de publication diffèrent des autres auteurs et sont spécifiques aux temps du motifs, et dont les tendances de publication diffèrent sur les autres conférences. Nous proposons l’utilisation d’une hiérarchie sur les attributs comme connaissance à priori de l’utilisateur afin d’obtenir des motifs plus généraux et adaptons l’ensemble des contraintes à l’utilisation de cette hiérarchie. Cette hiérarchie se traduit dans notre exemple par des attributs nouveaux comme par exemple “conférences de fouille de données” et le motif peut alors porter sur une conférence précise ou sur la tendance de publication dans les conférences de fouille de données. Finalement, pour simplifier l’utilisation de l’algorithme par l’utilisateur en réduisant le nombre de seuils à fixer et pour extraire uniquement l’ensemble des motifs les plus intéressants, nous utilisons le concept de “skyline” réintroduit récemment dans le domaine de la fouille de données. Nous proposons ainsi trois algorithmes MINTAG, H-MINTAG et Sky-H-MINTAG qui sont complets pour extraire l’ensemble de tous les motifs qui respectent les différentes contraintes. L’étude des propriétés des contraintes (anti-monotonie, monotonie/anti-monotonie par parties) nous permet de les pousser efficacement dans les algorithmes proposés et d’obtenir ainsi des extractions sur des données réelles dans des temps raisonnables. Afin de valider notre méthode, nous expérimentons sur plusieurs jeux de données (graphes) créés à partir de données réelles.
Abstract.
This thesis was conducted within the project ANR FOSTER,
“Spatio-Temporal Data Mining: application to the understanding and
monitoring of erosion” (ANR-2010-COSI-012-02, 2011-2014). In this
context, we are interested in the modeling of spatio- temporal data in
enriched graphs so that computation of patterns on such data can be
used to formulate interesting hypotheses about phenomena to understand.
Specifically, we are working on pattern mining in relational graphs
(each vertex is uniquely identified), attributed (each vertex of the
graph is described by numerical attributes) and dynamic (attribute
values and relations between vertices may change over time). We propose
a new pattern domain that has been called co-evolution patterns. These
are trisets of vertices, times and signed attributes, i.e., attributes
associated with a trend (increasing or decreasing). The interest of
these patterns is to describe a subset of the data that has a specific
behaviour and a priori interesting to conduct non-trivial analysis. For
this purpose, we define two types of constraints, a constraint on the
structure of the graph and a constraint on the co-evolution of the
value worn by vertices attributes. Let us consider a graph of
scientific co-publications where vertices are authors that are
connected by an edge if they co-authored at least one paper at any
given time and where the attributes are the number of publications in a
set of conferences at every time. In this context, a pattern can be a
set of co-authors who have published together on several times and
whose publications have increased over the time steps in a subset of
the conferences. To confirm the specificity of the pattern with regard
to the rest of the data, we define three measures of density that tend
to answer to three questions. How similar is the behaviour of the
vertices outside the co-evolution pattern to the ones inside it? What
is the behaviour of the pattern over time, does it appear suddenly?
Does the vertices of the pattern behave similarly only on the
attributes of the pattern or even outside? Considering our example, we
want to extract a set of authors whose trends of publication differ
from other authors and are specific to the times of the pattern, and
whose trends differ on other conferences. We propose the use of a
hierarchy of attributes as an a priori knowledge of the user to obtain
more general patterns and we adapt the set of constraints to the use of
this hierarchy. This hierarchy is reflected in our example by new
attributes such as “data-mining conferences” and patterns can then
focus on the publication trend on a specific conference or in data
mining conferences. Finally, to simplify the use of the algorithm by
the user by reducing the number of thresholds to be set and to extract
only all the most interesting patterns, we use the concept of “skyline”
reintroduced recently in the domain of data mining. We propose three
constraint-based algorithms, called MINTAG, H-MINTAG and Sky-HMINTAG,
that are complete to extract the set of all patterns that meet the
different constraints. These algorithms are based on constraints, i.e.,
they use the anti-monotonicity and piecewise
monotonicity/anti-monotonicity properties to prune the search space and
make the computation feasible in practical contexts. To validate our
method, we experiment on several sets of data (graphs) created from
real-world data.
Publications