Graph Structured Sparse Subset Selection

We propose a new method for variable subset selection and regression coefficient estimation in linear regression models that incorporates a graph structure of the predictor variables. The proposed method is based on the cardinality constraint that controls the number of selected variables and the graph structured subset constraint that encourages the predictor variables adjacent in the graph to be simultaneously selected or eliminated from the model. Moreover, we develop an efficient discrete projected gradient descent method to handle the NP-hardness of the problem originating from the discrete constraints. Numerical experiments on simulated and real-world data are conducted to demonstrate the usefulness and applicability of the proposed method by comparing it with existing graph regularization methods in terms of the predictive accuracy and variable selection performance. The results confirm that the proposed method outperforms the existing methods.