Face images captured in heterogeneous environments, e.g., sketches generated by the artists or composite-generation software, photos taken by common cameras and infrared images captured by corresponding infrared imaging devices, usually subject to large texture (i.e., style) differences. This results in heavily degraded performance of conventional face recognition methods in comparison with the performance on images captured in homogeneous environments. In this paper, we propose a novel sparse graphical representation based discriminant analysis (SGR-DA) approach to address aforementioned face recognition in heterogeneous scenarios. An adaptive sparse graphical representation scheme is designed to represent heterogeneous face images, where a Markov networks model is constructed to generate adaptive sparse vectors. To handle the complex facial structure and further improve the discriminability, a spatial partition-based discriminant analysis framework is presented to refine the adaptive sparse vectors for face matching. We conducted experiments on six commonly used heterogeneous face datasets and experimental results illustrate that our proposed SGR-DA approach achieves superior performance in comparison with state-of-the-art methods.