Clustered low rank approximation of graphs in information science applications

In this paper we present a fast and accurate procedure called clustered low rank matrix approximation for mas-sive graphs. The procedure involves a fast clustering of the graph and then approximates each cluster separately using existing methods, e.g. the singular value decom-position, or stochastic algorithms. The cluster-wise ap-proximations are then extended to approximate the entire graph. This approach has several benefits: (1) important community structure of the graph is preserved due to the clustering; (2) highly accurate low rank approximations are achieved; (3) the procedure is efficient both in terms of computational speed and memory usage; (4) better per-formance in problems from various applications compared to standard low rank approximation. Further, we general-ize stochastic algorithms to the clustered low rank approx-imation framework and present theoretical bounds for the approximation error. Finally, a set of experiments, using large scale and real-world graphs, show that our meth-ods outperform standard low rank matrix approximation algorithms