weighted projection of hypergraphs

[Liyubov]

We have been discussing this with Nicholas briefly. @nwlandry

At the moment there is one way to make the projection of the hypergraph:

• the projection is unweighted graph, which essentially makes sense when you want to analyze some structural properties of hypergraphs but not all of them:

https://xgi.readthedocs.io/en/stable/_modules/xgi/convert/graph.html

But when you want to really compare some higher-order properties of hypergraphs (even paths properties), you will need to look and make some weighted projections of hypergraphs. There are some algorithms available for this, and I am happy to help with implementing them or discussing if you think this is something which can already be derived from your existing functionalities :)

[nwlandry]

Thanks for this comment, @Liyubov! We have a few options for weighted matrices (See the linalg section). It looks like NetworkX can convert weighted matrices to graphs with a weight attribute --- is this what you were picturing? If you have an idea for the particular matrix (The clique motif matrix, for example) we can easily add the option to output this as a weighted graph. Great idea and thanks for the suggestion!

[Liyubov]

@nwlandry I was thinking of not going through networkx, as if you go through networkx then it is essentially becomes not the higher-order feature anymore, but feature of the projection.

the linalg section is great, and using it we can generated the initialy non-projected version using operations on tensor, we try to develop similar things here when we load and associate the tensor to the hypergraph and then make all operations with it...

https://github.com/Liyubov/hypergraph_structures/blob/main/code%20notebooks/hyper_graph_motif_counting_rewriting_numpy_ipynb_txt.ipynb

the difficulty with this approach is that it is actually then slow in python. so python may not be best?

[maximelucas]

Hi @Liyubov thanks for the suggestion. What exact object would you like to see implemented with weights?

We already have have NxN adjacency matrices at each order, optionally with weights for example: https://xgi.readthedocs.io/en/stable/api/linalg/xgi.linalg.hypergraph_matrix.html#xgi.linalg.hypergraph_matrix.adjacency_matrix With this, by summing them for all orders, you have what I would call a weighted projection of the hypergraph.

Were you thinking of something like this?

[Liyubov]

Hi @maximelucas there were several ideas regarding this. First and the main is that if we have weighted hypergraph, then when you are projecting it, depending on the type of projection you choose you can get various weights of the corresponding projected hypergraph. The idea of the method we wanted to propose develop further some ideas from this paper https://www.mdpi.com/1099-4300/25/6/923

We are currently working on trying to distinguish several types of projections of hypergraphs e.g. using line-graph projection of weighted hypergraph vs. clique-projection of weighted graph, which both bring two different results.

Happy to explain more.

[maximelucas]

Hi @Liyubov, thanks for the precisions!

Maybe the easiest towards implementations is if you wanted to submit a PR and we take a look?

If you prefer, you could also first share here a plan: how many different projections, in how many functions, with what specificities. Maybe we can then see how the existing functions could be used to implement those.

[Liyubov]

As is shown here (already for unweighted graphs) https://www.mdpi.com/1099-4300/25/6/923

If I understand well the description (correct me if I am wrong @maximelucas ) this matrix representation of hypergraph is not distinguishing between line graph and clique graph projections https://xgi.readthedocs.io/en/stable/api/linalg/xgi.linalg.hypergraph_matrix.html#xgi.linalg.hypergraph_matrix.adjacency_matrix

We are developing more code and explanations here https://github.com/Liyubov/hypergraph_distances Feel free to comment and happy to discuss/see what we can explain better there. Thanks!