DELAUNAY COMPONENT ANALYSIS FOR EVALUATION OF DATA REPRESENTATIONS
Year: 2022

Abstract:
Advanced representation learning techniques require reliable and general evaluation methods. Recently, several algorithms based on the common idea of geometric and topological analysis of a manifold approximated from the learned data representations have been proposed. In this work, we introduce Delaunay Component Analysis (DCA) – an evaluation algorithm which approximates the data manifold using a more suitable neighbourhood graph called Delaunay graph. This provides a reliable manifold estimation even for challenging geometric arrangements of representations such as clusters with varying shape and density as well as outliers, which is where existing methods often fail. Furthermore, we exploit the nature of Delaunay graphs and introduce a framework for assessing the quality of individual novel data representations. We experimentally validate the proposed DCA method on representations obtained from neural networks trained with contrastive objective, supervised and generative models, and demonstrate various use cases of our extended single point evaluation framework.

text: 1 INTRODUCTION
Quality evaluation of learned data representations is gaining attention in the machine learning community due to the booming development of representation learning techniques. One common approach is to assess representation quality based on their performance on a pre-designed downstream task (Bevilacqua et al., 2021; Li et al., 2020). Typically, a classification problem is used to evaluate either the ability of a model to recover labels of raw inputs, or the transferability of their representations to other domains, as done in state-of-the-art unsupervised representation learning methods (Chen et al., 2020b; Ermolov et al., 2021). However, in many scenarios such straightforward downstream classification task cannot be defined, for instance, because it does not represent the nature of the application or due to the scarcity of labeled data as often occurs in robotics (Chamzas et al., 2021; Lippi et al., 2020). In these scenarios, representations are commonly evaluated on hand-crafted downstream tasks, e.g., specific robotics tasks. However, these are time consuming to design, and potentially also bias evaluation procedures and consequentially hinder generalization of representations across different tasks.
Recently, more general evaluation methods such as Geometry Score (GS) (Khrulkov & Oseledets, 2018), Improved Precision and Recall (IPR) (Kynkäänniemi et al.,
2019) and Geometric Component Analysis (GeomCA) (Poklukar et al., 2021) have been proposed.
∗Correspondence to Petra Poklukar, poklukar@kth.se.
These methods analyze global geometric and topological properties of representation spaces instead of relying on specific pre-designed downstream tasks. These works assume that a set of evaluation representations E is of high quality if it closely mimics the structure of the true data manifold captured by a reference set of representationsR. This reasoning implies thatR andE must have similar geometric and topological properties, such as connected components, their number and size, which are extracted from various approximations of the data manifolds corresponding to R and E. For example, GS and GeomCA estimate the manifolds using simplicial complexes and proximity graphs, respectively, while IPR leverages a k-nearest neighbour (kNN) based approximation. However, as we discuss in Section 2, neither of these approaches provides a reliable manifold estimate in complex arrangements of R and E, for instance, when points form clusters of varying shape and density as well as in the presence of outliers. Moreover, the informativeness of the scores introduced by these methods is limited.
In this work, we address the impediments of evaluation of learned representations arising from poor manifold approximations by relying on a more natural estimate using Delaunay graphs. As seen in Figure 1, edges (solid lines) in a Delaunay graph connect spacial neighbours and thus vary in length. In this way, they naturally capture local changes in the density of the representation space and thus more reliably detect outliers, all without depending on hyperparameters. We propose an evaluation framework called Delaunay Component Analysis (DCA) which builds the Delaunay graph on the union R ∪ E, extracts its connected components, and applies existing geometric evaluation scores to analyze them. We experimentally validate DCA on a variety of setups by evaluating contrastive representations (Section 4.1), generative models (Section 4.2) and supervised models (Section 4.3).
Furthermore, we exploit the natural neighbourhood structure of Delaunay graphs to evaluate a single query representation. This is crucial in applications with continuous stream of data, for example, in interactions of an intelligent agent with the environment or in the assessment of the visual quality of individual images generated by a generative model as also explored by Kynkäänniemi et al. (2019). In these cases, existing representation spaces need to be updated either by embedding novel query points or distinguishing them from previously seen ones. In Delaunay graphs, this translates to analyzing newly added edges to the given query point. We demonstrate various possible analyses in Section 4 using aforementioned experimental setups.

heading: 2 STATE-OF-THE-ART METHODS AND THEIR LIMITATIONS
text: We review the state-of-the-art methods for evaluation of learned data representations, namely GS (Khrulkov & Oseledets, 2018), IPR (Kynkäänniemi et al., 2019) and GeomCA (Poklukar et al., 2021), which compare topological and geometrical properties of an evaluation set E with a reference set R representing the true underlying data manifold. We discuss differences in their manifold approximations, visualized in Figure 2, as well as informativeness of their scores.
The pioneering method in this area, GS, constructs witness simplicial complexes on randomly sampled subsets of R and E (panel (a)), and compares their connected components using tools of computational topology (Zomorodian & Carlsson, 2004). The result is an average over several iterations summarized either in the form of histograms, which are cumbersome for quantitative comparison, or as a single un-normalized score, which is in many cases not sufficiently informative. Moreover, GS
depends on four hyperparameters, which can be difficult to understand and tuned by practitioners unfamiliar with computational topology.
In contrast, IPR obtains manifold approximations by enlarging each point in R (or E) with a hypersphere of radius equal to the distance to its kNN in that set (panel (b)). It defines two scores: precision PI which counts the number of E points contained on the approximated R manifold, and vice versa for recall RI . While the method depends only on one hyperparameter k, it is highly affected by outliers which induce overly large spheres and dense areas of the space which yield too conservative coverage as visualized in panel (b). Moreover, it is the only method expecting R and E to be of equal size, thus, often requiring subsampling of one of them. Both GS and IPR have been primarily developed to assess generative adversarial networks (GANs) (Goodfellow et al., 2014).
The most recent and generally applicable method, GeomCA, extends GS and IPR in two ways: i) it provides functionality to analyze individual connected components of the approximated manifold, hence enabling one to examine local areas of representation spaces where inconsistencies arise, and ii) characterizes the captured geometry in four global scores: precisionPG and recallRG, which are similar to IPR, as well as network consistency cG and network quality qG, which are also the basis of the GeomCA local evaluation scores (see Section 3 for recap). GeomCA estimates the manifolds using ε-proximity graphs where the hyperparameter ε defines the maximum distance between two points connected by an edge and is estimated from distances among points in R. However, in practice, representations often form clusters of different shape and density which makes it impossible to select a single value of ε that adequately captures such variations (see examples in panel (c)).
Moreover, GeomCA reduces the number of points by performing geometric sparsification that extracts a subset of points from each of R and E being pairwise at least distance δ apart, where δ is estimated from ε. While the authors argue that this step does not affect their scores as it preserves the topology, we show that it nevertheless can bias the manifold estimation ofR and E. An example is illustrated in the bottom component of panels (c) and (d), where the sparsification removes a large portion of the denseE subset and artificially increases the precision. We demonstrate the occurrence of this scenario in the evaluation of a GAN model in Section 4.2.
Our DCA framework utilizes Delaunay graphs (panel (e)) to address the discussed limitations in manifold approximations of the existing methods, and employs evaluation scores introduced by Poklukar et al. (2021) to maximize its informativeness. Moreover, it extends the existing methods by additionally providing a general framework for quality evaluation of single query representations.

