Application of Graph Embeddings to Network Convexity Problems

Graphs exist in a wide range of real-life scenarios, from transportation networks to social media networks. Nowadays, graphs are ubiquitously used for organizing relational information in a human-readable format, displaying the structure of data and patterns in them. However, high computational complexity is the bottleneck of many algorithms on real networks. Graph embedding presents a mapping between the nodes of the graph and vectors in a low-dimensional space conserving the graph's core properties, which is now widely studied for applicability of transforming algorithms on graphs onto well-known vector space. In this paper, we aim to construct embedding preserving network convexity in order to enhance the performance of the convex hull construction algorithms. As a result, we created the algorithm for building the embedding and assessing its quality, as well as evaluated it on different datasets with various parameters. In addition, the algorithm for building convex sets on graphs was proposed and the experiment comparing the speed of the construction of convex sets on both graphs and embedding sets were conducted.