vector representation of Y . Then the optimal alignment kernel k (*X, Y* ) induced by the standard inner product of X is given by k(*X, Y* ) = max {hx, yi,hγ(x), yi,hx, γ(yi),hγ(x), γ(yi)}
Evaluating the inner products yields hx, yi = h(1, 2),(3, 2)i = 7 hγ(x), yi = h(2, 1),(3, 2)i = 8 hx, γ(y)i = h(1, 2),(2, 3)i = 8 hγ(x), γ(y)i = h(2, 1),(2, 3)i = 7.

Thus, we have k(*X, Y* ) = 8.

Example 3. Suppose that X and Y are attributed graphs where edges have attribute 1 and vertices have attribute 0. The optimal alignment kernel k (*X, Y* )
induced by the standard inner product of X is the number of edges of a maximum common subgraph of X and Y .

Example 4. More generally, if property P1 is satisfied, then any optimal alignment kernel on a bounded set of attributed graphs as defined in (1) is also an optimal assignment kernel of some Riemannian orbifold.

Suppose that X ∈ XΓ . Since k(*X, X*) = hx, xi for all x ∈ X, we can define the *length* of X by l(X) = pk(*X, X*).

The optimal alignment kernel together with the length satisfies the CauchySchwarz inequality |k(X, Y )| ≤ l(X) · l(Y ).

Since the Cauchy-Schwarz inequality is valid, the geometric interpretation of k(·|·) is that it computes the cosine of a well-defined angle between X and X0 provided they are normalized to length 1.

Likewise, k(·|·) gives rise to a distance function defined by d(*X, Y* ) = pl(X)
2 − 2k(*X, Y* ) + l(Y ).

From the definition of k(·|·) follows that d is a metric. In addition, we have d(*X, Y* ) = min {kx − yk : x ∈ X, y ∈ Y }, (3)
where k·k denotes the Euclidean norm induced by the inner product h·, ·i of the Euclidean space X . Example 5. Consider the Riemannian orbifold (X *, Γ, π*) of Example 1 and 2.

Suppose that x = (1, 2) is a vector representation of X and y = (3, 2) is a vector representation of Y . Then the squared lengths of X and Y are l(X)
2 = 5 and l(Y )
2 = 13. Since k(*X, Y* ) = 8 according to Example 2, the distance is d(*X, Y* ) = √5 − 16 + 13 = √2.