IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

1

Unsupervised Many-to-Many Object Matchingfor Relational Data
Tomoharu Iwata, James Robert Lloyd, Zoubin Ghahramani
Abstract—We propose a method for unsupervised many-to-many object matching from multiple networks, which is the task of finding
correspondences between groups of nodes in different networks. For example, the proposed method can discover shared word groups
from multi-lingual document-word networks without cross-language alignment information. We assume that multiple networks sharegroups, and each group has its own interaction pattern with other groups. Using infinite relational models with this assumption, objects indifferent networks are clustered into common groups depending on their interaction patterns, discovering a matching. The effectivenessof the proposed method is experimentally demonstrated by using synthetic and real relational data sets, which include applications tocross-domain recommendation without shared user/item identifiers and multi-lingual word clustering.
Index Terms—Unsupervised Object Matching, Bayesian Nonparametrics, Relational Data, Stochastic Block Model, MCMC✦

1I NTRODUCTION

Object matching is the task of finding correspondences
between objects in different domains. Examples of object
matching include document alignment [1] and sentencealignment [2], [3] in natural language processing, matching images and annotations in computer vision [4],and matching user identifiers in different databases forcross domain recommendation [5]. Most object matching
methods require similarity measures between objects indifferent domains, or correspondence data for learning
the similarity measures. However, similarity measuresand correspondence data may not always be available
due to cost or privacy issues.
For these situations, a number of unsupervised object
matching methods have been proposed recently [6], [7],[8], [9], which can find matchings without correspondence information. These methods find only one-to-one
matchings between objects. However, in some applications it is appropriate to find many-to-many matching.
For example, multiple English words with the same
meaning (e.g. car, automobile, motorcar) might correspond to multiple German words (e.g. Wagen, Automobil). We also might want to find correspondences
between groups of people instead of individuals in
different social networks.
In this paper, we propose a method for finding manyto-many matchings from multiple networks, or relational data sets. We call the proposed method ReMatch(relational matching). ReMatch assumes that the given
multiple networks have common latent groups, where
each group exhibits a particular interaction pattern withother groups. Networks from a wide variety of fields
fulfill this assumption. Let us consider lexical networks
with multiple languages as an example. Each network• T. Iwata is with NTT Communication science laboratories, J. Lloyd andZ. Ghahramani are with University of Cambridge

consists of nodes of words in a language, and nodes arelinked when there are relations between them. Synonym
groups in a language would have the same relations withgroups in another language, e.g. group {car, automobile,
motorcar} is connected to {drive, ride} in English, and{Wagen, Automobil} is connected to {fahren, treiben}
in German. As further examples, social networks fromdifferent research laboratories would share similar relationship patterns among faculty, post-docs and students,
and biological networks from different species would
have some common components. By assigning objects
in different networks to common groups, we can findmany-to-many matchings across networks without correspondence information, where objects assigned into
the same group are considered to be matched.
We cluster objects into common latent groups using
the infinite relational model (IRM) [10]. The IRM is a
nonparametric Bayesian extension of the stochastic blockmodel [11], [12], and it finds latent groups from a network without fixing the number of groups in advance.
The IRM has been proposed for clustering nodes in asingle network. In this paper, we assume that different
networks share cluster proportions and interaction patterns between clusters. According to this assumption,
nodes in multiple networks are clustered into common
groups. Figure 1 shows the generative process of two
networks in our model. The cluster proportions andconnectivity, which defines interaction patterns between
clusters, are shared by two networks. Each node is
assigned to a cluster, and the link between two nodes
is generated depending on their cluster assignments,
and the connectivity. ReMatch does not assume that
correspondence information between nodes in different
networks is given in advance or even possible to obtain.
The number of clusters is automatically inferred using
Dirichlet process priors, and ReMatch is applicable todata sets in which the size of each cluster is different
across networks, and some clusters might not appear inIEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

cluster proportions: βAB Ccluster assignments: z
6
2
A 3

51
49
B 87 C

networks1: X1

C

A
B
C
6 2 3 5 1 8 7 4 9

7 9 6 1 4 3 2 5 8

B

43
58
2 C

networks2: X2

6 2 3 5 1 8 7 4 9A79
A 61 B

7 9 6 1 4 3 2 5 8ABCconnectivity: η A 0.9 0.2 0.8
B 0.1 0.1 0.7
C 0.1 0.8 0.2

Fig. 1. Generative process of two networks with ourmodel. The cluster proportions and connectivity areshared by both of the networks. From the cluster proportions, a cluster assignment for each node is generated.
For example, nodes 6, 2 and 3 are assigned into the firstcluster in Network1. The nodes assigned to the samecluster are considered matched; nodes 6, 2 and 3 in
Network1 and nodes 7, 9, 6 and 1 in Network2 arematched. Using the cluster assignments and connectivity,
links are generated.

some networks. ReMatch can handle multiple networks
with different numbers of nodes. Since ReMatch is basedon the IRM, it can handle multiple types of nodes,
such as a document-word network and a user-item-tag
network, as well as a single type, such as a personperson network, and multiple relations, such as ‘like’and ‘hate’ relations. ReMatch corresponds to applying
the IRM to a single large network that is constructed by
combining all the networks, where connections between
different networks are unobserved.
ReMatch can be used for many applications, suchas cross-domain recommendation [5], [13], [14], multilingual corpus analysis [15], [16], and bioinformatics [17],[18], where we can expect some shared latent clusters
and cannot obtain correspondence information. In crossdomain recommendation, we would for example like torecommend books to users in an online movie store. User
identifiers are not shared between the stores becauseof the need to preserve privacy. The given data set
is a user-item bipartite network for each store, which
represents whether each user has purchased a partic-2

ular item or not. The books and movies would shareclusters, or genres; for example, users who like horror
books/movies may tend to like mystery books/movies.
ReMatch can find the shared groups, and perform crossdomain recommendations without common user/item
identifiers. In multi-lingual corpus analysis, ReMatch canbe used for discovering shared topics across languages
by applying it to multi-lingual document-word networks without alignments. Most existing techniques incross-domain recommendation and multi-lingual corpus
analysis require alignment information between nodes
across domains; for example, user/item identifiers areshared [13], [14], documents are aligned in polylingual
topic models [19] and multi-view canonical correlation
analysis [20], dictionaries are given, and morphologicalsimilarity is assumed in multilingual topic models [15].
However, user identifiers might not be shared between
different companies, alignments might not be available
in minor languages, and morphological similarity cannot
be assumed between languages using different characters such as between English and Japanese.
The paper is organized as follows: In Section 2, weoutline related work. In Section 3, we propose a methodfor discovering clusters shared across multiple networks
without node correspondence. In Section 4, we experimentally demonstrate the effectiveness of ReMatch byusing synthetic and real relational data sets, which
include applications to cross-domain recommendation
without shared user/item identifiers, and to multilingual word clustering without dictionaries/alignedtexts.

2

R ELATED WORK

Unsupervised object matching methods have been proposed, such as kernelized sorting [7], least square object
matching [8], matching canonical correlation analysis [6],and variational Bayesian matching [9]. These methods
find one-to-one correspondences between objects in two
domains, and require that the two data sets contain thesame number of objects. On the other hand, the proposed
method finds many-to-many correspondences, and canhandle multiple domains with different numbers of
nodes. Recently, an unsupervised many-to-many object
matching method for real-valued data was proposed[21]. Because the method assumes Gaussian noise for
input data, it is not well suited for network or relational
data which are the focus of this paper.
Latent groups in a single network can be extracted
by using probabilistic models, such as the stochastic
block model [11], [12], mixed membership stochastic
block model [22], infinite relational model [10], andnetwork community detection methods [23]. However,these methods have not been used for discovering
shared groups from multiple networks.
ReMatch can be seen as a multi-task learning method
for networks. Multi-task learning techniques assumes
that common properties are shared among different tasks

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

or domains. Most multi-task learning methods are developed for supervised learning [24], [25], [26]. Multi-task
learning for clustering has been proposed [27], whererelationship between clusters of different tasks is learned
by using centroids of clusters. It is not applicable to
network data because clusters of network data are notdefined based on cluster centroids but on connectivities
between clusters.
Finding correspondence between multiple networks isrelated to network de-anonymization [28] given multiple networks. However, this paper is different fromthe network de-anonymization setting since we try tofind cluster-level correspondence instead of node-level
correspondence.

3

P ROPOSED METHOD : R E M ATCH

In the rest of the paper, we assume that the given
data are binary bipartite networks, such as user-itemand document-word networks, for simplicity. However,
ReMatch is applicable to other kinds of networks, suchas single-type, multi-type and/or multiple-relation networks.
Suppose that we are given D networks, X = {Xd }D
d=1 .
Here, Xd is the dth network, or relational data, represented by a (Vd1 × Vd2 ) matrix, where each element is
xdij = 1 if nodes i and j are connected, and xdij = 0
otherwise. Vdt is the number of nodes of type t ∈ {1, 2}
in the dth network. In the case of a user-item network,a type 1 node represents a user, and a type 2 node
represents an item. The task is to find a many-to-many
matching of nodes in an unsupervised fashion given
multiple networks.
ReMatch uses an infinite relational model (IRM) for
unsupervised matching. We assume that different networks share clusters and their interaction patterns between clusters, or a connectivity matrix η. The (k, l)element of the η matrix, ηkℓ ∈ [0, 1], defines the probability of a connection between type 1 nodes belonging
to cluster k and type 2 nodes belonging to cluster ℓ. Ourmodel is nonparametric in the sense that the number ofpossible clusters is countably infinite, and therefore η isa doubly infinite matrix.
Each type t has its own common cluster proportions
βt = (βt1 , βt2 , . . . ) that are shared across networks,
where βtk ∈ [0, 1] represents the probability
P∞ that a nodeis assigned to cluster k in type t, and k=1 βtk = 1. The
infinite vector of shared cluster proportions βt is generated by the stick-breaking distribution [29]. For eachnode i of type t in network d, a cluster assignment zdti ∈{1, 2, 3, . . . } is drawn according to a discrete distribution
with parameter βt . The existence of an edge between
nodes i and j is determined by xdij ∼ Bernoulli(ηzd1i ,zd2j )depending on their cluster assignments.
In summary, ReMatch assumes the following generative process for a set of bipartite networks X:
For each cluster for type 1: k = 1, . . . , ∞For each cluster for type 2: ℓ = 1, . . . , ∞

3

a
γ
β1
V1

b

η ∞x∞

z

x

γ
β2

z
V2 D

Fig. 2. Graphical model representation of ReMatch forbipartite networks.

Draw connectivityηkℓ ∼ Beta(a, b)
For each type: t = 1, 2
Draw shared cluster proportions
βt ∼ Stick(γ)
For each network: d = 1, . . . , D
For each type: t = 1, 2
For each node: i = 1, . . . , Vdt
Draw latent cluster assignment
zdti ∼ Discrete(βt )For each node of type 1: i = 1, . . . , Vd1
For each node of type 2: j = 1, . . . , Vd2
Draw relation
xdij ∼ Bernoulli(ηzd1i ,zd2j )Figure 2 shows a graphical model representation of
ReMatch, where shaded and unshaded nodes indicate
observed and latent variables, respectively.
Figure 3 shows the input and output of ReMatch.
ReMatch takes a set of networks as input, where there
is no correspondence information between nodes acrossthe networks, and the networks can contain different
numbers of nodes. In this example, the size of Network1
is (100 × 65) and that of Network2 is (80 × 105). ReMatchdiscovers clusters shared across the networks, which
reveal the block structure when the nodes are sorted
according to the cluster assignments as shown in Figure
3b. Each pair of clusters from types t = 1 and t = 2,(k, l), has its own connectivity ηkℓ that is shown in thebottom of Figure 3b. The cluster sizes can be different
depending on the network. Some clusters might not be
used in some networks. For example, cluster k = 5 intype t = 1 is used only in Network2.
Since ReMatch corresponds to applying the IRM to a
combined network as described, we can use the same
inference procedure as the IRM. Given the multiple
relational data X, we infer latent cluster assignments bycollapsed Gibbs sampling [10], in which cluster assignments Z = {zdti } are sampled while cluster proportions{βt } and the connectivity parameters η are analyticallyintegrated out.
Given the current state of all but one latent cluster
assignment zj , where j = (d, t, i), a new value for zj isIEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

