# Multiview Community Discovery Algorithm via Nonnegative Factorization Matrix in Heterogeneous Networks

Authors: Wang Tao; Liu Yang
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

With the rapid development of the Internet and communication technologies, a large number of multimode or multidimensional networks widely emerge in real-world applications. Traditional community detection methods usually focus on homogeneous networks and simply treat different modes of nodes and connections in the same way, thus ignoring the inherent complexity and diversity of heterogeneous networks. It is challenging to effectively integrate the multiple modes of network information to discover the hidden community structure underlying heterogeneous interactions. In our work, a joint nonnegative matrix factorization (Joint-NMF) algorithm is proposed to discover the complex structure in heterogeneous networks. Our method transforms the heterogeneous dataset into a series of bipartite graphs correlated. Taking inspiration from the multiview method, we extend the semisupervised learning from single graph to several bipartite graphs with multiple views. In this way, it provides mutual information between different bipartite graphs to realize the collaborative learning of different classifiers, thus comprehensively considers the internal structure of all bipartite graphs, and makes all the classifiers tend to reach a consensus on the clustering results of the target-mode nodes. The experimental results show that Joint-NMF algorithm is efficient and well-behaved in real-world heterogeneous networks and can better explore the community structure of multimode nodes in heterogeneous networks.


---

## Body

## 1. Introduction

Community structure is an important feature of real-world networks as it is crucial for us to study and understand the functional characteristics of the real complex systems. With the fast growth of Internet and computational technologies in the past decade, many data mining applications have advanced swiftly from the simple clustering of one data type to the multiple types, which usually involved high heterogeneity, such as the interrelations of users, videos, pictures, and web page in web networks (shown in Figure1). Those networks with multiple modes/dimensions are called heterogeneous network in this work. Unlike homogeneous networks that only contain one kind of nodes and have explicit community structure, the community structures of heterogeneous networks are usually obscure and complicated, which are owing to the coexistence of multimode or multidimensional interactions. Therefore, it is challenging to effectively integrate the information of multiple dimensions/modes to discover the hidden community structure underlying heterogeneous interactions.Figure 1
An illustrative example via web networks.There are a number of problems for traditional clustering methods to mine the community structure in heterogeneous networks. First, heterogeneous networks contain different types of nodes and relationships. Processing and interpreting them in a unified way present a major challenge. Second, various data types are related to each other. Tackling each type independently will lose the mutual information between those interactions, which are essential to gain a full understanding of heterogeneous networks. Consequently, matrix-factorization-based clustering has emerged as an effective approach for clustering problems in high-dimensional datasets. In [1], it is shown that nonnegative matrix factorization outperforms spectral methods in document clustering, achieving higher accuracy and efficiency.In this paper, we adopt multiview learning as a tool to reveal the communities in heterogeneous networks, because it has powerful interpretability and applicability for data clustering. So we present a joint nonnegative matrix factorization (Joint-NMF) solution to detect community in heterogeneous networks. To summarize, the main contributions of this work includes the following: (1) we construct the bipartite graph model of heterogeneous networks, which efficiently incorporates the multimode or multidimensional information, to enhance the community detection in heterogeneous networks. (2) We propose an optimal algorithm for the iterative procedure of joint matrix factorization. Computationally, Joint-NMF clustering is more efficient and flexible than graph-based models and can provide more intuitive clustering results. In particular, it provides mutual information between each network graph to realize the collaborative learning of different classifiers and makes all the classifiers tend to reach a consensus on the clustering results of heterogeneous networks.The remainder of the paper is organized as follows. In Section2, we demonstrate the related work about corresponding domain and define the bipartite graph model of heterogeneous networks. In Section 3, we formulate the multiview method via Joint-NMF for community detection in heterogeneous networks and present an optimal algorithm to achieve fast convergence. Then we test our algorithm on a variety of real heterogeneous networks and present the experimental results in Section 4. Finally, Section 5 concludes the paper.


## 2. Preliminary

### 2.1. Related Work

In the past years, the research of community discovery in heterogeneous networks has attracted more and more attention of researchers. Among these methods, matrix factorization effectively reflects the community structure of the networks and promises a meaningful community interpretation that is independent of the network topology. In addition to a quantification of how strongly each node participates in its community, nonnegative matrix factorization (NMF) does not suffer from the drawbacks of modularity optimization methods [2], such as the resolution limit [3]. Nguyen et al. [4] used nonnegative matrix factorization with I-divergence as the cost function and introduce two approaches which are, respectively, applied to the directed and undirected networks. Based on the importance of each node when forming links in each community, He et al. [5] use nonnegative matrix factorization to form a generative model, taking it as an optimization problem to discover the structure of link communities. Chen et al. [6] presented a semisupervised community discovery algorithm based on NMF. It introduced the a priori knowledge as constraints into the heterogeneous networks and reconstructed the feature matrix to detect communities. Tang et al. [7] introduced the concept of modularity optimization into the heterogeneous network and integrated the network snapshots in a time period and then obtained the community partition with maximum at that moment. Wang et al. [8] took the internal connections as the graph regularization constraint and utilize tri-NMF model to improve the performance of community detection in bipartite networks.Due to multidimensional nodes and special link patterns in heterogeneous networks, it is more suitable to mine the special community structure via semisupervised methods. However, most community detection methods still focus on homogeneous networks and might not work well in heterogeneous networks. There are two main reasons: first, heterogeneous data contain different types of relations. Processing and interpreting them in a unified way present a major challenge. Second, the special link patterns of heterogeneous networks greatly limit the effectiveness of these methods, which tend to cluster the multimode nodes by constructing the node or edge similarities of them, as they did in the homogeneous networks. But, for heterogeneous networks, the similarities among one-mode nodes sometimes can only be defined by the nodes of the other mode. That made these methods unable to keep working well in heterogeneous networks. In summary, most works are derived based on the graph model, which requires solving eigenvalue-problem. Computationally, they are inefficient and inapplicable to large-scale datasets. Moreover, they are completely unsupervised and ignore the inherent complexity and diversity of heterogeneous networks.Recent works [9–11] have shown that multiview learning in multimode datasets can effectively improve the clustering performance in the sense that clustering can make full use of the dual interdependence between multiple nodes to discover certain hidden community structures. In this work, we present a semisupervised method (Joint-NMF) to incorporate multimode/multidimension information for unity discovery. In the proposed methodology, users are able to provide constraints on the target mode, specifying the multiple connecting relationships in each bipartite graph. Our goal is to improve the quality of community structure by multiview learning in all modes of nodes and linking. Using an optimal iterative procedure, we then perform joint-factorizations of the bipartite graph matrices to obtain the consensus of network partition and finally infer the target-mode clusters while simultaneously deriving the communities of related feature nodes. In addition, due to the fact that NMF-based methods often require the community numbers of networks to be specified beforehand, several methods [10, 12, 13] have been developed to solve this problem. Due to the simplicity and practicability of the existing method in [4], here we choose it to get the community numbers.


