Community Detection of Multi-Layer Attributed Networks via Penalized Alternating Factorization

Abstract

Communities are often associated with important structural characteristics of a complex network system, therefore detecting communities is considered to be a fundamental problem in network analysis. With the development of data collection technology and platform, more and more sources of network data are acquired, which makes the form of network as well as the related data more complex. To achieve integrative community detection of a multi-layer attributed network that involves multiple network layers together with their attribute data, effectively utilizing the information from the multiple networks and the attributes may greatly enhance the accuracy of community detection. To this end, in this article, we study the integrative community detection problem of a multi-layer attributed network from the perspective of matrix factorization, and propose a penalized alternative factorization (PAF) algorithm to resolve the corresponding optimization problem, followed by the convergence analysis of the PAF algorithm. Results of the numerical study, as well as an empirical analysis, demonstrate the advantages of the PAF algorithm in community discovery accuracy and compatibility with multiple types of network-related data.

1. Introduction

Network science is one of the most active research fields in recent years [1], which has been successfully applied in many fields, including the social science to study social relationships among individuals [2], biology to study interactions among genes and proteins [3], neuroscience to study the structure and function of the brain [4], and so on. Networks can represent and analyze the relational structure among interacting units of a complex system, and in many cases, the units of a network can be divided into groups with the property that there are many edges between units in the same group, but relatively few edges between units in different groups. Such groups are known as communities, which are often associated with important structural characteristics of a complex system. [5,6].

For example, in social networks, communities can correspond to groups with common interests [7,8]. In World Wide Web networks, communities can correspond to webpages with related topics [9]; in brain networks, they can correspond to specialized functional components [10]; and in protein–protein interaction networks, they can correspond to groups of proteins that contribute to the same cellular function [11]. Communities are often useful for understanding the essential functionality and organizational principles of networks. Therefore, community detection is considered a fundamental problem in understanding and analyzing networks [6].

Community detection has been widely studied in many application fields since the 1980s. Various models and algorithms have been developed in different fields, such as machine learning, network science, social science, and statistical physics. Community detection is a computationally challenging problem because the number of possible partitions of nodes into nonoverlapping groups is non-polynomial in the size of a network, especially in large networks. To deal with this challenging problem, a large number of algorithmic approaches have been proposed [12,13,14,15,16], including various greedy algorithms, such as hierarchical clustering [17], graph partitioning [18], and the methods based on optimizing a global criterion over all possible partitions, such as normalized cuts [19] and modularity [20]. Other algorithmic approaches include spectral methods [21,22,23,24], semi-definite programming [25,26], low-rank approximation [27], and non-negative matrix factorization [28].

Recently the quantities and types of network-related data are rising very fast, as data collection technologies or platforms rapidly evolve. Consequently, a large number of studies on community detection for various types of network-related data have been conducted, which will be introduced as follows according to the type of networks they are targeting.

First, for a single network, a number of approaches to community detection have been proposed based on probabilistic models for networks with communities, such as the stochastic block model [29], the degree-corrected stochastic block model [30], and the latent factor model [31]. Other approaches by optimizing a criterion measuring the strength of community structure in some sense also have appeared, often through non-negative matrix factorization [28] and spectral approximations, such as normalized cuts [19], modularity [20,32], and many variants of spectral clustering [33,34].

For attributed network, i.e., a network together with its attribute data, several generative models for jointly modeling the edges and the attributes have been proposed, including the network random effects model [35], the embedding feature model [36], the latent variable model [37], the discriminative approach [38], the latent multi-group membership graph model [39], the social circles model for ego networks [40], the communities from edge structure and node attributes model [41], the Bayesian graph clustering model [42], the topical communities and personal interest model [43], the modified stochastic block model [44], and a criterion-based method [45].

Multi-layer network involves networks from interdependent but distinct sources [46,47], which can be simultaneously collected for a certain group of units [48]. Community detection of this type of network has been applied to a variety of problems [49,50], including clustering of temporal networks through a dynamic stochastic block model [51], modeling and analysis of air transportation routes [52], studying individuals with multiple sociometric relations [53,54], and analyzing relationships between social interactions and economic exchange [55].

