Comparing set relations

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:

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 .

• A relation (as you've defined it) is equivalent to a directed graph with vertex set a subset of the non-negative integers and an arc from $i$ to $j$ if $(i,j)$ is in the relation. Standard software packages such as nauty can decide isomorphism of directed graphs. But this question is not appropriate for this site. – Chris Godsil Feb 14 '12 at 15:09
• I don't think that's quite right, Chris: if I'm reading dsign's description correctly, it looks like the equivalence is "equal up to a relabeling of the codomain", and that the elements of the domain and codomain don't come with a natural correspondence. The two example relations are equivalent, but not isomorphic as directed graphs. – Owen Biesel Feb 14 '12 at 15:21
• @Chris: I don´t think the OP asked for a method to decide if two relations are equivalent. He asked for a way to measure "how equivalent" they are. I find the question interesting and potentially of "research level", even though one doesn´t need sophisticated, researchy-sounding words to ask it. – Ramiro de la Vega Feb 14 '12 at 15:28
• dsign, could you tell us a little more about what you want from this similarity measure? If you give an example of "not equivalent, but pretty close", it may be easier to build a function that's close to what you want. – Owen Biesel Feb 14 '12 at 15:30

If you're comparing two relations $R$ and $S$, try choosing a maximal relation $T$ such that $T$ is equivalent to a subrelation $T'$ of $R$ and to a subrelation $T''$ of $S$. Then let the "distance" $d(R,S)$ from $R$ to $S$ be the cardinality of $(R\setminus T')\cup (S\setminus T'')$ (i.e. $|R|+|S|-2|T|$); this defines a metric on the set of relations, and it is the number of ordered pairs you have to add and subtract from $R$ to get something equivalent to $S$.

Or if you would rather have a similarity "measure", try setting $\mu(R,S)=2|T|/(|R|+|S|)$, with $T$ as above. This equals 1 iff $|T|=|R|=|S|$, i.e. $R$ and $S$ are equivalent, and equals 0 iff $R$ and $S$ label nonoverlapping sets of objects.

Edit: For phylogenetic trees, you might want something slightly different, as the relations you get have the following property: for the sets of objects picked out by any two distinct labels, either they are disjoint, or one is strictly contained in the other. Perhaps you wouldn't mind allowing two relations to be equivalent up to reordering of labels and deleting duplicate labels?

In that case, each of the steps in the following path are distance 1 and the trees on either end are distance 2 apart, which agrees more with intuition than the earlier prescription of distances 2, 3, and 3, respectively. (source)

(Picture from John Baez's post on Operads and the Tree of Life, which discusses work done on the topological space of phylogenetic trees.)

• Hey, thanks, I will study and consider the choice using cardinals today carefully. Thanks for your expansion to phylogenetic trees; however, as I mentioned, they might me not be trees in the strict mathematical sense, due to horizontal gene transfer. But in that case still your above set measure applies. – dsign Feb 15 '12 at 5:53
• After checking, I think that your measure is simple and intuitive. Furthermore, doing a little research about how to determine T, I stumbled upon LSH (en.wikipedia.org/wiki/Locality_sensitive_hashing), which I think is a worthy finding. However I will leave the question open for a few hours more in the hope that somebody posts about instances of this problem in other concrete areas. – dsign Feb 15 '12 at 9:39

You might see how some notions fit with your intuition when small cases are examined. In the case of 1 object with n labels, similarity depends only on the number of labels given, and not which labels they are. In the case of 1 label for many objects, the dual notion of how many objects are labeled is key. Does your study favor one notion over the other?

Supposing that you temporarily study relations where each object is assigned at most one label. Now similarity can be measured by which objects share a label, and which do not. Is there an intuition as to what pair of relations is most dissimilar?

If you consider other properties you may want this measure to have, you may be able to classify and then later select which measure or measures best suit your purpose. Fortunately you have the restriction that the domain (the row order) is invariant, so that will simplify certain enumerations that you may want to classify your measure. For example, call the l-signature of a relation R that tuple such that the alpha-th coordinate is the number of labels assigned to alpha. How different can relations with the same l-signature be?

When you form and answer a number of questions of these types, then you can (or come back with your findings and we can) form your own class of measures which fit your intuition. Even just coming up with a set of signatures and saying which ones the measure should care about and which ones the measure can ignore will be progress.

Gerhard "Ask Me About System Design" Paseman, 2012.02.14