# Multityped Community Discovery in Time-Evolving Heterogeneous Information Networks Based on Tensor Decomposition

Authors: Jibing Wu; Lianfei Yu; Qun Zhang; Peiteng Shi; Lihua Liu; Su Deng; Hongbin Huang
Journal: Complexity
 (2018)

---

## Abstract

The heterogeneous information networks are omnipresent in real-world applications, which consist of multiple types of objects with various rich semantic meaningful links among them. Community discovery is an effective method to extract the hidden structures in networks. Usually, heterogeneous information networks are time-evolving, whose objects and links are dynamic and varying gradually. In such time-evolving heterogeneous information networks, community discovery is a challenging topic and quite more difficult than that in traditional static homogeneous information networks. In contrast to communities in traditional approaches, which only contain one type of objects and links, communities in heterogeneous information networks contain multiple types of dynamic objects and links. Recently, some studies focus on dynamic heterogeneous information networks and achieve some satisfactory results. However, they assume that heterogeneous information networks usually follow some simple schemas, such as bityped network and star network schema. In this paper, we propose a multityped community discovery method for time-evolving heterogeneous information networks with general network schemas. A tensor decomposition framework, which integrates tensor CP factorization with a temporal evolution regularization term, is designed to model the multityped communities and address their evolution. Experimental results on both synthetic and real-world datasets demonstrate the efficiency of our framework.


---

## Body

## 1. Introduction

Most artificial online systems, such as World Wide Web, social networks, and collaboration networks, can be represented as information networks, which describe the interactions and relationships between numerous objects, for example, hyperlinks between web pages, friendships between users, and coauthorships between researchers. The information network analysis is attracting an increasing number of researchers from a variety of fields, such as social science [1, 2], machine learning [3–5], and recommendation systems [6, 7]. Community discovery is one of the most significant focuses in information network analysis, which aims to discover interpretable hidden structures, patterns of interactions among objects, and their evolution along with time in such network. Although community detection in networks has been studied for many years, most existing approaches are designed to analyze static information network [1, 8, 9] and homogeneous information network [10–12]. That is, there is only one type of objects and links contained in the network, and the objects and links are not time-varying.However, in real-world scenarios, information networks are typically heterogeneous and time-evolving. In contrast to communities in traditional approaches, which only contain one type of static objects and links, communities in time-evolving heterogeneous information networks contain multiple types of dynamic objects and links. For example, the DBLP network, an open resource including most bibliographic information on computer science, is a typical time-evolving heterogeneous information network. DBLP network contains four types of objects: author (A), paper (P), venue (i.e., conference or journal) (V), and term (T). The links between different object types represent different semantic relationships, such as “an author wrote a paper” and “a paper published in a conference.” The most intriguing communities in DBLP are research areas, which contain the authors with similar research interests, the papers they wrote, the conferences they attended, and the terms they used. With the addition of new authors and new hot topics, the structures of communities are dynamic and varying gradually.Although the traditional community discovery methods can be applied to time-evolving heterogeneous information network by converting such network into a set of homogeneous information networks and aggregating the time-evolving objects and links along with all timestamps into one snapshot, the rich semantic relationships among different object types and the dynamic property of the communities are lost. In recent years, community discovery in time-evolving heterogeneous information networks has emerged as an outstanding challenge and attracted the attention of many researchers. For instance, Sun et al. used net-clusters [13] to describe the communities and proposed a Dirichlet Process Mixture Model based algorithm named Evo-NetClus [14, 15] to detect the communities in heterogeneous information networks with star network schema. In the star network schema, the links only appear between target objects and attribute objects.In this paper, we focus on community discovery in time-evolving heterogeneous information networks with general network schemas, which presents several challenges as follows:(i)
Heterogeneity: obviously, the communities in heterogeneous information networks are also heterogeneous, which contain multityped objects and links.(ii)
Time-varying: the communities are constantly changing, with new objects coming and old objects vanishing. We assume that the evolution of communities at two adjacent snapshots should be smooth.(iii)
Being suitable for general network schema: the network schema of a heterogeneous information network is often more complex than star network schema. The community discovery method should be able to handle the general network schema.(iv)
Online mode: although some offline frameworks can produce a global view of community evolution along time by capturing all historical information, online framework is more realistic.To overcome the aforementioned challenges, we propose a tensor decomposition framework for modeling the multityped communities and address their evolution in time-evolving heterogeneous information networks with general network schemas. Essentially, a time-evolving heterogeneous information network consists of a sequence of network snapshots. We model the time-evolving heterogeneous information network as a sequence of multiway arrays, that is, tensors. Tensor is a highly effective and veracious approach for modeling high-mode data, which can naturally express the complex structures and interactions in heterogeneous information networks. By integrating the tensor CP factorization with a temporal evolution regularization term, the multityped communities and their evolution along time can be formalized as a tensor decomposition problem. A second-order stochastic gradient descent algorithm is presented to solve the problem, and the experimental results on both synthetic and real-world datasets demonstrate the efficiency of our framework.The rest of this paper is organized as follows. In Section2, we discuss the related work on community discovery in time-evolving heterogeneous information networks. Section 3 formalizes the problem as tensor decomposition, which integrates tensor CP factorization with a temporal evolution regularization term. A second-order stochastic gradient descent algorithm is presented in Section 4. Section 5 discusses some implementation issues, including dead and new objects, online deployment, and time complexity analysis. The experimental results on both synthetic and real-world datasets are presented in Section 6. Finally, the conclusions are drawn in Section 7.


## 2. Related Work

Community discovery is a fundamental technique of information network analysis. Many creative methods for discovering communities in static and homogeneous network have been deployed in the past decades. Stochastic block model [16, 17] and mixed membership model [18] are powerful probabilistic community discovery models for analyzing static networks. These two models, however, lack capability of time-evolving networks and cannot be directly used for heterogeneous information networks.Tracking the evolution of communities [11, 19] takes the dynamic properties in time-evolving networks into consideration. A commonly used framework [20–22] is to apply the static community detection algorithms for each snapshot of the time-evolving networks and then generate the evolution of communities by computing the match between two adjacent snapshots. Another attempt to track community evolution in time-evolving networks is multiobjective optimization model [23–25], which integrates the measurement of community quality and temporal smoothness into a multiobjective cost function. Nevertheless, these methods are designed for homogeneous networks.Recently, the community discovery in heterogeneous information networks has become a hot topic. Tang et al. introduced the community evolution in multimode network and proposed a framework which partitioned the multimode network into a set of bityped networks [26, 27]. Sun et al. used net-clusters [13] to describe the communities and proposed Evo-NetClus [14, 15] to detect the communities automatically. However, the net-clusters and Evo-NetClus are only suitable for star network schema, where the links only appear between target objects and attribute objects.To analyze the heterogeneous information networks with general network schemas, tensor factorization offers a promising way for extracting hidden communities in such networks. Tensor is an effective expression of complicated and interpretable structures among different dimensions in heterogeneous information network. For instance, Lin et al. proposed MetaGraph Factorization [28, 29] to detect the communities from dynamic social networks. In addition, a tensor factorization based mixed membership framework [30] simulates the generation of communities as Dirichlet distribution, which can identify the communities automatically. However, this method needs to partition the heterogeneous network into four parts artificially and organize them as a 3-star network. Meanwhile, the 3-star count tensor must be converted to an orthogonal symmetric tensor. Thus the capability of this method to deal with time-evolving heterogeneous information networks could be degraded.Our prior works in [31–33] have also focused on clustering heterogeneous information networks based on tensor decomposition, which can cluster multityped objects simultaneously in heterogeneous information networks. However, these methods treat the heterogeneous information networks as static networks and integrate the time-evolving networks into one snapshot, which lose the dynamic properties among multityped objects and links.Another line related to our work is on the incremental tensor factorization [34]. Though tensor factorization has been widely studied in many domains, such as image processing [35] and computer vision [36], the incremental tensor factorization is still a challenging intellectual task [34]. Sun et al. proposed a general framework of incremental tensor analysis [34] for mining higher-order data streaming, which included three methods: dynamic tensor analysis, streaming tensor analysis, and window-based tensor analysis. Even though the higher-order data streaming can be effectively analyzed in such framework, the smooth evolution of latent patterns cannot be guaranteed.


## 3. Problem Formulation

