Graph Structured Sparse Subset Selection

Hyungrok Do, Myun Seok Cheon, Seoung Bum Kim

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)71-94
Number of pages24
JournalInformation Sciences
Publication statusPublished - 2020 May


  • Constrained regression
  • Discrete optimization
  • Graph structure
  • Variable subset selection

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence


Dive into the research topics of 'Graph Structured Sparse Subset Selection'. Together they form a unique fingerprint.

Cite this