Substructure Discovery in Heterogeneous Multilayer Networks

Graph mining analyzes graphs to find core substructures (connected subgraphs) in applications that are modeled using graphs. These identified substructures, based on frequency or some other metric, are important as they reveal an inherent feature or property in the given graph/forest. Interesting substructures that are frequent or compress the graph well offer insights into hidden regularities. The process of finding these interesting patterns using unsupervised learning is termed substructure discovery. SUBDUE is an early main-memory algorithm developed for substructure discovery. Since then, this algorithm has been extended using disk-based, database-oriented approaches, and more recently using the Map/Reduce paradigm to exploit distributed and parallel processing. Graph sizes have increased steadily, thanks to the advent of the Internet and social network applications. To model complex datasets – with multiple types of entities and relationships - multilayer networks (or MLNs) have been shown to be effective. MLNs have also been shown to be superior as compared to simple and attributed graphs for modeling complex data. MLNs are also useful for modeling different data types using distinct layers. This paper focuses on substructure discovery in heterogeneous multilayer networks (one type of MLN) using the novel decoupling-based approach. In this approach, each layer is processed independently and then the results from two or more layers are composed to identify substructures in the entire MLN. The algorithm is designed and implemented, including the composition part, using the Map/Reduce paradigm for understanding speedup. After validating accuracy of results with ground truth, we analyze speedup and response time of the proposed algorithm and approach through extensive experimental analysis on large synthetic datasets with diverse graph characteristics.