Subset Infinite Relational Models

Katsuhiko Ishiguro
Naonori Ueda
Hiroshi Sawada
NTT Communication Science Laboratories, NTT Corporation. 619-0237 Kyoto, Japan.
{ishiguro.katsuhiko , ueda.naonori , sawada.hiroshi} @lab.ntt.co.jp

Abstract
We propose a new probabilistic generative model
for analyzing sparse and noisy pairwise relational data, such as friend-links on social network services and customer records in online
shops. Real-world relational data often include
a large portion of non-informative pairwise data
entries. Many existing stochastic blockmodels
suﬀer from these irrelevant data entries becauseof their rather simpler forms of priors. The proposed model incorporates a latent variable that
explicitly indicates whether each data entry is
relevant or not to diminish bad eﬀects associated with such irrelevant data. Through experiments using synthetic and real data sets, we showthat the proposed model can extract clusters withstronger relations among data within the cluster
than clusters obtained by the conventional model.

1

Introduction

Analysis of pairwise relational data, such as the customer
records of purchases in online shops, friend-links on social networks, or bibliographic citations between scientificarticles, is useful in many aspects. Many statistical models for relational data have been presented [Liben-Nowell
and Kleinberg, 2003, Clauset et al., 2008, Zhu et al., 2009,
Erosheva et al., 2004] in the literature. Among them,the stochastic block model (SBM) [Nowicki and Snijders,2001] and the infinite relational model (IRM) [Kemp et al.,2006] perform simultaneous clustering on the row and column dimensions of a given pairwise relational data matrix. For example, in the case of customer records, the row
and column correspond to users and items, respectively.
The row and column clusters are interpreted as latent usergroups and item topics, respectively. SBM requires specifying the number of clusters in advance, while IRM auAppearing in Proceedings of the 15th International Conference on
Artificial Intelligence and Statistics (AISTATS) 2012, La Palma,
Canary Islands. Volume XX of JMLR: W&CP XX. Copyright2012 by the authors.

tomatically estimates the number of clusters depending on
the observed data. The usefulness of these models has already been established.
However, the real-world relational data are often noisy andsparse. For example, relations between users and shop
items in online purchase records is very sparse: there arethousands of items and users, but only very few item-user
pairs are observed in records. In the case of friend-links in
Social Network Services (SNS) such as Twitter, the problem of sparseness again holds. Furthermore, we can findsome noisy observations due to spam accounts that randomly follow unknown users for advertisement or otherpurposes. When applying the conventional block models
to such data, as shown later, we often obtain unexpectedclusters with weak relations among pairwise relational data
within the cluster.
In this paper, we address the problems of noisiness andsparseness of real-world relational data. The number ofthese irrelevant data entries (elements of the observed relational data matrix) that do not strongly relate to the otherdata entries is huge in the dataset. As a result, they may obscure the interesting part of the observations. Assume eachuser is a data point located in a sparse and high-dimensionalfeature space: its feature vector is an observed relation between many other users. In such a space, every data point issimilarly distant from all other data points because most of
the feature vectors are sparse or uniformly distributed. Thismeans we cannot distinguish the users because of highdimensional irrelevant features. Also, since SBM and IRM
are optimized to maximize the posterior probability of allclustering and parameters based on all the observations, theirrelevant data entries make it diﬃcult to extract the core
structure of small relevant and interesting clusters.
Specifically, we extend IRM so that only relevant rows andcolumns of a given relational data matrix can automaticallybe extracted for clustering. Intuitively, in the case of useritem purchase records, not all users and items but some ofthem are supposed to be analyzed for clustering. The proposed model estimates the relevancy of each row and column depending on the observations. If a row (column) is
estimated as irrelevant to form a cluster, then the row (column) is excluded from the IRM process. We only perform

Subset Infinite Relational Models

the IRM on those who are classified as relevant; therefore,
the IRM analysis on the core relations are not disturbed bynoise observations. This relevancy and IRM-based clustering are seamlessly connected in the probabilistic generative model, and we can obtain its inference algorithm as astraightforward Gibbs sampler. Our proposed model is inspired by the subset clustering model [Hoﬀ, 2005, Guanet al., 2011] that explicitly excludes irrelevant elementsfrom feature vectors for better clustering of these vectors.
The rest of this paper is organized as follows. In thenext section, we introduce the IRM as the baseline of our
method, and reveal its drawbacks. We present a new model
as a solution for the problem in the third section, and explain the inference procedure in the fourth section. The
fifth section is devoted to experimental evaluations, and thefinal section concludes the paper.

2

Infinite Relational Models

