The　problem　of　face　recognition　was　considered　the　most　popular　topic　in　artificial　intelligence　and　computer　vision.　In　this　paper,　we　investigate　face　recognition　based　on　graph　kernels.　We　define　the　concept　of　max　spanning　tree,　six　graph　kernels　and　a　complicated　kernel　based　on　graph　kernel　and　gray　kernel.　The　result　of　our　experiment　shows　that　our　spanning-tree　kernels　have　significantly　higher　classification　accuracy　than　walk-based　kernels.　©　2010　IEEE.