Exact Learning of Weighted Graphs Using Composite Queries
Not on the map. Why?
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.
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
14 of 32 references.
References · 14
- 2013Trace Complexity of Network Inferencecited by 8
- 2021Tight query complexity bounds for learning graph partitionscited by 5
- 2020Graph Connectivity and Single Element Recovery via Linear and OR Queriescited by 3
- 2021A Simple Algorithm for Graph Reconstructioncited by 3
- 2019Retrieving Top Weighted Triangles in Graphscited by 2
- 2023Interplay between Topology and Edge Weights in Real-World Graphs: Concepts, Patterns, and an Algorithmcited by 2
- 2013Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebookcited by 1
- 2016Reconstructing a Bounded-Degree Directed Tree Using Path Queriescited by 1
- 2020Reconstructing Biological and Digital Phylogenetic Trees in Parallelcited by 1
- 2022Reconstructing Ultrametric Trees from Noisy Experimentscited by 1
- 2022Exact Learning of Multitrees and Almost-Trees Using Path Queriescited by 1
- 2023Are there graphs whose shortest path structure requires large edge weights?cited by 1
Built on by
Not cited yet.