We first explain the infinite relational model (IRM) [Kempet al., 2006], which estimates an unknown number of hidden clusters from relational data. In IRM, the Dirichlet process (DP) is used as a prior for clusters of an unknown number, and is denoted as DP(α, G0 ) where α > 0 is a parameter
and G0 is a base measure. We write G ∼ DP(α, G0 ) whena distribution G (θ) is sampled from DP. We can implement
DP by using either a stick-breaking process [Sethuraman,
1994] or a Chinese restaurant process (CRP) [Blackwell
and MacQueen, 1973] as a marginalized form of stickbreaking process. In this paper, we employ the CRP representation of DP. CRP itself is a probability of partitioning of
N objects. Let zi = k, i ∈ {1, . . . , N}, k ∈ {1, . . . , K} denotethat the ith object is assigned to the kth partition (cluster)among the total K partitions. Then the CRP is represented
as the following equations:∏K(nk − 1)!
CRP(z1:N |α) = αK ∏Nk=1,(1)(α+ i − 1)
i=1
 n
k\i


 n−1+α nk\i > 0,p(zi = k|z\i , α) = 
(2)

 α
n = 0.
N−1+αk\i

Equation 1 shows the joint probability of K partitions.
Equation 2 represents the probability of the object i being
allocated to the partition k given K − 1 partitions. nk denotes the number of objects assigned to the partition k, andnk\i denotes the same number excluding object i.
The IRM is an application of the DP for relational data.
Let us first assume a binary two-place relation on the setof objects D = {1, . . . , i, . . . , N} as D × D → {0, 1}. For
simplicity, we assume two-place relations throughout the
paper, but the extension for more high-dimensional data isstraightforward. The IRM divides the set of N objects into
multiple clusters based on the matrix of observed relational
data X = {xi, j ∈ {0, 1}; 1 ≤ i, j ≤ N}. The IRM is able toinfer the number of clusters at the same time because it uses
DP as a prior distribution of the cluster partition. A data entry xi, j ∈ {0, 1} denotes the existence of a relation between arow object i and a column object j (i, j ∈ {1, 2, . . . , N}). In
the case of SNS friend-links, if there is (not) a friend-linkfrom user i to user j, then xi, j = 1 (0). We allow asymmetric
relations xi, j , x j,i throughout the paper. The probabilistic
generative model of the IRM is as follows:()
θk,l |ck,l , dk,l ∼ Beta ck,l , dk,l ,(3)
zi |α ∼ CRP (α) ,(4)()
xi, j |Z, {θ} ∼ Bernoulli θzi ,z j .
(5)
In Eq. (3), θk,l is the strength of a relation between the objects in clusters k and l. We sample a cluster index of theobject i, zi = k, k ∈ {1, 2, . . . , } using the CRP as in Eq. (4).
Generating the observed relational data xi, j follows Eq. (5)N
conditioned by the cluster assignments Z = {zi }i=1
and thestrengths θ. We call this model a “one-domain” model since
object indices i and j point to the same domain (in the caseof SNS, both i and j denote a user). A graphical model of
one-domain IRM is illustrated in Fig. 2(A).
Let us assume the case where relation is defined between
objects in diﬀerent domains, namely D1 × D2 → {0, 1}
where D1 = {1, . . . , i, . . . , N1 } and D2 = {1, . . . , j, . . . , N2 }.
For such data, we define a “two-domain” IRM as follows:()
θk,l |ck,l , dk,l ∼ Beta ck,l , dk,l ,(6)
z1,i |α1 ∼ CRP (α1 ) ,(7)
z2, j |α2 ∼ CRP (α2 ) ,(8)()
xi, j |Z 1 , Z 2 , {θ} ∼ Bernoulli θz1,i ,z2, j .
(9)In the above equations, i indexes the object of the first domain D1 , and j indexes the object of the second domain D2 .
In the case of an online purchase record, the first domain
corresponds to a user list, and an object i denotes a specificuser i. The second domain corresponds to a list of shop
items, and an object j denotes a specific item j. The data
entry xi, j represents a relation between the user i and theitem j: namely, the purchase record. In Eq. (6), θk,l is thestrength of a relation between the cluster k of the first domain and the cluster l in the second domain. z1,i in Eq. (7)and z2, j in Eq. (8) denotes the cluster assignments in thefirst domain and the second domain, respectively. The main
diﬀerence between the one-domain IRM and two-domain
IRM is that the object cluster assignments of two domains
are generated from independent CRP Eq. (7) and Eq. (8).
It means that each domain may have a diﬀerent number ofclusters.
One drawback of IRM for highly noisy and sparse relational data, which is often the case, is the CRP prior itself.
As we can see from Eq. (1) and Eq. (2), the CRP priornaively “counts” the cluster assignments. Therefore, thecounts of irrelevant objects of X aﬀect the posterior of Z.

