Ellipsoidal Embeddings of Graphs

Volume: 85 • Number: 2 • Pages: 413-432

Due to their flexibility to represent almost any kind of relational data, graph-based models have enjoyed 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 that 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 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 in a hyperellipsoid. Our method may be seen as an alternative to popular spectral embedding techniques, with which it shares certain similarities we discuss. To illustrate the utility of the embedding we conduct a case study in which we analyze synthetic and real world networks with modular structure, and compare the results obtained with known methods in the literature.