Model-based clustering for random hypergraphs

A hypergraph is represented by a pair \(H = (V,E)\), where \(V = \{v_{1},v_{2},\ldots ,v_{N}\}\) is the set of N vertices and \(E = \{e_{1}, e_{2}, \ldots , e_{M}\}\) is the set of M hyperedges. A hyperedge e is a subset of V, and we allow repetitions in the hyperedge set E. Thus, the hypergraph H can alternatively be represented with a \( N \times M \) matrix \( {\mathbf {X}} = (x_{ij})\) where \( x_{ij} = 1 \) if vertex \(v_{i}\) appears in hyperedge \(e_{j}\) and \( x_{ij}=0\) otherwise.

The binary latent class analysis (LCA) model (Lazarsfeld and Henry 1968; Goodman 1974) is a commonly used mixture model for high dimensional binary data. It assumes that each observation is a member of one and only one of the G latent classes, and conditional on the latent class membership, the manifest variables are mutually independent of each other. The LCA model appears to be a natural candidate to model random hypergraphs where hyperedges are partitioned into G latent classes, and the probability that a hyperedge \(e \in E\) contains a vertex \(v \in V\) depends only on its latent class assignment.

Let \({{\mathbf {X}}} = (x_{ij})\) be the matrix representation of the hypergraph H where \(x_{ij} = 1\) if vertex \(v_i\) is in hyperedge \(e_j\) and \(x_{ij}=0\) otherwsie. Let \( \pi = (\pi _{1}, \ldots , \pi _{G} ) \) be the a priori latent class membership probabilities, where \(\pi _g\) is the probability that a hyperedge belongs to latent class g. We define the \(N \times G\) matrix \({\mathbf {P}}\), where \(p_{ig}\) is the probability that vertex \(v_{i}\) is contained in a hyperedge e with latent class membership g. The probability of observed hyperedge \(e_j\), which is represented by \((x_{1j}, \ldots , x_{Nj})\), is thusThus, the likelihood function of \({\mathbf {P}}\) and \(\pi \) can be written asLet \({\mathbf {Z}}^{(1)}\) be a \(M \times G\) latent class membership matrix, where \(z^{(1)}_{jg} = 1\) if hyperedge \(e_{j}\) has latent class label g and \(z^{(1)}_{jg}=0\) otherwise. The complete-data likelihood of \({\mathbf {P}}\) and \(\pi \) can be expressed as (1).In comparison to the hypergraph beta models introduced in Stasi et al. (2014), the LCA model is capable of capturing the clustering and heterogeneity of hyperedges. For example, academic papers can be naturally labelled according to subject areas and conditional on a paper being labelled mathematics, one would expect that the probability a mathematician co-authored the paper is higher than a biologist. The LCA model does not assume an upper bound on the size of hyperedges and can model hyperedges of any size. Furthermore, an expectation maximization algorithm (Dempster et al. 1977) can be easily derived to perform parameter estimation.

While the LCA model captures the clustering and heterogeneity of hyperedges in real world data sets, a large number of latent classes are typically required to achieve a good fit of the data. As a result, the number of parameters grows quickly with a moderate or large number of nodes. The complexity of the LCA model can be substantially reduced if we assume that some of the latent class conditional probabilities \((p_{ig})_{i=1}^{N}\) tend to be proportional to each other for different values of g. While assuming proportionality of latent class conditional probabilities may appear rather restrictive, it is a reasonable assumption in many hypergraph applications. We develop the Extended Latent Class Analysis (ELCA) model which builds on the proportionality assumption on the conditional probabilities.

Let \(a=(a_{1}, \ldots , a_{K})\) with \(0 \le a_k \le 1\) be a K dimensional vector, the ELCA model assumes that the latent class conditional probabilities are of the form \( (\phi _{ig} a_k)_{i=1}^{N}\) for \(g=1, \ldots , G\) and \(k=1, \ldots , K\). In the context of hypergraph applications, the \(a_k\) parameters capture the variations in the size (number of vertices) of the hyperedges whereas the \(\phi _{ig}\) values capture the probability that a node is contained in a hyperedge. The ELCA model can be considered as having two types of clustering structure, with the primary clustering structure defined by \(\phi _{ig}\) parameters and an additional clustering structure captured by \(a_k\) parameters. We note that the ELCA reduces to the standard LCA when \(K=1\).

Let \( \tau =(\tau _{1},\ldots ,\tau _{K})\) be the clustering assignment probabilities corresponding to the additional structure, the ELCA model assumes that these two clustering structure are a priori independent. Thus, the probability that a hyperedge has primary cluster label g and additional cluster label k is \(\pi _g \tau _k\), and the probability that the vertex \(v_i\) is contained in a hyperedge from the clusters pair (g, k) is \(a_k \phi _{ig}\), and the probability that the vertex \(v_i\) is contained in a hyperedge from the primary cluster g is \(\phi _{ig} \sum _{k=1}^{K} a_k \tau _k \).

