Simplicial SMOTE: Oversampling Solution to the Imbalanced Learning Problem

Thank you for the high evaluation of our paper, especially noting the use of topological data analysis tools for a general learning problem and the overall quality of experiments and presentation.

Regarding questions:

Q1: The authors could be a bit more clear on why a simplicial complex may be better than a graph for creating synthetic points for oversampling-- it feels like there is some type of local decision-boundary type of argument which would make clear when this method should be valuable.

A1: We assume that a geometric model represented by a simplicial complex is better than one of the graph, i.e. the data distribution is well-approximated by a union of simplices of a geometric neighborhood complex for some set of the neighborhood size parameter k and and the maximal simplex dimension p. We also hypothesize that p could be related to the intrinsic dimension of the data. Informally, as we state in the last two paragraphs of introduction, one could not fill the whole data manifold using samples from the edges of the neighborhood graph as edges are 1-dimensional. By increasing the dimension of simplices we fill more space, ideally to match the simplex dimension to the local intrinsic dimension of data. For graphic explanation see https://anonymous.4open.science/r/simplical-smote/motivation.png.

Addressing mentioned weaknesses:

W3: There empirical results could be presented better. The tables are fine and are valuable because they give access to the raw data. However, they could benefit from the addition of confidence intervals. Alternatively, additional visualizations may more clearly summarize the value of the proposed algorithm for each dataset.

A2: Unfortunately, at the time of writing the paper, we did not find a suitable and easy-to-understand way to present confidence intervals and significance testing results between a dozen of methods in a readable and compact way. We would improve the presentation with the critical difference diagrams with pairwise or multiple testing.

Thank you for noting the innovativeness of our approach of using topological data analysis tools to address the imbalanced learning problem and the overall clarity of presentation.

Below we added running time showing that our method is only 1.4 times slower than SMOTE, and made publicly available the code of Simplicial SMOTE and the main experiment at https://anonymous.4open.science/r/simplical-smote/. Hope our feedback would allow you to re-evaluate our paper.

Q1: How sensitive is the performance of Simplicial SMOTE to the choice of parameters such as the neighborhood size parameter k and and the maximal simplex dimension p? How were the optimal parameters selected for each dataset in the evaluation?
Q4: Could the authors provide more detailed implementation information to aid reproducibility, such as the specific configurations or hyperparameters used during the evaluation?

A1: The parameter selection is described in the paper, please refer to the second paragraph of section 4.2. We used the grid search for k with step 2, and for p with step 1 within a range which was dataset-specific, depending on the number of data points and features. You can refer to the parameter selection in the main experiment code https://anonymous.4open.science/r/simplical-smote/experiment.py.

Q2: Could the authors provide more insights into the scalability of the proposed method with respect to the number of data points and dimensionality of the datasets? Have the authors tested the method on datasets with larger dimensionality to understand the impact on computational resources and performance?
W2: Limited evaluation on high-dimensional datasets.

A2: We have considered datasets from the popular package imbalanced-learn, with datasets having up to several hundreds of features. The clique expansion stage does not depend on data dimensionality; for the k-nearest neighbors graphs with the same edge density there would not be an impact on the running time of the algorithm.
One of the assumptions of our method is the manifold hypothesis – despite the data being high-dimensional, described by hundreds or thousands of features, its intrinsic dimensionality is much lower. By the increased dimension of a simplex to sample from, we can better match the intrinsic geometry of the data than SMOTE which models the data as a union of 1-dimensional edges spanned by pairs of existing data points being sufficiently close. For graphic explanation see https://anonymous.4open.science/r/simplical-smote/motivation.png.

Q3: Can the authors provide more details on the computational complexity of Simplicial SMOTE in comparison with the original SMOTE, especially concerning the time and memory requirements? Are there any optimizations suggested to mitigate the computational demand, especially when applying Simplicial SMOTE on large-scale or high-dimensional datasets?
W1,3: Increased computational complexity due to a single additional hyperparameter (e.g., maximal simplex dimension) and a concern whether this could hinder the real-time or practical applications of the proposed method.

A3: To answer your question whether the method is practical we provide the running time of an experiment on all 23 datasets, with the same pipeline as in the paper including scaler, oversampler and logistic regression as the classifier. We run 5-fold cross-validation repeated 5 times for the neighborhood size parameter k=10. The maximal simplex dimension p was set to 3. Different values of p does not affect computation time as we our current implementation of clique expansion algorithm uses the Bron-Kerbosch algorithm to find all maximal simplices and then subdivide them (which is inexpensive compared to MCE) to p-simplices according to maximal simplex dimension p. Computation was run on 2x Intel(R) Xeon(R) Gold 6248R CPU @ 3.00GHz system, with 48 cores and 96 threads total.

