MR-SimLab: Scalable subgraph selection with label similarity for big data

Abstract : With the increasing size and complexity of available databases, existing machine learning and data mining algorithms are facing a scalability challenge. In many applications, the number of features describing the data could be extremely high. This hinders or even could make any further exploration infeasible. In fact, many of these features are redundant or simply irrelevant. Hence, feature selection plays a key role in helping to overcome the problem of information overload especially in big data applications. Since many complex datasets could be modeled by graphs of interconnected labeled elements, in this work, we are particularly interested in feature selection for subgraph patterns. In this paper, we propose MR-SimLab, a MapReduce-based approach for subgraph selection from large input subgraph sets. In many applications, it is easy to compute pairwise similarities between labels of the graph nodes. Our approach leverages such rich information to measure an approximate subgraph matching by aggre-gating the elementary label similarities between the matched nodes. Based on the aggregated similarity scores, our approach selects a small subset of informative representative subgraphs. We provide a distributed implementation of our algorithm on top of the MapReduce framework that optimizes the computational efficiency of our approach for big data applications. We experimentally evaluate MR-SimLab on real datasets. The obtained results show that our approach is scalable and that the selected subgraphs are informative.
Liste complète des métadonnées

Littérature citée [39 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01573398
Contributeur : Sabeur Aridhi <>
Soumis le : mercredi 9 août 2017 - 14:12:12
Dernière modification le : vendredi 5 octobre 2018 - 13:10:09

Fichier

IS_2017_Revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Wajdi Dhifli, Sabeur Aridhi, Engelbert Mephu Nguifo. MR-SimLab: Scalable subgraph selection with label similarity for big data. Information Systems, Elsevier, 2017, 69, pp.155 - 163. 〈10.1016/j.is.2017.05.006〉. 〈hal-01573398〉

Partager

Métriques

Consultations de la notice

1465

Téléchargements de fichiers

89