In addition, in many real network data analysis, there will be a more complex or general type of network, named multi-layer attributed network, which involves multiple network layers together with their attribute data. If the multiple networks share a common community structure and the distribution of unit attributes is also correlated with this community structure, then an integrative community detection approach that can integrate information from the multiple networks as well as the attributes may make better use of all these network-related data, therefore increase the accuracy of community detection as much as possible. Unfortunately, the research on multi-layer attributed network is still in its infancy, which leads us to further explore the problem description and corresponding solution of its community detection.

To this end, in this article, we employ the framework of integrative matrix factorization to formulate and achieve community detection of a multi-layer attributed network, which can be compatible with all the special cases of a multi-layer attributed network: the single network, attributed network, and the multi-layer network. In pursuit of community discovery accuracy and compatibility with multiple types of network-related data, we propose to use the penalized alternative factorization, named the PAF algorithm, to resolve the corresponding optimization problem.

The rest of this article is organized as follows. We elaborate the community detection problem of multi-layer attributed network in Section 2, and present the PAF algorithm to learn communities in Section 3, followed by the theoretical analysis of PAF in Section 4. The numerical performance of PAF is demonstrated in Section 5, and an empirical analysis is demonstrated in Section 6. Finally, we conclude this article in Section 7 and relegate the technical proofs to Appendix A and Appendix B.

2. Problem Formulation

In this section, we will describe in detail the problems of community detection based on matrix factorization from the single network to the multi-layer attributed networks.

2.1. Single Network

Let $G=(N,E)$ denote a single network, where $N=\{1,...,n\}$ is the node set that represents the units of the modeled system, and $E\subseteq N\times N$ is the edge set containing all pairs of nodes $(u,v)$ such that nodes u and v share a social, physical, or functional relationship, where $N\times N$ denotes the Cartesian product of N and N. A network G can be characterized by an $n\times n$ adjacency matrix $A=\left(A_{ij}\right)$ with each $A_{ij}\in \{0,1\}$, where $A_{ij}=1$ means that there exists an edge from nodes i to j in network G; otherwise, is not. The purpose of community detection is to identify a partition of N with community structure via the observed adjacency matrix A. Due to numerous definitions of communities, there are numerous approaches to implementing community detection. In view of the simplicity and effectiveness of a matrix factorization approach, in this article we consider the problem of community detection based on the framework of matrix factorization.

In the framework of matrix factorization, the problem of community detection, given a predetermined number of communities $k^{*}$, can be formulated as the following optimization problem,

$$\underset{\begin{array}{c}C\in {\mathcal{R}}^{n\times k^{*}}\\ S\in {\mathcal{R}}^{k^{*}\times k^{*}}\end{array}}{min}{\parallel A-CS{C}^T\parallel }_F^2,$$

(1)

where C is the unknown $n\times k^{*}$ matrix used to find $k^{*}$ communities, S is the unknown $k^{*}\times k^{*}$ weight matrix, and ${\parallel ·\parallel }_F$ denotes the Frobenius norm. This optimization problem is the same as that studied in [28], except that in our optimization problem the non-negative constraints on matrix elements of C and S are removed to improve computational efficiency. The matrix C can be viewed as the community label matrix of A. By treating each row of C as a point in ${\mathbb{R}}^{k^{*}}$, we divide these points into $k^{*}$ clusters via k-means or any other clustering algorithm. Then, we assign the network node $i\in N$ to community $k\in \{1,...,k^{*}\}$ if and only if row i of matrix C is assigned to cluster k.

From a statistical point of view, we find that the above optimization problem (1) is closely related to the well-known stochastic block model (SBM) [29]. Specifically, under the $k^{*}$-community SBM with the $n\times k^{*}$ ground truth label matrix $C^{\left(0\right)}$ and the $k^{*}\times k^{*}$ connectivity probability matrix $S^{\left(0\right)}$, once the diagonal elements of the adjacency matrix A are also considered as random terms, not fixed to be zero, then the conditional expectation of A given $C^{\left(0\right)}$ is

$$\begin{array}{c}\hfill \mathbb{E}\left(A\right|C^{\left(0\right)})=C^{\left(0\right)}{S}^{\left(0\right)}{C^{\left(0\right)}}^T.\end{array}$$

(2)

Similar to the least-squares method, the ground truth labels $C^{\left(0\right)}$ can be predicted by minimizing the sum of squares of the observations $A_{ij}$’s and their conditional expectation $\mathbb{E}\left(A_{ij}\right|C)$’s:

$$\begin{array}{c}\hfill \underset{\begin{array}{c}C\in {\{0,1\}}^{n\times k^{*}}\\ S\in {[0,1]}^{k^{*}\times k^{*}}\end{array}}{min}{\parallel A-\mathbb{E}\left(A\right|C)\parallel }_F^2=\underset{\begin{array}{c}C\in {\{0,1\}}^{n\times k^{*}}\\ S\in {[0,1]}^{k^{*}\times k^{*}}\end{array}}{min}{\parallel A-CS{C}^T\parallel }_F^2,\end{array}$$

(3)

subject to ${\sum }_{j=1}^{k^{*}}{C}_{ij}=1$ for each $i\in \{1,...,n\}$. This minimization problem is very hard to achieve, as the range of C, $\{C\in {\{0,1\}}^{n\times k^{*}}:{\sum }_{j=1}^{k^{*}}{C}_{ij}=1\}$, includes ${k^{*}}^n$ values. Consequently, to make the corresponding calculation feasible, (3) may be relaxed into (1), if the accuracy of community recovery can be guaranteed. Note that in (1), the ranges of C and S are relaxed into the Euclidean spaces ${\mathbb{R}}^{n\times k^{*}}$ and ${\mathbb{R}}^{k^{*}\times k^{*}}$, respectively, whereas in other methods, such as the non-negative matrix factorization methods [28], the ranges can be relaxed into ${{\mathbb{R}}^{+}}^{n\times k^{*}}$ and ${{\mathbb{R}}^{+}}^{k^{*}\times k^{*}}$. Here, we remove the non-negative constraints to improve computational efficiency and compatibility of the proposed method, which will be explained in the following section.

2.2. Multi-Layer Attributed Network

Once the structural information from multiple sources and the attribution information of the network nodes can be collected together, we will consider the so-called multi-layer attributed network, which is written as $G_{Att}^{Mul}=(N,E^{\left(1\right)},...,E^{\left(m^{*}\right)},X)$ and characterized by $m^{*}$$n\times n$ adjacent matrices $\{A^{\left(1\right)},...,A^{\left(m^{*}\right)}\}$ as well as an $n\times p$ attribution matrix X. This is a unified framework, which can include the single network, multi-layer network, and attributed network. To achieve community detection of $G_{Att}^{Mul}$, we study the following integrative matrix factorization problem,

$$\begin{array}{c}\hfill \underset{\begin{array}{c}C\in R^{n\times k^{*}}\\ S^{\left(1\right)},...,S^{\left(M\right)}\in {\mathbb{R}}^{k^{*}\times k^{*}}\\ V\in {\mathbb{R}}^{p\times k^{*}}\end{array}}{min}{\displaystyle \sum _{m=1}^{m^{*}}}{\omega }_m\parallel A^{\left(m\right)}-C{S}^{\left(m\right)}{C}^T{\parallel }_F^2+{\omega }_0{\parallel X-C{V}^T\parallel }_F^2,\end{array}$$

(4)

where ${\left\{{\omega }_m\right\}}_{m=0}^{m^{*}}$ with ${\sum }_{m=0}^{m^{*}}{\omega }_m=1$ are the weight parameters specified beforehand and V is a $p\times k^{*}$ matrix as the right part of the matrix factorization of X. Similarly, to solve (4), we consider the following approximate minimization problem,

$$\begin{array}{c}\hfill \underset{\begin{array}{c}C\in R^{n\times k^{*}}\\ S^{\left(1\right)},...,S^{\left(m^{*}\right)}\in {\mathbb{R}}^{k^{*}\times k^{*}}\\ V\in {\mathbb{R}}^{p\times k^{*}}\end{array}}{min}{\displaystyle \sum _{m=1}^{m^{*}}}{\omega }_m\parallel A^{\left(m\right)}-C^{\left(1\right)}{S}^{\left(m\right)}{C}^{\left(2\right)}{\parallel }_F^2+\frac{{\omega }_0}{2}{\displaystyle \sum _{t=1}^2}\parallel X-C^{\left(t\right)}{V}^T{\parallel }_F^2+\lambda {\parallel C^{\left(1\right)}-C^{\left(2\right)}\parallel }_F^2\\ \hfill +\nu \{\parallel C^{\left(1\right)}{\parallel }_F^2+\parallel C^{\left(2\right)}{\parallel }_F^2+\parallel V{\parallel }_F^2+{\displaystyle \sum _{m=1}^{m^{*}}}\parallel S^{\left(m\right)}{\parallel }_F^2\}.\end{array}$$

