{"ID":2840217,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.14882","arxiv_id":"2511.14882","title":"Exact Learning of Weighted Graphs Using Composite Queries","abstract":"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.","short_abstract":"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$...","url_abs":"https://arxiv.org/abs/2511.14882","url_pdf":"https://arxiv.org/pdf/2511.14882v1","authors":"[\"Michael T. Goodrich\",\"Songyu Liu\",\"Ioannis Panageas\"]","published":"2025-11-18T20:02:02Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\"]","methods":"[]","has_code":false}