Delaunay Component Analysis for Evaluation of Data Representations
Authors: Petra Poklukar
Vladislav Polianskii
Anastasiia Varava
Florian T. Pokorny
Danica Kragic Jensfelt
Venue: ICLR 2022 Poster (2022)
Keywords: Interpretation and Evaluation of Learned Representations
Generative Models
Contrastive Learning

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.

DELAUNAY COMPONENT ANALYSIS FOR EVALUATION OF DATA REPRESENTATIONS
Petra Poklukar, Vladislav Polianskii, Anastasia Varava, Florian T. Pokorny & Danica Kragic KTH Royal Institute of Technology, Stockholm, Sweden
ABSTRACT
Advanced representation learning techniques require reliable and general evalu- ation methods. Recently, several algorithmss based on the common idea of geo- metric and topological analysis of a manifold approximated from the learned data representations have been proposed. In this work, we introduce Delaunay Com- ponent Analysis (DCA) - an evaluation algorithm which approximates the data manifold using more suitable neighbourhood graph called Delaunay graph. This provides a reliable manifold estimation even for challenging geometric arrange- ments of representations such as clusters with varying shape and density 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 con- trastive objective, supervised and generative models, and demonstrate various use cases of our extended single point evaluation framework.
INTRODUCTION
Quality evaluation of learned data representations is gain- ing attention in the machine learning community due to the booming development of representation learning tech- niques. One common approach is to assess representa- tion quality based their performance downstream task (Bevilacqua et al. 2021 Li et al.) 2020). Typically, classification problem used to evaluate ther the ability of a model to recover labels of raw in- puts, the transferability domains, as done in state-of-ther thetheeand art unsupervised repre- sentation learning methods (Chen et al.) [202bb] |Emmlovv et al. 2021). However, in many scenarios such straight- forward downstream classification task cannot defined, for instance, because it does not represent the nature of the application or due to the scarcity of labeled data as of- ten occurs in robotics (Chamzas et al. 202 Lippi et al. 2020). In these scenarios, representations are commonly evaluated hand-crafted downstream tasks, e.g., spe- cific robotics tasks. However, these are time consuming design, and potentially also bias evaluation procedures and consequentially hinder generalization of representa- tions across different tasks.
a pre-deeigned
their representations other
Figure 1: Example of approximated Delaunay graph Gp = GD(R u E) (solid edges) obtained from the Voronoi cells (dashed gray lines) of the consid- ered R and E points as well as the dis- tilled Delaunay graph GDD containing three connected components (solid dark colored and gray edges) used in the final evaluation of R and E. See Section for furher details.
Recently, more general evaluation methods such as Ge-
ometry Score (GS) (Khrulkov & Oseledets 2018). Im- proved Precision and Recall (IPR) (Kynkäänniemi et al.
2019) and Geometric Component Analysis (GeomCA) (Poklukar et 2021 have been proposed.
"Correspondence Petra Poklukar, poklukar@kkt kt..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 set of evaluation representations E' is of high quality if it closely mimics the structure of the true data manifold cap- tured by reference set of representations R. This reasoning implies that and E must have similar geometric and topological properties, such connected components, their number and size, which are extracted from various approximations of the data manifolds corresponding to R and E. For ex- ample, 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 Section 2 neither of these approaches provides a reliable manifold estimate com- plex arrangements of It 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 more natural estimate using Delaunay graphs. As seen in Figure edges (solid lines) in 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 the union R J F, extracts its connected components, and applies existing geometric evaluation scores analyze them. We experimentally validate DCA on a variety of setups by evaluating contrastive representations (Section 4.1. generative models (Section
and supervised models (Section 4.3
Furthermore, we exploit the natural neighbourhood structure of Delaunay graphs evaluate 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 the assessment of the visual quality of individual images generated by generative model as also explored by Kynkää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 using aforementioned experimental setups.
STATE-OF-THE-ARU METHODS AND THEIR LIMITATIONS
We review the state-of the-art methods for evaluation of learned data representations, namely GS (Khrulkov & Oseledets 2018). IPR (Kynkäänniemi et al. 2019) and GeomCA (Poklukar et al. 2021). which compare topological and geometrical properties of an evaluation set E with refer- ence 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.
GS
IPR
GoomCA
GeomCA +
DCA (ours)
R E
(a)
(b)
(c)
(d)
(e)
Figure 2: Visualization of manifold approximations obtained by GS (a), IPR (b), GeomCA without sparsification (c). GeomCA with sparsification (d) and our proposed DCA (e).
The pioneering method in this area, GS, constructs witness simplicial complexes randomly sam- pled subsets of R and E (panel (a)), and compares their connected components using tools of com- putational topology (Zomorodian & Carlsson 2004]. The result is average over several iterations summarized either in the form of histograms, which are cumbersome for quantitative comparison. or single normozaalized score, which is in many cases sufficiently informative. Moreover, GS
2

---

depends 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 hy- persphere of radius equal to the distance to its kNN in that set (panel (b)). defines two scores: precision pl which counts the number of E points contained on the approximated R manifold, and vice versa for recall R'. 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) 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 ti) characterizes the captured geometry in four global scores: precision pG and recall RC, which are similar to IPR, as well as network consistency cc and network quality g which are also the basis of the GeomCA local evaluation scores (see Section for recap). GeomCA estimates the manifolds using e-proximity graphs where the hyperparameter E 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 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 ex- tracts a subset of points from each of R and E being pairwise at least distance 6 apart, where is estimated from e. 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 of R and E. An example is illustrated in the bottom component of panels (c) and (d), where the sparsification removes a large portion of the dense E 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 Pok- lukar et al. (202T) to maximize its informativeness. Moreover, extends the existing methods by additionally providing general framework for quality evaluation of single query representations.
3 METHOD
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 [ 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 I the unique property of Delaunay graphs is the definition of neighbouring points that are connected by an edge. For example, in an e-graph, two points are adjacent if they are at most & distance apart. In 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 D. 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 Voronoi cells (depicted as dashed lines in Figure ID in the following.
a point and rigorously define them through
Definition 3.1 Given a set W C. R we define the Voronoi cell Cell(z) associated to a point W as the set of points in IN for which z is the closest among W: Cell(z) W]. The Delaunay graph GD(W) (V.E) built the set V = W is then defined by connecting points whose Voronoi cells intersect, i.e., E =
{x E N
| - 2|l $ -
((z,, 2,) W x W Cell(z;) n Cell(z;) & 0, z $ 23}-
3

---

J We consider reference set R (2 C R and evaluation set E { 1=1 C IN of data representations with R * E, and approximate the Delaunay graph GD = ( E). By Defini- tion 3.1 edges in 9D 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 is based sampling rays originating from each & E R U E and finding their intersection with the boundary of its Voronoi cell Cell(z). This allows 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 2. However, as we show in ablation studies in Appendix [.I and B.2 our evaluation framework is stable with respect to the variations T. Next, we discuss the distillation of GD into connected components.
Phase 2: Component distillation Since edges in GD are obtained among natural neighbours, Gp 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 D. or equivalently, by finding clusters of points having similar natural neighbours (depicted with opaque edges in Figure
We distill 9D into connected components by adapting the state- of-the-art art hierarchical clustering algorithm HDBSCAN (Melnnes et al. 2017) summarized in Appendix(A) A We apply the part HDB- SCAN that extracts connected components (9: from the minimum spanning tred D) We emphasise that applying HDBSCAN directly on MST(GD) efficiently bypasses the calculation of com- plete pairwise distance matrixi of size n& + ng which becomes a computational burden for large R and sets. Such calculation is an integral part of HDBSCAN performed to reduce the sensitiv- ity of the method to noise or outliers which can be omitted in case of Delaunay graphs due their natural neighhourhood structure (see Appendix [A] for further details). In this way, our modification HDBSCAN inherits only one of its original hyperparameters, the minimum cluster size mes parameter, determining the minimum number of points needed for 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. [and [.22 we show that DCA is stable with respect to variations in mes. At the end of this phase, we obtain the distilled Delaunay graph GDD L), Gi of GD which we denote simply by G when no confusion arises. Lastly, we analyze the components of G as summarized below.
Bu
Figure 3: Delaunay graph ap- proximation. In this exam- ple, five rays (green arrows) detect four Delaunay edges (solid gray). The angular size Bi of the bottom right bound- ary is marked in red.
Component evaluation We analyze the connected components Gi of using local and global evaluation scores introduced by Poollukar et al. (202T) which we recap below. Following their notation, we denote by 16lv and [9]g the cardinalities of the vertex and edge sets of graph G = (V, E), respectively, and by GZ (Vlo,Eloxx) C G its restriction to a set Q C.
Phase 3:
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 F, i.e., if | I>> ~ | lv. where G. G denote the restrictions of Gi to Rt and E. Similarly, G, obtains a high quality score if points from It 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 homogeneous edges among points in each of the sets, | & and [ &g, is small compared to the number of her- erogeneous edges connecting representations from R and E. This is rigorously defined as follows:
Definition 3.2 (Local Evaluation Scores, Poklukar et al. 2021 component Gj 9 are defined as the ratios
Consistency e and quality g of
c(G)) = 1 | f
1 liv
(1 e G.
G 2
and ((G.)=
(I)
Gily
otherwise,
'Minimum spanning tree a graph is a tree minimizing the total edge length and connecting vertices. 'The matrix represents mutual reachability distance calculated among each pair of points with respect to the minimum samples parameter.
4

---

respectively. Moreover, 9s is called consistent c(G.) > ne and of high-quality if (G.) Na for given thresholds ne. Bl E (0.1) C R. A consistent component of high-quality as determined by lg is called fundamental component. The union of fundamental components is denoted by F = F(G, Be. M4) and indexed by the subscript J, Lee, we write G F.
The thresholds Ne: f2 are designed to enable 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 between R and E, 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() and network quality g()) as in Definition 3.2 as well as precision P and recall R as
F 1
and R F l
p
respectively, where FR,F ,F denote the restrictions of F = F(G, ne. 77) to the sets R and E.
3.1 EXTENSION: QUERY POINT INSERTION AND EVALUATION
A practical evaluation framework should not only provide functionality to analyse sets of represen- tations but also to assess the quality of individual points with respect R, which is desirable in any application where data is being collected continuously. In case of Delaunay graphs, evaluating the quality of query point q C R |R is equivalent to studying its insertion into the distilled Delaunay graph GDD(R) Formally, we consider the neighbourhood N(g) of in the distilled Delaunay graph GDD(R (RU {q}} defined as the subgraph of ( RR {q}) induced by all vertices adjacent to q includ- ing q and intersected with GDD RR. To find the edges of N (g)). it suffices to perform the sampling process described in Phase only within the Voronoi cell Cell(g) of Gp. In fact, this process can be efficiently performed for set Q of query points independently from each other and has equal com- putational 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, DCDCA algorithm.
The obtained neighbourhood graph N(g) = (y)(a), gN))) 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 in R closest to q, ii) by additionally extracting the length of that edge, or di) 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
3.2 DELAUNAY GRAPH REDUCTION VIA SPHERE COVERAGE
In high dimensions, the Delaunay graph 9p 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 (2, 2z) E(GD) directly de- pends the angular size of Cell(z,) n Gell(zz) viewed from one of the point 3 It visualized in Figure 3 and formally defined as the solid angle Bey E (0, 1] at 2, of a cone with vertex 2; and base Cell( 2 n Cell(2;) normalized by the volume of the unit hypersphere. It is approximated by the ratio of all rays sampled from 2; that provided the corresponding edge (z,, 2j) using the algorithm of Pollinskki & Pokorny 2019). Intuitively, low Big values correspond to edges that unstable (depicted with thinner lines in Figure []] because they may disappear with small perturbations of data. We therefore propose to remove the longest edges (zi, 2,) connecting 2; such that the sum Σ, Biy of solid angles corresponding to the remaining ones is larger than a predetermined parame- ter B E [o, 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.I
'The authors of Rushdi al. 2017) call this significance.
5

---

3.3 COMPLEXITY ANALYSIS
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] + + 2(N), we utilize the probabílistic method for the construction of the graph proposed by PPlliankki & Pokorny (2019)
that yields the total complexity ([[ + [E)² (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] + {)) 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 (Poliankki & Pokorny 2019). (Campello et al. 2015) and (Melnnes & Healy 2017) for details.
4 EXPERIMENTS
Our implementation of the DCA algorithm is based on the C+++/peenCI implementation of Delau- nay graph approximation provided by Polianskii & Pokorny (2019) as well as on Python libraries
HDBSCAN (MeInnes et al., 2017) and Networkx (Hagberg ct al. 2008). The code is available on We considered similar experimental setup as in (Poklukar et al. 2021 and analyzed (i) representation space of contrastive learning model trained with NT-Xent contrastive loss (Chen 2020a), (ii) generation capabilities of a StyleGAN trained on the FFHQ dataset (Karras et al.]
Github
ct 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 p&G R= ca G and without it (denoted by pc; RC c (649) IPR (denoted by P', ,R) 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
4.1 CONTRASTIVE REPRESENTATIONS
A successfully trained contrastive learner provides a controlled setup with known structure of learned representations, thus enabling us to perform series of experiments validating the correct- ness 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 [.I] where we i) show how q-DCA be applied to investigate the robustness of the model's '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 PPoklukar et al. (202T), and lastly üii perform a thorough ablation study on hyperparameters of DCA.
We used model trained on an image dataset shown in Figure 4 presented by Chamzas et al. (2021). The training DJ and test DE datasets each con- sisted of 5000 images containing four boxes arranged in 12 possible configu- rations, referred to as classes, recorded from the front camera angle (Figure left). We created the sets It and E from 12-dimensional encodings of DJ and DF, respectively, corresponding the first 7 classes, co,..., Cs. Due to the contrastive training objective, we expect to observe 7 clusters corresponding to each class and therefore set fe: Fly defining fundamental components, to rather high values of 0.75 and 0.45, respectively.
Figure 4: Box im- ages recorded from the front and right views, respectively.
Varying component density To demonstrate reliability of DCA in various geometric arrange- ments of points, repeatedly sampled 10 times 3 classes G; and discarded fraction of p e (0.5,0.75, 0.999) points in R with that label. In this way, R contained smaller and sparser com- ponents for p 0.5, 0.75, while p 0.999 mimics scenario with outliers. Since such pruning
https: tww.ttthhhhh.ooog com wtt.:/oc////eeeeeeee rapok www.akkwwkkkkkkkooookkkkk ukar//CA

---

necessarily removed 3 fundamental components due to 7) 0.75, we expected observe the erage precision P = 4/7 regardless the value of p. On the contrary, increasing corresponds to majority of R being contained in the remaining fundamental components, thus R should approach (see Appendix B. for precise calculation of the optimal values). Since by design, [ < [ we performed downsampling of E. in case of IPR.
(0) p=
p=
p 0.999
1.0
1.0
1.0
0.8
0.6
0.2
0.2
0.2
0.0
P 7 6 P
R R R'
0.0
1á0 7e
R R R!
0.0
P PáC p p
R RR x!
Mean and std of DCA (P, R). GeomCA with and without sparsification (p=6 R pc, ) and IPR scores (P', R') obtained when varying the fraction controlling the amount of discarded points. Vertical lines denote optimal values for P (blue) and (orange).
Figure
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 Rs 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, R ss 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 0.75 and p 0.999, where both GeomCA and sparse GeomCA A scores are lower than DCA due to a largely disconnected graph resulting from a small e. The IPR was again not robust for p 0.75, while p 0.999, pl 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 R' resulting in low score. In Appendix B.1 we also report the results for GS which we found to be inadequaltely informative.
4.2 EVALUATION OF A STYLEGAN
Next, we applied our proposed DCA and q-DCA algorithms to assess the quality of both data distri- bution learned by 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 (Kynkäänniemi et al.) 2019 Poklukar et al., 2021) where during testing latent vectors were sampled from a normal distribution truncated with 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 trunca- tion db (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 Rt and E, respectively. For low values of th 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 diver- sity of the training images. Due to the large number of considered representations, we reduced the size of the approximated Delaunay graph GD U E)) by setting the sphere coverage parameter B, introduced in Section 3.2 to 0.7.
Figure shows the obtained DCA scores (solid lines) together with GeomCA, IPR and GS scores (dashedTingg Tines). All methods correctly reflect the truncation level v apart from GS at // = 0 and DCA at di 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 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
7

---

was successfully trained, which is 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 p= RRC For IPR, it is because the radii of spheres around F. points yield conservative coverage discussed in Section 2 Therefore, this analysis demonstrates that DCA scores in this case provide more accurate description of the geometry.
Next, we analyze the in- consistency in R and E de- tected by DCA at &b = 0.5. It originates from their peculiar geometric position similar to that visualized in Figure 2 where points in formed a denser cluster that slightly mixed but mostly concatenated to a more scattered cluster in R. As discussed in Section ? such formation can neither be detected by IPR due to the large sphere radii ob- tained from the more scat- tered R points nor Ge- omCA due to the sparsi- fication removing majority of dense E points that are concatenated to the R cluster, while a single score of GS is too uninformative. In Appendix (B.2] provide detailed investigation where 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.
1.0
1.0
1.0
R
R40
0.8
0.6
0.6
0.6
scores
0.4
0.4
0.4
0.2
0.0
0.0
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Figure 6: Mode truncation results. Left: DCA P, GeomCA PeG and IPR Pl precision scores (in blue colors), together with GS (green). Middle: DCA R. GeomCA ReG and IPR R! recall scores. Right: DCA (c, q) and GeomCA (e*G, .q*C)) network consistency (light green)
and quality scores (purple).
Lastly, note that network consistency c and quality g values are reversed in DCA compared to Ge- omCA as we consider all 50000 points. Therefore, we trivially obtained e cequal to I that is perfectly aligned with qº score due to the geometric sparsification (see Appendix B On contrary, q in- creased with şi except for the observed irregularity at e = 0.5.
Quality of individual generated images A challenging problem in generative modelling is to as- sess the quality of individual generated samples, which 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 train- ing images, approximated g GDD R)) and analyzed newly added edges gN(w) for each query representation 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 Kynkääänniemi jet al. (2019) and sorted the generated images both by increasing Delaunay edge length and decreas- ing 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 repre- sentations in this experiment to perform an ablation study on the hyperparameters of our proposed DCA method. Similarly 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
8

---

shortest distance
largest distance
Figure 7: Examples of images generated by a StyleGAN that closest (left) and furthest (right) to training images from FFHQ dataset in representation space of a pretrained VGG16.
Delaunay graph Gp (Phase 1), ii) the minimum cluster size parameter used in the distillation of OD (Phase 2) and lastly, lii) 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 higher dimensional representation spaces. We refer the reader Appendix B.2 for further details.
4.3 REPRESENTATION SPACE OF VGG16
Lastly, we applied q- J-DCA to analyze whether the structure the representation space of a VGGI6 classification model pretrained on ImageNet reflects the human labeling. By repeating the experi- ment investigating separability of classes performed by Poklukar et al. (202I). we reached a similar conclusion that VGG16 moderately separates semantic content (see Appendix [B.3). However, further investigated whether the limited class separation originates from inadequacies of the model or human labeling inconsistencies. To distinguish between the two scenarios, applied q-DCA to obtain labels of query points and compared them to their true labels.
Amending labelling inconsistencies We used representations of ImageNet images constructed by PPoklukar et al. (2021) corresponding classes representing kitchen utilities and 5 classes representing dogs. We constructed R by randomly sampling 10000 points, and composed the query set Q1 of the remaining 2758 points. We then determined the label of each query point g by the label of closest point in its neighbour- hood (Qq). The obtained 87.6% accuracy offers interesting insights into both human labeling and structure of the VGG16 representation space. In Figure 8 show various examples of query images (left) and the corresponding closest image in GDD (right) having different labels. The first shows amples of pairs of images considered close by VGG16 despite no clear semantic connection between them. The second row shows examples having mcaningfully different labels but are encoded close by VGG16 potentially due to the similar pat- tern. On the other hand, the last row shows examples where human labeling different but VGG16 correctly encoded the images close due to their striking semantic similarity. More examples can be found in Appendix B.33, where we show similar cases using images correspond- ing 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.
query point
eloeest R point
clear semansic connection
similar pattern
similar semantic information
Figure 8: Examples of query im- ages (left) and their corresponding closest R images (right).
CONCLUSION
We presented Delaunay Component Analysis (DCA) framework for evaluation of learned data repre- sentations which compares the structure of two sets of representations R and E using the introduced distilled Delaunay graphs. We showed that distilled Delaunay graphs provide reliable approxima- tion in various complex geometric arrangements of R and E, thus resulting in a stable output of our DCA scores. Moreover, introduced the extended q g-DCA framework for individual query repre- sentations evaluation. We experimentally demonstrated the applicability and flexibility of q DCA on three different scenarios.

---

ACKNOWLEDGEMENTS
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 GitHub 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
REFERENCES
Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph classification extrapolations. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 837-851. PMLR, 18-22 24 Jul 2021. URL https::/pprceedd.ng
mlr. mll.:rees//1133//eeicccc .ttmmmal..mmmmmmmm
Ricardo JGB Campello, Davoud Moulavi, Arthur Zimek, and Jörg Sander. Hierarchical density es- timates for data clustering, visualization, and outlier detection. ACM Transactions Knowledge Discovery from Data (TKDD), 10(1):1-51, 2015.
Constantinos Chamzas, Martina Lippi, Michael C Welle, Anastasia Varava, Lydia E Kavraki, and Danica Kragic. Comparing reconstruction and contrastive- -based models for visual task planning. arXiv preprint arXiv:2109.066
2021.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Pro- ceedings of Machine Learning Research, pp. 1597-1607. PMLR, 13-18 Jul 2020a. URL https::/proceedingg mlr press /alsss/vili 19 chen20 .htll
Ting Chen, Simon Korbblith, Kevin Swersky, Mohammad Norouzi. and Geoffrey Hin- ton. Big self-supervised models are strong semi-supervised learners. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.). Advances in Neu- ral Information Processing Systems, volume 33, pp. 22243 22255. Curran Associates, Inc., 2020b. URL htteps://proceeddinnn www.nig.n.eiiip... neurips. http://eerrrpp..pppppee//22a cc/paperr2220//1lee Ecbc95codd55 1aal 81 0112700cc1400eee Paper.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. IEEE, 2009.
Aleksandr Ermolov, Aliaksandr Siarohin, Enver Sangineto, and Nicu Sebe. Whitening for self- supervised representation learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, 3015-3024 3024. PMLR, 18 24 Jul 2021. URL https:tt///tt / htttp:://proceedings. mlr. wttp:ess//13///emooo2222.2. html
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahra- mani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27, pp. 2672-2680. Curran Asso- ciates, Inc., 2014. URL https: http::://pocceddan.eetr newripsisss.... httpp//ps....pppaee//////e/e 5ca3e9b1 9
pd
10

---

Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using networkx. In Gaël Varoquaux, Travis Vaught, and Jarrod Millman (eds.), Proceedings of the 7th Python in Science Conference, pp. 11 15, Pasadena, CA USA, 2008.
Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4401-4410, 2019.
Valentin Khrulkov and Ivan V. Oseledets. Geometry score: A method for comparing generative adversarial networks. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th In- ternational Conference on Machine Learning, ICML 2018, Stockholmsmüsssnn Stockholm, Swe- den, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 2626 2634. PMLR, 2018. URL http:::ppocceeeeeiiccccc
mir
html
Tuomas Kynkäänniemi, Tero Karras, Samuli Laine, Jaakko Lehtinen, and Timo Aila. Improved precision and recall metric for assessing generative models. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Informa- fion Processing Systems 2019, NeurlPS 2019, December 8-14. 2019, Vancouver, BC, Canada, pp. 3929-309 3938, 2019. URL https: htRLhhts::///ptttm http:::sss/ppccceedeee new.eeeewweeeenee.eeee..ee...ee http://wwww...aaaaaaooppaaappppa 0234c51 wwwpdd08c22cccccccccccccccc
html
Nanbo Li, Cian Eastwood, and Robert Fisher. Learning object-centric representations of multi- object scenes from multiple views. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Bal- can, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5656-5666. Curran Associates, Inc., 2020. URL http:::tttttttssseee www.angs..nuusrsrooo Pappee..p.ppppp.pppp......
Martina Lippi, Petra Poklukar, Michael C Welle, Anastasiia Varava, Hang Yin, Alessandro Marino, and Danica Kragic. Latent space roadmap for visual action planning of deformable and rigid object manipulation. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2020.
Leland McInnes and John Healy. Accelerated hierarchical density based clustering. In 2017 IEEE International Conference Data Mining Workshops (ICDMW), pp. 33-42, 2017. doi: 10. 109/ 1CDMW.2017.12.
Leland McInnes, John Healy, and Steve Astels. hdbscan: Hierarchical density based clustering. The Journal of Open Source Software, 2(11), mar 2017. doi: 10.21105/joss.00005. URL https:
00205
Petra Poklukar, Anastasiaa Varava, and Danica Kragic. Geomea: Geometric evaluation data representations. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International
Conference on Machine Learning, volume 139 Proceedings of Machine Learning Research, pp- 3588-8596 PMLR, 18-24 Jul 2021. URL https: http:////occeeeeeeeeeeeee mlr. wttpsssww..ppp....eeeeememm
poklukar2la.hi html
Vladislav Polianskii and Florian T. Pokorny. Voronoi boundary classification: A high-dimensional geometric approach via weighted Monte Carlo integration. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2019. URL
PMLR, 09-15 Jun 9a. html
mlr. pttpmm/m.ppeeee/ee/ooooaaaaaeee
Ahmad Rushdi, Laura P Swiler, Eric T Phipps, Marta D'Elia, and Mohamed S Ebeida. Vps: Voronoi piecewise surrogate models for high-dimensional data fitting. International Journal for Uncer- tainty Quantification, 7(1), 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA. May 7-9, 2015, Conference Track Proceed- ings, 2015. URL http:://axxxii http:///arxiv.orr//aa///00 1556

---

Afra Zomorodian and Gunnar Carlsson. Computing persistent homology. In Proceedings of the Twentieth Annual Symposium on Computational Ceometry, SCG '04, pp. 347-356, New York, NY. USA. 2004. Association for Computing Machinery. ISBN 1581138857.
doi:
10.1145/997811.997788 UtR.tttps::/do' http::://dooor///..... org/10........ 1et..1115999711777 997870
A METHOD: ADDITIONAL BACKGROUND
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 of representations (Phase 1), zi) HDBSCAN (Melnnes al. 2017) for obtaining the distilled Delaunay graph GDD from GD (Phase 2), and lastly iii) GeomCA evaluation scores (Poklukar al. 202T) for analyzing the connected components of GDD (Phase 3). Therefore, DCA naturally inherits hyperparameters associated to the methods used in Phases and 2, which we summarize below.
Algorithm Delaunay Component Analysis (DCA)
Require: sets of representations R. and E
Optional input: number of sampled rays T (default 10*)
Optional imput:
sphere coverage parameter B (default 1.0)
Optional input:
minimum cluster size mes (default 10)
Optional input:
component consistency threshold ne (default 0.0)
Optional input: component quality threshold 17y (default 0.0)
[Phase 1: Manifold approximation]
GD + approx wwtroximateen iatt weeiiiaatteeeeaee Lawaateaeaaaaaaaaaaaaahhh R,
if < 1.0 then
Gn -.f.itee.DDDlauuayrrrrhhh..C... (Section 3.2
end
[Phase 2:
Component distillation]
Ipn + distil Delaunay graph(Gn, mcs)
[Phase 3: Component evaluation]
C < peee.coonecteedcccooonnttttsss
Stocal f zeros((C),
for i = 0, 0=...,,.,', do
+ C[i]
compute c(G.) and ((G.) as in Definition 3.2 (local scores)
Syecl [i, - [c(G,), (9:)]
end for
compute e(Gpp), ((pp)) P(ne: na), R(yo: 1h) as in Definition 3.3 (global scores)
Sglobal x [c(GDD), ((GD)), P(1e: n4), R(Te: n4)l
Return: Siocal: Sglobal
Delaunay Graph Approximation As discussed Section 3 the Monte Carlo based algorithm pre- sented by Polianskii & Pokorny (2019) samples rays originating from each representation = RUE 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 Go by Definition 3.I 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 2. However, as we show in ablation studies in Appendix 1 our obtained distilled Delaunay graph Gon and DCA scores are stable with respect to variations T. In all our experiments, we used 10a unless the value was decreased for computational purposes.
HDBSCAN is a hierarchical clustering algorithm that extracts flat clusters using a technique de- termining 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 given set W defined as dmex (2,, 27) {dy (zz), dy (2j). 2,),, where 2; * 2j E W and de (2;) is the distance to kth NN of z This induces the first so-called minimum samples hyperparameter of
12

---

Algorithm 2 query point Delaunay Component Analysis (q-DCA)
Require: Delaunay graph (DD(R) built on a set of representations R
Require: set of query representations Q
Optional input: number of sampled rays T (default 10*)
Optional input: sphere coverage parameter B (default 1.0)
querry + 2eroos[[)].
for j ...... [ do
4 Q[i]
N(g) = (VNN g + heg.ee/l..aaagy..aaaaooooooorror
if B 1.0 then
(g)) + wtt.l:/e..uuuuuy...eoooooororrrr (Section 3.2
end if
Processing option 1: Section
2g < -arg mig,in,,eee E e d(( (z 9
[get closest representation in R]
PPooessing option 2: Section 4.2
4 f d(zg. q) [get length of the edge to the closest representation in RR]
[Processing option 3: Section 4.1
(N(() + O
[initiate the set of typical edges]
for 93 E F do
calculate ((Eer), ((E))) of edge lengths in g9, end for for (2,, 9) E E(a) do if d(z, S p(E9;) (881)) for any Gy then
(N(a) + ENia) {(2,9)}
end if end for
Squary [ +- l2g. lg. [N(o)]
end for Return: Squery
HDBSCAN, k, which we eliminate from DCA by bypassing the computation of dma-k as discussed in Section 3 This is possible because the approximated Delaunay graph Gp obtained in Phase 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 reach- ability distance matrix, obtain it directly from Gp. 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 real split, if there is more than minimum cluster size mes 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 modi- fication of HDBSCAN, DCA inherits only one hyperparameter mcs, which is intuitive 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 mes. all our experiments we used mes 10.
We summarize our DCA framework in Algorithm D
and its D-DCA extension in Algorithm
B ADDITIONAL EXPERIMENTAL RESULTS
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 I we report the hyperparameters of all the methods used our ex- periments presented in Section 4l and Appendix B For IPR, used neighborhood size & 3 as recommended by the authors and constructed the sets and E of equal size by randomly sampling min( RR], FE) points from each of them. For GS and GeomCA, followed the same hyperparame-
13

---

ter choices in (Poklukar et al. 2021). By default, we used GeomCA with geometric sparsification as suggested by Poklukar et al. (202)) unless specified otherwise. Note that using 6 e 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, set mes 10 for all experiments. Whenever computations were feasible on a single GPU, we used T = 10 and performed no filtering of GD (i.e., used B = 1.0). This was possible when evaluating contrastive representations in Section and representations obtained from VGG16 in Section 4.3 When eval- uating generation capabillities 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.
Table I: Hyperparameters, used for the benchmark methods GS, IPR and GeomCA as well as our DCA method in the experiments presented in Section The same hyperparameter choices apply for experiments presented in Appendix B
GS
IPR
GEOMCA
DCA
Lo
Y
imex
7
c(P)
mcs
SECTION
4.1
64
1/128
10
1000
3
c(1)
s/2
1. 10
1.0
10
SECTION
64
1/128
100
1000
3
<(10)
5. 10a
0.7
10
SECTION
/
/
3
<(10)
E
1 10
1.0
10
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 's representation space to novel images, and present the results of the additional mode truncation experiment per- formed in (Poklukar et al. 2021). Lastly, we present the results of an extensive ablation study on the inherited hyperparameters of DCA: T, mes and the optional parameter, described in Appendix [A]
Varying component density In Table 3 we report the num- ber of representations corresponding to each class in the con- sidered training D and test Dÿ datasets containing images of boxes placed in 12 possible configurations recorded from the front camera view. The total number of representations corresponding to the first 7 classes cu... .o...... C6 contained in R and was 3514 and 3463, respectively. Therefore, on aver- age, each class in R contained 502 points. By Definition 3.3 recall R is defined as the fraction of R points contained in the union of fundamental components F over the total num- ber of points in R. Thus, when discarding p = 0.5 frac- tion of points from three fundamental components in R, the average optimal value of recall R., is calculated as R. ao (502- 4)/(502
downsampled
0-
0.5
0.75
0.999
0.5
0.75 0.999
p
Figure 9: Mean and standard de- viation of GS scores (multiplied by 100) obtained over 10 iterations when varying the fraction p con- trolling the amount of discarded R points. Left: GS calculated on R and E of equal size by downsam- pling E. Right: GS calculated on the original R. and E sets of un- equal size.
251 3) R 0.73. When p 0.75, we get that R, As (502- 4)/ 4 4 + 126 3) s 0.84, and for p 0.999, R. s (502 4) -502-4+11 44+1-3) since precision P is defined as the fraction of E points con- tained in F over the total number of points in E, its average optimal value is calculated as P. ~ (494 4)/3463 R 0.57. This value optimal for all values of p since variations in p do not affect the number of points in E.
0.99. Similarly,
In Figure 9 we additionally report the mean and standard de- viation (std) of GS scores (multiplied by 100) obtained over 10 iterations in Section 4.1 when varying p E (0.5.0 0.75, 0.999}. We calculated GS both on R and E sets of equal size by downsam- pling 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 light green) and can exhibit large std which is most evident in the case of
14

---

outliers for 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 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: Qi containing 100 test representations of classes Co2 C6 that were removed from E. Q2 containing 100 test representations of classes ,1....,CiI. 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 co...., Co. we expected Q1 to be close to existing fundamental connected components in the distiled Delaunay graph G = GDD R U 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 9. while the remaining ones should lie further apart.
To obtain an assignment (if any) of query point 93 E Qk to an existing fundamental component Gy = (v0r, gd1)= E F. we analyzed the edges inserted using q-DCA (see also Algorithm 2 in Appendix Aj. Recall that due to the nature of Delaunay graphs, qj can have edges associated to several g 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 ((E3r) ) and std (EEr) of the length of edges in each Gj E F and kept only edges from N (aa) n gy that were shorter than ((E9)) + (E9)). We refer to these edges as typical edges and define two assignment procedures: (1) conservative where we assigned 4j to a component 9 only if all typical edges connected q, to exactly one G and did not assign it to any otherwise, and (2) flexible where additionally assigned gj. whose typical edges connected to more than one component, to a component 9 if it attained both shortest and maximum number of typical edges among all the candidate components.
Using class labels G, we first determined the majority-vote label of each gj which we observed to be > 99.9% accurate (see also Table 4 in Appendix B.I]. Given the labels of qj Qi. we then extracted those Lj that a) were assigned to a component and report the percentage A of those that were assigned the one with the correct label. However, by design, our assignment procedure might not assign all the points. Therefore, we additionally extract 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 combination of the two cases, where 1750 representations corresponding to Co,.... GB should be assigned to a component if the model is able to extract the underlying semantic information, while the remaining 1250 representations corresponding to c, 2 should not. Therefore, for A, the higher the better for Q1. the lower the better for Q2 and A xe 1750/3000 for Qs. while for B it holds that the higher the better for all Q+-
Table 2: Results of assigning points in query sets QE to fundamental components Gy E F.
A = % CORRECTLY ASSIGNED
B
% THAT SHOULD ASSIGNED
(t) Q2(L)
Q3
(t(
Q2(t)
Qa(t)
CONSERVATIVE
0.99
0.00
0.08
0.68 0.98
0.85
0.28
FLEXIBLE
0.99
0.00
0.08
0.83
0.19
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 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 of B to 98% of correct as- signments. For Q2. the conservative approach resulted in B = 85% due to 77 points being assigned to component despite their wrong label c, i > 7 (thus leading to A 0%). suggesting a moderate separation of classes. For Qs. we see that A = 8% and B = 28% in the conservative approach which indicates that the model was not able recognize similar box configurations recorded from different camera view, which is aligned with the results obtained by Chamzas et al. (202I). Lastly, observe that flexible approach yielded only minor decrease in B for Q2 and Q3-
15

---

Table 3: Number of representations corresponding to each class o contained in the training Dj (top row) and test D (middle row) datasets. The bottom shows the size of the sets Eg used in the mode truncation experiment.
0
2
3
4
6
7
8
10
11
D
670
690
395
706
349
409
295
296
292
311
258
331
666
625
373
684
429
377
309
312
310
293
279
345
E,
666
1291
1664
2348
2777
3154
3463
3775
4085
4378
4657
5002
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
P
R
440
0.2
0.2
0.2
RC
GS
R!
9
0.0
0.0
10
6
8
2
8
10
t
Figure 10: Scores obtained on R and E, when varying the truncation parameter t. Left: DCA P. GeomCA with sparsification pao and IPR pt precision scores (blue) together with GS score multiplied by 100 (green). Middle: DCA R. GeomCA with sparsification R&G and IPR R! recall scores. Right: network consistency (green) and quality (purple) scores of DCA (c, q) and GeomCA with sparsification (c=G 99
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 classes, co. Co...., Co. and the sets E, containing representations corresponding to images of the first t classes Co. ...,.. for S 11 (see Table the exact number of points in each of these sets). Since expect representations to be separated by the class label due to the contrastive training objective, we again set Nes 1l defining fundamental components to high values of 0.75 and 0.45, respectively. By design, the sets R and E, should reflect mode collapse scenario for < and mode discovery scenario for > 7, while in the case of R and Eg we expect to observe a perfect alignment with exactly fundamental connected components.
Figure 10 shows the obtained P, R (left) and c, (right) DCA scores for each the sets R U E, for t E T0.... 11). We observe that DCA correctly correlated with the number of (dis)covered modes contained in E,, The precision P (solid blue) increased with i, while recall R (solid orange) decreased. Moreover, the highest scores were achieved at 6 where all the modes in R were cov- ered in Eg. 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 correctly reflect mode collapse for E (0, 1} as well 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 (PaG R& c nG 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 (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.
16

---

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-1J 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 controlled representation space where prior knowledge of its structure is available, we used the sets It and Es 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 EEsl = 1750 which always yielded a perfect network consistency score and is therefore omitted from the results. For all experiments, we set Ve = 0.75 and 7// 0.45 in order to anchor the analysis on the fundamental components only, We always fixed T = 10 in the approximation of 9D. B = 1.0 (i.e. preformed no filtering of Gp) and msc 10 for HDBSCAN except in Ab-l) where we varied msc {3. 5, 10, 20), in Ab-2) where we varied B E (0.5, 0.6, 0.7, 0.8, 0.9, 1.0), and in Ab-3) where we varied T E {10, 102, 10 10 10%).
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 cor- responding to the same class. In Table 4 we report the percentage of points in R U Es that con- tributed to the majority-vote label of each fundamental connected component 9 E F (top rows) when varying mes (columns) in Ab- I). In square brackets, we report the obtained majority-vote label [cy] corresponding to each Gy. 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 Gن (row excluded). Firstly, for any choice of mcs, the majority-vote labels of the fundamental components are unique and include all classes Co,...,CB. Cp. Secondly, we observe that only mes 3 resulted in [F] > 7, where points of class C3 were split in two fundamental components. Thirdly, for any choice of mes, each G correctly contains approximately 1/7 0.14% of all the 3500 points in R J Eg. except for f 6 (and = 10) where a small fraction of points were excluded. However, we see that with increasing mes, the percentage of excluded points decreased and stabilized for mes 2 10. In Ab-2) and Ab-3), we observed the same values as for mes 2 10 in Table These results show that DCA is robust to the choice of hyperparameters, resulting the correct distilled Delaunay graph GDD-
Table 4: The percentage of points in R J Es contributing to the majority- labelling of each fundamental component G, E F(GDn(R (R U Ea), The 0.75, M0 = 0.45) (shown in rows) when varying mes (columns). The majority vote label e; of each Gf is shown in square brackets [ca]. The bottom rows show the total percentage of points from R U F.g that contributed to the majority-vote labelling (row included) and that were excluded from fundamental components F (row excluded).
% OF POINTS LABELLED WITH MAJORITY- [c]]
3
5
10
20
0
0.143
[2
0.143
c2
0.143
[ca]
0.143
[cc]
1
0.142
C44
0.142
C1
0.142
[c]
0.142
[1]
G
2
0.141
Cs
0.142
C4
0.142
C4
0.142
Ca
3
0.140
[c]
0.141
Cs
0.141
Cca
0.141
Co
COMP.
4
0.139
[co
0.140
Cca
0.140
[c6]
0.140
08
IDX
5
0.127
[c]]
0.139
co
0.139
[co]
0.139
[o
6
0.127
[c3]
0.127
[ea]
0.136
[ca]
0.136
[ca]
10
0.001
[ca]
INCLUDED [%]
0.960
0.973
0.981
0.981
EXCLUDED [%]
0.040
0.027
0.018
0.018
STABILITY OF DCA SCORES: Next, in each Ab-i), we measured the stability of our precision P. recall R. network quality as well as the number of fundamental components |.FI 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 mes affects the number of edges in GDD because of the definition of outlying points by HDBSCAN. The results are shown in Table where the column % edges in square brackets additionally shows the maximum number of edges
17

---

Table 5: DCA ablation results obtained when varying mes in experiment Ab-1) ) (top rows). sphere coverage parameter B in Ab-2) (middle rows) and number of sampled rays T in Ab-3) (bottom rows). For each experiment Ab-i), we report in columns the obtained precision P, recall R, network quality (()), percentage of edges normalized by the maximum number obtained per experiment Ab- (with maximum absolute value shown in square brackets) and lastly, the number of fundamental components F.
P
R
(
% EDGES
|F
3
0,949
0,972
0,502
0.959
8
0,967
0.979
0,502
0.984
7
YICS
0.977
0.987
0,502
1.0
0.977
0.987
0.502
1.0 [301376]
[0.967 + 0.013]
[0.981 + 0.007]
[0.502 + 0.000]
0.5
0.977
0.989
0.502
0.357
0.6
0.977
0.987
0.502
0.393
7
0.7
0.977
0.987
0,502
0.448
7
0.8
0.977
0.987
0.502
0,534
7
0.9
0.977
0.987
0,502
0.676
1.0
0,977
0,987
0.502
1.0 [301376]
7
[0.977 + 0.000]
[0.988 + 0.00]
[0.502 = 0.000]
10
0.975
0.982
0.498
0.056
7
10a
0.977
0.987
0.501
0,223
10a
0.977
0.987
0,503
0.467
10"
0.977
0.987
0,502
0,693
7
10a
0.977
0.987
0.501
0.871
10t
0.977
0.987
0.501
1.0 (434802]
7
[0.976 + 0.000]
[0.987 + 0.002]
[0.501 +: 0.002]
obtained in each Ab-i) used in the respective normalization. Firstly, observe that the obtained P, R. and are robust to various choices of hyperparameters, with minor deviations for mcs = 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 not only significantly reduces the number of edges GDD but also does not affect the obtained scores. This empirically shows that the edge filtering, introduced in Section 3.22 correctly removes unstable edges that are not significant for the correct manifold estimation. We observe similar result in Ab-3) (bottom rows), where increasing the number of sampled rays T naturally increased the number found Delaunay edges, while again not affecting the resulting scores except for the minor decrease in of the extremely low T 10. These result show the reliability both our manifold approximation using Delaunay graphs and the introduced edge filtering using B, well the stability of our DCA scores.
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 Gp), distilling 9D into the distilled Delaunay graph GDD (distill GpD) 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, see that in Ab-3) increasing naturally increases the time necessary for the approximation of GD and consequentially the time needed distill GD and analyze GDD- For clarity, report the actual elapsed time seconds for columns distill Gp and analyse IDD because the potentially misleading percentage obtained from the large normalization constant (column total).
DCA RUNTIME:
18

---

Table 6: Empirical runtime of the main components of DCA algorithm obtained when varying mcs in experiment Ab-l) (top rows), sphere coverage parameter B in Ab-2) (middle rows) and num- ber of sampled rays T in Ab-3) (bottom rows). For each experiment Ab-i), we report the elapsed time normalized by the total elapsed time per experiment of the following implementation parts: ap- proximation of the Delaunay graph GD (column approx. GD). filtration of GD using sphere coverage parameter B (filter GD). distillation of GD into the distilled Delaunay graph GDD (distill Gnn) and analysis of connected components obtained Gnn (analyse GDD). For columns distill GnD and analyse GDD in Ab-3), additionally report in square brackets the actual elapsed time alleviate the effects of the large normalization constant. Finally, we report the total time elapsed in seconds (total) for each experiment in Ab-i).
APPROX. Gn [%]
FILTER GD [%]
DISTIL GD [%6]
ANALYSE GDD [%]
TOTAL [s]
3
0.852
0.046
0.029
49.6
5
0.837
0.054
0.032
50.4
mcs
10
0.841
0.054
0.029
50.2
20
0.841
0.051
0.031
50.2
0.5
0.748
0.151
0.028
0.046
57.1
0.724
0.169
0.031
0.048
59.0
0.7
0.732
0.155
0.033
0.050
58.4
B
0.8
0.715
0.155
0.037
0.058
59.7
0.9
0.699
0.150
0.043
0.069
61.1
1.0
0.729
0.084
0.109
58.6
10
0.792
0.085 [0.28s]
0.060 [0.19s]
3.2
10a
0.622
0.114 [.566s
0.094 [0.46s]
4.9
10a
0.601
0.126 [1.0a
0.084 [1.00s]
12.0
T
10
0.854
0.043 [2088
0.028 [1.77s]
48.1
10S
0.975
1
0.008 [..2a
0.004 [1.80s]
422.6
10
0.997
0.001 4.39s)
0.001 [2.00s]
4157.8
Table 7: The mean and the standard deviation of the lengths of homogeneous edges among points in R and among points in E per truncation level sb.
0.0
0.1
0.2
0.3
0.4
0.5
30.07 + 6.29
30.11
6.34
30.22 + 6.37
30.35 + 6.41
30.48
6.45
30.47 + 6.55
E
7.25 + 0.85
9.76 + 1.44
12.96 + 2.50
15.96 + 3.29
18.37 + 3.78
20.28 + 4.09
0.6
0.7
0.8
0.9
1.0
R
30.53 1 6.62
30.40 1 6.59
30.21 1 6.66
29.97 + 6.61
29.71 1: 6.53
E
21.91 1 4.44
23.32 4.72
24.74 1 4.98
26.13
5.26
27.41 1 5.44
B.2 ADDITIONAL. EVALUATION OF STYLEGAN
In this section, we present 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.I
Investigation the geometry of R and points obtained in Section 4.2 Firstly, we additionally verified the correctness of the obtained DCA scores for each truncation level v by investigating the average length homogeneous edges among It 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 increases with increasing & and resembles the average length of the homogeneous edges among R for 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.
1.0. This analysis suggests that the StyleGAN model was
19

---

Next, performed series of further experiments to investigate the decrease in 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 F = R((s = 0.5) and b) R = R( = 0.4) and F. (iyh 0.5), where we denoted by, e-g., R(gh = 0.4). the set R obtained at truncation level u = 0.4 in Section 4.2] In a), we obtained that P = 0.98, R = 0.98 and = 0.55 indicating no irregularities in the set R(v 0.5) of sampled training image representations, while in b) we obtained p- = 0.52, R 0.05 and = 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(yh = 0.5).
Next, in order to verify that R and F. were formed in specific geometric arragenment similar to that depicted in Figure 2 we additionally analyzed the minimum spanning tree GS)(Gp) obtained from the approximated Delaunay graph 9D built on the sets = R(vb = 0.5) and F E( = 0.5). Recall that G)) 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 π and E)) in MST(G We obtained the average length of homogeneous edges 21.58 = 4.88 among R and 13.78 + 3.29 among E' points, while for heterogencous 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(p = 0.5). which resulted in | 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 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 Ap- pendix A and Section using nigh-dimensional representations of training and generated images obtained from the VGGT6 model, and show that our algorithm is robust to their choices. As in Section B.T we performed an ablation study on Ab-1) HDBSCAN min cluster size mes 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 1)c = 0.0 and 77 = 0.0 as done in Section 4.2 We always fixed T = 10a in the approximation of Gp. B = 0.7 and msc = 10 for HDBSCAN except in Ab-l) where we varied msc E {3. 5, 10, 20). in Ab-2) where we varied B E {0.5, 0.6, 0.7, 0.8, 0.9, 1.0), and in Ab-3) where we varied T E {10, 10? 10a, 10², 10%).
We measured the stability of our precision P. recall R, network quality q for each experiment Ab- i) 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 mes affects the number of edges in GDD because of the definition of outlying points by HDBSCAN.
The results are shown in Table 3 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 the P, R values obtained in Ab-/) when varying mes parameter (top rows). However, such variations are expected due to the nature of the mes parameter, which directly affects the obtained connected components. Increasing mes naturally yields more outliers or components of lower quality, which can be seen in the decrease of the P, R values for mes = 10 and mcs = 20. We emphasise that the
20