(5)

Note that throughout this section, the weights ${\left\{{\omega }_m\right\}}_{m=0}^{m^{*}}$ need to be given beforehand by the users according to background knowledge. To determine these weights, one user may have to take into account the importance and scale of data from each source. If no additional information is available, for simplicity, the weights can be equally distributed.

3. Learning Algorithm

We present a penalized alternating factorization (PAF) scheme to minimize (5). In particular, the objective function is minimized step by step by fixing any $m^{*}+2$ matrices in $\{C^{\left(1\right)},C^{\left(2\right)},S^{\left(1\right)},...,S^{\left(m^{*}\right)},V\}$ and then optimizing the objective function with respect to the remaining one. The algorithm is described in details as follows.

Algorithm 1 Penalized Alternating Factorization (PAF) Algorithm.

Input:  $m^{*}$$n\times n$ adjacent matrices $\{A^{\left(1\right)},...,A^{\left(m^{*}\right)}\}$, an $n\times p$ attribution matrix X, the number of communities $k^{*}$. Output:  a length-n community label vector $L=(L_1,...,L_n)$. 1: Initialization: 2: (a) $t=0$; $C^{(1,-1)}$ and $C^{(2,-1)}$ are both $n\times k^{*}$ zero matrix. 3: (b) apply SCP, the spectral clustering with perturbations [33], to $A^{*}={\displaystyle \sum _{m=1}^{m^{*}}}{\omega }_m{A}^{\left(m\right)}$ and find $k^{*}$ initial communities, transform the resulting length-n community label vector into the $n\times k^{*}$ community label matrix, then make $C^{(1,0)}$ and $C^{(2,0)}$ equal to this initial community label matrix, where $C^{(1,0)},C^{(2,0)}\in R^{n\times k^{*}}$ are initial chooses of $C^{\left(1\right)},C^{\left(2\right)}$ respectively. 4: (c) let $$\begin{array}{ccc}{V}^{\left(0\right)}& =& X^T\left[C^{(1,0)}+C^{(2,0)}\right]{\left[{C^{(1,0)}}^T{C}^{(1,0)}+{C^{(2,0)}}^T{C}^{(2,0)}\right]}^{-1},\\ S^{(m,0)}& =& {\left[{C^{(1,0)}}^T{C}^{(1,0)}\right]}^{-1}{C^{(1,0)}}^T{A}^{\left(m\right)}{C}^{(2,0)}{\left[{C^{(2,0)}}^T{C}^{(2,0)}\right]}^{-1}.\end{array}$$ 5: while$C^{(1,t-1)}$, $C^{(2,t-1)}$, $C^{(1,t)}$, $C^{(2,t)}$ are not equal do 6: (a) given $\left(C^{(2,t)},{\left\{S^{(m,t)}\right\}}_{m=1}^{m^{*}},V^{\left(t\right)}\right)$, update $C^{(1,t+1)}$ by $$\begin{array}{c}\left[{\displaystyle {\displaystyle \sum _{m=1}^{m^{*}}}}{\omega }_m{A}^{\left(m\right)}{C}^{(2,t)}{S^{(m,t)}}^T+\frac{{\omega }_0}{2}X{V}^{\left(t\right)}+\lambda \right]\\ {\left[{\displaystyle {\displaystyle \sum _{m=1}^{m^{*}}}}{\omega }_m{\left[C^{(2,t)}{S^{(m,t)}}^T\right]}^T\left[C^{(2,t)}{S^{(m,t)}}^T\right]+\frac{{\omega }_0}{2}{V^{\left(t\right)}}^T{V}^{\left(t\right)}+\left(\lambda +\nu \right)I_{k^{*}}\right]}^{-1};\end{array}$$ (6) 7: (b) given $\left(C^{(1,t+1)},{\left\{S^{(m,t)}\right\}}_{m=1}^{m^{*}},V^{\left(t\right)}\right)$, update $C^{(2,t+1)}$ by $$\begin{array}{c}\left[{\displaystyle {\displaystyle \sum _{m=1}^{m^{*}}}}{\omega }_m{A}^{\left(m\right)}T{C}^{(1,t+1)}{S}^{(m,t)}+\frac{{\omega }_0}{2}X{V}^{\left(t\right)}+\lambda \right]\\ {\left[{\displaystyle {\displaystyle \sum _{m=1}^{m^{*}}}}{\omega }_m{\left[C^{(1,t+1)}{S}^{(m,t)}\right]}^T\left[C^{(1,t+1)}{S}^{(m,t)}\right]+\frac{{\omega }_0}{2}{V^{\left(t\right)}}^T{V}^{\left(t\right)}+\left(\lambda +\nu \right)I_{k^{*}}\right]}^{-1};\end{array}$$ (7) 8: (c) given $\left(C^{(1,t+1)},C^{(2,t+1)},V^{\left(t\right)}\right)$, update $S^{(m,k+1)}$ for each $m\in \{1,...,m^{*}\}$ as follows, $$\begin{array}{c}\hfill \mathit{vec}\left(S^{(m,k+1)}\right)={\left({\omega }_m{B^{(2,k+1)}}^T\otimes B^{(1,k+1)}+(\alpha +\nu )I_{k^{*}}\right)}^{-1}\mathit{vec}\left(U^{(m,k+1)}\right),\end{array}$$ (8) where $B^{(1,k+1)}={C^{(1,t+1)}}^T{C}^{(1,t+1)}$, $B^{(2,k+1)}={C^{(2,t+1)}}^T{C}^{(2,t+1)}$, $U^{(m,k+1)}={\omega }_m{C^{(1,t+1)}}^T{A}^{\left(m\right)}{C}^{(2,t+1)}-\alpha S^{(m,t)}$, and $vec(·)$ denotes the vectorization of a matrix by stacking its columns and ⊗ is the Kronecker product of two matrices; 9: (d) given $\left(C^{(1,t+1)},C^{(2,t+1)},{\left\{S^{(m,k+1)}\right\}}_{m=1}^{m^{*}}\right)$, update $V^{(t+1)}$ by $$\begin{array}{c}\hfill \left[X^T\left(C^{(1,t+1)}+C^{(2,t+1)}\right)+2\beta /{\omega }_0{V}^{\left(t\right)}\right]{\left[{C^{(1,t+1)}}^T{C}^{(1,t+1)}+{C^{(2,t+1)}}^T{C}^{(2,t+1)}+2(\beta +\nu )/{\omega }_0\right]}^{-1};\end{array}$$ (9) 10: (e) $t=t+1$. 11: end while 12: return the community label vector L by applying k-means to cluster the rows of $C^{(1,t)}$.

