A Contribution towards Graph Embedding in Symmetric Spaces.

Abstract:

In so-called information age many big data sets have the form of graphs. Using a meaningful embedding into a matching geometric space, it is possible to infer information about the graph from its structure within the embedding space. Due to the natural connection of hierarchical structure and spaces of negative sectional curvature, embedding in hyperbolic space has recently received much attention. Since a graph very often also possesses non-hierarchical structure at the same time, it is promising to consider embedding spaces of non-constant sectional curvature. For this purpose
symmetric spaces of higher rank come into one’s mind. 

In the first part of this thesis an introduction to symmetric spaces is given. As simple cases of symmetric spaces with non-constant sectional curvature, Cartesian products are examined thoroughly with respect to their sectional curvature and totally geodesic submanifolds. By means of Siegel’s upper half-space, the consideration of symmetric spaces is motivated with the versatility of totally geodesic submanifolds contained therein. An implementation of the Riemann gradient descent method is developed.
In the second part, different variants of this optimization algorithm are examined and evaluated using test graphs. Since previous embedding algorithms have considered working with a preprocessed embedding, but have not yet implemented that, this procedure is investigated experimentally. In order to be interpretable, it is essential that the embedding maintains the structure of the graph. Since current optimization methods are not (yet) able to point out this structure reliably, it is suggested that the “entanglement” of the embedded graph is addressed at first such that further
optimization can be successful. Finally, with regard to these results, suggestions are made for a further improvement of these algorithms in order to enable a future implementation of a structure-preserving algorithm to embed graphs in general symmetric spaces.