To overcome these difficulties, we isometrically embed graphs as points into a Riemannian orbifold in order to apply methods that generalize gradient descent techniques and methods from stochastic optimization for non-convex and nondifferentiable distortion functions.

## 3 Riemannian Orbifolds

Orbifolds generalize the notion of manifold as locally being a quotient of R
n by finite group actions. Consequently, learning on orbifolds generalizes learning on Euclidean spaces and Riemannian manifolds. This section introduces Riemannian orbifolds and their intrinsic metric structure. Proofs for new results are delegated to Section B.1. For all other proofs we refer to [4, 21].

## 3.1 Riemannian Orbifolds

To keep the treatment simple, we assume that X = R
n is the n-dimensional Euclidean vector space, and Γ is a permutation group acting on X . In a more general setting, however, we can assume that X is a Riemannian manifold, and Γ is a finite group of isometries acting effectively on X .

The binary operation
· : Γ *× X → X* , (γ, x) 7→ γ(x)
is a group action of Γ on X . For x ∈ X , the *orbit* of x is the set defined by
[x] = {γ(x) : γ ∈ Γ} .

The quotient set XΓ = X /Γ = {[x] : x *∈ X }*
consisting of all all orbits carries the structure of a *Riemannian orbifold*. Its orbifold chart is the surjective continuous mapping

$\mathbf{a}$ $\mathbf{b}$
π : *X → X*Γ , x 7→ [x]
that projects each point x to its orbit [x].

In the following, an orbifold is a triple Q = (X *, Γ, π*) consisting of an Euclidean space X , a permutation group Γ acting on X and its orbifold chart π.

With Γ = {id} being the trivial permutation group consisting of the identity only, a manifold X is also an orbifold. In general, however, the underlying space XΓ of an orbifold is not a manifold. Thus, orbifolds generalize the notion of manifold. The points at which an orbifold XΓ is locally not homeomorphic to a manifold are its *singular points*. We call the elements of XΓ *structures*, since they represent combinatorial structures like attributed graphs. We use capital letters *X, Y, Z, . . .* to denote structures from XΓ and write, by abuse of notation, x ∈ X if π(x) = X. Each vector x ∈ X is a *vector representation* of structure X and the set X of all vector representation is the *representation space* of XΓ .