Exact Learning of Weighted Graphs Using Composite Queries
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911275264507904 |
|---|---|
| author | Goodrich, Michael T. Liu, Songyu Panageas, Ioannis |
| author_facet | Goodrich, Michael T. Liu, Songyu Panageas, Ioannis |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_14882 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exact Learning of Weighted Graphs Using Composite Queries Goodrich, Michael T. Liu, Songyu Panageas, Ioannis Data Structures and Algorithms Machine Learning 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. |
| title | Exact Learning of Weighted Graphs Using Composite Queries |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2511.14882 |