heading: 3 METHOD
text: We propose Delaunay Component Analysis (DCA) algorithm for evaluation of data representations consisting of three parts: i) manifold approximation which approximates the Delaunay graph on the given sets of representations, ii) component distillation which distills the graph into connected components, and lastly iii) component evaluation which outputs the evaluation scores summarizing the geometry of the data. We provide an outline of our DCA framework in Algorithm 1 found in Appendix A. Moreover, by exploiting the nature of Delaunay graphs, DCA can be efficiently implemented (Section 3.2) and extended for evaluation of individual representations (Section 3.1).
Phase 1: Manifold approximation As mentioned in Section 1, the unique property of Delaunay graphs is the definition of neighbouring points that are connected by an edge. For example, in an ε-graph, two points are adjacent if they are at most ε distance apart. In a kNN graph, a point is connected to all points that are closer than the k-th smallest distance of that point to any other. In contrast, in a Delaunay graph (Figure 1), a point is adjacent to any point that is its spatial neighbour, regardless of the actual distance between them or the number of its other spatial neighbours. We refer to such spatial neighbours as natural neighbours of a point and rigorously define them through Voronoi cells (depicted as dashed lines in Figure 1) in the following.
Definition 3.1 Given a set W ⊂ RN we define the Voronoi cell Cell(z) associated to a point z ∈ W as the set of points in RN for which z is the closest among W : Cell(z) ={ x ∈ RN ∣∣ ∥x− z∥ ≤ ∥x− zi∥∀zi ∈W}. The Delaunay graph GD(W ) = (V, E) built on the set V = W is then defined by connecting points whose Voronoi cells intersect, i.e., E = {(zi, zj) ∈W ×W | Cell(zi) ∩ Cell(zj) ̸= ∅, zi ̸= zj}.
We consider a reference set R = {zi}nRi=1 ⊂ RN and evaluation set E = {zi} nE i=1 ⊂ RN of data representations with R ̸= E, and approximate the Delaunay graph GD = GD(R ∪ E). By Definition 3.1, edges in GD correspond to points on the boundary of Voronoi cells which are obtained using Monte Carlo based sampling algorithm presented by Polianskii & Pokorny (2019) (see Appendix A for further details). The process, visualized in Figure 3, is based on sampling rays originating from each z ∈ R ∪ E and finding their intersection with the boundary of its Voronoi cell Cell(z). This allows to reconstruct GD via subgraph approximation, and can be additionally exploited for memory optimizations which we present in Section 3.2. Due to the sampling, the number of found edges directly depends on the number T of rays sampled from each z. However, as we show in ablation studies in Appendix B.1 and B.2, our evaluation framework is stable with respect to the variations in T . Next, we discuss the distillation of GD into connected components. Phase 2: Component distillation Since edges in GD are obtained among natural neighbours, GD consists of a single connected component uniting regions of points formed in different densities or shape. These can be distinguished by removing large edges (depicted with transparent edges in Figure 1), or equivalently, by finding clusters of points having similar natural neighbours (depicted with opaque edges in Figure 1).
We distill GD into connected components by adapting the stateof-the-art hierarchical clustering algorithm HDBSCAN (McInnes et al., 2017) summarized in Appendix A. We apply the part of HDBSCAN that extracts connected components {Gi} from the minimum spanning tree1 MST(GD). We emphasise that applying HDBSCAN directly on MST(GD) efficiently bypasses the calculation of a complete pairwise distance matrix2 of size nR + nE which becomes a computational burden for large R and E sets. Such calculation is an integral part of HDBSCAN performed to reduce the sensitivity of the method to noise or outliers which can be omitted in case of Delaunay graphs due their natural neighbourhood structure (see Appendix A for further details). In this way, our modification of HDBSCAN inherits only one of its original hyperparameters, the minimum cluster size mcs parameter, determining the minimum number of points needed for a set of points to form a cluster. This parameter is intuitive to tune and can be flexibly adjusted depending on the nature of the application. In our ablation studies reported in
Appendix B.1 and B.2, we show that DCA is stable with respect to variations in mcs. At the end of this phase, we obtain the distilled Delaunay graph GDD = ⊔ i Gi of GD which we denote simply by G when no confusion arises. Lastly, we analyze the components of G as summarized below. Phase 3: Component evaluation We analyze the connected components Gi of G using local and global evaluation scores introduced by Poklukar et al. (2021) which we recap below. Following their notation, we denote by |G|V and |G|E the cardinalities of the vertex and edge sets of a graph G = (V, E), respectively, and by GQ = (V|Q, E|Q×Q) ⊂ G its restriction to a set Q ⊂ V . We start by introducing the two local scores: component consistency and quality. Intuitively, a component Gi attains high consistency if it is equally represented by points from R and E, i.e., if |GRi |V ≈ |GEi |V , where GRi ,GEi denote the restrictions of Gi to R and E. Similarly, Gi obtains a high quality score if points from R and E are also well mixed which is measured in terms of edges connecting R and E, i.e., the points are geometrically well aligned if the number of homogeneous edges among points in each of the sets, |GRi |E and |GEi |E , is small compared to the number of heterogeneous edges connecting representations from R and E. This is rigorously defined as follows:
Definition 3.2 (Local Evaluation Scores, Poklukar et al. (2021)) Consistency c and quality q of a component Gi ⊂ G are defined as the ratios
c(Gi) = 1− | |GRi |V − |GEi |V |
|Gi|V and q(Gi) =
{ 1− (|G R i |E+|G E i |E)
|Gi|E if |Gi|E ≥ 1, 0 otherwise,
(1)
1Minimum spanning tree of a graph is a tree minimizing the total edge length and connecting all vertices. 2The matrix represents mutual reachability distance calculated among each pair of points with respect to the
minimum samples parameter.
respectively. Moreover, Gi is called consistent if c(Gi) > ηc and of high-quality if q(Gi) > ηq for given thresholds ηc, ηq ∈ [0, 1) ⊂ R. A consistent component of high-quality as determined by ηc, ηq is called a fundamental component. The union of fundamental components is denoted by F = F(G, ηc, ηq) and indexed by the subscript f , i.e., we write Gf ∈ F .
The thresholds ηc, ηq are designed to enable a flexible definition of fundamental components and are assumed to be set depending on the application and available prior knowledge. By examining the proportion of R and E points contained in F , we obtain the first two global scores: precision and recall, respectively. Two more global scores, network consistency and network quality, used to measure global imbalances and misalignment betweenR andE, can be simply derived by extending Definition 3.2 to the entire graph G. In summary, we consider the following global evaluation scores:
Definition 3.3 (Global Evaluation Scores, Poklukar et al. (2021)) We define network consistency c(G) and network quality q(G) as in Definition 3.2, as well as precision P and recallR as
P = |F E |V |GE |V and R = |F R|V |GR|V , (2)
respectively, where FR,FE denote the restrictions of F = F(G, ηc, ηq) to the sets R and E.

heading: 3.1 EXTENSION: QUERY POINT INSERTION AND EVALUATION
text: A practical evaluation framework should not only provide a functionality to analyse sets of representations but also to assess the quality of individual points with respect to R, which is desirable in any application where data is being collected continuously. In case of Delaunay graphs, evaluating the quality of a query point q ⊂ RN\R is equivalent to studying its insertion into the distilled Delaunay graph GDD(R). Formally, we consider the neighbourhood N(q) of q in the distilled Delaunay graph GDD(R∪{q}) defined as the subgraph of GD(R∪{q}) induced by all vertices adjacent to q including q and intersected with GDD(R). To find the edges of N(q), it suffices to perform the sampling process described in Phase 1 only within the Voronoi cell Cell(q) of GD. In fact, this process can be efficiently performed for a set Q of query points independently from each other and has equal computational complexity as the construction of GD(R) provided that |R| and |Q| are comparable. We refer to this extension as query (point) Delaunay Component Analysis, or in short, q-DCA algorithm.
The obtained neighbourhood graph N(q) = (VN(q), EN(q)) can be analyzed in numerous ways depending on the application. In this work, we experiment with the length and the number of the inserted edges in three ways: i) by extracting the point inR closest to q, ii) by additionally extracting the length of that edge, or iii) by examining the number of inserted edges to each fundamental component as well as the length of the shortest one. We provide a summary of the three variants in Algorithm 2 in Appendix A and experimentally validate them in Section 4.