Here, $\alpha$, $\beta$, and $\nu$ are set to be three small positive numbers, used to ensure convergence of the algorithm. Note that in the update step of the above algorithm, all the update formulas have explicit expressions. Specifically, given $\left(C^{(2,t)},{\left\{S^{(m,t)}\right\}}_{m=1}^{m^{*}},V^{\left(t\right)}\right)$, we update $C^{(1,t+1)}$ by

$$\begin{array}{ccc}{C}^{(1,t+1)}\hfill & =\hfill & \underset{C^{\left(1\right)}\in {\mathbb{R}}^{n\times k^{*}}}{argmin}\{{\displaystyle \sum _{m=1}^{m^{*}}}{\omega }_m{\parallel A^{\left(m\right)}-C^{\left(1\right)}{S}^{(m,t)}{C}^{(2,t)}\parallel }_F^2\hfill \\ & & +\frac{{\omega }_0}{2}\parallel X-C^{\left(1\right)}{V^{\left(t\right)}}^T{\parallel }_F^2+\lambda {\parallel C^{\left(1\right)}-C^{(2,t)}\parallel }_F^2+\nu \parallel C^{\left(1\right)}{\parallel }_F^2\},\hfill \end{array}$$

which has the explicit expression in in (6)

$$\begin{array}{c}\left[{\displaystyle \sum _{m=1}^{m^{*}}}{\omega }_m{A}^{\left(m\right)}{C}^{(2,t)}{S^{(m,t)}}^T+\frac{{\omega }_0}{2}X{V}^{\left(t\right)}+\lambda \right]\hfill \\ {\left[{\displaystyle \sum _{m=1}^{m^{*}}}{\omega }_m{\left[C^{(2,t)}{S^{(m,t)}}^T\right]}^T\left[C^{(2,t)}{S^{(m,t)}}^T\right]+\frac{{\omega }_0}{2}{V^{\left(t\right)}}^T{V}^{\left(t\right)}+\left(\lambda +\nu \right)I_{k^{*}}\right]}^{-1}.\hfill \end{array}$$