### 2.2. Model Formulation

Both the multimode and multidimensional networks can be modeled as bipartite graphs, which completely describe the diverse properties and characteristics of the multimode connections. In this way, the heterogeneous network can be regarded as a comprehensive depiction of multimode nodes, described by a series of subbipartite graphs. Each bipartite graph represents the relationship between a special kind of node and the target nodes and contains the structural feature of the heterogeneous network in its own perspective. Compared to processing each subgraph independently, combining multiple bipartite graphs would undoubtedly be more effective and accurate for community discovery. For example, the document can be clustered through both semantics and reference relationship, and multimedia resources can be through the content annotation and the user preferences.By means of the multiview learning, we treat each bipartite graph as one independent feature set of the target nodes. In this way, heterogeneous networks can be depicted in multifaceted, different perspectives simultaneously. As shown in Figure1, the web network can be expressed with the triple vector. Assuming users as the target mode, pages and tags are the two-dimensional feature space that reflects the community structure of user nodes. Specifically, the bipartite graph XUserPicture shows the users’ feature in the picture dimension, and XUserVideo indicates the users’ feature in the video dimension. Based on the bipartite graph model (shown in Figure 2), heterogeneous network can be decomposed into a series of bipartite graphs {X11,X12,…,X1p}, where X1p indicates the relationships between mode 1 and mode p.Figure 2
(a) Transforming web networks into the bipartite graph model. (b) According to the bipartite graph model, the relationships between modes 1 andp are expressed as graph X1p.
(a)
(b)In this work, we take the core mode nodes as target nodes and give priority to the community division of target nodes. Due to the core position of target nodes in heterogeneous networks, community distribution of the other nodes is exclusively conducted and decided by the community structure of target nodes. Through grouping the target nodes in different communities, our method simultaneously divides the connecting nodes of the other mode into the corresponding communities. Through the bipartite graphs model, each mode’s nodes can naturally be split into different graphs, any of which suffices for mining knowledge. Observing that these bipartite graphs often provide compatible and complementary information, it becomes natural for one to integrate them together to obtain better performance rather than relying on a single view. Based on the bipartite graph model, we can use multiview learning for seamlessly integrating multiple node information to discover the underlying community structure in heterogeneous networks.


## 2.1. Related Work

In the past years, the research of community discovery in heterogeneous networks has attracted more and more attention of researchers. Among these methods, matrix factorization effectively reflects the community structure of the networks and promises a meaningful community interpretation that is independent of the network topology. In addition to a quantification of how strongly each node participates in its community, nonnegative matrix factorization (NMF) does not suffer from the drawbacks of modularity optimization methods [2], such as the resolution limit [3]. Nguyen et al. [4] used nonnegative matrix factorization with I-divergence as the cost function and introduce two approaches which are, respectively, applied to the directed and undirected networks. Based on the importance of each node when forming links in each community, He et al. [5] use nonnegative matrix factorization to form a generative model, taking it as an optimization problem to discover the structure of link communities. Chen et al. [6] presented a semisupervised community discovery algorithm based on NMF. It introduced the a priori knowledge as constraints into the heterogeneous networks and reconstructed the feature matrix to detect communities. Tang et al. [7] introduced the concept of modularity optimization into the heterogeneous network and integrated the network snapshots in a time period and then obtained the community partition with maximum at that moment. Wang et al. [8] took the internal connections as the graph regularization constraint and utilize tri-NMF model to improve the performance of community detection in bipartite networks.Due to multidimensional nodes and special link patterns in heterogeneous networks, it is more suitable to mine the special community structure via semisupervised methods. However, most community detection methods still focus on homogeneous networks and might not work well in heterogeneous networks. There are two main reasons: first, heterogeneous data contain different types of relations. Processing and interpreting them in a unified way present a major challenge. Second, the special link patterns of heterogeneous networks greatly limit the effectiveness of these methods, which tend to cluster the multimode nodes by constructing the node or edge similarities of them, as they did in the homogeneous networks. But, for heterogeneous networks, the similarities among one-mode nodes sometimes can only be defined by the nodes of the other mode. That made these methods unable to keep working well in heterogeneous networks. In summary, most works are derived based on the graph model, which requires solving eigenvalue-problem. Computationally, they are inefficient and inapplicable to large-scale datasets. Moreover, they are completely unsupervised and ignore the inherent complexity and diversity of heterogeneous networks.Recent works [9–11] have shown that multiview learning in multimode datasets can effectively improve the clustering performance in the sense that clustering can make full use of the dual interdependence between multiple nodes to discover certain hidden community structures. In this work, we present a semisupervised method (Joint-NMF) to incorporate multimode/multidimension information for unity discovery. In the proposed methodology, users are able to provide constraints on the target mode, specifying the multiple connecting relationships in each bipartite graph. Our goal is to improve the quality of community structure by multiview learning in all modes of nodes and linking. Using an optimal iterative procedure, we then perform joint-factorizations of the bipartite graph matrices to obtain the consensus of network partition and finally infer the target-mode clusters while simultaneously deriving the communities of related feature nodes. In addition, due to the fact that NMF-based methods often require the community numbers of networks to be specified beforehand, several methods [10, 12, 13] have been developed to solve this problem. Due to the simplicity and practicability of the existing method in [4], here we choose it to get the community numbers.