---

network quality remains unaffected and exhibits low std. In Ab-2) (middle rows), 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 7 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 introduced edge filtering using B.
Table DCA ablation results for StyleGAN obtained when varying mcs experiment Ab-1) (top rows), sphere coverage parameter B in Ab-2) (middle rows) and number of sampled rays T in Ab- 3) (bottom rows) as described in Section B.2, For each experiment Ab-i), we report in columns the obtained precision P, recall R, network quality g()), percentage of edges normalized by the maximum number obtained per experiment Ab-i) (with maximum absolute value shown in square brackets).
P
R
((9)
% EDGES
3
0.992
0,970
0,494
1.0 [47093874]
5
0.954
0.900
0,495
0.896
TTCCS
10
0.564
0.469
0,493
0,293
0.564
0.469
0,493
0,293
[0.768 4: 0.237]
[0.702 + 0.271]
[0.494 + 0.001]
0.5
0.564
0.469
0.490
0,375
0.6
0.564
0.469
0,492
0.537
0.7
0.564
0.469
0,493
0.709
0.8
0.564
0.469
0.493
0.859
0.9
0.564
0.469
0.493
0.954
1.0
0.564
0.469
0.4932
1.0 [13784316]
[0.564 1: 0.000]
[0.469 +: 0.000]
[0.492 1: 0.001]
10
0.592
0.486
0.471
0.002
10a
0.478
0.376
0.479
0,011
10a
0.563
0.469
0,487
0.086
10
0.563
0.469
0.493
0.307
10a
0.563
0.469
0.496
0.673
10c
0.564
0.469
0.497
1.0 [44866410]
[0.553 + 0.041]
[0.456 + 0.040]
[0.487 0.010]
B.3 REPRESENTATIONS SPACE OF VGG16
In this section, further describe the experiments performed to analyze the representation space of a VGG16 model (Simonyan & Zisserman 2013) pretrained on the ImageNet dataset (Deng et al.) 2009). We present the results obtained by repeating the experiment investigating separability of classes performed by Pokkukar et al. (202I) and show additional examples of images analyzed in Section 4.3 where we applied qCDCA investigate whether the limited class separation originates from inadequacies of the model or human labeling inconsistencies.
We used the same representations Poklukar et al. (202T) who constructed R and E from repre- sentations 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 random.
Class separability We analyzed the distilled Delaunay graph G GDD E) built on the sets R and É in each version. In Table we report the DCA scores, the relative size of the largest connected component Go (normalized by IRU. E') and the total number of non-trivial components denoted as # non-trivial. In version 1, we observed one large connected component containing z 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 F.) contributing to the network quality (9)) were contained in the first component. A relatively
21

---

comp. idx
comp.
idx 2
comp. idx 3
comp. idx
version
version
Figure 11: Examples of images contained in three non-trivial E components obtained in version (marked with blue) and in the single non-trivial E component obtained in version 2 (marked with green).
large R. 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 [9ol] and (9)) increased compared to version 1 indicating that points R and 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 ((g) score. Moreover, we observe larger P and lower R compared to version 1 which means that more E but less R points due to the random choice. Interestingly. by visual inspection (see example images Figure [ we that all non-trivial E components both versions consist of individual dog breeds suggesting that features representing dogs might be easier for the network to distinguish.
contained in the largest component
For comparison, included GeomCA scores reported by Poklukar et al., (2021). We emphasise two main differences in the interpretation of the results: i) their network quality and consistency scores are affected by the sparsification process, while ours reflect the structure of the original sets R and E, ii) their absolute values of ', R and [ool] are substantially lower than ours which is the result of lower number of edges obtained GeomCA. For example, the ratio of the number of edges over the number of nodes in version resulted in 0.006 in GeomCA and 673.5 in DCA. This also indicates that E-edges constructed based on maximum Euclidean distance are not as expressive in higher dimensions Delaunay ones, which is also seen from higher number of smaller non-trivial connected components obtained in GeomCA.
DCA scores (top row) obtained on VGG16 representations of ImageNet images from ver- sion (kitchen utilities vs dogs) and version (random) compared with GeomCA scores (bottom row). For each method, cision P, recall R. the relative size |9ul y of the largest component normalized by the total number of points in R U E and lastly, the total number of non-trivial connected components (# non-trivial).
Table 9:
report in columns network consistency c(G), network quality (G), pre-
VERSION
<(G)
v())
p
R
# NON-TRIVIAL
1
0.98
0.31
0.4975
0.7247
0.610
DCA
2
1.0
0.42
0.6551
0.6302
0.640
1
0.75
1.00
0.0042
0.0130
0.004
7
GEOMCA
2
0.98
1.00
0.0423
0.0391
0.023
25
Amending labelling inconsistencies We show additional examples of images supporting the ex- periment performed in S.. 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 inconsisten- cies 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 GDD U E) using G-DCA extension.
22

