D-GRIL: End-To-End Topological Learning with $\mathrm{𝟐}$-Parameter Persistence

In this subsection, we briefly review the concepts in multiparameter persistent homology. We focus, primarily, on 2-parameter persistent homology. For detailed definitions, refer [20, 22]. We begin by recalling the definition of a simplicial complex. Given a finite vertex set $V$, a simplicial complex $K=K(V)$ defined on this vertex set is a collection of subsets of $V$ such that if a subset $\sigma \subseteq V$ is in $K$, then all proper subsets $\tau \subset \sigma$ are also in $K$. Each element in $K$ with cardinality $k+1$ is called a $k$-simplex or simply a simplex. A graph is a simplicial complex where $V$ is the vertex set of the graph and $K$ consists of edges and vertices of the graph. A filtration is a collection of simplicial complexes ${\{K_{𝐱}\}}_{𝐱\in ℝ}$ indexed by the reals, with the property that $K_{𝐱}\subseteq K_{𝐲}$ for each $𝐱\le 𝐲$. Extending this definition to collections of complexes indexed by ${ℝ}^2$ with the product partial order ($𝐱\le 𝐲\in {ℝ}^2$ if $x_1\le y_1$ and $x_2\le y_2$), we get a bifiltration.

Let $K$ be a simplicial complex and $f:K\to {ℝ}^2$ be a map with the property that $f(\sigma )\le f(\tau )\in {ℝ}^2$ for all $\sigma \subseteq \tau$. For each $𝐱\in {ℝ}^2$, let $K_{𝐱}≔\{\sigma \in K:f(\sigma )\le 𝐱\}$. Clearly, $K_{𝐱}\subseteq K_{𝐲}$ for all comparable $𝐱\le 𝐲\in {ℝ}^2$. The resulting bifiltration, denoted ${\{K_{𝐱}^f\}}_{𝐱\in {ℝ}^2}$, is called the sub-level set bifiltration of the bifiltration function $f$.

A filtration in the $1$-parameter case induces a persistence module, obtained by considering the inclusion-induced linear maps between the vector spaces given by the homology groups of the simplicial complexes comprising the filtration. Similarly, we obtain a $2$-parameter persistence module from a bifiltration.

Readers familiar with category theory can recognize that a 2-parameter persistence module is a functor $M:{ℝ}^2\to {\text{vec}}_{𝔽}$ where the poset ${ℝ}^2$ is regarded as a category and ${\text{vec}}_{𝔽}$ denotes the category of finite-dimensional vector spaces over a field $𝔽$.

Given a bifiltration ${\{K_{𝐱}\}}_{𝐱\in {ℝ}^2}$, we consider $H_i(K_{𝐱})$, the $i$th homology group of the simplicial complex $K_{𝐱}$ over a field $F$, say ${\mathbb{Z}}_2$. Then, for each inclusion $K_{𝐱}\subseteq K_{𝐲}$, we get an induced linear map $H_i(K_{𝐱})\to H_i(K_{𝐲})$. By this assignment, we get a 2-parameter persistence module.

Let ${\{K_{𝐱}^f\}}_{𝐱\in {ℝ}^2}$ be a sub-level set bifiltration. Then the 2-parameter persistence module $M$ obtained by the homology assignment is called the 2-parameter persistence module induced by $f$, and we denote it as $M_f$.

As mentioned in Section 2, Gril vectorization uses the concept of generalized rank introduced by [32], which we define below formally.

We refer the reader to [36] for the definitions of limit, colimit, and the construction of the canonical limit-to-colimit map. Intuitively, generalized rank captures the number of independent topological features supported over the interval $I$. It can be computed efficiently for $2$-parameter persistence modules [18] using zigzag persistence [17].

We recall the definitions of o-minimal structure and definable function here.

A subset $A\in S_n$ for some $n\in \mathbb{N}$ is known as a definable set in the o-minimal structure. Let $A\in S_n$ be given. A function $f:A\to {ℝ}^m$ is said to be definable if the graph of the function in ${ℝ}^{n+m}$ is a definable set.