## 2.2. Model Formulation

Both the multimode and multidimensional networks can be modeled as bipartite graphs, which completely describe the diverse properties and characteristics of the multimode connections. In this way, the heterogeneous network can be regarded as a comprehensive depiction of multimode nodes, described by a series of subbipartite graphs. Each bipartite graph represents the relationship between a special kind of node and the target nodes and contains the structural feature of the heterogeneous network in its own perspective. Compared to processing each subgraph independently, combining multiple bipartite graphs would undoubtedly be more effective and accurate for community discovery. For example, the document can be clustered through both semantics and reference relationship, and multimedia resources can be through the content annotation and the user preferences.By means of the multiview learning, we treat each bipartite graph as one independent feature set of the target nodes. In this way, heterogeneous networks can be depicted in multifaceted, different perspectives simultaneously. As shown in Figure1, the web network can be expressed with the triple vector. Assuming users as the target mode, pages and tags are the two-dimensional feature space that reflects the community structure of user nodes. Specifically, the bipartite graph XUserPicture shows the users’ feature in the picture dimension, and XUserVideo indicates the users’ feature in the video dimension. Based on the bipartite graph model (shown in Figure 2), heterogeneous network can be decomposed into a series of bipartite graphs {X11,X12,…,X1p}, where X1p indicates the relationships between mode 1 and mode p.Figure 2
(a) Transforming web networks into the bipartite graph model. (b) According to the bipartite graph model, the relationships between modes 1 andp are expressed as graph X1p.
(a)
(b)In this work, we take the core mode nodes as target nodes and give priority to the community division of target nodes. Due to the core position of target nodes in heterogeneous networks, community distribution of the other nodes is exclusively conducted and decided by the community structure of target nodes. Through grouping the target nodes in different communities, our method simultaneously divides the connecting nodes of the other mode into the corresponding communities. Through the bipartite graphs model, each mode’s nodes can naturally be split into different graphs, any of which suffices for mining knowledge. Observing that these bipartite graphs often provide compatible and complementary information, it becomes natural for one to integrate them together to obtain better performance rather than relying on a single view. Based on the bipartite graph model, we can use multiview learning for seamlessly integrating multiple node information to discover the underlying community structure in heterogeneous networks.


## 3. Multiview Algorithm via Joint-NMF for Community Detection in Heterogeneous Networks

In this section, based on multiview learning, we propose a joint nonnegative factorization matrix algorithm for community detection. This method adopts semisupervised learning to integrate multiple bipartite graphs in heterogeneous networks and extends semisupervised learning from single graph to multiview graphs. Based on the collaborative learning between different modes (graphs), the multiview learners finally obtain the consensus on the clustering results of the target nodes, thus jointly promoting the performance of community discovery. For convenience, we present in the Notations the important notations used in this paper.


### 3.1. Objective Function of Multiview Learning via Joint-NMF

