Shortest path distance approximation using deep learning techniques
This addresses scalability issues in graph processing for applications relying on shortest paths, but it is incremental as it applies existing deep learning techniques to a known bottleneck.
The paper tackles the problem of scaling shortest path distance computations in large graphs by using deep learning to approximate distances with low distortion error, achieving significant speedup on social networks like Facebook and YouTube.
Computing shortest path distances between nodes lies at the heart of many graph algorithms and applications. Traditional exact methods such as breadth-first-search (BFS) do not scale up to contemporary, rapidly evolving today's massive networks. Therefore, it is required to find approximation methods to enable scalable graph processing with a significant speedup. In this paper, we utilize vector embeddings learnt by deep learning techniques to approximate the shortest paths distances in large graphs. We show that a feedforward neural network fed with embeddings can approximate distances with relatively low distortion error. The suggested method is evaluated on the Facebook, BlogCatalog, Youtube and Flickr social networks.