Demesmaeker, Florian
[UCL]
Nijssen, Siegfried
[UCL]
Ghrab, Amine
[Euranova]
Due to the availability of rich network data, graph mining techniques have been improved to handle the emergence of such heterogeneous data. Exploratory data analysis in rich networks aims at discovering interesting information in complex data and is an open challenge. In this work we search for repeating structures or patterns that represent an association between two entities according to some of their features. Patterns can be found in social networks. Let us say that we observe a high number of relationships between American and Chinese people. This is a pattern that we may find in a social network. However, since a large number of people live in the USA and China, it is not surprising that the number of relationships between people of these two countries is important. On the other hand observing the same high number of connections between Belgian and Chinese people is more surprising. In this work we search for surprising features associations in networks that we model by attributed graphs. To quantify how interesting a pattern is, we use a hypothesis testing framework. We define a null model that we assume has generated the data at hand. We then evaluate how likely it is that a pattern occurs under the null model. The earlier mentioned type of pattern can be found using the graph cube framework proposed by Zhao et al. This framework defines one network per combination of node features. Afterwards we show that there is a relationship between our graph mining approach and the frequent itemset mining literature. We propose a mapping from pattern mining in attributed graphs to a frequent itemset mining setting and compare our method with some techniques from this literature. Different experiments are performed on the MovieLens dataset and we show the interpretability of the results.
Bibliographic reference |
Demesmaeker, Florian. Graph cube mining. Ecole polytechnique de Louvain, Université catholique de Louvain, 2017. Prom. : Nijssen, Siegfried ; Ghrab, Amine. |
Permanent URL |
http://hdl.handle.net/2078.1/thesis:10691 |