SMOTE, k=10 – 15.03 sec (0.65 sec per dataset on average)
Simplicial SMOTE, k=10, p=3 – 20.79 sec (0.90 sec per dataset on average)

To conclude, the running time of a typical scenario to fit an oversampler and a linear classifier 25 times is only 1.4 times slower for the Simplicial SMOTE compared to the original SMOTE algorithm.

If a practitioner does not have a time for an extensive grid search of hyperparameters she/he can try to use Simplicial SMOTE with the default value of maximal simplex dimension p, which considers the exact maximal simplices in the neighborhood graph, depending on neighborhood size k, i.e. not limiting their dimension. This in many cases leads to better performance than of SMOTE, yet we obtained the best results by searching for the optimal maximal simplex size. We also observed that simply raising a dimension of a maximal simplex to sample from an edge, as did in SMOTE, to a triangle often resulted in better quality metrics of the downstream tasks. We also plan to release the computationally optimized version of Simplicial SMOTE upon the paper acceptance.

Q5: Have the authors considered comparing Simplicial SMOTE with more recent methods or extensions of SMOTE, other than the ones mentioned in the paper? How does Simplicial SMOTE compare with state-of-the-art methods in handling imbalanced datasets? How can Simplicial SMOTE be extended to handle multi-class imbalanced datasets? Have the authors considered evaluating the method in multi-class scenarios?

A5: We compared Simplicial SMOTE with classic SMOTE extensions such as Borderline SMOTE, Safe-level SMOTE, and ADASYN, recent methods like Mixup, and the methods taken from the paper [Kovacs19] evaluating 85 SMOTE variants with DBSMOTE, AHC and LVQ-SMOTE shown to get rank 1 for different classifiers and metrics.
As most of the existing work on SMOTE and its variants we have considered only the binary case. Oversampling methods trivially handle the multi-class scenario, by oversampling all classes except major to match it in size. We would state it explicitly in the updated version of text. Imbalanced-learn, the popular framework implementing SMOTE and several its extensions, contains benchmark data which is binary labeled as well.

[Kovacs19] Kovacs G., An Empirical Comparison and Evaluation of Minority Oversampling Techniques on a Large Number of Imbalanced Datasets

Thank you for noting the problem significance, modularity of our approach, ready to be combined with existing variants of SMOTE, an extensive experimental part and good presentation.

Below we added the running time showing that our method is only 1.4 times slower than SMOTE, and made publicly available the code of Simplicial SMOTE and the main experiment at https://anonymous.4open.science/r/simplical-smote/. Hope our answers would allow you to reconsider the paper evaluation.

Regarding your questions (Q) and stated weaknesses (W):

Q1: What's the time performance of the proposed and baseline algorithms?
W3: The proposed algorithm is more complicated and slower than the baseline algorithms (see Table 1). However, the time performance of the proposed and baseline algorithms is not shown in the paper. Without time performance, it's hard to judge the tradeoff between time and accuracy in the experimental comparisons.
A1: Below we provide the running time of an experiment on 23 datasets, with the same pipeline as in the paper including scaler, oversampler and logistic regression as the classifier. We run 5-fold cross-validation repeated 5 times for the neighborhood size parameter k=10. The maximal simplex dimension p was set to 3. Different values of p does not affect computation time as we our current implementation of clique expansion algorithm uses the NetworkX’s Bron-Kerbosch algorithm to find all maximal simplices and then subdivide them (which is inexpensive compared to MCE) to p-simplices according to maximal simplex dimension p. Computation was run on 2x Intel(R) Xeon(R) Gold 6248R CPU @ 3.00GHz system, with 48 cores and 96 threads total.

SMOTE, k=10 – 15.03 sec (0.65 sec per dataset on average)
Simplicial SMOTE, k=10, p=3 – 20.79 sec (0.90 sec per dataset on average)

To conclude, the running time of a typical scenario to fit an oversampler and a linear classifier 25 times is only 1.4 times slower for the Simplicial SMOTE compared to the original SMOTE algorithm on the benchmark datasets from the imbalanced-learn package.

Q2: Are there any assumptions and limits on the level of class imbalance?
Q3: Are there any assumptions on the data distribution to implement the simplicial SMOTE? W1: In the setup section (section 3, p3), it lacks the assumptions and descriptions on the data distribution (x,y), and especially the level of class imbalance. Without data distribution assumptions, it will limit the guidance for practitioners.
A2: We assumed that a geometric model represented by a simplicial complex is better than one of the graph, i.e. the data distribution is well-approximated by a union of simplices of a geometric neighborhood complex for some set of the neighborhood size parameter k and and the maximal simplex dimension p. We also hypothesize that p could be related to the intrinsic dimension of the data, and the neighborhood size depends on data’s local geometry.
We had no specific assumptions on the level of class imbalance (like most of the literature). Common sense argument is that the class imbalance should be at a level where an empirical sample of the minor class is representative for the minor class distribution.

