Flagifying the Dowker Complex

Abstract

The Dowker complex ${\mathrm{D}}_R(X,Y)$ is a simplicial complex capturing the topological interplay between two finite sets $X$ and $Y$ under some relation $R\subseteq X\times Y$. While its definition is asymmetric, the famous Dowker duality states that ${\mathrm{D}}_R(X,Y)$ and ${\mathrm{D}}_R(Y,X)$ have homotopy equivalent geometric realizations. We introduce the Dowker-Rips complex ${\mathrm{DR}}_R(X,Y)$, defined as the flagification of the Dowker complex or, equivalently, as the maximal simplicial complex whose $1$-skeleton coincides with that of ${\mathrm{D}}_R(X,Y)$. This is motivated by applications in topological data analysis, since as a flag complex, the Dowker-Rips complex is less expensive to compute than the Dowker complex. While the Dowker duality does not hold for Dowker-Rips complexes in general, we show that one still has that ${\mathrm{H}}_i({\mathrm{DR}}_R(X,Y))\cong {\mathrm{H}}_i({\mathrm{DR}}_R(Y,X))$ for $i=0,1$. We further show that this weakened duality extends to the setting of persistent homology, and quantify the ``failure" of the Dowker duality in homological dimensions higher than $1$ by means of interleavings. This makes the Dowker-Rips complex a less expensive, approximate version of the Dowker complex that is usable in topological data analysis. Indeed, we provide a Python implementation of the Dowker-Rips complex and, as an application, we show that it can be used as a drop-in replacement for the Dowker complex in a tumor microenvironment classification pipeline. In that pipeline, using the Dowker-Rips complex leads to increase in speed while retaining classification performance.

14 pages, comments welcome; fixed typos