# On Learning Graphs with Edge-Detecting Queries

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2018.

## Built on by (most cited first, 9 of 9)

- [A Parameterized Theory of PAC Learning](https://mlsanity.com/paper/2304.14058/) (2023)
- [Non-adaptive Learning of Random Hypergraphs with Queries](https://mlsanity.com/paper/2501.12771/) (2025)
- [Learning Partitions with Optimal Query and Round Complexities](https://mlsanity.com/paper/2505.05009/) (2025)
- [A Fast Binary Splitting Approach for Non-Adaptive Learning of ErdHos--R'enyi Graphs](https://mlsanity.com/paper/2511.17240/) (2025)
- [Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle](https://mlsanity.com/paper/2305.13402/) (2023)
- [Concomitant Group Testing](https://mlsanity.com/paper/2309.04221/) (2023)
- [Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs](https://mlsanity.com/paper/2506.08405/) (2025)
- [Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds](https://mlsanity.com/paper/2608.02176/) (2026)
- [Non-Adaptive Learning of Sparse ErdHos--R'enyi Graphs via Affine Splitting](https://mlsanity.com/paper/2609.33704/) (2026)

## Abstract (arXiv)

We consider the problem of learning a general graph G=(V,E) using edge-detecting queries, where the number of vertices |V|=n is given to the learner. The information theoretic lower bound gives mlog n for the number of queries, where m=|E| is the number of edges. In case the number of edges m is also given to the learner, Angluin-Chen's Las Vegas algorithm citeAC08 runs in 4 rounds and detects the edges in O(mlog n) queries. In the other harder case where the number of edges m is unknown, their algorithm runs in 5 rounds and asks O(mlog n+√mlog2 n) queries. There have been two open problems: (i) can the number of queries be reduced to O(mlog n) in the second case, and, (ii) can the number of rounds be reduced without substantially increasing the number of queries (in both cases). For the first open problem (when m is unknown) we give two algorithms. The first is an O(1)-round Las Vegas algorithm that asks mlog n+√m(log[k]n)log n queries for any constant k where log[k]n=log stackrelkcdots log n. The second is an O(log^*n)-round Las Vegas algorithm that asks O(mlog n) queries. This solves the first open problem for any practical n, for example, n<265536. We also show that no deterministic algorithm can solve this problem in a constant number of rounds. To solve the second problem we study the case when m is known. We first show that any non-adaptive Monte Carlo algorithm (one-round) must ask at least Omega(m2log n) queries, and any two-round Las Vegas algorithm must ask at least m4/3-o(1)log n queries on average. We then give two two-round Monte Carlo algorithms, the first asks O(m4/3log n) queries for any n and m, and the second asks O(mlog n) queries when n>2m. Finally, we give a 3-round Monte Carlo algorithm that asks O(mlog n) queries for any n and m.