General Information

Student:	Andrew Xie
Office:	CoRE 444 96 Frelinghuysen Rd, Piscataway, NJ 08854
School:	Rutgers University
E-mail:	andrew.x@rutgers.edu
Project:	Persistent Homology in the study of dynamic networks

Project Description

A dynamic metric space is a finite set of points equipped with a pseudometric that varies through time. The goal of this project is to extend curvature-set persistent homology to dynamic metric spaces, providing a computationally efficient method to track how the topology of data changes over time. We aim to develop a construction that is provably stable and representable, offering a principled technique to analyze dynamic data, such as motions of particles or neural activity.

Weekly Log

Week 0:

Much of this week was spent learning background material and defining possible research directions.

In particular, we read about poset-indexed persistence modules (most importantly zigzag persistence), which allows for non-monotone filtrations used to analyze dynamic data. We also reviewed Tom Needham's book on applied algebraic topology for general persistence theory.

In addition, Prof. Memoli has given us a few talks on Gromov-Hausdorff distance and dynamic metric spaces, and posed a few interesting questions about G-H distance between spheres and intervals/trees.

Week 1:

This week we found an interesting topic to work on, which is extending the notion of curvature set persistent homology to a dynamic (time-evolving) setting. At the moment, we have a rough roadmap of what to focus on next few weeks:

• Stability: given dynamic metric spaces \( \gamma_X \) and \( \gamma_Y \), the \( k \)th persistent homology of size \( n \) curvature sets is stable, i.e. "if \( \gamma_X \) and \( \gamma_Y \) are gromov-hausdorff close, then the persistence diagrams of the curvature sets must be similar". Formally:
  \[ 2 d^{\text{dyn}}_{\text{GH}}(\gamma_X, \gamma_Y) \ge d^{\mathcal{D}}_H(D_{n,k}(\gamma_X), D_{n,k}(\gamma_Y)) \]
• Representation: find an efficient way to summarize "thin" persistent vector spaces indexed by \( \mathbf{Int} \times \mathbb{R}_{+} \), where \( \mathbf{Int} \) is the poset category of intervals in \( \mathbb{R} \).

In addition, we gave a brief talk about our project to the rest of the DIMACS cohort.

Week 2:

This week I proved a partial result towards the classification task: for a persistence module \( f: \mathbf{Int} \times \mathbb{R}_{+} \rightarrow \textbf{Vec} \) arising from our particular construction, the structure maps \( f(I_1, \delta_1) \rightarrow f(I_2, \delta_2) \) are uniquely determined by \( \dim f(I_1, \delta_1) \) and \( \dim f(I_2, \delta_2) \). This allows us to summarize \( f \) as just a mapping, instead of a functor.

We also thought a bit more about Nadya's question of an explicit example of two spaces that are not homotopic but have the same Vietoris-Rips barcode. Prof. Memoli suggested adapting the classic \( S^2 \vee S^1 \vee S^1 \) and \( S^1 \times S^1 \) example with a modified metric, which seems to work.

Week 3:

This week we focused on characterizing the interleaving distance \( d_I(D_{n, k}(\gamma_X), D_{n, k}(\gamma_Y)) \).

By an earlier result, our persistence modules are uniquely determined by their "support", i.e. all the \( (I, \delta) \) where \( f(I, \delta) \cong \mathbb{F} \). I came up with a metric \( d \) that depends only on the geometry of the supports that lower bounds \( d_I \). This metric should be very easy to compute, if we allow ourselves to discretize the support.

I was hoping that \( d = d_I \), but unfortunately this isn't true. Intuitively, I believe that the counterexample I produced is basically the only way \( d = d_I \) can fail, so perhaps a slightly modified definition of \( d \) will suffice.

Week 4:

This week I worked on computing the interleaving distance \( d_I \) precisely: I came up with a metric \( d^* \) on the support sets such that \( d^*(S_\mathbb{V}, S_\mathbb{W}) = d_I(\mathbb{V}, \mathbb{W}) \). However, after speaking to my mentor we agreed that exactly computing the interleaving distance may not be necessary, and the less computationally intensive \( d \) may actually be preferable. Still, it was a somewhat interesting exercise.

We also thought about characterizing the support sets a bit more: we were able to rule out some very degenerate cases (e.g. the support set being a countable dense subset of a plane \( P \), where any two points in \( P \) are incomparable).

Finally, we discussed some computational (coding) details.

Week 5:

Since last week, we made some progress in understanding the structure of our modules, and produced a minimum viable implementation of our methods.

In particular, I proved that the modules \( \mathbb{V} \) produced by our construction are interval-decomposible, with the intervals being given by the order-connected components of the support: i.e. \( \mathbb{V} \cong \bigoplus_{\alpha \in A} \mathbf{1}_{S_\alpha} \) where \( \{S_\alpha\}_{\alpha \in A} \) are the connected components of \( S_\mathbb{V} \).

In addition, I was able to implement some python code that computes the support in \( O(t^2) \) time, and computes \( d \) in \( O(t^2 \log{t}) \) time, where \( t \) is the number of timesteps. This isn't a great time complexity, but for a research implementation it will probably suffice. Nadya was also able to produce an implementation of the erosion distance \( d_E \) in \( O(t^6) \) time, which although slow has the advantage of being very well-characterized in existing TDA literature (as opposed to \( d \)).

Week 6:

Much of this week was focused on (1) preparing for the final presentation, and (2) porting our python code to C++

Also, as the final presentation is coming up, I decided to prove the stability of our construction to ensure that we had some theoretical justification for the "validity" of our method. The proof ended up being more straightforward than expected, as there was already an existing stability result for a construction without curvature sets - making it work with curvature sets just required a technical lemma about Gromov-Hausdorff distance between subsets.

In addition, Nadya was able to find a very nice DP to compute \( d_E \) in \( O(t^3) \) time, which is now fast enough for us to run numerical experiments.

Additional Information

• My Mentors
  • Dr. Facundo Memoli
  • Sriram Raghunath
• My Personal Website