Similarly, we update $C^{(1,t+1)}$ in (7). Then, in (8), given $\left(C^{(1,t+1)},C^{(2,t+1)},V^{\left(t\right)}\right)$, we update $S^{(m,t+1)}$ by

$$\begin{array}{c}\hfill S^{(m,t+1)}=\underset{S^{\left(m\right)}\in {\mathbb{R}}^{k^{*}\times k^{*}}}{argmin}{\omega }_m\parallel A^{\left(m\right)}-C^{(1,t+1)}{S}^{\left(m\right)}{C}^{(2,t+1)}{\parallel }_F^2+\alpha {\parallel S^{\left(m\right)}-S^{(m,t)}\parallel }_F^2+\nu \parallel S^{\left(m\right)}{\parallel }_F^2.\end{array}$$

Finally, given $\left(C^{(1,t+1)},C^{(2,t+1)},{\left\{S^{(m,t+1)}\right\}}_{m=1}^{m^{*}}\right)$, we update $V^{(t+1)}$ by

$$\begin{array}{ccc}\hfill V^{(t+1)}& =& \underset{V\in {\mathbb{R}}^{p\times k^{*}}}{argmin}\frac{{\omega }_0}{2}{\displaystyle \sum _{l=1}^2}\parallel X-C^{(l,t+1)}{V}^T{\parallel }_F^2+\beta {\parallel V-V^{\left(t\right)}\parallel }_F^2+{\nu \parallel V\parallel }_F^2,\hfill \end{array}$$

which has the explicit expression in (9)

$$\begin{array}{c}\left[X^T\left(C^{(1,t+1)}+C^{(2,t+1)}\right)+2\beta /{\omega }_0{V}^{\left(t\right)}\right]\hfill \\ {\left[{C^{(1,t+1)}}^T{C}^{(1,t+1)}+{C^{(2,t+1)}}^T{C}^{(2,t+1)}+2(\beta +\nu )/{\omega }_0\right]}^{-1}.\hfill \end{array}$$

4. Theoretical Analysis

Next, we consider the convergence theory of the PAF algorithm. We will present that the iteration sequence ${\{{\Theta }^{\left(t\right)}=(C^{(1,t)},C^{(2,t)},{\left\{S^{(m,t)}\right\}}_{m=1}^{m^{*}},V^t)\}}_{t=1}^{\infty }$ generated by the PAF algorithm converges to a critical point of (5).

Proposition 1.

There exist a constant $\delta >0$ such that for each $t\in \{1,2,...\}$, $\parallel {\Theta }^{\left(t\right)}{\parallel }_F\le \delta$.

Proof. 

Please see Appendix A.1.□

Proposition 2.

For each $t\in \{1,2,...\}$,

$${\rho }_1{\parallel {\Theta }^{(t+1)}-{\Theta }^{\left(t\right)}\parallel }_F^2\le [\mathcal{H}\left({\Theta }^{\left(t\right)}\right)-\mathcal{H}\left({\Theta }^{(t+1)}\right)],$$

(10)

where ${\rho }_1=min\{2(\lambda {+\nu )}^2,\alpha ,\beta \}$.

Proof. 

Please see Appendix A.2.□

Proposition 3.

For each $t\in \{1,2,...\}$,

$$\forall {\kappa }^{(t+1)}\in \partial H\left({\Theta }^{(t+1)}\right),\parallel {\kappa }^{(t+1)}{\parallel }_F\le {\rho }_2{\parallel {\Theta }^{(t+1)}-{\Theta }^{\left(t\right)}\parallel }_F,$$

(11)

where ${\rho }_2=max\{4\delta (2{\delta }^3+\tau )+2\alpha ,2({\delta }^4+\tau \delta M+\lambda ),2(2{\delta }^2+{\parallel X\parallel }_F+\beta \left)\right\}$.

Proof. 

Please see Appendix A.3.□

Theorem 1.

$\left\{{\Theta }^{\left(t\right)}\right\}$ converges to a critical point of $\mathcal{H}(\Theta )$.

