Advancing Interaction-Sensitive Feature Selection: Novel Relief-Based Algorithms, Expanded Comparisons, and Recommendations for Biomedical Data Mining

Kia Kazemi-Nia; Harsh Bandhey; Philip J. Freda; Ryan J. Urbanowicz

Source-linked AI summary

Advancing Interaction-Sensitive Feature Selection: Novel Relief-Based Algorithms, Expanded Comparisons, and Recommendations for Biomedical Data Mining

Kia Kazemi-Nia, Harsh Bandhey, Philip J. Freda, Ryan J. Urbanowicz

arXiv:2608.28552v1Aug 28, 2026cs.LG

TL;DR

Feature-selection methods often trade interaction sensitivity against computational cost or algorithm dependence. This study expands and refactors scikit-rebate and benchmarks RBA variants across simulated genomic datasets. Most RBAs detected 2-way interactions, while far-scoring variants favored interactions at the expense of main effects and refactoring reduced runtimes substantially.

Problem
Filter methods often struggle to detect feature interactions, whereas wrapper and embedded methods can be computationally expensive or algorithm-dependent.
Method
The study refactors and expands scikit-rebate, adds SWRF*, µ-Relief, and five novel RBA variants, and benchmarks 12 RBAs across simulated genomic datasets.
Results
Most RBAs detected 2-way epistasis; far-scoring variants performed best for 2-way interactions but lost main-effect sensitivity, while non-star variants offered a balance.
Takeaways & Limitations
SWRF, MultiSWRF, MultiSURF, and MultiSWRFDB were strongest across main-effect and 2-way interaction datasets, with MultiSWRFDB best when 3-way interactions were included.
Takeaways & Limitations
The study calls for evaluation on diverse real-world datasets, broader 3-way interaction settings, larger feature spaces, and additional endpoint types.

Abstract

from arXiv · show

As a precursor to high-dimensional biomedical data modeling, reliable feature selection can reduce computational expense, improve modeling performance, and yield simpler, more interpretable models. However, most filter-based feature selection methods struggle to detect feature interactions, while wrapper or embedded feature selection methods are computationally expensive. Relief-based algorithms (RBAs) are filter methods that are sensitive to feature interactions while mitigating these other limitations. This study (1) refactors, optimizes, and expands the scikit-rebate Python package with existing and newly proposed RBA variants and (2) conducts rigorous RBA benchmark comparisons across diverse genomic simulations. We expand scikit-rebate to include SWRF*, mu-Relief, and 5 novel RBA variants implementing alternative strategies for neighbor selection and feature scoring. All RBAs were evaluated to compare predictive feature ranking and runtime across simulated genomic datasets varying in sample size, number of features, heritability, and underlying association type (e.g. main effects and interactions). All RBAs, except mu-Relief, were proficient in detecting 2-way interactions in noisy data. RBAs utilizing 'far' scoring were best at detecting 2-way interactions - with MultiSWRFDB* top-performing - but were far less sensitive to main effects. SWRF, MultiSWRF, MultiSURF, and MultiSWRFDB yielded top performance across main effect and 2-way interaction datasets with MultiSWRFDB performing best when also considering 3-way interactions. Refactoring of scikit-rebate resulted in 10 to 35-fold reductions in RBA runtimes. The newly introduced RBAs were among the strongest performing, and by robustly retaining both main effects and 2-way epistatic interactions, these algorithms preserve predictive signals for downstream modeling.

1 Introduction

Feature selection reduces dimensionality while preserving feature meaning, but efficient methods often struggle with predictive interactions. This study expands scikit-rebate and benchmarks broader RBA variants to address these limitations.

