because each instantiation of r
′ **will at some time also appear as an instantiation**
of r**. It is justified to consider** P(r
′ ⊆ r**), because a large** P(r
′ ⊆ r**) implies that**
r
′
(x, y) ⇒ r(*x, y***). This means that a large** P(r
′ ⊆ r) implies that fun(r) <
fun(r
′
) and fun−1(r) *< fun*−1(r
′
).

If there is no x
′
, y′ **with** r
′
(x
′
, y′**), we set as usual the last factor of the formula**
to one, Qr
′(x′,y′)
(1 − P(x ≡ x
′
**))) := 1. This decreases** P(x ≡ x
′
**) in case one**
instance has relations that the other one does not have.

To each instance from the first ontology, our algorithm assigns multiple equivalent instances from the second ontology, each with a probability score. For each instance from the first ontology, we call the instance from the second ontology with the maximum score the *maximal assignment***. If there are multiple instances**
with the maximum score, we break ties arbitrarily, so that every instance has at most one maximal assignment.

## 4.3 Subclasses

A class corresponds to a set of entities. One could be tempted **to treat classes**
just like instances and compute their equivalence. However, the class structure of one ontology may be more fine-grained than the class structure of the other ontology. Therefore, we aim to find out not whether one class c **of one ontology** is equivalent to another class c
′ of another ontology, but whether c **is a subclass**
of c
′
, c ⊆ c
′
**. Intuitively, the probability** P(c ⊆ c
′
**) shall be proportional to the**
number of instances of c **that are also instances of** c
′
:

$P(c\:\subseteq\:c')=\dfrac{\#\ c\cap c'}{\#c}$  But how do we have a finite amount? 

. Again, we estimate the expected number of instances that are in both classes
$$\mathbb{E}(\#\,c\cap c^{\prime})=\sum_{x:type(x,c)}(1-\prod_{y:type(y,d)}(1-P(x\equiv y)))$$  We divide this expected number by the total number of instances of $c$:  $$P(c\subseteq c^{\prime})=\frac{\sum_{x:type(x,c)}(1-\prod_{y:type(y,d)}(1-P(x\equiv y)))}{\#x:type(x,c)}\tag{12}$$  $\cdot$
The fact that two resources are instances of the same class can reinforce our belief that the two resources are equivalent. Hence, it seems tempting to feed the subclass-relationship back into Equation (10). However, in practice, we found that the class information is of less use for the equivalence **of instances. This** may be because of different granularities in the class hierarchies. It might also be because some ontologies use classes to express certain properties (*MaleSingers*),
whereas others use relations for the same purpose (gender = *male***). Therefore,**
we compute the class equivalences only *after* **the instance equivalences have**
been computed.

## 5 Implementation 5.1 Iteration

Our algorithm takes as input two ontologies. As already mentioned, we assume that a single ontology does not contain duplicate (equivalent) entities.