Noname manuscript No.
(will be inserted by the editor)

Robust Unsupervised Cluster Matching for Network Data
Tomoharu Iwata · Katsuhiko Ishiguro

Received: date / Accepted: date

Abstract Unsupervised cluster matching is a task to find matching between clustersof objects in different domains. Examples include matching word clusters in different
languages without dictionaries or parallel sentences and matching user communities
across different friendship networks. Existing methods assume that every object is
assigned into a cluster. However, in real-world applications, some objects would notform clusters. These irrelevant objects deteriorate the cluster matching performancesince mistakenly estimated matching affect on estimation of matching of other objects. In this paper, we propose a probabilistic model for robust unsupervised cluster
matching that discovers relevance of objects and matching of object clusters, simultaneously, given multiple networks. The proposed method finds correspondence only
for relevant objects, and keeps irrelevant objects unmatched, which enables us to improve the matching performance since the adverse impact of irrelevant objects is eliminated. With the proposed method, relevant objects in different networks are clusteredinto a shared set of clusters by assuming that different networks are generated froma common network probabilistic model, which is an extension of stochastic blockmodels. Objects assigned into the same clusters are considered as matched. Edges forirrelevant objects are assumed to be generated from a noise distribution irrespectiveof cluster assignments. We present an efficient Bayesian inference procedure of the
proposed model based on collapsed Gibbs sampling. In our experiments, we demonstrate the effectiveness of the proposed method using synthetic and real-world data
sets, including multilingual corpora and movie ratings.
T. Iwata
NTT Communication Science Laboratories
2-4 Hikaridai, Seikacho, Sorakugun, Kyoto, 619-0237, Japan
Tel.: +81-774-93-5161
Fax: +81-774-93-5155
E-mail: iwata.tomoharu@lab.ntt.co.jp
K. Ishiguro
NTT Communication Science Laboratories

2

Tomoharu Iwata, Katsuhiko Ishiguro

Keywords unsupervised learning · object matching · network modeling · multilingual corpus analysis · stochastic block model

1 Introduction
Network analysis has become an important tool for a wide variety of fields, such associology, biology and information engineering (Albert and Barabási, 2002). Many
networks from different fields exhibit common characteristics. For example, we canfind heavy-tailed degree distributions, or scale-free properties, in collaboration networks, World Wide Web, power grid and protein-protein interaction networks (Barabási
and Albert, 1999). Other examples of commonly found structures include the small
world property (Watts and Strogatz, 1998), community structure (Girvan and Newman, 2002) and hierarchical structure (Clauset et al, 2008).
We consider situations in which different networks contain common latent clusters, where each cluster exhibits a particular interaction pattern to other clusters. For
example, lexical networks from different languages would have similar synonym
groups that have characteristic dependencies between the groups, social networks
from different research labs would share similar relationship patterns among faculty,
post-docs and students, and biological networks from different species would havesome common components.
Our task is to discover common latent clusters of objects, or to find matching
between clusters, in different networks without correspondence information, which
we call unsupervised cluster matching. An example is to find common word clusters from document-word networks in English and German without dictionaries orparallel sentences. Other examples include matching user communities across different friendship networks, and matching genes groups in gene regulatory networks
from different species. Some unsupervised cluster matching methods, such as ReMatch (Iwata et al, 2016), have been proposed, where every object is assumed to
be assigned into a cluster. However, in real-world applications, some objects would
not form clusters. We call these objects that do not form clusters with other objects
as irrelevant objects, and objects that form clusters as relevant objects. The irrelevant objects deteriorate the cluster matching performance since mistakenly estimatedmatching affect on estimation of matching of other objects.
We propose a probabilistic model for robust unsupervised cluster matching that
discovers relevance of objects and matching of object clusters, simultaneously, given
multiple networks. The proposed method finds correspondence only for relevant objects, and keeps irrelevant objects unmatched, which enables us to improve the matching performance since the adverse impact of irrelevant objects is eliminated. With theproposed method, relevant objects in different networks are clustered into a shared setof clusters by assuming that different networks are generated from a common network
probabilistic model, where interaction patterns between clusters are shared among
different networks. We use infinite relational models (Kemp et al, 2006), which is anextension of stochastic block models (Wang and Wong, 1987; Nowicki and Snijders,
2001) with Bayesian nonparametrics, as a basic component for modeling relevant objects in a single network. Objects assigned into the same clusters are considered asRobust Unsupervised Cluster Matching for Network Data

3

matched. Edges for irrelevant objects are assumed to be generated from a noise distribution irrespective of cluster assignments. We name the proposed method as subset
ReMatch (subset relational matching).
Figure 1 shows an example of the output result with the proposed method when
two bipartite networks are given as input. Each plot represents the adjacency matrix, where a dot at (i, j) indicates existence of an edge between the ith Type1 object
and the jth Type2 object. Here, Type1 and Type2 objects are e.g. documents andwords, respectively, in a document-word bipartite network. Note that input networks
is not restricted to bipartite networks; they can be networks with a single type such as
person-person networks, those with multiple types such as user-item-tag networks,
or those with multiple relations such as ‘like’ and ‘hate’ relations. In addition, theproposed method can handle more than two networks. The number of objects can bedifferent across different networks; the adjacency matrix size of Networks 1 and 2
is (120 × 140) and (90 × 110), respectively, in this example. The proposed method
outputs relevance for each object and cluster assignments for relevant objects. In Figure 1(b), objects are sorted by their relevance and cluster assignments. The red lines
indicates the border of clusters, and the lower right region that is not surrounded by
red lines represents edges of irrelevant objects. The cluster assignments indicate theircorrespondence; for instance, with Type2, objects 1–20 in Network1 and objects 1–20
in Network2 are matched since they are assigned into cluster ‘a’, and objects 21–60
in Network1 and objects 21–40 in Network2 are matched since they are assigned
into cluster ‘b’. Clusters in different networks have similar connectivities; The first
Type2 cluster ‘a’ has a high link probability to the first Type1 cluster ‘A’, but has a
low link probability to the second Type1 cluster ‘B’, in both networks. Some clusters
can appear only in a network; the fourth Type1 cluster ‘D’ does not appear in Network1, but appears in Network2. With the proposed method, the number of clusters
is automatically inferred using Dirichlet processes. Irrelevant objects are connectedirrespective of their partners’ cluster assignments. The number of irrelevant objects
can be different among networks; there are no irrelevant Type1 objects in Network2.
The paper is organized as follows: In Section 2, related work is briefly outlined. In
Section 3, we propose a probabilistic model for robust unsupervised cluster matchingthat discovers relevance and cluster matching from multiple networks without correspondence. In Section 4, an efficient Bayesian inference procedure of the proposedmodel based on collapsed Gibbs sampling is presented. In Section 5, we describe
connection between the proposed model and a closely related existing model. In Section 6, we experimentally demonstrate the effectiveness of the proposed model by using synthetic and real data sets, which include multilingual word clustering without
dictionaries/aligned-texts. Finally, we present concluding remarks and a discussionof future work in Section 7.

