RTD-Lite: Scalable Topological Analysis for Comparing Weighted Graphs in Learning Tasks
This work addresses a computational bottleneck for researchers and practitioners using topological analysis in machine learning, though it is incremental as it builds on existing methods to improve efficiency.
The paper tackles the problem of computational inefficiency in topological methods for comparing weighted graphs in learning tasks by introducing RTD-Lite, a scalable algorithm that reduces computation time while effectively identifying topological differences, as demonstrated in experiments on synthetic and real-world datasets.
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