When simplification increases the number of edges (by removing edges through unary nodes)

[hyanwong]

We have encountered the case, a number of times, when simplification with keep_unary=False can actually increase the number of edges in a tree sequence. Indeed, for this reason, we currently keep unary nodes when simplifying in tsinfer.

An intuition for this rather unexpected result can be seen in the example currently used in the what-is-an-arg paper:

As I noted in the issue for that figure,

There is an interesting occurrence in this particular example which may bear more investigation. The simplification process (fig b) has actually created 2 edges above node 4, where 1 originally existed (fig a). That's because the lineage goes entirely through node 11, but in some trees, node 11 is a unary node. This is an example of a case where removing unary nodes both increases the number of edges and also generates a potentially misleading topology. It would be nice if there was a way to identify cases like this during simplification, but I think that would require very deep thought.

@petrelharp also commented:

This gives perhaps some good open questions? "Given a tree sequence, what is a good lower bound on the minimum number of edges required to represent it by a consistent tree sequence?" and "What is an algorithm that finds a consistent tree sequence with the minimum number of edges?" (where "consistent" means here having node identities agree)

[hyanwong]

I worry a little that the current simplification process could be seen to misleadingly create extra topology, in the example above, linking 4 to 13 without going through 11. We therefore need to be careful to say that in an arg diagram like the above, even if it appears that there are separate routes through the topology, they may (weirdly?) actually correspond to the same lineage.

[jeromekelleher]

I think the current simplification is well justified, in that it guarantees to keep all of the coalescences. So, if what you want are the marginal trees with all nodes of arity > 1 (which is what nearly everyone would consider a tree in the first place), this is what simplify does. I'd bet that this corresponds to the minimal number of nodes which you could use to represent the full information of those trees (including branch lengths), but I'm not sure how you'd go about proving that.

The default simplify operation may not be what you want in every situation, but it's well defined and a useful thing to do.

[jeromekelleher]

Totally agree these are interesting open questions btw.

[hyanwong]

Yes, I agree that it's a sensible (probably ideal) operation if all that you want are the marginal trees. I just think that we need a (minor) word of caution when interpreting the structure when plotted out as a graph instead of a set of trees.

[hyanwong]

I'd bet that this corresponds to the minimal number of nodes which you could use to represent the full information of those trees (including branch lengths)

Just to say that the version that I'm proposing, which keeps unary nodes if they are also coalescent points in other trees, is guaranteed to have the same number of tree sequence nodes as the fully simplified version, without unary nodes), although as @jeromekelleher says (above), local trees may have extra unary nodes present.

The interesting thing would be to show under what circumstances it is possible to simplify to a lower number of edges than the default simplification process, while keeping the total number of nodes the same.

[jeromekelleher]

I think this can be done reasonably easily, we just need to take a first pass through the overlapping_segments here to check if there is any coalescence (len(X) > 1 anywhere) and then act accordingly given the input parameters. This would also simplify the loop logic, because we wouldn't have to reason about creating new nodes or not in the the second pass. So, the basic change is that we make two passes through the overlapping segments, rather than one.

Can you come up with a name for this option to simplify and open an issue to track, please?

[hyanwong]

Issue is at #2127 for reference