2 Related work
Object matching is the task of finding correspondence between objects in different
domains, such as images and annotations (Socher and Fei-Fei, 2010), user identifiersin different databases (Li et al, 2009), sentences written in different languages (Gale4Tomoharu Iwata, Katsuhiko Ishiguro
0
0

20

10
20
30
Type1 Objects

Type1 Objects

40

60

80

40
50
60
70

100

80

120
0

20

40

60

80

100

120

90
0

140

20

40

Type2 Objects

60

80

100

Type2 Objects

Network1

Network2(a) Input

0

a

b

c

irrelevant
0

a

b

c

irrelevant

A
20

10

A
Sorted Type1 Objects

Sorted Type1 Objects

B 40
60

C
80

20
30

B 40
50
60

C

irrelevant

70

100
80

D

120
0

20

40

60

80

100

120

140

90
0

Sorted Type2 Objects

20

40

60

80

100

Sorted Type2 Objects

Network1

Network2(b) Output

Fig. 1 Example of the input and output for the proposed method.

and Church, 1991; Rapp, 1999). Most object matching methods involve similarity or
correspondence information. However, the information is unavailable in some applications because of its high cost or privacy protection.
For this situation, a number of unsupervised object matching methods, e.g. matching canonical correlation analysis (Haghighi et al, 2008), kernelized sorting (Quadrianto
et al, 2010), convex kernelized sorting (Djuric et al, 2012), least square object matching (Yamada and Sugiyama, 2011) and Bayesian object matching (Klami, 2013,2012), and unsupervised cluster matching methods, e.g. many-to-many matching latent variable models (Iwata et al, 2013) and ReMatch (Iwata et al, 2016), have been
proposed. Intuitively, they find matching using relationship of objects within a domain, since distance between objects in different domains cannot be calculated with
unsupervised setting, but distance between objects in the same domain can be calculated. When irrelevant objects exist, the relationship is distorted, and the performance of these methods would be deteriorated. On the other hand, with the proposed
method, the relationship within a domain is maintained by introducing relevance.
Another advantage of the proposed method over existing unsupervised object matching methods is the proposed method can handle different numbers of objects. The

Robust Unsupervised Cluster Matching for Network Data

5

Table 1 Notation.
Symbol
D
Ndt
Kt
xdnm
zdtn
rdtn

Description
number of networks
number of Type-t objects in network dnumber of realized clusters for Type-t
edge existence between the nth Type1 object and the mth Type2 object in network d,
xdnm ∈ {0, 1}
cluster assignment of the nth Type-t object in network d, zdtn ∈ {0, 1, · · · , ∞}relevance of the nth Type-t object in network d, rdtn ∈ {0, 1}

proposed method is an extension of the ReMatch (Iwata et al, 2016), which is anunsupervised cluster matching method for network data, for noisy data. By clustering only relevant objects, the proposed method can obtain intuitive cluster matching
results compared with the ReMatch.
There have been proposed many methods for discovering latent clusters from asingle network, such as the stochastic block model (Wang and Wong, 1987; Nowicki and Snijders, 2001), mixed membership stochastic block model (Airoldi et al,2008), infinite relational model (IRM) (Kemp et al, 2006), and subset IRM (Ishiguro
et al, 2012). However, these methods cannot discover shared groups from multiple
networks. The proposed method corresponds to applying the subset IRM to a single large network that is constructed by combining all the networks, where edges
between different networks are assumed to be missing.
3 Proposed model
Suppose that we are given D bipartite networks X = {Xd }D
d=1 , where Xd =Nd1 Nd2{{xdnm }n=1 }m=1 is the dth network, and xdnm ∈ {0, 1} indicates existence ofan edge between the nth Type1 object and the mth Type2 object. Our notation issummarized in Table 1. Although we assume that given data are bipartite networks
for simplicity, the proposed model is applicable to networks with a single type, thosewith more than two types, and those with multiple relations.
The model proposed for this task is a probabilistic generative model of multiple
networks. We assume that there are two classes of objects: 1) relevant objects thathave hidden common structure and are connected depending on their latent cluster
assignments, and 2) irrelevant objects that are noisy and are randomly connected toother objects. A latent relevancy variable rdtn ∈ {0, 1} is associated with each object,
where rdtn = 1 if it is relevant and rdtn = 0 otherwise. For modeling networks forrelevant objects, the proposed model is based on an IRM (Kemp et al, 2006), but
is extended for multiple networks by sharing clusters and connectivity parameters.
The proposed model assumes that there are potentially a countably infinite numberof clusters for each type, and clusters are shared across different networks. Eachrelevant object is assigned into a cluster zdtn ∈ {1, · · · , ∞}. An edge between two
relevant objects is generated depending on their cluster assignments. In particular, theprobability of connecting objects assigned into clusters k and ℓ is assumed to be θkℓ ,which is common across all networks. An edge for irrelevant objects are generated
randomly with probability ϕ, which does not depend on the cluster assignment of6Tomoharu Iwata, Katsuhiko Ishiguro

Networks2

Networks1

cluster assignments for Type2: z

cluster assignments for Type2: z

acluster
assignments
for Type1: z

a

C

B

26

b

c

a
cluster
assignments
for Type1: z

irrelevant

C

A

B

5 10
18

b

23
11

97
6

4
c

irrelevantabc

5 10 1 8 11 2 3 4 9 7 6

13
7
A
28
5

B

64

C

C

1 3 7 2 8 5 6 4 9

A
43
58
11

93

56
c

3 8 7 1 10 4 5 6 9 3

7 10
61

B

b

14
10

7 10 6 1 4 3 11 5 8 2 6

A

38
7

9

irrelevant

irrelevant

a

b

c

A

0.9 0.2 0.3

B

0.1 0.2 0.8

C

0.1 0.8 0.2

0.2
connectivity for irrelevant objects: φconnectivity for relevant objects: θ

Fig. 2 Generative process of two bipartite networks with the proposed model.

the opponent object. Figure 2 shows an illustration of the generative process of two
bipartite networks with the proposed model.
The proposed model generates multiple bipartite networks X according to thefollowing process:1. Draw connectivity for irrelevant objects ϕ ∼ Beta(a, b)
2. For each cluster for Type1: k = 1, · · · , ∞(a) For each cluster for Type2: ℓ = 1, · · · , ∞i. Draw connectivity for relevant objects θkℓ ∼ Beta(c, d)
3. For each type: t = 1, 2(a) Draw relevance probability λt ∼ Beta(e, f )(b) For each network: d = 1, · · · , D
i. For each object: n = 1, · · · , Ndt
A. Draw relevance
rdtn ∼ Bernoulli(λt )B. Draw cluster assignment
zdtn ∼ CRP(αt ) if rdtn = 1
zdtn = 0otherwise
1. For each network: d = 1, · · · , D(a) For each object of Type1: n = 1, · · · , Nd1
i. For each object of Type2: m = 1, · · · , Nd2
A. Draw relation
d1n rd2m 1−rd1n rd2m)
xdnm ∼ Bernoulli(θzrd1n
zd2m ϕRobust Unsupervised Cluster Matching for Network Data

c

θ ∞x∞

d
α1

e
f

z

λ1

7

x

r

N1

a

φ

b
z

α2

r

λ2
N2 D

e
f

Fig. 3 Graphical model representation of the proposed model for bipartite networks.

Here, CRP(α) indicates the Chinese restaurant process (Blackwell and MacQueen,1973) with concentration parameter α, which is a representation of Dirichlet processes, and I(A) = 1 if A is true, I(A) = 0 otherwise. By using the CRP, the numberof clusters can be automatically estimated from a given data. We use beta distributions
for priors of Bernoulli parameters, ϕ, θ = {θkℓ }, λ = {λt }, since the beta distribution is the conjugate prior of the Bernoulli distribution, which enables us to develop
an efficient Bayesian inference algorithm as describe in Section 4. At the last line of
the generative process, an edge is generated using the Bernoulli distribution, where
the probability is θzd1n zd2m when both objects are relevant because rd1n rd2m = 1,
and it is ϕ when either object is irrelevant. Figure 3 shows graphical model representation of the proposed model, where shaded and unshaded nodes indicate observed
and latent variables, respectively.
The joint distribution of networks X, cluster assignments Z = {zdtn } and relevance R = {rdtn } given hyperparameters α = {α1 , α2 }, a, b, c, d, e, f is describedas follows:p(X, Z, R|α, a, b, c, d, e, f ) = p(R|e, f )p(Z|R, α)p(X|Z, R, a, b, c, d).

(1)

The first factor on the right hand side of (1) is calculated byp(R|e, f ) =

2 ∫ ∏
D N
dt
∏
∏
t=1

=

p(rdtn |λt )p(λt |e, f )dλt

d=1 n=1

2∏
B(e + Lt1 , f + Lt0 )
t=1

B(e, f )

(2)

where
Ltr =

Ndt
D ∑
∑

rdtn ,(3)

d=1 n=1(f )is the number of Type-t objects with relevance r, and B(e, f ) = ΓΓ(e)Γ
(e+f ) is thebeta function. The Bernoulli parameters λt are analytically integrated out by using

8

Tomoharu Iwata, Katsuhiko Ishiguro

conjugate Beta distribution priors p(λt |e, f ) = Beta(e, f ). The second factor of (1)is given by∏Kt
2∏
αKt k=1(Mtk − 1)!
p(Z|R, α) =,(4)α (αt + 1) · · · (αt + Mt − 1)t=1 t
since cluster assignments are drawn from the Chinese restaurant process for relevant
objects and deterministic functions for irrelevant objects. Here,
Mtk =

Ndt
D ∑
∑

rdtn I(zdtn = k),(5)d=1 n=1∑Kt
is the number of Type-t relevant objects assigned to cluster k, Mt = k=1
Mtk isthe total number of Type-t relevant objects, and Kt is the current number of realized
clusters for Type-t. The third factor of (1) is given by
∫ ∏
D N
d1 N
d2
∏
∏
p(X|Z, R, a, b, c, d) =(1 − rd1n rd2m )p(xdnm |ϕ)p(ϕ|a, b)dϕ
d=1 n=1 m=1

×

∫ ∏
D N
d1 N
d2
∏
∏

rd1n rd2m p(xdnm |θzd1n zd2m )p(θ|c, d)dθ

d=1 n=1 m=1

B(a + Q, b + Q̄) ∏1 ∏2 B(c + Nkℓ , d + N̄kℓ ),B(a, b)B(c, d)
K

=

K

(6)

k=1 ℓ=1

where relations between relevant objects, {(d1n, d2m)|rd1n rd2m = 1}, are drawn
from a cluster-dependent distribution Bernoulli(θzd1n zd2m ), and the other relations,{(d1n, d2m)|rd1n rd2m = 0}, are drawn from Bernoulli(ϕ). The Bernoulli parameters, θ = {θkℓ }, ϕ, are analytically integrated out due to their conjugate priors. Here,
Q=

Nd1 ∑
Nd2
D ∑
∑

(1 − rd1n rd2m )xdnm ,(7)

d=1 n=1 m=1

is the number of edges for irrelevant objects,
Q̄ =

Nd1 ∑
Nd2
D ∑
∑

(1 − rd1n rd2m )(1 − xdnm ),(8)d=1 n=1 m=1

is the number of non-edges for irrelevant objects,
Nkℓ =

Nd1 ∑
Nd2
D ∑
∑

rd1n rd2m I(zd1n = k)I(zd2m = ℓ)xdnm ,(9)

d=1 n=1 m=1

is the number of edges between clusters k and ℓ for relevant objects, andN̄kℓ =

Nd1 ∑
Nd2
D ∑
∑

rd1n rd2m I(zd1n = k)I(zd2m = ℓ)(1 − xdnm ),d=1 n=1 m=1

is the number of non-edges between clusters k and ℓ for relevant objects.

(10)Robust Unsupervised Cluster Matching for Network Data

9

4 Inference
We describe the inference procedures for the proposed model based on collapsed
Gibbs sampling (Kemp et al, 2006). The parameters, ϕ, θ = {θkℓ } and λ = {λt },can be analytically marginalized out thanks to their conjugacy. The unknown latentvariables to be inferred are cluster assignments Z = {zdtn } and relevance R ={rdtn }. We sample zdtn and rdtn simultaneously. Given the current state of all but
one latent assignment (zi , ri ), where i = (d, t, n), a new value for (zi , ri ) is sampledfrom the following probability,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 ),(11)where the superscript \i denotes the set or value when excluding object i, X+i =dt̄{xdnm }N
m=1 is the set of edges for object i, t̄ = 1 if t = 2 and t̄ = 2 if t = 1, andthis is derived from (1). Here, we omit the hyperparameters for simplicity. When theobject is irrelevant ri = 0, its cluster assignment is always zi = 0. When the object isrelevant ri = 1, its cluster assignment is sampled from existing clusters {1, · · · , Kt }or a new cluster Kt + 1. Since we sample a cluster assignment for each object, there
is no probability that zi becomes greater than Kt + 1. The first factor is calculated byp(zi = k, ri |Z\i , R\i )p(ri , R\i )p(zi = k, Z\i |ri , R\i )p(R\i )p(Z\i |R\i )\i
if ri = 0, zi = 0,
f + Lt0


\i

Mtk
\i
∝ (e + Lt1 ) αt +∑K′t M \i′ if ri = 1, zi = k ∈ {1, · · · , Kt },
k =1
tk


α

(e + L\i
if ri = 1, zi = Kt + 1,
∑K t
\i
t1 )
=

αt +

k′ =1

(12)

Mtk′

using (2) and (4). The second factor for irrelevant objects is calculated byp(X+i |zi = 0, ri = 0, X\i , Z\i , R\i )=p(X+i , X\i |zi = 0, Z\i , ri = 0, R\i )p(X\i |Z\i , R\i )=B(a + Q\i + Q+i0 , b + Q̄\i + Q̄+i0 ),B(a + Q\i , b + Q̄\i )(13)using (6), where the superscript +i0 denotes that the same statistics are computed on
X+i assuming ri = 0. Similarly, the second factor for relevant objects is calculated
as follows,p(X+i |zi = k, ri = 1, X\i , Z\i , R\i )=×

B(a + Q\i + Q+i1 , b + Q̄\i + Q̄+i1 )B(a + Q\i , b + Q̄\i )
Kt̄
\i
\i
∏
B(c + N + N +ik , d + N̄ + N̄ +ik )
kℓ

ℓ=1

kℓ
\i

kℓ
\i

B(c + Nkℓ , d + N̄kℓ )

kℓ

,

(14)

10

Tomoharu Iwata, Katsuhiko Ishiguro

Algorithm 1 Inference procedure for the proposed model.
initialize cluster assignments Z, relevance R, and hyperparameters α, a, b, c, d, e, f
repeatfor d = 1 to D dofor t = 1 to 2 dofor n = 1 to Ndt dosample cluster assignment zdtn and relevance rdtn by (11)end forend forend forsample hyperparameters α, a, b, c, d, e, f by (15)until end condition is met

where the superscript +ik denotes that the same statistics are computed on X+i assuming ri = 1 and zi = k.
We fit hyperparameters α, a, b, c, d, e, f by posterior sampling assuming Gamma
priors. In particular, we sample the value of hyperparameter a according to the following posterior probability:p(a = â|X, Z, R, α, b, c, d, e, f ) ∝ p(a = â)p(X, Z, R|α, a = â, b, c, d, e, f ),(15)
In our experiments, we used p(a) = Gamma(5, 5), and ten candidates of â are generated for each sampling. The other hyperparameters α, b, c, d, e, f are sampled in
the same way.
By iterating sampling of cluster assignments and relevance variables for all objects and sampling of hyperparameters, we obtain an estimate of posteriors. Algorithm 1 summarizes the inference procedure for the proposed model. We initialize
cluster assignments relevance and hyperparameters randomly. We use the last sample of the cluster assignments in the inference for matching. When initial assignments are different, different cluster assignments are obtained after the sampling.
The∑computational
complexity for each iteration of the collapsed Gibbs sampling isD ∑TO( d=1 t=1 Ndt Kt ) since we calculate probabilities of Kt + 1 clusters for each∑D ∑T
object, and there are d=1 t=1 Ndt objects in total.
Although all parameters are marginalized out during the inference, the posteriorsof parameters are calculated using the samples as follows,p(ϕ|X, Z, R) = Beta(a + Q, b + Q̄),p(θkℓ |X, Z, R) = Beta(c + Nkℓ , d + N̄kℓ ),

(16)
(17)

p(λt |X, Z, R) = Beta(e + Lt1 , f + Lt0 ).

(18)

5 Relationship with ReMatch
The ReMatch (Iwata et al, 2016) is an unsupervised cluster matching method for
network data, which corresponds to the proposed model without relevance variables.
In particular, the ReMatch assumes the following generative process:Robust Unsupervised Cluster Matching for Network Data

c

11

θ ∞x∞

d
α1

z
N1

x

α2

z
N2 D

Fig. 4 Graphical model representation of the ReMatch for bipartite networks.

1. For each cluster for Type1: k = 1, · · · , ∞(a) For each cluster for Type2: ℓ = 1, · · · , ∞i. Draw connectivity θkℓ ∼ Beta(c, d)
2. For each type: t = 1, 2(a) For each network: d = 1, · · · , D
i. For each object: n = 1, · · · , Ndt
A. Draw cluster assignment zdtn ∼ CRP(αt )1. For each network: d = 1, · · · , D(a) For each object of Type1: n = 1, · · · , Nd1
i. For each object of Type2: m = 1, · · · , Nd2
A. Draw relation
xdnm ∼ Bernoulli(θzd1n zd2m )Figure 4 shows graphical model representation of the ReMatch.
The ReMatch assigns all objects into shared clusters even if they are irrelevant. In
real-world applications, some objects would not form clusters. These irrelevant objects deteriorate the cluster matching performance since mistakenly estimated matching affect on estimation of matching of other objects. On the other hand, the proposedmodel assigns only relevant objects into shared clusters, which enables us to handle
noisy observation, and improve the performance.

