Measuring Diversity: Axioms and Challenges
Authors: Mikhail Mironov
Liudmila Prokhorenkova
Venue: ICML 2025 poster (2025)
Keywords: diversity measure
desirable properties
axiomatic approach
Primary area: theory
TL;DR: We formulate three desirable properties of a good diversity measure, show that none of the existing measures has all these properties, and pose an open problem of constructing a measure that has these properties while being computationally feasible.

Abstract: This paper addresses the problem of quantifying diversity for a set of objects. First, we conduct a systematic review of existing diversity measures and explore their undesirable behavior in certain cases. Based on this review, we formulate three desirable properties (axioms) of a reliable diversity measure: monotonicity, uniqueness, and continuity. We show that none of the existing measures has all three properties and thus these measures are not suitable for quantifying diversity. Then, we construct two examples of measures that have all the desirable properties, thus proving that the list of axioms is not self-contradictory. Unfortunately, the constructed examples are too computationally expensive (NP-hard) for practical use. Thus, we pose an open problem of constructing a diversity measure that has all the listed properties and can be computed in practice or proving that all such measures are NP-hard to compute.

Measuring Diversity: Axioms and Challenges
Mikhail Mironov
Liudmila Prokhorenkova'
Abstract
synthetic data in augmentation (Mumuni & Mumuni, 2022).
Thus, being able to quantify diversity is important.
This paper addresses the problem of quantifying diversity for a set of objects. First, we conduct systematic review of existing diversity mea- sures and explore their undesirable behavior in certain cases. Based on this review, we formulate three desirable properties (axioms) of reliable diversity measure: monotonicity, uniqueness, and continuity. We show that none of the existing measures has all three properties and thus these measures are not suitable for quantifying diversity. Then, we construct two examples of measures that have all the desirable properties, thus proving that the list of axioms is not self-contradictoryy Unfor- tunately, the constructed examples are too compu- tationally expensive (NP-hard) for practical use. Thus, we pose an open problem of constructing a diversity measure that has all the listed properties and can be computed in practice or proving that all such measures are Na-hard to compute.
Traditional methods of assessing diversity may differ across domains and tasks. In the image generation domain, diver- sity ensures that at least some of the generated images can fit a user's s preference. The average of pairwise distances be- tween the output images is commonly used as a measure of diversity. For instance, Ruiz et al. (2023) compute diversity as the average L.IPS similarity between the output objects, while Saharia et al. (2022) compute the average pairwise SSIM between the first output sample and the remaining samples. Similarly, in recommender systems, diversity en- sures that at least some of the model outputs can fit user's s preference. The average pairwise distance between the out- puts is a popular diversity measure in this domain (Alhijawi et al., 2022). Another way of assessing diversity is via the determinantal point process (DPP) approach that defines diversity the determinant of the similarity matrix (Wil- helm et al., 2018). In the molecule generation domain, the typical task is to generate a diverse collection of molecules with some predefined properties. The underlying goal is to explore the whole space of such possible molecules and pick the best candidates, so diversity of the output collection en- sures that generated molecules are not clustered in one area, while other areas are unexplored. A common diversity mea- here is also the average pairwise distance between the outputs (Du et al., 2022), although sometimes the percent- age of unique generated molecules is reported (Hoogeboom et al., 2022). Finally, in a recent paper on generating struc- turally diverse graphs (Velikonivtsev et al., 2024), new measure called energy is proposed as a better and more reliable alternative to the average pairwise distance.
1. Introduction
Diversity of a collection of objects is concept that is widely used in practice: image generation models are required to generate diverse sample of images for a given prompt, recommender systems are required to output a diverse set of suggestions for a query, molecule generation models often aim at generating collection of structurally diverse molecules with given property. Diversity can also play an important role in assessing how representative given dataset is, c.g., in molecule generation (Xie et al., 2023) or neural algorithmic reasoning (Veličković & Blundell, 2021; Mahdavi et al., 2023); and Zhao et al. (2024) argue that is critical to provide a clear definition of diversity when analyzing datasets. well-defined diversity measure also ensures informative sample selection in active learning (Ren et al., 2021) or may guide the generation of meaningful
Note that in all the examples above, diversity can also be thought of as coverage: the goal is to cover different areas of the space of potentially valid outputs. Thus, in this paper, we use the terms diversity and coverage interchangeably. In the literature, there have been a few attempts to analyze, compare, or suggest better measures of diversity (Xie et al., 2023; Friedman & Dieng, 2023; Velikonivtsev et al., 2024). However, as show in this paper, the problem is still underexplored.
Yandex Research. Correspondence to: Mikhail Mironov <mironov.m.ke wwg.mlll.com........... <ostroumova @ la yandex--neaaee team.ru>.
Liudmila Prokhorenkova
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
We limit the scope of our research to the following setup: we are given a collection of abstract objects and their pairwise

---

