Two-sample tests are an important class of problems in statistics, with abundant applications ranging from astrophysics to zoology. However, much of the previous art assumes the data samples live in finite dimensional Euclidean space. Here, we consider a foray into two-sample testing when the objects live in a non-Euclidean space, with special emphasis on graph valued observations. Via embedding each graph into Euclidean space, and then learning a manifold along which the reside, we demonstrate the existence of a test such that for a given confidence level alpha, we obtain power > alpha. Simulations and real data applications demonstrate the pragmatic utility of our approach even for very large graphs.