Support hypergraphs and hypergraph algorithms

[agitter]

This issue is for brainstorming what would be involved in generalizing SPRAS to support hypergraphs and hypergraph algorithms. One possible goal could be showing how converting hypergraphs to graphs and running the graph algorithms in SPRAS is ineffective.

There are no short term plans to work on this.

[gkrieg]

Are any of the datasets naturally a hypergraph that have instead been converted into a graph for graph algorithms? I know that PPIs are typically graphs, and may be difficult to convert into hypergraphs, but any reaction network can be naturally converted to a hypergraph.

I suspect that many evaluation metrics are likely directly applicable to hyperpaths, as long as they refer to the original nodes and reactions within the reaction network.

[agitter]

We don't have many datasets in SPRAS yet and are making a push to add them this summer. We will likely add pathway databases, so those (e.g. Reactome) would support hypergraph representations.

[gkrieg]

That would be great. Do you already have a set of metrics to compare different pathway reconstruction methods? If so, could you point me to them?

[agitter]

We don't have anything written up yet. @ntalluri is working on that. We will likely use fairly standard machine learning classification metrics. The question is what to use for ground truth and when we will have edges versus only nodes for ground truth, which is likely when working with real data.

[gkrieg]

Sounds good. I would love to test our hyperpath and factory methods on pathway reconstruction benchmarks once they are available.

[tristan-f-r]

We can support this by using comma-separated gene names on the current interactome file format, giving the idea of a mixed hypergraph:

A	D	U
B,C,D	B,C,D	U
C	E	D
B,D	G,F,E	D
A	A	U

The main problem is representing those undirected hyperedges well: we should be tolerant of empty columns in those cases. For example, all of these should produce the same graph:

A	D	U
B,C,D	B,C,D	U

A	D	U
C,D	B,C	U

A	D	U
	B,C,D	U

A	D	U
B,C,D		U

[tristan-f-r]

I should mention this here: I'm currently working on a PR that adds mixed hypergraph support to halp: Murali-group/halp#34.