Parallel SimRank computation on large graphs with iterative aggregation
Key Lab of Data Engineering and Knowledge Engineering of Ministry of Education, China
In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining (2010), pp. 543-552.
@conference{he2010parallel,
title={Parallel SimRank computation on large graphs with iterative aggregation},
author={He, G. and Feng, H. and Li, C. and Chen, H.},
booktitle={Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining},
pages={543–552},
year={2010},
organization={ACM}
}
Recently there has been a lot of interest in graph-based analysis. One of the most important aspects of graph-based analysis is to measure similarity between nodes in a graph. SimRank is a simple and influential measure of this kind, based on a solid graph theoretical model. However, existing methods on SimRank computation suffer from two limitations: 1) the computing cost can be very high in practice; and 2) they can only be applied on static graphs. In this paper, we exploit the inherent parallelism and high memory bandwidth of graphics processing units (GPU) to accelerate the computation of SimRank on large graphs. Furthermore, based on the observation that SimRank is essentially a first-order Markov Chain, we propose to utilize the iterative aggregation techniques for uncoupling Markov chains to compute SimRank scores in parallel for large graphs. The iterative aggregation method can be applied on dynamic graphs. Moreover, it can handle not only the link-updating problem but also the node-updating problem. Extensive experiments on synthetic and real data sets verify that the proposed methods are efficient and effective.
December 6, 2010 by hgpu