6 Experiments
6.1 Synthetic data
We evaluated the proposed subset ReMatch by using the following three types ofsynthetic data sets with two bipartite networks: Noisy-Dirichlet, Noisy-Partial andDirichlet. With the Noisy-Dirichlet data, cluster proportions were generated from asymmetric Dirichlet distribution for each type and for each network, where there were
100 relevant objects, 20 irrelevant objects and five clusters for each type. With the
Noisy-Partial data, some clusters appear in either network. In particular, there were
five clusters, but the first/last cluster does not appear in Network2/Network1. There
were 20 relevant objects for each cluster and 20 irrelevant objects for each type. The
Dirichlet data is the same with the Noisy-Dirichlet data except that there were noirrelevant objects. With all data sets, the edge probability was generated from a beta

12

Tomoharu Iwata, Katsuhiko Ishiguro
a

b

c

d

irrelevant

e

a

0

b cd e0A

irrelevant

A
20

B

B
40

20

40

C

C 60

60

D
80

80

D
E

E
100

100

irrelevant

irrelevant

120

120

0

20

40

60

80

100

120

0

20

Network1

40

60

80

100

120

Network2(a) Noisy-Dirichlet

a

b

c

irrelevant

d

a

A

10

A

30

B

50

C

10

30

50
60

60

D

irrelevant

d

40

40

C

c

20

20

B

b

0

0

70

D

70
80

80
irrele- 90
vant

90

irrelevant

100

100
0

20

40

60

80

0

100

20

Network1

40

60

80

100

Network2(b) Noisy-Partial

a

b

e

d

c

a

0

0

10

10

b

c

e

A
20

20

30

A

30

40

40

B
50

50

60

C 60

70

B

D 70

C 80
D 90

E 90

E

80

100

100

0

20

40

60

80

100

0

Network1

20

40

60

80

100

Network2(c) Dirichlet

Fig. 5 Examples of the synthetic data sets. Objects are aligned by their cluster assignments and the redlines indicate the border of clusters. The lower right region that is not surrounded by red lines represents
edges of irrelevant objects in the Noisy-Dirichlet and Noisy-Partial data.

distribution, Beta( 12 , 12 ), and edges were generated according to a Bernoulli distribution depending on the assigned clusters. Figure 5 shows examples of the synthetic
data sets.
We compared the proposed method with the following four methods: ReMatch,
MMLVM, IRM+KS and KS. The ReMatch is an unsupervised cluster matching method
for network data (Iwata et al, 2016), and it corresponds to the proposed method without irrelevant objects. The MMLVM is the many-to-many matching latent variableRobust Unsupervised Cluster Matching for Network Data

13

model (Iwata et al, 2013). It is an unsupervised cluster matching method for realvalued data, where Gaussian noise is assumed for observation. The KS is the convex
kernelized sorting (Djuric et al, 2012), which is an unsupervised object matching
method that finds one-to-one matching and does not cluster objects. The IRM+KS is
the combination of the IRM and KS, where objects are clustered for each network
individually, and then the obtained clusters are matched by the convex kernelized
sorting.
For the evaluation measurement, we used matching adjusted Rand index (MARI) (Iwata
et al, 2016). The MARI becomes high when pairs of matched/unmatched objects indifferent networks were correctly assigned into the same/different clusters, and it becomes low when they were incorrectly assigned. It takes the value from -1 to 1, andgives 0 for random cluster matching. In particular, the MARI for Type-t is calculatedby
MARIt =

ht1 + ht2 − µt,
Nt1 Nt2 − µt(19)where ht1 (ht2 ) is the number of object pairs in different networks that are correctly
assigned into the same (different) clusters both in the estimated and true assignments,
and µt is the expected value of ht1 + ht2 , which is obtained byµt =(ht1 + ht3 )(ht1 + ht4 ) + (ht2 + ht3 )(ht2 + ht4 ),Nt1 Nt2(20)

where ht3 (ht4 ) is the number of object pairs in different networks that are incorrectly
assigned into the same (different) clusters in the estimation but assigned into thedifferent (same) clusters in the true assignments. With the proposed method, the setof irrelevant objects are considered as a cluster when the MARI was calculated.
Table 2 shows the MARI with the synthetic data sets. In all cases, the proposed
method achieved the best MARI. With the Dirichlet data, which did not contain any
irrelevant objects, the MARI of the proposed method and ReMatch were comparable.
This result indicates that the performance of the proposed method is not deteriorated
even when given networks consist of only relevant objects. The performance of the
MMLVM was low since it assumes Gaussian noise, which is not appropriate for network data. On the other hand, the proposed model assumes Bernoulli noise, which isa natural assumption for network data. The MARI achieved by KS was low since itdoes not cluster objects. By clustering objects using IRM, IRM+KS improved the performance compared with KS. However, it did not outperform the proposed method,
because errors accumulated in clustering by IRM cannot be corrected in the matching process with KS. In contrast, since the proposed method performs clustering andmatching simultaneously, it can find clusters that are appropriate when matched.

6.2 Real-world data
Next, we evaluated the proposed method by using the following four real-world data
sets: 20News, NIPS, Movie and Multilingual. The 20News data consisted of binary
occurrence data for 100 words in documents obtained from 20 Newsgroups data

14

Tomoharu Iwata, Katsuhiko Ishiguro

Table 2 Matching adjusted Rand indices with the synthetic data sets and their standard errors, which wereaveraged over 100 experiments for each data set. The values in bold are not significantly different from thebest performing method in each row according to a paired t-test.
Proposed
ReMatchMMLVM
IRM+KS
KS
Noisy-Dirichlet 0.579 ± 0.029 0.463 ± 0.030 0.228 ± 0.023 0.069 ± 0.021 0.008 ± 0.001
Noisy-Partial
0.684 ± 0.021 0.579 ± 0.021 0.326 ± 0.018 0.062 ± 0.019 0.008 ± 0.001
Dirichlet
0.454 ± 0.036 0.438 ± 0.036 0.148 ± 0.026 0.124 ± 0.027 0.002 ± 0.001

