Vertex ordering in motif vertex maps

Hi there,

I am currently working with the clustering.motifs function and ran into a question/issue about the ordering of vertices in the returned vertex maps. Let me illustrate by an example:

edges = [(0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 4), (3, 5), (4, 6), (4, 7), (5, 7), (6, 8), (6, 9), (8, 9)]
gt_graph3 = gt.Graph(edges, directed=False)

motifs, counts, locations = gt.clustering.motifs(gt_graph3, 3, return_maps = True, motif_list = None)

for g, count, locations in zip(*(motifs, counts, locations)):
    print(g.get_edges())
    print([l.a for l in locations])

For d = 3 one of the motifs is simply a path with edges (0, 1), (1, 2) (i.e. node “1” is the middle node of the path)
The locations vertex map returns a list with entries [0, 3, 5], [0, 3, 4], [0, 1, 2] etc. that each map to a triple of vertices where this motif can be found.
Now I noticed that the order of the labels of these vertices is increasing, instead of in the same order as the motif.
More specifically, we have that nodes (0, 3, 5) indeed form a path with node 3 in the middle, but on the other hand nodes (0, 1, 2) also form a path but with node 0 in the middle.

Is there a way to ensure that the ordering of nodes in the vertex maps is the same as within the motif? This would mean that the vertex maps would be (0, 3, 5), (0, 3, 4), (1, 0, 2) etc. I have graphtool version 2.59

thank you!

This seems to be a bug! Can you please open an issue at https://git.skewed.de/count0/graph-tool/-/issues with this example? Thank you!

Hi Tiago,

Thank you! I opened an issue :slight_smile:

In the meantime, I was wondering whether you have any (efficient) suggestions to find the correct mapping of motifs?

My first idea was to do the following:

Let loc be the set of nodes where motif occurs, then simply construct the subgraph and check the isomorphic mapping of the nodes to the motif with the graphtool isomorphism function.

However, I encountered an issue with the isomorphism function (see my other post), and am also wondering about the efficiency of this approach? If you have any insights, I’d appreciate hearing your thoughts.

Sincerely, Eline

Yes, this approach should work, and should be fast enough for some purposes, but I understand this is a suboptimal situation, since the mapping shouldn’t be scrambled.

There’s a simple workaround for the isomorphism bug with filtered graphs that I posted in the other thread.

I’ll get these issues fixed soon.

FYI, this has been fixed in the newest release.

Awesome! Thank you very much for your time :slight_smile:

1 Like