Document Open Access Logo

Graph Searching with Predictions

Authors Siddhartha Banerjee , Vincent Cohen-Addad, Anupam Gupta, Zhouzi Li

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.12.pdf
  • Filesize: 0.93 MB
  • 24 pages

Document Identifiers

Author Details

Siddhartha Banerjee
  • Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA
Vincent Cohen-Addad
  • Google Research, Zürich, Switzerland
Anupam Gupta
  • Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA
Zhouzi Li
  • IIIS, Tsinghua University, Beijing, China

Funding

The authors gratefully acknowledge funding received from the following sources:
  • Banerjee, Siddhartha: NSF: ECCS-1847393, CNS-1955997, ARO: W911NF-19-0217.
  • Gupta, Anupam: NSF awards CCF-1955785, CCF-2006953, and CCF-2224718.

Acknowledgements

Part of this work was done when SB and AG were visitors to the Data-Driven Decision Making program at the Simons Institute for Theoretical Computing in Berkeley.

Cite As Get BibTex

Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, and Zhouzi Li. Graph Searching with Predictions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 12:1-12:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.12

Abstract

Consider an agent exploring an unknown graph in search of some goal state. As it walks around the graph, it learns the nodes and their neighbors. The agent only knows where the goal state is when it reaches it. How do we reach this goal while moving only a small distance? This problem seems hopeless, even on trees of bounded degree, unless we give the agent some help. This setting with "help" often arises in exploring large search spaces (e.g., huge game trees) where we assume access to some score/quality function for each node, which we use to guide us towards the goal. In our case, we assume the help comes in the form of distance predictions: each node v provides a prediction f(v) of its distance to the goal vertex. Naturally if these predictions are correct, we can reach the goal along a shortest path. What if the predictions are unreliable and some of them are erroneous? Can we get an algorithm whose performance relates to the error of the predictions?
In this work, we consider the problem on trees and give deterministic algorithms whose total movement cost is only O(OPT + Δ ⋅ ERR), where OPT is the distance from the start to the goal vertex, Δ the maximum degree, and the ERR is the total number of vertices whose predictions are erroneous. We show this guarantee is optimal. We then consider a "planning" version of the problem where the graph and predictions are known at the beginning, so the agent can use this global information to devise a search strategy of low cost. For this planning version, we go beyond trees and give an algorithms which gets good performance on (weighted) graphs with bounded doubling dimension.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Algorithms with predictions
  • network algorithms
  • graph search

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Steve Alpern and Shmuel Gal. The theory of search games and rendezvous, volume 55 of International series in operations research and management science. Kluwer, 2003. Google Scholar
  2. Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, NeurIPS 2020, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/5a378f8490c8d6af8647a753812f6e31-Abstract.html.
  3. R.A. Baeza-Yates, J.C. Culberson, and G.J.E. Rawlins. Searching in the plane. Information and Computation, 106(2):234-252, 1993. URL: https://doi.org/10.1006/inco.1993.1054.
  4. Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, NeurIPS 2020, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/af94ed0d6f5acc95f97170e3685f16c0-Abstract.html.
  5. Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online learning with imperfect hints. In International Conference on Machine Learning, pages 822-831. PMLR, 2020. Google Scholar
  6. Avrim Blum, Prabhakar Raghavan, and Baruch Schieber. Navigating in unfamiliar geometric terrain. SIAM J. Comput., 26(1):110-137, 1997. URL: https://doi.org/10.1137/S0097539791194931.
  7. Lucas Boczkowski, Uriel Feige, Amos Korman, and Yoav Rodeh. Navigating in trees with permanently noisy advice. ACM Trans. Algorithms, 17(2):15:1-15:27, 2021. URL: https://doi.org/10.1145/3448305.
  8. Sébastien Bubeck, Christian Coester, and Yuval Rabani. Shortest paths without a map, but with an entropic regularizer, 2022. URL: https://doi.org/10.48550/ARXIV.2202.04551.
  9. William R. Burley. Traversing layered graphs using the work function algorithm. J. Algorithms, 20(3):479-511, 1996. URL: https://doi.org/10.1006/jagm.1996.0024.
  10. Argyrios Deligkas, George B. Mertzios, and Paul G. Spirakis. Binary search in graphs revisited. Algorithmica, 81(5):1757-1780, 2019. URL: https://doi.org/10.1007/s00453-018-0501-y.
  11. Xiaotie Deng, Tiko Kameda, and Christos H. Papadimitriou. How to learn an unknown environment I: the rectilinear case. J. ACM, 45(2):215-245, 1998. URL: https://doi.org/10.1145/274787.274788.
  12. Xiaotie Deng and Christos H Papadimitriou. Exploring an unknown graph. Journal of Graph Theory, 32(3):265-297, 1999. Google Scholar
  13. Dariusz Dereniowski, Stefan Tiegel, Przemyslaw Uznanski, and Daniel Wolleb-Graf. A framework for searching in graphs in the presence of errors. In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, volume 69 of OASIcs, pages 4:1-4:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/OASIcs.SOSA.2019.4.
  14. Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In Péter Biró, Shuchi Chawla, and Federico Echenique, editors, EC '21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, pages 409-429. ACM, 2021. URL: https://doi.org/10.1145/3465456.3467623.
  15. Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal. Deterministic and probabilistic binary search in graphs. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 519-532. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897656.
  16. Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with noisy information. SIAM J. Comput., 23(5):1001-1018, 1994. URL: https://doi.org/10.1137/S0097539791195877.
  17. Amos Fiat, Dean P. Foster, Howard J. Karloff, Yuval Rabani, Yiftach Ravid, and Sundar Vishwanathan. Competitive algorithms for layered graph traversal. SIAM J. Comput., 28(2):447-462, 1998. URL: https://doi.org/10.1137/S0097539795279943.
  18. Shmuel Gal. Search games, volume 149 of Mathematics in Science and Engineering. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. Google Scholar
  19. Andrew V. Goldberg and Chris Harrelson. Computing the shortest path: A search meets graph theory. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 156-165. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070455.
  20. Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 534-543. IEEE Computer Society, 2003. URL: https://doi.org/10.1109/SFCS.2003.1238226.
  21. Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In International Conference on Learning Representations, 2019. Google Scholar
  22. Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitrović, and Ronitt Rubinfeld. Online page migration with ml advice. arXiv preprint arXiv:2006.05028, 2020. Google Scholar
  23. Patrick Jaillet and Matthew Stafford. Online searching. Oper. Res., 49(4):501-515, 2001. URL: https://doi.org/10.1287/opre.49.4.501.11227.
  24. Patrick Jaillet, Matthew Stafford, and Shmuel Gal. Note: Online searching / on the optimality of the geometric sequences for the m ray search online searching. Oper. Res., 50(4):744-745, 2002. Google Scholar
  25. Camille Jordan. Sur les assemblages de lignes. J. Reine Angew. Math., 70:185-190, 1869. URL: https://doi.org/10.1515/crll.1869.70.185.
  26. Bala Kalyanasundaram and Kirk Pruhs. A competitive analysis of algorithms for searching unknown scenes. Computational Geometry, 3(3):139-155, 1993. URL: https://doi.org/10.1016/0925-7721(93)90032-2.
  27. Bala Kalyanasundaram and Kirk R Pruhs. Constructing competitive tours from local information. Theoretical Computer Science, 130(1):125-138, 1994. Google Scholar
  28. Ming-Yang Kao, Yuan Ma, Michael Sipser, and Yiqun Lisa Yin. Optimal constructions of hybrid algorithms. J. Algorithms, 29(1):142-164, 1998. URL: https://doi.org/10.1006/jagm.1998.0959.
  29. Ming-Yang Kao, John H. Reif, and Stephen R. Tate. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Inf. Comput., 131(1):63-79, 1996. URL: https://doi.org/10.1006/inco.1996.0092.
  30. Howard J. Karloff, Yuval Rabani, and Yiftach Ravid. Lower bounds for randomized k-server and motion-planning algorithms. SIAM J. Comput., 23(2):293-312, 1994. URL: https://doi.org/10.1137/S0097539792224838.
  31. Richard M. Karp, Michael E. Saks, and Avi Wigderson. On a search problem related to branch-and-bound procedures. In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 19-28. IEEE Computer Society, 1986. URL: https://doi.org/10.1109/SFCS.1986.34.
  32. Richard M. Karp and Yanjun Zhang. Randomized parallel algorithms for backtrack search and branch-and-bound computation. J. ACM, 40(3):765-789, 1993. URL: https://doi.org/10.1145/174130.174145.
  33. Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1859-1877. SIAM, 2020. Google Scholar
  34. Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and instance-robust predictions for online matching, flows and load balancing, 2020. URL: http://arxiv.org/abs/2011.11743.
  35. Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Allocating online advertisement space with unreliable estimates. In Jeffrey K. MacKie-Mason, David C. Parkes, and Paul Resnick, editors, Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, California, USA, June 11-15, 2007, pages 288-294. ACM, 2007. URL: https://doi.org/10.1145/1250910.1250952.
  36. Andrés Muñoz Medina and Sergei Vassilvitskii. Revenue optimization with approximate bid predictions. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1856-1864, 2017. Google Scholar
  37. Nicole Megow, Kurt Mehlhorn, and Pascal Schweitzer. Online graph exploration: New results on old and new algorithms. Theoretical Computer Science, 463:62-72, 2012. URL: https://doi.org/10.1016/j.tcs.2012.06.034.
  38. Michael Mitzenmacher. A model for learned bloom filters, and optimizing by sandwiching. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 462-471, 2018. Google Scholar
  39. Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  40. Shay Mozes, Krzysztof Onak, and Oren Weimann. Finding an optimal tree searching strategy in linear time. In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 1096-1105. SIAM, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347202.
  41. Krzysztof Onak and Pawel Parys. Generalization of binary search: Searching in trees and forest-like partial orders. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 379-388. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/FOCS.2006.32.
  42. Christos H. Papadimitriou and Mihalis Yannakakis. Shortest paths without a map. Theoretical Computer Science, 84(1):127-150, 1991. URL: https://doi.org/10.1016/0304-3975(91)90263-2.
  43. Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems, pages 9661-9670, 2018. Google Scholar
  44. Hariharan Ramesh. On traversing layered graphs on-line. J. Algorithms, 18(3):480-512, 1995. URL: https://doi.org/10.1006/jagm.1995.1019.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact