Infinite Feature Selection: A Graph-based Feature Filtering Approach

Giorgio Roffo; Simone Melzi; Umberto Castellani; Alessandro Vinciarelli; Marco Cristani

Source-linked AI summary

Infinite Feature Selection: A Graph-based Feature Filtering Approach

Giorgio Roffo, Simone Melzi, Umberto Castellani, Alessandro Vinciarelli, Marco Cristani

arXiv:2006.08184v1Jun 15, 2020cs.CVcs.LGstat.ML

TL;DR

Feature selection seeks relevant, nonredundant features across challenging data settings. Inf-FS models feature subsets as paths in a weighted graph and evaluates them through power-series and absorbing-Markov-chain interpretations. Across 11 benchmarks, it generally outperforms competitors or achieves second- or third-best performance among 18 comparative approaches.

Problem
Feature selection must reduce dimensionality and improve interpretability while identifying relevant, nonredundant features across heterogeneous settings.
Method
Inf-FS builds a weighted feature graph with customizable pairwise relations and evaluates feature values by aggregating paths of arbitrary length through power-series and absorbing-Markov-chain interpretations.
Results
Across 11 benchmarks, Inf-FS generally outperforms competitors or achieves second- or third-best performance across diverse feature-selection scenarios.
Takeaways & Limitations
Inf-FS provides a flexible feature-selection strategy with automatic thresholding for choosing retained features across heterogeneous settings.
Takeaways & Limitations
The graph formulation uses one of many possible ways to compute joint feature values, and the authors identify end-to-end estimation as future work.

Abstract

from arXiv · show

We propose a filtering feature selection framework that considers subsets of features as paths in a graph, where a node is a feature and an edge indicates pairwise (customizable) relations among features, dealing with relevance and redundancy principles. By two different interpretations (exploiting properties of power series of matrices and relying on Markov chains fundamentals) we can evaluate the values of paths (i.e., feature subsets) of arbitrary lengths, eventually go to infinite, from which we dub our framework Infinite Feature Selection (Inf-FS). Going to infinite allows to constrain the computational complexity of the selection process, and to rank the features in an elegant way, that is, considering the value of any path (subset) containing a particular feature. We also propose a simple unsupervised strategy to cut the ranking, so providing the subset of features to keep. In the experiments, we analyze diverse settings with heterogeneous features, for a total of 11 benchmarks, comparing against 18 widely-known comparative approaches. The results show that Inf-FS behaves better in almost any situation, that is, when the number of features to keep are fixed a priori, or when the decision of the subset cardinality is part of the process.

1 INTRODUCTION

Inf-FS is a graph-based filter that ranks features by evaluating feature subsets as paths of arbitrary, potentially infinite, length. It supports unsupervised and supervised settings and performs competitively across diverse benchmarks.

Framework: Inf-FS represents features as nodes in a fully connected weighted graph, with customizable edge relations encoding relevance and nonredundancy.The framework supports user-crafted pairwise relations among feature distributions.
Framework: Power-series and absorbing-Markov-chain interpretations evaluate feature values across paths of variable length, including paths extending to infinity.The resulting vector assigns each feature a value or probability aggregated over possible path lengths.
Experiments: The framework is compared with 18 feature-selection approaches using an SVM classifier on 11 publicly available benchmarks spanning heterogeneous scenarios.The benchmarks include cancer microarrays, handwritten characters, general classification tasks, and CNN features.
Results: Across scenarios including small samples, high dimensionality, class imbalance, overlap, and noise, Inf-FS generally outperforms competitors or achieves second- or third-best performance.The experiments evaluate both unsupervised and supervised versions.
Results: Inf-FS also provides a simple automatic thresholding strategy for deciding which ranked features to retain and operates on neural features.The paper presents the framework as a general feature-selection strategy across heterogeneous settings.
Contributions: The paper generalizes earlier unsupervised Inf-FS by introducing a supervised counterpart and a Markov-chain-based explanation for subset selection.The contribution extends the prior algebraically motivated formulation.

2 STATE OF THE ART

Feature-selection methods are commonly divided into filters, wrappers, and embedded methods, with filters and wrappers further separated into unsupervised and supervised variants. The paper situates Inf-FS within this taxonomy and emphasizes ranking followed by subset selection.

Method families: Filters evaluate features from intrinsic data properties, wrappers use predictor performance, and embedded methods incorporate selection into model training.The taxonomy distinguishes methods by whether feature evaluation is data-intrinsic, predictor-based, or integrated into learning.
Supervision: Feature-selection techniques are further categorized as unsupervised or supervised according to whether class-label information is used.The paper presents Inf-FS in both settings.
Selection workflow: Many algorithms first rank an initial feature set and then determine the retained subset, commonly through cross-validation on validation data.The paper later contrasts this workflow with its automatic thresholding strategy.

2.1 Filter methods

Filter methods use intrinsic data properties and can be faster and classifier-independent, but they include diverse clustering, mutual-information, graph, and relevance–redundancy approaches with distinct computational trade-offs.

Unsupervised filters: Unsupervised filters include locality- and clustering-based methods such as Laplacian Score, MCFS, and LLCFS.These methods use neighborhood structure, spectral analysis, or clustering-related feature weighting.
Supervised filters: Relief and Relief-F score features using differences between neighboring samples, while mRMR explicitly balances relevance against redundancy.The cited discussion notes that Relief can select redundant subsets and that mRMR relies on joint mutual information.
Supervised filters: Mutual-information methods evaluate feature–class dependencies, whereas Inf-FS extends pairwise reasoning to higher-order feature subsets represented as graph paths.Inf-FS can incorporate inter- and intraclass reasoning through customizable relations.
Graph-based filters: Graph-based alternatives include eigenvector centrality and ILFS, but Inf-FS explicitly crafts graph weights rather than learning them through probabilistic latent semantic analysis.The paper reports that Inf-FS outperforms ILFS in the experiments.
Trade-offs: Filter methods are faster and classifier-independent, but they can have lower performance than supervised approaches because they do not depend on a specific classifier.The paper presents these as general advantages and disadvantages of filters.

2.2 Wrapper approaches

Wrapper approaches select features through classifier performance, often using iterative procedures that can be computationally expensive or unstable. The paper contrasts these properties with Inf-FS’s classifier-agnostic, one-shot filtering design.

Unsupervised approaches: DGUFS, FSASL, and UFSOL use graph, dependence, structure-learning, or locality-based procedures, with iterative methods vulnerable to expense or local minima.The cited comparison characterizes these methods as estimating feature interrelationships iteratively.
Inf-FS contrast: Inf-FS is presented as one-shot and classifier-agnostic, using intrinsic properties of data and labels instead of repeated classifier-driven selection.This contrast is stated against iterative feature-selection methods and wrapper approaches.
Supervised approaches: RFE removes features sequentially using a linear SVM, ranking features according to their contribution to class separation.Several variants address instability by changing elimination, weighting, ensembling, or clustering procedures.
Trade-offs: Wrapper methods can exploit classifier-specific advantages and often achieve higher classification accuracy than filters.Their classifier dependence limits portability and contributes to computational expense.

2.3 Embedded methods

Embedded methods incorporate feature selection into an internal model, including regularized regression, SVM-based approaches, and hard-thresholding strategies. Compared with wrappers, they are described as less prone to over-fitting, while Inf-FS is presented as an independent filter before classification.

Embedded methods include feature selection within an internal regression model, such as L1 or LASSO regularization and decision trees.
Unsupervised approaches: UDFS combines discriminative information and feature correlations through an L2,1-norm regularized objective with orthogonal and locality-preserving constraints.Its non-smooth objective and non-convex constraints make the optimization difficult to solve.
Supervised approaches: SVM-based approaches select features by maximizing a separating margin while reducing dimensions or encouraging sparsity.Examples include FSV and L0 SVMs.
Supervised approaches: LASSO selects variables with non-zero weighting coefficients, while LASSOh and LASSOu adapt it for classification using hinge and unhinged losses.The experiments include both LASSOh and LASSOu as comparative approaches.
Supervised approaches: Hard-thresholding methods such as GraHTP and NHTP use non-convex optimization under strong restricted convexity or smoothness assumptions.NHTP is included as a comparative approach.
Inf-FS differs conceptually from embedded methods because it filters features before a subsequent independent classification step.

