Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new method to assess the quality of learned data representations. Recent works have proposed to evaluate data representations by looking at geometric and topological alignment of a set of evaluation representations E and a set of reference set of representations R. The key idea in this paper consists in improving approximation of the data manifold using Delaunay neighbourhood graphs (DCA). The suggested method is meant to work better than existing algorithms (GS, IPR, GeomCA) in heterogeneous settings with outliers and/or varying cluster densities.

The DCA algorithm then amounts to realizing the Delaunay graph on the set $R\cup E$ relying on a Monte-Carlo method proposed in Polianskii & Pokorny (2019), distilling components using the hierarchical clustering algorithm HDBSCAN (McInnes
et al., 2017), and finally adopting the metrics introduced in Poklukar et al. (2021). Options to deal with query point extensions and pruning of the Delaunay graphs are discussed. Evaluation of the proposed DCA method are analysed for contrastive learning models trained with NT-Xent contrastive loss, for generation capabilities of a StyleGAN and on the VGG16 supervised model pretrained on the ImageNet dataset.

 
main_review: Pros: (appearing in random order)

- Section 2 is well written and offers a clear picture of the limitations of existing methods (GS, IPR, GeomCA). In particular, the drawbacks deriving from either using $\epsilon$-proximity or $k$-NN approximations is well documented and rightly leads to finding better approximations to deal with outliers or varying density clusters.

- The structure of the DCA algorithm described in Section 3 is clear. The usage of Delaunay neighbourhood graphs seems a sound way of tackling the main limitations highlighted previously. The query point insertion and evaluations represents a consistent way of relying on the cell formalism to adapt to cases where data are being collected continuously. The proposed method to prune the graph based on the solid angles also seems geometrically clear.

- Efforts are made to test DCA on different scenarios in Section 4 to support the claims of better robustness and ability to adapt to cases with outliers.


Cons: (appearing in random order)

- While limitations of existing algorithms are thoroughly discussed, an intuitive picture of the potential of using Delaunay graphs is only briefly touched upon in Section 3, implicitly referring to the evaluation section to support the idea. Are there other ways of accounting for spatial information (neighbours)? What is particularly convenient in the Delaunay formalism?

- The novelty of the paper is not too strong. DCA amounts to linking existing methods together. While this in principle is not a bad thing, it seems that there isn't a significantly new idea somewhere in the paper about the different aspects of DCA being used, not even in the metric/component section.

- One of the major weaknesses is that the paper lacks analysis of complexity of the proposed method as opposed to the existing ones. This should be investigated to some extent. While the pruning method implicitly tries to address that, it is not clear the tradeoff between accuracy and complexity. In this regard, it is also not clear the role played by the number of sampled rays T, this should be somehow discussed.

- One of the main motivation for relying on DCA is avoiding difficult to tune hyperparameters. It seems though that in the distillation phase the clustering algorithm introduces a hyperparameter? Why is this more interpretable than, say, $\epsilon$ in the proximity graph construction? Similar questions for $\eta_{c}, \eta_{q}$.

- Section 4 is detailed but quite hard to access. The presentation here is not particularly good with results on the experiments that are very hard to understand with the exception - to some extent - of 4.1. 

- (Minor) It would be good to understand whether the tradeoff in complexity is worth it to account for outliers. How much of an issue is that in general when we have high-dimensional data compared to the complexity of the method?

- (Minor) Could the pruning method proposed in 3.2 be potentially damaging for outliers? Also you propose to remove the longest edges such that the sum of solid angles corresponding to the remaining ones is \emph{larger} than a predetermined parameter B. Am I missing something here or should it be smaller than some parameter?




summary_of_the_review: Despite my comments, I believe that the idea of relying on Delaunay neighbourhood graphs is worth investigating. The paper could improve on many aspects - presentation of the experiment section, intuition behind the proposed method, discussion on hyperparameters and most importantly complexity - however its core contributions are valid albeit with limited novelty.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper explores a new method (DCA) to evaluate the quality of learned data representations. The goal of this paper is to score representations from sets R (reference) and E (evaluation) using geometric and topological properties (like connected components) of the representations spaces. To put simply, if the local geometry and overall topology of both R and E are similar, then the representations are considered consistent and aligned (hence yielding overall high precision and recall). 

The authors primarily compare with 3 methods: GS, IPR and GCA (including a sparse variant) and argue that in scenarios of prevalent outliers and varying component densities of the representation spaces, such methods typically yield non-informative and suboptimal scores to compare representations. To that aid, the main method proposed in this paper proposes to alleviate these drawbacks and comprises of 3 steps: 1.) manifold estimation, 2.) component distillation 3.) component evaluation. 

The main contribution of this paper is the use of Delaunay graphs in step (1.) as opposed to eps-neighbor or knn graphs as is done in prior methods. The authors claim that this choice of graph construction along with the distillation procedure leads to identifying consistent and high quality connected components leading to more stable results. In addition the authors also propose a ‘out-of-sample’ variant of their method to handle individual queries.

The authors demonstrate their metric in three different setups: (A.) Contrastive Learning on the synthetic Chamzas et al. (2021) images dataset (B.) Style GAN (C.) Representation space of VGG16. Results, especially on (A.) show that the proposed evaluation metric is better suited with accurate recognitions of mode-collapse and mode discovery.