We note that all semi-algebraic functions are definable. In fact, the author in, [47], shows that there exists an o-minimal structure that simultaneously contains all semi-algebraic sets and the graph of the exponential function. The authors in [14] use this result to show that a neural network, being a composition of definable functions, is definable (Corollary 5.11 [14]). For readers not familiar with the notion of definable functions, it is sufficient to know that a piecewise affine map is definable.

In this subsection, we briefly review the result and the conditions under which stochastic sub-gradient descent converges as shown in [14]. In [7], authors use this result in the setting of $1$-parameter persistent homology and show that stochastic sub-gradient descent converges in that case. We begin by reviewing the definition of Clarke subdifferential. Given a locally Lipschitz function $f:{ℝ}^n\to ℝ$, the Clarke subdifferential of $f$ at a point $x$ is defined as:

where $\mathrm{𝐂𝐨}$ denotes the convex hull of the set.

Now, given a loss function $ℒ$ with the objective of minimizing it, consider the differential inclusion

where $\partial ℒ(𝐳(t))$ denotes the Clarke subdifferential of the function $ℒ$ at the point $𝐳(t)$. The solutions $𝐳(t)$ are the trajectories of the sub-gradient of $ℒ$ which can be approximated by the standard stochastic sub-gradient descent method given by:

where the sequence ${({\alpha }_k)}_k$ is the learning rate and ${({\zeta }_k)}_k$ is a sequence of random variables or “noise”. [14] establish that under mild technical assumptions ( stated below) on these two sequences, the stochastic sub-gradient method converges almost surely to critical points of $ℒ$ if $ℒ$ is locally Lipschitz and definable.

Consider the following assumptions (Assumption C in [14]):

1. 1.

   for any $k$, ${\alpha }_k\ge 0$, ${\mathrm{\Sigma }}_{k=1}^{\mathrm{\infty }}=\mathrm{\infty }$ and ;

2. 2.

   , almost surely;

3. 3.

   denoting by ${ℱ}_k$ the increasing sequence of $\sigma$-algebras , there exists a function $p:{ℝ}^d\to ℝ$ which is bounded on bounded sets such that almost surely, for any $k$,

We begin by recalling the definitions of $\mathrm{\ell }$-worm and Gril.

Refer to Figure 1 for a $2$-worm.

Fixing the bifiltration function $f$ and $k,\mathrm{\ell }$, the landscape ${\lambda }^M$ provides a function ${\lambda }_{k,\mathrm{\ell }}^{M_f}:{ℝ}^2\to ℝ$, $𝐩\mapsto {\lambda }^{M_f}(𝐩,k,\mathrm{\ell })$. The Gril vector is the vector of values of ${\lambda }_{k,\mathrm{\ell }}^{M_f}$ evaluated at a set of chosen sample points $\{{𝐩}_1,\mathrm{\dots },{𝐩}_s\}\subset {ℝ}^2$.

Let $K$ be a simplicial complex with $n$ simplices, labelled ${\sigma }_1,{\sigma }_2,\mathrm{\dots },{\sigma }_n$. A bifiltration function $f:K\to {ℝ}^2$ can be viewed as a vector ${𝐯}_f\in {ℝ}^{2n}$ where, for $k=1,\mathrm{\dots },n$, ${𝐯}_f[2k-1]=f_x({\sigma }_k)$ and ${𝐯}_f[2k]=f_y({\sigma }_k)$. Here, $f_x(\sigma )$ and $f_y(\sigma )$ denote the $x$- and $y$-coordinates of the vector $f(\sigma )$ respectively. Notice that the vectors in ${ℝ}^{2n}$ that correspond to a valid bifiltration function form a convex cone. We work with this set of vectors in ${ℝ}^{2n}$. In this setting, the authors in [48] show that Gril is Lipschitz continuous in the following sense.

