{'fraction_non_alphanumeric': 0.04728456899195374, 'fraction_numerical': 0.01112749894128127, 'mean_word_length': 4.373087485288348, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 4, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
FirmTruss Community Search in Multilayer Networks

In applications such as biological, social, and transportation networks, interactions between objects span multiple aspects. For accurately modeling such applications, multilayer networks have been proposed. Community search allows for personalized community discovery and has a wide range of applications in large real-world networks. While community search has been widely explored for single-layer graphs, the problem for multilayer graphs has just recently attracted attention. Existing community models in multilayer graphs have several limitations, including disconnectivity, free-rider effect, resolution limits, and inefficiency. To address these limitations, we study the problem of community search over large multilayer graphs. We first introduce FirmTruss, a novel dense structure in multilayer networks, which extends the notion of truss to multilayer graphs. We show that FirmTrusses possess nice structural and computational properties and bring many advantages compared to the existing models. Building on this, we present a new community model based on FirmTruss, called FTCS, and show that finding an FTCS community is NP-hard. We propose two efficient 2-approximation algorithms, and show that no polynomial-time algorithm can have a better approximation guarantee unless P = NP. We propose an index-based method to further improve the efficiency of the algorithms. We then consider attributed multilayer networks and propose a new community model based on network homophily. We show that community search in attributed multilayer graphs is NP-hard and present an effective and efficient approximation algorithm. Experimental studies on real-world graphs with ground-truth communities validate the quality of the solutions we obtain and the efficiency of the proposed algorithms.


INTRODUCTION
Community detection is a fundamental problem in network science and has been traditionally addressed with the aim of determining an organization of a given network into subgraphs that express † These authors contributed equally. This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 16 [25]. Recently, a query-dependent community discovery problem, called community search (CS) [66], has attracted much attention due to its ability to discover personalized communities. It has several applications like social contagion modeling [70], content recommendation [12], and team formation [27]. The CS problem seeks a cohesive subgraph containing the query nodes given a graph and a set of query nodes.
Significant research effort has been devoted to the study of CS over single-layer graphs, which have a single type of connection. However, in applications featuring complex networks such as social, biological, and transportation networks, the interactions between objects tend to span multiple aspects. Multilayer (ML) networks [50], where nodes can have interactions in multiple layers, have been proposed for accurately modeling such applications. Recently, ML networks have gained popularity in an array of applications in social and biological networks and in opinion dynamics [7,58,61,65], due to their more informative representation than single-layer graphs. Example 1. Figure 1(a) is an ML network showing a group of researchers collaborating in various topics, where each layer represents collaborations in an individual topic.
To find cohesive communities in single-layer graphs, many models have been proposed, e.g., -core [66,67], -truss [43], -plex [73], and -clique [15]. Existing methods for finding cohesive structures in ML networks are inefficient. As a result, there is a lack of practical density-based community models in ML graphs. Indeed, there have been a number of studies on cohesive structures in ML networks [28,38,56,82]. However, they suffer from two main limitations. (1) The decomposition algorithms [28,38,56] based on these models have an exponential running time complexity in the number of layers, making them prohibitive for CS. (2) These models have a hard constraint that nodes/edges need to satisfy in all layers. It has been noted that ML networks may contain noisy/insignificant layers [28,35]. These noisy/insignificant layers may be different for each node/edge. Therefore, this hard constraint could result in missing some dense structures [35]. Recently, FirmCore structure [35] in ML graphs has been proposed to address these limitations. However, a connected FirmCore can be disconnected by just removing one edge, and it might have an arbitrarily large diameter. Both of these properties are undesirable for community models.
In addition to the above drawbacks of cohesive structures in ML networks, existing CS methods in ML graphs (e.g., [29,44,59]) suffer from some important limitations. (1) Free-rider effect [75]: some cohesive structure, irrelevant to the query vertices, could be included in the answer community. (2) Lack of connectivity: a community, at a minimum, needs to be a connected subgraph [43,76], but existing community models in ML graphs are not guaranteed to be connected. Natural attempts to enforce connectivity in these arXiv:2205.00742v2 [cs.SI] 17 Nov 2022 models lead to additional complications (see § 5.3 for a detailed comparison with previous community models).
(3) Resolution Limit [26]: in a large network, communities smaller than a certain size may not be detected. (4) Failure to scale: to be applicable to large networks, a community model must admit scalable algorithms. To the best of our knowledge, all existing models suffer from these limitations. To address the above limitations of existing studies, we study the problem of CS over multilayer networks. First of all, we propose the notion of ( , )-FirmTruss, based on the truss structure in simple graphs, as a subgraph (not necessarily induced) in which every two adjacent nodes in at least individual layers are in at least − 2 common triangles within the subgraph. We show that it inherits the nice properties of trusses in simple graphs, viz., uniqueness, hierarchical structure, bounded diameter, edge-connectivity, and high density. Based on FirmTruss, we formally define our problem of FirmTruss Community Search (FTCS). Specifically, given a set of query nodes, FTCS aims to find a connected subgraph which (1) contains the query nodes; (2) is a FirmTruss; and (3) has the minimum diameter. We formally show that the diameter constraint in FTCS definition avoids the so-called "free-rider effect".
In real-world networks, nodes are often associated with attributes. For example, they could represent a summary of a user's profile in social networks, or the molecular functions, or cellular components of a protein in protein-protein interaction networks. This rich information can help us find communities of superior quality. While there are several studies on single-layer attributed graphs, to the best of our knowledge, the problem of CS in multilayer attributed networks has not been studied. Unfortunately, even existing CS methods in single-layer attributed graphs suffer from significant limitations. They require users to input query attributes; however, users not familiar with the attribute distribution in the entire network, are limited in their ability to specify proper query attributes. Moreover, these studies only focus on one particular type of attribute (e.g., keyword), while most real-world graphs involve more complex attributes. E.g., attributes of proteins can be multidimensional vectors [36]. The recently proposed VAC model [57] for single-layer graphs does not require users to input query attributes, but is limited to metric similarity measures. To mitigate these limitations, we extend our FTCS model to attributed ML graphs, call it AFTCS, and present a novel community model leveraging the well-known phenomenon of network homophily. This approach is based on maximizing the -mean of similarities between users in a community and does not require users to input query attributes.
However, should a user wish to specify query attributes (say for exploration), AFTCS can easily support them. Moreover, it naturally handles a vector of attributes, handling complex features.
Since ML graphs provide more complex and richer information than single-layer graphs, they can benefit typical applications of single-layer CS [22] (e.g., event organization, friend recommendation, advertisement, etc.), delivering better solutions. Below we illustrate an exclusive application for multilayer CS.
Brain Networks. Detecting and monitoring functional systems in the human brain is an important and fundamental task in neuroscience [8,62]. A brain network (BN) is a graph in which nodes represent the brain regions and edges represent co-activation between regions. A BN generated from an individual subject can be noisy and incomplete, however using BNs from many subjects helps us identify important structures more accurately [52,59]. A multilayer BN is a multilayer graph in which each layer represents the BN of a different person. A community search method in multilayer graphs can be used to (1) identify functional systems of each brain region; (2) identify common patterns between people's brains affected by diseases or under the influence of drugs.
We make the following contributions: (1) We introduce a novel dense subgraph model for ML graphs, FirmTruss, and show that it retains the nice structural properties of Trusses ( § 4). (2) We formulate the problem of FirmTruss-based Community Search (FTCS) in ML graphs, and show the FTCS problem is NP-hard and cannot be approximated in PTIME within a factor better than 2 of the optimal diameter, unless P = NP ( § 5). (3) We develop two efficient 2-approximation algorithms ( § 6), and propose an indexing method to further improve efficiency ( § 7). (4) We extend FTCS to attributed networks and propose a novel homophily-based community model. We propose an exact algorithm for a special case of the problem and an approximation algorithm for the general case ( § 8). (5) Our extensive experiments on real-world ML graphs with groundtruth communities show that our algorithms can efficiently and effectively discover communities, significantly outperforming baselines ( § 9). For lack of space, some proofs are sketched. Complete details of all proofs and additional details can be found in Appendix.
Attributed Community Search. Given a set of query nodes, attributed CS finds the query-dependent communities in which nodes share attributes [20,42]. Most existing works on attributed singlelayer graphs can be classified into two categories. The first category takes both nodes and attributes as query input [14,21]. The second category takes only attributes as input, and returns the community related to the query attributes [13,83]. All these studies (1) require users to specify attributes as input, and (2) consider only simple attributes (e.g., keywords), limiting their applications. Most recently, Liu et al. [57] introduced VAC in single-layer graphs, which does not require input query attributes. However, they are restricted to metric similarity between users, which can limit applications. All these models are limited to single-layer graphs.
Community Search and Detection in ML Networks. Several methods have been proposed for community detection in ML networks [39,40,69]. However, they focus on detecting all communities, which is time-consuming and independent of query nodes. Surprisingly, the problem of CS in ML networks is relatively less explored. Interdonato et al. [44] design a greedy search strategy by maximizing the ratio of similarity between nodes inside and outside of the local community, over all layers. Galimberti et al. [29] adopt a community search model based on the ML k-core [5]. Finally, Luo et al. [59] design a random walk strategy to search local communities in multi-domain networks.
Dense Structures in ML Graphs. Jethava et al. [45] formulate the densest common subgraph problem. Azimi et al. [5] propose a new definition of core, k-core, over ML graphs. Galimberti et al. [28] propose algorithms to find all possible k-cores, and define the densest subgraph problem in ML graphs. Zhu et al. [82] introduce the problem of diversified coherent -core search. Liu et al. [56] propose the CoreCube problem for computing ML -core decomposition on all subsets of layers. Hashemi et al. [35] propose a new dense structure, FirmCore, and develop a FirmCore-based approximation algorithm for the problem of ML densest subgraph. Huang et al. [38] define TrussCube in ML graphs, which aims to find a subgraph in which each edge has support ≥ − 2 in all selected layers, which is different from the concept of FirmTruss.

PRELIMINARIES
We let = ( , , ) denote an ML graph, where is the set of nodes, the set of layers, and ⊆ × × the set of intralayer edges. We follow the common definition of ML networks [50], and consider inter-layer edges between two instances of identical vertices in different layers. The set of neighbors of node ∈ in layer ℓ ∈ is denoted ℓ ( ) and the degree of in layer ℓ is denotes this subgraph in layer ℓ, and deg ℓ ( ) denotes the degree of in this subgraph. Abusing notation, we write ℓ [ ] and ℓ [ ] as ℓ and ℓ , respectively. We use the following notions in this paper. Edge Schema. Connections (i.e., relationships) between objects in ML networks can have multiple types; by the edge schema of a connection, we mean the connection ignoring its type.
Given an edge schema = ( , ), we abuse the notation and use ℓ to refer to the relationship between and in layer ℓ, i.e., ℓ = ( , , ℓ), whenever ( , , ℓ) ∈ . Distance in ML Networks. For consistency, we use the common definition of ML distance [3] in the literature. However, our algorithms are valid for any definition of distance that is a metric.
Note that inter-layer edges between identical nodes are used as a penalty for changing edge types in a path. We define the distance of two nodes and , ( , ), as the length of the shortest path between them. The diameter of a subgraph [ ], ( [ ]), is the maximum distance between any pair of nodes in [ ]. 1 Example 2. In Figure 1(a), the diameter of ML graph is 7, corresponding to the path (path schema) in Figure 1 Density in ML Networks. In this study, we use a common definition of density in multilayer graphs proposed in [29].
Definition 3 (Density). [29] Given an ML graph = ( , , ), a non-negative real number , the density function is a real-valued function : 2 → R + , defined as: Free-Rider Effect. Prior work has identified an undesirable phenomenon known as the "free-rider effect" [75]. Intuitively, if a community definition admits irrelevant subgraphs in the discovered community, we refer to the irrelevant subgraphs as free riders. Typically, a community definition is based on a goodness metric ( ) for a subgraph : subgraphs with the highest (lowest) (.) value are identified as communities.
Definition 4 (Free-Rider Effect). Given an ML graph = ( , , ), a non-empty set of query vertices , let be a solution to a community definition that maximizes (resp. minimizes) goodness metric (.), and * be a (global or local) optimum solution when our query set is empty. If ( * ∪ ) ≥ ( ) (resp. ( * ∪ ) ≤ ( )), we say that the community definition suffers from free rider effect.
For each edge schema = ( , ) ∈ E, we consider an | |dimensional support vector, denoted S , in which -th element, S , denotes the support of the corresponding edge of in -th layer. We define the Top-support of as the -th largest value in 's support vector. Next, we show that not only is the maximal ( , )-FirmTruss unique, it also has the nested property. In ML networks, the degree of a node is an | |-dimensional vector whose -th element is the degree of node in -th layer. Let Top-degree of be the -th largest value in the degree vector of . By Property 3, each node in a ( , )-FirmTruss has a Top-degree of at least − 1. That means, each ( , )-FirmTruss is a ( − 1, )-FirmCore [35]. Like trusses, a FirmTruss may be disconnected, and we refer to its connected components as connected FirmTrusses.
Trusses are known to be dense, cohesive, and stable structures. These important characteristics of trusses make them popular for modeling communities [43]. Next, we discuss the density, closeness, and edge connectivity of FirmTrusses. Detailed proofs of the results and tightness examples can be found in Appendix A.2.
Theorem 1 (Density Lower Bound). Given an ML graph = ( , , ), the density of a ( , )-FirmTruss, [ ] ⊆ , satisfies: Theorem 2 (Diameter Upper Bound). Given an ML graph = ( , , ), the diameter of a connected ( , )-FirmTruss, [ ] ⊆ , Proof Sketch. We show that if P is the diameter of the ( , )-FT, and +1 | | > ≥ −1 | |, then its path schema, , has a length at least +1 × |P |. Then we consider every consecutive edges in the diameter as a block and construct a path, with the same path schema as P such that edges in each block are in the same layer. Next, we use edge schema supports to bound its length in each block. □

FIRMTRUSS-BASED COMMUNITY SEARCH 5.1 Problem Definition
In this section, we propose a community model based on FirmTruss in ML networks. Generally, a community in a network is identified as a set of nodes that are densely connected. Thus, we use the notion of FirmTruss for modeling a densely connected community in ML graphs, which inherits several desirable structural properties, such as high density (Theorem 1), bounded diameter (Theorem 2), edge connectivity (Theorem 3), and hierarchical structure (Property 2). Problem 1 (FirmTruss Community Search). Given an ML network = ( , , ), two integers ≥ 2 and ≥ 1, and a set of query vertices ⊆ , the FirmTruss community search (FTCS) is to find a connected subgraph [ ] ⊆ satisfying: (1) ⊆ , Here, Condition (1) requires that the community contains the query vertex set , Condition (2) makes sure that the community is densely connected through a sufficient number of layers, and Condition (3) requires that each vertex in the community be as close to other vertices as possible, which excludes irrelevant vertices from the community. Together, all three conditions ensure that the returned community is a cohesive subgraph with good quality. Example 5. In the graph shown in Figure 1, let 1 be the query node, = 4, and = 2. The union of purple and blue nodes is a (4, 2)-FirmTruss, with diameter 2. The FTCS community removes purple nodes to reduce the diameter. Let 6 be the query node, = 4, and = 1, the entire graph is a (4, 1)-FirmTruss, with diameter 7. The FTCS community removes blue and green nodes to reduce the diameter.
Why FirmTruss Structure? Triangles are fundamental building blocks of networks, which show a strong and stable relationship among nodes [74]. In ML graphs, every two nodes can have different types of relations, and a connection can be counted as strong and stable if it is a part of a triangle in each type of interaction. However, forcing all edges to be a part of a triangle in every interaction type is too strong a constraint. Indeed, TrussCube [38], which is a subgraph in which each edge has support − 2 in all selected layers, is based on this strong constraint. In Figure 1, the green nodes are densely connected. However, while this subgraph is a (4, 1)-FirmTruss, due to the hard constraint of TrussCube, green nodes are a 2-TrussCube, meaning that this model misses it. That is, even if the green subgraph were to be far less dense and have no triangles in it, it would still be regarded as 2-TrussCube. Furthermore, in some large networks, there is no non-trivial TrussCube when the number of selected layers is more than 3 [38]. In addition to these limitations, the exponential-time complexity of its algorithms makes it impractical for large ML graphs. By contrast, FirmTrusses have a polynomial-time algorithm, with guaranteed high density, bounded diameter, and edge connectivity. While FirmCore [35] also has a polynomial-time algorithm, a connected FirmCore can be disconnected by just removing one edge, and it might have an arbitrarily large diameter, which are both undesirable for communities.

Problem Analysis
Next we analyze the hardness of the FTCS problem and show not only that it is NP-hard, but it cannot be approximated within a factor better than 2. Thereto, we define the decision version of the FTCS, -FTCS, to test whether contains a connected FirmTruss community with diameter ≤ , that contains . Given ≥ 1 and the optimal solution to FTCS, [ * ], an algorithm achieves anapproximation to FTCS if it outputs a connected ( , )-FirmTruss, , such that ⊆ and Theorem 4 (FTCS Hardness and Non-Approximability). Not only the -FTCS problem is NP-hard, but also for any > 0, the FTCS-problem cannot be approximated in polynomial-time within a factor (2 − ) of the optimal solution, unless = .
In § 6, we provide a 2-approximation algorithm for FTCS, thus essentially matching this lower bound.
Avoiding Free-rider Effect. We can show:

Comparison of CS Models in ML Networks
We compare FirmTruss with existing CS models for ML networks.
Cohesiveness. In the literature, communities are defined as cohesive, densely connected subgraphs. Hence, cohesiveness, i.e., high density, is an important metric to measure the quality of communities. It is shown that FirmCore can find subgraphs with higher density than the ML k-core [35]. Since each ( , )-FirmTruss is a ( − 1, )-FirmCore (Property 3), FirmTruss is more cohesive than ML k-core. ML-LCD model [44] maximizes the similarity of nodes within the subgrpah. RWM [59] is a random walk-based approach and minimizes the conductance. Both of these models do not control the density of the subgraph. Thus, one node may have degree 1 within the subgraph, allowing non-cohesive structures.

Connectivity.
A minimal requirement for a community is to be a connected subgraph. Surprisingly, ML k-core, ML-LCD, and RWM (with multiple query nodes) community search models do not guarantee connectivity! Natural attempts to enforce connectivity in these community models lead to additional complications and might change the hardness of the problem. Even after enforcing connectivity, these models can be disconnected by just removing one intralayer edge, which is undesirable for community models [37]. Our FirmTruss community model forces the subgraph to be connected, and guarantees that after removing up to × ( − 1) intra-layer edges, the ( , )-FirmTruss is still connected (Theorem 3).
Edge Redundancy. In ML networks, the rich information about node connections leads to repetitions, meaning edges between the same pair of nodes repeatedly appear in multiple layers. Nodes with repeated connections are more likely to belong to the same community [78]. Also, without such redundancy of connections, the tight connection between objects in ML networks may not be represented effectively and accurately. While none of the models ML k-core, ML-LCD, and RWM guarantees edge redundancy, in a ( , )-FirmTruss, each edge is required to appear in at least layers.
Hierarchical Structure. The hierarchical structure is a desirable property for community search models as it represents a community at different levels of granularity, and can also avoid the Resolution Limit problem as is discussed in [26]. While FirmTruss has a hierarchical structure, none of the existing models has this property.

FTC ONLINE SEARCH
Given the hardness of the FTCS problem, we propose two online 2-approximation algorithms in top-down and bottom-up manner.

Global Search
We start by defining query distance in multilayer networks. [ ] ( , ), is defined as the maximum length of the shortest path from ∈ to a query vertex ∈ , i.e., [ ] For a graph , we use ( , ) to denote the query distance for a vertex ∈ . Previous works (e.g., see [19,43]) use a simple greedy algorithm which iteratively removes the nodes with maximum distance to query nodes, in order to minimize the query distance. This approach can be inefficient, as it reduces the query distance by just 1 in each iteration, in the worst case. We instead employ a binary search on the query distance of a subgraph.

Algorithm 1: FTCS Global Search
Input : An ML graph = ( , , ), a set of query vertices ⊆ , and two integers ≥ 2 and ≥ 1 Output : A connected ( , )-FT containing with a small diameter 1 0 ← Find a maximal connected ( , )-FirmTruss containing ; // See Algorithm 2 (or Algorithm 5) Delete nodes in and their incident edges from ′ in all layers; 7 Maintain ′ as ( , )-FirmTruss by removing vertices/edges; Let the remaining graph ′ as G; 13 return G; Algorithm 1 gives the details of the FTCS Global algorithm. It first finds a maximal connected ( , )-FirmTruss 0 containing . We keep our best found subgraph in G, through the algorithm. Then in each iteration, we make a copy of G, ′ , and for each vertex ∈ [ ′ ], we compute the query distance of . Then, we conduct a binary search on the value of and delete vertices with query distance ≥ and all their incident edges, in all layers. From the resulting graph we remove edges/vertices to maintain ′ as a ( , )-FirmTruss (lines 6 and 7). We maintain the ( , )-FirmTruss by deleting the edge schemas whose Top-support is < − 2. Finally, the algorithm returns a subgraph G, with the smallest query distance. The procedure for finding the maximal FirmTruss containing is given in Algorithm 2. Notice, a ( , )-FirmTruss (see Def. 6) is a maximal subgraph [ ] in which each edge schema ∈ E [ ] has Top-support ≥ − 2. The algorithm first uses Property 3, and removes all vertices with Top-degree < − 1. It then iteratively deletes all instances of disqualified edge schemas in all layers from the original graph , and then updates the Top-support of their adjacent edges. To do this efficiently, we use the following fact: Fact 1. If two edge schemas and ′ are adjacent in layer ℓ, removing edge schema cannot affect Top− (S ′ ), unless Top− (S ′ ) = S ℓ ′ . Thus, in lines 12-20, we update the Top-support of those edge schemas whose Top-support may be affected by removing . Finally, we use BFS traversal from a query node ∈ to find the connected component including query vertices. We omit the details of FirmTruss maintenance since it can use operations similar to those in lines 8-21 of Algorithm 2. Example 6. In Figure 1, let = 4, = 2, and = { 2 }. Algorihtm 2 first calculates the support of each edge schema. Next, it removes the edge schema = ( 12 , 13 ) in all layers, as its Top-2 support is 0. Next, it updates the support of edge schema adjacent to , and iteratively removes all edges between green, red, and purple nodes since their edge schema has Top-2 support less than 2. Finally, the remaining graph, the union of blue of purple nodes, is returned by the algorithm.
Pick and remove = ( , ) from ; Remove all instance of from ′ in all layers; 22 ← The connected component of ′ containing ; , removes all nodes with query distance ≥ 4, and maintains the remaining graph as (4, 1)-FirmTruss. The remaining graph includes blue, purple, and red nodes. Next, it sets = ⌊ 3+1 2 ⌋ = 2, removes all vertices with query distance ≥ 2, and maintains the remaining graph as a (4, 1)-FirmTruss, which includes blue nodes. Algorithm 1 terminates and returns this subgraph as the solution.
Next, we analyze the approximation quality and complexity of the FTCS Global algorithm.

Local Search
The top-down approach of the Global algorithm may incur unnecessary computations over massive networks. The FTCS Local algorithm (Algorithm 3), presented next, addresses this limitation using a bottom-up approach.
We can first to collect all vertices whose query distances are ≤ into ′ (line 3) and then construct ′ as the induced subgraph of by ′ (line 4). Next, given , examine whether ′ contains a ( , )-FirmTruss whose query distance is . If such a FirmTruss

Algorithm 3: FTCS Local Search
Input : An ML graph = ( , , ), a set of query vertices ⊆ , and two integers ≥ 2 and ≥ 1 Output : A connected ( , )-FT containing with a small diameter exists, return it as the solution, and otherwise, increment by 1 and iterate. One drawback of this approach is that it increases the query distance only by 1 in each iteration, which is inefficient. We instead conduct a binary search on the value of . One challenge is the lack of upper bound on . A trivial upper bound, which is the query distance in the entire graph, might lead to considering almost the entire graph in the first iteration. We instead use a doubling search whereby we double the query distance in every iteration until a solution is found. Then by considering the resulting query distance as an upper bound on , we conduct a binary search. Algorithm 3 shows the details.
Theorem 8 (FTCS-Local Quality Approximation). Algorithm 3 achieves 2-approximation to an optimal solution [ * ] of the FTCS problem, that is, the obtained ( , )-FirmTruss, [ ] satisfies Proof Sketch. We first prove that the binary search method finds a solution with a smaller query distance than the optimal diameter solution. Next, by the triangle inequality, we show that the diameter of the found solution is at most twice the optimal. The detailed proof can be found in Appendix A.2. □

INDEX-BASED ALGORITHM
Both online algorithms need to find FirmTruss from scratch. However, for each query set, computing the maximal FirmTruss from scratch can be inefficient for large multilayer networks. In this section, we discuss how to employ FirmTruss decomposition to accelerate our algorithms, by storing maximal FirmTrusses as they are

Algorithm 4: FirmTruss Decomposition
Input : An ML graph = ( , , ) Output : Skyline FirmTruss index of each edge schema Remove all instance of from in all layers; 23 Remove all dominated indices in SFT( ) for each ∈ E; identified into an index structure. We first present our FirmTruss decomposition algorithm and then describe how the index can be used for efficient retrieval of the maximal FirmTruss given a query.

FirmTruss Decomposition
In this section, we define the Skyline FirmTrussness index. For an edge schema ∈ E, we let ( ) denote the set {( , ) | is in a ( , )-FirmTruss}. We will use the following notion of index dominance.
In order to find all possible FirmTrusses, we only need to compute the skyline FirmTrussness for every edge schema in a multilayer graph . To this end, we present the details of FirmTruss algorithm in Algorithm 4. For a given edge schema , if Top− (S ) = − 2, then it cannot be a part of a ( ′ , )-FirmTruss, for ′ > . Therefore, given , we can consider Top− (S ) + 2 as an upper bound on the FirmTruss index of (line 5). In the FirmTruss decomposition, we recursively pick an edge schema with the lowest Top− (S ), assign its FirmTruss index as Top− (S ) + 2, and then remove it from the graph. After that, to efficiently update the Top-support of its adjacent edges, we use Fact 1 (lines [13][14][15][16]. At the end of the algorithm, we remove all dominated indices in SFT( ) for each ∈ E to only store skyline indices (line 23). We can show:

Index-based Maximal FirmTruss Search
Using Algorithm 4, we can find offline all skyline FirmTruss indices for a given edge schema and query vertex set. Next, we start from the query vertices and by using a breadth-first search, check for each neighbor whether its corresponding edge schema has a skyline FirmTruss index that dominates the input ( , ). Algorithm 5 shows the procedure. We have: This indexing approach can be used in Algorithm 1 to find the maximal 0 , as well as in Algorithm 3 so that we only need to add edges whose corresponding edge schema has an index that dominates ( , ). We refer to these variants of Global and Local as iGlobal and iLocal, respectively.

ATTRIBUTED FIRMTRUSS COMMUNITY
Often networks come naturally endowed with attributes associated with their nodes. For example, in DBLP, authors may have areas of interest as attributes. In protein-protein interaction networks, the attributes may correspond to biological processes, molecular functions, or cellular components of a protein made available through the Gene Ontology (GO) project [4]. It is natural to impose some level of similarity between a community's members, based on their attributes.
Network homophily is a phenomenon which states similar nodes are more likely to attach to each other than dissimilar ones. Inspired by this "birds of a feather flock together" phenomenon, in social networks, we argue that users remain engaged with their community if they feel enough similarity with others, while users who feel dissimilar from a community may decide to leave the community. Hence, for each node, we measure how similar it is to the community's members and use it to define the homophily in the community.
We show that surprisingly, use of homophily in a definition of attributed community offers an alternative means to avoid the free-rider effect. In this section, we extend the definition of the FirmTruss-based community to attributed ML networks, where we assume each vertex has an attribute vector. In order to capture vertex similarity, we propose a new function to measure the homophily in a subgraph. We show that this function not only guarantees a high correlation between attributes of vertices in a community but also avoids the free-rider effect. Unlike previous work [20,42,79], our model allows for continuous valued attributes. E.g., in a PPI network, the biological process associated with a protein may have a real value, as opposed to just a boolean or a categorical value.
Let A = { 1 , ..., } be a set of attributes. An attributed multilayer network = ( , , , Ψ), where ( , , ) is a multilayer network and Ψ : → R ≥0 is a non-negative function that assigns a -dimensional vector to each vertex, with Ψ( ) [ ] representing the strength of attribute in vertex . Let ℎ( , ) be a symmetric and non-negative similarity measure based on attribute vectors of and . E.g., ℎ( , ) can be the cosine similarity between Ψ( ) and Ψ( ). Let be a community containing . We define ℎ ( ), capturing the aggregate similarity between and members of : The higher the value ℎ ( ) the more similar user "feels" they are with the community . While cosine similarity of attribute vectors is a natural way to compute the similarity ℎ( , ), any symmetric and non-negative measure can be used in its place.
Based on ℎ ( ), we define the homophily score of community as follows. Let ∈ R∪ {+∞, −∞} be any number. Then the homophily score of is defined as: The parameter gives flexibility for controlling the emphasis on similarity at different ends of the spectrum. When → +∞ (resp. → −∞) , we have higher emphasis on large (resp. small) similarities. This flexibility allows us to tailor the homophily score to the application at hand.
Hardness Analysis. Next we analyze the complexity of the AFTCS problem and show that when is finite, it is NP-hard.
Proof Sketch. Finding the densest subgraph with ≥ vertices in single-layer graphs [48] is a hard problem. Given an instance of this problem, = ( , ), we construct a complete, attributed ML graph and provide an approach to construct an attribute vector of each node such that ∀ vertices , , ℎ( , ) = 1 2| | if ( , ) ∈ , and ℎ( , ) = 0, if ( , ) ∉ . So the densest subgraph with ≥ vertices in is a solution for AFTCS, and vice versa. □ Free-rider Effect. Analogously to Theorem 5, we can show: Theorem 13 (AFTCS Free-Rider Effect). For any attributed ML network = ( , , , Ψ) and query vertices ⊆ , there is a solution [ ] to the AFTCS problem such that for all query-independent optimal solutions [ * ], either * = , or [ ∪ * ] is disconnected, or [ ∪ * ] has a strictly smaller homophily score than [ ].

Algorithms
In this section, we propose an efficient approximation algorithm for the AFTCS problem. We show that when = +∞, or −∞, this algorithm finds the exact solution. We can show that our objective function Γ (.) is neither submodular nor supermodular (proof in Appendix C), suggesting this problem may be hard to approximate, for some values of .
Consider a set of vertices ⊆ . Our approximation algorithm is to greedily remove nodes ∈ that may improve the objective. Since removing any node ∈ will change the denominator of Γ ( ) in the same way, we can choose the node that leads to the minimum (maximum) drop in the numerator. Let us examine the change to the Γ ( ) from dropping ∈ : Notice that Δ ( ) represents the exact decrease in the numerator of Γ ( ) resulting from removing . Based on this observation, in Algorithm 6, we recursively remove a vertex with a minimum (maximum) Δ value, and maintain the remaining subgraph as a ( , )-FirmTruss. We have the following result: where is the number of iterations, 0 and 0 are the vertex set and edge set of maximal ( , )-FirmTruss.
As for the approximation quality, we can show the following when ≥ 1. The detailed proof and tightness example can be found in Appendix A.2 and B.
Theorem 15 (AFTCS-Approx Quality). Let ≥ 1, Algorithm 6 returns a ( + 1) 1/ -approximation solution of AFTCS problem. Proof Sketch. Let * be the optimal solution. Since removing a node * ∈ * will produce a subgraph with homophily score at most Γ ( * ), we have Γ ( * ) ≤ Δ * ( * ). Next, we show that the first removed node * ∈ * by the algorithm cannot be removed by maintaining FirmTruss, so it was a node with a minimum Δ. Then, we use the fact that the minimum value of Δ is less than the average of Δ over all nodes and provide an upper bound of ( + 1)Γ ( ) for the average of Δ over . Finally, we show that function | |Γ ( ) is supermodular for ≥ 1, and based on its increasing differences property, we conclude the approximation guarantee. □ Remark 1. How much good can Algorithm 6 work? As increases, Algorithm 6 has a better approximation factor. In the worst case, ( = 1), we get approximation factor = 2, and when → ∞, our approximation factor has a limit of 1. This limit of the approximation factor intuitively matches the fact that when = +∞ the optimal solution is trivial to obtain by the maximal FirmTruss.
Exact Algorithm when = +∞, or −∞. The case = +∞ is straightforward, where we just want to maximize Γ +∞ ( ) = max ∈ ℎ ( ). The solution of this case is the maximal subgraph that satisfies the conditions (1) and (2) in Problem 2. In the = −∞ case, we want to maximize Γ −∞ ( ) = min ∈ ℎ ( ). We can recursively remove a vertex with minimum value of ℎ and maintain the remaining subgraph such that satisfies conditions (1) and (2) in Problem 2. The pseudocode is identical to Algorithm 6, except in lines 5-8, we recursively remove a vertex with a minimum value of ℎ . We refer to this modified peeling algorithm as Exact-MaxMin.

EXPERIMENTS
We conduct experiments to evaluate the proposed CS models and algorithms. Additional experiments on efficiency and parameter sensitivity can be found in Appendix F.   Baseline Methods. We compare our FTCS with the state-of-theart CS methods in ML networks. ML k-core [29] uses an objective function to automatically choose a subset of layers and finds a subgraph such that the minimum of per-layer minimum degrees, across selected layers, is maximized. ML-LCD [44] maximizes the ratio of Jaccard similarity between nodes inside and outside of the local community. RWM [59] sends random walkers in each layer to obtain the local proximity w.r.t. the query nodes and returns a subgraph with the smallest conductance. We implemented a baseline based on TrussCube [38], which finds a maximal connected TrussCube containing query nodes. We compare our approach with CTC [43], which finds the closest truss community in single-layer graphs, and VAC [57], an attributed variant of CTC, also on single-layer graphs.
Datasets. We perform extensive experiments on thirteen real networks [1, 11, 16-18, 28, 31, 49, 51, 53, 60, 63] covering social, genetic, co-authorship, financial, brain, and co-purchasing networks, whose main characteristics are summarized in Table 1. While Terrorist and DBLP datasets naturally have attributes, for RM and YouTube, we chose one of the layers, embedded it using node2vec [33], and used the vector representation of each node as its attribute vector.
Queries and Evaluation Metrics. We evaluate the performance of all algorithms using different queries by varying the number of query nodes, and the parameters , , and . To evaluate the quality of found communities , we measure their F1-score to grade their alignment with the ground truth˜. Here, 1( ,˜) = To evaluate the efficiency, we report the running time. In reporting results, we cap the running time at 5 hours and memory footprint at 100 GB. For index-based methods, we cap the construction time at 24 hours. Unless stated otherwise, we run our algorithms over 100 random query sets with a random size between 1 and 10, and report the average results. We randomly set and to one of the common skyline indices of edge schemas incident to query nodes.  Quality. We evaluate the effectiveness of different community search models over multilayer networks. Figure 2 reports the average F1-scores of all methods on datasets with the ground-truth community. We observe that our approach achieves the highest F1-score on all networks against baselines. The reason is two-fold. First, in our problem definition, we enforce the minimum-diameter restriction, effectively removing the irrelevant vertices from the result. Second, FirmTruss requires each edge schema to have enough support in a sufficient number of layers, ensuring that the found subgraphs are cohesive and densely connected. While CTC also minimizes the diameter, it is a single-layer approach and misses some structure due to ignoring the type of connections.
We also evaluate all algorithms in terms of other goodness metrics -density ( = 1), and diameter. Table 2 reports the results on FAO, Obama, YEAST, and Higgs datasets. The results on other datasets are similar, and are omitted for lack of space. We observe that our approach achieves the highest density, and lowest diameter on all networks against baselines.
Since there are no prior models for attributed community search in ML networks, we compare the quality of AFTCS with our ML unattributed baselines as well as VAC. Table 3 reports the F1-score and density of communities found, over four datasets with groundtruth communities. AFTCS consistently beats the baselines. Notice that AFTCS has a higher F1-score than FTCS in all but one case, as the existence of both attributes and structure is richer information than only structure. Accordingly, AFTCS is better able to distinguish members from non-members of a ground-truth community.
Efficiency. We evaluate the efficiency of different community search models on multilayer graphs. Figure 3 shows the query processing time of all methods. All of our methods terminate within 1 hour,  except Global on the two largest datasets, as it generates a large candidate graph 0 . Our algorithms Local and iLocal run much faster than Online-Global. Overall, iLocal achieves the best efficiency, and it can deal with a search query within a second on most datasets. Local is the only algorithm that scales to graphs containing billions of edges. Bars for iGlobal and iLocal are missing for Google+, as index construction time exceeds our threshold.
Parameter Sensitivity. We evaluate the sensitivity of algorithm efficiency to the parameters , , and , varying one parameter at a time. Figures 4(a) and (b) show the running time as a function of and on DBLP. The larger and for Global and iGlobal result in lower running time since the algorithms generate a smaller 0 . However, the larger and increase the running time of Local and iLocal since they need to count more nodes in the neighborhood of query nodes to find a ( , )-FirmTruss. This also is the reason for the sharp increase of time in both plots. With large and , Local and iLocal need to count nodes farther away, and there is a significant increase in the number of nodes that they need to explore. Figure 4(c) shows the running time as a function of . We observe that AFTCS-Approx achieves a stable efficiency on different finite values of . Notice, when = −∞, this algorithm takes less time as it does not need to calculate Δ ( ) for each node and can simply remove the vertex with minimum ℎ ( ) in each iteration.
Scalability. We test our algorithms using different versions of StackOverflow obtained by selecting a variable #layers from 1 to 24 and also with different subsets of edges. Figure 5 shows the results of the index-based Global, Local Search, and AFTCS-Approx algorithms. The results Global and iLocal are similar, and are omitted for lack of space (see Appendix F). The running time of all approaches scales linearly in #layers. By varying #edges, all algorithms scale gracefully. As expected, the Local algorithm is less sensitive to varying #edges than #layers.
Index Construction. Figure 6 reports the SFT index construction time and size. The size of indices is more dependent on the structure of a graph than its size. That is, since we store the SFT indices for each edge schema, the size of indices depends on the number of FirmTrusses in the network. For all datasets, the SFT index can be Case Studies: Identify Functional Systems in Brain Networks.
Detecting and monitoring functional systems in the human brain is a primary task in neuroscience. However, the brain network generated from an individual can be noisy and incomplete. Using brain networks from many individuals can help to identify functional systems more accurately. A community in a multilayer brain network, where each layer is the brain network of an individual, can be interpreted as a functional system in the brain. In this case study, to show the effectiveness of the FTCS, we compare its detected functional system with ground truth. Here, we focus on the "visual processing" task in the brain. As the "Occipital Pole" is primarily responsible for visual processing [47], we use one of its representing nodes as the query node. Figure 7 reports the found communities by FTCS and baselines. The identified communities are highlighted in red, and the query node is green. Results show the effectiveness of FTCS as the community detected by our method is very similar to the ground truth with F1-score of 0.75. RWM, which is a random walk-based community model, includes many false-positive nodes that cause F1-score of 0.495. On the other hand, some nodes in the boundary region are missed by ML-LCD that caused low F1-score of 0.4. The result of the ML k-core is omitted as it does not terminate even before one week.  Case Studies: Classification on Brain Networks. Behavioral disturbances in attention deficit hyperactivity disorder (ADHD) are considered to be caused by the dysfunction of spatially distributed, interconnected neural systems [32]. In this section, we employ our FTCS to detect common structures in the brain functional connectivity network of ADHD individuals and typically developed (TD) people. Our dataset is derived from the functional magnetic resonance imaging (fMRI) of 520 individuals with the same methodology used in [52]. It contains 190 individuals in the condition group, labeled ADHD, and 330 individuals in the control group, labeled TD. Here, each layer is the brain network of an individual person, where nodes are brain regions, and each edge measures the statistical association between the functionality of its endpoints. Since "Temporal Pole" is known as the part of the brain that plays an important role in ADHD symptoms [64,68], we use a subset of its representing nodes as the query nodes. Next, we randomly chose 230 individuals labeled TD and 90 individuals labeled ADHD to construct two multilayer brain networks and then found the FirmTruss communities associated with "Temporal Pole" in each group separately, referred to as TD and ADHD in Figure 8. In the second step, for each individual unseen brain network, we find the associated communities to the query nodes using the FTCS model, setting | | = 1. In order to classify an unseen brain network, we calculate the similarity of its found communities with TD and ADHD and then predict its label as the label of the community with maximum similarity. Here, we use the overlap coefficient [71] as the similarity measure between two communities.
To ensure that the result is statistically significant, we repeat this process for 1000 trials and report the mean, and its relative standard deviation of accuracy, precision, recall and F1-score in Table 4. Not only does our FTCS outperform baseline community search models, but it also achieves results comparable with the state-of-the-art ADHD classification model [32], based on SVM, which reports an accuracy of 76%. This comparable result is achieved by the FTCS method, which is a white-box and explainable model.
Case Studies: DBLP. We conduct a case study on the DBLP dataset to judge the quality of the AFTCS model and to show the effectiveness of the homophily score in removing free riders. The multilayer DBLP dataset is a collaboration network derived following the methodology in [10]. In this dataset, each node is a researcher, an edge shows collaboration, and each layer is a topic of research. For each author, we consider the bag of words drawn from the titles of all their papers and apply LDA topic modeling [9] to automatically identify 240 topics. The attribute of each author is the vector that describes the distribution of their papers in these 240 topics. We use "Brian D. Athey" as the query node. The maximal (8, 2)-FirmTruss, including the query node, has 44 nodes with a minimum homophily score of 0.08, shown in Figure 9(a). The community found by AFTCS ( = −∞) is an (8, 2)-FirmTruss with a minimum homophily score of 0.28, which resulted from removing 28 nodes as free-riders. The found community is shown in the larger circle, while the smaller circle shows free riders. We compute the average attributes of community members and free-riders and then cluster their non-zero elements into ten known research topics. Results are shown in Figure 9(b). While researchers in the found community have focused more on "Health Informatics," removed researchers (free-riders) have focused more on "Databases." The connection between these two communities, which results in their union being an (8, 2)-FirmTruss, is the collaboration of "Brian D. Athey," from the "Health Informatics" community with some researchers in "Databases" community. AFTCS divides the maximal FirmTruss into two communities with more correlations inside each of them.

CONCLUSIONS
We propose and study a novel extended notion of truss decomposition in ML networks, FirmTruss, and establish its nice properties. We then study a new problem of FirmTruss-based community search over ML graphs. We show that the problem is NP-hard. To tackle it efficiently, we propose two 2-approximation algorithms and prove that our approximations are tight. To further improve their efficiency, we propose an index and develop fast index-based variants of our approximation algorithms. We extend the FirmTrussbased community model to attributed ML networks and propose a homophily-based model making use of generalized -mean. We prove that this problem is also NP-hard for finite value of and to solve it efficiently, we develop a fast greedy algorithm which has a quality guarantee for ≥ 1. Our extensive experimental results on large real-world networks with ground-truth communities confirm the effectiveness and efficiency of our proposed models and algorithms, while our case studies on brain networks and DBLP illustrate their practical utility.

A PROOFS A.1 Properties
Property 1 (Uniqueness). Proof. (a) The property follows from the definition of FirmTruss and this fact that in a subgraph, every edge schema ∈ E that has at least −1 supports, also has at least −2 supports. (b) Similarly, if edge schema in at least + 1 layers has no less than − 2 supports, in at least layers it has at least − 2 supports as well. □

Property 3 (Minimum Degree).
Proof. Given an edge schema ( , ) ∈ E, where , ∈ , since ( , ) in at least layers has at least − 2 supports, and has at least − 2 common neighbours in at least layers. Therefore, each has degree at least − 1 in at least layers. □
Proof. First, we provide a lower bound for the mean of average degree over all layers: We can rewrite the numerator as half of the sum of degrees of each node in each layer. In fact, Since is a FirmTruss, each edge schema = ( , ) in at least layers has at least − 2 supports. Accordingly, and each in at least layers have at least − 1 neighbours. Therefore, Based on Equations (1) and (2), we can conclude that the mean of average degree over all layers is at least 2| | . Since it is the average over all layers, there exist a layer ℓ 1 ∈ such that: Now, ignoring this layer, and exploiting the definition of , each edge schema = ( , ) in at least − 1 layers has at least − 2 supports. Accordingly, and each in at least − 1 layers have at least − 1 neighbours. Therefore, the mean of average degree over remaining layers, \ {ℓ 1 }, is at least . Again, we can conclude that there is a layer ℓ 2 ≠ ℓ 1 such that . So there is a subset of ,ˆ= {ℓ 1 , ℓ 2 }, with two layers such that each layer has density at least . By iterating this process, we can conclude that ∃˜⊆ , such that each layer ℓ ∈˜has density at least Based on the definition of the density in ML graphs, we can conclude that: The right hand side of the above inequality is a function of |˜|, and since the above inequality is valid for each arbitrary integer 1 ≤ |˜| ≤ , ( ) is not less than the maximum of this function exhibited by these values. □
Next we show that the length of is bounded by ⌊ 2| |−2 ⌋.
Given the part of , : +1 → +2 → · · · → + , that all edges are in layer ℓ * , for any 0 ≤ ≤ ⌊ | |+1 ⌋. We know that each edge ( + , + +1 , ℓ * ) has at least − 2 supports. Thus, each pair ( + , + +1 ) has at least − 2 common neighbours in layer ℓ * . We divide the set of common neighbours into two sets and : each holds those vertices not in that are adjacent to both + and + +1 , and to no other vertices in P ′ ; each holds those vertices that are adjacent to all three of + −1 , + and Overall, we have: The last (right) inequality comes from the fact that the start and end of paths P and P ′ are the same. Accordingly, if the length of P ′ is less than P, then P ′ is the shortest path between the start and end nodes, which contradicts the assumption that P is the diameter. □

Theorem 3 (Edge Connectivity).
Proof. Let be a minimal set of intra-layer edges whose removal will divide the [ ] into separate components, and = ( , , ℓ) ∈ . When all of the edges in are removed, the vertices and will be in separate components, else the removal of was unnecessary, violating the minimality of . Since ( , ) ∈ E ( ) there are at least layersˆ= {ℓ 1 , . . . , ℓ } in which and are joined by at least − 2 independent paths of length 2. Therefore, in each layer ℓ ∈ˆ, at least − 1 edges must be removed to place and in separate components. Therefore, | | ≥ ( − 1). □

Theorem 4 (FTCS Hardness and Non-Approximability).
Proof. We directly prove non-approximibility. The proof of NPhardness follows a similar construction.
Assume there exists a polynomial time (2 − )-approximation algorithm for the FTCS problem, for any ∈ (0, 1). Let A be an algorithm that provides a solution with an approximation factor Since diameter is an integer, we deduce that ( ′ [ * ]) ≥ 2. In this case, ′ ℓ [ * ] cannot possibly contain a clique of size in any layer, for if it did, that clique would be the optimal solution to the FTCS problem with diameter 1. Therefore, since ′ ℓ [ * ] = [ * ], we can distinguish between the YES and NO instances of the Maximum Clique Decision problem in polynomial-time, which is a contradiction.
To show the NP-hardness of -FTCS problem, we reduce the Maximum Clique (decision version) to -FTCS problem. By setting = 1, the instance construction and proof is similar to the proof of non-approximability. □

B TIGHTNESS EXAMPLES
Density Lower Bound. For simplicity assume that = 0 (for other values of the example is similar), for a given and , we construct a multilayer graph = ( , , ), such that | | = and for each ℓ ∈ , ℓ is a -clique. In this case, ( ) = −1 2 and lower bound for the density of is −1 2 × = −1 2 . Which shows that the lower bound is tight.
Diameter Upper Bound. First, the diameter of a connectedtruss with vertices in a single layer graph is no more than ⌊ 2 −2 ⌋, and this is a tight upper bound. Therefore, for a given , there exists a single layer -truss, , with diameter ⌊ 2 −2 ⌋. Now, for any arbitrary and , we construct a multilayer graph = ( , , ), such that | | = and for each ℓ ∈ , ℓ = . In this case = 1 and diameter of G is ⌊ 2| |−2 ⌋.
Edge Connectivity. For a given , , we construct a multilayer graph = ( , , ), such that | | = and for each ℓ ∈ , ℓ is a -clique. To make disconnected, we have to make ℓ for all ℓ ∈ disconnected. Since the edge connectivity of a -clique is − 1, we have to remove at least × ( − 1) intra-layer edges to make disconnected.
Given a complete multilayer graph = ( , , ), we want to construct the set of tuples E ⊆ × such that AFTCS-Approx returns an approximation solution that asymptotically approaches ( + 1) 1/ of the exact solution of AFTCS problem.

C PROPERTIES OF HOMOPHILY SCORE FUNCTION
Positive Influence of Similar Vertices. The first property of homophily score is positive influence of similar nodes. As we discussed, Δ ( ) is the value that droping ∈ changes the numerator of the homophily score: Similarly, Δ ( ∪ { }) is the value that adding to channges the numerator of the homophily score. Next fact, illustrates when adding a vertex can increase the homophily score. Example 8. Let = 1, Fact 2 states that adding a node with nodehomophily score ℎ ( ) > 1 2| | ∈ ℎ ( ) to subgraph , increases the homophily score of the subgraph.
Negative Influence of Dissimilar Vertices. Adding dissimilar vertices to the community decreases the homophily score.
Non-monotone Property. Non-monotonicity is a desirable property for the community model. Assume that if the attribute correlation measure for the community model is monotone and increasing, then always the maximal FirmTruss is the optimal solution. At the same time, we know that maximal FirmTruss may include some free riders. The introduced homophily score function is non-monotone: as we discussed in Facts 2 and 3, adding a vertex might increase or decrease the homophily score.
Non-submodularity and Non-supermodularity. Optimization problems over submodular or supermodular functions lend themselves to efficient approximation. We thus study whether our homophily score function is submodular or supermodular with respect to the set of vertices. By a contradictory example, we show that our homophily score function is neither submodular nor supermodular.

D REPRODUCIBILITY
All algorithm implementations and code for our experiments are available at Github.com/joint-em/FTCS.

E DATASETS
We perform extensive experiments on thirteen real networks including social, genetic, co-authorship, financial, and co-purchasing networks, whose main characteristics are summarized in Table 1.
Using the raw Noordin terrorist network data [63], we constructed the multilayer terrorist relationship network. Each node in this network represents a terrorist, and each layer represents a type of relationship (e.g., friendships, organizations, educational institutions, businesses, and religious institutions, etc.  month. Phones are divided into two communities according to their owners' affiliations. Brain is derived from the functional magnetic resonance imaging (fMRI) of 520 individuals with the same methodology used in [52]. It contains 190 individuals in the condition group, labelled as ADHD and 330 individuals in the control group, labelled as TD. Here, each layer is the brain network of an individual, nodes are brain regions, and an edge measures the statistical association between the functionality of nodes. Each community is a functional system in the brain. YEAST is a biological network, in which the layers correspond to interaction networks of genes in Saccharomyces cerevisiae (which was obtained via a synthetic geneticarray methodology) and correlation-based networks in which genes with similar interaction profiles are connected to each other [17]. FAO represents different types of trade relationships among countries in which layers represent products, nodes are countries and edges at each layer represent import/export relationships among countries [18]. Obama network represent re-tweeting, mentioning, and replying among Twitter users, focusing on Barack Obama's visit in 2013 [60]. DBLP is a co-authorship network until 2014 that is used in [28]. Amazon is a co-purchasing network, in which each layer corresponds to one of its four snapshots between March and June 2003 [53]. Higgs is a two-layer network where the first layer represents tracking the spread of news about the discovery of the Higgs boson on Twitter, and the second layer is for the following relation [16]. Friendfeed contains commenting, liking, and following interactions among users of Friendfeed [11]. StackOverflow represents user interactions from the StackExchange site where each layer corresponds to interactions in one hour of the day [51]. Finally, Google+ is a billion-scale network consisting of 4 Google+ snapshots between July and October 2011 [31].

F ADDITIONAL EXPERIMENTS F.1 Scalability of Other Algorithms
We test our algorithms using different versions of StackOverflow obtained by selecting a variable #layers from 1 to 24 and also with different subsets of edges. Figure 10 shows the results of the Global, and iLocal algorithms. The running time of these algorithms scales linearly in #layers. By varying #edges, all algorithms scale gracefully. As expected, the iLocal algorithm is less sensitive to varying #edges than #layers.

F.2 Effect of Query Set Size
Effectiveness. We evaluate the effect of the query set size on the quality of found communities by FTCS and AFTCS. Figure 11  and (b) show the F1-score as a function of query set size, | |, on Terrorist and RM datasets. We observe that increasing the size of the query set first results in increasing F1-score, but after it achieves its maximum, the F1-score decreases. The reason is increasing | | increases F1-score as long as | | is less than the size of the groundtruth community. If | | exceeds the size of the community, the F1-score starts to decrease.
Efficiency. We evaluate the effect of the query set size on the efficiency of proposed algorithms. Figure 12(a) and (b) show the query time as a function of query set size, | |, on Terrorist and DBLP datasets. We observe that increasing the size of the query set results in increasing the running time. Increasing the query set size results in increasing the running time as our algorithms need to explore more nodes in the neighborhood of query nodes. Figure 13 shows the result of the effect of varying and on running time. As we discussed earlier, the larger and for Global algorithms results in less running time since algorithms generate a smaller 0 . However, the larger and increases the running time of Local algorithms since it needs to count more nodes in the neighbourhood of query nodes to find a ( , )-FirmTruss.

F.4 Effect of and on Found Communities
Since and are given by the user, one might ask what happens if inappropriate values of and are given? We conduct a case study on the DBLP dataset to evaluate the effect of and , and to show the effectiveness of the FTCS in removing free riders. Table 5 shows the 0 size, the size of found community by FTCS, and the # free-riders for different values of and , and for different query nodes, "Jiawei Han", "Samuel Madden", "Yoshua Bengio". These results show that giving inappropriate values of and results in increasing the size of 0 . However, since FTCS minimizes the diameter, it is able to remove far nodes from the query node and always finds a community with appropriate size and quality. Accordingly, FTCS is robust to inappropriate values of and . We know that given ∈ N + and ≥ 0, the ( + 1, )-FT and ( , + 1)-FT of a multilayer graph are subgraphs of its ( , )-FT. Another property of FTCS that is shown in Table 5 is its hierarchical structure. This is an important property for a community model as by varying the value of and it can find communities at different levels of granularity. Remark 2. How is a user supposed to choose the parameters? The reported experiments on the effect of , , and offer some guidance. Figure 4 in the paper shows the effect of , , and on the efficiency. Based on this experiment, the value of does not affect the efficiency much and the running times are comparable for different values of . Also, our iLocal algorithm shows a stable trend, whereby varying and has a negligible impact on the running time. On the other hand, in the Global and iGlobal algorithms we see a decreasing trend and in the Local algorithm, we see an increasing trend, as , are increased. Thus, when an index is available, iLocal is clearly the algorithm of choice as it has a stable performance fairly independent of the parameters. Otherwise, one can use the Global algorithm for large values of and and use Local algorithm for small values of and . Table 5 shows the effect of and on the quality of the communities found from the DBLP dataset. We measured the size of the largest connected ( , )-truss found, the number of free-riders removed, the final community size, as well as the F1 score w.r.t. the ground truth. These results show the robustness of our approach even in many cases when different values of and are chosen.
In sum, a user can start with some initial values for the parameters , , , subsequently modify them, and explore the various extracted communities and choose the one that best matches their needs. Our experiments show that either using iLocal (if index is available) or  using Global (if , are large), or Local (if , are small), each resulting community can be extracted in about a second, permitting efficient exploration. In terms of quality, our experiments show that even the worst choice of leads to a quality that is better than all the baselines.

F.5 Efficiency of FirmTruss Decomposition
We compare the efficiency of FirmTruss decomposition algorithm with the state-of-the-art dense strcture mining algorithms, Firm-Core [35], ML k-core [28], and TrussCube [38], in multilayer graphs. Figure 14 shows the running time of these algorithms on different datasets. FirmTruss outperforms all other algorithms, except FirmCore, and can be scaled to graphs with hundred thousands of edges. As we previously discussed, although FirmCore is more efficient that FirmTruss, FirmTrusses are denser than FirmCores. It is a trade-off between density and efficiency.

G COMPARISON OF DIFFERENT ML COMMUNITY SEARCH MODELS
Example 11. In Figure 1, the green nodes are densely connected and intuitively they form a community. Let 10 be the query node, we expect a good CS model to return the green nodes as the corresponding community of 10 . Let = 4 and = 1, we can see that FTCS returns the green nodes as a community. For TrussCube, 2 when the number of selected layer is 2, or 3, it returns the entire graph as the community of 10 , which includes many false positive nodes. Note that, choosing only 1 layer is equivalent to a simple truss in a single layer graph. Let = 1, then -core returns a subgraph including { 1 , 2 , 3 , 8 , 9 , 10 , 11 , 13 } as the community, which misses several nodes in the expected community (i.e., the green nodes). Let = 3, ML -core returns a subgraph including all nodes as the community, which includes many false positives. Finally, ML-LCD returns { 9 , 10 , 11 } as the corresponding community, which misses several green nodes.