W2: There is no analysis of the theoretical guarantee of the algorithm's performance.
A3: Indeed, in the paper we have not provided any theoretical analysis of the proposed algorithm. We published the empirical results of classifiers trained on oversampled data, as with most of the papers on SMOTE and its extensions.
In the process of working on the text, following [Blagus13], we investigated the issue of preserving the mean and variance of data for multivariate Gaussian random variables, but did not consider it new for publication. Also, there was an idea to show that the empirical distribution generated by the proposed algorithm is closer to the ground truth distribution of data in the Wasserstein distance sense, from which we abstained due to text volume limitations imposed by the conference.
Except [Blagus13], while writing an answer to your question we have discovered several recent papers, studying the theoretical guarantees of SMOTE [Elredy23] and Mixup [Kimura21] methods. We would consider the applicability of the proposed and newer techniques to the theoretical analysis of Simplicial SMOTE.

References
[Blagus13] Blagus R., Lusa L. SMOTE for High-dimensional Class-imbalanced Data, BMC Bioinformatics (2019)
[Kimura21] Kimura, M. Why Mixup Improves the Model Performance, International Conference on Artificial Neural Networks (2021)
[Elredy23] Elredy D., Atiya A., Kamalov F. A Theoretical Distribution Analysis of Synthetic Minority Oversampling Technique (SMOTE) for Imbalanced Learning, Machine Learning (2023)

Thank you for a very thorough review, we find your comments very valuable, letting us improve the paper. We also thank you for noting the originality and modularity of our approach, ready to be combined with existing variants of SMOTE.

Below we added the running time showing that our method is only 1.4 times slower than SMOTE, our motivation behind the algorithm, and made the code of Simplicial SMOTE and the main experiment publicly available at https://anonymous.4open.science/r/simplical-smote/. Hope it would allow you to re-evaluate our paper.

Regarding questions:

Q1: How the datasets were selected? The imbalanced-learn library contains 27 datasets but only 23 were selected for the experiments.
A1: For the reason of the speed of an extensive evaluation of 12 oversampling methods using the hyperparameter grid search, we have selected datasets from the imbalanced-learn package which are not exceeding 20000 data points.

Q2: What was the running time of the proposed method and how it compares with other methods under study?
A2: Below we provide the running time of an experiment on 23 datasets, with the same pipeline as in the paper including scaler, oversampler and logistic regression as the classifier. We run 5-fold cross-validation repeated 5 times for the neighborhood size parameter k=10. The maximal simplex dimension p was set to 3. Different values of p does not affect computation time as we our current implementation of clique expansion algorithm uses the NetworkX’s Bron-Kerbosch algorithm to find all maximal simplices and then subdivide them (which is inexpensive compared to MCE) to the p-simplices according to maximal simplex dimension p. Computation was run on 2x Intel(R) Xeon(R) Gold 6248R CPU @ 3.00GHz system, with 48 cores and 96 threads total.

SMOTE, k=10 – 15.03 sec (0.65 sec per dataset on average)
Simplicial SMOTE, k=10, p=3 – 20.79 sec (0.90 sec per dataset on average)

To conclude, the running time of a typical scenario to fit an oversampler and a linear classifier 25 times is only 1.4 times slower for the Simplicial SMOTE compared to the original SMOTE algorithm on the benchmark datasets from the imbalanced-learn package.

Q3: The authors use Mixup in their experiment which interpolates not only the feature values x but also target vectors y. Such interpolated target vectors are easy to use in NN but not necessarily in GBT or kNN used in the experiments. How it was applied? If no target vector interpolation was used, how the target value was established?
A3: In the introduction we stated that we consider the sampling approach used in Mixup (which is generally presented as the data augmentation algorithm) for oversampling of the minor class, without label interpolation. Therefore, we upsampled only the data's minor class, with the label for a synthetic point assigned to be the same as the minor class. Thank you for highlighting that it is not completely clear, it is helpful to us to further improve the text.