Motivation: Feature selection identifies informative features to build simpler, better-performing, and less-overfit models while preserving their original meaning.It reduces dimensionality without transforming features into a new mathematical space.
Motivation: Filter methods are appealing because wrappers are extremely computationally expensive and wrapper or embedded selections may not transfer across algorithms.Filters score features using intrinsic statistical properties rather than a particular machine-learning algorithm.
Motivation: Very few feature-selection methods consistently and efficiently detect features whose predictive value primarily comes from interactions.Exhaustive subset searches such as FOCUS are computationally expensive.
Relief-based algorithms: RBAs use local neighborhoods to detect pure epistasis without exhaustively exploring feature combinations and scale linearly with feature count.They scale quadratically with instance count, which can be mitigated by subsampling large datasets.
Study gap: Earlier benchmarks used limited feature counts, omitted SWRF* and µ-Relief, and left higher-order epistasis performance insufficiently established.Later 100-feature benchmarks showed inability to detect pure 4- or 5-way epistasis reliably.
Study aims: The study refactors scikit-rebate, adds SWRF*, µ-Relief, and five novel core variants, and evaluates their strengths across diverse simulated genomic datasets.It also provides updated recommendations for biomedical data-mining applications.

2 Methods

The methods section covers the implemented algorithms, package updates, datasets, analyses, and post-hoc evaluations used in the study.

Scope: The methods cover existing and newly proposed relief-based algorithms.
Scope: The study describes scikit-rebate updates, benchmarking datasets, and experimental analyses.
Scope: Post-hoc analyses are included alongside the primary experimental evaluation.

2.1 Existing Relief-based Algorithms

Relief-based algorithms rank features by updating weights from local instance comparisons. Their variants differ in neighborhood size, distance rules, far scoring, recalculated metrics, and deadband treatment.

Relief framework: RBAs return feature weights after training, with higher weights denoting greater feature importance.The original Relief algorithm iterates over selected training instances as targets.
Relief framework: Relief updates reduce weights for feature differences between a target and hit while increasing weights for differences between the target and miss.Updates among neighboring instances provide Relief’s interaction sensitivity.
Neighborhood selection: ReliefF uses k nearest hits and misses, whereas SURF automatically defines neighbors using the global mean pairwise distance.Larger k can improve noisy-data sensitivity but may reduce interaction sensitivity in small training sets.
Distance-based scoring: SURF* adds a far neighborhood with inverted scoring weights, improving 2-way interaction detection but reducing main-effect sensitivity.Far-neighborhood differences reverse the usual hit and miss contributions.
Distance-based scoring: SWRF* replaces binary near/far weights with a sigmoid gradient based on distance, global mean distance, and global standard deviation.The gradient smoothly decreases weights as distance approaches the mean.
Target-specific neighborhoods: MultiSURF* recalculates neighborhood metrics for each target and assigns zero weight to instances in its middle-distance deadband zone.Its near and far neighborhoods are defined relative to target-specific µi and σi.
Target-specific neighborhoods: MultiSURF excludes far neighbors during scoring while retaining target-specific neighborhood metrics.Prior benchmarking identified it as a strong general-use RBA across main effects, 2-way and 3-way interactions, and genetic heterogeneity.
µ-Relief: µ-Relief selects k hit and miss instances maximizing distance deviation from same-class averages but retains standard scoring weights for all selected neighbors.The study implemented it for categorical and quantitative outcomes.

2.2 Novel RBA Variants

The novel variants recombine sigmoid scoring, target-specific neighborhood metrics, far-neighbor exclusion, and deadband zones to alter feature-weight updates.

MultiSWRF variants: MultiSWRF* combines SWRF*’s sigmoid weight gradient with MultiSURF*’s per-target recalculation of µi and σi.It allows all instances to participate in updating W, as in SWRF*.
SWRF variants: SWRF applies SWRF*’s sigmoid gradient with global µ and σ but excludes far neighbors from feature scoring.This design is expected to recover main-effect performance relative to star variants.
MultiSWRF variants: MultiSWRF retains SWRF’s sigmoid gradient and far-neighbor exclusion while recalculating µi and σi for each target.It is expected to perform better on main effects as a non-star algorithm.
MultiSWRFDB variants: MultiSWRFDB* combines MultiSWRF* with MultiSURF*’s deadband, assigning zero weight to middle-distance instances.Its design excludes those instances from W updates while retaining far scoring.
MultiSWRFDB variants: MultiSWRFDB adds far-neighbor exclusion to MultiSWRFDB and combines four design elements hypothesized to improve overall performance.These include far-score exclusion, sigmoid scoring, per-target metric recalculation, and deadband zero weights.

2.3 Updates to scikit-rebate Python package

The scikit-rebate package was updated for greater runtime efficiency and more explicit control over feature and endpoint treatment.

