Supervised Feature Selection in Graphs with Path Coding Penalties and Network Flows

Abstract

We consider supervised learning problems where the features are embedded in a graph, such as gene expressions in a gene network. In this context, it is of much interest to automatically select a subgraph with few connected components; by exploiting prior knowledge, one can indeed improve the prediction performance or obtain results that are easier to interpret. Regularization or penalty functions for selecting features in graphs have recently been proposed, but they raise new algorithmic challenges. For example, they typically require solving a combinatorially hard selection problem among all connected subgraphs. In this paper, we propose computationally feasible strategies to select a sparse and well-connected subset of features sitting on a directed acyclic graph (DAG). We introduce structured sparsity penalties over paths on a DAG called "path coding" penalties. Unlike existing regularization functions that model long-range interactions between features in a graph, path coding penalties are tractable. The penalties and their proximal operators involve path selection problems, which we efficiently solve by leveraging network flow optimization. We experimentally show on synthetic, image, and genomic data that our approach is scalable and leads to more connected subgraphs than other regularization functions for graphs.

37 pages; to appear in the Journal of Machine Learning Research (JMLR)

References in corpus (6)

• The composite absolute penalties family for grouped and hierarchical variable selection
• Learning with Structured Sparsity
• Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
• Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning
• Optimization with First-Order Surrogate Functions
• Smoothing Proximal Gradient Method for General Structured Sparse Learning

Cited by in corpus (9)

• Convex Relaxation for Combinatorial Penalties
• Network assisted analysis to reveal the genetic basis of autism
• Generalized Conditional Gradient for Sparse Estimation
• Minimum Distance Estimation for Robust High-Dimensional Regression
• Knowledge-Based Distant Regularization in Learning Probabilistic Models
• Graph-based regularization for regression problems with alignment and highly-correlated designs
• Technical Report: Graph-Structured Sparse Optimization for Connected Subgraph Detection
• Automatically Redundant Features Removal for Unsupervised Feature Selection via Sparse Feature Graph
• Parametric Maxflows for Structured Sparse Learning with Convex Relaxations of Submodular Functions