heading: 3.2 DELAUNAY GRAPH REDUCTION VIA SPHERE COVERAGE
text: In high dimensions, the Delaunay graph GD can have a large number of edges. In this section, we propose an optional procedure for removing the least significant edges and thus reducing the overall memory consumption.
During the construction of GD, the probability of sampling an edge (zi, zj) ∈ E(GD) directly depends on the angular size of Cell(zi) ∩ Cell(zj) viewed from one of the points3. It is visualized in Figure 3 and formally defined as the solid angle βij ∈ (0, 1] at zi of a cone with vertex zi and base Cell(zi) ∩ Cell(zj) normalized by the volume of the unit hypersphere. It is approximated by the ratio of all rays sampled from zi that provided the corresponding edge (zi, zj) using the algorithm of Polianskii & Pokorny (2019). Intuitively, low βij values correspond to edges that are unstable (depicted with thinner lines in Figure 1) because they may disappear with small perturbations of data. We therefore propose to remove the longest edges (zi, zj) connecting zi such that the sum∑
j βij of solid angles corresponding to the remaining ones is larger than a predetermined parameter B ∈ [0, 1). We refer to B as sphere coverage and demonstrate its usefulness on the large scale experiment in Section 4.2 and perform an ablation study in Appendix B.1.
3The authors of Rushdi et al. (2017) call this significance.

heading: 3.3 COMPLEXITY ANALYSIS
text: The computational complexity of the Delaunay graph approximation performed in Phase 1 grows polynomially with the dimensionality of representations N . Given that the number of points |R| + |E| is at least linear corresponding to their dimensionality N , i.e. |R| + |E| = Ω(N), we utilize the probabilistic method for the construction of the graph proposed by Polianskii & Pokorny (2019) that yields the total complexity O((|R|+ |E|)2 · (N + T )). The complexity for q-DCA is obtained by substituting |E| with |Q| for a set of query points Q. Moreover, the asymptotics of the modified HDBSCAN clustering algorithm utilized in Phase 2 rely on the graph obtained in Phase 1, which again does not directly depend on the dimensionality N and is at most quadratic of the number of points, i.e. O((|R| + |E|)2). Real computation times of Phase 1 and Phase 2 are comparable (see Appendix B.1, Table 6), partially due to high GPU parallelization of Phase 1. We refer the reader to (Polianskii & Pokorny, 2019), (Campello et al., 2015) and (McInnes & Healy, 2017) for details.

heading: 4 EXPERIMENTS
text: Our implementation of the DCA algorithm is based on the C++/OpenCL implementation of Delaunay graph approximation provided by Polianskii & Pokorny (2019) as well as on Python libraries HDBSCAN (McInnes et al., 2017) and Networkx (Hagberg et al., 2008). The code is available on Github4. We considered a similar experimental setup as in (Poklukar et al., 2021) and analyzed (i) representation space of a contrastive learning model trained with NT-Xent contrastive loss (Chen et al., 2020a), (ii) generation capabilities of a StyleGAN trained on the FFHQ dataset (Karras et al., 2019), and (iii) representation space of the widely used VGG16 supervised model (Simonyan & Zisserman, 2015) pretrained on the ImageNet dataset (Deng et al., 2009).
Using each of the above scenarios, we demonstrate the stability and informativeness of DCA and showcase three variants of the q-DCA extension. We compare the obtained results to the discussed evaluation methods: GeomCA used with geometric sparsification (denoted by PsG,RsG, csG, qsG) and without it (denoted by PG,RG, cG, qG), IPR (denoted by PI ,RI ) and GS. We refer to the evaluation scores obtained using the Delaunay graph as DCA scores. We report the hyperparameters choices of the respective methods in Appendix B.

heading: 4.1 CONTRASTIVE REPRESENTATIONS
text: A successfully trained contrastive learner provides a controlled setup with known structure of learned representations, thus enabling us to perform a series of experiments validating the correctness and reliability of our DCA method. In this section, we demonstrate the superior performance of DCA compared to the benchmark methods in various complex geometric arrangements of R and E. Additional experiments on this experimental setup can be found in Appendix B.1, where we i) show how q-DCA can be applied to investigate the robustness of the model’s representation space to novel images, ii) demonstrate that DCA successfully recognizes mode collapse and mode discovery situations by repeating the mode truncation experiment performed by Poklukar et al. (2021), and lastly iii) perform a thorough ablation study on hyperparameters of DCA.
Varying component density To demonstrate reliability of DCA in various geometric arrangements of points, we repeatedly sampled 10 times 3 classes ci and discarded a fraction of p ∈ {0.5, 0.75, 0.999} points in R with that label. In this way, R contained smaller and sparser components for p = 0.5, 0.75, while p = 0.999 mimics a scenario with outliers. Since such pruning
4https://github.com/petrapoklukar/DCA
necessarily removed 3 fundamental components due to ηc = 0.75, we expected to observe the average precision P ≈ 4/7 regardless the value of p. On the contrary, increasing p corresponds to majority of R being contained in the remaining 4 fundamental components, thusR should approach 1 (see Appendix B.1 for precise calculation of the optimal values). Since by design, |R| < |E|, we performed downsampling of E in case of IPR.
Figure 5 shows the mean and standard deviation (std) of the obtained DCA, GeomCA and IPR scores together with the optimal values (solid vertical lines). For DCA, we observe the correct average P ≈ 0.57 for all p as well as increasing R with increasing p. Moreover, we observed the scores to have a low std indicating the stability of our method. For p = 0.5, the sparsification in GeomCA led to an artificial increase in scores, while PI ,RI ≈ 0.7 did not detect the differences in the sets potentially due to the additional downsampling. While the average GeomCA scores obtained without sparsification are more aligned with DCA, they exhibit large std due to the unstable ε estimation. Similar conclusions hold for p = 0.75 and p = 0.999, where both GeomCA and sparse GeomCA scores are lower than DCA due to a largely disconnected graph resulting from a small ε. The IPR was again not robust for p = 0.75, while in p = 0.999, PI exhibited larger mean and std compared to other scores indicating the erroneous merges originating from large radii of the outliers. Lastly, downsampling of E negatively affected RI resulting in a low score. In Appendix B.1, we also report the results for GS which we found to be inadequaltely informative.

