Graph Searching with Predictions

Our first main result is for the (more challenging) exploration problem, for the case of trees.

One application of the above theorem is for the layered graph traversal problem (see §1.3 for a complete definition).

The proof of the above corollary is immediate: Since the input is a tree (with some additional structure that we do not require) that is revealed online, we can use the algorithm from Theorem 1.1. Hence, given an instance $I$ of layered graph traversal (with predictions), we can use the algorithm from Theorem 1.1 in combination with the [BCR22], thereby being both consistent and robust: if the predictions are of high quality, then our algorithm ensures that the cost will be nearly optimal; otherwise if the predictions are useless, [BCR22]’s algorithm gives an upper bound in the worst case.

Moreover, we show that the guarantee obtained in Theorem 1.1 is the best possible, up to constants.

Our next set of results are for the planning problem, where we know the graph and the predictions up-front, and must come up with a strategy with this global information.

Note that result (i) is very similar to that of Theorem 1.1 (for the harder exploration problem): the differences are that we do not lose any constant in the distance $d(r,g)$ term, and also that the algorithm used here (for the planning problem) is simpler. Moreover, the lower bound from Theorem 1.3 continues to hold in the planning setting, since the knowledge of the graph and the predictions does not help the algorithm; hence result (i) is tight.

We do not yet know an analog of result (ii) for the exploration problem: extending Theorem 1.1 to general graphs, even those with bounded doubling metrics remains a tantalizing open problem. Moreover, we currently do not have a lower bound matching result (ii); indeed, we conjecture that a cost of $d(r,g)+2^{O(\alpha)}\cdot|\mathcal{E}|$ should be achievable. We leave these as questions for future investigation.

To get some intuition for the problem, consider the case where given a tree and a guarantee that the goal is at distance $D$ from the start node $r$. Suppose each node $v$ gives the “null” prediction of $f(v)=D+d(r,v)$. In case the tree is a complete binary tree, then these predictions carry no information and we would have to essentially explore all nodes within distance $D$. But note that the predictions for about half of these nodes are incorrect, so these erroneous nodes can pay for this exploration. But now consider a “lopsided” example, with a binary tree on one side of the root, and a path on the other (Figure 1). Suppose the goal is at distance $D$ along the path. In this case, only the path nodes are incorrect, and we only have $O(D+|\mathcal{E}|)=O(D)$ budget for the exploration. In particular, we must explore more aggressively along the path, and balance the exploration on both sides of the root. But such gadgets can be anywhere in the tree, and the predictions can be far more devious than the null-prediction, so we need to generalize this idea.

We start off with a special case which we call the known-distance case. This is almost the same as the general problem, but with the additional guarantee that the prediction of the root is correct. Equivalently, we are given the distance $D:=d(r,g)$ of the goal vertex from the root/starting node $r$. For this setting, we can get the following very sharp result:

Hence in the zero-error case, or in low-error cases where $|\mathcal{E}|\ll D$, the algorithm loses very little compared to the optimal-in-hindsight strategy, which just walks from the root to the goal vertex, and incurs a cost of $D$. This algorithm is inspired by the “lopsided” example above: it not only balances the exploration on different subtrees, but also at multiple levels. To generalize this idea from predictions, we introduce the concepts of anchor and loads (see §2). At a high level, for each node we consider the subtrees rooted at its children, and identify subset of nodes in each of these subtrees which are erroneous depending on which subtree contains the goal $g$. We ensure that these sets have near-equal sizes, so that no matter which of these subtrees contains the goal, one of them can pay for the others. This requires some delicacy, since we need to ensure this property throughout the tree. The details appear in §3.

Having proved Theorem 1.5, we use the algorithm to then solve the problem where the prediction for the root vertex may itself be erroneous. Given Theorem 1.5 and Algorithm 1, we can reduced the problem to finding some node $v$ such that $d(v,g)$ is known; moreover this $v$ must not be very far from the start node $r$. The idea is conceptually simple: as we explore the graph, if most predictions are correct we can use these predictions to find such a $v$, otherwise these incorrect predictions give us more budget to continue exploring. Implementing this idea (and particularly, doing this deterministically) requires us to figure out how to “triangulate” with errors, which we do in §4.

Finally, we give the ideas behind the algorithms for the planning version of the problem. The main idea is to define the implied-error function $\varphi(v):=|\{u\mid f(u)\neq d(u,v)\}|$, which measures the error if the goal is sitting at node $v$. Since we know all the predictions and the tree structure in this version of the problem, and moreover $\phi(g)=|\mathcal{E}|$, it is natural to search the graph greedily in increasing order of the implied-error. However, naively doing this may induce a large movement cost, so we bucket nodes with similar implied-error together, and then show that the total cost incurred in exploring all nodes with $\varphi(v)\approx 2^{i}$ is itself close to $2^{i}$ (times a factor that depends on the degree or the doubling dimension). It remains an interesting open problem to extend this algorithm to broader classes of graphs. The details here appear in §5.

