Generalized Latent Factor Models for Social Network Analysis

1 Introduction

A social network 1 [Wasserman and Faust, 1994] is often represented as a graph in which the nodes represent the objects and the edges (or called links) represent the binary relations between objects. The edges in a graph can be directed or undirected. If the edges are directed, we call the graph a directed graph. Otherwise, the graph is an undirected graph. Unless otherwise stated, we focus on directed graphs in this paper because an undirected edge can be represented by two directed edges with opposite directions. Some typical networks include friendship networks among people, web graphs, and paper citation networks.

As pointed out by [Hoff, 2008], homophily and stochastic equivalence are two primary features of interest in social networks. If an edge is more likely to exist between two nodes with similar characteristics than between those nodes having different characteristics, we say the graph exhibits homophily. For example, two individuals are more likely to be friends if they share common interests. Hence, a friendship graph has the feature of homophily. On the other hand, if the nodes of a graph can be divided into groups where members within a group have similar patterns of links, we say this graph exhibits stochastic equivalence. The web graph has such a feature because some nodes can be described as hubs which are connected to many other nodes called authorities but the hubs or authorities are seldom connected among themselves. For stochastic equivalence, the property that members within a group have similar patterns of links also implies that if two nodes link to or are linked by one common node, the two nodes most likely belong to the same group.

1 In this paper, we use the terms 'network', 'social network' and 'graph' interchangeably.

(b) stochastic equivalence

Figure 1: Homophily and stochastic equivalence in networks.

Examples of homophily and stochastic equivalence in directed graphs are illustrated in Figure 1, where the locations in the 2-dimensional space denote the characteristics of the points (nodes). From Figure 1(a), we can see that a link is more likely to exist between two points close to each other, which is the property of homophily. In Figure 1(b), the points form three groups associated with different colors, and the nodes in each group share similar patterns of links to nodes in other groups, but the nodes in the same group are not necessarily connected to each other. This is the property of stochastic equivalence. Note that in a graph exhibiting stochastic equivalence, two points close to each other are not necessarily connected to each other and connected points are not necessarily close to each other, which is different from the property of homophily.

As social network analysis (SNA) is becoming more and more important in a wide range of applications, many SNA models have been proposed [Goldenberg et al., 2009]. In this paper, we focus on latent variable models [Bartholomew and Knott, 1999] which have been successfully applied to model social networks [Hoff, 2008; Nowicki and Snijders, 2001; Hoff et al., 2002; Kemp et al., 2006; Airoldi et al., 2008;

Hoff, 2009]. These models include: the latent class model [Nowicki and Snijders, 2001] and its extensions [Kemp et al., 2006; Airoldi et al., 2008], the latent distance model [Hoff et al., 2002], the latent eigenmodel [Hoff, 2008], and the multiplicative latent factor model (MLFM) [Hoff, 2009]. Among all these models, the recently proposed latent eigenmodel, which includes both the latent class model and the latent distance model as special cases, can capture both homophily and stochastic equivalence in networks. However, it can only model undirected graphs. MLFM [Hoff, 2009] adapts the latent eigenmodel for directed graphs. However, as to be shown in our experiments, in fact it cannot model well homophily.

In this paper, we propose a novel model, called generalized latent factor model (GLFM), for social network analysis by enhancing homophily modeling in MLFM. The learning algorithm of GLFM is guaranteed to converge to a local optimum and has linear-time complexity. Hence, GLFM can be used to model large-scale graphs. Extensive experiments on community detection in some real-world networks show that GLFM dramatically outperforms existing methods.

2 Notation and Definition

We use boldface uppercase letters, such as K, to denote matrices, and boldface lowercase letters, such as x, to denote vectors. The ith row and the jth column of a matrix K are denoted as Ki∗ and K∗j, respectively. Kij denotes the element at the ith row and jth column in K. xi denotes the ith element in x. We use tr(K) to denote its trace, KT for its transpose and K-1 for its inverse. ‖ · ‖ is used to denote the length of a vector. | · | denotes the cardinality of a set. I denotes the identity matrix whose dimensionality depends on the context. For a matrix K, K ⪰ 0 means that K is positive semi-definite (psd) and K ≻ 0 means that K is positive definite (pd). K ⪰ Mmeans K-M ⪰ 0. N(·) denotes the normal distribution, either for scalars or vectors. ◦ denotes the Hadamard product (element-wise product).

