Graph Inference with Effective Resistance Queries
Huck Bennett, Mitchell Black, Amir Nayyeri, Evelyn Warton · 2025
Read Graph Inference with Effective Resistance Queries by Huck Bennett, Mitchell Black, Amir Nayyeri, Evelyn Warton (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-18350.txt.
Introduction
Huck Bennett and co-authors learn hidden graphs by asking about electrical resistance. Their 2025 paper deals with graph inference, where an oracle answers queries about a graph no one can see. Their oracle returns effective resistance between two points, a circuit-born distance. All pairs would rebuild a graph outright, but what cheap query sets can test or rebuild stayed open.
Linear-size query sets settle tree checks, graph equality under a nesting promise, and cut point tests. Property testers cover joinedness, two-color form, flatness, and banned shapes. Rebuilders recover graphs from tree-like splits and from near-complete matrices with holes.
Catalog record
| CREATOR | Huck Bennett, Mitchell Black, Amir Nayyeri, Evelyn Warton |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-18350
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graph Inference with Effective Resistance Queries Huck Bennett, Mitchell Black, Amir Nayyeri, Evelyn Warton 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 an n n -vertex graph can be uniquely reconstructed by making all ( n 2 ) = Θ ( n 2 ) \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 ) 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 k -connectivity, bipartiteness, planarity, and containment of a fixed subgraph. 3. Graph reconstruction algorithms, including an algorithm for reconstructing a graph from a low-width tree decomposition; a Θ ( k 2 ) \Theta(k^{2}) -query, polynomial-time algorithm for recovering the entire adjacency matrix A A of the hidden graph, given A A with k k of its entries deleted; and a k k -query, exponential-time algorithm for the same task. 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. 1 Introduction Let G=(V,E) be a hidden graph with n vertices, and let d:V\times V\rightarrow\mathbb{R}^{\geq 0} be a metric on G . We study graph inference problems, where the goal is to reconstruct G or deduce properties of G using a limited number of queries to d . In this work, we focus on the case where d is the effective resistance (ER) metric on G . Graph inference using the ER metric and its close cousin, the shortest path (SP) metric, arises naturally in many applications. Inferring a graph from SP queries has been widely studied in the context of network discovery [ Bee+06 ] , where it is used to map unknown regions of the internet. It is also applied in the reconstruction of evolutionary trees [ Hei89 , KZZ03 , RS07a ] , where understanding evolutionary relationships based on pairwise distances is crucial. On the other hand, ER-based inference is particularly relevant in the study of social network privacy [ Agg14 , Hos+18 ] , where the goal is to assess the potential of revealing hidden network features through random-walk-based queries. Graph inference via SP queries has also been explored extensively from a theoretical perspective, leading to notable algorithmic and lower bound results. For instance, bounded-degree graphs can be reconstructed using \widetilde{O}(n^{3/2}) queries [ KMZ18 ] , and bounded-degree almost-chordal graphs can be reconstructed using O(n\log n) queries [ BG23 ] . On the other hand, \Omega(n^{2}) queries are needed to even reconstruct trees if they are not bounded degree [ RS07 ] . However, the study of graph inference via ER queries is still in its early stages. Beyond the \Theta(n^{2}) -query algorithm that guarantees full reconstruction given all pairwise ER distances (see [ Wit+09 , Spi12 , Hos+18 ] ), little is known that comes with theoretical guarantees. Moreover, the quadratic query complexity needed to reconstruct a whole graph is impractical for large graphs and when the ability to make ER measurements is limited. The focus of this work is to address the corresponding natural question: What properties of a graph can be inferred from a subquadratic number of ER queries? We interpret this question quite generally, and study graph reconstruction, property testing, and more using ER queries. A closely related question asks what the comparative power of SP and ER queries is in the context of machine learning on graphs. In the context of graph neural networks and graph transformers, distance measures such as SP and ER are often used as inputs to the network in the form of positional encodings [ Zha+23 , Vel+24 ] . A primary challenge in graph neural networks is to identify which positional encodings offer the highest expressive power, enabling the model to detect the most properties of a graph. For example, graph transformers using ER as a positional encoding can determine which vertices are cut vertices, while graph transfomers using SP cannot [ Zha+23 ] . While there have been several works aiming to understand and compare the relative expressive power of SP and ER encodings [ Zha+23 , Bla+24 , Vel+24 ] , the capabilities of SP or ER remain only partially understood. A deeper understanding of their potential could lead to better feature selection strategies and improved learning efficiency. 1.1 Our Contribution In this paper, we study a number of fundamental graph inference problems using ER queries. To begin with, we demonstrate that with O(n) ER queries, the following tasks can be performed: (1) Determining whether a graph is a tree ( Theorem 3.3 ). (2) Determining whether two graphs are identical, assuming one is a subgraph of the other. In other words, we can detect if some edges have been added to the graph or if some edges have been deleted, but not both ( Theorem 3.5 ). (3) Deciding whether a given vertex is a cut vertex ( Theorem 3.6 ). (4) Deciding whether a pair of vertices are adjacent with a cut edge ( Theorem 3.8 ). Furthermore, we explore (approximate) property testing of graphs, where our algorithms can distinguish between the case where the graph satisfies a given property and the case where it is \varepsilon -far from satisfying the property, meaning that at least \varepsilon m edge modifications are required to satisfy the property. In this setting, we present the following results: (1) Determining whether a graph is vertex-biconnected or \varepsilon -far from being vertex-biconnected with O(n/\varepsilon) ER queries ( Theorem 4.1 ). (2) Determining whether a graph is edge-biconnected or \varepsilon -far from being edge-biconnected with O(n/\varepsilon^{2}+1/\varepsilon^{4}) ER queries ( Theorem 4.4 ). (3) Showing that for any property that can be tested in f(\varepsilon,n) time in the well-studied bounded-degree model, there is an algorithm to test it for bounded-treewidth graph with f(\varepsilon,n)\cdot n ER queries ( Theorem 4.5 ). As a result, we obtain property testers that require a subquadratic number of ER queries for bounded-treewidth graphs, addressing a range of problems such as the inclusion of a fixed subgraph, k -connectivity, bipartiteness, the presence of long cycles, and any minor-closed