Iterative methods for low rank approximation of graph similarity matrices (Q1940336)

Similarity between two directed graphs introduced by \textit{V. D. Blondel} et al. [SIAM Rev. 46, No. 4, 647--666 (2004; Zbl 1055.05099)] is characterized by a similarity matrix containing certain similarity scores between the vertices of the graphs. It turns out that the similarity matrix can be obtained by an iterative process equivalent to the power method applied to a matrix given by a sum of two Kronecker products involving the adjacency matrices of the given graphs. The similarity matrices are often of low rank. In the present paper, the authors propose two iterative algorithms (which can be considered as a sort of modification of the original power method) which compute rank \(k\) approximations to the similarity matrix (represented in the form of the truncated singular value decomposition) in the set of matrices of unit Frobenius norm. One algorithm considers the feasible set consisting of the matrices with \(k\) identical singular values, while the other algorithm looks for the approximations having at most \(k\) singular values. The algorithms solve certain optimization problems and it is shown that the iterates converge to their respective stationary points. Both methods show improvements in terms of the cost with respect to the original power method in particular for large and sparse graphs. The accuracy of the computed similarity matrices using the first algorithm may be poor due to the fact of restricting the singular values of the candidates to a single value. On the other hand, the second algorithm delivers good approximations with their accuracy consistently improving while increasing the upper bound of the rank \(k\).