For the original NMF framework, it just considers the intertype information of 1-mode nodes. Such formulation assumes each subnetwork to be independent and fails to model the heterogeneous networks in a unified way. Recently, some researchers [9, 10] have found that multiview learning on multiple bipartite graphs is well applied to heterogeneous networks for community clustering, because it can promote the performance of the intrinsic structure discovery in multimode networks. As a result, by constructing the bipartite graphs of heterogeneous networks, the optional intertype information of different modes of nodes is incorporated into Joint-NMF. More importantly, we can exploit the mutual information from multidimensional spaces to group like-minded nodes from different graph perspectives, thus strengthening the community detection in heterogeneous networks.For multiview learning, the bipartite graphs of different mode have conditional independence. It means that all the independent learners under different graphs can not make the wrong decision in the same time. Therefore, our semisupervised learning method can effectively integrate bipartite graph information and unlabeled information and adopt cooperative learning between multiview graphs to surmount the obstacle of complexity and diversity in heterogeneous datasets. In this way, our method realizes the information complementation of different information graph, thereby enhancing the overall performance of community discovery in heterogeneous networks.In order to group the relevant target-mode nodes and the corresponding nodes of other mode into the same community, the following objective function is used to measure the accuracy and smoothness of clustering results:(1)min∑i=1MX1i-WiHiTF2+∑j=1MλjHj-H∗F2s.t.Wi,Hi,H∗≥0,where Wi∈Rm×r and Hi∈Rn×r, respectively, denote the basis matrix and coefficient matrix decomposed from graph X1i. m is associated with the node number of mode 1, and n is the node number of model i, and let r be the preset community number. In particular, it is worthwhile to note that mode 1 is regarded as the target node in this paper. The internal connection matrix X11 has also been incorporated for nonnegative matrix factorization.For each single bipartite graphX1i∈Rm×n (Figure 3), according to the principle of NMF, we can minimize the objective function min⁡X1i-Wi(Hi)TF2 to obtain the ith dimensional clustering results of the target nodes. And, for heterogeneous network, it is indispensable to minimize the sum of fitting errors for revealing the community structure of target nodes in the multidimensional/multimode space.Figure 3
The Joint-NMF model for community detection in heterogeneous networks with multiview learning.However, Joint-NMF is also subject to several problems such as slow convergence and large computation. Moreover, heterogeneous networks have more complicated connecting relationships between multiple modes/multiple dimensions, which further limits the application and effectiveness of NMF to explore the hidden community structures. Aiming at these problems, our work mainly optimizes the iterative solutions of NMF from the two aspects:(1)
To simplify the iterative procedure, a matrixQr×r is introduced that satisfies the condition(2)WHT=WQ-1QHT.(2)
Inspired by [14, 15], we incorporate the idea of multiview learning into joint matrix factorization, which can effectively extend semisupervised learning from single graph to multiple graphs, from single mode to multiple-mode nodes. Moreover, our method adds some essential constraints on the matrix factorization, which can ensure the uniqueness and accuracy of the results in network partition.


### 3.2. Optimization Algorithm of Joint-NMF

Assuming mode 1 as the target mode in heterogeneous network, the other modes are all connected with the target mode. To achieve an accuracy network partition with joint nonnegative matrix factorization, it must satisfy the condition(3)DHi,H∗=Hi-H∗F2,0<i≤p,where H∗ denotes the coefficient matrix of the target nodes, which is concluded under the multiview learning of all the modes {X11,X12,…,X1p}. H∗ indicates the final consensus of community partition on the target node and the other nodes.First, we construct the objective function of Joint-NMF, which mainly comprises two terms: the first term is the standard NMF approximation of the objective function, and the second one is a penalty term about the deviation from the consensusH∗. In particular, by means of semisupervised learning in multiple bipartite graphs, it is realized that the collaborative learning between multiple modes or multiple dimensions is applied to community structure mining in heterogeneous networks. In this way, the target nodes can be clustered as consistent as possible, and then we automatically obtain the cluster results of the other nodes with maximum consistency.Applying the regularizations (see (3)) in (1), the objective of our Joint-NMF approach is transformed to minimize(4)min∑i=1MX1i-WiHiTF2+∑j=1MλjHj-H∗F2s.t.Wi,Hi,H∗≥0,where mode 1 is the target nodes and the objective combines the internal connection of mode 1 X11 and all other connecting graphs {X21,…,Xp1} related to mode 1. λj is mainly used to adjust the weight of bipartite graph Xj1, and it also reflects the importance of the corresponding linking mode in networks, 0<λj<1. When λj=0, (4) is transformed into an unsupervised NMF function.In order to optimize the procedure of matrix factorization, we construct a special diagonal matrix(5)Qi=Diag∑j=1MWj,1i,∑i=1MWj,2i,…,∑i=1MWj,ri,where Diag· denotes the diagonal matrix operations. According to (4), the objective function can be transformed into the following minimization problem:(6)O=∑i=1MX1i-WiHiTF2+∑j=1MλjHjQj-H∗F2s.t.∀1≤i≤p+1,Wi,Hi,H∗≥0.Since Joint-NMF (see (4)) is a nonconvex function about factor matrices W, H, it is difficult to obtain the global optimal solution directly. As a result, we propose an alternative iterative update solution, which iterates with the following two steps sequentially to reach the fast convergence.Step 1.
FixingH∗, calculate Wi and Hi to minimize the objective function.Step 2.
FixingWi and Hi, calculate H∗ to minimize the objective function.In this way, the alternative iterative update solution fixes one relevant variable with the latest value, and thus the minimizing objective (see (6)) is transformed into a convex optimization problem about some single variable. By means of alternating iterative update, we would get the local extremum solution or stable solution finally. Thus, our multiplicative update procedure can effectively be applied to multiple matrix factorization and speed up the convergence process.To minimize the objective function, it is necessary to decompose each bipartite graph separately to converge. For one single graphX1i, its specific objective function is regarded as(7)Oi=X1i-WiHiTF2+λiHiQi-H∗F2,W,H≥0;when H∗ is fixed, for any given graph X1i, the results of Wi and Hi do not rely on the calculation of other graphs. Assuming Ψ as the Lagrange multipliers that constrain W≥0, the Lagrangian function of (6) can be simplified as L=O+Tr(ΨWi), and Tr(·) denotes the matrix trace. Accordingly, L can be rewritten as(8)L1=TrWHTHWT-2XHWT+λiR+TrΨW,where R=Tr(HQQTHT-2HQ(H∗)T) includes the regularization term HQ-H∗F2. Introducing the diagonal matrix Q constructed in (5), R can be rewritten as(9)R=∑j=1r∑k=1nHj,k∑i=1MWi,k∑i=1MWi,kHj,k-∑j=1r∑k=1nHj,k∑i=1MWi,kHj,k∗.By setting the derivative ofR with respect to W, we obtain(10)∂R∂Wi,k=2∑i=1MWi,k∑j=1MHj,k2-∑l=1MHl,kHj,k∗.According to Karush-Kuhn-Tucker (KKT) condition in [13], set the derivative of L1 with respect to U:(11)∂L1∂U=-2XV+2UVTV+λiP+Ψ=0Ψi,kUi,k=0,∀1≤i≤M,1≤k≤r.Based on KKT optimization condition, the solutionWi,k is obtained by(12)Wi,k⟵Wi,kXHi,k+λi∑j=1MHj,kHj,k∗WHTHi,k+λi∑l=1MWl,k∑j=1MHj,k2.If the initialization Wi,k>0, it can be concluded that Wi,k will remain nonnegative in the subsequent iteration.FixingH∗ and Wi, use the diagonal matrix Q to normalize the column vector of matrix W, and then we obtain(13)W⟵WQ-1,H⟵HQ,where the normalization process does not change the numerical value of W, H. Assuming Φ as the Lagrange multipliers that constrain H≥0, the Lagrangian function of (8) can be rewritten as(14)L2=TrWHTHWT-2XHWT+λiTrHHT-2HH∗T+TrΦH.Similarly, according to Karush-Kuhn-Tucker (KKT) condition in [13], set the derivative of L2 with respect to H:(15)∂L2∂H=2HWTW-2XTW+2λiH-H∗+Φ=0,Φj,kHj,k=0,∀1≤j≤p+1,1≤k≤r.Hence, the iterative update solution ofHj,k is regarded as(16)Hj,k⟵Hj,kXTWj,k+λiHj,k∗HWTWj,k+λiHj,k.After getting the matricesWi and Hi, according to KTT condition, set the derivative of O with respect to H∗:(17)∂O∂H∗=∂∑i=1pλiHiQi-H∗F2∂H∗=-2λi∑i=1pHi-H∗=0.To minimize the objectiveO, the iterative update solution of Hj,k is regarded as(18)H∗=∑i=1pλiHiQi∑i=1pλi≥0.Repeat the above iteration of matrix factorization, and update the factor matrixesW, H, and H∗ continuously, until the objective function tends to converge or reaches the maximum iteration number.After iterations, we can infer the community membership of multiple nodes based on the Joint-NMF results. For simplicity, the community indices are determined by taking the maximum of each column inH∗ (the target nodes) and Hi (the other mode nodes). Note that once we obtain the consensus matrix H∗, the cluster label of mode i could be computed from Hi. The detailed procedure is illustrated in Algorithm 1.Algorithm 1:Joint-NMF.
Input: Network{X11,X12,…,X1p}, {λ1,λ2,…,λp}, r;
Output: Consensus coefficient matrixH∗
(1) Normalize X1i∈{X11,X12,…,X1p}; //normalize all the
dataset matrices
(2) Initialize Wi, Hi, H∗; //1≤i≤p
(3) % the iterative procedure of Joint-NMF%
(4) repeat
(5)  for each i∈Ndo
(6)    repeat
(7)     Fixing H∗ and Hi, update Wi by Eq. (12);
(8)     Normalize Wi and Hi by Eq. (13);
(9)     Fixing H∗and Wi, update Hi by Eq. (18);
(10)    until Eq. (7) converges.
(11)  end for
(12)  Fixing Wi and Hi, update H∗ by Eq. (18);
(13) until Eq. (6) converges.
(14) returnW,H,H∗.