Katsuhiko Ishiguro, Naonori Ueda, Hiroshi Sawada

Observed relations { x ij }Clustering results of IRM Clustering results of SIRM
j (sorted)
r=1

(A)

i (sorted)i (sorted)i

r=0

j (sorted)j(B)“Irrelevant entries”(C)

Figure 1: Illustrative example of IRM and SIRM (best viewed in color). (A): Observed relationships of Enron (Aug.)dataset (see the Experiments section for details). One black spot indicates existence of a link from a row object i to acolumn object j. (B): Clustering result of dataset by IRM. Color lines indicate the boundaries of object clusters, andeach rectangle block represents a cluster-cluster relationship that abstracts individual data entries within the block. The
object indices are sorted. (C): Clustering result of the same dataset by proposed SIRM. The lower right region that is NOT
surrounded by color lines represents “irrelevant” data entries. SIRM automatically excludes these irrelevant data entries,
and finds a more detailed cluster structure within “relevant” objects in the upper left region.
Another problem is minute clusters. IRM assumes that every object must be assigned to one of K clusters. According
to the stick-breaking construction of DP, the mixing ratioof K clusters tends to follow the power law. Thus a typicalclustering result of IRM looks like Fig. 1(B): many minuteclusters in the lower right area. This is practically problematic because it makes it diﬃcult to discern whether eachminute cluster truly extracts a property of given relational
data or just fits to noise.

3

Subset Infinite Relational Models

We introduce an extension of IRM called the Subset Infinite
Relational Model (SIRM) to deal with the aforementioned
problems of irrelevant data entries. The term “subset” indicates that we only focus on hidden structure among therelevant objects that are the subset of whole objects.
This SIRM is inspired by the subset clustering models in[Hoﬀ, 2005]. Similar models also have been proposed in[Hoﬀ, 2006, Guan et al., 2011]. Our assumption is that relevant data entries follow some cluster-dependent properties,
and irrelevant ones have no such dependencies. According
to this assumption, a column (or row) data entry of an irrelevant object will distribute in the same manner regardlessto the object in its counterpart. Such objects are not usefulfor data clustering nor do they characterize each cluster. To
address this problem, we try to remove objects that do notcontribute to the clustering under consideration. Thus, wedefine them as “irrelevant” objects. To distinguish relevant
and irrelevant objects, we introduce a new hidden variableri ∈ {0, 1}. If object i is (not) relevant, then ri = 1 (0).

In the case of one-domain IRM (D×D → {0, 1}), our SIRM
is described as follows:
φ|a, b ∼ Beta (a, b) ,()θk,l |ck,l , dk,l ∼ Beta ck,l , dk,l ,λi |e, f ∼ Beta (e, f ) ,ri |λi ∼ Bernoulli (λi ) ,zi |ri = 1, α ∼ CRP (α) ,zi |ri = 0 ∼ I (zi = 0) ,( rr)
xi, j |Z, R, {θ}, φ ∼ Bernoulli θzii ,zjj φ1−ri r j .

(10)
(11)
(12)
(13)
(14)
(15)
(16)

Equation 10 defines the distribution of a relation strengthfor irrelevant data entries, and Eq. (11) defines a relation
strength for relevant data entries. Based on that assumption, the relevant parameters are independently sampled foreach (k, l) cluster pair. λi in Eq. (12) denotes the probability of a relevancy flag variable ri being 1. As explained,
ri = {0, 1} in Eq. (13) indicates whether the object i is relevant or not.
The relevancy variables R = {ri }i=1,...,N aﬀect the remaining
generative process. If ri = 1, then zi is chosen based on
the CRP as in Eq. (14). Otherwise (ri = 0), its cluster assignment is set to zi = 0 with a probability 1 as in Eq. (15).
I(·) denotes that the predicate always holds with a probability 1. The cluster 0 is an “irrelevant” cluster that is not
related to the CRP in Eq. (14). Finally, the observed relation xi, j is conditioned by Z and R. Equation 16 is slightly
tricky: if both items i and j are assumed as relevant objects,
i.e. ri = r j = 1, then “relevant” relation strength θ is used
as a parameter of a Bernoulli trial. Otherwise, “irrelevant”
relation strength φ is employed. These two equations indi-Subset Infinite Relational Models