set (Lang, 1995) 1 . The documents were categorized into the following four categories: Computers, Recreation, Science and Talk. We generated two disjoint sets of
documents, where 250 documents were sampled for each category, and created two
document-word networks with size (1000 × 100). The two networks contained thesame set of 100 words although their correspondence were assumed to be unknown.
The NIPS data consist of binary word occurrence data for the NIPS conference
papers from 2001 to 2003 2 . There were 593 documents, and vocabulary size was
13,762. We split the documents and words into two disjoint sets, and created two
document-word networks with size (296 × 6881) and (297 × 6881). The papers werecategorized in 13 categories, such as Algorithms & Architectures, Applications and
Neuroscience.
The Movie data consist of movie ratings obtained from the Eachmovie data set,
where a movie and a user are linked when the user has rated the movie. We omit theusers that rated less than 50 movies, and split the movies and users into two disjoint
sets, and created two movie-user networks with size (507 × 7180). The movies werecategorized into ten genres, such as Action, Comedy and Romance.
The Multilingual data were obtained from Wikipedia articles in English, German,
Italian and Japanese in the following five categories: Nobel laureates in Physics, Nobel laureates in Chemistry, American basketball players, American composers andEnglish footballers. We created two document-word networks for each pair of languages, where 50 documents were sampled for each category that appeared in bothlanguages. We used 1,000 frequent words after removing stop-words for each language. The size of a created document-word network was (150 × 1000). Note that
20News, NIPS and Movie data were not originally multiple networks and therefore
we split objects into two networks randomly, but the Multilingual data were originallymultiple networks.
For comparing methods with real-world data, we used the ReMatch, MMLVM
and IRM+KS. We excluded KS, since they were not effective and took too long computational time with large networks as shown Tables 2 and 4. The average MARIscores with the real-world data sets are shown in Table 3. The proposed method
achieved the highest MARI with all data sets. This result implies that inferring relevance of objects is effective for find matching in noisy real-world network data. Withthe 20News data, there were no significant difference between the proposed method
and ReMatch. It would be because words were completely shared across two different
networks with the 20News data, and noise was small compared with the other data
1
2

Available at http://www.cs.nyu.edu/˜roweis/data.html
Available at http://ai.stanford.edu/˜gal/Robust Unsupervised Cluster Matching for Network Data

15

Table 3 Matching adjusted Rand indices with the real-world data sets and their standard errors, whichwere averaged over 30 experiments for each data set. The values in bold are not significantly different
from the best performing method in each row according to a paired t-test.
Proposed
0.178 ± 0.011
0.221 ± 0.004
0.049 ± 0.001
0.203 ± 0.026
0.263 ± 0.026
0.244 ± 0.022
0.208 ± 0.023
0.165 ± 0.019
0.262 ± 0.024

20NewsNIPS
Movie
English-German
English-ItalianEnglish-Japanese
German-ItalianGerman-Japanese
Italian-Japanese

ReMatch0.153 ± 0.015
0.174 ± 0.005
0.045 ± 0.000
0.118 ± 0.021
0.160 ± 0.021
0.188 ± 0.014
0.130 ± 0.017
0.090 ± 0.017
0.213 ± 0.017

MMLVM
0.030 ± 0.001
NANA
0.098 ± 0.008
0.102 ± 0.010
0.069 ± 0.012
0.087 ± 0.008
0.042 ± 0.009
0.078 ± 0.010

IRM+KS−0.009 ± 0.010
0.005 ± 0.011
0.001 ± 0.001−0.004 ± 0.012
0.011 ± 0.011−0.001 ± 0.007−0.007 ± 0.009
0.013 ± 0.012
0.022 ± 0.011

Table 4 Computational time with the Noisy-Dirichlet data with 500 relevant objects for each type and foreach network.
Proposed
10 minutes
9 minutes
2 hours
38 hours
1 hourNoisy-Dirichlet
20NewsNIPS
Movie
English-German

ReMatch
9 minutes
4 minutes
2 hours
4 hours
13 minutes-0.135

MMLVM
7 hours
10 hoursNANA
25 hours

IRM+KS
4 minutes
8 minutes
4 hours
4 hours
25 minutesKS
13 hours
NA
NA
NA
NA

-0.19
-0.195-0.14-0.2-0.145-0.205
-0.21

-0.15

-0.215-0.155-0.22-0.16-0.225
0

20

40

60

80

100

120

140

160

180

200

0

20

40

60

(a) 20News

80

100

120

140

160

180

200

120

140

160

180

200

(b) NIPS

-0.16

-0.22

-0.165

-0.23

-0.17

-0.24

-0.175

-0.25

-0.18

-0.26

-0.185

-0.27

-0.19

-0.28

-0.195

-0.29
0

20

40

60

80

100

(c) Movie

120

140

160

180

200

0

20

40

60

80

100

(d) English-German

Fig. 6 Averaged training log likelihoods for each iteration in the inference.

sets. The results by the MMLVM with NIPS and Movie data sets were not available
due to its high computational cost.

16

Tomoharu Iwata, Katsuhiko Ishiguro

1

matching ARI

0.8

0.6

0.4

0.2

0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

data index

categories

Fig. 7 Box plot of the MARI with different initializations using 30 Noisy-Dirichlet data sets. For eachdata set, we conducted 30 runs with different initializations. The bottom and top of the box are the first
and third quartiles, the bar inside the box is the median, and red ‘×’ indicates the MARI of the best log
likelihood.
1
2
3
4
5

1
2
3
4
5
2

4

6

8

1
2
3
4
5

1
2
3
4
5
2

4

6

8

10

1
2
3
4
5
2

4

6

8

(a) English-German

2

4

6

8

2

4

6

8

1
2
3
4
5
2

4

6

8

clusters(b) English-Italian

10(c) English-JapaneseFig. 8 Confusion matrices of the proposed method with the Multilingual data. The horizontal axis is thecluster index, and the vertical axis is the category index, 1: Nobel laureates in Physics, 2: Nobel laureates in Chemistry, 3: American basketball players, 4: American composers, and 5: English footballers.
The brighter element indicates the larger number of documents in the category is assigned into the cluster. The top row shows the confusion matrix of English, and the bottom-most row shows that of German/Italian/Japanese.

