Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata

Cited literature [39 references]  Display  Hide  Download

https://hal.inria.fr/hal-01573398
Contributor : Sabeur Aridhi <>
Submitted on : Wednesday, August 9, 2017 - 2:12:12 PM
Last modification on : Wednesday, April 21, 2021 - 8:52:05 AM

File

IS_2017_Revised.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

1660

Files downloads

441