Many methods have been proposed for community detection in networks, but most of them do not take into account additional information on the nodes that is often available in practice. In this paper, we propose a new joint community detection criterion that uses both the network edge information and the node features to detect community structures. One advantage our method has over existing joint detection approaches is the flexibility of learning the impact of different features which may differ across communities. Another advantage is the flexibility of choosing the amount of influence the feature information has on communities. The method is asymptotically consistent under the block model with additional assumptions on the feature distributions, and performs well on simulated and real networks. Community detection is a fundamental problem in network analysis, extensively studied in a number of domains -see (1) and (2) for some examples of applications. A number of approaches to community detection are based on probabilistic models for networks with communities, such as the stochastic block model (3), the degree-corrected stochastic block model (4), and the latent factor model (5). Other approaches work by optimizing a criterion measuring the strength of community structure in some sense, often through spectral approximations. Examples include normalized cuts (6), modularity (7; 8), and many variants of spectral clustering, e.g., (9). Many of the existing methods detect communities based only on the network adjacency matrix. However, we often have additional information on the nodes (node features), and sometimes edges as well, for example, (10), (11) and (12). In many networks the distribution of node features is correlated with community structure (13), and thus a natural question is whether we can improve community detection by using the node features. Several generative models for jointly modeling the edges and the features have been proposed, including the network random effects model (14), the embedding feature model (15), the latent variable model (16), the discriminative approach (17), the latent multi-group membership graph model (18), the social circles model for ego networks (13), the communities from edge structure and node attributes (CESNA) model (19), the Bayesian Graph Clustering (BAGC) model (20) and the topical communities and personal interest (TCPI) model (22) . Most of these models are designed for specific feature types, and their effectiveness depends heavily on the correctness of model specification. Model-free approaches include weighted combinations of the network and feature similarities (23; 24), attribute-structure mining (25), simulated annealing clustering (26), and compressive information flow (27). Most methods in this category use all the features in the same way without determining which ones influence the community structure and which do not, and lack flexibility in how to balance the network information with the information coming from its node features, which do not always agree. Including irrelevant node features can only hurt community detection by adding in noise, while selecting features that by themselves cluster strongly may not correspond to features that correlate with the community structure present in the adjacency matrix. In this paper, we propose a new joint community detection criterion that uses both the network adjacency matrix and the node features. The idea is that by properly weighing edges according to feature similarities on their end nodes, we strengthen the community structure in the network thus making it easier to detect. Rather than using all available features in the same way, we learn which features are most helpful in identifying the community structure from data. Intuitively, our method looks for an agreement between clusters suggested by two data sources, the adjacency matrix and the node features. Numerical experiments on simulated and real networks show that our method performs well compared to methods that use either  Our method is designed to look for assortative community structure, that is, the type of communities where nodes are more likely to connect to each other if they belong to the same community, and thus there are more edges within communities than between. This is a very common intuitive definition of communities which is incorporated in many community detection criteria, for example, modularity (8). Our goal is to use such a community detection criterion based on the adjacency matrix alone, and add feature-based edge weights to improve detection. Several criteria using the adjacency matrix alone are available, but having a simple criterion linear in the adjacency matrix makes optimization much more feasible in our particular situation, and we propose a new criterion which turns out to work particularly well for our purposes. Let A denote the adjacency matrix with A ij = 0 if there is no edge between nodes i and j, and otherwise A ij > 0 which can be either 1 for unweighted networks or the edge weight for weighted networks. The community detection criterion we start from is a very simple analogue of modularity, to be maximized over all possible label assignments e: ( 1.1) Here e is the vector of node labels, with e i = k if node i belongs to community k, for k = 1, . . . , K, E k = {i : e i = k}, and |E k | is the number of nodes in community k. We assume each node belongs to exactly one community, and the number of communities K is fixed and known. Rescaling by |E k | α is designed to rule out trivial solutions that put all nodes in the same community, and α > 0 is a tuning parameter. When α = 2, the criterion is approximately the sum of edge densities within communities, and when α = 1, the criterion is the sum of average "within community" degrees, which both intuitively represent community structure. This criterion can be shown to be consistent under the stochastic block model by checking the conditions of the general theorem in (28). The ideal use of features with this criterion would be to use them to up-weigh edges within communities and down-weigh edges between them, thus enhancing the community structure in the observed network and making it easier to detect. However, node features may not be perfectly correlated with community structure, different communities may be driven by different features, as pointed out by (13), and features themselves may be noisy. Thus we need to learn the impact of different features on communities as well as balance the roles of the network itself and its features. Let f i denote the p-dimensional feature vector of node i. We propose a joint community detection criterion (JCDC), where α is a tuning parameter as in (1.1), β k ∈ R p is the coefficient vector that defines the impact of different features on the kth community, and β := {β 1 , . . . , β K }. The criterion is then maximized over both e and β. Having a different β k for each k allows us to learn the roles different features may play in different communities. The balance between the information from A and F := {f 1 , . . . , f n } is controlled by w n , another tuning parameter which in general may depend on n. For the sake of simplicity, we model the edge weight W (f i , f j , β k ; w n ) as a function of the node features f i and f j via a p-dimensional vector of their similarity measures φ ij = φ(f i , f j ). The choice of similarity measures in φ depends on the type of f i (for example, on whether the features are numerical or categorical) and is determined on a case by case basis; the only important property is that φ assigns higher values to features that are more similar. Note that this trivially allows the inclusion of edge features as well as node features, as long as they are converted to some sort of similarity. To eliminate potential differences in units and scales, we standardize all φ ij along each feature dimension. Finally, the function W should be increasing 2 in φ ij , β , which can be viewed as the "overall similarity" between nodes, and for optimization purposes it is convenient to take W to be concave. Here we use the exponential function, One can use other functions of similar shapes, for example, the logit exponential function, which we found empirically to perform similarly. The joint community detection criterion needs to be optimized over both the community assignments e and the feature parameters β. Using block coordinate descent, we optimize JCDC by alternately optimizing over the labels with fixed parameters and over the parameters with fixed labels, and iterating until convergence. When parameters β are fixed, all edge weights w ijk 's can be treated as known constants. It is infeasible to search over all n K possible label assignments, and, like many other community detection methods, we rely on a greedy label switching algorithm to optimize over e, specifically, the tabu search (29), which updates the label of one node at a time. Since our criterion involves the number of nodes in each community |E k |, no easy spectral approximations are available. Fortunately, our method allows for a simple local approximate update which does not require recalculating the entire criterion. For a given node i considered for label switching, the algorithm will assign it to community k rather than l if where S kk is twice the total edge weights in community k, and S i↔k is the sum of edge weights between node i and all the nodes in E k . When |E k | and |E l | are large, we can ignore +1 in the denominators, and (2.1) becomes 2) which allows for a "local" update for the label of node i without calculating the entire criterion. This also highlights the impact of the tuning parameter α: when α = 1, the two sides of (2.2) can be viewed as averaged weights of all edges connecting node i to communities E k and E l , respectively. Then our method assigns node i to the community with which it has the strongest connection. When α = 1, the left hand side of (2.2) is multiplied by a factor (|E k |/|E l |) 1−α . Suppose |E k | is larger than |E l |; then choosing 0 < α < 1 indicates a preference for assigning a node to the larger community, while α > 1 favors smaller communities. A detailed numerical investigation of the role of α is provided in the Supplemental Material. The edge weights involved in (2.2) depend on the tuning parameter w n . When β = 0, all weights are equal to w n − 1. On the other hand, w ijk ≤ w n for all values of β. Therefore, w n /(w n − 1) is the maximum amount by which our method can reweigh an edge. When w n is large, w n /(w n − 1) ≈ 1, and thus the information from the network structure dominates. When w n is close to 1, the ratio is large and the feature-driven edge weights have a large impact. See the Supplemental Material for more details on the choice of w n . While the tuning parameter w n controls the amount of influence features can have on community detection, it does not affect the estimated parameters β for a fixed community assignment. This is easy to see from rearranging terms in (1.2): where the function g does not depend on w n . Note that the term containing w n does not depend on β.  Since we chose a concave edge weight function (1.3), for a given community assignment e the joint criterion is a concave function of β k , and it is straightforward to optimize over β k by gradient ascent. The role of β k is to control the impact of different features on each community. One can show by a Taylor-series type expansion around the maximum (details omitted) and also observe empirically that for our method, the estimatedβ k 's are correlated with the feature similarities between nodes in community k. In other words, our method tends to produce a large estimatedβ ( ) k for a feature with high similarity values φ ( ) ij 's for i, j ∈ E k . However, in the extreme case, the optimalβ ( ) k can be +∞ if all φ ( ) ij 's are positive in community k or −∞ if all φ ( ) ij 's are negative (recall that similarities are standardized, so this cannot happen in all communities). To avoid these extreme solutions, we subtract a penalty term λ β 1 from the criterion (1.2) while optimizing over β. We use a very small value of λ (λ = 10 −5 everywhere in the paper) which safeguards against numerically unstable solutions but has very little effect on other estimated coefficients. The proposed JCDC criterion (1.2) is not model-based, but under certain models it is asymptotically consistent. We consider the setting where the network A and the features F are generated independently from a stochastic block model and a uniformly bounded distribution, respectively. Let P(A ij = 1) = ρ n P cicj where ρ n is a factor controling the overall edge density and c = (c 1 , . . . , c n ) is the vector of true labels. Assume the following regularity conditions hold: 1. There exist global constants M φ and M β , such that φ ij 2 ≤ M φ and β k 2 ≤ M β for all k, and the tuning parameter w n satisfies log w n > M φ M β . Condition 1 states that node feature similarities are uniformly bounded. This is a mild condition in many applications as the node features are often themselves uniformly bounded. In practice, for numerical stability the user may want to standardize node features and discard individual features with very low variance, before calculating the corresponding similarities φ. Condition 2 guarantees communities do not vanish asymptotically. Condition 3 enforces assortativity. Since the estimated labels e are only defined up to an arbitrary permutation of communities, we measure the agreement betwee e and c by d(e, c) = min σ∈P K 1 n n i=1 1(σ(e i ) = c i ), where P K is the set of all permutations of {1, . . . , K}. Theorem 1 (Consistency of JCDC). Under conditions 1, 2 and 3, if nρ n → ∞, w n ρ n → ∞, and the parameter α satisfies then we have, for any fixed δ > 0, The proof is given in the Supplemental Material. We compare JCDC to three representative benchmark methods which use both the adjacency matrix and the node features: CASC (Covariate Assisted Spectral Clustering, (24)), CESNA (Communities from Edge 4 Structure and Node Attributes, (19)), and BAGC (BAyesian Graph Clustering, (20) ). In addition, we also include two standard methods that use either the network adjacency alone (SC, spectral clustering on the Laplacian regularized with a small constant τ = 1e − 7, as in (21)), or the node features alone (KM, Kmeans performed on the p-dimensional node feature vectors, with 10 random initial starting values). We generate networks with n = 150 nodes and K = 2 communities of sizes 100 and 50 from the degree-corrected stochastic block model as follows. The edges are generated independently with probability θ i θ j p if nodes i and j are in the same community, and rθ i θ j p if nodes i and j are in different communities. We set p = 0.1 and vary r from 0.25 to 0.75. We set 5% of the nodes in each community to be "hub" nodes with the degree correction parameter θ i = 10, and for the remaining nodes set θ i = 1. All resulting products are thresholded at 0.99 to ensure there are no probability values over 1. These settings result in the average expected node degree ranging approximately from 22 to 29. For each node i, we generate p = 2 features, with one "signal" feature related to the community structure and one "noise" feature whose distribution is the same for all nodes. The "signal" feature follows the distribution N (µ, 1) for nodes in community 1 and N (−µ, 1) for nodes in community 2, with µ varying from 0.5 to 2 (larger µ corresponds to stronger signal). For use with CESNA, which only allows categorical node features, we discretize the continuous node features by partitioning the real line into 20 bins using the 0.05, 0.1, . . . , 0.95-th quantiles. For the JCDC, based on the study of the tuning parameters in the Supplemental Material, we use α = 1 and compare two values of w n , w n = 1.5 and w n = 5. Finally, agreement between the estimated communities and the true community labels is measured by normalized mutual information, a measure commonly used in the network literature which ranges between 0 (random guessing) and 1 (perfect agreement). For each configuration, we repeat the experiments 30 times, and record the average NMI over 30 replications. Figure 1 shows the heatmaps of average NMI for all methods under these settings, as a function of r and µ. As one would expect, the performance of spectral clustering (c), which uses only the network information, is only affected by r (the larger r is, the harder the problem), and the performance of K-means (d), which uses only the features, is only affected by µ (the larger µ is, the easier the problem). JCDC is able to take advantage of both network and feature information by estimating the coefficients β from data, and its performance only deteriorates when neither is informative. The informative features are more helpful with a larger value of w (a), and conversely uninformative features affect perfomance slightly more with a lower value of w (b), but this effect is not strong. CASC (e) appears to inherit the sharp phase transition from spectral clustering, which forms the basis of CASC; the sharp transition is perhaps due to different community sizes and hub nodes, which are both challenging to spectral clustering; CESNA (f) and BAGC (g) do not perform as well overall, with BAGC often clustering all the hub nodes into one community. 5
It is also computational inefficient to include a large number of attributes in the training phase REF .
Community Detection in Networks with Node Features
Electronic Journal of Statistics, Volume 10, Number 2 (2016), 3153-3178
Mathematics Computer Science Physics