Discovering Relevance-Dependent Bicluster Structure from Relational Data

1 Introduction

Relational data encoding pairwise relationships between I and J objects appears in many fields. Biclustering is one of the most popular techniques to extract useful insights from relational data. It abstracts the given data matrix to a low-dimensional block structure by simultaneously clustering both the row and column objects. For example, biclustering of point-of-sale (POS) data can be used to elucidate bipartite relationships between particular customers and particular items that sell well. In this paper, we focused on the most typical type of relational data, i.e., sets of observations represented as a binary matrix.

Figure 1a shows standard biclustering, which is the basic concept assumed in many existing biclustering models [Nowicki and Snijders, 2001; Kemp et al., 2006; Airoldi et al., 2008; Xu et al., 2006]. In particular, the Infinite Relational Model (IRM) [Kemp et al., 2006] is one of the most widely used biclustering models, and it can automatically estimate the number of clusters. In such standard biclustering models, it is assumed that the given relational data is abstracted by a block structure in which each block has uniform density. However, this assumption has problems when we analyze relational data. We typically analyze an obtained cluster from the objects constituting the cluster. Thus, the assumption requires that we inspect all objects in the rows and columns of each block to understand what the block means. Furthermore, biclustering models with this assumption often extract many meaningless clusters that comprise objects with few links [Ishiguro et al., 2012; 2016]. Thus, extracting insights from standard biclustering results is often very time-consuming.

In this paper, we propose relevance-dependent biclustering (Fig. 1b) to solve the drawbacks of standard biclustering. We assume that each row and column object has a hidden variable indicating a relevance value that determines how strongly the object relates to the cluster. A large relevance value means that the corresponding object strongly relates to the cluster. Thus, such highly relevant objects ought to be inspected to aid in understanding the meaning of the clusters. In other words, a small relevance value indicates that the corresponding object is non-informative. The advantages of relevancedependent biclustering are as follows:

• The meaning of obtained clusters can be understood by inspecting only a few highly relevant objects.
• All obtained clusters are interpretable because they are related to at least one meaningful (dense) block.

Consequently, the meaning of the biclustering results can be understood easily without cumbersome manual effort.

Now we provide a motivating example for the proposed biclustering. When analyzing the shopping behavior of customers on an e-commerce site, there may be items that a certain customer would like to purchase but cannot afford, whereas a customer with a larger budget can purchase any item on sale. Therefore, the bicluster structure underlying real-world relationships may represent highly distorted relationships rather than ideal relationships. To obtain a bicluster structure in such a situation, it is natural to assume additional latent factors (i.e., relevance values) that affect the link probabilities of objects regardless of their cluster membership. Although the necessity of considering clusters with uneven density has been discussed in social community analysis [Araujo et al., 2014], this problem has not yet been studied directly. Another challenge is to develop an efficient inference algorithm for this problem, as simultaneous estimation of bicluster structure and relevance is a chicken-and-egg problem.

Contributions: We have four contributions in this paper.

1. For modeling relevance-dependent binary matrices, we propose Relevance-Dependent Bernoulli Distribution (R-BD), which is parameterized by a typical link strength common to all entries in the matrix and relevance parameters for each row and column object. We also propose conjugate priors for R-BD. Thus, all R-BD parameters can be marginalized out.
2. By incorporating R-BD, we propose a novel biclustering model called the Relevance-Dependent Infinite Biclustering (R-IB) model, which can extract relevancedependent bicluster structure from relational data with an unknown number of clusters.
3. The R-IB has an efficient inference algorithm because all model parameters can be marginalized out and do not need to be estimated explicitly.
4. In experiments, we quantitatively confirm that the R-IB can capture more essential bicluster structure with better computational efficiency than conventional models. In addition, we show the ability of the R-IB to derive an interpretable bicluster structure that facilitates the extraction of insights from real-world relational data.

The rest of this paper is organized as follows. We describe existing models in Sec. 2. We propose our novel model and its inference algorithm in Sec. 3. We present experimental results in Sec. 4. Finally, we conclude the paper in Sec. 5.

2 ExistingModels

First, we review the IRM [Kemp et al., 2006] as a baseline standard biclustering model and then review existing IRM extensions that consider the relevance of objects.

