Colored gravitational instantons, known as Eguchi-Hanson instantons, mediate vacuum-vacuum transitions in an analogous way to the well-known BPST instantons. As a result, a new source of CP-violation is present in gauge theories, described by an additional 'quantum gravity' vacuum angle. This second angle spoils the usual axion as a solution to the strong CP problem. The simplest solution to this issue is to instead introduce two axions, which are necessarily coupled in order to solve the strong CP problem. Such models possess extremely rich and novel phenomenology. In this talk I will summarize the companion axion theory and investigate phenomenology and constraints relating to the axion-photon coupling, with some focus as well on the new two-axion system as dark matter.