Note: [] Corresponding author: Roni Stern, Department of Information System Engineering, Ben Gurion University of the Negev, Beer-Sheva, 84105, Israel. E-mail: [email protected].
Abstract: Solving a problem in an unknown graph requires an agent to iteratively explore parts of the searched graph. Exploring an unknown graph can be very costly, for example, when the exploration requires activating a physical sensor or performing network I/O. In this paper we address the problem of searching for a given input pattern in an unknown graph, while minimizing the number of required exploration actions. This problem is analyzed theoretically. Then, algorithms that choose which part of the environment to explore next are presented. Among these are adaptations of existing algorithms for finding cliques in a known graph as well as a novel heuristic algorithm (Pattern*). Additionally, we investigate how probabilistic knowledge of the existence of edges can be used to further minimize the required exploration. With this additional knowledge we propose a Markov Decision Problem (MDP) formulation and a Monte-Carlo based algorithm (RPattern*) which greatly reduces the total exploration cost. As a case study, we demonstrate how the different heuristic algorithms can be implemented for the k-clique pattern as well as for the complete bipartite pattern. Experimental results are provided that demonstrate the strengths and weaknesses of the proposed approaches on random and scale-free graphs as well as on an online web crawler application searching in Google Scholar. In all the experimental settings we have tried, the proposed heuristic algorithms were able to find the searched pattern with substantially less exploration cost than random exploration.
