Changed behavior of Graph.Biadjacency in igraph 1.0

[jboynyc]

Describe the bug

Creating a bipartite graph from a biadjacency matrix works in subtly different ways in igraph 0.11 and 1.0.

To reproduce

import numpy as np

m = np.array(range(1, 10)).reshape(3,3)

import igraph as ig

ig.__version__
# => '0.11.8'

ig.Graph.Biadjacency(m.tolist(), weighted=True).es["weight"]
# => [1, 2, 3, 4, 5, 6, 7, 8, 9]

ig.__version__
# => '1.0.0'

ig.Graph.Biadjacency(m.tolist(), weighted=True).es["weight"]
# => [1, 4, 7, 2, 5, 8, 3, 6, 9]

The behavior in igraph 1.0 is the equivalent of calling Graph.Biadjacency on the transposed biadjacency matrix in igraph 0.11:

ig.Graph.Biadjacency(m.T.tolist(), weighted=True).es["weight"]
# => [1, 4, 7, 2, 5, 8, 3, 6, 9]

Version information

0.11.8 and 1.0

[jboynyc]

I found that the tests for Graph.Biadjacency were updated in 1c423c60c77499476f9ae51aad65fca9340acef6 with the switch to c-igraph 1.0, anticipating the changed order of edges.

I could not locate the relevant change in the C core.

[szhorvat]

Could be an accidental change, i.e. bug, introduced by an optimization attempt. Will look into it

[szhorvat]

The graph created is the same, but the ordering of edges is indeed different. I don't know if we've ever guaranteed the ordering of edges. It'd be good to think this through and be explicit in the documentation about whether there are any guarantees about it.

Here's the C core commit:

https://github.com/igraph/igraph/commit/1ae1d033e3e420cf5d87bef05a32c6e477e3db06

The motivation was to improve performance by iterating through the matrix in storage-order, which happens to be column-major. At the time I simply missed the consequence on the edge order of the created graph.

The same change was made for igraph_adjacency(), but apparently only partially (not for all mode values). It's not even clear if the behaviour between different modes was ever consistent.

I'd probably not guarantee any edge order, but honestly I have to think this through. Any input / comments are very welcome!

[jboynyc]

Thanks! I think I used to assign weights directly, like g.es["weight"] = iter, but it looks like I switched to using g.es.set_attribute_values (example).

So, I guess I already learned not to depend on a specific order of edges. Maybe the changed behavior isn't such a big deal after all.

[szhorvat]

like g.es["weight"] = iter, but it looks like I switched to using g.es.set_attribute_values (

But this does not solve the issue, does it? The weight list still needs to be in an appropriate order.

What are your use cases for this, and how do you end up with both a weighted adjacency matrix and a list of weights that need to be compatible?

[jboynyc]

I poked around my codebase to understand where and why I do this. There is actually just one place where I need to assign edge weights, and that has little to do with the result of Graph.Biadjacency. I only noticed the changed behavior of Graph.Biadjacency due to a test that assumed stable edge order that started failing. It is not at all essential to how I work with bipartite networks.

Still, this might be an interesting edge case (ha!) to consider in thinking this through. I project the weighted bipartite network created by calling Graph.Biadjacency into a one-mode network. Since Graph.bipartite_projection does not handle weights, I calculate the weights of the projected network by multiplying the biadjacency matrix by its transpose (m @ m.T), and then I set them as edge attributes on the one-mode network I got from calling g.bipartite_projection.

I think I learned that I cannot assume a stable edge order, which is why I use g.es.set_attribute_values("weight", [weight[i] for i in pairs]) where pairs is a list of tuples containing vertex indices for each edge.

I hope that's clear enough.

[szhorvat]

I was about to make a note in the documentation of the C library when I saw that it's already there:

No guarantees are given about the ordering of edges.

https://igraph.org/c/html/latest/igraph-Generators.html#igraph_adjacency

https://igraph.org/c/html/latest/igraph-Generators.html#igraph_weighted_adjacency

I'll leave it to @ntamas to close this or update the Python docs.

If you have concerns (I can actually imagine that this might cause difficulties), let's work with specific examples/use cases and try to make the use case easy through the most appropriate means instead of just guaranteeing the edge ordering.