New algorithm counts the hidden building blocks of multilayer networks

Networks are rarely as simple as a single web of connections. A city’s commuters ride metro lines, trains and buses; students relate to each other as friends, classmates or online contacts; a worm’s neurons communicate through several distinct kinds of links. Scientists represent such systems as multilayer networks, and among the most widely used special cases are multiplex networks, in which the same set of nodes exists in every layer. A new study published in Applied Network Science introduces MPCount, a computational tool that counts, exactly and efficiently, all the small subgraphs of a specified size in multiplex networks, filling a gap that researchers say has limited the practical analysis of these systems.

Subgraphs are the small structural pieces of a network: triangles, stars, chains and other configurations of a handful of nodes and edges. Counting how often each type appears, a task known as a subgraph census, is a core operation in network science because it underpins higher-level analyses such as the detection of statistically overrepresented subgraphs called motifs and the computation of graphlet degree signatures. Yet the task is computationally hard. It is directly related to the subgraph isomorphism problem, which is NP-complete for general graphs, so researchers are often restricted to small subgraphs or to specific predefined structures. The authors of the new work, André Couto Meira and Pedro Ribeiro, note that no general polynomial-time solution is known, which drives the search for efficient methodologies.

While single-layer networks have been studied for decades, multilayer network analysis has gained momentum only in recent years, supported by foundational formalisms that established a coherent theoretical framework and by some general software tools. The authors argue that the practical side of multilayer analysis still remains relatively underdeveloped, limiting the ability to fully explore these systems and potentially leaving important phenomena undiscovered. For the multilayer case, the existing literature on subgraph counting is limited, and the few available approaches are often difficult to apply or computationally inefficient. Some existing methods work only for very specific subgraph types, such as three-node subgraphs, three-edge subgraphs or triangles; others are limited to two layers, use frequency concepts that do not allow overlapping edges between occurrences, or focus on graphlets and the structural position of nodes inside multiplex subgraphs.

Multiplex networks add a specific twist to the counting problem. Because subgraphs may span multiple layers, researchers must decide when two subgraphs count as the same structure. The new work distinguishes two notions of multiplex isomorphism. Node isomorphism requires a bijection between the nodes that preserves the exact same connections in each layer. Node-layer isomorphism additionally allows a bijection between the layers themselves, so that structures differing only by an exchange of layer labels are treated as equivalent. The authors illustrate the difference with triangles in a three-layer example network: under node isomorphism there are three types of triangles, while under node-layer isomorphism two of those types merge into one because the red and yellow layers can be mapped onto each other. In a real application, one concept might be more suitable than the other, and MPCount supports both.

The new method builds on well-established machinery from single-layer network analysis. The ESU algorithm, designed to eliminate symmetry redundancy, enumerates each subgraph exactly once by selecting a starting node and recursively expanding partial subgraphs through a maintained list of candidate nodes. Later algorithms such as FaSE preserved this non-redundant enumeration strategy but substantially improved the efficiency of isomorphism testing by grouping subgraphs according to their shared topological structure and executing a single isomorphism test per group. FaSE takes advantage of a specialized data structure called a g-trie, analogous to a prefix tree used for organizing words by common prefixes, which organizes graphs by their shared substructures and yields significant savings in both memory and execution time.

MPCount adapts this machinery to the multiplex setting. The tool takes as input a multiplex network, represented as an edge list, and a subgraph size k. During reading of the network it constructs an auxiliary overlap matrix that records whether there is any connection between two nodes across all layers, with each element true only if at least one edge connects the nodes in any layer. This aggregation is not a computation time bottleneck, since it can be done during edge reading, and in terms of memory it is the same as containing a new layer. The overlap network then allows the use of efficient enumeration algorithms originally designed for monoplex networks, particularly an adapted version of ESU enhanced with ideas from FaSE, which guarantees that each subgraph is enumerated exactly once.

