Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits

• URL: http://arxiv.org/abs/2405.18680v3
• Date: Thu, 24 Oct 2024 20:21:36 GMT
• Title: Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits
• Authors: Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, Torsten Suel,
• Abstract summary: A graph is navigable if we can successfully move from any starting node to any target node. The important question for applications is if sparser graphs can be constructed. We give a simple and efficient way to construct a navigable graph with average degree $O(sqrtn log n )$ for any set of $n$ points, in any dimension, for any distance function.
• Score: 24.592554830963966
• License:
• Abstract: There has been significant recent interest in graph-based nearest neighbor search methods, many of which are centered on the construction of navigable graphs over high-dimensional point sets. A graph is navigable if we can successfully move from any starting node to any target node using a greedy routing strategy where we always move to the neighbor that is closest to the destination according to a given distance function. The complete graph is navigable for any point set, but the important question for applications is if sparser graphs can be constructed. While this question is fairly well understood in low-dimensions, we establish some of the first upper and lower bounds for high-dimensional point sets. First, we give a simple and efficient way to construct a navigable graph with average degree $O(\sqrt{n \log n })$ for any set of $n$ points, in any dimension, for any distance function. We compliment this result with a nearly matching lower bound: even under the Euclidean metric in $O(\log n)$ dimensions, a random point set has no navigable graph with average degree $O(n^{\alpha})$ for any $\alpha < 1/2$. Our lower bound relies on sharp anti-concentration bounds for binomial random variables, which we use to show that the near-neighborhoods of a set of random points do not overlap significantly, forcing any navigable graph to have many edges.

Related papers

• Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
  We consider the problem of graph searching with prediction recently introduced by Banerjee et al. In this problem, an agent, starting at some $r$ has to traverse a (potentially unknown) graph $G$ to find a hidden goal node $g$. We design algorithms for this search task on unknown graphs.
  arXiv  Detail & Related papers  (2024-02-27T18:12:58Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  We study high-probability regret bounds for adversarial $K$-armed bandits with time-varying feedback graphs over $T$ rounds. We develop an algorithm that achieves the optimal regret $widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$ with high probability. We also develop the first algorithm that achieves the optimal high-probability regret bound for weakly observable graphs.
  arXiv  Detail & Related papers  (2022-10-04T04:36:15Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs) A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data. We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
  arXiv  Detail & Related papers  (2021-11-12T07:08:13Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph.
  arXiv  Detail & Related papers  (2021-10-02T07:41:17Z)
• Improved Reconstruction of Random Geometric Graphs [3.930410971186142]
  We consider the classic model of random geometric graphs where $n$ points are scattered uniformly in a square of area $n$. We use a hybrid of graph distances and short-range estimates based on the number of common neighbors to estimate Euclidean distances. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors.
  arXiv  Detail & Related papers  (2021-07-29T20:37:28Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  We propose a new algorithm for graph matching under probabilistic models. Our algorithm recovers the underlying matching with high probability when $alpha le 1 / (log log n)C$. This improves the condition $alpha le 1 / (log n)C$ achieved in previous work.
  arXiv  Detail & Related papers  (2021-01-28T02:39:27Z)
• Topology-Aware Graph Pooling Networks [51.9008939769679]
  Pooling operations are effective on computer vision and natural language processing tasks. One challenge of performing pooling operations on graph data is the lack of locality that is not well-defined on graphs. We propose the topology-aware pooling (TAP) layer that explicitly considers graph topology.
  arXiv  Detail & Related papers  (2020-10-19T20:14:30Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  We study the algorithmic task of finding a large independent set in a sparse ErdHos-R'enyi random graph. We show that the class of low-degree algorithms can find independent sets of half-optimal size but no larger.
  arXiv  Detail & Related papers  (2020-10-13T17:26:09Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis [7.99536002595393]
  We study the problem of learning the structure of an optimal Bayesian network when additional constraints are posed on the network or on its moralized graph. We show that learning an optimal network with at most $k$ edges in the moralized graph presumably has no $f(k)cdot |I|O(1)$-time algorithm.
  arXiv  Detail & Related papers  (2020-04-30T12:31:13Z)

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.