Differentiable Euler Characteristic Transforms for Shape Classification

We thank the reviewer for the time reviewing our paper. Please find our comments below. We highly appreciate that the reviewer shares our enthusiasm for the novelty of this method.

One of the main technical contributions of this work is swapping a Dirac function to a sigmoid with a hyperparameter. It is unclear if this is a non-obvious contribution.

The computation with indicator functions is also novel. One usually does this with a loop, which is less scalable than our method. Moreover, we add differentiability with respect to the angles and with respect to the spatial coordinates, also novel and show our method is sometimes up to an order of magnitude faster than classical GNN methods. When comparing to other topological methods the speedup is even more dramatic.

The application of the ECT to learn directions and do point cloud approximation has not been attempted before, and we believe that this is both a novel and valuable contribution to the literature.

(purely out of interest) Would it be possible to combine the proposed description with methods like GCN, e.g. for dense prediction tasks (point cloud segmentation), where descriptor would be per-primitive (e.g. per point).

We very much appreciate the curiosity! The DECT, due to its differentiability, is very well suited to be used in a GNN/GCN aggregation layer. Together with node prediction, we would love to tackle point cloud segmentation in future work. We also believe that we can do this in a flexible and adaptive framework for many types of data.

How important is the differentiability aspect of DECT? E.g. one could potentially take a predefined set of parameters for (6), and use the output of that as a descriptor? Do you actually estimate the parameters of the transform, and does it add to the performance?

Theoretically yes. There is an upper bound with respect to dimension, the cardinality of the input data and minimum distance between points that guarantees injectivity. This theoretical bound is typically rather high and for point clouds and graphs in practice and it is typically prohibitive to require injectivity. The precise bound can be found in [1], Theorem 7.14.

Hence we use fewer directions and instead opt to learn which directions can discriminate between the classes.

To show that this indeed yields increased classification we ran an additional ablation on the differentiability aspect of DECT. Please see the general remarks above or section 5.1 in the manuscript.

It looks like the method can also be used when defining loss functions as a way to compare shapes, which is nice.

This is correct and we believe that we can explore this further in future work, hoping to use it for point cloud approximation / sparse approximation and segmentation.

We thank the reviewer for their time reviewing our paper and for appreciating the utility of DECT for shape classification. Please find our comments below.

Although ECT is theoretically injective, it happens only when the number of directions is sufficient. For example, for point cloud classification it could be the case that the number of directions is required to be no less than the cardinality of the point set, for ECT to be injective. This restricts the expressivity, especially for the application on point clouds, and explains why the results on point cloud classification is relatively weaker than graph classification.

This is indeed true. Guaranteed injectivity depends on the cardinality of the set and dimension see [1]. For classification tasks, only the characteristics of the data distribution are needed, hence we can do with a rather coarse approximation of the ECT and still get useful results. We believe that the point cloud results can also be partially explained by the fact that we eschew an approximation in terms of additional combinatorial complexes. Nevertheless, further research into how to get more expressive representations of the ECT in the context of machine learning are still very much needed. We would also like to stress that this is the first application of the ECT on more complex datasets, something not attempted yet (except for MNIST and some binary classification tasks) in the literature.

The literature usually applies a coarse dimensionality reduction such as UMAP to the ECT to get a representation for an SVM. Finding better suited classification representations is still an open question. Such a pipeline does not exploit the fact that similar directions share information, and hence organizing them in a way that allows this spatial information in the representation can be exploited by, for instance, a CNN architecture, leads to better performance. The closest analogy is flattening an image to a single vector, whereby one loses the spatial information that a CNN uses to get its performance.

To apply the method to graph learning, it requires the graph to have spatial coordinates.

We believe that this can be overcome: if data features on the vertices are not present, one can construct them in terms of filtrations, such as node degree or curvature information. Our method will work for these types of metrics as well. Moreover, filtrations can be learned in a task-specific fashion, thus posing no strong restriction of the scope of our work. We will clarify this in the revision.

Ablations on differentiability and number of directions.

We agree with the reviewer that an ablation on the number of directions would be a valuable addition to the paper.

We provide an ablation study on the number of directions. We find that rather few (compared to theoretical injectivity guarantees) provide significant expressivity.

[1] 1805.09782.pdf (arxiv.org)

We thank reviewer v8eE for the review and very much appreciate that the reviewer also finds the core ideas of our work useful!

Please find more detailed responses to your queries below:

Be more direct in explaining what features of data are simply not achievable using standard feature descriptors and how the proposed contributions alleviate it.

• We believe that our method offers substantial advantages over existing methods along the dimensions of speed, scalability, expressivity, permutation invariance, and flexibility.

• In terms of speed, we are almost an order of magnitude faster than some classical GNN methods. This advantage goes up significantly when comparing to other topological methods. In our framework, training cycles that take regular methods—in particular methods based on message passing—days, take minutes in our framework (and we made sure to use the most optimized implementations of our baseline comparison partners).

• In terms of scalability, we are the first topological method that can make use of hardware acceleration and (although not explicitly done in this paper) can also be computed using distributed computing.

• In terms of expressivity, our method can also be used in traditional classification tasks and exhibits performance that is on a par with other methods. Notably, we achieve this using a comparatively simple architecture.
  Moreover, our method is permutation invariant and can be easily used for sets of arbitrary sizes without requiring additional architectural changes. Finally, in terms of flexibility, to our knowledge there is no framework that exhibits this level of versatility. Our method can deal with any type of simplicial complex at the same time without changing anything. For instance, DeepSets still assumes a fixed cardinality of the input point clouds. GNNs cannot work directly with point clouds. Neither can DeepSets work directly on graphs, or simplicial complexes. Our method works on all data types without changing a single line of code.

