LEGEND: A Learned Explainable Graph-Enhanced Navigable Index for Hybrid Vector-Graph Search
Open Access
- 30 May 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 18-21
Abstract
We demonstrate LEGEND, a hybrid vector-graph index where knowledge graph structure guides HNSW construction, creating ''semantic shortcuts'' that improve navigation for graph-constrained queries. Unlike TigerVector and NaviX, which treat graph predicates as post-construction filters, LEGEND incorporates KG edges during neighbor selection, achieving 14-18% higher recall. Our system introduces KG-HNSW (reserving HNSW neighbor slots for KG-connected nodes), community-aligned partitioning via Louvain detection, attention-based score fusion with interpretable weight decompositions, and a learned query router selecting among four execution strategies. On FB15K-237 and a 100K-node Amazon product subgraph, LEGEND achieves 0.92 Recall@10 versus 0.78 for TigerVector, with ablations confirming KG-HNSW contributes the largest gain (+12%). Our demonstration enables attendees to visualize semantic shortcuts in real-time, inspect per-result score explanations, and stress-test recall under low-selectivity filters. A demo video is available at https://drive.google.com/file/d/1w1mN-jG69Wr0jOVCAaf_p26EmFhu6yc/view?usp=sharing [HERE].Keywords
This publication has 11 references indexed in Scilit:
- Graph Retrieval-Augmented Generation: A SurveyACM Transactions on Information Systems, 2025
- NaviX: A Native Vector Index Design for Graph DBMSs With Robust Predicate-Agnostic Search PerformanceProceedings of the VLDB Endowment, 2025
- TigerVector: Supporting Vector Search in Graph Databases for Advanced RAGs2025
- DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation GraphProceedings of the ACM on Management of Data, 2025
- ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured DataProceedings of the ACM on Management of Data, 2024
- Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters2023
- Billion-Scale Similarity Search with GPUsIEEE Transactions on Big Data, 2019
- Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World GraphsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2018
- Image-Based Recommendations on Styles and Substitutes2015
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008