Proof. 

Please see Appendix A.4.□

5. Numerical Study

We now present the results of some numerical study to demonstrate the performance of the PAF algorithm, and the comparison with some existing methods, abbreviated as SCP, ANMF, and NMF, respectively. SCP is the spectral clustering with perturbations [33]. ANMF and NMF are the non-negative matrix factorization methods proposed in [28] for directed and undirected networks respectively. All the network data are generated from SBM or multi-layer SBM, and the attribution data are generated from multivariate normal distributions, where the distribution parameters will be specified in each following setting. We will use the normalized mutual information (NMI) to measure the consistency between the predicted labels and the true community labels.

First, we consider the following two simulation settings for single networks and attributed networks:

I

The $n\times n$ adjacency matrix A is generated from the undirected SBM with the parameters

$$\begin{array}{c}\hfill P=\left(\begin{array}{cc}0.20& 0.12\\ 0.12& 0.20\end{array}\right),\pi =\left(\begin{array}{c}0.50\\ 0.50\end{array}\right).\end{array}$$

(12)

Each row of the $n\times 2$ attribution matrix is independently generated from the multivariate normal distribution $N_2({\mu }_k,{\sigma }^2{I}_2)$, where the kth element of ${\mu }_k$ is 1 and the remaining element is 0, and ${\sigma }^2=0.15$.

II

The same as Setting I, except that the undirected SBM is replaced by directed SBM.

The simulation results for Settings I and II are summarized in Figure 1, where SCP $\left(A\right)$, NMF $\left(A\right)$, ANMF $\left(A\right)$, and PAF $\left(A\right)$ denote applying SCP, NMF, ANMF, and PAF to A, respectively, k-means $\left(X\right)$ denotes applying k-means to X and PAF $(A,X)$ denotes applying PAF to $(A,X)$. The results of SCP $\left(A\right)$, NMF $\left(A\right)$, ANMF $\left(A\right)$, and PAF $\left(A\right)$ in Figure 1 suggest that (1) PAF is a very good alternative to NMF and ANMF in terms of accuracy of community detection, and (2) NMF, ANMF, and PAF outperform SCP in situation where directed networks are studied.

On the other hand, the comparison between PAF $(A,X)$ and the other methods in Figure 1 suggests that applying k-means to the attribution data alone fails to achieve community detection; however, once the attribution data and the network data are combined, much better results can be obtained than using the network and attribution data separately.

Next, we consider the following two simulation settings for multi-layer networks and multi-layer attributed networks:

III

The $m^{*}=3$$n\times n$ adjacent matrices $\{A^{\left(1\right)},A^{\left(2\right)},A^{\left(3\right)}\}$ are generated independently from the undirected multi-layer SBM with common community labels, where the parameters are set as follows,

$$\begin{array}{ccc}\hfill P_1& =& \left(\begin{array}{ccc}0.2& 0.2& 0.13\\ 0.2& 0.2& 0.13\\ 0.13& 0.13& 0.2\end{array}\right),P_2=\left(\begin{array}{ccc}0.2& 0.13& 0.13\\ 0.13& 0.2& 0.2\\ 0.13& 0.2& 0.2\end{array}\right),\hfill \end{array}$$

(13)

$$\begin{array}{ccc}\hfill P_3& =& \left(\begin{array}{ccc}0.2& 0.13& 0.2\\ 0.13& 0.2& 0.13\\ 0.2& 0.13& 0.2\end{array}\right),\pi =\left(\begin{array}{c}0.3\dot{3}\\ 0.3\dot{3}\\ 0.3\dot{3}\end{array}\right).\hfill \end{array}$$

(14)

Each row of the $n\times 3$ attribution matrix is independently generated from the multivariate normal distribution $N_3({\mu }_k,{\sigma }^2{I}_3)$, where the kth element of ${\mu }_k$ is 1 and the remaining elements are 0, and ${\sigma }^2=0.15$.

IV

The same as Setting III, except that the undirected multi-layer SBM model is replaced by directed multi-layer SBM.

