Two approaches to low-parametric SimRank computation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915812937302016 |
|---|---|
| author | Berezin, Egor P. Zaks, Robert T. Alekhin, German Z. Morozov, Stanislav V. Matveev, Sergey A. |
| author_facet | Berezin, Egor P. Zaks, Robert T. Alekhin, German Z. Morozov, Stanislav V. Matveev, Sergey A. |
| contents | In this work, we discuss low-parametric approaches for approximating SimRank matrices, which estimate the similarity between pairs of nodes in a graph. Although SimRank matrices and their computation require a significant amount of memory, common approaches mostly address the problem of algorithmic complexity. We propose two major formats for the economical embedding of target data. The first approach adopts a non-symmetric form that can be computed using a specialized alternating optimization algorithm. The second is based on a symmetric representation and Newton-type iterations. We propose numerical implementations for both methodologies that avoid working with dense matrices and maintain low memory consumption. Furthermore, we study both types of embeddings numerically using real data from publicly available datasets. The results show that our algorithms yield a good approximation of the SimRank matrices, both in terms of the error norm (particularly the Chebyshev norm) and in preserving the average number of the most similar elements for each given node. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_20282 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Two approaches to low-parametric SimRank computation Berezin, Egor P. Zaks, Robert T. Alekhin, German Z. Morozov, Stanislav V. Matveev, Sergey A. Numerical Analysis Discrete Mathematics 97N40, 05C50, 05C82, 90B10, 65F99, F.2.1; G.1.3; G.2.2 In this work, we discuss low-parametric approaches for approximating SimRank matrices, which estimate the similarity between pairs of nodes in a graph. Although SimRank matrices and their computation require a significant amount of memory, common approaches mostly address the problem of algorithmic complexity. We propose two major formats for the economical embedding of target data. The first approach adopts a non-symmetric form that can be computed using a specialized alternating optimization algorithm. The second is based on a symmetric representation and Newton-type iterations. We propose numerical implementations for both methodologies that avoid working with dense matrices and maintain low memory consumption. Furthermore, we study both types of embeddings numerically using real data from publicly available datasets. The results show that our algorithms yield a good approximation of the SimRank matrices, both in terms of the error norm (particularly the Chebyshev norm) and in preserving the average number of the most similar elements for each given node. |
| title | Two approaches to low-parametric SimRank computation |
| topic | Numerical Analysis Discrete Mathematics 97N40, 05C50, 05C82, 90B10, 65F99, F.2.1; G.1.3; G.2.2 |
| url | https://arxiv.org/abs/2602.20282 |