NumPy vector-wide operations refactored feature scoring to achieve significant speedups.
Users can explicitly control whether individual features and endpoints are treated as categorical or quantitative.

2.4 Simulated Benchmark Datasets

The benchmark uses simulated genetic and XOR datasets whose conditions and ground-truth relevance are systematically controlled. Configurations vary association type, feature counts, sample size, heritability, and model difficulty.

Simulation provides known ground truth for relevant and irrelevant features, signal-to-noise ratio, and association type.
77 dataset configurations vary association type, predictive-feature count, total-feature count, instance count, heritability, and architecture difficulty.Configurations also include XOR interactions of 2, 3, 4, or 5 ways.
Table 1 separates primary dataset configurations from secondary ones and identifies simulation sources as GAMETES, custom scripts, or both.

2.5 Experimental Evaluation

The evaluation compares RBA and baseline feature rankings directly against simulated ground truth, using replicate-based percentile power, summary rankings, statistical tests, and runtime measurements.

14 RBA algorithm settings are compared alongside 7 existing RBAs, 5 novel RBAs, Mutual Information, and Random Shuffle.ReliefF and µ-Relief are each evaluated with k=10 and k=100.
Predictive-feature ranking is evaluated directly against non-predictive features, avoiding training/testing splits and downstream-model evaluation.
Success is measured by how often all predictive features appear within each top x% subset across 30 replicates.
Heatmaps encode replicate power by feature percentile, with solid purple indicating all predictive features ranked above non-predictive features in every replicate.
Runtime is recorded for datasets containing 100, 1,000, 10,000, and 100,000 features, while mean and median predictive-feature rankings provide aggregate summaries.
Pairwise algorithm comparisons use Mann-Whitney U and permutation tests with Benjamini-Hochberg FDR adjustment, and global metrics support scenario-specific recommendations.

3 Results

Most RBAs detected 2-way epistasis, with star, deadband, and gradient-scoring methods generally strongest, whereas performance varied substantially for 3-way and higher-order interactions.

2-way Epistasis: Most RBAs performed well on 2-way pure epistasis, with losses under lower heritability, fewer instances, and harder architectures.
2-way Epistasis: MultiSWRFDB* achieved the best 2-way pure-epistasis group mean and median rankings, although its advantage over other star RBAs was small and non-significant.
2-way Epistasis: Most RBAs showed ideal or near-ideal performance on easier 2-way XOR and heterogeneous 2-way interaction configurations, with µ-Relief and ReliefF exceptions in specific settings.
3-way Epistasis: ReliefF and µ-Relief performed best on 3-way XOR, while star RBAs failed; MultiSWRFDB was the only broadly strong RBA across these and other configurations.
4-way and 5-way Epistasis: No examined RBA reliably detected features involved in XOR 4-way or 5-way interactions with 1600 training instances.

3.2 Detecting Univariate Effects

Non-star RBAs were generally strongest for univariate effects, whereas star RBAs became unreliable as feature dimensionality increased. Refactored scikit-rebate implementations also substantially reduced runtime.

Univariate effects: Most non-star RBAs achieved near-ideal performance across 1-feature main-effect configurations, while star RBAs performed significantly worse.ReliefF and µ-Relief were slightly worse than the leading non-star algorithms; star algorithms performed similarly to Random Shuffle on easy, low-heritability datasets.
Univariate effects: All non-star RBAs performed ideally on additive-effect datasets, while star RBAs were less reliable.Algorithms using more near neighbors without far neighbors performed best across these simulations.
Scaling: Beyond 10K features, pure 2-way interaction-ranking reliability progressively decreased, although star RBAs generally outperformed non-star RBAs.MultiSWRFDB* was best at 20K features, MultiSURF* at 50K, and MultiSWRFDB* stood out at 100K, where no RBA consistently ranked both predictive features above the 75th percentile.
Scaling: At 100, 1K, 10K, and 100K features, every non-star RBA and Mutual Information achieved ideal main-effect ranking.Every star RBA declined as feature count increased, reaching Random Shuffle-level performance at and above 10K features.
Runtime: Refactoring scikit-rebate produced 10-35x RBA performance speedups.The speedups were reported for previously benchmarked RBAs.

3.4 Global Metrics for Different Scenarios