Under the ELCA model with G primary clusters and K additional clusters, the probability of observing a hyperedge \((x_{1j}, \ldots , x_{Nj})\) is given byLet \(\theta = (\pi , \tau , \phi , a)\) denote the model parameters, the likelihood function can be written asThe ELCA model is not identifiable if the parameters \((a_k)_{k=1}^{K}\) are not constrained. To see this, if \(0< a_k < 1\) for all k, then the likelihood function is invariant under the transformation \((a_k)_{k=1}^{K} \rightarrow (C a_k)_{k=1}^{K} \) and \((\phi _{ig})_{i=1,g=1}^{i=N,g=G} \rightarrow (C^{-1} \phi _{ig})_{i=1, g=1}^{i=N, g=G}\), where C is some positive constant such that \(\max _{k} \{C a_k \} \le 1\). Thus, to ensure the identifiability of the model, \((a_k)_{k=1}^{K}\) are ranked by increasing order with \(a_K=1\).

We define the \(M \times K\) additional cluster membership matrix \({\mathbf {Z}}^{(2)} = (z_{jk}^{(2)})\), where \(z_{jk}^{(2)} = 1\) if hyperedge \(e_{j}\) has additional cluster label k and \(z_{jk}^{(2)}=0\) otherwise. The complete data likelihood function of \({\mathbf {X}}\), \({\mathbf {Z}}^{(1)}\) and \({\mathbf {Z}}^{(2)}\) is given asWe note that any ELCA with G primary clusters and K additional clusters can be equivalently represented as a standard LCA with \(G \times K\) clusters. Under the standard LCA representation of the ELCA model, the \(G \times K\) vectors of latent class conditional probabilities \(\big \{ (p_{ig})_{i=1}^{N} \big \}_{g=1}^{G \times K}\) can be partitioned into G sets of equal size K, and \((p_{ig})_{i=1}^{N}\) are proportional to each other within each set with the constants of proportionality determined by \((a_k)_{k=1}^{K}\). Consider the ELCA with 2 primary clusters and 2 additional clusters, which is a special case of the 4-cluster LCA model. The probabilities that vertex \(v_i\) is contained in a hyperedge from the cluster pair (1, 1), (1, 2), (2, 1), (2, 2) are given by \(\phi _{i1}, \phi _{i2}, a_1 \phi _{i1}, a_1 \phi _{i2} \).

It is easy to see that under the proportionality assumption, the ELCA model achieves significant reduction in the number of parameters. For the ELCA model with G primary clusters and K additional clusters, the number of parameters is given by \(GN + 2(K-1) + (G-1)\) whereas the number of parameters for the LCA with \(G \times K\) clusters is \(G K N + (G K - 1) \).

We analyze the distribution of the size of a random hyperedge under the proposed ELCA model. Proposition 1 below shows that the size of the hyperedges simulated from the ELCA model tend to have larger variance than those simulated from the LCA model.

We now let \(f_{N}(y)\) be the probability mass of the size of a random hyperedge simulated from a G cluster LCA model. Similarly, we let \(h_{N}(y)\) be the probability mass of the size of a random hyperedge simulated from the ELCA model with G clusters and K additional clusters. The following result can be derived.

Proposition 2 implies that under mild conditions, the distribution of the size of hyperedges converges to a mixture of Poisson distributions with \(G \times K\) mixture components as the number of vertices increases. We note that the mixture components of the limiting mixture of Poisson distribution are subject to the same proportionality condition. Nevertheless, larger variations in the size of hyperedges tend to be obtained under the ELCA compared to those obtained under the standard LCA.

We estimate the parameters \(\theta = (\pi , \tau , \phi , a) \) of the ELCA model using an EM algorithm (Dempster et al. 1977) which is a popular method in fitting mixture models. The E-step of the EM algorithm involves computing the expected value of the complete data log-likelihood (2) with respect to the distribution of the unobserved \({\mathbf {Z}}^{(1)}\) and \({\mathbf {Z}}^{(2)}\) given the current estimates. The M-step involves maximizing the expected complete data log-likelihood.

Taking logarithm of the complete data likelihood in (2), we obtain the complete data log-likelihood function below.

We use the Bayesian Information Criterion (BIC) (Schwarz 1978) to determine the optimal number of primary and additional clusters for the ELCA model. For the ELCA model, the BIC takes the following form:where \(\log L\) is the log-likelihood evaluated at the estimated parameters, and \(G N + 2(K-1) + (G-1)\) is the number of parameters in the model. The model with the lowest BIC value is selected. The accuracy of the BIC as a model selection criterion requires M to be relatively large compared to N. For the standard latent class models, existing literature suggests that the BIC is a good indicator of the true number of classes (Collins et al. 1993) and extensive simulation studies were performed in Nylund et al. (2007) to validate this claim. The performance of BIC as a model selection criterion for the ELCA model is assessed using simulation studies in Sect. 4.

Our first application is modeling co-appearance of the main characters in the scenes of the movie “Star Wars: A New Hope”. We collected the scripts of the movie from the Internet Movie Script Database¹ and constructed a hypergraph for the eight main characters so that each character is a vertex in the hypergraph. We define each scene in the movie as a hyperedge with a total of 178 hyperedges, and a character is contained in the scene if he/she speaks in the scene.

