Understanding output of Graph Matching for unequal sized matches

[dokato]

I have two adjacency matrices of different sizes. I perform graph matching in both directions:

import numpy as np
from graspologic.simulations import sbm
from graspologic.match import GraphMatch as GMP

np.random.seed(1)

n = [50, 50]
p = [[0.5, 0.2],
     [0.2, 0.05]]

G = sbm(n=n, p=p)
 
n = [40, 40]
p = [[0.4, 0.2],
     [0.2, 0.01]]

Gsmall = sbm(n=n, p=p)

gm1 = GMP(padding='naive')
gm1.fit(G,Gsmall)
pi1 = gm1.perm_inds_

gm2 = GMP(padding='naive')
gm2.fit(Gsmall,G)
pi2 = gm2.perm_inds_

pi1.shape # (100,)
pi2.shape # (100,)

np.unique(pi1).shape # (100,)
np.unique(pi2).shape # (100,)

I'd expect pi2 to be of a different size than pi1. In particular I would think that output of gm2 would give me mapping of big G to a Gsmall. Or this is always just permutation of a larger graph?

---

Or in other words, when I want to compare the matching based on some labels from two graphs, it's easy on the gm2 case:

np.mean(labelsGsmall == labelsG[gm.perm_inds_][:len(labelsGsmall)])

How to do it for gm1?

[bdpedigo]

hi @dokato! I believe in either case, only the first min(len(Gsmall, G)) elements of perm_inds_ will be relevant, the other nodes were essentially matched to nothing - can you confirm @asaadeldin11? @asaadeldin11 I am trying to think whether this behavior would mean that only the first nodes of G are the ones being matched to in the case where the second graph is smaller.

In the meantime, I would just recommend always making the second graph the larger one - is there some reason you want to match things the other way around? the result should not depend on the order here.

regardless of what the answer ends up being we should clarify this in the docs, thanks for bringing this up.

[dokato]

Thanks @bdpedigo. I think that after reading more carefully the "Padded Graph Matching" chapter from docs I also found the solution to my labels problem. I just need to pad them at the end so they match the bigger graph.

is there some reason you want to match things the other way around

I was actually testing if the order matters when I got confused.

[bdpedigo]

@dokato great! please let me know if you have any other questions using the graph matching tools in particular - if you have a real-world problem in mind, there are some tricks (e.g. smart initializations, using seeds, etc) to using graph matching that we've found very helpful in the past but not all of them have been included/documented well yet.