> > > > is it really the case that you are always finding eigenvectors of a fully > > *dense* > > matrix? The DRM and Lanczos impls in Mahout may really not be terribly > > suited to this use case, if so... >
The transition matrix itself is already pretty sparse. Particularly with images, it's very rare that an arbitrary node has more than 8 connected neighbors (corresponding to the neighboring pixels). While each row of the transition matrix sums to 1 (the probability of moving from the node denoted by the current row to any other node in the graph), most of these transitions will be 0 since there won't be an edge. The algorithm uses a slightly adjusted version of the transition matrix, one which has a more stable eigen-decomposition. It's not quite as sparse as the one I described, but it's pretty close. The lower-rank approximation does make the matrix more sparse, so if you think this is an issue, I could certainly look into it. I just hadn't considered it until now. Shannon