cate that the irrelevant object does not aﬀect the clusteringby the CRP in terms of the CRP prior (Eq. (14)) nor the
likelihood (Eq. (16)). Thus, the SIRM focuses on relevant
objects and is able to eﬀectively reconstruct the hidden relation structure among these objects. A graphical model of
one-domain SIRM is illustrated in Fig. 2(B).
In the case of cross-domain relational data (D1 × D2 →{0, 1}), we need to augment the “two-domain” IRM. Its
extension is easy: we just double the variables of “onedomain” SIRM. The generative model for the two-domain
SIRM is described as follows:
φ|a, b ∼ Beta (a, b) ,()θk,l |ck,l , dk,l ∼ Beta ck,l , dk,l ,
λ1,i |e1 , f1 ∼ Beta (e1 , f1 ) ,λ2, j |e2 , f2 ∼ Beta (e2 , f2 ) ,( )r1,i |λ1,i ∼ Bernoulli λ1,i ,( )r2, j |λ2, j ∼ Bernoulli λ2, j ,

(17)
(18)
(19)
(20)
(21)
(22)

z1,i |r1,i = 1, α1 ∼ CRP (α1 ) ,(23)()
z1,i |r1,i = 0 ∼ I z1,i = 0 ,(24)
z2, j |r2, j = 1, α2 ∼ CRP (α2 ) ,(25)()
z2, j |r2, j = 0 ∼ I z2, j = 0 ,(26)( r1,i r2, j)
1−r1,i r2, j
xi, j |Z 1 ,Z 2 ,R1 ,R2 ,{θ},φ ∼ Bernoulli θz1,i ,z2, j φ. (27)
Equation 19, Eq. (21), Eq. (23), and Eq. (24) define parameters and hidden variables for the first domain D1 . Equation
20, Eq. (22), Eq. (25), and Eq. (26) define parameters andhidden variables for the second domain D2 .
We explain the virtues of SIRM for highly noisy and sparse
relational data using Fig. 1, comparing panels (B) and (C).
Panel (C) presents a typical clustering result of SIRM.
SIRM automatically excludes irrelevant data entries to thelower right region thanks to relevance variables ri . Becauseof Eq. (14) and Eq. (15), irrelevant objects have no impact
on the clustering of the detailed structure of relevant data
entries in the upper left region.
SIRM also solves the problem of minute clusters. One reason for generating so many minute clusters in IRM is that
IRM partitions every object to one of K clusters. Therefore, a noisy random object tends to fit as an independent
cluster. However, in SIRM only relevant objects are partitioned by CRP. Thus, most of the clusters in the colorlines-surrounded upper left region in Fig. 1 (C) have somemeaning, including minute clusters. On the contrary, noisy
minute clusters will be merged in the irrelevant region.
3.1

Carvalho et al. applied a latent factor model for regression tasks of cancer characteristics using high-dimensional
gene expression feature vectors [Carvalho et al., 2008]. In
their work, sparsity priors were placed on loading matricesof the regression to pick up a limited number of eﬀective
elements. They also studied the use of Dirichlet Process
to discover the unknown number of latent factors. Miller
et al. [Miller et al., 2009] incorporated binary variable selection variables in the context of relational data analysis.
In their model, each object is characterized by binary variables that select appropriate latent features to describe theobject. Their model extends the number of latent features
to infinite (so as the binary variables), and is formulatedusing the Indian Buﬀet Process [Griﬃths and Ghahramani,2011]. One major diﬀerence between the model of [Miller
et al., 2009] and our proposed model is the usage of binary
variables. The former employs binary variables to selectlatent features, while the latter, our model, employs binary
variables to select relevant and irrelevant observed data entries: i.e. objects.
In the context of bi-clustering of relational data, Sutskever
et al. proposed a bi-clustering model called Bayesian Clustered Tensor Factorization (BCTF) [Sutskever et al., 2010]. BCTF is a richer bi-clustering model that the relations
itself can be decomposed into several clusters while ourmodel (and the original IRM) considers only one type of
relations. Instead, our model introduces the binary variables to cope with the sparsity problem mentioned above
while BCTF does not directly solve this problem. In [Bordes et al., 2011], the authors proposed a novel technique toembed objects into a low-dimensional vector space using
object-object multi-type relations in knowledge bases suchas WordNet. Since the goals of [Bordes et al., 2011] andour work is diﬀerent, soft clustering of objects like vector embedding could be another possible application of our“subset” model.

4

Inference

Since SIRM is a rather simple probabilistic model, a variety
of inference procedures are applicable for solving SIRM.
In this paper, we briefly explain the inference algorithm of
one-domain SIRM by Gibbs sampling. We can marginalizeout all parameters φ, θ, λ thanks to the conjugacy. Also we
fit hyperparameters α, a, b, c, d, e, f by posterior samplingassuming Gamma priors.
For detailed derivations and the inference algorithms forthe two-domain SIRM, please consult the supplemental
material.

Related Works
4.1

The proposed SIRM is most related to the feature (variable)
selection models like [Hoﬀ, 2005], but is also connected tosparse latent variable models and bi-clustering techniques.

