Sorry for repeating this very basic concept here, I just want to give some context:

Relations are nonnegative ordered pairs. A relation consists of a domain and range.A domain is a set of all first coordinates(x) of a relation, while a range is the set of all second coordinates(y).

E.G. Relation is {(1,10),(2,20),(3,30),(4,40)}

We are working with classification problems whose output is a relation with discrete domain and range. The domain is conformed by the elements to be classified, and the range is made of labels. All what's matter about the label is its identity.

We want to compare two relations for the same domain. For example, relation $A_1=\{(1,2),(2,1),(3,1)\}$ and relation $A_2=\{(1,1),(2,2),(3,2)\}$, which are both defined over the domain $\{1,2,3\}$. We consider two relations equivalent if one can be obtained from the other by a bijection over the labels. In this example, $A_1$ and $A_2$ would be equivalent. We need a measure $\mu$ that can compare this kind of relations, scoring their similarity continuously from 0 to 1. "0" would mean that the two relations are unrelated, and "1" that they are equivalent.

My questions are:

Which methods are usually employed for comparing two relations for similarity, if the two relations are given explicitly as sets?

In which scenarios this need arise?

We certainly have a definition of equivalence that fixes the upper bound of the measure, but we don't have any definition of "utterly dissimilar" to associate with the lower bound "0". Any ideas here?

My second questions is because, although we need to compare such relations, we don't know where to look for previous solutions to this problem.

Anyway, thoughts, opinions and partial answers are very much appreciated.

### Bigger examples?

Imagine that the classified set is big enough. Given a relation/classification $A$ generated by an algorithm, if a second algorithm gets wrong only a few tuples of $A$ and also uses its own different-up-to-a-renaming label names, you would expect that a measure comparing $A$ with the output of the second algorithm would be very close to "1", or whatever the value for "equivalent" be in the concrete similarity measure.

### What we are trying to solve:

Here is the only known-by-me previous attempt in this direction:

https://sites.google.com/site/andrealancichinetti/mutual

### Hypothetical use cases

Here are a few scenarios where this need arises, although I don't know of any attempts to use it.

Two phylogenetic trees over the same set of species. Each specie is member of several -- nested -- taxonomical groups (the labels). This scenario can be further complicated if horizontal gene transfer is accounted for: in that case, two sibling groups can overlap in a few species. There are several methods in the literature to generate phylogenetic trees from sequence data, and a measure of similarity between them would be useful to create a consensus tree.

Comparing outputs of fuzzy classifiers, when they do soft labeling: http://www.scholarpedia.org/article/Fuzzy_classifiers .