Finding optimal correspondences between objects given two square distance matrices

Question

I would like to find the optimal correspondences between two systems of objects based on the distances between objects WITHIN the two systems. So, the input to the algorithm would be two square distance matrices which express the distances of every object from one system to every other object within the same system. For example, if one system has objects {Q, R, S} and the other has objects {A, B, C} then the two distance matrices might look like:

        Q       R       S
Q       0       .5      .2
R       .5      0       .7
S       .2      .7      0

        A       B       C
A       0       .8      .4
B       .8      0       .3
C       .4      .3      0

meaning, for example, that the distance of object R to S is 0.7. Every object has a distance of 0 to itself, but the distances need not satisfy the assumptions of a metric space. However, each of the distance matrices can be assumed to be symmetric as in this example. The output of the algorithm would be a set of correspondences between objects in the systems that minimizes the sum of the absolute differences between the distances of corresponding objects under the constraint that no object in one system corresponds to more than one object in the other system. In the example above, the optimal correspondences would be R<->A, Q<->C, and S<->B, which results in a sum of dissimilarities between distances of:

|0.4-0.5| + |0.8-0.7|   for the distance relations that R and A enter into. E.g. dist(R,Q)=.5 and dist(A,C)=.4
          +
|0.2-0.3| + |0.5-0.4|   for the distance relations that Q and C enter into.
          +
|0.3-0.2| + |0.7-0.8|   for the distance relations that S and B enter into.
          =
         0.6

which is lower than any other consistent (no 2-to-1 correspondences allowed) way of placing the objects in correspondence. The output, then, for the algorithm, might look like:

        Q       R       S
A       0       1       0
B       0       0       1
C       1       0       0

where 1 means that the objects are placed into correspondences. I have already developed (http://cognitrn.psych.indiana.edu/rgoldsto/pdfs/relalign.pdf) an iterative neural network constraint satisfaction algorithm for this problem, but it is far too slow and computationally inefficient for systems that contain more than 20 or so objects because it has O(n^4) complexity. It feels like there should be a fast linear algebraic solution to this problem. There are a couple of possibly related solutions that I can’t seem to get to be related enough for my needs. For example, the “assignment problem” has a O(n^3) solution in the form of the “Hungarian algorithm” but this assumes fixed costs for each assignment, whereas in the above problem the cost associated with assigning A to Q, for example, depends on all of the other assignments being made because these other assignments will change which distances between systems are being compared. The problem also seems like something that might be handled with Multidimensional Unfolding or Generalized Procrustes Analysis, but the key difference in the current problem is that we don’t have labels that tell us which objects from one system are the same as which objects in the other system — that’s what we’re trying to figure out in the first place! Thanks for any leads.

Answer 1

One possible approach: use the Hungarian twice.

Here is your two square symmetric proximity matrices (I multiplied everything by 10; also, changed AB value from 8 to 9 - my fancy, with your permission)

        Q       R       S
Q              
R       5       
S       2       7       

        A       B       C
A       
B       9       
C       4       3       

Consider every pair of values between the matrices, their absolute difference, as a cost and construct the cost matrix

      AB     AC     BC
QR  |5-9|  |5-4|  |5-3|
QS  |2-9|  |2-4|  |2-3|
RS  |7-9|  |7-4|  |7-3|
             =
      AB     AC     BC
QR     4      1*     2
QS     7      2      1*
RS     2*     3      4

Perform Hungarian matching. The starred values above being the ones which sum is the minimum, and so the matching is

QR - AC
QS - BC
RS - AB

OK. In each pair, there is two objects from set1 and two objects from set2. Construct set1 X set2 object matrix showing how many times they encounter with each other within pairs.

   A   B   C
Q  1   1   2*
R  2*  1   1
S  1   2*  1

Perform Hungarian match (now treating these frequencies as gain, not cost). The starred values, which sum is maximized, mark the pairs you are after.

Q - C
R - A
S - B

As a variant, you can weight counts of the last (gain) matrix by the values from the previous cost matrix. For example, R and A encounter twice, as we see. Once under RS-AB with cost 2 and once under QR-AC with cost 1. So you can weight the frequency, make it the sum-of-costs. In your example, since costs are opposite to gains, you should somehow invert those weights; or just do the whole analysis based only on gains from the beginning.

Answer 2

I tried implementing ttnphns's proposed solution, with interesting results. To test the approach, I randomly generated 20 points in two dimensions for System 1, copied them over with a little noise to form System 2, and then I created a 20 X 20 distance matrix for each system based on the Euclidean distances between each pair of points within a system. If I created System 2 with very little noise, then the alignment is perfect:

(The blue and red shaded polygons and their defining edges are just added for visual legibility; they don't influence the algorithm at all)

So bravo ttnphn for proposing a solution that actually works! However, if I add just a bit more noise (you can intuitively see how much by comparing the positions of the points on the left and right sides), then the alignment is only slightly better than chance:

My impression for why the algorithm is not very noise-tolerant is that it is not treating the distances as properly structured. It does create consistent matches between the two sets of distance edges across the two systems, and then consistent matches of elements across the two systems, but there's nothing in the algorithm that pushes for R corresponding to A specifically because Q very likely corresponds to C and Q's distance to R is very similar to C's distance to A. My original algorithm is considerably more noise-tolerant than ttnphns's Double Hungarian algorithm, but alas, its computational complexity (O(C*N^4) where N is the number of elements per system and C is the number of constraint satisfaction iterations, typically at least 1000) still prevents it from being applied to more than, say, 30 elements per system.