Stitching Inner Product and Euclidean Metrics for Topology-aware Maximum Inner Product Search

• URL: http://arxiv.org/abs/2504.14861v2
• Date: Wed, 23 Jul 2025 06:37:06 GMT
• Title: Stitching Inner Product and Euclidean Metrics for Topology-aware Maximum Inner Product Search
• Abstract summary: We introduce a novel graph-based index called Metric-Amphibious Graph (MAG) and a corresponding search algorithm, Adaptive Navigation with Metric Switch (ANMS)<n>Building on these insights, we introduce a novel graph-based index called Metric-Amphibious Graph (MAG) and a corresponding search algorithm, Adaptive Navigation with Metric Switch (ANMS)
• Score: 21.295432955733197
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Maximum Inner Product Search (MIPS) is a fundamental challenge in machine learning and information retrieval, particularly in high-dimensional data applications. Existing approaches to MIPS either rely solely on Inner Product (IP) similarity, which faces issues with local optima and redundant computations, or reduce the MIPS problem to the Nearest Neighbor Search under the Euclidean metric via space projection, leading to topology destruction and information loss. Despite the divergence of the two paradigms, we argue that there is no inherent binary opposition between IP and Euclidean metrics. By stitching IP and Euclidean in the design of indexing and search algorithms, we can significantly enhance MIPS performance. Specifically, this paper explores the theoretical and empirical connections between these two metrics from the MIPS perspective. Our investigation, grounded in graph-based search, reveals that different indexing and search strategies offer distinct advantages for MIPS, depending on the underlying data topology. Building on these insights, we introduce a novel graph-based index called Metric-Amphibious Graph (MAG) and a corresponding search algorithm, Adaptive Navigation with Metric Switch (ANMS). To facilitate parameter tuning for optimal performance, we identify three statistical indicators that capture essential data topology properties and correlate strongly with parameter tuning. Extensive experiments on 12 real-world datasets demonstrate that MAG outperforms existing state-of-the-art methods, achieving up to 4x search speedup while maintaining adaptability and scalability.

Related papers

• LLM-Aided A* Search in Non-Geometric Network Graphs [0.4078247440919473]
  We propose a large language model (LLM)-aided A* algorithm in which an LLM generates intermediate waypoints that guide the A* expansion toward promising graph regions.<n>Our experiments on multiple graph topologies with up to 2,000 nodes demonstrate that LLM reduce the number of expanded nodes by around 50% while incurring only a marginal path cost increase compared to the optimal solution.
  arXiv  Detail & Related papers  (2026-06-22T10:26:35Z)
• MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search [0.9179857807576733]
  MCGI is a geometry-aware and disk-resident indexing method that adapts search strategies to the data's intrinsic geometry.<n> Empirically, MCGI achieves 5.8$times$ higher throughput at 95% recall on high-dimensional GIST1M compared to state-of-the-art DiskANN.<n>On the billion-scale SIFT1B dataset, MCGI further validates its scalability by reducing high-recall query latency by 3$times$, while maintaining performance parity on standard lower-dimensional datasets.
  arXiv  Detail & Related papers  (2026-01-05T09:23:48Z)
• From HNSW to Information-Theoretic Binarization: Rethinking the Architecture of Scalable Vector Search [0.7804710977378487]
  This paper analyzes the architectural limitations of the dominant "HNSW + float32 + cosine similarity" stack.<n>We introduce and empirically evaluate an alternative information-theoretic architecture based on maximally informative binarization (MIB)<n>Results demonstrate retrieval quality comparable to full-precision systems, while achieving substantially lower latency and maintaining constant throughput at high request rates.
  arXiv  Detail & Related papers  (2025-12-16T23:24:37Z)
• Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities [19.352675865525395]
  This paper proposes GATE, high-tier proximity Graph with Adaptive Topology and Query AwarEness.<n>Gate achieves a 1.2-2.0X speed-up in query performance compared to state-of-the-art graph-based indexes.
  arXiv  Detail & Related papers  (2025-06-19T03:07:12Z)
• Retrieval with Learned Similarities [2.729516456192901]
  State-of-the-art retrieval algorithms have migrated to learned similarities.<n>We show that Mixture-of-Logits (MoL) can be realized empirically to achieve superior performance on diverse retrieval scenarios.
  arXiv  Detail & Related papers  (2024-07-22T08:19:34Z)
• The Impacts of Data, Ordering, and Intrinsic Dimensionality on Recall in Hierarchical Navigable Small Worlds [0.09208007322096533]
  Investigation focuses on HNSW's efficacy across a spectrum of datasets. We discover that the recall of approximate HNSW search, in comparison to exact K Nearest Neighbours (KNN) search, is linked to the vector space's intrinsic dimensionality. We observe that running popular benchmark datasets with HNSW instead of KNN can shift rankings by up to three positions for some models.
  arXiv  Detail & Related papers  (2024-05-28T04:16:43Z)