Following the works by Sun et al. in [15] and our prior work [33], we first introduce some definitions of heterogeneous information networks and tensor construction from a given heterogeneous information network.Aheterogeneous information network [15] is a graph G=(V,E) consisting of more than one type of objects V or links E. Assume that V belongs to N object types V=V(n)n=1N, and E belongs to M link types E=R(m)m=1M. That is, in a heterogeneous information network, N>1 or M>1. Otherwise, the network becomes a homogeneous information network.TheV(n) indicates the set of objects from the nth type. We denote an arbitrary object in V(n) as vin(n), for in=1,2,…,In; n=1,2,…,N, where In is the number of objects in type V(n); that is, In=V(n). Thus, the total number of objects in the heterogeneous information network G is given by I=∑n=1NIn.Thenetwork schema [15] for a given heterogeneous information network G=(V,E) is a metatemplate that indicates the formation of object types V and link types E in the network. The network schema is denoted by SG={V,E}. In other words, G=(V,E) is an instance of SG={V,E}. For example, the star network schema shown in Figure 1 is a typical network schema, in which four types of objects are contained, that is, author, paper, venue, and term. In Figure 1, paper is target object, and the others are attribute objects. The feature of star network schema is that the links in the network only appear between target object and attribute objects.Figure 1
A typical star network schema extracted from DBLP network.Agene-network [33], denoted by ϕ, is a minimum instance of SG={V,E} in the set of subnetworks of G=(V,E). It is noteworthy that a gene-network is an integrated semantic relation in the heterogeneous information network, which is quite different from gene regulatory network in Bioinformatics [37]. For example, a gene-network in DBLP network, denoted by ϕ=({vi(A),vj(P),vl(V),vm(T)},{〈vi(A),vj(P)〉,〈vj(P),vl(V)〉,〈vj(P),vm(T)〉}), represents an integrated semantic relation; that is, “an author vi(A) writes a paper vj(P), which contains the term vm(T) and is published in the venue vl(V).” For simplicity, we can mark the gene-network ϕ by the subscripts of objects in ϕ, that is, ϕi,j,l,m.Following our prior work [33], a Nth order tensor X∈RI1×I2×⋯×IN can be constructed according to the distribution of gene-networks, where each mode of X represents one type of objects in the network G. An arbitrary element xi1i2⋯iN∈{0,1} is an indicator of whether the corresponding gene-network ϕi1,i2,…,iN exists, where in=1,2,…,In, for n=1,2,…,N, is the index of an object in type V(n).(1)xi1i2⋯iN=1,if∃ϕi1,i2,…,iN;0,otherwise.The time-evolving heterogeneous information networks can be segmented into anetwork sequence according to a series of snapshots. The heterogeneous information network associated with timestamp t can be denoted as G(t)=(V(t),E(t)); then the network sequence is GS=(G(1),G(2),…,G(t),…). Thereby, the tensor representation of the network sequence is X(1),X(2),…,X(t),…. Actually, X(t)∈{0,1}I1×I2×⋯×IN is the hyper-adjacency tensor of the given heterogeneous information network at the tth timestamp, which indicates the distribution of gene-networks.The community in heterogeneous information network is calledmultityped community, which is more complex than that in homogeneous information network. A multityped community is a set of gene-networks that share the same features and connect together. In other words, a multityped community contains all associated types of objects and links. As shown in Figure 2, the multityped communities about research areas in DBLP network consist of the authors with similar research interests, the papers they wrote, the conferences they attended, and the terms they used. In each multityped community, the authors, papers, venues, and terms are connected to each other and organized as gene-networks. In fact, the objects may belong to several multityped communities since some gene-networks coming from different multityped communities may share the same objects. For example, a famous scientist can cooperate with other researchers within different areas by publishing many interdisciplinary papers; that is, the famous scientist will be contained in many gene-networks across different multityped communities.Figure 2
An instance of multityped communities in DBLP network.The problem of multityped community discovery from such a network sequence can be decomposed into two subproblems: (A) detect the multityped communities in each network snapshot, and (B) model the evolution of multityped communities over time.(A) Multityped Community Discovery in Each Network Snapshot. Without loss of generality, we take the tth network snapshot G(t) as an example. Let {Ck(t)}k=1K denote K hidden multityped communities in the network G(t) and uin,k(n,t) represent the probability that the inth object in type V(n) belongs to the kth community at the tth timestamp. Denote(2)ukn,t=u1,kn,t,u2,kn,t,…,uIn,kn,t⊤∈RIn.Following our prior work [33], a multityped community can be represented as(3)Ckt=uk1,t∘uk2,t∘⋯∘ukN,t,where ∘ is the outer product of two vectors. Actually, the multityped community Ck(t) is a rank-one tensor with the same size of X(t). Equation (3) indicates the gene-networks and the probability of associated objects belonging to the kth community. Thereby, we can approximate X(t) through a sum of K rank-one tensors; that is,(4)Xt≈∑k=1KCkt=∑k=1Kuk1,t∘uk2,t∘⋯∘ukN,t.Obviously, (4) is a tensor CP factorization. Let factor matrix U(n,t)=u1(n,t),u2(n,t),…,uK(n,t)∈RIn×K be the latent community membership matrix for the nth type of objects at timestamp t, where n=1,2,…,N. We denote(5)U1,t,U2,t,…,UN,t≡∑k=1Kuk1,t∘uk2,t∘⋯∘ukN,t.By minimizing the Frobenius norm of the difference between X(t) and its CP approximation, the multityped community discovery in each network snapshot can be formulated as an optimization problem:(6)min12Xt-U1,t,U2,t,…,UN,tF2,s.t.∑k=1Kuin,kn,t=1,∀n,∀in,uin,kn,t∈0,1,∀n,∀in,∀k,∑in=1Inuin,kn,t>0,∀n,∀k,where in=1,2,…,In; n=1,2,…,N; and k=1,2,…,K. The first and second constraints in (6) guarantee that uin,k(n,t) is the probability. The last constraint in (6) ensures that each multityped community consists of all associated types of objects.(B) Multityped Community Evolution over Time. Equation (6) just performs the multityped community discovery at each timestamp independently and does not consider their smooth evolution at two adjacent snapshots. We denote the objective function in (6) as f(t); that is,(7)ft=12Xt-U1,t,U2,t,…,UN,tF2.In order to ensure that the evolution of the multityped communities is smooth, a temporal evolution regularization term g(t) is introduced.(8)gt=λ2∑n=1NUn,t-Un,t-1F2,where λ>0 is a temporally regularized parameter. Indeed, g(t) is a first-order Markov assumption, which forces the multityped communities at current timestamp to resemble that at previous snapshot.Denote the objective function as(9)Lt=ft+gt=12Xt-U1,t,U2,t,…,UN,tF2+λ2∑n=1NUn,t-Un,t-1F2.Therefore, the problem of multityped community discovery in time-evolving heterogeneous information networks can be formulated as(10)minU1,t,U2,t,…,UN,tLts.t.∑k=1Kuin,kn,t=1,∀n,∀in,uin,kn,t∈0,1,∀n,∀in,∀k,∑in=1Inuin,kn,t>0,∀n,∀k.Here,U(n,t-1)n=1N are constants at current timestamp t, which are solved at previous timestamp. When t=1, we have no a priori knowledge about the multityped communities. We set U(n,t=0)=0, for n=1,2,…,N. Thus, g(t=1) becomes(11)gt=1=λ2∑n=1NUn,tF2.It is worth noting that g(t=1) is also a Tikhonov regularization term [38], which ensures the sparsity of the factor matrices and makes the optimization solution easy to be found. Moreover, when t=1, problem (10) degrades into the same form as we proposed in [33]. That is, the work in [33] is the special case for static networks.


## 4. Algorithm

The stochastic gradient descent algorithm is an efficient tool for optimizing tensor factorization [33, 39]. However, the first-order stochastic gradient descent algorithm has a poor convergence speed near the optimal point. It has been proven that the second-order stochastic algorithm has not only a faster convergence speed but also better robustness with respect to the learning rate [33]. The SOSClus proposed in [33] is a second-order stochastic algorithm which has been well studied for the case of t=1 in (10), that is, static heterogeneous information networks. Here, we present a second-order stochastic gradient descent algorithm, named SOSComm, for the time-evolving case, which is an extension of SOSClus. In this section, some multilinear operators and tensor algebra for tensor factorization will be used, which can be found in [40].Whent>1, the snapshot of the current heterogeneous information network X(t) and the previous community membership matrices U(n,t-1)n=1N are known. To compute the factor matrix U(n,t), we can rewrite L(t) in (10) by matricization of X(t) along the nth mode. According to (7), (8), and (9), we have(12)Lnt=fnt+gnt,where(13)fnt=12Xnt-Un,t⊙/nU⊤F2,gnt=gt.The X(n)(t)∈RIn×∏m=1m≠nNIm is the matricization of X(t) along the nth mode, and the symbol ⊙ indicates the Khatri-Rao product of two matrices. Given two matrices A∈RI×K and B∈RJ×K, their Khatri-Rao product is a matrix of size IJ×K and defined by(14)A⊙B=a11b:,1a12b:,2⋯a1Kb:,Ka21b:,1a22b:,2⋯a2Kb:,K⋮⋮⋱⋮aI1b:,1aI2b:,2⋯aIKb:,K,where aik, i=1,2,…,I, k=1,2,…,K, is an element of A, and b:,k∈RJ, k=k=1,2,…,K, is a column of B. In particular, we denote the Khatri-Rao product of a series of matrices except U(n,t) as(15)⊙/nU=UN,t⊙⋯⊙Un+1,t⊙Un-1,t⊙⋯⊙U1,t.Since the partial derivative off(n)(t) with respect to U(n,t) has been given in [33], we introduce the result directly.(16)∂fnt∂Un,t=-Xnt⊙/nU+Un,tΓn,t,where(17)Γn,t≡⊙/nU⊤⊙/nU=U1,t⊤U1,t∗⋯∗Un-1,t⊤Un-1,t∗Un+1,t⊤Un+1∗⋯∗UN,t⊤UN,t,and symbol ∗ is Hadamard product, also named element-wise product of two matrices with the same dimension.The partial derivative ofg(n)(t) with respect to U(n,t) is(18)∂gnt∂Un,t=λ∂Un,t-Un,t-1F22∂Un,t=λ∂TrUn,t-Un,t-1Un,t-Un,t-1⊤2∂Un,t=λ∂TrUn,tUn,t⊤2∂Un,t-λ∂TrUn,tUn,t-1⊤∂Un,t+λ∂TrUn,t-1Un,t-1⊤2∂Un,t=λUn,t-Un,t-1.Therefore, the partial derivative ofL(n)(t) with respect to U(n,t) is given by(19)∂Lnt∂Un,t=-Xnt⊙/nU+Un,tΓn,t+λI-λUn,t-1,where I is a unit matrix. And the second-order partial derivative of L(n)(t) with respect to U(n,t) can be obtained as(20)∂2Lnt∂2Un,t=Γn,t+λI.Recalling the update rule of the second-order stochastic algorithm [33, 41], we have(21)Un,t⟵Un,t-η∂2Lnt∂2Un,t-1∂Lnt∂Un,t=ηXnt⊙/nU+λUn,t-1Γn,t+λI-1+1-ηUn,t,where η is named learning rate or step size with a positive number.Whent=1, (21) has the same form as SOSClus. That is, the SOSComm is an extension of SOSClus for time-evolving heterogeneous information networks. To satisfy the constraints in (10), the factor matrices derived by (21) should be normalized as(22)uin,kn,t⟵uin,kn,t∑k=1Kuin,kn,t.For the current networkG(t), based on the tensor representation X(t) and the previous community membership matrices U(n,t-1)n=1N, the alternating optimization can be used to update U(n,t) according to (21) and (22), while all other variables are fixed. The community membership matrices U(n,t)n=1N obtained by (21) and (22) are the approximations. We also need to recover the discrete community membership matrices from the approximations in some cases, which can be achieved by applying K-means to the factor matrices. Conveniently, we can simply assign each object to the multityped community which has the largest entry in the corresponding row of factor matrix. After that, the multityped communities consist of gene-networks that can be extracted according to (3). Therefore, the pseudocode of SOSComm is given in Algorithm 1.Algorithm 1:SOSComm.
Input: the tensor representation of the current network X ( t ), the number of multi-typed communities K, temporally regularization parameter λ, the community membership matrices for the previous network snapshot U ( n , t - 1 ) n = 1 N, and maximum iterations MaxIter. Output: community membership matrices for the current network snapshot U(n,t)n=1N and multi-typed communities Ck(t)k=1K. (1) Set  U(n,t)n=1N←U(n,t-1)n=1N; (2) Set iter←1; (3) repeat (4) for  n←1  to  N  do (5) Set η←1/(iter+1); (6) Update U(n,t) according to (21); (7) Normalize U(n,t) according to (22); (8) end for (9) Set iter←iter+1; (10) until  L(t) unchanged or iter=MaxIter (11) Recover the discrete community membership matrices from U(n,t)n=1N (optional). (12) Extract the multi-typed communities Ck(t)k=1K according to (3).


