We prove a remarkable formula for Hodge integrals conjectured by Mari\~{n}o and Vafa, 2002, based on large $N$ duality, using functorial virtual localization on certain moduli spaces of relative stable morphisms.