In this paper, we propose a novel framework for computational disease stratification based on protein expression tissue images. We extract cellular staining response using color information and create a graph based on morphological features and their spatial distance. This graph is collapsed using a learned dictionary. We then compute the commute time matrix and use it as unique signature per protein and disease grade. We combine protein-based signatures using SVM with an Multiple Kernel Learning approach. We test the proposed framework on a prostate cancer tissue dataset and demonstrate the efficacy of the derived protein signatures for both disease stratification and quantification of the relative importance of each protein.