2.1 Infinite Relational Model

Let R be I × J relational data between I row objects and J column objects. Ri,j = 1(0) indicates the existence of a link (non-link) between the i-th row and the j-th column. The IRM has latent variables z1,i ∈ {1, · · · ,K} and z2,j ∈ {1, · · · ,L} that indicate the cluster assignments for I and J objects, respectively. In addition, let η ∈ [0, 1]K×L be a link probability matrix between K row clusters and L column clusters. Then, the link between the i-th row object and the j-th column object is drawn as follows:

In the IRM, the Chinese Restaurant Process (CRP) [Blackwell and MacQueen, 1973; Aldous, 1985] is used as the prior for cluster assignments z1 and z2. Thus, the IRM estimates the number of clusters automatically from the observed data. Thanks to the conjugacy between beta and Bernoulli distributions, η can be marginalized out. Consequently, the posterior inference for the IRM can be performed efficiently using collapsed methods [Liu, 1994; Teh et al., 2006b].

As the IRM is widely used, many extensions have been proposed to extract more advanced cluster structures, such as the mixed membership structure [Airoldi et al., 2008], the hierarchical structure [Roy et al., 2006], the multiple membership structure [Mørup et al., 2011; Palla et al., 2012], and other extensions [Nakano et al., 2014; Ho et al., 2011; Ishiguro et al., 2010; Fu et al., 2009]. However, none of them provides relevance information, because these models also assume that the given data exactly follows the density defined by only the cluster structure. As these advanced models can be considered instances of standard biclustering models, we focus on the IRM as the baseline model.

2.2 Existing Relevance Modeling

Few studies consider relevance dependency in biclustering. The Relevance Dependent Infinite Relational Model (RDIRM) [Ohama et al., 2013; 2016] assumes that only a subset of entries is relevant to the cluster structure.

More specifically, in the RDIRM, mixing parameters ρ1,i, ρ2,j ∈ [0, 1] are introduced for each object, and observations are drawn from a mixture of foreground ηz1,i,z2,j and background η0 densities as follows:

where F(·, ·) is a Boolean function typically set to the logical product.

Although the aim of the RDIRM is to exclude noninformative entries as noise, this mechanism can be considered an approach for modeling relevance dependency because mixing parameters ρ1 and ρ2 affect the observed link probabilities regardless of a given object's cluster membership.

However, there is a number of drawbacks in their approach. First, in the RDIRM, a link probability for an entry depends on many internal parameters: foreground probability ηz1,i,z2,j , background probability η0, mixing parameters ρ1,i, ρ2,j , and Boolean function F (·, ·). This makes the effect of the relevance on link probabilities too complex to interpret. Second, to infer the RDIRM, not only I + J cluster assignments z1, z2 must be estimated but also I ×J latent variables r1, r2. Thus, the RDIRM can be applied to only very small relational data. Finally, no reasonable strategy is available to select the Boolean function F(·, ·). Ohama et al. [2015] tackled this problem by assuming the prior for Boolean functions. However, the interpretability of relevance is degraded as the estimated probabilistic Boolean function becomes increasingly complex.

3 ProposedModel

First, we introduce the R-BD: a novel prior for relevancedependent binary matrices. Then, by incorporating the R-BD, we propose the R-IB model.

3.1 Relevance-Dependent Bernoulli Distribution

To design a prior distribution for an I × J relevancedependent binary matrix x, we consider three non-negative parameters λ, θ1,i, and θj,2. The first parameter λ in the range [0,+∞] is a typical link strength that controls the overall density for matrix x. The remaining parameters θ1,i and θ2,j (also in [0,+∞]) are the relevance parameters for the i-th row and the j-th column, respectively. Then, we define the relevance-dependent link strength for an entry xi,j by multiplying these parameters as θi,1θj,2λ. Finally, to obtain a binary random variable, we define Relevance-dependent Bernoulli distribution (R-BD) as follows:

where the function f(s) = 1 - e-s is the Bernoulli-Poisson (BerPo) link function [Zhou, 2015] that transform a nonnegative variable s into a probability.

The relevance modeling in our R-BD is more interpretable than that in the RDIRM, because the effect of relevance is defined by a simple multiplication of non-negative variables.

