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.

The fol­low­ing sum­mary of the man­u­script was pre­vi­ously posted on Twitter. Please check out the man­u­script on the arXiv for full de­tails.

---

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.

---

---

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 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).

---

---

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.

---

---

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.

---

---