heading: 4.2 EVALUATION OF A STYLEGAN
text: Next, we applied our proposed DCA and q-DCA algorithms to assess the quality of both data distribution learned by a StyleGAN model trained on the FFHQ dataset and individual generated images.
Generation capacity To evaluate generation capabilities of StyleGAN, we repeated the truncation experiment performed in (Kynkäänniemi et al., 2019; Poklukar et al., 2021) where during testing latent vectors were sampled from a normal distribution truncated with a parameter ψ affecting the perceptual quality and variation of the generated images. A lower ψ results in improved quality of individual images but at the cost of reducing the overall generation variety. For each truncation ψ ∈ {0.0, 0.1, . . . , 1.0}, we randomly sampled 50000 training images and generated 50000 images, and encoded them into a VGG16 model pretrained on ImageNet. The corresponding 4096- dimensional representations composed the sets R and E, respectively. For low values of ψ, we expect to obtain high precision values as the high-quality generated images should be embedded close to the (fraction of) training images but low recall values as the former poorly cover the diversity of the training images. Due to the large number of considered representations, we reduced the size of the approximated Delaunay graph GD(R ∪ E) by setting the sphere coverage parameter B, introduced in Section 3.2, to 0.7.
Figure 6 shows the obtained DCA scores (solid lines) together with GeomCA, IPR and GS scores (dashed lines). All methods correctly reflect the truncation level ψ apart from GS at ψ = 0 and DCA at ψ = 0.5, which we discuss in detail below. Firstly, DCA scores exhibit larger absolute values of P,R compared to the benchmarks. Even though this is expected because Delaunay edges naturally connect more points, we additionally investigated the average length of homogeneous edges among R and among E points to verify the correctness of the obtained scores. In Table 7, we observe that the average length homogeneous edges among E increases with increasing ψ and resembles the average length homogeneous edges among R for ψ = 1.0. This indicates that the StyleGAN model
was successfully trained, which is on par with the high-quality images reported by Karras et al. (2019). However, both GeomCA and IPR methods result in more conservative values which are especially visible for recall. For GeomCA, this is because ε is estimated from R resulting in fewer and smaller components (also due to the sparsification), which in turn yields low PsG,RsG. For IPR, it is because the radii of spheres around E points yield a conservative coverage as discussed in Section 2. Therefore, this analysis demonstrates that DCA scores in this case provide more accurate description of the geometry.
concatenated to the R cluster, while a single score of GS is too uninformative. In Appendix B.2, we provide a detailed investigation where we both analyzed the lengths of edges in MST(GD) and applied DCA to R and E sets obtained at different truncation levels. The obtained results verify the irregular formation of the points and highlight ineffectiveness of existing methods in such scenarios.
Lastly, note that network consistency c and quality q values are reversed in DCA compared to GeomCA as we consider all 50000 points. Therefore, we trivially obtained c equal to 1 that is perfectly aligned with qsG score due to the geometric sparsification (see Appendix B). On contrary, q increased with ψ except for the observed irregularity at ψ = 0.5.
Quality of individual generated images A challenging problem in generative modelling is to assess the quality of individual generated samples, which is possible with our q-DCA extension by analyzing the shortest edges of their corresponding representations added to an existing G. To demonstrate this, we again created R from representations of randomly sampled 50000 training images, approximated G = GDD(R) and analyzed newly added edges EN(q) for each query representation q corresponding to 1000 generated images. In Figure 7, we visualize examples of generated images with shortest (left) and largest (right) inserted edges. We observe that the length of the inserted edges correlates well with the visual quality of generated images, where generated images close to the training ones display clear faces (left) and those further away display distorted ones (right). We compared our results with the realism score (RS) introduced by Kynkäänniemi et al. (2019) and sorted the generated images both by increasing Delaunay edge length and decreasing RS and computed the intersection of first and last 100 samples. We obtained that 51% and 83% of images are commonly marked as high and low quality, respectively, by both methods. Following the discussion in Section 2, we emphasize that RS is highly affected both by outliers and uneven distribution of points in R, which the authors address by discarding half of the hyperspheres with the largest radii. Such adjustments are not robust to various arrangements or small perturbations of points, and are not needed in case of Delaunay graphs.
Additional ablation study on DCA hyperparameters We use the high dimensionality of representations in this experiment to perform an ablation study on the hyperparameters of our proposed DCA method. Similarly as for the experimental setup in Section 4.1, we investigated the stability of our scores with respect to variations in i) the number of sampled rays T in the approximation of the
Delaunay graph GD (Phase 1), ii) the minimum cluster size mcs parameter used in the distillation of GD (Phase 2) and lastly, iii) the optional sphere coverage parameter B that can be used to reduce the number of edges in the distilled Delaunay graph GDD. The results, shown in Table 8, show that our DCA framework is stable with respect to the choice of hyperparameters even in higher dimensional representation spaces. We refer the reader to Appendix B.2 for further details.

heading: 4.3 REPRESENTATION SPACE OF VGG16
text: Lastly, we applied q-DCA to analyze whether the structure of the representation space of a VGG16 classification model pretrained on ImageNet reflects the human labeling. By repeating the experiment investigating separability of classes performed by Poklukar et al. (2021), we reached a similar conclusion that VGG16 moderately separates semantic content (see Appendix B.3). However, we further investigated whether the limited class separation originates from inadequacies of the model or human labeling inconsistencies. To distinguish between the two scenarios, we applied q-DCA to obtain labels of query points and compared them to their true labels.
examples can be found in Appendix B.3, where we show similar cases using images corresponding to randomly chosen classes also considered by Poklukar et al. (2021). The results suggest that a more reliable labeling could result from a combination of human input and the ability of neural networks to recognize semantic similarity in images.

heading: 5 CONCLUSION
text: We presented Delaunay Component Analysis (DCA) framework for evaluation of learned data representations which compares the structure of two sets of representationsR and E using the introduced distilled Delaunay graphs. We showed that distilled Delaunay graphs provide a reliable approximation in various complex geometric arrangements of R and E, thus resulting in a stable output of our DCA scores. Moreover, we introduced the extended q-DCA framework for individual query representations evaluation. We experimentally demonstrated the applicability and flexibility of q-DCA on three different scenarios.

heading: ACKNOWLEDGEMENTS
text: This work has been supported by the Knut and Alice Wallenberg Foundation, Swedish Research Council and European Research Council.
REPRODUCIBILITY STATEMENT
Full implementation of our DCA algorithm together with the code for reproducing our experiments is available on our GitHub4. We provide datasets used in all experiments in Section 4.1 and the q-DCA experiment in Section 4.2. For all other experiments, we provide the code containing the processing steps that we applied on datasets provided by Poklukar et al. (2021) (see files named * utils.py). The full description of hyperparameters used in our experiments is available in Appendix B. Lastly, in Appendix A we provide additional explanation of our DCA method presented in Section 3.

