Efficient Community Detection in Boolean Composed Multiplex Networks

Networks (or graphs) are used to model the dyadic relations between entities in a complex system. In cases where there exists multiple relations between the entities, the complex system can be represented as a multilayer network, where the network in each layer represents one particular relation (or feature). The analysis of multilayer networks involves combining edges from specific layers and then computing a network property. Different subsets of the layers can be combined. For any Boolean combination operation (e.g. AND, OR), the number of possible subsets is exponential to the number of layers. Thus recomputing for each subset from scratch is an expensive process. In this paper, we propose to efficiently analyze multilayer networks using a method that we term network decomposition. Network decomposition is based on analyzing each network layer individually and then aggregating the analysis results. We demonstrate the effectiveness of using network decomposition for detecting communities on different combinations of network layers. Our results on multilayer networks obtained from real-world and synthetic datasets show that our proposed network decomposition method requires significantly lower computation time while producing results of high accuracy.

I. INTRODUCTION
Networks (or graphs) are used to represent the pair-wise relationship between entities in a system. The entities may be connected by multiple relations (or features). For example, traffic accidents can be related if they occur in the same location, or under the same light condition; actors can be related if they acted in movies of the same genre; authors can be related if they publish in the same conferences. The relationships pertaining to each feature can be represented as a network. This group of networks are together termed as a multiplex or homogeneous multilayer network, where each network (layer) denotes a distinct relationship based on a feature among the same set of entities.
Motivation. Often different sets of layers need to be combined and analyzed. For example, if a city with limited resources was trying to reduce accidents, they might be interested in finding the top two conditions that lead to accidents. In this case, the combination of all pairs of layers have to be tested. Another example would be to identify which subset of social networking platforms form the most strongly connected groups. In this case, all possible combinations of the layers representing the platforms have to analyzed.
In the current approach, multiplexes are analyzed by combining the required layers into a single network, which we term the composed network. Network analysis operations such as community detection or finding high centrality vertices is then applied to this composed network. It is easy to see that the analysis has to be recomputed from scratch for different combinations of layers, rendering the analysis process very expensive. As a solution, we propose an elegant method, which we term network decomposition, for finding communities in different compositions of the network layers.
Our Contribution. Our main contribution is to apply network decomposition for efficiently finding communities in different Boolean compositions of network layers. The principle is to first analyze the property, such as communities, in each individual layer and then aggregate the results to obtain the final results on the composed network (see Figure 1). Thus, we only need to analyze each network once, and then combine the results as per the aggregation method. Our goal is to apply network decomposition to efficiently find communities (i.e. strongly connected groups on nodes) in layers of multiplex that are combined using the Boolean AND and OR operations. For the AND (OR) operation, the combined network will contain an edge, if there exists an edge in all (any one) of the individual layers. An AND-Composition represents how multiple features together affect an analysis. For example, in identifying regions that become accident prone due to poor lighting conditions as well as bad roads. An OR-Composition represents how any one of the features affects a property. For example, in finding the group of people who are friends via least one of the social networking platforms among Facebook, Linkedin and Twitter.
Using network decomposition, we generate communities for each of the individual layers and then combine the resultant communities based on the Boolean operators. As our results in Section IV demonstrate, our approach significantly reduces the computational costs while providing results of high accuracy.
Problem Statement: Given a set of layers G 1 , G 2 , . . . , G x , that are combined using a Boolean operation and a community detection algorithm COM M , develop an aggregation algorithm Θ, such that COM M ( Our goal is to find an aggregation algorithm Θ, such that the results of finding the communities in the individual layers and then aggregating them via Θ, should be the nearly the same as the communities obtained from the composed network where the layers are combined using the Boolean operator 1 . The remainder of the paper is organized as follows. In Section II, we provide a brief description of community detection in multiplexes. In Section III, we present our contribution of community detection using network decomposition. In Section IV we present the experimental results. In Section V, we discuss related research and conclude in Section VI with a discussion of our future plans.

II. COMMUNITY DETECTION IN MULTIPLEXES
We describe how multiplex networks are created from datasets, and how communities are obtained in AND and OR composition of layers.

A. Creating Multiplex Networks
In a multirelational dataset, entities are related through multiple features. For example, people can be connected through different social networks. Authors of academic papers can be connected based on the common journals where they publish.
In a multiplex or multilayer network, each feature is represented as a separate network or layer. The set of entities (or nodes) remain the same in each layer. The edges, based on interactions between the entities change across the layers with respect to the corresponding feature. Table I lists the notations of the terms of multilayer networks discussed in this paper.
1) Modeling the IMDb Dataset as a Multiplex: We use the Internet Movie Database (IMDb) to illustrate how a multiplex is constructed. The IMDb is an online database that contains information on television programs and movies including actors, directors, genre, and year of release [1].
We create a multiplex where the entities represent actors and two actors are connected to each other if they have acted in the same movie. Each layer in the multiplex represents a movie genre, such as comedy, drama, action, etc. As per the notations in Table I, the IMDb multiplex is defined follows: • I: The set of actors form the entities, I = {I 1 , I 2 , ...}. • f : The set of features corresponds to the genres, f = {f 1 , f 2 , ...}. The number of layers, N L , is equal to |f |. 1 We use "nearly equal" rather than "equal" because community detection is non-unique and changes to the order in which vertices are processed can slightly change the results.
Represntative node for i th entity in the k th layer V k Set of nodes in the k th layer An edge in the k th layer E k Set of edges in the k th layer The m th community in the k th layer The k th layer represents the relations among the set of actors, I, with respect to the genre f k .
If the i th and the j th actors have worked together in at least one movie that belongs to the k th genre, f k , G k , contains the edge (u i k , u j k ). In Figure 2 we have selected two genres, comedy (f 1 ) and drama (f 2 ) to form the two layers, G 1 and G 2 , respectively. This multiplex shows the co-actor relationship among 16 actors (denoted by nodes numbered from 1 to 16) with respect to these genres. The same 16 actors are present in both layers. Note that each co-actor network has a distinct structure. By taking the information from the two networks together we can gain interesting insights to the data, as follows.
For example, actors I 3 and I 8 have never worked together in a drama, but have worked together in a comedy. Thus this pair of actors may together be more likely to be considered in a comedy, rather than a drama. Also observe that the actor I 14 is the actor with most connections in the drama genre, while in the case of comedies, actor I 11 is one of the nodes with the most connections, i.e. worked with most number of actors.