Let N denote the number of nodes in a graph. A is the adjacency (link) matrix for the N nodes. Aij = 1 if there exists a link from node i to node j. Otherwise, Aij = 0. D denotes the number of latent factors. In real-world networks, if Aij = 1, we can say that there is a relation from i to j. However, Aij = 0 does not necessarily mean that there is no relation from i to j. In most cases, Aij = 0 means that the relationship from i to j is missing. Hence, we use an indicator matrix Z to indicate whether or not an element is missing. More specifically, Zij = 1 means that Aij is observed while Zij = 0 means that Aij is missing.

3 Multiplicative Latent Factor Models

The latent eigenmodel is formulated as follows 2 :

where X is an N × D matrix with Xi∗ denoting the latent representation of node i and μ is a parameter reflecting the overall density of the links in the network, Λ is a D × D diagonal matrix with the diagonal entries being either positive or negative. The latent eigenmodel generalizes both latent class models and latent distance models. It can model both homophily and stochastic equivalence in undirected graphs [Hoff, 2008].

2 Note that in this paper, we assume for simplicity that there is no attribute information for the links. It is straightforward to integrate attribute information into the existing latent variable models as well as our proposed model.

To adapt the latent eigenmodel for directed graphs, MLFM defines

where X and W have orthonormal columns. Note that the key difference between the latent eigenmodel and MLFM lies in the fact that MLFM adopts a different receiver factor matrix W which enables MLFM to model directed (asymmetric) graphs. As we will show in our experiments, this modification in MLFMmakes it fail to model homophily in networks.

where E is an N×N matrix with all entries being 1.

We can find that MLFM is a special case of the following model:

For example, we can get MLFM by setting U = X and V = WΛ. Furthermore, it is easy to compute the X, W and Λ in (2) based on the learned U and V in (3). Hence, in the sequel, MLFM refers to the model in (3).

4 Generalized Latent Factor Models

As discussed above, MLFM can capture stochastic equivalence but cannot model well homophily in directed graphs. Here, we propose our GLFM to enhance homophily modeling in MLFM.

4.1 Model

In GLFM, Θik is defined as follows:

Comparing (4) to (3), we can find that GLFM generalizes MLFMby adding an extra termUi∗UTk∗ . 3 It is this extra term that enables GLFM to model homophily in networks, which will be detailed in Section 4.2 when we analyze the objective function in (7). This will also be demonstrated empirically later in our experiments.

Based on (4), the likelihood of the observations can be defined as follows:

where

Note that as in the conventional SNA model, we ignore the diagonal elements of A. That is, in this paper, we set Aii = Zii = 0 by default.

Furthermore, we put normal priors on the parameters μ, U and V: p(μ) = N(μ | 0, τ -1 ), p(U) = ∏Dd=1 N (U∗d | 0, βI), p(V) = ∏Dd=1 N (V∗d | 0, γI).

3 Note that the coefficient 12 in (4) makes no essential difference between (4) and (3). It is only for convenience of computation.

4.2 Learning

Although the Markov chain Monte Carlo (MCMC) algorithms designed for other latent variable models can easily be adapted for GLFM, we do not adopt MCMC here for GLFM because MCMC methods typically incur very high computational cost. In this paper, we adopt the maximum a posteriori (MAP) estimation strategy to learn the parameters. The log posterior probability can be computed as follows:

where c is a constant independent of the parameters. Note that in (7) we assume that all existing links should be observed. That is to say, if Aik = 1, then Zik = 1.

The term AikUi∗UTk∗ in (7) results from the extra term Ui∗UTk∗ in (4). In (7), to maximize the objective function L, we have to make Ui∗UTk∗ as large as possible if there exists a link between nodes i and k (i.e., Aik = 1). This conforms to the property of homophily, i.e., a link is more likely to exist between two nodes with similar characteristics than between those nodes having different characteristics. Note that here the latent factor Ui∗ reflects the characteristics of node i. Therefore, the extra termUi∗UTk∗ in (4) enables GLFM to model homophily in networks.

If we directly optimize all the parameters U, V and μ jointly, the computational cost will be very high. For example, if we want to use the second-order information, generally we need to invert the Hessian matrix where the time complexity is cubic in the number of parameters.

Here, we adopt an alternating projection strategy to maximize L. More specifically, each time we optimize one parameter, such as U, with the other parameters fixed.

Learning U

To learn U, we optimize each row of it with all other rows fixed. The gradient vector and Hessian matrix can be computed as follows:

Because both the gradient vector and Hessian matrix depend on Si∗ which is a function of Ui∗, we have to resort to iterative methods to find the optimal values. Here, we devise a minorization-maximization (MM) algorithm [Lang et al., 2000] to learn it. MM is a so-called expectationmaximization (EM) algorithm [Dempster et al., 1977] without missing data, alternating between constructing a concave lower bound of the objective function and maximizing that bound.

