  We propose a novel graph clustering method guided by additional information
on the underlying structure of the clusters (or communities). The problem is
formulated as the matching of a graph to a template with smaller dimension,
hence matching $n$ vertices of the observed graph (to be clustered) to the $k$
vertices of a template graph, using its edges as support information, and
relaxed on the set of orthonormal matrices in order to find a $k$ dimensional
embedding. With relevant priors that encode the density of the clusters and
their relationships, our method outperforms classical methods, especially for
challenging cases.
