Due to the inherent measurement noise in microarray experiments, heterogeneity across samples, and limited sample size, it is often hard to find reliable gene markers for classification. For this reason, several studies proposed to analyze the expression data at the level of groups of functionally related genes such as pathways. One practical problem of these pathway-based approaches is the limited coverage of genes by known pathways. To overcome this problem, we propose a new method for identifying effective subnetwork markers by overlaying the gene expression data with a genome-scale protein-protein interaction network. Experimental results on two independent breast cancer datasets show that the subnetwork markers lead to more accurate classification of breast cancer metastasis and are more reproducible than both gene and pathway markers.