Graph drawing via distortion minimization

Abstract

In recent years, graph signal processing (GSP) has attracted considerable attention due to its ability to process high-dimensional data more eciently. However, in many cases, the graph is not directly available. Thus, the graph needs to be learned by capturing the relationship between data. In many applications, there is a need to reconstruct the original data from the graph, i.e., the graph drawing. One of the challenges in this area is to reconstruct the original data with minimal distortion. Especially for sparse graphs where some edges are missing. There are many existing graph learning and graph drawing algorithms; however, not all of them can properly fit together. One of the problems that slows down the process of precisely drawing a graph is comparing the error in results continuously and choosing the optimum graph drawing algorithm. To overcome this problem, deep learning is a suitable candidate.In this work, we introduced our algorithm to measure the distortion between the original and reconstructed data to evaluate them. The key idea here was to remove rotation and reflection from the distortion measurement. This is because the graph learning step is not able to capture the information of the original data. However, we presented a dierent approach when we employed regression or deep learning models, since the previous approach could destroy our learning process. The idea here was to fix the position of at least two data points before graph learning step.We also implemented dierent existing graph drawing and graph learning schemes and examine which schemes complement each other the best. For the case of k nearest neighbor (k-NN) and multidimensional scaling as a graph learning and graph drawing respectively, we started with a fully connected graph then we increased the sparsity and observed the impact of sparsity on our reconstruction distortion measurement. We employed a regression model and we saw that it can predict with a high precision the number of edges that are required for a k-NN graph with a specific number of nodes, to achieve specific distortion without doing a complex computation.For some of the graph learning and graph drawing algorithms that do not have the same structure in the sense of whether they are similarity-based or distance-based, we use a regression model to fit them together. This will be done by using regression to estimate the corresponding distance elements from distance elements of a graph weight matrix and then feeding it to a distance-based graph drawing scheme.Finally, we employed dierent regressions and our simple deep learning models by defining several layers to work as graph drawing step. Our simple deep learning model showed a better performance compared to the regression models and was capable of handling a slightly larger number of nodes as well as sparser graphs. However, the model is still too simple to handle a huge number of nodes.