  CO$_2$ capture using carbon-based materials, particularly graphene and
graphene-like materials, is a promising strategy to deal with CO$_2$ emissions.
However, significant gaps remain in our understanding of the molecular-level
interaction between CO$_2$ molecules and graphene, particularly, in terms of
chemical bonding and electron transfer. In this work, we employ random
structure search and density functional theory to understand the adsorption of
CO$_2$ molecules on Ca, Sr, Na, K, and Ti decorated graphene surfaces. Compared
to the pristine material, we observe enhanced CO$_2$ adsorption on the
decorated graphene surfaces. Particularly on group 2 metals and titanium
decorated graphene, CO$_2$ can be strongly chemisorbed as a bent CO$_2$ anion
or as an oxalate, depending on the number of CO$_2$ molecules. Electronic
structure analysis reveals the adsorption mechanism to involve an ionic charge
transfer from the metal adatom to the adsorbed CO$_2$. Overall, this study
suggests that reducing CO$_2$ to oxalate on group 2 metals and titanium
metal-decorated graphene surfaces is a potential strategy for CO$_2$ storage.