• Minimally Supervised Learning using Topological Projections in Self-Organizing Maps [55.31182147885694]
  We introduce a semi-supervised learning approach based on topological projections in self-organizing maps (SOMs) Our proposed method first trains SOMs on unlabeled data and then a minimal number of available labeled data points are assigned to key best matching units (BMU) Our results indicate that the proposed minimally supervised model significantly outperforms traditional regression techniques.
  arXiv  Detail & Related papers  (2024-01-12T22:51:48Z)
• Efficient Architecture Search via Bi-level Data Pruning [70.29970746807882]
  This work pioneers an exploration into the critical role of dataset characteristics for DARTS bi-level optimization. We introduce a new progressive data pruning strategy that utilizes supernet prediction dynamics as the metric. Comprehensive evaluations on the NAS-Bench-201 search space, DARTS search space, and MobileNet-like search space validate that BDP reduces search costs by over 50%.
  arXiv  Detail & Related papers  (2023-12-21T02:48:44Z)
• Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration [87.53543137162488]
  We propose an easy-to-implement online reinforcement learning (online RL) framework called textttMEX. textttMEX integrates estimation and planning components while balancing exploration exploitation automatically. It can outperform baselines by a stable margin in various MuJoCo environments with sparse rewards.
  arXiv  Detail & Related papers  (2023-05-29T17:25:26Z)
• Towards Meta-learned Algorithm Selection using Implicit Fidelity Information [13.750624267664156]
  IMFAS produces informative landmarks, easily enriched by arbitrary meta-features at a low computational cost. We show it is able to beat Successive Halving with at most half the fidelity sequence during test time.
  arXiv  Detail & Related papers  (2022-06-07T09:14:24Z)
• Pretrained Cost Model for Distributed Constraint Optimization Problems [37.79733538931925]
  Distributed Constraint Optimization Problems (DCOPs) are an important subclass of optimization problems. We propose a novel directed acyclic graph schema representation for DCOPs and leverage the Graph Attention Networks (GATs) to embed graph representations. Our model, GAT-PCM, is then pretrained with optimally labelled data in an offline manner, so as to boost a broad range of DCOP algorithms.
  arXiv  Detail & Related papers  (2021-12-08T09:24:10Z)
• Riemannian classification of EEG signals with missing values [67.90148548467762]
  This paper proposes two strategies to handle missing data for the classification of electroencephalograms. The first approach estimates the covariance from imputed data with the $k$-nearest neighbors algorithm; the second relies on the observed data by leveraging the observed-data likelihood within an expectation-maximization algorithm. As results show, the proposed strategies perform better than the classification based on observed data and allow to keep a high accuracy even when the missing data ratio increases.
  arXiv  Detail & Related papers  (2021-10-19T14:24:50Z)
• ZARTS: On Zero-order Optimization for Neural Architecture Search [94.41017048659664]
  Differentiable architecture search (DARTS) has been a popular one-shot paradigm for NAS due to its high efficiency. This work turns to zero-order optimization and proposes a novel NAS scheme, called ZARTS, to search without enforcing the above approximation. In particular, results on 12 benchmarks verify the outstanding robustness of ZARTS, where the performance of DARTS collapses due to its known instability issue.
  arXiv  Detail & Related papers  (2021-10-10T09:35:15Z)
• ROME: Robustifying Memory-Efficient NAS via Topology Disentanglement and Gradient Accumulation [106.04777600352743]
  Differentiable architecture search (DARTS) is largely hindered by its substantial memory cost since the entire supernet resides in the memory. The single-path DARTS comes in, which only chooses a single-path submodel at each step. While being memory-friendly, it also comes with low computational costs. We propose a new algorithm called RObustifying Memory-Efficient NAS (ROME) to give a cure.
  arXiv  Detail & Related papers  (2020-11-23T06:34:07Z)
• Distributed Optimization, Averaging via ADMM, and Network Topology [0.0]
  We study the connection between network topology and convergence rates for different algorithms on a real world problem of sensor localization. We also show interesting connections between ADMM and lifted Markov chains besides providing an explicitly characterization of its convergence.
  arXiv  Detail & Related papers  (2020-09-05T21:44:39Z)
• Rethinking Performance Estimation in Neural Architecture Search [191.08960589460173]
  We provide a novel yet systematic rethinking of performance estimation (PE) in a resource constrained regime. By combining BPE with various search algorithms including reinforcement learning, evolution algorithm, random search, and differentiable architecture search, we achieve 1, 000x of NAS speed up with a negligible performance drop.
  arXiv  Detail & Related papers  (2020-05-20T09:01:44Z)

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.