4

t=2

0

Network1

Network2

0.5

0.9

A

a

10

t=2

20
0

30

10

40

20

t=150
60

0.3

t=1 40

70

C

B

40

80
0

60

20

40

60

80

100

Network2(a) Input
l=4

{

l=3

{

l=2

{
{

l=1

10

k=1

30

{

l=3

c

b

0.9

0.1

0.9

A

a
0.3

0.8

10

{

0.1 0.1

C

B

0.1

0.3

0.1

0.1

0.9

0.1

k=2

50

0.5

0.1

l=4

0

20

40

0.9

0.8

0.5

c

b

0.9

0.1

30

k=3

{

l=2

{

20

{

l=1

{
{

{

0.3

0.5

(a) Unidentifiable Networks
Network1
Network2

70

20

Network1

k=2

0.9

60

100
0

{
{

0.1 0.1

0.1

90

k=1

0.1

0.3

0.1

0.1

0.9

50

80

0

0.3

0.1

30

(b) Identifiable Networks

{
{
{

60

40

k=3

70

50

k=4

80

k=4

90

Fig. 4. Cluster connectivities of (a) matching unidentifiable networks and (b) matching identifiable networks.
Each node represents a cluster, and the value at the edge
represents its connectivity.

60
70

k=5

100
0

20

40

80
0

60

20

Network1

40

60

80

100

Network2
k=1
k=2
k=3
k=4
k=5
l=1

l=2

l=3

l=4

Connectivity(b) Output
Fig. 3. (a) Input networks. In this case, the inputs are two
bipartite networks, where type t = 1 nodes are aligned
vertically, and type t = 2 nodes are aligned horizontally.
(b) Outputs of ReMatch: (top) cluster assignments, where
the nodes are sorted according to the assignments, and(bottom) the inferred connectivity matrix η.
sampled from the following probability distribution:\j
M · p(X|Z \j , zj = k) tk
for an existing cluster(1)p(zj = k|X, Z \j ) ∝
\j

γ
·
p(X|Z
, zj = k)for a new cluster

where Mtk is the number of nodes that are assigned
to cluster k in type t, and \j represents the set or
value when excluding sample j. The likelihood term is
calculated byKt̄

p(X|Z \j , zj = k) =Y B(N +j + a, N̄ +j + b)

kℓ
kℓ
,
\j
\j
ℓ=1 B(Nkℓ + a, N̄kℓ + b)(2)

where B(·) is the beta function, t̄ = 2 if t = 1 and t̄ = 1
if t = 2, Kt is the number of existing clusters, Nkℓ is
the number of links between clusters k and ℓ, N̄kℓ is thenumber of non-links between clusters k and ℓ, and +jrepresents the value when sample j is assigned to cluster
k. In the experiments, we fixed the hyperparameters as
follows: γ = 1, a = 1, and b = 1. We used the last sampleof the cluster assignments in the inference for matching.
Identifiability of matching clusters depends on connectivities between clusters. Suppose that we know the true
clusters and true their connectivities for each network.
Then, matching is identifiable if the connectivities arematched only with the true matched clusters and they
are not matched with other clusters. For example, wehave two networks with cluster connectivities as in
Figure 4(a). Since two possibilities of matching exist: (Ab, B-a, C-c) and (A-b, B-c, C-a), their matching is unidentifiable. On the other hand, when we have networks withconnectivities as in Figure 4(b), only one matching exists(A-b, B-c, C-a), and therefore it is identifiable. Note thateven if it is identifiable, the inference might not find thetrue matching when it falls into a local optimum solution. Since true clusters and connectivities are unknown,
we need to infer clusters and connectivities. Therefore,
matching performance depends also on how well thetrue clusters and connectivities can be inferred.

4

E XPERIMENTS

4.1 Synthetic data
We evaluated ReMatch by using the following three
types of synthetic data sets with two networks: Balance, Partial and Dirichlet. Figure 5 shows examplesof the synthetic data sets. For the Balance data, thenumber of nodes in each cluster is constant. In particular, each cluster has 20 nodes and there are fourIEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

1

1

0.5

0.5

1

2

3

0

4

0

0

10

10

1

1

0

30

50

M ARI =

30

4

20

40

60

0

1

80
0

80

80
0

20

Network1(a) Balance
1

1

0.5

1

2

3

4

40

60

80

Network2

0.5

0

0

5

1

2

3

4

1

1

0

2

2

20
30

10
20

3

3

40
50

30

60

4

4

40
50

20

40

60

60

80

5

5

70
80
0

0

1

0.5

0

1

0.5

70
80
0

Network1

20

40

60

80

Network2(b) Partial

1

1

0.5

0.5

0

1

2

3

4

0

5

30

50

4

5

30

50
60

4

4

60
70

70

5

80

5

80

20

40

60

80

100

0

90
1

100
0

0.5

90
0

3

40
3

3

40

1

2

10
20

2

2

20

0.5

1

0
1

1

0
10

Network1(c) Dirichlet

(3)

100
0

20

40

60

80

where c1 (c2 ) is the number of node pairs in different
networks that are correctly assigned into the same cluster(different clusters) both in the estimated and true assignments, Nd is the number of nodes in network d, and µ
is the expected value of c1 + c2 , which is obtained by
µ=

5

0
10

c1 + c2 − µ,
N1 N2 − µ

50

70
0.5

70
0

matching task, where nodes in different networks should
be correctly assigned to the same cluster. The matching
adjusted Rand index is calculated by

4

60

4

60

1

3

40
3

3

40

0.5

2

20
2

2

20

1

5

100

Network2

Fig. 5. Examples of synthetic data sets. Nodes arealigned by their cluster assignments. The bar chart shows
the cluster proportions of the type in the network.

clusters in each network. For the Partial data, nodes
are partially matched. The first cluster is used only inthe first network, and the fifth cluster is used onlyin the second network. The second, third and fourthclusters are shared by both of the networks. For the
Dirichlet data, the cluster proportions are generated froma Dirichlet distribution. Therefore, the numbers of nodes
are different across clusters. The total number of nodes is100, and the number of clusters is five. In all of the data
sets, the connectivity between clusters was randomly
sampled from a Beta(0.5, 0.5) distribution, and the links
were generated according to the Bernoulli distribution
depending on the assigned clusters.
We evaluated the performance of finding correspondences between groups of nodes in different networks
using the matching adjusted Rand index. The adjusted
Rand index [30] is used for the evaluation of clustering
performance, which quantifies the similarity between
inferred clusters and true clusters, and takes the value
from −1 to 1, and gives 0 for random clustering. We
modified the adjusted Rand index for the many-to-many(c1 + c3 )(c1 + c4 ) + (c2 + c3 )(c2 + c4 ),N1 N 2(4)

where c3 (c4 ) is the number of node pairs in different
networks that are incorrectly assigned into the samecluster (different clusters) in the estimated assignments
but that are assigned into different clusters (the samecluster) in the true assignments.
For the comparison methods, we used IRM+KS, KS
and MMLVM explained below. For the IRM+KS, first
we discovered clusters by the infinite relational model(IRM) for each network individually, and then foundthe correspondence between clusters in two networks
by using convex kernelized sorting (KS) [31], which isan unsupervised object matching method. It requiresthat two networks have the same number of clusters.
Therefore, we set the number of clusters for the IRM
by using the inferred number of clusters by ReMatch,and the IRM is inferred while fixing the number ofclusters. Note that the IRM with a fixed number ofclusters corresponds to the stochastic block model [11],[12]. The KS method directly finds correspondence between nodes using convex kernelized sorting, where theaccuracy is calculated by assuming each node is assigned
to a different cluster. The MMLVM is a many-to-manylatent variable model [21], which can find a many-tomany object matching given real-valued data. We ran
the MMLVM with latent dimensionality {1, 2, · · · , 10},and show the best value.
The average matching adjusted Rand index over 30
experiments is shown in Table 1. ReMatch achieved
the highest matching adjusted Rand index for all of
the data sets. When IRMs are inferred individually foreach network, the discovered clusters can be different
among the networks because of local optima or noisein the data. Therefore, even if we try to find correspondences between clusters after the individual IRM
inference, there would not be corresponding clusters,
and the accuracies by IRM+KS were low. On the other
hand, ReMatch alleviates this problem by finding sharedclusters simultaneously in multiple networks. Because
KS finds only a one-to-one matching, the performancefor matching groups becomes low. The MMLVM is better
than IRM+KS and KS because the MMLVM simultaneously finds clusters and their matching. However, since
the MMLVM assumes real-valued data with Gaussian
noise, it is not well suited for binary data, and theIEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

1

0.65

0.9

0.6

0.8

0.55

0.7

0.5

0.6

0.45

0.5

0.4

0.4

0.35

6

Type 165432
1Type 2
3
2

10

20

30

40

50

60

70

80

6

8

10

(a) Dirichlet parameter

2

4

6

8

10

(b) number of networks

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

6

8

10

(c) number of clusters

40

50

60

70

80

20

30

40

50

60

70

80

20

30

40

50

60

70

80

20

30

40

50

60

70

80

20

30

40

50

60

70

80

20

30

40

50

60

70

80

2

2
1

10

20

30

40

50

60

70

80

1

10

2nd iteration
5

3

4
2

2
1

10

20

30

40

50

60

70

80

1

10

3rd iteration
5

4

4
4

30

3

3

2

20

4
3

4

10

1st iteration
5

2

1

50

100

150

200

(d) number of nodes

Fig. 6. Average matching adjusted Rand index with (a)different Dirichlet parameters, (b) different numbers of
networks, (c) different numbers of clusters and (d) different numbers of nodes for each cluster with the synthetic
Dirichlet data sets.

performance of the MMLVM with the best latent dimensionality setting is lower than that of ReMatch that canhandle binary data.
Figure 6 shows the matching adjusted Rand index
with different parameter settings with Dirichlet data sets.
The default setting of the Dirichlet parameter is one, thenumbers of networks, clusters and nodes are two, fiveand 100, respectively. The Dirichlet parameter controls
the variance of the number of nodes in each cluster.
ReMatch achieved high performance when the Dirichletparameter was high, or when the distribution of cluster
sizes was uniform (a). When the Dirichlet parameter islow, clusters with a small number of nodes are likely
to be generated. It is difficult to discover such small
clusters because of data scarcity, and also difficult tofind matchings. Even when the number of networks washigh, the performance was high (b). Since ReMatch findcorrespondence between clusters, the number of possible
correspondences is high when there are many clusters.
Therefore, as the number of clusters was increased, thematching adjusted Rand index became low (c). The performance was high when the number of nodes for eachcluster was high (d). This is because we can accurately
identify the interaction patterns between clusters when
their are many nodes per cluster.
Figure 7 shows the cluster assignments over iterationsin the inference with the Balance data. Here, node indices are aligned by their true cluster assignments; forexample, indices 1 to 20 belongs to cluster 1 for both
networks. We started with three clusters, where nodes
were assigned randomly to one of the clusters. At the
1st iteration, many nodes were not clustered. At the
2nd iteration, some nodes were clustered and matched

3

3
2

2
1

10

20

30

40

50

60

70

80

1

10

4th iteration
5

4

4

3

3
2

2
1

10

20

30

40

50

60

70

80

1

10

5th iteration
4

4

3

3

2
1

2
10

20

30

40

50

60

70

80

1

10

20th iteration
Fig. 7. Cluster assignments over iterations in the inference with a Balance data set. The horizontal axis is thenode index, and the vertical axis is the cluster index.
Each blue ‘o’ represents a node in the first network, andeach red ‘x’ represents a node in the second network.
Therefore, when ‘o’ and ‘x’ are overlapped, nodes fromdifferent networks are correctly assigned into the samecluster.
correctly, such as the node 60 to 80 in type 2. At the
5th iteration, nodes except for 1 to 10 in type 1 arecorrectly matched. At the 20th iteration, all of the nodes
were perfectly matched. ReMatch finds clear clusters thatare easy to be matched at early stage, and then, it finds
other clusters by flexibly changing the number of clusters
based on Dirichlet process priors. By simultaneously
finding clusters and their matching, we can discourage
being trapped into different local optima across multiple
networks.
4.2 Cross-domain recommendation
For evaluating ReMatch in a cross-domain recommendation setting, we used Movie data. The Movie data consist of two user-movie networks obtained from MovieLens [32], which is a standard benchmark data set forcollaborative filtering. The MovieLens data contained
943 users, 1,682 movies, and 100,000 ratings. First, we
split users and movies into two sets. Then, the first(second) user-movie network is constructed by users andIEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

7

TABLE 1
Average matching adjusted Rand index, and its standard error for the synthetic data sets. Values in bold typeface are
the best, or are not statistically different (at the 5% level) from the best as indicated by a paired t-test.
Balance
PartialDirichlet

ReMatch0.941 ± 0.012
0.728 ± 0.050
0.419 ± 0.064

IRM+KS
0.344 ± 0.069
0.057 ± 0.040
0.065 ± 0.040

0

100

200

300

400
0

100

200

300

400

500

600

700

800

(a) Network1
0

100

200

300

KS
0.067 ± 0.001−0.001 ± 0.002
0.003 ± 0.001

MMLVM
0.736 ± 0.039
0.262 ± 0.043
0.156 ± 0.045

d′ is calculated by ηzd1i zd′ 2j . We predicted links in theother network for hidden corresponding users using
ReMatch, IRM+KS, User-average, Item-average and Average methods. The User-average method predicts links
by the average connectivity of the user, and Item-averagemethod predicts by the average connectivity of the itemin the other network. Table 2 shows the results averaged
over 30 experiments. For the evaluation measurements,
we used the test likelihood, AUC (area under the ROC
curve), and accuracy. With all of the measurements, ReMatch achieved the best predictive performance. We did
not compare with KS or MMLVM because they require
a huge amount of computational time. When using acomputer with 2.93GHz CPU, the computational timeof ReMatch, KS and MMLVM were 20 minutes, 4 days,and 8 days, respectively, for a single experiment. The
computational complexity of KS is cubic in the numberof nodes because a linear assignment problem solver
is required. Since MMLVM does not assume relationaldata, it found too many clusters (over 200 clusters) with
the Movie data, and thus took a long time to compute.

400

4.3 Co-clustering words and documents
0

100

200

300

400

500

600

700

800

(b) Network2
Fig. 8. Shared latent group structures discovered by
ReMatch in the Movie data. The vertical axis represents
the user index, and the horizontal axis represents themovie index.

movies in the first (second) set, where xdij = 1 if user i
has rated movie j in network d, and xdij = 0 otherwise.
The two networks do not share any users and movies.
Note that collaborative filtering methods would notwork for cross-domain recommendation because there
are no shared users and items. Cross-domain recommendation methods have been proposed [14], [33]. However,since they assume a Gaussian noise model they are
unlikely to perform well on binary data; we empiricallydemonstrate the poor performance of a similar modelwith Gaussian noise, MMLVM [21], in Section 4.1. Figure
8 shows the latent group structures inferred by ReMatch,where similar structures were discovered in two different
networks.
We evaluated ReMatch in terms of cross-domain recommendation performance. With ReMatch, the probability that user i in network d purchases item j in network

We used the 20News data to evaluate ReMatch on coclustering words and documents with multiple text data
sets. The 20News data are generated from 20 Newsgroups data set [34] with binary occurrence data for
100 words across 16,242 documents1 . The documents are
categorized into the following four newsgroups: ‘computers’, ‘recreation’, ‘science’ and ‘talk’. We randomly
sampled two disjoint sets of 1,000 documents from thedata with 250 documents from each category, and created two word-document networks.
Figure 9 shows the shared group structure discovered
by ReMatch, where the words and documents in the two
networks were co-clustered with similar patterns. Table
4 shows the word clustering result by ReMatch, where
it discovered 10 word clusters. Even though we did not
use the correspondence information between words in
different networks, most words were assigned into thesame cluster. Figure 10 shows the document clusteringresult by ReMatch, where it discovered eight document
clusters. Each cluster exhibits similar proportions of document categories across the two networks. Some clusters
correspond to a particular category, for example mostof the documents in cluster ℓ = 3 are categorized into
’computers’. Table 3 shows the matching adjusted Rand
1. available at http://www.cs.nyu.edu/˜roweis/data.html

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

8

TABLE 2
Cross-domain recommendation results using the Movie data.
ReMatch
IRM+KS
User-average
Item-average
Average
Likelihood −0.141 ± 0.000 −0.189 ± 0.003 −0.191 ± 0.000 −0.211 ± 0.000 −0.235 ± 0.000
AUC
0.926 ± 0.000 0.855 ± 0.005 0.832 ± 0.000 0.748 ± 0.000 0.500 ± 0.000
Accuracy
0.946 ± 0.000 0.931 ± 0.001 0.937 ± 0.000 0.937 ± 0.000 0.937 ± 0.000

TABLE 3
Average matching adjusted Rand index and theirstandard error for the 20News data.
ReMatch0.082 ± 0.005

IRM+KS−0.002 ± 0.003

TABLE 6
Average matching adjusted Rand index and theirstandard error for the Wikipedia data.
ReMatch0.118 ± 0.021

IRM+KS−0.004 ± 0.012

index for the task of matching document categories.
ReMatch achieved higher performance than IRM+KS.
4.4

Multi-lingual word clustering

We applied ReMatch to multi-lingual word clustering.
The Wikipedia data consists of English and German
Wikipedia documents in the following five categories:‘Nobel laureates in Physics’, ‘Nobel laureates in Chemistry’, ‘American basketball players’, ‘American composers’ and ‘English footballers’. For each category, we
sampled 50 documents that appear in both English andGerman Wikipedia. We used 1,000 frequent words after
removing stop-words for each language. There were
150 nodes (documents) for type 1, 1,000 nodes (words)
for type 2, and 13,892 relations (word occurrences) on
average for each language document-word network.
Figure 11 shows the latent groups discovered by ReMatch, which have different structures in English andGerman. However, some clusters are shared as shownin Table 5, which contains some examples of the shared
word clusters. For example, the first cluster is ‘nobel
prize’, the second is ‘basketball’, and the third is ‘football’. Note that even though some words appear inboth English and German, we did not use the correspondence nor morphological similarity information for
the inference. ReMatch discovered shared word clusters
from English and German documents without any correspondence in documents and words. Table 6 shows thematching adjusted Rand index for the task of matching
document categories. ReMatch achieved higher performance than IRM+KS. Figure 12 shows the document
clustering result by ReMatch on the Wikipedia data.
Each cluster exhibits similar proportions of document
categories across English and German networks. For
example, in both the English and German networks,
all of the documents in cluster ℓ = 1 were categorizedin ‘American composers’, and all of the documents incluster ℓ = 3 were categorized in ‘English footballer’.

5

C ONCLUSION

We have proposed a method for unsupervised many-tomany object matching for relational data, which discovers shared latent groups from multiple networks without
node correspondence. We have experimentally shown
the effectiveness of the proposed method on unsupervised discovery of cluster correspondence, cross-domain
recommendation, multi-task co-clustering of multiple
document-word networks, and multi-lingual word clustering. In this paper, we exploited a common property
among multiple networks of shared latent groups. For
future work, we would like to investigate to use othercommon properties such as heavy-tailed degree distributions and the small world property. A simple extensionof the proposed approach is to use other distributions forobservation, such as Gaussian and Poisson distributions,which would enable us to handle continuous and countdata. The IRM has been extended in many directions,such as the latent feature network model [35] that allows
each node to be assigned to multiple clusters, and the
dynamic IRM [36] that discovers clusters from timevarying network data. Also, models for finding structured clusters have been proposed, such as trees [37] andmulti-way clustering [38]. We would like to apply theframework proposed in this paper to these models fordiscovering richer latent structures.

R EFERENCES
[1]

[2]

[3]

[4]

[5]

T. Vu, A. T. Aw, and M. Zhang, “Feature-based method for
document alignment in comparable news corpora,” in Proceedingsof the 12th Conference of the European Chapter of the Association
for Computational Linguistics.
Association for Computational
Linguistics, 2009, pp. 843–851.
W. A. Gale and K. W. Church, “A program for aligning sentencesin bilingual corpora,” in Proceedings of the 29th annual meeting on
Association for Computational Linguistics. Association for Computational Linguistics, 1991, pp. 177–184.
R. Rapp, “Automatic identification of word translations fromunrelated english and german corpora,” in Proceedings of the37th annual meeting of the Association for Computational Linguistics
on Computational Linguistics.
Association for Computational
Linguistics, 1999, pp. 519–526.
R. Socher and L. Fei-Fei, “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, ser. CVPR, 2010, pp. 966–973.
B. Li, Q. Yang, and X. Xue, “Transfer learning for collaborative
filtering via a rating-matrix generative model,” in Proceedings ofthe 26th Annual International Conference on Machine Learning, ser.
ICML ’09, 2009, pp. 617–624.

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

9

0

50

100
0

100

200

300

400

500

600

700

800

900

1000

600

700

800

900

1000

(a) Network1
0

50

100
0

100

200

300

400

500

(b) Network2
Fig. 9. Shared latent group structures discovered by ReMatch in the 20News data. The vertical axis represents theword index, and the horizontal axis represents the document index.
TABLE 4
Word clustering by ReMatch with the 20News data. Each pair of rows corresponds to a cluster, and the top/bottom
row shows words from Network1/Network2, respectively.
Network
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2

[6]

Words
version files mac dos graphics memory driver video ftp image pc display disk
version memory card files dos graphics mac display disk driver ftp image pc
evidence jesus war rights bible religion health jews food president israel
children war gun religion bible jesus israelcomputer program software drive phone
program computer drive data phone technology
moon shuttle medicine mission doctor orbit launch studies solar cancer lunar
health medicine orbit launch president disease moon mission patients
space research data nasa science technology
space research science nasa
hockey season baseball hit players league nhl fans won puckgames players league won fans hockey nhl puckengine oil insurance water dealer bmw hondaengine honda bmw oil dealer
team games
team baseball season
help problem question
problem question
university world course fact case number state powercourse world power case fact number
email systememail help system university
god government christian human law earth gun children
god state government human christian evidence law rights earth jews water

A. Haghighi, P. Liang, T. Berg-Kirkpatrick, and D. Klein, “Learning bilingual lexicons from monolingual corpora,” in Proceedingsof ACL-08: HLT, 2008, pp. 771–779.
[7] N. Quadrianto, A. J. Smola, L. Song, and T. Tuytelaars, “Kernelized sorting,” IEEE Trans. on Pattern Analysis and MachineIntelligence, vol. 32, no. 10, pp. 1809–1821, 2010.
[8] M. Yamada and M. Sugiyama, “Cross-domain object matchingwith model selection,” in In Proceedings of Fourteenth International
Conference on Articial Intelligence and Statistics, ser. AISTATS ’11,
2011, pp. 807–815.
[9] A. Klami, “Variational Bayesian matching,” in Proceedings of Asian
Conference on Machine Learning, 2012, pp. 205–220.
[10] C. Kemp, J. Tenenbaum, T. Griffiths, T. Yamada, and N. Ueda,“Learning systems of concepts with an infinite relational model,”in AAAI Conference on Artificial Intelligence, vol. 21, 2006, p. 381.
[11] Y. Wang and G. Wong, “Stochastic blockmodels for directed
graphs,” Journal of the American Statistical Association, vol. 82, no.
397, pp. 8–19, 1987.
[12] K. Nowicki and T. Snijders, “Estimation and prediction forstochastic blockstructures,” Journal of the American Statistical Association, vol. 96, no. 455, pp. 1077–1087, 2001.
[13] W. Pan, E. Xiang, N. Liu, and Q. Yang, “Transfer learning incollaborative filtering for sparsity reduction,” in Proceedings of theTwenty-Fourth AAAI Conference on Artificial Intelligence, 2010, pp.
230–235.
[14] Y. Zhang, B. Cao, and D.-Y. Yeung, “Multi-domain collaborative
filtering,” in Proceedings of the 26th Conference on Unvertainty in
Artificial Intelligence, ser. UAI. AUAI Press, 2010, pp. 725–731.
[15] J. Boyd-Graber and D. Blei, “Multilingual topic models for unaligned text,” in Proceedings of the Twenty-Fifth Conference on
Uncertainty in Artificial Intelligence. AUAI Press, 2009, pp. 75–
82.
[16] T. Iwata, D. Mochihashi, and H. Sawada, “Learning common
grammar from multilingual corpus,” in Proceedings of the ACL2010 Conference Short Papers.
Association for Computational
Linguistics, 2010, pp. 184–188.
[17] C. Wang and S. Mahadevan, “Manifold alignment without correspondence,” in Proceedings of the 21st International Jont Conferenceon Artifical Intelligence, ser. IJCAI’09, 2009, pp. 1273–1278.
[18] P. Kirk, J. Griffin, R. Savage, Z. Ghahramani, and D. Wild,“Bayesian correlated clustering to integrate multiple datasets,”
Bioinformatics, 2012.
[19] D. Mimno, H. Wallach, J. Naradowsky, D. Smith, and A. McCallum, “Polylingual topic models,” in Proceedings of the 2009

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

ℓ=1

10

ℓ=2

ℓ=3

ℓ=4

1

1

1

1

0.5

0.5

0.5

0.5

0

1

2

3

0

4

1

ℓ=5

2

3

0

4

1

ℓ=6

2

3

0

4

1

1

1

0.5

0.5

0.5

0.5

1

2

3

0

4

1

2

3

0

4

1

2

2

3

4

3

4

ℓ=8

1

0

1

ℓ=7

3

0

4

1

2

Fig. 10. Document clustering by ReMatch with the 20News data. The x-axis in each figure shows the category index:(1) computers, (2) recreation, (3) science, and (4) talk. The y-axis in each figure of cluster ℓ shows the probability
that documents assigned to cluster ℓ are labeled with the category. The left blue bar shows the probability in the first
network, and the right red bar shows that in the second network.
0

50

100

150
0

100

200

300

400

500

600

700

800

900

1000

600

700

800

900

1000

(a) English
0

50

100

150
0

100

200

300

400

500

(b) German
Fig. 11. Shared latent group structures discovered by ReMatch in the Wikipedia data. The vertical axis represents the
document index, and the horizontal axis represents the word index.

Conference on Empirical Methods in Natural Language Processing:Volume 2-Volume 2. Association for Computational Linguistics,
2009, pp. 880–889.
[20] J. Rupnik and J. Shawe-Taylor, “Multi-view canonical correlation
analysis,” in Conference on Data Mining and Data Warehouses(SiKDD 2010), 2010.
[21] T. Iwata, T. Hirao, and N. Ueda, “Unsupervised cluster matching
via probabilistic latent variable models,” in AAAI ’13: Proceedingsof the 27th AAAI Conference on Artificial Intelligence, 2013.
[22] E. Airoldi, D. Blei, S. Fienberg, and E. Xing, “Mixed membershipstochastic blockmodels,” The Journal of Machine Learning Research,
vol. 9, pp. 1981–2014, 2008.
[23] J. Leskovec, K. J. Lang, and M. Mahoney, “Empirical comparisonof algorithms for network community detection,” in Proceedingsof the 19th international conference on World wide web, ser. WWW’10. New York, NY, USA: ACM, 2010, pp. 631–640.
[24] R. Caruana, “Multitask learning,” Machine learning, vol. 28, no. 1,
pp. 41–75, 1997.
[25] R. Ando and T. Zhang, “A framework for learning predictive
structures from multiple tasks and unlabeled data,” The Journalof Machine Learning Research, vol. 6, pp. 1817–1853, 2005.
[26] T. Evgeniou, C. Micchelli, and M. Pontil, “Learning multiple tasks
with kernel methods,” Journal of Machine Learning Research, vol. 6,
no. 1, p. 615, 2006.

[27] J. Zhang and C. Zhang, “Multitask Bregman clustering,” Neurocomputing, vol. 74, no. 10, pp. 1720–1734, 2011.
[28] M. Hay, G. Miklau, D. Jensen, D. Towsley, and P. Weis, “Resisting
structural re-identification in anonymized social networks,” Proceedings of the VLDB Endowment, vol. 1, no. 1, pp. 102–114, 2008.
[29] J. Sethuraman, “A constructive definition of Dirichlet priors,”
Statistica Sinica, vol. 4, pp. 639–650, 1994.
[30] L. Hubert and P. Arabie, “Comparing partitions,” Journal of Classification, vol. 2, no. 1, pp. 193–218, 1985.
[31] N. Djuric, M. Grbovic, and S. Vucetic, “Convex kernelized sorting,” in Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012.
[32] J. L. Herlocker, J. A. Konstan, A. Borchers, and J. Riedl, “Analgorithmic framework for performing collaborative filtering,” inProceedings of the 22nd annual international ACM SIGIR conference
on Research and development in information retrieval. ACM, 1999,
pp. 230–237.
[33] S. Gao, H. Luo, D. Chen, S. Li, P. Gallinari, and J. Guo, “Crossdomain recommendation via cluster-level latent factor model,”in Machine Learning and Knowledge Discovery in Databases, Lecture
Notes in Computer Science, 2013, pp. 161–176.
[34] K. Lang, “Newsweeder: Learning to filter netnews,” in Proceedingsof the Twelfth International Conference on Machine Learning, 1995, pp.
331–339.
[35] K. Miller, T. Griffiths, and M. Jordan, “Nonparametric latent

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

ℓ=1

11

ℓ=2

ℓ=3

ℓ=4

1

1

1

1

0.5

0.5

0.5

0.5

0

1

2

3

4

5

0

1

2

ℓ=5

3

4

5

0

1

2

ℓ=6

3

4

5

0

1

1

1

0.5

0.5

0.5

0.5

1

2

3

4

5

0

1

2

ℓ=9

3

4

5

0

1

2

ℓ = 10

3

4

5

0

1

1

0.5

0.5

0.5

0.5

2

3

4

5

0

1

2

3

4

5

0

1

2

3

3

4

5

2

3

4

5

4

5

ℓ = 121

1

1ℓ = 11

1

0

2

ℓ=8

1

0

1

ℓ=7

4

5

0

1

2

3

Fig. 12. Document clustering by ReMatch with the Wikipedia data. The x-axis in each figure shows the categoryindex: (1) Nobel laureates in Physics, (2) Nobel laureates in Chemistry, (3) American basketball players, (4) Americancomposers, and (5) English footballers’. The y-axis in each figure of cluster ℓ shows the probability that documents
assigned to cluster ℓ are labeled with the category. The left blue bar shows the probability in English, and the right red
bar shows that in German.
TABLE 5Multi-lingual word clustering by ReMatch in the Wikipedia data. Each pair of rows corresponds to a cluster, and the
top/bottom row shows words from English/German, respectively.
Lang
EN
DE
EN
DE
EN
DE
EN
DE
EN
DE
EN
DE
EN
DE
EN
DE
EN
DE
EN
DE

Words
prize laureates fields nobel
nobelpreis preisverleihung nobelstiftung hochschullehrer
basketball nba draft weight sportspeople guard pro kg lb averaged ncaa
draft basketball cm rebounds punkte forward playoffs lakers pickyouth cup goals clubs premier counted footballers app gls fa caps manchester uefa soccerbase correct friendly substitute arsenal
englischer fc united tore kader angegeben league manchester englische premier tor fa
robertson thompson duncan teammate consecutive bio champion pick playoffs assists wilkins mvp rebounds ron rookie highlights
punkten philadelphia assists zweimal bester spitzname finals bill year player guard celtics serie olympischen holte spielern rookie
planck einstein shockley lamb yang jensen braun franck laue stark landau purcell alvarez glaser gabor townes millikan bardeen
grundlagen theoretischen theoretische assistent zeitschrift verfasste ernst materie naturwissenschaften quantenmechanik friedrichsteve break joe terry twice broke chris suffered performances captain ball fifth agreed shot offer county missed chance finish
george lee folgen mittlerweile erstes beste erfolgreichen gary martin dritten west gespielt durchbruch brown tony young acht van
chemist otto carl chemical frederick harold kurt chemists doi irving stanley biographical fellows friedrich porter fischer lecture todd
chemie chemiker datensatz pnd individualisierter vorhanden biochemiker
transfer cole draw soccer defeat campbell stadium euro neville beckham charity liverpool ham wembley eriksson promotion fee
wm schoss unterschrieb pfund arsenal chris taylor absolvierte foto wayne spielzeit chelsea minuten steve cup englands partie fansparents berlin lawrence jewish columbia interested taught contributed contributions graduated mitchell francisco victor student
auszeichnungen heiratete school institute starb life biographie royal high weltkrieg american wuchs kalifornien amerikanischer
coach championship johnson kevin retired champions round seasons tournament teams finals championships
besten vertrag berufen erreichte bevor beendete liga johnson jugend aktiv leistung sommer gewinnen finale verlor trikotnummerfeature models for link prediction,” Advances in Neural Information
Processing Systems (NIPS), vol. 22, 2009.
[36] K. Ishiguro, T. Iwata, N. Ueda, and J. Tenenbaum, “Dynamic infinite relational model for time-varying relational data analysis,”
Advances in Neural Information Processing Systems, vol. 23, 2010.
[37] C. Blundell, Y. W. Teh, and K. A. Heller, “Bayesian rose trees,”in Proceedings of the 27th Conference on Unvertainty in Artificial
Intelligence, ser. UAI. AUAI Press, 2011.
[38] P. Shafto, C. Kemp, V. Mansinghka, and J. B. Tenenbaum, “Aprobabilistic model of cross-categorization,” Cognition, vol. 120,
no. 1, pp. 1–25, 2011.

Tomoharu Iwata received the B.S. degree inenvironmental information from Keio University
in 2001, the M.S. degree in arts and sciencesfrom the University of Tokyo in 2003, and the
Ph.D. degree in informatics from Kyoto University in 2008. In 2003, he joined NTT Communication Science Laboratories, Japan. From2012 to 2013, he was a visiting researcher atUniversity of Cambridge, UK. He is currently
a senior research scientist (distinguished researcher) at Learning and Intelligent Systems
Research Group of NTT Communication Science Laboratories, Kyoto,
Japan. His research interests include data mining, machine learning,
information visualization, and recommender systems.

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

James Robert Lloyd is a post doctoral researcher at the University of Cambridge working
with Zoubin Ghahramani in the machine learninggroup. He studied mathematics, specialising instatistics, at the University of Cambridge where
he also obtained his PhD in 2015. His research
has included work on Gaussian processes, networks, automatic regression model building andmodel criticism.

Zoubin Ghahramani is Professor of Information Engineering at the University of Cambridge,
where he leads the Machine Learning Group. He
studied computer science and cognitive scienceat the University of Pennsylvania, obtained his
PhD from MIT in 1995, and was a postdoctoral
fellow at the University of Toronto. His academic
career includes concurrent appointments as oneof the founding members of the Gatsby Computational Neuroscience Unit in London, and asa faculty member of CMU’s Machine Learning
Department for over 10 years. He has published over 200 papers,
receiving 27,000 citations (an h-index of 73). His current researchinterests include statistical machine learning, Bayesian nonparametrics,
scalable inference, probabilistic programming, and building an automatic
statistician. He has held a number of leadership roles as programme
and general chair of the leading international conferences in machinelearning: AISTATS (2005), ICML (2007, 2011), and NIPS (2013, 2014).
In 2015 he was elected a Fellow of the Royal Society.

12