Carbon-based materials such as graphene sheets and carbon nanotubes have inspired a broad range of applications ranging from high-speed flexible electronics all the way to ultrastrong membranes. However, many of these applications are limited by the complex interactions between carbon-based materials and metals. In this work, we experimentally investigate the structural interactions between graphene and transition metals such as palladium (Pd) and titanium (Ti), which have been confirmed by density functional simulations. We find that the adsorption of titanium on graphene is more energetically favorable than in the case of most metals, and density functional theory shows that a surface induced p-d hybridization occurs between atomic carbon and titanium orbitals. This strong affinity between the two materials results in a short-range ordered crystalline deposition on top of graphene as well as chemical modifications to graphene as seen by Raman and X-ray photoemission spectroscopy (XPS). This induced hybridization is interface-specific and has major consequences for contacting graphene-nanoelectronic devices as well as applications toward metal-induced chemical functionalization of graphene.