Because 0 < Sik < 12 , we can get Sik(1 - Sik) < 14 . Let us define:

It is easy to prove that ∂ 2L ∂UTi∗ ∂Ui∗ ⪰ Hi .

Let

where Ui∗(t) denotes the value of the former iteration and Hi(t) is computed with the updated U except for Ui∗.

Then we have the following theorem:

Theorem 1 L(Ui∗) ≥ f (Ui∗), which means that f (Ui∗) is a lower bound of L(Ui∗).

The proof of Theorem 1 is simple and we omit it here.

We can see that f (Ui∗) has a quadratic form of Ui∗. By setting the gradient of f (Ui∗) with respect to Ui∗ to 0, we have the update rule for Ui∗:

Learning V

The gradient vector and Hessian matrix of Vi∗ can be computed as follows:

Let Gi = - 1 γ I1 16 ∑k,k̸=i {ZkiUTk∗Uk∗}, we can prove that ∂ 2L ∂VT i∗ ∂Vi∗ ⪰ Gi .

Similar to the update rule for Ui∗, we can obtain the update rule for Vi∗ as follows:

where Vi∗(t) denotes the value of the former iteration and Gi(t) is computed with the updated parameters except for Vi∗.

Learning μ

Using similar learning techniques as those for U and V, we can get the update rule for μ:

4.3 Convergence and Computational Complexity

With the MM algorithm, the learning procedure of GLFM is guaranteed to converge to a local maximum.

The time complexity to compute the gradient and Hessian for node i is linear to the total number of ones in both Z∗i and Zi∗. In general, this number is O(1) because the observations in real networks are always very sparse. Furthermore, since Hi and Gi are D×D, the computational complexity to invert the Hessian matrices is O(D3 ). Typically, D is a very small number. Hence, to update the whole U and V, only O(N ) time is needed.

5 Experiment

There exist many different SNA tasks such as social position and role estimation [Wasserman and Faust, 1994], link prediction [Hoff, 2009], node classification [Li et al., 2009a; Li and Yeung, 2009; Li et al., 2009b], community detection [Yang et al., 2009a], and so on. In this paper, we adopt the same evaluation strategy as that in [Yang et al., 2009a; 2009b] for social community detection. The main reason for choosing this task is that from our model formulation we can clearly see the difference between GLFM and other latent factor models. However, many other models from different research communities have also been proposed for SNA. It is difficult to figure out the connection and difference between those models and GLFM from the formulation perspective. Hence, we use empirical evaluation to compare them. Most mainstream models have been compared in [Yang et al., 2009a; 2009b] for community detection, which provides a good platform for our empirical comparison.

For MLFM and GLFM, we adopt k-means to perform clustering based on the normalized latent representation U. Here normalization means that the latent representation of each node is divided by its length. Because the magnitude of Ui∗ reflects the activity of i, we select the most active user as the first seed of the k-means, and then choose a point as the seed of the next community if summation of the distances between this point and all the existing seeds is the largest one. Hence, the initialization of k-means is fixed. We set Z = A. For fair comparison, the hyper-parameters in GLFM and all the baselines to be compared, such as the τ in (7), are chosen from a wide range and the best results are reported. More specifically, for GLFM, the τ is fixed to 106 , β and γ are set to 2, and D = 20.

5.1 Data Sets and EvaluationMetric

As in [Yang et al., 2009a], we use two paper citation networks, Cora and Citeseer data sets 4 , for evaluation. Both data sets contain content information in addition to the directed links.

The Cora data set contains 2708 research papers from the 7 subfields of machine learning: case-based reasoning, genetic algorithms, neural networks, probabilistic methods, reinforcement learning, rule learning, and theory. Each paper is described by a 0/1-valued word vector indicating the absence/presence of the corresponding word from a dictionary of 1433 unique words. There are overall 5429 citations (links) between the papers.

4 The two data sets can be downloaded from http: //www.cs.umd.edu/projects/linqs/projects/ lbc/index.html.

The Citeseer data set contains 3312 papers which can be classified into 6 categories. Each paper is described by a 0/1-valued word vector indicating the absence/presence of the corresponding word from a dictionary of 3703 unique words. There are overall 4732 citations (links) between the papers. After deleting the self-links, we obtain 4715 links for our evaluation.

As in [Yang et al., 2009a], we use Normalized Mutual Information (NMI), Pairwise F-Measure (PWF) and Modularity (Modu) as metrics to measure the clustering accuracy of our model. For all the algorithms, we set the number of communities to the ground-truth number of class labels in the data.

5.2 Baselines

