Shortest path distance approximation using deep learning techniques

• URL: http://arxiv.org/abs/2002.05257v1
• Date: Wed, 12 Feb 2020 21:59:25 GMT
• Title: Shortest path distance approximation using deep learning techniques
• Authors: Fatemeh Salehi Rizi, Joerg Schloetterer, Michael Granitzer
• Abstract summary: 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.
• Score: 0.43461794560295636
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: 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.

Related papers

• Learning the Geodesic Embedding with Graph Neural Networks [22.49236293942187]
  We present GeGnn, a learning-based method for computing the approximate geodesic distance between two arbitrary points on discrete polyhedra surfaces. Our key idea is to train a graph neural network to embed an input mesh into a high-dimensional embedding space. We verify the efficiency and effectiveness of our method on ShapeNet and demonstrate that our method is faster than existing methods by orders of magnitude.
  arXiv  Detail & Related papers  (2023-09-11T16:54:34Z)
• GridPull: Towards Scalability in Learning Implicit Representations from 3D Point Clouds [60.27217859189727]
  We propose GridPull to improve the efficiency of learning implicit representations from large scale point clouds. Our novelty lies in the fast inference of a discrete distance field defined on grids without using any neural components. We use uniform grids for a fast grid search to localize sampled queries, and organize surface points in a tree structure to speed up the calculation of distances to the surface.
  arXiv  Detail & Related papers  (2023-08-25T04:52:52Z)
• Learning Graph Search Heuristics [48.83557172525969]
  We present PHIL (Path Heuristic with Imitation Learning), a novel neural architecture and a training algorithm for discovering graph search and navigations from data. Our function learns graph embeddings useful for inferring node distances, runs in constant time independent of graph sizes, and can be easily incorporated in an algorithm such as A* at test time. Experiments show that PHIL reduces the number of explored nodes compared to state-of-the-art methods on benchmark datasets by 58.5% on average.
  arXiv  Detail & Related papers  (2022-12-07T22:28:00Z)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  We propose FINGER, a fast inference method to achieve efficient graph search. FINGER approximates the distance function by estimating angles between neighboring residual vectors with low-rank bases and distribution matching. Empirically, accelerating a popular graph-based method named HNSW by FINGER is shown to outperform existing graph-based methods by 20%-60% across different benchmark datasets.
  arXiv  Detail & Related papers  (2022-06-22T22:30:46Z)
• GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
  We propose a learnable network to approximate geodesic paths on 3D surfaces. The proposed method provides efficient approximations of the shortest paths and geodesic distances estimations.
  arXiv  Detail & Related papers  (2022-05-30T16:22:53Z)
• Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
  Finding shortest paths in a graph is relevant for numerous problems in computer vision and graphics. We introduce the novel graph-theoretic concept of a shortest path in a graph with matrix-valued edges.
  arXiv  Detail & Related papers  (2021-12-08T08:23:37Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• Isometric Graph Neural Networks [5.306334746787569]
  We propose a technique to learn Isometric Graph Neural Networks (IGNN) IGNN requires changing the input representation space and loss function to enable any GNN algorithm to generate representations that reflect distances between nodes. We observe a consistent and substantial improvement as high as 400% in Kendall's Tau (KT)
  arXiv  Detail & Related papers  (2020-06-16T22:51:13Z)
• Large Batch Training Does Not Need Warmup [111.07680619360528]
  Training deep neural networks using a large batch size has shown promising results and benefits many real-world applications. In this paper, we propose a novel Complete Layer-wise Adaptive Rate Scaling (CLARS) algorithm for large-batch training. Based on our analysis, we bridge the gap and illustrate the theoretical insights for three popular large-batch training techniques.
  arXiv  Detail & Related papers  (2020-02-04T23:03:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.