B. Community Detection in Multiplexes
Community detection involves finding items with similar properties by identifying tightly connected groups of vertices. We consider non-overlapping communities, that is, there are no common vertices or edges between two communities. Figure  3 shows the communities for the composed layers, G 1AN D2 and G 1OR2 for IMDB multiplex in Figure 2.
Bridge Edges. We term the external edges that connect two communities as bridge edges. Formally, if there exists an edge, (u i k , u j k ), such that u i k ∈ C m k and u j k ∈ C n k , where m = n, then this edge is a bridge edge. Bridge edges form links between two distinct communities. In the AND and OR composedlayer of Figure 3, the actors I 1 and I 5 belong to different communities, but are connected by a bridge edge. The actors I 9 and I 1 5 have a bridge edge in the OR composed network, but not in the AND-composed network.
1) Communities in AND-Composed Layers.: AND composition of layers in a multiplex allows users to find communities that are related across multiple features. Examples of some queries that can be addressed by the AND composition are; • Groups of actors who have expertise in working together in both comedies and dramas (IMDb multiplex). • Author groups who publish in all of these conferences; ICDM, SIGMOD and VLDB (DBLP multiplex). • Groups of accidents that have similar conditions for all these features; light conditions, weather conditions, road conditions, and speed limit (Accident Multiplex).
The standard practice is to combine the layers using the AND operation, i.e. only edges that occur in all the layers are included. Then a community detection algorithm, such as Infomap, is executed on the combined network. This single graph approach, termed C-SG-AND, is given in Algorithm 1.

Algorithm 1 Algorithm for C-SG-AND
2) Communities in OR-Composed Layers: OR-composition forms a composed network that includes an edge if it appears in any of the layers. Algorithm 2 shows the steps of this single network based community detection using the OR operation, termed as C-SG-OR. Examples of queries that can be addressed by the OR composition are; • Groups of actors who have acted together in either a comedy or drama (IMDb multiplex).
• Groups of authors who have published in at least one of these conferences, ICDM, VLDB, SIGMOD (DBLP multiplex). • Groups of accidents that have at least one condition in common (Accident Multiplex).

Algorithm 2 Algorithm for C-SG-OR
{Initialize the set of communities to NULL.} 2: for each community pair say, C p i and C q j do 3: {Add new community to the set of communities.} 5: end for

III. OUR CONTRIBUTION: NETWORK DECOMPOSITION FOR EFFICIENT COMMUNITY DETECTION ON MULTIPLEX
The Boolean composition of the layers of a multiplex provides in-depth analysis of the database. However, for any single Boolean operation, say AND, 2 N − 1 different combinations are possible. Thus the cost of finding the communities on each of them separately is very expensive. Moreover, if the networks do not change, several computations are rendered redundant. For example, consider finding the communities in the composed layer G 1AN D2AN D3 and G 1AN D2AN D4 . In this case, the composed layer related to G 1AN D2 remains unchanged, but has to be recomputed.
As a solution, we propose network decomposition for efficient community detection on multiplex networks. In network decomposition, the communities in each layer are identified separately and the results are then aggregated to obtain the results with respect to the composed network. Note that the storage required is only of the order of O(V * f ), where V is the number of vertices in each layer and f is the number of features/layers. Figure 4 shows the communities in each of the layers of the example IMDB network.
The challenge is to develop aggregation algorithms, Θ, that can correctly aggregate the communities from each of the layers to obtain the communities over the composed network. We present the aggregation methods for AND and OR composition. For ease of understanding we will discuss the algorithms with respect to two layers. Note, however, that any binary operations can be easily extended to multiple layers.

A. Vertex based Community Detection of AND Composed Layers (CV-AND)
An earlier paper on obtaining communities in ANDcomposed layers was presented in [2]. We discuss this work, termed CV-AND, here for completeness.
CV-AND (see Algorithm 3) heavily depends on the presence of self-preserving communities. A community is self preserving if the vertices in it are so tightly connected such that any connected subset of the vertices will form a smaller community rather than joining an existing larger community. Formally, consider a graph G i , with a community whose vertices are given by the set C v . Now consider a subset of vertices C S v ∈ C v . If the vertices in C S v form a community by themselves, for any subset , then community C v is self preserving. The main result of [2] was that if the communities from the layers are self preserving, then the communities of the AND-composed graph can be obtained by taking the vertex based intersection of the communities from the individual layers.
Drawbacks The main drawback of CV-AND is that for most networks, there is no guarantee that the communities will be self-preserving. If this algorithm is applied without testing for self-preserving communities, the results may not be accurate.
As an example, consider the community C 5 1 in the comedy layer of the network (Figure 4). This community is not self preserving, and when combined with community C 4 2 in the drama layer, which has the same vertices, it gives one large community, { I 6 , I 11 , I 15 ,I 16 ,I 17 ,I 18 }. In reality, as seen in This is a subtle but important difference because the community id determines whether two entities are similar. If two disconnected groups of vertices are placed in the same community (as is possible when using CV-AND), then, two dissimilar groups are marked to be similar, which is incorrect.