W1: Lack of motivation. The last two paragraphs of introduction are unclear.
A4: We were motivated by the assumption that a geometric model represented by a simplicial complex is better than one of the graph, i.e. the data distribution is well-approximated by a union of simplices of a geometric neighborhood complex for some set of the neighborhood size parameter k and and the maximal simplex dimension p. We also hypothesize that p could be related to the intrinsic dimension of the data, and the neighborhood size depends on data’s local geometry.
As we state in the last two paragraphs of introduction, one could not fill the whole data manifold using samples from the edges of the neighborhood graph as edges are 1-dimensional. By increasing the dimension of simplices we fill more space, ideally to match the simplex dimension to the local intrinsic dimension of data. For the graphic explantion see https://anonymous.4open.science/r/simplical-smote/motivation.png

W2: The method is currently not suitable for handling multi-class data, tested only on binary classification problems.
A5: Our method can be used to handle the multi-class scenario, by oversampling all classes except the major to match it in size. Yet, as most of the existing works on SMOTE and its variants, we considered only the binary case. We should state it explicitly in the updated version of text.

W3: The paper claims to extend several other SMOTE variants like ADASYN, Safe-level SMOTE and Border-line SMOTE but only the latter is actually tested in the experiments.
A6: We have reported the evaluation results of the simplicial extension of Borderline SMOTE due to the fact that the original Borderline SMOTE performed better than Safe-level SMOTE and ADASYN (see Tables 3, 4, 6 and 7). Moveover, the original Borderline SMOTE was either the best or the second-best among non-simplicial oversampling algorithms, and its simplicial version was shown to always perform better than the original one.

W4: Related works comments related to Mixup and ROS, and the geometric sampling methods taxonomy
A7: Thank you for highlighting that whether we upsample only the minor class via SMOTE or Mixup (which is generally presented as the data augmentation algorithm) is not completely clear. For the former we implied that it is known for SMOTE practitioners and the latter needs a more explicit explanation. We used Mixup for the oversampling, as it is widely known, improves the solution of the imbalanced learning problem, and fits well to the family of geometric sampling algorithms.
In topological data analysis there is a concept of filtration of a metric space, where given all pairwise distances we can view them as edges of a graph and add them one by one in increasing order. ROS and Mixup correspond to the extremes of the filtration, with ROS being the zero step and Mixup the last one. SMOTE corresponds to a graph somewhere in between of the filtration, and Simplicial SMOTE to the clique complex of that graph. Next, one decides from simplices of which dimension to sample: 0-simplices for ROS, 1-simplices for Mixup and SMOTE, 2-simplices and greater for Simplicial SMOTE.

W5: Artificial data experiment purpose is unclear
A9: The purpose of the artificial data experiment was to show the importance of local sampling to respect data’s geometry and topology, which makes SMOTE-based algorithms better than Mixup. In all four examples if the sampling is not local, the synthetic points of the minor class shown in red would either mix with the points of the major class or would result in completely different topology of the decision boundary like in the circle inside the circle example.

W6: The statistical comparisons are performed only with respect to the original SMOTE from 2002 and not to any of the more modern extensions
A10: Indeed, we showed that both our methods perform significantly better than the original SMOTE, by providing two single-page tables of p-values for each of the used metrics. Unfortunately, we did not find a suitable and easy-to-understand way to present significance testing results between a dozen of methods in a readable and compact way. We will be kindly obliged if you could recommend something in this direction.

W7: Lack of evaluation with some state-of-the-art implementation of GBT algorithm like CatBoost or XGBoost
A11: During our experiments we have tried Catboost as a classifier, which while resulting in slightly higher values of evaluation metrics (in most cases, the difference was insignificant), but was much slower, so we decided to resort to the implementation of gradient boosting algorithm from the scikit-learn library.

W8: F1 score metric has been criticized in imbalanced learning literature. It'd be better to also report G-mean value and other specialized metrics.
A12: Thank you for the suggestion. We used F1 score and MCC as the complementary pair of metrics. F1 score emphasizes the correct classification of the minor class, while MCC considers all elements of the contingency table like G-mean does. We cite the references describing the advantages of MCC in our paper [Chicco20,23].

W9: Making the implementation of the method available would increase the reproducibility of this research and its potential impact.
A13: We had to obtain permission to make the code publicly-available, and it took more time than expected. For now, everything is OK, and we have our method implemented in Python, made available at an anonymized repository https://anonymous.4open.science/r/simplical-smote/. We plan to release the computationally optimized version of Simplicial SMOTE at publicly-available github repository upon the paper acceptance.

References
[Chicco20] Chicco D., Jurman G. The Advantages of the Matthews Correlation Coefficient (MCC) over F1 Score and Accuracy in Binary Classification Evaluation. BMC Genomics (2020)
[Chicco23] Chicco D., Jurman G. The Matthews Correlation Coefficient (MCC) Should Replace the ROC AUC as the Standard Metric for Assessing Binary Classification. BioData Mining (2023)