Thomas Chaplin

DPhil Student - Mathematics

Grounded persistent path homology: a stable, topological descriptor for weighted digraphs ⊆ Research

Grounded per­sis­tent path ho­mol­ogy: a sta­ble, topo­log­i­cal de­scrip­tor for weighted di­graphs

Posted to site: 25/10/22

arXiv

Weighted di­graphs are used to model a va­ri­ety of nat­ural sys­tems and can ex­hibit in­ter­est­ing struc­ture across a range of scales. In or­der to un­der­stand and com­pare these sys­tems, we re­quire sta­ble, in­ter­pretable, mul­ti­scale de­scrip­tors. To this end, we pro­pose grounded per­sis­tent path ho­mol­ogy (GRPPH) - a new, func­to­r­ial, topo­log­i­cal de­scrip­tor that de­scribes the struc­ture of an edge-weighted di­graph via a per­sis­tence bar­code. Joint work with Heather A. Harrington and Ulrike Tillmann.

Project Summary

Persistent path ho­mol­ogy (PPH) com­bines path ho­mol­ogy (a ho­mol­ogy the­ory for di­graphs) and per­sis­tent ho­mol­ogy (a tool for de­vel­op­ing mul­ti­scale sta­tis­tics). The in­put to PPH is a di­rected net­work and the out­put is a bar­code; the pipeline is sta­ble.

But what if I have a weighted di­graph and I care about its un­der­ly­ing topol­ogy? As a first at­tempt, let’s com­pute the short­est-path qua­si­met­ric (a di­rected net­work) and then mea­sure PPH.

This is a nat­ural pipeline, but it has a prob­lem! Con­sider this ex­am­ple; 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 sub­di­vid­ing, we re­cover the small fea­tures and birth times re­duce.

The standard pipeline does not respect the number of holes in the underlying graph.
The stan­dard pipeline does not re­spect the num­ber of holes in the un­der­ly­ing graph.

This raises an is­sue for in­ter­pre­ta­tion: the num­ber of “holes” changes upon sub­di­vi­sion. The un­der­ly­ing graph al­ready had three “holes” but our pipeline does not re­spect them. More­over, rep­re­sen­ta­tives for the fea­tures do not nat­u­rally live in G.

To fix this is­sue, we in­tro­duce grounded per­sis­tent path ho­mol­ogy (GrPPH). We al­ter the path ho­mol­ogy chain com­plex so that all edges in G are born at time 0, but gen­er­a­tors in de­gree 2 ap­pear at the same time.

The new chain complex, altered from path homology, at time t in the filtration.
The new chain com­plex, al­tered from path ho­mol­ogy, at time t in the fil­tra­tion.

The num­ber of fea­tures in the re­sult­ing bar­code is equal to the cir­cuit rank of the un­der­ly­ing graph. More­over, we show there is a choice of undi­rected cir­cuits, which form a ba­sis for the cy­cle space and a per­sis­tence ba­sis for GrPPH. The geo­met­ric na­ture of these rep­re­sen­ta­tives make them ideal for in­ter­pre­ta­tion.

Back to our work­ing ex­am­ple, \(G_1\) and \(G_2\) end up with the same bar­code: \(\{\!\{[0, 1), [0, 1), [0, 2)\}\!\}\). Below, the small fea­tures are rep­re­sented in blue and the larger fea­ture in green (or red).

Representatives of the three cycles detcted by GrPPH, before and after subdivison.
Representatives of the three cy­cles detcted by GrPPH, be­fore and af­ter sub­di­vi­son.

GrPPH is a func­tor from a cat­e­gory of weighted di­graphs, where mor­phisms are maps of the un­der­ly­ing di­graphs and con­trac­tions of the short­est-path qua­si­met­ric. This al­lows us to com­pare the GrPPH of di­graphs re­lated by such mor­phisms.

We find sta­bil­ity to weight per­tur­ba­tion and edge sub­di­vi­sion, as well as some edge col­lapses and edge dele­tions. As a corol­lary, GrPPH (and in­deed PPH) con­verges un­der it­er­ated sub­di­vi­sion.

We also show that GrPPH de­com­poses as a di­rect sum when G de­com­poses as a dis­joint union or wedge sum. This is a boon for in­ter­pre­ta­tion and com­pu­ta­tion: if an edge or a ver­tex be­longs to no sim­ple cir­cuit, we can delete it with­out af­fect­ing GrPPH.

Two decomposition of G which lead to a decomposition of GrPPH
Two de­com­po­si­tion of G which lead to a de­com­po­si­tion of GrPPH.

For com­plete­ness, we ap­ply the same method­ol­ogy to the di­rected flag com­plex. We find that weaker func­to­ri­al­ity leads to an in­sta­bil­ity; delet­ing the blue edge be­low changes the bar­code from \(\{\!\{[0, 21)\}\!\}\) to \(\{\!\{[0, 30)\}\!\}\).

When us­ing GrPPH, the two per­sis­tent vec­tor spaces are iso­mor­phic.

A small example illustrating the instability when using the directed flag complex.
A small ex­am­ple il­lus­trat­ing the in­sta­bil­ity when us­ing the di­rected flag com­plex.

Software

If you would like to use GrPPH to study your data, in­stall our python li­brary with:

  pip install grpphati

Current fea­tures in­clude:

Documentation is still a work in progress but in­for­ma­tive ex­am­ples are avi­l­able on the GitHub repo.

If you need a more per­for­mant li­brary, check out grp­phati-rs which boosts grp­phati with Rust-accelerated bound­ary ma­trix con­struc­tion.

If you would like to get started right away, with­out in­stalling any­thing, then you can clone and start work­ing on this Google Colab note­book.

Computational Examples

Consider the fol­low­ing toy vas­cu­lar net­works which are mod­elled as fol­lows:

  1. Each edge is as­signed a length \(L\) and a cross-sec­tional area \(A\).
  2. Each node is given a net cur­rent (most are 0 ex­cept in­lets and out­lets).
  3. the net­work is mod­elled as an elec­tri­cal re­sis­tance net­work with edge re­sis­tance \(R = L/A \).
  4. Kirchoff’s laws yield a sys­tem of lin­ear equa­tions which we solve for the cur­rent \(I\) in each edge.
  5. Each cur­rent is con­verted to a time via \(T = (L * A) / I \).
A selection of toy vascular networks
A se­lec­tion of toy vas­cu­lar net­works.

Note the fol­low­ing dif­fer­ence be­tween the net­works:

We then mea­sure GrPdFlH of each of these net­works and com­pute the Betti curves.

Betti curves of GrPdFlH for each of the toy networks.
Betti curves of GrPdFlH for each of the toy net­works.

Some ob­ser­va­tions:

To as­sess the sta­bil­ity of each of these net­works we now sub­ject the net­works to two ran­dom per­tur­ba­tions

  1. Random in­de­pen­dent each re­moval, with prob­a­bil­ity \(p\).
  2. Random edge shuf­fling, with \(N\) at­tempted shuf­fles.

To make the sta­bil­ity dif­fer­ences more com­pa­ra­ble, we nor­malise each Betti curve by its max­i­mum value at \(t=0\).

Distribution of Betti curves un­der ran­dom ab­la­tion.
Distribution of Betti curves un­der ran­dom edge shuf­fles.

Note that the bi­fur­ca­tion net­works are more un­sta­ble to these per­tu­ba­tions, when com­pared to the Voronoi net­work, de­spite the sim­i­lar ini­tial de­scrip­tor.