Traditional mass spectrometry biomarker discovery studies which focus on single biomarkers or a panel of biomarkers have shown their limitations with low reproducibility. In this paper, we propose a novel biomarker motif discovery approach by integrating both mass spectrometry data and protein interaction network information together to identify biomarkers. A novel Bayesian score method is developed to score the protein subnetwork both from the expression of protein and from the protein interaction network structure. Compared with the previous biomarker discovery method, our biomarker motif identification method not only models the expression of each protein, but also the relationship of proteins affected by the protein-protein interaction network. The experiment results show that our proposed biomarker discovery method has a higher sensitivity and lower false discovery rates than previously used methods. When applying our biomarker motifs discovery approach to the real stroke mass spectrometry data, we can identify several biomarker motifs for ischemic stroke which can achieve a higher classification performance with high biological significance.