We compare GLFM with the closely related method MLFM [Hoff, 2009]. The U and V in both MLFM and GLFM are initialized by principal component analysis (PCA) on the content information. In addition, we also adopt the methods introduced in [Yang et al., 2009a] and [Yang et al., 2009b] for comparison. Those methods can be divided into three groups: link-based methods, content-based methods, link+content based methods.

The link-based methods include: PHITS [Cohn and Chang, 2000], LDA-Link [Erosheva et al., 2004]-an extension of latent Dirichlet allocation (LDA) for link analysis, the popularity-based conditional link model (PCL) [Yang et al., 2009b], and the normalized cut (NCUT) for spectral clustering [Shi and Malik, 2000].

The content-based methods include: the probabilistic latent semantic analysis (PLSA) [Hofmann, 1999], LDA-Word, and NCUT respectively with the Gaussian RBF kernel and the probabilistic product (PP) kernel [Jebara et al., 2004].

The link+content based methods include: PHITSPLSA [Cohn and Hofmann, 2000], LDA-Link-Word [Erosheva et al., 2004], Link-Content-Factorization (LCF) [Zhu et al., 2007], NCUT, PCL-PLSA, PHITS-DC, PCL-DC and C-PLDC [Yang et al., 2009a]. Here PCL-PLSA represents the combination of PCL and PLSA, PHITS-DC represents the PHITS model combined with the discriminative content (DC) model in [Yang et al., 2009a] , PCL-DC represents the PCL model combined with DC, and C-PLDC refers to the combined popularity-driven link model and DC model [Yang et al., 2009a]. Moreover, the setting for t in C-PLDC follows that in [Yang et al., 2009a]. More specifically, CPLDC(t = 1) denotes a special case of C-PLDC without popularity modeling [Yang et al., 2009a].

5.3 Illustration

We sample a subset from Cora for illustration. The sampled data set contains two classes. The learned latent representations U for the data instances are illustrated in Figure 2, where the blue circle and red cross are used to denote the data instances from two different classes respectively, and the (directed) black edges are the citation relationships between the data points. In Figure 2, (a) and (c) show the original learned latent factors of MLFM and GLFM, respectively, (b) and (d) show the corresponding normalized latent factors of MLFM

and GLFM, respectively. Here normalization means that we divide the latent factor of each node by its length. Hence, it is clear to see that all the points in (b) and (d) have unit length. Note that for fair comparison all the different subfigures from (a) to (d) are generated automatically by our program with the same parameter settings and initial values.

In (a) and (b) of Figure 2, two instances are more likely to be close if they are connected by or connect to the same instance, which is just the feature of stochastic equivalence. However, there exist many links across the inner part of the circle in (b), which means that two instances linked with each other are not necessarily close in the latent space. This just violates the feature of homophily. Hence, we can conclude that MLFM cannot effectively model homophily in networks.

In (c) and (d) of Figure 2, homophily is obvious since two nodes are close to each other in general if there exists a link between them.

5.4 Convergence Speed

When D = 20, the objective function values of GLFM against the iteration number T are plotted in Figure 3, from which we can see that our learning procedure with the MM method for GLFM converges very fast. We set the maximum number of iterations T as T = 5 in all our following experiments.

5.5 Accuracy

We compare GLFM with all the baselines introduced in Section 5.2 in terms of NMI, PWF and Modu [Yang et al., 2009a; 2009b]. The results are reported in Table 1, from which we can see that GLFM achieves the best performance on all the data sets for the three criteria. Especially for the Citeseer data set, GLFM dramatically outperforms the second best model. According to the prior knowledge, the paper citation networks are more likely to exhibit homophily because the citations often exist among papers from the same community. This can explain why GLFM can achieve such good performance on these data sets. Hence, GLFM provides a way to model networks which cannot be modeled well by MLFM.

Figure 4 shows the performance of GLFM when D takes different values. We see that GLFM is not sensitive to D as long as D is not too small.

6 Conclusion

In this paper, a generalized latent factor model is proposed to model homophily in social networks. A linear-time learning algorithm with convergence guarantee is proposed to learn the parameters. Experimental results on community detection in real-world networks show that our model can effectively model homophily to outperform state-of-the-art methods.

Acknowledgments

Li is supported by a grant from the "project of Arts & Science" of Shanghai Jiao Tong University (No. 10JCY09). Yeung is supported by General Research Fund 622209 from the Research Grants Council of Hong Kong. Zhang is supported by the NSFC (No. 61070239), the 973 Program of China (No. 2010CB327903), the Doctoral Program of Specialized Research Fund of Chinese Universities (No. 20090101120066), and the Fundamental Research Funds for the Central Universities.