3 OUR APPROACH

Inf-FS ranks features by evaluating feature subsets as paths in a weighted graph, using customizable relations that encode relevance and redundancy. Its infinite-path formulation supports feature ranking and an automatic subset-selection strategy, with unsupervised and supervised variants.

Graph construction: Inf-FS offers unsupervised Inf-FSU and supervised Inf-FSS variants built on a weighted, undirected, fully connected graph of feature distributions.Edges model pairwise relations between features, while the supervised variant incorporates class information.
Graph construction: Inf-FSU combines feature dispersion and inverse Spearman correlation, whereas Inf-FSS adds Fisher criterion and mutual information to class-aware scoring.The supervised score also includes normalized standard deviation, with the factors combined linearly.
Scope and limitations: The approach’s measure depends strongly on adjacency-matrix parameters, and its pairwise feature-value formulation is only one possible alternative.The authors identify end-to-end weight estimation as future work and note that the two regularizations produce the same ranking.
Infinite-path evaluation: The method evaluates paths of increasing length through matrix power series or absorbing Markov chains, interpreting scores as feature participation across subsets.The Markov view treats matrix entries as expected visits or transition probabilities associated with feature-selection paths.
Feature ranking: Infinite summation produces final feature scores whose decreasing-order ranking places the most discriminative and relevant features first.The resulting ranking reflects each feature’s importance as a function of the importance of its neighbors.
Subset selection: The automatic selection strategy clusters the distribution of feature scores and retains the cluster containing the first-ranked feature.The authors use one-dimensional mean-shift with automatic bandwidth selection, but report cases where Pareto-like distributions make mean-shift ineffective.

4 EXPERIMENTS AND RESULTS

Across 11 benchmarks and diverse feature-selection settings, Inf-FS is evaluated against established methods for fixed-cardinality and automatic subset selection. The results generally favor Inf-FSU and Inf-FSS, with strong performance, stable rankings, and effective automatic feature-count selection.

Small-sample, high-dimensional challenge: Performance improves until a knee around 50 selected features and generally saturates after 150 features in both supervised and unsupervised settings.Inf-FSU maintains a mild but consistent average advantage among unsupervised methods, while Inf-FSS performs best when selecting 10–100 features.
Supervised versus unsupervised Inf-FS: Inf-FSS generally outperforms Inf-FSU because class-label information guides feature weighting, although the two methods are comparable on COLON, LEUKEMIA, and LUNG.Inf-FSU is nevertheless better than Inf-FSS on MADELON with 10 features, where it discards correlated features.
CNN features: On CNN features, Inf-FSS is among the strongest approaches, while Inf-FSU is more consistent with other unsupervised methods across image-classification settings.For VOC 2007, the supervised Inf-FSS trend is slightly superior to ECFS and improves as more features are added.
Overall ranking: Across datasets, supervised and unsupervised Inf-FS obtain the best average ranks with ranking variance 0.23, indicating stable behavior.Inf-FSS is most effective when few features are selected, whereas Inf-FSU leads among unsupervised methods.
Automatic subset selection: Automatic selection gives Inf-FSU and Inf-FSS higher performance than LASSO on 9 of 11 cases while retaining fewer features than LASSO in most settings.Inf-FSS selects fewer features than Inf-FSU across all datasets under automatic selection, while LASSO unhinged performs poorly in small-sample, high-dimensional settings.

5 CONCLUSIONS

Inf-FS reframes feature selection as path-based regularization on a weighted graph, scoring features through relevance and non-redundancy relations. Its Markov-chain interpretation supports subset selection from score distributions, while pairwise functions allow unsupervised and supervised customization.

Inf-FS models features as nodes in a weighted fully-connected graph, with feature subsets represented as paths of length l.
Each feature receives a score from pairwise functions measuring relevance and non-redundancy.
Under the absorbing Markov-chain interpretation, scores indicate how often a feature is associated with complementary cues before selection ends.
A precise feature subset can be selected by examining the distribution of feature scores.
Inf-FS supports hand-crafted pairwise functions for unsupervised and supervised scenarios, with end-to-end inference of optimal functions left for future work.