By Rademacher’s theorem [23], ${\mathrm{\Lambda }}_{k,\mathrm{\ell }}^{𝐩}$ is differentiable almost everywhere.

Let ${𝒢}_{k,\mathrm{\ell }}:{ℝ}^{2n}\to {ℝ}^s$ be the map defined as:

where ${\{{𝐩}_j\}}_{j=1}^s$ are the $s$ sampled center points. We drop the $k,\mathrm{\ell }$ and refer to ${𝒢}_{k,\mathrm{\ell }}$ as $𝒢$ whenever $k,\mathrm{\ell }$ are well understood. We note that $𝒢$ is also a function of the center points ${𝐩}_j$ for all $j$. We show that $𝒢$ is piecewise affine.

For notational convenience, in what follows we denote $f_x(\sigma )$ as ${\sigma }^x$ and $f_y(\sigma )$ as ${\sigma }^y$, and we call them the simplex coordinates of $\sigma$. Similarly, we denote the $x$-coordinate and $y$-coordinate of $𝐩$ as ${𝐩}^x$ and ${𝐩}^y$ respectively.

We observe that, if there are two simplices ${\sigma }_i,{\sigma }_j$ such that for some $\rho \in \mathbb{Z}\text{ and }0\le \rho \le \mathrm{\ell }$ and $a,b\in \{x,y\}$, one has $|{\sigma }_i^a-{𝐩}_t^a|=\rho \cdot |{\sigma }_j^b-{𝐩}_t^b|$ then, say for $a=x$ and $b=y$, the point representing the vector ${𝐯}_f$ lies on a hyperplane in ${ℝ}^{2n}$:

Corresponding to each such pair of simplex coordinates, we get one hyperplane. Here, in the example, we chose one simplex coordinate to be $x$-coordinate and the other to be $y$-coordinate. This, however, need not always be the case: we can have all four possible combinations of $x$- and $y$-coordinates, corresponding to each of which we get a hyperplane. We refer the reader to Appendix A in [40] for the exact formula of all such hyperplanes. Combining all these hyperplanes, we get an arrangement $\mathscr{H}$ of hyperplanes in ${ℝ}^{2n}$ [26]. The arrangement $\mathscr{H}$ partitions ${ℝ}^{2n}$ into relatively open $r$-cells, $r\in \{0,\mathrm{\dots },2n\}$. We observe that this arrangement induces an affine stratification ${𝒮}_{\mathscr{H}}$ (refer [34] for the formal definition) of ${ℝ}^{2n}$ where the $r$-dimensional strata are precisely the $r$-cells.

In the following we prove that $𝒢$ is a piecewise affine map relative to this arrangement, meaning that it is affine on each stratum of ${𝒮}_{\mathscr{H}}$. To this end, we introduce the notions of upper boundary, lower boundary, and constraining simplex coordinate for an $\mathrm{\ell }$-worm which will allow us to characterize the strata of ${𝒮}_{\mathscr{H}}$ in terms of conditions on the bifiltration function. We give an intuitive explanation of these concepts using Figure 1. We refer the reader to Appendix A in [40] for the formal definitions.

In Figure 1, a $2$-worm is shown with its lower boundary colored in blue and its upper boundary in red. As depicted, the lower boundary consists of the part of the boundary that is in the lower half of the worm, while the upper boundary consists of the rest of the boundary, i.e., a point belongs to the lower boundary (resp. upper boundary) if the open lower-set (resp. upper-set) of the point does not intersect the worm.

For an intuitive understanding of constraining simplex coordinate, consider the Gril value $d$ of an $\mathrm{\ell }$-worm centered at $𝐩$ for a given rank $k$. It follows from Definition 8 that there exists at least one simplex $\sigma$ such that ${\sigma }^x$ or ${\sigma }^y$ prevents the worm from expanding any further to have a Gril value more than $d$ at $𝐩$. The coordinate in question (either ${\sigma }^x$ or ${\sigma }^y$) is called a constraining simplex coordinate for the $\mathrm{\ell }$-worm centered at $𝐩$. Here, by preventing the worm from expanding, we mean that if the worm were to expand then the value of the generalized rank over the worm would drop below the given value of rank $k$. Note that an $\mathrm{\ell }$-worm can have multiple constraining simplex coordinates, including some coming from the same simplex $\sigma$.