---

query point
closest R point
query point
closest R pointl
5
clear
semantic
connection
IOMA
similar pattern, background or structure
T010
similar semantic information
versinn
version
Additional examples of query images (odd columns) and their corresponding closest R images (even columns) taken from version (left) and version 2 (right).
Figure 12:
This approach resulted 87.6% accuracy version 1, and 90.3% version 2, providing interesting insights into the nature of both human labeling and structure of the VGG16 representation space. In Figure we show examples of query images (odd columns) and the corresponding closest image in (even columns) having different labels corresponding to version (left, blue) and version 2 (right, green). Similarly as Figure 8, the first row shows examples of pairs of images considered close by VGG16 despite 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 diffferent labels. The last 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.
23


Reviews:
[{"review_id": "wD9rRgKiTx2", "reviewer": "Reviewer_vfbH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros. \n- The paper is very well written and well motivated (especially the parts that show difficulties with GCA and prior methods)\n- I find the evaluation to be comprehensive, especially the analysis in Section 4.\n\n\nCons (minor)\n- (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. \n\n- The complexity of constructing the delaunay graph in high dimensions can be a computationally expensive affair.\n", "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). \n\nThe 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. \n\nThe 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.\n\nThe 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.\n", "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. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KjlorHeiQUE", "reviewer": "Reviewer_vso9", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Novelty and contribution:\n- 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. \n- 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). \n\nPresentation:\n- The overall presentation is adequate, but not always perfectly clear/easy to follow.\n- 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.\n- The presentation would benefit from a brief, rigorous problem formulation paragraph at the beginning of Sec. 2. \n- 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.\n\nMethod and results:\n- The motivation of the method is clear and it is technically sound. \n- 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).\n- 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?\n- 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}? \n\nMinor comments:\n- It is not clear from the paragraph \"Phase 2\" alone, whether HDBSCAN has additional tunable parameters, please add a short clarification.\n- 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.\n- Figure captions are generally not sufficient to interpret the figures throughout the paper.\n- 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.\n- Similar issues with Fig. 9 and Fig. 10 of the appendix. \n\n=============================================================================================\n\nPost discussion:\nReading 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "C7AAYcgbiVH", "reviewer": "Reviewer_JKBs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros: (appearing in random order)\n\n- 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.\n\n- 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.\n\n- 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.\n\n\nCons: (appearing in random order)\n\n- 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?\n\n- 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.\n\n- 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.\n\n- 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}$.\n\n- 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. \n\n- (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?\n\n- (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?\n\n\n\n", "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.\n\nThe 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\net 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.\n\n ", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)