Abstract: This paper illustrates face recognition based on spanning-tree kernels to improve the accuracy of face recognition,defines the concept of max spanning tree,seven spanning-tree kernels and three complicated kernels based on spanning-tree kernel and histogram intersection kernel.Experimental result shows that spanning-tree kernels have significantly higher classification accuracy than walk-based kernels.