Algorithm 4 Algorithm for CE-AND
Require: Communities from layers G i and G j : We address these limitations by developing a community detection method, CE-AND (see Algorithm 4), that is based on the intersection of edges rather than vertices as follows.
For every pair of communities, C m i (V m i , E m i ) from layer G i and C n j (V n j , E n j ) from layer G j , the edge-based community intersection, E m i ∩ E n j , will produce k disconnected edge-sets, E 1 iAN Dj , E 2 iAN Dj , ..., E k iAN Dj . These edge sets will form the AND-composed communities, C 1 iAN Dj , C 2 iAN Dj , ..., C k iAN Dj .
Correctness and Limitations. Figure 5 shows how the communities are obtained for the example network using CE-AND. Comparing this result to that in Figure 3, we see that most of the communities are obtained with the exception of the singleton node 8 and the common bride edge (1,5). Lemma 1. Let V i,j be a set of vertices that are assigned to the same community in all the layers of the multiplex. Let the set of common edges in all the layers whose both endpoints are in V i,j , be E i,j . If |E i,j | ≥ |V i,j | − 1, then the community composed of vertices V i,j will be detected by CE-AND.
Proof. The proof is based on the observation that if a subgraph has n vertices and n − 1 edges, then the subgraph is connected. Since this subgraph is a community and is present in all the layers, therefore the community will be detected. Lemma 1 provides a lower bound (n − 1) on the density of common edges of the communities that is needed for them to be detected by the CE-AND.
Lemma 2. The CE-AND method returns all the communities of size ≥ 2 that were returned by the CV-AND method.
Proof. The proof is derived from Lemma 1. All selfpreserving communities have to be densely connected, and thus satisfying the lower bound. Thus CE-AND will detect all the common self preserving communities.
Lemma 3. Common edges that form a bridge edge in at least one layer will not be detected by CE-AND.
Proof. This proof follows from Algorithm 4 in that both endpoints of the common edge have to be in the same community to be considered. Lemma 3 highlights the limitations of finding communities in cases where the common communities do not share a dense substructure. Note that these limitations only occur for communities that are not dense. Since communities are informally defined as tightly connected groups of vertices, these sparse subpgraphs in most cases may not be relevant communities at all. We illustrate the issues in Figure 6.
The left-hand panels of Figure 6 shows two layers. The top right panel shows the communities obtained by the standard single network approach (C-SG-AND). The bottom right panel shows the communities obtained by CE-AND.
Note that the community C 3 SG−AN D produced by C-SG-AND contains the edges (h, o) and (l, s) that act as bridges in both Layer L1 and L2. Thus CE-AND is not able to detect this community, and instead produces two communities, C 4 CE−AN D and C 5 CE−AN D , which should be merged into one by taking the bridge edges into account.
Also consider the community C 2 SG−AN D which consists of the edges (a, i) and (e, m) that are bridges in Layer L1, but are part of the community C 2 2 in Layer L2. As only those edges that are within community in all layers are considered, CE-AND produces two communities, C 2 CE−AN D and C 3 CE−AN D .