### 3.3. Algorithm Convergence and Complexity

Here we prove the theoretical convergence of Joint-NMF algorithm.Proposition 1.
Given a bipartite graphX1i∈Rm×n and its initialization factor matrices W∈Rm×k and H∈Rn×k≥0, the objective function (9) decreases monotonically under the alternative iterative update rules (see (12) and (18)).Proof.
The proof of theproposition is similar to the convergence proof of nonnegative matrix triple-factorization in [16]. Moreover, recent studies [17] found the following: despite the alternating iterative update may fail to converge to a stable point, but the improved iterative rules (see (12) and (18)) can guarantee Joint-NMF algorithm can converge to a local extremum point.In our algorithm,W and H are sparse matrices, and the computation of them only involves vector norm enumeration without matrix multiplication, and thus it is more computationally efficient. Moreover, instead of minimizing each matrix factor optimally with time-consuming multiplications of large matrices, Joint-NMF transforms the original heterogeneous networks into some bipartite graphs requiring much fewer matrix multiplications and effectively optimizes the iterative procedure with faster convergence and lower computational complexity.The running time of our algorithm is mainly consumed in the alternative iterative procedure. For single network graphX1i, the complexity of matrix factorization is O(trmn), where t is the iterative number of algorithms and r is the preset community number. As a result, the computational complexity for Joint-NMF method is O(ptrmn).


## 3.1. Objective Function of Multiview Learning via Joint-NMF

