2

I have a binary square sparse matrix A that can be seen as an adjacency matrix of a Graph.

Now consider a second binary square sparse matrix B that could have a different dimension.

I would like to build an algorithm that reorder the matrix A, or a set of elements of matrix A, in order to maximize the overlap with matrix B.

Below is an example:

I create a random sparse matrix B in python:

import scipy.spatial as spatial
import matplotlib.pyplot as plt
import numpy

coords_B = numpy.random.uniform(size=(20,3))*20
pdistmat = spatial.distance.squareform(spatial.distance.pdist(coords_B))
B = (pdistmat <= 8)
matshow(B)
colorbar()

matrix B

Now I build the matrix A by adding noise to B and adding some rows and columns:

coords_A = numpy.r_[numpy.random.uniform(size=(5,3))*20, 
                coords_B + numpy.random.uniform(size=(20,3))*4, 
                numpy.random.uniform(size=(6,3))*20]
pdistmat = spatial.distance.squareform(spatial.distance.pdist(coords_A))
A = (pdistmat <= 8)
matshow(A)
colorbar()

matrix A

Now I randomized the matrix A:

random_order = numpy.random.choice(A.shape[0], replace=False,
                                   size=A.shape[0])
A_randomized = A[random_order][:, random_order]
matshow(A_randomized)
colorbar()

A_randomized

I would like to reorder A_randomized to maximize the overlap with B as below:

x, y = numpy.where(A==1)
scatter(y,30-x, label='A')
x, y = numpy.where(B==1)
x+=5
y+=5
scatter(y,30-x, marker='.', label='B')
legend()

enter image description here

I would like to implement the algorithm in python using numpy and scipy.sparse libraries.

bougui
  • 3,507
  • 4
  • 22
  • 27
  • 1
    Once you choose the reordering, you probably want to implement it as a matrix multiplication. In fact, row or column indexing of `csr` format matrices is performed via matrix multiplication. https://stackoverflow.com/questions/39500649/sparse-matrix-slicing-using-list-of-int – hpaulj Jan 19 '18 at 08:00
  • 1
    Are these matrices always distance matrices? – Paul Brodersen Jan 19 '18 at 12:16
  • 1
    Also, is the goal to compute some sort of distance/similarity between the two matrices? There are ways to that that do not involve finding a mapping from one set of indices to another. – Paul Brodersen Jan 19 '18 at 12:18
  • @Paul: Yes these matrices always distance matrices thresholded – bougui Jan 19 '18 at 12:44
  • @Paul: The goal is to compute some sort of distance/similarity between the two matrices and to get the mapping from matrix A to matrix B – bougui Jan 19 '18 at 12:50
  • If these are indeed (euclidean) distances, then I would compute my similarity measure in euclidean space, not in the space of pairwise distances. Aligning two sets of points is a much easier and better understood problem than aligning two sets of distance measures. – Paul Brodersen Jan 19 '18 at 13:46
  • @Paul: Actually, the described example in my question is a toy model. In the real case I usually only know the binary sparse matrix and not the exact distances – bougui Jan 19 '18 at 13:49
  • The most general formulation of your problem is [graph matching](https://en.wikipedia.org/wiki/Graph_matching). Essentially, each index corresponds to a node and a non-zero entry in the matrix corresponds to an edge. However, [the general problem is quite hard, even in the exact case](https://en.wikipedia.org/wiki/Graph_isomorphism_problem). As these are distance matrices, I feel there should be a shortcut, but I can't think of one at the moment. – Paul Brodersen Jan 19 '18 at 14:02

0 Answers0