Table 4 shows the computational time. The proposed method, ReMatch and IRM+KS
are efficient. The KS requires long computational time since the computational complexity of KS is cubic in the number of objects. The IRM+KS does not take a longtime since KS is applied not to objects but to clusters, where the number of clusters
was much smaller than the number of objects. The MMLVM is inefficient because
it requires matrix inversion for the inference. Figure 6 shows the averaged training
log likelihoods of the proposed method for each iteration in the inference with thereal-world data sets. The log likelihoods became high with about 100 iterations.
Figure 7 shows the sensitivity of the proposed model to different initialization.
With some data sets, the variance is high, which indicates high sensitivity. However,when we selected a result according to the log likelihood (1), its MARI was high,Robust Unsupervised Cluster Matching for Network Data

17

Table 5 Word clusters with the proposed method in the Multilingual data. Each pair of rows corresponds to a cluster, the upper row shows words from English, and the lower row shows words from German/Italy/Japanese in each pair of rows. The bottom-most pair of rows shows irrelevant words. Japanesewords are translated in English.

EN
DE
EN
DE
EN
DE
EN
DE
EN
DE

(a) English-German
composers musicians recording recordings songs composer walk concert piano orchestra album
music life schrieb my jazz database movie is erschien at diskografie durchbruch komponistenbasketball draft nba sportspeople averaged kg lb pick mvp rebounds rookie ncaa
vereinigte basketballspieler nba draft basketballmatch goals cup clubs premier counted footballers friendly app gls fa uefa fifa manchester
englischer verein trainer united nationalmannschaft fc league englische tore kader manchester
prize laureates nobel
preisverleihung nobelstiftung nobelpreis
cooper eric felix dudley marcus phillips chairman receiving richardson fowler texas ramsey
school leistungen treffer lee high bevor ernannt william anerkennung sonstiges abschluss

EN
IT
EN
IT
EN
IT
EN
IT
EN
IT

(b) English-Italian
draft overall pro guard weight sportspeople thompson playoffs kg lb pick teammate assists
media game high team basketball rookie scelto finali ala scelta titoli assoluta assist mvp starrecording composers composer album piano musicians write recordings instrumental piececompositori compositore musicale tecniche album it me musicali band musicisti visita
manchester honours transfer fifa euro correct draw soccer premiership substitute beckham
manchester ferdinand presenze gol fifa cup premier neville reti centrocampista campbell ham
prize nobel laureatespremio premi vincito
appointed moore mitchell sir aaron richardson elected marcus todd charge anthony heat gilbert
van ottenne nominato wilson jack alan richardson londra membro national award britannici

EN
JP
EN
JP
EN
JP
EN
JP
EN
JP

(c) English-Japanesemusicians composers album composer grammy
performance piano classic history event instrument orchestra religion violin classic romansquad cup match goals premier clubs manchester counted footballers
commentary england soccer club birthday foot relieve united
fields alma mater professor institutions chemistry sciences physics faculty physicist scientists
physics william scholar strike professor frederick chemical issue richard phd mali max
johnson kevin retired jones round barry jordan teams basketball draft jackson thompson overall
victory performance enters player basketball namefellow lawrence retirement mitchell glenn howard cooper confirmed anthony donald moore
california london in chicago ray born source hertford al smith leave tony bra jack sony black

which is represented by ‘x’ in Figure 7. This result implies that the log likelihood isa good measurement to select a result from multiple runs.
Figure 8 shows the confusion matrices of the proposed method with the Multilingual data. The documents in the first and second categories, which were the Nobel
laureates in Physics and Chemistry, were assigned into the same clusters, e.g. the firstcluster in English-German. It is reasonable since they are closely related categories.
Although the proposed method could not discriminate the Nobel laureates in Physics
from those in Chemistry, it separated the Nobel laureates in Physics and Chemistryfrom the other categories. In addition, documents in the other categories were successfully assigned into different clusters. Some documents in the same category wereassigned into different clusters, e.g. documents in the fifth category, which was En-

18

Tomoharu Iwata, Katsuhiko Ishiguro(i) English
a

b

c

e

d

f

g

h

i

irrelevant

u

0

A

C
E

50

G 100

150

documents

0

100

200

300

400

500

600

700

800

900

1000

(ii) German
a

b

d

c

f

e

g

h

irrelevant

i

0
A
50
B
E

100

I
150
0

100

200

300

400

500

600

700

800

900

1000

700

800

900

1000

p

s

u

700

800

900

words
(a) Proposed(i) English
a

b

c

e

d

f

g

i

j

k

p

s

0
B
C
50
D
100
O
150

documents

0

100

200

300

400

500

600

(ii) German
a

b

c

d

e

i

j

k

0

A
C

50
F
100
Q
R
150
0

100

200

300

400

500

600

1000

words
(b) ReMatch
Fig. 9 Inferred shared latent clusters and relevance with the Multilingual English-German data (a) by the
proposed method, and (b) by the ReMatch.

glish footballer, were assigned into the third and fourth clusters in English-German.
It would be because the proposed method is an unsupervised method, and documentsin the same category could use different vocabulary.
Table 5 shows word clusters inferred by the proposed method with the Multilingual data. Related words were appropriately assigned into the same clusters acrossdifferent languages, e.g. in Table 5(a) the first, second, third and fourth cluster related
to music, basketball, football and Nobel prize, respectively. The words that were notrelated to a specific category were inferred as irrelevant, which were shown in thebottom-most pair of rows in the table, such as common family name, city name,common noun and verb.
Figure 9(a) shows the inferred shared latent clusters and relevance by the proposed method with the Multilingual English-German data. There were few irrelevantRobust Unsupervised Cluster Matching for Network Data

19(i) English
a

b

c

d

f

e

g

h

i

600

700

irrelevant

0
B
C
50
D
J

100

Q
150

documents

0

100

200

300

400

500

800

900

1000

(ii) Italian
a

b

c

d

e

f

g

h

irrelevant

i

0
A
B

50

C
D
100

150
0

100

200

300

400

500

600

700

800

900

1000

words
Fig. 10 Inferred shared latent clusters and relevance by the proposed method with the MultilingualEnglish-Italian data.

(i) English
a

b

g

e

d

c

h

i

irrelevant

k

0
A
C 50
E
F
100
I
150