C. Edge based Community Detection of OR Composed Layers
We now consider how to obtain communities in ORcomposed networks. Note that the number of edges in the OR-composed network will at least as much, generally more, than the number of edges in each layer. Thus for any two layers G i and G j , the total number of edges is |E i ∪ E j |.
The computational complexity of community detection algorithms are at least proportional to the size of the graph. Thus the denser the graph, the more time will be required to find the communities. Thus for the OR-composed case, the goal is not only to lower the time by reducing the need to recompute different compositions of layers, but also to reduce the size of the graph to be analyzed.
To recreate the communities of OR Composed Layers, we propose the CE-OR algorithm (given in Algorithm 5 and illustrated in Figure 7). The CE-OR method reduces the size of the graph to be analyzed by leveraging the fact that the common communities across layers can be processed as a single node. The steps of the CE-OR algorithm are as follows; Algorithm 5 Algorithm for CE-OR Require: Communities from layers G i (V, E i ) and G j (V, E j ): if ∃ u, v, r: (u, v) ∈ E r i or (u, v) ∈ E r j , u ∈ U and v ∈ V then Overview of CE-OR. Find the common communities in all the network layers (Line 1) by using CE-AND. Then construct a metagraph (OR-MG), as follows. Each metanode represents a set of vertices. Combine each of the vertices in a common community into a metanode (Line 2-4). Assign all remainder vertices, that are not part of any common community into singleton sets. Each of these sets is also a metanode (Line 5-9). Connect two metanodes, (U, V ) via a metaedge, if there exists an intra-community (within community) edge, in any one of the layers between an element (node) of U and an element (node) of V (Line [10][11][12][13][14]. Apply appropriate weights to these edges (Line 15). Apply community detection on the metagraph (Line 16). The communities in the OR-composed network are obtained by expanding the metanodes in the communities obtained by the CE-OR algorithm.
Assigning Weights to Metaedges. Note that the metanodes represent vertex sets of varying sizes, and the number of edges between them represent the degree of similarity. Therefore although the original graph is composed on unweighted edges, the edges in the metagraph have to be weighted to quantify the extent of this similarity. A critical component of the CE-OR algorithm is based on correctly assigning these weights.
We propose two different weight metrics to quantity the similarity between two meta nodes. For any meta edge (A, B), let V A and V B be the set of entity nodes in the ANDcomposed communities, respectively. Further, let the set of intra-community edges between V A and V B be E A,B . Then the weight to the metaedge can be computed as follows;  Figure 7 illustrates how the CE-OR algorithm is applied to identify communities in the ORcomposed layers of the example IMDb graph. First the CE-AND communities obtained in Figure 5 and the remaining vertex I 8 are used to form the metanodes (Figure 7 (a)). Then these nodes are connected based on the intra-community edges. These edges are weighted in the meta graph using w f (Figure 7 (b)). A community detection algorithm on the metagraph produces the communities of the OR-composed layers (Figure 7 (c)). Comparing with the communities obtained by the C-SG-OR method in Figure 3, to those obtained by expanding the communities in the metanodes (Figure 7 (d)), we see that all the communities have been obtained. However, the bridge edges between the communities are missing. Lemma 4. Let V k , |V k | = n, be a set of vertices. Let E k be the set of edges whose both endpoints are in V k , i.e. ∀(x, y) ∈ E k , x ∈ V k and y ∈ V k . If all (x, y) ∈ E k , form an intracommunity edge in at least one of the network layers and the vertices in V k form a community in the OR-composed network, then this community will be detected by the CE-OR algorithm.
Proof. As per Algorithm 5, any edge that is an intracommunity edge in at least one of the layers will be included in the metagraph. If a community in the OR-composed layer is formed only of intra-edges, then in the metagraph, given appropriate weighting function, these set of edges would also form a dense subgraph and hence a community.
Lemma 5. If a community in the OR-composed layer contains significant number of edges that are bridge (inter-community) edges in all the layers, then the community cannot be detected in its entirety by the CE-OR algorithm.
Proof. Since the CE-OR algorithm analyzes only the intracommunity edges, the bridge edges will not be part of the metagraph. Thus any community that is composed of mainly bridge edges will not be part of the metagraph and hence will not be detected by CE-OR. Consider the community C 2 SG−OR generated by C-SG-OR approach that has edges (i, l), (h, m), (j, o) and (l, t) which are not intra-community edges in any of the layers, and are present as bridge edges in only one of the layers. These edges will not be part of the metagraph and thus CE-OR does not know that they exist. CE-OR, thus, generates three communities C 2 CE−OR , C 3 CE−OR and C 4 CE−OR , instead of merging them into one community, as per the C-SG-OR method.
However in the community C 1 SG−OR generated by C-SG-OR, the edges (a, b) and (d, f) are bridge edges in one layer but are intra-community edges in another layer. Therefore these edges will be part of the metagraph. Thus CE-OR can use these edges and correctly generate the community C 1 CE−OR . The primary limitations of our CE-AND and CE-OR algorithms is due to the non-inclusion of bridge edges. In the AND-composed network, we rationalize this non-inclusion by positing that communities formed solely of bridge edges cannot be dense, and hence are not strong communities. In the OR-composed network, note that we only exclude an edge if it is a bridge edge in all the layers. This is an infrequent case where bridge nodes from all layers come together to form communities. Our experiments in Section IV, justify this policy of not including bridge edges by demonstrating that the normalized mutual information (NMI) values between the communities returned by CE-AND and C-SG-AND are in general high.

IV. EMPIRICAL RESULTS
In this section we compare the performance and accuracy of our proposed algorithms with the ground truth results obtained by the standard methods, C-SG-AND and C-SG-OR.

A. Experimental Setup:
Since the results of community detection depend heavily on the type of algorithm used [3], to control this parameter in the experiment we use the popular community detection algorithm Infomap [4], both to find the communities in the single network approach and the network decomposition approach. Our algorithms were implemented in C++ and were executed on a Linux machine with 8 GB RAM and installed with UBUNTU 16.10.
Datasets Used. We performed our experiments on multiplexes created from three real-world datasets and one synthetic dataset created using the RMAT [5] graph generator. We selected the real-world datasets such that they were sufficiently large and contained communities. To test on larger networks with more vertices, we created the synthetic RMAT dataset. The details of the datasets are as follows (also see Table II); • IMDb: From the IMDB dataset [1], we created the following three layers in the multiplex, with the nodes representing the actors. In the first layer, (L1, co-acting) two nodes are connected if they co-acted in at least one movie. In the second layer, (L2, rating) two nodes are connected if the average ratings of the movies where they acted were similar. In the third layer, (L3, genre) two nodes are connected if they acted in movies of similar genres.   In layer L2 we applied perturbation to 1% of the edges and in layer L3 to 5% of the edges. We limited the number of perturbations because if the network structure is significantly changed between the layers, the number of bridge edges also increase.
Ground Truth and Accuracy Metrics: Since our goal is to achieve the results obtained by the standard C-SG-AND and C-SG-OR methods, we use the communities obtained from these methods as the ground truth. We disregard communities of just one vertex, since these result due to an artifact of the algorithm rather than provide any meaningful analysis. We use two metrics to evaluate the accuracy of the communities -i) Normalized Mutual Information (NMI) that measures the quality with respect to the participating entity nodes only and ii) modified-NMI that also takes into account the topology of the communities. For both metrics higher is better, with maximum value of 1 and minimum of 0(definitions in [8]). Each multiplex has 3 layers. Thus, a total of 4 compositions are possible (3 for 2-layers and 1 3-layers). Thus we compare results for 8 (4 combinations X 2 Boolean operations) composed networks.

B. Accuracy of the Aggregation Algorithms.
For the AND-composed networks we show in Figure 9, the average NMI and m-NMI of all the four multiplexes with respect to the ground truth for the CV-AND and CE-AND methods. The results show that the accuracy obtained with CE-AND is higher than that from CV-AND.
For the OR-composed networks we show in Figure 10, the average NMI and m-NMI of all the four multiplexes with respect to the ground truth for the two weighting metrics; Aggregation (w a ) and Fractional (w f ). The results show that the accuracy obtained using both the metrics are similar.  In Table III we provide the accuracy values for all the different layer compositions with respect to CE-AND for the AND composition and CE-OR with Fractional Weights. As can be seen nearly all the values are high, ≥ 70%.
Some low values occur for the CE-OR method. An egregious example is IMDb (L1, L2) for which the accuracy results are less than 1%! In this case the metagraph had 193 nodes, and on running the community detection algorithm 56 communities were obtained. However, the ground truth communities obtained by C-SG-OR had only 2 communities. This happened because there existed many bridge edges in  Table III: Accuracy Values using CE-AND on the different compositions of the datasets.
the layers that were not included in the metagraph. Moreover, because the communities represented in the metanodes were small in size, the weights were also lower and could not combine the communities.

