# A Tensor CP Decomposition Method for Clustering Heterogeneous Information Networks via Stochastic Gradient Descent Algorithms

Authors: Jibing Wu; Zhifei Wang; Yahui Wu; Lihua Liu; Su Deng; Hongbin Huang
Journal: Scientific Programming
 (2017)

---

## Abstract

Clustering analysis is a basic and essential method for mining heterogeneous information networks, which consist of multiple types of objects and rich semantic relations among different object types. Heterogeneous information networks are ubiquitous in the real-world applications, such as bibliographic networks and social media networks. Unfortunately, most existing approaches, such as spectral clustering, are designed to analyze homogeneous information networks, which are composed of only one type of objects and links. Some recent studies focused on heterogeneous information networks and yielded some research fruits, such as RankClus and NetClus. However, they often assumed that the heterogeneous information networks usually follow some simple schemas, such as bityped network schema or star network schema. To overcome the above limitations, we model the heterogeneous information network as a tensor without the restriction of network schema. Then, a tensor CP decomposition method is adapted to formulate the clustering problem in heterogeneous information networks. Further, we develop two stochastic gradient descent algorithms, namely, SGDClus and SOSClus, which lead to effective clustering multityped objects simultaneously. The experimental results on both synthetic datasets and real-world dataset have demonstrated that our proposed clustering framework can model heterogeneous information networks efficiently and outperform state-of-the-art clustering methods.


---

## Body

## 1. Introduction

