# Exact Learning of Weighted Graphs Using Composite Queries

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 32 references that are in the map.
- First posted on arXiv 18 Nov 2025.

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

- [Trace Complexity of Network Inference](https://mlsanity.com/paper/1308.2954/) (2013)
- [Tight query complexity bounds for learning graph partitions](https://mlsanity.com/paper/2112.07897/) (2021)
- [Graph Connectivity and Single Element Recovery via Linear and OR Queries](https://mlsanity.com/paper/2007.06098/) (2020)
- [A Simple Algorithm for Graph Reconstruction](https://mlsanity.com/paper/2112.04549/) (2021)
- [Retrieving Top Weighted Triangles in Graphs](https://mlsanity.com/paper/1910.00692/) (2019)
- [Interplay between Topology and Edge Weights in Real-World Graphs: Concepts, Patterns, and an Algorithm](https://mlsanity.com/paper/2305.09083/) (2023)
- [Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook](https://mlsanity.com/paper/1310.6753/) (2013)
- [Reconstructing a Bounded-Degree Directed Tree Using Path Queries](https://mlsanity.com/paper/1606.05183/) (2016)
- [Reconstructing Biological and Digital Phylogenetic Trees in Parallel](https://mlsanity.com/paper/2006.15259/) (2020)
- [Reconstructing Ultrametric Trees from Noisy Experiments](https://mlsanity.com/paper/2206.07672/) (2022)
- [Exact Learning of Multitrees and Almost-Trees Using Path Queries](https://mlsanity.com/paper/2208.04216/) (2022)
- [Are there graphs whose shortest path structure requires large edge weights?](https://mlsanity.com/paper/2308.13054/) (2023)
- [Reconstruction of geometric random graphs with the Simple algorithm](https://mlsanity.com/paper/2407.18591/) (2024)
- [Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing](https://mlsanity.com/paper/2505.10789/) (2025)

## Abstract (arXiv)

In this paper, we study the exact learning problem for weighted graphs, where we are given the vertex set, V, of a weighted graph, G=(V,E,w), but we are not given E. The problem, which is also known as graph reconstruction, is to determine all the edges of E, including their weights, by asking queries about G from an oracle. As we observe, using simple shortest-path length queries is not sufficient, in general, to learn a weighted graph. So we study a number of scenarios where it is possible to learn G using a subquadratic number of composite queries, which combine two or three simple queries.