Another remarkable property of R-BD is that all internal parameters (i.e., λ, θ1, and θ2) can be marginalized out. Following the property of BerPo link, Eq. (3) can be equivalently rewritten by truncating a Poisson random variable x∗i,j as

where I(·) is 1 if the predicate holds and is 0 otherwise. Posterior sampling of x∗i,j can be easily performed as follows:

Note that δ(0) is a point mass at zero and ZTP(·) denotes a zero-truncated Poisson distribution [Geyer, 2007]. This representation enables the construction of conjugate priors for R-BD parameters. Assuming gamma and Dirichlet priors as λ ∼ Gamma(a, b) 1 , {θ1,i}Ii=1 /I ∼ Dirichlet(c1), and {θ2,j}Jj=1/J ∼ Dirichlet(c2), we obtain a closed-form marginal likelihood for auxiliary counts x∗ as follows:

where Mi,· = ∑j x∗i,j , M·,j = ∑i x∗i,j , and M = ∑i,j x∗i,j . Thus, the parameters for R-BD no longer need to be estimated explicitly because they have been marginalized out. This gives the R-BD an affinity with collapsed inference.

Figure 2 depicts the random binary matrices drawn from RBD with different Dirichlet parameters. Although the binary matrices drawn from R-BD indicate various density patterns, the expected link strengths for these matrices are equal to exactly λ. Therefore, the estimated value of λ can be interpreted as a representative value of a given binary matrix.

3.2 Relevance-Dependent Infinite Biclustering

Here, we describe the proposed R-IB model. CRP(γ) denotes a CRP with concentration parameter γ. The full description of the R-IB model, incorporating R-BD to the observation model of the IRM, is as follows:

where n1,k (n2,l) is the number of row (column) objects assigned to cluster k (l). Note that θ1,k (θ2,l) is a set of relevance parameters θ1,i (θ2,j), where z1,i = k (z2,j = l).

Thanks to the conjugacy between R-BD and its priors, by introducing auxiliary Poisson counts R∗ , the model parameters λ, θ1, and θ2 can be marginalized out. The marginal

1 Gamma(a, b) denotes a gamma distribution with shape parameter a and rate parameter b, i.e., P(λ | a, b) = λa-1 e-bλ /G(a, b) where G(a, b) = Γ(a)/ba . Γ(·) denotes the gamma function.

likelihood for R∗ , given z1 and z2, is then given as

where Mk,l = ∑i,j R∗ i,j I(z1,i = k)I(z2,j = l), Mk,· = ∑l Mk,l, and M·,l = ∑k Mk,l.

Figure 3 shows an R-IB solution for a synthetic dataset, in which link probabilities are distorted by object relevance. As can be seen in Fig. 3a, a 3×3 bicluster structure is present in the data. As shown in Fig. 3b, the IRM fails to extract the true partitions, because the IRM assumes uniform density within each block. In contrast, the R-IB (Fig. 3c) successfully finds the true partitions by estimating relevance values.

3.3 Inference

Posterior inference for the R-IB can be performed via collapsed Gibbs sampling. As the parameters of R-BD have been marginalized out, the only variables we have to estimate are cluster assignments z1, z2 and auxiliary counts R∗ .

As z1,i and z2,j can be sampled in the same way, we concentrate on z1,i. Using (8) and the likelihood for the CRP, given R∗ , the posterior probability that the i-th object is assigned to cluster k∗ is given by

where superscript -i indicates that the corresponding statistic is computed while excluding the i-th row object. Conversely,

+i means that the corresponding statistic is computed while including the i-th row object in cluster k∗ .

From (5), the posterior sampling for R∗ i,j is given by

Note that explicit samples for λ, θ1, and θ2 are only required during the sampling of R∗ , and are drawn as follows: λk,l | - ∼ Gamma(a + Mk,l, b + n1,kn2,l), θ1,k/n1,k | - ∼ Dirichlet(c1 + M1,k), and θ2,l/n2,l |- ∼ Dirichlet(c2 + M2,k), where c1 +M1,k (c2 +M2,l) is the set of c1 +Mi,· (c2 +M·,j) in row (column) cluster k (l).