Graph Searching. Graph searching is a fundamental problem, and there are too many variants to comprehensively discuss: we point to the works closest to ours. Baeza-Yates, Culberson, and Rawlins [BYCR93] considered the exploration problem without predictions on the line (where it is also called the “cow-path” problem), on $k$-spiders (i.e., where $k$ semi-infinite lines meet at the root) and in the plane: they showed tight bounds of $9$ on the deterministic competitive ratio of the line, $1+2k^{k}/(k-1)^{k-1}$ for $k$-spiders, among other results. Their lower bounds (given for “monotone-increasing strategies”) were generalized by Jaillet and Stafford [JS01]; [JSG02] point out that the results for $k$-spiders were obtained by Gal [Gal80] before [BYCR93] (see also [AG03]). Kao et al. [KRT96, KMSY98] give tight bounds for both deterministic and randomized algorithms, even with multiple agents.

The layered graph traversal problem [PY91] is very closely related to our model. A tree is revealed over time. At each timestep, some of the leaves of the current tree die, and others have some number of children. The agent is required to sit at one of the current (living) leaves, so if the node the agent previously sat is no longer a leaf or is dead, the agent is forced to move. The game ends when the goal state is revealed and objective is to minimize the total movement cost. The width $k$ of the problem is the largest number of leaves alive at any time (observe that we do not parameterize our algorithm with this parameter). This problem is essentially the cow-path problem for the case of $w=2$, but is substantially more difficult for larger widths. Indeed, the deterministic bounds lie between $\Omega(2^{k})$ [FFK⁺98] and $O(k2^{k})$ [Bur96]. Ramesh [Ram95] showed that the randomized version of this problem has a competitive ratio at least $\Omega(k^{2}/(\log k)^{1+\varepsilon})$ for any $\varepsilon>0$; moreover, his $O(k^{13})$-competitive algorithm was improved to a nearly-tight bound of $O(k^{2}\log\Delta)$ in recent exciting result by Bubeck, Coester, and Rabani [BCR22].

Kalyanasundaram and Pruhs [KP93] study the exploration problem (which they call the searching problem) in the geometric setting of $k$ polygonal obstacles with bounded aspect ratio in the plane. Some of their results extend to the mapping problem, where they must determine the locations of all obstacles. Deng and Papadimitriou [DP99] study the mapping problem, where the goal is to traverse all edges of an unknown directed graph: they give an algorithm with cost $2|E|$ for Eulerian graphs (whereas $OPT=|E|$), and cost $\exp(O(d\log d))|E|$ for graphs with imbalance at most $d$. Deng, Kameda, and Papadimitriou [DKP98] give an algorithm to map two-dimensional rectilinear, polygonal environments with a bounded number of obstacles.

Kalyanasundaram and Pruhs [KP94] consider a different version of the mapping problem, where the goal is to visit all vertices of an unknown graph using a tour of least cost. They give an algorithm that is $O(1)$-competitive on planar graphs. Megow et al. [MMS12] extend their algorithm to graphs with bounded genus, and also show limitations of the algorithm from [KP94].

Blum, Raghavan and Schieber [BRS97] study the point-to-point navigation problem of finding a minimum-length path between two known locations $s$ and $t$ in a rectilinear environment; the obstacles are unknown axis-parallel rectangles. Their $O(\sqrt{n})$-competitiveness is best possible given the lower bound in [PY91]. [KRR94] give lower bounds for randomized algorithms in this setting.

Our work is related in spirit to graph search algorithms like $A^{*}$-search which use score functions to choose the next leaf to explore. One line of work giving provably good algorithms is that of Goldberg and Harrelson [GH05] on computing shortest paths without exploring the entire graph. Another line of work related in spirit to ours is that of Karp, Saks, and Wigderson [KSW86] on branch-and-bound (see also [KZ93]).

Noisy Binary Search. A very closely related line of work is that of computing under noisy queries [FRPU94]. In this widely-used model, the agent can query nodes: each node “points” to a neighbor that is closer to the goal, though some of these answers may be incorrect. Some of these works include [OP06, MOW08, EKS16, DMS19, DTUW19, BFKR21]. Apart from the difference in the information model (these works imagine knowing the entire graph) and the nature of hints (“gradient” information pointing to a better node, instead of information about the quality/score of the node), these works often assume the errors are independent, or adversarial with bounded noise rate. Most of these works allow random-access to nodes and seek to minimize the number of queries instead of the distance traveled, though an exception is the work of [BFKR21]. As far as we can see, the connections between our models is only in spirit. Moreover, we show in §7.3 that results of the kind we prove are impossible if the predictions don’t give us distance information but instead just edge “gradients”.

Algorithms with Predictions. Our work is related to the exciting line of research on algorithms with predictions, such as in ad-allocation [MNS07], auction pricing [MV17], page migration [IMTMR20], flow allocation [LMRX20], scheduling [PSK18, LLMV20, Mit20], frequency estimation [HIKV19], speed scaling [BMRS20], Bloom filters [Mit18], bipartite matching and secretary problems [AGKK20, DLLV21], and online linear optimization [BCKP20].

