relations, similarity relations constitute the underlying relation in many application domains where relations between objects need to be learned. Symmetric relations are formally defined as follows.

A binary relation ${Q}: {\mathcal{V}}^2 \rightarrow [0,1]$ is called a symmetric relation if for all $({v},{v}') \in {\mathcal{V}}^2$ it holds that ${Q}({v},{v}') = {Q}({v}',{v})$.

A binary relation ${h}: {\mathcal{V}}^2 \rightarrow {\mathbb{R}}$ is called a symmetric relation if for all $({v},{v}') \in {\mathcal{V}}^2$ it holds that ${h}({v},{v}') = {h}({v}',{v})$.

Note that $\nabla$ preserves symmetry. For symmetric relations, edges in multi-graphs like Figure \[fig:examples\] become undirected. Applications arise in many domains and metric learning or learning similarity measures can be seen as special cases. If the relation is $2$-valued as $Q: {\mathcal{V}}^2 \rightarrow \{0,1\}$, then we end up with a classification setting instead of a regression setting.

Just like reciprocal relations, it turns out that symmetry can be easily incorporated in our framework.

Let $\Psi$ be a feature mapping on ${\mathcal{V}}^2$ and let ${h}$ be a hypothesis defined by (\[eq:primalmodel\]), then the relation $Q$ of type (\[eq:monmap\]) is symmetric if $\Phi$ is given by $$\Phi_S({e})=\Phi_S({v},{v}')=\Psi({v},{v}')+\Psi({v}',{v}) \,.$$

In addition, by using mathematical properties of the Kronecker product, one obtains in the dual formulation an edge kernel that 