## 5. Implementation Issues

### 5.1. New Objects Coming and Old Objects Vanishing

In realistic scenarios, objects in time-evolving heterogeneous information networks have various lifecycles. With the lifecycles beginning and end, new objects are born and join the network while old objects die and leave. The framework designed above does not consider the various lifecycles of objects, which assumes that the objects in a network remain unchanged and keep active. Here, we discuss more realistic cases that new objects coming and old objects vanishing in a time-evolving heterogeneous information network.Note that the tensor representationX(t) is a distribution of gene-networks in the heterogeneous information network, whose elements indicate whether the gene-networks exist or not. If the lifecycle of a new object vIn+1(n) begins at the tth timestamp, it will join the network and become active. Since the size of U(n,t) becomes (In+1)×K and only the previous factor matrix U(n,t-1) is used to regularize the temporal smoothness, we can add an all-zero row to the corresponding position on U(n,t-1) when updating U(n,t).If the lifecycle of a specified objectvin(n) ends at the tth timestamp, it will not appear in any gene-network in the network. According to (1), x:,…,in,…,:=0. That is, each element in the hyperplane, which is perpendicular to the nth dimensionality and passes the inth point of the nth dimensionality in the tensor space, is zero. Therefore, we set all entries in the inth row of U(n,t) equal to zero; that is, uin,k(n,t)=0 for k=1,2,…,K. However, this operation makes the factor matrix U(n,t) dissatisfy the first constraint in (10). Since our framework is an approximation and the dead objects will never appear in any multityped community (according to (3)), we can loosen the first constraint in (10) as(23)∑k=1Kuin,kn,t≤1,∀n,∀in,which does not affect the performance of recovering the discrete community membership matrices from U(n,t)n=1N and extracting the multityped communities Ck(t)k=1K.


### 5.2. Online Deployment

The snapshots in the network sequence of time-evolving heterogeneous information networks are coming in a stream way, which makes the storage of the whole network sequence unrealistic. Fortunately, we only use the new network snapshot and the previous community membership matrices to update the model, which makes SOSComm easy to deploy online. However, three issues should be taken into account.Firstly, the initialization of factor matrices has a large impact on the efficiency of SOSComm. A good initialization may reduce the number of iterations significantly. In practice, previous community membership matrices served as the start when updating the current factor matrices is a good choice. That is, set(24)Un,tn=1N⟵Un,t-1n=1N,in the beginning of the algorithm. See line (1) in Algorithm 1.Secondly, the second-order stochastic gradient descent algorithm has a fast convergence speed [33, 41] with good initialization, which will be proven in the experiments in Section 6. And the factor matrices obtained by SOSComm are the approximations to community membership matrices. Therefore, we can set the maximum iteration to be a very small positive integer.Finally, the sparsity of heterogeneous information network should be used to speed up the calculation. According to (21), the primary computation cost for updating U(n,t) is calculating a series of Khatri-Rao products, that is, ⊙(/n)U. If we store all the elements of X(t) and calculate the Khatri-Rao product of the N-1 factor matrices orderly, it will be a very expensive calculation because the largest scale of intermediate results will reach K×∏n=1NIn. Actually, the heterogeneous information networks are usually very sparse; namely, a great amount of elements in tensor X are zeros. By considering X(n)(t)⊙(/n)U∈RIn×K as a whole, the elements of X(n)(t)⊙(/n)U are given by(25)Xnt⊙/nUin,k=∑iml=1l≠nNxin,∏l=1l≠nNil∏l=1l≠nNuil,kl,t.Obviously, when xin,∏l=1l≠nNil=0, we can directly set X(n)(t)⊙(/n)Uin,k=0; that is, the following calculation of Khatri-Rao products is unnecessary. Thus, by considering the sparsity, only nonzero elements in X need to be stored and calculated.


### 5.3. Time Complexity Analysis

The primary computation cost for updating the factor matrices in each iteration of SOSComm is calculating three part:X(n)(t)⊙(/n)U, Γ(n,t)+λI-1, and the product of them. Firstly, for calculating X(n)(t)⊙(/n)U, only nonzero elements in X need to be concerned. Therefore, the time complexity is O(nnz(X)InK), where nnz(X) is the number of nonzero elements in X and also is the total number of gene-networks in the network. Secondly, according to (17), since a series of matrix-matrix multiplications and Hadamard products are used to replace numerous Khatri-Rao products, calculating Γ(n,t) costs O((I-In)K2), where I=∑nIn is the total number of objects in the network. Thus, the time complexity for calculating the inverse matrix of Γ(n,t)+λI is O(((I-In)K2)+K3). Finally, the product of X(n)(t)⊙(/n)U+λU(n,t-1) and Γ(n,t)+λI-1 is a matrix-matrix multiplication, where X(n)(t)⊙(/n)U+λU(n,t-1)∈RIn×K and Γ(n,t)+λI-1∈RK×K, so, the time complexity is O(InK2).To summarize, the time complexity for SOSComm in each iteration isO(nnz(X)IK+NIK2+NK3), where nnz(X) is the total number of gene-networks, I is the total number of objects, N is the number of object types, and K is the number of multityped communities. Since K≪I and N≪I, the time complexity for SOSComm is nearly O(nnz(X)I).


## 5.1. New Objects Coming and Old Objects Vanishing

In realistic scenarios, objects in time-evolving heterogeneous information networks have various lifecycles. With the lifecycles beginning and end, new objects are born and join the network while old objects die and leave. The framework designed above does not consider the various lifecycles of objects, which assumes that the objects in a network remain unchanged and keep active. Here, we discuss more realistic cases that new objects coming and old objects vanishing in a time-evolving heterogeneous information network.Note that the tensor representationX(t) is a distribution of gene-networks in the heterogeneous information network, whose elements indicate whether the gene-networks exist or not. If the lifecycle of a new object vIn+1(n) begins at the tth timestamp, it will join the network and become active. Since the size of U(n,t) becomes (In+1)×K and only the previous factor matrix U(n,t-1) is used to regularize the temporal smoothness, we can add an all-zero row to the corresponding position on U(n,t-1) when updating U(n,t).If the lifecycle of a specified objectvin(n) ends at the tth timestamp, it will not appear in any gene-network in the network. According to (1), x:,…,in,…,:=0. That is, each element in the hyperplane, which is perpendicular to the nth dimensionality and passes the inth point of the nth dimensionality in the tensor space, is zero. Therefore, we set all entries in the inth row of U(n,t) equal to zero; that is, uin,k(n,t)=0 for k=1,2,…,K. However, this operation makes the factor matrix U(n,t) dissatisfy the first constraint in (10). Since our framework is an approximation and the dead objects will never appear in any multityped community (according to (3)), we can loosen the first constraint in (10) as(23)∑k=1Kuin,kn,t≤1,∀n,∀in,which does not affect the performance of recovering the discrete community membership matrices from U(n,t)n=1N and extracting the multityped communities Ck(t)k=1K.


## 5.2. Online Deployment

The snapshots in the network sequence of time-evolving heterogeneous information networks are coming in a stream way, which makes the storage of the whole network sequence unrealistic. Fortunately, we only use the new network snapshot and the previous community membership matrices to update the model, which makes SOSComm easy to deploy online. However, three issues should be taken into account.Firstly, the initialization of factor matrices has a large impact on the efficiency of SOSComm. A good initialization may reduce the number of iterations significantly. In practice, previous community membership matrices served as the start when updating the current factor matrices is a good choice. That is, set(24)Un,tn=1N⟵Un,t-1n=1N,in the beginning of the algorithm. See line (1) in Algorithm 1.Secondly, the second-order stochastic gradient descent algorithm has a fast convergence speed [33, 41] with good initialization, which will be proven in the experiments in Section 6. And the factor matrices obtained by SOSComm are the approximations to community membership matrices. Therefore, we can set the maximum iteration to be a very small positive integer.Finally, the sparsity of heterogeneous information network should be used to speed up the calculation. According to (21), the primary computation cost for updating U(n,t) is calculating a series of Khatri-Rao products, that is, ⊙(/n)U. If we store all the elements of X(t) and calculate the Khatri-Rao product of the N-1 factor matrices orderly, it will be a very expensive calculation because the largest scale of intermediate results will reach K×∏n=1NIn. Actually, the heterogeneous information networks are usually very sparse; namely, a great amount of elements in tensor X are zeros. By considering X(n)(t)⊙(/n)U∈RIn×K as a whole, the elements of X(n)(t)⊙(/n)U are given by(25)Xnt⊙/nUin,k=∑iml=1l≠nNxin,∏l=1l≠nNil∏l=1l≠nNuil,kl,t.Obviously, when xin,∏l=1l≠nNil=0, we can directly set X(n)(t)⊙(/n)Uin,k=0; that is, the following calculation of Khatri-Rao products is unnecessary. Thus, by considering the sparsity, only nonzero elements in X need to be stored and calculated.


## 5.3. Time Complexity Analysis

The primary computation cost for updating the factor matrices in each iteration of SOSComm is calculating three part:X(n)(t)⊙(/n)U, Γ(n,t)+λI-1, and the product of them. Firstly, for calculating X(n)(t)⊙(/n)U, only nonzero elements in X need to be concerned. Therefore, the time complexity is O(nnz(X)InK), where nnz(X) is the number of nonzero elements in X and also is the total number of gene-networks in the network. Secondly, according to (17), since a series of matrix-matrix multiplications and Hadamard products are used to replace numerous Khatri-Rao products, calculating Γ(n,t) costs O((I-In)K2), where I=∑nIn is the total number of objects in the network. Thus, the time complexity for calculating the inverse matrix of Γ(n,t)+λI is O(((I-In)K2)+K3). Finally, the product of X(n)(t)⊙(/n)U+λU(n,t-1) and Γ(n,t)+λI-1 is a matrix-matrix multiplication, where X(n)(t)⊙(/n)U+λU(n,t-1)∈RIn×K and Γ(n,t)+λI-1∈RK×K, so, the time complexity is O(InK2).To summarize, the time complexity for SOSComm in each iteration isO(nnz(X)IK+NIK2+NK3), where nnz(X) is the total number of gene-networks, I is the total number of objects, N is the number of object types, and K is the number of multityped communities. Since K≪I and N≪I, the time complexity for SOSComm is nearly O(nnz(X)I).


## 6. Experiments and Results

