Iterative methods for low rank approximation of graph similarity matrices
type: Item
instance of: scholarly article
title: Iterative methods for low rank approximation of graph similarity matrices
zbMATH Open document ID: 1264.65060
author: T. P. Cason
author: P.-A. Absil
author: Paul van Dooren
published in: Linear Algebra and its Applications
publication date: 2013-03-06T00:00:00Z
review text: 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\).
reviewed by: Pavel Jiránek
Mathematics Subject Classification ID: 65F20
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 15A03
Mathematics Subject Classification ID: 15A18
zbMATH DE Number: 6142094
zbMATH Keywords: node-to-node similarity
zbMATH Keywords: trace maximization
zbMATH Keywords: low-rank approximation
zbMATH Keywords: set of low-rank matrices
zbMATH Keywords: directed graphs
zbMATH Keywords: similarity matrix
zbMATH Keywords: adjacency matrices
zbMATH Keywords: iterative algorithm
zbMATH Keywords: power method
zbMATH Keywords: truncated singular value decomposition
MaRDI profile type: Publication
full work available at URL: j.laa.2011.12.004
OpenAlex ID: W2179686847
cites work: A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching
cites work: Authoritative sources in a hyperlinked environment
cites work: Optimizing the Coupling Between Two Isometric Projections of Matrices
cites work: Limits of tangent spaces to real surfaces
cites work: Q4943597
cites work: Comparing Two Matrices by Means of Isometric Projections
cites work: Q5433140
cites work: Q4040931
cites work: Error and Perturbation Bounds for Subspaces Associated with Certain Eigenvalue Problems
cites work: Numerical computation of an analytic singular value decomposition of a matrix valued function
cites work: Functions of Matrices
DOI: 10.1016/J.LAA.2011.12.004
description: scientific article; zbMATH DE number 6142094