We can characterize the top-dimensional ($2n$-dimensional) strata of ${𝒮}_{\mathscr{H}}$ in terms of conditions on constraining simplex coordinates for $\mathrm{\ell }$-worms, and consequently, in terms of conditions on the bifiltration functions.

We state the main theorem of this subsection.

Overview of the proof: $𝒢$ depends affinely on the simplex coordinates in each top-dimensional stratum, because there is a unique constraining simplex coordinate for each $\mathrm{\ell }$-worm. By continuity of $𝒢$ (Proposition 9), the restriction of $𝒢$ to each (affine) lower dimensional stratum is affine.

In our machine learning pipeline, the Gril map $𝒢$ is post-composed with a loss function $N:{ℝ}^s\to ℝ$, derived e.g. from some neural network. In the corollary below, we give sufficient conditions on $N$ that ensure the convergence of stochastic sub-gradient descent on $N\circ 𝒢$.

Overview of the proof: In the discussion towards the end of section 3.3, we saw that any piecewise affine map is definable. Since $𝒢$ is piecewise affine, it is locally Lipschitz and definable. We know that the composition of two definable functions is definable, and that the composition of two locally Lipschitz functions is locally Lipschitz. These facts, put together with Proposition 6, immediately lead to the fact that stochastic sub-gradient descent converges almost surely to critical points of $N\circ 𝒢$.

In order to back-propagate gradients through the Gril computation, we need an explicit formula for the differential of $𝒢$. Such a formula is needed only in the top-dimensional strata, where $𝒢$ is actually smooth. In lower-dimensional strata, sub-gradients can be approximated using, e.g., gradient sampling [3].

In section 4.1, we saw that $𝒢$ is piecewise affine, which implies that its differential is constant in each top-dimensional stratum. In order to compute it, we need to determine the sign of the gradient at different simplex coordinates. To do so, given a worm, we distinguish between simplex coordinates that constrain the lower boundary of the worm and those that constrain its upper boundary. Since each simplex has two coordinates, $x$ and $y$, and these can be constraining either the upper boundary or the lower boundary, we get four different cases: lower $x$-constraining, lower $y$-constraining, upper $x$-constraining and upper $y$-constraining. All these cases are shown in Figure 1.

We deduce an explicit formula for the differential of $𝒢$ in the top-dimensional strata.

Recall that each ${𝐯}_f$ in a top-dimensional stratum of ${𝒮}_{\mathscr{H}}$ corresponds to a bifiltration function $f$ with a unique constraining simplex. Refer to Figure 2 for an intuitive explanation about the sign of the gradient and the different cases in Theorem 13, as shown by the arrows in Figure 1.

In section 4.1 we saw that $𝒢$ is piecewise affine and in section 4.2 we deduced that stochastic sub-gradient descent converges almost surely to critical points of $N\circ 𝒢$ for any definable and locally Lipschitz loss function $N$. We gave an explicit formula for the differential of Gril in the top-dimensional strata in section 4.3, and at the beginning of that section we argued that gradient sampling can be used to approximate sub-gradients in lower-dimensional strata. In practice, for the sake of computational efficiency, we use a simple variant of gradient sampling, which consists of sampling a single nearby point and taking its gradient.

So far, we considered a bifiltration function on the entire simplicial complex $K$. However, in practice, we may need to extend the filtration function to the entire simplicial complex based on filtration function values on certain simplices. For example, in a lower-star filtration, the filtration function values on the higher dimensional simplices are dictated by the filtration function values on the vertices of the simplicial complex. In a Rips filtration, the filtration function values on the vertices are 0, while the filtration function values on higher dimensional simplices are dictated by the filtration function values on the edges.