For the original NMF framework, it just considers the intertype information of 1-mode nodes. Such formulation assumes each subnetwork to be independent and fails to model the heterogeneous networks in a unified way. Recently, some researchers [9, 10] have found that multiview learning on multiple bipartite graphs is well applied to heterogeneous networks for community clustering, because it can promote the performance of the intrinsic structure discovery in multimode networks. As a result, by constructing the bipartite graphs of heterogeneous networks, the optional intertype information of different modes of nodes is incorporated into Joint-NMF. More importantly, we can exploit the mutual information from multidimensional spaces to group like-minded nodes from different graph perspectives, thus strengthening the community detection in heterogeneous networks.For multiview learning, the bipartite graphs of different mode have conditional independence. It means that all the independent learners under different graphs can not make the wrong decision in the same time. Therefore, our semisupervised learning method can effectively integrate bipartite graph information and unlabeled information and adopt cooperative learning between multiview graphs to surmount the obstacle of complexity and diversity in heterogeneous datasets. In this way, our method realizes the information complementation of different information graph, thereby enhancing the overall performance of community discovery in heterogeneous networks.In order to group the relevant target-mode nodes and the corresponding nodes of other mode into the same community, the following objective function is used to measure the accuracy and smoothness of clustering results:(1)min∑i=1MX1i-WiHiTF2+∑j=1MλjHj-H∗F2s.t.Wi,Hi,H∗≥0,where Wi∈Rm×r and Hi∈Rn×r, respectively, denote the basis matrix and coefficient matrix decomposed from graph X1i. m is associated with the node number of mode 1, and n is the node number of model i, and let r be the preset community number. In particular, it is worthwhile to note that mode 1 is regarded as the target node in this paper. The internal connection matrix X11 has also been incorporated for nonnegative matrix factorization.For each single bipartite graphX1i∈Rm×n (Figure 3), according to the principle of NMF, we can minimize the objective function min⁡X1i-Wi(Hi)TF2 to obtain the ith dimensional clustering results of the target nodes. And, for heterogeneous network, it is indispensable to minimize the sum of fitting errors for revealing the community structure of target nodes in the multidimensional/multimode space.Figure 3
The Joint-NMF model for community detection in heterogeneous networks with multiview learning.However, Joint-NMF is also subject to several problems such as slow convergence and large computation. Moreover, heterogeneous networks have more complicated connecting relationships between multiple modes/multiple dimensions, which further limits the application and effectiveness of NMF to explore the hidden community structures. Aiming at these problems, our work mainly optimizes the iterative solutions of NMF from the two aspects:(1)
To simplify the iterative procedure, a matrixQr×r is introduced that satisfies the condition(2)WHT=WQ-1QHT.(2)
Inspired by [14, 15], we incorporate the idea of multiview learning into joint matrix factorization, which can effectively extend semisupervised learning from single graph to multiple graphs, from single mode to multiple-mode nodes. Moreover, our method adds some essential constraints on the matrix factorization, which can ensure the uniqueness and accuracy of the results in network partition.


## 3.2. Optimization Algorithm of Joint-NMF

