Efficient Computation of Mean Truncated Hitting Times on Very Large Graphs
This work addresses a computational limitation for researchers and practitioners in graph-based learning, enabling large-scale applications, though it is incremental as it builds on existing hitting time methods.
The paper tackles the computational bottleneck of random walk hitting times on large graphs by developing a new approximation algorithm that enables their use on very large, disk-resident graphs, making applications like collaborative filtering and query suggestion feasible for previously inaccessible problems.
Previous work has shown the effectiveness of random walk hitting times as a measure of dissimilarity in a variety of graph-based learning problems such as collaborative filtering, query suggestion or finding paraphrases. However, application of hitting times has been limited to small datasets because of computational restrictions. This paper develops a new approximation algorithm with which hitting times can be computed on very large, disk-resident graphs, making their application possible to problems which were previously out of reach. This will potentially benefit a range of large-scale problems.