Sampling Hidden Variables

We found that simultaneous sampling of ri and zi leads toa simpler inference for SIRM than deriving a solution forKatsuhiko Ishiguro, Naonori Ueda, Hiroshi Sawada

e

f

α

λi

zi

ri

α

zi
i = 1, ..., N

i = 1, ..., N

x i, jck, lad k, lbθk, li = 1, ..., N
j = 1, ..., N

ck, l
φ

x i, jθk, l

i = 1, ..., N
j = 1, ..., N

k = 1, 2, ...
l = 1, 2, ...

d k, lk = 1, 2, ...
l = 1, 2, ...

(A)

(B)

Figure 2: Graphical models. Circle node denotes probabilistic variables, rectangle nodes denote constants, and shaded
nodes represent observations. (A): Original one-domain IRM. (B): Proposed one-domain SIRM.
each variable independently.

λi out using the conjugacy, we obtain the following:

Let us denote the current number of realized clusters by
K. Regarding the sampling of the ith object, we divide theobservations X into two parts: data entries that relate tothe object i X+i = {xi,· , x·,i }, and those that do not X\i ={X \ X+i }. Also we define the following quantities:()
p zi = k, ri |Z \i , R\i∑
f + i0 ,i (1 − ri0 )





m\i
( e + ∑ 0 r 0 ) ∑k∝
i ,i i α+ m\i

k k


∑
(
)

α

 e + 0 r i0∑

nk,l =
n̄k,l =
mk =

∑∑
i

j

i

j

∑∑
∑

i ,i

ri zi,k r j z j,l xi, j ,

(28)

(
)
ri zi,k r j z j,l 1 − xi, j ,(29)

ri zi,k ,

(30)

i

q=

∑∑(
)
1 − ri r j xi, j ,
i

j

i

j

∑∑(
)(
)
q̄ =
1 − ri r j 1 − xi, j .

(31)
(32)

The superscript of \i denotes the above statistics computed
on X\i . Also, the superscript +i0, +ik denotes that the same
statistics are computed on X+i assuming ri = 0 or {ri =1, zi = k}, respectively.
We formulate the Gibbs posterior of {ri , zi } as follows:()()
p zi = k, ri |X, Z \i , R\i ∝ p zi = k, ri |Z \i , R\i()
× p X+i |zi = k, ri , X\i , Z \i , R\i(33)
The first term of the right hand of Eq. (33) is straightforward. Multiplying Eq. (13) and Eq. (14) and marginalizing

α+

\i
k mk

ri = 0, zi = 0,ri = 1, zi = k ∈ {1, 2, . . . , K},
ri = 1, zi = K + 1.
(34)

The second term of the right hand of Eq. (33) requires somecomputations. This is a likelihood term; thus we separately
present the final results for ri = 0 and ri = 1.
()
p X+i |zi = 0, ri = 0, X\i , Z \i , R\i()
B a + q\i + q+i0 , b + q̄\i + q̄+i0=()
B a + q\i , b + q̄\i()
p X+i |zi = k, ri = 1, X\i , Z \i , R\i()
B a + q\i + q+i1k , b + q̄\i + q̄+i1k=()
B a + q\i , b + q̄\i
(
)
\i
+i1k
+i1k
B ck,k + n\i
+
n
,
d
+
n̄
+
n̄
k,k
k,k
k,k
k,k
k,k
(
)
×
\i
B ck,k + n\i,d+n̄k,k k,k
k,k
(
)
\i
+i1k
+i1k
∏ B ck,l + nk,l + nk,l , dk,l + n̄\ik,l + n̄k,l()×\i
B ck,l + n\il,kk,l , dk,l + n̄k,l
(
)
\i
+i1k
+i1k
∏ B cl,k + n\il,k + nl,k , dl,k + n̄l,k + n̄l,k()×\i
B cl,k + n\il,kl,k , dl,k + n̄l,k

(35)

(36)

Subset Infinite Relational Models

4.2

Posteriors of parameters

Though all parameters are marginalized out during the inference, the posteriors of parameters may be useful in manycases. Here we present these posteriors for that purpose.
p (φ|X, Z, R) = Beta (a + q, b + q̄)()()
p θk,l |X, Z, R = Beta ck,l + nk,l , dk,l + n̄k,lp (λi |R) = Beta (e + ri , f + (1 − ri ))5

Experiments

5.1

Data

(37)
(38)
(39)

