  We consider the production of gravitons via two photon and electron-photon
fusion in Kaluza-Klein theories which allow TeV scale gravitational
interactions. We show that at electron-positron colliders, the processes l+l-
-> l+ l- graviton, with l=e, mu, can lead to a new signal of low energy gravity
of the form l+l- -> l+l- + missing energy which is well above the Standard
Model background. For example, with two extra dimensions at the Next Linear
Collider with a center of mass energy of 500 or 1000 GeV, hundreds to thousands
such l+ l- graviton events may be produced if the scale of the gravitational
interactions, M_D, is around a few TeV. At a gamma-electron collider, more
stringent bounds may be placed on M_D via the related reaction e^-\gamma -> e^-
graviton. For instance, if a 1TeV electron positron collider is converted to an
electron-photon collider, a bound of ~10TeV may be placed on the scale M_D if
the number of extra dimensions delta=2 while a bound of ~4TeV may be placed if
delta=4.