During enumeration, each time a new node is added to a subgraph, a label is generated to encode its connections in all layers, multiplying the monoplex process by the number of layers. These labels are stored in a g-trie, allowing repeated patterns to be aggregated and avoiding redundant computations in subsequent steps. The leaf nodes of the g-trie store the frequencies of each subgraph type, with many occurrences producing the same tree path and ending on the same leaf. Different leaf nodes may still correspond to the same isomorphic class, so the tool relies on the external isomorphism detection program nauty to obtain each class. The authors emphasize that heuristic approximations such as the Weisfeiler-Leman test are not adequate for their purposes, because unlike that test, which is designed to quickly and approximately distinguish non-isomorphic graphs without guaranteeing correctness, their task requires grouping topologies into exact isomorphic classes.

To reduce the multiplex isomorphism problem to a classical one, the method reconstructs each subgraph representation into a supra-adjacency matrix, which encodes all layer connections and preserves the structural properties of the subgraph. Supernodes, which remain consistent across all subgraphs, are systematically added to the matrix, and nauty computes canonical orderings of the nodes so that two subgraphs are isomorphic if and only if they share the same canonical representation. Crucially, a matrix is created for each g-trie leaf rather than for each individual subgraph, drastically reducing the number of isomorphism checks and speeding up the process. The final output is a complete census of subgraphs of a given size, grouped by isomorphic class along with their frequencies, complemented with visualization resources that present the results as Scalable Vector Graphics in HTML pages, with edges split into colored segments representing connections in different layers.

The experimental comparison faced a sparse field: the authors report that they found only two available implementations that could be directly compared, an adaptation of the SubEnum algorithm by Takes and colleagues, developed for finding motifs in multiplex corporate networks, and the pymnet library, which supports both types of multiplex isomorphism but relies on a more general multilayer enumeration approach. Experiments were conducted on a machine equipped with an Intel Core i7-4710HQ CPU, using a C++ implementation of MPCount that the authors make available online. The datasets combined synthetic networks randomly generated through the Erdős–Rényi model, with varying numbers of layers and nodes, and four real-world multiplex networks obtained from Manlio De Domenico’s website: VickChan, representing seventh grade students and different types of personal relationships; CSAarhus, consisting of five kinds of online and offline relationships between employees of a Computer Science department; CElegans, the connectome of the C. Elegans organism with layers of different types of neural connections; and AirLines, whose layers correspond to different airlines operating in Europe, of which the first 7 of the original 37 layers were used so the experiments could run in a reasonable amount of time.

Against pymnet, tested on undirected networks for subgraph sizes of 3, 4 and 5 nodes with a 24-hour cutoff, MPCount was always faster, by 3 to 5 orders of magnitude, while both methods found the same numbers of subgraph occurrences and isomorphic classes. Against the adapted SubEnum, MPCount was at least twice as fast at every tested scale. The comparison also surfaced a correctness problem in the competing tool: depending on the number of layers, the adapted SubEnum found the same number of occurrences but a different number of isomorphic classes, and testing on small hand-checkable networks led the authors to conclude that it was unable to identify the isomorphic classes correctly for networks with more than 6 layers, demonstrated on the AirLines network. The issue lies in the modification whereby each binary edge label was replaced with a numeric digit label using a single character, which is insufficient to encode a large number of layers; the authors note that the adaptation was developed with a three-layer scenario in mind, in which it calculates accurately. For synthetic networks, where the Erdős–Rényi model generates random networks independently in each layer and produces higher subgraph occurrences than most real networks, the tests identified subgraphs in the tens of millions and confirmed a consistent number of subgraphs processed per second, suggesting performance largely independent of network characteristics. The authors plan to extend the work to the more general multilayer case, reduce the memory footprint by exploiting matrix sparsity, and pursue parallelism and sampling to trade accuracy for speed on larger networks.

Subject of Research: An exact subgraph counting algorithm for multiplex networks

Article Title: Counting subgraphs in multiplex networks

Article References: Meira, A. C., & Ribeiro, P. (2026). Counting subgraphs in multiplex networks. Applied Network Science, 11(1), Article 58. https://doi.org/10.1007/s41109-026-00812-4

Image Credits: AI Generated

DOI: 10.1007/s41109-026-00812-4

Keywords: multiplex networks, multilayer networks, subgraph census, network motifs, graph mining, isomorphism, g-trie, nauty, Applied Network Science, computational complexity, network science, algorithm