• Representation: Moreover, it outputs a fixed size representation of your data! Hence any standard method can be used afterwards. We display this by considering one of the simplest neural network architectures available and still having decent performance.

• Mathematical guarantees: Viewed as a feature layer, it comes backed up by strong mathematical guarantees. Injectivity being one. Moreover, our method can also be used for aggregation layer in a Graph Neural Network architecture. We have not explored this in this paper but plan on doing so in future work.

Elaborate more concretely on the multi-scale aspect of the descriptor.

For a multi-scale approach, one would have to define a different type of filtration function, in particular an alpha complex would much better capture this type of information. Our method as of now captures spatial information and directional information.

How do you take inner products along given directions for higher dimensional simplices like the edge and face on a mesh?

Functions on simplicial complexes are defined through an extension principle. One defines a “normal” function on the vertices (in our case the inner product of the vertex coordinates and the direction) and extend it to higher simplices. In our case we use the maximum extension, i.e. a higher-order simplex is assigned the maximum of its vertices. For example, to compute the value of an edge, we take the maximum of the vertex values it is spanned by.

The ECT and DECT are a set of descriptors lying on the unit hypersphere, and in higher dimensions working with directions sampled on the unit hypersphere becomes computationally very demanding. How can this be alleviated in the current framework?

This is indeed one of the core principles and advantages of our method as we do not need to sample uniformly—we are learning directions instead. Since we take inner products with the direction vectors and the coordinates of our n-sphere, computations do not get much more involved and this property is very much in contrast to other topological methods, where the dimensions and size and dimension become prohibitive factors rather quickly. In most cases one computes an alpha or Vietoris-Rips complex and this captures the multi-scales aspect of point clouds in a natural fashion. Comparison with additional topological baselines.

We will discuss the suggested references in more detail, but they deal with different use cases than ours, namely unsupervised representation learning (in particular the ‘Topological Autoencoders’ works and follow-ups). While we believe that the ECT has the potential to be used as a loss term in unsupervised data analysis as well, we plan on postponing such an analysis for future work and believe that additional experiments in that direction would be out of scope. Instead, we restrict ourselves to graph classification and shape analysis.

I apologize to the authors. I previously posted the review to another paper. Now it should be ok!

We thank the reviewer for their helpful comments and positive remarks, especially for recognizing the potential of our method, which we indeed believe to permit copious follow-up work. Concerning the novelty, all computational aspects and the description of the ECT are in fact novel as well and deviate from the existing literature. The key changes to existing literature are (1) speed, (2) scalability, and (3) differentiability. Please also check out the resource [1] for additional details. We are more than happy to answer any additional questions you might have!

Please find below a detailed set of responses to the concerns.

Architecture description: In “Integration into deep NN” it is written that MLP + global pooling is used to achieve rotation permutation invariance, but the architecture is then described as a CNN over a 16x16 image. Break Permutation invariance?

We recognize that additional clarity is required and will rewrite the paper accordingly. We evaluate two types of architectures in our paper. The first is indeed done by considering the ECT as an image of size {directions} x {discretization steps} and use a CNN or MLP architecture to classify the dataset. The second type of architecture embeds the Euler curve in each direction into a higher-dimensional feature space. We subsequently use the embedding for classification. This means we are not only invariant with respect to permutations of the vertices, but also equivariant with respect to permutations in the directions. We will clarify this in the revision.

What is the dependence on the sampling density for point clouds etc.

An exact upper bound for injectivity is given in [2] Theorem 7.14 and depends on the dimension and cardinality of the set. Hence, we believe that our sparse method is rather powerful.

In the case of point clouds, how is the graph built? Do you consider all disconnected points?

We count the number of points above a hyperplane in a direction theta and let this hyperplane go from $-\infty$ to $\infty$. We do indeed consider all disconnected points as we scale the point cloud to fit in a unit sphere. In the case of point clouds, we do not construct a simplicial complex, we only count the points above hyperplanes in each direction.

Eq 1 is not clear: what is k in the exponent?

The reviewer caught a typo, it is corrected—thanks! The Euler Characteristic is computed as the alternating sum of the number of simplices in dimension n.

Notation in eq 3 and 4 is not straightforward, is the second row the actual function definition? What is $x$?

We will clarify this in the document, the $x$ is the spatial coordinate of the vertex and $\xi$ is the direction, viewed as a point on the n-sphere.

I find eq 5 difficult to read, especially the definition of the indicator function 1. Also, what is $\sigma_k$?

We will add some extra clarification in the manuscript. A k-dimensional simplex is denoted by $\sigma_k$ and $h_\xi(\sigma_k)$ denotes the height of the k-simplex in the direction $\xi$. This new notation is hopefully clearer.

Table 3 reports 2 times ECT-CNN.

That is a correct observation. In the top row we use a low amount of parameters (4k, see the column next to it) for comparisons with other methods. In the row below it we use a higher number of parameters to see how well the model behaves. Therefore, we have also not considered in the highlighting. We will stress this in the manuscript.

Additional resources:

• [1] 2307.13940.pdf (arxiv.org)
• [2] 1805.09782.pdf (arxiv.org)