Thank you very much for appreciating our work and helping us correct the typos! We would like to address your insightful questions with the following responses.

What is the role of the random partitioning of the set V?

We consider scenarios where the ground set V is so large that a single GPU cannot process all elements simultaneously. Consequently, we must partition $V$ into various partitions, $S_1, S_2, \dots, S_m$, to obtain individual representations and subsequently combine them. We suggest that methodologies should be capable of processing and aggregating each subset from a set partition, yielding an identical representation as if the entire set was encoded at once (Identity Property). For clarity, this can be expressed as f(V) = $g(f(S_1), f(S_2), \dots, f(S_m))$, where $m$ can vary while remaining less than or equal to $n$. According to Theorem 4.2, our methods are designed to support the random partitioning of the set $V$.

What is the impact of the random partitioning in the experiments?

In our theorems, we do not impose any limitations on the size or number of partitions, allowing for arbitrary partitioning. In practical terms, we use two partitions (m=2) when comparing HORSE with the baselines. Furthermore, we present Figure 3 to demonstrate the impact of varying the number of partitions and the size of each partition on the results. While all neural subset methods experience a decline in performance as the number of partitions increases, HORSE demonstrates significantly more robust and superior performance. This implies that HORSE is more robust in large-scale settings.

To provide further evidence and for your convenience, we have included new results on BindingDB-2 in the table below. Please note that for simplicity, we maintain an equal size for each partition. Otherwise, there would be numerous possible partitioning methods, making experimentation challenging.

How to define the "effective" aggregation function in Property 3.1?

The aggregation function can be calculated based on our proof of Theorem 4.2. Specifically, for our method HORSE, the expression of g is defined in the following formula:

$$g(\{h(S_1), \dots, h(S_m) \} ) \coloneqq \text{diag}\left(\sum_{i=1}^m h_1(S_i)\right)^{-1} \cdot \sum_{i=1}^m h_2(S_i),$$

where $h_1(S_i) = nl(\hat{A}^{(i)})\mathbb{1}_{n_i}$ and $h_2(S_i) = nl(\hat{A}^{(i)})S_iW^v.$ The algorithm $h(S_i)$ can be found in our Algorithm 1. In practice, due to the neural network's ability to learn useful $h_1(S_i)$ and $h_2(S_i)$, set-related works typically employ pooling methods as the aggregation method, e.g., [1,2,3,4]. In our work, we use the most common method – mean pooling. We also conducted ablation studies on the pooling methods to demonstrate the effectiveness of the aggregation methods. These four methods have similar overall performance, with sum pooling and mean pooling being slightly better.

We sincerely thank you once again for your time and valuable contribution. Should you have any additional suggestions or questions, please do not hesitate to let us know.

---

[1] Maron et al., "On learning sets of symmetric elements," ICML, 2020.

[2] Zaheer et al., "Deep Sets", NIPS 2017.

[3] Willette et al., "Universal Mini-Batch Consistency for Set Encoding Functions", arXiv 2022.

[4] Xie et al., "Enhancing Neural Subset Selection: Integrating Background Information into Set Representations", ICLR 2024.

Thank you very much for your appreciation of our work and for posing such interesting and promising questions! We will first offer some clarifications and then proceed to response to your insightful questions.

Some confusion regarding the experimental settings

As stated in the Introduction, the framework of our problem is derived from references [1,2]. For tasks involving neural subset selection, all existing methodologies necessitate the construction of models to learn a set function, $F(S,V)$. Our enhancement to [1, 2] involves considering scenarios where the ground set V is so large that a single GPU cannot process all elements simultaneously. Consequently, we must partition V into various sections, $S_1, S_2, \dots, S_m$, to obtain individual representations and subsequently combine them.

