Lower-star filtration algorithms

[ulupo]

It seems to me that flagser has all the components needed to be able to perform lower-star filtrations of (edge-unweighted) graphs or of their associated (edge-unweighted) flag complexes. This is a fairly popular technique in the literature, particularly on graph classification using persistent homology (esp. with deep learning...), and so I think it might be a nice addition to make, at very low cost.

The idea here would be that only the node weights and the set of passed edges are used for the filtration, but not the actual edge weights. There can be at least two versions:

1. Nodes appear according to their weights, and any edge (i, j) which was passed gets the maximum between node weight i and node weight j. No higher simplices are present.
2. As for 1 for nodes and edges, but higher simplices also appear according to "flagification".

I'm not too familiar with the algorithms mini-language but let me take a quick stab at 2:

lower_star_flag = max(faceWeights, 0, dimension)

On the other hand, I'm not too sure how to implement 1. Maybe assigning infinite filtration value to all simplices in dimension 2 or above?

A slightly unrelated question: what does the remove_edges algorithm https://github.com/luetge/flagser/blob/7ffe92782ae639b4265a52403d2d90d3151bb67b/algorithms.math#L19 achieve? Again because of my lack of familiarity with the mini-language (I've read the docs but a bit quickly...) it seems to me quite similar to max, except for the fact that it requires the user to pass at least one (random??) edge weight, and sets the node weights to zero regardless of user input. If my interpretation is correct, I guess I wonder why it is called remove edges, and what a typical use-case for it is.

[luetge]

Hi!

Sorry for the very late response. You can indeed do what you want: lower_star_flag overrideEdges = max(faceWeights)

This ignores edge weights, uses vertex weights and computes or each simplex of dimension >= 1 the value as the maximum weight of all faces. This should do what you described as 2., if you want to compute 1. then you just run the computation with --max-dim 1, to ignore all higher simplices.

The remove_edges algorithm came from an experiment we ran, where we wanted to measure the effect of randomly removing edges on the betti numbers of the flag complex. We achieve this by having all vertices present from the beginning and then adding edges at random times. Looking at the betti numbers over time gives an idea of how the complexity visible in the betti numbers relates to the amount of edges in the graph. The algorithm requires the user to provide edge weights for all edges, and no other weights.

I hope that helps, otherwise re-open the issue please!

[ulupo]

Sorry for the very late response.

No worries at all -- thanks for the comprehensive response!

You can indeed do what you want: lower_star_flag overrideEdges = max(faceWeights)

This ignores edge weights, uses vertex weights and computes or each simplex of dimension >= 1 the value as the maximum weight of all faces. This should do what you described as 2.

Just to confirm: your solution will not add new edges, but simply replace the values of existing ones, correct? If so, indeed this is the behaviour I'd like, and I wonder if you'd be happy for either of us to open a small PR adding this functionality.

if you want to compute 1. then you just run the computation with --max-dim 1, to ignore all higher simplices.

My understanding (from reading the docs) was that this would limit the computation to homology degree 1, while still computing 2-simplices. My question concerned computing homology degree 1 with an empty set of 2-simplices, but I realise that this is fundamentally outside the scope of an algorithm for persistent homology of flag complexes.

The remove_edges algorithm came from an experiment we ran, where we wanted to measure the effect of randomly removing edges on the betti numbers of the flag complex. We achieve this by having all vertices present from the beginning and then adding edges at random times. Looking at the betti numbers over time gives an idea of how the complexity visible in the betti numbers relates to the amount of edges in the graph. The algorithm requires the user to provide edge weights for all edges, and no other weights.

Thanks for the clarification!

[luetge]

Yes, there will not be any new edges added, only their filtration values will be ignored and replaced by the computation provided in the formula (here the maximum).

Regarding computation of homology in degree 1: you are absolutely right, it computes the homology taking 2-simplices into account. What you want seems to be just the homology of the graph itself, which you can determine from the euler characteristic. If you compute --max-dim 0 and you write down the chain complexes, you should be able to determine the persistence for dimension 1 as well.

Another option: if you subdivide your graph once (add a vertex into the middle of each edge), the flag complex is identical to the graph itself, and this operation does not impact the persistence diagram if you give the vertex the weight of the edge (in your case the maximum of the weights of the vertices the edge connects). If you are trying to read off generators you have to be careful to interpret the output properly (un-subdivide it in a way), but if you just want the diagrams then this should be enough.

[ulupo]

What you want seems to be just the homology of the graph itself, which you can determine from the euler characteristic. If you compute --max-dim 0 and you write down the chain complexes, you should be able to determine the persistence for dimension 1 as well.

Indeed, the "static" version (Betti 1) is easy via the Euler-Poincaré formula as you point out. Persistence would presumably need more work, i.e. knowledge of the Euler characteristic curve. I guess this is what you mean with "If [...] you write down the chain complexes".

Another option: if you subdivide your graph once (add a vertex into the middle of each edge), the flag complex is identical to the graph itself, and this operation does not impact the persistence diagram if you give the vertex the weight of the edge

Clever! (At least for me.) I only worry about the added memory overhead but this definitely works otherwise. Thanks for the input anyway!

Quoting myself in case this was missed:

I wonder if you'd be happy for either of us to open a small PR adding this functionality.

What do you think?

[luetge]

Memory should not be a problem since you are only looking at the 1skeleton, but certainly there are more efficient ways of doing this, agreed!

Happy to accept a pull request, sorry for skipping that part.