With the rapid development of Web 2.0 and the Internet of things, predicting relationships in heterogeneous networks has evolved as a heated research topic. Traditionally, people analyze existing relationships in heterogeneous networks that relate in a particular way to a target relationship of interest to predict the emergence of the target relationship. However most existing methods are incapable of systematically identifying relevant relationships useful for the prediction task, especially those relationships involving multiple objects of heterogeneous types, which may not rest on a simple path in the concerned heterogeneous network. Another problem with the current practice is that the existing solutions often ignore the dynamic evolution of the network structure after the introduction of newly emerged relationships. To overcome the first limitation, we propose a new algorithm that can systematically and comprehensively detect relevant relationships useful for the prediction of an arbitrarily given target relationship through a disciplined graph searching process. To address the second limitation, the new algorithm leverages a series of temporally-sensitive features for the relationship occurrence prediction via a supervised learning approach. To explore the effectiveness of the new algorithm, we apply the prototype implementation of the algorithm on the DBLP bibliographic network to predict the author citation relationships and compare the algorithm performance with that of a state-of-the-art peer method and a series of baseline methods. The comparison shows consistently higher prediction accuracy under a range of prediction scenarios.