Maximal persistence in random clique complexes

Recently, the topology of random simplicial complexes has been an active area of study — see, for example, the surveys [14] and [3]. This study has had applications in topological data analysis, including in neuroscience [11]. We will assume that the reader is familiar with the notions of persistent homology and a persistence diagram [9]. In topological inference, one sometimes considers points far from the diagonal in the persistence diagram to be representing “signal” and points near the diagonal as representing “noise”.

With this in mind, Bobrowski, Kahle, and Skraba studied maximally persistent cycles in random geometric complexes in [4]. They showed that with high probability the maximal persistence of a $k$-dimensional cycle in a random geometric complex in $\mathbb{R}^{d}$ is $\asymp\left(\log n/\log\log n\right)^{1/k}$. We write $f\asymp g$ if $f$ and $g$ grow at the same rate in the sense that there exist constants $c_{1},c_{2}>0$ such that $c_{1}f(n)\leq g(n)\leq c_{2}f(n)$ for all large enough $n$. Both the Vietoris–Rips and Čech filtrations have an underlying parameter $r$. Persistence of a cycle is measured multiplicatively as $r_{2}/r_{1}$ where $r_{1}$ and $r_{2}$ are the birth and death radius.

Our main result is that for fixed $k\geq 1$, the maximal persistence of $k$-cycles in a random clique complex filtration is of order roughly $n^{1/k(k+1)}$. A precise statement is given in Theorem 4.1. Here we measure the persistence of a cycle as $p_{2}/p_{1}$, where $p_{1}$ and $p_{2}$ are the birth and death edge probabilities, respectively.

The comparison between the Erdős–Rényi and random geometric settings may be more apparent if we renormalize so that the persistence of the associated filtrations can be measured on the same scale. One natural way to try to do this is to reconsider maximal persistence in random geometric complexes, using instead birth and death edge probability rather than radius.

The edge probability $P$ in a random geometric complex is of order $P\asymp r^{d}$. So if

then

As long as $d$ is fixed, $\left(\log n/\log\log n\right)^{d/k}$ is still much smaller than the maximal persistence of cycles in the random clique complex. However, this parameterization makes it clear that if $d$ grows, we expect cycles to persist for longer. It is known that random geometric graphs in dimension growing quickly enough converge in total variation distance to Erdős-Rényi random graphs, and this connection has been further explored and quantified in a number of recent papers — see, for example [7, 6, 18]. From this point of view, our main result can be seen as a “curse of dimensionality” for topological inference—as the ambient dimension gets bigger, noisy cycles persist for much longer.

In this section, we review the definition of the random clique complex, and briefly survey the literature on topology of random clique complexes.

The following random graph is sometimes called the Erdős–Rényi model.

We use the notation $G\sim G(n,p)$ to indicate that a graph $G$ is chosen according to this distribution. We say that $G$ has a given property with high probability (w.h.p.) if the probability that $G$ has the property tends to one as $n\to\infty$.

We define $X(n,p)$ to be the clique complex of the Erdős–Rényi random graph $G(n,p)$. We write $X\sim X(n,p)$ to indicate that $X$ is a random simplicial complex chosen according to this distribution.

In  [12], Kahle studied the topology of random clique complexes, and the following theorem roughly identified the threshold for homology to appear.

We use the notation $f\ll g$ to indicate $\lim_{n\to\infty}f/g=0$. Theorem 2.2 shows that the threshold for the appearance of $k$th homology is roughly $n^{-1/k}$. The following is the main result of a later paper, [13], showing that the threshold for the vanishing of $k$th homology is roughly $n^{-1/(k+1)}$.

Theorem 2.3 describes a sharp threshold for cohomology to vanish, in the same spirit as in Linial and Meshulam’s work [15]. These theorems all describe high-dimensional cohomological generalizations of the Erdős–Rényi theorem on the threshold for connectivity of $G(n,p)$ [10]. By universal coefficients, since we are working over a field, the results hold for homology with $\mathbb{Q}$ coefficients as well as cohomology.

Malen gave a topological strengthening of part (1) of Theorem 2.2 in [16].

This implies, in particular, that $H_{k-1}(X)$ is torsion-free, so this represents an important step toward the “bouquet-of-spheres conjecture” described in [12] and [13].

Newman recently refined Malen’s collapsing argument to give a probabilistic refinement [17].

In summary, earlier results show that there is one threshold where homology is born for the first time, when $p\approx n^{-1/k}$, and another where homology dies for the last time, when $p\approx n^{-1/(k+1)}$. Our main result is that there exist cycles that persist for nearly the entire interval of nontrivial homology.

We briefly review the second moment method, i.e. the use of Chebyshev’s inequality, which is our main probabilistic tool.

The variance is defined by

If $X$ can be written as a sum of indicator random variables $X=\displaystyle\sum_{i}X_{i}$, then the following is easy to derive and its proof appears, for example, in Chapter 4 of Alon and Spencer’s book [1].

It follows from Chebyshev’s inequality 3.1 that if $\mathbb{E}(X)\rightarrow\infty$ and

then $X>0$ w.h.p. In fact, $X\sim\mathbb{E}(X)$ w.h.p., meaning that $X/\mathbb{E}(X)\to 1$ in probability.

Finally, we note that if are $X_{i},X_{j}$ are indicator random variables for events $A_{i},A_{j}$, we have that

Here $A_{i}\wedge A_{j}$ denotes the event that both $A_{i}$ and $A_{j}$ occur.

We consider the random graph $G(n,p)$ as a stochastic process, as follows. Consider the random filtration of the complete graph $K_{n}$ where each edge $e$ appears at time $p_{e}$, chosen uniform randomly in the interval $[0,1]$. Similarly, the random clique complex $X(n,p)$ is a random filtration of the simplex on $n$ vertices $\Delta_{n}$.

We assume the reader is familiar with persistent diagrams [9, 8]. A point $(x,y)$ in the persistence diagram for $H_{k}$ with $\mathbb{Q}$ coefficients and $k\geq 1$ represents a $k$-dimensional cycle with birth time $x$ and death time $y$. We measure the persistence of that cycle multiplicatively, as $y/x$. Define

where the maximum is taken over all points in the persistence diagram for homology in degree $k$.

An equivalent definition is the following. Consider the natural inclusion map $i:X(n,p_{1})\hookrightarrow X(n,p_{2})$, where $0\leq p_{1}\leq p_{2}\leq 1$. For every $k\geq 1$, there is an induced map on homology $i_{*}:H_{k}(X(n,p_{1}))\to H_{k}(X(n,p_{2}))$. Then

where the maximum is taken as $p_{1}$ and $p_{2}$ range over all values with $0\leq p_{1}\leq p_{2}\leq 1$.

Our main result is the following.

Our results are actually slightly sharper then this. A slightly sharper statement is the following.

Suppose that

and

Then w.h.p.

So then our results are sharp, up to a small power of $\log n$.

Since Theorem 2.3 is only known to hold for $\mathbb{Q}$ coefficients (or any field of characteristic zero), our upper bounds on maximal persistence only apply for persistent homology with $\mathbb{Q}$ coefficients. For lower bounds, we use the second moment method to prove the existence of cycles that persist nearly as long as possible, and these lower bounds hold for arbitrary field coefficients.

Recall that we earlier defined

We believe that the $M_{k}(n)$ is likely of order roughly $f_{k}(n)$, in the following sense.

Let $\omega(n)$ be any function that tends to infinity with $n$. We showed in the proof of Theorem 4.1 that

We believe that an analogous lower bound should hold.

The following kind of limit theorem would provide precise answers to questions like, “Given a prior of this kind of distribution, what is the probability $P(\lambda)$ that there exists a cycle of persistence greater than $\lambda$?”

See Figures 1 and 2 for some numerical experiments illustrating these conjectures. These experiments were computed with the aid of Ulrich Bauer’s software Ripser [2].

It also seems natural to study more about the “rank invariant” of a random clique complex filtration. That is, given $k\geq 1$, $p_{1}$, and $p_{2}$, how large do we expect the rank of the map $i_{*}:H_{k}\left(X(n,p_{1})\right)\to H_{k}\left(X(n,p_{2})\right)$ to be?

In [12], it is shown that

so this conjecture is that almost all of the homology persists for as long as possible.

Bobrowski and Skraba study limiting distributions for maximal persistence in their recent preprint [5]. They describe experimental evidence that there is a universal distribution for maximal persistence over a wide class of models, including random Čech and Vietoris–Rips complexes. It is not clear whether we should expect the random clique complex filtration studied here to be in the same conjectural universality class.