C. Performance of the Aggregation Algorithms
We now compare the time taken to obtain the communities using the aggregation methods (CV-AND, CE-AND and CE-OR) with respect to C-SG-AND and C-SG-OR. Figure 11 shows that the time to compute the communities over all the 4-composed layers is significantly lower for both CV-AND and CE-AND methods than C-SG-AND. When the layers are sparse, CE-AND will be faster than CV-AND, as can be seen for DBLP multiplex. However if the network layers are dense, then the edge-based intersection approach of CE-AND has a higher cost as compared to the CV-AND. Figure 11: Efficiency of CV-AND and CE-AND as compared to C-SG-AND Figure 12 gives the time for executing CE-OR. For CE-OR, CE-AND is used as a subroutine. One scan of community edges is required to generate the meta graph (OR-MG) on which we apply Infomap. If the layers are sparse and the multiplex contains many bridge nodes, then cost of generating the meta graph and applying Infomap will become an overhead as compared to simply applying Infomap on OR graph (C-SG-OR approach). This can be seen from the DBLP multiplex where sparse layers (density of densest layer (SIGMOD) = Figure 12: Efficiency of CE-OR as compared to C-SG-OR 0.0001!) make the CE-OR 67% less efficient as compared to C-SG-OR. However, for multiplexes with fewer bridge edges (IMDb, Accident), CE-OR is significantly faster.

V. RELATED WORK
Analysis of Multilayer Networks. Homogeneous multilayer networks [9], [10] are used to handle interactions among the same set of entities such as co-authorship [11], citation across different topics [12], and relationships across different social media platforms [13]. Multiplexes have also been analyzed in form of adjacency tensors [14], [15].
Community detection in temporal homogeneous multilayer networks use spectral optimization of the modularity function [16], [17]. Techniques based on information theory have been proposed for reducing the number of layers in multilayer protein-protein interactions [18]. Software for creating or analysing multiplex networks include Muxviz [19], [20], MAMMULT [21], [22], MultiTensor [23] and Pymnet [24]. However, they support only a few simple analysis functions, not community detection.
Recent work has also extended community detection algorithms for multilayer networks based on matrix factorization [32], pattern mining [33], cluster expansion philosophy [34] and Bayesian probabilistic models [35], but all of these use the single layer approach. To the best of our knowledge, we are the first to infer the communities of the combined network from communities of individual layers.

VI. CONCLUSION AND FUTURE WORK
In this paper, we presented algorithms for efficiently finding communities in Boolean composed layers of multiplex networks. The results show that for most cases our algorithms are significantly faster than the standard methods and produce results of similar quality. The only cases that our algorithm fails is when the layers have significantly more bridge edges.
In future plan, we will investigate how to include some percentage of bridge edges without reducing the computation time. We also plan to explore adaptive techniques that can select between the network decomposition and standard methods as suitable. Finally, we also aim to develop methods to efficiently find communities when the NOT operator is used.


DARTS+: Improved Differentiable Architecture Search with Early Stopping

Recently, there has been a growing interest in automating the process of neural architecture design, and the Differentiable Architecture Search (DARTS) method makes the process available within a few GPU days. In particular, a hyper-network called one-shot model is introduced, over which the architecture can be searched continuously with gradient descent. However, the performance of DARTS is often observed to collapse when the number of search epochs becomes large. Meanwhile, lots of"skip-connects"are found in the selected architectures. In this paper, we claim that the cause of the collapse is that there exist cooperation and competition in the bi-level optimization in DARTS, where the architecture parameters and model weights are updated alternatively. Therefore, we propose a simple and effective algorithm, named"DARTS+", to avoid the collapse and improve the original DARTS, by"early stopping"the search procedure when meeting a certain criterion. We demonstrate that the proposed early stopping criterion is effective in avoiding the collapse issue. We also conduct experiments on benchmark datasets and show the effectiveness of our DARTS+ algorithm, where DARTS+ achieves $2.32\%$ test error on CIFAR10, $14.87\%$ on CIFAR100, and $23.7\%$ on ImageNet. We further remark that the idea of"early stopping"is implicitly included in some existing DARTS variants by manually setting a small number of search epochs, while we give an explicit criterion for"early stopping".

The common practice of NAS first derives an architecture search space, and then finds the best architecture in the search space with a specific search method. Early works of NAS usually adopt the REINFORCE method [25,40] and evolutionary algorithms [26] for searching effective architectures. However, obtaining state-of-the-art architectures with such methods involves huge computational cost (e.g., thousands of GPU days [40]), because a large number of architectures need to be trained and evaluated. Recently, one-shot methods [2,3,20,25,34] are proposed to reduce the search cost. Among the one-shot methods, Liu, Simonyan, and Yang [20] propose the Differentiable Architecture Search (DARTS) method to relax the search space to be continuous, so that one can search architectures and learn model weights directly with gradient descent. In particular, DARTS encodes the architecture search space with continuous parameters and performs searching with bi-level optimization, where the model weights and architecture parameters are optimized with training data and validation data alternatively. DARTS can reduce the search cost from thousands of GPU days to a few GPU days while keeping comparable performance.
Despite the efficiency of DARTS, a severe issue underlying DARTS has been found [4]. Namely, after a certain searching epochs, the number of skip-connects increases dramatically in the selected architecture, which results in poor performance of the selected architecture. We call the phenomenon of performance drop after a certain number of epochs the "collapse" of DARTS. To tackle such issue, Chen et al. [4] propose a search space regularization in their P-DARTS, where dropout [29] is used to alleviate the dominance of skip-connects during the search procedure, and the number of skip-connects is manually controlled after the search procedure. However, this approach involves more hyper-parameters like dropout rate and the number of skip-connects, which need to be carefully tuned by human experts. Moreover, Stamoulis et al. [30] propose Single-Path NAS using the one-level optimization instead of the bi-level optimization in DARTS, where the architecture parameters and model weights are updated simultaneously. However, the search space of Single-Path NAS is carefully designed. If searching is done in the original search space of DARTS, one-level optimization will perform worse than bilevel ones [20]. In summary, the mechanism of the collapse of DARTS is still unknown and needs to be addressed.
In this paper, we first show the cause of the collapse of DARTS is that there exist cooperation and competition in the bi-level optimization in DARTS, where the architecture parameters and model weights are updated alternatively. In particular, we give an explanation of why lots of skip-connects are involved in the selected architectures in DARTS and why they hurt the performance. To avoid the collapse of DARTS, we add the simple and effective "early stopping" paradigm to the original DARTS, named "DARTS+", where the search procedure stops by a certain criterion, illustrated in Fig. 1(a). We remark that recent progresses of DARTS, including P-DARTS [4], Auto-DeepLab [19] and PC-DARTS [37], also adopt the early stopping idea implicitly where fewer search epochs are manually set in their methods.
Moreover, we conduct sufficient experiments on benchmark datasets to demonstrate the effectiveness of the proposed DARTS+ algorithm. Specifically, DARTS+ achieves the state-of-the-art 2.32% test error on CIFAR10 and 14.87% test error on CIFAR100, while the search time is less than 0.4 GPU days. When transferring to ImageNet, DARTS+ achieves the state-of-the-art 23.7% top-1 error and impressive 22.5% top-1 error if SE-Module [12] is introduced. DARTS+ is also able to search on ImageNet directly and achieves 23.9% top-1 error.
In summary, our main contributions are listed as follows: • We study the collapse issue of the DARTS method, and point out the underlying reason is the cooperation and competition in the bi-level optimization.
• We introduce an efficient "early stopping" paradigm to DARTS to avoid the collapse, and propose an effective criterion for early stopping.
• we conduct extensive experiments on benchmark datasets to demonstrate the effectiveness of the proposed algorithm, which achieves the state-of-the-art results on all of them.

