Modeling homophily and stochastic equivalence in symmetric relational data Peter D. Hoff Departments of Statistics and Biostatistics University of Washington Seattle, WA 98195-4322. hoff@stat.washington.edu Abstract This article discusses a latent variable model for inference and prediction of symmetric relational data. The model, based on the idea of the eigenvalue decomposition, represents the relationship between two nodes as the weighted inner-product of node-specific vectors of latent characteristics. This "eigenmodel" generalizes other popular latent variable models, such as latent class and distance models: It is shown mathematically that any latent class or distance model has a representation as an eigenmodel, but not vice-versa. The practical implications of this are examined in the context of three real datasets, for which the eigenmodel has as good or better out-of-sample predictive performance than the other two models. 1 Introduction Let {yi,j : 1 i < j n} denote data measured on pairs of a set of n objects or nodes. The examples considered in this article include friendships among people, associations among words and interactions among proteins. Such measurements are often represented by a sociomatrix Y , which is a symmetric n × n matrix with an undefined diagonal. One of the goals of relational data analysis is to describe the variation among the entries of Y , as well as any potential covariation of Y with observed explanatory variables X = {xi,j , 1 i < j n}. To this end, a variety of statistical models have been developed that describe yi,j as some function of node-specific latent variables ui and uj and a linear predictor T xi,j . In such formulations, {u1 , . . . , un } represent across-node variation in the yi,j 's and represents covariation of the yi,j 's with the xi,j 's. For example, Nowicki and Snijders [2001] present a model in which each node i is assumed to belong to an unobserved latent class ui , and a probability distribution describes the relationships between each pair of classes (see Kemp et al. [2004] and Airoldi et al. [2005] for recent extensions of this approach). Such a model captures stochastic equivalence, a type of pattern often seen in network data in which the nodes can be divided into groups such that members of the same group have similar patterns of relationships. An alternative approach to representing across-node variation is based on the idea of homophily, in which the relationships between nodes with similar characteristics are stronger than the relationships between nodes having different characteristics. Homophily provides an explanation to data patterns often seen in social networks, such as transitivity ("a friend of a friend is a friend"), balance ("the enemy of my friend is an enemy") and the existence of cohesive subgroups of nodes. In order to represent such patterns, Hoff et al. [2002] present a model in which the conditional mean of yi,j is a function of xi,j - |ui - uj |, where {u1 , . . . , un } are vectors of unobserved, latent characteristics in a Euclidean space. In the context of binary relational data, such a model predicts the existence of more transitive triples, or "triangles," than would be seen under a random allocation of edges among pairs of nodes. An important assumption of this model is that two nodes with a strong 1 q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q qq q q q qq qq q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q Figure 1: Networks exhibiting homophily (left panel) and stochastic equivalence (right panel). relationship between them are also similar to each other in terms of how they relate to other nodes: A strong relationship between i and j suggests |ui - uj | is small, but this further implies that |ui - uk | |uj - uk |, and so nodes i and j are assumed to have similar relationships to other nodes. The latent class model of Nowicki and Snijders [2001] and the latent distance model of Hoff et al. [2002] are able to identify, respectively, classes of nodes with similar roles, and the locational properties of the nodes. These two items are perhaps the two primary features of interest in social network and relational data analysis. For example, discussion of these concepts makes up more than half of the 734 pages of main text in Wasserman and Faust [1994]. However, a model that can represent one feature may not be able to represent the other: Consider the two graphs in Figure 1. The graph on the left displays a large degree of transitivity, and can be well-represented by the latent distance model with a set of vectors {u1 , . . . , un } in two-dimensional space, in which the probability of an edge between i and j is decreasing in |ui - uj |. In contrast, representation of the graph by a latent class model would require a large number of classes, none of which would be particularly cohesive or distinguishable from the others. The second panel of Figure 1 displays a network involving three classes of stochastically equivalent nodes, two of which (say A and B ) have only across-class ties, and one (C ) that has both within- and across-class ties. This graph is well-represented by a latent class model in which edges occur with high probability between pairs having one member in each of A and B or in B and C , and among pairs having both members in C (in models of stochastic equivalence, nodes within each class are not differentiated). In contrast, representation of this type of graph with a latent distance model would require the dimension of the latent characteristics to be on the order of the class membership sizes. Many real networks exhibit combinations of structural equivalence and homophily in varying degrees. In these situations, use of either the latent class or distance model would only be representing part of the network structure. The goal of this paper is to show that a simple statistical model based on the eigenvalue decomposition can generalize the latent class and distance models: Just as any symmetric matrix can be approximated with a subset of its largest eigenvalues and corresponding eigenvectors, the variation in a sociomatrix can be represented by modeling yi,j as a function of xi,j + uT uj , where {u1 , . . . , un } are node-specific factors and is a diagonal matrix. In this i article, we show mathematically and by example how this eigenmodel can represent both stochastic equivalence and homophily in symmetric relational data, and thus is more general than the other two latent variable models. The next section motivates the use of latent variables models for relational data, and shows mathematically that the eigenmodel generalizes the latent class and distance models in the sense that it can compactly represent the same network features as these other models but not vice-versa. Section 3 compares the out-of-sample predictive performance of these three models on three different datasets: a social network of 12th graders; a relational dataset on word association counts from the first chapter of Genesis; and a dataset on protein-protein interactions. The first two networks exhibit latent homophily and stochastic equivalence respectively, whereas the third shows both to some degree. 2 In support of the theoretical results of Section 2, the latent distance and class models perform well for the first and second datasets respectively, whereas the eigenmodel performs well for all three. Section 4 summarizes the results and discusses some extensions. 2 Latent variable modeling of relational data 2.1 Justification of latent variable modeling The use of probabilistic latent variable models for the representation of relational data can be motivated in a natural way: For undirected data without covariate information, symmetry suggests that any probability model we consider should treat the nodes as being exchangeable, so that Pr({yi,j : 1 i < j n} A) = Pr({yi,j : 1 i < j n} A) for any permutation of the integers {1, . . . , n} and any set of sociomatrices A. Results of Hoover [1982] and Aldous [1985, chap. 14] show that if a model satisfies the above exchangeability condition for each integer n, then it can be written as a latent variable model of the form yi,j = h(µ, ui , uj , i,j ) (1) for i.i.d. latent variables {u1 , . . . , un }, i.i.d. pair-specific effects { i,j : 1 i < j n} and some function h that is symmetric in its second and third arguments. This result is very general - it says that any statistical model for a sociomatrix in which the nodes are exchangeable can be written as a latent variable model. Difference choices of h lead to different models for y . A general probit model for binary network data can be put in the form of (1) as follows: { i,j : 1 i < j n} i.i.d. normal(0, 1) {u1 , . . . , un } i.i.d. f (u| ) yi,j = h(µ, ui , uj , i,j ) = (0,) (µ + (ui , uj ) + i,j ), where µ and are parameters to be estimated, and is a symmetric function, also potentially involving parameters to be estimated. Covariation between Y and an array of predictor variables X can be represented by adding a linear predictor T xi,j to µ. Finally, integrating over i,j we obtain Pr(yi,j = 1|xi,j , ui , uj ) = [µ + T xi,j + (ui , uj )]. Since the i,j 's can be assumed to be independent, the conditional probability of Y given X and {u1 , . . . , un } can be expressed as Pr(yi,j = 1|xi,j , ui , uj ) i,j Pr(Y |X, u1 , . . . , un ) = [µ + T xi,j + (ui , uj )] i y = i,ij,j (1 - i,j )yi,j 0 or k < 0. In this way, the model can represent both positive or negative homophily in varying degrees, and stochastically equivalent nodes (nodes with the same or similar latent vectors) may or may not have strong relationships with one another. We now show that the eigenmodel generalizes the latent class and distance models: Let Sn be the set of n × n sociomatrices, and let CK DK EK = {C Sn : ci,j = mui ,uj , ui {1, . . . , K }, M a K × K symmetric matrix}; = {D Sn : di,j = -|ui - uj |, ui RK }; = {E Sn : ei,j = uT uj , ui RK , a K × K diagonal matrix}. i In other words, CK is the set of possible values of {(ui , uj ), 1 i < j n} under a K dimensional latent class model, and similarly for DK and EK . ~ EK generalizes CK : Let C CK and let C be a completion of C obtained by setting ci,i = mui ,ui . ~ and so C is of rank K at most. Since the set EK contains ~ There are at most K unique rows of C all sociomatrices that can be completed as a rank-K matrix, we have CK EK . Since EK includes matrices with n unique rows, CK EK unless K n in which case the two sets are equal. EK +1 weakly generalizes DK : Let D DK . Such a (negative) distance matrix will generally be of full rank, in which case it cannot be represented exactly by an E EK for K < n. However, what is critical from a modeling perspective is whether or not the order of the entries of each D can be matched by the order of the entries of an E . This is because the probit and ordered probit model we are considering include threshold variables {µy : y Y } which can be adjusted to accommodate monotone transformations of (ui , uj ). With this in mind, note that the matrix of squared distances among a set of K -dimensional vectors {z1 , . . . , zn } is a monotonic transformation of the distances, is of rank K + 2 or less (as D2 = [z1 z1 , . r . , zn zn ]T 1T + 1[z1 z1 , . . . , zn zn ] - 2Z Z T ) and so is . 2 - z T z ) RK +1 for each i {1, . . . , n}, we have in EK +2 . Further( ore, letting ui = (zi , m ii i i 2 - |u |2 )(r 2 - |u |2 ). For large r this is approximately r 2 - |z - z |2 /2, which u u j = z zj + r i j i j is an increasing function of the negative distance di,j . For large enough r the numerical order of the entries of this E EK +1 is the same as that of D DK . DK does not weakly generalize E1 : Consider E E1 generated by = 1, u1 = 1 and ui = r < 1 for i > 1. Then r = e1,i1 = e1,i2 > ei1 ,i2 = r2 for all i1 , i2 = 1. For which K is such an ordering of the elements of D DK possible? If K = 1 then such an ordering is possible only if n = 3. For K = 2 such an ordering is possible for n 6. This is because the kissing number in R2 , or the number of non-overlapping spheres of unit radius that can simultaneously touch a central sphere of unit radius, is 6. If we put node 1 at the center of the central sphere, and 6 nodes at the centers of the 6 kissing spheres, then we have d1,i1 = d1,i2 = di1 ,i2 for all i1 , i2 = 1. We can only have d1,i1 = d1,i2 > di1 ,i2 if we remove one of the non-central spheres to allow for more room between those remaining, leaving one central sphere plus five kissing spheres for a total of n = 6. Increasing n increases the necessary dimension of the Euclidean space, and so for any K there are n and E E1 that have entry orderings that cannot be matched by those of any D DK . 4 A less general positive semi-definite version of the eigenmodel has been studied by Hoff [2005], in which was taken to be the identity matrix. Such a model can weakly generalize a distance model, but cannot generalize a latent class model, as the eigenvalues of a latent class model could be negative. 3 Model comparison on three different datasets 3.1 Parameter estimation Bayesian parameter estimation for the three models under consideration can be achieved via Markov chain Monte Carlo (MCMC) algorithms, in which posterior distributions for the unknown quantities are approximated with empirical distributions of samples from a Markov chain. For these algorithms, it is useful to formulate the probit models described in Section 2.1 in terms of an additional latent variable zi,j normal[ xi,j + (ui , uj )], for which yi,j = y if µy < zi,j < µy+1 . Using conjugate prior distributions where possible, the MCMC algorithms proceed by generating a new (s+1) (s+1) state (s+1) = {Z (s+1) , µ(s+1) , (s+1) , u1 , . . . , un } from a current state (s) as follows: 1. 2. 3. 4. For each {i, j }, sample zi,j from its (constrained normal) full conditional distribution. For each y Y , sample µy from its (normal) full conditional distribution. Sample from its (multivariate normal) full conditional distribution. Sample u1 , . . . , un and their associated parameters: · For the latent distance model, propose and accept or reject new values of the ui 's with the Metropolis algorithm, and then sample the population variances of the ui 's from their (inverse-gamma) full conditional distributions. · For the latent class model, update each class variable ui from its (multinomial) conditional distribution given current values of Z, {uj : j = i} and the variance of the elements of M (but marginally over M to improve mixing). Then sample the elements of M from their (normal) full conditional distributions and the variance of the entries of M from its (inverse-gamma) full conditional distribution. · For the latent vector model, sample each ui from its (multivariate normal) full conditional distribution, sample the mean of the ui 's from their (normal) full conditional distributions, and then sample from its (multivariate normal) full conditional distribution. To facilitate comparison across models, we used prior distributions in which the level of prior variability in (ui , uj ) was similar across the three different models (further details and code to implement these algorithms are available at my website). 3.2 Cross validation To compare the performance of these three different models we evaluated their out-of-sample predictive performance under a range of dimensions (K {3, 5, 10}) and on three different datasets exhibiting varying combinations of homophily and stochastic equivalence. For each combination of dataset, dimension and model we performed a five-fold cross validation experiment as follows: nd 1. Randomly divide the 2 ata values into 5 sets of roughly equal size, letting si,j be the set to which pair {i, j } is assigned. 2. For each s {1, . . . , 5}: (a) Obtain posterior distributions of the model parameter conditional on {yi,j : si,j = s}, the data on pairs not in set s. (b) For pairs {k , l} in set s, let yk,l = E [yk,l |{yi,j : si,j = s}], the posterior predictive ^ mean of yk,l obtained using data not in set s. ^ This procedure generates a sociomatrix Y , in which each entry yi,j represents a predicted value ^ ^ obtained from using a subset of the data that does not include yi,j . Thus Y is a sociomatrix of out-of-sample predictions of the observed data Y . 5 K 3 5 10 Table 1: Cross validation results and area under the ROC curves. Add health Genesis Protein interaction dist class eigen dist class eigen dist class eigen 0.82 0.64 0.75 0.62 0.82 0.82 0.83 0.79 0.88 0.81 0.70 0.78 0.66 0.82 0.82 0.84 0.84 0.90 0.76 0.69 0.80 0.74 0.82 0.82 0.85 0.86 0.90 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q qq q q q q q q q q q q q q q q q q qq qq q q qq q q q q q q q q q q q qq q q q q q q q q q qq q q q q q q q q q q q q q q qq q q qq q q q q qq q q q q q q q q q q q q q q qq qq q qq q q qq q q q q q qq q q q q q q q q qq q qqq q q q q qq qq qq q qq q q q q q q q q q q q q q q q q q q q q qq q qq q q qq q q q q q q q q q q q q q q q q q q q q q q qq q q qq q q q qq qq true positives 100 200 300 q q qqq q q 400 q qq q q q distance class vector 0 5000 15000 25000 false positives Figure 2: Social network data and unscaled ROC curves for the K = 3 models. 3.3 Adolescent Health social network The first dataset records friendship ties among 247 12th-graders, obtained from the National Longitudinal Study of Adolescent Health (www.cpc.unc.edu/projects/addhealth). For these data, yi,j = 1 or 0 depending on whether or not there is a close friendship tie between student i and j (as reported by either i or j ). These data are represented as an undirected graph in the first panel of Figure 2. Like many social networks, these data exhibit a good deal of transitivity. It is therefore not surprising that the best performing models considered (in terms of area under the ROC curve, given in Table 1) are the distance models, with the eigenmodels close behind. In contrast, the latent class models perform poorly, and the results suggest that increasing K for this model would not improve its performance. 3.4 Word neighbors in Genesis The second dataset we consider is derived from word and punctuation counts in the first chapter of the King James version of Genesis (www.gutenberg.org/dirs/etext05/bib0110.txt). There are 158 unique words and punctuation marks in this chapter, and for our example we take yi,j to be the number of times that word i and word j appear next to each other (a model extension, appropriate for an asymmetric version of this dataset, is discussed in the next section). These data can be viewed as a graph with weighted edges, the unweighted version of which is shown in the first panel of Figure 3. The lack of a clear spatial representation of these data is not unexpected, as text data such as these do not have groups of words with strong within-group connections, nor do they display much homophily: a given noun may appear quite frequently next to two different verbs, but these verbs will not appear next to each other. A better description of these data might be that there are classes of words, and connections occur between words of different classes. The cross validation results support this claim, in that the latent class model performs much better than the distance model on these data, as seen in the second panel of Figure 3 and in Table 1. As discussed in the previous section, the eigenmodel generalizes the latent class model and performs equally well. 6 0 make one two a aa withouorm wnsaleis usplace t mreht y ng f g gathered their unto be i hadtself fruiherleinhold own very wtfuseasons likeness his kind da our togethierhtssaiwhosys s d sign e lg ss appear graood so ame eated g gatherinmn d eat set gwacr , thebe is r blessed im broughtfinisheasge : after e lteteseefor life shall easeas h h med ale i land ing br forth eadthr sgo t f m w n erismyhignt aimuldiply m h ed rai la h abuatdwh.ccnlredatslfruitupoin movetovbearing n aa kne far tidmec t t se t yielding hath l dry open ofhg ave;foree at r creepeth underp fr li e n t w e also deewereom the imht and l thhngb have h di i i g d thus t beginnvndesawthi subdue ature e ver e smosninhospiriday crebedisvido emaly you given tar r g issh t f g a att d sixth facgdstaeerlenll h livongvoicreeping reen me re r t p e is nin i i r ial tsi firht rd lessehfelveens g ver wingedinion fsffcondhmovingvule ive yeardom ietourt h g s r above may fly true positives 100 200 300 400 distance class vector 0 4000 8000 false positives 12000 Figure 3: Relational text data from Genesis and unscaled ROC curves for the K = 3 models. We note that parameter estimates for these data were obtained using the ordered probit versions of the models (as the data are not binary), but the out-of-sample predictive performance was evaluated based on each model's ability to predict a non-zero relationship. 3.5 Protein-protein interaction data Our last example is the protein-protein interaction data of Butland et al. [2005], in which yi,j = 1 if proteins i and j bind and yi,j = 0 otherwise. We analyze the large connected component of this graph, which includes 230 proteins and is displayed in the first panel of 4. This graph indicates patterns of both stochastic equivalence and homophily: Some nodes could be described as "hubs", connecting to many other nodes which in turn do not connect to each other. Such structure is better represented by a latent class model than a distance model. However, most nodes connecting to hubs generally connect to only one hub, which is a feature that is hard to represent with a small number of latent classes. To represent this structure well, we would need two latent classes per hub, one for the hub itself and one for the nodes connecting to the hub. Furthermore, the core of the network (the nodes with more than two connections) displays a good degree of homophily in the form of transitive triads, a feature which is easiest to represent with a distance model. The eigenmodel is able to capture both of these data features and performs better than the other two models in terms of out-of-sample predictive performance. In fact, the K = 3 eigenmodel performs better than the other two models for any value of K considered. 4 Discussion Latent distance and latent class models provide concise, easily interpreted descriptions of social networks and relational data. However, neither of these models will provide a complete picture of relational data that exhibit degrees of both homophily and stochastic equivalence. In contrast, we have shown that a latent eigenmodel is able to represent datasets with either or both of these data patterns. This is due to the fact that the eigenmodel provides an unrestricted low-rank approximation to the sociomatrix, and is therefore able to represent a wide array of patterns in the data. The concept behind the eigenmodel is the familiar eigenvalue decomposition of a symmetric matrix. The analogue for directed networks or rectangular matrix data would be a model based on the singular value decomposition, in which data yi,j could be modeled as depending on uT Dvj , where i ui and vj represent vectors of latent row and column effects respectively. Statistical inference using the singular value decomposition for Gaussian data is straightforward. A model-based version of 7 0 q q q q q q qq qq q q q q q q q qq qq qq q q q q q q q q q q q q q q q q qq q 0 100 q q q q q qq q q qq q q q q q q q q qq q q qq q q qq q q q q q q qq qq qq q q q q qq q q q qq q q q q qq q q q q q qqqq qq q q q q q qq q q q q qq q q q q qq q q q q q q qq q qq qq q q qq q q q q q q q qq q q q q q qq q q qq q q q qq q q qq q q qq qq qq q qq q q q q q qq q qq q q q q q q q q qq q q q q qq q q qq q qq q q q q qq q q q q true positives 300 500 700 distance class vector 0 5000 15000 false positives 25000 Figure 4: Protein-protein interaction data and unscaled ROC curves for the K = 3 models. the approach for binary and other non-Gaussian relational datasets could be implemented using the ordered probit model discussed in this paper. Acknowledgment This work was partially funded by NSF grant number 0631531. References Edoardo Airoldi, David Blei, Eric Xing, and Stephen Fienberg. A latent mixed membership model for relational data. In LinkKDD '05: Proceedings of the 3rd international workshop on Link discovery, pages 82­89, New York, NY, USA, 2005. ACM Press. ISBN 1-59593-215-1. doi: http://doi.acm.org/10.1145/1134271.1134283. ´ David J. Aldous. Exchangeability and related topics. In Ecole d'ete de probabilites de Saint-Flour, ´´ ´ XIII--1983, volume 1117 of Lecture Notes in Math., pages 1­198. Springer, Berlin, 1985. G. Butland, J. M. Peregrin-Alvarez, J. Li, W. Yang, X. Yang, V. Canadien, A. Starostine, D. Richards, B. Beattie, N. Krogan, M. Davey, J. Parkinson, J. Greenblatt, and A. Emili. Interaction network containing conserved and essential protein complexes in escherichia coli. Nature, 433:531­537, 2005. Peter D. Hoff. Bilinear mixed-effects models for dyadic data. J. Amer. Statist. Assoc., 100(469): 286­295, 2005. ISSN 0162-1459. Peter D. Hoff, Adrian E. Raftery, and Mark S. Handcock. Latent space approaches to social network analysis. J. Amer. Statist. Assoc., 97(460):1090­1098, 2002. ISSN 0162-1459. D. N. Hoover. Row-column exchangeability and a generalized model for probability. In Exchangeability in probability and statistics (Rome, 1981), pages 281­291. North-Holland, Amsterdam, 1982. Charles Kemp, Thomas L. Griffiths, and Joshua B. Tenenbaum. Discovering latent classes in relational data. AI Memo 2004-019, Massachusetts Institute of Technology, 2004. Krzysztof Nowicki and Tom A. B. Snijders. Estimation and prediction for stochastic blockstructures. J. Amer. Statist. Assoc., 96(455):1077­1087, 2001. ISSN 0162-1459. Stanley Wasserman and Katherine Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, 1994. 8