Pooled metrics distinguish RBA choices by whether the priority is 2-way epistasis, univariate effects, or a combination that also includes 3-way epistasis. Newly proposed algorithms ranked highest across these scenarios, while secondary datasets exposed failures for star RBAs in one 9-class setting.

2-way epistasis: For 2-way epistasis alone, star RBAs performed best overall, with MultiSWRFDB* ranked highest.The global comparisons pooled predictive-feature ranking metrics across primary datasets.
2-way + univariate: For combined 2-way epistasis and univariate effects, SWRF, MultiSWRF, MultiSURF, and MultiSWRFDB shared closely comparable top performance.Their mean rankings were within 0.05.
Generalized scenario: When 2-way, univariate, and 3-way effects were considered together, MultiSWRFDB performed best because of significantly better 3-way-epistasis performance.This scenario restricted comparison to algorithms already strong on both 2-way epistasis and univariate effects.
Recommendations: MultiSWRFDB*, SWRF, and MultiSWRFDB were the top-ranked algorithms for the three respective use scenarios, and all were newly proposed.MultiSURF* and SWRF* also ranked highly for 2-way epistasis, while MultiSURF ranked highly in the combined scenarios.
Secondary datasets: Most secondary-dataset configurations retained ideal or near-ideal performance, but star RBAs completely failed on the 9-class endpoint configuration.In that configuration, star RBAs regularly assigned predictive features the lowest scores, contradicting earlier reports for MultiSURF* and SURF*.

4 Discussion

The discussion identifies a trade-off between far scoring and main-effect sensitivity, while DB and gradient strategies improve interaction detection without harming univariate performance. Scalability is effective through practical feature-selection thresholds but remains limited at larger dimensions and in untested settings.

Overall findings: Nearly all RBAs detected 2-way epistasis, but no RBA reliably detected 4- or 5-way epistasis.Star RBAs gained a modest advantage for 2-way epistasis while losing substantial univariate-effect sensitivity; non-star RBAs provided a balance.
Scoring strategies: DB and/or gradient scoring improved 2-way-epistasis sensitivity, while their non-star counterparts were the strongest non-star RBAs on those datasets.These scoring elements had negligible impact on univariate-effect detection in the reported comparisons.
Scoring strategies: Minimizing updates from potentially uninformative middle-distance neighbors was associated with better epistasis detection without harming main-effect detection.The strongest global performers used a deadband, gradient scoring, or both.
Neighborhood metrics: Recalculating neighborhood metrics had limited, situation-specific effects, with negligible differences for 2-way epistasis detection.MultiSWRF* showed a slight improvement over SWRF* on univariate effects, although neither performed strongly.
Algorithm-specific findings: µ-Relief failed to detect 2-way epistasis, performed slightly worse on univariate effects, and performed best among RBAs for 3-way epistasis.The authors use this contrast to support broader direct benchmarking of new algorithms on interaction-rich simulations.
Scalability and scope: Most star and non-star RBAs scaled effectively to 10K features, with at least 80% power to rank both pure 2-way interaction features above the 5th percentile.Ideal ranking was observed through 2K features for non-star RBAs and 8K features for star RBAs; future work should examine larger spaces and real-world datasets.

5 Conclusion

The study expands and benchmarks Relief-based algorithms for interaction-sensitive feature selection, identifies scenario-specific recommendations, and accelerates the scikit-rebate package. Its recommendations target 2-way epistasis, univariate effects, and combined interaction settings.

Contributions: The study evaluates 12 RBAs, including 5 novel variants, while expanding and refactoring scikit-rebate.The package additions include SWRF*, µ-Relief, and five newly proposed algorithms, alongside precise discrimination of feature types.
Contributions: Refactoring produced 10-35 fold speedups for RBA implementations.The updated package supports the study’s broader algorithm comparisons and application recommendations.
Recommendations: The recommended algorithms are MultiSWRFDB* for 2-way epistasis, SWRF for 2-way epistasis and/or univariate effects, and MultiSWRFDB for all three effect types.The conclusion separately identifies µ-Relief for 3-way epistasis only.
Scope: The study’s evidence comes from rigorous benchmarking across simulated genomic datasets.The supplied conclusion describes the work as a comprehensive evaluation of RBA variants for interaction-sensitive feature selection.