Heterogeneous information networks are ubiquitous in the real-world applications. Generally, heterogeneous information networks consist of multiple types of objects and rich semantic relations among different object types. The bibliographic network extracted from the DBLP database (http://www.informatik.uni-trier.de/~ley/db/) is a typical heterogeneous information network, as shown in Figure 1. The DBLP database is an open resource that contains most bibliographic information on computer science. The bibliographic network contains four types of objects: author (A), paper (P), venue (i.e., conference or journal) (V), and term (T). The edges are labeled by “write” or “written by” between author and paper or labeled by “publish” or “published by” between paper and venue or labeled by “contain” or “contained in” between paper and term.Figure 1
An example of heterogeneous information network: a bibliographic network extracted from the DBLP database.Clustering analysis is a basic and essential method for mining such networks, which can help us better understand the semantic information and interpretable structure in the network. Unfortunately, most existing approaches, such as spectral clustering, are designed to analyzehomogeneous information networks[1] that consist of only a single type of objects and links, while the real-world situations are oftenheterogeneous information networks [2] in nature with more than one type of objects and links. The mission of clustering such a heterogeneous information network is more difficult than that in a homogeneous information network, as we cannot directly measure the similarity among the different types of objects and relations.Though some recent studies have focused on clustering heterogeneous information networks, such as RankClus [1] and NetClus [2], they can only be applied to some specific simple network schemas. RankClus can only be used to model bityped networks, where only two different types of objects exist in the network. NetClus was developed for the star network schema, where the links only appear between target objects and attribute objects. The network schema is a metatemplate of a heterogeneous information network, which shows how many types of objects and links are there in the network [3]. Figure 1 shows a typical star network schema, where the paper (P) is the target object and others are attribute objects.A tensor is a generalization of the matrix in the high-dimensional space. It is a natural expression of complicated and interpretable structures in high-mode data. In this paper, we model a heterogeneous information network as a tensor without the restriction of network schema. Each type of objects maps onto one mode of the tensor, and the semantic relations among different object types map onto the elements in the tensor. Then, a tensor CP decomposition method is adapted to formulate the clustering problem in heterogeneous information networks. And two stochastic gradient descent algorithms are developed, which lead to effective clustering multityped objects simultaneously. The experimental results on both synthetic datasets and real-world dataset show that the proposed clustering framework can model the heterogeneous information networks efficiently and outperform the state-of-the-art clustering methods.The rest of this paper is organized as follows. In Section2, we discuss the related work on clustering for heterogeneous information networks and the tensor factorization. Section 3 gives some notations and definitions used in this paper. In Section 4, we formulate the clustering problem and describe two stochastic gradient descent algorithms. The experimental results on both synthetic datasets and real-world dataset are presented in Section 5. Finally, the conclusions are drawn in Section 6.


## 2. Related Work

Our work mainly focuses on the clustering heterogeneous information networks and the tensor factorization.


### 2.1. Clustering Heterogeneous Information Networks

Clustering is an unsupervised learning method to recognize the distribution and hidden structures in the data, which is a basic and significant mission for pattern recognition and machine learning. Since MacQueen first proposedK-means [4] in 1967, many subtle algorithms have been developed for clustering in the past decades. However, most existing algorithms, such as hierarchical clustering algorithm [5], density-based clustering [6], mesh-based clustering [7], fuzzy clustering algorithm [8], and spectral clustering [9], are designed to analyze point sets or homogeneous information networks, which are composed of only one type of objects and links.In real-world applications, the datasets are often organized as heterogeneous information networks, where objects and the relations between them are of more than one type. In recent years, researchers have made a significant progress on clustering for heterogeneous information networks [10, 11], which largely focused on four main directions: the first is to use a ranking based clustering algorithm [1]; it developed the RankClus algorithm that integrated clustering with ranking for clustering bityped networks. Its extension, NetClus [2], was developed for the star network schema. They have proven that ranking and clustering can mutually enhance each other. GPNRankClus [12] assumed that edges in heterogeneous information networks follow a Poisson distribution. This method can simultaneously achieve both clustering and ranking in a heterogeneous information network. In addition, FctClus [13] achieved a higher computational speed and had a greater clustering accuracy when applied to heterogeneous information networks. But, same as NetClus, FctClus algorithm can only handle the star network schema. For a general network schema, HeProjI [14] projected the network into a number of bityped or star schema subnetworks and performed the ranking based clustering in each subnetwork.The second direction involves metapath based clustering algorithms [15, 16]. A metapath is a connected path defined on the network schema of a heterogeneous information network, which represents a composite semantic relation between two objects. PathSim (metapath based top-k similarity search) [3] measured the similarity between the same types of objects based on metapath in heterogeneous information networks. However, it has a limitation: the metapath must be symmetric; that is, PathSim could not work on different types of objects. The PathSelClus algorithm in [15–17] integrated metapath selection with user guidance to cluster objects in networks, where user provided seeds for each cluster acted as guidance.The third direction is structural-based clustering. Sun et al. proposed a probabilistic clustering method [18] to deal with heterogeneous information networks with incomplete attributes, which integrated the incomplete attribute information and the network structure information. NetSim [19] is a structural-based similarity measurement between objects for x-star network. Xu proposed a Bayesian probabilistic model based on network structural information for clustering heterogeneous information networks.The final direction is a clustering algorithm based on social network features. Zhou and Liu designed the SI-Cluster algorithm [20], which adopted the heat diffusion procedure to model the social influence and then measure the similarity between objects.


### 2.2. Tensor Factorization

A tensor is a multidimensional array, in which the elements are addressed by more than two indices. Tensor factorization has been studied since the early 20th century [21–25]. Two of the most popular tensor factorization methods are Tucker decomposition [21, 24] and canonical decomposition using parallel factors (CANDECOMP/PARAFAC) [23, 24]. The CANDECOMP/PARAFAC is also named CP decomposition. It is worth noting that CP decomposition is a special case of Tucker decomposition.The clustering issues based on tensor factorization are often modeled as the optimization problems [26]. But it has been proven in [27] that tensor clustering formulations are NP-hard. In the past years, many approximation algorithms for tensor clustering are proposed [28–30]. These theories provide a new perspective for us as to clustering heterogeneous information networks. Tensor factorization based clustering has also been used in some specific applications. Examples include link prediction in higher-order network structures [31, 32], collaborative filtering in recommendation systems [33], community detection in multigraphs [34], graph clustering [35], and modeling multisource datasets [36].The Alternating Least Squares (ALS) algorithm [22, 37, 38] is one of the most famous and commonly used algorithms to solve the tensor factorization, which updates one component iteratively at each round, while holding the others constant. However, ALS suffers from some limitations; for example, ALS may converge to a local minimum and the memory consumption may explode when the scale of tensor is large. Nonlinear optimization approach is another option to obtain the tensor factorization, such as nonlinear conjugate gradient method [39], Newton based optimization [40], randomized block sampling method [41], and stochastic gradient descent [42]. In this paper, we adopt a stochastic gradient descent algorithm with Tikhonov regularization item loss function to process the tensor CP decomposition based clustering.


## 2.1. Clustering Heterogeneous Information Networks

Clustering is an unsupervised learning method to recognize the distribution and hidden structures in the data, which is a basic and significant mission for pattern recognition and machine learning. Since MacQueen first proposedK-means [4] in 1967, many subtle algorithms have been developed for clustering in the past decades. However, most existing algorithms, such as hierarchical clustering algorithm [5], density-based clustering [6], mesh-based clustering [7], fuzzy clustering algorithm [8], and spectral clustering [9], are designed to analyze point sets or homogeneous information networks, which are composed of only one type of objects and links.In real-world applications, the datasets are often organized as heterogeneous information networks, where objects and the relations between them are of more than one type. In recent years, researchers have made a significant progress on clustering for heterogeneous information networks [10, 11], which largely focused on four main directions: the first is to use a ranking based clustering algorithm [1]; it developed the RankClus algorithm that integrated clustering with ranking for clustering bityped networks. Its extension, NetClus [2], was developed for the star network schema. They have proven that ranking and clustering can mutually enhance each other. GPNRankClus [12] assumed that edges in heterogeneous information networks follow a Poisson distribution. This method can simultaneously achieve both clustering and ranking in a heterogeneous information network. In addition, FctClus [13] achieved a higher computational speed and had a greater clustering accuracy when applied to heterogeneous information networks. But, same as NetClus, FctClus algorithm can only handle the star network schema. For a general network schema, HeProjI [14] projected the network into a number of bityped or star schema subnetworks and performed the ranking based clustering in each subnetwork.The second direction involves metapath based clustering algorithms [15, 16]. A metapath is a connected path defined on the network schema of a heterogeneous information network, which represents a composite semantic relation between two objects. PathSim (metapath based top-k similarity search) [3] measured the similarity between the same types of objects based on metapath in heterogeneous information networks. However, it has a limitation: the metapath must be symmetric; that is, PathSim could not work on different types of objects. The PathSelClus algorithm in [15–17] integrated metapath selection with user guidance to cluster objects in networks, where user provided seeds for each cluster acted as guidance.The third direction is structural-based clustering. Sun et al. proposed a probabilistic clustering method [18] to deal with heterogeneous information networks with incomplete attributes, which integrated the incomplete attribute information and the network structure information. NetSim [19] is a structural-based similarity measurement between objects for x-star network. Xu proposed a Bayesian probabilistic model based on network structural information for clustering heterogeneous information networks.The final direction is a clustering algorithm based on social network features. Zhou and Liu designed the SI-Cluster algorithm [20], which adopted the heat diffusion procedure to model the social influence and then measure the similarity between objects.


## 2.2. Tensor Factorization

A tensor is a multidimensional array, in which the elements are addressed by more than two indices. Tensor factorization has been studied since the early 20th century [21–25]. Two of the most popular tensor factorization methods are Tucker decomposition [21, 24] and canonical decomposition using parallel factors (CANDECOMP/PARAFAC) [23, 24]. The CANDECOMP/PARAFAC is also named CP decomposition. It is worth noting that CP decomposition is a special case of Tucker decomposition.The clustering issues based on tensor factorization are often modeled as the optimization problems [26]. But it has been proven in [27] that tensor clustering formulations are NP-hard. In the past years, many approximation algorithms for tensor clustering are proposed [28–30]. These theories provide a new perspective for us as to clustering heterogeneous information networks. Tensor factorization based clustering has also been used in some specific applications. Examples include link prediction in higher-order network structures [31, 32], collaborative filtering in recommendation systems [33], community detection in multigraphs [34], graph clustering [35], and modeling multisource datasets [36].The Alternating Least Squares (ALS) algorithm [22, 37, 38] is one of the most famous and commonly used algorithms to solve the tensor factorization, which updates one component iteratively at each round, while holding the others constant. However, ALS suffers from some limitations; for example, ALS may converge to a local minimum and the memory consumption may explode when the scale of tensor is large. Nonlinear optimization approach is another option to obtain the tensor factorization, such as nonlinear conjugate gradient method [39], Newton based optimization [40], randomized block sampling method [41], and stochastic gradient descent [42]. In this paper, we adopt a stochastic gradient descent algorithm with Tikhonov regularization item loss function to process the tensor CP decomposition based clustering.


## 3. Preliminaries

First, we introduce some related concepts and notations of tensors used in this paper. More details about tensor algebra can be found in [24, 43]. The order of a tensor is the number of dimensions, also known as ways or modes. We will follow the convention used in [23] to denote scalars by lowercase letters, for example, a,b,c, vectors (one mode) by boldface lowercase letters, for example, a,b,c, matrices (two modes) by boldface capital letters, for example, A,B,C, and tensors (three modes or more) by boldface calligraphic letters, for example, X,Y,Z. Elements of a matrix or a tensor are denoted by lowercase letters with subscripts; that is, the (i1,i2,…,iN)th element of an Nth-order tensor X is denoted by xi1,i2,…,iN. The notations about tensor algebra used in this paper are summarized in Notations.If anNth-order tensor X∈RI1×I2×⋯×IN can be written as the outer product of N vectors, that is, X=a(1)∘a2∘⋯∘a(N) and a(n)∈RIn;n=1,2,…,N, tensor X is named rank-one tensor. The CP decomposition represents a tensor as a sum of R rank-one tensors; that is, the CP decomposition of X is X=∑r=1R‍ar(1)∘ar(2)∘⋯∘ar(N), where R is a positive integer and ar(n)∈RIn;r=1,2,…,R;n=1,2,…,N. The rank of a tensor is defined as the smallest number of rank-one tensors for which the equality holds in the CP decomposition and denoted as rank(X)=minR. In fact, the problem of tensor rank determination is NP-hard [27].Let factor matricesA(n)=a1(n),a2(n),…,aR(n)∈RIn×R, for n=1,2,…,N. We denote A(1),A(2),…,A(N)≡∑r=1R‍ar(1)∘ar(2)∘⋯∘ar(N). By minimizing the Frobenius norm of the difference between X and its CP approximation, the CP decomposition can be formulated as an optimization problem: (1)min12X-A1,A2,…,ANF2.Then, we give the definitions for the information network and the network schema, which are based on the work by Sun et al. [3].Definition 1 (information network [3]).
Aninformation network is a graph G=(V,E) defined on a set of objects V and a set of links E, where V belongs to T objects types V=Vtt=1T and E belongs to L links types E=Rll=1L.
Specifically, whenT>1 or L>1, the information network is calledheterogeneous information network; otherwise, it is calledhomogeneous information network.
We denote the object set of typeVt as {vnt}n=1Nt, where Nt is the number of objects in type Vt; that is, Nt=|Vt| and t=1,2,…,T. The total number of objects in the network is given by N=∑t=1T‍Nt.Definition 2 (network schema [3]).
Thenetwork schemais a metatemplate for a heterogeneous information network G=(V,E), which is a graph defined over object types V and links types E, denoted by SG={V,E}.
A network schemaSG={V,E} shows how many types of objects are there in the network G=(V,E) and which type the links between different object types belong to. Figure 1 shows the network schema of DBLP, which follows a star network schema.


## 4. Tensor CP Decomposition Based Clustering Framework

### 4.1. Tensor Construction

According to Definition2, we know that the network schema SG={V,E} is a metatemplate for the given heterogeneous information network G=(V,E). In other words, G=(V,E) is an instance of SG={V,E}. So we can find at least one subnetwork of G=(V,E), which follows the schema SG={V,E}.Definition 3 (gene-network).
A gene-network, denoted byG′=(V′,E′), is the minimum subnetwork of G=(V,E), which follows the schema SG={V,E}.
It is easy to see that a gene-network is one of the smallest instances ofSG={V,E} in the set of subnetworks of G=(V,E). For example, a gene-network in DBLP network (in Figure 1, which contains four types of objects, A,P,V,T), denoted by G′=viA,vjP,vmV,vnT,〈viA,vjP〉,〈vjP,vmV〉〈vjP,vnT〉, represents a semantic relation of“an AuthorviAwrites a PapervjPpublished in the VenuevmVand containing the TermvnT.” For simplicity, we can use the subscript of each object in G′ to mark the corresponding gene-network. In the example, the gene-network G′ can be marked by Gi,j,m,n′.
LetX be a Tth-order tensor of size N1×N2×⋯×NT; each mode of X represents one type of objects in the network G. An arbitrary element, xn1n2⋯nT∈{0,1}, for nt=1,2,…,Nt, is an indicator of whether the corresponding gene-network Gn1,n2,…,nT′ exists; that is,(2)xn1n2⋯nT=1if∃Gn1,n2,…,nT′;0otherwise.
Then, the heterogeneous information networkG=(V,E) can be represented by the form of tensor as X.


### 4.2. Problem Formulation

Using the tensor representationX of G=(V,E), we can partition the multityped objects into different clusters by the CP decomposition. We assume that there are K clusters in G=(V,E) and denote U(t)∈RNt×K;t=1,2,…,T as the cluster indication matrix of the tth type of objects. Then, the CP decomposition of X is(3)minX-U1,U2,…,UTF2.Each row uk(t)=uk,1(t),uk,2(t),…,uk,Nt(t)⊤ of the factor matrix U(t) is the probability vector for each object from tth type belonging to the kth cluster. In other words, the kth cluster is composed of the kth rank-one tensor in the CP decomposition; that is, uk(1)∘uk(2)∘⋯∘uk(T).Figure2 gives an example of tensor CP decomposition method for clustering heterogeneous information network. The left one is the original network with three types of objects, the middle cube is a 3-mode tensor, and the right one is the CP decomposition of the 3-mode tensor and also is the partition of the original network. In addition, the three types of objects are the yellow round, the blue square, and the red triangle, respectively. The number within each object is the identifier of the object. Each element (black dot in the middle cube) in the tensor represents a gene-network in the network (black dashed circle in the left). Each component (black dashed circle in the right) in the CP decomposition shows one cluster of the original network.Figure 2
An illustration of tensor CP decomposition method for clustering heterogeneous information network.The problem in (3) is an NP-hard nonconvex optimization problem, which has a continuous manifold of equivalent solutions [39]. In other words, the global minimum is drowned in many local minima, which makes it difficult to be found. In real-world scenarios, the objects in the heterogeneous information networks may belong to more than one cluster; that is, the clusters are overlapping. However, the number of clusters that the vast majority of objects may belong to is much smaller than the total number of clusters. That is, most of the elements in U(t) should be zero; that is, U(t) should be sparse. To overcome the two challenges, we can introduce a Tikhonov regularization term, proposed by Paatero in [44, 45], in the objective function and replace the objective function by the following loss function:(4)LX,U1,U2,…,UT=12X-U1,U2,…,UTF2+λ2∑t=1TUtF2,where λ>0 is a regularization parameter. Let(5)fX,U1,U2,…,UT=12X-U1,U2,…,UTF2be the first squared loss function component in L and let(6)gU1,U2,…,UT=λ2∑t=1TUtF2be the Tikhonov regularization term in L, respectively. Then (7)L=f+g.The Tikhonov regularization termg in the loss function L has an encouraging property, which makes the Frobenius norms of all factor matrices in the optimization be equal; that is,(8)U1F=U2F=⋯=UTF.Therefore, the local minima of loss function L become isolated, and any replacement and scaling of the satisfactory solutions will escape from the optimization. The details of proof can be found in [39]. Meanwhile, the Tikhonov regularization term can ensure the sparsity of the factor matrices by penalizing the number of nonzero elements.Therefore, the tensor CP decomposition method for clustering heterogeneous information networks can be formalized as(9)minU1,U2,…,UTLX,U1,U2,…,UTs.t.∑k=1Kun,kt=1,∀t,∀n,un,kt∈0,1,∀t,∀n,∀k,∑n=1Ntun,kt>0,∀t,∀k,where n=1,2,…,Nt; t=1,2,…,T; k=1,2,…,K, and K<minN1,N2,…,NT is the total number of clusters. In (9), we divide X into K clusters and obtain the structure of each cluster, which includes the distribution of each object. The first constraint in (9) guarantees that the sum of probabilities for each object belonging to all clusters is 1. The second constraint in (9) represents that each probability should be in the range of [0,1]. The last constraint in (9) makes sure that there is no empty cluster for any mode.


### 4.3. The Stochastic Gradient Descent Algorithms

Stochastic gradient descent is a mature and widely used tool for optimizing various models in machine learning, such as artificial neural networks, support vector machines, and logistic regression. In this section, the regularized clustering problem in (9) will be addressed by the stochastic gradient descent algorithms. The details of tensor algebra and properties used in this section can be found in [43].First, we review the stochastic gradient descent algorithm. To solve an optimization problem,minxQ(x), where Q(x) is a differentiable object function to be minimized and x is a variable, the stochastic gradient descent method to update x can be described as(10)x⟵x-η∇Qx,where η is a positive number, named learning rate or step size. The convergence speed of stochastic gradient descent algorithm depends on the choice of learning rate η and initial solution.Though the stochastic gradient descent algorithm may converge to a local minimum at a linear speed, the efficiency of the algorithm near the optimal point is not all roses [46]. To speed up the final optimization phase, an extension method named second-order stochastic algorithm is designed in [46], which replaces the learning rate η by the inverse of second-order derivative of the object function; that is,(11)x⟵x-η∇2Qx-1∇Qx.Now, we apply the stochastic gradient descent and the second-order stochastic algorithm to the clustering problem in (9) and propose two algorithms, named SGDClus (StochasticGradientDescent forClustering) and SOSClus (Second-OrderStochastic forClustering), respectively.


#### 4.3.1. SGDClus

In SGDClus, we apply the stochastic gradient descent algorithm to the clustering problem in (9). According to (10), each factor matrix U(t), for t=1,2,…,T, is updated by the rule(12)Ut⟵Ut-η∂L∂Ut=Ut-η∂f∂Ut+∂g∂Ut.Actually,∂g/∂U(t) is easy to be obtained according to (6); that is,(13)∂g∂Ut=λUt.To compute ∂f/∂U(t), fX,U(1),U(2),…,U(T) can be rewritten by matricization of X along the tth mode as (14)ft=12Xt-Ut⊙/tU⊤F2, where ⊙(/t)U=U(T)⊙⋯⊙U(t+1)⊙U(t-1)⊙⋯⊙U(1). Then, we have(15)∂ft∂Ut=∂TrXt-Ut⊙/tU⊤Xt-Ut⊙/tU⊤⊤2∂Ut=∂TrXtXt⊤2∂Ut-∂Tr2Xt⊙/tUUt⊤2∂Ut+∂TrUt⊙/tU⊤Ut⊙/tU⊤⊤2∂Ut=-Xt⊙/tU+Ut⊙/tU⊤⊙/tU.Another way to compute ∂f(t)/∂U(t) is given in [39], which has the same result as (15). Following the works in [39], we denote(16)Γt=⊙/tU⊤⊙/tU=U1⊤U1∗⋯∗Ut-1⊤Ut-1∗Ut+1⊤Ut+1∗⋯∗UT⊤UT.Therefore, the partial derivative of L is given by(17)∂L∂Ut=-Xt⊙/tU+UtΓt+λUt.And (12) can be rewritten as(18)Ut⟵Ut-η∂L∂Ut=UtI-ηΓt+λI+ηXt⊙/tU,where I is an identity matrix. Note that {U(t)}t=1T derived by (18) do not satisfy the first and second constraints in (9). To satisfy these two constraints, we can normalize each row of {U(t)}t=1T by(19)un,kt⟵un,kt∑k=1Kun,kt.Furthermore, the pseudocode of SGDClus is given in Algorithm1.Algorithm 1:The SGDClus algorithm.
Input:    X, K, λ.
Output:    {U(t)}t=1T.
(1)  Initialize {U(t)}t=1T;
(2)  Set iter←1;
(3)   repeat
(4)  for  t←1  to  T  do
(5)     Set η;
(6)     Update U(t) according to (18);
(7)     Normalize U(t) according to (19);
(8)   end for
(9)    Set iter←iter+1;
(10)   until   LX,U(1),U(2),…,U(T) unchanged or iter
reaches the maximum iterations


#### 4.3.2. SOSClus

In SOSClus, we apply the second-order stochastic algorithm to the clustering problem in (9). According to (11), each factor matrix U(t), for t=1,2,…,T, is updated by the rule(20)Ut⟵Ut-η∂2L∂2Ut-1∂L∂Ut.According to (17), we can obtain the second-order partial derivative of L with respect to U(t); that is,(21)∂2L∂2Ut=Γt+λI.By substituting (17) and (21) into (20), we have(22)Ut⟵1-ηUt+ηXt⊙/tUΓt+λI-1.Note thatX(t)⊙(/t)UΓ(t)+λI-1 is the General Gradient-based Optimization (OPT) [39] solution for updating U(t) in the regularized CP decomposition by making (17) equal to zero. See the details of proof in [39]. Let(23)Uoptt=Xt⊙/tUΓt+λI-1.Therefore, the updating rule of U(t) in SOSClus is a weighted average of the current solution and the OPT solution intuitively; that is,(24)Ut⟵1-ηUt+ηUoptt.Actually, SOSClus is a general extension of General Gradient-based Optimization (OPT) [39] and the ALS with step size restriction in randomized block sampling method [41]. In (24), when the learning rate η=1, we get the OPT solution. When the regularization parameter λ=0, SOSClus becomes the ALS with step size restriction in randomized block sampling method.Similar to SGDClus,{U(t)}t=1T derived by (24) in SOSClus also do not satisfy the first and second constraints in (9). We should normalize each row of {U(t)}t=1T according to (19). The pseudocode of SOSClus is given in Algorithm 2.Algorithm 2:The SOSClus algorithm.
Input:  X, K, λ.
Output:  {U(t)}t=1T.
(1)  Initialize {U(t)}t=1T;
(2)  Set iter←1;
(3)repeat
(4)   for   t←1   to   T   do
(5)    Set η;
(6)    Compute Uopt(t) according to (23)
(7)    Update U(t) according to (24);
(8)    Normalize U(t) according to (19);
(9)   end for
(10)     Set iter←iter+1;
(11)until   LX,U(1),U(2),…,U(T) unchanged or iter
reaches the maximum iterations


### 4.4. Feasibility Analysis

Theorem 4.
The CP decomposition ofX obtains the clustering of multityped objects in the heterogeneous information network G=(V,E) simultaneously.Proof.
Since the proofs for different types of objects in the heterogeneous information networkG=(V,E) are similar, we will simply describe the process for a single type of objects. Without loss of generality, we detail the proof on the tth type of objects.
Given a heterogeneous information networkG=(V,E) and its tensor representation X, the nonzero elements in X represent the input gene-networks in G=(V,E), which we want to partition into K clusters C1,C2,…,CK. The centre of the cluster Ck is denoted by ck. By using the coordinate format [47] as the sparse representation of X, the gene-networks can be denoted as a matrix M∈Rnnz(X)×T, where nnz(X) is the number of nonzero elements in X. Each row mn∈M,n=1,2,…,nnz(X) gives the subscripts of corresponding nonzero element in X. In other words, mn represents a gene-network and the entries mn,t∈mn,t=1,2,…,T are the subscripts of the objects contained in the gene-network.
The traditional clustering approach, such asK-means, minimizes the sum of differences between individual gene-network in each cluster and the corresponding cluster centres; that is,(25)minpn,k,ck∑n=1nnzXmn-∑k=1Kpn,kckF2,where pn,k is the probability of gene-network mn belonging to the kth cluster. Also we can rewrite the problem by a new perspective of clustering individual object in the gene-network as follows: (26)minpnt,k,ck,t∑n=1nnzX∑t=1Tmn,t-∑k=1Kpnt,kck,tF2,where pnt,k is the probability of object vnt belonging to the kth cluster.
In the matrix form,K-means can be formalized as (27)minP,CM-PCF2,where P is the cluster indication matrix and C is the cluster centres.
By matricization ofX along the tth mode, the CP decomposition of X in (3) can be rewritten as (28)minU1,U2,…,UTXt-Ut⊙/tU⊤F2X(t) is the matricization of X along the tth mode and M is the sparse representation of X. Let U(t)=P and let ⊙(/t)U⊤=C. That is, U(t) is the cluster indication matrix for the tth type of objects and ⊙(/t)U⊤ is the cluster centres. So, the CP decomposition in (3) is equivalent to theK-means clustering for the tth type of objects in heterogeneous information network G=(V,E).
By matricization ofX in (3) along different modes, we can prove that the CP decomposition is equivalent to theK-means clustering for other types of objects. So, the CP decomposition of X obtains the clustering of multityped objects in the heterogeneous information network G=(V,E) simultaneously.It is worth noting that the CP decomposition based clustering is a soft clustering method; the factor matrices indicate the probability of objects belonging to corresponding clusters. The soft clustering is more in line with reality, because many objects in the heterogeneous information networks may belong to several clusters. In other words, the clusters are overlapping. In some cases, the overlapping clusters need to be translated into nonoverlapping clusters, which can be achieved by using different approaches, such asK-means, to cluster the rows of factor matrices. Usually, the nonoverlapping clusters can be obtained by simply assigning each object to the cluster which has the largest entry in the corresponding row of factor matrix.


### 4.5. Time Complexity Analysis

The main time consumption of updating each factor matrixU(t) in SGDClus is computing ∂L/∂U(t). According to (17), we need to calculate X(t)⊙(/t)U and U(t)Γ(t), respectively. Since U(t)∈RNt×K and X(t)∈RNt×∏i=1i≠tT‍Ni, we have X(t)⊙(/t)U∈RNt×K, Γ(t)∈RK×K, and U(t)Γ(t)∈RNt×K.Firstly, if we successively calculate the Khatri-Rao product ofT-1 matrices and a matrix-matrix multiplication when computing X(t)⊙(/t)U, the intermediate results will be of very large size and the computational cost will be very expensive. In practice, we can reduce the complexity by ignoring the unnecessary calculation. Let us observe the element of X(t)⊙(/t)U; that is,(29)Xt⊙/tUnt,k=∑nii=1i≠tTxnt,∏i=1i≠tTni∏i=1i≠tTuni,ki;xnt,∏i=1i≠tTni is an element in the matricization of X, which represents a corresponding gene-network in the heterogeneous information network. When xnt,∏i=1i≠tTni=0, we can ignore the following Khatri-Rao product. Hence, only nonzero elements in X need to be computed. Therefore, the time complexity for computing X(t)⊙(/t)U is Onnz(X)NtK.Secondly, the element ofU(t)Γ(t) is given by(30)UtΓtnt,k=∑j=1Kunt,jt∏i=1i≠tT∑ni=1Niuni,jiuni,ki.So, the time complexity of computing U(t)Γ(t) is O(N-Nt)K2, where N=∑t=1T‍Nt is the total number of objects in the networks.Above all, the time complexity of each iteration in SGDClus isOnnz(X)NK+(T-1)NK2. Note that, in the real-world heterogeneous information networks, the number of clusters K and the number of object types T are usually far less than N; that is, K≪N and T≪N.According to (22), the time complexity of updating each factor matrix U(t) in SOSClus is composed of three components: X(t)⊙(/t)U, Γ(t)+λI-1, and the product of them. Compared to SGDClus, only the time consumption of computing an inverse matrix for Γ(t)+λI is additional in SOSClus. Since Γ(t)+λI is a K×K square matrix, computing the inverse of such matrix costs O(K3). Nevertheless, O(K3) is usually negligible because K≪N.


## 4.1. Tensor Construction

According to Definition2, we know that the network schema SG={V,E} is a metatemplate for the given heterogeneous information network G=(V,E). In other words, G=(V,E) is an instance of SG={V,E}. So we can find at least one subnetwork of G=(V,E), which follows the schema SG={V,E}.Definition 3 (gene-network).
A gene-network, denoted byG′=(V′,E′), is the minimum subnetwork of G=(V,E), which follows the schema SG={V,E}.
It is easy to see that a gene-network is one of the smallest instances ofSG={V,E} in the set of subnetworks of G=(V,E). For example, a gene-network in DBLP network (in Figure 1, which contains four types of objects, A,P,V,T), denoted by G′=viA,vjP,vmV,vnT,〈viA,vjP〉,〈vjP,vmV〉〈vjP,vnT〉, represents a semantic relation of“an AuthorviAwrites a PapervjPpublished in the VenuevmVand containing the TermvnT.” For simplicity, we can use the subscript of each object in G′ to mark the corresponding gene-network. In the example, the gene-network G′ can be marked by Gi,j,m,n′.
LetX be a Tth-order tensor of size N1×N2×⋯×NT; each mode of X represents one type of objects in the network G. An arbitrary element, xn1n2⋯nT∈{0,1}, for nt=1,2,…,Nt, is an indicator of whether the corresponding gene-network Gn1,n2,…,nT′ exists; that is,(2)xn1n2⋯nT=1if∃Gn1,n2,…,nT′;0otherwise.
Then, the heterogeneous information networkG=(V,E) can be represented by the form of tensor as X.


## 4.2. Problem Formulation

Using the tensor representationX of G=(V,E), we can partition the multityped objects into different clusters by the CP decomposition. We assume that there are K clusters in G=(V,E) and denote U(t)∈RNt×K;t=1,2,…,T as the cluster indication matrix of the tth type of objects. Then, the CP decomposition of X is(3)minX-U1,U2,…,UTF2.Each row uk(t)=uk,1(t),uk,2(t),…,uk,Nt(t)⊤ of the factor matrix U(t) is the probability vector for each object from tth type belonging to the kth cluster. In other words, the kth cluster is composed of the kth rank-one tensor in the CP decomposition; that is, uk(1)∘uk(2)∘⋯∘uk(T).Figure2 gives an example of tensor CP decomposition method for clustering heterogeneous information network. The left one is the original network with three types of objects, the middle cube is a 3-mode tensor, and the right one is the CP decomposition of the 3-mode tensor and also is the partition of the original network. In addition, the three types of objects are the yellow round, the blue square, and the red triangle, respectively. The number within each object is the identifier of the object. Each element (black dot in the middle cube) in the tensor represents a gene-network in the network (black dashed circle in the left). Each component (black dashed circle in the right) in the CP decomposition shows one cluster of the original network.Figure 2
An illustration of tensor CP decomposition method for clustering heterogeneous information network.The problem in (3) is an NP-hard nonconvex optimization problem, which has a continuous manifold of equivalent solutions [39]. In other words, the global minimum is drowned in many local minima, which makes it difficult to be found. In real-world scenarios, the objects in the heterogeneous information networks may belong to more than one cluster; that is, the clusters are overlapping. However, the number of clusters that the vast majority of objects may belong to is much smaller than the total number of clusters. That is, most of the elements in U(t) should be zero; that is, U(t) should be sparse. To overcome the two challenges, we can introduce a Tikhonov regularization term, proposed by Paatero in [44, 45], in the objective function and replace the objective function by the following loss function:(4)LX,U1,U2,…,UT=12X-U1,U2,…,UTF2+λ2∑t=1TUtF2,where λ>0 is a regularization parameter. Let(5)fX,U1,U2,…,UT=12X-U1,U2,…,UTF2be the first squared loss function component in L and let(6)gU1,U2,…,UT=λ2∑t=1TUtF2be the Tikhonov regularization term in L, respectively. Then (7)L=f+g.The Tikhonov regularization termg in the loss function L has an encouraging property, which makes the Frobenius norms of all factor matrices in the optimization be equal; that is,(8)U1F=U2F=⋯=UTF.Therefore, the local minima of loss function L become isolated, and any replacement and scaling of the satisfactory solutions will escape from the optimization. The details of proof can be found in [39]. Meanwhile, the Tikhonov regularization term can ensure the sparsity of the factor matrices by penalizing the number of nonzero elements.Therefore, the tensor CP decomposition method for clustering heterogeneous information networks can be formalized as(9)minU1,U2,…,UTLX,U1,U2,…,UTs.t.∑k=1Kun,kt=1,∀t,∀n,un,kt∈0,1,∀t,∀n,∀k,∑n=1Ntun,kt>0,∀t,∀k,where n=1,2,…,Nt; t=1,2,…,T; k=1,2,…,K, and K<minN1,N2,…,NT is the total number of clusters. In (9), we divide X into K clusters and obtain the structure of each cluster, which includes the distribution of each object. The first constraint in (9) guarantees that the sum of probabilities for each object belonging to all clusters is 1. The second constraint in (9) represents that each probability should be in the range of [0,1]. The last constraint in (9) makes sure that there is no empty cluster for any mode.


## 4.3. The Stochastic Gradient Descent Algorithms

Stochastic gradient descent is a mature and widely used tool for optimizing various models in machine learning, such as artificial neural networks, support vector machines, and logistic regression. In this section, the regularized clustering problem in (9) will be addressed by the stochastic gradient descent algorithms. The details of tensor algebra and properties used in this section can be found in [43].First, we review the stochastic gradient descent algorithm. To solve an optimization problem,minxQ(x), where Q(x) is a differentiable object function to be minimized and x is a variable, the stochastic gradient descent method to update x can be described as(10)x⟵x-η∇Qx,where η is a positive number, named learning rate or step size. The convergence speed of stochastic gradient descent algorithm depends on the choice of learning rate η and initial solution.Though the stochastic gradient descent algorithm may converge to a local minimum at a linear speed, the efficiency of the algorithm near the optimal point is not all roses [46]. To speed up the final optimization phase, an extension method named second-order stochastic algorithm is designed in [46], which replaces the learning rate η by the inverse of second-order derivative of the object function; that is,(11)x⟵x-η∇2Qx-1∇Qx.Now, we apply the stochastic gradient descent and the second-order stochastic algorithm to the clustering problem in (9) and propose two algorithms, named SGDClus (StochasticGradientDescent forClustering) and SOSClus (Second-OrderStochastic forClustering), respectively.


### 4.3.1. SGDClus

In SGDClus, we apply the stochastic gradient descent algorithm to the clustering problem in (9). According to (10), each factor matrix U(t), for t=1,2,…,T, is updated by the rule(12)Ut⟵Ut-η∂L∂Ut=Ut-η∂f∂Ut+∂g∂Ut.Actually,∂g/∂U(t) is easy to be obtained according to (6); that is,(13)∂g∂Ut=λUt.To compute ∂f/∂U(t), fX,U(1),U(2),…,U(T) can be rewritten by matricization of X along the tth mode as (14)ft=12Xt-Ut⊙/tU⊤F2, where ⊙(/t)U=U(T)⊙⋯⊙U(t+1)⊙U(t-1)⊙⋯⊙U(1). Then, we have(15)∂ft∂Ut=∂TrXt-Ut⊙/tU⊤Xt-Ut⊙/tU⊤⊤2∂Ut=∂TrXtXt⊤2∂Ut-∂Tr2Xt⊙/tUUt⊤2∂Ut+∂TrUt⊙/tU⊤Ut⊙/tU⊤⊤2∂Ut=-Xt⊙/tU+Ut⊙/tU⊤⊙/tU.Another way to compute ∂f(t)/∂U(t) is given in [39], which has the same result as (15). Following the works in [39], we denote(16)Γt=⊙/tU⊤⊙/tU=U1⊤U1∗⋯∗Ut-1⊤Ut-1∗Ut+1⊤Ut+1∗⋯∗UT⊤UT.Therefore, the partial derivative of L is given by(17)∂L∂Ut=-Xt⊙/tU+UtΓt+λUt.And (12) can be rewritten as(18)Ut⟵Ut-η∂L∂Ut=UtI-ηΓt+λI+ηXt⊙/tU,where I is an identity matrix. Note that {U(t)}t=1T derived by (18) do not satisfy the first and second constraints in (9). To satisfy these two constraints, we can normalize each row of {U(t)}t=1T by(19)un,kt⟵un,kt∑k=1Kun,kt.Furthermore, the pseudocode of SGDClus is given in Algorithm1.Algorithm 1:The SGDClus algorithm.
Input:    X, K, λ.
Output:    {U(t)}t=1T.
(1)  Initialize {U(t)}t=1T;
(2)  Set iter←1;
(3)   repeat
(4)  for  t←1  to  T  do
(5)     Set η;
(6)     Update U(t) according to (18);
(7)     Normalize U(t) according to (19);
(8)   end for
(9)    Set iter←iter+1;
(10)   until   LX,U(1),U(2),…,U(T) unchanged or iter
reaches the maximum iterations


### 4.3.2. SOSClus

In SOSClus, we apply the second-order stochastic algorithm to the clustering problem in (9). According to (11), each factor matrix U(t), for t=1,2,…,T, is updated by the rule(20)Ut⟵Ut-η∂2L∂2Ut-1∂L∂Ut.According to (17), we can obtain the second-order partial derivative of L with respect to U(t); that is,(21)∂2L∂2Ut=Γt+λI.By substituting (17) and (21) into (20), we have(22)Ut⟵1-ηUt+ηXt⊙/tUΓt+λI-1.Note thatX(t)⊙(/t)UΓ(t)+λI-1 is the General Gradient-based Optimization (OPT) [39] solution for updating U(t) in the regularized CP decomposition by making (17) equal to zero. See the details of proof in [39]. Let(23)Uoptt=Xt⊙/tUΓt+λI-1.Therefore, the updating rule of U(t) in SOSClus is a weighted average of the current solution and the OPT solution intuitively; that is,(24)Ut⟵1-ηUt+ηUoptt.Actually, SOSClus is a general extension of General Gradient-based Optimization (OPT) [39] and the ALS with step size restriction in randomized block sampling method [41]. In (24), when the learning rate η=1, we get the OPT solution. When the regularization parameter λ=0, SOSClus becomes the ALS with step size restriction in randomized block sampling method.Similar to SGDClus,{U(t)}t=1T derived by (24) in SOSClus also do not satisfy the first and second constraints in (9). We should normalize each row of {U(t)}t=1T according to (19). The pseudocode of SOSClus is given in Algorithm 2.Algorithm 2:The SOSClus algorithm.
Input:  X, K, λ.
Output:  {U(t)}t=1T.
(1)  Initialize {U(t)}t=1T;
(2)  Set iter←1;
(3)repeat
(4)   for   t←1   to   T   do
(5)    Set η;
(6)    Compute Uopt(t) according to (23)
(7)    Update U(t) according to (24);
(8)    Normalize U(t) according to (19);
(9)   end for
(10)     Set iter←iter+1;
(11)until   LX,U(1),U(2),…,U(T) unchanged or iter
reaches the maximum iterations


## 4.3.1. SGDClus

In SGDClus, we apply the stochastic gradient descent algorithm to the clustering problem in (9). According to (10), each factor matrix U(t), for t=1,2,…,T, is updated by the rule(12)Ut⟵Ut-η∂L∂Ut=Ut-η∂f∂Ut+∂g∂Ut.Actually,∂g/∂U(t) is easy to be obtained according to (6); that is,(13)∂g∂Ut=λUt.To compute ∂f/∂U(t), fX,U(1),U(2),…,U(T) can be rewritten by matricization of X along the tth mode as (14)ft=12Xt-Ut⊙/tU⊤F2, where ⊙(/t)U=U(T)⊙⋯⊙U(t+1)⊙U(t-1)⊙⋯⊙U(1). Then, we have(15)∂ft∂Ut=∂TrXt-Ut⊙/tU⊤Xt-Ut⊙/tU⊤⊤2∂Ut=∂TrXtXt⊤2∂Ut-∂Tr2Xt⊙/tUUt⊤2∂Ut+∂TrUt⊙/tU⊤Ut⊙/tU⊤⊤2∂Ut=-Xt⊙/tU+Ut⊙/tU⊤⊙/tU.Another way to compute ∂f(t)/∂U(t) is given in [39], which has the same result as (15). Following the works in [39], we denote(16)Γt=⊙/tU⊤⊙/tU=U1⊤U1∗⋯∗Ut-1⊤Ut-1∗Ut+1⊤Ut+1∗⋯∗UT⊤UT.Therefore, the partial derivative of L is given by(17)∂L∂Ut=-Xt⊙/tU+UtΓt+λUt.And (12) can be rewritten as(18)Ut⟵Ut-η∂L∂Ut=UtI-ηΓt+λI+ηXt⊙/tU,where I is an identity matrix. Note that {U(t)}t=1T derived by (18) do not satisfy the first and second constraints in (9). To satisfy these two constraints, we can normalize each row of {U(t)}t=1T by(19)un,kt⟵un,kt∑k=1Kun,kt.Furthermore, the pseudocode of SGDClus is given in Algorithm1.Algorithm 1:The SGDClus algorithm.
Input:    X, K, λ.
Output:    {U(t)}t=1T.
(1)  Initialize {U(t)}t=1T;
(2)  Set iter←1;
(3)   repeat
(4)  for  t←1  to  T  do
(5)     Set η;
(6)     Update U(t) according to (18);
(7)     Normalize U(t) according to (19);
(8)   end for
(9)    Set iter←iter+1;
(10)   until   LX,U(1),U(2),…,U(T) unchanged or iter
reaches the maximum iterations


## 4.3.2. SOSClus

In SOSClus, we apply the second-order stochastic algorithm to the clustering problem in (9). According to (11), each factor matrix U(t), for t=1,2,…,T, is updated by the rule(20)Ut⟵Ut-η∂2L∂2Ut-1∂L∂Ut.According to (17), we can obtain the second-order partial derivative of L with respect to U(t); that is,(21)∂2L∂2Ut=Γt+λI.By substituting (17) and (21) into (20), we have(22)Ut⟵1-ηUt+ηXt⊙/tUΓt+λI-1.Note thatX(t)⊙(/t)UΓ(t)+λI-1 is the General Gradient-based Optimization (OPT) [39] solution for updating U(t) in the regularized CP decomposition by making (17) equal to zero. See the details of proof in [39]. Let(23)Uoptt=Xt⊙/tUΓt+λI-1.Therefore, the updating rule of U(t) in SOSClus is a weighted average of the current solution and the OPT solution intuitively; that is,(24)Ut⟵1-ηUt+ηUoptt.Actually, SOSClus is a general extension of General Gradient-based Optimization (OPT) [39] and the ALS with step size restriction in randomized block sampling method [41]. In (24), when the learning rate η=1, we get the OPT solution. When the regularization parameter λ=0, SOSClus becomes the ALS with step size restriction in randomized block sampling method.Similar to SGDClus,{U(t)}t=1T derived by (24) in SOSClus also do not satisfy the first and second constraints in (9). We should normalize each row of {U(t)}t=1T according to (19). The pseudocode of SOSClus is given in Algorithm 2.Algorithm 2:The SOSClus algorithm.
Input:  X, K, λ.
Output:  {U(t)}t=1T.
(1)  Initialize {U(t)}t=1T;
(2)  Set iter←1;
(3)repeat
(4)   for   t←1   to   T   do
(5)    Set η;
(6)    Compute Uopt(t) according to (23)
(7)    Update U(t) according to (24);
(8)    Normalize U(t) according to (19);
(9)   end for
(10)     Set iter←iter+1;
(11)until   LX,U(1),U(2),…,U(T) unchanged or iter
reaches the maximum iterations


## 4.4. Feasibility Analysis

Theorem 4.
The CP decomposition ofX obtains the clustering of multityped objects in the heterogeneous information network G=(V,E) simultaneously.Proof.
Since the proofs for different types of objects in the heterogeneous information networkG=(V,E) are similar, we will simply describe the process for a single type of objects. Without loss of generality, we detail the proof on the tth type of objects.
Given a heterogeneous information networkG=(V,E) and its tensor representation X, the nonzero elements in X represent the input gene-networks in G=(V,E), which we want to partition into K clusters C1,C2,…,CK. The centre of the cluster Ck is denoted by ck. By using the coordinate format [47] as the sparse representation of X, the gene-networks can be denoted as a matrix M∈Rnnz(X)×T, where nnz(X) is the number of nonzero elements in X. Each row mn∈M,n=1,2,…,nnz(X) gives the subscripts of corresponding nonzero element in X. In other words, mn represents a gene-network and the entries mn,t∈mn,t=1,2,…,T are the subscripts of the objects contained in the gene-network.
The traditional clustering approach, such asK-means, minimizes the sum of differences between individual gene-network in each cluster and the corresponding cluster centres; that is,(25)minpn,k,ck∑n=1nnzXmn-∑k=1Kpn,kckF2,where pn,k is the probability of gene-network mn belonging to the kth cluster. Also we can rewrite the problem by a new perspective of clustering individual object in the gene-network as follows: (26)minpnt,k,ck,t∑n=1nnzX∑t=1Tmn,t-∑k=1Kpnt,kck,tF2,where pnt,k is the probability of object vnt belonging to the kth cluster.
In the matrix form,K-means can be formalized as (27)minP,CM-PCF2,where P is the cluster indication matrix and C is the cluster centres.
By matricization ofX along the tth mode, the CP decomposition of X in (3) can be rewritten as (28)minU1,U2,…,UTXt-Ut⊙/tU⊤F2X(t) is the matricization of X along the tth mode and M is the sparse representation of X. Let U(t)=P and let ⊙(/t)U⊤=C. That is, U(t) is the cluster indication matrix for the tth type of objects and ⊙(/t)U⊤ is the cluster centres. So, the CP decomposition in (3) is equivalent to theK-means clustering for the tth type of objects in heterogeneous information network G=(V,E).
By matricization ofX in (3) along different modes, we can prove that the CP decomposition is equivalent to theK-means clustering for other types of objects. So, the CP decomposition of X obtains the clustering of multityped objects in the heterogeneous information network G=(V,E) simultaneously.It is worth noting that the CP decomposition based clustering is a soft clustering method; the factor matrices indicate the probability of objects belonging to corresponding clusters. The soft clustering is more in line with reality, because many objects in the heterogeneous information networks may belong to several clusters. In other words, the clusters are overlapping. In some cases, the overlapping clusters need to be translated into nonoverlapping clusters, which can be achieved by using different approaches, such asK-means, to cluster the rows of factor matrices. Usually, the nonoverlapping clusters can be obtained by simply assigning each object to the cluster which has the largest entry in the corresponding row of factor matrix.


## 4.5. Time Complexity Analysis

The main time consumption of updating each factor matrixU(t) in SGDClus is computing ∂L/∂U(t). According to (17), we need to calculate X(t)⊙(/t)U and U(t)Γ(t), respectively. Since U(t)∈RNt×K and X(t)∈RNt×∏i=1i≠tT‍Ni, we have X(t)⊙(/t)U∈RNt×K, Γ(t)∈RK×K, and U(t)Γ(t)∈RNt×K.Firstly, if we successively calculate the Khatri-Rao product ofT-1 matrices and a matrix-matrix multiplication when computing X(t)⊙(/t)U, the intermediate results will be of very large size and the computational cost will be very expensive. In practice, we can reduce the complexity by ignoring the unnecessary calculation. Let us observe the element of X(t)⊙(/t)U; that is,(29)Xt⊙/tUnt,k=∑nii=1i≠tTxnt,∏i=1i≠tTni∏i=1i≠tTuni,ki;xnt,∏i=1i≠tTni is an element in the matricization of X, which represents a corresponding gene-network in the heterogeneous information network. When xnt,∏i=1i≠tTni=0, we can ignore the following Khatri-Rao product. Hence, only nonzero elements in X need to be computed. Therefore, the time complexity for computing X(t)⊙(/t)U is Onnz(X)NtK.Secondly, the element ofU(t)Γ(t) is given by(30)UtΓtnt,k=∑j=1Kunt,jt∏i=1i≠tT∑ni=1Niuni,jiuni,ki.So, the time complexity of computing U(t)Γ(t) is O(N-Nt)K2, where N=∑t=1T‍Nt is the total number of objects in the networks.Above all, the time complexity of each iteration in SGDClus isOnnz(X)NK+(T-1)NK2. Note that, in the real-world heterogeneous information networks, the number of clusters K and the number of object types T are usually far less than N; that is, K≪N and T≪N.According to (22), the time complexity of updating each factor matrix U(t) in SOSClus is composed of three components: X(t)⊙(/t)U, Γ(t)+λI-1, and the product of them. Compared to SGDClus, only the time consumption of computing an inverse matrix for Γ(t)+λI is additional in SOSClus. Since Γ(t)+λI is a K×K square matrix, computing the inverse of such matrix costs O(K3). Nevertheless, O(K3) is usually negligible because K≪N.


## 5. Experiments and Results

In this section, we present several experiments on synthetic and real-world datasets for heterogeneous information networks and compare the performance with a number of state-of-the-art clustering methods.


### 5.1. Evaluation Metrics and Experimental Setting

#### 5.1.1. Evaluation Metrics

In the experiments, we adopt the Normalized Mutual Information (NMI) [48] and Accuracy (AC) as our performance measurements.NMI is used to measure the mutual dependence information between the clustering result and the ground truth. GivenN objects, K clusters, one clustering result, and the ground truth classes for the objects, let n(i,j), i,j=1,2,…,K, be the number of objects that labeled i in clustering result but labeled j in the ground truth. The joint distribution can be defined as p(i,j)=n(i,j)/N, the marginal distribution of rows can be calculated as p1(j)=∑i=1K‍p(i,j), and the marginal distribution of columns can be calculated as p2(i)=∑j=1K‍p(i,j). Then, the NMI is defined as (31)NMI=∑i=1K∑j=1Kpi,jlogpi,j/p1jp2i∑j=1Kp1jlog⁡p1j∑i=1Kp2ilog⁡p2i.The NMI ranges from 0 to 1: the larger value of NMI, the better the clustering result.AC is used to compute the clustering accuracy that measures the percent of the correct clustering result. AC is defined as(32)AC=∑t=1T∑n=1Ntδmapυnt,labelυnt∑t=1TNt,where map(υnt) is the cluster label of the object υnt and the label(υnt) is the ground truth class of the object υnt. And δ(·) is an indicator function: (33)δ·=1ifmapυnt=labelυnt,0ifmapυnt≠labelυnt.Since both of NMI and AC are used to measure the performance of clustering one type of object, the weighted average NMI and AC are also used to measure the performance of STFClus and other state-of-the-art methods:(34)NMI¯=∑t=1TNtNMIt∑t=1TNt,AC¯=∑t=1TNtACt∑t=1TNt.


#### 5.1.2. Experimental Setting

In order to compare the performance of our proposed SGDClus and SOSClus with others impartially, all methods share a common stopping condition, that is,(35)Liter-Liter-1Liter-1≤10-6,or iter reaches the maximum iterations. Liter and Liter-1 are the values of function L at the current, that is, (iter)th, iteration, and the previous, that is, (iter-1)th, iteration, respectively. And we set the maximum iterations to be 1000. Throughout the experiments, the regularization parameter λ in SGDClus and SOSClus is fixed as λ=0.001.All experiments are implemented in the MATLAB R2015a (version 8.5.0), 64-bit. And the MATLAB Tensor Toolbox (version 2.6,http://www.sandia.gov/~tgkolda/TensorToolbox/) is used in our experiments. Since the heterogeneous information networks are often sparse in real-world scenarios, that is, most elements in the tensor X are zeros, we use the sparse format of X as proposed in [47], which has been supported by MATLAB Tensor Toolbox. The experimental results are the average values obtained by running the algorithms ten times on corresponding datasets.


### 5.2. Experiments on Synthetic Datasets

#### 5.2.1. The Synthetic Datasets Description

The purpose of using synthetic datasets is to examine whether the proposed tensor CP decomposition clustering framework can work well, since the detailed cluster structures of the synthetic datasets are known. In order to make the synthetic datasets similar to a realistic situation, we assume that the distribution for different types of objects that appear in a gene-network follows Zipf’s law (see details online:https://en.wikipedia.org/wiki/Zipf’s_law). Zipf’s law is defined by f(r;ρ,N)=r-ρ/∑n=1N‍n-ρ, where N is the number of objects, r is the object index, and ρ is the parameter characterizing the distribution. Zipf’s law denotes the frequency of the rth object appearing in the gene-network. We set ρ=0.95 and generate 4 synthetic datasets with different parameters. The details of these synthetic datasets are shown in Table 1.Table 1
The synthetic datasets.
Synthetic datasets
T
K
S
D
S
y
n
1
2
2
1
M
=
1000
×
1000
0.1%
S
y
n
2
2
4
10
M
=
1000
×
10000
0.01%
S
y
n
3
4
2
100
M
=
100
×
100
×
100
×
100
0.1%
S
y
n
4
4
4
1000
M
=
100
×
100
×
100
×
1000
0.01%
T is the number of object types in the heterogeneous information network and also the number of modes in the tensor. K is the number of clusters. S is the network scale, and S=N1×N2×⋯×NT. D is the density of the tensor, that is, the percentage of nonzero elements in the tensor, and D=nnz(X)/S.


#### 5.2.2. Experimental Results

In the beginning of the experiments, we set a common learning rate,η=1/(iter+1), for SGDClus and SOSClus. We find that SOSClus has a faster convergence speed and better robustness with respect to the learning rate, which is clearly shown in Figure 3. Although SGDClus may eventually converge to a local minimum, the efficiency of the optimization near a local minimum is not all roses. As shown in Figure 3, the solutions of SGDClus swing around a local minimum. This phenomenon proves that the convergence speed of SGDClus is sensitive to the choice of learning rate η.Figure 3
Convergence speed of SGDClus and SOSClus on the 4 synthetic datasets with a common learning rate, that is,η=1/(iter+1).Then, we modify the learning rate toη=1/(iter+c) for SGDClus, where c is a constant optimized in the experiments. In practice, c=27855 for SGDClus running on Syn3 and c=430245 for SGDClus running on Syn4. The performance comparison of SGDClus with learning rate η=1/(iter+c) and SOSClus with learning rate η=1/(iter+1) on Syn3 and Syn4 is shown in Figure 4. By employing the optimized learning rate, SGDClus converges to a local minimum quickly. However, compared to SOSClus, SGDClus still has no advantage. The hand drawing blue circles over the curve of SOSClus in Figure 4 shows that SOSClus can escape from a local minimum and find the global minimum, while SGDClus just obtains the first reaching local minimum.Figure 4
Convergence speed of SGDClus and SOSClus onSyn3 and Syn4 with different learning rate. The learning rate for SOSClus is η=1/(iter+1), while that for SGDClus is η=1/(iter+c), where c is a constant optimized in the experiments.According to (23) and (24), we accessorily obtain the solutions of OPT by running SOSClus. So, we compare the AC and NMI of OPT, SGDClus, and SOSClus on the 4 synthetic datasets, which are shown in Figure 5. With the increase of object types in the heterogeneous information networks, the AC and NMI of SOSClus and OPT increase distinctly, while performance of SGDClus almost does not change. When T=2, AC and NMI of these three methods on Syn1 and Syn2 are almost equal and low. However, AC and NMI of SOSClus increase to 1 when T=4. Since the histograms of OPT, SGDClus, and SOSClus on Syn1 and Syn2 are almost the same and on Syn3 and Syn4 are also similar, we know that the parameters K and S have no significant effect on the performance. Generally, the larger density D and the number of object types T in the network result in higher AC and NMI of SOSClus.Figure 5
The AC and NMI of OPT, SGDClus, and SOSClus on the 4 synthetic datasets.Obviously, in the experiments on the 4 synthetic datasets, SOSClus shows an excellent performance. SOSClus has a faster convergence speed and better robustness with respect to the learning rate. Meanwhile, SOSClus performs better on AC and NMI, because it can escape from a local minimum and find the global minimum.


### 5.3. Performance Comparison on Real-World Dataset

#### 5.3.1. Real-World Dataset Description

The experiments on the real-world dataset are used to compare the performance of the tensor CP decomposition clustering framework with other state-of-the-art methods.The real-world dataset extracted from the DBLP database is the DBLP-four-area dataset, which can be downloaded fromhttp://web.cs.ucla.edu/~yzsun/data/DBLP_four_area.zip. It is a four research-area subset of DBLP and is used in [2, 3, 12, 13, 15, 16, 18]. The four research areas in DBLP-four-area dataset are database (DB), data mining (DM), machine learning (ML), and information retrieval (IR), respectively. There are five representative conferences in each area. And all related authors, papers published in these conferences, and terms contained in these papers’ titles are included. The DBLP-four-area dataset contains 14,376 papers with 100 labeled, 14,475 authors with 4,057 labeled, 20 labeled conferences, and 8,920 terms. The density of the DBLP-four-area dataset is 9.01935×10-9, so we construct a 4-mode tensor with size of 14,376 × 14,475 × 20 × 8,920 and 334832 nonzero elements. We compare the performance of tensor CP decomposition clustering framework with several other methods on the labeled record in this dataset.


#### 5.3.2. Comparative Methods

(i) NetClus (see [2]). An extended version of RankClus [1], which can deal with the network, follows the star network schema. The time complexity of NetClus for clustering each object type in each iteration is O(K|E|+(K2+K)N), where K is the number of clusters, |E| is the number of edges in the network, and N is the total number of objects in the network.(ii) PathSelClus (see [15, 16]). A clustering method based on the predefined metapath requires a user guide. In PathSelClus, the distance between the same type objects is measured by PathSim [3], and the method starts with the given seeds by user. The time complexity of PathSelClus for clustering each object type in each iteration is O((K+1)|P|+KN), where |P| is the number of metapath instances in the network. And, the time complexity of PathSim used by PathSelClus for clustering each object type is O(Nd), where d is the average degree of objects.(iii) FctClus (see [13]). It is a recently proposed clustering method for heterogeneous information networks. As with NetClus, the FctClus method can deal with networks following the star network schema. The time complexity of FctClus for clustering each object type in each iteration is O(K|E|+TKN).


#### 5.3.3. Experimental Results

As the baseline methods can only deal with specific schema heterogeneous information networks, here we must construct different subnetworks for them. For NetClus and FctClus, the network is organized as a star network schema like in [2, 13], where the paper (P) is the centre type, and author (A), conference (C), and term (T) are the attribute types. For PathSelClus, we select the metapath of P-T-P, A-P-C-P-A, and C-P-T-P-C to cluster the papers, authors, and conferences, respectively. And in PathSelClus, we give each cluster one seed to start.We model the DBLP-four-area dataset as a 4-mode tensor, where each mode represents one object type. The 4 modes are author (A), paper (P), conference (C), and term (T), respectively. Actually, the sequence of the object types is insignificant. And each element of the tensor represents a gene-network in the heterogeneous information network. In the experiments, we set the learning rate for SOSClus to beη=1/(iter+1) and an optimized learning rate η=1/(iter+c) with c=1000125 for SGDClus. By running SOSClus, we accessorily obtain the solutions of OPT. So, we compare the experimental results of OPT, SGDClus, and SOSClus on the DBLP-four-area dataset with the three baseline methods. See the details in Tables 2, 3, and 4.Table 2
AC of experiments on DBLP-four-area dataset.
AC
OPT
SGDClus
SOSClus
NetClus
PathSelClus
FctClus
Paper
0.5882
0.8476
0.9007
0.7154
0.7551
0.7887
Author
0.5872
0.8486
0.9486
0.7177
0.7951
0.8008
Conference
1
0.99
1
0.9172
0.9950
0.9031
a
v
g
(
A
C
)
0.5892
0.8493
0.9477
0.7186
0.7951
0.8010Table 3
NMI of experiments on DBLP-four-area dataset.
NMI
OPT
SGDClus
SOSClus
NetClus
PathSelClus
FctClus
Paper
0.6557
0.6720
0.8812
0.5402
0.6142
0.7152
Author
0.6539
0.8872
0.8822
0.5488
0.6770
0.6012
Conference
1
0.8497
1
0.8858
0.9906
0.8248
a
v
g
(
N
M
I
)
0.6556
0.8778
0.8827
0.5503
0.6770
0.6050Table 4
Running time of experiments on DBLP-four-area dataset.
Running time (s)
OPT
SGDClus
SOSClus
NetClus
PathSelClus
FctClus
Paper
—
—
—
802.6
542.3
808.4
Author
—
—
—
743.7
681.1
774.9
Conference
—
—
—
658.4
629.3
669.8
Total time
672.6
432.4
818.4
2204.7
1852.7
2253.1In Tables2 and 3, SOSClus performs best on average AC and NMI, and SGDClus takes the second place. All methods achieve satisfactory AC and NMI on the conference, since there are only 20 conferences in the network. SGDClus takes the shortest running time, and OPT and SOSClus have an obvious advantage on running time compared with other baselines. The time complexity of SGDClus is Onnz(X)NK+(T-1)K2N, and the time complexity of SOSClus is Onnz(X)NK+(T-1)K2N+K3, where nnz(X) is the number of nonzero elements in X, that is, the number of gene-networks in the heterogeneous information network. We have nnz(X)<|P|≪|E|, K≪N, and T≪N. Compared with the time complexity of the three baselines, SGDClus and SOSClus have a little disadvantage. However, it is worth noting that the three baselines can only cluster one type of objects in the network in each running, while OPT, SGDClus, and SOSClus can obtain the clusters of all types of objects simultaneously by running once. This is the reason why only the total time is shown for OPT, SGDClus, and SOSClus in Table 4. Moreover, the total time of OPT, SGDClus, and SOSClus is on the same order of magnitude as the running time of other baselines for clustering each type of objects, which is consistent with the comparison of the time complexity.


## 5.1. Evaluation Metrics and Experimental Setting

### 5.1.1. Evaluation Metrics

In the experiments, we adopt the Normalized Mutual Information (NMI) [48] and Accuracy (AC) as our performance measurements.NMI is used to measure the mutual dependence information between the clustering result and the ground truth. GivenN objects, K clusters, one clustering result, and the ground truth classes for the objects, let n(i,j), i,j=1,2,…,K, be the number of objects that labeled i in clustering result but labeled j in the ground truth. The joint distribution can be defined as p(i,j)=n(i,j)/N, the marginal distribution of rows can be calculated as p1(j)=∑i=1K‍p(i,j), and the marginal distribution of columns can be calculated as p2(i)=∑j=1K‍p(i,j). Then, the NMI is defined as (31)NMI=∑i=1K∑j=1Kpi,jlogpi,j/p1jp2i∑j=1Kp1jlog⁡p1j∑i=1Kp2ilog⁡p2i.The NMI ranges from 0 to 1: the larger value of NMI, the better the clustering result.AC is used to compute the clustering accuracy that measures the percent of the correct clustering result. AC is defined as(32)AC=∑t=1T∑n=1Ntδmapυnt,labelυnt∑t=1TNt,where map(υnt) is the cluster label of the object υnt and the label(υnt) is the ground truth class of the object υnt. And δ(·) is an indicator function: (33)δ·=1ifmapυnt=labelυnt,0ifmapυnt≠labelυnt.Since both of NMI and AC are used to measure the performance of clustering one type of object, the weighted average NMI and AC are also used to measure the performance of STFClus and other state-of-the-art methods:(34)NMI¯=∑t=1TNtNMIt∑t=1TNt,AC¯=∑t=1TNtACt∑t=1TNt.


### 5.1.2. Experimental Setting

In order to compare the performance of our proposed SGDClus and SOSClus with others impartially, all methods share a common stopping condition, that is,(35)Liter-Liter-1Liter-1≤10-6,or iter reaches the maximum iterations. Liter and Liter-1 are the values of function L at the current, that is, (iter)th, iteration, and the previous, that is, (iter-1)th, iteration, respectively. And we set the maximum iterations to be 1000. Throughout the experiments, the regularization parameter λ in SGDClus and SOSClus is fixed as λ=0.001.All experiments are implemented in the MATLAB R2015a (version 8.5.0), 64-bit. And the MATLAB Tensor Toolbox (version 2.6,http://www.sandia.gov/~tgkolda/TensorToolbox/) is used in our experiments. Since the heterogeneous information networks are often sparse in real-world scenarios, that is, most elements in the tensor X are zeros, we use the sparse format of X as proposed in [47], which has been supported by MATLAB Tensor Toolbox. The experimental results are the average values obtained by running the algorithms ten times on corresponding datasets.


## 5.1.1. Evaluation Metrics

In the experiments, we adopt the Normalized Mutual Information (NMI) [48] and Accuracy (AC) as our performance measurements.NMI is used to measure the mutual dependence information between the clustering result and the ground truth. GivenN objects, K clusters, one clustering result, and the ground truth classes for the objects, let n(i,j), i,j=1,2,…,K, be the number of objects that labeled i in clustering result but labeled j in the ground truth. The joint distribution can be defined as p(i,j)=n(i,j)/N, the marginal distribution of rows can be calculated as p1(j)=∑i=1K‍p(i,j), and the marginal distribution of columns can be calculated as p2(i)=∑j=1K‍p(i,j). Then, the NMI is defined as (31)NMI=∑i=1K∑j=1Kpi,jlogpi,j/p1jp2i∑j=1Kp1jlog⁡p1j∑i=1Kp2ilog⁡p2i.The NMI ranges from 0 to 1: the larger value of NMI, the better the clustering result.AC is used to compute the clustering accuracy that measures the percent of the correct clustering result. AC is defined as(32)AC=∑t=1T∑n=1Ntδmapυnt,labelυnt∑t=1TNt,where map(υnt) is the cluster label of the object υnt and the label(υnt) is the ground truth class of the object υnt. And δ(·) is an indicator function: (33)δ·=1ifmapυnt=labelυnt,0ifmapυnt≠labelυnt.Since both of NMI and AC are used to measure the performance of clustering one type of object, the weighted average NMI and AC are also used to measure the performance of STFClus and other state-of-the-art methods:(34)NMI¯=∑t=1TNtNMIt∑t=1TNt,AC¯=∑t=1TNtACt∑t=1TNt.


## 5.1.2. Experimental Setting

In order to compare the performance of our proposed SGDClus and SOSClus with others impartially, all methods share a common stopping condition, that is,(35)Liter-Liter-1Liter-1≤10-6,or iter reaches the maximum iterations. Liter and Liter-1 are the values of function L at the current, that is, (iter)th, iteration, and the previous, that is, (iter-1)th, iteration, respectively. And we set the maximum iterations to be 1000. Throughout the experiments, the regularization parameter λ in SGDClus and SOSClus is fixed as λ=0.001.All experiments are implemented in the MATLAB R2015a (version 8.5.0), 64-bit. And the MATLAB Tensor Toolbox (version 2.6,http://www.sandia.gov/~tgkolda/TensorToolbox/) is used in our experiments. Since the heterogeneous information networks are often sparse in real-world scenarios, that is, most elements in the tensor X are zeros, we use the sparse format of X as proposed in [47], which has been supported by MATLAB Tensor Toolbox. The experimental results are the average values obtained by running the algorithms ten times on corresponding datasets.


## 5.2. Experiments on Synthetic Datasets

### 5.2.1. The Synthetic Datasets Description

The purpose of using synthetic datasets is to examine whether the proposed tensor CP decomposition clustering framework can work well, since the detailed cluster structures of the synthetic datasets are known. In order to make the synthetic datasets similar to a realistic situation, we assume that the distribution for different types of objects that appear in a gene-network follows Zipf’s law (see details online:https://en.wikipedia.org/wiki/Zipf’s_law). Zipf’s law is defined by f(r;ρ,N)=r-ρ/∑n=1N‍n-ρ, where N is the number of objects, r is the object index, and ρ is the parameter characterizing the distribution. Zipf’s law denotes the frequency of the rth object appearing in the gene-network. We set ρ=0.95 and generate 4 synthetic datasets with different parameters. The details of these synthetic datasets are shown in Table 1.Table 1
The synthetic datasets.
Synthetic datasets
T
K
S
D
S
y
n
1
2
2
1
M
=
1000
×
1000
0.1%
S
y
n
2
2
4
10
M
=
1000
×
10000
0.01%
S
y
n
3
4
2
100
M
=
100
×
100
×
100
×
100
0.1%
S
y
n
4
4
4
1000
M
=
100
×
100
×
100
×
1000
0.01%
T is the number of object types in the heterogeneous information network and also the number of modes in the tensor. K is the number of clusters. S is the network scale, and S=N1×N2×⋯×NT. D is the density of the tensor, that is, the percentage of nonzero elements in the tensor, and D=nnz(X)/S.


### 5.2.2. Experimental Results

In the beginning of the experiments, we set a common learning rate,η=1/(iter+1), for SGDClus and SOSClus. We find that SOSClus has a faster convergence speed and better robustness with respect to the learning rate, which is clearly shown in Figure 3. Although SGDClus may eventually converge to a local minimum, the efficiency of the optimization near a local minimum is not all roses. As shown in Figure 3, the solutions of SGDClus swing around a local minimum. This phenomenon proves that the convergence speed of SGDClus is sensitive to the choice of learning rate η.Figure 3
Convergence speed of SGDClus and SOSClus on the 4 synthetic datasets with a common learning rate, that is,η=1/(iter+1).Then, we modify the learning rate toη=1/(iter+c) for SGDClus, where c is a constant optimized in the experiments. In practice, c=27855 for SGDClus running on Syn3 and c=430245 for SGDClus running on Syn4. The performance comparison of SGDClus with learning rate η=1/(iter+c) and SOSClus with learning rate η=1/(iter+1) on Syn3 and Syn4 is shown in Figure 4. By employing the optimized learning rate, SGDClus converges to a local minimum quickly. However, compared to SOSClus, SGDClus still has no advantage. The hand drawing blue circles over the curve of SOSClus in Figure 4 shows that SOSClus can escape from a local minimum and find the global minimum, while SGDClus just obtains the first reaching local minimum.Figure 4
Convergence speed of SGDClus and SOSClus onSyn3 and Syn4 with different learning rate. The learning rate for SOSClus is η=1/(iter+1), while that for SGDClus is η=1/(iter+c), where c is a constant optimized in the experiments.According to (23) and (24), we accessorily obtain the solutions of OPT by running SOSClus. So, we compare the AC and NMI of OPT, SGDClus, and SOSClus on the 4 synthetic datasets, which are shown in Figure 5. With the increase of object types in the heterogeneous information networks, the AC and NMI of SOSClus and OPT increase distinctly, while performance of SGDClus almost does not change. When T=2, AC and NMI of these three methods on Syn1 and Syn2 are almost equal and low. However, AC and NMI of SOSClus increase to 1 when T=4. Since the histograms of OPT, SGDClus, and SOSClus on Syn1 and Syn2 are almost the same and on Syn3 and Syn4 are also similar, we know that the parameters K and S have no significant effect on the performance. Generally, the larger density D and the number of object types T in the network result in higher AC and NMI of SOSClus.Figure 5
The AC and NMI of OPT, SGDClus, and SOSClus on the 4 synthetic datasets.Obviously, in the experiments on the 4 synthetic datasets, SOSClus shows an excellent performance. SOSClus has a faster convergence speed and better robustness with respect to the learning rate. Meanwhile, SOSClus performs better on AC and NMI, because it can escape from a local minimum and find the global minimum.


## 5.2.1. The Synthetic Datasets Description

The purpose of using synthetic datasets is to examine whether the proposed tensor CP decomposition clustering framework can work well, since the detailed cluster structures of the synthetic datasets are known. In order to make the synthetic datasets similar to a realistic situation, we assume that the distribution for different types of objects that appear in a gene-network follows Zipf’s law (see details online:https://en.wikipedia.org/wiki/Zipf’s_law). Zipf’s law is defined by f(r;ρ,N)=r-ρ/∑n=1N‍n-ρ, where N is the number of objects, r is the object index, and ρ is the parameter characterizing the distribution. Zipf’s law denotes the frequency of the rth object appearing in the gene-network. We set ρ=0.95 and generate 4 synthetic datasets with different parameters. The details of these synthetic datasets are shown in Table 1.Table 1
The synthetic datasets.
Synthetic datasets
T
K
S
D
S
y
n
1
2
2
1
M
=
1000
×
1000
0.1%
S
y
n
2
2
4
10
M
=
1000
×
10000
0.01%
S
y
n
3
4
2
100
M
=
100
×
100
×
100
×
100
0.1%
S
y
n
4
4
4
1000
M
=
100
×
100
×
100
×
1000
0.01%
T is the number of object types in the heterogeneous information network and also the number of modes in the tensor. K is the number of clusters. S is the network scale, and S=N1×N2×⋯×NT. D is the density of the tensor, that is, the percentage of nonzero elements in the tensor, and D=nnz(X)/S.


## 5.2.2. Experimental Results

In the beginning of the experiments, we set a common learning rate,η=1/(iter+1), for SGDClus and SOSClus. We find that SOSClus has a faster convergence speed and better robustness with respect to the learning rate, which is clearly shown in Figure 3. Although SGDClus may eventually converge to a local minimum, the efficiency of the optimization near a local minimum is not all roses. As shown in Figure 3, the solutions of SGDClus swing around a local minimum. This phenomenon proves that the convergence speed of SGDClus is sensitive to the choice of learning rate η.Figure 3
Convergence speed of SGDClus and SOSClus on the 4 synthetic datasets with a common learning rate, that is,η=1/(iter+1).Then, we modify the learning rate toη=1/(iter+c) for SGDClus, where c is a constant optimized in the experiments. In practice, c=27855 for SGDClus running on Syn3 and c=430245 for SGDClus running on Syn4. The performance comparison of SGDClus with learning rate η=1/(iter+c) and SOSClus with learning rate η=1/(iter+1) on Syn3 and Syn4 is shown in Figure 4. By employing the optimized learning rate, SGDClus converges to a local minimum quickly. However, compared to SOSClus, SGDClus still has no advantage. The hand drawing blue circles over the curve of SOSClus in Figure 4 shows that SOSClus can escape from a local minimum and find the global minimum, while SGDClus just obtains the first reaching local minimum.Figure 4
Convergence speed of SGDClus and SOSClus onSyn3 and Syn4 with different learning rate. The learning rate for SOSClus is η=1/(iter+1), while that for SGDClus is η=1/(iter+c), where c is a constant optimized in the experiments.According to (23) and (24), we accessorily obtain the solutions of OPT by running SOSClus. So, we compare the AC and NMI of OPT, SGDClus, and SOSClus on the 4 synthetic datasets, which are shown in Figure 5. With the increase of object types in the heterogeneous information networks, the AC and NMI of SOSClus and OPT increase distinctly, while performance of SGDClus almost does not change. When T=2, AC and NMI of these three methods on Syn1 and Syn2 are almost equal and low. However, AC and NMI of SOSClus increase to 1 when T=4. Since the histograms of OPT, SGDClus, and SOSClus on Syn1 and Syn2 are almost the same and on Syn3 and Syn4 are also similar, we know that the parameters K and S have no significant effect on the performance. Generally, the larger density D and the number of object types T in the network result in higher AC and NMI of SOSClus.Figure 5
The AC and NMI of OPT, SGDClus, and SOSClus on the 4 synthetic datasets.Obviously, in the experiments on the 4 synthetic datasets, SOSClus shows an excellent performance. SOSClus has a faster convergence speed and better robustness with respect to the learning rate. Meanwhile, SOSClus performs better on AC and NMI, because it can escape from a local minimum and find the global minimum.


## 5.3. Performance Comparison on Real-World Dataset

### 5.3.1. Real-World Dataset Description

The experiments on the real-world dataset are used to compare the performance of the tensor CP decomposition clustering framework with other state-of-the-art methods.The real-world dataset extracted from the DBLP database is the DBLP-four-area dataset, which can be downloaded fromhttp://web.cs.ucla.edu/~yzsun/data/DBLP_four_area.zip. It is a four research-area subset of DBLP and is used in [2, 3, 12, 13, 15, 16, 18]. The four research areas in DBLP-four-area dataset are database (DB), data mining (DM), machine learning (ML), and information retrieval (IR), respectively. There are five representative conferences in each area. And all related authors, papers published in these conferences, and terms contained in these papers’ titles are included. The DBLP-four-area dataset contains 14,376 papers with 100 labeled, 14,475 authors with 4,057 labeled, 20 labeled conferences, and 8,920 terms. The density of the DBLP-four-area dataset is 9.01935×10-9, so we construct a 4-mode tensor with size of 14,376 × 14,475 × 20 × 8,920 and 334832 nonzero elements. We compare the performance of tensor CP decomposition clustering framework with several other methods on the labeled record in this dataset.


### 5.3.2. Comparative Methods

(i) NetClus (see [2]). An extended version of RankClus [1], which can deal with the network, follows the star network schema. The time complexity of NetClus for clustering each object type in each iteration is O(K|E|+(K2+K)N), where K is the number of clusters, |E| is the number of edges in the network, and N is the total number of objects in the network.(ii) PathSelClus (see [15, 16]). A clustering method based on the predefined metapath requires a user guide. In PathSelClus, the distance between the same type objects is measured by PathSim [3], and the method starts with the given seeds by user. The time complexity of PathSelClus for clustering each object type in each iteration is O((K+1)|P|+KN), where |P| is the number of metapath instances in the network. And, the time complexity of PathSim used by PathSelClus for clustering each object type is O(Nd), where d is the average degree of objects.(iii) FctClus (see [13]). It is a recently proposed clustering method for heterogeneous information networks. As with NetClus, the FctClus method can deal with networks following the star network schema. The time complexity of FctClus for clustering each object type in each iteration is O(K|E|+TKN).


### 5.3.3. Experimental Results

As the baseline methods can only deal with specific schema heterogeneous information networks, here we must construct different subnetworks for them. For NetClus and FctClus, the network is organized as a star network schema like in [2, 13], where the paper (P) is the centre type, and author (A), conference (C), and term (T) are the attribute types. For PathSelClus, we select the metapath of P-T-P, A-P-C-P-A, and C-P-T-P-C to cluster the papers, authors, and conferences, respectively. And in PathSelClus, we give each cluster one seed to start.We model the DBLP-four-area dataset as a 4-mode tensor, where each mode represents one object type. The 4 modes are author (A), paper (P), conference (C), and term (T), respectively. Actually, the sequence of the object types is insignificant. And each element of the tensor represents a gene-network in the heterogeneous information network. In the experiments, we set the learning rate for SOSClus to beη=1/(iter+1) and an optimized learning rate η=1/(iter+c) with c=1000125 for SGDClus. By running SOSClus, we accessorily obtain the solutions of OPT. So, we compare the experimental results of OPT, SGDClus, and SOSClus on the DBLP-four-area dataset with the three baseline methods. See the details in Tables 2, 3, and 4.Table 2
AC of experiments on DBLP-four-area dataset.
AC
OPT
SGDClus
SOSClus
NetClus
PathSelClus
FctClus
Paper
0.5882
0.8476
0.9007
0.7154
0.7551
0.7887
Author
0.5872
0.8486
0.9486
0.7177
0.7951
0.8008
Conference
1
0.99
1
0.9172
0.9950
0.9031
a
v
g
(
A
C
)
0.5892
0.8493
0.9477
0.7186
0.7951
0.8010Table 3
NMI of experiments on DBLP-four-area dataset.
NMI
OPT
SGDClus
SOSClus
NetClus
PathSelClus
FctClus
Paper
0.6557
0.6720
0.8812
0.5402
0.6142
0.7152
Author
0.6539
0.8872
0.8822
0.5488
0.6770
0.6012
Conference
1
0.8497
1
0.8858
0.9906
0.8248
a
v
g
(
N
M
I
)
0.6556
0.8778
0.8827
0.5503
0.6770
0.6050Table 4
Running time of experiments on DBLP-four-area dataset.
Running time (s)
OPT
SGDClus
SOSClus
NetClus
PathSelClus
FctClus
Paper
—
—
—
802.6
542.3
808.4
Author
—
—
—
743.7
681.1
774.9
Conference
—
—
—
658.4
629.3
669.8
Total time
672.6
432.4
818.4
2204.7
1852.7
2253.1In Tables2 and 3, SOSClus performs best on average AC and NMI, and SGDClus takes the second place. All methods achieve satisfactory AC and NMI on the conference, since there are only 20 conferences in the network. SGDClus takes the shortest running time, and OPT and SOSClus have an obvious advantage on running time compared with other baselines. The time complexity of SGDClus is Onnz(X)NK+(T-1)K2N, and the time complexity of SOSClus is Onnz(X)NK+(T-1)K2N+K3, where nnz(X) is the number of nonzero elements in X, that is, the number of gene-networks in the heterogeneous information network. We have nnz(X)<|P|≪|E|, K≪N, and T≪N. Compared with the time complexity of the three baselines, SGDClus and SOSClus have a little disadvantage. However, it is worth noting that the three baselines can only cluster one type of objects in the network in each running, while OPT, SGDClus, and SOSClus can obtain the clusters of all types of objects simultaneously by running once. This is the reason why only the total time is shown for OPT, SGDClus, and SOSClus in Table 4. Moreover, the total time of OPT, SGDClus, and SOSClus is on the same order of magnitude as the running time of other baselines for clustering each type of objects, which is consistent with the comparison of the time complexity.


## 5.3.1. Real-World Dataset Description

The experiments on the real-world dataset are used to compare the performance of the tensor CP decomposition clustering framework with other state-of-the-art methods.The real-world dataset extracted from the DBLP database is the DBLP-four-area dataset, which can be downloaded fromhttp://web.cs.ucla.edu/~yzsun/data/DBLP_four_area.zip. It is a four research-area subset of DBLP and is used in [2, 3, 12, 13, 15, 16, 18]. The four research areas in DBLP-four-area dataset are database (DB), data mining (DM), machine learning (ML), and information retrieval (IR), respectively. There are five representative conferences in each area. And all related authors, papers published in these conferences, and terms contained in these papers’ titles are included. The DBLP-four-area dataset contains 14,376 papers with 100 labeled, 14,475 authors with 4,057 labeled, 20 labeled conferences, and 8,920 terms. The density of the DBLP-four-area dataset is 9.01935×10-9, so we construct a 4-mode tensor with size of 14,376 × 14,475 × 20 × 8,920 and 334832 nonzero elements. We compare the performance of tensor CP decomposition clustering framework with several other methods on the labeled record in this dataset.


## 5.3.2. Comparative Methods

(i) NetClus (see [2]). An extended version of RankClus [1], which can deal with the network, follows the star network schema. The time complexity of NetClus for clustering each object type in each iteration is O(K|E|+(K2+K)N), where K is the number of clusters, |E| is the number of edges in the network, and N is the total number of objects in the network.(ii) PathSelClus (see [15, 16]). A clustering method based on the predefined metapath requires a user guide. In PathSelClus, the distance between the same type objects is measured by PathSim [3], and the method starts with the given seeds by user. The time complexity of PathSelClus for clustering each object type in each iteration is O((K+1)|P|+KN), where |P| is the number of metapath instances in the network. And, the time complexity of PathSim used by PathSelClus for clustering each object type is O(Nd), where d is the average degree of objects.(iii) FctClus (see [13]). It is a recently proposed clustering method for heterogeneous information networks. As with NetClus, the FctClus method can deal with networks following the star network schema. The time complexity of FctClus for clustering each object type in each iteration is O(K|E|+TKN).


## 5.3.3. Experimental Results

As the baseline methods can only deal with specific schema heterogeneous information networks, here we must construct different subnetworks for them. For NetClus and FctClus, the network is organized as a star network schema like in [2, 13], where the paper (P) is the centre type, and author (A), conference (C), and term (T) are the attribute types. For PathSelClus, we select the metapath of P-T-P, A-P-C-P-A, and C-P-T-P-C to cluster the papers, authors, and conferences, respectively. And in PathSelClus, we give each cluster one seed to start.We model the DBLP-four-area dataset as a 4-mode tensor, where each mode represents one object type. The 4 modes are author (A), paper (P), conference (C), and term (T), respectively. Actually, the sequence of the object types is insignificant. And each element of the tensor represents a gene-network in the heterogeneous information network. In the experiments, we set the learning rate for SOSClus to beη=1/(iter+1) and an optimized learning rate η=1/(iter+c) with c=1000125 for SGDClus. By running SOSClus, we accessorily obtain the solutions of OPT. So, we compare the experimental results of OPT, SGDClus, and SOSClus on the DBLP-four-area dataset with the three baseline methods. See the details in Tables 2, 3, and 4.Table 2
AC of experiments on DBLP-four-area dataset.
AC
OPT
SGDClus
SOSClus
NetClus
PathSelClus
FctClus
Paper
0.5882
0.8476
0.9007
0.7154
0.7551
0.7887
Author
0.5872
0.8486
0.9486
0.7177
0.7951
0.8008
Conference
1
0.99
1
0.9172
0.9950
0.9031
a
v
g
(
A
C
)
0.5892
0.8493
0.9477
0.7186
0.7951
0.8010Table 3
NMI of experiments on DBLP-four-area dataset.
NMI
OPT
SGDClus
SOSClus
NetClus
PathSelClus
FctClus
Paper
0.6557
0.6720
0.8812
0.5402
0.6142
0.7152
Author
0.6539
0.8872
0.8822
0.5488
0.6770
0.6012
Conference
1
0.8497
1
0.8858
0.9906
0.8248
a
v
g
(
N
M
I
)
0.6556
0.8778
0.8827
0.5503
0.6770
0.6050Table 4
Running time of experiments on DBLP-four-area dataset.
Running time (s)
OPT
SGDClus
SOSClus
NetClus
PathSelClus
FctClus
Paper
—
—
—
802.6
542.3
808.4
Author
—
—
—
743.7
681.1
774.9
Conference
—
—
—
658.4
629.3
669.8
Total time
672.6
432.4
818.4
2204.7
1852.7
2253.1In Tables2 and 3, SOSClus performs best on average AC and NMI, and SGDClus takes the second place. All methods achieve satisfactory AC and NMI on the conference, since there are only 20 conferences in the network. SGDClus takes the shortest running time, and OPT and SOSClus have an obvious advantage on running time compared with other baselines. The time complexity of SGDClus is Onnz(X)NK+(T-1)K2N, and the time complexity of SOSClus is Onnz(X)NK+(T-1)K2N+K3, where nnz(X) is the number of nonzero elements in X, that is, the number of gene-networks in the heterogeneous information network. We have nnz(X)<|P|≪|E|, K≪N, and T≪N. Compared with the time complexity of the three baselines, SGDClus and SOSClus have a little disadvantage. However, it is worth noting that the three baselines can only cluster one type of objects in the network in each running, while OPT, SGDClus, and SOSClus can obtain the clusters of all types of objects simultaneously by running once. This is the reason why only the total time is shown for OPT, SGDClus, and SOSClus in Table 4. Moreover, the total time of OPT, SGDClus, and SOSClus is on the same order of magnitude as the running time of other baselines for clustering each type of objects, which is consistent with the comparison of the time complexity.


## 6. Conclusion

In this paper, a tensor CP decomposition method for clustering heterogeneous information networks is presented. In tensor CP decomposition clustering framework, each type of objects in heterogeneous information network is modeled as one mode of tensor, and the gene-networks in the network are modeled as the elements in tensor. In other words, tensor CP decomposition clustering framework can model different types of objects and semantic relations in the heterogeneous information network without the restriction of network schema. In addition, two stochastic gradient descent algorithms, named SGDClus and SOSClus, are designed. SGDClus and SOSClus can cluster all types of objects and the gene-networks simultaneously by running once. The proposed algorithms outperformed other state-of-the-art clustering methods in terms of AC, NMI, and running time.



---

*Source: 2803091-2017-04-30.xml*