Several problems in chemistry can be formulated as classification or regression problems over molecules which, when represented by their planar structure, can be seen as labeled graphs. Several approaches have been proposed recently to define positive definite kernels over labeled graphs, paving the way to the use of powerful kernel methods in chemoinformatics. In this talk I will review some of these approaches and present relevant applications in computational chemistry.