We determine the optimal number of clusters and additional clusters using BIC where the results are provided in Table 6. The ELCA model with 3 clusters and 2 additional clusters has the lowest BIC value and is selected. It is worth noting that the standard LCA with 3 clusters is also competitive based on the BIC.

The results from fitting the ELCA model with \(G=3\) and \(K=2\) are provided in Tables 7 and 8. We can see the variation in the size of hyperedges from the parameter estimates \({\hat{a}}\) and \({\hat{\tau }}\) with the majority (81%) of hyperedges having size much smaller than the rest of the hyperedges. Thus, one can deduce that a small proportion of the movie scenes have far more characters.

The estimates \({\hat{\phi }}\) in Table 8 reveal interesting clustering structure for the 8 main characters in the movie. For example, the lead character “Luke” has a strong tendency to appear in the two largest clusters. On the other hand, it is extremely unlikely for “Obi-Wan” and “Han” appear in the same scene.

The estimated primary cluster assignment probabilities from the EM algorithm for each movie scene in the Star Wars movie are shown in chronological order in Fig. 3. We can see from the plot that scenes in the early part of the movie are mainly associated with cluster 1, while cluster 2 contains most of the scenes from roughly scene 40 to scene 100. We can deduce from this, for example, that the character “Han” is very active in the middle part of the movie. On the other hand, there does not appear to be any obvious pattern for the third cluster. The clustering for many early and late movie scenes is relatively uncertain, as shown in the plot.

The uncertainties in primary clustering are also illustrated in a ternary plot in Fig. 4. Each dot in the plot represents a movie scene, and the three corners of the plot represent the three clusters. The closer the dot is to the corner, the higher probability that the corresponding movie scene belongs to the corresponding cluster. The ternary plot in Fig. 4 shows significant uncertainties in clustering a number of movie scenes into the first two clusters. This is reasonable since for a number of actors including the lead actor “Luke”, the probabilities of scene appearance are similar for the first two clusters.

The estimated additional cluster assignment probabilities for each movie scene in the Star Wars movie are shown in chronological order in Fig. 5. We observe that majority of the scenes are assigned additional cluster 1 with only a small number of scenes between scene 40 and 100 assigned to additional cluster 2 where these scenes tend to have more characters.

As a comparison, the results from fitting the standard LCA model with 3 clusters are shown in Tables 9 and 10, and a contigency table comparing the primary clustering structure of the ELCA model and the LCA model are given in Table 11. The contingency table shows a very different clustering structure obtained from fitting the standard LCA model versus the ELCA model. We show the estimated cluster assignment probabilities for each movie scene for the LCA model with 3 clusters in chronological order in Fig. 6. In comparing Fig. 3 with Fig. 6, we see that while primary cluster 2 and 3 for the fitted ELCA model are similar with cluster 2 and 3 for the fitted LCA model, there is significant difference between primary cluster 1 in the ELCA model and cluster 1 in the LCA model.

The difference in the clustering structure between the ELCA model and the LCA model is expected as the ELCA model explicitly captures the variation in the size of hyperedges. In comparison, the LCA model cannot decouple the variation in the size of hyperedges from the primary clustering structure. This is a key advantage of the ELCA model where the underlying structure of the size of the hyperedges can be uncovered. Furthermore, as a constrained version of the LCA model with 6 clusters, the ELCA model with 3 primary clusters and 2 additional clusters is far more parsimonious.

As a second application of the ELCA model, we collected news articles published by Reuters² in January 2020. We analyze the co-appearance relationships among the Group of Eight+Five (G8+5) countries. A hypergraph is constructed by defining each news article as a hyperedge and each country as a vertex. A vertex is contained in a hyperedge if the corresponding country is mentioned in the corresponding news article. News articles that do not mention any of the 13 countries were removed, and the resulting hypergraph contains 1828 hyperedges.

The model with 5 clusters and 2 additional clusters was chosen by the BIC and fitted to the data set. The BIC scores for a range of models are shown in Table 12. It is worth noting that according to the BIC scores the ELCA models with two additional clusters generally outperform the standard LCA models whereas the standard LCA performs better than the ELCA with three additional clusters.

The parameter estimates \({\hat{\pi }}, {\hat{\tau }}\) and \({\hat{a}}\) are given in Table 13. The estimate \({\hat{\pi }}\) shows that the hyperedges are relatively evenly distributed across the five clusters. We can deduce from \({\hat{a}}\) and \({\hat{\tau }}\) that there are a small number of articles mentioning many countries whereas the vast majority of the articles mention very few countries. Specifically, about 6% of articles mentioned a much larger number of countries compared to the rest of the articles. The incorporation of an additional clustering structure results in significant reduction in the number of parameters.

The clustering structure can be deduced from the estimate \({\hat{\phi }}\) given in Table 14. China, Russia and USA are among the most popular in articles in cluster 1 whereas China, France and Japan are the most commonly mentioned by articles in cluster 2. Canada, Britain and USA have the highest probability of appearing in articles in cluster 3 whereas Canada, Mexico and USA are the most likely to appear in news articles in cluster 4. Germany, France and Britain are most likely to be mentioned by news articles in cluster 5 (Table 13).