Collapse of DARTS
There is a severe issue underlying DARTS [20], that lots of skip-connects tend to appear in the selected architecture when the number of searching epoch is large, making the performance poor. The phenomenon of performance drop is called the "collapse" of DARTS in our paper. In this section, we first give a quick review of the original DARTS, and then point out the collapse issue of DARTS. Moreover, we will discuss the cause of the collapse issue.

Preliminary: DARTS
The goal of DARTS is to search for a cell, which can be stacked to form a convolutional network or recursively connected to form a recurrent network. Each cell can be regraded as a directed acyclic graph (DAG) of N nodes {x i } N −1 i=0 , where each node represents a network layer. We denote the operation space as O, and each element is a candidate operation, e.g., zero, skip-connect, convolution, maxpool, etc. Each edge (i, j) of DAG represents the information flow from node x i to x j , which consists of the candidate operations weighted by the architecture parameter α (i,j) . In particular, each edge (i, j) can be formulated by a function , and the weight of each operation o ∈ O is a softmax of the architecture parameter α (i,j) , that is p . An intermediate node is x j = i<jō (i,j) (x i ), and the output node x N −1 is depth-wise concatenation of all the intermediate nodes excluding input nodes. The above hyper-network is called one-shot model, and we denote w as the weights of the hyper-network.
For the search procedure, we denote L train and L val as the training and validation loss respectively. Then the architecture parameters are learned with the following bi-level optimization problem: After obtaining architecture parameters α, the final discrete architecture is derived by: 1) setting o (i,j) = arg max o∈O,o =zero p

Collapse Issue
It has been observed in DARTS that lots of skip-connects are involved in the selected architecture, which makes the architecture shallow and the performance poor. As an example, let us consider searching on CIFAR100. The alpha value of skip-connects (green line in Fig. 2(c)) becomes large when the number of search epochs is large, and thus the number of skip-connects increases in the selected architecture as shown in the green line in Fig. 2(a). Such shallow network has less learnable parameters than deep ones, thus it has weaker expressive power. As a result, architectures with lots of skipconnects have poor performance, i.e., collapsed, indicated as the blue line in Fig. 2(a). To be more intuitive, we draw the selected architectures from different search epochs on CIFAR100 in Fig. 1(b). When the number of search epochs increases, the number of skip-connects in the selected architecture also increases. Such phenomenon can also be observed on other datasets, such as CIFAR10 and ImageNet.
To avoid the collapse, one might propose to adjust search hyper-parameters, such as 1) adjusting learning rates, 2) changing the portion of training and validation data, and 3) adding regularization on skip-connects like dropout. Unfortunately, such methods would only delay the collapse as the choice of hyper-parameters is not the essential cause of collapse.
The underlying reason of the collapse issue is that there exist cooperation and competition in the bi-level optimization in DARTS, where the architecture parameters and model weights are updated alternatively. Intuitively, the architecture parameters and model weights are well optimized at the beginning, and then gradually turn to compete against each other after a while. Since the model weights have more With a proper early stopping mechanism, we may obtain better architectures, or we may end up with collapsed architectures with lots of skip-connects.
advantages than the architecture parameters in the competition, (e.g., the number of the model weights is far more than the number of architecture parameters, the architecture parameters are not sensitive to the final loss in the bi-level optimization, etc.), the architecture parameters cannot beat the model weights in the competition. As a result, the performance of selected architecture will first increase and then decrease (See blue lines in Fig. 2(a)).
In particular, at the initial state of the search procedure, the one-shot model underfits the training data. Thus, architecture parameters α and model weights w, which are learnable parameters of the one-shot model, will get better together at the beginning of the search procedure. This is the cooperation period. Note that the first cells in the whole oneshot model can touch the fresh data information, while the data that feed to the last cells are much noisier. If we allow different cells to have distinct architectures in the oneshot model, the first cells will learn features more quickly than the last cells. Since the feature representation learned by the last cells is relatively worse than the one learned by the first cells, the last cells are more likely to select more skip-connects to obtain the good feature representation directly from the first cells. Fig. 3 shows the learned normal cell architectures at different layers if we allow different architectures at different stages 1 . It can be seen that the algorithm tends to select deep architectures with learnable operations (namely, operations with parameters to be learned such as convolutions) in the first cells ( Fig. 3(a)), while architectures with many skipconnects are preferred in the last cells (Fig. 3(c)). If different cells are forced to have the same architecture, as DARTS does, skip-connects will be broadcasted from the last cells  The major advantage of the proposed stopping criterion is its simplicity. Compared with other DARTS variants, DARTS+ only needs a few modifications based on DARTS, and can significantly increase the performance with less search time. As mentioned in Sec. 2.2, too many skipconnects will hurt the performance of DARTS. On the other hand, an appropriate number of skip-connects is helpful for transferring the information from first layers to last layers and stabilizing the training process, e.g., ResNet [10], which makes the architectures achieve better performance. Therefore, stopping by Criterion 1 is a reasonable choice. Criterion 1 is motivated by P-DARTS [4], where the number of skip-connects in the cell of final architecture is manually cut down to two. Although both DARTS+ and P-DARTS keep two skip-connects in the cell of their final architectures, DARTS+ is essentially different from P-DARTS in dealing with the skip-connects. P-DARTS does not intervene the number of skip-connects during the search procedure, but only replaces the redundant skip-connects with other operations as a post-processing after the search procedure finishes. In contrast, our DARTS+ ends up with desired architectures with a proper number of skip-connects to avoid the collapse of DARTS. It controls the number of skipconnects more directly and also more effectively (See Table 1 for a performance comparison between DARTS+ and P-DARTS). Now we give some intuition for Criterion 1 in Fig. 2. The red circles in Fig. 2(a-b) denote the points that the ranking of architecture parameters α for learnable operations (e.g.,  convolutions) becomes stable on CIFAR10, CIFAR100 and Tiny-ImageNet-200, respectively. Note that only the operation with the maximum α value is chosen in the selected architecture. When the ranking of α becomes stable, the operations to be selected are nearly determined, which implies that the search is almost saturated. The experiments also verify that after the point that the ranking of α becomes stable (red circles in Fig. 2(a)), the validation accuracies of selected architectures on all datasets (blue lines) tend to decrease, i.e., collapse. It can be seen that this point is close to the stopping point when Criterion 1 holds (the red dash line in Fig. 2(a)), thus stopping by Criterion 1 can prevent the collapse of DARTS.
Since the stable ranking of architecture parameters α for learnable operations indicates the saturated search procedure in DARTS, we can also use the following stopping criterion: Criterion 1* The search procedure stops when the ranking of architecture parameters α for learnable operations becomes stable for a determined number of epochs (e.g., 10 epochs).
We remark that Criterion 1 is much easier to operate, but if one needs stopping more precisely or other search spaces are involved, Criterion 1* could be used instead. We further remark that our early stopping paradigm solves an intrinsic issue of DARTS and is orthogonal to other tricks, thus it has potential to be used in other DARTS-based algorithms to achieve better performance.
We note that recent state-of-the-art differentiable architecture search methods also introduce the early stopping idea in an ad hoc manner. To avoid the collapse, P-DARTS [4] uses 1) searching for 25 epochs instead of 50 epochs, 2) adopting dropout after skip-connects, and 3) manually reducing the number of skip-connects to two. Auto-DeepLab [19] starts to update architecture parameters for a few epochs after updating weight parameters. PC-DARTS [37] uses partialchannel connections to reduce search time, and therefore more epochs are needed for convergence of searching. Thus, setting 50 training epochs is also an implicit early stopping paradigm.