The simulation results for Settings III and IV are summarized in Figure 2, where PAF $(A^{\left(1\right)},A^{\left(2\right)},A^{\left(3\right)},X)$ denotes applying PAF to $(A^{\left(1\right)},A^{\left(2\right)},A^{\left(3\right)},X)$ and $A^{*}=\frac{1}{m^{*}}{\sum }_{m=1}^{m^{*}}{A}^{\left(m\right)}$. The comparison between PAF $(A^{\left(1\right)},A^{\left(2\right)},A^{\left(3\right)},X)$ and NMF $\left(A^{*}\right)$, ANMF $\left(A^{*}\right)$, SCP $\left(A^{*}\right)$, SCP $\left(A^{\left(1\right)}\right)$, SCP $\left(A^{\left(2\right)}\right)$, and SCP $\left(A^{\left(3\right)}\right)$ suggests that (1) integrating community information from the multiple adjacent matrices of the network layers may perform better than using each network layer separately, and (2) using the PAF algorithm to achieve integrative community detection for the multi-layer attributed network can make appropriate use of the network-related data from multiple sources.

6. Empirical Analysis

In this section, we apply the proposed PAF method to a dataset that comes from a network study of a corporate law partnership, which was carried out in a Northeastern US corporate law firm, referred to as SG&R, 1988–1991 in New England and previously studied in [45,56,57]. The dataset includes 71 attorneys of this firm and three network layers, co-work layer, advice layer, friendship layer, as well as some attributes of the attorneys, such as status (1 = partner; = associate), gender (1 = man; 2 = woman), office (1 = Boston; 2 = Hartford; 3 = Providence), years with the firm, age, practice (1 = litigation; 2 = corporate), and law school (1: Harvard, Yale; 2: UCON; 3: other). We treat the attribute “status” as the ground truth community label as in [45]. In fact, after eliminating six isolated nodes, the heatmap plots of the adjacency matrices with nodes sorted by each attribute variable indicate that the partition by “status” can present a strong assortative structure. Then, the data of the remaining six attributes together with the three network layers form a multi-layer attributed network to be studied, with $m^{*}=3$ network layers and $p=6$ attribute variables, which falls right into the scope of application of the proposed method.

Intuitively, all these three network layers and six attributes can contribute to the community detection task with the ground truth label “status”. Specifically, the descriptive analysis results in Figure 3 present that all these six attributes can provide useful information to distinguish the two values of “status”; the top three panels of Figure 4, i.e., the heatmap plots of the three adjacent matrices partitioned by the ground truth labels, partly present block structure according to the two values of “status”.

The authors of [45] offered a comparison of seven methods for community detection of this dataset, we recall the NMI results of these methods in [45] by

Table 1. The NMI results of eight community detection methods for the multi-layer attributed network with $m^{*}=3$ network layers and $p=6$ attribute variables.

Method	NMI
JCDC, ${\omega }_n=5$	0.54
JCDC, ${\omega }_n=1.5$	0.50
SCP	0.44
k-means	0.44
CASC	0.49
CESNA	0.07
BAGC	0.20
PAF	0.58

, together with the NMI result obtained by applying the proposed PAF method to the multi-layer attributed network with $m^{*}=3$ network layers and $p=6$ attribute variables. Table 1 indicates that the NMI performance of the PAF method is almost the same as the best existing one. Intuitively, the heatmap plots of the three adjacent matrices partitioned by the predicted labels of the PAF method are given in the bottom three panels of Figure 4, which are quite similar to those partitioned by the ground truth labels. Viewed from another perspective, we present the plots of the three network layers, colored by the ground truth labels and the predicted labels by PAF, respectively, in Figure 5, which indicate that the partition by both the ground truth labels and the predicted labels by the proposed PAF method can present a strong assortative structure for the three network layers, especially for the friendship layer. These results demonstrate the practicability of the PAF method in community detection of multi-layer attributed networks.

7. Conclusions

We have proposed PAF—a unified framework and algorithm that is applicable to community detection of multi-layer attributed networks—as well as its special cases, such as single networks, attributed networks, and multi-layer networks. The main idea of PAF is replacing the community label matrix at two different positions in the original objective function with two different substitution matrices, penalizing the gap between the two substitution matrices, and then alternately optimizing each of the substitution matrices as well as some other variable matrices. The results of the simulation study and empirical analysis demonstrate the advantages of the PAF algorithm in community discovery accuracy and compatibility with multiple types of network-related data.

In our future work, we will study community detection of multi-layer attributed networks in statistical ways, where likelihood functions under some statistical models of multi-layer attributed networks will be considered.