In this section, the proposed SOSComm is evaluated on both synthetic and real-world datasets. We demonstrate the efficiency of SOSComm for multityped community discovery in time-evolving heterogeneous information networks with general network schemas and further compare the performances with several other state-of-the-art community discovery methods. The experiments are simulated by MATLAB R2015a (version 8.5.0, 64-bit), with the MATLAB Tensor Toolbox (version 2.6,http://www.sandia.gov/~tgkolda/TensorToolbox/). The code and datasets used in experiments are available online https://github.com/tianshuilideyu/SOSComm.


### 6.1. Experiments on Synthetic Datasets

#### 6.1.1. Dataset Description

Typically, the real-world heterogeneous information networks are often without ground-truth of community membership. Furthermore, due to the large scale and sparsity, it is impossible to manually assign the community labels to objects in a real-world network. Therefore, several synthetic networks with detailed community structures are resorted to demonstrate the effectiveness of SOSComm.We construct four synthetic networks with different parameters as the initial networks, that is, the network snapshots att=1. In order to obtain more realistic synthetic networks, the interactions between objects are assumed to follow Zipf’s law (see details online: https://en.wikipedia.org/wiki/Zipf’s_law), which denotes the distribution of gene-networks in networks. The parameters are as follows, and the details of the synthetic networks at the first timestamp are shown in Table 1:(i)
N is the number of object types in networks.(ii)
K is the number of multityped communities.(iii)
S is the network scale, and S=I1×I2×⋯×IN.(iv)
D is the tensor density, and D=nnz(X)/S.Table 1
The synthetic datasets.
Synthetic datasets N K S D Syn1 2 2 1 M = 1000 × 1000 0.1% Syn2 2 4 10 M = 1000 × 10000 0.01% Syn3 4 2 100 M = 100 × 100 × 100 × 100 0.1% Syn4 4 4 1000 M = 100 × 100 × 100 × 1000 0.01%To simulate the smooth evolution of multityped communities, each synthetic network is evolved into a network sequence with 10 timestamps. Within each evolution, a percentage (from 5% to 10%) of the objects from each type change their community memberships by interacting with other objects in different communities randomly at each timestamp.For completeness, we also randomly generate from 10% to 15% new objects coming and old objects vanishing in Syn4 at each timestamp. With new objects coming and interacting with other objects, many new gene-networks are generated. Meanwhile, with old objects vanishing, they will not appear in any gene-network in the network.


#### 6.1.2. Comparative Methods and Experimental Setting

The performances of SOSComm on synthetic networks are compared with two state-of-the-art baselines:(1)
SOSClus (see [33]): an offline clustering framework for static heterogeneous information networks, which treats every snapshot in the network sequence independently without the temporal evolution regularization term.(2)
CEMNTR (see [26, 27]): a framework of community evolution in multimode network with temporal evolution regularization term, denoted as CEMNTR. CEMNTR partitions the multimode network into a set of bityped networks and detects communities in each bityped network via block model approximation with temporal regularization.Both the baselines and SOSComm share the same stopping conditions; that is, the change of corresponding objective function is less than10-6 and the maximum iterations MaxIter=10000. The experiments in our prior work [33] have shown that the second-order stochastic gradient descent has good robustness with respect to the learning rate. Hence, we set the learning rate η=1/(iter+1) for both SOSClus and SOSComm. As CEMNTR needs to partition the networks into a set of bityped networks, we divide each network snapshot in Syn3 and Syn4 into 3 bityped networks and construct the adjacent matrices for each pair of object types.Since the ground-truth of the community structures in the synthetic networks is known, we adopt the Normalized Mutual Information (NMI) [42] as the metric to evaluate the performances. NMI is a measurement of mutual dependence information between multityped community membership and the ground-truth, which ranges from 0 to 1. The larger the value of NMI is, the better the result is.


#### 6.1.3. Experimental Results

We set the temporally regularized parameterλ=1.0 for SOSComm and CEMNTR. Since the number of multicommunities K is an important parameter for SOSComm, we evaluate the performance with different K on the 4 synthetic networks firstly. With K varying from 1 to 10, the average values of NMIs of SOSComm on the 4 synthetic networks are shown in Figure 3. Obviously, on Syn1 and Syn3, SOSComm performs best when K=2, and on Syn2 and Syn4, SOSComm performs best when K=4. The results are consistent with the real setting for synthetic networks in Table 1; that is, the real number of multityped communities is 2 for Syn1 and Syn3, and 4 for Syn2 and Syn4. With the widening gap between K and the real number of multityped communities, SOSComm performs worse and worse in all synthetic networks.Figure 3
The performances of SOSComm on 4 synthetic networks with differentK.In the following experiments, we fixK as the real number of multityped communities in each synthetic network. The comparison of NMIs for SOSComm and two baselines on the 4 synthetic networks is shown in Figure 4. In Figure 4, each subgraph shows NMIs of the three methods on each network snapshot in corresponding synthetic network. The tendency of the NMI curve turns out the ability of tracing communities evolution. From the 4 subgraphs in Figure 4, we find that SOSComm performs best on NMI and tracing communities evolution. Since no knowledge of previous community membership at the first timestamp is available, SOSComm and SOSClus share the same starting point on the 4 synthetic networks. Moreover, with the time evolving, SOSComm can trace the evolution of multityped communities closely, while the NMIs of SOSClus and CEMNTR on the 4 synthetic networks decline steadily.Figure 4
The comparison of the performances of NMIs for SOSComm, SOSClus, and CEMNTR at each timestamp on the 4 synthetic networks.
(a)
Experimental results on Syn1 (b)
Experimental results on Syn2 (c)
Experimental results on Syn3 (d)
Experimental results on Syn4As shown in Figure4(d), with the new objects coming and old objects vanishing in the network at each timestamp, the NMIs of SOSClus and CEMNTR on Syn4 drop sharply; in detail, NMI of SOSClus drops from 1.0 to 0.2865 and NMI of CEMNTR drops from 0.8099 to 0.0976. Meanwhile, NMI of SOSComm keeps smooth relatively. This reveals that SOSComm can handle the time-evolving heterogeneous information networks with new objects coming and old objects vanishing effectively.The convergence speed is also a significant focus for studying the performances of our framework. We run SOSComm on Syn3 and Syn4 withλ=1.0 and analyze the changes of the objective function L(t) between adjacent iterations, denoted as error=|Liter+1(t)-Liter(t)|/Liter(t), for all timestamps in the two network sequences. When the errors almost keep constant, the algorithm converges. Figure 5 shows the experimental results of error, where each subgraph displays the convergence speed of SOSComm on Syn3 and Syn4 at corresponding timestamp. In Figure 5, we can see that SOSComm converges quickly on both Syn3 and Syn4 at all timestamps. Particularly, SOSComm has converged when the iterations are less than 10 in all subgraphs, which is a good property for online deployment.Figure 5
The changes of the objective function between adjacent iterations for SOSComm on Syn3 and Syn4 at each timestamp.
(a)
t = 1 (b)
t = 2 (c)
t = 3 (d)
t = 4 (e)
t = 5 (f)
t = 6 (g)
t = 7 (h)
t = 8 (i)
t = 9 (j)
t = 10The temporally regularized parameterλ in (10) controls the impact of historical information on the current community distribution. The larger the λ is, the more significant the impact is. To study the influence of temporally regularized parameter λ tuning, we apply SOSComm on Syn4 with λ varying from 0.1 to 100. The average values of NMIs and iterations on all network snapshots over all timestamps are shown in Figure 6, where the coordinates of x-axis are based on a logarithmic transformation. As shown in Figure 6, the NMIs and iterations maintain the satisfactory results when λ is less than 10. However, when λ>10 and keeps increasing, the performances of NMIs and iterations become worse quickly. That is, the historical information dominates and the algorithm consumes more resources to smooth the time-evolving communities, when the temporally regularized parameter λ is too large. Certainly, the temporally regularized parameter contributes to multityped communities detection by considering the temporal information when λ ranges from 0.1 to 10.Figure 6
The average values of NMIs and iterations of SOSComm on Syn4 with differentλs.To conclude, the experiments on the 4 time-evolving synthetic networks demonstrate that SOSComm outperforms the SOSClus and CEMNTR. With a fast convergence speed, SOSComm can trace the evolution of multityped communities in the 4 synthetic networks accurately. In particular, on Syn4, with the new objects coming and old objects vanishing in the network, SOSComm can detect the multityped communities evolution well, while the performances of SOSClus and CEMNTR deteriorate rapidly as time goes on. The performances of NMIs for SOSComm on the 4 synthetic networks with differentK show that SOSComm is sensitive to K. The K is closer to the real number of multityped of communities, so SOSComm performs better. Moreover, when λ ranges from 0.1 to 10, the performances of SOSComm are satisfactory.


### 6.2. Experiments on Real-World Dataset

#### 6.2.1. Dataset Description

Here, we compare the performances of SOSComm with the baselines on real-world dataset. The real-world dataset is a 25-year DBLP network sequence, which is collected by Tang et al. [27] and available online: http://www.leitang.net/heterogeneous_network.html. In the 25-year DBLP dataset, the papers published from 1980 to 2004 are extracted, and all related authors, terms (words contained in the papers’ titles), and venues (the conferences or journals the papers published in) are included. The low frequency used and stop words have been abandoned. In the real-world dataset, the 25-year DBLP network is segmented into 25 network snapshots according to the publication year associated with each paper. After that, we construct a 4-mode tensor for each network snapshot, where the 4 modes of the tensors represent the papers, authors, venues, and terms, respectively. Table 2 shows the number of papers, authors, venues, terms, and gene-networks in each network snapshot of the 25-year DBLP dataset. Meanwhile, each row in Table 2 indicates the size of the corresponding tensor. For example, the size of the tensor for year=2004 is 69,021 × 105,292 × 1,238 × 9,153, with 1,182,458 nonzero elements. It is worth noting that there is no ground-truth of community memberships in the real-world dataset, because it is difficult and unrealistic to label the massive objects in a real-world network automatically or even manually.Table 2
The details of the real-world dataset.
Year Type Paper Author Venue Term Gene-network Number 1980 2783 3400 80 2994 21814 1981 3693 4630 95 3511 31156 1982 3525 4418 89 3451 30228 1983 3872 5066 100 3742 33790 1984 4299 5674 106 3917 38060 1985 5076 6630 124 4238 45081 1986 5531 7539 145 4505 51625 1987 6368 8871 170 4929 60488 1988 7522 10415 195 5169 72363 1989 8665 11856 213 5562 85161 1990 10332 14801 243 6005 105975 1991 11435 16107 268 6134 116875 1992 13654 19546 323 6609 147849 1993 15183 22130 363 6870 171968 1994 16860 25160 380 7197 201015 1995 18532 27737 418 7469 225549 1996 21611 31828 472 7828 266749 1997 25492 38684 551 8233 338227 1998 26133 40595 584 8352 351770 1999 29082 45201 634 8515 401446 2000 34500 53735 718 8721 492333 2001 40402 62770 852 8948 601616 2002 47322 72126 957 9059 720623 2003 60833 92843 1144 9198 978413 2004 69021 105292 1238 9153 1182458


#### 6.2.2. Evaluation Metrics

Different from the synthetic networks, NMI cannot be adopted as the metric to evaluate the performances due to the lack of ground-truth of community membership in the real-world dataset. In fact, to evaluate the detection of community evolution is challenging. Alternatively, we extend the modularityQ [43, 44], a widely used metric of measuring the quality of communities in a homogenous network, to the high-order tensor space, so that the extended modularity Q is suitable for the heterogeneous information networks. In a network, the high modularity reflects dense connections among vertices within a community and sparse connections among vertices across different communities.Following the work of [44], modularity Q is defined as the fraction of the edges that fall within the given communities minus the expected fraction of randomization of these edges with the fixed degree of each vertex. We directly give the calculation of modularity Q in [44]:(26)Q=12e∑v,wavw-dvdw2eδv,w,where e is the total number of edges in the whole network, avm is an element of adjacent matrix A∈{0,1}N×N, and dv denotes the degree of vertices v. The function δ(v,w) indicates whether the vertices v and w are in the same community or not. The value of Q falls in the range [-0.5,1), which can be negative. In practice, when the value of Q ranges from 0.3 to 0.7, the quality of community is satisfactory.Without loss of generality, we take the heterogeneous information network at thetth timestamp as an example and ignore the superscript of timestamp in the following discussion. In our framework, each nonzero element of tensor X maps a gene-network in the given heterogeneous information network, while the outer product of a series of the kth column in the corresponding factor matrices indicates the distribution of the kth multityped community for gene-networks; that is, Ck=uk(1)∘uk(2)∘⋯∘uk(N). In other words, a gene-network is the minimum unit in our framework. Then, a new graph Φ reflecting the connections of gene-networks is formed, in which each gene-network in the original heterogeneous information network is treated as a vertex. In other words, the vertices in Φ are the gene-networks in original heterogeneous information network. If two vertices ϕ and φ are connected or an edge between ϕ and φ exists in Φ, this means that the gene-networks denoted by ϕ and φ in the original heterogeneous information network share one or more same objects.Accordingly, the modularityQ can be used to evaluate the quality of communities in Φ. Since the vertices in Φ are in one-to-one correspondence with gene-networks in original heterogeneous information network, the multityped communities Ck|k=1K consisting of gene-networks in original heterogeneous information network are also the partition of communities in Φ. Let J denote the total number of vertices in Φ; that is, J=nnz(X). The adjacent matrix of Φ becomes A∈{0,1}J×J, whose element aϕφ indicates whether ϕ connects to φ or not. Here, the adjacent matrix A is a symmetric matrix with all zeros diagonal; that is, aϕφ=aφϕ and aϕϕ=0.Thereby, the total number of edges inΦ is e=1/2∑ϕφaϕφ, and the degree of ϕ is dϕ=∑φaϕφ. According to (26), the extended modularity Q (also denoted by Q) can be calculated by(27)Q=12e∑ϕ,φaϕφ-dϕdφ2eδϕ,φ.If ϕ and φ are in the same multityped community, δ(ϕ,φ)=1. Otherwise, δ(ϕ,φ)=0.


#### 6.2.3. Experimental Results

Firstly, The baselines and SOSComm are deployed in offline mode in order to learn their best performances on multityped communities discovery. That is, the baselines and SOSComm are iterated on each network snapshot until they converge. In the offline mode, we share the same comparative methods and experimental setting as that in experiments on synthetic networks; that is, the change of corresponding objective function is less than10-6 and the maximum iterations MaxIter=10000. We set the temporally regularized parameter λ=1.0 for SOSComm and CEMNTR.To seek out the suitable number of multityped communities, we perform the SOSComm on the 25-year DBLP network with differentK. Figure 7 gives the average values of modularity Q on the 25 timestamps with K varying from 1 to 50. In Figure 7, when 14≤K≤31, Q≥0.3. Though the average values of modularity Q are almost equal when K=18,19,20,21,22, and 23, the maximum of Q is obtained when K=20. Therefore, in the following experiments, the number of multityped communities in the 25-year DBLP network is fixed to 20.Figure 7
The performances of SOSComm on the 25-year DBLP network with differentK.The comparison of modularityQ for the baselines and SOSComm in offline mode is shown in Figure 8. SOSComm performs the best modularity Q on each network snapshot. With the time evolving, SOSComm traces the evolution of multityped communities more and more closely, while the modularity Q of SOSClus keeps low all the time and the modularity Q of CEMNTR declines steadily.Figure 8
The comparison of modularityQ for SOSComm, SOSClus, and CEMNTR in offline mode.Secondly, we learn the performances of SOSComm in online mode. In the online mode, the maximum iteration is limited to 5. The comparison of modularityQ for the baselines and SOSComm in online mode is shown in Figure 9. Although the modularity Q of SOSComm has declined relatively to that in offline mode, its performance is still the best.Figure 9
The comparison of modularityQ for SOSComm, SOSClus, and CEMNTR in online mode.In addition, Figure10 shows the comparison of modularity Q for SOSComm in offline mode and online mode. In Figure 10, we can find that the performance of SOSComm in online mode is not worse than that in offline mode. Before 2000, the two curves almost overlap. With the explosive growth of the tensors in the last 5 years, the modularity Q of SOSComm in online mode is slightly less than that in offline mode. Table 3 summarizes the running time of the baselines and SOSComm in online mode. CEMNTR and SOSComm, as shown in Table 3, yield the obvious advantages. Most of the time, SOSComm is the fastest.Table 3
The running time of the three methods on the real-world dataset in online mode.
Year Method SOSClus CEMNTR SOSComm Time (s) 1980 10.27 0.9472 1.59 1981 6.14 1.4157 1.24 1982 6.10 1.41 1.25 1983 6.19 1.53 1.33 1984 6.07 1.63 1.36 1985 6.20 1.76 1.35 1986 6.27 1.98 1.35 1987 6.36 2.16 1.66 1988 6.38 2.66 1.37 1989 6.55 2.92 3.10 1990 6.75 3.90 6.73 1991 6.85 3.49 5.46 1992 8.31 4.18 4.13 1993 8.83 4.70 7.37 1994 9.48 6.08 4.34 1995 11.34 5.82 12.06 1996 12.66 12.12 8.26 1997 14.02 14.00 4.92 1998 17.94 14.52 8.31 1999 20.36 9.02 5.19 2000 33.79 11.31 19.50 2001 24.96 12.87 12.26 2002 27.54 49.05 15.52 2003 28.93 19.18 17.90 2004 36.71 21.94 10.67Figure 10
The comparison of modularityQ for SOSComm in offline mode and online mode.To summarize, the experiments on the 25-year DBLP dataset show that SOSComm outperforms the SOSClus and CEMNTR. With a larger modularityQ, SOSComm can detect the multityped communities and trace their evolution in the 25-year DBLP network. In particular, the experimental results of online mode demonstrate that SOSComm has the best performances on modularity Q and running time. That is, SOSComm has a good property of online deployment.


## 6.1. Experiments on Synthetic Datasets

### 6.1.1. Dataset Description

Typically, the real-world heterogeneous information networks are often without ground-truth of community membership. Furthermore, due to the large scale and sparsity, it is impossible to manually assign the community labels to objects in a real-world network. Therefore, several synthetic networks with detailed community structures are resorted to demonstrate the effectiveness of SOSComm.We construct four synthetic networks with different parameters as the initial networks, that is, the network snapshots att=1. In order to obtain more realistic synthetic networks, the interactions between objects are assumed to follow Zipf’s law (see details online: https://en.wikipedia.org/wiki/Zipf’s_law), which denotes the distribution of gene-networks in networks. The parameters are as follows, and the details of the synthetic networks at the first timestamp are shown in Table 1:(i)
N is the number of object types in networks.(ii)
K is the number of multityped communities.(iii)
S is the network scale, and S=I1×I2×⋯×IN.(iv)
D is the tensor density, and D=nnz(X)/S.Table 1
The synthetic datasets.
Synthetic datasets N K S D Syn1 2 2 1 M = 1000 × 1000 0.1% Syn2 2 4 10 M = 1000 × 10000 0.01% Syn3 4 2 100 M = 100 × 100 × 100 × 100 0.1% Syn4 4 4 1000 M = 100 × 100 × 100 × 1000 0.01%To simulate the smooth evolution of multityped communities, each synthetic network is evolved into a network sequence with 10 timestamps. Within each evolution, a percentage (from 5% to 10%) of the objects from each type change their community memberships by interacting with other objects in different communities randomly at each timestamp.For completeness, we also randomly generate from 10% to 15% new objects coming and old objects vanishing in Syn4 at each timestamp. With new objects coming and interacting with other objects, many new gene-networks are generated. Meanwhile, with old objects vanishing, they will not appear in any gene-network in the network.


### 6.1.2. Comparative Methods and Experimental Setting

The performances of SOSComm on synthetic networks are compared with two state-of-the-art baselines:(1)
SOSClus (see [33]): an offline clustering framework for static heterogeneous information networks, which treats every snapshot in the network sequence independently without the temporal evolution regularization term.(2)
CEMNTR (see [26, 27]): a framework of community evolution in multimode network with temporal evolution regularization term, denoted as CEMNTR. CEMNTR partitions the multimode network into a set of bityped networks and detects communities in each bityped network via block model approximation with temporal regularization.Both the baselines and SOSComm share the same stopping conditions; that is, the change of corresponding objective function is less than10-6 and the maximum iterations MaxIter=10000. The experiments in our prior work [33] have shown that the second-order stochastic gradient descent has good robustness with respect to the learning rate. Hence, we set the learning rate η=1/(iter+1) for both SOSClus and SOSComm. As CEMNTR needs to partition the networks into a set of bityped networks, we divide each network snapshot in Syn3 and Syn4 into 3 bityped networks and construct the adjacent matrices for each pair of object types.Since the ground-truth of the community structures in the synthetic networks is known, we adopt the Normalized Mutual Information (NMI) [42] as the metric to evaluate the performances. NMI is a measurement of mutual dependence information between multityped community membership and the ground-truth, which ranges from 0 to 1. The larger the value of NMI is, the better the result is.


### 6.1.3. Experimental Results

We set the temporally regularized parameterλ=1.0 for SOSComm and CEMNTR. Since the number of multicommunities K is an important parameter for SOSComm, we evaluate the performance with different K on the 4 synthetic networks firstly. With K varying from 1 to 10, the average values of NMIs of SOSComm on the 4 synthetic networks are shown in Figure 3. Obviously, on Syn1 and Syn3, SOSComm performs best when K=2, and on Syn2 and Syn4, SOSComm performs best when K=4. The results are consistent with the real setting for synthetic networks in Table 1; that is, the real number of multityped communities is 2 for Syn1 and Syn3, and 4 for Syn2 and Syn4. With the widening gap between K and the real number of multityped communities, SOSComm performs worse and worse in all synthetic networks.Figure 3
The performances of SOSComm on 4 synthetic networks with differentK.In the following experiments, we fixK as the real number of multityped communities in each synthetic network. The comparison of NMIs for SOSComm and two baselines on the 4 synthetic networks is shown in Figure 4. In Figure 4, each subgraph shows NMIs of the three methods on each network snapshot in corresponding synthetic network. The tendency of the NMI curve turns out the ability of tracing communities evolution. From the 4 subgraphs in Figure 4, we find that SOSComm performs best on NMI and tracing communities evolution. Since no knowledge of previous community membership at the first timestamp is available, SOSComm and SOSClus share the same starting point on the 4 synthetic networks. Moreover, with the time evolving, SOSComm can trace the evolution of multityped communities closely, while the NMIs of SOSClus and CEMNTR on the 4 synthetic networks decline steadily.Figure 4
The comparison of the performances of NMIs for SOSComm, SOSClus, and CEMNTR at each timestamp on the 4 synthetic networks.
(a)
Experimental results on Syn1 (b)
Experimental results on Syn2 (c)
Experimental results on Syn3 (d)
Experimental results on Syn4As shown in Figure4(d), with the new objects coming and old objects vanishing in the network at each timestamp, the NMIs of SOSClus and CEMNTR on Syn4 drop sharply; in detail, NMI of SOSClus drops from 1.0 to 0.2865 and NMI of CEMNTR drops from 0.8099 to 0.0976. Meanwhile, NMI of SOSComm keeps smooth relatively. This reveals that SOSComm can handle the time-evolving heterogeneous information networks with new objects coming and old objects vanishing effectively.The convergence speed is also a significant focus for studying the performances of our framework. We run SOSComm on Syn3 and Syn4 withλ=1.0 and analyze the changes of the objective function L(t) between adjacent iterations, denoted as error=|Liter+1(t)-Liter(t)|/Liter(t), for all timestamps in the two network sequences. When the errors almost keep constant, the algorithm converges. Figure 5 shows the experimental results of error, where each subgraph displays the convergence speed of SOSComm on Syn3 and Syn4 at corresponding timestamp. In Figure 5, we can see that SOSComm converges quickly on both Syn3 and Syn4 at all timestamps. Particularly, SOSComm has converged when the iterations are less than 10 in all subgraphs, which is a good property for online deployment.Figure 5
The changes of the objective function between adjacent iterations for SOSComm on Syn3 and Syn4 at each timestamp.
(a)
t = 1 (b)
t = 2 (c)
t = 3 (d)
t = 4 (e)
t = 5 (f)
t = 6 (g)
t = 7 (h)
t = 8 (i)
t = 9 (j)
t = 10The temporally regularized parameterλ in (10) controls the impact of historical information on the current community distribution. The larger the λ is, the more significant the impact is. To study the influence of temporally regularized parameter λ tuning, we apply SOSComm on Syn4 with λ varying from 0.1 to 100. The average values of NMIs and iterations on all network snapshots over all timestamps are shown in Figure 6, where the coordinates of x-axis are based on a logarithmic transformation. As shown in Figure 6, the NMIs and iterations maintain the satisfactory results when λ is less than 10. However, when λ>10 and keeps increasing, the performances of NMIs and iterations become worse quickly. That is, the historical information dominates and the algorithm consumes more resources to smooth the time-evolving communities, when the temporally regularized parameter λ is too large. Certainly, the temporally regularized parameter contributes to multityped communities detection by considering the temporal information when λ ranges from 0.1 to 10.Figure 6
The average values of NMIs and iterations of SOSComm on Syn4 with differentλs.To conclude, the experiments on the 4 time-evolving synthetic networks demonstrate that SOSComm outperforms the SOSClus and CEMNTR. With a fast convergence speed, SOSComm can trace the evolution of multityped communities in the 4 synthetic networks accurately. In particular, on Syn4, with the new objects coming and old objects vanishing in the network, SOSComm can detect the multityped communities evolution well, while the performances of SOSClus and CEMNTR deteriorate rapidly as time goes on. The performances of NMIs for SOSComm on the 4 synthetic networks with differentK show that SOSComm is sensitive to K. The K is closer to the real number of multityped of communities, so SOSComm performs better. Moreover, when λ ranges from 0.1 to 10, the performances of SOSComm are satisfactory.


## 6.1.1. Dataset Description

Typically, the real-world heterogeneous information networks are often without ground-truth of community membership. Furthermore, due to the large scale and sparsity, it is impossible to manually assign the community labels to objects in a real-world network. Therefore, several synthetic networks with detailed community structures are resorted to demonstrate the effectiveness of SOSComm.We construct four synthetic networks with different parameters as the initial networks, that is, the network snapshots att=1. In order to obtain more realistic synthetic networks, the interactions between objects are assumed to follow Zipf’s law (see details online: https://en.wikipedia.org/wiki/Zipf’s_law), which denotes the distribution of gene-networks in networks. The parameters are as follows, and the details of the synthetic networks at the first timestamp are shown in Table 1:(i)
N is the number of object types in networks.(ii)
K is the number of multityped communities.(iii)
S is the network scale, and S=I1×I2×⋯×IN.(iv)
D is the tensor density, and D=nnz(X)/S.Table 1
The synthetic datasets.
Synthetic datasets N K S D Syn1 2 2 1 M = 1000 × 1000 0.1% Syn2 2 4 10 M = 1000 × 10000 0.01% Syn3 4 2 100 M = 100 × 100 × 100 × 100 0.1% Syn4 4 4 1000 M = 100 × 100 × 100 × 1000 0.01%To simulate the smooth evolution of multityped communities, each synthetic network is evolved into a network sequence with 10 timestamps. Within each evolution, a percentage (from 5% to 10%) of the objects from each type change their community memberships by interacting with other objects in different communities randomly at each timestamp.For completeness, we also randomly generate from 10% to 15% new objects coming and old objects vanishing in Syn4 at each timestamp. With new objects coming and interacting with other objects, many new gene-networks are generated. Meanwhile, with old objects vanishing, they will not appear in any gene-network in the network.


## 6.1.2. Comparative Methods and Experimental Setting

The performances of SOSComm on synthetic networks are compared with two state-of-the-art baselines:(1)
SOSClus (see [33]): an offline clustering framework for static heterogeneous information networks, which treats every snapshot in the network sequence independently without the temporal evolution regularization term.(2)
CEMNTR (see [26, 27]): a framework of community evolution in multimode network with temporal evolution regularization term, denoted as CEMNTR. CEMNTR partitions the multimode network into a set of bityped networks and detects communities in each bityped network via block model approximation with temporal regularization.Both the baselines and SOSComm share the same stopping conditions; that is, the change of corresponding objective function is less than10-6 and the maximum iterations MaxIter=10000. The experiments in our prior work [33] have shown that the second-order stochastic gradient descent has good robustness with respect to the learning rate. Hence, we set the learning rate η=1/(iter+1) for both SOSClus and SOSComm. As CEMNTR needs to partition the networks into a set of bityped networks, we divide each network snapshot in Syn3 and Syn4 into 3 bityped networks and construct the adjacent matrices for each pair of object types.Since the ground-truth of the community structures in the synthetic networks is known, we adopt the Normalized Mutual Information (NMI) [42] as the metric to evaluate the performances. NMI is a measurement of mutual dependence information between multityped community membership and the ground-truth, which ranges from 0 to 1. The larger the value of NMI is, the better the result is.


## 6.1.3. Experimental Results

We set the temporally regularized parameterλ=1.0 for SOSComm and CEMNTR. Since the number of multicommunities K is an important parameter for SOSComm, we evaluate the performance with different K on the 4 synthetic networks firstly. With K varying from 1 to 10, the average values of NMIs of SOSComm on the 4 synthetic networks are shown in Figure 3. Obviously, on Syn1 and Syn3, SOSComm performs best when K=2, and on Syn2 and Syn4, SOSComm performs best when K=4. The results are consistent with the real setting for synthetic networks in Table 1; that is, the real number of multityped communities is 2 for Syn1 and Syn3, and 4 for Syn2 and Syn4. With the widening gap between K and the real number of multityped communities, SOSComm performs worse and worse in all synthetic networks.Figure 3
The performances of SOSComm on 4 synthetic networks with differentK.In the following experiments, we fixK as the real number of multityped communities in each synthetic network. The comparison of NMIs for SOSComm and two baselines on the 4 synthetic networks is shown in Figure 4. In Figure 4, each subgraph shows NMIs of the three methods on each network snapshot in corresponding synthetic network. The tendency of the NMI curve turns out the ability of tracing communities evolution. From the 4 subgraphs in Figure 4, we find that SOSComm performs best on NMI and tracing communities evolution. Since no knowledge of previous community membership at the first timestamp is available, SOSComm and SOSClus share the same starting point on the 4 synthetic networks. Moreover, with the time evolving, SOSComm can trace the evolution of multityped communities closely, while the NMIs of SOSClus and CEMNTR on the 4 synthetic networks decline steadily.Figure 4
The comparison of the performances of NMIs for SOSComm, SOSClus, and CEMNTR at each timestamp on the 4 synthetic networks.
(a)
Experimental results on Syn1 (b)
Experimental results on Syn2 (c)
Experimental results on Syn3 (d)
Experimental results on Syn4As shown in Figure4(d), with the new objects coming and old objects vanishing in the network at each timestamp, the NMIs of SOSClus and CEMNTR on Syn4 drop sharply; in detail, NMI of SOSClus drops from 1.0 to 0.2865 and NMI of CEMNTR drops from 0.8099 to 0.0976. Meanwhile, NMI of SOSComm keeps smooth relatively. This reveals that SOSComm can handle the time-evolving heterogeneous information networks with new objects coming and old objects vanishing effectively.The convergence speed is also a significant focus for studying the performances of our framework. We run SOSComm on Syn3 and Syn4 withλ=1.0 and analyze the changes of the objective function L(t) between adjacent iterations, denoted as error=|Liter+1(t)-Liter(t)|/Liter(t), for all timestamps in the two network sequences. When the errors almost keep constant, the algorithm converges. Figure 5 shows the experimental results of error, where each subgraph displays the convergence speed of SOSComm on Syn3 and Syn4 at corresponding timestamp. In Figure 5, we can see that SOSComm converges quickly on both Syn3 and Syn4 at all timestamps. Particularly, SOSComm has converged when the iterations are less than 10 in all subgraphs, which is a good property for online deployment.Figure 5
The changes of the objective function between adjacent iterations for SOSComm on Syn3 and Syn4 at each timestamp.
(a)
t = 1 (b)
t = 2 (c)
t = 3 (d)
t = 4 (e)
t = 5 (f)
t = 6 (g)
t = 7 (h)
t = 8 (i)
t = 9 (j)
t = 10The temporally regularized parameterλ in (10) controls the impact of historical information on the current community distribution. The larger the λ is, the more significant the impact is. To study the influence of temporally regularized parameter λ tuning, we apply SOSComm on Syn4 with λ varying from 0.1 to 100. The average values of NMIs and iterations on all network snapshots over all timestamps are shown in Figure 6, where the coordinates of x-axis are based on a logarithmic transformation. As shown in Figure 6, the NMIs and iterations maintain the satisfactory results when λ is less than 10. However, when λ>10 and keeps increasing, the performances of NMIs and iterations become worse quickly. That is, the historical information dominates and the algorithm consumes more resources to smooth the time-evolving communities, when the temporally regularized parameter λ is too large. Certainly, the temporally regularized parameter contributes to multityped communities detection by considering the temporal information when λ ranges from 0.1 to 10.Figure 6
The average values of NMIs and iterations of SOSComm on Syn4 with differentλs.To conclude, the experiments on the 4 time-evolving synthetic networks demonstrate that SOSComm outperforms the SOSClus and CEMNTR. With a fast convergence speed, SOSComm can trace the evolution of multityped communities in the 4 synthetic networks accurately. In particular, on Syn4, with the new objects coming and old objects vanishing in the network, SOSComm can detect the multityped communities evolution well, while the performances of SOSClus and CEMNTR deteriorate rapidly as time goes on. The performances of NMIs for SOSComm on the 4 synthetic networks with differentK show that SOSComm is sensitive to K. The K is closer to the real number of multityped of communities, so SOSComm performs better. Moreover, when λ ranges from 0.1 to 10, the performances of SOSComm are satisfactory.


## 6.2. Experiments on Real-World Dataset

### 6.2.1. Dataset Description

Here, we compare the performances of SOSComm with the baselines on real-world dataset. The real-world dataset is a 25-year DBLP network sequence, which is collected by Tang et al. [27] and available online: http://www.leitang.net/heterogeneous_network.html. In the 25-year DBLP dataset, the papers published from 1980 to 2004 are extracted, and all related authors, terms (words contained in the papers’ titles), and venues (the conferences or journals the papers published in) are included. The low frequency used and stop words have been abandoned. In the real-world dataset, the 25-year DBLP network is segmented into 25 network snapshots according to the publication year associated with each paper. After that, we construct a 4-mode tensor for each network snapshot, where the 4 modes of the tensors represent the papers, authors, venues, and terms, respectively. Table 2 shows the number of papers, authors, venues, terms, and gene-networks in each network snapshot of the 25-year DBLP dataset. Meanwhile, each row in Table 2 indicates the size of the corresponding tensor. For example, the size of the tensor for year=2004 is 69,021 × 105,292 × 1,238 × 9,153, with 1,182,458 nonzero elements. It is worth noting that there is no ground-truth of community memberships in the real-world dataset, because it is difficult and unrealistic to label the massive objects in a real-world network automatically or even manually.Table 2
The details of the real-world dataset.
Year Type Paper Author Venue Term Gene-network Number 1980 2783 3400 80 2994 21814 1981 3693 4630 95 3511 31156 1982 3525 4418 89 3451 30228 1983 3872 5066 100 3742 33790 1984 4299 5674 106 3917 38060 1985 5076 6630 124 4238 45081 1986 5531 7539 145 4505 51625 1987 6368 8871 170 4929 60488 1988 7522 10415 195 5169 72363 1989 8665 11856 213 5562 85161 1990 10332 14801 243 6005 105975 1991 11435 16107 268 6134 116875 1992 13654 19546 323 6609 147849 1993 15183 22130 363 6870 171968 1994 16860 25160 380 7197 201015 1995 18532 27737 418 7469 225549 1996 21611 31828 472 7828 266749 1997 25492 38684 551 8233 338227 1998 26133 40595 584 8352 351770 1999 29082 45201 634 8515 401446 2000 34500 53735 718 8721 492333 2001 40402 62770 852 8948 601616 2002 47322 72126 957 9059 720623 2003 60833 92843 1144 9198 978413 2004 69021 105292 1238 9153 1182458


### 6.2.2. Evaluation Metrics

Different from the synthetic networks, NMI cannot be adopted as the metric to evaluate the performances due to the lack of ground-truth of community membership in the real-world dataset. In fact, to evaluate the detection of community evolution is challenging. Alternatively, we extend the modularityQ [43, 44], a widely used metric of measuring the quality of communities in a homogenous network, to the high-order tensor space, so that the extended modularity Q is suitable for the heterogeneous information networks. In a network, the high modularity reflects dense connections among vertices within a community and sparse connections among vertices across different communities.Following the work of [44], modularity Q is defined as the fraction of the edges that fall within the given communities minus the expected fraction of randomization of these edges with the fixed degree of each vertex. We directly give the calculation of modularity Q in [44]:(26)Q=12e∑v,wavw-dvdw2eδv,w,where e is the total number of edges in the whole network, avm is an element of adjacent matrix A∈{0,1}N×N, and dv denotes the degree of vertices v. The function δ(v,w) indicates whether the vertices v and w are in the same community or not. The value of Q falls in the range [-0.5,1), which can be negative. In practice, when the value of Q ranges from 0.3 to 0.7, the quality of community is satisfactory.Without loss of generality, we take the heterogeneous information network at thetth timestamp as an example and ignore the superscript of timestamp in the following discussion. In our framework, each nonzero element of tensor X maps a gene-network in the given heterogeneous information network, while the outer product of a series of the kth column in the corresponding factor matrices indicates the distribution of the kth multityped community for gene-networks; that is, Ck=uk(1)∘uk(2)∘⋯∘uk(N). In other words, a gene-network is the minimum unit in our framework. Then, a new graph Φ reflecting the connections of gene-networks is formed, in which each gene-network in the original heterogeneous information network is treated as a vertex. In other words, the vertices in Φ are the gene-networks in original heterogeneous information network. If two vertices ϕ and φ are connected or an edge between ϕ and φ exists in Φ, this means that the gene-networks denoted by ϕ and φ in the original heterogeneous information network share one or more same objects.Accordingly, the modularityQ can be used to evaluate the quality of communities in Φ. Since the vertices in Φ are in one-to-one correspondence with gene-networks in original heterogeneous information network, the multityped communities Ck|k=1K consisting of gene-networks in original heterogeneous information network are also the partition of communities in Φ. Let J denote the total number of vertices in Φ; that is, J=nnz(X). The adjacent matrix of Φ becomes A∈{0,1}J×J, whose element aϕφ indicates whether ϕ connects to φ or not. Here, the adjacent matrix A is a symmetric matrix with all zeros diagonal; that is, aϕφ=aφϕ and aϕϕ=0.Thereby, the total number of edges inΦ is e=1/2∑ϕφaϕφ, and the degree of ϕ is dϕ=∑φaϕφ. According to (26), the extended modularity Q (also denoted by Q) can be calculated by(27)Q=12e∑ϕ,φaϕφ-dϕdφ2eδϕ,φ.If ϕ and φ are in the same multityped community, δ(ϕ,φ)=1. Otherwise, δ(ϕ,φ)=0.


### 6.2.3. Experimental Results

Firstly, The baselines and SOSComm are deployed in offline mode in order to learn their best performances on multityped communities discovery. That is, the baselines and SOSComm are iterated on each network snapshot until they converge. In the offline mode, we share the same comparative methods and experimental setting as that in experiments on synthetic networks; that is, the change of corresponding objective function is less than10-6 and the maximum iterations MaxIter=10000. We set the temporally regularized parameter λ=1.0 for SOSComm and CEMNTR.To seek out the suitable number of multityped communities, we perform the SOSComm on the 25-year DBLP network with differentK. Figure 7 gives the average values of modularity Q on the 25 timestamps with K varying from 1 to 50. In Figure 7, when 14≤K≤31, Q≥0.3. Though the average values of modularity Q are almost equal when K=18,19,20,21,22, and 23, the maximum of Q is obtained when K=20. Therefore, in the following experiments, the number of multityped communities in the 25-year DBLP network is fixed to 20.Figure 7
The performances of SOSComm on the 25-year DBLP network with differentK.The comparison of modularityQ for the baselines and SOSComm in offline mode is shown in Figure 8. SOSComm performs the best modularity Q on each network snapshot. With the time evolving, SOSComm traces the evolution of multityped communities more and more closely, while the modularity Q of SOSClus keeps low all the time and the modularity Q of CEMNTR declines steadily.Figure 8
The comparison of modularityQ for SOSComm, SOSClus, and CEMNTR in offline mode.Secondly, we learn the performances of SOSComm in online mode. In the online mode, the maximum iteration is limited to 5. The comparison of modularityQ for the baselines and SOSComm in online mode is shown in Figure 9. Although the modularity Q of SOSComm has declined relatively to that in offline mode, its performance is still the best.Figure 9
The comparison of modularityQ for SOSComm, SOSClus, and CEMNTR in online mode.In addition, Figure10 shows the comparison of modularity Q for SOSComm in offline mode and online mode. In Figure 10, we can find that the performance of SOSComm in online mode is not worse than that in offline mode. Before 2000, the two curves almost overlap. With the explosive growth of the tensors in the last 5 years, the modularity Q of SOSComm in online mode is slightly less than that in offline mode. Table 3 summarizes the running time of the baselines and SOSComm in online mode. CEMNTR and SOSComm, as shown in Table 3, yield the obvious advantages. Most of the time, SOSComm is the fastest.Table 3
The running time of the three methods on the real-world dataset in online mode.
Year Method SOSClus CEMNTR SOSComm Time (s) 1980 10.27 0.9472 1.59 1981 6.14 1.4157 1.24 1982 6.10 1.41 1.25 1983 6.19 1.53 1.33 1984 6.07 1.63 1.36 1985 6.20 1.76 1.35 1986 6.27 1.98 1.35 1987 6.36 2.16 1.66 1988 6.38 2.66 1.37 1989 6.55 2.92 3.10 1990 6.75 3.90 6.73 1991 6.85 3.49 5.46 1992 8.31 4.18 4.13 1993 8.83 4.70 7.37 1994 9.48 6.08 4.34 1995 11.34 5.82 12.06 1996 12.66 12.12 8.26 1997 14.02 14.00 4.92 1998 17.94 14.52 8.31 1999 20.36 9.02 5.19 2000 33.79 11.31 19.50 2001 24.96 12.87 12.26 2002 27.54 49.05 15.52 2003 28.93 19.18 17.90 2004 36.71 21.94 10.67Figure 10
The comparison of modularityQ for SOSComm in offline mode and online mode.To summarize, the experiments on the 25-year DBLP dataset show that SOSComm outperforms the SOSClus and CEMNTR. With a larger modularityQ, SOSComm can detect the multityped communities and trace their evolution in the 25-year DBLP network. In particular, the experimental results of online mode demonstrate that SOSComm has the best performances on modularity Q and running time. That is, SOSComm has a good property of online deployment.


## 6.2.1. Dataset Description

Here, we compare the performances of SOSComm with the baselines on real-world dataset. The real-world dataset is a 25-year DBLP network sequence, which is collected by Tang et al. [27] and available online: http://www.leitang.net/heterogeneous_network.html. In the 25-year DBLP dataset, the papers published from 1980 to 2004 are extracted, and all related authors, terms (words contained in the papers’ titles), and venues (the conferences or journals the papers published in) are included. The low frequency used and stop words have been abandoned. In the real-world dataset, the 25-year DBLP network is segmented into 25 network snapshots according to the publication year associated with each paper. After that, we construct a 4-mode tensor for each network snapshot, where the 4 modes of the tensors represent the papers, authors, venues, and terms, respectively. Table 2 shows the number of papers, authors, venues, terms, and gene-networks in each network snapshot of the 25-year DBLP dataset. Meanwhile, each row in Table 2 indicates the size of the corresponding tensor. For example, the size of the tensor for year=2004 is 69,021 × 105,292 × 1,238 × 9,153, with 1,182,458 nonzero elements. It is worth noting that there is no ground-truth of community memberships in the real-world dataset, because it is difficult and unrealistic to label the massive objects in a real-world network automatically or even manually.Table 2
The details of the real-world dataset.
Year Type Paper Author Venue Term Gene-network Number 1980 2783 3400 80 2994 21814 1981 3693 4630 95 3511 31156 1982 3525 4418 89 3451 30228 1983 3872 5066 100 3742 33790 1984 4299 5674 106 3917 38060 1985 5076 6630 124 4238 45081 1986 5531 7539 145 4505 51625 1987 6368 8871 170 4929 60488 1988 7522 10415 195 5169 72363 1989 8665 11856 213 5562 85161 1990 10332 14801 243 6005 105975 1991 11435 16107 268 6134 116875 1992 13654 19546 323 6609 147849 1993 15183 22130 363 6870 171968 1994 16860 25160 380 7197 201015 1995 18532 27737 418 7469 225549 1996 21611 31828 472 7828 266749 1997 25492 38684 551 8233 338227 1998 26133 40595 584 8352 351770 1999 29082 45201 634 8515 401446 2000 34500 53735 718 8721 492333 2001 40402 62770 852 8948 601616 2002 47322 72126 957 9059 720623 2003 60833 92843 1144 9198 978413 2004 69021 105292 1238 9153 1182458


## 6.2.2. Evaluation Metrics

Different from the synthetic networks, NMI cannot be adopted as the metric to evaluate the performances due to the lack of ground-truth of community membership in the real-world dataset. In fact, to evaluate the detection of community evolution is challenging. Alternatively, we extend the modularityQ [43, 44], a widely used metric of measuring the quality of communities in a homogenous network, to the high-order tensor space, so that the extended modularity Q is suitable for the heterogeneous information networks. In a network, the high modularity reflects dense connections among vertices within a community and sparse connections among vertices across different communities.Following the work of [44], modularity Q is defined as the fraction of the edges that fall within the given communities minus the expected fraction of randomization of these edges with the fixed degree of each vertex. We directly give the calculation of modularity Q in [44]:(26)Q=12e∑v,wavw-dvdw2eδv,w,where e is the total number of edges in the whole network, avm is an element of adjacent matrix A∈{0,1}N×N, and dv denotes the degree of vertices v. The function δ(v,w) indicates whether the vertices v and w are in the same community or not. The value of Q falls in the range [-0.5,1), which can be negative. In practice, when the value of Q ranges from 0.3 to 0.7, the quality of community is satisfactory.Without loss of generality, we take the heterogeneous information network at thetth timestamp as an example and ignore the superscript of timestamp in the following discussion. In our framework, each nonzero element of tensor X maps a gene-network in the given heterogeneous information network, while the outer product of a series of the kth column in the corresponding factor matrices indicates the distribution of the kth multityped community for gene-networks; that is, Ck=uk(1)∘uk(2)∘⋯∘uk(N). In other words, a gene-network is the minimum unit in our framework. Then, a new graph Φ reflecting the connections of gene-networks is formed, in which each gene-network in the original heterogeneous information network is treated as a vertex. In other words, the vertices in Φ are the gene-networks in original heterogeneous information network. If two vertices ϕ and φ are connected or an edge between ϕ and φ exists in Φ, this means that the gene-networks denoted by ϕ and φ in the original heterogeneous information network share one or more same objects.Accordingly, the modularityQ can be used to evaluate the quality of communities in Φ. Since the vertices in Φ are in one-to-one correspondence with gene-networks in original heterogeneous information network, the multityped communities Ck|k=1K consisting of gene-networks in original heterogeneous information network are also the partition of communities in Φ. Let J denote the total number of vertices in Φ; that is, J=nnz(X). The adjacent matrix of Φ becomes A∈{0,1}J×J, whose element aϕφ indicates whether ϕ connects to φ or not. Here, the adjacent matrix A is a symmetric matrix with all zeros diagonal; that is, aϕφ=aφϕ and aϕϕ=0.Thereby, the total number of edges inΦ is e=1/2∑ϕφaϕφ, and the degree of ϕ is dϕ=∑φaϕφ. According to (26), the extended modularity Q (also denoted by Q) can be calculated by(27)Q=12e∑ϕ,φaϕφ-dϕdφ2eδϕ,φ.If ϕ and φ are in the same multityped community, δ(ϕ,φ)=1. Otherwise, δ(ϕ,φ)=0.


## 6.2.3. Experimental Results

Firstly, The baselines and SOSComm are deployed in offline mode in order to learn their best performances on multityped communities discovery. That is, the baselines and SOSComm are iterated on each network snapshot until they converge. In the offline mode, we share the same comparative methods and experimental setting as that in experiments on synthetic networks; that is, the change of corresponding objective function is less than10-6 and the maximum iterations MaxIter=10000. We set the temporally regularized parameter λ=1.0 for SOSComm and CEMNTR.To seek out the suitable number of multityped communities, we perform the SOSComm on the 25-year DBLP network with differentK. Figure 7 gives the average values of modularity Q on the 25 timestamps with K varying from 1 to 50. In Figure 7, when 14≤K≤31, Q≥0.3. Though the average values of modularity Q are almost equal when K=18,19,20,21,22, and 23, the maximum of Q is obtained when K=20. Therefore, in the following experiments, the number of multityped communities in the 25-year DBLP network is fixed to 20.Figure 7
The performances of SOSComm on the 25-year DBLP network with differentK.The comparison of modularityQ for the baselines and SOSComm in offline mode is shown in Figure 8. SOSComm performs the best modularity Q on each network snapshot. With the time evolving, SOSComm traces the evolution of multityped communities more and more closely, while the modularity Q of SOSClus keeps low all the time and the modularity Q of CEMNTR declines steadily.Figure 8
The comparison of modularityQ for SOSComm, SOSClus, and CEMNTR in offline mode.Secondly, we learn the performances of SOSComm in online mode. In the online mode, the maximum iteration is limited to 5. The comparison of modularityQ for the baselines and SOSComm in online mode is shown in Figure 9. Although the modularity Q of SOSComm has declined relatively to that in offline mode, its performance is still the best.Figure 9
The comparison of modularityQ for SOSComm, SOSClus, and CEMNTR in online mode.In addition, Figure10 shows the comparison of modularity Q for SOSComm in offline mode and online mode. In Figure 10, we can find that the performance of SOSComm in online mode is not worse than that in offline mode. Before 2000, the two curves almost overlap. With the explosive growth of the tensors in the last 5 years, the modularity Q of SOSComm in online mode is slightly less than that in offline mode. Table 3 summarizes the running time of the baselines and SOSComm in online mode. CEMNTR and SOSComm, as shown in Table 3, yield the obvious advantages. Most of the time, SOSComm is the fastest.Table 3
The running time of the three methods on the real-world dataset in online mode.
Year Method SOSClus CEMNTR SOSComm Time (s) 1980 10.27 0.9472 1.59 1981 6.14 1.4157 1.24 1982 6.10 1.41 1.25 1983 6.19 1.53 1.33 1984 6.07 1.63 1.36 1985 6.20 1.76 1.35 1986 6.27 1.98 1.35 1987 6.36 2.16 1.66 1988 6.38 2.66 1.37 1989 6.55 2.92 3.10 1990 6.75 3.90 6.73 1991 6.85 3.49 5.46 1992 8.31 4.18 4.13 1993 8.83 4.70 7.37 1994 9.48 6.08 4.34 1995 11.34 5.82 12.06 1996 12.66 12.12 8.26 1997 14.02 14.00 4.92 1998 17.94 14.52 8.31 1999 20.36 9.02 5.19 2000 33.79 11.31 19.50 2001 24.96 12.87 12.26 2002 27.54 49.05 15.52 2003 28.93 19.18 17.90 2004 36.71 21.94 10.67Figure 10
The comparison of modularityQ for SOSComm in offline mode and online mode.To summarize, the experiments on the 25-year DBLP dataset show that SOSComm outperforms the SOSClus and CEMNTR. With a larger modularityQ, SOSComm can detect the multityped communities and trace their evolution in the 25-year DBLP network. In particular, the experimental results of online mode demonstrate that SOSComm has the best performances on modularity Q and running time. That is, SOSComm has a good property of online deployment.


## 7. Conclusion

In this paper, a novel online framework for multityped community discovery in time-evolving heterogeneous information network without the restriction of network schema is proposed. Each snapshot of the network sequence is expressed as a tensor, and the multityped community is modeled as a rank-one tensor. Then, the problem of multityped community discovery is formalized as a tensor decomposition, which integrates the tensor CP factorization with a temporal evolution regularization term. In addition, a second-order stochastic gradient descent algorithm, named SOSComm, is designed to address the tensor decomposition. In this framework, the community membership matrices of all types of objects, the multityped communities, and their evolutions over time can be obtained simultaneously. Whether in offline or online mode, the proposed algorithm outperformed the other state-of-the-art methods.



---

*Source: 9653404-2018-03-06.xml*