Thank you for your thoughtful review and support! We sincerely appreciate that you acknowledge theoretical soundness of our research and its relevance to practice.

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.

The paper does not explore approximations or alternative methods that balance theoretical soundness with practical efficiency.

In 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.

The paper does not test existing diversity measures on real-world datasets.

To 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. 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.

No experiments are provided to validate the proposed axioms.

Validating 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.

Author should discuss potential applications of the proposed framework in real-world machine learning tasks.

Thank 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.

The appendix provides extensive proofs but lacks practical implementation details.

Note 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.

The evaluation criteria focus solely on theoretical correctness, neglecting computational efficiency and practical applicability.

Let 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.

The computational feasibility of the new diversity measures is not explored through empirical benchmarks.

Let 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.

Considering weighted distances or context-aware diversity measures could improve the framework’s applicability.

Thank 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.

We are open to further discussions!

Thank you for your thoughtful comments and positive feedback!

We see that the main concern is regarding the necessity of the continuity axiom, so let us elaborate on this subject.

Continuity axiom

First, 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.

Consider 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:

• Count the number of unique points in both configurations;
• If the numbers of unique points are different, then the configuration with a bigger number is more diverse;
• If the numbers of unique points are the same, compare configurations based on the measure $M$ (or, equivalently, $M’$).

We 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.

The 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.

We will add the above reasoning to Appendix A.

Regarding 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.

The 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.$

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.

Thank 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.

We hope that our response addresses your concerns. We are open to further discussions!

Thank you for the feedback and suggestions! We address the concerns below and will be happy to discuss any of the raised issues further.

Continuity being the new axiom, I am not fully convinced with the example that it is important (mentioned in Appendix A)

Regarding 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).

Also, 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.

Can authors cite and discuss about the following work - "Position: Measure Dataset Diversity, Don't Just Claim It". ICML'24

Thank 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.

Axioms could've been explained formally using math.

In the paper, we opted for more intuitive definitions and will add formal versions in the revised text.

As 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}$.

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)$.

Axiom 2 (Uniqueness). Suppose that for $A,B \in D_n$:

• $a_{ij}=b_{ij}$ for all $i>2, j>2$
• $b_{1i}=b_{2i}$ for all $i$
• $a_{2j}=b_{2j}$ for all $j>2$
• $a_{1j}>0$ for all $j>1$

Then $\mathrm{Diversity}(A) > \mathrm{Diversity}(B)$.

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.

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.

Thank you for the reference, we will add a discussion on submodular functions in the updated version.

Submodular 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).

Usually, 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$.

We 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.

In most of the practical situations one is interested in coming up with a subset of the data starting from no datapoints.

Thank 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.

do these corner cases (particularly for the determinant-based examples) occur regularly?

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.

Please, 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.

We hope that our response addresses the raised issues.