Assuming mode 1 as the target mode in heterogeneous network, the other modes are all connected with the target mode. To achieve an accuracy network partition with joint nonnegative matrix factorization, it must satisfy the condition(3)DHi,H∗=Hi-H∗F2,0<i≤p,where H∗ denotes the coefficient matrix of the target nodes, which is concluded under the multiview learning of all the modes {X11,X12,…,X1p}. H∗ indicates the final consensus of community partition on the target node and the other nodes.First, we construct the objective function of Joint-NMF, which mainly comprises two terms: the first term is the standard NMF approximation of the objective function, and the second one is a penalty term about the deviation from the consensusH∗. In particular, by means of semisupervised learning in multiple bipartite graphs, it is realized that the collaborative learning between multiple modes or multiple dimensions is applied to community structure mining in heterogeneous networks. In this way, the target nodes can be clustered as consistent as possible, and then we automatically obtain the cluster results of the other nodes with maximum consistency.Applying the regularizations (see (3)) in (1), the objective of our Joint-NMF approach is transformed to minimize(4)min∑i=1MX1i-WiHiTF2+∑j=1MλjHj-H∗F2s.t.Wi,Hi,H∗≥0,where mode 1 is the target nodes and the objective combines the internal connection of mode 1 X11 and all other connecting graphs {X21,…,Xp1} related to mode 1. λj is mainly used to adjust the weight of bipartite graph Xj1, and it also reflects the importance of the corresponding linking mode in networks, 0<λj<1. When λj=0, (4) is transformed into an unsupervised NMF function.In order to optimize the procedure of matrix factorization, we construct a special diagonal matrix(5)Qi=Diag∑j=1MWj,1i,∑i=1MWj,2i,…,∑i=1MWj,ri,where Diag· denotes the diagonal matrix operations. According to (4), the objective function can be transformed into the following minimization problem:(6)O=∑i=1MX1i-WiHiTF2+∑j=1MλjHjQj-H∗F2s.t.∀1≤i≤p+1,Wi,Hi,H∗≥0.Since Joint-NMF (see (4)) is a nonconvex function about factor matrices W, H, it is difficult to obtain the global optimal solution directly. As a result, we propose an alternative iterative update solution, which iterates with the following two steps sequentially to reach the fast convergence.Step 1.
FixingH∗, calculate Wi and Hi to minimize the objective function.Step 2.
FixingWi and Hi, calculate H∗ to minimize the objective function.In this way, the alternative iterative update solution fixes one relevant variable with the latest value, and thus the minimizing objective (see (6)) is transformed into a convex optimization problem about some single variable. By means of alternating iterative update, we would get the local extremum solution or stable solution finally. Thus, our multiplicative update procedure can effectively be applied to multiple matrix factorization and speed up the convergence process.To minimize the objective function, it is necessary to decompose each bipartite graph separately to converge. For one single graphX1i, its specific objective function is regarded as(7)Oi=X1i-WiHiTF2+λiHiQi-H∗F2,W,H≥0;when H∗ is fixed, for any given graph X1i, the results of Wi and Hi do not rely on the calculation of other graphs. Assuming Ψ as the Lagrange multipliers that constrain W≥0, the Lagrangian function of (6) can be simplified as L=O+Tr(ΨWi), and Tr(·) denotes the matrix trace. Accordingly, L can be rewritten as(8)L1=TrWHTHWT-2XHWT+λiR+TrΨW,where R=Tr(HQQTHT-2HQ(H∗)T) includes the regularization term HQ-H∗F2. Introducing the diagonal matrix Q constructed in (5), R can be rewritten as(9)R=∑j=1r∑k=1nHj,k∑i=1MWi,k∑i=1MWi,kHj,k-∑j=1r∑k=1nHj,k∑i=1MWi,kHj,k∗.By setting the derivative ofR with respect to W, we obtain(10)∂R∂Wi,k=2∑i=1MWi,k∑j=1MHj,k2-∑l=1MHl,kHj,k∗.According to Karush-Kuhn-Tucker (KKT) condition in [13], set the derivative of L1 with respect to U:(11)∂L1∂U=-2XV+2UVTV+λiP+Ψ=0Ψi,kUi,k=0,∀1≤i≤M,1≤k≤r.Based on KKT optimization condition, the solutionWi,k is obtained by(12)Wi,k⟵Wi,kXHi,k+λi∑j=1MHj,kHj,k∗WHTHi,k+λi∑l=1MWl,k∑j=1MHj,k2.If the initialization Wi,k>0, it can be concluded that Wi,k will remain nonnegative in the subsequent iteration.FixingH∗ and Wi, use the diagonal matrix Q to normalize the column vector of matrix W, and then we obtain(13)W⟵WQ-1,H⟵HQ,where the normalization process does not change the numerical value of W, H. Assuming Φ as the Lagrange multipliers that constrain H≥0, the Lagrangian function of (8) can be rewritten as(14)L2=TrWHTHWT-2XHWT+λiTrHHT-2HH∗T+TrΦH.Similarly, according to Karush-Kuhn-Tucker (KKT) condition in [13], set the derivative of L2 with respect to H:(15)∂L2∂H=2HWTW-2XTW+2λiH-H∗+Φ=0,Φj,kHj,k=0,∀1≤j≤p+1,1≤k≤r.Hence, the iterative update solution ofHj,k is regarded as(16)Hj,k⟵Hj,kXTWj,k+λiHj,k∗HWTWj,k+λiHj,k.After getting the matricesWi and Hi, according to KTT condition, set the derivative of O with respect to H∗:(17)∂O∂H∗=∂∑i=1pλiHiQi-H∗F2∂H∗=-2λi∑i=1pHi-H∗=0.To minimize the objectiveO, the iterative update solution of Hj,k is regarded as(18)H∗=∑i=1pλiHiQi∑i=1pλi≥0.Repeat the above iteration of matrix factorization, and update the factor matrixesW, H, and H∗ continuously, until the objective function tends to converge or reaches the maximum iteration number.After iterations, we can infer the community membership of multiple nodes based on the Joint-NMF results. For simplicity, the community indices are determined by taking the maximum of each column inH∗ (the target nodes) and Hi (the other mode nodes). Note that once we obtain the consensus matrix H∗, the cluster label of mode i could be computed from Hi. The detailed procedure is illustrated in Algorithm 1.Algorithm 1:Joint-NMF.
Input: Network{X11,X12,…,X1p}, {λ1,λ2,…,λp}, r;
Output: Consensus coefficient matrixH∗
(1) Normalize X1i∈{X11,X12,…,X1p}; //normalize all the
dataset matrices
(2) Initialize Wi, Hi, H∗; //1≤i≤p
(3) % the iterative procedure of Joint-NMF%
(4) repeat
(5)  for each i∈Ndo
(6)    repeat
(7)     Fixing H∗ and Hi, update Wi by Eq. (12);
(8)     Normalize Wi and Hi by Eq. (13);
(9)     Fixing H∗and Wi, update Hi by Eq. (18);
(10)    until Eq. (7) converges.
(11)  end for
(12)  Fixing Wi and Hi, update H∗ by Eq. (18);
(13) until Eq. (6) converges.
(14) returnW,H,H∗.


## 3.3. Algorithm Convergence and Complexity

Here we prove the theoretical convergence of Joint-NMF algorithm.Proposition 1.
Given a bipartite graphX1i∈Rm×n and its initialization factor matrices W∈Rm×k and H∈Rn×k≥0, the objective function (9) decreases monotonically under the alternative iterative update rules (see (12) and (18)).Proof.
The proof of theproposition is similar to the convergence proof of nonnegative matrix triple-factorization in [16]. Moreover, recent studies [17] found the following: despite the alternating iterative update may fail to converge to a stable point, but the improved iterative rules (see (12) and (18)) can guarantee Joint-NMF algorithm can converge to a local extremum point.In our algorithm,W and H are sparse matrices, and the computation of them only involves vector norm enumeration without matrix multiplication, and thus it is more computationally efficient. Moreover, instead of minimizing each matrix factor optimally with time-consuming multiplications of large matrices, Joint-NMF transforms the original heterogeneous networks into some bipartite graphs requiring much fewer matrix multiplications and effectively optimizes the iterative procedure with faster convergence and lower computational complexity.The running time of our algorithm is mainly consumed in the alternative iterative procedure. For single network graphX1i, the complexity of matrix factorization is O(trmn), where t is the iterative number of algorithms and r is the preset community number. As a result, the computational complexity for Joint-NMF method is O(ptrmn).


## 4. Experimental Results