In such scenarios, the bifiltration function $f$ is given on a subcomplex $L$ of the simplicial complex $K$. This is extended to a bifiltration function $\overline{f}$ on the entire simplicial complex in a piecewise constant manner. We use the example of lower-star bifiltration to show how our framework fits to this type of scenario. Let $f:K^0\to {ℝ}^2$ be a function on the vertices of the simplicial complex $K$ with $m$ vertices and $n$ simplices. The map $f$ is extended to a piecewise constant map $\overline{f}:K\to {ℝ}^2$ as follows: for an edge $e=(u,v)$, we let ${\overline{f}}_x(e)=\max \{f_x(u),f_x(v)\}$ and ${\overline{f}}_y(e)=\max \{f_y(u),f_y(v)\}$; the values on higher dimensional simplices are defined inductively. Notice that for each simplex $\sigma \in K$, there is a maximal $x$-vertex and a maximal $y$-vertex, the vertices that give the $x$ and $y$-values to the simplex respectively. We know that $f$ can be represented as a vector ${𝐯}_f\in {ℝ}^{2m}$ and $\overline{f}$ as a vector ${𝐯}_{\overline{f}}\in {ℝ}^{2n}$ after ordering the simplices of $K$. Consider the map $q:{ℝ}^{2m}\to {ℝ}^{2n}$ given by $q({𝐯}_f)={𝐯}_{\overline{f}}$. The map $q$ is piecewise affine and thus, $𝒢\circ q$ is piecewise affine as well. Therefore, we can apply stochastic sub-gradient descent on $N\circ 𝒢\circ q$ with analogous convergence guarantees.

Observe that we get an arrangement of hyperplanes on ${ℝ}^{2m}$, ${\mathscr{H}}_q$, analogous to $\mathscr{H}$ on ${ℝ}^{2n}$ that we saw in the previous subsections. On the top-dimensional cells of ${\mathscr{H}}_q$, the differential of $q$ is well-defined and constant and expressions analogous to the ones in Theorem 13 can be derived, and the chain rule can be used for back-propagating gradients. As mentioned previously, we use a simple form of gradient sampling to approximate sub-gradients when the gradient is not well-defined. For the experimental section that follows, $N$ is a neural network with one of the standard choices for loss functions, which is definable as discussed towards the end of section 3.2.

We observe that if the bifiltration $f$ is extended to $\overline{f}$ as described above , then we end up in a scenario where multiple simplices have the same $x$ or $y$-values. This is a degenerate scenario with respect to the assumptions in Theorem 11. To avoid this, in practice, we add an infinitesimal perturbation to the higher dimensional simplices to ensure the values are not exactly the same. We note that this is, in spirit, similar to gradient sampling.

Every instance in each dataset is an attributed graph with a label associated with it. We use a Graph Isomorphism Network (GIN) [49], as a candidate GNN architecture, to obtain a bifiltration function over the vertices. We consider the lower-star bifiltration of this function. This gives us a bifiltration function on the entire graph, which we denote as $f$. Let ${𝐯}_f$ denote the vector representation of $f$ which we get after ordering the $n$ simplices of the graph. We divide the range of $f$ into a grid of size $100\times 100$. We randomly initialize the $s$ center points from this grid and compute the vector ${𝒢}_{k,\mathrm{\ell }}({𝐯}_f)$ (Eq. (2)) for $k=1,2,3$ and $\mathrm{\ell }=2$ at these center points. This vector ${𝒢}_{k,\mathrm{\ell }}({𝐯}_f)$ is fed to a $3$-layer Multilayer Perceptron (MLP) classifier and the loss is back-propagated through the Gril computation according to the gradient described in Section 4. Refer to Figure 3 for an illustration. Note that the positions of the $s$ center points are also optimized as the gradient can be back-propagated to the coordinates of the center points as well. We refer the reader to Appendix B in [40] for additional details.