main_review: Pros. 
- The paper is very well written and well motivated (especially the parts that show difficulties with GCA and prior methods)
- I find the evaluation to be comprehensive, especially the analysis in Section 4.


Cons (minor)
- (novelty) Conceptually, it appears that this paper builds on the main ideas proposed in GCA (which is not necessarily a bad thing). However, the main idea of opting for a delaunay graph is an act of making an existing algorithm (GCA) more robust without fundamentally proposing a new metric. 

- The complexity of constructing the delaunay graph in high dimensions can be a computationally expensive affair.

summary_of_the_review: All in all, I perceive this to be a good paper. The authors do a good job of highlighting drawbacks of prior methods to compare representation spaces and proposing a solution that mitigates them. The use of Delaunay graphs in lieu of k-nn based or eps-proximity based methods is an interesting way to explore the geometry and topology of representation manifolds. The diversity and comprehensiveness of evaluation is also quite good.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents a novel approach to analyzing and comparing feature manifolds, e.g. from a learned embedding. The main idea is to construct a graph from a set of discrete samples to approximate the underlying, continuous manifold. The graph embedding can then be used to assess the similarity of a training and test set embedding, defined as their overlap and interconnectedness. Related existing methods construct such graphs via k-nearest neighbor or epsilon proximity graphs, whereas the proposed method uses Delaunay graphs.
main_review: Novelty and contribution:
- The proposed method has a clear motivation and an inbuilt superior robustness: knn or epsilon graphs are inconsistent for outliers and varying sampling densities, which DCA circumvents. The former also have an inbuilt hyperparameter (k, eps) which is difficult to choose in practice. 
- The main contribution of the method is demonstrating that such graphs are a useful approximation of features manifolds. The main technical challenge is combining the established Delaunay graph (Polianskii & Pokorny, 2019) extraction method with the clustering algorithm of (McInnes et al., 2017). 

Presentation:
- The overall presentation is adequate, but not always perfectly clear/easy to follow.
- Chapter 4 is overall too long and cluttered minor details. I suggest to move some of these details to the appendix and focus on highlight the core message of each experimental setting. This is especially crucial, since assessing the performance of the proposed method is generally not as simple as reading off a number. Advantages over prior methods need to be highlighted more clearly.
- The presentation would benefit from a brief, rigorous problem formulation paragraph at the beginning of Sec. 2. 
- To make the paper more self-contained, I would like to see more details on the Delaunay graph extraction in Sec 3., since it is a key technique. Most details are currently in the appendix.

Method and results:
- The motivation of the method is clear and it is technically sound. 
- I imagine that constructing the Delaunay graph for high-dimensional embeddings gets increasingly difficult. In practice, the number of Monte-Carlo sampled rays should increase with the number of dimensions and the graph becomes more connected (ergo the need for the pruning in Sec. 3.2). I would to see a more thorough discussion of this effect, the authors simply state that they usually choose T=1e4. How much does the sampling affect the results in higher dimensions? Error bars are only provided for the low-dim. embeddings in Sec. 4.1 and not for the high-dim. embeddings of StyleGAN and VGG16 (Sec. 4.2 and 4.3).
- The metrics P and R have a fairly coarse granularity and introduce additional hyperparameters eta_c, eta_q. What additional value do they provide, beyond c and q? Why not simply report the mean c and q values?
- Why do we need the distinction between DCA and q-DCA (in Sec. 3.1)? What is the difference of q-DCA and applying DCA with E={q}? 

Minor comments:
- It is not clear from the paragraph "Phase 2" alone, whether HDBSCAN has additional tunable parameters, please add a short clarification.
- Fig. 1 needs a legend for the blue and orange nodes and edges, as well as a more detailed explanation of why some of the edges are solid and others dashed.
- Figure captions are generally not sufficient to interpret the figures throughout the paper.
- In Fig. 6, labels and colors are small and hard to distinguish. Do q^SG and c overlap closely? Moreover, P and R should be compared in separate graphs.
- Similar issues with Fig. 9 and Fig. 10 of the appendix. 

=============================================================================================

Post discussion:
Reading the other reviews and the authors' responses did not raise any further, major questions on my end. The authors addressed most of my concerns in their response and evidently took the time to implement many of the reviewers' suggestions in the updated draft of the paper. I am therefore happy to increase my rating to "accept". I believe that the method has a strong motivation and the presented results are encouraging.
summary_of_the_review: The idea of using (pruned) Delaunay graphs to approximate continuous feature spaces is novel and technically sound. In my view, it has a lot of potential utility for analyzing high-dimensional embedding spaces, an important open problem. I am further convinced that this formulation is an improvement over related approaches such as IPR (Kynkaanniemi et al., 2019) or GeomCA  (Poklukar et al., 2021). On the other hand, several issues with the clarity of the presentation (especially in Sec. 4) obscure this main message. Overall, I am inclined to give the paper a more positive rating and hope that the authors can provide clarifications.
review_title: null

Meta-review: The paper proposes "Delaunay Component Analysis", a novel manifold learning technique. Reviewers raised several concerns regarding novelty, computational complexity of the method, and presentation. The authors provided a thorough rebuttal and engaged in discussion with the reviewers that addressed the concerns in a satisfactory manner. After the discussion, all the reviewers and AC recommend acceptance.
Decision: Accept (Poster)