Recent advances in graph-based search techniques derived from Kleinberg's work have been impressive. This paper further improves the graph-based search algorithm in two dimensions. Firstly, variants of Kleinberg's techniques do not take into account the semantics of the query string nor of the nodes being searched. As a result, polysemy of query words cannot be resolved. This paper presents an interactive query scheme utilizing the simple web ontology provided by the Open Directory Project to resolve meanings of a user query. Secondly, we extend a recently proposed personalized version of the Kleinberg algorithm. Simulation results are presented to illustrate the sensitivity of our technique. We outline the implementation of our algorithm in the Persona personalized web search system.