Hypergraph operations

[nwlandry]

It would be cool to define the add and subtract methods (and maybe other methods?) for hypergraphs.

[maximelucas]

Could frame them as set operations: union, intersection, subtraction.

[nwlandry]

I like this idea!

[nwlandry]

Okay, so addition first: I add two hypergraphs. What should it return? And what I mean is

• What should we do if there are conflicting node/edge attributes?
• What to do to combine edges? Two options I can think of: (1) we go by edge IDs and resolve conflicts between duplicate edge IDs or (2) we go by edge members, in which case we either (a) completely re-index edges and make sure that every edge is added even though they may be duplicated or (b) look for unique edges, in which case, multi-edges are prohibited.

[leotrs]

When there is no canonical way of doing things, we should offer both ways OR implement whatever is easiest for the time being.

What should we do if there are conflicting node/edge attributes?

I'd suggest something like the following

xgi.add(G, H, attrs_from="first") # keep ONLY the attributes of G
xgi.add(G, H, attrs_from="second") # keep ONLY the attributes of H
xgi.add(G, H, attrs_from="update_first") # use attrs from G and then call .update() with attrs of H
xgi.add(G, H, attrs_from="update_second") # use attrs from H and then call .update() with attrs of G

What to do to combine edges? Two options I can think of: (1) we go by edge IDs and resolve conflicts between duplicate edge IDs

If there are ID conflicts I would throw an exception

(a) completely re-index edges and make sure that every edge is added even though they may be duplicated

This should always be an option, whether or not there are conflicts.

(b) look for unique edges, in which case, multi-edges are prohibited.

This is the same as adding all edges from both graphs and then removing duplicates, no?

[nwlandry]

• That seems reasonable.
• This seems reasonable I think? The only issue I would have with this is suppose that we run

H2 = xgi.uniform_hypergraph_configuration_model(k, 2)
H3 = xgi.uniform_hypergraph_configuration_model(q, 3)
H = xgi.add(H2, H3)

That would be super nice to be able to do without reindexing all the edges in H3.

• Yep, that's equivalent.

Another thought that I had (though in the context of this discussion seems maybe too reductive?) was that it would be cool to define H2 + H3 in the prior example.

[leotrs]

That would be super nice to be able to do without reindexing all the edges in H3.

I agree, but the question is, after executing this code, what do you expect the node IDs of H to be? Some nodes/edges have to be relabeled.

Unless you meant that you would like xgi.add to do the relabeling by default instead of throwing an exception by default?

Another thought that I had (though in the context of this discussion seems maybe too reductive?) was that it would be cool to define H2 + H3 in the prior example.

Yes that's what I was thinking too - this can easily be done by just defining __add__ to use the default arguments of xgi.add. Of course the infix operator + will never be as flexible tho.

[nwlandry]

Yeah, it's an interesting question. I can see both ways of doing it. I think the key problem is that some edge IDs actually mean something if we got the IDs from a dataset but some are auto-created if they don't already exist. Re-indexing would be good for this second case but doesn't make sense if the IDs mean something.

[leotrs]

If we ever implement __add__ then we must make sure that this is commutative so that H_1 + H_2 always gives the same as H_2 + H_1. If we implement hypergraph addition as taking attributes from, say, the first argument, then we should not implement __add__ since it would not be commutative.

[maximelucas]

#203 adds a version of "add"

[nwlandry]

I would be okay with closing this. I think we learned that it is actually pretty challenging to make hypergraph operations truly commutative so I don't know if the add method will be possible in the short term. And I think eventually subtraction would be interesting to have but I can't think of a good use for it now.

[maximelucas]

We could probably implement union and intersection? Using our ideas from the merge function.

[leotrs]

Closing this for now. Reasons:

• the add method turned out to be more difficult than expected
• this issue is way too broad, and the discussion incited from it has come to an end (it seems)
• if in the future we want/need to implement union/intersection/other operations we can open dedicated issues