  How can we analyze enormous networks including the Web and social networks
which have hundreds of billions of nodes and edges? Network analyses have been
conducted by various graph mining methods including shortest path computation,
PageRank, connected component computation, random walk with restart, etc. These
graph mining methods can be expressed as generalized matrix-vector
multiplication which consists of few operations inspired by typical
matrix-vector multiplication. Recently, several graph processing systems based
on matrix-vector multiplication or their own primitives have been proposed to
deal with large graphs; however, they all have failed on Web-scale graphs due
to insufficient memory space or the lack of consideration for I/O costs. In
this paper, we propose PMV (Pre-partitioned generalized Matrix-Vector
multiplication), a scalable distributed graph mining method based on
generalized matrix-vector multiplication on distributed systems. PMV
significantly decreases the communication cost, which is the main bottleneck of
distributed systems, by partitioning the input graph in advance and judiciously
applying execution strategies based on the density of the pre-partitioned
sub-matrices. Experiments show that PMV succeeds in processing up to 16x larger
graphs than existing distributed memory-based graph mining methods, and
requires 9x less time than previous disk-based graph mining methods by reducing
I/O costs significantly.