heading: A METHOD: ADDITIONAL BACKGROUND
text: Our DCA method utilizes several existing methods in each of the three phases, namely, i) Delaunay approximation algorithm (Polianskii & Pokorny, 2019) for obtaining the approximated Delaunay graph GD built on the given set of representations (Phase 1), ii) HDBSCAN (McInnes et al., 2017) for obtaining the distilled Delaunay graph GDD from GD (Phase 2), and lastly iii) GeomCA evaluation scores (Poklukar et al., 2021) for analyzing the connected components of GDD (Phase 3). Therefore, DCA naturally inherits hyperparameters associated to the methods used in Phases 1 and 2, which we summarize below.
Algorithm 1 Delaunay Component Analysis (DCA) Require: sets of representations R and E Optional input: number of sampled rays T (default 104) Optional input: sphere coverage parameter B (default 1.0) Optional input: minimum cluster size mcs (default 10) Optional input: component consistency threshold ηc (default 0.0) Optional input: component quality threshold ηq (default 0.0)
[Phase 1: Manifold approximation] GD ← approximate Delaunay graph(R,E, T ) if B < 1.0 then GD ← filter Delaunay graph(GD, B) (Section 3.2) end if [Phase 2: Component distillation] GDD ← distil Delaunay graph(GD,mcs) [Phase 3: Component evaluation] C ← get connected components(GDD) Slocal ← zeros(|C|, 2) for i = 0, . . . , |C| do Gi ← C[i] compute c(Gi) and q(Gi) as in Definition 3.2 (local scores) Slocal[i, :]← [c(Gi), q(Gi)] end for compute c(GDD), q(GDD),P(ηc, ηq),R(ηc, ηq) as in Definition 3.3 (global scores) Sglobal ← [c(GDD), q(GDD),P(ηc, ηq),R(ηc, ηq)]
Return: Slocal,Sglobal
Delaunay Graph Approximation As discussed in Section 3, the Monte Carlo based algorithm presented by Polianskii & Pokorny (2019) samples rays originating from each representation z ∈ R∪E and efficiently finds their intersection with the boundary of the Voronoi cell Cell(z). The points on the boundary then correspond to edges in the Delaunay graph GD by Definition 3.1, allowing to iteratively reconstruct GD via subgraph approximation. Consequently, the number of found edges directly depends on the number T of rays sampled from each z. However, as we show in ablation studies in Appendix B.1, our obtained distilled Delaunay graph GDD and DCA scores are stable with respect to variations in T . In all our experiments, we used T = 104 unless the value was decreased for computational purposes.
HDBSCAN is a hierarchical clustering algorithm that extracts flat clusters using a technique determining the stability of clusters. To reduce the sensitivity to outliers and noise, HDBSCAN first performs a transformation of space using which points with low density are spread apart. Formally, this is achieved by computing mutual reachability distance among each pair of points from a given set W defined as dmr-k(zi, zj) = {dk(zi), dk(zj), d(zi, zj)}, where zi ̸= zj ∈ W and dk(zi) is the distance to kth NN of zi. This induces the first so-called minimum samples hyperparameter of
Algorithm 2 query point Delaunay Component Analysis (q-DCA) Require: Delaunay graph GDD(R) built on a set of representations R Require: set of query representations Q Optional input: number of sampled rays T (default 104) Optional input: sphere coverage parameter B (default 1.0) Squery ← zeros(|Q|, 3) for j = 0, . . . , |Q| do q ← Q[j] N(q) = (VN(q), EN(q))← get Delaunay neighbourhood graph(GDD(R), q, T ) if B < 1.0 then N(q)← filter Delaunay neighbourhood graph(N(q), B) (Section 3.2)
end if [Processing option 1: Section 4.3] zq ← argminzi∈VN(q)∩R d(zi, q) [get closest representation in R] [Processing option 2: Section 4.2] lq ← d(zq, q) [get length of the edge to the closest representation in R] [Processing option 3: Section 4.1] ÊN(q) ← {} [initiate the set of typical edges] for Gf ∈ F do
calculate µ(EGf ), σ(EGf ) of edge lengths in EGf end for for (zi, q) ∈ EN(q) do
if d(zi, q) ≤ µ(EGf ) + σ(EGf ) for any Gf then ÊN(q) ← ÊN(q) ∪ {(zi, q)}
end if end for Squery[i, :]← [zq, lq, ÊN(q)]
end for Return: Squery
HDBSCAN, k, which we eliminate from DCA by bypassing the computation of dmr-k as discussed in Section 3. This is possible because the approximated Delaunay graph GD obtained in Phase 1 already captures the natural neighbourhood of points in W , where edges originating from outliers and noise differ in length and solid angle from edges originating from points in dense and regular regions. Thus, while HDBSCAN obtains the minimum spanning tree MST from the mutual reachability distance matrix, we obtain it directly from GD. From MST, HDBSCAN then extracts the dendrogram representing the hierarchy of connected components, which is further simplified into a condensed tree. The latter is obtained by categorizing each split in the dendrogram either as a real split, if there is more than minimum cluster size mcs points in each branch, or as outlying points otherwise. Lastly, by analyzing the distances associated to the birth and death of the clusters in the condensed tree, HDBSCAN extracts flat clusters with longest lifetime. Therefore, with our modification of HDBSCAN, DCA inherits only one hyperparameter mcs, which is intuitive to tune. In Appendix B.1, we show that our obtained distilled Delaunay graph GDD and DCA scores are stable with respect to the choice of mcs. In all our experiments we used mcs = 10.
We summarize our DCA framework in Algorithm 1 and its q-DCA extension in Algorithm 2.