As the sampling for R∗ is computationally insignificant compared with that for z1 and z2, both the R-IB and IRM require the O((I + J)KL) computation for each iteration. However, the computation of a beta function required for the IRM is more expensive than that of a gamma function required for the R-IB. As a result, computational time of the R-IB is significantly shorter than that of both the RDIRM and IRM.

The hyperparameters for the R-IB (i.e., γ1, γ2, c1, c2, a, and b) can also be sampled assuming gamma priors. Thanks to the conjugacy between gamma distributions, posterior sampling for the rate parameter b is straightforward. For the remaining hyperparameters, posterior sampling is performed using data augmentation techniques [Escobar and West, 1994; Zhou, 2015; Teh et al., 2006a; Newman et al., 2009] (omitted here for brevity).

4 Experiments

We present experimental results obtained using real-world datasets. The purposes of the experiments are as follows:

• To quantitatively show that the R-IB can capture more essential cluster structures with better computational efficiency than the IRM and RDIRM (Sec. 4.2).
• To show the usefulness of relevance-dependent biclustering results obtained by the R-IB in understanding the meaning of each cluster (Sec. 4.3).

In all the experiments, we also fit all hyperparameters of both the proposed and baseline models assuming the same gamma priors (Gamma(1.0,1.0)).

4.1 Datasets

The first dataset was the Animal [Osherson et al., 1991] dataset, which maps relationships between 50 mammals and 85 attributes. Each attribute is rated on a scale of 0-100 for each animal. We prepared binary relational data with a threshold that yielded Ri,j = 1 for all ratings higher than the overall average rates. Therefore, Ri,j = 1(0) indicated that the i-th animal had (or lacked) the j-th attribute. The second dataset was the Enron [Klimat and Yang, 2004] dataset, which comprises e-mails sent between Enron employees. We extracted e-mail transactions between August and October 2001, and constructed three relational datasets: Enron08, Enron09, and Enron10. These contained e-mail transactions between 149 employees in the corresponding month. For these datasets, Ri,j = 1(0) was used to indicate whether an email was, or was not, sent by the i-th employee to the j-th employee. The final dataset was the MovieLens [MOV, as of 2003] dataset, which comprises five-point scale ratings of 1,682 movies submitted by 943 users. For this dataset, we set Ri,j = 1 when the rating was higher than three and Ri,j = 0 otherwise, so that Ri,j = 1(0) indicated whether or not the i-th user liked the j-th movie. The densities of the Animal, Enron08, Enron09, Enron10, and MovieLens datasets were 0.368, 0.015, 0.016, 0.026, and 0.035, respectively.

4.2 Quantitative Comparison

Many real-world relational data contains many zero entries. Thus, in order to evaluate the ability of the R-IB to capture essential bicluster structure, we evaluated the link prediction ability for held-out entries by calculating the averaged Area Under the Curve of the Precision-Recall curve (AUCPR) [Davis and Goadrich, 2006]. We compared three biclustering models: the IRM, the RDIRM, and the R-IB. We ran 4000 Gibbs iterations for each model on each dataset and used the final 500 iterations to calculate the measurement. All scores were calculated using 10-fold cross validation, and the overall average and deviation were reported.

Table 1 lists the results. As can be seen, R-IB significantly outperformed the RDIRM with all datasets. The IRM demonstrated the best performance for only the Animal dataset. Compared with the IRM, the other models require additional parameters to be estimated. This caused the RDIRM, and R-IB to overfit the data, because the Animal dataset was too small to allow the underlying cluster structure to be generalized. However, the difficulty in obtaining insights from the data increased as the datasets became larger. As we consider the performance with larger datasets to be a more important criterion, the results demonstrated the superiority of our R-IB over conventional models in link prediction accuracy.

The average number of Gibbs iterations within 5 min was used as the metric to evaluate the computational efficiency of the different models. As shown in Fig. 4, our R-IB overwhelmingly outperformed the RDIRM. Even in the worst case, posterior sampling for the R-IB was 16.1 times faster than that for the RDIRM. Furthermore, the proposed R-IB significantly outperformed the baseline standard biclustering model (i.e., the IRM), providing experimental confirmation of the computational efficiency of our model, as discussed in Sec. 3.3.