We suggest that methodologies should be capable of processing and aggregating each subset from a set partition, yielding an identical representation as if the entire set was encoded at once (Identity Property). For simplicity, this can be expressed as $f(V) = g(f(S_1), f(S_2), …, f(S_m)$, where m can vary while remaining less than or equal to $n$.

In our theorems, we do not impose any limitations on the size or number of partitions, meaning the partition can be arbitrary. In practical terms, we use two partitions (m=2) when comparing HORSE with the baselines. Moreover, we present Figure 3 to demonstrate how variations in $m$ and $n_i$ will impact the results. While all neural subset methods will experience a drop in performance, HORSE exhibits significantly more robust and superior performance. This implies that HORSE will be more robust in large-scale settings.

To provide further evidence and for your convenience, we have included new results on BindingDB-2 in the table below. Please note that for simplicity, we ensure that each partition has an equal size by maintaining the same value of $n_i$ across all partitions. Otherwise, there would be numerous possible partitioning methods, making experimentation challenging.

Can the proposed framework be used in the image pixel grouping task, e.g., image segmentation and predicting a subset of pixels from the entire image pixels?

In Neural Subset Selection tasks, the central premise is the necessity to identify an optimal subset for each ground set. In other words, we can only predict one optimal subset S* from one set V. In contrast, determining an optimal subset for image segmentation is challenging, as it is difficult to pinpoint which part is optimal. Nonetheless, predicting a subset of pixels (that satisfy certain properties) appears to align with the objectives of neural subset selection tasks. In this case, HORSE can be potentially applied, as pixels can serve as elements and the entire image constitutes the ground set. The primary challenge when employing neural subset selection methods might be encoding each pixel into a useful embedding, which we consider as a very promising future extension of our methods.

Why is the partitions required to be disjoint?

Our ultimate objective is to enable methods to process and aggregate each subset from a set partition, producing a representation identical to encoding the entire set at once. Intuitively, if the subsets overlap, aggregating their representations would introduce redundant information, making it challenging for models to identify the true ground set V. This difficulty arises as models may not discern that $\\\{ e_1, e_2, e_3, e_4 \\\}$ and $\\\{ e_1, e_2, e_2, e_3, e_3, e_4 \\\}$ represent the same set. Thus, overlapping subsets can pose additional challenges for model learning. For instance, given $V = \\\{e_1, e_2, e_3, e_4\\\}$, it is easier to train a model to satisfy $f(V) = g(f(\\\{e_1, e_2\\\}), f(\\\{e_3, e_4\\\}))$ than to train a model to satisfy $f(V) = g(f(\\\{e_1, e_2, e_3\\\}), f(\\\{e_2, e_3, e_4\\\}))$. The second method required the models to possess the capability to disregard the repeated elements.

Thank you for your time and thoughtful consideration again. If you have any concerns or questions, please don't hesitate to reach out to us.

---

[1] Ou et al., “Learning neural set functions under the optimal subset oracle” NeurIPS 2022.

[2] Tschiatschek et al., “Differentiable submodular maximization,” IJCAI, 2018.

We sincerely appreciate the time and effort you have invested! Your suggestions regarding notations and typos have greatly assisted us in revising our manuscript. For the remaining concerns, we offer the corresponding clarifications below.

The difference between neural subset selection and (core) subset selection.

As described in our Introduction, the configuration of our problem primarily originates from references [1, 2], which postulate that the underlying process of determining the optimal $S^*$ can be modeled by a utility function $F_\theta (S;V)$ parameterized by $\theta$, and the following criteria:

$$S^* = argmax_{S \in 2^{V}} F_\theta (S; V).$$

This is the reason our task is referred to as Neural Subset Selection. The key distinction between Neural Subset Selection and (Core) Subset Selection is that our tasks possess the ground truth of the optimal subsets. For instance, in the set anomaly detection (Figure 4&5 in [1]), several images within an image set exhibit notable differences from the others based on certain properties.

In the case of (core) subset selection, there may not be an optimal subset as each item contributes some positive utility, necessitating the cardinality constraint. Such problems often employ methods that maximize a submodular function [3, 4, 5]. However, from my perspective, these are two distinct tasks. To prevent any confusion among readers, we will include a paragraph in our related work to discuss the differences between the two tasks. We would greatly appreciate any references you could provide, and kindly correct us if we have missed any.

What is the objective function for training?

We follows the objective function from [1], which is as follows. (Apologies for the error in the first line; it should be $log p_\theta (S | V)$ intead of $log p (S | V),$ We retained the mistake due to the presentation issues on OpenReview.)

$$argmax_\theta\ \mathbb{E}_{\mathbb{P}(V, S)} [log p (S | V)]$$ $$s.t. p_\theta (S | V) \propto F_\theta (S ; V), \forall S \in 2^V,$$

where the constraint admits the learned set function to obey the objective defined in

$

S^* = argmax_{S \in 2^{V}} F_\theta (S; V).

$

Since our work mainly concentrates on the model, we offer a concise explanation in the second paragraph of the Introduction and encourage readers interested in the objective to refer to Appendix D.3 for further details.

What is the initiation method of $\xi$?

Thank you for the reminder. We have included the initialization method for \xi = {s_1, s_2, \dots, s_m} in our revised draft. Specifically, we initialize it by sampling a random initialization for $m$ embeddings $\xi \in \mathbb{R}^{m \times d_s}$ where $d_s$ is the dimension of each embedding. Specifically,

$

\xi \sim \mathcal{N}(\mu, \text{diag}(\sigma)) \in \mathbb{R}^{m \times d_s},

$

where $\mu \in \mathbb{R}^{1 \times d_s}$ and $\sigma \in \mathbb{R}^{1 \times d_s}$ are learnable parameters. This method is inspired from [6], which has been demonstrated to be effective in slot-based attention.

Do $h(V)$ and $h(S)$ share the same $\xi$ ?

Indeed, they share the same $\xi$. Here, $[S_1, S_2, \dots, S_m]^T$ is constructed from $V$ using a partitioning method. We employ $h(S_i)$ to emphasize that the calculations of $h(S_i)$ are induced by V and its corresponding partitions, achieved by splitting the input matrix $V$ into several parts, as described in Algorithm 1 in our appendix. Throughout the calculation, any other input remains the same for $h(S_i)$ and $h(V)$. Therefore, we appreciate your suggestion to use $h_V(S)$, as it is more meaningful.

Why we need Theorem 4.1 and what is the definition of permutation matrix?

Sets are inherently permutation invariant by construction. However, since models process sets in matrix form, a general MLP cannot guarantee the permutation invariance property. This is the reason we require Theorem 4.1. As previous works, such as [1,7], share this consensus, we do not emphasize that the input is a matrix. Furthermore, designing models to satisfy such permutation-invariant properties is an important research topic, and numerous works have been dedicated to it, such as [1, 7, 8].

Furthermore, you are correct that a permutation matrix is a square binary matrix with exactly one entry of 1 in each row and each column, and all other entries being $0$, as defined in Linear Algebra. Here, $\pi_S \in \mathbb{R}^{n_i \times n_i}$ and $\pi_V \in \mathbb{R}^{n \times n}.$ In order to accommodate readers with a variety of backgrounds, we have incorporated your suggestions and revised the description of Theorem 4.1, emphasizing that the input is in matrix form and defining the permutation matrix $\pi.$

Thank you again for your valuable time and efforts in reviewing our manuscript. We would appreciate knowing if you have any additional feedback or suggestions.

---

[1] Ou et al., "Learning Neural Set Functions under the Optimal Subset Oracle," NeurIPS, 2022.

[2] Tschiatschek et al., "Differentiable Submodular Maximization," IJCAI, 2018.

[3] Wei et al., "Submodularity in Data Subset Selection and Active Learning," ICML, 2015.

[4] Mirzasoleiman et al., "Coresets for Data-Efficient Training of Machine Learning Models," ICML, 2020.

[5] Yang et al., "Towards Sustainable Learning: Coresets for Data-Efficient Deep Learning," ICML, 2023.

[6] Locatello et al., "Object-Centric Learning with Slot Attention," NeurIPS, 2020.

[7] Zaheer et al., "Deep Sets," NIPS, 2017.

[8] Maron et al., "On Learning Sets of Symmetric Elements," ICML, 2020.

Dear Reviewer aVVy,

We sincerely appreciate your valuable and helpful suggestions. We are wondering whether you have any more suggestions or questions after our response. Specifically, do you have any questions on our training objective or do you have any reference about Corset Selection to help use differentiate Neural Subset Selection with Corset Selection. Moreover, if you find our response satisfactory, we kindly invite you to consider the possibility of improving your rating.

Sincerely, Authors

Ablation Studies on the pooling methods

Our method employs pooling methods as our aggregation function. Following the common selection in set-related works, such as [1, 2], we use mean pooling, as it typically yields better performance. In our studies, we also find that these four methods exhibit similar overall performance, with sum pooling and mean pooling being slightly superior.

How does HORSE handle imbalanced datasets or noisy data?

In neural subset selection tasks, the imbalance may arise from differences in the size of the optimal subsets and the size of the ground set. To provide empirical evidence, we conduct additional experiments that showcase INSET's consistent superiority over the baselines, even in scenarios with imbalanced ground set sizes. Specifically, we train the model on the two-moons dataset using fixed optimal subset sizes of 12 and evaluate its performance on various ground set sizes ranging from 200 to 1000.

For imbalanced datasets, we carry out additional experiments using the CelebA Dataset to underscore INSET's consistent superiority over the baseline models. Specifically, we will randomly insert one wrong image in the optimal subset for anomaly detection tasks. From the results, the performance of all methods drops significantly, while HORSE still outperforms the others. This inspires further promising research on the topic to make neural subset selection methods more robust against noisy labels.

We greatly appreciate the time and effort you have invested! In response to your concerns and insightful questions, we have provided detailed clarifications and additional experimental results.

Are there any state-of-the-art GNN-based or deep sets models that utilize attention mechanisms?

Most GNN-based methods for subset selection are engineered to select a subset from the entire training dataset for efficient model training, as seen in examples like [1, 2]. This is commonly referred to as Coreset Selection. In this context, there is no supervision for the optimal subset. Thus, these methods cannot be directly applied to our tasks.

Regarding deep sets with attention mechanisms, we also use the set-transformer [3] as a baseline. To include a broader and more up-to-date set of baselines, we have added two more: Set-T (ISAB) denotes one of the variants of the Set Transformer [3], and EquiVSet-T represents the addition of EquiVSet [4] with an self-attention mechanism. Please note that EquiVSet is one of the state-of-the-art methods in the Neural Subset Selection field. Due to time constraints and for your convenience, we have only reported a portion of the results for the Product Recommendation tasks. We will include the full results in our revised version once it is completed.

More detailed ablation study to analyze the impact of different components of the proposed method.

Thank you for your suggestion. There are two main choice will influence our method's performance, i.e., pooling and partitioning method. Firstly, we report various choices of pooling methods as the aggregation function to demonstrate their impacts. Due to space limitation, we kindly invited your to refer table 1 in the following comments window. These four methods have similar overall performance, with sum pooling and mean pooling being slightly better. We use mean pooling in our method across different tasks and datasets.

For the partitioning strategy, we use random partitioning, which is a common choice. Indeed, the number of partitions will impact the performance of HORSE. We have presented Figure 3 to demonstrate how variations in the number of partitions and the size of each partition will impact the results. While all neural subset methods will experience a drop in performance when the number of partitions increase, HORSE exhibits significantly more robust and superior performance. This implies that HORSE will be more robust in large-scale settings.

What is the computational complexity of HORSE compared to other methods.

Our framework shares a simlar framework with our baselines, EquiVSet and INSET. When considering only the attention mechanism, our method's time complexity is O(nk), which is lower than that of self-attention-based methods such as EquiVSet-T, which has a time complexity of O(n^2). Therefore, computational complexity should not be a major concern, as HORSE is more scalable and performs better and faster than EquiVSet-T, especially on extremely large datasets.

Provide further theoretical insights into the properties of HORSE and its relationship to the Identity Property

We provide Theorem 4.2 in our paper to illustrate that the attention mechanism we proposed adheres to the Identity Property. This suggests that HORSE can process and aggregate each subset from a set partition, resulting in the same representation as encoding the entire set at once.

How does HORSE handle imbalanced datasets or noisy data?

Due to space limitations and for your convenience, we have included some empirical studies in the following comments section. We kindly invite you to review them. These results demonstrate that HORSE can still achieve better performance than our baselines.

What are the potential challenges and limitations of applying HORSE to real-world applications?

We concur that in real-world applications, noisy data and distribution gaps may diminish the performance of HORSE, an issue also overlooked by other neural subset selection methods. As such, we eagerly anticipate future research that could potentially enhance the robustness of these methods. From a deployment perspective, there are additional concerns, such as communication and synchronization issues, which fall outside the scope of our paper.

Thank you for your time. If you have any additional questions, we would be delighted to discuss them further.

---

[1] Breustedt et al., "On the Interplay of Subset Selection and Informed Graph Neural Networks," 2023.

[2] Jain et al., "Efficient Data Subset Selection to Generalize Training Across Models: Transductive and Inductive Networks," 2024.

[3] Lee et al., "Set Transformer: A Framework for Attention-Based Permutation-Invariant Neural Networks," 2019.

[4] Ou et al., "Learning Neural Set Functions under the Optimal Subset Oracle," 2022.