Computing and Information Systems - Theses
Permanent URI for this collection
Search Results
1 - 1 of 1
-
ItemEmbedding Graphs for Shortest-Path Distance Predictions( 2020)Graph is an important data structure and is used in an abundance of real-world applications including navigation systems, social networks, and web search engines, just to name but a few. We study a classic graph problem – computing graph shortest-path distances. This problem has many applications, such as finding nearest neighbors for place of interest(POI) recommendation or social network friendship recommendation. To compute a shortest-path distance, traditional approaches traverse the graph to find the shortest path and return the path length. These approaches lack time efficiency over large graphs. In the applications above, the distances may be needed first (e.g., to rank POIs), while the actual shortest paths may be computed later (e.g., after a POI has been chosen). Thus, an alternative approach precomputes and stores the distances, and answers distance queries with simple lookups. This approach, however, falls short in the space cost – O(n^2) in the worst-case for vertices, even with various optimizations. To address these limitations, we take an embedding based approach to predict the shortest-path distance between two vertices using their embeddings without computing their path online or storing their distance offline. Graph embedding is an emerging technique for graph analysis that has yielded strong performance in applications such as node classification, link prediction, graph reconstruction, and more. We propose a representation learning approach to learn a k-dimensional (k<