Scalable Substructure Discovery Algorithm For Homogeneous Multilayer Networks

Arshdeep Singh, Abhishek Santra and Sharma Chakravarthy · 2025

Read Scalable Substructure Discovery Algorithm For Homogeneous Multilayer Networks by Arshdeep Singh, Abhishek Santra and Sharma Chakravarthy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19328.txt.

Introduction

Arshdeep Singh, Abhishek Santra, and Sharma Chakravarthy build a scalable way to find repeating patterns inside multilayer networks. Their work appeared in twenty twenty-five. Such networks stack several layers of links, which suits data with many kinds of ties.

Their method splits the problem by layer. Each layer is mined on its own, and the results are then composed into patterns for the whole network. They prove the composition step is correct. The system runs on a distributed framework, so it grows with data size. Tests on large made-up and real networks measure speed and response time. The authors argue the split approach stays both accurate and efficient where whole-network mining bogs down.

Catalog record

CREATORArshdeep Singh, Abhishek Santra and Sharma Chakravarthy
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-19328

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Scalable Substructure Discovery Algorithm For Homogeneous Multilayer Networks Arshdeep Singh, Abhishek Santra and Sharma Chakravarthy Abstract Graph mining analyzes real-world graphs to find core substructures (connected subgraphs) in applications modeled as graphs. Substructure discovery is a process that involves identifying meaningful patterns, structures, or components within a large data set. These substructures can be of various types, such as frequent patterns, motifs, or other relevant features within the data. To model complex data sets – with multiple types of entities and relationships – multilayer networks (or MLNs) have been shown to be more effective as compared to simple and attributed graphs. Analysis algorithms on MLNs using the decoupling approach have been shown to be both efficient and accurate. Hence, this paper focuses on substructure discovery in homogeneous multilayer networks (one type of MLN) using a 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 one of the distributed processing frameworks (the Map/Reduce paradigm) to provide scalability. After establishing the correctness, we analyze the speedup and response time of the proposed algorithm and approach through extensive experimental analysis on large synthetic and real-world data sets with diverse graph characteristics. I Introduction Substructure discovery is an unsupervised approach to data mining to infer new knowledge and is typically applied to graph representations. Frequent patterns are a common concept in data mining that refers to item sets, subsequences, or substructures that occur frequently in a given data set, meeting or exceeding a user-defined threshold. By identifying frequent subgraphs, we can gain insights into the underlying structure of the data and identify recurring patterns or motifs. Graph models have been used to analyze the World Wide Web’s structure [ 1 ] , social-media data, bio-informatics data [ 2 ] , atoms and covalent relationships in chemistry [ 3 ] , etc. Graphs are better than other data representations that embed inherent relationships among objects or entities and are also easy to understand. They use vertices and edges where each vertex of the graph will correspond to an entity and each edge is a relationship between two entities. Applications can be modeled using several graph alternatives: (i) Simple graphs, (ii) Attributed graphs, and (iii) Multilayer networks. Need for Multilayer Networks: Social networks and many other applications often include diverse types of nodes and relationships between them. Modeling or representing them as simple graphs (also termed a network) by using only one type of node and relationship often leads to an oversimplification of reality and information loss. Attributed graphs are better, but lack algorithms for analysis. Sociologists have long acknowledged the significance of using distinct types of connectivity among the same group of individuals [ 4 ] . Therefore, such systems are better studied through multilayer networks. Multilayer networks are a more general framework that allows for the analysis of complex systems with multiple interacting units and inter-dependencies that are not properly captured by simple graphs. In a multilayer network, each layer represents a different type of interaction or relationship between the system’s constituents. For example, in a social network, one layer may represent friendships between individuals, while another layer may represent professional LinkedIn connections. By analyzing the interactions between layers, it is possible to gain insights into the emergent behavior of the system as a whole. Fig. 1 : MLN Types Multilayer networks can be of several types, including (i) homogeneous (HoMLNs, Figure 1 (a)), (ii) heterogeneous (HeMLNs, Figure 1 (b)), and (iii) hybrid (HyMLNs, Figure 1 (c)), depending on the type of layers and connections between them. Figure 1 shows these types of multilayer networks. Since the focus of this paper is HoMLNs, we start with a formal definition of a MLN. Definition 1 A multilayer network MLN(G,X) , is defined by two sets of graphs. The set G=\{G_{1},G_{2},\ldots,G_{n}\} contains simple graphs (one for each layer), where G_{i}(V_{i},E_{i}) is defined by a set of vertices V_{i} and a set of edges E_{i} . An edge e(v,u)\in E_{i} , connects vertices v and u , where v,u\in V_{i} . The set X=\{X_{1,2},X_{1,3},\ldots,X_{m-1,m}\} consists of bipartite graphs 1 1 1 The number of bipartite graphs can be less or even more than the number of graphs/layers. That is, m can be <= or even > n . . Each graph X_{i,j}(V_{i},V_{j},L_{i,j}) is defined by two sets of vertices V_{i} and V_{j} and a set of edges (or links) L_{i,j} , such that for every link l(a,b)\in L_{i,j} , a\in V_{i} and b\in V_{j} , where V_{i} ( V_{j} ) is the vertex set of graph G_{i} ( G_{j} ). Some of X_{i,j} can be empty. For HoMLNs, inter-layer graphs are implicit as nodes in layers form a common subset having same identity. Problem Addressed: Given a homogeneous MLN (HoMLN) with l number of layers – G 1 (V, E 1 ), G 2 (V, E 2 ), …, G l (V, E l ) , where V and E_{i} are the vertex and edge set in the i^{th} layer – the goal is to discover interesting substructures of the HoMLN for any r layers correctly and efficiently using the decoupling approach. For correctness, r HoMLN layers under consideration are conflated into a simple graph using the Boolean OR operator, and substructures discovered on that simple graph are used as the Ground Truth (GT). Why Map/Reduce?: We have used the Map/Reduce paradigm as an example of the distributed and parallel processing approach. Without loss of generality, any other paradigm (e.g., Spark, Pregel) can be used in its stead without the need to modify the algorithms presented in this paper. Implementation will change slightly based on the choice of the framework. Contributions of this paper are: • Map/Reduce Algorithm for substructure discovery in a layer. • Map/Reduce Composition algorithm to correctly generate substructures spanning Homogeneous layers. • Map/Reduce Partitioned approach to layer graph processing. • Correctness proof of both independent expansion and the composition algorithm (Ho-ICA). • Extensive experimental analysis on a large number of synthetic and real-world graphs. • Accuracy with ground truth, response time, and speedup comparisons. Roadmap: MLN analysis alternatives are briefly discussed in Section II to highlight our choice. Section III has related work. Preliminaries and terminology are outlined in Section IV . Section V details the substructure and composition algorithm and Map/Reduce implementation of the proposed substructure discovery. Correctness of algorithms is proved in Section VI . Detailed experimental evaluation is given in Section VIII . Section IX has conclusions. II MLN Analysis Alternatives and Challenges Figure 2 shows three alternatives to perform analysis on MLNs. Figure 2 (a) shows the traditional approach, where a MLN is conflated into a simple graph using type-independent [ 5 ] or projection-based [ 6 ] approaches. As both ignore type information for the transformation, they do not support the structure and semantic preservation of MLNs. Moreover, as observed in the literature, without additional mappings , these approaches are likely to result in some information loss and distortion of properties [ 7 ] , or hide the effect of different entity types and/or different intra-

Read the complete text