RTD-Lite: Scalable Topological Analysis for Comparing Weighted Graphs in Learning Tasks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912276769931264 |
|---|---|
| author | Tulchinskii, Eduard Voronkova, Daria Trofimov, Ilya Burnaev, Evgeny Barannikov, Serguei |
| author_facet | Tulchinskii, Eduard Voronkova, Daria Trofimov, Ilya Burnaev, Evgeny Barannikov, Serguei |
| contents | Topological methods for comparing weighted graphs are valuable in various learning tasks but often suffer from computational inefficiency on large datasets. We introduce RTD-Lite, a scalable algorithm that efficiently compares topological features, specifically connectivity or cluster structures at arbitrary scales, of two weighted graphs with one-to-one correspondence between vertices. Using minimal spanning trees in auxiliary graphs, RTD-Lite captures topological discrepancies with $O(n^2)$ time and memory complexity. This efficiency enables its application in tasks like dimensionality reduction and neural network training. Experiments on synthetic and real-world datasets demonstrate that RTD-Lite effectively identifies topological differences while significantly reducing computation time compared to existing methods. Moreover, integrating RTD-Lite into neural network training as a loss function component enhances the preservation of topological structures in learned representations. Our code is publicly available at https://github.com/ArGintum/RTD-Lite |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_11910 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | RTD-Lite: Scalable Topological Analysis for Comparing Weighted Graphs in Learning Tasks Tulchinskii, Eduard Voronkova, Daria Trofimov, Ilya Burnaev, Evgeny Barannikov, Serguei Machine Learning Artificial Intelligence Symplectic Geometry Topological methods for comparing weighted graphs are valuable in various learning tasks but often suffer from computational inefficiency on large datasets. We introduce RTD-Lite, a scalable algorithm that efficiently compares topological features, specifically connectivity or cluster structures at arbitrary scales, of two weighted graphs with one-to-one correspondence between vertices. Using minimal spanning trees in auxiliary graphs, RTD-Lite captures topological discrepancies with $O(n^2)$ time and memory complexity. This efficiency enables its application in tasks like dimensionality reduction and neural network training. Experiments on synthetic and real-world datasets demonstrate that RTD-Lite effectively identifies topological differences while significantly reducing computation time compared to existing methods. Moreover, integrating RTD-Lite into neural network training as a loss function component enhances the preservation of topological structures in learned representations. Our code is publicly available at https://github.com/ArGintum/RTD-Lite |
| title | RTD-Lite: Scalable Topological Analysis for Comparing Weighted Graphs in Learning Tasks |
| topic | Machine Learning Artificial Intelligence Symplectic Geometry |
| url | https://arxiv.org/abs/2503.11910 |