heading: B ADDITIONAL EXPERIMENTAL RESULTS
text: In this section, we provide further results supporting the experiments discussed in Section 4 as well as present results of our additional experiments. Moreover, we report the hyperparameters used for DCA and the benchmark methods GS, IPR and GeomCA in each experiment.
Hyperparameters In Table 1, we report the hyperparameters of all the methods used in our experiments presented in Section 4 and Appendix B. For IPR, we used neighborhood size k = 3 as recommended by the authors and constructed the sets R and E of equal size by randomly sampling min(|R|, |E) points from each of them. For GS and GeomCA, we followed the same hyperparame-
ter choices as in (Poklukar et al., 2021). By default, we used GeomCA with geometric sparsification as suggested by Poklukar et al. (2021) unless specified otherwise. Note that using δ = ϵ trivially results in perfect network quality q as it necessarily yields only heterogeneous edges among points from R and E (see (Poklukar et al., 2021) for details). In some cases, we also applied GS on the sets R and E of equal size which were constructed as for IPR. For DCA, we set mcs = 10 for all experiments. Whenever computations were feasible on a single GPU, we used T = 104 and performed no filtering of GD (i.e., used B = 1.0). This was possible when evaluating contrastive representations in Section 4.1 and representations obtained from VGG16 in Section 4.3. When evaluating generation capabilities of a StyleGAN in Section 4.2, we instead sampled less rays T in the approximation of the Delaunay graph GD and used B = 0.7.
B.1 CONTRASTIVE REPRESENTATIONS
In this section, we first derive the optimal values of precision and recall scores used in the varying component density experiment in Section 4.1 and present GS score results for the same experiment. We then show how q-DCA can be applied to investigate the robustness of the model’s representation space to novel images, and present the results of the additional mode truncation experiment performed in (Poklukar et al., 2021). Lastly, we present the results of an extensive ablation study on the inherited hyperparameters of DCA: T ,mcs and the optionalB parameter, described in Appendix A.
In Figure 9, we additionally report the mean and standard deviation (std) of GS scores (multiplied by 100) obtained over 10 iterations as in Section 4.1 when varying p ∈ {0.5, 0.75, 0.999}. We calculated GS both on R and E sets of equal size by downsampling the set E as in calculation of IPR (dark green) and original R and E of unequal sizes (light green) as used in DCA. Firstly, we see that the results are not robust to the changes in the number of points in each set (dark vs light green) and can exhibit large std which is most evident in the case of
outliers for p = 0.999. The results show that GS does not reflect the geometric arrangement of the R and E points which illustrates inadequate informativeness of the score.
Cluster assignments We applied our q-DCA algorithm, presented in Section 3.1, to analyze the robustness of the model to novel images not seen during the training. For this, we constructed three different query sets: Q1 containing 100 test representations of classes c0, . . . , c6 that were removed from E, Q2 containing 100 test representations of classes c7, . . . , c11, and Q3 comprising 250 randomly chosen representations of images of all classes that were recorded from the right camera view (see Figure 4, right). As R and E contain only representations of classes c0, . . . , c6, we expected Q1 to be close to existing fundamental connected components in the distiled Delaunay graph G = GDD(R ∪ E) and Q2 further away. Moreover, if the model is robust to the semantic content in the right-view images, points in Q3 labeled with first 7 classes were expected to be close to G, while the remaining ones should lie further apart. To obtain an assignment (if any) of a query point qj ∈ Qk to an existing fundamental component Gf = (VGf , EGf ) ∈ F , we analyzed the edges inserted using q-DCA (see also Algorithm 2 in Appendix A). Recall that due to the nature of Delaunay graphs, qj can have edges associated to several Gf although these vary in their length. Therefore, we considered only those inserted edges whose length were representative of the connected components they connected to, i.e, we calculated the mean µ(EGf ) and std σ(EGf ) of the length of edges in each Gf ∈ F and kept only edges from N(qj) ∩ Gf that were shorter than µ(EGf ) + σ(EGf ). We refer to these edges as typical edges and define two assignment procedures: (1) conservative where we assigned qj to a component Gf only if all typical edges connected qj to exactly one Gf and did not assign it to any otherwise, and (2) flexible where we additionally assigned qj , whose typical edges connected to more than one component, to a component Gf if it attained both shortest and maximum number of typical edges among all the candidate components.
Using class labels ci, we first determined the majority-vote label of each Gf which we observed to be > 99.9% accurate (see also Table 4 in Appendix B.1). Given the labels of qj ∈ Qk, we then extracted those qj that a) were assigned to a component and report the percentage A of those that were assigned to the one with the correct label. However, by design, our assignment procedure might not assign all the points. Therefore, we additionally extract qj that b) should be assigned to a component and report the percentage B of them that were correctly assigned. Thus, for Q1, the extracted representations in b) is the entire set Q1. Same holds for Q2 as in this case we assumed that points in Q2 should not be assigned to any component and thus report the percentage of those that were correctly not assigned to any. In Q3, we consider a combination of the two cases, where 1750 representations corresponding to c0, . . . , c6 should be assigned to a component if the model is able to extract the underlying semantic information, while the remaining 1250 representations corresponding to ci, i ≥ 7 should not. Therefore, for A, the higher the better for Q1, the lower the better for Q2 and A ≈ 1750/3000 for Q3, while for B it holds that the higher the better for all Qi.
We show the assignment results in Table 2. For Q1, we see that the conservative approach resulted in A = 99% and B = 68%. The former is because 3 points were wrongly assigned, while the latter is due to the fact that 219 representations out of 700 were assigned to several components. Out of these, 206 were considered in the flexible assignment yielding an increase ofB to 98% of correct assignments. For Q2, the conservative approach resulted in B = 85% due to 77 points being assigned to a component despite their wrong label ci, i ≥ 7 (thus leading to A = 0%), suggesting a moderate separation of classes. For Q3, we see that A = 8% and B = 28% in the conservative approach which indicates that the model was not able to recognize similar box configurations recorded from different camera view, which is aligned with the results obtained by Chamzas et al. (2021). Lastly, we observe that flexible approach yielded only minor decrease in B for Q2 and Q3.
Mode Truncation We repeated the mode truncation experiment performed by Poklukar et al. (2021) and applied DCA on the set R comprised of representations corresponding to images of the first 7 classes, c0, . . . , c6, and the sets Et containing representations corresponding to images of the first t classes c0, . . . , ct for t ≤ 11 (see Table 3 for the exact number of points in each of these sets). Since we expect representations to be separated by the class label due to the contrastive training objective, we again set ηc, ηq defining fundamental components to high values of 0.75 and 0.45, respectively. By design, the sets R and Et should reflect mode collapse scenario for t < 6 and mode discovery scenario for t > 7, while in the case of R and E6 we expect to observe a perfect alignment with exactly 7 fundamental connected components.
Figure 10 shows the obtained P,R (left) and c, q (right) DCA scores for each of the sets R ∪ Et for t ∈ {0, . . . , 11}. We observe that DCA correctly correlated with the number of (dis)covered modes contained in Et. The precision P (solid blue) increased with t, while recallR (solid orange) decreased. Moreover, the highest scores were achieved at t = 6 where all the modes in R were covered in E6. The IPR scores reflect the same behaviour but resulted in lower absolute values. This is likely due to the small radius of the constructed hyperspheres arising from a small distance between representations of the same class (as discussed in Section 2). We observe that GS (multiplied by 100) failed to correctly reflect mode collapse for t ∈ {0, 1} as well as mode discovery cases, which illustrates that GS is not sufficiently informative. Additionally, we see that precision and recall (left), and component consistency and quality (right) are aligned for both DCA (P,R, c, q marked with solid lines) and GeomCA (PsG,RsG, csG, qsG marked with dashed lines). This is because the similar density of connected components in this case yielded a reliable ε estimation (see Section 2). Lastly, for DCA, network consistency c (green) and quality q (purple) correctly increased until they reached the maximum at t = 6 and then started to decrease. Note that, in contrast to GeomCA, DCA utilized all the points.
Ablation Study We present the results of an ablation study on DCA hyperparameters discussed in Appendix A and Section 3.2, and show that our algorithm is robust to their choices. We performed an ablation study on Ab-1) HDBSCAN min cluster size mcs parameter, Ab-2) sphere coverage parameter B and Ab-3) the parameter T determining the number of rays used in the Delaunay graph approximation algorithm. To ensure a controlled representation space where prior knowledge of its structure is available, we used the sets R and E6 as in previous experiments. However, to fairly evaluate the obtained scores, we additionally balanced the sets to contain 250 representations corresponding to each of the 7 classes. Thus, |R| = |E6| = 1750 which always yielded a perfect network consistency score c and is therefore omitted from the results. For all experiments, we set ηc = 0.75 and ηq = 0.45 in order to anchor the analysis on the fundamental components only. We always fixed T = 104 in the approximation of GD, B = 1.0 (i.e. preformed no filtering of GD) and msc = 10 for HDBSCAN except in Ab-1) where we variedmsc ∈ {3, 5, 10, 20}, in Ab-2) where we variedB ∈ {0.5, 0.6, 0.7, 0.8, 0.9, 1.0}, and in Ab-3) where we varied T ∈ {10, 102, 103, 105, 106}. VALIDITY OF FUNDAMENTAL COMPONENTS: Firstly, for each experiment in Ab-i), we verified that the fundamental components in the distilled Delaunay graph GDD contain representations corresponding to the same class. In Table 4, we report the percentage of points in R ∪ E6 that contributed to the majority-vote label of each fundamental connected component Gf ∈ F (top rows) when varying mcs (columns) in Ab-1). In square brackets, we report the obtained majority-vote label [ci] corresponding to each Gf . In bottom rows, we report the total percentage of points that contributed to the majority-vote labelling (row included) as well as the percentage of points that were not contained in any fundamental component Gf (row excluded). Firstly, for any choice of mcs, the majority-vote labels of the fundamental components are unique and include all classes c0, . . . , c6. Secondly, we observe that only mcs = 3 resulted in |F| > 7, where points of class c3 were split in two fundamental components. Thirdly, for any choice of mcs, each Gf correctly contains approximately 1/7 ≈ 0.14% of all the 3500 points in R ∪ E6, except for f = 6 (and f = 10) where a small fraction of points were excluded. However, we see that with increasing mcs, the percentage of excluded points decreased and stabilized for mcs ≥ 10. In Ab-2) and Ab-3), we observed the same values as for mcs ≥ 10 in Table 4. These results show that DCA is robust to the choice of hyperparameters, resulting in the correct distilled Delaunay graph GDD.
STABILITY OF DCA SCORES: Next, in each Ab-i), we measured the stability of our precision P , recall R, network quality q, as well as the number of fundamental components |F| with respect to the varying hyperparameter. Moreover, since variations in all hyperparameters affect the number of edges obtained in the resulting distilled Delaunay graph GDD, we also report percentage of edges normalized by the highest number obtained in each ablation experiment separately. Note that varying T directly affects the number of found edges in GD, while varying mcs affects the number of edges in GDD because of the definition of outlying points by HDBSCAN. The results are shown in Table 5, where the column % edges in square brackets additionally shows the maximum number of edges
obtained in each Ab-i) used in the respective normalization. Firstly, we observe that the obtained P,R and q are robust to various choices of hyperparameters, with minor deviations for mcs = 3 which is also the only case that wrongly resulted in 8 fundamental components. Secondly, in Ab-1) (top rows) we observe rather stable number of edges in GDD. In Ab-2) (middle rows), we observe that sphere coverage parameter B not only significantly reduces the number of edges in GDD but also does not affect the obtained scores. This empirically shows that the edge filtering, introduced in Section 3.2, correctly removes unstable edges that are not significant for the correct manifold estimation. We observe a similar result in Ab-3) (bottom rows), where increasing the number of sampled rays T naturally increased the number of found Delaunay edges, while again not affecting the resulting scores except for the minor decrease in case of the extremely low T = 10. These result show the reliability of both our manifold approximation using Delaunay graphs and the introduced edge filtering using B, as well as the stability of our DCA scores.
DCA RUNTIME: Lastly, we additionally report empirical runtime (obtained on NVIDIA GeForce GTX 1650 with Max-Q Design) of the main components of the proposed DCA method normalized by the total elapsed time of each experiment: approximating the Delaunay edges in GD (column approx. GD), filtering of Delaunay edges using sphere coverage parameter B (filter GD), distilling GD into the distilled Delaunay graph GDD (distill GDD) and the analysis of connected components obtained in GDD (analyse GDD). We also report the total time elapsed in seconds (total) for each experiment in Ab-i). The obtained times are shown in Table 6. Firstly, we see that the largest computational bottleneck is the approximation of the Delaunay graph GD, followed by its filtering using B if performed (middle rows). Secondly, we observe that choosing B < 1.0 significantly reduces the number of edges and hence improves the memory consumption (see middle rows in Table 5) at the cost of slightly increasing the total computational time (column total). Thirdly, we see that in Ab-3) increasing T naturally increases the time necessary for the approximation of GD and consequentially the time needed to distill GD and analyze GDD. For clarity, we report the actual elapsed time in seconds for columns distill GD and analyse GDD because of the potentially misleading percentage obtained from the large normalization constant (column total).
B.2 ADDITIONAL EVALUATION OF STYLEGAN
In this section, we present a detailed investigation of the geometry of R and E points obtained in Section 4.2 as well as an additional ablation study on the hyperparameters of the DCA method similar to the one carried out in Section B.1.
Investigation of the geometry of R and E points obtained in Section 4.2 Firstly, we additionally verified the correctness of the obtained DCA scores for each truncation level ψ by investigating the average length of homogeneous edges among R and among E points. The results including mean and standard deviation of the lengths are reported in Table 7. We observe that the average length homogeneous edges among E increases with increasing ψ and resembles the average length of the homogeneous edges among R for ψ = 1.0. This analysis suggests that the StyleGAN model was successfully trained, which is supported by the high-quality images reported in (Karras et al., 2019), and indicates the correctness of the obtained DCA values.
Next, we performed a series of further experiments to investigate the decrease in our DCA scores obtained at truncation level ψ = 0.5 shown in Figure 6. Firstly, we analysed whether the decrease emerged from irregularities of points in R or points in E. To this end, we performed two more tests and applied DCA on the sets a) R = R(ψ = 0.4) and E = R(ψ = 0.5) and b) R = R(ψ = 0.4) and E = E(ψ = 0.5), where we denoted by, e.g., R(ψ = 0.4), the set R obtained at truncation level ψ = 0.4 in Section 4.2. In a), we obtained that P = 0.98,R = 0.98 and q = 0.55 indicating no irregularities in the set R(ψ = 0.5) of sampled training image representations, while in b) we obtained P = 0.52,R = 0.05 and q = 0.14, which is equally low as for R = R(ψ = 0.5) and E = E(ψ = 0.5) where P = 0.65,R = 0.10 and q = 0.19 (as visualized in Figure 6). This analysis showed that the irregularity originates from the geometry of the set E(ψ = 0.5).
Next, in order to verify thatR andE were formed in a specific geometric arragenment similar to that depicted in Figure 2, we additionally analyzed the minimum spanning tree MST(GD) obtained from the approximated Delaunay graph GD built on the sets R = R(ψ = 0.5) and E = E(ψ = 0.5). Recall that MST(GD) is a subgraph of GD connecting all the vertices such that the total edge length is minimized and there exist no cycles. The latter implies that an MST of a graph with n vertices contains n − 1 edges. If our hypothesis that R and E have different densities and are concatenated with a minor intersection is correct, this should be reflected in the length of the edges in MST(GD). We calculated the average length and standard deviation of both homogeneous (among points from only one of the sets) and heterogeneous edges (among points from R and E) in MST(GD). We obtained the average length of homogeneous edges 21.58± 4.88 among R and 13.78± 3.29 among E points, while for heterogeneous edges the length resulted in 18.19 ± 4.00. This indicates the differences in the density of points in each of the set. Moreover, homogeneous edges among R and E points represented 33% and 49% of all edges, respectively, while heterogeneous edges accounted only for the remaining 18%. Together with the obtained low network quality q = 0.19 showing that R and E are poorly geometrically mixed, this verifies that points from R and E are concatenated as shown in Figure 2. Moreover, when performing geometric sparsification on R = R(ψ = 0.5) and E = E(ψ = 0.5), which resulted in |R| = 9364 and |E| = 576, we obtained P = 0.77,R = 0.43 and q = 0.16, which artificially improved the DCA scores with a minor decrease in q compared to results obtained in Figure 6. We emphasise that this scenario cannot be detected with the existing methods due to their limitations discussed in Section 2.
Ablation study We perform an additional ablation study on DCA hyperparameters discussed in Appendix A and Section 3.2 using high-dimensional representations of training and generated images obtained from the VGG16 model, and show that our algorithm is robust to their choices. As in Section B.1, we performed an ablation study on Ab-1) HDBSCAN min cluster size mcs parameter, Ab-2) optional sphere coverage parameter B and Ab-3) the parameter T determining the number of rays used in the Delaunay graph approximation algorithm. For computational purposes, all the experiments were performed on fixed sets R and E containing 10000 VGG16 representations of training and generated images, respectively. For all experiments, we set ηc = 0.0 and ηq = 0.0 as done in Section 4.2. We always fixed T = 104 in the approximation of GD, B = 0.7 and msc = 10 for HDBSCAN except in Ab-1) where we varied msc ∈ {3, 5, 10, 20}, in Ab-2) where we varied B ∈ {0.5, 0.6, 0.7, 0.8, 0.9, 1.0}, and in Ab-3) where we varied T ∈ {10, 102, 103, 105, 106}. We measured the stability of our precision P , recall R, network quality q for each experiment Abi) with respect to the varying hyperparameter. Since variations in all hyperparameters affect the number of edges obtained in the resulting distilled Delaunay graph GDD, we also report percentage of edges normalized by the highest number obtained in each ablation experiment separately. For each Ab-i), we additionally report the mean and the standard deviation (std) of P ,R and q obtained when varying the corresponding parameter. Note that varying T directly affects the number of found edges in GD, while varying mcs affects the number of edges in GDD because of the definition of outlying points by HDBSCAN.
The results are shown in Table 8, where the column % edges in square brackets additionally shows the maximum number of edges obtained in each Ab-i) used in the respective normalization. Firstly, we observe that the obtained P,R and q are robust to various choices of hyperparameters, except for theP,R values obtained in Ab-1) when varyingmcs parameter (top rows). However, such variations are expected due to the nature of the mcs parameter, which directly affects the obtained connected components. Increasing mcs naturally yields more outliers or components of lower quality, which can be seen in the decrease of the P,R values for mcs = 10 and mcs = 20. We emphasise that the
network quality remains unaffected and exhibits low std. In Ab-2) (middle rows), we observe that lowering the sphere coverage parameter B significantly reduces the number of edges in GDD, while not affecting the resulting scores. This again empirically shows that the edge filtering, introduced in Section 3.2, correctly removes unstable edges even in higher dimensional spaces. Similarly, in Ab-3) (bottom rows), increasing the number of sampled rays T naturally increased the number of found Delaunay edges which did not affect the resulting scores. These result demonstrate the reliability and stability of our DCA method even in higher dimensions, and show the efficiency of introduced edge filtering using B.
B.3 REPRESENTATIONS SPACE OF VGG16
In this section, we further describe the experiments performed to analyze the representation space of a VGG16 model (Simonyan & Zisserman, 2015) pretrained on the ImageNet dataset (Deng et al., 2009). We present the results obtained by repeating the experiment investigating separability of classes performed by Poklukar et al. (2021) and show additional examples of images analyzed in Section 4.3 where we applied q-DCA to investigate whether the limited class separation originates from inadequacies of the model or human labeling inconsistencies.
We used the same representations as Poklukar et al. (2021) who constructed R and E from representations of images corresponding to 5 ImageNet classes in each set. In version 1, classes were manually chosen to maximize the semantic differences in representations where R and E contained classes representing kitchen utilities and dogs, respectively, while in version 2 classes were chosen at random.
Class separability We analyzed the distilled Delaunay graph G = GDD(R ∪ E) built on the sets R andE in each version. In Table 9, we report the DCA scores, the relative size of the largest connected component |G0|rV (normalized by |R ∪ E|) and the total number of non-trivial components denoted as # non-trivial. In version 1, we observed one large connected component containing≈ 61% of all the points in R and E, and 4 more non-trivial components containing E points only which in turn yielded a lower precision P . Consequentially, all the heterogeneous edges (among points from R and E) contributing to the network quality q(G) were contained in the first component. A relatively
largeR suggests that features corresponding to images of kitchen utilities were encoded close by in the representation space. On the other hand, in version 2, we observed that the relative size |G0|rV and q(G) increased compared to version 1 indicating that points in R and E are better aligned. Similarly as in version 1, we observed only one more non-trivial component again containing E points only which thus did not contribute to q(G) score. Moreover, we observe larger P and lowerR compared to version 1 which means that more E but less R points were contained in the largest component due to the random choice. Interestingly, by visual inspection (see example images in Figure 11), we see that all non-trivial E components in both versions consist of individual dog breeds suggesting that features representing dogs might be easier for the network to distinguish.
For comparison, we included GeomCA scores reported by Poklukar et al. (2021). We emphasise two main differences in the interpretation of the results: i) their network quality q and consistency c scores are affected by the sparsification process, while ours reflect the structure of the original sets R and E, ii) their absolute values of P,R and |G0|rV are substantially lower than ours which is the result of lower number of edges obtained in GeomCA. For example, the ratio of the number of edges over the number of nodes in version 1 resulted in 0.006 in GeomCA and 673.5 in DCA. This also indicates that ε-edges constructed based on maximum Euclidean distance are not as expressive in higher dimensions as Delaunay ones, which is also seen from higher number of smaller non-trivial connected components obtained in GeomCA.
Amending labelling inconsistencies We show additional examples of images supporting the experiment performed in Section 4.3 where we applied q-DCA to further investigate the origin of the limited class separation, i.e., whether it emerged from inadequacies of the model or inconsistencies of human labeling. We first ran DCA on randomly sampled 5000 points from each of the R and E sets in both versions, and then determined the labels of the remaining 2758 and 3000 points in version 1 and 2, respectively, by the label of their closest point in the distilled Delaunay graph G = GDD(R ∪ E) using q-DCA extension.
This approach resulted in 87.6% accuracy in version 1, and 90.3% in version 2, providing interesting insights into the nature of both human labeling and structure of the VGG16 representation space. In Figure 12, we show examples of query images (odd columns) and the corresponding closest image in G (even columns) having different labels corresponding to version 1 (left, blue) and version 2 (right, green). Similarly as in Figure 8, the first row shows examples of pairs of images considered close by VGG16 despite no clear semantic connection between them. The second row shows examples of images that are close in the VGG16 representation space possibly due to similar pattern, background or structure, while having meaningfully different labels. The last row shows examples where human labeling is different despite the images having strikingly similar semantic information, which is why they are encoded close by the VGG16 model.

Review summaries:
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.

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.   

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.