In this section, the experiments use a series of real networks to validate the algorithms’ performance. Real networks are always more irregular and various than synthetic networks and have more complex community structures. Here we choose 4 popular real heterogeneous networks in different sizes: WebKB [18], Newsgroups [19], Cora [20], and Last.fm [21]. For all the networks, we compare the experimental results with other 4 well-known algorithms of community detection:Kmeans [12], NMF [13], SS-NMF [6], and PMM [22]. All the experiments are performed on an Intel Core2 Duo 2.0 GHz PC with 2 GB RAM, running on Windows 7.In the following tests, different measures are introduced to evaluate the partition quality of the classical algorithms for community detection in heterogeneous networks. Since the structures of real networks are almost unknown, we adopt two standard measures widely used for clustering: normalized mutual information (NMI) [23] and clustering accuracy to quantify the partition quality of the community detection methods. For NMF-based methods, the weight parameters {λ1,λ2,…,λp} are set to 0.1, thus making all the bipartite graphs with the same weight. In addition, we obtain the community numbers r from the method as suggested in [4], which has been shown to well predict the number of network communities. In our experiments, we repeat each method with 50 times on all the networks and compute the average results.The average execution times found by different algorithms are shown in Table1. We can see thatKmeans costs much less time than NMF-based algorithms, as it does not need the matrix factorization iterations. For all the real heterogeneous networks, Joint-NMF effectively accelerates the convergence speed of nonnegative matrix factorization and converges in fewer iterations and CPU seconds than other NMF methods. Because the network scales are quite different, the corresponding performances of Joint-NMF are different, too. For the larger networks, Joint-NMF has a greater competitive advantage than other methods. Our method is only slower thanKmeans and NMF, which, however, has much worse clustering performance.Table 1
The average execution time of the 5 community detection methods on the real networks.
Algorithm
Execution time (seconds)
WebKB
Newsgroups
Cora
Last.fm
Kmeans
6.57 × 103
2.06 × 104
2.15 × 103
8.51 × 105
NMF
1.07 × 104
4.41 × 104
5.36 × 103
1.48 × 106
SS-NMF
1.81 × 104
6.33 × 104
8.61 × 104
2.18 × 106
PMM
2.15 × 104
7.53 × 104
6.13 × 104
2.96 × 106
Joint-NMF
1.51 × 104
4.52 × 104
5.01 × 104
1.68 × 106Tables2 and 3, respectively, show the clustering accuracy and NMI values found by different algorithms. The methods using semisupervised learning, including SS-NMF, PMM, and Joint-NMF, generally achieve better clustering results. Therefore, we can conclude from the experiment results that multiview learning gives full consideration to the multimode/multidimension information, and it is a better choice for mining the community structure in heterogeneous networks.Table 2
Clustering accuracy± standard deviation of the 5 community detection methods on the real networks.
Algorithm
Clustering accuracy (%)
WebKB
Newsgroups
Cora
Last.fm
Kmeans
59.4± 0.05
64.8± 0.07
61.2± 0.01
47.6± 0.05
NMF
67.6± 0.09
81.1± 0.03
63.9± 0.02
54.7± 0.02
SS-NMF
73.8± 0.07
91.3± 0.04
72.7± 0.06
58.6± 0.04
PMM
71.5± 0.06
84.1± 0.08
67.8± 0.03
56.0± 0.08
Joint-NMF
78.1± 0.02
94.9± 0 .01
75.1± 0.09
61.5± 0.01Table 3
NMI± standard deviation of the 5 community detection methods on the real networks.
Algorithm
NMI (%)
WebKB
Newsgroups
Cora
Last.fm
Kmeans
37.5± 0.02
61.2± 0.04
49.1± 0.08
47.6± 0.02
NMF
46.2± 0.01
71.6± 0.08
58.9± 0.05
49.3± 0.03
SS-NMF
49.1± 0.05
78.2± 0.01
62.4± 0.07
52.1± 0.04
PMM
48.8± 0.03
75.4± 0.05
61.2± 0.03
54.9± 0.06
Joint-NMF
55.7± 0.03
80.1± 0.08
65.3± 0.06
57.2± 0.09Joint-NMF method attains the maximum NMI and clustering accuracy in community structure for most test cases, which means that our method has better partition quality, and achieves accuracy community structure on the real heterogeneous networks. More importantly, our method does not suffer from the problems of modularity optimization methods and makes full use of the duality information of multimode nodes, which can greatly enhance the performance of clustering algorithms. Therefore, compared to the other 4 methods, we can conclude that Joint-NMF has competitive clustering performance in terms of both accuracy and partition quality against popular community detection methods.


## 5. Conclusions

In this work, we introduce a multiview learning algorithm of community discovery based on nonnegative matrix factorization. In order to reveal the underlying community structure embedded in heterogeneous networks, we divide the datasets into some relational bipartite graphs and require those graphs learnt from factorizations with multiple views towards a common consensus. To achieve this, we introduce multiview learning in the heterogeneous data mining with matrix factorization and finally make all the learners reach a consensus about network partition. Moreover, we design an optimal iterative procedure to ensure the matrix factorization is simple and meaningful in terms of clustering. Through multiview learning, we are able to discover the hidden global structure in the heterogeneous networks, which seamlessly integrates multiple data types to provide us with a better picture of the underlying community distribution, highly valuable in most real-world applications.Different form the traditional methods, our work is an instructive attempt to discover the multimode or multidimensional structure in heterogeneous networks. Actually, our Joint-NMF framework jointly takes intertype and intratype information of target nodes into considerations, thus makes the partitioning results more reasonable and effective, and detects communities with high accuracy and quality. Experimental results on four real-world datasets show that our algorithm is a competitive method to explore community structures in heterogeneous networks.



---

*Source: 8596893-2017-05-07.xml*