  Two-sample feature selection is the problem of finding features that describe
a difference between two probability distributions, which is a ubiquitous
problem in both scientific and engineering studies. However, existing methods
have limited applicability because of their restrictive assumptions on data
distributoins or computational difficulty. In this paper, we resolve these
difficulties by formulating the problem as a sparsest $k$-subgraph problem. The
proposed method is nonparametric and does not assume any specific parametric
models on the data distributions. We show that the proposed method is
computationally efficient and does not require any extra computation for model
selection. Moreover, we prove that the proposed method provides a consistent
estimator of features under mild conditions. Our experimental results show that
the proposed method outperforms the current method with regard to both accuracy
and computation time.