We evaluated the performance of our methods with original
IRMs using synthetic data and real data.
For synthetic data, we assume a sparse data scenario: i.e.
the irrelevant objects have very few relation observations,and relevant objects have some dense relationships among
them. We have prepared two datasets for one-domain models and two-domain models, respectively. For one-domain
models, N = 500 or N = 1, 000 while the number of relevant objects is fixed at 50. The ground truth number ofhidden clusters among relevant objects is fixed at K = 3 foreach data. For two-domain models, {N1 , N2 } = {400, 500}or {800, 900}. The number of relevant objects is again fixedat 40 for domain 1, and 50 for domain 2. The ground truth
number of hidden clusters among relevant objects is fixedat K1 = 4 and K2 = 5 for each data.
We choose the Enron e-mail dataset [Klimat and Yang,2004] as an example of a real-world one-domain dataset,and it is used in many studies [Tang et al., 2008, Fu et al.,2009, Ishiguro et al., 2010]. We extracted monthly transactions of e-mails sent in 2001. The dataset contained
N = 151 company members of Enron. xi, j = 1(0) if there is(not) an e-mail sent from a member i to a member j. Out of
twelve months, we selected the transactions of August andOctober because these two periods were milestones of theEnron scandal: the CEO of Enron resigned in August, andthe accounting scandal was first reported in October.
As real-world cross domain relational data, we collected
log data of an online cartoon distribution service for mobile phones in Japan. With this service, users pay monthly
to read cartoons on their phones. Thus, some users purchased an item more than once to read it over the course ofa month. Some cartoons have several volumes, and we regarded a cartoon that had several volumes as one item. The
first domain index i corresponds to a user, and the second
domain index j corresponds to a cartoon item. We selected
N1 = 1000 users’ records randomly. The number of cartoon items is N2 = 316. We prepared two datasets (Cartoon
1, Cartoon 2), each of which randomly and independently
subsamples users.

Table 1: Test data log likelihood per test data entry on onedomain data. Averages of 20 runs are presented, parenthesized numbers indicate standard deviations. Larger values
are better.
IRM
SIRM
Datasetsynth (small)-0.140 (0.007) -0.098 (0.001)-0.143 (0.082) -0.097 (0.000)
synth (large)
Enron (Aug.)-0.128 (0.012) -0.112 (0.006)
Enron (Oct.)-0.173 (0.006) -0.150 (0.004)

Table 2: Test data log likelihood per test data entry
on cross-domain data. Averages of 20 runs are presented, parenthesized numbers indicate standard deviations. Larger values are better.
Datasetsynth (small)synth (large)
Cartoon 1
Cartoon 2

IRM-0.094 (0.007)-0.103 (0.006)-0.130 (0.001)-0.133 (0.013)

SIRM-0.060 (0.000)-0.062 (0.000)-0.122 (0.012)-0.127 (0.007)

Please note that the sizes of these datasets are larger compared to the original IRM paper [Kemp et al., 2006]. Thisis because our goal is to build a model that is capable ofeﬀectively analyzing larger and noisy relational data.
5.2

Quantitative Results

For quantitative comparisons, we compute test data log
likelihood per test data entry. For each experimental run,
we randomly pick test data entries from the matrix X (approximately 1% of the entire X entries), and hide themduring the training period. After the Gibbs inference ofthe model is completed, we compute the log likelihoods ofthese test data entries. To align the diﬀerent number of test
data entries, we divide the log likelihoods by the numberof test data entries at that run. We tested several initial hyperparameter settings, and report the best result for eachmodel and the dataset.
Table 1 summarizes the test data log likelihoods on onedomain models. Also, we show the test data log likelihoods
on two-domain models in Table 2. As evident from thetable, the proposed SIRM is better than the original IRM
for all datasets.
5.3

Qualitative Results on One-domain Data

Next, we qualitatively examine the clustering results of
one-domain real data from Enron. The raw data and clustering results of the August data (Enron (Aug.)) are presented in Fig. 1. As evident from the figure, SIRM nicely
excludes irrelevant objects (company members) and finds
some detailed clusters within relevant objects.

Katsuhiko Ishiguro, Naonori Ueda, Hiroshi Sawada

Clustering results of IRM

Clustering results of SIRM
k=3

k=4 k=5k=5 k=4 k=3 k=2

k=1
k=2

k=2 k=3

k=1

k=1

sending member i (sorted)

k=2

k=3

sending member i (sorted)

k=1

receiving member j (sorted)

receiving member j (sorted)

(A)

(B)

