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 types of graph inference. In this work, we study graph inference using an oracle that returns the effective resistance (ER) between a pair of vertices. Effective resistance is a distance originating from the study of electrical circuits with many applications. However, ER has received little attention from a graph inference perspective. Indeed, although it is known that an $n$-vertex graph can be uniquely reconstructed from all $\binom{n}{2}$ possible ER queries, little else is known. We address this gap with several new results, 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- or edge-biconnected. We also give a reduction to adapt property testing results from the bounded-degree model to our ER query model. This yields ER-query-based algorithms for testing $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 $\Theta(k^2)$-query, polynomial-time algorithm for recovering the adjacency matrix $A$ of a hidden graph, given $A$ with $k$ of its entries deleted; and a $k$-query, exponential-time algorithm for the same task. We also compare the power of ER queries and shortest path queries, which are closely related but better studied. Interestingly, we show that the two query models are incomparable in power.

The distinguishing power of graph transformers is closely tied to the choice of positional encoding: features used to augment the base transformer with information about the graph. There are two primary types of positional encoding: absolute positional encodings (APEs) and relative positional encodings (RPEs). APEs assign features to each node and are given as input to the transformer. RPEs instead assign a feature to each pair of nodes, e.g., graph distance, and are used to augment the attention block. A priori, it is unclear which method is better for maximizing the power of the resulting graph transformer. In this paper, we aim to understand the relationship between these different types of positional encodings. Interestingly, we show that graph transformers using APEs and RPEs are equivalent in terms of distinguishing power. In particular, we demonstrate how to interchange APEs and RPEs while maintaining their distinguishing power in terms of graph transformers. Based on our theoretical results, we provide a study on several APEs and RPEs (including the resistance distance and the recently introduced stable and expressive positional encoding (SPE)) and compare their distinguishing power in terms of transformers. We believe our work will help navigate the huge number of choices of positional encoding and will provide guidance on the future design of positional encodings for graph transformers.

Message passing graph neural networks (GNNs) are a popular learning architectures for graph-structured data. However, one problem GNNs experience is oversquashing, where a GNN has difficulty sending information between distant nodes. Understanding and mitigating oversquashing has recently received significant attention from the research community. In this paper, we continue this line of work by analyzing oversquashing through the lens of the effective resistance between nodes in the input graph. Effective resistance intuitively captures the ``strength'' of connection between two nodes by paths in the graph, and has a rich literature spanning many areas of graph theory. We propose to use total effective resistance as a bound of the total amount of oversquashing in a graph and provide theoretical justification for its use. We further develop an algorithm to identify edges to be added to an input graph to minimize the total effective resistance, thereby alleviating oversquashing. We provide empirical evidence of the effectiveness of our total effective resistance based rewiring strategies for improving the performance of GNNs.

We consider the problem of finding patrol schedules for $k$ robots to visit a given set of $n$ sites in a metric space. Each robot has the same maximum speed and the goal is to minimize the weighted maximum latency of any site, where the latency of a site is defined as the maximum time duration between consecutive visits of that site. The problem is NP-hard, as it has the traveling salesman problem as a special case (when $k=1$ and all sites have the same weight). We present a polynomial-time algorithm with an approximation factor of $O(k^2 \log \frac{w_{\max}}{w_{\min}})$ to the optimal solution, where $w_{\max}$ and $w_{\min}$ are the maximum and minimum weight of the sites respectively. Further, we consider the special case where the sites are in 1D. When all sites have the same weight, we present a polynomial-time algorithm to solve the problem exactly. If the sites may have different weights, we present a $12$-approximate solution, which runs in polynomial time when the number of robots, $k$, is a constant.