For an unweighted tree $T$, we define the level of node $v$ with respect to the root $r$ to be $\ell(v):=d(r,v)$, and so level $L$ denotes the set of nodes $v$ such that $d(r,v)=\ell(v)=L$. Since the tree is rooted, there are clearly defined notions of parent and child, ancestor and descendent. Each node is both an ancestor and a descendant of itself. For any node $v$, let $T_{v}$ denote the subtree rooted at $v$. Extending this notation, we define the visited subtree $T^{t}:=T[V_{t}]$, and the extended subtree $\overline{T}^{t}:=T[V_{t}\cup\partial V_{t}]$, and let $T^{t}_{v}$ and $\overline{T}^{t}_{v}$ be the subtrees of $T^{t}$ and $\overline{T}^{t}$ rooted at $v$.

In other words, all nodes which have un-visited descendants (including those in the frontier $\partial V_{t}$) are active. Active nodes are further partitioned into degenerate nodes that have exactly one child subtree that has not been fully visited, and active nodes that have at least two active children. See Fig. 3 for an illustration.

For any node $v\in T$, define its children be $\chi_{i}(v)$ for $i=1,2,\ldots,\Delta_{v}$, where $\Delta_{v}\leq\Delta$ is the number of children for $v$. Note that the order is arbitrary but prescribed and fixed throughout the algorithm. For any time $t$, node $v$, and $i\in[\Delta_{v}]$, define the visited portion of the subtree rooted at the $i^{th}$ child as $C^{t}_{i}(v):=T^{t}_{\chi_{i}(v)}$.

Equipped with the definitions in §3.1, at a high level, the main idea of the algorithm is to balance the loads (as defined in Definition 3.5) of all the nodes $v$. Note that if the goal $g\in C_{i}(v)$, then the nodes $u\in C_{i}(v)$ that have $v$ as their anchor (i.e., $\tau(u)=v$) have erroneous predictions; hence balancing the loads automatically balances the cost and the budget. To balance the loads, we use the definition of a critical node (see Definition 3.6): whenever a node $v$ becomes critical, the algorithm goes back and explores another subtree of $v$, thereby maintaining the balance.

More precisely, our algorithm TreeX-KnownDist does the following: at each time step $t$, it checks whether there is a node that is critical. If there is no such node, the algorithm performs one more step of the current DFS, giving priority to the unexplored child of $v_{t}$ with smallest prediction. On the other hand, if there is a critical node $v$, then this $v$ must be the anchor $\tau(v_{t})$. In this case the algorithm pauses the current DFS, returns to the anchor $\tau(v_{t})$ and resumes the DFS in $\tau(v_{t})$’s child subtree having the smallest load (say $C_{q}(\tau(v_{t}))$). This DFS may have been paused at some time $t^{\prime}<t$, and hence is continued starting at node $v_{t^{\prime}}$. The variable $\operatorname{mem}(v)$ saves the vertex that the algorithm left the subtree rooted on $v$ last time. For example, in this case $\operatorname{mem}(\chi_{q}(\tau(v_{t})))=v_{t^{\prime}}$. If no such time $t^{\prime}$ exists, the algorithm starts a new DFS from some child of $\tau(v_{t})$ whose subtree has the smallest load (in this case, $\operatorname{mem}(\chi_{q}(\tau(v_{t})))=\bot$). The pseudocode appears as Algorithm 1.

A few observations: (a) While $D=d(r,g)$ does not appear explicitly in the algorithm, it is used in the definition of anchors (recall Definition 3.3). Even when $d(r,g)$, the predicted distance at the root, is not the true distance to the goal (as may happen in Section 4), given any input $D$ in Algorithm 1, we will still define $\tau(v)$ to be $v$’s ancestor at level $\alpha(u):=\frac{1}{2}(D+\ell(u)-f(u))$. (b) The new node $v_{t}$ is always on the frontier: i.e., the nodes which are either leaves of $T$ or have unvisited children. Moreover, (c) the memory value $\operatorname{mem}(v)=\bot$ if and only if $v\not\in V_{t}$, else $\operatorname{mem}(v)$ is on the frontier in the subtree below $v$.

The proof of Theorem 3.1 proceeds in two steps. The first step is to show that the total amount of “extra” exploration, i.e., the number of nodes that do not lie on the $r$-$g$ path, is $O(\Delta\cdot|\mathcal{E}|)$. Formally, let $P^{*}$ denote the $r$-$g$ path; for the rest of this section, suppose $g\in C_{1}(v)$ for all $v\in P^{*}$. Define the extra exploration to be the number of nodes visited in the subtrees hanging off this path:

Using the lemmas above (setting $t^{*}$ to be the time $\tau^{*}$ when we reach the goal) proves Theorem 1.5. In the following sections, we now prove Lemmas 3.7 and 3.8.