The data is extracted from the ChEMBL database [24, 13]. Each dataset contains the SMILES [46] encoding of a novel drug (compound), and activity pairs for a target of interest. For example, the EGFR dataset contains all the molecules that have been tested against epidermal growth factor receptor (EGFR) kinase, and their measured bio-activity. The SMILES encodings of the molecules are then converted to graphs with Molfeat [41]. Bio-activity is measured in half maximal inhibitory concentration $(I{C}_{50})$, which qualitatively indicates how much a drug is needed, in vitro, to inhibit a particular process by $50\%$. To facilitate the comparison of $I{C}_{50}$ values, it is common practice to convert $I{C}_{50}$ to $pI{C}_{50}=-{\log }_{10}(I{C}_{50})$, expressed in molar units. Threshold for activity cutoff $pI{C}_{50}=6.3$ is used throughout the paper. We refer the reader to Appendix B in [40] for additional details.

In the first set of experiments, we compare D-Gril with (i) a standard GNN model–GIN with sum-pooling, (ii) with GIN and Gril as a readout layer and with (iii) GIN and Mpsm [44]. Note that for the results on GIN-Gril, Gril is used as a passive readout layer, i.e., we obtain a bifiltration function from a pre-trained GIN (pre-trained for graph classification on the same dataset) and compute Gril on it. We use the exact same pipeline as GIN-Gril and train it end-to-end using D-Gril and GIN-Mpsm and report the results. The classifier, $3$-layer MLP, is the same for all the experiments. Refer to Figure 3 for the pipeline. From Table 1, we can see that adding topological information after GIN has been trained can improve the performance in some cases and need not be beneficial in others. However, it is clear that adding topological information in an end-to-end framework appears to be beneficial for bio-activity prediction. D-Gril has comparable performance to Mpsm.

Further, we perform a series of experiments where we augment other popular molecular fingerprints such as ECFP and Morgan3 [43, 37] with the D-Gril framework. In these experiments, we compare the performance of the model with and without D-Gril augmentation. We report the results in Table 2. We see from the table that augmenting with D-Gril seems to, generally, increase the performance of the model. Fingerprints such as ECFP and Morgan3 can essentially represent an infinite number of different molecular features, including stereochemical information [43] but they are not effective in capturing global features of molecules such as size and shape [4]. Combining D-Gril with these fingerprints augments the model with topological information, yielding an improved performance.

D-Gril can be used more generally for filtration learning on graph datasets. We perform a series of experiments with benchmark graph datasets such as Mutag, Proteins, Dhfr, Cox2 [38] and compare with existing multiparameter persistence methods. Details about the datasets are given in Appendix B in [40]. We report the results in Table 3. For a valid comparison, we use a $3$-layer MLP as the classifier for all the multiparameter signatures. Hence, the numbers reported look different from the ones in [48], [6] where the authors consider XGBoost [9]. In fact, in [48], the authors show that XGBoost performs much better than a $3$-layer MLP classifier for Gril vectors on these datasets. We can see from the table that learning the bifiltration function seems to perform better than multiparameter persistence methods on popular choices of bifiltration functions on most datasets. We can also see that D-Gril performs better than Gril, supporting our argument for an end-to-end learning framework. We also see that D-Gril performs better than Mpsm. The training times for the two end-to-end learning methods, D-Gril and Mpsm are reported in Table 4. We can see that the training times for D-Gril are improved by about $40\%$ compared to the ones of Mpsm. We refer the reader to Figure 4 [40] for visualizations of bifiltration functions learnt by D-Gril.

Additionally, we performed experiments where we added a fusion layer to combine the representation power of both D-Gril and MPSM. We present the results in Table 5. We see from the table that combining the representations leads to a better overall performance, which includes a generally higher mean and a lower standard deviation. Thus, D-Gril can also be used with existing vectorization methods in a complementary manner to capture additional topological information.