Figure 3: Typical clustering results of Enron (Oct.) dataset (best viewed in color). (A) Clustering result by IRM. (B)Clustering result by SIRM.
In this section, we closely look at the results on the October data. The clustering results of IRA and SIRM on
the October data (Enron (Oct.)) are presented in Fig. 3(A)and Fig. 3(B), respectively. Comparing these two figures,the most remarkable diﬀerence is the number of irrelevant
objects in SIRM. Out of N = 151 objects, 64 objects are
assumed irrelevant (ri = 0). Most of these irrelevant objects are merged in the first cluster in IRM, resulting in avery sparse and non-informative cluster. On the other hand,clusters in SIRM are much tighter and show strong (dense)
connections among the clusters.
The second cluster (k = 2) in SIRM is a set of VIP members. The objects assigned to this cluster include presidents
of Enron companies such as Enron online and Enron Global
Markets, a governmental relation executive, a manager ofchief risk management oﬃcers, an in-house lawyer, a headmanager of risk management, several vice presidents andthe founder of Enron. We thought that these VIP members must have had to keep in touch during this month todeal with the accounting scandal news. We note that thosemembers are also clustered in the second cluster of the IRM
result (Fig. 3(A)). However, in the IRM result, it is diﬃcult
to derive this VIP interpretation because other members arealso collected in the same cluster. This comparison indicates that relevant variables ri eﬀectively exclude irrelevant
objects, and “concentrate” the meaningful memberships.
One interesting point is that the third (k = 3) cluster by
IRM is almost the same with the third cluster by SIRM.
This cluster consists of employees and managers related topipeline and regulatory business. Clustered company members include a manager and a vice president of regulatoryaﬀairs, a director of pipeline business, and a president ofEnron Gas Pipeline.

As discussed, minute clusters in SIRM are meaningful
since irrelevant objects are excluded already. In Fig. 3(B),the fourth and fifth clusters are the ones. Both clusters have
only one object as a cluster member. However these objects
show very active relations among other clusters. because
these two objects correspond to a manager and the COO.
As expected, the IRM could not find these clusters.
5.4

Qualitative Results on Two-domain Data

Next, we qualitatively examine the result of two-domain
real data from Cartoon purchase data. Clustering results
are almost the same between two datasets. The clusteringresults of IRM and SIRM on the Cartoon data are presented
in Fig. 4(A) and Fig. 4(B), respectively.
Figure 4(A) shows a typical example of using IRM on realworld dataset. Because of noisy inputs and many objects,
the first domain D1 (users, the vertical axis) and the second
domain D2 (cartoon items, the horizontal axis) have many
minute clusters that prevent an eﬀective interpretation of
the clustering results. On the other hand, SIRM eﬀectively
excludes irrelevant cartoon items, and results in a relatively
moderate numbers of clusters for both domains (Fig. 4(A)).
Since we have no information about the users (the first domain), we focus on the clusters of the second domains in
the SIRM result (Fig. 4(B)). The second cluster (l = 2)of the second domain in SIRM is a cluster of major cartoons for youngsters. Genres of cartoons in this cluster is mixed: romantic comedies for girls and ladies (e,g,“Sensual Phrase”), action and heroic stories (e.g, “Devilman”, “BASARA”), situation comedies (e.g. “CrayonShin-chan”) and others. However, cartoon items in thiscluster have several common points to be major such as:

Subset Infinite Relational Models

Clustering results of IRM

Clustering results of SIRM
l=2 l=3l=4

l=5

k=3 k=2
k=4
k=5

user i (sorted)user i (sorted)

k=1

l=1

cartoon item j (sorted)

cartoon item j (sorted)
(A)

(B)

Figure 4: Typical clustering results of Cartoon dataset (best viewed in color). (A) Clustering result by IRM. (B) Clusteringresult by SIRM.
1. Published in the major cartoon magazines, mainly targeted for teenage boys and girls.
2. Animated as TV programs or OVAs. Some cartoons
are even filmized.
3. Relatively recent cartoons are assembled. Older cartoons are famous among recent young readers because
they are reprinted over years.
The third cluster (l = 3) of the second domain in SIRM
are a set of cartoon items mainly targeted at older (20-40year) male audiences. This cluster includes hard cyberpunks (e.g. “Appleseed”), stories about outlaws and gangsters (e.g. “Ore-no-Sora”, “Lupin III”), and stories about
the historical heroes (of Japan and China).
The fourth cluster (l = 4) of the second domain in SIRM
would be collected through a diﬀerent perspective. This
cluster consists of a mixture of diﬀerent kinds of cartoons such that some oldies (e.g. “Cyborg 009”, “Dokonjo
Gaeru”) and recent romance stories that were extraordinary
popular among the middle-aged (“Winter Sonata”). Ourguess is that this cluster is a set of cartoons popular for
male audiences of specific ages (around 30 to 50). The
oldies were popular when the audiences were very young,while the recent stories started the boom when the audiences got matured. Assuming from this observation, we
can infer that the fifth cluster (k = 5) of the first domain
would be the users with middle-aged males.
These qualitative results indicate that SIRM is useful fornoisy and sparse real-world cross-domain relational datain the sense that it can extract interpretable and interesting
relations.