Datasets
In this section, we conduct extensive experiments on benchmark classification datasets to evaluate the effectiveness of the proposed DARTS+ algorithm. We use four popular datasets including CIFAR10 [16], CIFAR100 [16], Tiny-ImageNet-200 3 and ImageNet [6]. CIFAR10/100 consists of 50K training images and 10K testing images and the resolution is 32 × 32. Tiny-ImageNet-200 contains 100K 64 × 64 training images and 10K testing images. ImageNet is obtained from ILSVRC2012 [27], which contains more than 1.2M training images and 50K validation images. We follow the general setting on the ImageNet dataset where the images are resized to 224 × 224 for training and testing.

Architecture Search
Unless specified, we use Criterion 1 as the stopping condition for DARTS+ in the experiments. Note that the stopping points by Criterion 1 and 1* are almost the same in the proposed search space, and we will discuss the two criteria in detail in Sec. 4.4.

Implementation Details.
We have similar experimental settings as DARTS. The experiments are carried out in two stages: architecture search and architecture evaluation. The search space is the same as DARTS which has 8 candidate operations including skip-connect, max-pool-3x3, avg-pool-3x3, sep-conv-3x3, sep-conv-5x5, dil-conv-3x3, dil-conv-5x5, zero, and the structure of each operation is exactly the same as DARTS.
For CIFAR10 and CIFAR100, we use the same one-shot model as the original DARTS in which 8 cells (i.e. 6 normal cells and 2 reduction cells) with 16 channels are trained for searching. We use a half of the training data to train the model weights and the other half to update the architecture parameters. We search for a maximum of 60 epochs with batch size 64. We use SGD to optimize the model weights with initial learning rate 0.025, momentum 0.9 and weight decay 3 × 10 −4 . Adam [15] is used to optimize architecture parameters with initial learning rate 3 × 10 −4 , momentum (0.5, 0.999) and weight decay 10 −3 . Early stopping is applied at certain epoch when Criterion 1 introduced in Sec. 3 is met.
For Tiny-ImageNet-200, the one-shot model is almost the same as CIFAR10/100 except that a 3 × 3 convolution layer with stride 2 is added on the first layer to reduce the input resolution from 64 × 64 to 32 × 32. Other settings are the same as those used in CIFAR10/100, including the "early stopping" criterion.
For ImageNet, following [37], the one-shot model starts with three 3 × 3 convolution layers with stride 2 to reduce the resolution from 224 × 224 to 28 × 28, and the rest of the network consists of 8 cells. We select 10% data from the training set for updating model weights, and another 10% for updating architecture parameters. We search with batch size 512 for both training and validation sets. SGD is used for model weights training with initial learning rate 0.2 (cosine 3 https://tiny-ImageNet.herokuapp.com/ learning rate decay), momentum 0.9, and weight decay 3 × 10 −4 . The architecture parameters are trained with Adam with learning rate 3 × 10 −3 , momentum (0.5, 0.999) and weight decay 10 −3 .
For all the datasets, the one-shot model weights and architecture parameters are optimized alternatively. The cell structure is determined by architecture parameters, following DARTS [20].
Search Results and Analysis. The proposed DARTS+ needs less searching time as "early stopping" is adopted. For CIFAR10, the search procedure requires 0.4 GPU days with a single Tesla V100 GPU, and stops at about 35 epochs. For CIFAR100, the searching time is 0.2 GPU days and the search procedure stops at about 18 epochs. For Tiny-ImageNet-200, searching stops at about 10 epochs. For Im-ageNet, the search procedure involves 200 epochs, and it requires 6.8 GPU days on Tesla P100 GPU.
The selected architectures are shown in Fig. 4. We observe that the cells searched by DARTS+ contain most convolutions and a few skip-connects.
It should be noticed that DARTS+ succeeds in searching with all three datasets including CIFAR10/100, Tiny-ImageNet-200 and ImageNet. However, the original DARTS fails to search on CIFAR100 as the selected architecture is full of skip-connects [4], and most previous works on differentiable search [4,20,34] do not search on ImageNet.

Architecture Evaluation
For each selected architecture, we follow the configurations and hyper-parameters of the previous works [4,20] for evaluation on different datasets.
Results on CIFAR10 and CIFAR100. We use network of 20 cells and 36 initial channels for evaluation to ensure a comparable model size as other baseline models. We use the whole training set to train the model for 2000 epochs with batch size 96 to ensure convergence. Other hyper-parameters are set the same as the ones in the search stage. Following existing works [18,25,26,41], we also add some enhancements including cutout, path dropout with probability 0.2 and auxiliary towers with weight 0.4.
The evaluation results are summarized in Table 1. For each selected cell from either CIFAR10 or CIFAR100, we report the performance on both datasets. With the simple "early stopping" paradigm, we achieve the best results with 2.32% test error on CIFAR10 and 14.87% test error on CIFAR100. The results are much better than the original DARTS, which gets 3% test error on CIFAR10 and 19.5% test error on CIFAR100 (See Fig. 2(a) with large epochs). The proposed DARTS+ is much simpler and better than other modified DARTS algorithms like P-DARTS and PC-DARTS. ProxylessNAS uses a different search space, and it involves more search time. Moreover, DARTS+ is much easier to implement than other modified DARTS variants including ASAP. We point out that "early stopping" can be used in many other differentiable search algorithms and search spaces to obtain better architectures.
We further increase the initial channel number from 36 to 50, and add more augmentation tricks including AutoAug-   ment [5] and mixup [39] to achieve better results. Table 1 shows that DARTS+ achieves impressive 1.68% test error on CIFAR10 and 13.03% test error on CIFAR100, demonstrating the effectiveness of DARTS+.
Results on Tiny-ImageNet-200. The network is similar as CIFAR10/100 where 20 cells and 36 channels are involved, except that an additional 3×3 convolution layer with stride 2 is inserted in the first layer. We transfer the architectures searched from other algorithms to Tiny-ImageNet-200 and evaluate the performance for fair comparison. Other experimental settings are the same as CIFAR10/100. The results are shown in Table 2. DARTS+ achieves the state-of-the-art 28.3% test error, which is much better than other baselines. Note that architecture searched on Tiny-ImageNet-200 with DARTS+ performs much better than DARTS and its parameter size is much larger than DARTS, because DARTS suffers from collapse and the architecture searched with DARTS contains lots of skip-connects. Desired architectures are more likely to be generated with the "early stopping" paradigm.
Results on ImageNet. We use the architecture searched directly from ImageNet for evaluation, and the architecture from CIFAR100 to test the tranferability of the selected architecture. We follow DARTS such that the number of cells is 14 and the initial number of channels is 48. We train the  The model is optimized with the SGD optimizer with an initial learning rate 0.8 (cosine decayed to 0), momentum of 0.9 and weight decay 3×10 −5 . We use learning rate warmup [9] for the first 5 epochs and other training enhancements including label smoothing [31] and auxiliary loss tower.
The experimental results are shown in Table 3. Note that we re-implement PC-DARTS and the results are reported. When searching on ImageNet with the proposed DARTS+, the selected architecture achieves impressive 23.9%/7.4% top-1/top-5 error, and the architecture transferred from CI-FAR100 achieves state-of-the-art 23.7%/7.2% error. The results imply that DARTS with "early stopping" succeeds in searching a good architecture with impressive performance on large-scale datasets with limited time.
We also adopt SE-module [12] in the architecture transferred from CIFAR100, and introduce AutoAugment [5] and mixup [39] for training to obtain better model. The results are shown in Table 3, and we achieve 22.5%/6.4% top-1/top-5 error with only additional 3M flops, showing the effectiveness of the selected architecture.

Effectiveness of Early Stopping
To further verify the effectiveness of DARTS+, we conduct extensive experiments on selected architectures at different epochs. The classification results on CIFAR10, CIFAR100 and Tiny-ImageNet-200 are shown in Fig. 2. We also point out the time to "early stop" under two criteria, marked as "red dashed line" and "red circle" respectively. We observe that the selected architecture performs worse with larger epochs, implying that the original DARTS suffers from the collapse issue. In contrast, "early stopping" is able to generate good architectures at both stopping criteria, regardless of the type of datasets.
We also compare "early stopping" Criterion 1 and 1* in Table 1 and Fig. 2. We observe that both criteria achieve comparable performance on all datasets as the stopping points are very close.

Conclusion
In this paper, we conduct comprehensive analysis and extensive experiments to show that DARTS suffers from the collapse problem, which is mainly caused by the cooperation and competition problem in the bi-level optimization in DARTS. We propose the "DARTS+" algorithm, in which the "early stopping" paradigm is introduced to avoid the collapse of DARTS. The experiments show that we succeed in searching on various benchmark datasets including largescale ImageNet with limited GPU days, and the resulting architectures achieve the state-of-the-art performances on all benchmark datasets. Moreover, it should be noticed that many recent progresses of DARTS could use "early stopping" to achieve better results, and the proposed "early stopping" criteria could be applied to many other types of search spaces, including the RandWire search space [35], mobile convnets search space [30], etc.