# Nexus: Inferring Join Graphs from Metadata Alone via Iterative Low-Rank Matrix Completion

arXiv: https://arxiv.org/abs/2602.08186 · HTML: https://mlsanity.com/paper/2602.08186/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 34 references that are in the map.
- First posted on arXiv 9 Feb 2026.

## Builds on (most cited first, 7 of 7)

- [Can LLM Already Serve as A Database Interface? A BIg Bench for Large-Scale Database Grounded Text-to-SQLs](https://mlsanity.com/paper/2305.03111/) (2023)
- [Factual Confidence of LLMs: on Reliability and Robustness of Current Estimators](https://mlsanity.com/paper/2406.13415/) (2024)
- [Dataset Discovery in Data Lakes](https://mlsanity.com/paper/2011.10427/) (2020)
- [LSH Ensemble: Internet-Scale Domain Search](https://mlsanity.com/paper/1603.07410/) (2016)
- [Efficient Joinable Table Discovery in Data Lakes: A High-Dimensional Similarity-Based Approach](https://mlsanity.com/paper/2010.13273/) (2020)
- [WarpGate: A Semantic Join Discovery System for Cloud Data Warehouses](https://mlsanity.com/paper/2212.14155/) (2022)
- [Auto-BI: Automatically Build BI-Models Leveraging Local Join Prediction and Global Schema Graph](https://mlsanity.com/paper/2306.12515/) (2023)

## Abstract (arXiv)

Automatically inferring join relationships is a critical task for effective data discovery, integration, querying and reuse. However, accurately and efficiently identifying these relationships in large and complex schemas can be challenging, especially in enterprise settings where access to data values is constrained. In this paper, we introduce the problem of join graph inference when only metadata is available. We conduct an empirical study on a large number of real-world schemas and observe that join graphs when represented as adjacency matrices exhibit two key properties: high sparsity and low-rank structure. Based on these novel observations, we formulate join graph inference as a low-rank matrix completion problem and propose Nexus, an end-to-end solution using only metadata. To further enhance accuracy, we propose a novel Expectation-Maximization algorithm that alternates between low-rank matrix completion and refining join candidate probabilities by leveraging Large Language Models. Our extensive experiments demonstrate that Nexus outperforms existing methods by a significant margin on four datasets including a real-world production dataset. Additionally, Nexus can operate in a fast mode, providing comparable results with up to 6x speedup, offering a practical and efficient solution for real-world deployments.