These quantitative results confirmed that the R-IB can extract more essential bicluster structures with better computational efficiency than conventional models.

4.3 Qualitative Comparison

We qualitatively compared our outcomes for the Animal and Enron09 datasets with those obtained using the IRM.

Figure 5 shows the clustering results on the Animal dataset. As can be seen from Fig. 5a and b, our R-IB abstracted relational data into relevance-dependent blocks in such a way that each block followed the R-BD, whereas blocks obtained using the IRM followed a uniform density. Thus, the IRM form non-informative clusters for irrelevant objects with few links (e.g., column cluster 1 in Fig. 5a). In contrast, as Fig. 5b shows, all clusters obtained by the proposed R-IB were informative because they were related to at least one meaningful (dense) block.

To assess the contents of the extracted clusters, Fig. 6 shows the content of several clusters obtained by R-IB. In each cluster, we can understand its meaning by inspecting only a few top-ranked objects. For example, "Meatteeth"

and "Fierce" in column cluster 3 clearly suggest that the cluster denotes carnivorous features. Similarly, other top-ranked objects (e.g., "(Eat) fish," "Quadrapedal," and "Vegetation") also facilitate interpretation of the corresponding clusters. Objects with smaller relevance values were also interesting. For example, "Meatteeth" and "Stalker" in column cluster 3 are definitely related because many carnivorous mammals stalk other animals to prey on them. However, as the third column of column cluster 3 (Fig. 6) shows, the IRM assigned them to different clusters because the IRM does not consider the heterogeneity of objects' relevance.

The results obtained by R-IB on the Animal dataset further suggested that the relevance of column objects varied more widely than that of row objects (see the relevance values listed in Fig. 6). Here all row objects were selected from a specified category (i.e., mammals). Thus, the row objects followed the underlying cluster structure with the same degree of clarity. In contrast, the attributes of the column objects covered a range of categories such as habitat, favorite food, appearance, and behavioral characteristics. Therefore, the relevance of the column objects was heterogeneous. Thus, the R-IB was shown to be able not only to extract the relevance-dependent bicluster structure but also to assess the necessity of relevance modeling of an arbitrary dataset.

Figure 7 shows the solutions obtained from the Enron09 dataset. As can be seen, the IRM produced several noninformative large blocks containing objects with few links (e.g., block A in Fig. 7a). Although the IRM also produced a comparatively large cluster block comprising many moderately strongly linked objects (block B in Fig. 7a), it was difficult to understand the meaning of the block. In contrast, R-IB produced a more interpretable bicluster structure (Fig. 7b). In the R-IB solution, the relevance parameters for objects with few links yielded small values, and these objects were assigned to the nearest meaningful cluster. Therefore, almost all the clusters produced by the R-IB were informative and worthy of inspection. In block C of Fig. 7b, the top five relevant row objects were four vice presidents and an anonymized person, and the top two relevant column objects were presidents. This allowed us to assume that the main role of block C could be understood as "reports from vice presidents to presidents." Similarly, blocks D and E in Fig. 7b were interpreted as "mails between cash analysts" and "reports from employees to the chief financial officer," respectively.

These results confirmed that the R-IB successfully extracted a relevance-dependent bicluster structure, allowing deep insights to be gained from real-world relational data.

5 Conclusions

In this paper, we addressed the problem of analyzing relational data while taking account of the relevance of objects. We introduced the relevance-dependent biclustering problem, which simultaneously estimates the bicluster structure and the relevance of objects. We proposed the R-BD as a prior distribution for relevance-dependent binary matrices. We further proposed conjugate priors for the R-BD to make collapsed inferences available. By incorporating R-BD as an observation model, we introduced a novel infinite biclustering model (i.e., R-IB) that is able to extract a relevancedependent bicluster structure from relational data with an unknown number of clusters. Finally, we proposed an efficient collapsed Gibbs sampler to infer the R-IB. Experiments using real-world datasets confirmed that the R-IB was able to extract more essential clusters with better computational efficiency than conventional models. We further confirmed that relevance-dependent clusters obtained by the R-IB were more interpretable than those obtained by standard biclustering. In the future, we intend to extend this to be able to discover more advanced structures, such as those with mixed membership or multiple membership assumptions.