6

Conclusion

In this paper, we have addressed the problem of noisinessand sparseness of the relational data. We have introduced
a notion of the relevancy of objects in relational data, andproposed an extension of the IRM incorporating the relevance variables. The proposed model partitions relevantrows and columns of a given relational data matrix, whileautomatically excludes irrelevant entries. Thus the IRM
analysis on the core relations is not annoyed by noise observations. Through experiments, we confirmed that the
proposed SIRM is superior in test data log likelihoods. We
also observed that the SIRM successfully extracted hiddenclusters of core relations from real-world datasets.
As future work, one promising way is to derive a dynamic extension of SIRM similar to a dynamic versionof IRM [Ishiguro et al., 2010]. Because the relationships
among objects are inherently time-varying, the relevancy ofan object in the relations is also time-varying. It is also important to verify the performance of SIRM against higherorder tensor relations such as three-place relations.
The proposed model is a bold simplification of the actual
data generation process. For example, the proposed model
does not care why an item is assumed relevant or irrelevantin purchase data. However, revealing such reasons (e.g.
shops to check items, or budget constraints of users) is useful for further clustering. This simple example indicatesthat there are still many open problems concerning the relevance clustering models.
Acknowledgements
This work is partially supported by FIRST program of
JSPS.

Katsuhiko Ishiguro, Naonori Ueda, Hiroshi Sawada

References
D. Blackwell and J. B. MacQueen. Ferguson distributions
via Polya urn schemes. The Annals of Statistics, 1(2):353–355, 1973.
A. Bordes, J. Weston, R. Collobert, and Y. Bengio. Learning structured embeddings of knowledge bases. In Proc.
AAAI, 2011.
C. M. Carvalho, J. Chang, J. E. Lucas, J. R. Nevins,
Q. Wang, and M. West. High-dimensional sparse factor
modeling: Applications in gene expression genomics. J.
Am. Stat. Assoc., 103(484):1438–1456, 2008.
A. Clauset, C. Moore, and M. E. J. Newman. Hierarchicalstructure and the prediction of missing links in networks.
Nature, 453:98–101, 2008.
E. Erosheva, S. Fienberg, and J. Laﬀerty.
Mixedmembership models of scientific publications. PNAS,
101(Suppl 1):5220–5227, 2004.
W. Fu, L. Song, and E. P. Xing. Dynamic mixed membership blockmodel for evolving networks. In Proc. ICML,
2009.
T. L. Griﬃths and Z. Ghahramani. The Indian buﬀet process: An introduction and review. Journal of Machine
Learning Research, 12:1185–1224, 2011.
Y. Guan, J. Dy, and M. Jordan. A unified probabilistic
model for global and local unsupervised feature selection. In Proc. ICML, 2011.
P. D. Hoﬀ. Subset clustering of binary sequences, with anapplication to genomic abnormality data. Biometrics, 61(4):1027–1036, 2005.
P. D. Hoﬀ. Model-based subspace clustering. Bayesian
Analysis, 1(2):321–344, 2006.
K. Ishiguro, T. Iwata, N. Ueda, and J. Tenenbaum. Dynamic infinite relational model for time-varying relational data analysis. In Proc. NIPS, 2010.
C. Kemp, J. B. Tenenbaum, T. L. Griﬃths, T. Yamada, andN. Ueda. Learning systems of concepts with an infinite
relational model. In Proc. AAAI, 2006.
B. Klimat and Y. Yang. The enron corpus: A new dataset
for email classification research. In Proc. ECML, 2004.
D. Liben-Nowell and J. Kleinberg. The link prediction
problem for social networks. In Proc. Int. Conf. on Information and Knowledge Management, pages 556–559,
2003.
K. T. Miller, T. L. Griﬃths, and M. I. Jordan. Nonparametric latent feature models for link prediction. In Proc.
NIPS, 2009.
K. Nowicki and T. A. B. Snijders. Estimation and prediction for stochastic blockstructures. J. Am. Stat. Assoc.,
96(455):1077–1087, 2001.

J. Sethuraman. A constructive definition of dirichlet process. Statistica Sinica, 4:639–650, 1994.
I. Sutskever, R. Salakhutdinov, and J. B. Tenenbaum. Modelling relational data using Bayesian clustered tensor factorization. In Proc. NIPS, 2010.
L. Tang, H. Liu, J. Zhang, and Z. Nazeri. Community
evolution in dynamic multi-mode networks. In Proc.
SIGKDD, pages 677–685, 2008.
S. Zhu, K. Yu, and Y. Gong. Stochastic relational models
for large-scale dyadic data using mcmc. In Proc. NIPS,
2009.