Measuring Diversity: Axioms and Challenges
distances (or pairwise similarities). We define a diversity measure function that takes this collection an input and returns some value as an output.
Table 1. Known diversity measures
Measure
Formula
First, we examine the existing diversity measures by pro- viding examples of their undesirable behavior. Namely, we show that existing measures may either lead to unexpected results when comparing diversity of two datasets (i.e., as- signing a higher score to a clearly less diverse dataset) or lead to degenerate solutions when being optimized. Moti- vated by these observations and previous studies on diversity, we formulate three properties (axioms) that a good diversity measure should have. Monotonicity requires that increasing pairwise distances between the objects increases diversity value. Uniqueness requires that having duplicate in the col- lection is worse for diversity than having any non-duplicate object instead. The last property is continuity, which re- quires diversity to be a continuous function of pairwise distances. We check which of the existing measures possess which properties, and find that none has all three. Then, we prove that the list of axioms is not self-contradictory by con- structing two examples of measures that satisfy all of them. Unfortunately, the proposed measures are too computation- ally expensive (NP-hard) be used in practice. Finally, we discuss why finding diversity measure that has all three desirable properties and is computationally manageable is a non-trivial task. We leave the question of whether there exists a computationally fcasible measure satisfying all the required axioms for future studies.
Average
k(n-1) 1]
Σ dj
SumAverage
Σ de
Diameter
max de 1<3
SumDiameter
Σ max dej y7t
Bottleneck
min dig
SumBottleneck
Σ min da
8 1 m(n-1)
Energy(1),
Σ d
#Circles(f),
max O m
C s.l. dystVifjee
Unique
max
C
s.L. dysoVVeeje
CCM
HamDiv
length of the shortest Hamiltonian circuit
Vendi Score
exp
>, log(A.)
DPP
det(s)
RKE
log
12?
T
Species(g).
Σ
Σ
81j
refer to this measure as HamDiv.
The remaining four measures are defined in terms of pair- wise similarities sij instead of pairwise distances. All these measures require Sty to be positive semi-definite similarity function and usually require 8;; = 1. Vendi Score is pro- posed by Friedman & Dieng (2023) and is calculated via the formula specified in Table 1, where Az...., An are the eigenvalues of the scaled similarity matrix S/n and S is the n n matrix with entries 8ij- The simplest Das-based measure is computed as the determinant of the similarity matrix S.! The Rényi Kernel Entropy Mode Count (RKE) is proposed by Jalali et al. (2023) and is defined as the negative logarithm of the average squared similarity. Finally, diver- sity of order q is proposed by Leinster & Cobbold (2012) to measure the diversity of a population consisting of several species. In our work, we refer to this measure as Species( (q). Here, the parameter q any nonnegative number not equal to 1. When applied to our setup (all elements having equal weights), the measure Species(g) can be written as specified in Table 1 (up to constant multiplier).
2. Measuring Diversity
In this section, we describe existing diversity measures. We assume that we are given a collection of n (possibly du- plicated) objects X = (xi,..., (nn and pairwise distances (dissimilarities) between them such that diz 2 0 and d, = 0 iff æ; and zy coincide. To maintain generality, we do not require the triangle inequality to be satisfied by dij.
Table lists existing diversity measures that cover in our study. As discussed above, arguably the most straight- forward and widely-used way to quantify diversity is via the average pairwise distance between the elements. Other simple alternatives are the minimum and maximum pairwise distances (often referred to as Bottleneck and Diameter, re- spectively). Xie et al. (2023) argue that none of the simple measures suitable for diversity quantification and pro- pose #Circles(!)) which is defined as the maximum number of non-intersecting circles of radius t/2 (for some t > 0) with centers at some elements of X. A measure called Energy(7) is proposed by Velikonivtsev et al. (2024) as a better alternative to the above measures. For 7 1, this measure equals the energy of system of equally charged particles. Hu et al. (2024) propose measuring diversity the length of the shortest Hamiltonian circuit; we further
Some previous works on measuring diversity analyze and compare measures based on properties they do or do not satisfy. We review these works in Section 4.4.
'In practice, more complex based diversity measures can be used (Wilhelm et al., 2018). For instance, when such measures are applied to recommender systems, the relevance scores of ob- jects w.r. user queries usually mixed into the similarity matrix, which we do not do here since we only consider diversity.
2

---

Measuring Diversity: Axioms and Challenges
Finally, there is rich literature on submodular functions that also be used to quantify diversity (Bilmes, 2022). However, submodular functions are not defined in terms of pairwise distances and thus are out of scope of our study. Also, some known submodular functions assume that we are provided with a set (space) of all possible objects and can sum, integrate, or iterate over all them. This assumption quite restrictive and our framework does not rely on it.
Average and SumAverage Since Average and Sum- Average differ only by constant factor, consider them together. Consider two configurations of 16 points in the unit square with Euclidean distance, as illustrated in the figure below (in the configuration on the left, each of the square's s corners contains 4 coinciding points). For the left configuration, Average equals 0.91, which is the maximum value among all possible configurations. For the right config- uration, Average equals 0.71. Since the right configuration is intuitively more diverse, this example shows undesirable behavior of Average w.r.t. both comparison and optimiza- tion. Informally, maximizing Average pushes all points to the boundary of the space, leaving central areas empty.
3. Drawbacks of Popular Diversity Measures
In this section, we discuss why none of the measures defined above can be reliably used to quantify diversity. For this, we show intuitive examples of an undesirable behavior for each measure. These examples serve as the main motivation for our research and for the axioms choose.
We start by discussing two usage scenarios of diversity mea- sures. First, diversity measure can be applied to given dataset to quantify its diversity. Thus, it should be able to identify which dataset is more diverse. For instance, when choosing between two recommendation algorithms, one can be interested comparing the diversity of the retrieved sets of items. Second, diversity can be used goal of an opti- mization process. For instance, Velikonivtsev et al. (2024) generate sets of graphs that are maximally diverse and for this purpose, the authors iteratively modify the set of graphs by accepting modifications that improve a given diversity measure. Thus, a good diversity measure should lead to diverse configurations of elements when being optimized.
Average: 0.91
Average: 0.71
SumAverage: 14.57
SumAverage: 11.42
Diameter and SumDiameter Consider two configura- tions of 16 points in the unit square as shown below (in the left configuration, two of the square's corners contain 8 coinciding points each). Diameter for both configura- tions equals 1.41, which is the maximum value among all possible configurations. Since the right configuration intuitively more diverse, this example shows undesirable behavior of Diameter w.r.t. both comparison and optimiza- tion. Note that once configuration contains two points the maximum distance from each other (in our case 1.41), the positions of all other points do not influence Diame- ter. While SumDiameter is expected to be a better diversity measure (it takes more distances into account), the same example demonstrates undesirable behavior w.r.t. com- parison and optimization since the left configuration has the maximum possible SumDiameter value. Indeed, if there are points I and with the maximum distance between them, we can make all other points coincide with Tq or I2, thus maximizing SumDiameter.
Below examine the diversity measures listed in Table from these two perspectives: comparison and optimiza- tion. We say that measure exhibits undesirable behavior w.r.t. comparison if there exists a pair of datasets, such that the first one is more diverse according to our intuitive per- ception of diversity, yet the diversity measure assigns the higher value to the second one. We say that a measure ex- hibits undesirable behavior w.r.t. optimization if the dataset with the maximum diversity according to this measure is not maximally diverse according to our intuitive perception of diversity. Note that if a measure exhibits undesirable behav- ior w.r.t. optimization, it also exhibits undesirable behavior w.r.t. comparison. Indeed, if a measure assigns the highest value to some intuitively non-diverse set, this means that assigns a lower value some set that more intuitively diverse, thus exhibiting undesirable behavior w.r.t. compar- ison. The opposite is not necessarily true: some measures can be suitable for optimization while being unable to reli- ably compare two non-optimal configurations.
Note that we limit our research to the simple case when the number of elements n fixed; thus, in the examples below all the configurations are of the same size.
Diameter: 1.41 SumDiameter: 22.63
Diameter: 1.41
SumDiameter: 19.04
3

---

Measuring Diversity: Axioms and Challenges
Bottleneck Bottleneck assigns any configuration without duplicates higher diversity value than any configuration with duplicates. Consider two configurations of 16 points in the unit square (in the right configuration of the figure below, the bottom-left corner contains 2 coinciding points). For the left configuration, Bottleneck equals 0.11, and for the right configuration, Bottleneck equals O. Since the right configuration is intuitively more diverse, we see undesirable behavior of Bottleneck w.r.t. comparison.
#Circles(1) To use this measure for reasonable compar- ison of two collections, priate value of t. Indeed, if t is too high, both collections will have diversity equal to 1, and if is too low, both col- lections will have diversity equal to their numher of unique elements. This complicates the use this measure for both comparison and optimization. Also, this measure is discrete and thus difficult optimize. Finally, computing the value of this measure NP-hard, which makes impractical.
needs to determine appro-
Unique Since this measure does not take into account pair- wise distances between objects, it is essentially unsuitable for comparison or optimization. Indeed, all collections with pairwise distinct objects have the same diversity value
HamDiy Similar to #Circles(t), the value of Him is NP-hard to compute, which makes it impractical. Addition- ally, this measure is insensitive to increases in any pairwise distances that are not part of the shortest Hamiltonian cir- cuit, making it unsuitable for comparison. To illustrate its undesirable behavior w.r.t. optimization, consider the fol- lowing example. Take two configurations of 4 points on the line segment [0, 1]: the first is O, 0, 1, 1, and the second is 0, 1 2 1. Both configurations have HamDiv equal to 2, 3 3
Bottleneck: 0.11
Bottleneck: 0 Energy(1):
Energy(1): -5.05
SumBottleneck To lesser extent, SumBottleneck has similar drawbacks to Bottleneck. Consider two configura- tions of 16 points in the unit square (in the left configuration, 15 points coincide corner of the square, and in the right configuration, each point has one duplicate). For the left configuration, SumBottleneek equals 0.1, and the right configuration, SumBottleneck equals O. Since the right con- figuration is intuitively more diverse, we see undesirable behavior of SumBottleneck w.r.t. comparison.
which is the maximum possible value. However, the first collection intuitively less diverse than the second.
HamDiv=2
HamDiv=2
Vendi Score Consider points circle with cosine sim- ilarity. Suppose the points 21, 222 3y are arranged in this order on the circle; the distance from Ij to x2 is 0.6 radians, and the distance from T2 to Ey is 1.4 radians. Now, we move T3 by 0.1 radians further away from 21 and Zz.. Intu- itively, we expect that decreasing the similarity between a3 and the other elements should increase diversity. However, the Vendi Score decreases from 1.941 to 1.916, which is an example of undesirable behavior w.r.t. comparison.
SumBottleneck: 0.1
SumBottleneck:
Energy(7) The drawback of this measure is that in the presence of duplicate, it takes the value oo and is insen- sitive to all other pairwise distances. The same example as for Bottleneck demonstrates undesirable behavior of Energy w.r.t. comparison.
X3
1.4
1.5
X2
X2
0.6
0.6
Note that the examples for Bottleneck, SumBottleneck, and Energy demonstrate their undesirable behavior only w.r.t. comparison. Intuitively, all these measures behave well w.r.t. optimization since maximizing them enforces a more uniform distribution by pushing away the closest ele- ments (the examples for Energy optimization can be found Velikonivtsev et al. (2024)).
X1
X1
Score: 1.941

---

Measuring Diversity: Axioms and Challenges
DPP
Consider two positive semidefinite symmetric matri-
2. if des then Wk: dis djti
ces:
3. Vi,j daj = dje.
0.2
0.6
0.3
0.6
S=
0.2
1
0.7
$=
0.3
1
0.7
In terms of objects, the first property requires that the dis- tance between any two objects is nonnegative, and distance from object to itself is O. The second property requires that if two objects coincide, then they must have equal dis- tances to any other object. The third property is symmetry of distance. Note that for generality, we do not require the triangle inequality to be satisfied by dij.
0.6
0.7
1
0.6
0.7
1
The matrices S and S differ by an increase in $12 (and symmetrically 821) from 0.2 to 0.3. Intuitively, we ex- pect that increasing similarity between any two elements must decrease diversity. However, det(S) = 0.278 and
(S) = 0.312 > 0.278, which an example of undesir- able behavior of the DPP-based measure w.r.t. comparison.
A diversity measure is a function that takes as input any such set of n objects and their pairwise distances and out- puts real number. We assume that diversity depends only distances dy and does not depend the nature of the objects z; itself. Thus, the input of our function can be fully described as an n. X n matrix D with entries dej. Denote by Dn a subset of all n x n matrices satisfying the three properties described above. Then, the diversity function is a function from D,, to R. Since diversity usually measured for multiset of objects, we also require permufation in- variance: if we permute (or rename) the objects in X (with correspondingly permuting the rows and columns of D), the value of diversity should not change. Thus, we get the following definition.
RKE and Species(g) Consider points a circle with cosine similarity (see the figure below for an illustration). Suppose the points 21. I2, I3 are arranged in this order on the circle; the distance from 21 to 22 is 1.1 radians, the distance from T2 to 23 is 0.4 radians. Now, we make T2 a duplicate of æ3- Intuitively, we expect that such a change should decrease diversity. However, RKE increases from 0.564 to 0.584, which is an example of undesirable behavior w.r.t comparison. The same example illustrates undesirable behavior w.r.t. comparison for Species(g) for various (see Appendix B).
Definition 4.1. A diversity function is a permutation- invariant function from D,, to TR.
X3
X2, X3
X2
0.4
1.5
Note that we assume the number of elements n to be fixed, Thus, we do not aim to determine how diversity should behave when the size of the dataset changes. Our paper shows that even for this (simpler) case it is non-trivial to construct a suitable diversity measure.
1.1
X1
X1
4.2. Axioms for Diversity
RKE: 0.564
RKE: 0.584
In this section, we formulate three axioms that we require for a reliable diversity measure.
4. Axiomatic Approach to Diversity Measures
Axiom 1 (Monotonicity). A diversity function must be strictly increasing w.r.t. all its arguments.
Motivated by our analysis in Section 3, we formulate list of properties (axioms) that a reliable diversity measure is expected to satisfy. First, we formally define diversity mea- sures, then formulate their desirable properties and discuss which existing measures have which properties, and finally review desirable properties suggested in previous studies and discuss how they relate to our setup.
In other words, if we increase one or several pairwise dis- tances while keeping all other distances fixed, the value of diversity must increase. This axiom is natural since it repre- sents the meaning of diversity: the more objects 21,..., Zn differ from each other, the greater diversity we expect. This property is analogous to monotonicity in Velikonivtsev et al. (2024), but has one important difference: we do not require the objects in X to be pairwise distinct for monotonicity to hold. This difference critical for being able to compare datasets: we want be able to tell which configuration is more diverse even if the datasets have duplicates. Otherwise, we may get a measure with undesirable behavior, as shown by the example for Bottleneck and Energy in Section 3.
4.1. Formal Definition of Diversity Measure
Assume that we are given a collection of n (possibly du- plicated) objects X = (#1,..., 2n) and pairwise distances between them dy satisfying the following conditions:
1. Vi,j dy 2 and Vi: dę = 0:
5

---

Measuring Diversity: Axioms and Challenges
Axiom 2 (Uniqueness). Suppose we are given two collections of objects (and their pairwise distances) which differ only by one element: .......,nnn11.. Zn and I1... 21....,,n-1... 1n- x'x Suppose th coincides with at least one of .1....., En-1, while In does not coincide with any of Then, the diversity of the first collection must be higher than that of the second collection."
4.4. Desirable Properties in Previous Works
Several papers analyze and compare diversity measures in terms of properties they do do not satisfy. For instance, Xie et al. (2023) formulate three axioms. The first one requires that diversity of union of two sets must be higher than the diversity of each of them. The second requires that diversity of a union of two sets should be at most the sum of their diversities. Note that both of these axioms constrain the behavior of diversity when the number of objects changes and thus do not apply in our setting with fixed number of objects. The last axiom requires that if we have only two objects in X, then diversity must be strictly monotone w.r.t. the pairwise distance between these objects. Note that our monotonicity requirement generalizes this axiom.
This property reflects our intuition that having duplicate (i²)) in the multiset is worse for diversity than having a unique element (zx) instead. Informally, we can say that having zn, does not help the multiset cover any new part of the space since copy of ai, is already present, while having Tn covers some area. Uniqueness allows one to avoid an undesirable behavior when the collection with duplicates has higher diversity than an intuitively more diverse collec- tion without duplicates or even when the maximum diversity is achieved by a degenerate configuration (which happens to Average and Diameter, as shown in Section 3). Note that, unlike the analogous property in Velikonivtsev al. (2024), our variant of uniqueness does not require all objects in X to be distinct. Similar to considerations for monotonicity, this modification is important for being able to compare datasets even when they have duplicated elements.
Friedman & Dieng (2023) propose Vendi Score and list four of its properties. One of the properties is called symmetry and it is equivalent to our permutation invariance that we require for all diversity measures. Another property requires that a diversity measure is maximized when all pairwise sim- ilarities are 0 and minimized when all pairwise similarities are 1. This property is generalized by our monotonicity axiom. The remaining two properties consider weighted elements or samples of different sizes and thus do not apply to our setup.
Axiom 3 (Continuity). A diversity function must be contin- nous.
Velikonivtsev et al. (2024) address the problem of generat- ing structurally diverse graphs and discuss what measures of diversity are suitable for optimization. The authors for- mulate two properties: monotonicity and uniqueness that are slightly weaker variants of the corresponding properties in our work (as discussed above in Section 4.2).
This property was not present in previous works, but it is natural to require, and we find it critical for reliable diver- sity measure. Indeed, in Appendix A.2 we show that there are examples of discontinuous functions that satisfy mono- tonicity and uniqueness while still exhibiting undesirable behavior. Thus, having only monotonicity and uniqueness insufficient.
Leinster & Cobbold (2012) list several groups of properties of Species(g). Partitioning properties do not apply to our case since we consider the diversity only for fixed number of objects. From the Elementary properties group, Symme- try corresponds to our requirement for diversity functions to be permutation invariant, and the properties Absent species and Identical species do not apply to our case (since we consider objects with equal weight and not n probabilities summing to 1). From the group of properties named Effect of species similarity on diversity, the only property applica- ble in our case is Monotonicity, which is equivalent to our monotonicity axiom.
4.3. Properties of Existing Measures
Table 2 shows which axioms are satislied by the existing measures listed in Table (the proofs can be found in Ap- pendix B). It can be seen that none of these measures has all three desirable properties.3 This leads to the main question of the paper: does there exist diversity measure with all three desirable properties? In the next section, we construct two examples of such measures, thus giving a pos- itive answer to this question. We include these measures as well as the computational complexities of all the measures in Table 2.
To sum up, among the properties from previous works, the ones applicable in our setting are monotonicity (in stronger form from Velikonivtsev et al. (2024) and Leinster & Cob- bold (2012) or weaker forms from Xie et al. (2023) and Friedman & Dieng (2023)) and uniqueness, given that per- mutation invariance is already incorporated in our definition of a diversity function.
FFor simplicity, we formulate this property in terms of objects, but it can be straightforwardly reformulated in terms of pairwise distances, see Appendix A.
NNoe that Energy was reported in Velikonivtsev et al. (2024) as having monotonicity and uniqueness, but it does not in our case since we have stronger versions of these properties that require them to hold even in the presence of duplicated elements.
6

---

Measuring Diversity: Axioms and Challenges
Table Properties of diversity measures
Measure
Monotonicity
Uniqueness
Continuity
Complexity
Average
(
SumAverage
(n
Diameter
O
SumDiameter
X
O
Bottleneck
X
X
(
SumBottleneck
X
(n²))
Energy(1), 7 >
(n²)
#Circles(t).. t
X
NP-hard
Unique
X
(n)
HamDiv
NP-hard
Vendi Score
X
(n
DPP
X
(
RKE
Onn²)
Species(4)
O(n²)
MultiDDm Volume
NP-hard
IntegralMaxCliqee
NP-hard
5. Diversity Measures with All Desirable Properties
maximum clique in a graph, and this problem is known to NP-hard. We refer to Appendix C for the formal proof.
Let us also note that there are multiple ways to define diversity based on the values mx(X). Indeed, can consider Σ ((mx(X)),, where f is an arbitrary contin- k=2
In this section, we construct two different examples of cormutation-nnvaiian measures that have all three desirable properties.
uous monotone function. particular, one may consider Diversity (X)
MultiDim Volume For given k. 2 k S and given submultiset K of size k of the multiset X = {.1,...,. Jn }, calculate the product of all pairwise distances between the elements of K. Note that this product equals zero at least two elements of K coincide. Then, for a given k, we take the maximum of such products over submultisets of size k of X and denote this maximum as my (X). We define the diversity of X as Σ m& (X). Putting the above into one formula, we get:
Σ (mn(X)=rn) This modification is km
natural since each summand is a product of k(k - 1)/2 terms. It follows from the proof in Appendix C that all such modifications satisfy all the desirable properties.
IntegralMaxCliquee For given threshold 2 O, we construct the following graph. The nodes are 21,... En- Two nodes x; and x are connected by edge iff d.j 2 t, and we assign dı as the weight of this edge. We find a clique (complete subgraph) in this graph with the maximum number of nodes. there are several such cliques, we pick the one with the maximum total weight of edges. For the chosen clique, calculate the total weight of its edges and denote it by w, (X). Then, define diversity
Diversity(X)
max
II
dej
(1)
KCX
KKT
Be.ty
EK
The intuition behind this formula that for a set K of size kt the product of all pairwise distances between the elements of K can be thought of as an analog of k-dimensional volume of K (analogy comes from the fact that two elements of K coincide, then the volume equals zero). Thus, mx(X) X is the maximum 'volume" of k-dimensional subset of X.
Diversity = 1 wx(X) dt.
This integral is finite since w,(X) is bounded by Σ dij-
and if > max daj, then the constructed graph has no edges Kgj and wx(X) = 0.
In Appendix C, we prove that MultiDim satisfies all the axioms. Unfortunately, computing Diversity(XX X) in Equation (1) is NP-hard since calculating MultiDim Volume allows one to solve the problem of finding the size of the
The intuition behind this formula is that we (X) can be inter- preted as the maximum diversity subset of X with the

---

Measuring Diversity: Axioms and Challenges
restriction that its elements should be at distance more from each other.
diversity of a set by updating one element time. Thus, they decompose considered diversity function into the fitness of one element and diversity of the rest of the ele- ments. Such decomposition would allow one to make quick updates of diversity (in linear time) when only one element is updated. In the proposition below, we show that for a proper diversity measure such decomposition cannot exist if we assume additive aggregation.
In Appendix D, we prove that Malegie satisfies all the axioms. Unfortunately, computing Diversity (X) in Equation (2) is NP-hard since, similarly to MultiDim Vol- ume, calculating IntegralMax.llqqee allows one to solve the problem of finding the size of the maximum clique in a graph. We refer to Appendix for the formal proof.
Proposition 6.2. Assume that a diversity function can be decomposed in the following way:
By constructing the two examples above, we prove that three desirable properties from our list do not contradict each other. Unfortunately, the constructed examples are too computationally complex for most practical applications.
Diversity (X) = F(112, d13..... dia) ) + G(12,...... .Tan),,
that is, the first term depends only on distances from one object in to all other objects, and the second term depends only on pairwise distances between the objects T2..... . Znn- Then, such a diversity function cannot sinultaneousty satisfy monotonicity, uniqueness, and continuity axioms.
6. Discussion
In the previous section, prove that the three axioms listed in Section 4.2 do not contradict each other. However, we have not been able to construct a measure that satisfies these axioms and is computationally feasible for practical application. We pose this as an important open problem to be addressed in future studies.
We prove this proposition in Appendix E.2. This is neg- ative result showing why it can be difficult to construct a proper diversity measure that is convenient for optimiza- tion. Note, however, that this proposition is only proven for the additive aggregations, thus other options are potentially possible.
Let us provide some intuition on why is hard to combine monotonicity, uniqueness, and continuity in one function. We first formulate the following proposition that shows an additional restriction that these three axioms imply.
Diversity measures in practice Let us note that even NP- hard diversity measures still be used in practice if set of items that need to be evaluated is sufficiently small. For instance, if a recommender service returns set of k = 100 items and we want to measure diversity of this set, then an NP-hard measure having all the desirable properties can potentially be used. Examples of diversity measures con- structed in Section demonstrate that there are several dif- ferent options that can be used (e.g., MultiDim Volume and IntegralMaxClique, along with their variations satisfying all the properties). We cannot rule out any of these measures based on their theoretical properties. Thus, a decision on which measure should be used may depend on a particular application. However, in this paper, we use the measures MultiDim
Proposition 6.1. Suppose a diversity function has unique- ness and continuity. Let F1,...,,2A Tyk be set of k pairwise different objects. Let C be multiset of n - k objects, each Then, diversity
of which coincides with one of ;1,..., Tg. of the multiset {E1...., U C is the same for all such C.
We prove this proposition in Appendix E.I. Informally, Proposition 6.1 states that the diversity of set does not depend on which elements are duplicated. This agrees well with our intuition: duplicates do not provide any additional elements and thus are not supposed to affect diversity. On the other hand, constructing a measure that is continuous while 'ignoring' duplicates is tricky since the object's 's prop- erty of being a duplicate is discontinuous. Indeed, we can move duplicate by any small 0 and it stops being duplicate, so our measure should no longer 'ignore' it. In MultiDim Volume, we address this problem by incorporat- ing products of pairwise distances within subgraphs: any duplicate zeros the corresponding products and thus the placement of a duplicate does not affect the result. In In- PgralMaxCliquee we use a threshold to filter out small edges, and thus duplicates do not affect the value for all 1>0 0.
and IntegralMaxx only to prove that our list of axioms is not self-contradictory. Evaluating these measures in practical applications goes beyond the scope of the current paper, which addresses the theoretical aspects of diversity measures applicable to a wide variety of scenarios.
7. Conclusion
In this paper, we reviewed existing diversity measures and demonstrated via intuitive examples that these measures cannot be reliably used for evaluating diversity. Based on these examples and previous research on diversity measures, we formulated three simple axioms (desirable properties) for a reliable diversity measure: monotonicity. uniqueness, and continuity. It turns out that none of the previously known
The next proposition states that a diversity function satis- fying all the axioms cannot be expressed in a certain form. This particular form is motivated by the approach in Ve- likonivtsev et al. (2024): the authors iteratively improve
8

---

Measuring Diversity: Axioms and Challenges
measures has all these properties. We constructed two di- versity measures that have all the desirable properties, thus proving that the axioms do not contradict each other. Unfor- tunately, the constructed examples are too computationally complex for practical use.
Leinster, T. and Cobbold, C. A. Measuring diversity: the importance of species similarity. Ecology, 93(3):477-489 2012.
Mahdavi, S., Swersky, K., Kipf, T., Hashemi, M., Thram- poulidis, C., and Liao, R. Towards better out-of- distribution generalization of neural algorithmic reason- ing tasks. Transactions on Machine Learning Research, 2023.
We leave for future research an important open problem of constructing a diversity measure that has all three desirable properties and is computationally feasible or proving that such measure cannot exist. While our study does not answer this question, we believe that it gives some important insights into measures of diversity that are frequently used in practice. Being aware of what shortcomings a particular measure has, one can use it more wisely. For instance, we cannot advise using Energy for comparing diversities of arbitrary datasets, while it can be safely used as a target for optimization.
Mumuni, A. and Mumuni, F. Data augmentation: A compre- hensive survey of modern approaches. Array, 16: 100258. 2022.
Ren, P., Xiao, Y., Chang, X., Huang, P.-Y., Li, Z., Gupta, B. B., Chen, X., and Wang, X. A survey of deep active learning, ACM Computing Surveys, 54(9): 2021.
Ruiz, N., Li, Y., Jampani, V., Pritch, Y., Rubinstein, M., and Aberman, K. DreamBooth: Fine tuning texi-to-image dif- fusion models for subject-driven generation. In Proceed- ings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 22500-2255 2023.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Saharia, C., Chan, W., Chang, H., Lee, C., Ho, J., Salimans,
T., Fleet, D., and Norouzi, M. Palette: image-to-image diffusion models. In ACM SIGGRAPH 2022 Conference Proceedings, 2022.
References
Alhijawi, B., Awajan, A., and Fraihat, S. Survey on the objectives of recommender systems: Measures, solutions, evaluation methodology, and new perspectives. ACM Computing Surveys, 55(5):1-38, 2022.
Veličković, P. and Blundell, C. Neural algorithmic reasoning. Patterns, 2(7), 2021.
Velikonivtsev, F., Mironov, M., and Prokhorenkova, L. Challenges of generating structurally diverse graphs. Advances in Neural Information Processing Systems (NeurlPS), 2024.
Bilmes, J. Submodularity in machine learning and artificial intelligence. arXiv preprint ar 202hv:2202.00132, 2022.
Du, Y., Fu, T., Sun, J., and Liu, S. MolGen: a sys- tematic survey in machine learning models for molecule design. arXiv preprint arXiv:2203.1453 14500, 2022.
Wilhelm, M., Ramanathan, A., Bonomo, A., Jain, S., Chi, E. H., and Gillenwater, J. Practical diversified recommen- dations on YouTube with determinantal point processes. Proceedings of the 27th ACM International Confer- ence on Information and Knowledge Management, pp. 2165-2173, 2018
Friedman, D. and Dieng, A. B. The Vendi Score: A diversity evaluation metric for machine learning. Transactions on Machine Learning Research, 2023.
Hoogeboom, E.,, Satorras, V. G., Vignac, C., and Welling, M. Equivariant diffusion for molecule generation in 3D. In International Conference on Machine Learning, pp. 8867-8887, PMLR, 2022.
Xie, Y., Xu, Z., Ma, J., and Mei, Q. How much space has been explored? Measuring the chemical space covered by databases and machine-generatie molecules. In The Eleventh International Conference on Learning Repre- sentations, 2023.
Hu, X., Liu, G., Yao, Q. Zhao, Y., and Zhang, H. Hamilto- nian diversity: effectively measuring molecular diversity by shortest hamiltonian circuits. Journal of Cheminfor- matics, 16:94, 2024.
Zhao, D.,, Andrews, J., Papakyriakopoulos, O., and Xiang, A. Position: Measure dataset diversity, don't 't just claim it. In International Conference on Machine Learning, pp. PMLR, 2024.
Jalali, M., Li, C. T., and Farnia, F. An cotemattion-hhereete evaluation of generative models in learning multi-moda. distributions. Advances in Neural Information Processing Systems (NeurIPS), 2023.
9

---

Measuring Diversity: Axioms and Challenges
A. Axioms for Diversity
A.1. Formal Definitions
In this section, we provide the formal definitions of the introduced axioms. Recall that diversity a function on D,.
Axiom 1 (Monotonicity). For any two matrices A, B E Dn such that Vi, aij 2 big and at least one of the inequalities strict, we have Diversity(A) Diversity (B).
Axiom 2 (Uniqueness). Suppose that for A, D,:
aij = bij for all i> 2,5 > 2;
b1j buj for all j;
a2j for all j > 2;
01j ffoor all j > 1.
Then, Diversity (A) Diversity (B).
Axiom 3 (Continuity). The space Dr is endowed with the subspace topology induced by the standard topology on the set of all matrices. A diversity function must be continuous w.r.t. this topology.
A.2. The Necessity of Continuity Axiom
Consider any measure M that is monotone (e.g., Average). Let M' be an order-preserving transformation of M whose range is [0, 1) (e.g., if M takes only non-negative values, can take MX) = 1 e-M(X)). Then, the measure (xiique(X++MCCC has both uniqueness and monotonicity, Essentially, Unique(X) (X)- compares two configurations in the following way:
Count the number of unique elements both configurations;
If the numbers of unique elements are different, then the configuration with bigger number is more diverse;
If the numbers of unique elements are the same, compare configurations based the measure M (or, equivalently, M').
We argue that Unique(X) + (X) is not a good diversity measure. To illustrate, consider any measure M that has the monotonicity property (for instance Average), optimize it, and after that spread the elements bit to make them unique. Then, we get (nearly) optimal configuration for Unique(X) + M'X) which very similar to the optimal configuration for (X). However, the optimal solution for M (X) may be not diverse, as we show with the example for Average in Section 3.
The discreteness of Unique(XX plays crucial role in the construction above. A natural way to prevent the measures of the form Unique(X) + MM from being considered good diversity measures is to require that diversity measures must be continuous.
B. Properties of Diversity Measures: Proofs
Let us prove the statements about which measures possess which properties, indicated in Table 2. Note that for some of the measures, their monotonicity and uniqueness were analyzed by Velikonivtsev et al. (2024). However, since modified these properties, we need to formally check the new ones.
Average and SumAverage Monotonicity and continuity are trivial as is the Onn²) complexity. To prove that uniqueness does not hold, consider diversity is achieved when every vertex contains 4 objects, and replacing any of these duplicates by any other object will decrease diversity.
the example from Section 3: given 16 points in a square with Euclidean distance, the maximum
10

---

Mcasuring Diversity: Axioms and Challenges
Diameter and SumDiameter Consider a collection of three objects with pairwise distances 2, 2, 1. Increasing distance 1 to 2 does not change the diversity value, thus proving that monotonicity does not hold. For uniqueness, consider the example from Section 3: given 16 points in square with Euclidean distance, the maximum diversity is achieved when two opposing vertices contain 8 objects each, and replacing any of these duplicates by any other object will not increase diversity. Continuity is trivial, as is the (n?²) complexity.
Bottleneck and Energy(r) Consider collection of three objects, where xj and z2 coincide, and d13 1. Increasing d to 2 will not change the diversity value, thus proving that monotonicity does not hold. Consider a collection of three coinciding objects. Replacing one of them with any other object does not change diversity value, thus proving that uniqueness does not hold. Continuity is trivial, as is the (n²²) complexity.
SumBottleneck Consider collection of four objects, where 21, 22 coincide, 23, 24 coincide, and d13 1. Increasing d13- d23 d14 d24 from 1 to 2 (while keeping d12 = d34 = 0) will not change diversity value, thus proving that monotonicity does not hold. Consider a collection of four objects, where I1, 22, 23 coincide and d14 = 10. Replacing I3 with a new object that has distance to x4 will decrease diversity from 10 to 2, thus proving that uniqueness does not hold. Continuity is trivial, as is the O(n²) complexity.
#Circles(t) Consider a collection of three objects with pairwise distances 4, 3, 2. Increasing distance 3 to 4 will not change the diversity (for any 1), thus proving that monotonicity does not hold. For a given 6, consider collection of two coinciding TO from the first one does not change the diversity value, thus proving that uniqueness does not hold. The lack of continuity is trivial. Let us prove that the complexity of calculating #Cireles(t) is NP-hard. The problem of finding the size of the maximum complete subgraph (clique) in an unweighted undirected graph is known to be Na-hard. Consider any unweighted undirected graph G with n nodes. Construct collection X with n objects corresponding to the nodes of G; the distance between two objects being t if the corresponding nodes are connected and 0.9t otherwise. Suppose we computed #Circles(t). Then, obviously, this value is also the size of the maximum clique in G. This proves that calculating #Circles(t) is Na-hard.
objects. Replacing the second of them with an object at distance A.
Unique Monotonicity, uniqueness, and continuity are trivial, as is the 0(1²) complexity.
HamDiv Consider a collection of four objects, where d12 = d23 = d31 = t1ه = 1 and d13 = d21 = 1.1. Increasing d13 from 1.1 to 1.2 will not change the diversity value, thus proving that monotonicity does not hold. Note that non-strict monotonicity holds; that is, if some pairwise distance increased, the diversity value cannot decrease (although can stay the same). Now, consider two collections of four objects each. The objects are points on the Euclidean line. The first collection is: O, 0, 1, 1; the second collection is: 0, 3: 5. 1. The diversity value for both collections is equal to 2; thus, uniqueness does not hold. Continuity is trivial. Complexity is known to be NP-hard.
To prove the results for Vendi Score, DPP, and RKE, we first need to formulate the axioms in terms of similarities. Monotonicity requires that the measure monotonically increases when some of the pairwise similarities decrease. Uniqueness is formulated in terms of objects, and two objects being duplicates means that they have the maximum similarity value. Finally, continuity can be trivially reformulated.
Vendi Score We first elaborate on the example of violation of monotonicity from Section 3. Consider points on a circle with cosine similarity. Suppose the points T1, X2, 23 are arranged in this order on the circle, the circle distance from 21 to 22 is 0.6 radians, the distance from x2 to D3 is 1.4 radians. Now we move Iz by 0.1 away from æ1 and Ø22 Let us see what similarity matrices we have before and after this move:
1
cos(0.6) cos(2.0) 1
cos(0.6) $ = (0.6) 1
(2.1)
S co.(
cos(1.4)
cos( 1.5)
(3)
cos (2.0)
co.(1.4)
cos (2.1) cos(1.5)
1
Vendi Score of S is 1.941 and Vendi Score of S is 1.916 < 1.941, which is a violation of the monotonicity property.
Now suppose the points 31, 22, My are arranged in this order on the circle, the circle distance from I1 to Iy is 0.2 radians, the distance from T2 to 23 0.3 radians. We replace x2 by a duplicate of x1. Let us see what similarity matrices we have

---

Measuring Diversity: Axioms and Challenges
before and after this replacement:
1
(O.(0.2)
(0.(
1
cos (0.5)
=
cos (0.2).2) (cos(0.5) (o.(
(0.3)
$
cos (0.5)
(4)
(O.( cos(0.5)
1
The corresponding collections of objects differ by replacing 22 with copy of on that is, 8 corresponds to (21) ( 22, and S corresponds to (Z1,21.1 23). Vendi Score of S is 1.187 and Vendi Score of $ is 1.233 >> 1.187, which is violation of the uniqueness property.
Continuity holds since exp (-Σ 12 A A log(A))
. An. which in turn continuously depend on the similarity matrix. It known that the complexity of finding the eigenvalues of general (positive-semideennit)) matrix is Onn"), thus the complexity of calculating Vendi Score is also Onn").
continuously depends on A1.....
i=1
The example of a violation of monotonicity is shown Section 3. To obtain the matrix S, we can consider three points A, B, C on a unit 2D sphere with pairwise spherical distances between and B equal to arccos = 0.927, between B and C' equal to arccos(0.7) = 0.795 and between and equal to arccos(0.2) = 1.369. The similarity given by the cosine function. For the matrix S, decrease the distance between and C. from arccos(0.2) 1.369 a0.cos(0.3) 1.266, while keeping the distance between A and B unchanged, and the distance between B and C unchanged.
DPP
To prove that uniqueness is violated, consider collection of three coinciding objects. Replacing one of them with any other object does not change the diversity value, thus proving that uniqueness is violated. Continuity is trivial. It is known that the complexity finding the determinant of general (positive-semidefnntt)) matrix On²)), thus the complexity of calculating (S) is also Onn²).
RKE Monotonicity, continuity, and complexity (nn²) are trivial. To prove that uniqueness is violated, we elaborate on the example from Section 3. Consider points on circle with cosine similarity. Suppose the points 21, 22, 33 are arranged in this order on the circle; the distance from æ to 22 is 1.1 radians, the distance from æ2 to æa is 0.4 radians. Now, we replace D2 with a duplicate of Zz. We get the following similarity matrices before and after the modification:
cos(1.1) S cos (1.1 1 cos (155) cos(0.4)
1
cos(1.5)
cos(1.5)
cos (1.5)
cos(0.4)
$ == cos(1.5)
1
1
(5)
cos 1.5)
1
1
The corresponding collections of objects differ by replacing x2 with a copy of ast that is, S corresponds to (æ1, 22, v2) and S corresponds to (æ1, N3, 22). RKE of 0.564 and RKE of Š is 0.584 >> 0.564, which is a violation of the uniqueness property.
Species(g) Continuity and complexity Onn²) are trivial. Monotonicity is trivial for both cases 0 S q < 1 and > 1. For violation of uniqueness, we consider the same example as for RKE. We computed Species(q) of the collection 21, 22, 33 and the collection æ1, I3. Ia for all q in the range [0, 100] with step size 0.001 (excluding defined). For all the considered g. the first collection has a lower value of Species(q) than the second collection, which is a violation of the uniqueness property.
when Species(g) is not
C. Properties of MultiDim Volume
Let us prove that MultiDim Volume has monotonicity, uniqueness, continuity and is NP-hard to compute.
For convenience, we repeat the definition of MultiDim Volume. For a given k; 2 < k S n, and a given submultiset K size of the multiset X = {ø1,.... } calculate the product of all pairwise distances between the elements of K. Note that this product equals zero if least two elements of K coincide. Then, for a given k. we take the maximum of such products
over all submultisets of size k of X and denote this maximum as mxXX.. We define the diversity of X as Σ my mx(X).
km
12

---

Measuring Diversity: Axioms and Challenges
Putting the above into one formula, we get:
Diversity(X)-
max K
II
dis
(6)
Assume that we are given any distance matrix D (or, equivalently, a collection of objects X). Denote by the maximum such that my (X) non-zero. Note that by construction, X includes exactly io pairwise non-coinciding objects and my the product of pairwise distances between these objects.
Monotonicity We want to prove that MultiDim Volume is strictly monotone in D. Suppose we increase the distance between two objects x2 and 2j by <> 0; that is, we replace dıj by d, + Obviously, for every k the value of (x) has not decreased. Thus, prove monotonicity, it is sufficient to prove that least one of my (X) has increased. If wa and zy did not coincide before increasing dey. then after increasing di the term mg (X) has increased since dı is one of the multipliers in my (X). If z; and 2; coincided before increasing diy. then after increasing dij the collection X includes exactly - non-coinciding objects, and m (X) has increased from 0 to some positive value.
Note that for some matrices D we cannot increase only one distance. For instance, if the objects ø1. 22 23 coincide and we increase 1 by c, we also need to simultaneously increase d13 or d23. otherwise we have d13 = d23 0, d > 0, which implies that æ1 coincides with my and 22 coincides with zz. but 21 and r2 do not coincide. Clearly, the proof above easily generalizes to the case when we increase several distances simultaneously.
Uniqueness Suppose X includes least one duplicate. We replace this duplicate with some new object that was not present in X. Then, m has increased from 0 to some positive value. Also, for any & < k, the values of m& have not decreased. Thus, Diversity has increased.
Continuity Note that Voluime is composition of product, maximum, and sum that are all continuous functions. A composition of continuous functions is continuous. Thus, MultiDim is continuous.
NP-hardness Let first prove that finding my (X) for all k is NP-hard. The problem of finding the size of the maximum complete subgraph (clique) in an unweighted undirected graph is known to be NP-hard. Consider any unweighted undirected graph G with nodes. Construct collection X with objects corresponding to the nodes of G, the distance between two objects being 3 if the corresponding nodes are connected and 2 otherwise. Suppose we computed (x()) for all k. Take the maximum i such that m& (X) 22 Then le is the size of the maximum clique in G, which concludes the proof.
Although we proved that finding m& mx(X) (X) for all k is NP-hard, it does not directly imply that computing MultiDim Volume is NP-hard. Indeed, maybe we can compute MultiDim Volume without directly computing mz()) for all k. Let give sketch of how to avoid this technical obstacle.
As above, consider a graph G for which we want to find the size of the maximum clique. Construct a collection X with n objects corresponding to the nodes of G, the distance between two objects being 2 + e if the corresponding nodes are connected and otherwise, where > 0 is small number (we will specify later how small it should be). Consider (X) for some k. It is the product of pairwise distances between some k objects of X. Denote by Tk. 0 < S 2 number of their pairwise distances which are equal to + e (so, the remaining k(k-1) T distances are equal to 2). This equivalent to saying that:
k(k-1) the
mx(X) = (2 r)r22 k(k-1) ro 2 -
Err2
bik-1)
+0(
Therefore,
Diversity(X) Σ mu (X)
Σ 2
r
A(A
+ +
Note that for given n, the value of e can be chosen sufficiently small so that the last term O(e2) is negligibly small compared to the other two terms.
13

---

Mcasuring Diversity: Axioms and Challenges
Now suppose we know Diversity(X). We also know the term
Σ 2 h=2
ke 12
and we know Thus, we can compute
Tk2 11--111
Σ rm2 kk- 1
We claim that knowing the value M
can recover r2, P.:.....: For this, note that for any
k = ......P n
kik
i(i - 1). 2
Indeed, this holds for and is easy to check that the left-hand side of the inequality grows faster than the right-hand side.
Now, consider i n and note that the left-hand side of (7) is equal to how much the value of M changes if change I' by 1. In turn, the right-hand side of (7) is an upper bound on the sum of all other terms in M. Thus, knowing M, we can find the maximum integer Tn such that r2 " < M. After we found Tn, we get rid of the term n' - and can do the same reasoning to find rn-1, and continue until we find all r2..... : Pn- After that, we take the maximum lc such that Tk= k(k-1) this & is the size of the maximum clique in G, which concludes the proof.
D. Properties of IntegralMax
Let us prove that IntegralMaxXliquee has monotonicity, uniqueness, continuity and is NP-hard to compute.
For convenience, we repeat the definition of IntegralMax For given threshold 2 O, we construct the following graph. The nodes are Ti, Ti,..., .n. Two nodes z; and zÿ are connected by an edge iff dij 2 f, and we assign dij as the weight of this edge. We find a clique (complete subgraph) in this graph with the maximum number of nodes. If there are several such cliques, we pick the one with the maximum total weight edges. For the chosen clique, we calculate the total weight of its edges and denote it by (X)) Then, we define diversity as
Diversity(X)) = / wx(X) dt.
(8)
Assume that we are given any distance matrix D (or, equivalently, collection of objects X). Denote by d the smallest non-zero pairwise distance between the objects of X. If all pairwise distances are O, then monotonicity is trivial, so we can assume > O. Note that for S the value of w: (x( (X) is the sum of pairwise distances between all pairwise non-coinciding elements of X.
Monotonicity Assume that we increase the distance between two objects x; and 2j by e > 0, that is, we replace dij by dij + e. Obviously, for every t, the value of wi (X) has not decreased. If dej > O, then for all t < d the term di is a summand in (X). thus for every < the value (X) has increased least by c. Therefore, Diversity has increased by least de. If dij 0, then for all S e, the value of wx(X (X) has increased by least (since a new element added to the maximum clique). Thus, Diversity (X) has increased by at least e
As with MultiDim Volume, this proof can be easily generalized to the case where several distances are increased simultane- ously.
Uniqueness Suppose X includes at least one duplicate. We remove one duplicated element and add some new object that was not present in X. Suppose the distance from the new object to the nearest object from X is r > 0. Then, for S r, the value of (XX) has increased by at least r, and for every t >> r, the value of wy (X) has not decreased. Thus, Diversity has increased by at least n2 This shows that making duplicates distinct increases diversity, establishing uniqueness.
Continuity Assume that we increase the distance between two objects x; and øj by e > 0, that is. we replace dy by di + 6. Let us see how much Diversity(X) (X) could change. Obviously, for every the value of wy (X) has not decreased.
14

---

Measuring Diversity: Axioms and Challenges
Let us estimate how much Diversity (X) could increase. We decompose the integral into three parts:
paste Diversity (X) ! wx(X) dl (xx)dd=/ J. we (x)(X) dl
Jug | wx(X) dl + f wx(X) dl.
deyte
It is easy to prove that fort S dzy, the value of u (X) could increase at most by e, thus the first part could increase at most by ediy (since we integrate from 0 to dız). For the second term, we note that w. (X) is bounded from above by Σ dul tE,
thus the second term is bounded by Σ du k<Í
+ e2 and could increase by at most this value. The third term does not change since for t > dey + e the value of (X) does not change.
Therefore, Diversity(X) has increased by at most ediy + c (I dut + +c. So, we increase diy by c, then Diversity
increases by at most cc, where e is some constant independent of (given that c < 1, so the term is bounded by c). From this, the continuity follows.
The problem of finding the size of the maximum complete subgraph (clique) in unweighted undirected graph is known to be NP-hard. Consider any unweighted undirected graph G with n nodes. Construct a collection X with objects corresponding to the nodes of G, the distance between two objects being 3 the corresponding nodes are connected and 2 otherwise. Suppose we computed Diversity(X). Let us show how to find the size of the maximum clique in G. Note that for S 2, the value of (x)) is the sum all pairwise distances in X, that is, Σ d&a (which can be computed in k<l
NP-hardness
O(n²) time). For 2 < t S 3, the value of wx(X) 3 =(=11) where s is the size of the maximum clique G. For >> 3, the 2
value of (X) is O. So, get Diversity (X) 2 Σ du + +3 from which can find in constant time. Thus, k<l
once we know Diversity(X), we can find s in On²)) time. This proves that calculating Diversity (X) is NP-hard.
E. Proofs of Propositions from Section 5
E.1. Proof of Proposition 6.1
Let us first recall the statement of the proposition. Suppose diversity function has uniqueness and continuity. Let 21, ..... Zk be a set of k pairwise distinct objects. Let C' be a multiset of n - A objects, each of which coincides with one of æ1. Z%. Then, diversity of the multiset
Fk U C' is the same for all such C.
Consider the following lemma.
be any collection of n 1 objects. We denote by A₁ the collection of n objects 23,...,,nn-117, 21 and by Ag the collection of n objects fi,...,Ta-11 (note that A and A2 differ only by the last object). Then, Diversity(A)) = Diversity(Ag).
Lemma E.1. Suppose a diversity function has uniqueness and continuity. Let
Informally, this lemma says that we can remove the duplicate of æ1 and add the duplicate of x2 without changing the value of the diversity function. The proposition trivially follows from this lemma, so it is sufficient to prove it.
W.l.o.g., assume that Diversity (AAr Diversity(AA) = e > Denote by A the following collection: take A and increase the distance from the last object to all objects by a small 8 >> 0 in such a way that diversity changes by less than 5 (note that the last object is no longer a duplicate). By continuity, this is possible. Then, Diversity (Ab) is less than Diversity (A2) + 2. Thus, Diversity (Ab)= < Diversity (A1). However, by uniqueness, we have Diversity (Ab)) > Diversity since the last object of A²2 is not duplicate, and the last object of A₁ is duplicate. So, we get a contradiction which concludes the proof of the lemma.
E.2. Proof of Proposition 6.2
We need to prove that a diversity function satisfying all the axioms cannot be decomposed in the following form:
Diversity (X) F(d12, dia..... .in) + G(xz, ..,,,..,,, zn)-
15

---

Mcasuring Diversity: Axioms and Challenges
Suppose we increase 112 (and d21) by some A. Then, diversity will increase by the following value:
F(d12+ A.d13. ...,,........................... d1n) G( ........,,... .n)) F(d12, d13....... ................................ .,in) Glz......... Fn)
F((112 A, d13. din) dis...d din). (10)
Note that by permutation invariance decompose Diversity (X (X) based not æi, but on d22
Diversity(X) F' d23..... d2n) G(z (3,...;;n).
(11)
Using this decomposition, we see that when we increase d12 (and d21) by A, the diversity increases by the following value:
Fd221 + A,d23, ... d2n) G( T3....,,yy F(221, d23, .......... d2n) G( 23. ;3....,,yy Fn) F(222 A, A,023, ... d2n)) Fd221, ((d21,d23:-- ,d2n) (12)
Combining the results of (11) and (12), we get:
F(d12 + A. dis............................. din) F(d12. dis..... d1n) F(221 + d2s..... d2n) F(221, d23, .... .22).
Note that the left part depends on d13, .., din, while the right part does not depend on these variables. Similarly, the right part depends on d23..... ......... d2n, while the left part does depend on these variables. This means that both parts actually do not depend any of d1.,.... din and . d2n. they depend only d12 (or d21, which is the same) and A. Thus, we proved that if we increase d12 by A, the diversity changes by some value that depends only on d12 and A and does not depend other pairwise distances. By permutation invariance, for any diy the analogous statement is true. From these statements, it easily follows that
Diversity(X) h(d12) + h(d1s) +... (ddy).
where we have the same function à applied to all distances by permutation invariance.
Consider the following collection: the first n 1 objects are duplicates of one element, and the last object at distance 1 from them. So, there are pairwise distances of 1 and (n-1)(n-2) distances of O. Thus, diversity is (n 1)/((1 1) + (n- (n-1))n-2) (0). Using Proposition 6. we can move one of the duplicates in such a way that now it duplicates the last object, and diversity should not change. Now, there are 2(n 2) pairwise distances of 1, and (n-2)(n-3) distances of 0.
Thus, diversity is 2(n 2)/(1) (n=2)(n=3) +1) h(0). So, we get
(n - 1)h(1)) + (n 1)(n 2) h(0) = 2(n 2)/(()) +
(n 2)(n 3) + +1) h(0),
2
2
from which we get (n 3)/(1) = (n (n-3) -3)((0)) which implies f(1) = (0) (given that 3). Monotonicity implies that is strictly monotone, which contradicts h(1) = Ic(0), which concludes the proof.
16


Reviews:
[{"review_id": "ehNPRmwF7s", "reviewer": "Reviewer_yDDf", "summary": "This paper discusses metrics for measuring diversity in various applications. The authors review existing diversity measures and highlight their limitations in corner cases. They propose three key properties—monotonicity, uniqueness, and continuity—that a reliable diversity measure should possess. The paper demonstrates that no existing measure satisfies all three properties, making them unsuitable for accurate diversity quantification. While the authors construct two examples of measures that meet these properties, they, too happen to be NP-Hard, and the paper concludes by posing the challenge of creating a feasible diversity measure.\n\n## update after rebuttal\n\nI've added follow-up comments for the authors, and I sincerely hope they'll resolve them in the next version of the manuscript. I have also raised score by a point.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "Thank you for the feedback and suggestions! We address the concerns below and will be happy to discuss any of the raised issues further.\n\n> Continuity being the new axiom, I am not fully convinced with the example that it is important (mentioned in Appendix A)\n\nRegarding the importance of the continuity axiom, we first note that it is natural to assume that minor changes in object locations should lead to small changes in diversity: this is important for interpretable comparison of diversity values across datasets. Also, please see our response to **Reviewer Pyqh (Continuity axiom).**\n\nAlso, we modify the definitions of both Monotonicity and Uniqueness. This modification is important (see lines 244-250 of Section 4.2) and makes developing a suitable diversity measure more challenging.\n\n> Can authors cite and discuss about the following work - \"Position: Measure Dataset Diversity, Don't Just Claim It\". ICML'24\n\nThank you for the reference. This paper gives motivation on why measuring diversity is important and argues that it is critical to provide a clear definition of diversity when analyzing datasets. We will cite this paper in the introduction.\n\n> Axioms could've been explained formally using math.\n\nIn the paper, we opted for more intuitive definitions and will add formal versions in the revised text.\n\nAs defined in the paper, let $D_n$ be a subset of all $n \\times n$ matrices satisfying the properties in lines 247-251. There is a natural action of the symmetric group $S_n$ on this subset (which simultaneously rearranges rows and columns). Diversity function is any $S_n$-invariant function from $D_n$ to $\\mathbb{R}$. \n\n**Axiom 1 (Monotonicity).** For any two matrices $A, B \\in D_n$ such that $\\forall i,j: a_{ij} \\ge b_{ij}$ and at least one of inequalities is strict, we have $\\mathrm{Diversity}(A) > \\mathrm{Diversity}(B)$.\n\n**Axiom 2 (Uniqueness).** Suppose that for $A,B \\in D_n$:\n\n- $a_{ij}=b_{ij}$ for all $i>2, j>2$\n- $b_{1i}=b_{2i}$ for all $i$\n- $a_{2j}=b_{2j}$ for all $j>2$\n- $a_{1j}>0$ for all $j>1$\n\nThen $\\mathrm{Diversity}(A) > \\mathrm{Diversity}(B)$.\n\n**Axiom 3  (Continuity).** The space $D_n$ is endowed with the subspace topology induced by the standard topology on the set of all $n \\times n$ matrices. A diversity function must be continuous w.r.t. this topology.\n\n> This paper misses on connecting the works with the vast literature on submodular functions, which are known to capture diversity, and appear in many areas of science.\n\nThank you for the reference, we will add a discussion on submodular functions in the updated version. \n\nSubmodular functions indeed can be used to capture diversity and there is a condition that a submodular function should satisfy that captures an intuitive behavior of diversity/coverage as some elements are added to a dataset (note that in our work we consider properties that hold when the number of elements is fixed). \n\nUsually, such functions are used as a diversity measure of a set of objects $X$, when the set of all possible objects $V$ is known. Thus, some known submodular functions use summation (or integration) over the set $V$ (for instance, see the facility location function). Our setting is more general: we want to measure diversity of $X$ without any information about the bigger space $V$, in particular we do not assume that we can sum over $V$. This restriction is reasonable in many cases: if $X$ is a set of several graphs or images and $V$ is a set of all graphs or all images, then it is infeasible to sum over $V$.\n\nWe are not aware of submodular functions that can be applied to our setup while being not equivalent to one of the measures in Table 1. If there is a particular function that you believe should be added to our analysis — we are happy to extend our work.\n\n> In most of the practical situations one is interested in coming up with a subset of the data starting from no datapoints.\n\nThank you for the comment! Although our properties assume that the number of elements in a dataset is fixed, they can still be applied within iterative strategies when one adds elements successively to optimize diversity. See, e.g., the greedy algorithm in Velikonivtsev et al. (2024). Other algorithms may operate with a dataset of fixed size: we may start with a random set of objects and then use, e.g., a genetic approach (or other optimization approaches) targeting at optimizing diversity.\n\n> do these corner cases (particularly for the determinant-based examples) occur regularly?\n\n> While the work says that it is quite difficult to satisfy all three axioms, it would've been nice to discuss an existing metric that doesn't succumb to corner cases in practical situations.\n\nPlease, see the first two comments in our reply to **Reviewer zmT9**. Here we provide an additional experiment and also discuss when existing measures can be used despite not having all the properties.\n\nWe hope that our response addresses the raised issues.", "claims_and_evidence": "Given the nature of this paper, the provided claims and evidence are clear. However, I think there are a few weakness\n\n1. The paper is quite similar to Velikonivtsev et al. 2024, which also talks about the first two axioms and many of the mentioned previous works. Continuity being the new axiom, I am not fully convinced with the example that it is important (mentioned in Appendix A) in particular, the entire argument of diversity is using the intuitive notion. For instance, I might consider that the Fig on right in Appendix A less diverse because of even a single duplicate (recall that you're changing two things at a same time, spread and adding duplicate).\nHence is no reason to believe that this intuitive notion of diversity will result in practical improvement for whatever downstream task is considered. \n2. Can authors cite and discuss about the following work - \"Position: Measure Dataset Diversity, Don't Just Claim It\". ICML'24\n3. Axioms could've been explained formally using math. That is, this work should have defined the exact notation for the diversity function, what are the arguments (subspace of all matrices defined on field R, multi set of examples), how is monotonicity mathematically defined for this multivariable function. \n4. This paper misses on connecting the works with the vast literature on submodular functions, which are known to capture diversity, and appear in many areas of science. See -- \"Submodularity In Machine Learning and Artificial Intelligence\" for a gentle introduction. \n5. In most of the practical situations one is interested in coming up with a subset of the data starting from no datapoints. This is something I am not sure how the current framework tackles (a discussion is missing)", "methods_and_evaluation_criteria": "1. From the point of view of picking out corner cases for existing measures, 2D examples are great. However, they still are toy examples at the core. Often, people are interested in finding a diverse subset of a given giant dataset; hence, do these corner cases (particularly for the determinant-based examples) occur regularly? \n2. Unfortunately, the proposed method is also NP-hard. While the work says that it is quite difficult to satisfy all three axioms, it would've been nice to discuss an existing metric that doesn't succumb to corner cases in practical situations.", "theoretical_claims": "I've gone through the proofs provided in the appendix.", "experimental_designs_or_analyses": "While 2D experiments are good to demonstrate, proposed method is not practical (even hard to compute, let alone optimize), therefore any empirical demonstration is not possible.", "relation_to_broader_scientific_literature": "The work lacks discussion with the entire area of submodular functions, which are at the core of measuring data diversity.", "essential_references_not_discussed": "1. \"Position: Measure Dataset Diversity, Don't Just Claim It\". ICML'24\n2. \"Submodularity In Machine Learning and Artificial Intelligence\"", "other_strengths_and_weaknesses": "Refer to the claims and evidence", "other_comments_or_suggestions": "Refer to the claims and evidence", "questions_for_authors": "Refer to the claims and evidence", "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": "", "extra_scores": {}}, {"review_id": "BzscUjaoru", "reviewer": "Reviewer_Pyqh", "summary": "This paper explores how to quantify diversity for a set of objects. The authors first review existing diversity measures, showing that they can have undesirable behaviors. To address this, the paper suggests three properties that a diversity measure should have: monotonicity (diversity should increase as pairwise distances between objects increase), uniqueness (replacing an object with a duplicate should decrease diversity), and continuity (diversity should be a continuous function of pairwise distances).    \n\nThe paper shows that none of the existing measures satisfies all three properties.  The authors provide examples of measures that do satisfy the properties, but these are complex for practical use. The paper concludes by posing the open problem of finding a measure that has all three properties and is computationally feasible.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thank you for your thoughtful comments and positive feedback! \n\nWe see that the main concern is regarding the necessity of the continuity axiom, so let us elaborate on this subject.\n\n**Continuity axiom**\n\nFirst, it is natural to assume that minor changes in object locations should lead to small changes in diversity: this is important for interpretable comparison of diversity values across datasets. Second, we believe that this property is critical since without assuming it one may come up with a range of measures that do satisfy the remaining two properties while being intuitively not useful for measuring diversity. The reasoning below extends the example in Appendix A.\n\nConsider any measure $M$ that is monotone (e.g., Average). Apply any order-preserving transformation to $M$ such that the range of the resulting measure $M’$ is in $[0,1)$. E.g., if $M$ takes only non-negative values, we can take $M’(X):=1-e^{M(X)}$. Then, the measure $Unique(X) + M’(X)$ has both uniqueness and monotonicity. Essentially, $Unique(X) + M’(X)$ compares two configurations of points in the following way: \n\n- Count the number of unique points in both configurations;\n- If the numbers of unique points are different, then the configuration with a bigger number is more diverse;\n- If the numbers of unique points are the same, compare configurations based on the measure $M$ (or, equivalently, $M’$).\n\nWe argue that $Unique(X) + M’(X)$ is (in many cases) not a good diversity measure. For this, consider any measure $M$ that has the monotonicity property (for instance Average), optimize it, and after that spread the points a bit to make them unique. Then, we get the (nearly) optimal configuration for $Unique(X) + M’(X)$ which is very similar to the optimal configuration for $M(X)$. However, the optimal solution for $M(X)$ may be not diverse, as we show with the example for Average on page 3.\n\nThe discreteness of $Unique(X)$ plays a crucial role in the construction above. A natural way to prevent the measures of the form $Unique(X) + M’(X)$ form being considered as a good diversity measure is to require that diversity measures must be continuous. \n\nWe will add the above reasoning to Appendix A.\n\nRegarding the visual example in Appendix A, we note that the penalty of a duplicate is higher than any increase in diversity that can be gained from moving already unique points further away from each other. We claim that all continuous monotone diversity measures do not show such behavior. Let us formally prove this.\n\nThe measure from Appendix A rate any configuration of $16$ unique points as more diverse than any configuration of $15$ unique points and $1$ duplicate. Suppose that a continuous measure $M$ does the same. For $a \\ge 0$ denote by $X_a$ the set of $16$ points with pairwise distances $a.$ For $a > 0$ denote by $Y_a$ the set of $16$ points from which $15$ have pairwise distances $a$ and one point is a duplicate. Let $r = M(Y_2)-M(Y_1)$, note that $r>0$ by monotonicity of $M$. By continuity of $M$ we can find $1>\\epsilon >0$ such that $(M(X_\\epsilon) - M(X_0)) < r/10$ and $(M(Y_\\epsilon) - M(X_0)) < r/10$. Then $M(X_\\epsilon)$ and $M(Y_\\epsilon)$ differ by at most $r/5.$ At the same time, $M(Y_1) > M(Y_\\epsilon)$ (since $\\epsilon<1$) and $M(Y_2)-M(Y_1) =r,$ thus $M(Y_2)$ is bigger than $M(X_\\epsilon)$ by at least $4r/5>0$. This is a contradiction since we assumed that $M(X_a)>M(Y_b)$ for all $a>0, b>0.$\n\n> There has been a trend in methods that use human feedback/judgment to learn a high-dimensional distance measure [1] or abstract diversity metrics [2]. Given that the authors touched human intuition on diversity, a discussion on these related work would be helpful to understand how the axioms and challenges apply to more practical settings such as GenAI.\n\nThank you for the references, we will extend the related work accordingly. The mentioned papers use human feedback/judgment to estimate pairwise distances between the objects. A good distance measure is a critical ingredient of a reliable diversity measure. In our work, we assume that pairwise distances are given and analyze different ways of aggregating these values into diversity.\n\nWe hope that our response addresses your concerns. We are open to further discussions!", "claims_and_evidence": "The authors support their claim that existing diversity measures exhibit undesirable behavior by providing examples and visual representations in Section 3.    \n\nIn Section 4, the authors clearly define the axioms and provide justifications for why these axioms are important for a reliable diversity measure. The proofs for the properties of existing measures and the proposed measures are detailed and can be found in the appendices. \n\nOne potential issue I think is with Axiom 3 (Continuity). A diversity function must be continuous. The authors claim that the function should naturally be continuous, and provide a counter example in Appendix. In this example, I do not agree the point that `the right configuration is intuitively more diverse`. The diversity in this case depends on the distance measure. For example, even with continuous functions, if you have very high penalty on duplicates (and/or near duplicates), you will still get such behavior, so the problem is not with continuity.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "The claims look good to me except the one with continuity mentioned above.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper makes significant contributions to the scientific literature by analyzing existing diversity measures, proposing a new set of axioms, identifying a gap in the literature, and proposing new measures that adhere to the axioms. The authors also clearly position their work within the context of prior research and highlight the direction for future work.", "essential_references_not_discussed": "There has been a trend in methods that use human feedback/judgment to learn a high-dimensional distance measure [1] or abstract diversity metrics [2]. Given that the authors touched human intuition on diversity, a discussion on these related work would be helpful to understand how the axioms and challenges apply to more practical settings such as GenAI.\n\n[1] Fu, Stephanie, et al. \"DreamSim: Learning New Dimensions of Human Visual Similarity using Synthetic Data.\" Advances in Neural Information Processing Systems 36 (2023): 50742-50768.\n[2] Ding, Li, et al. \"Quality diversity through human feedback: towards open-ended diversity-driven optimization.\" Proceedings of the 41st International Conference on Machine Learning. 2024.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "See Claims And Evidence.", "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": "", "extra_scores": {}}, {"review_id": "uFVZy2RrW8", "reviewer": "Reviewer_zmT9", "summary": "This paper studies the problem of diversity measurement and proposes three axioms—monotonicity, uniqueness, and continuity—as necessary conditions for a reliable diversity measure. The authors analyze existing diversity measures and demonstrate that none satisfy all three axioms. To address this gap, the paper constructs two theoretical diversity measures that adhere to the proposed axioms but are computationally infeasible. The work highlights an open challenge: finding a computationally efficient diversity measure that aligns with the theoretical principles.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for your suggestions and positive feedback! We appreciate that you find our approach novel, well-structured and theoretically sound. We address the raised concerns below.\n\n> The paper does not explore approximations or alternative methods that balance theoretical soundness with practical efficiency.\n\nIn the paper, we briefly discuss that some measures can still be suitable in some applications despite not satisfying all the properties. E.g., in Section 3, we discuss undesirable behavior w.r.t. optimization and note that not all measures have this problem. In lines 204-211, we mention that Bottleneck, SumBottleneck and Energy behave well w.r.t. optimization and thus can be used as target measures when constructing a diverse dataset. Energy has all the desirable properties when all elements are unique. When some elements coincide, this measure becomes infinite and thus the properties are not satisfied, which makes Energy inappropriate for comparing diversity of different datasets. On the other hand, while we do not advise optimizing Average, its value is interpretable and can be used as one of the measures evaluating dataset diversity.\n\n> The paper does not test existing diversity measures on real-world datasets.\n\nTo demonstrate that the choice of diversity measure is important and to illustrate shortcomings of a particular measure, we conducted the following experiment. We consider the setup of generating structurally diverse graphs from Velikonivtsev et al. (2024). Using the code publicly shared by the authors, we compare diverse graphs generated by a genetic algorithm while optimizing either Energy (as in the original paper) or Average. The obtained results can be found [here](https://anonymous.4open.science/r/ICML_2025_rebuttal-3966). We see that optimizing Average (portrait_genetic_optimizing_avg.pdf) leads to more similar graph structures that tend to be either too dense or too sparse, which agrees with our observations about corner cases for Average in Section 2. In turn, Energy is suitable for optimization and thus leads to more structurally diverse graphs.\n\n> No experiments are provided to validate the proposed axioms.\n\nValidating axioms is challenging: one can potentially compare two measures, one of which satisfies a particular axiom while the second one does not, but the result will not allow one to make conclusions about the axiom since there can be other properties affecting the comparison of the measures. That is why we first analyzed different measures and observed their failure cases and then formulated properties that are intuitively desirable for all diversity measures. If one knows which properties a particular measure does or does not satisfy, one can better interpret the obtained results.\n\n> Author should discuss potential applications of the proposed framework in real-world machine learning tasks.\n\nThank you for your suggestion. We will include a deeper discussion on how diversity measurement is used in machine learning tasks. Specifically, we will highlight that a well-defined diversity measure ensures informative sample selection in active learning, guides the generation of meaningful synthetic data in augmentation, and provides a way to assess cluster distinctiveness. \n\n> The appendix provides extensive proofs but lacks practical implementation details.\n\nNote that the main contribution of our paper is theoretical and the paper does not contain experiments. However, if there are any questions regarding potential implementations or applications, we will be happy to address them.\n\n> The evaluation criteria focus solely on theoretical correctness, neglecting computational efficiency and practical applicability.\n\nLet us remark that in the paper we pay attention to the computational efficiency of diversity measures: asymptotic computational complexity is analyzed and reported in Table 2. Both MultiDimVolume and IntegralMaxClique are NP-hard which is why we pose an important open problem on whether there exists a more efficient measure that satisfies all the properties.\n\n> The computational feasibility of the new diversity measures is not explored through empirical benchmarks.\n\nLet us note that the main goal of constructing these two measures was to show that our set of axioms is not self-contradictory. Since these measures are NP-hard, they cannot be used in most applications. That is why we believe that the open problem that we pose is important and hope that it will be addressed in future studies.\n\n> Considering weighted distances or context-aware diversity measures could improve the framework’s applicability.\n\nThank you for this suggestion! We believe that studying more complex scenarios is an important direction for future research. In our paper, we address the simplest case and observe that it is already challenging.\n\nWe are open to further discussions!", "claims_and_evidence": "The paper presents the following key claims:\n1.The three proposed axioms (monotonicity, uniqueness, and continuity) establish a theoretical basis for evaluating diversity measures.\n2.The paper systematically reviews existing diversity measures and demonstrates that they fail to satisfy all three axioms.\n3.Two new diversity measures (MultiDimVolume and IntegralMaxClique) are proposed that satisfy the axioms but have NP-hard complexity.\nThe claims are well-supported by rigorous theoretical analysis, but the lack of experimental validation weakens their practical impact.", "methods_and_evaluation_criteria": "The axiomatic approach provides a novel and well-structured evaluation framework.The systematic review of existing methods is insightful and identifies key limitations.\nHowever, the absence of benchmark datasets and experimental results limits the validation of the proposed axioms in real-world applications.\nThe evaluation criteria focus solely on theoretical correctness, neglecting computational efficiency and practical applicability.", "theoretical_claims": "The theoretical claims are well-structured and logically sound. And proofs are detailed and rigorously support the proposed axioms.\nHowever, no evidence is provided to show whether satisfying these axioms leads to improved diversity measurement in practical scenarios.", "experimental_designs_or_analyses": "No experiments are provided to validate the proposed axioms.\nThe paper does not test existing diversity measures on real-world datasets.\nThe computational feasibility of the new diversity measures is not explored through empirical benchmarks.", "relation_to_broader_scientific_literature": "The paper builds upon existing work on diversity measurement but does not discuss its implications for real-world applications such as active learning, data augmentation, or clustering\nAuthor should discuss potential applications of the proposed framework in real-world machine learning tasks.", "essential_references_not_discussed": "The paper does not reference works on diversity in active learning, dataset selection, or representation learning.", "other_strengths_and_weaknesses": "Strengths \n1.The paper introduces a novel axiomatic framework for diversity measurement, which provides a theoretical foundation for evaluating and comparing different diversity measures. \n2.The paper provides well-structured proofs to demonstrate that existing diversity measures fail to satisfy all three proposed axioms. The authors also construct two diversity measures that adhere to these axioms, proving their feasibility in a theoretical context.\nWeaknesses \n1.While the paper proposes diversity measures that satisfy the axioms, they are computationally infeasible (NP-hard), limiting their applicability in real-world scenarios. The paper does not explore approximations or alternative methods that balance theoretical soundness with practical efficiency.\n2.The paper does not provide experimental results to demonstrate the impact of the proposed axioms on real-world datasets. The theoretical framework is well-developed, but its practical implications remain unclear without empirical evaluation.\n3.The paper does not sufficiently explore how these axioms might be relevant to practical machine learning tasks, such as dataset selection, diversity-aware training, or clustering evaluation. \n4.The proposed framework assumes that all pairwise distances are equally important, neglecting the possibility that hierarchical structures or different levels of diversity may be relevant in real-world applications. Considering weighted distances or context-aware diversity measures could improve the framework’s applicability.", "other_comments_or_suggestions": "Please see the above weakness", "questions_for_authors": "Please see the above weakness", "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": "", "extra_scores": {}}, {"review_id": "YmNMaGpqbq", "reviewer": "Reviewer_Huhr", "summary": "This paper examines in depth the problem of quantifying diversity for a set of objects, a concept widely used in various fields such as image generation, molecule generation, and recommendation systems. The authors conduct a systematic review of existing diversity measures and highlight their undesirable behaviors in certain cases. Based on this analysis, they formulate three desirable properties (axioms) for a reliable diversity measure: monotonicity, uniqueness, and continuity. The paper demonstrates that none of the existing measures simultaneously satisfy these three axioms, thus suggesting their inadequacy for a rigorous quantification of diversity. Subsequently, the authors construct two examples of measures that possess all the desirable properties, proving that the set of axioms is not self-contradictory. However, these constructed examples turn out to be computationally too complex for practical use, leading to an open problem: that of designing a diversity measure that satisfies all the axioms while being efficiently computable.\n\n# update after rebuttal\nNo need to change my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thank you for your thoughtful review and support! We sincerely appreciate that you acknowledge theoretical soundness of our research and its relevance to practice.", "claims_and_evidence": "This is a purely theoretical paper, which can have a definitive impact on the practice. All the claims are thoroughly either illustrated or demonstrated. \n\nThe paper is well written and richly illustrated.\n\nAlthough the paper is theoretical and contains no experiments, I like it, and I believe it shall be published.", "methods_and_evaluation_criteria": "There is no application, this is a purely theoretical paper.", "theoretical_claims": "As far as I have been able to check, the proofs are correct.", "experimental_designs_or_analyses": "There is no experimental evaluation per se. However, the examples illustrating the different claims are convincing.", "relation_to_broader_scientific_literature": "The interest of the paper is to provide insights into measures of diversity that are frequently used in practice. As none of these measures satisfy the desired properties, it is important for the end-user to understand why and when they are failing, so that the measures can be used properly. \n\nFurthermore, the question of having an usable measure that satisfy the three desirable properties, which is an open problem in the paper, is of great interest.", "essential_references_not_discussed": "None", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The authors' contribution of axioms for diversity is insightful and opens the door for future work. There was some spirited back-and-forth regarding submodular functions, and we would like the authors to acknowledge that their framework does not capture at least one class of submodular functions that are commonly used in the context of the problem they study.
Decision: Accept (poster)