  Due to their flexibility to represent almost any kind of relational data,
graph-based models have enjoyed a tremendous success over the past decades.
While graphs are inherently only combinatorial objects, however, many prominent
analysis tools are based on the algebraic representation of graphs via matrices
such as the graph Laplacian, or on associated graph embeddings. Such embeddings
associate to each node a set of coordinates in a vector space, a representation
which can then be employed for learning tasks such as the classification or
alignment of the nodes of the graph. As the geometric picture provided by
embedding methods enables the use of a multitude of methods developed for
vector space data, embeddings have thus gained interest both from a theoretical
as well as a practical perspective. Inspired by trace-optimization problems,
often encountered in the analysis of graph-based data, here we present a method
to derive ellipsoidal embeddings of the nodes of a graph, in which each node is
assigned a set of coordinates on the surface of a hyperellipsoid. Our method
may be seen as an alternative to popular spectral embedding techniques, to
which it shares certain similarities we discuss. To illustrate the utility of
the embedding we conduct a case study in which we analyse synthetic and real
world networks with modular structure, and compare the results obtained with
known methods in the literature.
