Graph Inference with Effective Resistance Queries

Evelyn Warton, Huck Bennett, Mitchell Black, Amir Nayyeri
Proceedings of The 37th International Conference on Algorithmic Learning Theory, PMLR 313:1-31, 2026.

Abstract

The goal of *graph inference* is to design algorithms for learning properties of a hidden graph using queries to an oracle that returns information about the graph. Graph reconstruction, verification, and property testing are all special cases of graph inference. In this work, we study graph inference using an oracle that returns the *effective resistance* (ER) distance between a given pair of vertices. Effective resistance is a natural notion of distance that arises from viewing graphs as electrical circuits, and has many applications. However, it has received little attention from a graph inference perspective. Indeed, although it is known that any $n$-vertex graph can be uniquely reconstructed by making all $\binom{n}{2} = \Theta(n^2)$ possible ER queries, very little else is known. We address this and show a number of fundamental results in this model, including: 1. $O(n)$-query algorithms for testing whether a graph is a tree; deciding whether two graphs are equal assuming one is a subgraph of the other; and testing whether a given vertex (or edge) is a cut vertex (or cut edge). 2. Property testing algorithms, including for testing whether a graph is vertex-biconnected and whether it is edge-biconnected. We also give a reduction that shows how to adapt property testing results from the well-studied bounded-degree model to our model with ER queries. This yields ER-query-based algorithms for testing $k$-connectivity, bipartiteness, planarity, and containment of a fixed subgraph. 3. Graph reconstruction algorithms. We highlight two $k$-query (provably minimal) algorithms for recovering an entire graph with $k$ missing edge weights: an exact algorithm with an exponential running time for unweighted graphs, and an approximate numerical algorithm with polynomial running time for weighted graphs. We also give a simple, $O(k^2)$-query, polynomial-time algorithm for this problem. Additionally, we give an algorithm for reconstructing a graph from a low-width tree decomposition. We additionally compare the relative power of ER queries and shortest path queries, which are closely related and better studied. Interestingly, we show that the two query models are incomparable in power.

Cite this Paper

BibTeX
@InProceedings{pmlr-v313-warton26a, title = {Graph Inference with Effective Resistance Queries}, author = {Warton, Evelyn and Bennett, Huck and Black, Mitchell and Nayyeri, Amir}, booktitle = {Proceedings of The 37th International Conference on Algorithmic Learning Theory}, pages = {1--31}, year = {2026}, editor = {Telgarsky, Matus and Ullman, Jonathan}, volume = {313}, series = {Proceedings of Machine Learning Research}, month = {23--26 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v313/main/assets/warton26a/warton26a.pdf}, url = {https://proceedings.mlr.press/v313/warton26a.html}, abstract = {The goal of *graph inference* is to design algorithms for learning properties of a hidden graph using queries to an oracle that returns information about the graph. Graph reconstruction, verification, and property testing are all special cases of graph inference. In this work, we study graph inference using an oracle that returns the *effective resistance* (ER) distance between a given pair of vertices. Effective resistance is a natural notion of distance that arises from viewing graphs as electrical circuits, and has many applications. However, it has received little attention from a graph inference perspective. Indeed, although it is known that any $n$-vertex graph can be uniquely reconstructed by making all $\binom{n}{2} = \Theta(n^2)$ possible ER queries, very little else is known. We address this and show a number of fundamental results in this model, including: 1. $O(n)$-query algorithms for testing whether a graph is a tree; deciding whether two graphs are equal assuming one is a subgraph of the other; and testing whether a given vertex (or edge) is a cut vertex (or cut edge). 2. Property testing algorithms, including for testing whether a graph is vertex-biconnected and whether it is edge-biconnected. We also give a reduction that shows how to adapt property testing results from the well-studied bounded-degree model to our model with ER queries. This yields ER-query-based algorithms for testing $k$-connectivity, bipartiteness, planarity, and containment of a fixed subgraph. 3. Graph reconstruction algorithms. We highlight two $k$-query (provably minimal) algorithms for recovering an entire graph with $k$ missing edge weights: an exact algorithm with an exponential running time for unweighted graphs, and an approximate numerical algorithm with polynomial running time for weighted graphs. We also give a simple, $O(k^2)$-query, polynomial-time algorithm for this problem. Additionally, we give an algorithm for reconstructing a graph from a low-width tree decomposition. We additionally compare the relative power of ER queries and shortest path queries, which are closely related and better studied. Interestingly, we show that the two query models are incomparable in power.} }
Endnote
%0 Conference Paper %T Graph Inference with Effective Resistance Queries %A Evelyn Warton %A Huck Bennett %A Mitchell Black %A Amir Nayyeri %B Proceedings of The 37th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Matus Telgarsky %E Jonathan Ullman %F pmlr-v313-warton26a %I PMLR %P 1--31 %U https://proceedings.mlr.press/v313/warton26a.html %V 313 %X The goal of *graph inference* is to design algorithms for learning properties of a hidden graph using queries to an oracle that returns information about the graph. Graph reconstruction, verification, and property testing are all special cases of graph inference. In this work, we study graph inference using an oracle that returns the *effective resistance* (ER) distance between a given pair of vertices. Effective resistance is a natural notion of distance that arises from viewing graphs as electrical circuits, and has many applications. However, it has received little attention from a graph inference perspective. Indeed, although it is known that any $n$-vertex graph can be uniquely reconstructed by making all $\binom{n}{2} = \Theta(n^2)$ possible ER queries, very little else is known. We address this and show a number of fundamental results in this model, including: 1. $O(n)$-query algorithms for testing whether a graph is a tree; deciding whether two graphs are equal assuming one is a subgraph of the other; and testing whether a given vertex (or edge) is a cut vertex (or cut edge). 2. Property testing algorithms, including for testing whether a graph is vertex-biconnected and whether it is edge-biconnected. We also give a reduction that shows how to adapt property testing results from the well-studied bounded-degree model to our model with ER queries. This yields ER-query-based algorithms for testing $k$-connectivity, bipartiteness, planarity, and containment of a fixed subgraph. 3. Graph reconstruction algorithms. We highlight two $k$-query (provably minimal) algorithms for recovering an entire graph with $k$ missing edge weights: an exact algorithm with an exponential running time for unweighted graphs, and an approximate numerical algorithm with polynomial running time for weighted graphs. We also give a simple, $O(k^2)$-query, polynomial-time algorithm for this problem. Additionally, we give an algorithm for reconstructing a graph from a low-width tree decomposition. We additionally compare the relative power of ER queries and shortest path queries, which are closely related and better studied. Interestingly, we show that the two query models are incomparable in power.
APA
Warton, E., Bennett, H., Black, M. & Nayyeri, A.. (2026). Graph Inference with Effective Resistance Queries. Proceedings of The 37th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 313:1-31 Available from https://proceedings.mlr.press/v313/warton26a.html.

Related Material