documents

0

100

200

300

400

500

600

700

800

j

k

700

800

900

1000

(ii) Japanese
a

b

c

d

e

f

g

h

i

irrelevant

0
A
B 50
C
D
100

150
0

100

200

300

400

500

600

900

1000

words
Fig. 11 Inferred shared latent clusters and relevance by the proposed method with the MultilingualEnglish-Japanese data.

documents, but many irrelevant words. It is natural since all documents were sampledfrom the specific categories, but some words were not specific to a single category.
The irrelevant words, which were shown in the right region, have edges to documents
in all categories. Figure 9(b) shows the inferred shared latent clusters by the ReMatch.
The size of clusters inferred by the ReMatch was smaller than that by the proposed
method. By considering relevance, the proposed method could discover larger clusters which are easy to interpret. Figures 10 and 11 show the inferred shared latentclusters and relevance by the proposed method with the Multilingual English-Italianand English-Japanese data, respectively.

20

Tomoharu Iwata, Katsuhiko Ishiguro

7 Conclusion
We proposed a probabilistic model for unsupervised cluster matching, which is a task
to find matching between clusters of objects in different domains. Given multiple
networks as inputs, the proposed method infers matching of clusters and relevanceof objects simultaneously, which enables us to improve the matching performanceby handling noisy observation. We have confirmed experimentally that the matching
performance of the proposed method is higher than existing methods with synthetic
and real-world data sets. With the proposed method, the ReMatch was extended byintroducing relevance. This approach, i.e. introducing relevance, can be used for extending other existing object matching methods. The proposed method is based on
the IRM for clustering. We plan to use other probabilistic models for clustering, suchas dynamic IRM (Ishiguro et al, 2010) and latent feature models (Miller et al, 2009).
The scalability of the inference can be improved by using stochastic variational inference (Hoffman et al, 2013) or parallel inference (Williamson et al, 2013).

References
Airoldi E, Blei D, Fienberg S, Xing E (2008) Mixed membership stochastic blockmodels. Journal of Machine Learning Research 9:1981–2014
Albert R, Barabási A (2002) Statistical mechanics of complex networks. Reviews ofmodern physics 74(1):47
Barabási A, Albert R (1999) Emergence of scaling in random networks. Science286(5439):509–512
Blackwell D, MacQueen JB (1973) Ferguson distributions via Pólya urn schemes.
The Annals of Statistics pp 353–355
Clauset A, Moore C, Newman M (2008) Hierarchical structure and the prediction of
missing links in networks. Nature 453(7191):98–101
Djuric N, Grbovic M, Vucetic S (2012) Convex kernelized sorting. In: Proceedingsof the 26th AAAI Conference on Artificial Intelligence
Gale WA, Church KW (1991) A program for aligning sentences in bilingual corpora.
In: Proceedings of the 29th Annual Meeting on Association for Computational
Linguistics, pp 177–184
Girvan M, Newman M (2002) Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99(12):7821–7826
Haghighi A, Liang P, Berg-Kirkpatrick T, Klein D (2008) Learning bilingual lexicons
from monolingual corpora. In: Proceedings of ACL-08: HLT, pp 771–779
Hoffman MD, Blei DM, Wang C, Paisley JW (2013) Stochastic variational inference.
Journal of Machine Learning Research 14(1):1303–1347
Ishiguro K, Iwata T, Ueda N, Tenenbaum J (2010) Dynamic infinite relational modelfor time-varying relational data analysis. Advances in Neural Information Processing Systems 23
Ishiguro K, Ueda N, Sawada H (2012) Subset infinite relational models. In: International Conference on Artificial Intelligence and Statistics, pp 547–555

Robust Unsupervised Cluster Matching for Network Data

21

Iwata T, Hirao T, Ueda N (2013) Unsupervised cluster matching via probabilistic
latent variable models. In: Proceedings of the 27th AAAI Conference on Artificial
Intelligence
Iwata T, Lloyd J, Ghahramani Z (2016) Unsupervised many-to-many object matching for relational data. IEEE Transactions on Pattern Analysis and Machine Intelligence 38(3):607–619
Kemp C, Tenenbaum J, Griffiths T, Yamada T, Ueda N (2006) Learning systems
of concepts with an infinite relational model. In: Proceedings of the 20th AAAI
Conference on Artificial Intelligence, vol 21, p 381
Klami A (2012) Variational Bayesian matching. In: Proceedings of the 4th Asian
Conference on Machine Learning, pp 205–220
Klami A (2013) Bayesian object matching. Machine Learning 92:225–250
Lang K (1995) Newsweeder: Learning to filter netnews. In: Proceedings of the 12th
International Conference on Machine Learning, pp 331–339
Li B, Yang Q, Xue X (2009) Transfer learning for collaborative filtering via a ratingmatrix generative model. In: Proceedings of the 26th International Conference on
Machine Learning, pp 617–624
Miller K, Griffiths T, Jordan M (2009) Nonparametric latent feature models for link
prediction. Advances in Neural Information Processing Systems 22
Nowicki K, Snijders T (2001) Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association 96(455):1077–1087
Quadrianto N, Smola A, Song L, Tuytelaars T (2010) Kernelized sorting. IEEE Transactions on Pattern Analysis and Machine Intelligence 32(10):1809–1821
Rapp R (1999) Automatic identification of word translations from unrelated English
and German corpora. In: Proceedings of the 37th Annual Meeting on Association
for Computational Linguistics, pp 519–526
Socher R, Fei-Fei L (2010) Connecting modalities: Semi-supervised segmentation
and annotation of images using unaligned text corpora. In: Proceedings of the IEEE
Conference on Computer Vision and Pattern Recognition, pp 966–973
Wang Y, Wong G (1987) Stochastic blockmodels for directed graphs. Journal of theAmerican Statistical Association 82(397):8–19
Watts D, Strogatz S (1998) Collective dynamics of ‘small-world’ networks. Nature
393:440–442
Williamson S, Dubey A, Xing EP (2013) Parallel Markov Chain Monte Carlo for
nonparametric mixture models. In: Proceedings of the 30th International Conference on Machine Learning, pp 98–106
Yamada M, Sugiyama M (2011) Cross-domain object matching with model selection.
In: Proceedings of the 14th International Conference on Artificial Intelligence andStatistics, pp 807–815