Grounded persistent path homology: a stable, topological descriptor for weighted digraphs
Posted to site: 25/10/22
Weighted digraphs are used to model a variety of natural systems and can exhibit interesting structure across a range of scales. In order to understand and compare these systems, we require stable, interpretable, multiscale descriptors. To this end, we propose grounded persistent path homology (GRPPH) - a new, functorial, topological descriptor that describes the structure of an edge-weighted digraph via a persistence barcode. Joint work with Heather A. Harrington and Ulrike Tillmann.
The following summary of the manuscript was previously posted on Twitter. Please check out the manuscript on the arXiv for full details.
Persistent path homology (PPH) combines path homology (a homology theory for digraphs) and persistent homology (a tool for developing multiscale statistics). The input to PPH is a directed network and the output is a barcode; the pipeline is stable.
But what if I have a weighted digraph and I care about its underlying topology? As a first attempt, let’s compute the shortest-path quasimetric (a directed network) and then measure PPH.
This is a natural pipeline, but it has a problem! Consider this example; all edges in \(G_1\) have weight \(1\) and all edges in \(G_2\) have weight \(0.5\). The smaller holes in \(G_1\) are filled in as soon as they are born (by long squares at \(t=1\)). After subdividing, we recover the small features and birth times reduce.

This raises an issue for interpretation: the number of “holes” changes upon subdivision. The underlying graph already had three “holes” but our pipeline does not respect them. Moreover, representatives for the features do not naturally live in G.
To fix this issue, we introduce grounded persistent path homology (GrPPH). We alter the path homology chain complex so that all edges in G are born at time 0, but generators in degree 2 appear at the same time.

The number of features in the resulting barcode is equal to the circuit rank of the underlying graph. Moreover, we show there is a choice of undirected circuits, which form a basis for the cycle space and a persistence basis for GrPPH. The geometric nature of these representatives make them ideal for interpretation.
Back to our working example, \(G_1\) and \(G_2\) end up with the same barcode: \(\{\!\{[0, 1), [0, 1), [0, 2)\}\!\}\). Below, the small features are represented in blue and the larger feature in green (or red).

GrPPH is a functor from a category of weighted digraphs, where morphisms are maps of the underlying digraphs and contractions of the shortest-path quasimetric. This allows us to compare the GrPPH of digraphs related by such morphisms.
We find stability to weight perturbation and edge subdivision, as well as some edge collapses and edge deletions. As a corollary, GrPPH (and indeed PPH) converges under iterated subdivision.
We also show that GrPPH decomposes as a direct sum when G decomposes as a disjoint union or wedge sum. This is a boon for interpretation and computation: if an edge or a vertex belongs to no simple circuit, we can delete it without affecting GrPPH.

For completeness, we apply the same methodology to the directed flag complex. We find that weaker functoriality leads to an instability; deleting the blue edge below changes the barcode from \(\{\!\{[0, 21)\}\!\}\) to \(\{\!\{[0, 30)\}\!\}\).
When using GrPPH, the two persistent vector spaces are isomorphic.
